The Cooperative Games and Bargaining

THE: Kooperativn´ı hry a vyjednáván´ı The Cooperative Games and Bargaining Martin Hrubý Brno University of Technology Brno Czech Republic

November 5, 2014

Martin Hrub´ y

Kooperativn´ı hry a vyjedn´ av´ an´ı

´ Uvod ˇ ano z: Cerp´ ◮

Peleg, Sudholter: Introduction to the Theory of Cooperative Games

◮

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

◮

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

◮

Myerson, R. B.: Game theory: Analysis of Conflict, Harvard University Press, 2004

◮

Osborne, M., Rubinstein, A.: A Course in Game Theory, The MIT Press, 1994

◮

Brahms, S.: Win-Win solution

Martin Hrub´ y


´ Uvod: Kooperace a vyjednáván´ı

A/B poctivˇe vychytrale

pˇrijmout 10,10 100,1

zam´ıtnout 0,0 0,0

◮

Známe koncept nekooperativn´ıch her.

◮

Co znamená kooperativnost? Jak souvis´ı s efektivitou výstupu ze hry?

◮

Stabilita dohody (koalice, rozdˇelen´ı výsledku).

◮

NE je vˇsude. Co bude dnes hr´ aˇcova strategie?

◮

Budeme se zabývat kooperativn´ımi hrami s pˇrenositelným uˇzitkem (z hráˇce na hr´ aˇce).

Martin Hrub´ y


´ Uvod: Kooperace a vyjednáván´ı A/B poctivˇe vychytrale

pˇrijmout 10,10 100,1

zam´ıtnout 0,0 0,0

Výsledky: ◮

Nedohoda, nekooperativn´ı profil (vychytrale, pˇrijmout) – Nash.

◮

Nedohoda, hrozba (X, zam´ıtnout) – d˚ uvˇeryhodná (?) hrozba.

◮

Dohoda, (poctivˇe, pˇrijmout).

◮

Dohoda, (vychytrale, pˇrijmout) a extra dohoda o rozdˇelen´ı 101 zisku.

Ze hry lze z´ıskat aˇz 101 zisku. Kolik ovˇsem nab´ıdnout pro A za jeho spolupráci? Martin Hrub´ y


Pˇredpoklady pro kooperativn´ı jednán´ı Zat´ım nerozliˇsujeme kooperativn´ı hern´ı teorii a teorii vyjednáván´ı. ◮

Kaˇ zd´ a situace s moˇ znost´ı kooperace v sobˇ e obsahuje nekooperativn´ı v´ ysledek. Nekooperativn´ı hry jsou základ veˇskerých her.

◮

Hráˇci v kooperativn´ım profilu mus´ı z´ıskat v´ıce neˇz v nekooperativn´ım. Pozor na iracion´ aln´ı altruismus.

◮

Mus´ı existovat d˚ uvˇera ve vymahatelnost dohodnutého chován´ı.

◮

Pokud existuje hr´ aˇc, který m´ a vˇetˇs´ı pˇr´ınos pro kooperativn´ı profil, mus´ı m´ıt n´ arok na dodateˇcné pˇrerozdˇelen´ı výsledku.

◮

Souvis´ı s t´ım formov´ an´ı koalic hr´ aˇc˚ u.

◮

Koalice mus´ı b´ yt self-enforcing.

Budeme zkoumat pˇredpoklady pro vyjedn´ av´ an´ı, pˇredpoklady pro tvorbu koalic a spravedlivé pˇrerozdˇelen´ı zisku v koalici (Shapley value). Martin Hrub´ y


Schema vyjednáván´ı (bargaining)

Martin Hrub´ y


Vyjednáván´ı (bargaining) Vycház´ıme z klasické nekooperativn´ı hry. ◮

Vyjednáván´ı je pˇrirozený lidský zp˚ usob, jak dosáhnout efektivnˇejˇs´ıho výsledku neˇz je nekooperativn´ı NE.

◮

Pokud hráˇci nenajdou dohodu, hraje se nekooperativn´ı NE.

◮

Je evidentn´ı, ˇze pro vˇsechny hr´ aˇce mus´ı být vyjednaný profil lepˇs´ı neˇz nekooperativn´ı NE.

◮

Zkoumá se pouze, zda-li vyjedn´ av´ an´ı je moˇzné a který profil je spravedlivˇe nejlepˇs´ı pro vˇsechny.

Vˇsichni hr´ aˇ ci mus´ı vˇ eˇrit, ˇ ze pro nˇ e nen´ı lepˇs´ı ˇreˇsen´ı neˇ z vyjednan´ e. Pokud by ho vyˇ zadovali, pak hra pˇrepne na nekooperativn´ı NE.

Martin Hrub´ y


Vyjednáván´ı (bargaining) – základn´ı model Zadán´ı u ´lohy vyjednáv´ an´ı pro dva hr´ aˇce (pˇr´ıklad): ◮ ◮

◮ ◮

◮

Jsou hráˇci A a B. Hráˇci ˇreˇs´ı ideáln´ı rozdˇelen´ı X jednotek, tzn. takovou alokaci, ˇze xA + xB ≤ X . Z alokace xi má hr´ aˇc uˇzitek ui (xi ). V pˇr´ıpadˇe nedohody dostanou hr´ aˇci nekooperativn´ı výsledek hry ci (disagreement value). Hledáme takovou alokaci, ˇze ui (xi ) > ci pro vˇsechny i

Zat´ım neformálnˇe: Nash dok´ azal, ˇze dohody m˚ uˇze být dosaˇzeno v bodˇe, který odpov´ıdá maximalizaci funkce:

s omezen´ım

g (xA , xB ) = (uA (xA ) − cA )(uB (xB ) − cB ) uA (xA ) ≥ cA ∧ uB (xB ) ≥ cB Martin Hrub´ y


Pˇr´ıklad Peter (A) a John (B) si maj´ı rozdˇelit 100 USD. Pokud nenajdou shodu, pen´ıze propadnou, tzn. ci = 0. xA + xB ≤ 100 uA (xA ) = xA xB = 100 − xA ⇒ uB (xB ) = 100 − xA

