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

Vyjednáván´ı 1.1 Základn´ı vyjednávac´ı u´ loha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Definice vyjednávac´ı u´ lohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Axiomatická stavba Nashova vyjednávac´ıho ˇreˇsen´ı . . . . . . . . . . . . . . . . . .

2

Kooperativn´ı hry s pˇrenositelným uˇzitkem ´ 2.1 Uvod . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Vyjádˇren´ı individuáln´ıho zisku v kooperativn´ıch hrách ˇ sen´ı kooperativn´ıch her . . . . . . . . . . . . . . . 2.3 Reˇ 2.4 Shapleyho hodnota ve hˇre (Shapley value) . . . . . . . 2.5 Pˇr´ıklady kooperativn´ıch her . . . . . . . . . . . . . . . 2.6 Nukleolus . . . . . . . . . . . . . . . . . . . . . . . .

2

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

3 3 5 5 8 8 9 11 12 14 17

Chapter 1 Vyjednáván´ı V dosavadn´ım textu jsme se zabývali situacemi, kdy hrácˇ i spolu nesm´ı nebo nechtˇej´ı komunikovat, aby se domluvili na konkrétn´ım profilu. Proˇc by vlatnˇe mˇeli hrácˇ i provádˇet pokusy o dohodu profilu? Ve Vˇezˇnovˇe dilematu je zjevné, zˇ e by se hrácˇ i mohli dohodnout na spoleˇcné strategii nevypov´ıdat a dosáhnout tak evidentnˇe lepˇs´ıho uˇzitku neˇz pˇri nekooperativn´ı hˇre. Nab´ız´ı se ovˇsem u´ vaha, jak by dohoda dopadla, kdyby se opˇet rozeˇsli do svých cel a pak byli postaveni pˇred rozhodnut´ı izolovanˇe. Jejich dohoda by byla postavena na v´ıˇre, zˇ e zˇ a´ dný nezrad´ı. Tˇezˇ ko uvˇeˇrit, zˇ e by vˇezni dostáli svého slibu. Proto pˇredpokládejme, zˇ e dohoda o profilu mus´ı být pro hrácˇ e závazná. Mus´ı existovat nˇejaký arbitr, který udˇel´ı tak vysokou pokutu zrádci, zˇ e se zrada racionálnˇe vzato nevyplat´ı. Nem˚uzˇ eme d˚uvˇeˇrovat slib˚um, protoˇze stále pˇredpokládáme ryz´ı individuáln´ı racionalitu hrácˇ u˚ . Ve strategických interakc´ıch m˚uzˇ e doj´ıt k situaci nekooperativn´ı hry, která má sice svoje nekooperativn´ı nashovo ekvilibrium, ale pˇresto hrácˇ i vid´ı moˇznost efektivnˇejˇs´ıho výsledku hry, pokud se dohodnou na jiném profilu. Proces hledán´ı dohody se nazývá vyjednáván´ı (angl. bargaining). Vyjednávac´ı u´ lohy maj´ı v literatuˇre v´ıce moˇzných ˇreˇsen´ı. Jedno z nejznámnˇejˇs´ıch je ˇreˇsen´ı Johna Nashe z roku 1950 (odkaz) známé pod Nash bargaining solution. Nash sv˚uj pˇr´ıstup k vyjednáván´ı postavil na cˇ tyˇrech axiomech. Ukázal pak, zˇ e pokud lze splnit tyto axiomy (podm´ınky), pak má u´ loha právˇe jedno optimáln´ı ˇreˇsen´ı – Nash bargaining solution.

1.1

´ Základn´ı vyjednávac´ı uloha

Pˇredpokládejme dva hrácˇ e A a B. Hrácˇ i maj´ı za u´ kol navrhnout rozdˇelen´ı fixn´ı cˇ a´ stky X mezi sebe tak, zˇ e xA + xB ≤ X, kde xA je pod´ıl pro hrácˇ e A a obdobnˇe xB je pod´ıl pro hrácˇ e B. Pokud se dohoda nepovede, hrácˇ i budou vyplaceni nekooperativn´ım uˇzitkem cA , cB , kde lze pˇredpokládat, zˇ e ci << X/2. Koneˇcnˇe pˇredpokládáme, zˇ e hrácˇ i maj´ı obecnˇe odliˇsný uˇzitek ui (xi ) z pˇridˇelené cˇ a´ stky xi .

3

Problém pro vyjednáván´ı je stanoven´ı rozdˇelen´ı (x∗A , x∗B ) takové, zˇ e s n´ım oba hrácˇ i budou souhlasit. Zat´ım bez teoretických znalost´ı Nashova ˇreˇsen´ı pouze pˇrevezmeme Nash˚uv výsledný vzorec, kde Nash tvrd´ı, zˇ e optimáln´ı dohody lze dosáhnout maximalizac´ı funkce: g(uA , uB ) = (uA − cA ) · (uB − cB ) V pˇr´ıpadˇe naˇs´ı základn´ı u´ lohy to znamená: uA (xA ) = xA uB (xB ) = X − xA xA + xB ≤ X Tedy, g(·) = (xA − cA ) · (X − xA − cB ) Pokud poloˇz´ıme X = 100, cA = cB = 0, pak obdrˇz´ıme: g(·) = xA · (100 − xA ) Funkce g má extrém v bodˇe g 0 (xA ) = 0, tzn. g 0 = [100xA − x2A ]0 = 100 − 2xA g 0 = 0 = 100 − 2xA nám dává extrém v bodˇe xA = 50, tedy rozdˇelen´ı (x∗A , a∗B ) = (50, 50). Tento výsledek nen´ı moˇzná pro cˇ tenáˇre pˇrekvapuj´ıc´ı, neboˇt uˇzitkové funkce hrácˇ u˚ jsou symetrické a tud´ızˇ rozdˇelen´ı mus´ı nutnˇe vést k rovnomˇernému rozdˇelen´ı. V dalˇs´ım pˇr´ıkladˇe uvid´ıme vliv nesymetrických funkc´ı uˇzitku.

