THE: Mechanism design

THE: Mechanism design Martin Hrubý Brno University of Technology Brno Czech Republic

November 21, 2014

Martin Hrub´ y

THE: Mechanism design

´ Uvod

ˇ ano z: Cerp´ ◮

McCarthy, N., Mierowitz, A.: Political Game Theory: An Introduction, Cambridge University Press, 2007

◮

Nisan, N. et al.: Algorithmic Game Theory, Cambridge University Press, 2007

◮

Magdaléna Hykˇsov´ a: Pˇredn´ aˇsky z teorie her, Fakulta dopravn´ı ˇ CVUT

Martin Hrub´ y


´ Uvod Zat´ım jsme studovali ”hotové situace” a hledali racionalitu v reakci hráˇc˚ u na situaci. Tzn., um´ıme zkoumat reakci hr´ aˇc˚ u na situaci. ◮

Mechanism design je opaˇcnou u ´lohou.

◮

Také nazýváno ”Reverse game theory” – Teorie her naopak.

◮

Zabývá se studiem situac´ı s priv´ atn´ı (tajnou) informac´ı – c´ılem je formou návrhu hry dos´ ahnout pravidel, kdy je pro hráˇce racionáln´ım chován´ım ”odtajnit” svoje priv´ atn´ı informace.

◮

Stále se pˇredpokl´ ad´ a racionalita hr´ aˇc˚ u. Nebudujeme fyzikáln´ı zákony (kde se nemus´ıme strachovat o vymahatelnost), ale pravidla (mechanismy), kde je hr´ aˇcovou nejlepˇs´ı odpovˇed´ı se chovat dle naˇseho oˇcek´ av´ an´ı.

Leonid Hurwicz, Eric Maskin, and Roger Myerson – Nobelova cena, 2007. Martin Hrub´ y


Mechanism design (MD) MD nacház´ı uplatnˇen´ı v tˇechto tˇr´ıd´ ach problém˚ u: ◮

◮

◮

◮

◮

Volby (teorie veˇrejné volby) – kaˇzdý voliˇc m´ a své preference a zkoumáme volebn´ı mechanismy vedouc´ı k veˇrejnˇe optimáln´ı volbˇe. Trhy – zkoumáme mechanismy ekonomiky. Dokonalý trh zˇrejmˇe neexistuje. C´ılem je spr´ avn´ a realokace zboˇz´ı a penˇez. Aukce – speciáln´ı pˇr´ıpad trhu, kde je pouze jeden prodávaj´ıc´ı. Hledáme pravidla pro urˇcen´ı v´ıtˇeze a zp˚ usobu veden´ı aukce. Kombinatorické aukce. Dˇelen´ı (dˇelitelné/nedˇelitelné zboˇz´ı, kv´ oty) – spravedlivé rozdˇelen´ı, envy-free, efektivn´ı. Veˇrejné záleˇzitosti, pravidla a z´ akony – regulace, danˇe, alokace (kv´ ot, statk˚ u, ...), ...

Kl´ıˇcovým ukazatelem mechanismu je odolnost v˚ uˇci strategické manipulaci (strategy-proof, incentive compatible, truthfull). Martin Hrub´ y


Teorie veˇrejné volby (Social, Public Choice) Specifikace problému: ◮

Skupina voliˇc˚ u I = {i1 , ..., iN } chce zvolit jednoho z mnoˇziny A kandidát˚ u.

◮

Kaˇzdý voliˇc má na mnoˇzinˇe A své preference (´ uplné uspoˇrádán´ı – ostré/neostré).

◮

Vol´ıme ˇclovˇeka ve volb´ ach do funkce, vol´ıme alternativu veˇrejného rozhodnut´ı nebo jenom tˇreba film pro veˇcern´ı prom´ıtán´ı.

◮

Vˇzdy máme alternativy, voliˇce a potˇrebu se spoleˇcnˇe rozhodnout.

◮

Oˇcekáváme, ˇze kaˇzdý voliˇc chce dos´ ahnout svého c´ıle – racionálnˇe se rozhoduje a vn´ım´ a uˇzitek z výsledku rozhodnut´ı.

Volebn´ı pravidla (zp˚ usob urˇcen´ı v´ıtˇeze) = mechanismus. Martin Hrub´ y


Odolnost v˚ uˇci strategické manipulaci Esenciáln´ı otázka: proˇc je to d˚ uleˇzité? Tj., proˇc je d˚ uleˇzité zjistit pravdu? ◮

Volby (teorie veˇrejné volby) – skuteˇcnˇe prav´ a spoleˇcensky optimáln´ı volba.

◮

Trhy a Aukce – zjiˇstˇen´ı optim´ aln´ı ceny.

◮

Dˇelen´ı (dˇelitelné/nedˇelitelné zboˇz´ı, kv´ oty) – spravedlnost jako spoleˇcenská norma, stabilita systému.

◮

Veˇrejné záleˇzitosti, pravidla a z´ akony – zajiˇstˇen´ı poˇzadovaného chován´ı hráˇc˚ u.

