Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano...

47
Introduzione Implementazione nel caso ad informazione completa Formalizzazione Truthful implementation e revelation principle Esempio di Re Salomone Implementazione in equilibrio di Nash Bayesiano Introduzione alla teoria dell’implementazione Silvia Villa Dipartimento di Matematica Università di Genova [email protected] Almo Collegio Borromeo Pavia, 16 Aprile 2008 S. Villa Introduzione alla teoria dell’implementazione

Transcript of Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano...

Page 1: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Introduzione alla teoria dell’implementazione

Silvia Villa

Dipartimento di MatematicaUniversità di Genova

[email protected]

Almo Collegio BorromeoPavia, 16 Aprile 2008

S. Villa Introduzione alla teoria dell’implementazione

Page 2: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Outline

1 Introduzione

2 Implementazione nel caso ad informazione completa

3 Formalizzazione

4 Truthful implementation e revelation principle

5 Esempio di Re Salomone

6 Implementazione in equilibrio di Nash Bayesiano

S. Villa Introduzione alla teoria dell’implementazione

Page 3: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Bibliografia

Quanto segue è basato su:F. Patrone, “Implementazione con breve introduzione allescelte sociali e con l’esempio di Re Salomone”, all’indirizzo

www.diptem.unige.it/patrone

M. Osborne-A. Rubinstein, “A course in game theory”(cap.10).

S. Villa Introduzione alla teoria dell’implementazione

Page 4: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Esempio

Un pianificatore vuole assegnare un oggetto a uno tra dueindividui. Supponiamo che il pianificatore voglia dare l’oggettoa colui che lo valuta di più, ma non conosca le valutazioni deidue individui. Il suo problema è inventare un meccanismo conla proprietà che, per ogni coppia di valutazioni possibili, assegnil’oggetto all’individuo che lo valuta di più.

S. Villa Introduzione alla teoria dell’implementazione

Page 5: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Introduzione

Dati:un insieme di individui (giocatori) N = {1, . . . , n}un insieme di possibili alternative Ale preferenze di ogni individuo sugli elementi di A

S. Villa Introduzione alla teoria dell’implementazione

Page 6: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Social choice rule

Mettendo assieme le preferenze di ciascun individuo %i sicostruisce un profilo di preferenze (%1, . . . ,%n). Chiamiamo Pl’insieme dei possibili profili. E’ data una

social choice rule

ovverof : P ⇒ A

che ad ogni profilo di preferenze associa un sottoinsieme nonvuoto di A.

S. Villa Introduzione alla teoria dell’implementazione

Page 7: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Problema dell’implementazione:

Un pianificatore deve inventare un gioco, in una classe digiochi ammissibili G, che implementi la social choice rule,ovvero in modo che il risultato del gioco giocato dai giocatoricon le loro preferenze sia l’insieme di alternative previste dallasocial choice rule.

S. Villa Introduzione alla teoria dell’implementazione

Page 8: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Osservazioni

il pianificatore conosce la social choice ruleil pianificatore può scegliere il gioco da far giocare aigiocatoriil pianificatore non conosce le preferenze dei giocatori

S. Villa Introduzione alla teoria dell’implementazione

Page 9: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

La classe di giochi G a disposizione del pianificatore è costituitada giochi

in forma strategicaad informazione completa (ciascun giocatore conosce lepreferenze di tutti i giocatori)

Si deve specificare il concetto di soluzione adottato.

S. Villa Introduzione alla teoria dell’implementazione

Page 10: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Precisazioni

il pianificatore può scegliere soltanto la game form (ilMECCANISMO)game form + preferenze dei giocatori= gioco

S. Villa Introduzione alla teoria dell’implementazione

Page 11: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Game form in forma strategica a conseguenze in A

E’ una terna G = (N, (Xi)i∈N , g) doveN è l’insieme dei giocatori (gli individui di prima)Xi è un insieme (le strategie a disposizione del giocatore i)g : X → A è detta outcome function (X =

∏i∈N Xi )

S. Villa Introduzione alla teoria dell’implementazione

Page 12: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Aggiungiamo le preferenze

Aggiungendo le preferenze dei giocatori otteniamo il gioco informa strategica

(N, (Xi)i∈N, g, (%)i∈N) = (G,%)

S. Villa Introduzione alla teoria dell’implementazione

Page 13: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Concetto di soluzione

Il concetto di soluzione di cui ci occupiamo è quello di equilibriodi Nash (corrisponde ad un assunzione sulla razionalitàstrategica dei giocatori). Chiamiamo S la corrispondenza chead ogni gioco associa i suoi equilibri di Nash.

Un equilibrio di Nash del gioco (G,%) è un profilo di strategie(x∗1 , . . . , x∗n ) tale che

g(x∗1 , . . . , x∗i , . . . , x∗n ) %i g(x∗1 , . . . , xi , . . . , x∗n )