´ Základn´ı vyjednávac´ı uloha s nesymetrickou funkc´ı uˇzitku hrácˇ u˚ Pˇredpokládejme, zˇ e hrácˇ A je znaˇcnˇe citlivý na riziko a proto jeho uˇzitek z pod´ılu neroste lineárnˇe s výsˇ´ı pod´ılu. Podle vztahu k riziku rozliˇsujeme hrácˇ e (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´ı riziok (Risk-seeking): u(x) = x2 . 4

Hrácˇ A má tedy svou uˇzitkovou funkc´ı následuj´ıc´ı (druhý hrácˇ z˚ustává neutráln´ı k riziku): uA (xA ) =

√ xA

uB (xB ) = xB = 100 − xA Nyn´ı je optimalizovaná funkce v tomto tvaru: √ g(xA ) = ( xA ) · (100 − xA ) g0 =

100 − xA √ − xA √ 2 xA

, tedy rozdˇelen´ı, se kterým oba souhlas´ı je ( 100 , 2 · 100 ). Je vidˇet, a ta má extrém v bodˇe xA = 100 3 3 3 zˇ e hrácˇ citlivý k riziku souhlas´ı s menˇs´ım pod´ılem. V reálné situaci by proto nejsp´ısˇ tento hrácˇ sv˚uj postoj rád pˇred protihácˇ em utajil.

1.2

´ Definice vyjednávac´ı ulohy

V tomto odstavci formálnˇe zavedeme vyjednávac´ı u´ lohu. Tato definice je univerzáln´ı pro vˇsechny problémy tohoto druhu bez ohledu na volbu konkrétn´ıho vyjednávac´ıho ˇreˇsen´ı. Definice 1. Vyjednávac´ı u´ loha je definována jako dvojice (Ω, c), kde • Ω je tak zvaná vyjednávac´ı mnoˇzina, tedy mnoˇzina vˇsech dosaˇzitelných dvojic uˇzitk˚u (uA , uB ). • c = (cA , cB ) je nekooperativn´ı výsledek hry v pˇr´ıpadˇe nedosaˇzen´ı hodnoty (angl. disagreement value). Na obrázku 1.1 je vidˇet pˇr´ıklad vyjednávac´ı mnoˇziny. Obrázek vymezuje prostor vˇsech dosaˇzitelných uˇzitk˚u pro hrácˇ e A a B, a souˇcasnˇe ukazuje jejich nekooperativn´ı výsledek. Hrácˇ i zˇrejmˇe povedou vyjednáván´ı v té cˇ a´ sti mnoˇziny, kde dosahuj´ı lepˇs´ıch uˇzitk˚u neˇz tˇech nekooperativn´ıch a nav´ıc t´ım zcela vyˇcerpaj´ı dosaˇzitelné rozdˇelitelné maximum (dané zde ohraniˇcen´ım vyjednávac´ı mnoˇziny). Vˇsechny vyjednávac´ı situace tohoto typu lze oznaˇcit symbolem Σ. Vyjednávac´ı ˇreˇsen´ı oznaˇc´ıme pˇriˇrazen´ım F : Σ → R2 a symbolem Fi budeme rozumˇet uˇzitek hrácˇ e i. V tomto vyjádˇren´ı nám zápis F (Ω, c) oznaˇcuje výsledek zadané hry.

1.3

Axiomatická stavba Nashova vyjednávac´ıho rˇ eˇsen´ı

John Nash vyslovil ve svém cˇ lánku1 cˇ tyˇri axiomy vyjednáván´ı a dokázal, zˇ e existuje pouze jedna funkce (jedno ˇreˇsen´ı), která splˇnuje tyto axiomy. Projdeme si tyto axiomy a v závˇeru pˇredvedeme 1

Nash, J. (1950). The Bargaining Problem. Econometrica 18 (2)

5

Figure 1.1: Vyjednávac´ı mnoˇzina ve hˇre dvou hrácˇ u˚ [obrázek pˇrevzat s pˇrednásˇek M. Hykˇsové] Nash˚uv theorém o Nashovˇe vyjednávac´ım ˇreˇsen´ı (bez d˚ukazu). Podotknˇeme, zˇ e pochopitelnˇe na vyjednáván´ı existuje v´ıce názor˚u a ˇreˇsen´ı. Nezávislost na lineárn´ıch transformac´ıch uˇzitkových funkc´ı Axiom 1. Nechtˇ u0i = αi ui + βi a c0i = αi ci + βi , αi > 0. Ω0 je odvozeno od Ω. Pak Fi (Ω0 , c0 ) = αi Fi (Ω, c) + βi pro i ∈ {A, B}. Pˇredpokládáme tedy, zˇ e afinn´ı transformace uˇzitkových funkc´ı a nekooperativn´ıch uˇzitk˚u neovlivn´ı vyjednávac´ı proces. V´ıme, zˇ e dosáhneme ekvivalentn´ı hry, která vykazuje stejné strategické charakteristiky (dominance, BR, ekvilibria). Pareto efektivita rˇ eˇsen´ı Axiom 2. Je-li F (Σ) = (uA , uB ), pak neexistuje jiný výsledek (u0A , u0B ) ∈ Ω takový, zˇe u0i > ui pro nˇekterého hrácˇ e i a souˇcasnˇe u0j ≥ uj pro j 6= i. Tento axiom pˇredpokládá klasickou Pareto efektivitu, tzn. pokud hrácˇ i dojdou dohody (uA , uB ), pak neexistuje jiné rozdˇelen´ı (bargaining solution), ve kterém by alespoˇn jeden hrácˇ byl s výsledkem striktnˇe lepˇs´ı a zbytek hrácˇ u˚ pˇrinejmenˇs´ım na stejnˇe dobrém výsledku. V rámci vyjednávac´ı mnoˇziny existuj´ı výsledky (u0A , u0B ) ∈ Ω, kdy u0i > ui plat´ı pro nˇekterého hrácˇ e i a souˇcasnˇe u0j < uj pro j 6= i. Tyto vˇsak nezkoumáme jako pˇrijatelné. Z axiomu pˇredevˇs´ım plyne, zˇ e budeme zkoumat ohraniˇcen´ı vyjednávac´ı mnoˇziny, které tvoˇr´ı mnoˇzinu Pareto efektivn´ıch profil˚u. Vlic symetrie uˇzitkových funkc´ı na výsledek Axiom 3. Pˇripustˇme cA = cB a pˇredpokládejme, zˇe (uA , uB ) ∈ Ω právˇe tehdy pokud (uB , uA ) ∈ Ω. Pak FA (Ω, c) = FB (Ω, c). 6

Maj´ı-li hrácˇ i 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. Symetrie zavád´ı formu spravedlnosti mezi hrácˇ i. Zd˚uraznˇeme, zˇ e symetrii nenaruˇs´ı jenom rozd´ılnost uˇzitkových funkc´ı, ale i nesymetrie nekooperativn´ıch výsledk˚u. Logicky, pokud jeden hrácˇ pˇri nedohodˇe z´ıská v´ıce neˇz druhý, pak je jeho poˇca´ teˇcn´ı vyjednávac´ı situace lepˇs´ı neˇz u protihrácˇ e. Nezávislost na irelevantn´ıch alternativách Nezávislost na irelevantn´ıch alternativách (angl. Independence of Irrelevant Alternatives) je obecný, velmi d˚uleˇzitý pˇredpoklad ve vˇsech cˇ a´ stech teorie her, kde se oˇcekává zkoumán´ı preferenc´ı. Axiom 4. Mˇejme dvˇe vyjednávac´ı situace (Ω, c) a (Ω0 , c) takové, zˇe Ω0 ⊆ Ω a F (Ω, c) ⊆ Ω0 . Pak F (Ω, c) = F (Ω0 , c). Máme vyjednávac´ı oblast Ω a jej´ı rˇeˇsen´ı F (Ω, c). Pokud by se hypoteticky mˇelo vyjednáván´ı omezit na podmnoˇzinu Ω0 ⊆ Ω a souˇcasnˇe by ˇreˇsen´ı p˚uvodn´ıho problému F (Ω, c) z˚ustaválo prvkem Ω0 , pak v problému Ω0 nen´ı moˇzné doj´ıt k jinému ˇreˇsen´ı neˇz F (Ω, c). Prostor Ω0 \ Ω tvoˇr´ı irelevantn´ı alternativy, jejichˇz pˇr´ıtomnost nebo nepˇr´ıtomnost ve vyjednávac´ı mnoˇzinˇe nesm´ı m´ıt vliv na výsledek vyjednáván´ı.

Po formulaci cˇ tyˇrech vstupn´ıch pˇredpoklad˚u na nich J. Nash formuloval následuj´ıc´ı theorém. Vˇeta 5. Vyjednávac´ı rˇeˇsen´ı F : Σ → R2 naplˇnuje axiomy 1-4 právˇe tehdy, pokud je to Nashovo vyjednávac´ı rˇeˇsen´ı. Pro doplnˇen´ı toho podstatného detailu, co je to vlastnˇe to Nashovo vyjednávac´ı ˇreˇsen´ı (Nash bargaining solution) formulujme vˇetu jinak: Vˇeta 6. Existuje pouze jedna funkce F : Σ → R2 modeluj´ıc´ı Nashovo vyjednávac´ı rˇeˇsen´ı. Je definována jako F (Ω, c) = (u∗A , u∗B ), kde (u∗A , u∗B ) = arg max {(uA − cA )(uB − cB ) | (uA , uB ) ∈ Ω ∧ uA ≥ cA , uB ≥ cB } uA ,uB

7

Chapter 2 Kooperativn´ı hry s pˇrenositelným uˇzitkem 2.1

´ Uvod

Kooperativn´ı hry navazuj´ı na vyjednáván´ım v tom smˇeru, zˇ e tématem vyjednáván´ı je utvoˇren´ı koalic a pˇr´ıpadné pˇrerozdˇelen´ı zisku koalice. Na prvn´ı pohled se bude zdát, zˇ e v kooperativn´ıch hrách nen´ı patrný zájem jedince, jeho strategie a pˇr´ıpadný zisk. Tyto pojmy se vyjasn´ı v pr˚ubˇehu následuj´ıc´ıho textu. Jako obvykle, budeme zkoumat mnoˇzinu hrácˇ u˚ Q obsahuj´ıc´ı N hrácˇ u˚ . Hrácˇ i mohou vyjednávat o utvoˇren´ı koalic, kde koalic´ı K rozum´ıme neprázdnou podmnoˇzinu mnoˇziny hrácˇ u˚ . Pokud tedy neuvaˇzujeme prázdnou koalici, lze z N hrácˇ u˚ utvoˇrit celkem 2N − 1 koalic. Koalici tvoˇrenou vˇsemi hrácˇ i budeme nazývat velkou koalic´ı. Zaˇcneme definic´ı kooperativn´ı hry dané charakteristickou funkc´ı: Definice 2. Kooperativn´ı 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, zˇe v(∅) = 0. Charakteristickou funkc´ı budeme oznaˇcovat celou hru. Hodnoty v(⊆ Q) udávaj´ı s´ılu jednotlivých moˇzných koalic. Abychom lépe vyjádˇrili následuj´ıc´ı definice a vˇety, zavedeme mnoˇzinu GN vˇsech N-hrácˇ ových kooperativn´ıch her, lépe ˇreˇceno mnoˇzinu vˇsech moˇzných funkc´ı v : 2Q → R. Konkrétn´ı hru pak budeme vyb´ırat z této mnoˇziny, tedy budeme psát v ∈ GN . Hrácˇ i dohodnou utvoˇren´ı koalic a koalice jsou vyplaceny dle charakteristické funkce. Charakteristické funkce ovˇsem neurˇcuj´ı, kolik maj´ı dostat vyplaceno jednotliv´ı hrácˇ i a vzniká tedy dalˇs´ı problém k vyjednáván´ı a t´ım je pˇrerozdˇelen´ı zisku. 8

Teorie kooperativn´ıch her je pomˇernˇe velmi rozsáhlá. Zájemce o podrobnˇejˇs´ı definice m˚uzˇ e prostudovat obsáhlejˇs´ı práce1 . My se zamˇeˇr´ıme zkrácenˇe na tyto jej´ı podstatné cˇ a´ sti: • Vyjádˇren´ı individuáln´ıho zisku hrácˇ u˚ ve hˇre a tud´ızˇ i individuáln´ı racionality hrácˇ u˚ – povede to k definici pojmu imputace. • Koncepty ˇreˇsen´ı kooperativn´ıch situac´ı a tedy vlastnˇe formy ekvilibri´ı – zavedeme pojmy jádro hry, Shapleyho hodnota a nukleolus. • Vazba nekooperativn´ıch a kooperativn´ıch her. Pˇrednˇe si uvˇedom´ıme, zˇ e nás pˇr´ıliˇs nezaj´ımaj´ı tak zvané nepodstatné hry: Definice 3. Hra v ∈ GN se nazývá nepodstatná, pokud plat´ı: v(Q) =

X

v({i})

i∈Q

Pokud hra nen´ı nepodstatná, pak se nazývá podstatná. V nepodstatné hˇre spojen´ım dvou jednotlivc˚u i a j vznikne koalice, která má hodnotu sumy hodnoty v({i}) a v({j}). V takové hˇre nemá smysl tvoˇrit koalice, protoˇze nepˇrinásˇej´ı zˇ a´ dnou pˇridanou hodnotu. Podobnˇe vyzn´ıvá definice aditivn´ı hry: Definice 4. Hra v ∈ GN se nazývá aditivn´ı, pokud plat´ı: v(S ∪ T ) = v(S) + v(T ) pro vˇsechny S, T ⊆ Q, kde S ∩ T = ∅

2.2

Vyjádˇren´ı individuáln´ıho zisku v kooperativn´ıch hrách

Pˇredstavme si kooperativn´ı hru tˇrech hrácˇ u˚ Q = {A, B, C}, jej´ızˇ charakteristická funkce je dána v(∅) = 0, v(A) = v(B) = v(C) = 1, v({A, B} = v({A, C}) = v({B, C}) = 5, v(Q) = 100. Hrácˇ i by zˇrejmˇe svolili k utvoˇren´ı velké koalice, jej´ızˇ výplata by byla 100, ale co by dˇelali s obdrˇzeným ziskem? M˚uzˇ eme doufat, zˇ e by si ho rovnomˇernˇe rozdˇelili. Co ovˇsem udˇelaj´ı v situaci, kdy v(C) = 50? Hrácˇ C se zúcˇ astn´ı velké koalice pouze tehdy, pokud mu poskytne zisk lepˇs´ı neˇz pˇri jeho nekooperaci. Pˇredpokládejme, zˇ e se hrácˇ i sejdou a dohodnou rozdˇelen´ı zisku (25, 25, 50) nebo jeˇstˇe jistˇejˇs´ı (24, 24, 52). Vid´ıme, zˇ e vytvoˇren´ı koalice je spojeno s vyjednáván´ım o rozdˇelen´ı budouc´ıho zisku. 1

Pelef, Sudholter: Introduction to the Theory of Cooperative Games

9

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

X

ai

i∈S

Lze tuˇsit, zˇ e pracujeme se spojitými u´ lohami a zˇ e tud´ızˇ prostor pro vyjednáván´ı o rozdˇelen´ı individuáln´ıho zisku bude potenciálnˇe nekoneˇcný. Zˇrejmˇe budeme pracovat s prostorem výplatn´ıch vektor˚u X ∗∗ (v) takových, zˇ e X ∗∗ (v) = {a ∈ RN |a(Q) ≤ v(Q)} Prostor X ∗∗ (v) budeme nazývat prostorem dosaˇzitelných zisk˚u (feasible payoffs). Hrácˇ i si prostˇe nemohou rozdˇelit v´ıc, neˇz je hodnota velké koalice (lidovˇe ˇreˇceno prostˇe v´ıc penˇez k rozdˇelen´ı nemaj´ı). Je to ovˇsem pouze prvn´ı pˇribl´ızˇ en´ı k hledán´ı racionáln´ıho vyjednávac´ıho prostoru, neboˇt v X ∗∗ (v) existuj´ı takové výplatn´ı vektory a, zˇ e a(Q) < v(Q), coˇz znamená, zˇ e 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)} Prostor X ∗ (v) vyjadˇruje kolektivn´ı racionalitu koalic, které neuvaˇzuj´ı výplatn´ı vektory, které jim nepˇrinásˇ´ı alespoˇn zisk na u´ rovni hodnoty jejich koalice (vˇcetnˇe koalic jednoprvkových). Zaj´ımá nás pˇredevˇs´ım individuáln´ı racionalita jedince. Výplatn´ı vektor a ∈ X ∗ (v) je individuálnˇe racionáln´ı, pokud pro vˇsechny i ∈ Q plat´ı, zˇ e: ai ≥ v({i}) Dostáváme se k definici pojmu imputace. Definice 5. Výplatn´ı vektor a ∈ RN je imputac´ı ve hˇre v ∈ GN , pokud je efektivn´ı a souˇcasnˇe individuálnˇe racionáln´ı, t.j.: P • i∈Q ai = v(Q) • ai ≥ v({i}) pro vˇsechny i ∈ Q Prostor vˇsech imputac´ı hry v ∈ GQ budeme oznaˇcovat X(v). Je zˇrejmé, zˇ e X(v) bude prázdný P pouze tehdy, pokud v(Q) < i∈Q v({i}). Dále bude bude X(v) jednoprvkový v aditivn´ı hˇre (nepodstatné hˇre) a t´ım jedinným prvkem bude 10