Pokud je moˇznost manipulovat mechanismus, hr´ aˇci to udˇelaj´ı. Pokud manipuluj´ı vˇsichni, systém nefunguje. Mnohdy je vˇetˇs´ı diskuse kolem volby mechanismu (meta-volby) neˇz nad samotným pˇredmˇetem voleb. Dikt´ atorstv´ı. Martin Hrub´ y


Vˇetˇsinová volba Základn´ım mechanismem voleb je vˇ etˇsinov´ a volba. ◮

Seˇcteme hlasy pro jednotlivé kandid´ aty, v´ıtˇez´ı kandidát s nejvyˇsˇs´ım poˇctem hlas˚ u.

◮

Máme-li dva kandid´ aty A = {a1 , a2 }, je volba jednoduchá: seˇcteme hlasy pro a1 a hlasy pro a2 .

◮

Prvn´ı problém: co udˇel´ ame, pokud je poˇcet hlas˚ u shodný? Pokud volby zopakujeme, pak cel´ a ˇcinnost nedává smysl, protoˇze nem˚ uˇzeme oˇcek´ avat, ˇze voliˇci v druhém kole zmˇen´ı svoje preference.

◮

Pokud je kandidát˚ u v´ıce, m˚ uˇze to dapadnout jeˇstˇe horˇs´ım zp˚ usobem.

V´ıce kandidát˚ u a mechanismus vˇetˇsinové volby (duely) – pak silnˇe záleˇz´ı na poˇrad´ı rozhodov´ an´ı o jednotlivých dvojic´ıch. Martin Hrub´ y


Preference ◮

Máme mnoˇzinu alternativ A.

◮

Preference na mnoˇzinˇe A. Opˇet budeme definovat na relaci slabé preference R ⊆ A × A.

◮

Obvyklým zp˚ usobem ch´ apeme relaci striktn´ı preference a indiference. Slabou preferenci budeme zapisovat:

◮

◮ ◮

i vztaˇzenou ke hráˇci i vztaˇzenou k celkové spoleˇcnosti

◮

Striktn´ı preferenci obdobnˇe: ≻i , ≻

◮

Pˇripomeˇ nme, ˇze oˇcek´ av´ ame jistou logiku v preferenc´ıch – tranzitivitu preferenˇcn´ı relace.

Chceme zjistit, co se stane pˇri preferenc´ıch jednotlivc˚ u ≻i , jak´ a bude preference (a potom volba) spoleˇ cnosti ≻. Martin Hrub´ y


Smysl preference ve volbách

◮

Pokud je |A| = 1, volby se nekonaj´ı.

◮

Pokud je |A| = 2, intuitivnˇe ch´ apeme, ˇze hr´ aˇc preferuje jednu z alternativ (pˇreje si jednu a druhou nechce).

◮

Pokud je |A| ≥ 3, voliˇc st´ ale preferuje jednu alternativu (jeho maximum), ale mus´ı m´ıt n´ azor i na preference nad zbytkem alternativ.

◮

Pak p´ıˇseme a1 ≻i a2 ≻i ... ≻i ax .

V teorii veˇrejné volby nepracujeme s maximy hr´ aˇc˚ u, ale s jejich preferencemi.

Martin Hrub´ y


Vˇetˇsinová volba: manipulovatelnost pˇri |A| = 2

Vˇetˇsinová volba se dvˇema alternativami je z principu nemanipulovateln´ a. ◮

Hráˇc i preferuje a1 nad a2 . Tj., preference je a1 ≻i a2 .

◮

Uˇzitek Ui (a1 ) = 1, Ui (a2 ) = 0.

◮

Hráˇc nezv´ yˇs´ı sv˚ uj uˇzitek (ani slabˇe), pokud bude prezentovat jinou preferenci – a2 ≻i a1 .

◮

Pˇri |A| = 3 to m˚ uˇze být jinak.

Martin Hrub´ y


Modelová situace voleb – I.

Preference/Voliˇci: 1. 2. 3.

i1 A B C

i2 A C B

i3 B C A

Tabulka modelu preference voliˇc˚ u I = {i1 , i2 , i3 }. Voliˇc i1 : A ≻i B ≻i C . Pˇri vˇetˇsinové volbˇe zv´ıtˇez´ı alternativa A. Celkov´ a preference je A ≻ B ≻ C.

Martin Hrub´ y


Modelová situace voleb – II.


i1 A B C

i2 C A B

i3 B C A

Tabulka modelu preference voliˇc˚ u I = {i1 , i2 , i3 }. Voliˇc i1 : A ≻i B ≻i C .

Martin Hrub´ y


Prvn´ı názor Preference/Voliˇci: 1. 2. 3.

i1 A B C

i2 C A B

i3 B C A

V´ıtˇez by mˇel být schopen zv´ıtˇezit v duelu s kaˇzdým protikandidátem. ◮ ◮ ◮

Duel A:B (v´ıtˇez A, dva hlasy), tzn. celek A ≻ B Duel A:C (v´ıtˇez C, dva hlasy), tzn. celek C ≻ A Duel B:C (v´ıtˇez B, dva hlasy), tzn. celek B ≻ C