per ogni i ∈ N e per ogni xi ∈ Xi .

S. Villa Introduzione alla teoria dell’implementazione

Page 14: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Definizione implementabilità

DefinizioneSia dato un environment E = (N, A,P,G) e sia f : P ⇒ A unasocial choice rule.Diciamo che G = (N, (Xi)i∈N , g) ∈ Gimplementa f in equilibrio di Nash se

per ogni %∈ P, g(S(G,%)) = f (%).

Diciamo che f è implementabile in equilibrio di Nash se esisteG che implementa f .

S. Villa Introduzione alla teoria dell’implementazione

Page 15: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Rappresentazione grafica

Pf

-- A

?G 7→(G,%) = (N, X , g,%) --

SX

6

g

S. Villa Introduzione alla teoria dell’implementazione

Page 16: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Rappresentazione grafica

Pf

-- A

?G 7→(G,%) = (N, X , g,%)

--S

X

6

g

S. Villa Introduzione alla teoria dell’implementazione

Page 17: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Rappresentazione grafica

Pf

-- A

?G 7→(G,%) = (N, X , g,%) --

SX

6

g

S. Villa Introduzione alla teoria dell’implementazione

Page 18: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Rappresentazione grafica

Pf

-- A

?G 7→(G,%) = (N, X , g,%) --

SX

6

g

S. Villa Introduzione alla teoria dell’implementazione

Page 19: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Esempio

Sia N = {1, 2, 3} un insieme di elettori;sia A = {a, b} l’insieme di candidati;siano �i∈N le preferenze (strette) degli elettorila social choice rule f : P → A è quella di maggioranza

Sia G la game form in cuiXi = {a, b} per ogni i ∈ {1, 2, 3}g(x1, x2, x3) = a se ci sono almeno due a tra le strategiedei giocatori e b altrimenti.

(G,%) implementa la social choice rule “di maggioranza”.

S. Villa Introduzione alla teoria dell’implementazione

Page 20: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Esempio

Sia N = {1, 2, 3} un insieme di elettori;sia A = {a, b} l’insieme di candidati;siano �i∈N le preferenze (strette) degli elettorila social choice rule f : P → A è quella di maggioranza

Sia G la game form in cuiXi = {a, b} per ogni i ∈ {1, 2, 3}g(x1, x2, x3) = a se ci sono almeno due a tra le strategiedei giocatori e b altrimenti.

(G,%) implementa la social choice rule “di maggioranza”.

S. Villa Introduzione alla teoria dell’implementazione

Page 21: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Esempio-Aste

Supponiamo di voler vendere un oggetto e di voler usare ilmeccanismo dell’asta (a busta chiusa). Ci sono solo duepossibili acquirenti.

l’insieme degli esiti è A = {(t1, t2, i)}, dove i si aggiudical’oggetto, t1, t2 sono i pagamenti fatti dai giocatori;lo spazio delle strategie è Xi = [0, +∞);g(b1, b2) = (t1, t2, i), dove i è il giocatore che ha offerto dipiù e ti = bi , e tj = 0 se j 6= i .

S. Villa Introduzione alla teoria dell’implementazione

Page 22: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Truthful implementation

Definizione 179.2 O-RSia E = (N, A,P,G) un environment in cui G è una classe digiochi per cui l’insieme delle azioni dei giocatori Xi = P. Laforma strategica G truthfully S−implementa la choice rulef : P ⇒ A se per ogni profilo %∈ P si ha:

x∗ ∈ S(G,%), dove x∗i =% ∀i ∈ N;g(x∗) ∈ f (%)

S. Villa Introduzione alla teoria dell’implementazione

Page 23: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Commenti sulla definizione

perché abbiamo imposto Xi = P?possono esserci soluzioni non truth telling, cioè non sirichiede {x∗} = S(G,%);possono esserci profili di preferenze per cui non ogni esitosecondo f è soluzione del gioco, cioè non si richiedeg(S(G,%)) = f (%).

S. Villa Introduzione alla teoria dell’implementazione

Page 24: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Revelation principle

Lemma 185.2 O-RSia E = (N, A,P,G) un environment. Se la social choice rule fè Nash implementabile allora è truthfully Nash implementabile.

S. Villa Introduzione alla teoria dell’implementazione

Page 25: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Revelation principle

Se f è Nash-implementabile allora c’è una game form in cuiogni giocatore deve annunciare un profilo di preferenzedire la verità è un equilibrio di Nash

S. Villa Introduzione alla teoria dell’implementazione

Page 26: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Esempio 189.1 O-R

Un oggetto deve essere assegnato a un giocatore nell’insiemeN = {1, . . . , n}. Per tutti i possibili profili di preferenze solo ungiocatore preferisce avere l’oggetto anziché non averlo.Vogliamo implementare la funzione di scelta che assegnal’oggetto a questo giocatore.

