E-kniha: Pokročilá teorie her ve světě kolem nás – Martin Chvoj

POKROČILÁ TEORIE HER

ve světě kolem nás

Martin Chvoj

Martin

Chvoj

Na trhu ojedinělá kniha seznamuje čtenáře s evolučními hrami, diferenciálními

hrami, stati sti ckými hrami a metahrami, vysvětluje základní myšlenkové toky

a koncepty, a ilustruje je na mnoha, většinou původních příkladech. Všechny

tyto hry jsou v české literatuře velmi špatně dohledatelné a neexistuje u nás

publikace, která by je rozumně shrnovala. Autor nejprve stručně představuje

základní teorii her, která pak slouží jako odrazový můstek k zajímavějším druhům

her, a v závěru knihy vede polemiku o použitelnosti teorie her v běžném životě.

Publikace je určena zejména studentům vysokých škol, kteří prošli základním

kurzem teorie her a chtějí se o této disciplíně dozvědět více. Kniha klade na čte

náře nároky zběžné znalosti základů teorie her, logiky, teorie pravděpodobnosti

a matemati cké analýzy. Každá kapitola obsahuje dvě části : matemati ckou

a nematemati ckou. Matemati cká část tvoří zhruba dvě třeti ny kapitoly a je v ní vyložena látka s matemati ckou korektností doplněná příklady. Nematemati cká část shrnuje matemati ckou část řečí, která nepoužívá matemati cké výrazy,

a měla by sloužit čtenářům, jež nemají hlubší matemati cké znalosti , aby se

v látce zorientovali a pochopili hlavní myšlenky.

Kniha si klade tyto cíle:

• Seznámit čtenáře s pokročilými druhy her, jež se v základních

vysokoškolských kurzech běžně nevyskytují • Ukázat význam konceptu Nashovy rovnováhy, jenž provází teorii her skrz všechny kapitoly • Naučit pohlížet na situace kolem nás v pojmech teorie her a přemýšlet o jejich řešení • Pomoci pochopit matemati ckou složitost modelů teorie her • Defi novat hry skrz čtyři základní pojmy: hra, hráči, strategie a výplata Řekli o knize: „Kniha je napsána čti vě a nápaditě. Zavedení dvou simultánních výkladů látky, jeden matemati cky korektní a druhý popularizující, je zajímavým nápadem. Podle mého názoru se jedná o ti tul, který na českém trhu chybí. Domnívám se, že si kniha najde své čtenáře jak z odborné, tak i laické veřejnosti .“

Doc. RNDr. Petr Lachout, CSc.

MFF UK v Praze, katedra pravděpodobnosti a matemati cké stati sti ky

Grada Publishing, a.s.

U Průhonu 22, 170 00 Praha 7

tel.: +420 234 264 401, fax: +420 234 264 400

e-mail: obchod@grada.cz

www.grada.cz

Grada Publishing

Martin

Chvoj

Název kapitoly 1

Upozornění pro čtenáře a uživatele této knihy

Všechna práva vyhrazena. Žádná část této tištěné či elektronické knihy nesmí být reprodukována

a šířena v papírové, elektronické či jiné podobě bez předchozího písemného souhlasu naklada

tele. Neoprávněné užití této knihy bude trestně stíháno. RNDr. Martin Chvoj, MBA Pokročilá teorie her ve světě kolem nás TIRÁŽ TIŠTĚNÉ PUBLIKACE: Vydala Grada Publishing, a.s. U Průhonu 22, 170 00 Praha 7 tel.: +420 234 264 401, fax: +420 234 264 400 www.grada.cz jako svou 5095. publikaci Odborný recenzent: Doc. RNDr. Petr Lachout, CSc. Odpovědný redaktor Petr Somogyi Sazba RNDr. Martin Chvoj, MBA Počet stran 232 První vydání, Praha 2013 Vytiska Tiskárna PROTISK, s.r.o., České Budějovice © Grada Publishing, a.s., 2013 Kresba na obálce © Bc. Eliška Sedláčková Cover Design © Grada Publishing, a.s., 2013 ISBN 978-80-247-4620-3 ELEKTRONICKÉ PUBLIKACE: ISBN 978-80-247-8393-2 (ve formátu PDF)

Obsah 5

Obsah

OBSAH .................................................................................................................................5

PODĚKOVÁNÍ .......................................................................................................................7

O AUTOROVI ........................................................................................................................9

PŘEDMLUVA ...................................................................................................................... 11

ÚVOD DO TEORIE HER ....................................................................................................... 15

1.1 KLASICKÁ TEORIE HER ......................................................................................................... 15

1.2 UŽITEK A RACIONÁLNÍ CHOVÁNÍ ............................................................................................ 23

1.2.1 Užitek............................................................................................................................... 23

1.2.2 Racionální chování......................................................................................................... 25

1.3 KOOPERATIVNÍ HRY ............................................................................................................ 28

