Úvod do teorie her David Bartl, Lenka Ploháková Abstrakt Předložený text „Úvod do teorie her“ pokrývá čtyři nejdůležitější, vybrané kapitoly z této oblasti. Nejprve je čtenář seznámen s předmětem studia teorie her. Následuje kapitola o jedné základní, dnes již klasické části, totiž teorii maticových her a jejich souvislostem s oborem lineárního programování. Další kapitola je věnována hrám dvojmaticovým; poté obecnějším nekooperativním hrám n hráčů ve strategickém tvaru. Dokazujeme klasickou větu Nikaidô-Isody o existenci bodu Nashovy rovnováhy v konvexní hře; připomínáme potřebný netriviální matematický aparát nutný k jejímu důkazu. Závěrečná kapitola je věnována konceptům řešení kooperativních s přenosnou výhrou; uvádíme také řadu vztahů, které mezi koncepty řešení kooperativních her platí. Klíčová slova teorie her, maticové hry, dvojmaticové hry, konvexní hry, věta Nikaidô-Isody, bod Nashovy rovnováhy, kooperativní hry s přenosnou výhrou, koncepty řešení kooperativních her, jádro, vyjednávací množina
1
Úvod
Teorie her se zabývá studiem rozhodovacích situací. Účastníci rozhodovací situace – jejíž matematický model nazýváme hrou – se nazývají hráči. Model je popis dané rozhodovací situace matematickými prostředky, tj. pomocí množin, bodů, funkcí, čísel apod. Hry můžeme dělit podle různých kritérií: podle počtu hráčů (hry s jedním hráčem, se dvěma hráči, s obecným počtem n hráčů, s nekonečně mnoha hráči), podle existence spolupráce mezi hráči (nekooperativní hry, kooperativní hry – ty dále dělíme na hry s výhrou přenosnou a na hry s výhrou nepřenosnou), podle počtu strategií (hry konečné, hry nekonečné). Zde se budeme zabývat hrami n hráčů ve strategickém tvaru. Taková hra je zadána: 1. množinou hráčů N = {1, 2, …, n}, 2. prostory strategií X1, X2, …, Xn, což jsou neprázdné množiny, 3. výplatními funkcemi F1, F2, …, Fn: X1 × X2 × ··· × Xn → R. Každému hráči i = 1, 2, …, n je přiřazen jeho prostor strategií Xi a jeho výplatní funkce Fi. Hra probíhá následovně: 1. Hráči zvolí strategie x1 ε X1, x2 ε X2, …, xn ε Xn. 2. Hra proběhne. 3. Hráči dostanou výplaty F1(x1, x2, …, xn), F2(x1, x2, …, xn), …, Fn(x1, x2, …, xn).
216
Zajímá nás, zda v této herní situaci existuje rovnovážný stav. Učiníme tyto předpoklady o hráčích: 1. Hra je nekooperativní. Každý hráč se rozhoduje samostatně, nezávisle na ostatních. 2. Každý hráč se snaží maximalizovat svoji vlastní výhru, a to bez ohledu na výhry ostatních. 3. Je splněn tzv. princip pomalé reakce: jestliže jen jeden hráč změní svoje jednání (tj. svoji strategii), potom ostatní hráči na tuto změnu nereagují (tj. svoje strategie nezmění). Potom klasickou odpovědí na položenou otázku je bod Nashovy rovnováhy (Nash, 1950). Bod [x*1, x*2, …, x*n] ε X1 × X2 × ··· × Xn je bodem Nashovy rovnováhy právě tehdy, když pro každého hráče i = 1, 2, …, n a pro každou jeho strategii xi ε Xi je splněna nerovnost Fi(x*1, …, x*i–1, xi, x*i+1, …, x*n) ≤ Fi(x*1, …, x*i–1, x*i, x*i+1, …, x*n). To znamená, že pokud pouze i-tý hráč změní svoje jednání z x*i na xi, potom jeho výplata nebude větší, což jej přiměje vrátit se zpátky do rovnovážného bodu. Je třeba zdůraznit, že není nikde řečeno, že bod Nashovy rovnováhy představuje řešení dané nekooperativní hry v tom smyslu, že hráči „by měli volit rovnovážné strategie a těchto strategií se držet“. Hráči ve skutečnosti mohou mít na výběr i jiné možnosti a záleží pouze na nich, zda je využijí (resp. dokáží využít; viz níže uvedený příklad vězňova dilematu). Spíše lze pojem Nashovy rovnováhy použít jako předpověď stavu, ve kterém hra může skončit, jestliže jsou splněny tři výše uvedené předpoklady. 2 Maticové hry Maticovou hrou rozumíme konečnou hru dvou hráčů ve strategickém tvaru s nulovým součtem. To znamená, že maticová hra je zadána: 1. množinou hráčů N = {1, 2}, 2. prostory strategií X1 = {1, 2, …, m}, X2 = {1, 2, …, n}, což jsou neprázdné konečné množiny, 3. výplatními funkcemi F1, F2: X1 × X2 → R, které pro všechna x1 ε X1, x2 ε X2 vyhovují rovnici F1(x1, x2) + F2(x1, x2) = 0. Pro pohodlí klademe X = X1, Y = X2 a F = F1. Snadno nahlédneme, že bod [x*, y*] ε X × Y je bodem Nashovy rovnováhy v zadané maticové hře právě tehdy, když je sedlovým bodem funkce F, tj., pro všechna x ε X, y ε Y platí nerovnice F(x, y*) ≤ F(x*, y*) ≤ F(x*, y). Protože jde o konečnou hru (prostory strategií jsou konečné množiny), výplaty prvního hráče je možné popsat maticí hry A typu m × n s prvky aij = F(i, j) pro i ε X a j ε Y. Smíšeným rozšířením zadané maticové hry rozumíme následující hru, která je zadána: 1. stejnou množinou hráčů N = {1, 2}, 2. prostory strategií X = { x ε Rm; x1, x2, …, xm ≥ 0 & x1+ x2 + ··· + xm = 1 }, Y = { y ε ε Rn; y1, y2, …, yn ≥ 0 & y1+ y2 + ··· + yn = 1 }, 3. výplatní funkcí prvního hráče F: X × Y → R určenou vztahem F(x, y) = xTAy pro všechna x ε X, y ε Y. (Výplatní funkce druhého hráče má opačné znaménko, tj., je jí funkce –F.)
Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.
217
Zatímco původní maticová hra bod Nashovy rovnováhy nemusí mít, její smíšené rozšíření má alespoň jeden bod Nashovy rovnováhy vždy – jde o jeden z klasických výsledků teorie her, tzv. hlavní větu maticových her. Její důkaz je konstruktivní a podává návod, jak ve smíšeném rozšíření bod Nashovy rovnováhy najít řešením úloh lineárního programování. V učebním textu uvádíme i další souvislosti mezi smíšenými rozšířeními maticových her a úlohami lineárního programování. 3 Dvojmaticové hry a obecné hry n hráčů ve strategickém tvaru Dvojmaticovou hrou rozumíme konečnou hru dvou hráčů ve strategickém tvaru. To znamená, že dvojmaticová hra je zadána: 1. množinou hráčů N = {1, 2}, 2. prostory strategií X1 = {1, 2, …, m}, X2 = {1, 2, …, n}, což jsou neprázdné konečné množiny, 3. výplatními funkcemi F1, F2: X1 × X2 → R. Dvojmaticová hra je hrou maticovou, jestliže výplatní funkce pro všechna x1 ε X1, x2 ε X2 splňují rovnici F1(x1, x2) + F2(x1, x2) = 0. To znamená, že dvojmaticové hry jsou obecnější nežli hry maticové. Také zde pro pohodlí klademe X = X1, Y = X2. Připomeňme, že bod [x*, y*] ε X × Y je bodem Nashovy rovnováhy v zadané dvojmaticové hře právě tehdy, když pro všechna x ε X, y ε Y platí nerovnice F1(x, y*) ≤ F1(x*, y*)
a
F2(x*, y) ≤ F2(x*, y*).
Výplaty prvního a druhého hráče je možné popsat dvěma maticemi A a B typu m × n s prvky aij = F1(i, j) a bij = F2(i, j) pro i ε X a j ε Y. Smíšené rozšíření dvojmaticové hry zavádíme obdobně: výplatní funkce F1: X × Y → R a F2: X × Y → R prvního a druhého hráče jsou určeny vztahy F1(x, y) = xTAy a F2(x, y) = xTBy pro všechna x ε X a y ε Y. Neboť maticová hra nemusí bod Nashovy rovnováhy mít, ani obecnější dvojmaticová hra nemusí bod Nashovy rovnováhy mít. Zatímco podat důkaz existence Nashovy rovnováhy ve smíšeném rozšíření maticové hry je vcelku snadné (jde o aplikaci teorie duality lineárního programování), dokázat existenci Nashovy rovnováhy ve smíšeném rozšíření dvojmaticové hry je úkol velice netriviální. V učebním textu ji dokazujeme jako důsledek klasické věty Nikaidô-Isody (Nikaidô, Isoda, 1955). Uvažujme obecnou hru n hráčů ve strategickém tvaru (viz úvod). Tato hra se nazývá konvexní právě tehdy, když platí: 1. Pro každé i = 1, 2, …, n je prostor strategií Xi neprázdná kompaktní konvexní podmnožina euklidovského prostoru konečné dimenze (která pro každé i může být jiná). 2. Výplatní funkce Fi(x1, …, xi–1, xi, xi+1, …, xn) je konkávní v proměnné xi ε Xi, když ostatní proměnné x1, …, xi–1, xi+1, …, xn jsou zvoleny libovolně pevně. 3. Výplatní funkce Fi(x1, …, xi–1, xi, xi+1, …, xn) je spojitá v proměnných x1, …, xi–1, xi+1, …, xn, když proměnná xi ε Xi je zvolena libovolně pevně. 4. Součet ∑iεN Fi(x1, x2, …, xn) výplatních funkcí je spojitý ve všech proměnných. Věta Nikaidô-Isody říká: Každá konvexní hra má alespoň jeden bod Nashovy rovnováhy. V učebním textu podáváme důkaz tohoto klasického výsledku. Důkaz je založen na jiných ne zcela triviálních výsledcích, Heineho-Borelově pokrývací větě a Brouwerově větě o pevném bodě. Tyto věty v učebním textu také dokazujeme. Brouwerovu větu 218
dokazujeme poměrně elementárním způsobem, pomocí Spernerova lemmatu, jehož důkaz v textu rovněž podáváme. Vězňovo dilema Je slavným příkladem dvojmaticové hry. Představme si následující herní situaci. Dva lupiči jsou zadrženi policií a jsou vyslýcháni odděleně. Každý z obou kumpánů má na výběr z právě dvou možností: buď se přizná (čímž ovšem shodí kamaráda, jde ale také o polehčující okolnost před soudem), anebo bude zapírat (jestliže i kamarád zapírá, potom policie nic nezjistí, jinak jde o přitěžující okolnost). Jestliže budou oba lupiči zapírat (v terminologii teorie her budou navzájem spolupracovat), potom policie je bude muset oba propustit a vzájemně se podělí o naloupených 10 melounů (každý z nich bude mít 5 melounů). Jestliže se oba přiznají, potom oba půjdou do vězení na 5 let. Jestliže jeden zapírá (snaží se být solidární) a druhý se přizná (shodí kamaráda), potom ten, který zapíral, dostane 10 let, a ten, který se přiznal, bude propuštěn a ještě dostane celý lup 10 melounů. Výplaty hráčů shrnuje následující tabulka: 2. hráč přiznat se (zradit)
1. hráč
přiznat se (zradit) zapírat (spolupracovat)
zapírat (spolupracovat)
–5
–5
10
–10
–10
10
5
5
Povšimněme si, že tato hra má bod Nashovy rovnováhy. Je jím dvojice strategií [přiznat se, přiznat se]. Záleží tedy na tom, jak oba lupiči své dilema pojmou: zda jako hru nekooperativní, anebo jako kooperativní. Zvolí-li si nekooperativní variantu, znamená to, že každý z nich bude toliko hrabivě maximalizovat svůj vlastní prospěch, nehledě na kamaráda. Potom – s využitím teorie her – můžeme předpovědět, že hra skončí v rovnovážném bodě, tzn., že oba půjdou do vězení na 5 let, aby se poučili. Jestliže zvolí kooperativní variantu, potom zvolí dvojici [zapírat, zapírat] a každý dostane žádoucí výplatu 5 melounů. 4 Kooperativní hry Uvažujme hru s množinou hráčů N = {1, 2, …, n}. Je-li tato hra kooperativní, hráči vytvářejí koalice. Předpokládáme, že v rámci koalice hráči spolupracují, aby dosáhli maximálního společného zisku celé koalice. Matematicky tuto situaci modelujeme následovně: koalicí rozumíme libovolnou podmnožinu K množiny hráčů N. Zde budeme uvažovat pouze hry s přenosnou výhrou. To znamená, že celková výplata koalice je přerozdělitelná mezi její jednotlivé členy. Kooperativní hry s přenosnou výhrou lze studovat ve více tvarech (podle dané situace); nejčastěji se používá tvar koaliční funkce. Potenční množinou P(N) zadané množiny hráčů N rozumíme množinu všech jejích podmnožin. Potenční množina P(N) = { K; K je podmnožinou množiny N } je tedy kolekcí všech koalic, které mohou potenciálně vzniknout. Potom koaliční funkcí rozumíme zobrazení v: P(N) → R, takové, že v(Ø) = 0. Číslo v(K), které je koalici K přiřazeno, chápeme jako celkový zisk koalice K, jestliže tato koalice vznikla. Používáme konvenci, že zisk prázdné koalice je nulový. Dále předpokládáme, že hráči vytvoří koaliční strukturu, tj., rozdělí se do disjunktních koalic. Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.
219
Kolekce koalic S = {S1, S2, …, Sr} tvoří koaliční strukturu právě tehdy, když platí: 1. koalice S, T ε S nejsou disjunktní právě tehdy, když S = T, 2. sjednocením všech koalic z S je množina hráčů N. Nyní předpokládáme, že v rámci každé koalice S1, S2, …, Sr ε S si hráči chtějí přerozdělit celkový zisk v(S1), v(S2), …, v(Sr) své koalice mezi sebe. Rozdělení zisku popisujeme výplatním vektorem a ε Rn o složkách a1, a2, …, an, kde číslo ai je zisk připadnuvší i-tému hráči. Při dělení zisku se hráči patrně budou řídit některým z tzv. konceptů řešení. Oblíbeným je koncept jádra hry (Gillies, 1959). Jádrem kooperativní hry s množinou hráčů N a koaliční funkcí v vzhledem ke vniklé koaliční struktuře S rozumíme množinu všech výplatních vektorů a ε Rn takových, že ∑iεS ai ≤ v(S)
pro všechna S ε S,
∑iεK ai ≥ v(K)
pro všechna K ε P(N).
První z uvedených podmínek vyjadřuje podmínku přípustnosti: ve vzniklé koalici S ε S není možné přerozdělit více, než kolik činí její celkový zisk v(S). Druhá podmínka je podmínkou skupinové stability: pokud by se našla koalice K ε P(N) \ S, pro kterou by platila negace ∑iεK ai < v(K), potom by tato koalice vznikla (neboť po svém vzniku dosáhne většího zisku v(K), než který má dohromady nyní), což by mělo za následek zhroucení původní koaliční struktury S. Pro K ε S ovšem druhá podmínka vyjadřuje tzv. podmínku kolektivní racionálnosti, což znamená, že všichni hráči maximalizují své individuální zisky, tedy zisk v(S) své koalice si mezi sebe přerozdělí celý: dostáváme rovnost ∑iεS ai = v(S) pro S ε S. V učebním textu zavádíme také další koncepty řešení kooperativních her (vyjednávací množina, kernel, nukleolus, von Neumannovo-Morgensternovo řešení, Shapleyova hodnota). Dokazujeme také některé vztahy, které mezi uvedenými koncepty platí (např., jestliže jádro hry je neprázdné, potom má i neprázdný průnik s vyjednávací množinou atd.). 5 Závěr Na závěr uveďme jeden příklad ze života. (Příklad je skutečný, čísla jsou vymyšlená.) Před několika lety se katedra matematiky (KMA) PřF OU rozhodla vytvořit nový studijní obor nazvaný „Matematické a počítačové metody zpracování informace“. Účelem bylo vytvořit obor, který měl kombinovat předměty matematické i informatické, a měl tudíž být pro studenty zajímavý. Jedním z těchto předmětů měla být také „Teorie kódování a šifrování“. Problém byl v tom, že KMA v té době neměla žádného odborníka na tuto oblast. Ale na katedře informatiky a počítačů (KIP) PřF OU již tento předmět existoval, odborník na KIP byl k dispozici. Katedra matematiky uvažovala takto: Vytvářený obor „Matematické a počítačové metody zpracování informace“ bude jistě úspěšný, tedy v něm bude mnoho studentů. Když tito studenti budou chodit na výuku kódování na katedru informatiky a počítačů, potom všechny studentokredity (a tedy finance) za výuku tohoto předmětu (díky našim studentům) připadnou KIP – a to pro nás není přijatelné. Studentů v oboru totiž bude hodně. Tolik, že kdybychom předmět zajišťovali sami (jen pro své studenty), potom studentokreditů (financí) budeme mít tolik, že z nich budeme schopni zaplatit i externího odborníka. Uvedený příklad je možné modelovat jako kooperativní hru s přenosnou výhrou. Množina hráčů sestává z obou kateder, tedy N = {KIP, KMA}. Koaliční funkce mohla vypadat 220
takto: v({KIP, KMA}) = 80 (jestliže by obě katedry spolupracovaly, studenti KMA by se přidali k pár studentům KIP, kteří by společně chodili na kurs „Teorie kódování a šifrování“ zajišťovaný katedrou informatiky a počítačů; ta by také získala všechny studentokredity). v({KIP}) = 40 a v({KMA}) = 20 (katedra informatiky a počítačů učí pouze své studenty, ovšem má svého odborníka; katedra matematiky sice učí mnoho studentů, ovšem musí platit externího odborníka). Samozřejmě klademe v(Ø) = 0. Jestliže by obě katedry spolupracovaly, potom by vyjednávaly také o dělení zisku. Bylo by možné použít například koncept jádra, tj. množinu dvojic [aKIP, aKMA] ε R2 takových, že aKIP + aKMA = 80, aKIP ≥ 40, aKMA ≥ 20. Prvkem jádra je například dělení o souřadnicích aKIP = 50 a aKMA = 30. Obě katedry tedy mohly mít více peněz, než když každá učí svůj předmět samostatně (v({KIP}) = 40 a v({KMA}) = 20). 6 Literatura 1. NASH, John F., Jr. Equilibrium Points in n-Person Games. Proceedings of the National Academy of Sciences of the United States of America, 1950, Vol. 36, pp. 48–49. 2. NIKAIDÔ, Hukukane, ISODA, Kazuo. Note on non-cooperative convex games. Pacific Journal of Mathematics, 1955, Vol. 5, pp. 807–815. 3. GILLIES, Donald B. Solutions to general non-zero-sum games. In TUCKER, A. W., LUCE, R. D. (Eds.) Contributions to the Theory of Games: Volume IV. Princeton: Princeton University Press, 1959, pp. 47–85. (Annals of Mathematics Studies; No. 40). 4. PLOHÁKOVÁ, Lenka, BARTL, David. Úvod do teorie her. Ostrava: Ostravská univerzita v Ostravě, 2013. Učební text. RNDr. David Bartl, Ph.D.
[email protected] +420 597 092 276 Mgr. Lenka Ploháková
[email protected] +420 597 092 140 Katedra matematiky, Přírodovědecká fakulta Ostravská univerzita v Ostravě 30. dubna 22, 701 03 Ostrava
Tento projekt je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.
221
