Algojáték 7. gyakorlat megoldókulcs

A többségi szavazás eredményéhez megszámoljuk az első helyes szavazatokat:

• Az első csapat $9$ szavazója $a$-t tette első helyre, ez tehát $9$ szavazat $a$-nak.
• A második csapat $10$ szavazója $b$-t tette első helyre, ez tehát $10$ szavazat $b$-nek.
• A harmadik csapat $11$ szavazója $c$-t tette első helyre, ez tehát $11$ szavazat $c$-nek.

A társadalmi választási szabály ezeket teszi csökkenő sorrendbe, tehát: $$c \succ b \succ a$$.

Számítsuk ki az egyes alternatívák Borda-pontszámait:

$a$ alternatíva:

• Az első csapat 9 szavazója első helyre sorolta: $9 \cdot 2 = 18$ pont
• A második csapat 10 szavazója második helyre sorolta: $10 \cdot 1 = 10$ pont
• A harmadik csapat 11 szavazója második helyre sorolta: $11 \cdot 1 = 11$ pont
• Összesen: $B(a) = 18 + 10 + 11 = 39$ pont

$b$ alternatíva:

• Az első csapat 9 szavazója második helyre sorolta: $9 \cdot 1 = 9$ pont
• A második csapat 10 szavazója első helyre sorolta: $10 \cdot 2 = 20$ pont
• A harmadik csapat 11 szavazója harmadik helyre sorolta: $11 \cdot 0 = 0$ pont
• Összesen: $B(b) = 9 + 20 + 0 = 29$ pont

$c$ alternatíva:

• Az első csapat 9 szavazója harmadik helyre sorolta: $9 \cdot 0 = 0$ pont
• A második csapat 10 szavazója harmadik helyre sorolta: $10 \cdot 0 = 0$ pont
• A harmadik csapat 11 szavazója első helyre sorolta: $11 \cdot 2 = 22$ pont
• Összesen: $B(c) = 0 + 0 + 22 = 22$ pont

A Borda-pontszámok csökkenő sorrendje: $B(a) = 39 > B(b) = 29 > B(c) = 22$

Tehát a Borda-szavazás szerinti eredmény: $$a \succ b \succ c$$

Vizsgáljuk meg a párokat:

$a$ vs $b$:

• Az első és a harmadik csapat $a$-t sorolja $b$ elé, ez $9+11=20$ szavazó.
• A második csapat $b$-t sorolja $a$ elé, ez $10$ szavazó.
• $20 > 10$, tehát $a$-t szigorúan többen sorolták $b$ elé, ezért $a$ legyőzi $b$-t.

$a$ vs $c$:

• Az első és a második csapat $a$-t sorolja $c$ elé, ez $9+10=19$ szavazó.
• A harmadik csapat $c$-t sorolja $a$ elé, ez $11$ szavazó.
• $19 > 11$, tehát $a$-t szigorúan többen sorolták $c$ elé, ezért $a$ legyőzi $c$-t.

$b$ vs $c$:

• Az első és a második csapat $b$-t sorolja $c$ elé, ez $9+10=19$ szavazó.
• A harmadik csapat $c$-t sorolja $b$ elé, ez $11$ szavazó.
• $19 > 11$, tehát $b$-t szigorúan többen sorolták $c$ elé, ezért $b$ legyőzi $c$-t.

Igen, van Condorcet-győztes: az $a$ alternatíva, mivel legyőzött mindenki mást.

A c) rész eredményei alapján:

$a$ alternatíva:

• $w(a) = 2$ (legyőzte $b$-t és $c$-t)
• $l(a) = 0$ (őt senki nem győzte le)
• $C(a) = 2 - 0 = 2$

$b$ alternatíva:

• $w(b) = 1$ (legyőzte $c$-t)
• $l(b) = 1$ (őt $a$ legyőzte)
• $C(b) = 1 - 1 = 0$

$c$ alternatíva:

• $w(c) = 0$ (senkit nem győzött le)
• $l(c) = 2$ (őt $a$ és $b$ is legyőzték)
• $C(c) = 0 - 2 = -2$

A Copeland-pontszámok csökkenő sorrendje: $C(a) = 2 > C(b) = 0 > C(c) = -2$

Tehát a Copeland-szavazás szerinti eredmény: $$a \succ b \succ c$$