1.4 VĚZŇOVO DILEMA .............................................................................................................. 32

1.5 NEMATEMATICKÉ SHRNUTÍ .................................................................................................. 34

EVOLUČNÍ HRY ................................................................................................................... 41

2.1 MOTIVACE EVOLUČNÍCH HER ............................................................................................... 41

2.2 STATICKÁ ANALÝZA ............................................................................................................ 42

2.3 DYNAMICKÁ ANALÝZA ........................................................................................................ 48

2.4 ASYMETRICKÉ HRY ............................................................................................................. 55

2.4.1 Asymetrické hry využívající behaviorální strategie.................................................... 56

2.4.2 Alternativní přístup k asymetrickým hrám................................................................. 60

2.5 NEMATEMATICKÉ SHRNUTÍ .................................................................................................. 65

PROBLÉM REGULACE ......................................................................................................... 75

3.1 PROBLÉM OPTIMÁLNÍ REGULACE ........................................................................................... 75

3.1.1 Formalizace problému regulace................................................................................... 76

3.1.2 Typy regulací................................................................................................................... 81

3.2 VARIAČNÍ POČET ................................................................................................................ 82

3.2.1 Nutné podmínky............................................................................................................. 84

3.3 PRINCIP MAXIMA ............................................................................................................... 88

3.3.1 Věta o principu maxima................................................................................................ 89

3.4 HAMILTON-JACOBI-BELLMANOVA ROVNICE ............................................................................ 93

3.5 METODY ŘEŠENÍ, PŘÍKLAD A MOŽNÉ TVARY VÝSLEDKU ............................................................... 96

3.5.1 Poznámka k metodám řešení optimalizačních úloh.................................................. 96

3.5.2 Možné tvary výsledku.................................................................................................... 99

3.6 NEMATEMATICKÉ SHRNUTÍ ................................................................................................ 100

6 Pokročilá teorie her ve světě kolem nás

DIFERENCIÁLNÍ HRY ......................................................................................................... 104

4.1 ÚVOD DO DIFERENCIÁLNÍCH HER ......................................................................................... 104

4.2 ROVNOVÁHY V DIFERENCIÁLNÍCH HRÁCH .............................................................................. 106

4.3 TYPY DIFERENCIÁLNÍCH HER ............................................................................................... 109

4.3.1 Hry o pronásledování................................................................................................... 109

4.3.2 Stochastické diferenciální hry..................................................................................... 114

4.3.3 Nemarkovovy hry......................................................................................................... 116

4.4 ILUSTRAČNÍ PŘÍKLAD DIFERENCIÁLNÍCH HER ........................................................................... 120

4.5 NEMATEMATICKÉ SHRNUTÍ ................................................................................................ 126

STATISTICKÉ HRY ............................................................................................................. 136

5.1 DEFINICE A MOTIVACE STATISTICKÝCH HER ............................................................................ 136

5.2 BAYESOVSKÉ HRY ............................................................................................................. 143

5.3 NEMATEMATICKÉ SHRNUTÍ ................................................................................................ 154

METAHRY ........................................................................................................................ 161

6.1 VYMEZENÍ POJMU „METAHRA“ .......................................................................................... 161

6.2 DEFINICE A ZNAČENÍ METAHER ........................................................................................... 162

6.3 METARACIONÁLNÍ STRATEGIE, METAROVNOVÁHA .................................................................. 165

6.4 CHARAKTERIZACE METARACIONÁLNÍCH STRATEGIÍ .................................................................. 172

6.5 POLEMIKA NA OBHAJOBU METAHER .................................................................................... 174

6.6 NEMATEMATICKÉ SHRNUTÍ ................................................................................................ 179

SUN-C' A TI DRUZÍ ............................................................................................................ 190

7.1 TEORIE HER JAKO VĚDA ..................................................................................................... 190

7.2 TEORIE HER JAKO POMŮCKA............................................................................................... 191

7.2.1 Hry o pronásledování................................................................................................... 192

7.2.2 Rozděl a panuj............................................................................................................... 195

7.2.3 Omezená informace..................................................................................................... 196

7.2.4 Využití omezené informace v politice........................................................................ 200

7.3 TEORIE HER JAKO ZÁTĚŽ .................................................................................................... 202

APENDIX .......................................................................................................................... 204

A.1 TEORIE MÍRY .................................................................................................................. 204

A.2 TEORIE PRAVDĚPODOBNOSTI ............................................................................................. 210

A.3 JINÉ POUŽITÉ POJMY ........................................................................................................ 222

LITERATURA ..................................................................................................................... 225

SEZNAM POUŽITÝCH SYMBOLŮ ....................................................................................... 227

7

Poděkování

Rád bych na tomto místě poděkoval svému otci, teoretickému fyzikovi doc. RNDr. Zdeňku

Chvojovi, DrSc., jenž mě ve studiu matematiky již od útlého věku vytrvale podporoval a tato