ˇ s´ıme hledán´ı extrém˚ Reˇ u:

g (xA , xB ) = (uA (xA ) − 0)(uB (xB ) − 0) tzn.: g (xA )′ = [(xA )(100 − xA )]′ = 0 xA = 50, pak xB = 50 Martin Hrub´ y


Vztah mezi ziskem a uˇzitkem

Podle vztahu k riziku rozliˇsujeme hr´ aˇce (vztah zisk–uˇzitek, pˇr´ıklady uˇzitkových funkc´ı):

◮

Neutráln´ı k riziku (Risk-neutral): u(x) = x. √ Citlivý k riziku (Risk-averse): u(x) = x.

◮

Vyhledávaj´ıc´ı riziko (Risk-seeking): u(x) = x 2 .

◮

Martin Hrub´ y


Pˇr´ıklad s nesymetrickou funkc´ı uˇzitku Pˇredpokládejme, ˇze Peter je chudý a rozdˇelujeme 30 milion˚ u CZK. Lze oˇcekávat, ˇze bude n´ achylnˇejˇs´ı na riziko (risk-averse) neˇz John (risk-neutral). √ Uˇzitek Petera ze z´ıskán´ı uA (xA ) = xA , uB (xB ) = xB . Pak: √ [ xA (30 − xA )]′ = 0 30 − xA √ − xA = 0 √ 2 xA ⇒ xA = 10 ⇒ xB = 30 − 10 = 20

Dohoda tedy bude [10, 20] s uˇzitkem [3.16, 20] pro hráˇce. Pro Petera je zˇrejmˇe dobré tajit své ohodnocen´ı pˇr´ıpadného výsledku (budeme zkoumat dál v r´ amci mechanism design). Jak by dohodla dopadla, kdyby byl Peter extrémnˇe bohatý a na výsledku mu nezáleˇzelo? Martin Hrub´ y


Pˇr´ıklad s nesymetrickou funkc´ı uˇzitku Peter je risk-averse a John je risk-seeking.

Martin Hrub´ y


Vyjednávac´ı problém

◮

Je zadán vyjednávac´ı problém (vyjedn´ avac´ı mnoˇzina, ”disagreement value”).

◮

Klasicky pˇredpokl´ ad´ ame, ˇze vyjedn´ avac´ı mnoˇzina je konvexn´ı a ohraniˇcená.

◮

Hledáme algoritmus pro výpoˇcet akceptovatelné dohody.

◮

Bargaining problem m´ a v´ıce ˇreˇsen´ı.

◮

Prvn´ı pˇredvedl John Nash. Stanovil axiomy, které by mˇelo ˇreˇsen´ı naplˇ novat (axiomatický pˇr´ıstup).

Následovat bude Nash Bargaining Solution.

Martin Hrub´ y


Nashovy axiomy pro vyjednáván´ı Vyjednáván´ı by mˇelo být zaloˇzeno na tˇechto principech: ◮

Hráˇci maximalizuj´ı své oˇcek´ avané uˇzitky.

◮

Vyjednáván´ı je efektivn´ı. Rozdˇelen´ı plnˇe vyuˇz´ıvá zdroje a ˇzádný hráˇc nedostane ménˇe neˇz je jeho nekooperativn´ı výsledek (disagreement value).

◮

Rozdˇelen´ı (výsledek vyjedn´ av´ an´ı) zavis´ı pouze na preferenc´ıch hráˇc˚ u a jejich nekooperativn´ıch výsledc´ıch.

◮

Independence of irrelevant alternatives.

Nash v ”Nash, John (1950). The Bargaining Problem. Econometrica 18 (2)” uk´ azal, ˇze pokud hra odpov´ıdá následuj´ıc´ım ˇctyˇrem axiom˚ um, pak m´ a ”bargaining solution”, tzn. lze naj´ıt dohodu, která je výhodn´ a pro vˇsechny.

Martin Hrub´ y


Formalizace Nashových vyjednávac´ıch axiom˚ u Definice: ◮

Ω je mnoˇzina vˇsech dosaˇzitelných výsledk˚ u (uA , uB ) jako d˚ usledk˚ u rozdˇelen´ı X - tzv. vyjedn´ avac´ı mnoˇzina.

◮

Mnoˇzina Pareto-efektivn´ıch alokac´ı je Ωe = {ω ∈ Ω|uA > cA ∧ g (uA ) > cB }.

◮

Vyjednávac´ı situace je p´ ar (Ω, c), kde c = (cA , cB ).

◮

Mnoˇzina vˇsech vyjedn´ avac´ıch her je Σ a vyjednávac´ı ˇreˇsen´ı je F : Σ → R2 . Fi bude oznaˇcovat uˇzitek hr´ aˇce i .

◮

F (Ω, c) je tedy pro n´ as oznaˇcen´ı vyjedn´ avac´ıho ˇreˇsen´ı.

Vyjednávac´ı ˇreˇsen´ı má charakter ekvilibria, ale nelze ho povaˇzovat za pojem totoˇzný s vn´ım´ an´ım nekooperativn´ıho ekvilibria (NE).

Martin Hrub´ y


Axiom 1. Nezávislost na lineárn´ıch transformac´ıch uˇzitkových funkc´ı

Axiom Nechˇt ui′ = αi ui + βi a ci′ = αi ci + βi , αi > 0. Ω′ je odvozeno od Ω. Pak Fi (Ω′ , c ′ ) = αi Fi (Ω, c) + βi pro i ∈ {A, B}. Pˇredpokládáme tedy, ˇze afinn´ı transformace uˇzitkových funkc´ı a nekooperativn´ıch uˇzitk˚ u neovlivn´ı vyjedn´ avac´ı proces. V´ıme, ˇze dosáhneme ekvivalentn´ı hry, kter´ a vykazuje stejné strategické charakteristiky (dominance, BR, ekvilibria).

Martin Hrub´ y


