Doprovodné texty ke kurzu Teorie her

Doprovodné texty ke kurzu Teorie her

Martin Hrubý Fakulta informaˇcn´ıch technologi´ı Vysoké uˇcen´ı technické v Brnˇe

zimn´ı semestr, akad. rok 2010/11

1

Contents 1

Mechanism design

2

Teorie veˇrejné volby 2.1 Vˇetˇsinová volba a preference voliˇce . . . . . . . . . . . . . . . . ´ 2.2 Uloha volebn´ıch mechanism˚u . . . . . . . . . . . . . . . . . . . . 2.3 Condorcet˚uv paradox . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Strategická manipulace volebn´ıch mechanism˚u . . . . . . . . . . 2.5 Mechanismus Borda count . . . . . . . . . . . . . . . . . . . . . 2.6 Formáln´ı zaveden´ı volebn´ıch situac´ı . . . . . . . . . . . . . . . . 2.7 Funkce spoleˇcenského blahobytu (Social welfare function) . . . . 2.7.1 Podm´ınka tranzitivity . . . . . . . . . . . . . . . . . . . . 2.7.2 Podm´ınka nediktátorstv´ı . . . . . . . . . . . . . . . . . . 2.7.3 Podm´ınka Pareto optimality . . . . . . . . . . . . . . . . 2.7.4 Podm´ınka Nezávislosti na irelevantn´ıch alternativách (IIA) 2.8 Arrow’s paradox . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9 Funkce veˇrejné volby . . . . . . . . . . . . . . . . . . . . . . . . 2.9.1 Gibbard-Satterthwait˚uv teorém . . . . . . . . . . . . . . .

3

4

Teorie aukc´ı 3.1 Uˇzitek z aukce . . . . . . . . . . . . . . . . . . . . 3.2 Základn´ı typy aukc´ı . . . . . . . . . . . . . . . . . 3.3 Strategická ekvivalence anglické a holandské aukce 3.4 Ekvilibrium v tajných aukc´ıch . . . . . . . . . . . 3.5 Vliv citlivosti k riziku na ekvilibrium v aukci . . . 3.6 Vickrey-Clarke-Groves mechanismus . . . . . . . 3.6.1 Notace . . . . . . . . . . . . . . . . . . . 3.6.2 Mechanismus (direct revelation) . . . . . . 3.6.3 VCG-mechanismus . . . . . . . . . . . . . 3.6.4 Clarke Pivot Rule . . . . . . . . . . . . . .

2

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

5 5 6 7 7 8 8 8 9 9 9 10 11 12 13

. . . . . . . . . .

14 14 15 16 17 18 19 20 20 21 21

3.7

Pˇr´ıklady aplikace VCG-mechanismu . . . . . . . . . . . . . . . . . . . . . . . . . .

3

22

Chapter 1 Mechanism design Do tohoto okamˇziku jsme mˇeli moˇznost studovat modely hern´ıch situac´ı, které se rˇ´ıdily nˇejakými pˇredem známými pravidly. Proˇsli jsme nekooperativn´ı hry vˇsech forem, vyjednáván´ı a kooperativn´ı hry. V Mechanism designu se celá u´ loha otoˇc´ı. C´ılem Mechanism designu (ˇcesky snad Návrhu pravidel) bude navrhnout pravidla situace, ve které se posléze budou pohybovat strategiˇct´ı hrácˇ i sleduj´ıc´ı vlastn´ı c´ıle. Pravidla budeme navrhovat s ohledem na to, aby se hrácˇ i chovali vlivem vlastn´ı racionality tak, jak si pˇrejeme, aby se chovali. Typicky budeme poˇzadovat, aby hrácˇ i byli racionalitou nuceni nám sdˇelit své tajné preference týkaj´ıc´ı se vˇeci, o kterou se hraje. Mechanism design je velmi sˇiroký pojem zasahuj´ıc´ı do oblasti ekonomie, sociáln´ıch vˇed, ale i informatiky. Zejména ˇreˇs´ı problémy: • Ekonomických mechanism˚u vˇsech forem – trh˚u, výbˇerových ˇr´ızen´ı, ... • Elektronických forem obchodován´ı. • Aukc´ı. • Veˇrejných rozhodnut´ı, napˇr´ıklad volebn´ıch mechanism˚u. V THE se zamˇeˇr´ıme na oblast Teorie veˇrejné volby (Social/Public choice) a Teorie aukc´ı (Auction theory).

4

Chapter 2 Teorie veˇrejné volby Teorie veˇrejné volby se netýká pouze volebn´ıch mechanism˚u do r˚uzných veˇrejných funkc´ı (prezident, pˇredseda, zastupitel, parlamentn´ı poslanec). Vˇec volby vn´ımá obecnˇe jako rozhodnut´ı o zvolen´ı alternativy a z mnoˇziny moˇzných alternativ A, která je spoleˇcnost´ı – tedy mnoˇzinou voliˇcu˚ – vn´ımána jako veˇrejnˇe a spoleˇcensky optimáln´ı volba. Spoleˇcnost zde vystupuje jako (obvykle koneˇcná) mnoˇzina voliˇcu˚ Q, kde jednoho z voliˇcu˚ budeme tradiˇcnˇe oznaˇcovat i. Kaˇzdý voliˇc vˇzdy, jako kaˇzdý racionáln´ı hrácˇ , sleduje svoje individuáln´ı preference a t´ım i svou individuáln´ı racionalitu. Pokud je spoleˇcnost´ı voliˇcu˚ zvolena jeho preferovaná alternativa, c´ıt´ı z toho jakýsi uˇzitek. C´ılem voliˇce je tedy dosáhnout stavu, kdy spoleˇcnost bude preferovat (zvol´ı) jeho preferovanou alternativu.

2.1

Vˇetˇsinová volba a preference voliˇce

Pˇredstavme si situaci, kdy mnoˇzina voliˇcu˚ stoj´ı pˇred problémem spoleˇcné volby jedné alternativy z mnoˇziny A. T´ım problémem je zvolit mechanický postup takový, aby zvolená alternativa odpov´ıdala skuteˇcným preferenc´ım spoleˇcnosti. Jinak ˇreˇceno, otázkou je jak ty volby provést. Tradiˇcn´ı metodou (mechanismem) je vˇetˇsinová volba. Voliˇci zvol´ı svou alternativu a tu ohlás´ı nezávislému arbitrovi ve formˇe svého hlasu. Arbitr seˇcte hlasy pro jednotlivé alternativy a ohlás´ı alternativu a∗ ∈ A, která z´ıskala nejv´ıce hlas˚u. Zkoumejme tuto situaci nejprve s dvˇema alternativami, tzn. |A| = 2. Volby mohou skonˇcit jasnou vˇetˇsinou pro jednu alternativu nebo nerozhodnˇe (poˇcty hlas˚u pro alternativy se rovnaj´ı). Jasná vˇetˇsina vede k jasné volbˇe a mechanismus vˇetˇsinové volby je pak ideáln´ım volebn´ım mechanisme. Problém m˚uzˇ e nastat, pokud volby skonˇc´ı nerozhodnˇe. Myˇslenka volby zopakovat nevede ke koncepˇcn´ımu ˇreˇsen´ı, neboˇt nem˚uzˇ eme oˇcekávat, zˇ e na druhé kolo voliˇci zmˇen´ı své preference. Je nutno se vyrovnat s faktem, zˇ e volby vˇzdy nemus´ı skonˇcit jednoznaˇcným výsledkem. Mˇejme následuj´ıc´ı pˇr´ıklad na obrázku 2.1. Tabulka na obrázku prezentuje preference tˇr´ı voliˇcu˚ I = {i1 , i2 , i3 } nad alternativami J, K, L. Voliˇc i1 má tedy preference J i K i L. Pˇri vˇetˇsinové 5

volbˇe zv´ıtˇez´ı alternativa J. Preference/Voliˇci: i1 1. J 2. K 3. L

i2 J L K

i3 K L J

