Doprovodné texty ke kurzu Teorie her

Doprovodné texty ke kurzu Teorie her

Martin Hrubý Fakulta informaˇcn´ıch technologi´ı Vysoké uˇcen´ı technické v Brnˇe

zimn´ı semestr, akad. rok 2010/11

1

Contents 1

Pˇredmluva 1.1 Pˇredmˇet Teorie her na FIT VUT v Brnˇe . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Pˇrehled pˇrednásˇek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Opakován´ı matematických pojm˚u . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

´ Uvod do hern´ıch pojmu˚ ´ 2.1 Uvod do Teorie volby (Theory of Choice) 2.2 Teorie uˇzitku . . . . . . . . . . . . . . . 2.2.1 Uˇzitek ze zisku . . . . . . . . . . 2.3 D˚uleˇzité poznatky . . . . . . . . . . . . .

2

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

3 3 4 6 10 10 14 15 16

Chapter 1 Pˇredmluva 1.1

Pˇredmˇet Teorie her na FIT VUT v Brnˇe

Pˇredmˇet Teorie her byl otevˇren a poprvé pˇrednásˇen na FIT VUT v Brnˇe v akademickém roce 2009/10. V prvn´ım roce si pˇredmˇet zapsalo cca 110 student˚u a absolvovala pˇribliˇznˇe polovina. Z toho lze soudit reálnou kapacitu pˇredmˇetu a poˇcet zájemc˚u o hernˇe-teoretickou problematiku. Pˇredmˇet byl od poˇca´ tku orientován na magisterské studenty, kde lze oˇcekávat jiˇz jistou teoretickou pˇr´ıpravu, zkuˇsenosti a nadhled. Pro dalˇs´ı akademické roky je pˇredmˇet Teorie her r˚uznˇe charakterizován v r˚uzných magisterských oborech: pˇredmˇet je povinný v oborech Bioinformatika a biocomputing a Matematické metody v informaˇcn´ıch technologi´ıch. Povinnˇe volitelný je v oborech Inteligentn´ı systémy a Poˇc´ıtaˇcové s´ıtˇe a komunikace. V ostatn´ıch oborech magisterského studia je nab´ızen jako volitelný. Na zaˇca´ tek si zodpovˇezme dvˇe otázky: co je Teorie her a co studium Teorie her pˇrinese informatikovi? Teorie her je znaˇcnˇe multi-disciplinárn´ı vˇeda, která zkoumá a matematicky popisuje situace, kdy se skupina inteligentn´ıch jedinc˚u mus´ı nˇejak rozhodnout, jejich rozhodnut´ı vede k nˇejakým d˚usledk˚um, které tyto jedince zaj´ımaj´ı a jedinci maj´ı zájem dosáhnout d˚usledk˚u, které se z jejich pohledu jev´ı jako nejlepˇs´ı. Existuje spousta definic Teorie her a spousta názor˚u, jak na tuto teorii nahl´ızˇ et. Je kaˇzdopádnˇe jisté, zˇ e Teorie her nám pˇr´ımo neˇr´ıká, co konkrétnˇe jedinci v jejich situaci opravdu udˇelaj´ı, a uˇz v˚ubec nám negarantuje jistotu takové predikce. To v podstatˇe nikdo ani nechce. Teorie her nám umoˇzn´ı jejich situaci formálnˇe popsat, analyzovat, pochopit a vyvodit pro sebe nˇejaký závˇer o situaci. V rámci studia her budeme zkoumat individuáln´ı racionalitu jedinc˚u pˇri rozhodován´ı, jejich moˇznosti, preference a uˇzitek dosaˇzený ve hˇre. Kdyˇz se na Teorii her pod´ıvá informatik, tak m˚uzˇ e ˇr´ıct, zˇ e Teorie her je varianta umˇelé inteligence nebo vˇseobecnˇe metod modelován´ı. Budeme pracovat s modely a mnohdy budeme cht´ıt tyto modely 3

poˇc´ıtaˇcovˇe zpracovávat do formy simulaˇcn´ıch model˚u. Dále m˚uzˇ e informatika zaujmout algoritmická nároˇcnost nˇekterých problém˚u a t´ım i hledán´ı pro nˇe efektivn´ıho algoritmického ˇreˇsen´ı. Samozˇrejmˇe se nab´ız´ı souvislost matematické teorie her a poˇc´ıtaˇcových her (nˇekteré se dokonce nazývaj´ı strategické). Je dobré si hned na poˇca´ tku pˇriznat, zˇ e pˇredmˇet Teorie her (THE) nen´ı kurzem tvorby poˇc´ıtaˇcových her. Ovˇsem poˇc´ıtaˇcové hry v sobˇe obsahuj´ı prvky umˇelé inteligence a ty jsou zaloˇzeny na zde zkoumaných teori´ıch. Obecnˇe vzato m˚uzˇ e být studium her pˇr´ınosné pro kaˇzdého cˇ lovˇeka, protoˇze pozná modely mnoha kaˇzdodenn´ıch lidských situac´ı, pochop´ı, proˇc svˇet funguje zrovna t´ımto zp˚usobem a to rozhodnˇe nen´ı k zahozen´ı.

1.2

Pˇrehled pˇrednásˇek