a = (v(1), v(2), ..., v(N ))

2.3

ˇ sen´ı kooperativn´ıch her Reˇ

Budeme se nyn´ı zabývat hledán´ım racionáln´ıho podprostoru imputac´ı, který m˚uzˇ e vést k modelu rozhodnut´ı hrácˇ u˚ o utvoˇren´ı velké koalice a rozdˇelen´ı zisku. Budeme hledat formu ekvilibria v kooperativn´ıch hrách. Definic vyjadˇruj´ıc´ıch kooperativn´ı ekvilibrium je v´ıce, proto je budeme obecnˇe oznaˇcovat jako návrhy rˇeˇsen´ı hry (solution concepts). Základn´ı formou ˇreˇsen´ı hry je jádro hry. Definice 6. Jádro C(v) hry v ∈ GQ je tvoˇreno mnoˇzinou imputac´ı ( C(v) =

a ∈ X(v)|

) X

ai ≥ v(S); ∀S ∈ 2Q \ ∅

i∈Q

Jádro hry je tedy tvoˇreno mnoˇzinou imputac´ı, kde zˇ a´ dná koalice S nemá d˚uvod se rozloˇzit a utvoˇrit jinou koalici neˇz velkou koalici. Jádro tvoˇr´ı mnoˇzinu akceptovatelných stabiln´ıch ˇreˇsen´ı ve hˇre, m˚uzˇ eme tedy ˇr´ıct ekvilibri´ı. Je to vˇsak velmi obecné ˇreˇsen´ı, které je obecnˇe nekoneˇcné. Nejlépe ho lze vyjádˇrit mnoˇzinou lineárn´ıch nerovnic. Jádro hry lze tézˇ vyjádˇrit formou preferenc´ı hrácˇ u˚ nad imputacemi. Zavedeme proto pojem dominance nad imputacemi. ˇ Definice 7. Nechtˇ v ∈ GQ , S je koalice a a, b jsou imputace. Rekneme, zˇe a dominuje nad b pro koalici S, pokud: • ai > bi pro vˇsechny i ∈ S •

