2
HRA V EXPLICITNI´M TVARU
JJ x II 59
☛ Prˇ´ıklad 1 – Hra Nim. Uvazˇujme jednoduchou hru, kdy dva hra´cˇi – oznacˇme je cˇı´sly 1, 2 – majı´ prˇed sebou dveˇ hroma´dky, z nichzˇ kazˇda´ je tvorˇena dveˇma fazolemi. Hra´cˇ 1 musı´ vzı´t z jedne´ hroma´dky jednu nebo dveˇ fazole, fazole se nevracejı´ zpeˇt. Potom je na rˇadeˇ hra´cˇ 2, ktery´ take´ musı´ vzı´t z jedne´ hroma´dky jednu nebo dveˇ fazole. Takto se hra´cˇi strˇ´ıdajı´, azˇ jeden z nich vezme poslednı´ fazoli – a ten prohra´va´. Pokud byste si mohli vybrat, zda budete zacˇı´nat, cˇi budete-li hra´cˇem 2, pro co byste se rozhodli?
JJ x II 60
Vsˇechny mozˇne´ situace, ktere´ ve hrˇe mohou nastat, lze zna´zornit pomocı´ stromu hry:
Hráè 1
Hráè 2
0
0
Hráè 1
0
0
00 1 vyhrává
Hráè 2
0
0
00
2 vyhrává
2 vyhrává
00 1 vyhrává
00
00 2 vyhrává
00 1 vyhrává
JJ x II 61
Hráè 1
Hráè 2
0
0
Hráè 1
0
0
00 1 vyhrává
Hráè 2
0
0
00
2 vyhrává
2 vyhrává
00 1 vyhrává
00
00 2 vyhrává
00 1 vyhrává
Ze stromu hry je patrne´, zˇe at’ zvolı´ prvnı´ hra´cˇ jakoukoli strategii, druhy´ mu˚zˇe zvolit takovou strategii, ktera´ jej dovede k vı´teˇzstvı´.
JJ x II 62
HRA V EXPLICITNI´M TVARU Matematicky´ model rozhodovacı´ situace, v nı´zˇ rozhodnutı´ jednotlivy´ch hra´cˇu˚ probı´ha´ ve formeˇ postupneˇ prova´deˇny´ch tahu˚ (etap) Strom hry . . . zachycuje vsˇechny situace, ktere´ ve hrˇe mohou nastat. Kazˇde´ situaci odpovı´da´ jeden uzel, z kazˇde´ho uzlu vycha´zı´ urcˇity´ pocˇet hran odpovı´dajı´cı´ch mozˇny´m rozhodnutı´m, tzv. tahu˚m dane´ho hra´cˇe. Jestlizˇe se hra´cˇ, ktery´ je na rˇadeˇ, rozhodne pro neˇjaky´ tah, navodı´ novou situaci, v nı´zˇ se rozhoduje druhy´ hra´cˇ – te´to nove´ situaci opeˇt odpovı´da´ jisty´ uzel stromu spojeny´ s prˇedchozı´m hranou. Prˇi zna´zornˇova´nı´ se veˇtsˇinou postupuje ve smeˇru shora dolu˚ (poprˇ. zleva doprava) a pravidelneˇ se strˇ´ıdajı´ uzly, v nichzˇ se rozhoduje prvnı´ hra´cˇ, a uzly, v nichzˇ se rozhoduje druhy´ hra´cˇ. Hra = soubor pravidel Partie hry = jedna realizace hry
JJ x II 63
Pra´veˇ jeden uzel ma´ tu vlastnost, zˇe do neˇj nevcha´zı´ zˇa´dna´ hrana; takovy´ uzel se nazy´va´ pocˇa´tecˇnı´ uzel nebo take´ korˇen stromu. Da´le jsou zde uzly, z nichzˇ zˇa´dna´ hrana nevycha´zı´; tyto uzly se nazy´vajı´ koncove´ a odpovı´dajı´ pozicı´m, kdy je rozhodnuto o vy´sledku a hra koncˇı´. ☛ Prˇ´ıklad 2 – Hra Nim – obmeˇna Ve hrˇe Nim mı´sto dvou hroma´dek uvazˇujme trˇi hroma´dky po dvou fazolı´ch, pravidla jsou jinak stejna´. Ktery´ hra´cˇ ma´ nynı´ zarucˇenou vy´hru? Rˇesˇenı´. Na´vod: Prvnı´ hra´cˇ mu˚zˇe na zacˇa´tku odebrat jednu hroma´dku a tı´m postavil protihra´cˇe do pozice hra´cˇe cˇ. 1 v prˇedchozı´ varianteˇ se dveˇma hroma´dkami.
JJ x II 64
☛ Prˇ´ıklad 3 – Hlasova´nı´ o platech Trˇi za´konoda´rci hlasujı´ o tom, zda majı´ zvy´sˇit sve´ platy. Vsˇichni trˇi si zvy´sˇenı´ prˇejı´, za´rovenˇ vsˇak kazˇde´ho z nich v prˇ´ıpadeˇ hlasova´nı´ ”pro” cˇeka´ ztra´ta u volicˇu˚ v hodnoteˇ c. Prospeˇch ze zvy´sˇenı´ b prˇevysˇuje ztra´tu c, b > c. Hlasujı´-li postupneˇ a otevrˇeneˇ, je lepsˇ´ı volit jako prvnı´ nebo jako poslednı´? Kdo volı´ jako poslednı´, vidı´, jaka´ je situace a mu˚zˇe prˇ´ıpadneˇ rozhodnout o tom, zda zvy´sˇenı´ projde cˇi nikoli. Je to tedy nejvy´hodneˇjsˇ´ı? Rˇesˇenı´. Na´vod: Situaci si mu˚zˇeme zna´zornit na´sledujı´cı´m obra´zkem: 1 N
Y
2
2 Y
N
Y
3
3
3
Y
N
Y
N 3
Y
N
Y
N
N
(0
(0
(0
(b
(-
(b
(b
(b
,0
,0
,-
,0
,-
c,
)
c)
,b
0)
-c
,b
-c
-c
0)
,b
,b
,b
0,
,b
c,
-c
-c
-c
-c
-c
,b
,b
)
)
)
-c )
JJ x II 65
1 N
Y
2
2 Y
N
Y
3 3 (b-c, b-c, b) (b-c, b, b-c)
3 (b, b-c, b-c)
N 3 (0, 0, 0)
1 Y 2 (b-c, b, b-c)
N 2 (b, b-c, b-c)
Zpeˇtna´ indukce: na za´kladeˇ prˇedvı´da´nı´ budoucı´ho vy´voje jsou vybı´ra´ny nejvhodneˇjsˇ´ı alternativy na zacˇa´tku rozhodova´nı´
JJ x II 66
☛ Prˇ´ıklad 4 – Dvoukolova´ volba do vy´boru Martin, Petr a Pavel jsou cˇleny vy´boru velmi exkluzivnı´ Spolecˇnosti burzovnı´ch makle´rˇu˚. Za´veˇrecˇny´m bodem jednoho jejich dopolednı´ho jedna´nı´ je na´vrh, aby Alice byla prˇijata za nove´ho cˇlena. V na´vrhu chybeˇla zmı´nka o jine´m mozˇne´m kandida´tovi, Davidovi, a tak se objevil pozmeˇnˇovacı´ na´vrh, aby Alice byla nahrazena Davidem. Podle jednacı´ch pravidel je trˇeba hlasovat nejprve o pozmeˇnˇovacı´m na´vrhu, tj. ma´-li David nahradit Alici. Potom se hlasuje o tom, zda bude vı´teˇz prˇijat, cˇi zda nebude prˇijat nikdo. Preference jednotlivy´ch cˇlenu˚ vy´boru jsou na´sledujı´cı´:
JJ x II 67
Pokud by vsˇichni volili v obou kolech pouze podle svy´ch preferencı´, pak by volby probeˇhly takto: Prˇi volbeˇ mezi Alicı´ a Davidem by zvı´teˇzila Alice, protozˇe jak Martin, tak Petr ji uprˇednostnˇujı´ prˇed Davidem – Pavel by tak byl prˇehlasova´n. V druhe´m kole by Alice zı´skala hlasy od Martina a Pavla, nebot’ je v zˇebrˇ´ıcˇku jejich hodnot vy´sˇe nezˇ „nikdo“, a stala by se tak vı´teˇzem voleb.
JJ x II 68
Bude-li vsˇak Petr prozı´ravy´, zvolı´ v prvnı´m kole Davida, protozˇe vidı´, zˇe v druhe´m kole v tom prˇ´ıpadeˇ zvı´teˇzı´ varianta „nikdo“, cozˇ je pro neˇj ta nejvı´taneˇjsˇ´ı mozˇnost. Pavel by ovsˇem mohl prˇedvı´dat, zˇe Petr bude tı´mto zpu˚sobem taktizovat, a mohl by rovneˇzˇ volit strategicky: v prvnı´m kole by mı´sto Davida zvolil Alici, ktera´ by pak zvı´teˇzila, cozˇ Pavel preferuje vı´ce nezˇ variantu „nikdo“. Jiny´mi slovy, z obra´zku cˇi ze zpeˇtne´ indukce je patrne´, zˇe prvnı´ kolo je v podstateˇ rozhodova´nı´ mezi Alicı´ a niky´m, kterˇ´ı by zvı´teˇzili v druhe´m kole v jednotlivy´ch prˇ´ıpadech. Protozˇe Alice je prˇed niky´m preferova´na u Martina a Pavla, zvı´teˇzı´.
JJ x II 69
☛ Prˇ´ıklad 5 – Hra Hex Hra Hex se hraje na desce sesta´vajı´cı´ z n2 sˇestiu´helnı´ku˚ usporˇa´dany´ch do rovnobeˇzˇnı´ka:
JJ x II 70
Hra´cˇi se strˇ´ıdajı´ jeden po druhe´m. V kazˇde´m tahu hra´cˇ oznacˇı´ volny´ sˇestiu´helnı´k svy´m symbolem: hra´cˇ I krouzˇkem, hra´cˇ II krˇ´ızˇkem. Oznacˇeny´ sˇestiu´helnı´k se stane „zabrany´m u´zemı´m“ toho hra´cˇe, ktery´ jej oznacˇil. Na zacˇa´tku sesta´vajı´ teritoria obou hra´cˇu˚ vzˇdy ze dvou protilehly´ch stran desky. Vı´teˇzem je ten, kdo jako prvnı´ spojı´ sve´ strany desky souvisly´m rˇeteˇzem sˇestiu´helnı´ku˚ oznacˇeny´mi vlastnı´m symbolem. Naprˇ´ıklad na na´sledujı´cı´m obra´zku je vı´teˇzem hra´cˇ II:
JJ x II 71
Naprˇ´ıklad na na´sledujı´cı´m obra´zku je vı´teˇzem hra´cˇ II:
JJ x II 72
Lze doka´zat: ➥ Hex nemu˚zˇe skoncˇit remı´zou Je-li kazˇdy´ hexagon oznacˇen krouzˇkem nebo krˇ´ızˇkem, pak lze doka´zat, zˇe jedna z dvojice proteˇjsˇ´ıch stran musı´ by´t spojena. ➥ Hra´cˇ I ma´ vı´teˇznou strategii (ale nenı´ zna´mo jakou) Z Zermelovy veˇty lze vyvodit, zˇe jeden z hra´cˇu˚ ma´ vı´teˇznou strategii, sporem pak doka´zˇeme, zˇe to nemu˚zˇe by´t hra´cˇ II.
Veˇta (Zermelo). Necht’ T je libovolna´ mnozˇina vy´sledku˚ v konecˇne´ hrˇe dvou hra´cˇu˚ s u´plnou informacı´, bez na´hodny´ch tahu˚. Pak bud’ hra´cˇ I mu˚zˇe zajistit vy´sledek z mnozˇiny T nebo hra´cˇ II mu˚zˇe zajistit vy´sledek z doplnˇku ∼ T.
JJ x II 73
☛ Prˇ´ıklad 6 – Gangsterˇi ve meˇsteˇ Hernı´ deska prˇedstavuje sı´t’ ulic v centru meˇsta. Hra´cˇi I, resp. II prˇedstavuje gangstersky´ gang. Hra´cˇ I ma´ pod kontrolou oblasti na severu a na jihu meˇsta, hra´cˇ II na vy´chodeˇ a na za´padeˇ. Uzly v pla´nu zna´zornˇujı´ krˇizˇovatky. Hra´cˇi se strˇ´ıdajı´ v oznacˇova´nı´ uzlu˚, ktere´ dosud nebyly oznacˇeny. Hra´cˇ I pouzˇ´ıva´ krouzˇky, hra´cˇ II krˇ´ızˇky. Hra´cˇ, ktere´mu se podarˇ´ı oznacˇit oba konce ulice, ma´ tuto ulici pod kontrolou. Hra´cˇ I vı´teˇzı´, spojı´-li sever a jih cestou, kterou ma´ pod kontrolou. Podobneˇ hra´cˇ II vı´teˇzı´, spojı´-li vy´chod a za´pad.
Ukazˇte, zˇe hra je ekvivalentnı´ s hrou Hex.
JJ x II 74
☛ Prˇ´ıklad 7. Sofistikovana´ volba v soudnı´ch syste´mech Uvazˇujme trˇi pra´vnı´ syste´my, v nichzˇ vzˇdy rozhodujı´ trˇi soudci: 1. Status quo (pouzˇ´ıvany´ naprˇ. v USA): Nejprve se rozhoduje o vineˇ cˇi nevineˇ obzˇalovane´ho, v prˇ´ıpadeˇ viny se da´le rozhoduje o trestu. ˇ ´ımska´ tradice: 2. R Po prˇedlozˇenı´ du˚kazu˚ se zacˇne s hlasova´nı´m sestupneˇ od nejprˇ´ısneˇjsˇ´ıho trestu k nejmı´rneˇjsˇ´ımu, poprˇ. k propusˇteˇnı´ (naprˇ. zda ulozˇit trest smrti; pokud ne, zda dozˇivotı´, atd.). 3. Mandatornı´ soud: Nejprve se urcˇı´ trest pro dany´ zlocˇin, pak se urcˇı´, zda ma´ by´t obzˇalovany´ uzna´n vinny´m.
JJ x II 75
Uvazˇujme pro jednoduchost trˇi mozˇne´ vy´sledky, trest smrti, dozˇivotnı´ veˇzenı´, propusˇteˇnı´, a na´sledujı´cı´ preference jednotlivy´ch soudcu˚: Porˇadı´
Soudce A
Soudce B
Soudce C
1.
trest smrti
dozˇivotı´
propusˇteˇnı´
2.
dozˇivotı´
propusˇteˇnı´
trest smrti
3.
propusˇteˇnı´
trest smrti
dozˇivotı´
JJ x II 76
1. Status quo V prvnı´m kole se hlasuje o vineˇ cˇi nevineˇ; prˇi uprˇ´ımne´m hlasova´nı´ by zvı´teˇzilo „vinen“ (soudci A, B), v druhe´m kole, prˇi rozhodova´nı´ mezi trestem smrti a dozˇivotı´m, by zvı´teˇzil trest smrti (soudci A, C). Prvnı´ kolo je tedy v podstateˇ hlasova´nı´m mezi propusˇteˇnı´m a trestem smrti – prˇi sofistikovane´ volbeˇ, tedy budou-li soudci uvazˇovat raciona´lneˇ a budou prˇedvı´dat, co se stane v druhe´m kole, proto v prvnı´m kole zvı´teˇzı´ propusˇteˇnı´ (kromeˇ soudce C da´ v prvnı´m kole hlas propusˇteˇnı´ i B, nebot’ v opacˇne´m prˇ´ıpadeˇ by druhe´ kolo vedlo k jeho nejme´neˇ preferovane´ varianteˇ).
JJ x II 77
1. Status Quo:
Soudce A Soudce B
+ # Y
1. kolo
Trest smrti nebo doživotí
Trest smrti
Y + #
Vinen nebo nevinen Vinen
2. kolo
Soudce C
# Y +
Nevinen
Propuštění
Doživotí
JJ x II 78
1. Status Quo:
Soudce A Soudce B
+ # Y
Vinen A, B
Trest smrti nebo doživotí A, C
Trest smrti
Y + #
Vinen nebo nevinen
1. kolo
2. kolo
Soudce C
# Y +
Nevinen C
Propuštění
B
Doživotí
JJ x II 79
1. Status Quo:
Soudce A Soudce B
+ # Y
Vinen A, B
Trest smrti nebo doživotí A, C
Trest smrti
Y + #
Vinen nebo nevinen
1. kolo
2. kolo
Soudce C
# Y +
Nevinen C
Propuštění
B
Doživotí
JJ x II 80
1. Status Quo:
Soudce A Soudce B
+ # Y
Vinen A, B
Trest smrti nebo doživotí A, C
Trest smrti
Y + #
Vinen nebo nevinen
1. kolo
2. kolo
Soudce C
# Y +
Nevinen C
Propuštění
B
Doživotí
JJ x II 81
1. Status Quo:
Soudce A Soudce B
+ # Y
Vinen A
Trest smrti nebo doživotí A, C
Trest smrti
Y + #
Vinen nebo nevinen
1. kolo
2. kolo
Soudce C
# Y +
Nevinen C, B
Propuštění
B
Doživotí
JJ x II 82
ˇ ´ımska´ tradice 2. R V prvnı´m kole se hlasuje o nejprˇ´ısneˇjsˇ´ım trestu, tj. zda ulozˇit trest smrti cˇi nikoli. Pokud ano, je trest vykona´n, pokud ne, nastane druhe´ kolo, v neˇmzˇ se bude hlasovat, zda dozˇivotı´ cˇi propusˇteˇnı´. Protozˇe v druhe´m kole by zvı´teˇzilo dozˇivotı´ (soudci A, B), je prvnı´ kolo v podstateˇ hlasova´nı´m mezi trestem smrti a dozˇivotı´m – prˇi sofistikovane´ volbeˇ proto v prvnı´m kole zvı´teˇzı´ trest smrti (kromeˇ soudce A da´ v prvnı´m kole hlas trestu smrti i C, nebot’ v opacˇne´m prˇ´ıpadeˇ by druhe´ kolo vedlo k jeho nejme´neˇ preferovane´ varianteˇ).
JJ x II 83
2. Římská tradice:
Soudce A Soudce B
+ # Y
Upřímná volba:
Trest smrti
1. kolo
Ano A 2. kolo
Soudce C
Y + #
# Y +
Trest smrti
Ne B, C
Doživotí nebo propuštění A, B
Doživotí
C
Propuštění
JJ x II 84
2. Římská tradice:
Soudce A Soudce B Soudce C
+ # Y
Sofistikovaná volba:
Trest smrti
1. kolo
Ano A 2. kolo
Y + #
# Y +
Trest smrti
Ne B, C
Doživotí nebo propuštění A, B
Doživotí
C
Propuštění
JJ x II 85
2. Římská tradice:
Soudce A Soudce B Soudce C
+ # Y
Sofistikovaná volba:
Trest smrti
1. kolo
Ano A, C 2. kolo
Y + #
# Y +
Trest smrti
Ne B
Doživotí nebo propuštění A, B
Doživotí
C
Propuštění
JJ x II 86
3. Mandatornı´ syste´m V prvnı´m kole se hlasuje o trestu za dany´ zlocˇin, tj. zda ulozˇit trest smrti cˇi dozˇivotı´. V druhe´m kole se pak hlasuje o tom, zda dany´ trest ulozˇit cˇi nikoli (tj. propustit). Prˇi rozhodova´nı´ mezi trestem smrti a propusˇteˇnı´m by zvı´teˇzilo propusˇteˇnı´ (B, C), prˇi rozhodova´nı´ mezi dozˇivotı´m a propusˇteˇnı´m by zvı´teˇzilo dozˇivotı´ (A, B). Prvnı´ kolo je tedy rozhodova´nı´m mezi propusˇteˇnı´m a dozˇivotı´m, takzˇe veˇzenˇ bude odsouzen na dozˇivotı´ (A da´ v prvnı´m kole hlas radeˇji dozˇivotı´, nezˇ aby byl propusˇteˇn).
JJ x II 87
3. Mandatorní systém: Upřímná volba:
1. kolo
A, C
Trest smrti nebo propuštění A
Trest smrti
+ # Y
Soudce C
Y + #
# Y +
Trest smrti nebo doživotí Trest smrti
2. kolo
Soudce A Soudce B
B, C
Propuštění
Doživotí B
Doživotí nebo propuštění A, B
Doživotí
C
Propuštění
JJ x II 88
3. Mandatorní systém: Sofistikovaná volba:
1. kolo
A, C
Trest smrti nebo propuštění A
Trest smrti
+ # Y
Soudce C
Y + #
# Y +
Trest smrti nebo doživotí Trest smrti
2. kolo
Soudce A Soudce B
B, C
Propuštění
Doživotí B
Doživotí nebo propuštění A, B
Doživotí
C
Propuštění
JJ x II 89
3. Mandatorní systém: Sofistikovaná volba:
1. kolo
C
Trest smrti nebo propuštění A
Trest smrti
+ # Y
Soudce C
Y + #
# Y +
Trest smrti nebo doživotí Trest smrti
2. kolo
Soudce A Soudce B
B, C
Propuštění
Doživotí A, B
Doživotí nebo propuštění A, B
Doživotí
C
Propuštění
Tento prˇ´ıklad velmi na´zorneˇ ilustruje, jak se pouhou zmeˇnou volebnı´ch pravidel mu˚zˇe vy´sledek hlasova´nı´ zcela za´sadneˇ zmeˇnit: prˇi stejny´ch preferencı´ch soudcu˚ by byl obzˇalovany´ v jednom syste´mu propusˇteˇn, v jine´m popraven a v jine´m odsouzen k dozˇivotnı´mu zˇala´rˇi. JJ x II 90
