Úvod do teorie her ZVYŠOVÁNÍ ODBORNÝCH KOMPETENCÍ AKADEMICKÝCH PRACOVNÍKŮ OSTRAVSKÉ UNIVERZITY V OSTRAVĚ A SLEZSKÉ UNIVERZITY V OPAVĚ

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.



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).



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í).



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


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


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


— 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ů.




10

VĚZŇOVO DILEMA Výplaty hráčů shrnuje následující tabulka: 2. hráč


přiznat se (zradit)

11

1. hráč


–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áč



12

1. hráč


–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}.


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.


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


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


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


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).


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


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.



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.



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).




22

Úvod do teorie her ZVYŠOVÁNÍ ODBORNÝCH KOMPETENCÍ AKADEMICKÝCH PRACOVNÍKŮ OSTRAVSKÉ UNIVERZITY V OSTRAVĚ A SLEZSKÉ UNIVERZITY V OPAVĚ

Recommend Documents