Program pˇrednásˇek v Teorii her na FITu má jako sv˚uj c´ıl podat co moˇzná nejˇsirˇs´ı zábˇer pˇres vˇsechny problémy, které Teorie her ˇreˇs´ı. V kaˇzdé kapitole jsou diskutovány základy a nejd˚uleˇzitˇejˇs´ı modely. Lze oˇcekávat, zˇ e se v budoucnu program pˇrednásˇek dopln´ı o jednu aˇz dvˇe nové kapitoly, jisté vˇsak je, zˇ e v pˇrednásˇkách rozhodnˇe zazn´ı tato témata: ´ 1. Uvod do matematického rozhodován´ı – u´ vodn´ı kapitola zavede pojmy strategie, zisk, uˇzitek, preference a teorie optimáln´ı volby. D˚uleˇzité je zejména pochopen´ı pojmu preference a preferenˇcn´ı relace. 2. Hry v normáln´ı formˇe s nenulovým souˇctem – tento typ her je naprostým základem pro chápán´ı strategických interaktivn´ıch situac´ı. Zavede se vˇetˇsina nezbytných pojm˚u jako je strategie, hrácˇ , hra, best-response, dominance strategi´ı, ekvilibrium a dalˇs´ı. Pochopen´ı této kapitoly je kl´ıcˇ ové pro studium her. 3. Hry v normáln´ı formˇe s nulovým souˇctem – speciáln´ım pˇr´ıpadem her s nenulovým souˇctem jsou hry s nulovým souˇctem, ke kterým lze pˇristupovat m´ırnˇe odliˇsným zp˚usobem. Budou zavedeny základn´ı metody analýzy tˇechto her. Jako vedlejˇs´ı produkt této kapitoly bude vysvˇetlena metoda Lineárn´ıho programován´ı, které je pro teorii her základn´ım matematickým aparátem. 4. Algoritmy pro rˇeˇsen´ı strategických her – kapitola pˇrinese naprosto stˇezˇ ejn´ı modely oligopolu dle Cournota a Bertranda, které stály na poˇca´ tku u´ vah o podobˇe ekvilibria ve hrách s nenulovým souˇctem. Bude diskutován problém existence ekvilibria ve hrách s nenulovým souˇctem a proveden d˚ukaz existence ekvilibria v koneˇcných hrách. Souˇcasnˇe s t´ımto budou zavedeny hry ve sm´ısˇených strategi´ıch. V závˇeru budou pˇredvedny základn´ı postupy výpoˇctu Nashova ekvilibria ve sm´ısˇených strategi´ıch. 5. Hry v rozˇs´ırˇené formˇe – hry v rozˇs´ırˇené formˇe se také nazývaj´ı sekvenˇcn´ı nebo dynamické hry. V tˇechto hrách se hrácˇ i stˇr´ıdaj´ı v taz´ıch a hra je obecnˇe provedena ve v´ıce akc´ıch. Uvid´ıme

4

souvislost mezi sekvenˇcn´ı hrou a hrou v normáln´ı formˇe. Budou diskutovány problémy Stackelbergova ekvilibria, prvek d˚uvˇeryhodné/ned˚uvˇeryhodné hrozby v hern´ıch situac´ıch a forma ekvilibria ve hrách v rozˇs´ıˇrené formˇe – tak zvané Sub-game Perfect Nash Equilibrium (SPNE). 6. Vyjednáván´ı a kooperativn´ı hry – v druhé cˇ a´ sti semestru pˇripust´ıme, zˇ e hrácˇ i ve hˇre mohou spolu komunikovat a vyjednávat o volbˇe spoleˇcné strategie, pˇr´ıpadnˇe tvoˇrit koalice. Kooperativn´ı hry studuj´ı pˇredpoklady, za jakých okolnost´ı hrácˇ i mohou kooperovat a jaké zlepˇsen´ı zisku jim to pˇrinese. 7. Opakované hry – bude dokázáno, zˇ e pˇri opakován´ı strategické interaktivn´ı situace lze oˇcekávat u hrácˇ u˚ tendence ke kooperativn´ımu jednán´ı. Dokonce, pokud má hra nekoneˇcný poˇcet opakován´ı (tj. hrácˇ i neznaj´ı okamˇzik posledn´ıho opakován´ı hry), pak je jejich racionáln´ı volbou kooperovat. 8. Korelované ekvilibrium ve strategických hrách s nenulovým souˇctem – korelované ekvilibrium tvoˇr´ı alternativu pro Nashovo ekvilibrium ve sm´ısˇených strategi´ıch. Prozkoumáme jeho interpretaci a algoritmus výpoˇctu. 9. Mechanism design – obt´ızˇ nˇe pˇreloˇzitelný pojem, který lze interpretovat jako návrh pravidel ve strategických interaktivn´ıch situac´ıch. Mechanism design bývá obˇcas prezentován jako teorie her naruby. Jedná se o návrh pravidel hry takový, aby racionáln´ım chován´ım hrácˇ u˚ bylo chovat se tak, jak si návrháˇr hry pˇreje. Obvykle je c´ılem dosáhnout stavu, kdy hrácˇ i chtˇej´ı dobrovolnˇe prezentovat svou pravdivou preferenci o situaci. Jako nejtypiˇctˇejˇs´ı pˇr´ıklady tˇechto situac´ı si pˇredvedeme Teorii veˇrejné volby a Teorii aukc´ı. 10. Teorie aukc´ı – u´ vodn´ı kapitola do Teorie aukc´ı bude formálnˇe definovat základn´ı aukˇcn´ı principy a poznatky o ekvivalenci mezi nˇekterými aukcemi. Aukce jsou velmi významnou sloˇzkou reálného zˇ ivota. Proto je velmi praktické rozumˇet chován´ı v aukc´ıch, napˇr´ıklad pro situace, kdy mus´ıme nˇejakou aukci sami organizovat. 11. Evoluˇcn´ı biologie – evoluˇcn´ı biologie je pˇrekvapivá aplikace teorie her do zkoumán´ı vývoje zˇ ivoˇciˇsných druh˚u a modelován´ı jejich vzájemných interakc´ı. Kapitola bude vycházet z pˇrevratného cˇ lánku J. M. Smithse, který poprvé pouˇzil pojmy teorie her pro vysvˇetlen´ı r˚uzných fenotyp˚u chován´ı jedinc˚u a zavedl kl´ıcˇ ový pojem evoluˇcnˇe stabiln´ı strategie. 12. Theory of Moves – m´ırnˇe alternativn´ı teorie tah˚u od Stevena Bramse. 13. Rozbor pˇr´ıpadové studie simulaˇcn´ıho modelu zaloˇzeného na teorii her. Tato kapitola nebude souˇca´ st´ı skript. Jedná se o demonstraci teorie her v simulaˇcn´ım modelován´ı elektroˇ energetických trh˚u v Cesk´ e republice, kterým se autor po léta zabývá.

5

1.3

Opakován´ı matematických pojmu˚