Poniamo Xi = {SI, NO}g(x1, . . . , xn) = assegna l’oggetto al giocatore checorrisponde all’indice minimo in cui si trova un SI e algiocatore n altrimenti.

S. Villa Introduzione alla teoria dell’implementazione

Page 27: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Condizioni necessarie di Nash-implementabilità

Definizione 186.1 O-RUna social choice rule f : P ⇒ A è monotona secondo Maskinse:

c ∈ f (%) c /∈ f (%′)⇓

c’è un giocatore i ∈ N ed un esito a ∈ A tale che c %i a ea �′i c.

S. Villa Introduzione alla teoria dell’implementazione

Page 28: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Condizioni necessarie di Nash-implementabilità

Proposizione 186.2 O-R

Sia E = (N, A,P,G) un environment dove G è l’insieme di tutti igiochi in forma strategica. Se una social choice rule èNash-implementabile allora è monotona secondo Maskin.

S. Villa Introduzione alla teoria dell’implementazione

Page 29: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

La storia...

Esempio 186.3 O-RCiascuna di due donne, 1 e 2, reclama un bimbo; ognuna diloro sa chi è la vera madre, ma nessuna delle due è in grado diprovare di essere la vera madre. Salomone cerca di capirequale sia la verità minacciando di dividere il bambino in due,confidando sul fatto che la madre falsa preferisca questo esitoa quello in cui la vera madre ottiene il bimbo, mentre la veramadre preferisca dar via il bimbo anziché vederlo tagliato indue.

S. Villa Introduzione alla teoria dell’implementazione

Page 30: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Formalizzazione dell’esempio

gli esiti possibili sono tre:il bambino viene dato alla donna 1 (a)il bambino viene dato alla donna 2 (b)il bambino viene tagliato in due (d)

P = {p′, p′′}:

p′ : a �′1 b �′1 d ; b �′2 d �′2 a

p′′ : a �′′1 d �′′1 b; b �′′2 a �′′2 d

S. Villa Introduzione alla teoria dell’implementazione

Page 31: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Formalizzazione

La regola di scelta sociale

f (p′) = {a}; f (p′′) = {b}

non è implementabile in equilibrio di Nash, poiché non èmonotona. Infatti a ∈ f (p′) e a /∈ f (p′′), ma non si trova un altroesito y e un giocatore i tale che a %′i y e y �′′i a.

S. Villa Introduzione alla teoria dell’implementazione

Page 32: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Esempio di game form

Strategie di 1: x1 = MIO, x2 = SUO,x3 = MIO, MA SE L’ALTRA LO CHIEDE DATELO A LEIle strategie di 2 sono y1, y2, y3, uguali a quelle di 1.Game form:

1| 2 y1 y2 y3x1 d a ax2 b d bx3 b a d

S. Villa Introduzione alla teoria dell’implementazione

Page 33: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Dalla game form al gioco: preferenze

Per aggiungere le preferenze dei giocatori, usiamo le funzioni diutilità:1 è la vera madre:

u′1(a) = 2, u′1(b) = 1, u′1(d) = 0u′2(a) = 0, u′2(b) = 2, u′2(d) = 1

2 è la vera madre:u′′1(a) = 2, u′′1(b) = 0, u′′1(d) = 1u′′2(a) = 1, u′′2(b) = 2, u′′2(d) = 0

S. Villa Introduzione alla teoria dell’implementazione

Page 34: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Gioco di Re Salomone

Se 1 è la vera madre, otteniamo il gioco di sinistra, se 2 è lavera madre quello di destra

1|2 y1 y2 y3x1 (0,1) (2,0) (2,0)x2 (1,2) (0,1) (2,1)x3 (1,2) (2,0) (0,1)

1|2 y1 y2 y3x1 (1,0) (2,1) (2,1)x2 (0,2) (1,0) (0,2)x3 (0,2) (2,1) (1,0)

S. Villa Introduzione alla teoria dell’implementazione

Page 35: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Equilibri del gioco

Gli equilibri di Nash sono in rosso

1|2 y1 y2 y3x1 (0,1) (2,0) (2,0)x2 (1,2) (0,1) (2,1)x3 (1,2) (2,0) (0,1)

1|2 y1 y2 y3x1 (1,0) (2,1) (2,1)x2 (0,2) (1,0) (0,2)x3 (0,2) (2,1) (1,0)

Nel caso 1 sia la vera madre il bambino viene assegnato a 2,nel caso 2 sia la vera madre viene assegnato a 1.

S. Villa Introduzione alla teoria dell’implementazione

Page 36: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Osservazioni

il nome dato alle strategie è irrilevanteabbiamo implementato la social choice rule che dà ilbambino alla madre falsa (che è monotona nel senso diMaskin)non si può cambiare la game form dopo averla dichiarata(nel nostro modello)meccanismo stocastico?