P

i∈S

ai ≤ v(S)

P Imputace mus´ı být jaksi shora omezená ( i∈K ai ≤ v(K)). Preferenci budeme znaˇcit a S b. M˚uzˇ eme následnˇe definovat jádro hry pomoc´ı dominance nad imputacemi. Definice 8. Nechtˇ v ∈ GQ . Jádro hry v je tvoˇreno vˇsemi imputacemi, které nejsou dominovány zˇa´ dnou jinou imputac´ı pro jakoukoliv koalici. Je-li tedy imputace a v jádru hry v, pak zˇ a´ dná koalice ve hˇre nemá tendenci koalici zruˇsit a nahradit imputaci a jinou imputac´ı. V dalˇs´ım textu se budeme dále zabývat racionalitou jedince, který bude cht´ıt vyˇc´ıslit svou hodnotu pro koalici, j´ızˇ je cˇ lenem. Jedinec i bude je samozˇrejmˇe schopen odvodit rozd´ıl mezi hodnotou koalice s jeho pˇr´ıtomnost´ı a bez jeho pˇr´ıtomnost´ı. Takový jedinec chápe: 11

• Svou vlastn´ı hodnotu ve hˇre v({i}) a t´ım i pˇr´ıpadný sv˚uj individuáln´ı zisk, pokud by nekooperoval. • Svou pˇridanou hodnotu v(S) − v(S \ {i}), kterou pˇrinásˇ´ı pro koalici S, kde i ∈ S. Hrácˇ i ovˇsem chce znát svou pˇridanou hodnotu pro vˇsechny koalice. Hledá formu statistiky, která by mu ji jasnˇe vyˇc´ıslila a dokonce tak, aby jeho názor o celkové jeho pˇridané hodnotˇe pro hru byl akceptován i ostatn´ımi hrácˇ i.