Figure 2.1: Ukázka preferenc´ı voliˇcu˚ ve volbách S poˇctem alternativ (kandidát˚u) se pravdˇepodobnost na nerozhodnost výsledku zvyˇsuje. Nav´ıc s výsledkem vznikaj´ı i protesty tˇech voliˇcu˚ , jejichˇz alternativa nen´ı vybrána ve vˇetˇsinové volbˇe. Mˇejme 100 voliˇcu˚ a tˇri alternativy se ziskem hlas˚u a = 40, b = 32 a c = 28. Proˇc by mˇela být zvolena alternativa a, kdyˇz si ji 60 voliˇcu˚ (tedy vˇetˇsina) nepˇreje?! M˚uzˇ eme systém voleb vylepˇsit duely alternativ jako pˇri fotbalovém sˇampionátu. T´ım zdánlivˇe pˇrevedeme problém volby mezi v´ıce alternativami na problém volby mezi dvˇema alternativami. Voliˇcu˚ m bude poloˇzena otázka, zda-li preferuj´ı a nebo b. Voliˇcu˚ m alternativ a a b bude otázka jasná, jak ovˇsem na ni zareaguj´ı voliˇci alternativy c? Pˇripomeˇnme základn´ı pˇredpoklad pro smysluplnost preference hrácˇ e: preferenˇcn´ı relace mus´ı ´ být upln´ a a tranzitivn´ı. Voliˇci alternativy c mus´ı m´ıt tedy názor na preferenci mezi a a b. Vzniká tak preferenˇcn´ı relace kaˇzdého voliˇce. Notace pro teorii veˇrejné volby Zavedli jsme mnoˇzinu alternativ A a mnoˇzinu voliˇcu˚ Q. Nyn´ı zavedeme preferenˇcn´ı relaci nad alternativami – tato je z principu vˇeci obecnˇe odliˇsná pro kaˇzdého voliˇce. Relace slabé preference voliˇce i nad mnoˇzinou alternativ A nechˇt je u´ plná, tranzitivn´ı a reflexivn´ı relace i ⊆ A × A. Z relace slabé preference plyne i obvyklá formulace striktn´ı (ostré) preference i . Nové pro nás budou relace zohledˇnuj´ıc´ı preferenci celé spoleˇcnosti – a (tedy bez doln´ıho indexu i oznaˇcuj´ıc´ıho hrácˇ e).

2.2

´ Uloha volebn´ıch mechanismu˚

Pˇri zkoumán´ı volebn´ıch mechanism˚u nás bude zaj´ımat jednak problém zvolen´ı alternativy a pak pˇredevˇs´ım problém sestaven´ı celkové preference spoleˇcnosti. Od poˇca´ tku pˇredpokládáme, zˇ e c´ılem spoleˇcnosti je zvolit alternativu, která je pro spoleˇcnost jaksi pˇr´ınosná a preferovaná vˇetˇsinou. V Teorii veˇrejné volby proti sobˇe stoj´ı preference jedince (a jeho individuáln´ı uˇzitek) a preference spoleˇcnosti a s t´ım souvisej´ıc´ı veˇrejné blaho. Budeme pˇredpokládat, zˇ e spoleˇcnost chce volbou mechanismu voleb zajistit, aby byly volby spravedlivé a bez moˇznosti je manipulovat jedinci, kteˇr´ı s vˇetˇs´ım d˚urazem prosazuj´ı sv˚uj individuáln´ı zámˇer. Stále pˇredpokládáme, 6

zˇ e kaˇzdý voliˇc i ∈ Q má jediný zp˚usob chován´ı a t´ım je prezentace své individuáln´ı preference i . Právˇe prezentac´ı individuáln´ı preference m˚uzˇ e voliˇc volby manipulovat, jak pozdˇeji uvid´ıme.

2.3

˚ paradox Condorcetuv

Marie Jean Antoine Nicolas de Caritat, marquis de Condorcet (markýz de Condorcet, 1743–1794) byl francouzský filosof a matematik. Zabýval se volebn´ımi mechanismy a jako prvn´ı poukázal na koncepˇcn´ı nedostatek vˇetˇsinové volby (nen´ı odolná proti poruˇsen´ı tranzitivity). ˇ Jak probˇehne volba v situaci zobrazené na obrázku 2.2? Rekneme, zˇ e v´ıtˇez by mˇel být schopen zv´ıtˇezit v duelu s kaˇzdým protikandidátem. Tady jsou tedy ty duely: • Duel J:K (v´ıtˇez J, dva hlasy), tzn. celek J K • Duel J:L (v´ıtˇez L, dva hlasy), tzn. celek L J • Duel K:L (v´ıtˇez K, dva hlasy), tzn. celek K L V prvn´ım kole zv´ıtˇez´ı J, v druhém kole (J versus L) zv´ıtˇez´ı L. Je tedy L v´ıtˇezem voleb? Alternativa L zv´ıtˇezila nad obˇema protikandidáty, pˇresto toto plat´ı i opaˇcnˇe. V´ıtˇeze tedy nevid´ıme, ke vˇsemu je zmatek v celkové preferenci voliˇcu˚ : J K L J. Condorcet definoval v´ıtˇeze (tzv. Condorcet˚uv v´ıtˇez) jako alternativu X s tou vlastnost´ı, zˇ e pro kaˇzdou alternativu Y je poˇcet voliˇcu˚ preferuj´ıc´ıch X pˇred Y vˇetˇs´ı, neˇz poˇcet voliˇcu˚ preferuj´ıc´ıch Y pˇred X. Z principu tohoto mechanismu vˇsak Condorcet˚uv v´ıtˇez nemus´ı vˇzdy existovat, tzn. volby mohou skonˇcit patem.

2.4

Strategická manipulace volebn´ıch mechanismu˚

Na obrázku 2.2 je zobrazena jiná volebn´ı situace. Situace vede zˇrejmˇe k patovému výsledku voleb, neboˇt zˇ a´ dná alternativa nezv´ıtˇez´ı v duelech nad vˇsemi zbývaj´ıc´ımi. Pokud si napˇr´ıklad hrácˇ 3 tuto situaci uvˇedom´ı, m˚uzˇ e do voleb zasáhnout manipulac´ı své preference. Vycház´ıme z jeho pravdivé preference K i L i J, ze které je vidˇet, zˇ e se m˚uzˇ e obávat zvolen´ı alternativy J, jeho preferovaná alternativa K nen´ı ve spoleˇcnosti dostateˇcnˇe preferovaná, ale L je stále lepˇs´ı neˇz J. Kdyˇz tento strategický hrácˇ spoleˇcnosti bude prezentovat svou preferenci strategicky zmanipulovanou, tzn. L i K i J, dosáhne zvolen´ı alternativy L, která je pro nˇej stále jeˇstˇe pˇr´ıpustná. Tento postup je vˇsak spoleˇcnost´ı povaˇzován za sˇpatný.

7

Preference/Voliˇci: i1 1. J 2. K 3. L

i2 L J K

i3 K L J

Figure 2.2: Ukázka preferenc´ı voliˇcu˚ ve volbách II.

2.5

Mechanismus Borda count

Jean Charles de Borda (1733 – 1799) kritizoval volebn´ı mechanismy ve Francouzské akademii podobnˇe jako Condorcet. Navrhl rozdˇelit ”body” kandidát˚um: kaˇzdý voliˇc pˇridˇel´ı |A| svému prvn´ımu kandidátovi, |A| − 1 druhému, ..., jeden posledn´ımu. V´ıtˇez je kandidát s nejvyˇssˇ´ı sumou bod˚u. Zdá se to jako ideáln´ı metoda. Mnohdy vede k ˇreˇsen´ı, je ovˇsem strategicky manipulovatelná. Condorcetova metoda tud´ızˇ m˚uzˇ e poruˇsovat tranzitivitu a Bordova metoda poruˇsuje nemanipulovatelnost.

2.6

Formáln´ı zaveden´ı volebn´ıch situac´ı

