9
KOOPERATIVNI´ HRY ˇU ˚ ´C N HRA
JJ x II 335
V prˇedchozı´ kapitole mohli hra´cˇi koordinovat sve´ strategie, nemohli vsˇak sdı´let zisky. Ve hra´ch studovany´ch v te´to kapitole budou hra´cˇi moci spolupracovat zcela, vcˇetneˇ prˇ´ıpadne´ho prˇerozdeˇlenı´ vy´hry. Budeme prˇedpokla´dat, zˇe dohody, ktere´ uzavrˇou, jsou naprosto za´vazne´.
JJ x II 336
Definice 1. Uvazˇujme hru N hra´cˇu˚; mnozˇinu vsˇech hra´cˇu˚ oznacˇme symbolem Q. Koalicı´ se rozumı´ skupina hra´cˇu˚ spolupracujı´cı´ch prˇi volbeˇ strategiı´, prˇ´ıpadneˇ prˇi prˇerozdeˇlova´nı´ vy´hry. Koalicˇnı´ strukturou se nazy´va´ mnozˇina vsˇech koalic, ktere´ se v dane´ situaci z uvazˇovany´ch hra´cˇu˚ vytvorˇ´ı. Koalice budeme znacˇit pı´smeny K, L, Q, apod., prˇ´ıpadneˇ je uda´me prˇ´ımo jako mnozˇinu obsahujı´cı´ cˇleny te´to koalice, naprˇ. {1}, {2, 3, 5} aj. Protikoalicı´ ke koalici K ⊆ Q se rozumı´ mnozˇina hra´cˇu˚ K = Q \ K = {i ∈ Q; i 6∈ K}. Mnozˇina vsˇech hra´cˇu˚ Q se nazy´va´ velka´ koalice, jejı´ protikoalice, tj. pra´zdna´ mnozˇina, se nazy´va´ pra´zdna´ koalice. Obecneˇ se ve hrˇe mu˚zˇe vytvorˇit 2N koalic – pra´veˇ tolik je vsˇech podmnozˇin mnozˇiny Q.
JJ x II 337
Definice 2. Hra ve tvaru charakteristicke´ funkce sesta´va´ z mnozˇiny hra´cˇu˚ Q = {1, 2, . . . , N } a rea´lne´ funkce v definovane´ na mnozˇineˇ vsˇech koalic, pro kterou je v(∅) = 0 a pro kazˇde´ dveˇ disjunktnı´ koalice K, L platı´ superaditivita: v(K ∪ L) ≥ v(K) + v(L). Pro jednoduchost budeme symbolem v znacˇit i prˇ´ıslusˇnou hru ve tvaru charakteristicke´ funkce. Hodnoty charakteristicke´ funkce uda´vajı´ sı´lu jednotlivy´ch koalic.
JJ x II 338
Definice 3. Hra ve tvaru charakteristicke´ funkce se nazy´va´ nepodstatna´, jestlizˇe platı´: N X v(Q) = v({i}) i=1
Hra, ktera´ nenı´ nepodstatna´, se nazy´va´ podstatna´. Veˇta 1. Necht’ K je libovolna´ koalice hra´cˇu˚ v nepodstatne´ hrˇe. X Potom v(K) = v({i}) i∈K
Du˚kaz. Pro kazˇdou koalici K platı´ (ze superaditivity): X v(K) ≥ v({i}) i∈K
Kdyby pro neˇjakou koalici K platila ostra´ nerovnost, pak by bylo X v({i}) v(Q) ≥ v(K) + v(K) > i∈Q
JJ x II 339
Imputace Definice 4. Necht’ v je hra ve tvaru charakteristicke´ funkce s mnozˇinou hra´cˇu˚ Q = {1, 2, . . . , N }. N -tice a rea´lny´ch cˇı´sel se nazy´va´ imputace, jsou-li splneˇny na´sledujı´cı´ podmı´nky: • Individua´lnı´ racionalita: pro kazˇde´ho hra´cˇe i je ai ≥ v({i}).
(9.1)
• Kolektivnı´ racionalita: platı´ N X
ai = v(Q).
(9.2)
i=1
JJ x II 340
Motivace – individua´lnı´ racionalita:
∀i : ai ≥ v({i})
Kdyby pro neˇjake´ i bylo ai < v({i}), pak by se nikdy nevytvorˇila koalice, ktera´ by hra´cˇi prˇinesla pouze ai – pro hra´cˇe i by bylo vy´hodneˇjsˇ´ı zu˚stat sa´m za sebe a takove´ koalice se nezu´cˇastnit.
JJ x II 341
PN
Kolektivnı´ racionalita:
i=1
ai = v(Q)
Urcˇiteˇ platı´: N X
ai ≥ v(Q).
(9.3)
i=1
V opacˇne´m prˇ´ıpadeˇ by totizˇ bylo β = v(Q) −
N X
ai > 0.
i=1
Pro hra´cˇe by tak bylo vy´hodneˇjsˇ´ı vytvorˇit velkou koalici a rozdeˇlit si celkovy´ zisk ve vy´sˇi v(Q) tak, aby kazˇdy´ z nich zı´skal vı´ce – naprˇ´ıklad: a0i = ai + β/N. Na druhou stranu musı´ by´t take´ N X
ai ≤ v(Q),
(9.4)
i=1
protozˇe v(Q) prˇedstavuje maximum, co hra´cˇi mohou ve hrˇe zı´skat (plyne ze superaditivity).
JJ x II 342
Veˇta 2. Necht’ v je hra ve tvaru charakteristicke´ funkce. Je-li v nepodstatna´, pak ma´ pra´veˇ jednu imputaci, a to a = (v({1}), v({2}), . . . , v({N })). Je-li v podstatna´, pak ma´ nekonecˇneˇ mnoho imputacı´. Du˚kaz. Pro nepodstatnou hru v : Kdyby bylo pro neˇjake´ j aj > v({j}), pak N X i=1
ai >
N X
v({i}) = v(Q),
i=1
cozˇ by odporovalo podmı´nce kolektivnı´ racionality.
JJ x II 343
Pro podstatnou hru v : Uvazˇujme β = v(Q) −
N X
v({i}) > 0.
i=1
Pro jakoukoli N -tici α neza´porny´ch cˇı´sel, jejichzˇ soucˇet je β, definuje vztah ai = v({i}) + αi imputaci. Protozˇe existuje nekonecˇneˇ mnoho takovy´ch N -tic α, existuje i nekonecˇneˇ mnoho imputacı´.
JJ x II 344
Formalizace mysˇlenky, zˇe dana´ koalici preferuje jednu imputaci prˇed jinou: Definice 5. Necht’ v je hra ve tvaru charakteristicke´ funkce, ˇ ekneme, zˇe a dominuje K je koalice, a, b jsou imputace. R b pro koalici K, jestlizˇe platı´: • ai > bi pro vsˇechna i ∈ K, •
X
ai ≤ v(K).
i∈K
Dominanci budeme znacˇit symbolem a K b. Druha´ podmı´nka rˇ´ıka´, zˇe rozdeˇlenı´ a je dosazˇitelne´, tj. hra´cˇi v koalici K mohou zı´skat dostatecˇneˇ vysokou hodnotu na to, aby kazˇde´mu mohlo by´t vyplaceno prˇ´ıslusˇne´ ai .
JJ x II 345
Ja´dro hry Intuitivneˇ je zrˇejme´, zˇe bude-li neˇjaka´ imputace dominova´na pro neˇjakou koalici jinou imputacı´, budou mı´t hra´cˇi te´to koalice snahu zrusˇit pu˚vodnı´ koalici a ustavit tuto vy´hodneˇjsˇ´ı. Definice 6. Necht’ v je hra ve tvaru charakteristicke´ funkce. Ja´dro hry je tvorˇeno vsˇemi imputacemi, ktere´ nejsou dominova´ny zˇa´dnou jinou imputacı´ pro zˇa´dnou jinou koalici. Je-li tedy imputace a v ja´dru dane´ hry, nema´ zˇa´dna´ skupina hra´cˇu˚ du˚vod vytvorˇit jinou koalici a nahradit a jinou imputacı´. K usnadneˇnı´ rozhodnutı´, zda jista´ imputace lezˇ´ı v ja´dru hry cˇi nikoli, slouzˇ´ı na´sledujı´cı´ veˇta:
JJ x II 346
Veˇta 3. Necht’ v je hra ve tvaru charakteristicke´ funkce s N hra´cˇi a necht’ a je imputace. Potom a lezˇ´ı v ja´dru hry v pra´veˇ tehdy, kdyzˇ X ai ≥ v(K) (9.5) i∈K
pro kazˇdou koalici K. Du˚kaz. ⇐ Prˇedpokla´dejme, zˇe pro kazˇdou koalici platı´ vztah (9.5). Jestlizˇe neˇjaka´ jina´ imputace b dominuje a pro neˇjakou koalici K, pak X X bi > ai ≥ v(K), i∈K
i∈K
cozˇ odporuje podmı´nce dosazˇitelnosti z definice dominance. Proto a musı´ by´t v ja´dru.
JJ x II 347
⇒ Prˇedpokla´dejme naopak, zˇe a je v ja´dru a prˇedpokla´dejme, zˇe K je koalice, pro kterou X ai < v(K). i∈K
Chceme dojı´t ke sporu. Nejprve si uveˇdomme, zˇe K 6= Q, protozˇe by neplatila podmı´nka kolektivnı´ racionality. Da´le lze uka´zat, zˇe existuje hra´cˇ j ∈ K, pro neˇhozˇ aj > v({j}). Kdyby tomu tak nebylo, pak by vzhledem k superaditiviteˇ platilo: N X i=1
ai =
X i∈K
ai +
X i∈K
ai < v(K) +
X
v({i}) ≤ v(Q),
i∈K
cozˇ opeˇt odporuje podmı´nce kolektivnı´ racionality. Mu˚zˇeme tedy zvolit takove´ j ∈ K, zˇe existuje cˇı´slo α, pro ktere´ platı´: X 0 < α ≤ aj − v({j}) a α ≤ v(K) − ai . i∈K
Znacˇı´-li k pocˇet hra´cˇu˚ v koalici K, mu˚zˇeme definovat novou imputaci b dominujı´cı´ a vztahem: bi = ai + α/k pro i ∈ K, bj = aj − α, b i = ai pro vsˇechna ostatnı´ i. JJ x II 348
Takova´ imputace b dominuje imputaci a pro K, cozˇ je spor s prˇedpokladem, zˇe a lezˇ´ı v ja´dru. Tvrzenı´ 4. Necht’ v je hra ve tvaru charakteristicke´ funkce s N hra´cˇi a necht’ a je N -tice cˇı´sel. Potom a je imputace v ja´dru, pra´veˇ kdyzˇ platı´: •
N X
ai = v(Q),
i=1
•
X
ai ≥ v(K) pro kazˇdou koalici K.
i∈K
Du˚kaz. Kazˇda´ imputace z ja´dra zrˇejmeˇ splnˇuje obeˇ podmı´nky. Splnˇuje-li naopak N -tice a tyto podmı´nky, pak uzˇitı´m druhe´ podmı´nky na jednoprvkove´ koalice zı´ska´me individua´lnı´ racionalitu, prvnı´ prˇedstavuje prˇ´ımo kolektivnı´ racionalitu; a je proto imputacı´. Z prˇedchozı´ veˇty pak plyne, zˇe a lezˇ´ı v ja´dru.
JJ x II 349
☛ Prˇ´ıklad 1. Uvazˇujme hru trˇ´ı hra´cˇu˚ popsanou tabulkou: Trojice strategiı´ (1,1,1)
Vy´platnı´ vektory (-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)
Mnozˇina hra´cˇu˚ je Q = {1, 2, 3}, vsˇechny mozˇne´ koalice jsou ∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} = Q. Uvazˇujme koalici K = {1, 3}. Protikoalice je K = {2}. Koalice K ma´ cˇtyrˇi spolecˇne´ strategie: (1, 1), (1, 2), (2, 1), (2, 2). Protikoalice ma´ dveˇ ryzı´ strategie: 1, 2. Zajı´ma´-li na´s, co je koalice K schopna pro sebe zajistit, uvazˇujeme dvojmaticovou hru: JJ x II 350
Protikoalice K
Koalice K
Strategie
1
2
(1, 1) (1, 2) (2, 1)
(0, 1) (0, 1) (2, −1)
(2, −1) (−1, 2) (1, 0)
(2, 2)
(1, 0)
(−1, 2)
Maximinnı´ hodnoty vy´platnı´ch funkcı´ jsou 4/3 a −1/3, charakteristickou funkci proto budeme uvazˇovat takto: v({1, 3}) = 4/3,
v({2}) = −1/3.
Podobny´m zpu˚sobem obdrzˇ´ıme: v({1, 2}) = 1,
v({3}) = 0 v({2, 3}) = 3/4, v(Q) = 1,
v({1}) = 1/4,
v(∅) = 0.
Oveˇrˇte, zˇe takto definovana´ funkce v je charakteristickou funkcı´. Imputace: a1 + a2 + a3 = 1,
a1 ≥ 1/4,
a2 ≥ −1/3,
a3 ≥ 0. JJ x II 351
Naprˇ´ıklad: (1/3, 1/3, 1/3), (1/4, 3/8, 3/8), (1, 0, 0). Ja´dro: a1 + a2 + a3 = 1 a1 ≥ 1/4 a2 ≥ −1/3 a3 ≥ 0 a1 + a2 ≥ 1 a1 + a3 ≥ 4/3 a2 + a3 ≥ 3/4 Z 1., 4. a 5. vztahu plyne: a3 = 0, a1 + a2 = 1. Prˇitom ale a1 ≥ 4/3, a2 ≥ 3/4. Ja´dro hry je v tomto prˇ´ıpadeˇ pra´zdne´.
JJ x II 352
☛ Prˇ´ıklad 2. Uvazˇujme hru trˇ´ı hra´cˇu˚ s charakteristickou funkcı´: v({1}) v({2}) v({3}) v({1, 2}) v({1, 3}) v({2, 3}) v({1, 2, 3})
= = = = = = =
−1/2 0 −1/2 1/4 0 1/2 1
a1 + a2 + a3 a1 a2 a3 a1 + a2 a1 + a3 a2 + a3
= ≥ ≥ ≥ ≥ ≥ ≥
1 −1/2 0 −1/2 1/4 0 1/2
Ja´dro:
Tato soustava ma´ nekonecˇneˇ mnoho rˇesˇenı´; prvkem ja´dra je naprˇ´ıklad trojice (1/3, 1/3, 1/3).
JJ x II 353
☛ Prˇ´ıklad 3. Hra s ojety´m automobilem. David ma´ stary´ automobil, ktery´ nepuzˇ´ıva´ a je pro neˇj bezcenny´, pokud jej nebude moci prodat. O koupi se zajı´majı´ dva lide´, Marie a Frantisˇek. Marie automobil cenı´ na 50 000 Kcˇ, Frantisˇek na 70 000 Kcˇ. Hra spocˇı´va´ v tom, zˇe za´jemci navrhnou cenu Davidovi a ten bud’ prˇijme jednu z nabı´dek, nebo obeˇ odmı´tne. Ja´dro: (aD , aM , aF );
50 000 ≤ aD ≤ 70 000,
aF = 70 000 − aD ,
aM = 0.
JJ x II 354
9.1. 9.1.1.
ˇ ESˇENI´ DALSˇ´I POJMY R Shapleyho hodnota
Shapleyho hodnota bere v u´vahu hra´cˇu˚v prˇ´ıspeˇvek k u´speˇchu koalice, do nı´zˇ na´lezˇ´ı. Necht’ v je hra ve tvaru charakteristicke´ funkce s N hra´cˇi, K je koalice sesta´vajı´cı´ z k cˇlenu˚, do nı´zˇ na´lezˇ´ı hra´cˇ i. Pak cˇı´slo δ(i, K) = v(K) − v(K \ {i}) je mı´rou hodnoty hra´cˇe i, kterou prˇispeˇje koalici K, kdyzˇ se k nı´ prˇipojı´. Koalice K \ {i} ma´ k − 1 cˇlenu˚ a lze ji proto vytvorˇit
N −1 k−1
=
(N − 1)! (k − 1)!(N − k)!
zpu˚soby (hra´cˇ i je mimo vy´beˇr, do koalice vstupuje jako poslednı´). Strˇednı´ hodnota prˇ´ınosu hra´cˇe i ke vsˇem k-cˇlenny´m koalicı´m je
JJ x II 355
hi (k) =
X K⊂Q, k=|K| i∈K
v(K) − v(K \ {i}) = N −1 k−1 (9.6)
(k − 1)!(N − k)! (v(K) − v(K \ {i})) (N − 1)!
X
=
K⊂Q, k=|K| i∈K
Strˇednı´ hodnota prˇ´ınosu hra´cˇe i k u´hrnu vsˇech jednocˇlenny´ch, dvoucˇlenny´ch, . . . , N -cˇlenny´ch koalic je da´na vztahem:
Hi =
N X hi (k) k=1
N
=
X K⊂Q, i∈K
(N − |K|)!(|K| − 1)! (v(K) − v(K \ {i})) N! (9.7)
JJ x II 356
Definice 7. Shapleyho vektor hry N hra´cˇu˚ ve tvaru charakteristicke´ funkce je definova´n jako vektor H = (H1 , H2 , . . . , HN ),
(9.8)
jehozˇ i-ta´ slozˇka Hi je urcˇena vztahem (9.7). Slozˇka Hi se nazy´va´ Shapleyho hodnota pro hra´cˇe i.
Ihned z definice je patrne´, zˇe Shapleyho vektor vzˇdy existuje a pro danou hru je urcˇen jednoznacˇneˇ. Veˇta 4. Necht’ v je hra ve tvaru charakteristicke´ funkce. Potom Shapleyho vektor je imputacı´.
JJ x II 357
Veˇta 5. Necht’ v je hra ve tvaru charakteristicke´ funkce. Potom Shapleyho vektor je imputacı´. Du˚kaz: • Individua´lnı´ racionalita:
∀i ∈ Q : Hi ≥ v({i}):
Superaditivita ⇒ δ(i, K) = v(K) − v(K \ {i}) ≥ v({i}), proto
Hi =
X K⊂Q, i∈K
≥
X K⊂Q, i∈K
(N − |K|)!(|K| − 1)! (v(K) − v(K \ {i})) ≥ N! (N − |K|)!(|K| − 1)! N!
! v({i}) = v({i})
[soucˇet pravdeˇpodobnostı´ vsˇech mozˇny´ch usporˇa´da´nı´ hra´cˇu˚]
JJ x II 358
• Kolektivnı´ racionalita:
N X
Hi = v(Q)
i=1 N X
Hi =
i=1
N X
X
i=1 K⊂Q, i∈K
(N − |K|)!(|K| − 1)! (v(K) − v(K \ {i})) N!
Uvazˇujme libovolnou, ale pevneˇ zvolenou podmnozˇinu ∅ = 6 T (Q v(T ) se v soucˇtu objevı´ ve dvou typech cˇlenu˚: (N − |T |)!(|T | − 1)! N! [teˇchto cˇlenu˚ je |T | (pro kazˇde´ i ∈ T jeden)]
• s kladny´m koeficientem pro T = K . . .
• se za´porny´m koeficientem pro T = K \ {i} . . . (N − |T | − 1)!|T |! N! [teˇchto cˇlenu˚ je N − |T |] Celkem je u v(T ) koeficient |T | ·
(N − |T |)!(|T | − 1)! (N − |T | − 1)!|T |! − (N − |T |) · = N! N!
JJ x II 359
Celkem je u v(T ) koeficient
|T | ·
(N − |T |)!(|T | − 1)! (N − |T | − 1)!|T |! − (N − |T |) · = N! N! =
(N − |T |)!|T |! (N − |T |)!|T |! − =0 N! N!
Nenulove´ koeficienty proto zu˚sta´vajı´ jen u v(∅), v(Q). Protozˇe v(∅) = 0, dosta´va´me N X i=1
Hi = N ·
(N − N )!(N − 1)! · v(Q) = v(Q) N!
JJ x II 360
☛ Prˇ´ıklad 4. Uvazˇujme hru s charakteristickou funkcı´ v(Q) = 200, v({1}) = 100, v({1, 2}) = 150,
v(∅) = 0,
v({2}) = 10
v({1, 3}) = 110,
v({3}) = 0, v({2, 3}) = 20.
V tomto prˇ´ıpadeˇ bude h1 (1) = 100, h1 (2) =
h2 (1) = 10,
140 + 110 , 2
h1 (3) = 180,
h2 (2) =
h2 (3) = 90,
h3 (1) = 0, 50 + 20 , 2
h3 (2) =
10 + 10 , 2
h3 (3) = 50,
JJ x II 361
Celkem tedy: H1 =
100 + 125 + 180 = 135, 3
H2 =
10 + 35 + 90 = 45, 3
H3 =
0 + 10 + 50 = 20, 3
Shapleyho vektor: H = (135, 45, 20) .
JJ x II 362
☛ Prˇ´ıklad 5. Pro hru z prˇ´ıkladu 3 jsou Shapleyho hodnoty na´sledujı´cı´: HD = 43 333, 3;
HM = 8 333, 3; HF
18 333, 3;
tj. H = 43 333, 3; 8 333, 3; 18 333, 3 .
JJ x II 363
☛ Prˇ´ıklad 6. Hra Kocourkov. Obecnı´ spra´va v Kocourkoveˇ je tvorˇena meˇstskou radou a starostou. Rada je tvorˇena sˇesti radnı´mi a prˇedsedou. Vyhla´sˇka mu˚zˇe vejı´t v platnost dveˇma zpu˚soby: • Veˇtsˇina rady (prˇicˇemzˇ prˇedseda volı´ jen v prˇ´ıpadeˇ remı´zy mezi radnı´mi) ji schva´lı´ a starosta ji podepı´sˇe. • Rada ji schva´lı´, starosta ji vetuje, ale alesponˇ sˇest ze sedmi cˇlenu˚ rady pak veto prˇehlasuje (v tomto prˇ´ıpadeˇ prˇedseda vzˇdy volı´). Definujme v(S) = 1 pro vı´teˇznou koalici, v(S) = 0 pro porazˇenou koalici. Rozdeˇlenı´ (aS , aP , a1 , . . . , a6 ), kde S znacˇı´ starostu, P prˇedsedu a 1, 2, . . . , 6 radnı´, je imputacı´, pra´veˇ kdyzˇ aS , aP , a1 , . . . , a6 ≥ 0
a
aS + aP + a1 + · · · + a6 = 1.
Snadno lze odvodit, zˇe ja´dro te´to hry je pra´zdne´: Vzhledem k tomu, zˇe jaka´koli asponˇ sˇestiprvkova´ koalice zvı´teˇzı´, je aP + a1 + · · · + a6 ≥ 1 JJ x II 364
a stejna´ nerovnost platı´ i tehdy, kdyzˇ libovolny´ ze scˇı´tancu˚ vypustı´me. Protozˇe vsˇichni scˇı´tanci jsou neza´pornı´ a soucˇet vsˇech osmi je roven jedne´, musı´ by´t vsˇechny rovny nule, cozˇ je spor.
JJ x II 365
Pokusme se nynı´ najı´t Shapleyho vektor pro tuto hru. Zacˇneˇme s hodnotou starosty S. Nenulove´ cˇleny v soucˇtu (9.7) jsou ty, pro neˇzˇ je K \ {S} porazˇena´ koalice, ale K je vı´teˇzna´ (odstranı´-li starostu, radnı´ vyhla´sˇku schva´lı´, ale neprˇehlasujı´ jeho veto). V tomto prˇ´ıpadeˇ existujı´ cˇtyrˇi druhy vı´teˇzny´ch koalic: 1. K obsahuje starostu, trˇi radnı´ a prˇedsedu. Takovy´chto koalic je 6 = 20. 3 Protozˇe |K| = k = 5, je prˇ´ıspeˇvek teˇchto mnozˇin k celkove´ hodnoteˇ HS roven 20 ·
(N − k)!(k − 1)! (8 − 5)!(5 − 1)! 1 1 = 20 · = 20 · = . N! 8! 280 14
2. K obsahuje starostu a cˇtyrˇi radnı´. Takovy´chto koalic je 15 a prˇ´ıspeˇvek teˇchto mnozˇin k celkove´ hodnoteˇ HS je roven 15 ·
(8 − 5)!(5 − 1)! 3 = . 8! 56
3. K obsahuje starostu, cˇtyrˇi radnı´ a prˇedsedu. Takovy´chto koalic je 15 a prˇ´ıspeˇvek teˇchto mnozˇin k celkove´ hodnoteˇ JJ x II 366
HS je roven 15 ·
(8 − 6)!(6 − 1)! 5 = . 8! 56
4. K obsahuje starostu a peˇt radnı´ch. Takovy´chto koalic je 6 a prˇ´ıspeˇvek teˇchto mnozˇin k celkove´ hodnoteˇ HS je roven 6·
1 (8 − 6)!(6 − 1)! = . 8! 28
Celkem je tedy HS =
1 3 5 1 1 + + + = . 14 56 56 28 4
Da´le se podı´vejme na prˇedsedu P. V tomto prˇ´ıpadeˇ existujı´ jen dva druhy vı´teˇzny´ch koalic: 1. K obsahuje prˇedsedu, trˇi radnı´ a starostu (volba radnı´ch skoncˇı´ remı´zou, prˇedseda volı´, starosta podepı´sˇe. 2. K obsahuje prˇedsedu a peˇt radnı´ch (na´vrh bude vetova´n, ale s prˇedsedovy´m hlasem bude prˇehlasova´nj). Koalic prvnı´ho typu je celkem 20, druhe´ho typu 6. Proto HP = 20 ·
(8 − 5)!(5 − 1)! (8 − 6)!(6 − 1)! 3 +6· = . 8! 8! 28 JJ x II 367
Soucˇet vsˇech H je 1, hodnoty pro jednotlive´ radnı´ jsou zrˇejmeˇ stejne´, proto pro kazˇde´ i = 1, 2, . . . , 6 bude 1 1 3 3 Hi = (1 − − ) = . 6 4 28 28 Celkem:
H=
1 3 3 3 , , ,..., 4 28 28 28
Je videˇt, zˇe starosta ma´ mnohem veˇtsˇ´ı moc nezˇ prˇedseda cˇi obycˇejny´ radnı´. A ukazuje se, zˇe prˇedseda ma´ prˇesneˇ stejnou moc jako radnı´.
JJ x II 368
Lloyd Shapley (*1923), Martin Shubik (*1926) A Method for Evaluating the Distribution of Power in a Committee System, 1954 Model volebnı´ situace: kooperativnı´ hra ve tvaru charakteristicke´ funkce, v nı´zˇ je koalici, ktera´ mu˚zˇe prosadit na´vrh, prˇirˇazena hodnota 1, a koalici, ktera´ jej prosadit nemu˚zˇe, hodnota 0. Jak meˇrˇit sı´lu jednotlivy´ch volicˇu˚ ve volebnı´ hrˇe? Shapley, Shubik navrhli vyuzˇitı´ Shapleyho hodnoty: Hi =
X K⊂Q, i∈K
(N − |K|)!(|K| − 1)! (v(K) − v(K \ {i})) N!
JJ x II 369
Lloyd Shapley (*1923), Martin Shubik (*1926) A Method for Evaluating the Distribution of Power in a Committee System, 1954 Uvazˇujme skupinu jedincu˚, kterˇ´ı vsˇichni chteˇjı´ hlasovat pro neˇjaky´ na´vrh. Volı´ postupneˇ. Jakmile pro na´vrh hlasuje jizˇ dostatek jedincu˚, je povazˇova´n za schva´leny´ a poslednı´mu hlasujı´cı´mu se dostane pochvaly za to, zˇe umozˇnil za´konu projı´t. Zvolme na´hodne´ porˇadı´ hlasova´nı´ cˇlenu˚. Pak mu˚zˇeme spocˇı´tat, jak cˇasto je urcˇity´ jedinec „pivotem“, klı´cˇovy´m volicˇem – toto cˇı´slo na´m uda´va´ na´sˇ index. Jiny´mi slovy: pro volicˇe i je Shapley-Shubiku˚v index dany´ vztahem ϕi =
pocˇet serˇazenı´, v nichzˇ je i klı´cˇovy´m volicˇem
n!
Kombinatoricka´ formule pro ”S-S” index: ϕi =
X (k − 1)!(n − k)! , n! K
k = |K|,
kde soucˇet probı´ha´ prˇes vsˇechny koalice K, pro neˇzˇ je i „klı´cˇovy´m volicˇem“: koalice K je vı´teˇzna´, avsˇak koalice K \ {i} nikoli. JJ x II 370
John F. Banzhaf III. (*1940) Weighted Voting doesn’t work: a Mathematical Analysis, 1965 Vhodnou mı´rou za´konoda´rcovy sı´ly je jednodusˇe pocˇet ru˚zny´ch situacı´, v nichzˇ je schopen ovlivnit vy´sledek. Tj. v prˇ´ıpadeˇ n za´konoda´rcu˚, z nichzˇ kazˇdy´ jedna´ neza´visle a je schopen ovlivnit vy´sledek pouze svy´mi hlasy, pomeˇr sı´ly za´konoda´rce X k sı´le za´konoda´rce Y je stejny´ jako pomeˇr pocˇtu mozˇny´ch volebnı´ch kombinacı´ cele´ho sboru, v nichzˇ X mu˚zˇe zmeˇnit vy´sledek zmeˇnou sve´ho hlasu, k pocˇtu kombinacı´, v nichzˇ Y mu˚zˇe zmeˇnit vy´sledek zmeˇnou sve´ho hlasu. Jiny´mi slovy: Sı´la volicˇe i ma´ by´t prˇ´ımo u´meˇrna´ pocˇtu koalic, pro neˇzˇ je i „klı´cˇovy´m volicˇem“. Je vhodne´ vydeˇlit tento pocˇet celkovy´m pocˇtem koalic obsahujı´cı´ch i.
JJ x II 371
Sı´la volicˇe i ma´ by´t prˇ´ımo u´meˇrna´ pocˇtu koalic, pro neˇzˇ je i „klı´cˇovy´m volicˇem“. Je vhodne´ vydeˇlit tento pocˇet celkovy´m pocˇtem koalic obsahujı´cı´ch i. Nenormalizovany´ Banzhafu˚v index: βi0 =
pocˇet koalic, v nichzˇ je i „klı´cˇovy´m volicˇem“
2n−1
Normalizovany´ Banzhafu˚v index: β0 βi = P i 0 i βi One Man, 3,312 Votes: A Mathematical Analysis of the Electoral College, 1968
JJ x II 372
☛ Prˇ´ıklad 7: Rada bezpecˇnosti OSN 1946: V dobeˇ vzniku tvorˇilo Radu bezpecˇnosti OSN 5 sta´ly´ch ˇ ´ınska´ republika, Francie, Soveˇtsky´ svaz, USA, Spojene´ cˇlenu˚ (C kra´lovstvı´) a 6 cˇlenu˚ nesta´ly´ch, voleny´ch na 2 roky (Brazı´lie, Mexiko, Austra´lie, Polsko, Egypt, Nizozemı´). K prˇijetı´ rezoluce bylo trˇeba 7 kladny´ch hlasu˚ a zˇa´dne´ veto sta´le´ho cˇlena. Oznacˇme S – sta´le´ho cˇlena, N – nesta´le´ho cˇlena 11! 11 Pocˇet vsˇech serˇazenı´: = = 462 5 6!5! Serˇazenı´, prˇi nichzˇ je neˇktery´ z nesta´ly´ch cˇlenu˚ klı´cˇovy´: SSSSSN | {z } N N | N{zN N} 6 1 Shapley-Shubiku˚v index vsˇech nesta´ly´ch cˇlenu˚ dohromady: ϕN =
6 1 = = 0, 013 462 77
Shapley-Shubiku˚v index jednoho nesta´le´ho cˇlena: ϕ N0 =
1 = 0, 00216 462 JJ x II 373
Shapley-Shubiku˚v index vsˇech sta´ly´ch cˇlenu˚ dohromady: ϕS = 1 −
456 76 6 = = = 0, 987 462 462 77
Shapley-Shubiku˚v index jednoho sta´le´ho cˇlena: ϕ S0 =
76 = 0, 1974 5 · 77
Pomeˇr: ϕ S0 = 91, 4 ϕ N0
JJ x II 374
1965: Rada bezpecˇnosi rozsˇ´ırˇena na 10 nesta´ly´ch cˇlenu˚ (dnes: Belgie, Burkina Faso, Chorvatsko, Indone´sie, Ita´lie, Jihoafricka´ republika, Kostarika, Libye, Panama, Vietnam). K prˇijetı´ rezoluce je trˇeba 9 kladny´ch hlasu˚ a zˇa´dne´ veto od sta´le´ho cˇlena. 15! 15 Pocˇet vsˇech serˇazenı´: = = 3003 5 10!5! Serˇazenı´, prˇi nichzˇ je neˇktery´ z nesta´ly´ch cˇlenu˚ klı´cˇovy´:
N N N N} SSSSSN {z N N} N N | N N {z | 8! 8 = = 56 1 3 5!3!
56 = 0, 0186 = 1, 86%, 3003 2947 ϕS = = 0, 9814 = 98, 14%, 3003 ϕ S0 = 105, 25 ϕ N0 ϕN =
ϕN0 = 0, 00186 ϕS0 = 0, 19628
JJ x II 375
Banzhafu˚v index (v pu˚vodnı´m slozˇenı´ Rady): Vı´teˇzne´ koalice, pro neˇzˇ je jeden konkre´tnı´ nesta´ly´ cˇlen N klı´cˇovy´: SSSSSNN . . . 5 mozˇnostı´ (pro N) Vsˇech nepra´zdny´ch koalic ... 210 5 = 0, 004883 210 Vı´teˇzne´ koalice, pro neˇzˇ je jeden konkre´tnı´ sta´ly´ cˇlen S klı´cˇovy´: SSSSSNN, SSSSSNNN, . . . SSSSSNNNNNN 0 = Banzhafu˚v index jednoho nesta´le´ho cˇlena: βN 0
Banzhafu˚v index jednoho sta´le´ho cˇlena: 6 6 6 + + ··· + 2 3 6 57 βS0 0 = = 10 10 2 2 Soucˇet: X i
βN0 =
βi0 = 6 ·
57 30 + 285 315 5 + 5 · = = 210 210 210 210
5 = 0, 01587, 315
βS0 =
57 , 315
βS0 = 11, 4 βN0
JJ x II 376
☛ Prˇ´ıklad 8: Akciona´rˇi Uvazˇujme firmu, jejı´chzˇ 40 % akciı´ vlastnı´ jeden akciona´rˇ (oznacˇme jej V – velky´) a zby´vajı´cı´ch 60 % je rozdeˇleno mezi 600 maly´ch akciona´rˇu˚ (kazˇdy´ z nich tedy vlastnı´ 0,1 %; libovolne´ho z nich oznacˇme M – maly´). Pocˇet vsˇech serˇazenı´:
601
Serˇazenı´, prˇi nichzˇ je neˇktery´ z maly´ch akciona´rˇu˚ klı´cˇovy´: V {z. . . M} M M | M{z. . . M} | MM 101 · 1
= 101
M V . . . M} | MM | . . . {z {z. . . M} M M 1 · 100
= 100
Serˇazenı´, prˇi nichzˇ je klı´cˇovy´ velky´ akciona´ˇr:
201
601 − 201 = 400
JJ x II 377
Shapley-Shubiku˚v index: ϕV =
ϕM =
400 = 0, 666 = 66, 6 % 601
201 = 0, 334 = 33, 4 %, 601
ϕM 0 =
1 · 33, 4% = 0, 056 % 600
ϕV = 1194 ϕ M0
JJ x II 378
ˇ eske´ republiky ☛ Prˇ´ıklad 9: Strany v Parlamentu C
81
70
26
13
6
4
1
ODS
ČSSD
KSČM
KDU
SZ
N
200
velikost k 6
2 3 4 5 6 7
ODS ODS ODS ODS ODS
ČSSD ČSSD ČSSD ČSSD
KSČM KSČM KSČM
KDU KDU
SZ
196 194 187 174 130 119
5 5 5 5 5 5
0,033333333
N N N N N
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
ODS ODS ODS ODS
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
0,016666667
N N N N N N N N N N
190 183 170 126 115 181 168 124 113 161 117 106 104 93 49
ČSSD
ODS ODS ODS ODS ODS
ČSSD ČSSD ČSSD ČSSD ČSSD ČSSD ČSSD ČSSD ČSSD
KSČM KSČM KSČM KSČM KSČM KSČM KSČM KSČM KSČM
KDU KDU KDU KDU KDU KDU KDU
ČSSD KSČM
SZ SZ SZ SZ
KDU KDU KDU
KSČM KSČM
ODS
SZ SZ SZ SZ
KDU KDU KDU
SZ SZ SZ SZ SZ SZ
příspěvek k S-S
JJ x II 379
23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
ODS ODS ODS
43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
ODS ODS ODS ODS ODS ČSSD ČSSD ČSSD ČSSD KSČM KSČM KSČM KDU KDU SZ
ODS ODS
ČSSD ČSSD ČSSD ČSSD ČSSD
KSČM KSČM KSČM KSČM KSČM
ODS ČSSD KSČM ODS ODS
KDU KDU KDU
KDU KDU KDU
SZ SZ SZ SZ SZ SZ
ČSSD ČSSD
KSČM KSČM
ODS ČSSD KSČM
KDU KDU KDU
ODS ČSSD KSČM KDU ČSSD KSČM KDU SZ N KSČM KDU SZ N KDU SZ N SZ N N
SZ SZ SZ SZ
N N N N N N N N N N
177 164 109 120 157 102 113 89 100 45 155 106 91 87 98 43 80 91 36 23
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
0,016666667
151 107 94 87 85 96 83 76 74 39 32 30 17 17 10
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
0,033333333
JJ x II 380
Strana
Shapley-Shubiku˚v index ϕi
ODS (81) ˇ CSSD (70) ˇM KSC (26) ˇ SL (13) KDU-C SZ N
(6) (4) soucˇet
Banzhafu˚v index pocˇet klı´cˇ. pozic
βi0
βi
0,383333 0,25 0,25 0,05 0,05 0,016666667
19 13 13 3 3 1
0,59375 0,40625 0,40625 0,09375 0,09375 0,03125
0,365384615 0,25 0,25 0,057692308 0,057692308 0,019230769
1,000000
52
1,625
1,000000000
JJ x II 381
☛ Prˇ´ıklad 10: Rozdeˇlenı´ na´kladu˚ na stavbu Uvazˇujme cˇtyrˇi firmy, ktere´ pla´nujı´ postavit novy´ most, jehozˇ cena je C = 20 milionu˚ korun. Jednolive´ firmy jsou ochotny zaplatit maxima´lneˇ na´sledujı´cı´ cˇa´stky: u1 = 10, u2 = 8, u3 = 12, u4 = 16 milionu˚, ktere´ odpovı´dajı´ uzˇitku firem z nove´ho mostu (u´spora cˇasu, pohonny´ch hmot prˇi dopraveˇ apod.) Jaky´m zpu˚sobem by se celkove´ na´klady meˇly rozdeˇlit mezi firmy? Rˇesˇenı´. Uvazˇujme charakteristickou funkci v(K) = max
P
i∈K
ui − C, 0
({1}) = v({2}) = v({3}) = v({4}) = 0, v({1, 2}) = v({2, 3}) = 0, v({1, 3}) = 2, v({3, 4}) = 8, v({2, 4}) = 4, v({1, 4}) = 6, v({1, 2, 3}) = 10, v({1, 2, 4}) = 14, v({2, 3, 4}) = 16, v({1, 3, 4}) = 18, v({1, 2, 3, 4}) = 26
JJ x II 382
ϕ1 =
1!2! 4!
[(v({1, 3}) − v({3})) + (v({1, 4}) − v({4}))] +
+ 2!1! [(v({1, 2, 3}) − v({2, 3})) + (v({1, 3, 4}) − v({3, 4})) + 4! + (v({1, 2, 4}) − v({2, 4}))]+ [(v({1, 2, 3, 4}) − v({2, 3, 4}))] = + 3!0! 4! =
1 12
[2 + 6] +
1 12
[10 + 10 + 10] + 14 [10] =
68 12
=
17 3
= 5, 667
Analogicky: ϕ2 =
1 12
·4+
ϕ3 =
1 12
· 10 +
ϕ4 =
1 12
· 18 +
1 12
· 24 + 14 · 8 =
52 12
=
13 3
= 4, 333
1 12
· 34 + 41 · 12 =
80 12
=
20 3
1 12
· 46 + 41 · 16 =
112 12
=
28 3
= 6, 667 = 9, 333
JJ x II 383
ϕ1 = Platby:
17 , 3
ϕ2 =
13 , 3
ϕ3 =
20 , 3
ϕ4 =
28 3
p i = u1 − ϕ i p1 = 10 −
17 3
=
13 , 3
p2 = 8 −
p3 = 12 −
20 3
=
16 , 3
p4 = 16 −
P
i
pi =
13 3
+
11 3
+
16 3
+
20 3
13 3
=
28 3
11 , 3
=
20 , 3
= 20
JJ x II 384
9.1.2.
Nukleolus (Schmeidler, 1969)
Necht’ v je hra ve tvaru charakteristicke´ funkce s N hra´cˇi, a je ˇ ´ıslo dana´ imputace, K je dana´ koalice. C X ai (9.9) e(K, a) = v(K) − i∈K
se nazy´va´ exces koalice K vzhledem k imputaci a. Oznacˇme symbolem e(a) vektor o 2N −1 slozˇka´ch, ktery´ je tvorˇen excesy pro vsˇechny koalice. Usporˇa´dejme jeho slozˇky sestupneˇ podle velikosti a takto vznikly´ vektor oznacˇme jako f (a). Kazˇde´ imputaci a tı´mto zpu˚sobem prˇirˇad’me vektor f (a) a na takto vznikle´ mnozˇineˇ vektoru˚ {f (a); a je imputace} ˇ ekneme, zˇe imputace b uvazˇujme lexikograficke´ usporˇa´da´nı´. R je prˇijatelneˇjsˇ´ı nezˇ imputace a, jestlizˇe platı´: f (b) ≤(lex) f (a),
(9.10)
kde ≤(lex) je nerovnost v lexikograficke´m („slovnı´kove´m“) usporˇa´da´nı´, tj. bud’ je prvnı´ slozˇka vektoru b je mensˇ´ı nezˇ prvnı´ slozˇka vektoru a, nebo jsou prvnı´ slozˇky stejne´, ale druha´ slozˇka vektoru JJ x II 385
b je mensˇ´ı nezˇ druha´ slozˇka vektoru a, nebo jsou prvnı´ i druhe´ slozˇky stejne´, ale trˇetı´ slozˇka vektoru b je mensˇ´ı nezˇ trˇetı´ slozˇka vektoru a, atd. Uveˇdomme si, zˇe je-li imputace b prˇijatelneˇjsˇ´ı nezˇ imputace a, vzbuzuje me´neˇ na´mitek nezˇ imputace a nebo jsou tyto na´mitky stejne´ – prvnı´ rozdı´lny´ exces musı´ by´t v f (b) mensˇ´ı nezˇ v f (a). Definice 8. Nukleolem hry se nazy´va´ takova´ imputace, pro kterou platı´: f (b) ≤(lex) f (a)
pro vsˇechny imputace a.
JJ x II 386
☛ Prˇ´ıklad 11. Pro hru s charakteristickou funkcı´ v(Q) = 0,
v(∅) = 0,
v({1}) = v({2}) = v({3}) = −1, v({1, 2}) = v({1, 3}) = v({2, 3}) = 1, .
ma´ vektor e(a) tyto slozˇky: −(a1 + a2 + a3 ), 1 − a1 − a2 , 1 − a1 − a3 , 1 − a2 − a3 , −(1 + a1 ), −(1 + a2 ), −(1 + a3 ). Prvnı´ slozˇka je rovna nule, nebot’ v(Q) = a1 + a2 + a3 = 0. Protozˇe ai ≥ v({i}) = −1, jsou poslednı´ trˇi slozˇky vzˇdy nekladne´. Kladny´ exces proto mohou mı´t jen dvouprvkove´ koalice. Minimum min
a je imputace
max{1 − a1 − a2 , 1 − a1 − a3 , 1 − a2 − a3 } JJ x II 387
nasta´va´ pro a = (0, 0, 0). Nukleolus je tedy imputace (0, 0, 0).
JJ x II 388
☛ Prˇ´ıklad 12: Uvazˇujme hru s na´sledujı´cı´ charakteristickou funkcı´: 1 v(1) = , v(2) = 0, v(1, 2) = 1 2 Imputace: 1 a1 ≥ , a2 ≥ 0, a1 + a2 = 1 2
1 , 1 , a 2 = 1 − a1 2
1 , 1 , a 2 = 1 − a1 2
a1 ∈
Ja´dro hry: 1 a1 ≥ , a2 ≥ 0, a1 + a2 = 1 2 Shapleyho hodnota: 1 1 3 H1 = · +1 = , 2 2 4
a1 ∈
1 1 1 H2 = · 0 + = 2 2 4
JJ x II 389
Nukleolus: e({1}, a) = 12 −a1
e({2}, a) = 0−a2
e({1, 2}, a) = 1−a1 −a2 = 0
s
e(a) = −a2 , 12 − a1 , 0 = −a2 , a2 − 21 , 0 f (a) = 0, −a2 , a2 −
1 2
= 0, a2 − 21 , −a2
⇔ ⇔
0 ≤ a2 ≤ 1 4
1 4
≤ a2 ≤ 1
y
y = a2 -1 1 4
y=0
0
1 2
a2 minimalizace: a1 =
1 2
3 1 , a2 = 4 4
y = -a2
x x
JJ x II 390
Nash:
Status Quo: (a10 , a20 ) =
g(a1 , a2 ) =
1 a1 − 2
a2 =
1 a1 − 2
1 ,0 2
(1 − a1 ) = 3 1 = a1 − a21 − = h(a1 ) 2 2
a2
h0 (a1 ) =
a1 + a2 = 1
3 − 2a1 = 0 2
a1 =
0
1 2
3 4
3 1 , a2 = 4 4
a1
JJ x II 391
Babylonsky´ Talmud (5. stol. prˇ. Kr.) Deˇlenı´ odeˇvu (Contested garment) Dva [u soudu] drzˇ´ı odeˇv . . . jeden rˇ´ıka´: „cely´ je mu˚j!“ A druhy´ rˇ´ıka´: „ma´ je polovina!“ . . . Potom prvnı´ dostane trˇi cˇtvrtiny a druhy´ jednu cˇtvrtinu. [Misˇna, 4. odd., 2. trakta´t – Bava m’cija]
Rabi Rasˇi (†1105): druhy´ prˇizna´va´ prvnı´mu jednu polovinu – ta je tedy jasna´ a jedna´ se jen o zby´vajı´cı´ polovinu, ktera´ je pak rozdeˇlena rovny´m dı´lem. a1 =
1 1− + 2 2
1 2
=
3 , 4
a2 = 0 +
1 1 = 4 4
JJ x II 392
Na´roky:
d1 = 1, d2 = 1/2
Pozu˚stalost:
E = 1 < d1 + d2
ˇ esˇenı´: R
a = (a1 , a2 ); a1 + a2 = E (ai je cˇa´st, ktera´ prˇipadne veˇrˇiteli i)
ˇ esˇenı´ prˇedepsane´ CG-principem (contested garment): R a1 =
E − (E − d1 )+ − (E − d2 )+ + (E − d2 )+ , 2
a2 =
E − (E − d1 )+ − (E − d2 )+ + (E − d1 )+ , 2 kde (α)+ := Max (α, 0)
JJ x II 393
a1 =
E − (E − d1 )+ − (E − d2 )+ + (E − d2 )+ , 2
a2 =
E − (E − d1 )+ − (E − d2 )+ + (E − d1 )+ , 2
E ≤ d1 : (E − d1 )+ = (E − d2 )+ = 0, pro E = d1 :
a1 = a2 = E/2 a1 = a2 = d1 /2
d1 < E ≤ d2 : (E − d1 )+ > 0, (E − d2 )+ = 0, a1 = d1 /2, a2 = d1 /2 + (E − d1 ) = E − d1 /2 pro E = d1 :
a1 = d1 /2, a2 = d2 − d1 /2
d2 < E : (E − d1 )+ > 0, (E − d2 )+ > 0, a1 =
E + d1 − d2 E + d2 − d1 , a2 = 2 2
JJ x II 394
Obeˇma k uspokojenı´ cele´ho pozˇadavku chybı´: d1 − a1 = d1 −
E + d1 − d2 d1 + d2 − E = 2 2
d2 − a2 = d2 −
E + d2 − d1 d1 + d2 − E = 2 2
Slovy lze vy´sˇe uvedene´ vztahy vyja´drˇit takto: Male´ cˇa´stky, ktere´ nedosahujı´ ani mensˇ´ıho z obou na´roku˚, jsou rozdeˇleny rovny´m dı´lem. Jakmile veˇrˇitel s nejmensˇ´ım na´rokem dostane polovinu sve´ho pozˇadavku, kazˇda´ koruna navı´c prˇipadne jen druhe´mu veˇrˇiteli, a to azˇ do okamzˇiku, kdy mu chybı´ polovina mensˇ´ıho na´roku (neboli obeˇma chybı´ d1 /2). Pote´ se do hry vra´tı´ prvnı´ veˇrˇitel a kazˇda´ koruna navı´c je opeˇt rozdeˇlena rovny´m dı´lem. Ztra´ty, ktere´ obeˇma chybeˇjı´ k uspokojenı´ jejich na´roku˚, mu˚zˇeme sledovat jizˇ od hodnoty E = (d1 + d2 )/2. Zde proces probı´ha´ zrcadloveˇ: male´ ztra´ty jsou deˇleny rovny´m dı´lem (prˇ´ıpad d2 < E), jakmile veˇrˇiteli s mensˇ´ım na´rokem chybı´ polovina, kazˇda´ dalsˇ´ı chybeˇjı´cı´ koruna jde na vrub druhe´ho veˇˇritele, azˇ obeˇma chybı´ pra´veˇ polovina jejich na´roku.
JJ x II 395
M. M. Kaminski, 2000 Hydraulic Rationing. Mathematical Social Sciences 40, 131–135 Hydraulicka´ analogie deˇlenı´ cˇa´stky (kapalina) mezi veˇrˇitele s ru˚zny´mi na´roky (velikosti na´dob; kazˇda´ na´doba je tvorˇena dveˇma cˇa´stmi stejne´ho objemu; objem spojnice teˇchto cˇa´stı´ je zanedbatelny´; pu˚vodneˇ pro trˇi veˇrˇitele):
JJ x II 396
M. M. Kaminski, 2000 Hydraulic Rationing. Mathematical Social Sciences 40, 131–135 Hydraulicka´ analogie deˇlenı´ cˇa´stky (kapalina) mezi veˇrˇitele s ru˚zny´mi na´roky (velikosti na´dob; kazˇda´ na´doba je tvorˇena dveˇma cˇa´stmi stejne´ho objemu; objem spojnice teˇchto cˇa´stı´ je zanedbatelny´; pu˚vodneˇ pro trˇi veˇrˇitele):
JJ x II 397
Monotonie: Funkce a1 (E), a2 (E) vyjadrˇujı´cı´ za´vislost cˇa´stky, kterou dostane kazˇdy´ z veˇrˇitelu˚, na pozu˚stalosti E jsou neklesajı´cı´.
Nejle´pe je to videˇt opeˇt na hydraulicke´m modelu: prˇilijeme-li vodu, hladina v zˇa´dne´ z na´dob nepoklesne.
JJ x II 398
Proble´m bankrotu: (E, d), d = (d1 , d2 , . . . dn ) Veˇrˇitele´:
1, 2, . . . , n
Dluhy:
d1 ≥ 0, d2 ≥ 0, . . . , dn ≥ 0,
Pozu˚stalost:
E < d1 + d2 + · · · + dn
ˇ esˇenı´: R
x = (x1 , x2 , . . . xn ); x1 + x2 + · · · + xn = E (xi cˇa´stka, ktera´ prˇipadne veˇrˇiteli i)
Oznacˇme D = d1 + d2 + · · · + dn Konzistentnı´ rˇesˇenı´: pro vsˇechna i 6= j je deˇlenı´ cˇa´stky xi + xj prˇedepsane´ CG-principem pro dluhy di , dj rovno (xi , xj )
JJ x II 399
Veˇta (Aumann, Maschler, 1985): Kazˇdy´ proble´m bankrotu ma´ jedine´ konzistentnı´ rˇesˇenı´. Du˚kaz. Nejvy´sˇe jedno rˇesˇenı´: Sporem: Uvazˇujme dveˇ ru˚zna´ konzistentnı´ rˇesˇenı´ x, y, kde x = (x1 , . . . , xi , . . . , xj , . . . , xn ),
n X
xk = E, xk ≥ 0,
k=1
y = (y1 , . . . , yi , . . . , yj , . . . , yn ),
n X
yk = E, yk ≥ 0,
k=1
x i < y i , xj > y j ,
yi + y j ≥ x i + x j .
Konzistentnost ⇒ j dostane yj prˇi celkove´m jmeˇnı´ yi + yj , xj prˇi celkove´m jmeˇnı´ xi + xj . Monotonie (vlevo je rozdeˇlova´na vysˇsˇ´ı cˇa´stka) ⇒ yi + yj ≥ xi + xj ⇒ yj ≥ xj ⇒ spor s prˇedpokladem xj > yj
JJ x II 400
Konstrukce konzistentnı´ho rˇesˇenı´: Uvazˇujme rostoucı´ hodnotu cˇa´stky E. Pro 0 ≤ E ≤ nd1 /2 je konzistentnı´m rˇesˇenı´m rovne´ rozdeˇlenı´, kdy kazˇdy´ dostane cˇa´stku E/n. Jakmile prvnı´ veˇrˇitel obdrzˇ´ı d1 /2, prˇestane se jeho cˇa´stka zvysˇovat a s rostoucı´ hodnotou E se cˇa´stka, ktera´ je navı´c, rozdeˇlı´ mezi veˇrˇitele 2, 3, . . . , n, a to azˇ do okamzˇiku, kdy druhy´ obdrzˇ´ı d2 /2. Prˇi dalsˇ´ım zvysˇova´nı´ cˇa´stky E se pak bude vsˇe, co je navı´c, deˇlit mezi veˇrˇitele 3, 4, . . . , n, atd., azˇ kazˇdy´ obdrzˇ´ı pra´veˇ polovinu sve´ho pozˇadavku. Pro E > D/2 probı´ha´ proces zrcadloveˇ, jen se mı´sto „zisku“ xi uvazˇuje ztra´ta di − xi . Nebo: U veˇrˇitele s nejvysˇsˇ´ım na´rokem dosa´hne pokracˇujme ve zvysˇova´nı´ azˇ do dn − (dn−1 /2), tj. azˇ do okamzˇiku, kdy mu chybı´ polovina druhe´ho nejvysˇsˇ´ıho na´roku. Prˇi dalsˇ´ım navy´sˇenı´ E se do hry vra´tı´ veˇrˇitel n − 1 a vsˇe, co je navı´c, je rovny´m dı´lem rozdeˇleno mezi neˇj a veˇrˇitele n, a to azˇ do okamzˇiku, kdy obeˇma chybı´ dn−2 /2, atd.
JJ x II 401
M. M. Kaminski, 2000 Hydraulic Rationing. Mathematical Social Sciences 40, 131–135 Hydraulicka´ analogie deˇlenı´ cˇa´stky (kapalina) mezi veˇrˇitele s ru˚zny´mi na´roky (velikosti na´dob; kazˇda´ na´doba je tvorˇena dveˇma cˇa´stmi stejne´ho objemu; objem spojnice teˇchto cˇa´stı´ je zanedbatelny´):
JJ x II 402
Uvazˇujme dva veˇrˇitele s na´roky di ≤ dj . Pro male´ hodnoty E je cˇa´stka rozdeˇlena rovny´m dı´lem; jakmile prvnı´ veˇrˇitel dosa´hne poloviny sve´ho na´roku, zu˚stane u di /2 a cˇa´stka, ktera´ je navı´c, prˇipadne druhe´mu azˇ do dj /2. Prˇi dalsˇ´ım zvysˇova´nı´ se vra´tı´ do hry veˇrˇitel i a vsˇe, co je navı´c, se rozdeˇlı´ rovny´m dı´lem mezi oba dva. To je ovsˇem prˇesneˇ slovnı´ popis CG principu.
JJ x II 403
Bankrotova´ hra odpovı´dajı´cı´ proble´mu bankrotu (E, d) : vE,d (S) := (E − d(N \ S))+ ,
kde (α)+ := Max (α, 0)
Veˇta (Aumann, Maschler, 1985): Konzistentnı´ rˇesˇenı´ proble´mu bankrotu je nukleolus odpovı´dajı´cı´ hry.
JJ x II 404
Standardnı´ rˇesˇenı´ hry 2 hra´cˇu˚ v : xi =
v(1, 2) − v(1) − v(2) + v(i) 2
ekvivalentneˇ: x1 + x2 = v(1, 2), x1 − x2 = v(1 − v(2)) Jiny´mi slovy, standardnı´ rˇesˇenı´ da´va´ kazˇde´mu hra´cˇi i cˇa´stku v(i), kterou si mu˚zˇe zajistit sa´m, a zbytek deˇlı´ rovny´m dı´lem mezi oba hra´cˇe. Nukleolus, ja´dro a Shapleyho hodnota te´to hry dvou hra´cˇu˚ se vsˇechny shodujı´ se standardnı´m rˇesˇenı´m. BOJ O ODEˇV 1 Charakteristicka´ funkce: v(1) = , v(2) = 0, v(1, 2) = 1 2 Viz prˇ´ıklad vy´sˇe
JJ x II 405
ˇ ITELE´ ´ HRA – 3 VEˇR BANKROTOVA Babylonsky´ Talmud (5. stol. prˇ. Kr.), Misˇna, 3. odd.: Zˇeny, 2. trakta´t: Svatebnı´ u´pisy Zemrˇe muzˇ, ktery´ po sobeˇ zanecha´ trˇi vdovy, z nichzˇ kazˇda´ meˇla ve svatebnı´ smlouveˇ stanovenou cˇa´stku, kterou dostane v prˇ´ıpadeˇ manzˇelova u´mrtı´: prvnı´ zˇena ma´ dostat 100, druha´ 200 a trˇetı´ 300 peneˇzˇnı´ch jednotek zuz. Jak mezi vdovy rozdeˇlit pozu˚stalost, prˇedstavuje-li pouze 100, 200 nebo 300 zuz? ˇ esˇenı´ uvedene´ v trakta´tu lze shrnout do tabulky: R
Za´vazek
Pozu˚stalost
100
200
300
100
33 13
33 31
33 13
200
50
75
75
300
50
100
150
JJ x II 406
Talmud – historicka´ pozna´mka Prˇipomenˇme, zˇe jednı´m ze za´kladu˚ zˇidovske´ kultury, pra´va a na´bozˇenstvı´ je Misˇna (opakova´nı´, ucˇenı´ ). Jejı´ autor, Rabi Jehuda ha-Nasi (135 – 217) z galilejske´ho meˇsta Usˇa v nı´ shrnul do te´ doby prˇeva´zˇneˇ u´stneˇ tradovane´ pobiblicke´ na´bozˇenske´ pra´vo v ucelenou sbı´rku. Misˇna se pak stala prˇedmeˇtem studia dalsˇ´ıch generacı´ ucˇencu˚; vy´sledkem jejich cˇinnosti bylo vytvorˇenı´ Gemary (doplneˇnı´ ), rozsa´hle´ho komenta´rˇe obsahujı´cı´ho diskuse a polemiky jednotlivy´ch ucˇencu˚, jejich zˇa´ku˚ a sˇkol. Tyto Gemary vznikly dveˇ: na izraelske´ pu˚deˇ a v Babylonii. Soubor Misˇny a Gemary se nazy´va´ Talmud a podle mı´sta vzniku se rozlisˇuje Talmud jeruzale´msky´ cˇi palestinsky´, ktery´ byl dokoncˇen v polovineˇ cˇtvrte´ho stoletı´ (Svata´ zemeˇ se v te´ dobeˇ ocitla pod vla´dou krˇest’ansky´ch byzantsky´ch cı´sarˇu˚ a hlavnı´ centrum zˇidovske´ho zˇivota se prˇesouvalo do Babylonie; jeruzale´msky´ Talmud se proto nezachoval v takove´ u´plnosti jako da´le zmı´neˇny´ Talmud babylonsky´) a Talmud babylonsky´, jehozˇ konecˇnou redakci provedl RABI ASˇI (†427) a jeho zˇa´ci (Talmud babylonsky´ vznikal v prˇ´ızniveˇjsˇ´ıch podmı´nka´ch; zˇidovske´ obce v Babylonii byly obdarˇeny znacˇnou autonomiı´ a teˇsˇily se plny´m pra´vu˚m).
JJ x II 407
Misˇna se cˇlenı´ do sˇesti oddı´lu˚, z nichzˇ pro nasˇe potrˇeby je nejzajı´maveˇjsˇ´ı oddı´l trˇetı´ zvany´ Na´sˇ´ım (Zˇeny), ktery´ je tvorˇen sedmi trakta´ty; druhy´ z nich se nazy´va´ K’tubot(Svatebnı´ u´pisy) a rˇesˇ´ı kromeˇ jine´ho ota´zky spojene´ se svatebnı´ smlouvou vcˇetneˇ obnosu, ktery´m se muzˇ zˇeneˇ zavazuje pro prˇ´ıpad rozvodu nebo sve´ smrti. V trakta´tu Na´sˇ´ım lze nale´zt i rˇesˇenı´ vy´sˇe uvedene´ho proble´mu.
JJ x II 408
Nynı´ se vrat’me k tabulce rozdeˇlenı´ pozu˚stalosti mezi vdovy. Za´vazek
Pozu˚stalost
100
200
300
100
33 13
33 31
33 13
200
50
75
75
300
50
100
150
Poslednı´ rˇa´dek tabulky prˇedstavuje proporciona´lnı´ rozdeˇlenı´, ktere´ odpovı´da´ tomu, co by bez dlouhy´ch u´vah pravdeˇpodobneˇ zvolila veˇtsˇina z na´s. Rovne´ rozdeˇlenı´ v prvnı´m rˇa´dku, kdy pozu˚stalost neprˇevy´sˇ´ı hodnotu nejnizˇsˇ´ıho za´vazku, ma´ take´ jesˇteˇ sve´ logicke´ opodstatneˇnı´. Proˇ tyrˇi ru˚zna´ zdu˚vodstrˇednı´ rˇa´dek se vsˇak dlouho jevil jako tvrdy´ orˇ´ısˇek. C neˇnı´ cele´ tabulky podali R. J. Aumann a M. Maschler v roce 1985. Z toho trˇi jsou zalozˇena pouze na principech obsazˇeny´ch v Talmudu.
JJ x II 409
1. zdu˚vodneˇnı´: Konzistentnost ˇ esˇenı´ uvedene´ v Talmudu je konzistentnı´. R
2. zdu˚vodneˇnı´: Socia´lnı´ spravedlnost Druhe´ zdu˚vodneˇnı´ je zalozˇeno na jine´m talmudicke´m principu, ktery´ je obsazˇen v cˇa´sti Arachı´n (Odhady): Obecneˇ ten, kdo pu˚jcˇı´, ma´ automaticky retencˇnı´ pra´vo na nemovite´ jmeˇnı´ dluzˇnı´ka. Je-li vsˇak cena nemovitosti mensˇ´ı nezˇ 1/2 pu˚jcˇky, dluzˇnı´k s nı´ mu˚zˇe v urcˇity´ch prˇ´ıpadech volneˇ disponovat. Na prvnı´ pohled se na´m tento princip mu˚zˇe zda´t paradoxnı´, ma´ vsˇak svu˚j hlubsˇ´ı eticky´ a psychologicky´ za´klad. Je-li totizˇ cena nemovitosti veˇtsˇ´ı nezˇ 1/2 hodnoty pu˚jcˇky, je retencˇnı´ pra´vo du˚lezˇite´ a veˇrˇitel dı´ky neˇmu zı´ska´ veˇtsˇinu poskytnuty´ch peneˇz zpeˇt. Je-li vsˇak cena nemovitosti mensˇ´ı nezˇ 1/2 pu˚jcˇky, pra´vo na ni stejneˇ nehraje velkou roli; pu˚jcˇka byla pravdeˇpodobneˇ poskytnuta na za´kladeˇ du˚veˇry a bylo by nemora´lnı´ prˇevzı´t do vlastnictvı´ nemovitost od cˇloveˇka, ktery´ prˇijal pu˚jcˇku v dobre´ vı´rˇe.
JJ x II 410
Princip za´rovenˇ ilustruje mysˇlenku, ktera´ je pro Talmud typicka´ a kterou lze zjednodusˇeneˇ zformulovat takto: „Vı´ce nezˇ 1/2 je jako vsˇe, me´neˇ nezˇ 1/2 je jako nic.“ Polovina zde prˇedstavuje vy´znamny´ meznı´k: ma´me-li dostat vı´ce nezˇ 1/2 dluhu, zameˇrˇ´ıme se na celou cˇa´stku a stara´me se o velikost ztra´ty; ma´me-li dostat me´neˇ nezˇ 1/2, v duchu dluh odepı´sˇeme u´plneˇ a jsme pak vdeˇcˇni za cokoli, co nakonec dostaneme – soustrˇedı´me se na „odmeˇnu“. Bylo by tedy socia´lneˇ nespravedlive´, kdyby byli ru˚znı´ veˇˇritele´ na ru˚zny´ch strana´ch tohoto prˇedeˇlu, tj. aby jeden dostal veˇtsˇinu sve´ho na´roku, zatı´mco jiny´ by veˇtsˇinu ztratil. Pro E ≤ D/2 jsou proto zisky opeˇt deˇleny rovny´m dı´lem, jakmile vsˇak u neˇktere´ho veˇrˇitele prˇideˇlena´ cˇa´stka prˇesa´hne jednu polovinu jeho pozˇadavku, dostane pouze tuto polovinu a vsˇe, co je navı´c, se rozdeˇlı´ mezi ostatnı´; pro E ≥ D/2 se prˇi dodrzˇenı´ stejny´ch podmı´nek deˇlı´ rovny´m dı´lem ztra´ty.
JJ x II 411
3. zdu˚vodneˇnı´: Tvorba koalic Trˇetı´ zdu˚vodneˇnı´ vycha´zı´ z komenta´rˇe uvedene´ho v Jeruzale´mske´m Talmudu: Samuel ˇr´ıka´, zˇe Misˇna vycha´zı´ z toho, zˇe se vdovy navza´jem posilujı´, konkre´tneˇ, trˇetı´ se spojı´ s druhou prˇi jedna´nı´ s prvnı´. Mohou jı´ rˇ´ıci: „Tvu˚j pozˇadavek je 100, zˇe? Vezmi si 50 a jdi“. Druhe´ dveˇ zˇeny tak vytvorˇ´ı koalici proti prvnı´; po vyplacenı´ 50 jednotek si zbytek rozdeˇlı´ na za´kladeˇ CG principu. Pro E = 200 tak zı´ska´me rozdeˇlenı´ (50, 75, 75), pro E = 300 obdrzˇ´ıme (50, 100, 150). Tento princip ovsˇem funguje jen pro 150 ≤ E ≤ 450, nebot’ pro E < 150 by nebylo zachova´no usporˇa´da´nı´ a pro E > 450 by prvnı´ zˇena nesla veˇtsˇ´ı ztra´tu nezˇ druhe´ dveˇ.1 Konzistentnı´ rˇesˇenı´ pak vypada´ takto: Pro 0 ≤ E < 3d1 /2 se pozu˚stalost deˇlı´ na rovne´ dı´ly, pro 3d1 /2 ≤ E ≤ D − 3d1 /2 probı´ha´ rozdeˇlenı´ na za´kladeˇ vy´sˇe uvedene´ho koalicˇnı´ho principu, pro D − 3d1 /2 < E ≤ D se deˇlı´ ztra´ty na rovne´ dı´ly. Tento postup lze indukcı´ zobecnit na n veˇrˇitelu˚ a lze doka´zat, zˇe koalicˇnı´ proces vede ke konzistentnı´mu rˇesˇenı´ pro vsˇechny proble´my bankrotu.
1
Naprˇ´ıklad pro E = 100 bychom obdrzˇeli (50, 25, 25), pro E = 500 by vysˇlo (50, 175, 275).
JJ x II 412
4. zdu˚vodneˇnı´: Teorie kooperativnı´ch her Poslednı´ zdu˚vodneˇnı´ je zalozˇeno na soucˇasne´ teorii kooperativnı´ch her a je zajı´mave´ tı´m, zˇe ukazuje, zˇe dnesˇnı´ matematicke´ rˇesˇenı´ vede ke stejne´mu vy´sledku jako vy´sˇe naznacˇene´ filozoficke´ cˇi eticke´ u´vahy zalozˇene´ na talmudicky´ch principech. Nukleolus odpovı´dajı´cı´ hry s charakteristickou funkcı´ vE,d (S) := (E − d(N \ S))+ ,
kde (α)+ := Max (α, 0)
se ve vsˇech prˇ´ıpadech shoduje s rˇesˇenı´m uvedeny´m v Talmudu.
JJ x II 413
d1 = 100, d2 = 200, d3 = 300 E=100 v(1) = v(2) = v(3) = 0, v(1, 2) = v(1, 3) = v(2, 3) = 0, v(1, 2, 3) = 100 Imputace:
ai ≥ 0, a1 + a2 + a3 = 100
Ja´dro: ai ≥ 0, a1 + a2 ≥ 0, a1 + a3 ≥ 0, a2 + a3 ≥ 0, a1 + a2 + a3 = 100 100 100 100 Shapley: H= , , 3 3 3
JJ x II 414
Nukleolus: e(a) = (−a1 , −a2 , −a3 , −a1 − a2 , −a1 − a3 , −a2 − a3 , 100 − a1 − a2 − a3 ) f (a) = (0, −ai , −aj , −ak , . . . )
a1 + a2 + a3= 1
min.
a1 = a2 = a3 =
a1
a1 a2
100 3
a2 a3
a3 a1 + a2 + a3 = 100
100 200 300 Proporciona´lnı´ deˇlenı´ E : , , 6 6 6 100 200 300 100 100 100 0, − ,− ,− , . . . >lex 0, − ,− ,− ,... 6 6 6 3 3 3
JJ x II 415
E=200 v(1) = v(2) = v(3) = v(1, 2) = v(1, 3) = 0, v(2, 3) = 100, v(1, 2, 3) = 200 Imputace: ai ≥ 0, a1 + a2 + a3 = 200 Ja´dro: ai ≥ 0, a1 + a2 ≥ 0, a1 + a3 ≥ 0, a2 + a3 ≥ 100, a1 + a2 + a3 = 200 100 250 250 Shapley: H= , , 3 3 3 Nukleolus: e(a) = (−a1 , −a2 , −a3 , −a1 − a2 , −a1 − a3 , 100 − a2 − a3 , 0) f (a) = (0, −a1 , a1 − 100, −a2 , −a3 , −a1 − a2 , −a1 − a3 ) min.
a1 = 50, a2 = a3 = 75
JJ x II 416
y
y
y
y = a1 -100 50 0
y = a3 -200
y = a2 -200 100
100 a2
200
100
0
a2
200
0
a3
50 -100
-100
-100
y = -a1 y = -a2 -200
y = -a3 -200
a2 + a3 = 150
JJ x II 417
E=300 v(1) = v(2) = v(3) = v(1, 2) = 0, v(1, 3) = 100, v(2, 3) = 200, v(1, 2, 3) = 300 Imputace: ai ≥ 0, a1 + a2 + a3 = 300 Ja´dro: ai ≥ 0, a1 + a2 ≥ 0, a1 + a3 ≥ 100, a2 + a3 ≥ 200, a1 + a2 + a3 = 300 Shapley:
H = (50, 100, 150)
Nucleolus: e(a) = (−a1 , −a2 , −a3 , −a1 − a2 , 100 − a1 − a3 , 200 − a2 − a3 , 0) f (a) = (0, −a1 , a1 − 100, −a2 , a2 − 200, −a3 , a3 − 300) min.
a1 = 50, a2 = 100, a3 = 150
JJ x II 418
y
y
y = a1 -100
y y = a2 -200
50 0
100
100 a2
y
2
150
200
0
= a -E
a2
0
a3
50 -100 y = -a1
-100 y = -a2
-150 y = -a3
-200
y = a3 -300 -300
JJ x II 419