Pˇredmˇet THE od posluchaˇcu˚ nevyˇzaduje specializované znalosti matematiky, ale pouze základy a pˇredevˇs´ım schopnost d˚ukladnˇe studovat pˇredloˇzené definice, vˇety a d˚ukazy. Pˇredpokládá se pˇrehledová znalost z oblasti diskrétn´ı matematiky, algebry, matematické analýzy, teorie pravdˇepodobnosti a statistiky. Pˇresto se hod´ı znovu vysvˇetlit základn´ı pojmy, na kterých bude stavˇeno. Základn´ım pojmem je pojem mnoˇziny. Bez potˇreby hloubˇeji zkoumat teorii mnoˇzin a r˚uznˇe abstraktn´ı definice pojmu mnoˇzina lze mnoˇzinu vysvˇetlit jako matematický objekt A, pro který plat´ı, zˇ e jsme schopni pro kaˇzdý (∀) libovolný objekt o jednoznaˇcnˇe urˇcit, zda-li objekt o je nebo nen´ı prvkem A. Mnoˇzinu tedy urˇcuje vztah být prvkem mnoˇziny, coˇz p´ısˇeme: o∈A a cˇ teme ”objekt o je prvkem mnoˇziny A” (patˇr´ı do mnoˇziny) nebo naopak o ∈ / A – ”objekt o ˇ nen´ı prvkem mnoˇziny A” (nepatˇr´ı do mnoˇziny). Zavedme jako dohodu (notaci) mnoˇziny zapisovat s velkým poˇca´ teˇcn´ım p´ısmenem (nebo slovem zaˇc´ınaj´ıc´ım velkým p´ısmenem) a jejich prvky malým p´ısmenem. Pro informatiky je d˚uleˇzité zd˚uraznit, zˇe mnoˇzina nen´ı seznam. Pokud prvek patˇr´ı do mnoˇziny, pak je v mnoˇzinˇe pouze jednou1 . Co je dále d˚uleˇzité, je sdˇelen´ı, zˇ e prvky v mnoˇzinˇe nemaj´ı poˇrad´ı (nejsou seˇrazeny). Proto by nikdy nemˇelo zazn´ıt ”Prvn´ım prvkem mnoˇziny napˇr. A je ...”. Mnoˇziny cˇ asto zapisujeme výcˇ tem prvk˚u: A = {a1 , a2 , ..., ax } Prázdnou mnoˇzinu pak symbolem ∅. Zápisem |A| budeme znaˇcit poˇcet prvk˚u mnoˇziny (kardinalitu mnoˇziny). Tedy, |A| = x, kde x ∈ N+ ∪ {0}. Ustálené mnoˇziny cˇ´ısel budeme zapisovat zdvojeným p´ısmem – N pro zápis mnoˇziny pˇrirozených cˇ´ısel, tedy integers (dále N+ , N− , N0 ) a R pro zápis mnoˇziny reálných cˇ´ısel, tedy floats. Mnoˇzinu cˇ asto zapisujeme nˇejakou podm´ınkou, která plat´ı pro jej´ı prvky, obecnˇe B = {a ∈ A|condition(a)} Pˇred svislou cˇ arou je zápis mnoˇziny, ze které se vyb´ırá (FROM, mnoˇzina A) a za svislou cˇ arou je daný ”SELECT”. Pojem podmnoˇziny je jistˇe známý. Rozliˇsujeme ostrou podmoˇzinu A ⊂ B (tedy |A| < |B|) a neostrou ⊆ (tedy A = B ∨ A ⊂ B). 1

...na rozd´ıl od multi-mnoˇziny, ovˇsem multi-mnoˇzinu lze zapsat formou mnoˇziny dvojic (o, i) kde i znaˇc´ı poˇcet opakován´ı prvku o v mnoˇzinˇe

6

D˚uleˇzitou mnoˇzinou je tak zvaná poteˇcn´ı mnoˇzina. Mˇejme napˇr´ıklad mnoˇzinu A. Poteˇcn´ı mnoˇzina mnoˇziny A se zapisuje výrazem 2A a obsahuje jako své prvky vˇsechny moˇzné podmnoˇziny mnoˇziny A vˇcetnˇe prázdná mnoˇziny. Plat´ı |2A | = |2|A| . Zopakujme formáln´ı definice mnoˇzinových operac´ı sjednocen´ı (∪), pr˚uniku (∩) a mnoˇzinového rozd´ılu (\). Definice 1. Mˇejme dvˇe mnoˇziny A a B. Operace nad mnoˇzinami sjednocen´ı (∪), pr˚unik (∩) a mnoˇzinového rozd´ıl (\) definujeme takto: • C = A ∪ B ⇔ ∀c ∈ C : c ∈ A ∨ c ∈ B • C = A ∩ B ⇔ ∀c ∈ C : c ∈ A ∧ c ∈ B • C = A \ B ⇔ ∀c ∈ C : c ∈ A ∧ c ∈ / B resp. C = {c ∈ A|c ∈ / B} V mnoha zápisech budeme operátory ∪, ∩,

P

pouˇz´ıvat s iteraˇcn´ı promˇennou:

C=