Megjegyzés: Az $a$ Condorcet-győztes, így nem meglepő, hogy a Condorcet-konzisztens Copeland-szavazás is őt választja első helyre.

A többségi szavazás eredményéhez megszámoljuk az első helyes szavazatokat:

• Az első csapat $5$ szavazója és a második csapat $4$ szavazója $a$-t tette első helyre, ez tehát $9$ szavazat $a$-nak.
• A harmadik csapat $7$ szavazója $b$-t tette első helyre, ez tehát $7$ szavazat $b$-nek.
• A negyedik csapat $9$ szavazója $c$-t tette első helyre, ez tehát $9$ szavazat $c$-nek.

$a$ és $c$ között döntetlen van, ilyenkor az $1$. szavazó (az első csapat szavazó) szavazata dönt, aki szerint $a$ a jobb.

Tehát a többségi szavazás szerinti eredmény: $$a \succ c \succ b.$$

Számítsuk ki az egyes alternatívák Borda-pontszámait:

$a$ alternatíva:

• Az első csapat 5 szavazója első helyre sorolta: $5 \cdot 2 = 10$ pont
• A második csapat 4 szavazója első helyre sorolta: $4 \cdot 2 = 8$ pont
• A harmadik csapat 7 szavazója második helyre sorolta: $7 \cdot 1 = 7$ pont
• A negyedik csapat 9 szavazója harmadik helyre sorolta: $9 \cdot 0 = 0$ pont
• Összesen: $B(a) = 10 + 8 + 7 + 0 = 25$ pont

$b$ alternatíva:

• Az első csapat 5 szavazója második helyre sorolta: $5 \cdot 1 = 5$ pont
• A második csapat 4 szavazója harmadik helyre sorolta: $4 \cdot 0 = 0$ pont
• A harmadik csapat 7 szavazója első helyre sorolta: $7 \cdot 2 = 14$ pont
• A negyedik csapat 9 szavazója második helyre sorolta: $9 \cdot 1 = 9$ pont
• Összesen: $B(b) = 5 + 0 + 14 + 9 = 28$ pont

$c$ alternatíva:

• Az első csapat 5 szavazója harmadik helyre sorolta: $5 \cdot 0 = 0$ pont
• A második csapat 4 szavazója második helyre sorolta: $4 \cdot 1 = 4$ pont
• A harmadik csapat 7 szavazója harmadik helyre sorolta: $7 \cdot 0 = 0$ pont
• A negyedik csapat 9 szavazója első helyre sorolta: $9 \cdot 2 = 18$ pont
• Összesen: $B(c) = 0 + 4 + 0 + 18 = 22$ pont

A Borda-pontszámok csökkenő sorrendje: $B(b) = 28 > B(a) = 25 > B(c) = 22$

Tehát a Borda-szavazás szerinti eredmény: $$b \succ a \succ c$$

Vizsgáljuk meg a párokat:

$a$ vs $b$:

• Az első és a második csapat $a$-t sorolja $b$ elé, ez $5+4=9$ szavazó.
• A harmadik és a negyedik csapat $b$-t sorolja $a$ elé, ez $7+9=16$ szavazó.
• $16 > 9$, tehát $b$-t szigorúan többen sorolták $a$ elé, ezért $b$ legyőzi $a$-t.

$a$ vs $c$:

• Az első, a második és a harmadik csapat $a$-t sorolja $c$ elé, ez $5+4+7=16$ szavazó.
• A negyedik csapat $c$-t sorolja $a$ elé, ez $9$ szavazó.
• $16 > 9$, tehát $a$-t szigorúan többen sorolták $c$ elé, ezért $a$ legyőzi $c$-t.

$b$ vs $c$:

• Az első és a harmadik csapat $b$-t sorolja $c$ elé, ez $5+7=12$ szavazó.
• A második és a negyedik csapat $c$-t sorolja $b$ elé, ez $4+9=13$ szavazó.
• $13 > 12$, tehát $c$-t szigorúan többen sorolták $b$ elé, ezért $c$ legyőzi $b$-t.

A páronkénti összehasonlítások eredményei tehát:

• $b$ legyőzi $a$-t,
• $a$ legyőzi $c$-t,
• $c$ legyőzi $b$-t.

Nincs Condorcet-győztes, mivel nincs olyan alternatíva, amely minden másikat legyőzne páronkénti versenyben.