publikace, ke které mi dal mnoho užitečných rad, nechť je pro něj jistou zárukou, že jeho

snaha nebyla marná. Zvláštní poděkování patří mému učiteli z Matematicko-fyzikální fakulty

Univerzity Karlovy doc. RNDr. Petru Lachoutovi, CSc., bez jehož odborných připomí

nek a kontroly zejména matematické korektnosti by tato kniha nemohla vzniknout. Teorie her

je matematickou disciplínou, což běžně nepatří k nejlákavější četbě, proto bych rád poděkoval

své blízké kamarádce Andree Fuxové za stylistickou korekturu a její příspěvky k čitelnosti

často strohého technického textu. Tato kniha je určená především studentům aplikované ma

tematiky. Za poznámky, jež vedly k přístupnosti knihy cílové skupině, vděčím své kamarádce

a bývalé kolegyni Ing. Márii Bolcárové. Také bych rád poděkoval Bc. Elišce Sedláčkové, jejíž

pevná ruka ozdobila každou kapitolu krásnou a výstižnou ilustrací.

Knihu věnuji své matce JUDr. Blance Chvojové za její podporu a stále usměvavou povahu.

8 Pokročilá teorie her ve světě kolem nás

9

O autorovi

RNDr. Martin Chvoj, MBA

Absolvent Matematicko-fyzikální fakulty Univerzity Kar

lovy v Praze, obor finanční a pojistná matematika (RNDr.

2012) a Central European Management Institute (MBA 2013).

Pracoval tři roky jako auditor ve velké čtyřce poradenských firem. Mimo profesní život byl

aktivním členem akademického senátu, věnoval se organizování neziskových akcí pro mladé

dospělé. Teorie her ho zaujala během studia a napsal na toto téma všechny studijně významné

práce. Materiál, který v průběhu šesti let nasbíral, předává dále prostřednictvím této knihy.

10 Pokročilá teorie her ve světě kolem nás

Předmluva 11

Předmluva

V běžném životě často čelíme problémům, pro jejichž řešení potřebujeme nástroj, jenž

nám pomůže učinit správná rozhodnutí. Jedním z takových nástrojů může být matemati

ka a matematické modely. Pro mnoho lidí je však čistá matematika velmi nesrozumitel

ná a komplikovaná. Tudíž je potřeba ji nějak vhodně vyložit. Teorie her, jakožto samostatná

matematická větev, získala svou oblíbenost právě díky tomu, že dokáže interpretovat mate

matické výsledky způsobem, kterému lidé rozumějí. Dobrým příkladem je třeba slavná Na

shova věta, za kterou dostal John Nash v roce 1978 John Von Neumann Theory Prize. Tato

věta nepřináší do matematické teorie mnoho nového. Jedná se vlastně pouze o Browerovu

větu o pevném bodu aplikovanou v prostředí teorie her. Nicméně její skutečný význam spočí

vá v interpretaci. John Nash vyřkl závěr, který může být srozumitelný téměř každému, a tím

nezpochybnitelně přispěl k přitažlivosti matematiky. Od té doby bylo vymyšleno mnoho

základních modelových her, které se vyučují v řadě oborů, jako je biologie, psychologie,

vojenská strategie apod. Tyto hry bývají demonstrovány na skutečných oborových situa

cích, a tím je matematika předávána dále lidem, kteří by třeba o ni jinak zájem neměli.

Toto je pravděpodobně způsobeno pojmem „hra“, který je lidem běžně známý a vzbuzuje

představu, že nejde o náročné problémy. Nicméně teorie her pouze pohlíží na matematické

problémy z jiného úhlu, formuluje běžné úlohy svou vlastní řečí, ale výpočty na pozadí si

zachovávají veškerou matematickou náročnost. A právě proto může teorie her obsahovat

i velmi složité a pokročilé úvahy. „Klasická teorie her“, jak ji zde představíme, popisuje pře

devším jednokolové hry a rozděluje konflikty do několika jednoduchých kategorií. My se jí

budeme zabývat pouze z důvodu, že jde o neoddělitelné základy, které je potřeba popsat.

V první kapitole je, mimo úvodu do teorie her, definovaný pojem Nashovy rovnováhy, což je

stěžejní koncept rovnováhy pro většinu druhů her. Kniha se nicméně orientuje na jiné typy

her, které jsou v české literatuře podstatně méně popsané. Čtenář by se do jejich studia měl

pustit poté, co pochopí fungování a konstrukci Nashovy rovnováhy v základních hrách. Pro

tyto účely doporučuji uznávanou literaturu profesora Maňase (Maňas, 1991) nebo o něco

starší (Maňas, 1974).

Podotkněme, že se v této knize často budeme zabývat hledáním nějaké kombinace strate

gií, kterou nazveme rovnovážnou. V takové situaci hráči nemají důvod své strategie měnit.

Každá kapitola se věnuje jinému typu her, tudíž budeme definovat lehce odlišné koncepty