1. kolo – v´ıtˇez´ı A, 2. kolo (A versus C ) – v´ıtˇez´ı C . Je tedy C v´ıtˇez voleb? V´ıtˇeze nevid´ıme, ke vˇsemu je zmatek v celkové preferenci voliˇc˚ u: A ≻ B ≻ C ≻ A. Martin Hrub´ y


Condorcet˚ uv paradox Marie Jean Antoine Nicolas de Caritat, marquis de Condorcet (markýz de Condorcet, 1743–1794). ◮

Francouzský filosof a matematik.

◮

Poukázal na koncepˇcn´ı nedostatek vˇetˇsinové volby (zm´ınˇený paradox): pˇredpokl´ ad´ ame-li tranzitivitu u preferenc´ı voliˇc˚ u, lze dosáhnout netranzitivn´ı celkové preference.

◮

Condorcet˚ uv v´ıtˇez je alternativa X s tou vlastnost´ı, ˇze pro kaˇzdou alternativu Y je poˇcet voliˇc˚ u preferuj´ıc´ıch X pˇred Y vˇetˇs´ı, neˇz poˇcet voliˇc˚ u preferuj´ıc´ıch Y pˇred X .

◮

Pˇr´ıklad: Vˇetˇsina prefuje C pˇred B, C pˇred A, B pˇred A. Závˇer: A je poraˇzeno B i C, vˇetˇsina preferuje C nad B, v´ıtˇez´ı C.

◮

Condorcet˚ uv v´ıtˇez nemus´ı existovat.

◮

Dalˇs´ı studie: Condorcet’s jury theorem. Martin Hrub´ y


Strategická manipulace Preference/Voliˇci: 1. 2. 3.

i1 A B C

i2 C A B

i3 B C A

◮

Jsem tˇret´ı voliˇc.

◮

Vid´ım, ˇze m˚ uj kandid´ at B nen´ı obl´ıbený, ale nechci pˇripustit zvolen´ı A.

◮

Budu proto prezentovat svoji preferenci zmanipulovanou: C ≻3 B ≻3 A a ROZHODNU o v´ıtˇezi voleb.

Situace, kdy podán´ı nepravdivé informace o preferenc´ıch mohou ovlivnit výsledek volby jsou neˇz´ adouc´ı. Hled´ ame mechanismy, které jsou zabezpeˇceny proti strategické manipulaci. Martin Hrub´ y


Borda count

◮

Jean Charles de Borda (1733 – 1799).

◮

Kritizoval volebn´ı mechanismy ve Francouzské akademii.

◮

Navrhl rozdˇelit ”body” kandid´ at˚ um: kaˇzdý voliˇc pˇridˇel´ı |A| svému prvn´ımu kandid´ atovi, |A| − 1 druhému, ..., jeden posledn´ımu. V´ıtˇez je kandid´ at s nejvyˇsˇs´ı sumou bod˚ u.

◮

Zdá se to jako ide´ aln´ı metoda.

◮

Mnohdy vede k ˇreˇsen´ı, je ovˇsem strategicky manipulovatelná.

Martin Hrub´ y


Demo: Borda count


5 voliˇc˚ u A C B

4 voliˇci B C A

3 voliˇci C B A

Vˇetˇsinová volba je A ≻ B ≻ C (5:4:3). Jak dopadnou duely? ◮

A má 3 · 5 + 1 · 4 + 1 · 3 = 22 bod˚ u.

◮

B má 1 · 5 + 3 · 4 + 2 · 3 = 23 bod˚ u.

◮

C má 2 · 5 + 2 · 4 + 3 · 3 = 27 bod˚ u. Je to Bord˚ uv v´ıtˇez.

◮

C v´ıtˇez´ı i Condorcetovsky.

Martin Hrub´ y


Borda count, jiný pˇr´ıklad

1. 2. 3. 4.

1 X C B A

2 A X C B

3 B A X C

4 X C B A

5 A X C B

6 B A X C

7 X C B A

X=22, A=17, B=16, C=15 X odstoup´ı. V tom okamˇziku je výsledek: A=13, B=14, C=15 Borda count nen´ı odolný proti irelevantn´ım alternativ´ am.

Martin Hrub´ y


Duncan Black (1908–1991)

V´ıtˇezem je: ◮

Condorcet˚ uv v´ıtˇez, pokud existuje.

◮

Bord˚ uv v´ıtˇez v ostatn´ıch pˇr´ıpadech.

Zkuste sami navrhnout volebn´ı mechanismus pro 3 a v´ıce kandidáty (napˇr. r˚ uzné kolové (sekvenˇcn´ı) formy voleb dvou protikandidát˚ u). Kenneth Arrow ukázal, ˇze spravedlivé volby nejsou moˇzné. Pozor: Obecnˇe je nelze garantovat. Neznamen´ a to, ˇze ˇzijeme v nespravedlivém svˇetˇe.

Martin Hrub´ y


Profil ◮

Nechˇt A je mnoˇzina alternativ. Budeme formalizovat obor hodnot vˇsech moˇzných preferenc´ı.