2.4

Shapleyho hodnota ve hˇre (Shapley value)

Jak jiˇz bylo ˇreˇceno, zkoumáme vliv neúcˇ asti hrácˇ e v koalici δ(i, S) = v(S) − v(S \ {i}), tedy jeho nepopiratelný pˇr´ınos pro koalici. Pokud by koalice S mˇela být utvoˇrena, je jisté, zˇ e hrácˇ i by mˇel nárok poˇzadovat δ(i, S). Má to pro nˇej pochopitelnˇe význam pouze tehdy, pokud δ(i, S) ≥ v({i}). S pojmem koalice S nyn´ı budeme pracovat obecnˇe. Neˇreˇs´ıme jednu konkrétn´ı koalici (pˇr´ınos hrácˇ e i pro konrétn´ı koalici jsme si jiˇz odvodili). Koalici S budeme sestavovat ze vˇsech zbylých hrácˇ u˚ Q \ {i} a poˇzadovanou statistiku (Shapleyho hodnotu) budeme budovat postupnˇe. Zaˇcneme u pˇredpokladu vˇsech koalic S takových, zˇ e |S| = k. Pak koalice S \ {i} má k − 1 cˇ len˚u a lze vytvoˇrit (N − 1)! N −1 (N − 1)! = = (k − 1)!(N − 1 − (k − 1))! (k − 1)!(N − k)! k−1 zp˚usoby ze vˇsech zbylých hrácˇ u˚ Q \ {i}2 . Zkoumáme stˇredn´ı hodnotu pˇr´ınosu hrácˇ e i do vˇsech moˇzných k-ˇclenných koalic. Pˇr´ınos hrácˇ e i do vˇsech k-ˇclenných koalic je dán: X

v(S) − v(S \ {i}) N −1

S⊆Q,k=|S|,i∈S

k−1

hi (k) =

Je vidˇet, zˇ e hi (k) je obyˇcejný aritmetický pr˚umˇer (suma vˇsech pˇr´ınos˚u do vˇsech utvoˇritelných koalic dˇelená poˇctem utvoˇritelných koalic). Výraz hi (k) dále uprav´ıme na X

hi (k) =

S⊆Q,k=|S|,i∈S

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

Kdyˇz budeme iterovat pˇres vˇsechny velikosti moˇzné koalice, pak pro vˇsechny moˇzné koalice dále obdrˇz´ıme celkovou statistiku pˇr´ınosu hrácˇ e i do hry: Hi =

N X hi (k) k=1

2

N

=

X S⊆Q,i∈S

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

Snad je to jasné, ale mluv´ıme o kombinac´ıch bez opakovan´ı

12

(2.1)

Definice 9. Mˇejme v ∈ GQ . Shapleyho vektor této hry je definován jako vektor H = (H1 , H2 , ..., HN ) jehoˇz kaˇzdá i-tá sloˇzka Hi je dána vztahem 2.1. Sloˇzka Hi se nazývá Shapleyho hodnota pro hrácˇ e i. Z definice Shapleyho hodnoty je patrné, zˇ e vˇzdy existuje (v definiˇcn´ım oboru funkce Hi : GQ → R nen´ı zˇ a´ dná hodnota, pro kterou by funkce nemˇela být definována). Vˇeta 7. Mˇejme hru v ∈ GQ . Shapleyho vektor hry v je imputac´ı ve hˇre v. Proof. D˚ukaz (ovˇeˇren´ı individuáln´ı a kolektivn´ı racionality) jako domác´ı cviˇcen´ı. Pˇr´ıklad Mˇejme hru zadanou následuj´ıc´ı hodnot´ıc´ı funkc´ı: {1}

{2}

{3}

v(S) 100

10

0

S

{1, 2} {1, 3} 150

110

{2, 3} {1, 2, 3} 20

200

v(∅) 0

h1 (1) = 100 h2 (1) = 10 h3 (1) = 0 140+110 50+20 h1 (2) = h2 (2) = 2 h3 (2) = 10+10 2 2 h1 (3) = 180 h2 (3) = 90 h3 (3) = 50 Hrácˇ 1 se m˚uzˇ e 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).

Vlastnosti Shapleyho hodnoty Shapleyho hodnota má následuj´ıc´ı vlastnosti: • Individuáln´ı racionalita: Hi ≥ v({i}) pro vˇsechny i ∈ Q. Shapleyho hodnota vyˇc´ısluje imputaci, která je pˇrijatelná pro kaˇzdého jednotlivého hrácˇ e. • Efektivita:

P

i∈Q

Hi = v(Q). Shapleyho hodnota rozdˇeluje celou hodnotu velké koalice.

13