Nechˇt A je mnoˇzina alternativ. Budeme formalizovat obor hodnot vˇsech moˇzných preferenc´ı. Definice 1. Mˇejme mnoˇzinu alternativ A. Mnoˇzina R obsahuje vˇsechna moˇzná uspoˇra´ dán´ı na mnoˇzinˇe A (je izomorfn´ı s permutacemi na A). Mnoˇzina R je principem totoˇzná s Si ve strategických hrách. Strategi´ı hrácˇ e-voliˇce je volba jeho preference, kterou bude spoleˇcnosti prezentovat. Pochopitelnˇe, jedna z nich je ta jeho pravdivá preference a zbylé jsou moˇzné manipulace. Podobnˇe RN je principem totoˇzná s mnoˇzinou strategických profil˚u S ve strategických hrách. Tud´ızˇ potˇrebujeme zavést pojem profil preferenc´ı: Definice 2. Mˇejme mnoˇzinu alternativ A a n voliˇcu˚ . Profilem ρ uspoˇra´ dán´ı preferenc´ı budeme rozumˇet uspoˇra´ danou n-tici ρ = (R1 , R2 , ..., Rn ) ∈ Rn Jeden profil ρ reprezentuje jednu moˇznou situaci, která m˚uzˇ e u voleb nastat. Je to vektor konkrétn´ıch prezentovaných preferenc´ı voliˇcu˚ . V následuj´ıc´ım odstavci zavedeme formálnˇe funkci, která na zadaný profil sestav´ı spoleˇcenskou preferenci nad alternativami.

2.7

Funkce spoleˇcenského blahobytu (Social welfare function)

Jádrem volebn´ıch mechanism˚u je tak zvaná funkce spoleˇcenského blahobytu. V literatuˇre se objevuje také pod názvem Social Agregation Function nebo Preference Agregation Rule. Tato funkce 8

je matematickým modelem volebn´ıho mechanismu – je to program, který na zadaný vstupn´ı profil preferenc´ı voliˇcu˚ vyhodnot´ı, jaká je celková preference spoleˇcnosti. My budeme tuto funkci zkoumat jako modelového pˇredstavitele volebn´ıho mechanismu. Pˇredevˇs´ım budeme zkoumat jej´ı vlastnosti a tedy i vlastnosti volebn´ıho mechanismu, které u spravedlivých voleb oˇcekáváme. Definice 3. Funkc´ı spoleˇcenského blahobytu (social welfare function) budeme rozumˇet funkci F : Rn → R Funkce F je mechanickým arbitrem (ˇr´ıd´ı se pravidly), která na zadané preference voliˇcu˚ sestav´ı preferenci celé spoleˇcnosti (základ pro volbu optima). Následuj´ıc´ı cˇ tyˇri podm´ınky (tranzitivita, nediktátorstv´ı, pareto optimalita a nezávislost na irelevantn´ıch alternativách) jsou ideálem spravedlivých voleb, tedy cˇ tyˇri vlastnosti, které u funkce spoleˇcenského blahobytu oˇcekáváme. V následuj´ıc´ım textu pˇredevˇs´ım dokázˇ eme (Arrow’s Impossibility Theorem), zˇ e nem˚uzˇ e obecnˇe existovat funkce spoleˇcenského blahobytu taková, aby pro vˇsechny myslitelné ρ ∈ Rn tyto podm´ınky splˇnovala.

2.7.1

Podm´ınka tranzitivity

Definice 4. Funkce spoleˇcenského blahobytu F je tranzitivn´ı, je-li F (ρ) tranzitivn´ı pro vˇsechny ρ ∈ RN . Tranzitivitu povaˇzujeme za minimáln´ı projev logiky rozhodován´ı (napˇr. pro nalezen´ı maxima). Arbitr voleb (tj. funkce spoleˇcenského blahobytu) mus´ı být schopen sestavit tranzitivn´ı spoleˇcenskou preferenci ve vˇsech moˇzných situac´ıch preferenc´ı jednotlivc˚u. V´ıme jiˇz z Condorcetova paradoxu, zˇ e to nen´ı aˇz tak garantováno.

2.7.2

Podm´ınka nediktátorstv´ı

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

2.7.3

Podm´ınka Pareto optimality

Definice 6. Funkce spoleˇcenského blahobytu F je slabˇe Pareto optimáln´ı, pokud x i y pro vˇsechny i ∈ Q zp˚usob´ı, zˇe x y pro libovolné x, y ∈ A. 1

S t´ımto souvis´ı pojem volebn´ı moci/s´ıly (angl. Voting power)

9

Tato podm´ınka je velmi pˇr´ımoˇcará: pokud si kaˇzdý zvlásˇˇt preferuje x pˇred y, pak i celek preferuje x pˇred y. Existuje jeˇstˇe striktnˇe Paretovská 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á optimalita v tomto pˇr´ıpadˇe nesouvis´ı se slabost´ı/striktnost´ı preference. S podm´ınkou Pareto optimality bude také problém, neboˇt v d˚ukazu Arrowova theoremu ukázˇ eme, zˇ e m˚uzˇ e nastat situace, zˇ e celá spoleˇcnost nebude schopna rozhodnout (zvolit) zˇ a´ dnou z alternativ.

2.7.4

Podm´ınka Nezávislosti na irelevantn´ıch alternativách (IIA)

Independence of irrelevant alternatives (IIA) je pˇr´ıtomna ve vˇsech cˇ a´ stech THE posuzuj´ıc´ıch preference. Formálnˇe je definovaná: Definice 7. Funkce spoleˇcenského blahobytu F je nezávislá na irelevantn´ıch alternativách, pokud plat´ı pro libovolné x, y ∈ A a libovolné dva profily ρ, ρ0 ∈ RN , zˇe x i y ⇔ x 0i y pro vˇsechny i ∈ Q implikuje x y ⇔ x 0 y. Máme dva pohledy na vˇec: ρ, ρ0 ∈ RN , pokud v obou vˇsichni hrácˇ i 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ácˇ i stejný názor na preferenci na {x, y}, mˇely by být obˇe výsledné spoleˇcenské preference konzistentn´ı v otázce preference mezi {x, y}. Také lze tuto podm´ınku vyloˇzit tak, zˇ e vznik nebo zánik alternativy c (která se pochopitelnˇe zaˇrad´ı nˇekam do preferenˇcn´ıho seˇrazen´ı preferenc´ı) nem˚uzˇ e ovlivnit preferenci mezi a a b, tzn. pokud byla a b, pak zaveden´ım alternativy c se nesm´ı a b zmˇenit na b a. Demonstrace poruˇsen´ı IIA Uvaˇzujme Borda count jako volebn´ı mechanismus (tedy specifikaci funkce spoleˇcenského blahobytu), který zp˚usob´ı následuj´ıc´ı výsledky voleb daných situac´ı na obrázku 2.3: A – 11 bod˚u, D – 8 bod˚u, tedy pˇredevˇs´ım A D.

1. 2. 3. 4.

V A B C D

W A C B D

X B C D A

Y Z B C C B D D A A

Figure 2.3: Pˇr´ıklad poruˇsen´ı IIA-I Omez´ıme-li se pouze na alternativy {A, D}, pak podle obrázku 2.4 dostáváme výsledky: A – 7 bod˚u, D – 8 bod˚u, tedy D A. Alternativy {B, C} jsou zde chápány z pohledu {A, D} jako irelevantn´ı, pˇresto jejich nepˇr´ıtomnost zp˚usob´ı zmˇenu výsledné spoleˇcenské preference.

10

V 1. A 2. D

W A D

X D A

Y Z D D A A

Figure 2.4: Pˇr´ıklad poruˇsen´ı IIA-I

2.8

Arrow’s paradox

