Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano...
Transcript of Introduzione alla teoria dell'implementazione · Implementazione in equilibrio di Nash Bayesiano...
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
Almo Collegio BorromeoPavia, 16 Aprile 2008
S. Villa Introduzione alla teoria dell’implementazione
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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