Axiom 2. Pareto efektivita Axiom Je-li F (Σ) = (uA , uB ), pak neexistuje jiný výsledek (uA′ , uB′ ) ∈ Ω takový, ˇze ui′ > ui pro nˇekterého hr´ aˇce i a souˇcasnˇe uj′ ≥ uj pro j 6= i . Klasická Pareto efektivita, tzn. pokud hr´ aˇci dojdou dohody (uA , uB ), pak neexistuje jiné rozdˇelen´ı (bargaining solution), ve kterém by alespoˇ n jeden hr´ aˇc byl striktnˇe lepˇs´ı a zbytek hráˇc˚ u pˇrinejmenˇs´ım stejnˇe dobˇr´ı. Pozn.: Výsledek (uA′ , uB′ ) ∈ Ω takový, ˇze ui′ > ui pro nˇekterého ame jako pˇrijatelný. hráˇce i a souˇcasnˇe uj′ < uj pro j 6= i nezkoum´ Pozn.: Mnoˇzina Pareto efektivn´ıch profil˚ u leˇz´ı v ohraniˇcen´ı vyjednávac´ı mnoˇziny. Martin Hrub´ y


Axiom 3. Symetrie

Axiom Pˇripusˇtme cA = cB a pˇredpokl´ adejme, ˇze (uA , uB ) ∈ Ω právˇe tehdy pokud (uB , uA ) ∈ Ω. Pak FA (Ω, c) = FB (Ω, c). Maj´ı-li hráˇci stejné vstupn´ı podm´ınky a jsou-li jejich uˇzitky dostupné i jejich protivn´ık˚ um, pak mus´ı doj´ıt k rovnému rozdˇelen´ı X.

Martin Hrub´ y


Axiom 4. Nezávislost na irelevantn´ıch alternativách

Independence of Irrelevant Alternatives (obecný, velmi d˚ uleˇzitý pˇredpoklad ve vˇsech ˇc´ astech THE, kde se oˇcek´ av´ a zkoumán´ı preferenc´ı).

Axiom Mˇejme dvˇe vyjednávac´ı situace (Ω, c) a (Ω′ , c) takové, ˇze Ω′ ⊆ Ω a F (Ω, c) ⊆ Ω′ . Pak F (Ω, c) = F (Ω′ , c). Máme vyjednávac´ı oblast Ω a jej´ı ˇreˇsen´ı F (Ω, c). Pokud zkoumáme podmnoˇzinu Ω′ ⊆ Ω takovou, ˇze ˇreˇsen´ı F (Ω, c) ∈ Ω′ , pak je F (Ω, c) ˇreˇsen´ım i pro Ω′ .

Martin Hrub´ y


Nash bargaining solution

Theorem Vyjednávac´ı ˇreˇsen´ı F : Σ → R2 naplˇ nuje axiomy 1-4 právˇe tehdy pokud je to Nashovo vyjedn´ avac´ı ˇreˇsen´ı. Nash, J. (1950). The Bargaining Problem. Econometrica 18 (2)

Martin Hrub´ y


Nash bargaining solution, d˚ usledek

Theorem Existuje pouze jedna funkce F : Σ → R2 modeluj´ıc´ı Nashovo vyjednávac´ı ˇreˇsen´ı. Je definov´ ana tak, ˇze F (Ω, c) = (uA∗ , uB∗ ) a (uA∗ , uB∗ ) = arg maxuA ,uB { (uA − cA )(uB − cB ) | (uA , uB ) ∈ Ω ∧ uA ≥ cA , uB ≥ cB }

Martin Hrub´ y


Vyjednáván´ı v nekooperativn´ı hˇre Mˇejme hru: 5,1 7,4 1,10 Ekvilibria: (0, 1), 21 , 0, 12 , ((0, 1), (0, 0, 1)). 1,1 9,-2 5,1 9 Minimáln´ı oˇcekávaný zisk: (3, 1). Lze vyjednat 13 2 ,2 .

Martin Hrub´ y


Vyjednáván´ı v nekooperativn´ı hˇre

g (u, v ) = (u − 3)(v − 1) Bereme jako nekooperativn´ı výsledek (3, 1) a vyjednávac´ı oblast danou pˇr´ımkou v = −u + 11. Pak g (u, −u + 11) = (u − 3)(−u + 10) (−u 2 + 13u − 30)′ = 0 u=

13 9 ,v = 2 2

Martin Hrub´ y


Nash bargaining solution, závˇer

◮

Existuje tˇr´ıda problém˚ u, kterým se ˇr´ık´ a vyjednávac´ı (jsou zadány uˇzitkovými funkcemi, nekooperativn´ım profilem a vyjednávac´ı mnoˇzinou).

◮

Nash (1950) formuloval axiomatickou teorii vyjednáván´ı a ukázal ˇreˇsen´ı problému (Nash product), které odpov´ıdá jeho axiom˚ um a je unik´ atn´ı.

◮

Existuj´ı i jiné názory a vyjedn´ avac´ı modely.

Dalˇs´ı podoby vyjednáv´ an´ı (s jinými pˇredpoklady) jsou tématem projekt˚ u.

Martin Hrub´ y


Kooperativn´ı hry

◮

Tvorba koalic. Pˇrerozdˇelov´ an´ı zisku.

◮

Uvaˇzujme hru N hr´ aˇc˚ u, Q bude mnoˇzina hr´ aˇc˚ u.

◮

Koalice K ⊆ Q. Koaliˇcn´ı struktura je uskupen´ı koalic ve rámci hry.

◮

Protikoalic´ı ke koalici K se rozum´ı mnoˇzina hráˇc˚ u K− = Q \ K.

◮

◮

Mnoˇzina vˇsech hr´ aˇc˚ u se nazýv´ a velk´ a koalice. Prázdná koalice je opak. Je moˇzno vytvoˇrit 2N koalic (pokud nebudeme uvaˇzovat prázdnou koalici, tak 2N − 1).

Martin Hrub´ y


Kooperativn´ı hry

V ˇcem spoˇc´ıvá kooperativn´ı hra? ◮

Hráˇci vn´ımaj´ı nekooperativn´ı situaci a jsou schopni vyhodnotit s´ılu jednotlivých koalic. Pˇremýˇsl´ı, které koalice se z´ uˇcastn´ı.