• Symetrie: pro kaˇzdé dva hrácˇ e i, j ∈ Q, pro které plat´ı v(K ∪ {i}) = v(K ∪ {j}) pro vˇsechny K ⊆ Q, i ∈ / K, j ∈ / K, je Hi = Hj . Pokud existuj´ı dva hrácˇ i i, j ∈ Q takov´ı, zˇ e do libovolné koalice pˇrinásˇej´ı stejný potenciál, pak jsou ocenˇeni stejnou hodnotou. • Aditivita: pokud kombinujeme dvˇe hry v a w stejné struktury (se stejnými hrácˇ i), pak plat´ı, zˇ e Hi (v)+Hi (w) = Hi (v+w). Je to patrné z linearity Shapleyho funkce (je to lineárn´ı zobrazen´ı). • Nulový hrácˇ nebere nic: pokud existuje hrácˇ i takový, zˇ e v(K ∪ {i}) = v(K), ∀K ⊂ Q, i ∈ / K, pak je Hi = 0. Co je ovˇsem na Shapleyho hodnotˇe nejv´ıc d˚uleˇzité je jej´ı unikátnost. Pˇripomeˇnme, zˇ e hledáme ekvilibrium v kooperativn´ıch hrách. V pˇredchoz´ıch kapitolách jsme definovali mnoˇzinu imputac´ı a jádro hry, tedy podmnoˇzinu imputac´ı, ve které kaˇzdý výsledek je pro hrácˇ e stabiln´ı a t´ım i ekvilibriem. Jádro má ovˇsem potenciálnˇe nekoneˇcnˇe mnoho prvk˚u a pouze ukazuje vyjednávac´ı mnoˇzinu, která je efektivn´ı a individuálnˇe racionáln´ı. Shapley svou statistikou H ukázal nˇeco na zp˚usob maxima na této mnoˇzinˇe.

2.5

Pˇr´ıklady kooperativn´ıch her

Uvedeme si nˇekolik základn´ıch tˇr´ıd kooperativn´ıch her a jejich typické ˇreˇsen´ı. ˇ ef a zamˇestnanci S´ Následuj´ıc´ı pˇr´ıklad ukázˇ e vliv jednoho konkrétn´ıho hrácˇ e (ˇse´ fa) na moˇznosti utvoˇren´ı koalic a tedy proveditelnost kooperativn´ı hry. Pˇredpokládejme situaci sˇe´ fa o a zamˇestanc˚u w1 , w2 , ..., wk . Celkovˇe je tedy ve hˇre N = 1 + k hrácˇ u˚ a mnoˇzina hrácˇ u˚ je Q = {o, w1 , w2 , ..., wk }. Otázkou vyjednáván´ı je projekt, který nutnˇe ztroskotá bez u´ cˇ asti sˇe´ fa, coˇz v ˇreˇci hodnot´ıc´ı funkce znamená v(S) = 0, ∀K ⊂ S, o ∈ /K ˇ ef se bez zamˇestnanc˚u neobejde, proto taktézˇ v({o}) = 0. Kaˇzdý zamˇestnanec má pˇr´ınos daný S´ svým pracovn´ım výkonem ohodnotitelným cˇ´ıslem p, coˇz znaˇc´ı, zˇ e koalice S tvoˇrená sˇe´ fem a |S| − 1 zamˇestnanci má hodnotu v(S) = (|S| − 1) · p, ∀S ⊆ Q, o ∈ S Pochopitelnˇe, podobnˇe jako nezaˇrazený sˇe´ f, tak i nekooperuj´ıc´ı zamˇestnanec wi , i = 1..k má zisk v({wi }) = 0. 14

Ptáme se, jak si maj´ı hrácˇ i rozdˇelit zisk, aby mohla vzniknout koalice s nenulovým ziskem. Zaj´ımá nás pˇredevˇs´ım výplata pro sˇe´ fa. Minimáln´ı funkˇcn´ı koalice je S0 = {o, wi } tvoˇrená sˇe´ fem a nˇejakým jedn´ım zamˇestnancem wi , i = 1..k. Hodnota takové koalice je ovˇsem pouze v(S0 ) = p. Nen´ı d˚uvod, ˇ ef ovˇsem odvod´ı aby se nepˇridali ostatn´ı zamˇestnanci a dosáhlo se zisku velké koalice v(Q) = k · p. S´ Shapleyho hodnotu sebe a ostatn´ıch hrácˇ u˚ , která je: Ho =

(|Q| − 1) · p 2

p Hi = ; ∀i = 1..k 2 Kdyˇz si pro zaj´ımavost dosad´ıme za k = 5, tedy pˇet zamˇestnanc˚u firmy a pˇr´ınos kaˇzdého zamˇestnance do projektu ve výsˇi 10, pak dostáváme pod´ıl na zisku pro sˇe´ fa ve výsˇi ao = 25 a pro kaˇzdého zamˇestnance ai = 5. Ovˇeˇr´ıme, zˇ e Shapleyho vektor je imputac´ı – v naˇsem pˇr´ıpadˇe pracujeme s imputac´ı a = H = (Hi )i∈Q = (25, 5, 5, 5, 5, 5) Aby byl, mus´ı platit efektivita a individuáln´ı racionalita. Pro efektivitu je nutné, aby dˇelen´ı zisku P v sumˇe odpov´ıdalo zisku velké koalice, tedy i∈Q ai = v(Q), coˇz evidentnˇe plat´ı, neboˇt se rozdˇeluje zisk ve výsˇi 50 a ten odpov´ıdá hodnotˇe koalice zadané na poˇca´ tku. Individuáln´ı racionalita jistˇe také plat´ı, protoˇze absolutnˇe kaˇzdý ve hˇre c´ıt´ı, zˇ e v({i}) = 0, tedy plat´ı pro vˇsechny ai ≥ v({i}). Na závˇer tohoto pˇr´ıkladu poznamenejme, zˇ e tato situace je hodnˇe ze zˇ ivota a dokonce je vidˇet, zˇ e zisk sˇe´ fa roste pˇr´ımo s poˇctem jeho zamˇestnanc˚u, kdeˇzto zisk zamˇestnance z˚ustává nezmˇenˇen bez ohledu na to, kolik tato naˇse komunita vytvoˇr´ı celkové hodnoty. S´ılou jedince v takových situac´ıch se budeme jeˇstˇe zabývat v Teorii veˇrejné volby, kde budeme zkoumat tak zvaný power-index hrácˇ e, nebo-li jeho individuáln´ı moc. Stavba mostu Stavba veˇrejného zaˇr´ızen´ı je klasickou ukázkou tak zvaných cost-allocation games nebo také spoˇr´ıc´ıch her. Obecnˇe vˇzdy mus´ı hrácˇ i vytvoˇrit nadkritickou koalici takovou, aby svou silou byla schopna realizovat spoleˇcnou stavbu. Hrácˇ i ovˇsem stále plánuj´ı ve hˇre zisk. ˇ ri firmy zvaˇzuj´ı postavit most. Cena mostu je C = 20 milión˚u. Jednotlivé firmy jsou ochotny Ctyˇ zaplatit maximálnˇe u1 = 10, u2 = 8, u3 = 12, u4 = 16 milión˚u jako pod´ıl do stavby. M˚uzˇ eme si to pˇredstavit jako hraniˇcn´ı hodnotu, kdy je projekt jeˇstˇe pro firmu zaj´ımavý. Rozd´ıl mezi maximáln´ı zaplatitelnou cˇ a´ stkou a fináln´ı platbou tvoˇr´ı zisk hrácˇ e ve hˇre. 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, zˇ e se dohodnou na platbˇe.