◮

Mnoˇzina R je principem totoˇzn´ a s Si ve strategických hrách. Podobnˇe RN je S.

Definition Mˇejme mnoˇzinu alternativ A. Mnoˇzina R obsahuje vˇsechna moˇzná uspoˇrádán´ı na mnoˇzinˇe A (je izomorfn´ı s permutacemi na A).

Definition Mˇejme mnoˇzinu alternativ A a n voliˇc˚ u. Profilem ρ uspoˇrádán´ı preferenc´ı budeme rozumˇet uspoˇr´ adanou n-tici ρ = (R 1 , R 2 , ..., R n ) ∈ Rn

Martin Hrub´ y


Social welfare function Také pod názvem: Social Agregation Function, Preference Agregation Rule, ...

Definition Funkc´ı spoleˇcenského blahobytu (social welfare function) budeme rozumˇet funkci F : Rn → R Preference jednotlivce budeme zapisovat x ≻i y (vˇzdy vztaˇzeno k nˇejakému profilu ρ). Preference spoleˇcnosti x ≻ y . Funkce F je mechanickým arbitrem (ˇr´ıd´ı se pravidly), která na zadané preference voliˇc˚ u sestav´ı preferenci celé spoleˇcnosti (základ pro volbu optima). Martin Hrub´ y


Základn´ı pˇredpoklady

Je-li |A| = 2, pak je jediným rozumným mechanismem vˇetˇsinová volba. ◮

Poˇcet alternativ je |A| ≥ 3.

◮

Funkce spoleˇcenského blahobytu je definov´ ana pro vˇsechny profily individuáln´ıch preferenc´ı (tzn., arbitr je schopen sestavit spoleˇcenskou preferenci v libovolné situaci preferenc´ı voliˇc˚ u).

◮

Spoleˇcnost obsahuje alespoˇ n dva voliˇce.

Martin Hrub´ y


Podm´ınka tranzitivity

Definition Funkce spoleˇcenského blahobytu F je tranzitivn´ı, je-li F (ρ) tranzitivn´ı pro vˇsechny ρ ∈ RN . Tranzitivitu povaˇzujeme za minim´ aln´ı projev logiky rozhodován´ı (napˇr. pro nalezen´ı maxima). Arbitr je schopen sestavit tranzitivn´ı spoleˇcenskou preferenci ve vˇsech moˇzných situac´ıch preferenc´ı jednotlivc˚ u.

Martin Hrub´ y


Podm´ınka nediktátorstv´ı Definition Funkce spoleˇcenského blahobytu F je nedikt´ atorská, pokud neexistuje i ∈ Q takový, ˇze pro vˇsechny ρ ∈ RN a kaˇzdé dvˇe alternativy x, y ∈ A plat´ı, ˇze pokud x ≻i y , pak x ≻ y . Tato podm´ınka ukládá, aby ˇz´ adný hr´ aˇc i nezp˚ usobil svou preferenc´ı preferenci celku, bez ohledu na to, co si pˇreje celek. Zat´ım nemluv´ıme o strategické manipulaci (pˇredkl´ ad´ a nepravdivé preference). Uvid´ıme, ˇze s touto podm´ınkou je z´ asadn´ı problém. Nav´ıc, diktátorem nen´ı rozumˇen ”zlý ˇclovˇek” – prostˇe jsou situace, kdy rozhodnut´ı závis´ı na jednotlivci.

Martin Hrub´ y


Podm´ınka Pareto optimality

Definition Funkce spoleˇcenského blahobytu F je slabˇe Pareto optimáln´ı, pokud x ≻i y pro vˇsechny i ∈ Q zp˚ usob´ı, ˇze x ≻ y pro libovolné x, y ∈ A. Tato podm´ınka je velmi pˇr´ımoˇcar´ a: pokud si kaˇzdý zvláˇsˇt preferuje x pˇred y , pak i celek preferuje x pˇred y . Pozn.: Existuje jeˇstˇe striktnˇe Paretovsk´ a optimalita v teorii veˇrejné volby, podm´ınka je ovˇsem znaˇcnˇe silnˇejˇs´ı (moˇzno dostudovat). Tzn., slabˇe/silnˇe Paretovsk´ a optimalita v tomto pˇr´ıpadˇe nesouvis´ı se slabost´ı/striktnost´ı preference.

Martin Hrub´ y


Podm´ınka Nezávislosti na irelevantn´ıch alternativách (IIA) Independence of irrelevant alternatives (IIA) je pˇr´ıtomna ve vˇsech ˇcástech THE posuzuj´ıc´ıch preference. Form´ alnˇe je definovaná:

Definition Funkce spoleˇcenského blahobytu F je nez´ avisl´ a na irelevantn´ıch alternativách, pokud plat´ı pro libovolné x, y ∈ A a libovolné dva profily ρ, ρ′ ∈ RN , ˇze x i y ⇔ x ′i y pro vˇsechny i ∈ Q implikuje x y ⇔ x ′ y . Máme dva pohledy na vˇec: ρ, ρ′ ∈ RN , pokud v obou vˇsichni hráˇci preferuj´ı x pˇred y , pak i celek mus´ı v obou pˇr´ıpadech preferovat x pˇred y . Jinak ˇreˇceno, pokud v obou profilech maj´ı hr´ aˇci stejný n´ azor na preferenci na {x, y }, mˇely by být výsledné spoleˇcenské preference konzistentn´ı v otázce preference mezi {x, y }. Martin Hrub´ y