A c) rész eredményei alapján:

$a$ alternatíva:

• $w(a) = 1$ (legyőzte $c$-t)
• $l(a) = 1$ (őt $b$ legyőzte)
• $C(a) = 1 - 1 = 0$

$b$ alternatíva:

• $w(b) = 1$ (legyőzte $a$-t)
• $l(b) = 1$ (őt $c$ legyőzte)
• $C(b) = 1 - 1 = 0$

$c$ alternatíva:

• $w(c) = 1$ (legyőzte $b$-t)
• $l(c) = 1$ (őt $a$ legyőzte)
• $C(c) = 1 - 1 = 0$

A Copeland-pontszámok: $C(a) = C(b) = C(c) = 0$, tehát teljes döntetlen alakul ki.

Ilyenkor az egyenlőséget az $1$. szavazó preferenciarendezése töri meg, aki szerint: $$a \succ_1 b \succ_1 c.$$

Tehát a Copeland-szavazás szerinti eredmény: $$a \succ b \succ c$$

A többségi szavazás, a Borda-szavazás és a Copeland-szavazás sem anonim, mert egyenlőség esetén az 1. szavazó szavazata dönt. Például legyen $3$ szavazó, akik a következőképp szavaznak:

• $a \succ_1 b \succ_1 c$
• $c \succ_2 a \succ_2 b$
• $b \succ_3 c \succ_3 a$

Mindhárom szavazási mechanizmus semleges, hiszen az alternatívák címkéi nincsenek figyelembevéve a számítás során.

Megjegyzés: Ha a döntetleneket a nem az $1$. szavazó szavazata alapján döntenénk el, hanem például azt mondanánk, hogy a kisebb indexű alternatívát soroljuk előrébb, akkor már nem lenne semleges a mechanizmus (cserébe szimmetrikus lenne).

Mindhárom mechanizmus társadalmi választási szabálya egyhangú.

Ha mindenki előrébb sorolja $a$-t $b$-hez képest, akkor az biztosan nem fordul elő, hogy valaki $b$-t első helyre tette, tehát $b$ nulla db szavazatot kap. Ekkor két eset van:

• Ha $a$ szerepel első helyen valakinél, akkor a többségi szavazásban ő pozitív sok szavazatot kap és ezáltal előrébb lesz a végeredményben.
• Ha $a$ senkinél nem szerepel első helyen, akkor szintén nulla db szavazatot kap, ekkor pedig az $1$. szavazó szavazata dönt, aki (éppúgy mint a többiek) $a$-t sorolta előrébb $b$-hez képest.

Ha mindenki előrébb sorolja $a$-t $b$-hez képest, akkor $a$-nak szigorúan több lesz a Borda-pontszáma $b$-hez képest, tehát előrébb lesz a végeredményben.

Ha mindenki előrébb sorolja $a$-t $b$-hez képest, akkor $a$ legyőzi $b$-t. Továbbá:

Az $a$ mindenkit legyőz akit a $b$ is legyőzött: Hiszen ha $b$ legyőzte $c$-t akkor több $b \succ c$ szavazat van mint $c \succ b$. Tudjuk, hogy $a$-t mindenki $b$ elé rangsorolta, ezért a $b \succ c$ szavazatokra tudható az is, hogy $a \succ b \succ c$ alakúak. Mivel ennyi szavazat elég volt $b$-nek a győzelemre $c$ felett, ezért $a$-nak is győznie kell $c$ felett.
Ez képlettel $w(a) \geq w(b)$, továbbá mivel $a$ biztosan győz $b$ felett, ezért $w(a) > w(b)$ is teljesül.

Az $b$-t mindenki legyőzi aki $a$-t is legyőzte: Hiszen ha $c$ legyőzte $a$-t akkor több $c \succ a$ szavazat van mint $a \succ c$. Tudjuk, hogy $b$-t mindenki $a$ mögé rangsorolta, ezért a $c \succ a$ szavazatokra tudható az is, hogy $c \succ a \succ b$ alakúak. Mivel ennyi szavazat elég volt arra, hogy $a$ veszítsen $c$ ellen, ezért $b$ is veszíteni fog $c$ ellen.
Ez képlettel $l(a) \leq l(b)$, továbbá mivel $b$ biztosan veszít $a$ ellen, ezért $l(a) < l(b)$ is teljesül.