◮

Hráˇci vn´ımaj´ı, ˇze situace od nich oˇcek´ av´ a spolupráci hráˇc˚ u.

◮

Je tu jistá podobnost s vyjedn´ av´ an´ım (z dohody plyne lepˇs´ı uˇzitek neˇz ze samostatného jedn´ an´ı).

◮

V rámci koalice d´ ale pˇremýˇsl´ı, jak rozdˇelit spoleˇcný zisk.

◮

Pod´ıl na zisku (d˚ usledek u ´ˇcasti v koalici) mus´ı být vˇetˇs´ı neˇz nekooperativn´ı zisk jednotlivce.

Hráˇci mohou komunikovat.

Martin Hrub´ y


Hra ve tvaru charakteristické funkce (von Neumann, 1928) Pˇredpokládáme TU-games (Transferable Utility – uˇzitek je vztaˇzen na koalici a dál se dˇel´ı mezi hr´ aˇce).

Definition Kooperativn´ı TU hra ve tvaru charakteristické funkce je dána mnoˇzinou hráˇc˚ u Q = {1, 2, ..., N} a reálnou funkc´ı v : 2Q → R takovou, ˇze: v (∅) = 0. Charakteristickou funkc´ı budeme oznaˇcovat celou hru. Hodnoty v (⊆ Q) udávaj´ı s´ılu jednotlivých moˇzných koalic. Notace: G Q bude oznaˇcovat vˇsechny N-hr´ aˇcové TU hry. Jednotlivé hry budou oznaˇcov´ any v ∈ G Q . Martin Hrub´ y


Hra ve tvaru charakteristické funkce (von Neumann, 1928)

Definition Super-aditivita: Pro kaˇzdé dvˇe disjunktn´ı koalice K a L plat´ı v (K ∪ L) ≥ v (K ) + v (L) Super-aditivitu budeme obˇcas cht´ıt ignorovat.

Martin Hrub´ y


Hra ve tvaru charakteristické funkce (von Neumann, 1928) C´ılem hráˇce nen´ı utvoˇrit koalici, ale naj´ıt sobˇe lepˇs´ı výsledek neˇz je ten nekooperativn´ı. ◮

Mˇejme zadán´ı hry ve tvaru charakteristické funkce.

◮

Stále pˇredpokládáme individu´ aln´ı racionalitu hráˇc˚ u, t.j. snahu optimalizovat individu´ aln´ı zisk.

◮

v (K ) je zisk koalice K . Je tˇreba ho rozdˇelit hráˇc˚ um i ∈ K v koalici.

◮

Jak se koalice utvoˇr´ı? Nekooperativn´ı výsledek je rozdˇelen´ı do jednoprvkových koalic.

◮

Jak se hráˇci v koalici dohodnou na rozdˇelen´ı (TU) zisku v rámci koalice?

◮

Jak vyjádˇr´ıme individu´ aln´ı zisk?

Martin Hrub´ y


Nepodstatná hra (pˇredpokládáme super-aditivitu) Definition Hra ve tvaru charakteristické funkce se nazýv´ a nepodstatná, pokud plat´ı: X v (Q) = v ({i }) i ∈Q

Pokud hra nen´ı nepodstatn´ a, pak se nazýv´ a podstatná.

Theorem Nechˇt K je libovolná koalice v nepodstatné hˇre, pak X v (K ) = v ({i }) i ∈K

Závˇer: v nepodstatné hˇre nem´ a smysl tvoˇrit koalice (nen´ı ˇzádná pˇridaná hodnota). Martin Hrub´ y


Velká koalice

Velká koalice je v mnoha modelech ˇreˇsen´ı ten velký c´ıl, ovˇsem... Budeme oddˇelenˇe zkoumat hry: ◮ ◮

◮

kde je velká koalice nejhodnotnˇejˇs´ı koalic´ı, kde velká koalice NENÍ nejhodnotnˇejˇs´ı koalic´ı (neplat´ı super-aditivita), kde uvaˇzujeme vznik velké koalice, ale pˇr´ınos nˇekterých hráˇc˚ u do n´ı bude nulový.

Martin Hrub´ y


Individuáln´ı zisk pro hráˇce