rovnováhy. Jak však při bližším zkoumání uvidíme, ačkoliv se mohou tyto rovnováhy zdát

v definici odlišné, v zásadě se všechny odráží od jedné a té samé myšlenky. Jde právě o již

zmíněný koncept Nashovy rovnováhy, jenž říká, že v rovnovážném stavu nemá žádný jedinec

lepší možnost než hrát rovnovážnou strategii. Mohli bychom se však ptát, proč vůbec takovou

rovnováhu hledat. Co nám o hráčích řekne? V odpovědi na tuto otázku nesmí chybět zmínka

o tom, že popisování a hledání rovnovážných bodů je nedílnou součástí jakékoliv literatury

zabývající se teorií her, proto by byl hřích zde tyto úvahy nevyložit. Z pragmatického hledis

ka však důvod pro hledání rovnováhy existovat nemusí. Empirické průzkumy nám opakovaně

dokazují, že například lidští hráči se podle rovnovážných strategií nechovají. Nicméně i když

asi nebudeme schopni přímo určit, jak se hráč bude ve hře chovat jen čistě na základě naleze

12 Pokročilá teorie her ve světě kolem nás

ní rovnovážné strategie, tak jsme schopni lépe odhadovat pravděpodobné chování hráče.

Rovnovážná strategie tak bývá dobrým nástrojem k analýze chování racionálních hráčů.

Druhá a čtvrtá kapitola se soustředí na vícekolové hry, kdy hrají hráči tutéž hru opakovaně

a mohou své strategie v dalších kolech měnit. Jednu z větví těchto vícekolových her předsta

vují tzv. evoluční hry, což jsou v zásadě vícekolové hry, do nichž je zapracován mechanizmus

inspirovaný Darwinovou evoluční teorií. Nejprve zde popisujeme evoluční hry ze statického

pohledu a definujeme koncept evolučně stabilní rovnováhy. Tím, že se hry opakují a hrají

vícekrát za sebou, je užitečné dívat se na evoluční hry také z dynamického hlediska. Zejména

nás zajímá, zda lze zavést nějaký dynamický koncept (alespoň lokální) rovnováhy. Tu nalé

záme pod pojmem asymptoticky stabilní rovnováha.

Ve čtvrté kapitole se zabýváme diferenciálními hrami. Ty se od evolučních liší především

tím, že zatímco v evolučních hrách hráči hrají konečný počet kol a čas zde vystupuje diskrét

ně (skokovitě), tak v diferenciálních hrách se vždy hraje nekonečný počet kol a čas zde vy

stupuje spojitě. Trochu nepřesně by se dalo říci, že evoluční hry jsou diskrétní verzí diferen

ciálních her. I v diferenciálních hrách lze zavést koncept rovnováhy známý jako Markovova

Nashova rovnováha, která je opět jakousi obdobou Nashovy rovnováhy z klasické teorie her.

V páté k apitole, jež nese název „statistické hry“, se vracíme k rozšíření přehledu teorie

her. Výklad je zúžen na jednokolové hry dvou hráčů: statistika a přírody, přičemž se na pro

blém díváme pouze z pohledu statistika. U přírody očekáváme, že jde o hráče, jehož volbu

strategie nemůžeme z dostupných informací spolehlivě determinovat, a proto používáme

matematický aparát z teorie pravděpodobnosti. Popisujeme situaci, kdy statistik učiní po

kus a na základě jeho výsledku se snaží pomocí Bayesovské metody odhadnout, jakou strate

gii příroda do hry zvolí.

Šestá kapitola je zároveň poslední kapitola, která popisuje matematické partie teorie her.

Věnuje se v literatuře málo popisované větvi známé jako metahry. Tento přístup se snaží

dívat na hry odlišným způsobem než předchozí hry a jeho motivace vychází z pozorování

přemýšlení lidí. Popisujeme zde situace, kdy alespoň jeden z hráčů volí své strategie až poté,

co všichni ostatní oznámili ty své. Stejný model se však skrývá i za myšlenkou, že jeden hráč

dokáže spolehlivě odhadnout volbu strategií ostatních hráčů a tudíž se chová, jako by volil

svou strategii až poslední. Právě pro tuto vlastnost jsou metahry vhodné k modelování situací,

kde jsou hráči lidé. V samotném závěru kapitoly je uvedena polemika ospravedlňující tento

přístup.

Závěrečná sedmá kapitola se vůbec nezabývá matematikou. Klademe si v ní několik

pragmatických otázek týkajících se použitelnosti teorie her v běžném životě. Ptáme se, jak lze

využít složité modely pro situace, před nimiž denně stojíme. Zda je potřeba se teorií her za

bývat a analyzovat je, nebo nám stačí pouze tradiční poučky, jak je psal Sun-c' a jemu podob

ní. Tato kapitola zároveň slouží jako doslov a shrnutí celé knihy a snaží se ukázat cestu, jak

Předmluva 13