Demonstrace IIA Uvaˇzujme Borda count, kter´ a zp˚ usob´ı: A – 11 bod˚ u, D – 8 bod˚ u, tedy A ≻ D.

1. 2. 3. 4.

V A B C D

W A C B D

X B C D A

Y B C D A

Z C B D A

Omez´ıme-li se pouze na alternativy {A, D}, pak: A – 7 bod˚ u, D – 8 bod˚ u, tedy D ≻ A.

1. 2.

V A D

W A D

Martin Hrub´ y

X D A

Y D A

Z D A


Arrow˚ uv teorém

◮

Nazýván téˇz: Arrow’s paradox, Arrow’s impossibility theorem.

◮

Kenneth Arrow (Nobelova cena, 1972).

◮

Nejvýznamnˇejˇs´ı teorém ve spoleˇcenských vˇed´ ach.

◮

Arrow ukázal, ˇze funkce spoleˇcenského blahobytu, která je tranzitivn´ı, Pareto optim´ aln´ı a IIA, je dikt´ atorská.

◮

Taky lze ˇr´ıct, ˇze pˇredchoz´ı 4 podm´ınky (tranzitivita, Pareto optimalita, IIA, nedikt´ atorstv´ı) jsou vz´ ajemnˇe nekonzistentn´ı – nemohou platit souˇcasnˇe.

◮

Následky: vˇzdy jedna vlastnost vypadne

Martin Hrub´ y


Arrow’s Theorem

Theorem Je-li A koneˇcná mnoˇzina alternativ s alespoˇ n tˇremi alternativami, pak neexistuje spoleˇcensk´ a agregaˇcn´ı funkce F : RN → R, která je tranzitivn´ı, nediktátorsk´ a, slabˇe Pareto optim´ aln´ı a nezávislá na irelevantn´ıch alternativ´ ach. Existuje nˇekolik ekvivalentn´ıch formulac´ı Arrowova theoremu a stejnˇe tak nˇekolik jeho d˚ ukaz˚ u. Pˇredvedeme si d˚ ukaz zaloˇzený na zkoumán´ı mnoˇziny rozhoduj´ıc´ı uspoˇr´ adanou dvojici (x, y ). Mnoho partii MD je zaloˇzeno na hled´ an´ı minim´ aln´ı v´ıtˇ ezn´ e koalice. Skupinová racionalita.

Martin Hrub´ y


Pomocná definice Definition Pro funkci spoleˇcenského blahobytu F, je mnoˇzina/podmnoˇzina W ⊂ Q: ◮

semi-rozhoduj´ıc´ı dvojici (x, y ), plat´ı-li x ≻ y pro vˇsechny ρ ∈ RN , kde x ≻i y ; ∀i ∈ W a y ≻j x; ∀j ∈ Q \ W . Rozdˇelen´ı spoleˇcnosti na dva t´ abory.

◮

rozhoduj´ıc´ı dvojici (x, y ), plat´ı-li x ≻ y pro vˇsechny ρ ∈ RN , kde x ≻i y ; ∀i ∈ W .

◮

rozhoduj´ıc´ı, pokud je rozhoduj´ıc´ı dvojici (x, y ) pro vˇsechny x, y ∈ A.

Základ leˇz´ı v semi-rozhoduj´ıc´ı mnoˇzinˇe W ⊂ Q pro x proti y : (∀i ∈ W : x ≻i y ∧ ∀j ∈ Q \ W : y ≻j x) ∧ x ≻ y Martin Hrub´ y


Pomocné lemma (field expansion lemma) Lemma Je-li F tranzitivn´ı funkce spoleˇcenského blahobytu, která je slabˇe Paretovská a IIA, pak W ⊂ Q je rozhoduj´ıc´ı, pokud je W semi-rozhoduj´ıc´ı dvojici (x, y ) pro nˇekter´ a x, y ∈ A. D˚ ukaz jako domac´ı pˇr´ıprava (projekt). Poˇzadavky lemma na F jsou (témˇeˇr) nesplnitelné. Plyne z toho, ˇze pokud je nˇejak´ a skupina voliˇc˚ u semi-rozhoduj´ıc´ı pro nˇejaký pár alternativ (x,y), pak je skupina rozhoduj´ıc´ı. Pro funkce F, které jsou slabˇe Paretovské a IIA, skupina, která semi-rozhoduje nˇejaké (x,y), rozhoduje nad vˇsemi alternativami. Dále z toho plyne, ˇze skupina rozhoduje vˇse nebo nerozhoduje v˚ ubec nic. Z definice, W mus´ı být maxim´ aln´ı. Diktátorstv´ı skupiny nen´ı problém (to je demokracie). Martin Hrub´ y