Theorém Kennetha Arrowa nazývaný Arrow’s paradox nebo také Arrow’s impossibility theorem je ˇ ıká, zˇ e pˇri tˇrech a v´ıce alternavn´ımán jako nejvýznamnˇejˇs´ı výsledek ve spoleˇcenských vˇedách. R´ tivách nelze naj´ıt spoleˇcenskou funkci blahobytu takovou, aby obecnˇe pro vˇsechny moˇzné preferenˇcn´ı profily zachovávala cˇ tyˇri výsˇe popsané podm´ınky pro spravedlivou volbu. Jako d˚usledek mus´ıme pˇrijmout fakt, zˇ e jedna z tˇechto podm´ınek bude vˇzdy poruˇsena a skoro si m˚uzˇ eme vybrat, která to bude. Vˇeta 1 (Arrow’s paradox (Arrow’s impossibility theorem)). Je-li A koneˇcná mnoˇzina alternativ s alespoˇn tˇremi alternativami, pak neexistuje spoleˇcenská agregaˇcn´ı funkce F : RN → R, která je tranzitivn´ı, nediktátorská, slabˇe Pareto optimáln´ı a nezávislá na irelevantn´ıch alternativách. 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ˇra´ danou dvojici (x, y). Definice 8. 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 . • 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. Jednoduˇse ˇreˇceno, rozhodnout x proti y znamená zp˚usobit, zˇ e celá spoleˇcnost preferuje x proti y. Základ rozhodován´ı dvou alternativ leˇz´ı v semi-rozhoduj´ıc´ı mnoˇzinˇe W ⊂ Q pro x proti y (vˇsimnˇemi si, zˇ e zbytek spoleˇcnost preferuje pravý opak): (∀i ∈ W : x i y ∧ ∀j ∈ Q \ W : y j x) ⇒ x y Lemma 2. 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á x, y ∈ A. Plyne z toho, zˇ e pokud je nˇejaká skupina voliˇcu˚ 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á semirozhoduje nˇejaké (x,y), rozhoduje nad vˇsemi alternativami. Dále z toho plyne, zˇ e budˇ skupina ˚ rozhoduje vˇse nebo nerozhoduje vubec nic. Z definice, W mus´ı být maximáln´ı. 11

Ukázˇ eme, zˇ e budˇ je jednoˇclenná skupina rozhoduj´ıc´ı (tzn. poruˇs´ıme nediktátorstv´ı) nebo je celá spoleˇcnost nerozhoduj´ıc´ı (a t´ım poruˇs´ıme podm´ınku slabé Paretovskosti). Celkovˇe vzato ukázˇ eme, zˇ e stanovené podm´ınky jsou vzájemnˇe nesluˇcitelné. Je velmi d˚uleˇzité znovu zd˚uraznit, zˇ e zkoumáme celý prostor RN a vˇsechny moˇzné F . Tzn., d˚ukaz zaloˇz´ıme na situaci, kterou lze povaˇzovat za hypotetickou. D˚ukaz Arrowova paradoxu. Pˇredpokládejme koneˇcnou mnoˇzinu alternativ A, kde |A| ≥ 3. Pro potˇreby sporu pˇredpokládejme, zˇ e F je tranzitivn´ı, nediktátorská, slabˇe Paretovská a IIA (najdeme libovolný pˇr´ıpad, kdy to neplat´ı a t´ım prokázˇ eme spor s pˇredpokladem). Z pˇredchoz´ıho lemma plyne, zˇ e kaˇzdá skupina W ⊂ Q je budˇ rozhoduj´ıc´ı nebo nerozhoduje zˇ a´ dné (x, y). Pˇredpokládejme dvˇe disjunktn´ı mnoˇziny (prázdný 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á mnoˇzina) {i}, která by byla rozhoduj´ıc´ı, pak J,K,L mohou existovat. Dále pˇredpokládejme profil ρ− ∈ RN takový, zˇ e: − x − ∀i ∈ J 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, zˇ e skupina J ∪ K je ne-semi-rozhoduj´ıc´ı pro (x, y), a t´ım zˇ e J ∪ K je celkovˇe nerozhoduj´ıc´ı. Sjednocen´ı dvou nerozhoduj´ıc´ıch skupin tvoˇr´ı tedy opˇet nerozhoduj´ıc´ı mnoˇzinu. Z pˇredpokladu nediktátorstv´ı plyne, zˇ e zˇ a´ dná singleton skupina nem˚uzˇ e být rozhoduj´ıc´ı. Závˇerem tedy zˇ a´ dná skupina voliˇcu˚ voliˇcu˚ (vˇcetnˇe Q) nem˚uzˇ e být rozhoduj´ıc´ı a to poruˇsuje pˇredpoklad slabé Paretovskosti.

Naˇsli jsme hypotetickou konfiguraci, kdy m˚uzˇ e nastat, zˇ e celá skupina Q m˚uzˇ e být ne-semirozhoduj´ıc´ı jeden pár alternativ, coˇz implikuje, zˇ e nerozhodne nic. Jiné teorémy zjemˇnuj´ı Arrow˚uv paradox zaveden´ım omezen´ı, která vyluˇcuj´ı takové blokuj´ıc´ı situace. Existuj´ı formulace d˚ukazu Arrow’s Impossibility Theoremu, které prokázˇ´ı existenci diktátora.

2.9

Funkce veˇrejné volby

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

12

Definice 9. 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á volba a ∈ A má preferenˇcn´ı profil, který vede na a. Definice 10. G(ρ) je manipulovatelná v profilu ρ, pokud pro nˇekterého i ∈ Q existuje profil ρ0 = (R1 , ..., Ri−1 , Ri0 , Ri+1 , ...) takový, zˇe G(ρ0 ) i G(ρ). G je nemanipulovatelná (incentive compatible), pokud nen´ı manipulovatelná ve vˇsech ρ ∈ RN . Funkce veˇrejné volby je tedy manipulovatelná, pokud nˇekterý hrácˇ i m˚uzˇ e zmˇenou prezentace své preference z Ri na Ri0 dosáhnout výsledku, který preferuje (coˇz je v definici výsˇe popsáno jako G(ρ0 ) i G(ρ)). Stále to berme tak, zˇ e preference hrácˇ e je jeho strategie a profil je strategický profil. Uˇzitek hrácˇ e je dán um´ıstˇen´ım v´ıtˇeze v hrácˇ ovˇe preferenci. Pokud hrácˇ dokázˇ e zmˇenou své strategie posunout svého preferovaného kandidáta výsˇe k výhˇre, zvyˇsuje sv˚uj uˇzitek.

2.9.1

˚ teorém Gibbard-Satterthwaituv

Definice 11. 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á diktatura, pokud existuje i takový, zˇe je diktátor. Zat´ım jsme uvaˇzovali manipulovatelnost, coˇz je slabˇs´ı vlastnost neˇz diktátorstv´ı. U manipulovatelnosti musel existovat profil ρ0 takový, zˇ e hrácˇ v rámci tohoto profilu mohl manipulovat. Vedle toho, diktátor prosad´ı a ∈ A v kaˇzdém profilu ρ. Vˇeta 3 (Gibbard-Satterthwait˚uv teorém). Pokud existuj´ı tˇri a v´ıce alternativy, a G je nemanipulovatelná, pak existuje diktátor. Co z toho plyne? M˚uzˇ eme zajistit, aby G byla odolná proti strategické manipulaci, diktátor se vˇsak stejnˇe projev´ı. Zjednoduˇsenˇe d˚ukaz tvrzen´ı: Máme mnoˇzinu alternativ A. Pak m˚uzˇ eme 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ál. Vytvoˇr´ıme tedy preferenˇcn´ı uspoˇra´ 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, zˇ e proces musel ovlivnit diktátor.

13

Chapter 3 Teorie aukc´ı Aukce (ˇcesky tézˇ draˇzba) je forma zobchodován´ı hmotného nebo nehmotného objektu (napˇr. licence), ve kterém se potká typicky jeden prodávaj´ıc´ı s typicky v´ıce kupuj´ıc´ımi, cena pˇredmˇetu zobchodován´ı nen´ı pˇredem známa a má být výsledkem interakce mezi kupuj´ıc´ımi. Lze pˇredpokládát, zˇ e aukce známe z bˇezˇ ného zˇ ivota v podobˇe veˇrejného setkán´ı kupuj´ıc´ıch a prodeje nˇejakého umˇeleckého pˇredmˇetu. V tˇechto filmových aukc´ıch m˚uzˇ e vzniknout u pozorovatele dojem, zˇ e hlavn´ım c´ılem kupuj´ıc´ıch je z´ıskat pˇredmˇet aukce – v nˇekterých pˇr´ıpadech témˇeˇr za libovolnou cenu. V bˇezˇ ných aukc´ıch to tak samozˇrejmˇe nen´ı – kupuj´ıc´ı je strategický hrácˇ jako kaˇzdý jiný, sleduje svou individuáln´ı racionalitu a tou je maximalizace jeho uˇzitku. V podobné situaci je i prodávaj´ıc´ı, který má zájem na maximáln´ım výnosu z aukce. Situaci si pˇredvedeme na aukci o jeden dolar. Mˇejme v draˇzbˇe jeden americký dolar (1 USD). Vyvolávac´ı cena nechˇt je jeden cent, tzn. 0.01 USD. Hrácˇ i mohou v draˇzbˇe pˇrihazovat s minimáln´ım povoleným pˇr´ıhozem jeden cent. Lze oˇcekávat, zˇ e se draˇzba zastav´ı na u´ rovni 0.99 dolaru nebo na jednom dolaru. U této aukce je vidˇet, zˇ e pˇredmˇet aukce má univerzálnˇe známou hodnotu. Toto nen´ı u jiných aukc´ıch obvyklé. Ohodnocen´ı pˇredmˇetu aukce je fenoménem aukc´ı – z pohledu kupuj´ıc´ıho, prodávaj´ıc´ıho i celé spoleˇcnosti1 .