Abban a speciális esetben amikor legfeljebb két darab alternatíva van FLA lesz mindegyik, ez elfajuló esete a definíciónak.

Arrow tétel. Ha van legalább $3$ alternatíva, továbbá $F$ egyhangú és független a lényegtelen alternatíváktól, akkor $F$ diktatórikus.

Legalább három alternatíva esetén egyik mechanizmus TVSZ-e sem független a lényegtelen alternatíváktól, hiszen már beláttuk róluk hogy egyhangúak és tudjuk hogy egyik sem diktatórikus: az Arrow tétel szerint pedig az egyhangúság mellett az FLA tulajdonság csak diktatórikus mechanizmusra teljesülhet.

Ellenpélda például ha egy szavazó szerint $a \succ_1 b \succ_1 c \succ_1 d \succ_1 e$, illetve két másik szavazó szerint $e \succ_2 d \succ_2 c \succ_2 b \succ_2 a$.

Ekkor a Borda pontszámaik:

• $B(a) = 4 + 2 \cdot 0 = 4$
• $B(b) = 3 + 2 \cdot 1 = 5$
• $B(c) = 2 + 2 \cdot 2 = 6$
• $B(d) = 1 + 2 \cdot 3 = 7$
• $B(e) = 0 + 2 \cdot 4 = 8$

Tehát az őszinte szavazatokkal a Borda-szavazás eredménye szerint $e$ nyert. Ez az első szavazónak a legrosszabb lehetősége.

Ezután tegyük fel, hogy az első szavazó $d$-t teszi első helyre a szavazatában, például így szavaz: $$d \succ'_1 a \succ'_1 b \succ'_1 c \succ'_1 e.$$

Ekkor a Borda pontszámaik:

• $B'(a) = 3 + 2 \cdot 0 = 3$
• $B'(b) = 2 + 2 \cdot 1 = 4$
• $B'(c) = 1 + 2 \cdot 2 = 5$
• $B'(d) = 4 + 2 \cdot 3 = 10$
• $B'(e) = 0 + 2 \cdot 4 = 8$

Most a Borda-szavazás eredménye szerint $d$ nyert. Ezzel az első szavazó egy kicsivel jobban járt, mintha őszintén szavazott volna, hiszen a nyertes $d$-t ő jobban szereti $e$-hez képest.

Ez azt mutatja, hogy a Borda-szavazás manipulálható.

Másik megoldás: A Gibbard-Satterthwaite tétel szerint ha van legalább $3$ alternatíva, továbbá a társadalmi választási függvény (az $f$) szürjektív (mindegyik alternatíva előáll nyertesként valamilyen $\Pi$-re) és taktikázásbiztos, akkor $f$ diktatórikus. A Borda-szavazás társadalmi választási függvénye szürjektív, hiszen minden alternatíva elő tud állni nyertesként. De tudjuk, hogy a Borda-szavazás nem diktatórikus, ezért nem lehet taktikázásbiztos.

Ez teljesül, hiszen a szavazási mechanizmus nem veszi figyelembe a szavazók sorszámát, nincs kitüntetett szavazó. (Itt most egyenlőség sem jöhet ki, hiszen az igen szavazok paritása egyértelműen meghatározza az eredményt.)

Ha $n$ páratlan, akkor teljesül, gondoljuk végig:

1. eset: páros igen szavazat, páratlan nem szavazat, ekkor a nem nyer.

Ha most átneveznénk az igen-t nem'-re, a nem-et pedig igen'-re, akkor a szavazási mechanizmus azt látná, hogy az igen'-ből páratlan sok van, tehát az igen' nyerne. De az igen' igazából a nem alternatívát kódolja, így ugyanúgy a nem nyert.

2. eset: páratlan igen szavazat, páros nem szavazat, ekkor az igen nyer.

Ha most átneveznénk az igen-t nem'-re, a nem-et pedig igen'-re, akkor a szavazási mechanizmus azt látná, hogy az igen'-ből páros sok van, tehát a nem' nyerne. De a nem' igazából az igen alternatívát kódolja, így ugyanúgy az igen nyert.

Ha $n$ páros, akkor viszont nem teljesül, gondoljuk végig:

1. eset: páros igen szavazat, páros nem szavazat, ekkor a nem nyer.