Dohoda spoleˇcnosti Pˇredpokládejme dva t´ abory lid´ı A (50) a B (10). ◮

A: x > y > z

◮

B: y > x > z

◮

Pˇredpokládejme existenci mechanismu F (x > y > z, y > x > z) =?

◮

Condorcet: x > y > z

◮

A semi-rozhoduje x > y , pak rozhoduje vˇse. ˇ je n´ Nastane vˇzdy: bud azor okol´ı v souladu s rozhoduj´ıc´ı skupinou nebo nem´ a n´ azor okol´ı vliv na výsledek voleb.

◮

Zd˚ uraznˇeme: existence skupiny se stejným n´ azorem neznamená prosazen´ı názoru. Zjiˇstˇen´ı rozhoduj´ıc´ı skupiny je ”ex post”.

Martin Hrub´ y


D˚ ukaz Arrowse ˇ je jednoˇclenn´ Ukáˇzeme, ˇze bud a skupina rozhoduj´ıc´ı (tzn. poruˇs´ıme nediktátorstv´ı) nebo je cel´ a spoleˇcnost nerozhoduj´ıc´ı (a t´ım poruˇs´ıme podm´ınku slabé Paretovskosti). Tj., pokud se celá spoleˇcnou nedohodne na lib. (x, y ), pak se nedohodne na niˇ cem. Pokud si dokáˇze spoleˇcnost odhlasovat nˇejaké (x, y ), pak je rozhoduj´ıc´ı, ale pravdˇepodobnˇe obsahuje dikt´ atora. Celkovˇe vzato ukáˇzeme, ˇze stanovené podm´ınky jsou vzájemnˇe nesluˇcitelné. Velmi d˚ uleˇzité: zkoum´ ame celý prostor RN a vˇsechny moˇzné F . Tzn., d˚ ukaz zaloˇz´ıme na situaci, kterou lze povaˇzovat za hypotetickou.

Martin Hrub´ y


D˚ ukaz Arrowse Pˇredpokládejme koneˇcnou mnoˇzinu alternativ A, kde |A| ≥ 3. Pro potˇreby sporu pˇredpokl´ adejme, ˇze F je tranzitivn´ı, nediktátorská, slabˇe Paretovská a IIA (najdeme libovolný pˇr´ıpad, kdy to neplat´ı a t´ım prokáˇzeme spor s pˇredpokladem). ˇ Z pˇredchoz´ıho lemma plyne, ˇze kaˇzd´ a skupina W ⊂ Q je bud rozhoduj´ıc´ı nebo nerozhoduje ˇz´ adné (x, y ). Tvrzen´ı: pouze jedna (maximáln´ı) skupina m˚ uˇze být rozhoduj´ıc´ı. Pˇredpokládejme dvˇe disjunktn´ı mnoˇziny (pr´ azdný pr˚ unik) J, K ⊂ Q, které nejsou semi-rozhoduj´ıc´ı pro libovolné x,y (a t´ım nerozhoduj´ı v˚ ubec). Nechˇt L = Q \ (J ∪ K ). Protoˇze N > 2 a neexistuje singleton (jednoprvkov´ a mnoˇzina) {i }, která by byla rozhoduj´ıc´ı, pak J,K,L mohou existovat.

Martin Hrub´ y


D˚ ukaz Arrowse Dále pˇredpokládejme profil ρ− ∈ RN takový, ˇze: − ∀i ∈ J x ≻− i y ≻i z − − z ≻j x ≻j y ∀j ∈ K − y ≻− ∀t ∈ L t z ≻t x

Protoˇze J a K jsou ne-semi-rozhoduj´ıc´ı pro jakýkoliv pár, plyne z toho celkovˇe z − x a y − z. Pokud je F opravdu tranzitivn´ı, znamená to nav´ıc y − x. Z toho plyne, ˇze skupina J ∪ K je ne-semi-rozhoduj´ıc´ı pro (x, y ), a t´ım ˇze J ∪ K je celkovˇe nerozhoduj´ıc´ı. Sjednocen´ı dvou nerozhoduj´ıc´ıch skupin tvoˇr´ı tedy opˇet nerozhoduj´ıc´ı mnoˇzinu.

Martin Hrub´ y


D˚ ukaz Arrowse Z pˇredpokladu nediktátorstv´ı plyne, ˇze ˇz´ adn´ a singleton skupina nem˚ uˇze být rozhoduj´ıc´ı. Závˇerem tedy ˇzádná skupina voliˇc˚ u voliˇc˚ u (vˇcetnˇe Q) nem˚ uˇze být rozhoduj´ıc´ı a to poruˇsuje pˇredpoklad slabé Paretovskosti. Pozor: naˇsli jsme hypotetickou konfiguraci, kdy m˚ uˇze nastat, ˇze celá skupina Q m˚ uˇze být ne-semi-rozhoduj´ıc´ı jeden pár alternativ, coˇz implikuje, ˇze nerozhodne nic. Jiné teorémy zjemˇ nuj´ı Arrow˚ uv paradox zaveden´ım omezen´ı, kter´ a vyluˇcuj´ı takové blokuj´ıc´ı situace. Pozn.: Existuj´ı formulace d˚ ukazu Arrow’s Impossibility Theoremu, které prokáˇz´ı existenci dikt´ atora (d´ ale v projektech).