3.1

Uˇzitek z aukce

Kaˇzdý kupuj´ıc´ı i si pˇredmˇet aukce privátnˇe ohodnot´ı na hodnotu xi . Je jeho pochopitelným zájmem tuto informaci nesdˇelovat ani konkuruj´ıc´ım kupuj´ıc´ım ani prodávaj´ıc´ımu. Pokud kupuj´ıc´ı i pˇredmˇet aukce vyhraje a zaplat´ı nˇejakou cenu yi , pak je jeho zisk z aukce dán ui = xi − yi 1

V literatuˇre je popsán stav, kdy kupuj´ıc´ı nadhodnot´ı pˇredmˇet aukce, v aukci zv´ıtˇez´ı, zaplat´ı vysokou cenu a aˇz po tom si uvˇedom´ı pravdivou hodnotu pˇredmˇetu. Tento stav je nazýván jako Winner’s curse (proklet´ı výherce). Podobnˇe je na tom dilema po proveden´ı rozhodnut´ı (Post-Decision Dissonance), kdy cˇ lovek pˇremýsˇl´ı, jestli se rozhodnul dobˇre.

14

Pˇredpokládáme individuáln´ı racionalitu kupuj´ıc´ıho, tedy situaci, kdy kupuj´ıc´ı chce maximalizovat sv˚uj zisk ui . Pokud kupuj´ıc´ı zaplat´ı cˇ a´ stku yi = xi , pak je ui = 0. Z´ıská-li tedy kupuj´ıc´ı pˇredmˇet aukce za takovou cenu, tak se jeho finanˇcn´ı bilance nezmˇen´ı (nemá z n´ı uˇzitek). Pˇred aukc´ı mˇel napˇr. 1000 penˇez, pˇredmˇet si ocenil na 1000 penˇez, vydraˇzil ho za 1000 penˇez, ty i zaplatil a má tedˇ ˇ adná zmˇena. pˇredmˇet, který si cen´ı na 1000 penˇez. Z´ Kupuj´ıc´ı do aukce vstupuje formou své sázky (angl. bid) bi . Je dost jisté, zˇ e racionáln´ı kupuj´ıc´ı nebude podávat sázku vyˇssˇ´ı neˇz je jeho ohodnocen´ı pˇredmˇetu, tedy jistˇe bi ≤ xi . Prodávaj´ıc´ı pochopitelnˇe nezná tajná ohodnocen´ı xi hrácˇ u˚ (to mezi sebou neznaj´ı ani hrácˇ i). M˚uzˇ e vˇsak pozorovat jejich sázky bi . Prodávaj´ıc´ımu je dále jasné, zˇ e jeho výnos z aukce nebude u standardn´ı aukce vyˇssˇ´ı neˇz Revenuemax = max[xi ] i∈Q

C´ılem prodávaj´ıc´ıho je proto stanovit takový mechanismus aukce, aby motivoval hrácˇ e k podáván´ı sázek bi takových, aby se co nejv´ıce bl´ızˇ ily jejich xi , nejlépe takových, aby bi = xi . Je toto moˇzné? M˚uzˇ ete donutit kupuj´ıc´ıho odhalit jeho tajné hodnocen´ı pˇredmˇetu aukce a souˇcasnˇe mu dát nadˇeji na kladný zisk? Uvid´ıme, zˇ e je to moˇzné u tak zvaných vickreyovských aukc´ı.

3.2

Základn´ı typy aukc´ı

Aukce maj´ı svou veˇrejnou a tajnou formu. Pˇri veˇrejné formˇe aukce na sebe hrácˇ i vid´ı, pozoruj´ı svoje chován´ı a mohou nˇejak usoudit o tajném ohodnocen´ı xi svých protivn´ık˚u. Tajné formy aukc´ı nejlépe odpov´ıdaj´ı tak zvané obálkové metodˇe (angl. sealed-bid auction). V podstatˇe to jsou strategické hry v normáln´ı formˇe (statické, jednotahové hry). Na veˇrejné formˇe aukce si pˇredvedeme základn´ı dva typy aukc´ı – aukci anglickou a holandskou.

Anglická veˇrejná aukce (vzestupná draˇzba) A anglické aukce (také angl. ascending auction) se stanov´ı poˇca´ teˇcn´ı (vyvolávac´ı) draˇzebn´ı cena a hrácˇ i maj´ı moˇznost postupnˇe tuto cenu zvyˇsovat svými pˇr´ıhozy, kterých m˚uzˇ e být libovolnˇe mnoho. Kaˇzdý pˇr´ıhoz tedy mus´ı zvýsˇit aktuáln´ı draˇzebn´ı cenu. Aukce se ukonˇc´ı, pokud jiˇz neexistuje hrácˇ , který by aktuáln´ı draˇzebn´ı cenu svým pˇr´ıhozem zvýsˇil. Hrácˇ , který um´ıstil posledn´ı pˇr´ıhoz, se stává v´ıtˇezem aukce a zaplat´ı draˇzebn´ı cenu. Z principu vˇeci lze usoudit, zˇ e hrácˇ i pˇrihazuj´ı, dokud je draˇzebn´ı cena niˇzsˇ´ı neˇz jejich xi . Pokud sestupnˇe seˇrad´ıme xi hrácˇ u˚ do posloupnosti xi , xj , xk , ... pak hrácˇ i z´ıskává pˇredmˇet aukce za cenu xj + δ, kde δ m˚uzˇ e být libovolnˇe malé. Fakticky tak plat´ı druhou nejvyˇssˇ´ı nab´ıdnutou cenu a realizuje zisk ui = xi − (xj + δ), kde δ byl jeho posledn´ı 15

pˇr´ıhoz. Prodávaj´ıc´ı se mus´ı sm´ıˇrit s faktem, zˇ e se hrácˇ ovo ohodnocen´ı xi nikdy nedozv´ı. Anglická aukce je nejpopulárnˇejˇs´ım aukˇcn´ım mechanismem. U anglické aukce fakticky kupuj´ıc´ıho nemus´ı zaj´ımat ohodnocen´ı xj jeho protivn´ık˚u, neboˇt pˇrihazuje do výsˇe svého xi . Dále uvid´ıme, zˇ e anglická aukce je strategicky nemanipulovatelná, tedy, hrácˇ nemá profit z toho, kdyˇz prezentuje svoje xi nepravdivˇe2 .

Holandská veˇrejná aukce (sestupná draˇzba) V holandské aukci (také angl. descending auction) je situace obrácená – poˇca´ teˇcn´ı cena je arbitrem aukce postupnˇe sniˇzována do okamˇziku, kdy se jeden z kupuj´ıc´ıch pˇrihlás´ı a cenu akceptuje. Ten se stává v´ıtˇezem aukce a tuto cenu i zaplat´ı. Tato aukce historicky vznikla na trz´ıch, kde bylo potˇreba zboˇz´ı rychle prodat (ryby, kvˇetiny). Z pohledu aukc´ı je ovˇsem holandská aukce velmi významná svým vztahem k citlivosti na riziko hrácˇ u˚ . Z principu aukce je evidentn´ı, zˇ e hrácˇ o vˇec zaˇcne jevit zájem aˇz v okamˇziku, kdy draˇzebn´ı cena klesne pod jeho xi . Aby maximalizoval sv˚uj zisk z aukce, mus´ı pak nechat draˇzebn´ı cenu vhodnˇe dál klesnout, pˇritom vˇsak se zvyˇsuje pravdˇepodobnost, zˇ e na cenu pˇristoup´ı nˇejaký z protivn´ık˚u. U holandské aukce je proto nutné provádˇet zkoumán´ı moˇzného ohodnocen´ı vˇeci protivn´ıky. V této aukci hraje znaˇcnou roli citlivost hrácˇ e k riziku, tedy jeho vztah mezi ziskem a dosaˇzeným uˇzitkem ze zisku. V pˇredchoz´ıch textech byl vztah mezi ziskem a uˇzitkem jiˇz zaveden. Pˇripomeˇnme, zˇ e hrácˇ neutráln´ı k riziku vn´ımá uˇzitek lineárnˇe rostouc´ı se ziskem, kdeˇzto hrácˇ citlivý k riziku (obávaj´ıc´ı se rizika) preferuje niˇzsˇ´ı ale jistˇejˇs´ı zisk pˇred vyˇssˇ´ım nejistým. Takový hrácˇ se v holandské aukci pˇrihlás´ı dˇr´ıve neˇz hrácˇ s neutráln´ım vztahem k riziku.