15

Pozn.: Podobné u´ lohy ˇreˇs´ı mechanism design v situac´ıch, kdy chtˇej´ı hrácˇ i svoje ocenˇen´ı ui tajit. Je pak tˇreba nastavit pravidla, aby to v rámci racionáln´ıho chován´ı dobrovolnˇe pˇriznali. Tedy u1 = 10, u2 = 8, u3 = 12, u4 = 16 Hra je dána charakteristickou funkc´ı, která vyjadˇruje celkovou u´ sporu koalice: " v(S) = max

# X

ui − C, 0

i∈S

Pokud má koalice nadkritickou hodnotu a je schopna most postavit, pak je jej´ı zisk nezáporný. Pokud nen´ı schopna most postavit, stavba se nekoná a hra konˇc´ı pro hrácˇ e neutrálnˇe. Zˇrejmˇe dále plat´ı v({i}) = 0 pro vˇsechny i ∈ Q. Snadno zjist´ıme, zˇ e hodnota velké koalice je v(Q) = (10 + 8 + 12 + 16) − 20 = 26 Pro hrácˇ e bude nejsp´ısˇ nejlepˇs´ı, pokud se do stavby zapoj´ı vˇsichni. Zbývá jim jenom dohodnout spravedlivé pod´ıly na stavebn´ıch nákladech. Budeme pˇredpokládat, zˇ e hrácˇ i netaj´ı své pravdivé ohodnocen´ı mostu (k tomu se dostaneme v kapitole o Mechanism design, kdy budeme hledat taková pravidla komunikace, aby hrácˇ i nemˇeli snahu zakrývat své ui ). Proto jsou schopni vˇsichni odvodit pˇr´ınos jednotlivce pro velkou koalici, takˇze se opˇet dostáváme k Shapleyho hodnotˇe. Shapleyho hodnota ve hˇre je H = (5.667, 4.333, 6.667, 9.333). Shapleyho hodnota hrácˇ e i vyjadˇruje u´ sporu, kterou hrácˇ pˇrinese celku, pokud se do realizaˇcn´ı koalice zapoj´ı. Pokud tedy hrácˇ i maj´ı právo zˇ a´ dat výplatu Hi , pak do stavby mus´ı vloˇzit pi = ui − Hi 11 16 20 , , , . Celkem je to 13 + 11 + 16 + 20 = 20, tedy stavebn´ı náklady jsou pokryty, tedy p = 13 3 3 3 3 3 3 3 3 most se postav´ı a kaˇzdý hrácˇ i zaznamená uˇzitek ve výsˇi ui − pi . Pokud ovˇsem hru posuneme o u´ roveˇn výsˇe, m˚uzˇ eme pojmout prezentované ohodnocen´ı stavby ui hrácˇ i jako jejich strategie v rozhodován´ı. Pokud by totiˇz hrácˇ 1 nepravdivˇe prezentoval nam´ısto ohodnocen´ı 10 hodnotu 5, dával by t´ım najevo menˇs´ı zájem o stavbu a jeho H1 by bylo niˇzsˇ´ı, ˇreknˇeme 3.57. Zaplatil by pak pod´ıl na stavbˇe p1 = 5 − 3.57 = 1.43, coˇz by u nˇej vedlo k pravdivému uˇzitku 10 − 1.43, kter7 je rozhodnˇe vyˇssˇ´ı neˇz pˇri platbˇe 10 − 5.667. Pokud bychom pˇredpokládali takové chován´ı, stavba by se nejsp´ısˇ nerealizovala. Studium tˇechto problém˚u bude následovat v kapitole o Mechanism design. C´ılem této u´ vahy bylo prezentovat kˇrehkost kooperativity v reálných situac´ıch.

16

2.6

Nukleolus

Zavedli jsme pojem imputace a pojem jádra hry, které modeluje pro hrácˇ e akceptovatelné výsledky hry. V této kapitole budeme dál hledat spravedlivý výplatn´ı vektor pro hrácˇ e hry. ˇ ıslo Definice 10. Nechtˇ v ∈ GQ , a je daná imputace a S ⊆ Q je koalice. C´ e(S, a) = v(S) −

X

ai

i∈S

se nazývá exces koalice S vzhledem k imputaci a. Exces koalice S vzhledem k imputaci vyjadˇruje kolik mus´ı koalice zanechat nerozdˇeleno pˇri P imputaci a. Pˇripomeˇnme, zˇ e imputace a mus´ı být efektivn´ı, coˇz znamená, zˇ e i∈Q ai = v(Q). P Vˇsimnˇeme si tedy, zˇ e to nutnˇe neznamená i∈S ai = v(S). 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. Berme to jako formu statistiky, která vyˇc´ısluje ztrátu pˇri hran´ı imputace a pro veˇskeré myslitelné koalice {1}, {2}, ..., {N }, {1, 2}, ..., {1, N }, ..., Q. ˇ Seˇradme prvky e(a) sestupnˇe podle velikosti a oznaˇcme tuto posloupnost symbolem f (a). Jeli tedy e(a) posloupnost´ı cˇ´ısel, kde kaˇzdý prvek ohodnocuje m´ıru ztráty nˇejaké z koalic a |e(a)| = 2N − 1, pak stˇejnˇe tak f (a) je posloupnost´ı cˇ´ısel stejného charakteru, ovˇsem seˇrazených sestupnˇe. Nemus´ıme tud´ızˇ zkoumat, jaká pozice v posloupnosti pˇr´ısluˇs´ı jaké koalici a známe prostˇe jenom m´ıru protest˚u vˇsech hrácˇ u˚ v˚ucˇ i dané imputaci a. Nyn´ı budeme hledat zp˚usob, jak porovnávat dvˇe imputace P z hlediska jejich f (·). Vyjádˇrit nelibost v˚ucˇ i imputaci a pouhým jedn´ım cˇ´ıslem j=1..2N −1 e(a) by asi nestaˇcilo. Kaˇzdé imputaci a ∈ X(v) ve hˇre v ∈ GQ se tak pˇriˇrad´ı statistika f (a). Pracujeme s mnoˇzinou F (v) = {f (a)|a ∈ X(v)} Definujme na této mnoˇzinˇe F (v) lexikografické uspoˇra´ dán´ı ≤(lex) rekurzivn´ım zápisem takto (kde funkce head(p) vrac´ı prvn´ı prvek posloupnosti a funkce tail(p) vrac´ı posloupnost bez prvn´ıho prvku):