Ha most átneveznénk az igen-t nem'-re, a nem-et pedig igen'-re, akkor a szavazási mechanizmus azt látná, hogy az igen'-ből páros sok van, tehát a nem' nyerne. De a nem' igazából az igen alternatívát kódolja, így most az igen nyert.

2. eset: páratlan igen szavazat, páratlan nem szavazat, ekkor az igen nyer.

Ha most átneveznénk az igen-t nem'-re, a nem-et pedig igen'-re, akkor a szavazási mechanizmus azt látná, hogy az igen'-ből páratlan sok van, tehát az igen' nyerne. De az igen' igazából a nem alternatívát kódolja, így most a nem nyert.

Röviden úgy fogalmazhatunk, hogy ha páratlan az $n$ akkor az alternatívák átnevezésével a paritások is megcserélődnek a kettő között, ezért olyan mintha nem változna semmi. A páros $n$ esetében az alternatívákat átneveztük, de a paritások megmaradtak, így a szavazási mechanizmus most a másikat fogja győztesként kihozni.

Ha $n$ páratlan, akkor egyhangú, hiszen ha mindenki igen $\succ$ nem sorrendben szavaz, akkor az igen páratlan sok szavazatot kap és nyer, ha mindenki nem $\succ$ igen sorrendben, akkor az igen nulla, azaz páros sok szavazatot kap és veszít.

Ha $n$ páros, akkor viszont nem lesz egyhangú, akkor van gond, ha mindenki igen $\succ$ nem sorrendben szavaz, hiszen ekkor az igen páros sok szavazatot kap és veszít, pedig mindenki rá szavazott.

Igen, hiszen a két alternatívás TVSZ az FLA definíciójának egy elfajuló esete. Ha az alternatíváknak csak egy részhalmazát nézzük, az legfeljebb egy elemű. Az egy elemű halmaz saját magához képesti sorrendje meg nem tud sokat változni bárhogyan is variáljuk a többi alternatíva sorrendjét hozzá képest.

Igen, hiszen ha van olyan szavazó, akinek nem tetszik az eredmény, akkor ha ellenkező módon szavaz, attól azonnal a másik alternatíva fog nyerni.

Hasonlóan a 4. feladathoz a Gibbard-Satterthwaite tétel itt bizonyítja, hogy a Copeland-szavazás manipulálható.

Igen, például ha az első $n-2$ szavazó $c \succ_1 b \succ_1 a$ sorrendben szavazott, az $n$. szavazó pedig $a \succ_n b \succ_n c$ sorrendben. Ekkor ha az $n-1$. szavazó valódi preferenciasorrendje $b \succ_{n-1} c \succ_{n-1} a$, akkor ha őszintén szavaz, az $n$. szavazó döntése fog érvényesülni és az $a$ nyer. Azonban ha inkább beáll a tömegbe és ő is $c \succ_{n-1}' b \succ_{n-1}' a$ sorrendben szavaz, akkor az első $n-1$ db szavazó egyformán szavazott, ők döntenek, ettől pedig a $c$ fog nyerni. Az $n-1$. szavazónak a $c$ egy kicsivel jobb az $a$-nal, ezért ő jobban jár, ha így hazudik.

Alternatívák.

A lehetséges alternatívák most azt jelölik, hogy ki nyeri meg a tárgyat. Tehát az alternatíváink $A=\{a_1, \dots, a_n\}$ és ha az $a_i$ a nyertes, akkor az azt jelenti, hogy az $i$. licitáló kapja a tárgyat.

Valódi értékelő függvények $\hat{v_i}$.

A feladat szerint minden licitáló $C$ értékűnek tartja a tárgyat. Azt tételezzük fel, hogy csak annak örül, ha ő maga kapja meg a tárgyat, más kimenetel (amikor másé a tárgy) számára $0$ hasznosságú. Ezért: $$ \hat{v_i}(a_j) = \begin{cases} C, & \text{ha } i=j,\\ 0, & \text{ha } i \neq j. \end{cases} $$ Tehát az $i$-edik licitáló valódi hasznossága $C$, ha ő nyer, és $0$, ha valaki más nyer.

Licitfüggvények $v_i$.