3.3

Strategická ekvivalence anglické a holandské aukce

Veˇrejná forma anglické a holandské aukce je rozd´ılná. V mnoha pˇr´ıpadech vˇsak prodávaj´ıc´ı preferuje tajnou (obálkovou, angl. sealed-bid) formu podáván´ı sázek. Proto m˚uzˇ e být zaj´ımavé srovnán´ı veˇrejných a tajných forem aukc´ı. Zavedeme si dvˇe formy tajné aukce: aukci s prvn´ı cenou a aukci s druhou cenou. Vˇzdy bude v´ıtˇezem hrácˇ s maximáln´ı podanou sázkou, tedy i∗ = arg max[bi ] i

Zbývá doˇreˇsit, jakou cenu hrácˇ zaplat´ı. V tajné aukci s prvn´ı cenou (first price sealed-bid auction, 1st price auction) zaplat´ı v´ıtˇez cenu na u´ rovni nejvyˇssˇ´ı sázky, tedy tu svoji nab´ıdnutou cenu. V tajné 2

V pokroˇcilejˇs´ım studiu se m˚uzˇ eme zabývat tak zvanými false-bidders, jakýmisi provokatéry v aukc´ıch. Jejich c´ılem je vyhnat aukˇcn´ı cenu do jejich zvolené u´ rovnˇe. Pochopitelnˇe cˇ el´ı riziku, zˇ e pˇredmˇet aukce vydraˇz´ı oni. To je ovˇsem pokroˇcilejˇs´ı problém.

16

aukci s druhou cenou (second price sealed-bid auction, 2nd price auction) zaplat´ı v´ıtˇez i∗ druhou nejvyˇssˇ´ı nab´ıdku, tedy ∗ yII = max∗ [bj ] j∈Q\{i }

Následuj´ıc´ı theorém stanov´ı strategickou ekvivalenci mezi tajnými a veˇrejnými aukcemi. Vˇeta 4. Veˇrejná sestupná draˇzba (holandská aukce) je ryze strategicky ekvivalentn´ı s tajnou draˇzbou s prvn´ı cenou. Veˇrejná vzestupná draˇzba (anglická aukce) je slabˇe strategicky ekvivalent´ı s tajnou draˇzbou s druhou cenou. Slabá strategická ekvivalence anglické aukce a tajné 2nd price aukce je dána rozd´ılem mezi platbou výherce, který se liˇs´ı o libovolnˇe malý pˇr´ıhoz nad druhou cenu, který mus´ı hrácˇ s nejvyˇssˇ´ım xi provést, aby se stal v´ıtˇezem (v tajné aukci se stává v´ıtˇezem deklarac´ı své sázky).

3.4

Ekvilibrium v tajných aukc´ıch

Ekvilibrium v anglické a holandské draˇzbˇe budeme zkoumat na jejich tajných strategických ekvivalentech. Strategicky jednoduˇssˇ´ı je tajná aukce s druhou cenou, neboˇt ta je oproˇstˇena od nutnosti zkoumat tajná ohodnocen´ı u protivn´ık˚u. Vˇeta 5. Uvaˇzujme tajnou aukci, kde v´ıtˇezem je hrácˇ s nejvyˇssˇ´ı podanou nab´ıdkou. V´ıtˇez plat´ı druhou nejvyˇssˇ´ı nab´ıdnutou cenu. Pak je ekvilibriem v situaci pro kaˇzdého hrácˇ e (symetrickým ekvilibriem) podat sázku ∗ βII (x) = x ∗ (x) pˇri ohodnocen´ı x = xi u hrácˇ e i je strategi´ı tvoˇr´ıc´ı pro hrácˇ e Nashovo Strategie podat βII ekvilibrium. Hrácˇ , který z této strategie vyboˇc´ı, nezvýsˇ´ı sv˚uj zisk, jak o tom v roce 1960 informoval William Vickrey.

Vˇeta 6. Pro kaˇzdou sázku b1 , b2 , ..., bN a kaˇzdou jinou b0i , nechtˇ ui je uˇzitek i-tého hrácˇ e pˇri hran´ı bi a u0i je jeho uˇzitek pˇri hran´ı b0i . Pak ui ≥ u0i . William Vickrey (1960) Proof. Pˇredpokládejme, zˇ e hrácˇ i pˇri své sázce bi vyhraje a zaplat´ı (druhou nejvyˇssˇ´ı) cenu y ∗ . Jeho zisk je tedy ui = bi − y ∗ ≥ 0. Pˇri moˇzné manipulaci b0i > y ∗ , i je stále v´ıtˇez´ıc´ım hrácˇ em a u0i = ui . V druhém pˇr´ıpadˇe, kdy b0i < y ∗ , i prohraje a u0 = 0 ≤ u.

17

Pokud hrácˇ i pˇri sázce bi prohraje, pak ui = 0. Pak je v´ıtˇez j ∈ Q; j 6= i se sázkou bj ≥ bi (nebo lépe bj > bi ). Pro b0i < bj hrácˇ i stále prohrává a u0i = 0. Pro b0i ≥ bj (nebo striktnˇe vyˇssˇ´ı), i vyhrává a plat´ı y ∗ = bj , ale jeho zisk je u0i = bi − bj ≤ 0, tzn. u0i ≤ ui . Princip druhé ceny se stal základem tak zvaných vickreyovských mechanism˚u a i tato aukce se nazývá vickreyovská. Vyhodnocen´ı ekvilibria v aukc´ıch s prvn´ı cenou je sloˇzitˇejˇs´ı, neboˇt vyˇzaduje pravdˇepodobnostn´ı model ohodnocen´ı pˇredmˇetu aukce protivn´ıky. Pro jednoduchost si pˇredstav´ıme ekvilibrium v situaci, která pˇredpokládá, zˇ e na intervalu h0, ωi je hustota pravdˇepodobnosti ohodnocen´ı xi vˇsemi hrácˇ i rovnomˇernˇe rozloˇzena (jinak ˇreˇceno, vˇsechna ohodnocen´ı z h0, ωi jsou stejnˇe pravdˇepodobná). Vˇeta 7. Mˇejme N nezávislých hrácˇ u˚ se symetrickým privátn´ım ohodnocen´ım xi , které je rovnomˇernˇe distribuováno na h0, ωi. Pak je symetrickým Nashovým ekvilibriem hrát: βI∗ (x) =

N −1 x N

Pˇr´ıklad 1st price aukce Pˇredpokládejme tajné symetrické ohodnocen´ı pˇredmˇetu rovnomˇerným pravdˇepodobnostn´ım rozloˇzen´ım na intervalu h0, 1i. Pokud je mé ohodnocen´ı napˇr. x1 = 0.8 a N = 2, pak je m˚uj oˇcekávaný zisk nejvyˇssˇ´ı pro sázku bi = 0.4, coˇz dokumentuje obrázek 3.1. Pro moji sázku bi = 0.8 je pravdˇepodobnost mé výhry 0.8 a zisk nulový. Se sniˇzuj´ıc´ı sázkou klesá pravdˇepodobnost mé výhry, ale roste moˇzný zisk. b1 π1 = pravdˇepodobnost výhry ∗u1 0.8 0.8*0 0.7 0.7*0.1=0.07 0.6 0.6*0.2=0.12 0.5 0.5*0.3=0.15 0.4 0.4*0.4=0.16 0.3 0.3*0.5=0.15 0.2 0.2*0.6=0.12 Figure 3.1: Oˇcekávaný zisk pˇr´ıkladu aukce s prvn´ı cenou Pokud je pravdˇepodobnostn´ı model tajného ohodnocen´ı vˇeci jiný, pak m˚uzˇ e být ekvilibrium znaˇcnˇe sloˇzitˇejˇs´ı.