vidět hry v situacích kolem nás. Matematická část je zde z pochopitelných důvodů zcela vy

puštěna a jediné, co zbývá, jsou praktické závěry a otázky k zamyšlení.

Na samý závěr knihy je umístěn Apendix, v němž jsou uvedeny a stroze okomentovány

matematické pojmy a závěry použité v předchozích kapitolách, u nichž nebyl prostor

k důslednému výkladu. Plné pochopení zde uvedených definicí a vět předpokládá základní

znalosti matematické analýzy a diferenciálního počtu, který je vyučován v prvních ročnících

většiny vysokých škol s matematickým zaměřením. Apendix pak doplňuje tuto látku zejména

o základy teorie míry a teorie pravděpodobnosti. Pro hlubší pochopení těchto myšlenek je

však třeba obrátit se na odbornou literaturu zaměřující se přímo na tyto oblasti matematiky.

Definice a věty uvedené v knize jsou převzaty z literatury, jež je k nalezení za apendixem.

Uvedená literatura však není míněna jako kompletní seznam všeho, co bylo o zde probíra

ných částech napsáno. Její kompletní výčet by vystačil na další menší knihu. V dobách inter

netu není ani takový seznam žádoucí. Pokud budeme brát v potaz i internetové články

a elektronické publikace, tak lze říci, že nové texty tohoto výukového a popularizačního typu

se ve světě objevují velmi často a jakýkoliv pokus o úplný seznam by velmi rychle zastaral.

Čtenář mající zájem dále rozšířit své obzory v oblasti teorie her může pokračovat ve zdrojové

literatuře uvedené v závěru, ale stejně tak dobře může zadat do internetového vyhledávače

hledaný výraz a v krátkém čase dohledat materiál, jenž ho zajímá. Jedním dechem však dodá

vám, že česky napsaných textů týkajících se pokročilých partií teorie her je v době vydání

této knihy velmi omezené množství a je tak třeba sáhnout po anglicky psané literatuře. Kniha

by neměla být chápána jako vědecká práce a nemá ambice vytvářet nové matematické závěry.

Měla by sloužit jako průvodce světem vybraných pokročilých partií teorie her. Každá kapitola

je rozdělena na dvě části, přičemž první část je primárně matematická a druhá čistě nemate

matická. Obě části vykládají to samé, ale matematická část je určena pro čtenáře, kterým

nedělá problém orientovat se v matematických symbolech a považují tyto zápisy za přehledné

a srozumitelné. Také příklady, jež jsou zde uvedené, jsou popsané jako matematické modely,

které pak dále řešíme. Naproti tomu nematematická část neobsahuje žádné exaktní definice

a věty, vše je zde vyjadřováno slovně. Výsledky jsou interpretovány a ilustrovány na příkla

dech vybraných za účelem provázání hlavní myšlenky probírané kapitoly s praktickými situa

cemi z běžného života.

Výběr kapitol je proveden podle následující koncepce. V úvodní kapitole jsou představeny

hry, jež jsou považovány za absolutní základ. Jde však pouze jen o jeho stručné připomenutí,

abychom získali nějaký odrazový můstek pro zajímavější a složitější partie teorie her. Histo

ricky jde také o první modely, které se začaly nazývat hrami. Tyto matematicky jednoduché

hry jsou však jen obtížně použitelné, pokud bychom chtěli modelovat běžné situace nějak

přesněji. Většinou když v životě volíme svá rozhodnutí, tak přemýšlíme dopředu a zvažujeme

následky svých činů. Stejně tak přemýšlí i naši protihráči a všichni tak volí své strategie

s vědomím, že touto hrou svět nekončí. Zdá se tedy, že bychom se měli zabývat i vícekolo

vými hrami, které vnáší do teorie čas. Vývoj her v čase je tak první krok k pokročilým parti

ím teorie her. Evoluční hry z druhé kapitoly pracují se skokovitým časem a diferenciální hry

pak tyto evoluční zobecňují a uvažují modely, kdy čas plyne spojitě. Pomocí aparátu z těchto

kapitol jsme již schopni namodelovat téměř jakoukoliv situaci, která nás napadne a o které

14 Pokročilá teorie her ve světě kolem nás

máme plnou informaci. To však není v praxi normální. Běžně se stává, že něco nevíme, nebo

neumíme deterministicky modelovat. Nějaké informace nám jsou skryté a my je musíme

odhadnout. V takové chvíli má pro nás matematika modely, které pracují s náhodou, tzv.

stochastické modely. Úvod do her, které tyto modely používají, lze nalézt v kapitole zabýva

jící se statistickými hrami. Pokud ovládneme i tuto kapitolu, pak jsme již schopni namodelo

vat téměř libovolnou situaci. Další krok je tedy přirozeně zamyslet se nad tím, zda jsou hry

vůbec použitelné tam, kde je použít chceme. Co bychom od her mohli čekat, to je modelování