Pˇredstavme si kooperativn´ı hru tˇrech hr´ aˇc˚ u Q = {A, B, C } s charakteristickou funkc´ı: v (∅) = 0, v ({A}) = v ({B}) = v ({C }) = 1 v ({A, B} = v ({A, C }) = v ({B, C }) = 5, v (Q) = 100 Situace zˇrejmˇe vede na velkou koalici. Jaké bude rozloˇzen´ı zisk˚ u pro jednotlivé hráˇce? Jaké bude v situaci, kdy v (C ) = 50?

Martin Hrub´ y


Individuáln´ı zisk pro hráˇce Pro vyjádˇren´ı rozdˇelen´ı zisku si zavedeme vektory a ∈ RN (tak zvané výplatn´ı vektory). Pod z´ apisem a(S), kde S ⊆ Q budeme rozumˇet a(S) =

X

ai

i ∈S

Lze tuˇsit, ˇze pracujeme se spojitými u ´lohami a ˇze tud´ıˇz prostor pro vyjednáván´ı o rozdˇelen´ı individu´ aln´ıho zisku bude potenciálnˇe nekoneˇcný. Zˇrejmˇe budeme pracovat s prostorem výplatn´ıch vektor˚ u X ∗∗ (v ) takových, ˇze X ∗∗ (v ) = {a ∈ RN |a(Q) ≤ v (Q)} Mnoˇzina dosaˇzitelných (feasible) uˇzitk˚ u.

Martin Hrub´ y



V X ∗∗ (v ) existuj´ı takové výplatn´ı vektory a, ˇze a(Q) < v (Q), coˇz znamená, ˇze by velká koalice tratila rozd´ıl mezi v (Q) a a(Q), neboˇt a = v (Q) −

X

ai > 0

i ∈Q

Prostor dosaˇzitelných zisk˚ u proto omez´ıme zdola na prostor efektivn´ıch zisk˚ u: X ∗ (v ) = {a ∈ X ∗∗ (v )|a(Q) = v (Q)} Pracujeme pouze s hrami, kde ∄S ⊆ Q : v (S) > v (Q).

Martin Hrub´ y



Zaj´ımá nás pˇredevˇs´ım individu´ aln´ı racionalita jedince.

Definition Výplatn´ı vektor a ∈ X ∗ (v ) je individu´ alnˇe racion´ aln´ı, pokud pro vˇsechny i ∈ Q plat´ı, ˇze: ai ≥ v ({i }) Dostáváme se k definici pojmu imputace.

Martin Hrub´ y


Imputace Definition Nechˇt v je hra ve tvaru charakteristické funkce s mnoˇzinou hráˇc˚ u Q = {1, 2, ..., N} N-tice a reálných ˇc´ısel se nazýv´ a imputace, pokud jsou splnˇeny podm´ınky: ◮ ◮

Individuáln´ı racionalita: ai ≥ v ({i }); ∀i ∈ Q. P Kolektivn´ı racionalita: i ∈Q ai = v (Q).

Imputace je pˇrerozdˇelen´ı zisku koalice mezi jej´ı ˇcleny. Pro chápán´ı imputace je d˚ uleˇzité pozn´ an´ı, ˇze suma ohodnocen´ı vzniklých koalic (rozklad hr´ aˇc˚ u) je obecnˇe ménˇe neˇz v (Q). Imputace ovˇsem plánuje pˇrerozdˇelit v (Q) zisku. Tzn., nˇekteré koalice mohou dostat v´ıce neˇz je jejich hodnocen´ı. Martin Hrub´ y


Imputace

Prostor vˇsech imputac´ı hry v ∈ G Q budeme oznaˇcovat X (v ). Je zˇrejmé, ˇzP e X (v ) bude pr´ azdný pouze tehdy, pokud v (Q) < i ∈Q v ({i }). D´ ale bude bude X (v ) jednoprvkový v nepodstatné hˇre (aditivn´ı hˇre).

Theorem Nechˇt v je hra ve tvaru charakteristické funkce. Je-li v nepodstatná, pak má pr´ avˇe jednu imputaci, a to a = (v ({1}), v ({2}), ..., v ({N})) Je-li v podstatná, pak m´ a nekoneˇcnˇe mnoho imputac´ı.

Martin Hrub´ y


Preference nad imputacemi

Definition Nechˇt v je hra ve tvaru charakteristické funkce, K je koalice a a, b ˇ jsou imputace. Rekneme, ˇze a dominuje nad b pro koalici K , pokud: ◮ ◮

ai > bi pro vˇsechny i ∈ K P i ∈K ai ≤ v (K )

P Imputace mus´ı být jaksi shora omezen´ a ( i ∈K ai ≤ v (K )). Pokud hráˇc´ı p˚ ujdou do K , pak nedostanou dohromady v´ıce neˇz v (K ). Preferenci budeme znaˇcit a ≻K b.

Martin Hrub´ y


Koncepty ˇreˇsen´ı v TU hrách

Solution concepts. Zaj´ım´ a n´ as predikce racion´ aln´ıho chován´ı hráˇc˚ u. V TU kooperativn´ıch hr´ ach je to i forma vymezen´ı spravedlivého rozdˇelen´ı zisku. ◮

Jádro hry (the core).

◮

Shapleyho hodnota.

◮

Dalˇs´ı typy hodnot.

◮

Nukleolus.

Martin Hrub´ y


Jádro hry (The Core)

Definice Jádro C (v ) hry v ∈ G Q je tvoˇreno mnoˇzinou imputac´ı ( ) X C (v ) = a ∈ X (v )| ai ≥ v (S); ∀S ∈ 2Q \ ∅ i ∈S

Je to taková mnoˇzina imputac´ı, ˇze kaˇzd´ a pˇr´ıpadn´ a koalice S obdrˇz´ı alespoˇ n v (S), tzn. m˚ uˇze obdrˇzet v´ıc. Nemluv´ı se zde o formován´ı koalic. Srovnejme lib. S 6= Q a Q. Pokud je jádro prázdné, neexistuje stabiln´ı kooperativn´ı ˇreˇsen´ı, které by ustanovilo velkou koalici.

Martin Hrub´ y


Jádro hry (The Core) Hry se super-aditivitou: ◮

Pˇridán´ım jedince do koalice se nezhorˇs´ı hodnota koalice. Velká koalice.

◮

Imputace – neprázdn´ a mnoˇzina.

◮

Jádro – je neprázdné.

Hry bez super-aditivity: ◮

Pˇridán´ım jedince do koalice se zhorˇs´ı hodnota koalice. Velká koalice nemá smysl.

◮

Imputace – neprázdn´ a mnoˇzina. Nen´ı jiˇz kolektivn´ı racionalita. Koaliˇcn´ı racionalita.

◮

Jádro – je prázdné.

Martin Hrub´ y


Jádro hry (The Core) ◮

Imputace vyjadˇruje hern´ı profil.

◮

Pokud pro nˇejaký profil b najdeme profil a, ˇze vˇsichni hráˇci koalice K preferuj´ı a nad b, tak je jasné, ˇze neutvoˇr´ı koalici K s rozdˇelen´ım zisku b, ale a.

◮

Podobnˇe, jako v nekooperativn´ıch hr´ ach, budeme hledat takovou podmnoˇzinu ˇreˇsen´ı, ˇze kaˇzdé ˇreˇsen´ı z podmnoˇziny je stabiln´ı.

Definition Nechˇt v ∈ G Q je hra ve tvaru charakteristické funkce. Jádro hry v je tvoˇreno vˇsemi imputacemi, které nejsou dominovány ˇzádnou jinou imputac´ı pro jakoukoliv koalici. Je-li tedy vektor a v jádru hry v , pak ˇz´ adn´ a koalice ve hˇre nemá tendenci koalici zruˇsit a nahradit vektor a jiným vektorem. Martin Hrub´ y


Pˇr´ıklad bez velké koalice

vA = vB = vC = 1 vAB = 10 vAC = vBC = 7 vABC = 5 Zˇrejmˇe povede na koalici AB s vektorem (5, 5, 1). Pokud by nˇekdo z AB naruˇsil stabilitu, m˚ uˇze vést na vyjedn´ av´ an´ı s C a napˇr. (5, 0, 2) nebo (0, 5, 2).

Martin Hrub´ y


Co je jádro hry? ´ cast hráˇce v koalici je jeho forma volby strategie. Hráˇc hledá Uˇ takovou koalici, která mu spoleˇcnˇe s dohodou o rozdˇelen´ı zisku pˇrinese optimáln´ı uˇzitek. Kaˇzdý hráˇc v´ı, ˇze kaˇzd´ a imputace a ∈ C (v ) mu pˇriˇrazuj´ı optimáln´ı zisky. M´ıt neprázdné jádro je vlastnost hry pro ustanovitelnost velké koalice (pokud velká koalice vede k nejefektivnˇejˇs´ımu ˇreˇsen´ı hry). Logicky, pokud existuje koalice S ⊆ Q, ˇze v (S) > v (Q), pak jádro neexistuje.

Martin Hrub´ y


Pˇr´ıklad Uvaˇzujme tˇr´ıhráˇcovou hru. profil výplata (1,1,1) (-2,1,2) (1,1,2) (1,1,-1) (1,2,1) (0,-1,2) (1,2,2) (-1,2,0) (2,1,1) (1,-1,1) (2,1,2) (0,0,1) (2,2,1) (1,0,0) (2,2,2) (1,2,-2) Q = {1, 2, 3}. Koalice jsou ∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}. Prozkoumáme situaci koalice K = {1, 3} (versus {2}). Koalice K má strategie (1, 1),(1, 2), (2, 1), (2, 2). Protikoalice má ryz´ı strategie 1 a 2. Martin Hrub´ y