3.5

Vliv citlivosti k riziku na ekvilibrium v aukci

Zaˇcneme zjiˇsten´ım, zˇ e risk-averse hrácˇ v aukci s prvn´ı cenou preferuje niˇzsˇ´ı zisky, coˇz se projev´ı na jeho racionáln´ıch sázkách. 18

Vˇeta 8. Mˇejme N nezávislých hrácˇ u˚ se symetrickým privátn´ım ohodnocen´ım xi , které je rovnomˇernˇe distribuováno na h0, ωi. Pˇredpokládáme hrácˇ e citlivé k riziku (risk-averse) s koeficientem citlivosti α ∈ h0, 1i. Pak je symetrickým Nashovým ekvilibriem hrát: βI∗ (x) = xα M˚uzˇ e prodávaj´ıc´ı v aukci nˇejak vyuˇz´ıt znalosti o vztahu kupuj´ıc´ıch k riziku? Prodávaj´ıc´ı vol´ı aukˇcn´ı mechanismus a to je jediná strategie, kterou ve hˇre proti kupuj´ıc´ım vol´ı. Ukázˇ eme, zˇ e pokud prodávaj´ıc´ı cˇ el´ı kupuj´ıc´ım neutráln´ım k riziku, pak je indiferentn´ı ve svém oˇcekáván´ı v˚ucˇ i volbˇe aukce s prvn´ı cenou a druhou cenou. Jinak ˇreˇceno, jeho oˇcekávaný výnos (expected revenue) v tˇechto dvou formách aukce je stejný. Dokumentuje to tak zvaný Revenue equivalence theorem. Dále uvid´ıme, zˇ e pokud jsou kupuj´ıc´ı citliv´ı k riziku, prodávaj´ıc´ı dosáhne vyˇssˇ´ıho výnosu u aukce s prvn´ı cenou. Pˇredpokládejme dva kupuj´ıc´ı neutráln´ı k riziku s privátn´ımi ohodnocen´ımi x1 a x2 rovnomˇernˇe rozloˇzenými na intervalu h0, 1i. Pak je cena placená v´ıtˇezem v aukci s prvn´ı cenou yI = max(x1 /2, x2 /2) a v aukci s druhou cenou yII = min(x1 , x2 ). Je moˇzné snadno odvodit, zˇ e stˇredn´ı hodnota výnosu v obou akc´ıch je E(yI ) = E(yII ) = 31 . Vypadá to tedy, zˇ e v tˇechto dvou situac´ıch je oˇcekáván´ı výnosu stejné. Povrzuje to Revenue equivalence theorem: Vˇeta 9 (Revenue equivalence theorem). Pˇredpokládejme risk-neutral hrácˇ e. Maj´ı-li symetrické a nezávislé privátn´ı ohodnocen´ı pˇredmˇetu aukce, aukce je standardn´ı a zaruˇcuje nulovou platbu hrácˇ i deklaruj´ıc´ımu nulové ohodnocen´ı. Pak je výnos aukce pˇri aukci s prvn´ı cenou shodný s aukc´ı s druhou cenou. Závˇer je tedy jednoznaˇcný: Hraj´ı-li risk-neutral hrácˇ i, je jedno, zda vol´ıme 1st nebo 2st price aukci. A následuj´ıc´ı theorém Revenue equivalence theorem doplˇnuje dalˇs´ım zjiˇstˇen´ım: Hraj´ı-li riskaverse hrácˇ i, je lépe volit 1st price aukci. Vˇeta 10. Pˇredpokládejme risk-averse hrácˇ e. Maj´ı-li symetrické a nezávislé privátn´ı ohodnocen´ı pˇredmˇetu aukce, pak je výnos aukce pˇri aukci s prvn´ı cenou vyˇssˇ´ı neˇz u akce s druhou cenou.

3.6

Vickrey-Clarke-Groves mechanismus

W. Vickrey v roce 1961 publikoval návrh aukce s druhou cenou, kde ukázal, zˇ e je nemanipulovatelná (hrácˇ deklaruj´ıc´ı nepravdivé ohodnocen´ı pˇredmˇetu nez´ıská v´ıc). Clarke (1971) a Groves (1973) tuto myˇslenku zobecnili do VCG-mechanismu.

19

3.6.1

Notace

Pˇredpokládejme mnoˇzinu alternativ A. Na n´ı kaˇzdý hrácˇ deklaruje svou ohodnocovac´ı funkci vi : A → R Hrácˇ dává funkc´ı vi veˇrejnˇe najevo, jak si cen´ı jednotlivé alternativy a ∈ A. Mnoˇzina vˇsech ˚ ze nám sdˇelit libovolný ohodnocovac´ıch funkc´ı hrácˇ e je Vi (je to totoˇzné s Si u strategických her). Muˇ postoj vi ∈ Vi , my chceme jeho pravdivý postoj. Dále definujeme v = (v1 , v2 , ..., vN ) jako profil ve hˇre v ∈ V a podobnˇe mnoˇzinu profil˚u V = V1 × V2 × ... × VN . Podobnˇe chápeme V−i a v−i .

3.6.2

Mechanismus (direct revelation)

Zaˇcneme definic´ı obecného mechanismu, kde vystupuje veˇrejná volba jedné z alternativ a s n´ı spojené platby vˇsech hrácˇ u˚ . Definice 12. Mechanismus (direct revelation) je dán funkc´ı veˇrejné volby f : V1 × ... × VN → A a vektorem plateb p1 , ..., pN , kde pi : V1 × ... × VN → R je cˇ a´ stka, kterou zaplat´ı hrácˇ i. Hra se pak odehraje v techto kroc´ıch: • Hrácˇ i sdˇel´ı své ocenˇen´ı, tzn. postoje vi ∈ Vi v˚ucˇ i r˚uzným alternativám a ∈ A. • Funkce veˇrejné volby rozhodne, která alternativa a ∈ A se zvol´ı. • Urˇc´ı se pro kaˇzdého hrácˇ e i ∈ Q, kolik zaplat´ı – pi : V1 × ... × VN . C´ılem je formulovat mechanismus takový, aby zˇ a´ dný hrácˇ nemohl tˇezˇ it z pˇredstaven´ı svého nepravdivého postoje – tzn. aby nemohl manipulovat volbu alternativy a svou platbu do systému. Definice 13. Mechanismus (f, p1 , ..., pN ) se nazývá nemanipulovatelný (incentive compatible, strategyproof), pokud pro kaˇzdého hrácˇ e i, pro kaˇzdý profil v ∈ V a kaˇzdé vi0 ∈ Vi , pokud v´ıme, zˇe a = f (vi , v−i ) a a0 = f (vi0 , v−i ), pak plat´ı vi (a) − pi (vi , v−i ) ≥ vi (a0 ) − pi (vi0 , v−i ) Téma se stále opakuje dokola: pokud hrácˇ rˇ´ıká pravdu, nen´ı na tom h˚urˇ neˇz kdyˇz lˇze. Pˇri troˇse hernˇe teoretické fantazie nám m˚uzˇ e definice pˇripom´ınat definici Nashova ekvilibria, coˇz fakticky i je.

20

3.6.3

VCG-mechanismus

Hledáme takovou funkci veˇrejné volby f , aby v dané situaci vyb´ırala veˇrejné optimum, tzn. a∗ = arg max a∈A

X

vi (a)

i

Definice 14. Mechanismus (f, p1 , ..., pN ) se nazývá Vickrey-Clarke-Groves mechanismus (VCG), pokud: • f maximalizuje spoleˇcenský uˇzitek, tedy " f (v1 , ..., vN ) ∈ arg max

# X

a∈A

vi (a)

i

• pro sadu funkc´ı h1 , ..., hN , kde hi : V−i → R, definujeme pi (v1 , ..., vN ) = hi (v−i ) −

X

vj (f (v1 , ..., vN ))

j6=i