S. Villa Introduzione alla teoria dell’implementazione

Page 37: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Meccanismi diretti nel caso di Re Salomone

Le strategie a disposizione di 1 e 2 sono

X1 = X2 = {p′, p′′}.

La game form associata a un meccanismo diretto:

1|2 p′ p′′

p′ a1 a2p′′ a3 a4

Gli esiti ai ∈ {a, b, d}.

S. Villa Introduzione alla teoria dell’implementazione

Page 38: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Meccanismi diretti nel caso di Re Salomone

Truthful implementation⇒ dire la verità è un equilibrio di Nash.Proviamo con:

1|2 p′ p′′

p′ a dp′′ d b

Se le due donne fossero sincere, questo funzionerebbe.

S. Villa Introduzione alla teoria dell’implementazione

Page 39: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Meccanismi diretti nel caso di Re Salomone

Che giochi si ottengono? A sinistra 1 è la vera madre, a destra2 è la vera madre.

1|2 p′ p′′

p′ (2,0) (0,1)p′′ (0,1) (1,2)

1|2 p′ p′′

p′ (1,2) (1,0)p′′ (1,0) (0,2)

In rosso ci sono gli equilibri di Nash.

S. Villa Introduzione alla teoria dell’implementazione

Page 40: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Informazione incompleta

Ciascun giocatore NON conosce le preferenze degli altrigiocatoriTeoria dell’implementazione in equilibrio di Nashbayesiano (cfr. asta)

S. Villa Introduzione alla teoria dell’implementazione

Page 41: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Formalizzazione

Come nel caso a informazione completa abbiamo:un insieme di giocatori N;un insieme di possibili alternative A;

Le preferenze dei giocatori NON sono conoscenza comune.Aggiungiamo quindi:

Ti l’insieme dei tipi possibili per il giocatore i ;p una distribuzione di probabilità su T =

∏i Ti ;

le preferenze di ogni tipo sull’insieme A cherappresentiamo attraverso una funzione di utilitàui : A× Ti → R

S. Villa Introduzione alla teoria dell’implementazione

Page 42: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Formalizzazione

Un environment nel caso a informazione incompleta è unacollezione:

(N, A, T , p, (ui)i∈N ,G)

dove G è una classe di giochi in forma strategica ainformazione incompleta.

S. Villa Introduzione alla teoria dell’implementazione

Page 43: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Definizione implementabilità

DefinizioneSia dato un environment E = (N, A, T , p, (ui)i∈N ,G) e siaf : T → A una social choice function. Diciamo cheG = (N, T , p, (Xi)i∈N , g) ∈ G implementa f in equilibrio di Nashbayesiano se

g(s∗1(t1), . . . , s∗n(tn)) = f (t1, . . . , tn)

per ogni equilibrio di Nash bayesiano (s∗1, . . . , s∗n) di (G, (ui)i∈N)e per ogni (t1, . . . , tn) ∈ T . In altri termini, se S è l’insieme degliequilibri di Nash bayesiani di (G, (ui)):

g(S(G, (ui)i∈N)) = f

S. Villa Introduzione alla teoria dell’implementazione

Page 44: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Meccanismi diretti e incentive compatibility

DefinizioneUna social choice function è incentive compatible (o truthfullyimplementabile) se

(s∗1(t1), . . . , s∗n(tn)) = (t1, . . . , tn)

è un equilibrio di Nash bayesiano del meccanismo diretto(G, (ui)i∈N) con outcome function f .

S. Villa Introduzione alla teoria dell’implementazione

Page 45: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Commenti

Si parla di meccanismi diretti quando la classe di giochiconsiderata è tale che l’insieme delle azioni del giocatore iè Ti .f è incentive compatible se ogni giocatore non ha interessea mentire dichiarando un tipo diverso da quello che è inreltà, quando tutti gli altri giocatori riportano il loro vero tipo.

S. Villa Introduzione alla teoria dell’implementazione

Page 46: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Revelation principle (Myerson)

TeoremaSe f è implementabile in equilibrio di Nash bayesiano allorasoddisfa la proprietà di incentive compatibility, ovvero ètruthfully implementabile.

S. Villa Introduzione alla teoria dell’implementazione

Page 47: Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano Outline 1 Introduzione 2 Implementazione nel caso ad informazione completa 3 Formalizzazione

IntroduzioneImplementazione nel caso ad informazione completa

FormalizzazioneTruthful implementation e revelation principle

Esempio di Re SalomoneImplementazione in equilibrio di Nash Bayesiano

Ulteriore bibliografia

R. Serrano, The theory of implementation of social choicerules (per la parte ad informazione incompleta)

M. Jackson, A crash course in implementation theory

S. Villa Introduzione alla teoria dell’implementazione