Martin Hrub´ y


Funkce veˇrejné volby

Zat´ım jsme konstruovali funkci, kter´ a vytv´ aˇrela kolektivn´ı preferenci. Zjednoduˇs´ıme problém na volbu jednoho v´ıtˇeze (uˇz nebudeme potˇrebovat konstruovat kompletn´ı preferenci).

Definition Funkce veˇrejné volby G : RN → A zobrazuje dané preferenˇcn´ı profily na mnoˇzinu alternativ. Funkce G je funkce na mnoˇzinu, tzn. kaˇzd´ a volba a ∈ A má preferenˇcn´ı profil, který vede na a.

Martin Hrub´ y


Strategická manipulovatelnost Definition G (ρ) je manipulovateln´ a v profilu ρ, pokud pro nˇekterého i ∈ Q existuje profil ρ′ = (R1 , ..., Ri −1 , Ri′ , Ri +1 , ...) takový, ˇze G (ρ′ ) ≻i G (ρ). G je nemanipulovateln´ a (incentive compatible), pokud nen´ı manipulovateln´ a ve vˇsech ρ ∈ RN . Funkce veˇrejné volby je tedy manipulovateln´ a, pokud nˇekterý hráˇc m˚ uˇze zmˇenou prezentace své preference dos´ ahnout výsledku, který preferuje. Paralela: preference hr´ aˇce je jeho strategie, profil je strategický profil. Uˇzitek hráˇce je d´ an um´ıstˇen´ım v´ıtˇeze v hr´ aˇcovˇe preferenci. Pokud hráˇc dokáˇze zmˇenou své strategie posunout svého preferovaného kandidáta výˇse k výhˇre, zvyˇsuje sv˚ uj uˇzitek. Martin Hrub´ y


Gibbard-Satterthwait˚ uv teorém Definition Voliˇc i je diktátor v rámci G , jestliˇze pro vˇsechny ρ ∈ RN a ∀b ∈ A : b 6= a : a ≻i b ⇒ G (ρ) = a. G se nazýv´ a diktatura, pokud existuje i takový, ˇze je dikt´ ator. Diktátor se tedy prosad´ı v kaˇzdém profilu. Zat´ım jsme uvaˇzovali manipulovatelnost.

Theorem Pokud existuj´ı tˇri a v´ıce alternativy, a G je nemanipulovatelná, pak existuje diktátor. Co z toho plyne? M˚ uˇzeme zajistit, aby G byla odolná proti strategické manipulaci, dikt´ ator se vˇsak stejnˇe projev´ı. Martin Hrub´ y


Gibbard-Satterthwait˚ uv teorém

Zjednoduˇsenˇe d˚ ukaz tvrzen´ı: M´ ame mnoˇzinu alternativ A. Pak m˚ uˇzeme sestrojit tranzitivn´ı a IIA funkci veˇrejné volby, která zvol´ı v´ıtˇeze v1 = G (A). V dalˇs´ım kole ubereme z A prvek v1 a hledáme v2 = G (A \ {v1 }) a tak d´ al. Vytvoˇr´ıme tedy preferenˇcn´ı uspoˇrádán´ı v1 ≻ v2 ≻ ..., které je ovˇsem slabˇe Paretovské. Dostali jsme se tak k vytvoˇren´ı spoleˇcenské preference (funkce spoleˇcenského blahobytu) a z Arrowova teorému plyne, ˇze proces musel ovlivnit diktátor.

Martin Hrub´ y


Stable Matchings problem

◮

Model zpárován´ı podle preferenc´ı (muˇzi a ˇzeny, studenti a koleje, zamˇestnanci a firmy).

◮

Mnoˇzina M = {m1 , m2 , ...} muˇz˚ u a mnoˇzina W = {w1 , w2 , ...}.

◮

Zavedeme preference obvyklým zp˚ usobem, pˇredpokládáme |M| = |W |.

◮

Zpárován´ı je vytvoˇren´ı R ⊂ M × W , ˇze kaˇzdý muˇz je spárován právˇe s jednou ˇzenou a naopak

Martin Hrub´ y


Stable Matchings problem Ukázka dˇelen´ı 1:1 nedˇelitelného zboˇz´ı bez postrann´ıch plateb (finanˇcn´ı kompenzace). Existuj´ı dalˇs´ı modely.

Definition Mˇejme Stable-Matchings problém. Zp´ arov´ an´ı se nazývá nestabiln´ı, ′ pokud jsou dva muˇzi m, m a dvˇe ˇzeny w , w ′ , ˇze: ◮

m je zpárováno s w

◮

m′ je zpárováno s w ′

◮

w ′ ≻m w a m ≻w ′ m ′

