STRUTTURA DELLE RETI SOCIALI MATCHING MARKETS Vincenzo Auletta Università di Salerno MERCATI I mercati sono uno degli esempi più rilevanti di interazioni tra numerosi agenti strutturate come una rete Il mercato crea opportunità per stabilire interazioni tra venditori ed acquirenti ¢ Struttura delle Reti Sociali ¢ Autunno 2012 ¢ Le relazioni tra questi soggetti sono naturalmente codificate tramite una rete Possiamo utilizzare le reti per modellare le interazioni tra i partecipanti al mercato e la teoria dei giochi per prevedere il comportamento dei vari soggetti Gli stessi modelli possono essere utilizzati per studiare le dinamiche sociali all’interno di un gruppo di individui 1 MATCHING MARKETS Matching Markets sono una classe di modelli semplici che consentono di descrivere le interazioni tra diversi soggetti che offrono e cercano beni o servizi Struttura delle Reti Sociali Autunno 2012 ¢ I Modello ampiamente utilizzato e studiato in economia e ricerca operativa ¢ In un matching market ci sono vari oggetti che devono essere assegnati ai partecipanti Ogni partecipante ha le sue personali valutazioni (preferenze) sugli oggetti e si vuole calcolare un’allocazione degli oggetti ai partecipanti che sia socialmente ottima È possibile fissare dei prezzi per i beni in maniera decentralizzata se questo può servire a trovare allocazioni socialmente migliori 2 Autunno 2012 UNA VERSIONE SEMPLIFICATA DEL PROBLEMA ¢ Assumiamo che ogni partecipante può solo specificare quali oggetti gli piacciono Struttura delle Reti Sociali ¢ Es. Abbiamo la lista degli studenti che hanno diritto ad una stanza nella foresteria del campus Dobiamo decidere l’assegnamento delle stanze agli studenti Ogni studente può esprimere le sue preferenze (piano, finestra/ balcone, orientamento, dimensione, ecc.) ¢ Vogliamo trovare un’allocazione (se esiste) che accontenti tutti gli studenti ¢ 3 GRAFO DELLE PREFERENZE Autunno 2012 ¢ Le preferenze espresse dai partecipanti possono essere rappresentate tramite un grafo bipartito Studenti da un lato e stanze dall’altro ¢ Assumiamo stesso numero di studenti e stanze 294 CHAPTER 10. Struttura delle Reti Sociali MATCHING MARKETS Se a i piace la stanza j allora inseriamo l’arco (i, j) Room1 Vikram Room1 Vikram Room2 Wendy Room2 Wendy Room3 Xin Room3 Xin Room4 Yoram Room4 Yoram 4 Room5 Zoe (a) Bipartite Graph Room5 Zoe (b) A Perfect Matching ALLOCAZIONI E MATCHING matching delle stanze agli studenti è un sottoinsieme di archi tali che al più un solo arco incide su ogni nodo del grafo Struttura delle Reti Sociali Autunno 2012 ¢ Un’allocazione ¢ Se il matching contiene tanti archi quanti sono gli studenti allora è un perfect matching CHAPTER 10. MATCHING MARKETS Room1 Vikram Room2 Wendy Room3 Xin Room4 Yoram E’ possibile accontentare tutti gli studenti sse esiste un perfect matching 5 Room5 Zoe (b) A Perfect Matching PERFECT MATCHING ESISTONO SEMPRE? Autunno 2012 ¢ Tutti 296 CHAPTER 10. MATCHING MARKE i grafi bipartiti ammettono un perfect matching? NO Room1 Vikram Room1 Vikram Room2 Wendy Room2 Room3 Xin Room3 Room4 Yoram Room4 Yoram Room5 Zoe Room5 Zoe Struttura delle Reti Sociali Wendy Xin 6 ¢ Quali grafi bipartiti ammettono perfect matching? (a) Bipartite graph with no perfect (b) A constricted matching set demonstrating there is no perfect matching Figure 10.2: (a) A bipartite graph with no perfect matching. (b) A constricted set dem ¢ Autunno 2012 CARATTERIZZAZIONE DI GRAFI BIPARTITI CON PERFECT MATCHING Il grafo della slide precedente non aveva un perfect matching perché ha un constricted set CHAPTER 10. MATCHING MARKETS Insieme di vertici S che ha un insieme di vicini N(S) tali che | S| < |N(S)| N(S) Room1 Vikram Room2 Wendy Room3 Xin Room4 Yoram S Room1 Struttura delle Reti Sociali 296 Vikram MATCHING THEOREM Room2 Wendy (Konig, 1931) Se un grafo bipartito non ha un Room3 Xin perfect matching allora contiene un conscricted set Room4 Yoram 7 Room5 Zoe (a) Bipartite graph with no perfect Room5 Zoe (b) A constricted set demonstrating VALUTAZIONI ED ASSEGNAMENTI OTTIMALI In generale ogni partecipante ha una propria valutazione per ognuno degli oggetti da assegnare vij = valutazione dello studente i sulla stanza j (≥0) Struttura delle Reti Sociali ¢ Autunno 2012 ¢ La qualità di un’assegnamento è data dalla somma dei pesi assegnati ai suoi archi 10.1. BIPARTITE GRAPHS AND PERFECT MATCHINGS 297 Assegnamenti con massimo valore sono socialmente ottimale Valuations Valuations Room1 Xin 12, 2, 4 Room1 Xin 12, 2, 4 Room2 Yoram 8, 7, 6 Room2 Yoram 8, 7, 6 Room3 Zoe 7, 5, 2 Room3 Zoe 7, 5, 2 ¢ L’assegnamento (a) A set of valuations vale 23 ed è ottimale (b) An optimal assignment Figure 10.3: (a) A set of valuations. Each person’s valuations for the objects appears as a list next to them. (b) An optimal assignment with respect to these valuations. 8 Autunno 2012 ASSEGNAMENTI OTTIMALI E PERFECT MATCHING ¢ E’ Struttura delle Reti Sociali possibile utilizzare un algoritmo per il calcolo dell’assegnamento ottimale per trovare un perfect matching Per ogni studente assegniamo 1 agli archi che lo collegano alle stanze preferite e 0 agli altri Se l’allocazione ottimale ha valore n allora è un perfect matching, altrimenti esiste un restricted set ¢ Date le valutazioni degli studenti come è fatta un’allocazione ottimale? Risposta non banale 9 MERCATI Il problema di assegnamento che abbiamo studiato finora era centralizzato ¢ I mercati non prevedono la presenza di un’autorità centrale ¢ Un’amministratore deve assegnare le stanze agli studenti date le loro preferenze Ogni acquirente decide autonomamente cosa comprare sulla base delle sue valutazioni e dei prezzi degli oggetti senza conoscere le valutazioni degli altri acquirenti I prezzi devono sostituire il ruolo dell’autorità centrale E’ possibile fissare dei prezzi in modo tale che degli acquirenti razionali ed egoisti, sulla base delle loro valutazioni, esprimano delle preferenze che portino ad assegnamenti ottimali? Struttura delle Reti Sociali Autunno 2012 ¢ 10 UN ESEMPIO PIÙ CALZANTE che n persone vogliono acquistare una casa e ci sono n case sul mercato ¢ Se ad i viene assegnata la casa j ha un payoff di ui(j)= vij – pj i seleziona i suoi venditori preferiti ¢ ¢ Il Struttura delle Reti Sociali vij è la valutazione di i sulla casa j pj è il prezzo della casa j Autunno 2012 ¢ Supponiamo Quelli che massmimizzano il suo payoff Se ci sono più venditori preferiti ne sceglie uno a caso Se ui(j) < 0 per ogni venditore allora i rinuncia all’aquisto venditore della casa j ha un payoff di uj = pj Guadagna il suo payoff solo se la casa viene venduta 11 ALLOCAZIONI SOCIALMENTE OTTIMALI Vogliamo trovare un’allocazione delle case alle persone che sia socialmente ottimale ¢ Quanto vale un’assegnazione? ¢ Massimizzi la somma dei payoff di tutti i partecipanti (sia acquirenti che venditori) Il payoff dei clienti è dato dalla valutazione della casa acquistata meno il prezzo pagato Il payoff dei venditori è il prezzo a cui ha venduto la casa La somma di tutti i payoff è uguale alla somma delle valutazioni dei clienti che hanno comprato casa Un’assegnamento ottimale massimizza la somma delle valutazioni dei clienti I prezzi non influiscono sul valore dell’assegnamento ma devono rendere possibile tale assegnamento Struttura delle Reti Sociali Autunno 2012 ¢ 12 GRAFO DEI VENDITORI PREFERITI ¢ Il grafo dei venditori preferiti contiene solo i link tra ogni acquirente ed i suoi venditori preferiti Tutti i link adiacenti ad un acquirente hanno lo stesso payoff perfect matching nel grafo dei venditori preferiti rappresenta un assegnamento socialmente ottimale Struttura delle Reti Sociali i prezzi degli oggetti ogni acquirente prenderà in considerazione solo le offerte dei suoi venditori preferiti Autunno 2012 ¢ Dati ¢ Ogni 13 PREZZI MARKET CLEARING ¢ Idea: ¢ Se più acquirenti sono in competizione per la stessa casa il prezzo può servire per dissuadere quelli che hanno minori valutazioni e convincerli a fare altre scelte Struttura delle Reti Sociali insieme di prezzi è market clearing se nel grafo dei venditori preferiti indotto esiste un perfect matching Autunno 2012 ¢ Un L’assegnamento potrebbe richiedere un minimo d coordinamento tra gli acquirenti ¢ Ognuno ¢ Ognuno dovrebbe fare un’offerta per una casa diversa farà comunque un’offerta ad un venditore preferito e quindi massimizzerà il suo payoff 14 10.3.E PRICES AND THE MARKET-CLEARING PROPERTY UN SEMPIO Prices Sellers Buyers 5 a x 12, 4, 2 8, 7, 6 2 b y 8, 7, 6 7, 5, 2 0 c z 7, 5, 2 a x 12, 4, 2 b y c z Valuations (a) Buyer Valuations Valuations (b) Market-Clearing Prices Sellers Buyers 2 a x 12, 4, 2 3 a x 12, 4, 2 1 b y 8, 7, 6 1 b y 8, 7, 6 0 c z 7, 5, 2 0 c z 7, 5, 2 Valuations Prices Sellers Buyers Valuations Struttura delle Reti Sociali Buyers Autunno 2012 Sellers Prices 301 15 (c) Prices that Don’t Clear the Market (d) Market-Clearing Prices (Tie-Breaking Required) Figure 10.5: (a) Three sellers (a, b, and c) and three buyers (x, y, and z). For each buyer node, the valuations for the houses of the respective sellers appear in a list next to the node. (b) Each buyer creates a PROPRIETÀ DEI PREZZI MARKET CLEARING precedente siamo riusciti a trovare dei prezzi marlet clearing generale cosa succede? ESISTENZA DEI PREZZI MARKET CLEARING Per ogni insieme di valutazioni degli acquirenti esiste un insieme di prezzi degli oggetti che sono market clearing OTTIMALITA’ DEI PREZZI MARKET CLEARING Per ogni insieme di prezzi market clearing ogni assegnamento associato ad un perfect matching del grafo dei venditori preferiti è socialmente ottimo Struttura delle Reti Sociali ¢ In Autunno 2012 ¢ Nell’esempio 16 COME TROVARE PREZZI MARKET CLEARING? La procedura per trovare i prezzi market clearing utilizza un meccanismo di asta ¢ Algoritmo: 1. 2. 3. 4. Inizialmente tutti I prezzi sono 0 Ad ogni round I prezzi sono scalati in modo che il prezzo minimo sia 0 Ogni acquirente sceglie I suoi venditori preferiti Se il grafo dei venditori preferiti non ha un perfect matching deve esistere un constricted set S 1. 5. 6. Struttura delle Reti Sociali Diversa da quelle single-item studiate nella lezione precedente Descritta dagli economisti Demange, Gale e Sotomayor (1986) ma equivalente ad una costruzione ideata da Egervary (1916) Autunno 2012 ¢ Insieme di acquirenti che sono interessati alle stesse case I prezzi di tutti gli oggetti in N(S) vengono incrementati di 1 e si torna a (2) Se esiste un perfect matching si restituiscono I prezzi market clearing 17 10.4. CONSTRUCTING A SET OF MARKET-CLEARING PRICES U N ESEMPIO Sellers Buyers 1 a x 12, 4, 2 8, 7, 6 0 b y 8, 7, 6 7, 5, 2 0 c z 7, 5, 2 0 a x 12, 4, 2 0 b y 0 c z Valuations Prices (a) Start of first round Valuations (b) Start of second round Prices Sellers Buyers Valuations Sellers Buyers 2 a x 12, 4, 2 3 a x 12, 4, 2 0 b y 8, 7, 6 1 b y 8, 7, 6 0 c z 7, 5, 2 0 c z 7, 5, 2 Prices Valuations (c) Start of third round (d) Start of fourth round Figure 10.6: The auction procedure applied to the example from Figure 10.5. Each separate picture shows steps (i) and (ii) of successive rounds, in which the preferred-seller graph for that round is constructed. Struttura delle Reti Sociali Buyers Autunno 2012 Sellers Prices 305 18 PERCHÈ LA PROCEDURA TERMINA? ¢ Usiamo la tecnica del potenziale ¢ Il potenziale del gioco è sempre non-negativo ¢ Potenziale dell’acquirente = massimo payoff dati i prezzi Potenziale del venditore = prezzo di vendita Inizialmente I prezzi sono tutti 0 ed il potenziale del gioco è dato dalla somma dei massimi delle valutazioni degli acquirenti Struttura delle Reti Sociali Per ogni insieme di prezzi definiamo il potenziale del gioco come la somma dei potenziali dei giocatori Autunno 2012 ¢ Ad ogni round alcuni prezzi vengono incrementati i payoff degli acquirenti interessati a quegli oggetti diminuiscono della stessa quantità Poiché il numero di prezzi incrementati è superiore a quello degli acquirenti interessati il potenziale del gioco diminuisce Poiché il potenziale è sempre non-negativo dopo un numero finito di iterazioni dobbiamo trovare un insieme di prezzi market clearing 19 ¢ Che relazione c’è tra prezzi market clearing e le aste per singolo-item della lezione precedente? rappresentare il problema dell’asta come un problema di matching market Il grafo bipartito ha n acquirenti e n oggetti in vendita 1 reale e gli altri n-1 fittizi La valutazione di ogni acquirente per gli oggetti fittizi è 0 Struttura delle Reti Sociali ¢ Possiamo Autunno 2012 RELAZIONE TRA PREZZI MARKET CLEARING ED ASTE ¢ La procedura per la ricerca dei prezzi market clearing equivale ad un’asta ascendente Il bene è aggiudicato all’acquirente con ala valutazione più alta e paga la seconda valutazione più alta 20
© Copyright 2024 ExpyDoc
