ZVYŠOVÁNÍ ODBORNÝCH KOMPETENCÍ AKADEMICKÝCH PRACOVNÍKŮ
OSTRAVSKÉ UNIVERZITY V OSTRAVĚ A SLEZSKÉ UNIVERZITY V OPAVĚ
Úvod do teorie her David Bartl, Lenka Ploháková
OSNOVA Úvod (hra n hráčů ve strategickém tvaru) Dvojmaticové hry
Vězňovo dilema
Kooperativní hry Závěr aneb příklad ze života Hradec nad Moravicí listopad 2013
2
Hradec nad Moravicí listopad 2013
HRA N HRÁČŮ VE STRATEGICKÉM TVARU
3
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.
Hradec nad Moravicí listopad 2013
HRA N HRÁČŮ VE STRATEGICKÉM TVARU
4
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).
Hradec nad Moravicí listopad 2013
HRA N HRÁČŮ VE STRATEGICKÉM TVARU
5
— existuje rovnovážný stav? Předpoklady: Hra je nekooperativní. Každý hráč se rozhoduje samostatně, nezávisle na ostatních. Každý hráč se snaží maximalizovat svoji vlastní výhru, a to bez ohledu na výhry ostatních. 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í).
Hradec nad Moravicí listopad 2013
HRA N HRÁČŮ VE STRATEGICKÉM TVARU
6
Definice. Bod [x*1, x*2, …, x*n] ε X1 × X2 × ··· × Xn je bodem Nashovy rovnováhy (Nash, 1950) 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, x*i, x*i+1, …, x*n) ≤ Fi(x*1, …, x*i–1, x*i, x*i+1, …, x*n).
DVOJMATICOVÁ HRA
Hradec nad Moravicí listopad 2013
je konečná hra dvou hráčů ve strategickém tvaru;
7
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
Hradec nad Moravicí listopad 2013
Pro pohodlí klademe X = X1, Y = X2.
8
Protože jde o konečnou hru (prostory strategií jsou konečné množiny), 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. Jestliže pro všechna i ε X, j ε Y platí rovnice F1(i, j) + F2(i, j) = 0, potom jde o hru s nulovým součtem, zde o maticovou hru. Stačí znát pouze výplatní funkci F = F1 resp. matici A. (Druhá se dopočítá ze vztahu F2 = −F.)
VĚZŇOVO DILEMA
Hradec nad Moravicí listopad 2013
— slavný příklad dvojmaticové hry.
9
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).
VĚZŇOVO DILEMA 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ů.
Hradec nad Moravicí listopad 2013
10
VĚZŇOVO DILEMA Výplaty hráčů shrnuje následující tabulka: 2. hráč
Hradec nad Moravicí listopad 2013
přiznat se (zradit)
11
1. hráč
přiznat se (zradit)
–5 –5
zapírat –10 10 (spolupracovat)
zapírat (spolupracovat) 10 –10 5
5
VĚZŇOVO DILEMA Výplaty hráčů shrnuje následující tabulka: 2. hráč
Hradec nad Moravicí listopad 2013
přiznat se (zradit)
12
1. hráč
přiznat se (zradit)
–5 –5
zapírat –10 10 (spolupracovat)
zapírat (spolupracovat) 10 –10 5
Tato hra má bod Nashovy rovnováhy. Je jím dvojice strategií [přiznat se, přiznat se].
5
KOOPERATIVNÍ HRY Uvažujme hru s množinou hráčů N = {1, 2, …, n}.
Hradec nad Moravicí listopad 2013
Je-li tato hra kooperativní, hráči vytvářejí koalice.
13
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ě:
Definice. Koalicí rozumíme libovolnou podmnožinu K množiny hráčů N.
Hradec nad Moravicí listopad 2013
KOOPERATIVNÍ HRY
14
Definice. 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.
KOOPERATIVNÍ HRY
Hradec nad Moravicí listopad 2013
Zde uvažujeme pouze hry s přenosnou výhrou. To znamená, že celková výplata koalice je přerozdělitelná mezi její jednotlivé členy. Tyto hry budeme studovat ve tvaru koaliční funkce.
15
Definice. 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ý.
KOOPERATIVNÍ HRY
Hradec nad Moravicí listopad 2013
Dále předpokládáme, že hráči vytvoří koaliční strukturu, tj., rozdělí se do disjunktních koalic.
16
Definice. Kolekce koalic S = {S1, S2, …, Sr} tvoří koaliční strukturu právě tehdy, když platí: 1. koalice S, T ε S jsou disjunktní (S ∩ T = Ø) právě tehdy, když S ≠ T, 2. sjednocením všech koalic z S je množina hráčů N.
KOOPERATIVNÍ HRY
Hradec nad Moravicí listopad 2013
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.
17
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).
Hradec nad Moravicí listopad 2013
KOOPERATIVNÍ HRY
18
Definice. 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).
ZÁVĚR ANEB PŘÍKLAD ZE ŽIVOTA
Hradec nad Moravicí listopad 2013
Před několika lety se katedra matematiky (KMA) PřF OU rozhodla vytvořit nový studijní obor „Matematické a počítačové metody zpracování informace“.
19
Jedním z předmětů v oboru měla být také „Teorie kódování a šifrování“. 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.
Hradec nad Moravicí listopad 2013
ZÁVĚR ANEB PŘÍKLAD ZE ŽIVOTA
20
ÚVAHA (z hlediska katedry matematiky): 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.
Hradec nad Moravicí listopad 2013
ZÁVĚR ANEB PŘÍKLAD ZE ŽIVOTA
21
— jako kooperativní hra s přenosnou výhrou: 1. množina hráčů N = {KIP, KMA}; 2. koaliční funkce mohla vypadat takto: v(Ø) = 0, v({KIP, KMA}) = 80, v({KIP}) = 40, v({KMA}) = 20. Pro návrh řešení lze použít například koncept jádra hry. Jeho prvkem je například dělení o souřadnicích aKIP = 50, aKMA = 30.
REFERENCE 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. 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).
Hradec nad Moravicí listopad 2013
22