Pár (m, w ′ ) se nazývá blokuj´ıc´ı p´ ar. Zp´ arov´ an´ı, kde nen´ı blokuj´ıc´ı pár, se nazývá stabiln´ı. Skupinov´ a racionalita (skupina se m˚ uˇze odtrhnout a zaˇr´ıdit se po svém).

Martin Hrub´ y


Demo

≻ m1 w2 w1 w3

≻ m2 w1 w3 w2

≻ m3 w1 w2 w3

≻w1 m1 m3 m2

≻w2 m3 m1 m2

≻w3 m1 m3 m2

Zpárován´ı {(m1 , w1 ), (m2 , w2 ), (m3 , w3 )} je nestabiln´ı, protoˇze (m1 , w2 ) je blokuj´ıc´ı p´ ar. Zp´ arov´ an´ı {(m1 , w1 ), (m3 , w2 ), (m2 , w3 )} je stabiln´ı. Otázka: je vˇzdy moˇzné naj´ıt stabiln´ı zp´ arov´ an´ı?

Martin Hrub´ y


Algoritmus pro zpárován´ı–muˇzská iniciativa

1. Kaˇzdý muˇz zaˇsle n´ avrh své nejpreferovanˇejˇs´ı ˇzenˇe. 2. Kaˇzdá ˇzena, která obdrˇzela v´ıce n´ avrh˚ u, vybere z nich nejpreferovanˇejˇs´ıho muˇze a zbytek odm´ıtne. 3. Odm´ıtnut´ı muˇzi zaˇslou n´ avrh nejpreferovanˇejˇs´ı ˇzenˇe, která je jeˇstˇe neodm´ıtla. 4. Opakuje se, dokud existuje nezp´ arovaný muˇz.

Theorem Algoritmus pro zpárov´ an´ı–muˇzsk´ a varianta konˇc´ı ve stabiln´ım zpárován´ı. D˚ ukaz pˇri domác´ı pˇr´ıpravˇe ([Nisan]).

Martin Hrub´ y


Algoritmus pro zpárován´ı–muˇzská iniciativa ◮

◮

ˇ Oznaˇcme zpárován´ı jako µ. Zena w pˇriˇrazen´ a v párován´ı µ muˇzi m je oznaˇcena µ(m). Podobnˇe muˇz: µ(w ). Zpárován´ı µ je výhodnˇejˇs´ı pro muˇze (male-optimal), pokud neexistuje jiné zp´ arov´ an´ı ν: ◮ ◮ ◮

◮

∀m ∈ M : ν(m) ≻m µ(m) ∀m ∈ M : ν(m) = µ(m) ∧ ∃j ∈ M : ν(j) ≻j µ(j) tzn. slabá preference ν nad µ

Podobnˇe lze definovat zp´ arov´ an´ı výhodnˇejˇs´ı pro ˇzeny (female-optimal).

Theorem Algoritmus pro zpárov´ an´ı–muˇzsk´ a varianta je výhodnˇejˇs´ı pro muˇze (male-optimal). D˚ ukaz pˇri domác´ı pˇr´ıpravˇe ([Nisan]). Martin Hrub´ y


Algoritmus pro zpárován´ı M˚ uˇze existovat zpárov´ an´ı, které by nezvýhodˇ novalo jednu skupinu? Nelze... M˚ uˇze existovat skupina S ⊂ M ∪ W , kter´ a by mˇela zájem na vlastn´ı dohodˇe? Formálnˇe:

Definition Zpárován´ı µ′ dominuje nad µ, pokud existuje skupina S ⊂ M ∪ W taková, ˇze pro vˇsechny m, w ∈ S plat´ı souˇcasnˇe: ◮

µ′ (m), µ′ (w ) ∈ S

◮

µ′ (m) ≻m µ(m) a µ′ (w ) ≻w µ(w )

Stabilita je zvláˇstn´ı pˇr´ıpad dominance, kde se omez´ıme pouze na mnoˇziny S obsahuj´ıc´ı pouze jeden p´ ar. Mnoˇzina nedominovaných zpárován´ı se nazývá jádro (core) p´ arovac´ı hry.

Martin Hrub´ y


Algoritmus pro zpárován´ı–závˇer Theorem Jádro párovac´ı hry je tvoˇreno mnoˇzinou stabiln´ıch zpárován´ı. Zat´ım jsme pˇredpokládali, ˇze preference hr´ aˇc˚ u jsou common ˇ knowledge. Rekneme, ˇze funkce spoleˇcenské volby je strategy-proof, pokud je pro hr´ aˇce slabˇe dominantn´ı strategi´ı prezentovat své preference pravdivˇe.

Theorem Algoritmus pro zpárov´ an´ı–muˇzsk´ a varianta je ze strany muˇz˚ u strategy-proof. D˚ ukaz, ˇze muˇzi ˇr´ıkaj´ı pravdu je na stranˇe 258 [Nisan].

Martin Hrub´ y


Pˇr´ıˇstˇe

Mechanismy s penˇezi. ◮

Aukce.

◮

Vickrey-Clarke-Groves mechanismus.

◮

Revenue Equivalence Theorem.

Martin Hrub´ y


THE: Mechanism design

Recommend Documents