rozhodování živých lidí. Když bychom se po přečtení páté kapitoly ohlédli, mohli bychom

zjistit, že dosavadní konstrukce her jde jinou cestou než myšlenky běžného člověka. Nabízí se

tedy možnost pokusit se modelovat myšlenkové toky lidí jinak. O to se pokoušejí metahry

popsané v šesté kapitole. Od páté kapitoly se také mění pohled na hry. Zatímco v prvních

čtyřech kapitolách se celou dobu díváme na hry jako na „nějakým způsobem fungující sys

tém“, tak v posledních kapitolách hry analyzujeme zejména z pohledu jednoho individuálního

hráče. Závěrečná sedmá kapitola se pak snaží uvažovat nad skutečnou užitečností matematic

kých modelů a hledí na celou knihu pragmatickým okem.

Na závěr úvodu bych se s vámi podělil o jednu vzpomínku z doby, kdy jsem chodil do

druhé třídy a o teorii her jsem ještě nic nevěděl. Přesto jde myslím o pěknou ilustraci teorie

her z běžného života. Tehdy jsme ve škole v hodinách psaní přecházeli od sestavování písme

nek a psaní tužkou k dospělejším metodám. Měli jsme se začít učit psát plnícím perem. Roz

dali nám proto taková zelená pera, do nichž se musel nejprve natáhnout inkoust. Bohužel

jsem nepatřil k těm nejzručnějším ve třídě, a tak se mi po pár dnech podařilo ten inkoust

z pera vypustit do penálu. Abyste pochopili, jaký to byl problém, tak je třeba říci, že mě naše

třídní učitelka neměla ráda a často mě před třídou zesměšňovala. Kdyby přišla na to, co jsem

udělal, byla by štěstím bez sebe a mohla by být na koni několik týdnů. Potřeboval jsem se

nějak vyhnout tomu, abych byl označen za špindíru a sklidil škodolibé posměšky od zbytku

třídy. Pamatuji si, že jsem o tom usilovně přemýšlel celou velkou přestávku, až jsem skutečně

našel řešení. Dnes bych ho označil za geniální. Byl jsem pro naší třídní učitelku trnem v oku,

ale stejně tak ve třídě měla i své oblíbence. Jako byla například věčně vzorná Terezka. Chu

dák Terezka měla tu smůlu, že se stala příliš velkým mazlíčkem naší třídní učitelky a tudíž

i mým vhodným prostředkem, jak se vyhnout cílenému ponížení. Moje strategie spočívala

v tom, že jsem z individuálního problému udělal daleko větší problém, k jehož řešení bylo

potřeba použít úplně jiné prostředky. V nepozorovaný okamžik jsem Terezce udělal to, co

jsem udělal sám sobě, a vypustil jsem její plnící pero do jejího penálu. Jakmile Terezka zjisti

la, jakou spoušť jí v penálu udělalo nové pero, řekla to učitelce, která okamžitě začala zjišťo

vat, co se stalo. Přihlásil jsem se, že se mi přihodilo to samé. A kupodivu se přidali ještě další

dva spolužáci se stejným problémem, kteří to doposud tajili. Kdybych se přihlásil jenom já,

bylo by to trapné, ale tím, že do toho byla zapletena i Terezka, která by nic špatně udělat

nemohla, musela být chyba někde jinde. Výsledkem bylo, že nám učitelka dovolila používat

propisky.

Úvod do teorie her 15

1

Úvod do teorie her

1.1 Klasická teorie her

Teorii her lze chápat jako můstek

mezi reálnými každodenními problé

my, ve kterých je potřeba učinit něja

ké rozhodnutí, a teoretickou matema

tikou, v níž se často zdá, že se skutečným světem nemá nic společného. Situace, kde jsou nutná

rozhodnutí (nazývané někdy též konflikty), mohou být libovolného charakteru, jenž vás při tomto

slově napadne. Můžete si pod tím představit spor sourozenců o to, kdo umyje nádobí, cenovou

válku dvou konkurenčních firem, boj zvířat o potravu, šachovou partii, rozhodování o strategii

politické kampaně... Záleží jen na fantazii a schopnosti vnímat danou situaci jako „konfliktní“

v tom smyslu, že je nutné vybrat strategii, s níž bude jedinec situaci řešit. Teorie her je pak moc

ným matematickým nástrojem, který může usnadnit výběr takové strategie a dosáhnout lépe kýže

ného výsledku.

K pochopení této knihy je nutné si uvědomit, že ačkoliv využívá každá kapitola jiný ma

tematický aparát a pracuje s jinými pojmy, tak jde vždy jen o jinou definici čtyř základních

pojmů: hra, hráči, strategie a výplata. Celá teorie her se o tyto pojmy opírá a různé katego

rie her spočívají jen v obměně vymezení, co který pojem reprezentuje. To, že se pak dosta

neme k jiným matematickým prostředkům, je již jen důsledek potřeby vzniklý problém řešit.