Pˇr´ıklad pˇri koalici K = {1, 3} Hráˇci 1 a 3 tvoˇr´ı koalici proti hr´ aˇci 2. Jejich zisk se tud´ıˇz sˇc´ıtá. Strategie 1 2 (1,1) (0,1) (2,-1) (1,2) (0,1) (-1,2) (2,1) (2,-1) (1,0) (2,2) (1,0) (-1,2) Hra má unikátn´ı MNE = 13 , 0, 32 , 0 , 13 , 23 , pˇri kterém dosahuj´ı oˇcekávaného uˇzitku 43 , − 13 . Plyne z toho, ˇze v ({1, 3}) = 34 , v ({2}) = − 13 . Podobnˇe obdrˇz´ıme: v ({1, 2}) = 1, v ({3}) = 0, v ({2, 3}) = 43 , v ({1}) = 14 , v ({1, 2, 3}) = 1, v (∅) = 0. Funkce v je charakteristickou funkc´ı (ovˇeˇrte). Existuje imputace a taková, ˇze a1 + a2 + a3 = 1, a1 ≥ 41 , a2 ≥ − 13 , a3 ≥ 0 a je v jádˇre hry? Martin Hrub´ y


Pˇr´ıklad, výpoˇcet jádra hry Existuj´ı a1 , a2 , a3 , aby bylo splnˇeno (neoˇcek´ av´ ame jedno ˇreˇsen´ı, nýbrˇz mnoˇzinu): a1 + a2 + a3 = 1 a1 ≥ 1/4 a2 ≥ −1/3 a3 ≥ 0 a1 + a2 ≥ 1 a1 + a3 ≥ 4/3 a2 + a3 ≥ 3/4

ˇ sen´ı neexistuje, protoˇze a1 + a2 = 1 implikuje a3 = 0, tzn. Reˇ nesoulad s a1 + a3 ≥ 4/3. J´ adro hry je tud´ıˇz pr´ azdné. H = (0.61, 0.03, 0.36). Martin Hrub´ y


Pˇr´ıklad II., výpoˇcet jádra hry

K {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3} 1 1 v (K ) − 12 0 − 12 0 1 4 2 Soustava pro výpoˇcet j´ adra generovan´ a z této charakteristické funkce má nekoneˇcnˇe mnoho ˇreˇsen´ı, napˇr. (1/3, 1/3, 1/3). Vˇsechny imputace z jádra umoˇzn ˇuj´ı sestavit koalice a hrát kooperativnˇe. Potˇrebujeme dalˇs´ı zjemnˇen´ı tohoto ”solution concept”. H = (3/24, 15/24, 6/24) = (0.125, 0.625, 0.25)

Martin Hrub´ y


Shapley value Nejvýznamnˇejˇs´ı koncept kooperativn´ıch her. ◮

C´ılem je modelovat pˇr´ınos hr´ aˇce i ∈ K pro koalici K .

◮

Slouˇz´ı pro pˇrerozdˇelov´ an´ı zisku koalice. Hr´ aˇc se z´ uˇcastn´ı koalice pˇri imputaci, kter´ a mu pˇrinese jeho ”spravedlivý” pod´ıl.

◮

Obecnˇe: zkoumáme vliv ne´ uˇcasti hr´ aˇce v koalici δ(i , K ) = v (K ) − v (K \ {i })

Koalice K \ {i } má k − 1 ˇclen˚ u a lze vytvoˇrit N −1 (N − 1)! = (k − 1)!(N − k)! k −1

zp˚ usoby. Zkoumáme stˇredn´ı hodnotu pˇr´ınosu hr´ aˇce i do vˇsech moˇzných k-ˇclenných koalic.

Martin Hrub´ y


Shapley value Pˇr´ınos hráˇce i do vˇsech k-ˇclenných koalic: X

hi (k) =

K ⊂Q,k=|K |,i ∈K

X

=

K ⊂Q,k=|K |,i ∈K

v (K ) − v (K \ {i }) = N−1 k−1

(k − 1)!(N − k)! (v (K ) − v (K \ {i })) (N − 1)!

Pro vˇsechny moˇzné koalice to je:

Hi =

N X hi (k) k=1

N