≤(lex) (p1 , p2 ) =

   true  

p1 = p2 = ()

≤(lex) (tail(p1 ), tail(p2 )) head(p1 ) ≤ head(p2 )    f alse otherwise

ˇ Rekneme, zˇ e imputace b je pˇrijatelnˇejˇs´ı (vzbuzuje ménˇe námitek) neˇz imputace a, pokud f (b) ≤(lex) f (a). Jinak ˇreˇceno, po celé délce posloupnosti b plat´ı, zˇ e prvek na dané pozici je menˇs´ı nebo roven prvku na dané pozici v posloupnosti a. Znamená to, zˇ e imputace b ve vˇsech myslitelných koalic´ıch vede k lepˇs´ımu rozloˇzen´ı zisku.

17

Definice 11. Mˇejme hru v ∈ GQ . Nucleolem hry v je taková imputace b ∈ X(v), pro kterou plat´ı: f (b) ≤(lex) f (a) pro vˇsechny imputace a ∈ X(v). Vid´ıme, zˇ e nukleolus je forma globáln´ıho optima ve hˇre (stabiln´ı bod).

Demonstraˇcn´ı pˇr´ıklad Mˇejme hru s char. funkc´ı: v(Q) = 1, v({1}) = 21 , v({2}) = 0. Prvn´ı hrácˇ má tedy garantovaný výsledek ve výsˇi 12 . Pokud se spoj´ı do koalice s druhým hrácˇ em, má druhý hrácˇ nadˇeji na nenulový

výsledek a prvn´ı na výsledek v intervalu 12 , 1 . Nejdˇr´ıve si uvˇedom´ıme, zˇ e mnoˇzina imputac´ı ve hˇre je nekoneˇcná a je dána lineárn´ımi nerovnicemi: 1 a1 ≥ , a2 ≥ 0 2 které vyjadˇruj´ı individuáln´ı racionalitu a rovnic´ı vyjadˇruj´ıc´ı efektivitu výsledku: a1 + a2 = 1 Vyjednávac´ı prostor pro rozdˇelen´ı zisku je tedy analyticky urˇcen jako: a1 ∈

1 , 1 , a2 = 1 − a1 2

Pokud bychom k situaci pˇristoupili jako k nekooperativn´ı hˇre, pak se nab´ız´ı podobnost s ultimatum game, kde by podle Nashe mˇel druhý hrácˇ pˇristoupit na kterékoliv rozdˇelen´ı, které by mu pˇrineslo nenulový výsledek, to znamená napˇr´ıklad na imputaci (0.99, 0.01). V kooperativn´ıch hrách si vˇsak jiˇz dokázˇ eme pˇredstavit, zˇ e prvn´ı hrácˇ má také zájem na zisku v pásmu nad jeho disagreement value. Proto pˇredpokládáme snahu prvn´ıho hrácˇ e nab´ıdnout druhému rozumné rozdˇelen´ı zisku takové, aby doˇslo k ustanoven´ı velké koalice. Jádro hry pouze potvrzuje, zˇ e vˇsechny imputace hry jsou pro hrácˇ e akceptovatelné.

1 a1 ≥ , a2 ≥ 0, a1 + a2 = 1 2

a1 ∈

1 , 1 , a2 = 1 − a1 2

Vidˇeno optikou Shapleyho hodnoty zjiˇsˇtujeme, zˇ e prvn´ı hrácˇ zvyˇsuje hodnotu velké koalice z nuly na jedna a sám pro sebe má hodnotu jedné poloviny. Proto je 1 H1 = 2

1 +1 2

18

=

3 4

Druhý hrácˇ je pˇrinosem pro velkou koalici pouze do hodnoty jedné poloviny, neboˇt bez jeho u´ cˇ asti je v({1}) = 21 . 1 H2 = 2

1 1 0+ = 2 4

Proto se hrácˇ i mohou dohodnout na rozdˇelen´ı podle Shapleyho hodnoty a tedy ∗

a =

3 1 , 4 4

Nen´ı to aˇz tak pˇrekvapuj´ıc´ı, neboˇt pˇredpokládáme oba hrácˇ e symetrické z hlediska uˇzitku ve hˇre

a rozdˇelujeme z kolácˇ e 0, 21 . Pouˇzijeme nyn´ı solution concept definovaný jako nukleolus. Pˇripom´ınáme, zˇ e exces koalice S vzhledem k imputaci a je: X e(S, a) = v(S) − ai i∈S

Pak, vyjádˇreno analyticky pro imputaci a: Exces pro jednoprvkovou koalici hrácˇ e 1 je e({1}, a) = 12 − a1 , tedy jeho nejhorˇs´ı ztráta m˚uzˇ e být nula. Pro hrácˇ e dva je cokoliv nenulového pˇr´ınosem (kladný exces znaˇc´ı ztrátu): e({2}, a) = 0 − a2 . Velká koalice nemá výhrady k zˇ a´ dnému rozdˇelen´ı, naboˇt e({1, 2}, a) = 1 − a1 − a2 = 1 − a1 − (1 − a1 ) = 0. Exces tedy zap´ısˇeme analyticky jako (a dále pak s pˇredpokladem a1 = 1 − a2 ): e(a) =

1 1 − a1 , −a2 , 0 = a2 − , −a2 , 0 2 2

Excesy budeme zkoumat pro prahovou hodnotu a2 = 14 , kde oˇcekáváme zaj´ımavý vývoj: 1 1 f (a) = (0, −a2 , a2 − ) ⇔ 0 ≤ a2 ≤ 2 4 1 1 f (a) = (0, a2 − , −a2 ) ⇔ ≤ a2 ≤ 1 2 4 Pokud dáme a2 = 0, pak je exces 0, 0, − 12 . Pokud dáme a2 = 14 , pak je exces 0, − 41 , − 14 . Vid´ıme, zˇ e 0, − 41 , − 14 ≤(lex) 0, 0, − 21 . Co dát a2 = 21 ? Nejpˇrijatelnˇejˇs´ı exces je pˇri a2 = 14 ⇒ a1 = 34 .

19

Doprovodné texty ke kurzu Teorie her

Recommend Documents