A mechanizmus szerint minden $i$ licitáló egy $C_i$ számot ír fel a papírra, hogy mennyit fizetne a tárgyért. A modellben ezt úgy tekintjük, mint olyan licitfüggvényt, ahol csak a saját nyerési alternatívájára ad meg nemnulla értéket: $$ v_i(a) = \begin{cases} C_i, & \text{ha } a = i,\\ 0, & \text{ha } a \neq i. \end{cases} $$ Vagyis az $i$ játékos csak arra licitál, hogy ő kapja meg a tárgyat, arra, hogy más kapja, $0$-t licitál.

A mechanizmus $f$ kimeneti függvénye.

A leírás szerint a(z egyik) legnagyobb licitet felírónak adjuk oda a tárgyat. Legyen $f(v_1, \dots, v_n) = a_i$, ha $\max\{C_1, \dots, C_n\} = C_i$ és ha több maximális licit is van, akkor válasszuk például a minimális indexűt.

A $p_i$ kifizetési függvények.

A mechanizmus szerint a nyertesnek ki kell fizetnie a saját licitjét, a többiek semmit nem fizetnek. Tehát $$ p_j(v) = \begin{cases} C_j, & \text{ha } f(v) = a_j,\\ 0, & \text{ha } f(v) \neq a_j. \end{cases} $$

A fent leírt mechanizmus most feltételezte, hogy a felhasználók olyan $v_i$-ket adnak meg, amik teljesítik azt a feltételt, hogy egyetlen alternatívához rendelnek nem nulla értéket. Ha esetleg arra is fel szeretnénk készülni, hogy a felhasználók nem ennek a várakozásnak megfelelő licitfüggvényeket adnak meg, akkor választhatjuk $f$-nek például azt, ami a maximális összértékű alternatívát adja vissza, $p_i$-nek pedig a $v_i(f(v_1, \dots, v_n))$-t.

1. lépés: Az optimális allokáció meghatározása.

• $A \gets s$, $B \gets t$, $C \gets u$: összhaszon $=12 + 4 + 10 = 26$
• $A \gets s$, $B \gets u$, $C \gets t$: összhaszon $=12 + 8 + 5 = 25$
• $A \gets t$, $B \gets s$, $C \gets u$: összhaszon $=8 + 9 + 10 = 27$
• $A \gets t$, $B \gets u$, $C \gets s$: összhaszon $=8 + 8 + 0 = 16$
• $A \gets u$, $B \gets s$, $C \gets t$: összhaszon $=0 + 9 + 5 = 14$
• $A \gets u$, $B \gets t$, $C \gets s$: összhaszon $=0 + 4 + 10 = 14$

A fenti lehetőségek közül a legnagyobb összhaszon $27$, amit az $$A \gets t,\quad B \gets s,\quad C \gets u$$ allokáció ad. Az $f$ tehát ezt fogja választani. Ez $A$-nak $8$-at, $B$-nek $9$-et, $C$-nek pedig $10$-et ér.

2. lépés: Clarke-szabály szerinti fizetések.

$A$ játékos fizetése

Ha $A$ nincs, akkor látható, hogy akkor járnak a többiek a legjobban, ha $B \gets s$, $C \gets u$, ahol az összhaszon $9 + 10 = 19$. $A$ jelenlétében a többiek szintén $19$-et kapnak, ezért $A$ fizetése $$p_A = 19 - 19 = 0.$$

$B$ játékos fizetése

Ha $B$ nincs, akkor látható, hogy akkor járnak a többiek a legjobban, ha $A \gets s$, $C \gets u$, ahol az összhaszon $12 + 10 = 22$. $B$ jelenlétében a többiek $18$-at kapnak, ezért $B$ fizetése $$p_B = 22 - 18 = 4.$$

$C$ játékos fizetése

Ha $C$ nincs, akkor látható, hogy akkor járnak a többiek a legjobban, ha $A \gets s$, $B \gets u$, ahol az összhaszon $12 + 8 = 20$. $C$ jelenlétében a többiek $17$-et kapnak, ezért $C$ fizetése $$p_C = 20 - 17 = 3.$$

Végső válasz.

• $A$ játékos megkapja $t$-t és $p_A = 0$-t fizet.
• $B$ játékos megkapja $s$-t és $p_B = 4$-et fizet.
• $C$ játékos megkapja $u$-t és $p_C = 3$-at fizet.