=

X

K ⊂Q,i ∈K

(|K | − 1)!(N − |K |)! (v (K )−v (K \{i })) N!

Martin Hrub´ y


Shapley value Definition Mˇejme hru N hráˇc˚ u danou charakteristickou funkc´ı v. Shapleyho vektor této hry je definov´ an jako vektor H = (H1 , H2 , ..., HN ) jehoˇz kaˇzdá i-tá sloˇzka Hi je vypoˇctena pˇredchoz´ım vztahem. Sloˇzka Hi se nazývá Shapleyho hodnota pro hr´ aˇce i . Z definice Shapleyho hodnoty je patrné, ˇze vˇzdy existuje.

Theorem Shapleyho vektor zadané hry je imputac´ı ve hˇre. D˚ ukaz (ovˇeˇren´ı individu´ aln´ı a kolektivn´ı racionality) jako domác´ı cviˇcen´ı. Martin Hrub´ y


Pˇr´ıklad K v (K )

{1} 100

{2} 10

{3} 0

h1 (1) = 100 h1 (2) = 140+110 2 h1 (3) = 180

{1, 2} 150

{1, 3} 110

h2 (1) = 10 h2 (2) = 50+20 2 h2 (3) = 90

{2, 3} 20

{1, 2, 3} 200

v (∅) 0

h3 (1) = 0 h3 (2) = 10+10 2 h3 (3) = 50

Hráˇc 1 se m˚ uˇze zapojit do dvou dvouˇclenných koalic ({1, 2}, {1, 3}). Dle Shapleyho je jeho pˇr´ınos pro dvouˇclenné koalice dán 1 1 1 1 (v ({1, 3})−v ({3}))+ (v ({1, 2})−v ({2})) = (110−0)+ (150−10) 2 2 2 2 Celkem tedy H1 = 100+125+180 = 135, H2 = 45, H3 = 20. 3 Shapleyho vektor pro zadanou hru je H = (135, 45, 20).

Martin Hrub´ y


Vlastnosti Shapleyho hodnoty

◮ ◮

Individuáln´ı racionalita: Hi ≥ v ({i }) pro vˇsechny i ∈ Q. P Efektivita i ∈Q Hi = v (Q).

◮

Symetrie: pro kaˇzdé dva hr´ aˇce i , j ∈ Q, pro které plat´ı v (K ∪ {i }) = v (K ∪ {j}) pro vˇsechny K ⊆ Q, i ∈ / K, j ∈ / K , je Hi = Hj .

◮

Aditivita: pokud kombinujeme dvˇe hry v a w stejné struktury, pak plat´ı, ˇze Hi (v ) + Hi (w ) = Hi (v + w ).

◮

Nulový hráˇc nebere nic: pokud existuje hr´ aˇc i takový, ˇze v (K ∪ {i }) = v (K ), ∀K ⊂ Q, i ∈ / K , pak je Hi = 0.

Martin Hrub´ y


Pˇr´ıklad: ˇséf a zamˇestnanci

◮

◮

◮

◮

Pˇredpokládejme situaci ˇséfa o a zamˇestanc˚ u w1 , w2 , ..., wk . Q = {o, w1 , w2 , ..., wk }. ˇ s´ı se projekt, který ztroskot´ Reˇ a bez u ´ˇcasti ˇséfa, tzn. v (K ) = 0, ∀K ⊂ Q, o ∈ / K.

Kaˇzdý zamˇestnanec m´ a pˇr´ınos p do koalice, tzn. v (K ) = (|K | − 1)p, ∀K ⊆ Q, o ∈ K Shapley value ˇséfa je

(|K |−1)·p 2

+ |K − 1| ·

p 2

(|K |−1)·p , 2

zamˇestnance p2 .

= |K − 1| · p

Martin Hrub´ y


Pˇr´ıklad: Stavba mostu

4 firmy zvaˇzuj´ı postavit most. Cena mostu je 20 milión˚ u. Jednotlivé firmy jsou ochotny zaplatit maxim´ alnˇe u1 = 10, u2 = 8, u3 = 12, u4 = 16 milión˚ u. Které firmy se dohodnou na stavbˇe mostu a kolik kaˇzdá zaplat´ı? Firmy utvoˇr´ı akˇcn´ı koalici (pro stavbu mostu) pouze za pˇredpokladu, ˇze se dohodnou na platbˇe. Pozn.: Podobné u ´lohy ˇreˇs´ı mechanism design v situac´ıch, kdy chtˇej´ı hráˇci svoje ocenˇen´ı ui tajit. Je pak tˇreba nastavit pravidla, aby to v rámci racionáln´ıho chov´ an´ı dobrovolnˇe pˇriznali.

Martin Hrub´ y


Pˇr´ıklad: Stavba mostu

u1 = 10, u2 = 8, u3 = 12, u4 = 16 Hra je dána charakteristickou funkc´ı # " X ui − C , 0 v (K ) = max i ∈K

Char. funkce vyjadˇruje zisk koalice. v ({i }) = 0; ∀i ∈ Q. Celek v (Q) = 26. Shapley values: H = (5.667, 4.333, 6.667, 9.333). Platba hráˇc˚ u: pi = ui − Hi , tzn. 11 16 20 Celkem 13 + 3 3 + 3 + 3 = 20. Martin Hrub´ y

13 11 16 20 3 , 3 , 3 , 3

.


Nucleolus (Shmeidler, 1969) Definition Nechˇt v je charakteristick´ a funkce s N hr´ aˇci, a je daná imputace a ˇ K je koalice. C´ıslo e(K , a) = v (K ) −

X

ai

i ∈K

se nazývá exces koalice K vzhledem k imputaci a (kolik mus´ı koalice zanechat nerozdˇeleno pˇri imputaci a). Dále oznaˇcme symbolem e(a) vektor o délce 2|Q| − 1 odpov´ıdaj´ıc´ı ˇ exces˚ um vˇsech moˇzných koalic. Seˇradme prvky e(a) sestupnˇe podle velikosti a oznaˇcme tuto posloupnost symbolem f (a). Kaˇzdé imputaci a se tak pˇriˇrad´ı f (a). Pracujeme s mnoˇzinou {f (a)|a je imputace}. Definujme na této mnoˇzinˇe lexikografické uspoˇrádán´ı ≤(lex) . Martin Hrub´ y