[

f un(i)

i∈N

pokud je N mnoˇzinou. I=

N X

f un(i)

i=1

pokud je N pˇrirozené cˇ´ıslo a iterace prob´ıhá od i = 1 do i = N vˇcetnˇe, s krokem jedna. Pokud jsou tyto dvˇe alternativy cˇ tenáˇri zˇrejmé, lze zkracovat na, jako napˇr.: I=

N X

f un(i)

i

Kartézský souˇcin (angl. product), relace Kartézský souˇcin (znaˇc´ıme operátorem ×) mnoˇzin A a B je definován jako mnoˇzina vˇsech uspoˇra´ daných dvojic C = A × B = {(a, b)|a ∈ A ∧ b ∈ B} Podstatné tedy je, zˇ e se jedná o mnoˇzinu a jej´ımi prvky jsou uspoˇra´ dané dvojice. Uspoˇra´ daná N-tice je vektor prvk˚u, kde tedy jiˇz na poˇrad´ı záleˇz´ı, t.j. (a, b) je jiný objekt neˇz (b, a). Kartézský souˇcin m˚uzˇ e být libovolné dimenze, napˇr´ıklad definujeme CC = A × B × C × ... × Z 7

S kartézským souˇcinem souvis´ı pojem relace. Toto lidské slovo má opravdu hodnˇe význam˚u, ovˇsem pro matematiku je binárn´ı relace na mnoˇzinách A a B podmnoˇzinou kartézského souˇcinu mnoˇzin A a B (tzn. je to mnoˇzina uspoˇra´ daných dvojic). R⊆A×B Následuj´ıc´ı dva zápisy jsou ekvivalentn´ı: R ⊆ A × A, R ⊆ A2 . Pro relace se ustálila následuj´ıc´ı notace. Pokud je x ∈ R a x = (a, b), pak obˇcas p´ısˇeme aRb. Definujeme i n-árn´ı relace R ⊆ A × B × C × ... × Z. Pˇr´ıklad: A = {1, 2, 3}; B = {x, y} A × B = {(1, x), (1, y), (2, x), (2, y), (3, x), (3, y)} R ⊆ A × B napˇr. R = {(1, x), (1, y)} Nad relacemi definujeme nˇekolik charakteristik, které nám ulehˇcuj´ı vyjadˇrován´ı o r˚uzných vlastnostech naˇsich popisovaných jev˚u. Jsou to vlastnosti (provád´ıme výbˇer vlastnost´ı podstatných pro THE): ˇ Definice 2. Mˇejme relaci R ⊆ A × A. Rekneme, zˇe relace R je: • u´ plná, pokud ∀a, b ∈ A : aRb ∨ bRa nebo oboje. • reflexivn´ı, pokud ∀a ∈ A : aRa. • symetrická, pokud ∀a, b ∈ A : aRb ⇒ bRa. • antisymetrická, pokud ∀a, b ∈ A : aRb ∧ bRa ⇒ a = b, tzn. a i b jsou shodné prvky. • tranzitivn´ı, pokud aRb ∧ bRc ⇒ aRc. D˚uleˇzitý je fakt, zˇ e relace m˚uzˇ e m´ıt nˇekolik výsˇe zm´ınˇených vlastnost´ı souˇcasnˇe. Kombinace tˇechto vlastnost´ı vede k pojmenován´ı sloˇzených vlastnost´ı relac´ı, jako jsou kvazi-uspoˇra´ dán´ı, u´ plné uspoˇra´ dán´ı, ekvivalence a podobnˇe. Dalˇs´ı matematické znalosti Pˇredmˇet THE nevyˇzaduje u student˚u znalosti matematiky, které by pˇrekraˇcovaly rámec bˇezˇ ného informatického studia. Bylo by vˇsak dobré umˇet/chápat: • Pˇreˇc´ıst/pochopit matematický zápis – a pˇredevˇs´ım chápat, zˇ e matematický zápis nám zjednoduˇsuje inˇzenýrskou komunikaci a vede k jednoznaˇcnému vyjádˇren´ı naˇsich myˇslenek. ´ • Upravy algebraických výraz˚u (odvozován´ı, zjednoduˇsován´ı) – u´ pravy algebraických výraz˚u jsou umˇen´ım, které je tˇreba stále pˇestovat a rozv´ıjet. 8

• Vyˇreˇsen´ı lineárn´ı, kvadratické a jednoduché diferenciáln´ı rovnice. Základn´ı ˇreˇsen´ı soustav lineárn´ıch rovnic. • Derivovat funkce v´ıce promˇenných a hledat extrémy funkc´ı – matematická analýza by pro inˇzenýra mˇela být samozˇrejmost´ı. V rámci studia THE bude probrána (moˇzná) nová matematická metoda a t´ım je lineárn´ı programován´ı. Lineárn´ı programován´ı je soubor metod ˇreˇsen´ı optimalizaˇcn´ıch u´ loh s lineárn´ımi omezuj´ıc´ımi podm´ınkami a lineárn´ı hodnot´ıc´ı funkc´ı. Je to základ ˇreˇsen´ı mnoha hernˇe-teoretických problém˚u.

9

Chapter 2 ´ Uvod do hern´ıch pojmu˚ V této kapitole naznaˇc´ıme základn´ı problém rozhodován´ı a t´ım je volba jedné alternativy z mnoˇziny dostupných alternativ. V umˇelé inteligenci a v THE se budeme snaˇzit modelovat tyto okamˇziky, kdy se inteligentn´ı jedinec m˚uzˇ e nebo mus´ı nˇejak rozhodnout. Základem rozhodován´ı je pochopen´ı a poznán´ı moˇzných alternativ (”... m˚uzˇ eˇs si vybrat to nebo to...”). Souˇca´ st´ı naˇseho modelu bude pˇredevˇs´ım pak ten výcˇ et alternativ. Nem˚uzˇ eme zat´ım poˇc´ıtat s t´ım, zˇ e by si poˇc´ıtaˇcový model inteligentn´ıho tvora sám tento výcˇ et sestavil. Kaˇzdá akce má vˇsak reakci. Volba alternativy má sv˚uj d˚usledek (pozdˇeji budeme mluvit o uˇzitku). Budeme cht´ıt modelovat, zda-li si jedinec tento fakt uvˇedomuje a jakým zp˚usobem si ho uvˇedomuje. Budeme zkoumat, zda-li je schopen porovnat dva dosaˇzitelné d˚usledky a rozhodnout se, který on povaˇzuje za lepˇs´ı. Jinak ˇreˇceno, zda-li je schopen nˇejaký d˚usledek preferovat pˇred jiným. Za jistých okolnost´ı lze zamˇenit zkoumán´ı preferenc´ı nad d˚usledky se zkoumán´ı preferenc´ı nad alternativami. Jako výsledek této kapitoly definujeme okolnosti, za kterých je jedinec schopen provést racionáln´ı rozhodnut´ı nad mnoˇzinou alternativ, tedy rozhodnut´ı, které mu pˇrinese nejlepˇs´ı dosaˇzitelný d˚usledek. Pozdˇeji uvid´ıme, zˇ e to nemus´ı být nutnˇe absolutnˇe nejvyˇssˇ´ı d˚usledek (uˇzitek), ale budeme sp´ısˇe mluvit o optimáln´ım uˇzitku.

2.1

´ Uvod do Teorie volby (Theory of Choice)

V Teorii volby i v Teorii interaktivn´ıho strategického rozhodován´ı (Teorie her) jedinec provád´ı rozhodnut´ı, coˇz je jaksi zd˚uvodnitelná volba jedné z jeho moˇzných voleb (akc´ı, tah˚u, strategi´ı). M˚uzˇ eme zkoumat, zda-li jedinec dojde ke svému rozhodnut´ı pomoc´ı nˇejaké racionáln´ı u´ vahy nebo vol´ı-li sv˚uj tah náhodnˇe. Jedinec vol´ıc´ı sv˚uj tah náhodnˇe je v TH nazýván pˇr´ıroda (angl. the nature). Hry s takovým hrácˇ em jsou pak nazývány ”hry proti pˇr´ırodˇe”. T´ımto aspektem her se vˇsak budeme zabývat pouze velmi okrajovˇe. V Teorii her se budeme z vˇetˇs´ı cˇ a´ sti zabývat hrácˇ i, kteˇr´ı pro své rozhodnut´ı maj´ı nˇejaký d˚uvod a ke svému rozhodnut´ı dojdou nˇejakou matematicky podloˇzitelnou u´ vahou. Takové hrácˇ e budeme nazývat 10

racionáln´ımi. Pojem racionality je pro TH kl´ıcˇ ový a bude mu vˇenována pozornost v následuj´ıc´ı kapitole. Základem pro racionáln´ı u´ vahu je pochopen´ı faktu, zˇ e kaˇzdé rozhodnut´ı má sv˚uj d˚usledek. D˚usledek rozhodnut´ı je v TH podobnˇe d˚uleˇzitý fenomén jako samotná racionalita a velmi u´ zce spolu souvis´ı. D˚usledek je vyjádˇren formou nˇejakého kvantifikovatelného uˇzitku nebo také zisku. V THE budeme pojmy uˇzitek a zisk obvykle smˇesˇovat, pouze v nˇekterých kapitolách budeme odliˇsovat objektivn´ı zisk a vn´ımán´ı uˇzitku ze zisku (napˇr´ıklad v prvn´ı pˇrednásˇce, v rámci kapitoly o Teorii uˇzitku). V anglické literatuˇre bývaj´ı tyto pojmy oznaˇcovány jako payoff nebo utility.

Nyn´ı si formálnˇe definujeme rámec rozhodován´ı jedince. Mˇejme jedince provádˇej´ıc´ıho rozhodnut´ı o volbˇe své akce z mnoˇziny akc´ı A = {a1 , a2 , ..., ak }. Pˇredpokládejme, zˇ e jedinec má dostatek informac´ı o dané situaci takový, zˇ e je schopen definovat mnoˇzinu veˇskerých d˚usledk˚u svých rozhodnut´ı X = {x1 , x2 , ..., xn }. Jedinec je dále schopen jednoznaˇcnˇe pˇriˇradit kaˇzdé své volbˇe a ∈ A právˇe jeden d˚usledek x ∈ X. Matematicky tento fakt modelujeme funkc´ı (napˇr´ıklad nazývanou funkc´ı uˇzitku), která pˇriˇrazuje akc´ım a ∈ A právˇe jeden d˚usledek z mnoˇziny X u:A→X Máme tedy mnoˇzinu moˇzných akc´ı A, mnoˇzinu moˇzných d˚usledk˚u X a nyn´ı potˇrebujeme vod´ıtko pro volbu, kterou budeme chápat jako racionáln´ı. Racionalita má nˇekolik definic. Jedna z nich ˇr´ıká, zˇ e racionálnˇe chovaj´ıc´ı se jedinec vol´ı svou akci po d˚ukladném zvázˇ en´ı veˇskerých d˚usledk˚u. Dalˇs´ı ˇr´ıká, zˇ e racionáln´ı jedinec maximalizuje sv˚uj zisk. Zisk chápame obvykle jako cˇ´ıselné vyjádˇren´ı napˇr´ıklad formou penˇez. U takového vyjádˇren´ı kaˇzdý jedinec seznámený s penˇezi chápe, zˇ e 100 Kˇc je v´ıc neˇz 10 Kˇc. Chápe to proto, zˇ e je schopen obˇe hodnoty porovnat. Schopnost porovnáván´ı dvou moˇzných výsledk˚u proto bude základ pro racionáln´ı rozhodován´ı. Dodejme, zˇ e pokud je funkce u bijektivn´ı (vzájemnˇe jednoznaˇcné zobrazen´ı), coˇz znaˇc´ı, zˇ e u je jednoznaˇcné (pro kaˇzdé a ∈ A existuje právˇe jedno x ∈ X, zˇ e u(a) = x) a souˇcasnˇe ”na mnoˇzinu” (pro kaˇzdé x ∈ X existuje právˇe jedno a ∈ A, zˇ e u(a) = x), pak je jedno, zda-li mluv´ıme o zkoumán´ı optima na mnoˇzinˇe d˚usledk˚u nebo na mnoˇzinˇe alternativ. Je to jednoduché, pokud by existovaly dvˇe alternativy vedouc´ı ke stejnému d˚usledku, jsou pro jedince v zásadˇe totoˇzné. Vˇenujme se proto, zat´ım, zkoumán´ı preferenc´ı na mnoˇzinˇe alternativ. Dˇr´ıve, neˇz zavedeme pojem maxima (tzn. cestu k maximalizaci zisku), budeme definovat pojem ˇ jedincovy preference. V obecné mluvˇe chápeme preferenci jako nˇejakou formu priority. Rekneme, zˇ e obyvatel Vyˇskova preferuje vyˇskovské pivo, ale m´ın´ıme t´ım, zˇ e Vyˇskovan konfrontován s volbou vyˇskovské versus kterékoliv jiné pivo vˇzdy vol´ı svou domác´ı znaˇcku. V tomto vyjádˇren´ı implicitnˇe 11

chápeme výsledek pˇr´ıpadných konfrontac´ı, ale matematicky toto mus´ıme zd˚uraznit. Zd˚urazˇnujeme to zaveden´ım preferenˇcn´ı binárn´ı relace nad mnoˇzinou alternativ. Preferenˇcn´ı relace R ⊆ A × A je tedy mnoˇzina dvojic (a1 , a2 ), které interpretujeme tak, zˇ e ˇ a1 je preferováno nad (pˇred) a2 . Rekneme rovnou, zˇ e v teorii volby a v TH obecnˇe se pro lepˇs´ı obecnost zavád´ı tak zvaná slabá preference (angl. weak preference), která se interpretuje tak, zˇ e je-li (a1 , a2 ) ∈ R, coˇz také p´ısˇeme a1 Ra2 , pak jedinec nepreferuje a2 nad a1 , nebo-li v kladné mluvˇe ˇreˇceno, chápe a1 jako lepˇs´ı nebo stejnˇe dobrou akci jako a2 . Pro lepˇs´ı pˇredstavu srovnejme slabou preferenci s matematickým operátorem ≥ nad cˇ´ısly (coˇz je opˇet relace a dokonce relace se stejnými vlastnostmi jako slabá preference). V TH je také cˇ asto t´ımto operátorem slabá preference zapisována. Pokud by nám chybˇela silnˇejˇs´ı/radikálnˇejˇs´ı forma preference, m˚uzˇ eme zavést relaci striktn´ı preference (budeme ji oznaˇcovat P ). ˇ Definice 3. Mˇejme hrácˇ e s mnoˇzinou alternativ A a relac´ı slabé preference R ⊆ A × A. Rekneme, zˇe jedinec striktnˇe preferuje a1 nad a2 (tedy a1 P a2 ), pokud plat´ı a1 Ra2 ∧ ¬a2 Ra1 Jinak ˇreˇceno, pokud (a1 , a2 ) ∈ P , pak (a1 , a2 ) ∈ R a souˇcasnˇe (a2 , a1 ) ∈ / R. Podobnˇe zavedeme relaci indiference I (doslova – nerozliˇsitelnosti), tedy: ˇ Definice 4. Mˇejme hrácˇ e s mnoˇzinou alternativ A a relac´ı slabé preference R ⊆ A × A. Rekneme, zˇe jedinec je indiferentn´ı mezi dvˇema r˚uznými a1 a a2 (tedy a1 Ia2 ), pokud plat´ı a1 Ra2 ∧ a2 Ra1 Jaké mus´ı m´ıt relace slabé preference vlastnosti, aby dala jedinci návod k racionáln´ı volbˇe? Stále pˇredpokládáme, zˇ e jedinec plánuje zvolit akci, která bude nejlepˇs´ı ze vˇsech moˇzných, tedy nebude existovat jiná akce, kterou by striknˇe preferoval nad svoj´ı volbou. Chceme totiˇz naj´ıt nˇejaké maximum. Definice 5. Pro relaci slabé preference R a mnoˇzinu alternativ A definujeme maximáln´ı mnoˇzinu M (R, A) ⊂ A tak, zˇe M (R, A) = {x ∈ A|xRy; ∀y ∈ A} Maximáln´ı mnoˇzina M (R, A) je tedy tvoˇrena takovými prvky ⊆ A, zˇ e neexistuje prvek y ∈ A \ M (R, A) takový, zˇ e by byl preferován nad nˇejakým prvkem z M (R, A). Existuje pro jedincovu rozhodovac´ı situaci vˇzdy maximáln´ı mnoˇzina? Jaké vlastnosti mus´ı splˇnovat jedincova preferenˇcn´ı relace, aby maximáln´ı mnoˇzina existovala? Maximáln´ı mnoˇzina je návod pro hledán´ı maxima na mnoˇzinˇe alternativ, ale existuje pouze tehdy pokud preferenˇcn´ı relace tvoˇr´ı uspoˇra´ dán´ı na mnoˇzinˇe alternativ, je tedy u´ plná, reflexivn´ı a tranzitivn´ı. Pro to, aby preferenˇcn´ı relace mˇela maximáln´ı mnoˇzinu jsou nejd˚uleˇzitˇejˇs´ı jej´ı vlastnosti u´ plnost ´ a tranzitivita. Uplnost relace je vlastnost ˇr´ıkaj´ıc´ı, zˇ e pro kaˇzdé dvˇe r˚uzné alternativy a1 , a2 ∈ A plat´ı 12

budˇ a1 Ra2 nebo a2 Ra1 nebo plat´ı oboje souˇcasnˇe. Z hlediska interpretace této vlastnosti t´ım m´ın´ıme stav, kdy hrácˇ má názor na preferenci nad vˇsemi svými alternativami. Tento fakt se m˚uzˇ e jevit jako naprosto pˇrirozený, ale spousta psycholog˚u zde nam´ıtá, zˇ e tento poˇzadavek nen´ı aˇz tak samozˇrejmý. Zkusme si vzpomenout, kdy v nˇekterých situac´ıch ˇr´ıkáme ”nev´ım” nebo ”na toto nemám názor” nebo ”nem˚uzˇ u si vybrat z tˇechto variant”. Pokud hrácˇ ova preferenˇcn´ı relace splˇnuje u´ plnost, pak jeˇstˇe nav´ıc mus´ı m´ıt urˇcitou vnitˇrn´ı logickou konzistenci. Ta je vyjádˇrena poˇzadavkem tranzitivity relace, která ˇr´ıká, zˇ e pokud máme a1 Ra2 a souˇcasnˇe a2 Ra3 , pak rozhodnˇe mus´ı být dvojice (a1 , a3 ) prvkem preferenˇcn´ı relace. Pokud tedy jedinec preferuje Plzeˇn nad Radegastem, a Radegast nad Starobrnem, rozhodnˇe by nemˇel pochybovat o preferenci Plznˇe nad Starobrnem. Pokud pˇresto (Starobrno, P lzen) ∈ R, pak jedinec nemá sˇanci provést rozhodnut´ı, neboˇt se mu preference zacykl´ı P lzen ≥ Radegast ≥ Starobrno ≥ P lzen. Tyto vlastnosti (úplnost, reflexivita, tranzitivita) u preferenˇcn´ı relace dˇelaj´ı z preferenˇcn´ı relace u´ plné neostré uspoˇra´ dán´ı (angl. weak ordering). Definice 6. Mˇejme relaci R ⊆ A × A. Pokud je R u´ plná, tranzitivn´ı a reflexivn´ı, pak tvoˇr´ı u´ plné neostré uspoˇra´ dán´ı na mnoˇzinˇe A. Vˇeta 1. Je-li A koneˇcná neprázdná mnoˇzina a R u´ plné neostré uspoˇra´ dán´ı na A, pak M (R, A) 6= ∅. Proof. Nechˇt A je koneˇcná mnoˇzina a R je u´ plná, reflexivn´ı a tranzitivn´ı relace. D˚ukaz bude proveden matematickou indukc´ı. Krok 1: Je-li A jednoprvková mnoˇzina, tedy A = {a}, pak z reflexivity plyne aRa a proto M (R, A) = {a}. Krok 2: Ukázˇ eme, zˇ e je-li tvrzen´ı pravdivé pro A0 s n prvky a relaci R0 na A0 , pak mus´ı být pravdivé i pro libovolnou A s n + 1 prvky a uspoˇra´ dán´ı R. ˚ Dukaz kroku 2: Budeme pracovat s mnoˇzinami A a A0 , kde A = A0 ∪ {a}. Na mnoˇzinách A a A0 jsou definovány uspoˇra´ dán´ı R a R0 tak, zˇ e R0 je R omezená na A0 , tedy R0 = R ∩ (A0 × A0 ). Dle naˇsich pˇredpoklad˚u (a dle postupu matematické indukce) je M (R0 , A0 ) 6= ∅. Pak z pˇredpoklad˚u u´ plnosti preferenˇcn´ı relace plyne, zˇ e pro libovolné y ∈ M (R0 , A0 ) plat´ı budˇ yRa nebo aRy nebo plat´ı oboje. Budeme proto zkoumat dvˇe varianty preferenc´ı y a novˇe pˇridané alternativy a: 1. Plat´ı yRa neboli prvky maxima na A0 jsou preferovány nad novým prvkem a. Pak tedy yRz pro vˇsecny z ∈ A0 ∪ {a} (z definice maximáln´ı mnoˇziny) a proto y ∈ M (R, A). A t´ım dokazujeme krok 2. 2. Plat´ı aRy. Pokud tedy y ∈ M (R0 , A0 ), pak yRz pro libovolné z ∈ A0 . Vycház´ıme z aRy a v´ıme, zˇ e yRz pro vˇsechny z ∈ A0 . Z tranzitivity R plyne aRz pro vˇsechny z ∈ A0 . Obecnˇe to implikuje aRw pro vˇsechny w ∈ A0 a proto a ∈ M (R, A) a to opˇet dokazuje krok 2. Principem matematické indukce jsme dokázali tuto vˇetu pomoc´ı krok˚u 1 a 2.

13

2.2

Teorie uˇzitku

Pokud d˚usledek nˇejaké akce chápeme jako zisk, pak je nutno zkoumat, jaký nám ten zisk pˇrinese uˇzitek. Je jasné, zˇ e zisk tis´ıce CZK je pro kaˇzdého cˇ lovˇeka stejný zisk tis´ıce CZK. Chudému cˇ lovˇeku vˇsak tento zisk pˇrinese vˇetˇs´ı uˇzitek neˇz miliardáˇri. Uˇzitek je v ekonomii chápán jako subjektivn´ı m´ıra uspokojen´ı plynouc´ı ze spotˇreby statk˚u. Neˇz zaˇcneme zkoumat zisk a uˇzitek, zavedeme si dva zp˚usoby zkoumán´ı dvou odliˇsných d˚usledk˚u x a y: • Ordinalistický pˇr´ıstup – poznáme, zˇ e x je lepˇs´ı neˇz y nebo naopak nebo jsou oba stejné. Takto jsme schopni porovnávat alternativy. • Kardinalistický pˇr´ıstup – kromˇe prostého porovnán´ı x a y, kde je napˇr. x lepˇs´ı neˇz y, jsme nav´ıc schopni vyˇc´ıslit, kolikrát je x lepˇs´ı neˇz y. Jsme tedy schopni kvantifikovanˇe vyjádˇrit rozd´ıl |x − y|. ˇ Rekli jsme, zˇ e za pˇredpokladu bijektivnosti uˇzitkové funkce u : A → X si m˚uzˇ eme zvolit, zdaˇ li budeme hledat maximum na alternativách nebo d˚usledc´ıch. Pro poˇra´ dek si zavedme relaci slabé preference na d˚usledc´ıch: Definice 7. Mˇejme mnoˇzinu alternativ A, mnoˇzinu d˚usledk˚u X, uˇzitkovou funkci u z A na X a relaci slabé preference R ⊆ A × A. Nechtˇ potom: • u(x) ≥ u(y) ⇔ xRy • u(x) > u(y) ⇔ xP y • u(x) = u(y) ⇔ xIy A dále: ˇ Definice 8. Mˇejme mnoˇzinu alternativ A a preferenˇcn´ı relaci R ⊆ A2 . Rekneme, zˇe uˇzitková funkce u : A → R reprezentuje R, pokud pro vˇsechny x, y ∈ A : u(x) ≥ u(y) ⇔ xRy. Pˇrechod od zkoumán´ı preferenc´ı nad alternativami ke zkoumán´ı nad d˚usledky jeˇstˇe sám o sobˇe neumoˇznˇ uje kardinalistický pˇr´ıstup, tedy vyhodnocen´ı rozd´ılu |u(x)−u(y)|, ∀x, y ∈ A. Proto budeme obvykle klást X = R, tedy u : A → R a formulovat d˚usledky (nyn´ı jiˇz zisky) reálnými cˇ´ısly. Dodejme, zˇ e následuj´ıc´ı algoritmy teorie her právˇe zkoumaj´ı m´ıru rozd´ılu zisku mezi dvˇema alternativami. Maximáln´ı mnoˇzinu lze jiˇz pak definovat velmi intuitivnˇe, a sice jako:

14

M (u, A) = arg max[u(a)] a∈A

Pˇrechodem od ordinalistického zkoumán´ı preferenc´ı nad alternativami ke kardinalistickému zkoumán´ı nad cˇ´ıselnými zisky se algoritmy rozhodován´ı sice zjednoduˇsuj´ı, ale problém modelován´ı situace se pˇresouvá k validn´ımu ohodnocen´ı d˚usledku volby jedince tak, aby ohodnocen´ı bylo sjednocuj´ıc´ı pro vˇsechny hrácˇ e ve hˇre. To je ovˇsem uˇz problém samotného modelován´ı rozhodovac´ıch situac´ı a pro u´ vodn´ı studium her je tato poznáma znaˇcnˇe pˇredˇcasná.

2.2.1

Uˇzitek ze zisku

Jako demonstraci zkoumán´ı vztahu mezi ziskem a uˇzitkem si ukázˇ eme tak zvaný St. Petersbourg paradox vyslovený Danielem Bernoullim v roce 1738. Mˇejme hru mezi u´ cˇ astn´ıkem a bankéˇrem, kde u´ cˇ astn´ık zaplat´ı vstupn´ı poplatek c a pak házˇ e minc´ı tak dlouho, dokud nepadne hlava. Bankéˇr souhlas´ı, zˇ e mu zaplat´ı 1 dukát, pokud padne v prvn´ım hodu, 2 dukáty v druhém hodu, 4 v tˇret´ım hodu, atd. Oˇcekávaný zisk hrácˇ e tedy mus´ı být nekoneˇcný: ∞

X1 1 1 1 1 1 1 1 1 =∞ E = (−c) + 1 + 2 + 4 + 8 + ...+ = + + + + ... = 2 4 8 16 2 2 2 2 2 k=1 Problém je, zˇ e s t´ımto vˇetˇsina reálných lid´ı nesouhlas´ı a za svou u´ cˇ ast by nezaplatili v´ıce neˇz 20 dukát˚u, dokonce by radostnˇe prodali svou u´ cˇ ast ve hˇre za 20 dukát˚u. Jak je toto moˇzné? Proˇc vˇetˇsina lid´ı preferuje jistotu dvaceti dukát˚u pˇred teoreticky nekoneˇcným ziskem? St. Petersbourg paradox vyvolal diskuzi, jaký je vlastnˇe uˇzitek z pˇrijet´ı nˇejakého (napˇr. finanˇcn´ıho) vstupu. Gabriel Cramer pˇri korespondenci s D. Bernoullim prohlásil, zˇ e lidé hodnot´ı finanˇcn´ı cˇ a´ stky podle uˇzitku, který jim pˇrinesou. Doplnil následuj´ıc´ı pˇredpoklad: jakákoliv cˇ a´ stka pˇresahuj´ıc´ı 224 dukát˚u cˇ lovˇeku pˇripadá stejná jako 224 dukát˚u. Pak je oˇcekávaný uˇzitek hry: 1 1 1 1 1 1 1 + 2 + 4 + ... + 24 223 + 25 224 + 26 224 + ...+ = 2 4 8 2 2 2 1 1 1 1 1 + + ... + + + + ... = 12 + 1 = 13 2 2 2 4 8 Potom je realisticky oˇcekávaný uˇzitek ze hry 13 dukát˚u. Daniel Bernoulli pokraˇcoval ve své u´ vaze dále. Definoval poˇcet jednotek uˇzitku u(x) z vlastnictv´ı cˇ a´ stky x. Podle nˇej, pˇri navýsˇen´ı majetku z x na x + dx je pˇr´ırustek uˇzitku du(x) pˇr´ımo u´ mˇerný pˇr´ırustku dx a nepˇr´ımo u´ mˇerný dosavadn´ımu majetku x (dále bude α znaˇcit poˇca´ teˇcn´ı majetek a b ∈ R+ berme jako nˇejaký subjektivn´ı koeficient vn´ımán´ı pˇr´ırustku). Podotknˇenme, zˇ e tento zp˚usob =

15

vn´ımán´ı uˇzitku se nazývá Logoritmický uˇzitek. du(x) =

b dx x

Po integraci celé rovnice obdrˇz´ıme: u(x) = b ln x + c; c ∈ R Integraˇcn´ı konstantu c vyjádˇr´ıme jako vn´ımán´ı poˇca´ teˇcn´ıho majetku α a formulujeme stejným zp˚usobem jako pˇr´ırustek majetku. x α coˇz obecnˇe vyjadˇruje uˇzitek ln(po akci) − ln(pˇred akc´ı). Kdyˇz nyn´ı vyjádˇr´ıme oˇcekávaný uˇzitek ze hry pomoc´ı logaritmického uˇzitku, dostáváme (ovˇsem bez pˇripom´ınky G. Cramera o hraniˇcn´ım majetku): u(x) = b ln x − b ln α = b ln

∞ X α + 2n−1 1 b ln = E= n 2 α n=1 1

1

1

= b ln [(α + 1) 2 (α + 2) 4 (α + 4) 8 ...] − b ln α ˇ astka D, jej´ızˇ pˇridán´ı k poˇca´ teˇcn´ımu Kolik tedy mus´ı hrácˇ vyhrát, aby jeho uˇzitek byl kladný? C´ majetku pˇrinese stejný uˇzitek jako uˇzitek z výhry ve hˇre je dána vztahem, kde na levé stranˇe rovnice máme uˇzitek z pˇr´ırustku D a na pravé uˇzitek z výhry: i h 1 1 1 α+D 2 4 8 b ln = b ln (α + 1) (α + 2) (α + 4) ... − b ln α α z toho plyne, zˇ e takové D je: h i 1 1 1 D = (α + 1) 2 (α + 2) 4 (α + 4) 8 ... − α √ √ √ Pro nulové α = 0 poˇca´ teˇcn´ı jmˇen´ı je D = 2 1 · 4 2 · 8 4 · · · = 2. M´ıt nulový poˇca´ teˇcn´ı majetek, tak nezaplat´ım za uˇcast ve hˇre v´ıc neˇz dva dukáty. Promyslete si, jaký uˇzitek pˇrinese hra hrácˇ i s nenulovým poˇca´ teˇcn´ım majetem α.

2.3

˚ zité poznatky Duleˇ

Provedeme výcˇ et d˚uleˇzitých poznatk˚u na závˇer kapitoly o volbˇe a uˇzitku: • Jedinec se rozhoduje nad volbou jedné z mnoˇziny alternativ A. 16

• Pokud má být jedincova volba racionáln´ı, mus´ı nad mnoˇzinou alternativ A definovat relaci slabé (neostré) preference R, která mus´ı být u´ plná, reflexivn´ı a tranzitivn´ı. • Pokud preferenˇcn´ı relace splˇnuje tyto tˇri vlastnosti, existuje na n´ı maximáln´ı mnoˇzina M (R, A), která obsahuje pro jedince optimáln´ı volby. • Alternativnˇe m˚uzˇ eme kaˇzdé volbˇe alternativy pˇrisoudit kvantifikovatelný d˚usledek (zisk, uˇzitek) formou uˇzitkové funkce u : A → R. Vˇetˇs´ı cˇ a´ st THE pracuje s uˇzitkovými funkcemi, kde jsou preference evidentn´ı. • Nˇekdy chceme zkoumat subjektivn´ı uˇzitek z nˇejakého objektivn´ıho zisku.

17

Doprovodné texty ke kurzu Teorie her

Recommend Documents