pi (v1 , ..., vN ) = hi (v−i ) −

X

vj (f (v1 , ..., vN ))

j6=i

Jinak ˇreˇceno, platba za u´ cˇ ast ve hˇre je dána sloˇzkami: • hi (v−i ), tedy platby, o které rozhodne mechanismus z kontextu v−i . P • − j6=i vj (f (v1 , ..., vN )), tedy nahrazen´ı hodnoty, kterou protihrácˇ i ztrác´ı faktem, zˇ e nejsou vybráni. Je tedy definován VCG-mechanismus, nyn´ı nás zaj´ımá jeho odolnost proti strategické manipulaci: Vˇeta 11. Kaˇzdý VCG-mechanismus je strategicky nemanipulovatelný. D˚ukaz najdeme v publikaci Algorithmic Game Theory[Nisan, p. 219].

3.6.4

Clarke Pivot Rule

Trochu jsme odsunuli problém jeho pˇreveden´ım na formulaci funkc´ı {hi (v−i )}i∈Q . Definice 15. Mˇejme VCG-mechanismus. • Mechanismus je (ex-post) individuálnˇe racionáln´ı, pokud hrácˇ i vˇzdy z´ıskaj´ı kladný zisk (tedy i nulový). Formálnˇe, pro vˇsechny v ∈ V : vi (f (v)) − pi (v) ≥ 0; ∀i ∈ Q. 21

• Mechanismus nemá zˇa´ dné postrann´ı platby, pokud zˇa´ dný hrácˇ platbou nez´ıská. Formálnˇe, ∀v ∈ V : ∀i ∈ Q : pi (v) ≥ 0 (pi nedává záporné hodnoty platby). Hrácˇ i u´ cˇ ast´ı ve hˇre z´ıskává ui (v) = vi (f (v)) − pi (v), tzn. jak si cen´ı výsledku f (v) po odeˇctu platby pi (v). Definice 16. Clarke pivot platba je " hi (v−i ) = max b∈A

# X

vj (b)

j6=i

Potom je platba hrácˇ e v profilu v ∈ V dána pi (v) = max b

X

vj (b) −

j6=i

X

vj (a)

j6=i

kde a = f (v).

Hrácˇ zaplat´ı do systému cˇ a´ stku, která se rovná celkové sˇkodˇe, kterou ostatn´ım zp˚usobil. Lemma 12. VCG mechanismus s Clarke pivot platbou nezp˚usobuje zˇa´ dné postrann´ı platby. Pokud je vi (a) ≥ 0 pro vˇsechny vi ∈ Vi a a ∈ A, pak je také individuálnˇe racionáln´ı.

3.7

Pˇr´ıklady aplikace VCG-mechanismu

VCG-mechanismus je obecným pojet´ım nemanipulovatelného mechanismu, kdy je tˇreba zvolit veˇrejnˇe jednu z alternativ, ze které pro hrácˇ e plynou pˇr´ınosy a náklady. Berme VCG-mechanismus jako parametrizovatelnou definici, tzn. jej´ım dospecifikován´ım z´ıskáváme mechanismus pro konrétn´ı situaci. Na následuj´ıc´ıch pˇr´ıkladech ukázˇ eme dvˇe pˇr´ıhodné aplikace – aukci o jeden pˇredmˇet a mechanismus pro odvozen´ı plateb pˇri stavbˇe veˇrejnˇe prospˇesˇného zaˇr´ızen´ı (podobný pˇr´ıklad jsme ˇreˇsili v kooperativn´ıch hrách). VCG mechanismus – single-object aukce Mnoˇzinu alternativ zde tvoˇr´ı mnoˇzina moˇzných v´ıtˇez˚u aukce o pˇredmˇet, tedy A = {i − wins|i ∈ Q} – tedy mnoˇzinu identifikac´ı v´ıtˇeze. Pˇredpokládáme, zˇ e kaˇzdý hrácˇ hodnot´ı své v´ıtˇezstv´ı kladnˇe a v´ıtˇezstv´ı jiného nulovˇe, tedy Vi = {vi |vi (i − wins) ≥ 0; ∀j 6= i : vi (j − wins) = 0} 22

Pokud má hrácˇ v plánu deklarovat pouze cenu xi , pak je vi (i − wins) = xi , vi (j − wins) = 0 ∀j 6= i. Jinak m˚uzˇ e deklarovat dalˇs´ı funkce vi1 , vi2 , ... VCG mechanismus s Clarkovým pivotem nám dává pˇresnˇe Vickreyovu aukci. Ukaˇzme si jednoduchý pˇr´ıklad. Mˇejme situaci tˇr´ı hrácˇ u˚ , tzn. A = {1, 2, 3}, kde x1 = 10, x2 = 15, x3 = 4. Následuje jeden moˇzný profil v = (v1 , v2 , v3 ): i/A v1 (a) v2 (a) v3 (a)

1

2

3

10 0 0 15 0 0

0 0 4

Funkce veˇrejné volby optimalizuje veˇrejný uˇzitek, tedy hledá alternativu a ∈ A takovou, zˇ e zinˇe A maximáln´ı. Tedy, f (v) = 2 je zvolena alternativa ”vyhrál 2”. Platby i v(a) je na mnoˇ hrácˇ u˚ jsou potom: P

p1 (v) = max[0, 15, 4] − 15 = 0 p2 (v) = max[10, 0, 4] − 0 = 10 p3 (v) = max[10, 15, 0] − 15 = 0 Tento VCG-mechanismus se tedy chová naprosto stejnˇe jako vickreoyvská aukce, coˇz jsme chtˇeli ukázat. VCG mechanismus – stavba veˇrejnˇe prospˇesˇného objektu Mˇejme komunitu o N jedinc´ıch, kde se ˇreˇs´ı otázka stavby veˇrejnˇe prospˇesˇného zaˇr´ızen´ı, jehoˇz stavebn´ı náklady jsou urˇceny jako C. Vláda bude stavbu finanˇcnˇe garantovat, pokud budou hrácˇ i deklarovat P sv˚uj zájem dostateˇcnˇe velký i vi > C. Z deklarovaného zájmu maj´ı vyplynout pˇr´ıspˇevky hrácˇ u˚ na financován´ı projektu. Zˇrejmˇe kaˇzdý hrácˇ bude m´ıt zájem na realizaci projektu, ale bude zvaˇzovat, jakou hodnotu bude deklarovat – vyplyne totiˇz z n´ı jeho pˇr´ıspˇevek. Pˇredpokládáme hrácˇ e vi ≥ 0, ale je pˇr´ıpustné i vi < 0. Problémem je oznámit pivotn´ı pravidlo takové, aby hrácˇ i mˇeli potˇrebu pravdivˇe deklarovat svá vi . Proto vláda deklaruje jako souˇca´ st mechanismu Clarke pivot tak, zˇ e hrácˇ i s vi ≥ 0 zaplat´ı P P nenulovou cˇ a´ stku pouze tehdy, je-li pivotn´ım hrácˇ em, tzn.: j6=i vj ≤ C a souˇcasnˇe j∈Q vj > C. P V takovém pˇr´ıpadˇe zaplat´ı hrácˇ pi = C − j6=i vj P P Hrácˇ se záporným ohodnocen´ım zaplat´ı nenulovou cˇ a´ stku pouze, kdyˇz j6=i vj > C a j vj ≤ P C, pak pi = j6=i vj − C. P Bohuˇzel vˇzdy bude platit i pi < C. Situace je jiná, neˇz u pˇr´ıkladu se Shapleyho hodnotou (tady hrácˇ i nemus´ı dát v sumˇe C).

23

Mˇejme tˇri hrácˇ e s jejich deklarovanou hodnotou pro stavbu projektu: v1 = 10, v2 = 5, v3 = 4, C = 17. Z pivotu plynou tyto platby hrácˇ u˚ : p1 = 17 − 9 = 8 p2 = 17 − 14 = 3 p3 = 17 − 15 = 2 P Coˇz dává v sumˇe j pj = 13. Mechanismus je odolný proti manipulaci, neboˇt pokud v10 = 8, pak p01 = 17 − 9. Pˇri v100 = 7 se stavba jiˇz nepostav´ı.

24

Doprovodné texty ke kurzu Teorie her

Recommend Documents