Pojďme si tedy slovně říci, co jednotlivé pojmy znamenají. Hra je jakýsi mechanizmus

pravidel, do něhož vstupují různě inteligentní objekty zvaní hráči, hrající hru se strategiemi,

jež si zvolili z nějaké množiny strategií. Hra pak posbírá od všech hráčů jejich strategie, vy

hodnotí je a jednotlivým hráčům rozdělí výhry neboli výplaty.

+ Pokročilá teorie her ve světě kolem nás

Tím se dostáváme k vysvětlení, jak se stane, že si text v jedné knize o teorii her přečte bez

problémů čtenář, na něhož je kladen pouze požadavek středoškolské matematiky, a v jiné, podobné knize se pak ztrácí v pojmech jako funkcionál nebo stochastický integrál. Jedno je však zřejmé – teorie her je především matematická disciplína, proto se bez matematiky a logického uvažování neobejdeme. Tvorba matematického pozadí kolem jednotlivých kategorií teorie her funguje následovně:

1) Určí se, jaký druh reálného konfliktu chceme pomocí her modelovat.

2) V souladu s bodem 1) se vymezí čtveřice základních pojmů: hra, hráči, strategie

a výplata. Například hra může být jednokolová nebo vícekolová, hráči mohou být

přemýšliví nebo nevypočitatelní, strategie pro všechny hráče stejné nebo má každý in

dividuální možnosti volby, výplata vypočitatelná nebo nejistá apod.

3) Když máme definované čtyři základní pojmy, tak můžeme sestavit optimalizační úlo

hu, kterou se budeme snažit vyřešit. Tato úloha má tvar a složitost danou právě cha

rakterem jednotlivých detailů, které jsme určili v bodu 2).

4) Jakmile máme formulovanou optimalizační úlohu, tak hledáme vhodný matematický

nástroj, kterým se pokusíme, co nejpřesněji úlohu vyřešit. Záměrně zde píši „co nej

přesněji“, protože často jsou optimalizační úlohy tak složité, že buď by bylo přesné

vyřešení úlohy příliš časově nákladné, nebo není matematický nástroj vůbec dostupný.

5) Výsledek z bodu 4) interpretujeme do kontextu identifikovaného konfliktu z bodu 1)

a posoudíme, zda jsme dostali rozumný závěr, který situaci nějak může řešit, či ji ale

spoň vhodně a použitelně analyzuje. Jak ale poznáme, zda námi zvolený přístup vhodně řeší zkoumaný problém? Pro drtivou většinu situací reálného života nepotřebujeme znát číselně přesné výsledky. Už jen fakt, že ve výplatě hráčů pracujeme s užitkem, nám dává mnoho „příležitostí“ k nepřesným odhadům tvarů výplatních funkcí. V bodu 4) je také psáno, že se problémy řeší často aproximačními metodami. Dopouštíme se různých zjednodušení, jako třeba že populaci 10 milionů hráčů šikovně nahradíme jedním hráčem, abychom pak neměli 10 milionů rovnic pro výplatu. Diferenciální rovnice, které mohou vzniknout u diferenciálních her (viz kapitola 4), se často řeší numericky, neboť by analytické řešení bylo příliš zdlouhavé a navíc bychom ho byli schopni vypočíst jen u jednoduchých her. A reálné situace se jen zřídkakdy dají vyjádřit pomocí jednoduchých her. Po takovýchto ústupcích od ideálního řešení je pak vždy dobré nezapomenout na bod 5) a své závěry si nějakým způsobem otestovat. Například zda jsou v souladu s historickými daty. Třeba při špatné volbě modelu hry nám může u plánování politické kampaně vyjít závěr, že nejlepší strategií by bylo zavést jednotnou daň z příjmu 90 %. Politik, který by však tuto daň navrhl, by brzy zjistil, že výsledná optimální strategie je politicky neprosaditelná. V takové situaci by bylo potřeba učinit závěr, že buď modelu chyběla nějaká omezení, nebo že se model špatně interpretoval. Z těchto důvodů se výklad teorie her zpravidla omezuje na body 2) až 4) a body 1) a 5) pouze pro inspiraci uvádí na několika příkladech. V naší knize budeme postupovat úplně stejně. Nicméně hlavním cílem knihy je, aby si pak čtenář dokázal kroky 1) a 5) domyslet již sám, aby chápal, jak jsou jednotlivé typy her spolu propojené, aby dokázal přemýšlet o každodenních situacích v řeči teorie her.

Úvod do teorie her 17

Přejděme nyní k matematické formalizaci, bez které se dále v knize neobejdeme. Obecně

můžeme hru definovat takto:

Definice 1.1: Nechť je dána konečná neprázdná -prvková množina a dále

měřitelných množin

a omezených reálných funkcí

definova

ných na kartézském součinu

. Hrou hráčů v normálním tvaru budeme

rozumět uspořádanou -tici

(1.1)