Látható, hogy ez éppen egy VCG-mechanizmus Clarke-szabállyal. Legyenek ugyanis az alternatívák azok, hogy melyik licitáló kapja a tárgyat. Ekkor mindenki 0-át licitál a többiek alternatívájára (a sajátjára pedig amennyit eddig is). A VCG-mechanizmusban az az alternatíva nyer, ami maximalizálja a társadalmi összjót, ami éppen a legnagyobb licitű játékos nyerése lesz. A Clarke-szabály szerint pedig annyit kell fizetnie, mint amennyivel megkárosította a többieket a jelenlétével, ez éppen a második legnagyobb licit, hiszen az ehhez tartozó játékos nyert volna, ha a legnagyobb licitű nincs jelen. Tanultunk két szuper tételt:

Tétel. A VCG mechanizmus taktikázásbiztos.

Tétel. A VCG mechanizmus Clarke-szabállyal szubvenciómentes és veszteségmentes, ha minden $i$ licitáló $\hat{v_i}$ valódi értékelőfüggvénye nemnegatív.

Megjegyzés: A szubvenciómentesség és a veszteségmentesség persze anélkül is látszik, hogy beláttuk volna, hogy ez egy VCG mechanizmus.

Legyen $n=3$ és tegyük fel, hogy az őszinte licitek különbözők. Ekkor a második legnagyobb licitet tevő játékosnak megérné úgy hazudni, hogy az első legnagyobb licitnél nagyobbat mond. Így ő vihetné el a tárgyat és a harmadik legnagyobb licitet kellene kifizetnie, ami kisebb mint az övé, tehát nyerne vele.

A VCG mechanizmus taktikázásbiztos, használjuk ezt. Jelentse (továbbra is) az $a_i$ alternatíva azt, hogy az $i$. szolgáltató nyert.

A szolgáltatók valódi értékelőfüggvényei: $$ \hat{v_i}(a_j) = \begin{cases} -w_i, & \text{ha } i=j,\\ 0, & \text{ha } i \neq j. \end{cases} $$

A negatív értékelőfüggvényt úgy kell értelmezni, hogy a szolgáltatók arra licitálnak, hogy mennyi pénzt szeretnének kapni a mechanizmustól, ha ők nyernek, ez pont az amire nekünk szükségünk van.

A negatív előjelű licitek miatt pedig a VCG mechanizmus most költséget minimalizál, azaz éppen a legkisebb munkadíjú szolgáltatót fogja megbízni. A kifizetés pedig a Clarke-szabály szerint éppen a második legkisebb munkadíj lesz.

Legyen $T$ az az alternatíva, aki mindenkinél extrém (első vagy utolsó). Tegyük fel indirekt, hogy a $T$ alternatíva $F(\Pi)$-ben nem extrém azaz vannak valamilyen $a,b \in A$, akik $T$-től és egymástól is különböző alternatívák, hogy $a \succ_{F(\Pi)} T \succ_{F(\Pi)} b$.

Képezzük a $\Pi'$ választási profilt $\Pi$-ből a következőképpen:

• Ha az adott szavazatban $T$ első helyen van, akkor mozgassuk $b$-t a második helyre.
• Ha pedig $T$ utolsó helyen van, akkor mozgassuk $b$-t az első helyre.

Látható, hogy $\Pi$-ben $b$ és $T$ egymáshoz viszonyított sorrendje nem változott meg a szavazatokban, tehát a lényegtelen alternatíváktól való függetlenség miatt az eredményben sem változhat meg a viszonyuk, továbbra is $T \succ_{F(\Pi')} b$.

Hasonlóan, $T$ és $a$ egymáshoz viszonyított sorrendje sem változott meg a szavazatokban, tehát továbbra is $a \succ_{F(\Pi')} T$.

Viszont az $b$ előremozgatásával biztosan elértük, hogy minden szavazatban megelőzze $a$-t. Mivel $F$ egyhangú, ezért ebből következik, hogy $b \succ_{F(\Pi')} a$.

Ha a fentieket összegezzük, azt kapjuk hogy $b \succ_{F(\Pi')} T \succ_{F(\Pi')} a \succ_{F(\Pi')} b$, ami ellentmondás. Tehát $T$ biztosan extrém alternatíva lesz a közös döntésben is.

Megjegyzés: Lásd a jegyzetben, 2.15. Lemma (Trump-lemma).