Nucleolus, pˇredpoklady

≤(lex)

 p1 = p2 = ()  true (p1 , p2 ) = ≤(lex) (tail (p1 ), tail (p2 )) head(p1 ) ≤ head(p2 )   false otherwise

ˇ Rekneme, ˇze imputace b je pˇrijatelnˇejˇs´ı (vzbuzuje ménˇe námitek) neˇz imputace a, pokud f (b) ≤(lex) f (a).

Znamená to, ˇze imputace b ve vˇsech myslitelných koalic´ıch vede k lepˇs´ımu rozloˇzen´ı zisku.

Martin Hrub´ y


Nucleolus, definice

Definition Nucleolem hry je takov´ a imputace b, pro kterou plat´ı: f (b) ≤(lex) f (a) pro vˇsechny imputace a. Vid´ıme, ˇze nukleolus je forma glob´ aln´ıho optima ve hˇre (stabiln´ı bod).

Martin Hrub´ y


Pˇr´ıklad K {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3} v (K ) −1 −1 −1 1 1 1 0 K výpoˇctu nucleolu pˇristoup´ıme analyticky, budeme proto vyjadˇrovat vektory e(a) analyticky: −(a1 + a2 + a3 ) 1 − a1 − a2 1 − a1 − a3 1 − a2 − a3 −(1 + a1 ) −(1 + a2 ) −(1 + a3 ) Protoˇze v (Q) = 0, je prvn´ı sloˇzka rovna nule. Pˇrijatelné je cokoliv, kde ai ≥ −1. Nukleolus je (0, 0, 0). Martin Hrub´ y


Pˇr´ıklad Mˇejme hru s char. funkc´ı: v (Q) = 1, v ({1}) = 12 , v ({2}) = 0. Imputace: 1 a1 ≥ , a2 ≥ 0, a1 + a2 = 1 2

a1 ∈

1 , 1 , a2 = 1 − a1 2

a1 ∈

1 , 1 , a2 = 1 − a1 2

Jádro (core): 1 a1 ≥ , a2 ≥ 0, a1 + a2 = 1 2 Shapley value: H1 = ⇒ a1 = 43 , a2 = 14

1 2

1 2

+ 1 = 34 , H2 =

Martin Hrub´ y

1 2

0+

1 2


=

1 4

Pˇr´ıklad, nucleolus Pˇripom´ınáme: e(K , a) = v (K ) − Pak

X

ai

i ∈K

e({1}, a) = 12 − a1 , e({2}, a) = 0 − a2 ,1e({1, 2}, a) = 1 − a1 − a2 = 0 1 e(a) = −a2 , 2 − a1 , 0 = −a2 , a2 − 2 , 0 f (a) = (0, −a2 , a2 − 12 ) ⇔ 0 ≤ a2 ≤ 41 f (a) = (0, a2 − 12 , −a2 ) ⇔ 41 ≤ a2 ≤ 1 Pokud dáme a2 = 0, pak je exces 0, 0, − 12 . Pokud dáme a2 = 41 , pak je exces 0, − 41 , − 14 . Vid´ ıme, ˇze 1 1 1 0, − 4 , − 4 ≤(lex) 0, 0, − 2 . Co dát a2 = 21 ? Nejpˇrijatelnˇejˇs´ı exces je pˇri a2 = 41 ⇒ a1 = 34 . Martin Hrub´ y


Pˇr´ıklad, Nashovské vyjednáván´ı

g (a1 , a2 ) =

1 a1 − 2

a2 =

1 a1 − 2

(1 − a1 ) =

1 3 = a1 − a12 − = h(a1 ) 2 2

h′ (a1 ) = 0 ⇒ a1 =

Martin Hrub´ y

3 1 , a2 = 4 4


Pˇr´ıklad, z historie

Pˇr´ıpad u soudu: Dva drˇz´ı jeden kus odˇevu. Jeden volá: ”celý je m˚ uj”, druhý volá: ”má je polovina”. Potom prvn´ı dostane tˇri ˇctvrtiny a druhý jednu ˇctvrtinu. Talmud Rabi Raˇsi (1105) komentuje ˇreˇsen´ı: druhý pˇrizn´ av´ a prvn´ımu polovinu, ta je tedy jasn´ a. Zbýv´ a rozdˇelit tu druhou polovinu rovným d´ılem.

Martin Hrub´ y


Zanedbáno

◮

Dalˇs´ı modely vyjedn´ av´ an´ı.

◮

D˚ ukaz Nash bargaining solution.

◮

Shapley-Shubik˚ uv index a dalˇs´ı indexy.

◮

Stable-sets (von Neumann, Morgenstern).

◮

Formalizace výpoˇctu nucleolu.

◮

Case-study.

Martin Hrub´ y


Pˇr´ıˇstˇe Opakované hry: ◮

forma her v rozˇs´ıˇrené formˇe (sekvenˇcn´ı),

◮

vliv opakovan´ı na chov´ an´ı hr´ aˇc˚ u,

◮

skuteˇcnˇe to vede ke spolupr´ aci (tzn. k efektivnˇejˇs´ımu výsledku konfliktu)?

Dalˇs´ı kapitoly THE: ◮

Mechanism design – jak to udˇelat, aby se lidi chovali správnˇe?

◮

Aukce – jak to udˇelat, aby zaplatili co nejv´ıc?

◮

Public choice – jak nastavit pravidla voleb, abychom dosáhli objektivnosti?

◮

Korelované ekvilibrium – existuje obecnˇejˇs´ı koncept neˇz MNE?

◮

Evoluce – je výsledkem strategických konflikt˚ u?

◮

Rozbor modelu energetických trh˚ u ve stˇredn´ı Evropˇe – jak modelovat reálný sloˇzitý problém? Martin Hrub´ y


The Cooperative Games and Bargaining

Recommend Documents