I

Množinu nazveme množinou hráčů množinu

nazveme prostorem strategií hráče ,

prvek

nazveme strategií hráče a funkci

nazveme výplatní funkcí hráče (vše

pro ).

Hodnotu výplatní funkce

nazveme výplatou hráče . Je-li hodnota výplatní funkce

pro daného hráče kladná hovoříme o zisku, je-li záporná hovoříme o ztrátě.

Podmnožina množiny se nazývá koalice. Spojenou strategii hráčů z koalice

značíme

, kde

je prostor spojených

strategií hráčů z .

Zde je na místě důležitá poznámka k značení. V definici (1.1) jsme označili jako

strategie hráčů. Nicméně značení jako strategie se nebudeme v následujících kapitolách

striktně držet. Proto je na místě věnovat pozornost značení v úvodu každé kapitoly, aby nedo

šlo k chybné interpretaci vyložené látky.

Uveďme, že chceme-li vypočíst výplatu hráče , tak jakkoliv může být nemateriální, je

vhodné modelovat výplatní funkce

tak, aby vyjadřovaly užitek, který danému hráči přine

se výsledek hry. V hrách, kde se vyskytují peníze, zpravidla používáme totiž předpoklad, že

hráčův užitek je přímo úměrný výši jeho peněžního příjmu. Užitku se blíže věnuje následující

podkapitola.

Když nyní známe obecnou definici hry, pojďme se podívat, jak lze hry kategorizovat po

mocí různých vymezení základních pojmů. Celková klasifikace her je však v literatuře nejed

notná. Následující výčet není úplný a ani zdaleka jediný. Pokud však čtenář pochopí, že se

k jednotlivým bodům dostane skrz obměnu základních pojmů, pak nebude tuto klasifikaci

potřebovat a třeba si vytvoří i vlastní. Uvádím zde tento výčet kvůli lepší orientaci

v literatuře. Zde je tedy jen několik možných pohledů na hry, jež mohou sloužit jako vodítko

k představě, jak hry členit či klasifikovat:

I

V dalším budeme značit

..

,

..

a hra pak bude Pokročilá teorie her ve světě kolem nás

i) Kooperativní a nekooperativní hry

Hry jsou kooperativní, pokud mohou hráči uzavírat vynutitelné dohody,

v nekooperativních hrách toto umožněno není.

ii) Jednokolové a vícekolové hry

V jednokolových hrách hráči odehrají jednu hru, rozeberou si výplaty

a zkušenosti nabyté ve hře již dále neuplatňují. Důležité je také, že hráči přímo

volí své strategie na základě faktu, že další kola hry již nebudou. Ve vícekolo

vých hrách se hraje hra vícekrát za sebou a hráči před každým kolem mohou

změnit své strategie. Ve volbě rozumných rozhodnutí vzniká potřeba uvažovat

více kol dopředu, neboť je zde například hrozba msty ze strany hráčů, kteří v y

jdou z dřívějších kol poškození nebo s horší výplatou. Zvláštní případ vícekolo

vých her, kde hráči kopírují strategie úspěšnějších hráčů, se nazývají evoluční

hry (viz kapitola 2).

Je třeba zmínit, že pokud hráči vědí, že hrají poslední kolo vícekolové hry, tak

se chovají, jakoby hráli jednokolovou hru. Jejich volba strategií se tedy mění na

základě počtu kol, která mají před sebou. Dobrý příklad jednokolové hry je

konkurzní řízení firmy v likvidaci. Všichni zúčastnění se snaží ze zbankrotované

firmy sobecky vytáhnout co nejvíce peněz. Zatímco pokud firma funguje nor

málně a zdravě, hrají akcionáři vícekolovou hru a jejich cíle můžou být

i dlouhodobé, nebudou se tak snažit jen vybrat z firmy v co nejkratším čase co

nejvíce peněz.

iii) Symetrické a asymetrické hry

Pod symetrickými hrami se zpravidla rozumí takové hry, kde hráči volí ze shodné množiny strategií. V některých zdrojích se ještě navíc předpokládá, že výplatní funkce jsou pro hráče stejné. V asymetrických hrách nic takového neplatí a hráči se pak logicky ocitají v nerovnocenném postavení.

iv) Hry s nulovým součtem a hry s nenulovým součtem

Hry, ve kterých je součet výplat všech hráčů vždy roven nule, jsou hry s nulovým součtem. Velmi často lze za hry s nulovým součtem označit hry, kde je součet výplat všech hráčů roven jakékoliv dopředu dané konstantě. Hry s nenulovým součtem jsou pak hry, kde nelze dopředu určit, jaká konkrétně bude hodnota součtu výplat všech hráčů.

v) Hry s úplnou (dokonalou) informací a s částečnou informací

Hry s úplnou informací jsou takové hry, kde hráči mohou znát všechny možné průběhy hry. Hry s částečnou informací jsou naproti tomu takové, kde hráči do