Pokud existuje několik konfliktních stran (osob), z nichž každá učiní určité rozhodnutí určené daným souborem pravidel a každá z nich zná konečný stav konfliktní situace s platbami předem určenými pro každou ze stran, pak se hraje se prý koná.
Úkolem teorie her je vybrat pro daného hráče linii chování, od které odchylka může pouze snížit jeho výhru.
Některé definice hry
Kvantitativní hodnocení výsledků hry se nazývá platba.
Čtyřhra (dvě osoby) se nazývá hra s nulovým součtem, pokud je součet plateb nulový, tzn. pokud se ztráta jednoho hráče rovná zisku druhého.
Jednoznačný popis volby hráče v každé z možných situací, ve kterých musí provést osobní tah, se nazývá strategii hráče .
Strategie hráče se nazývá optimální, pokud při mnohonásobném opakování hry poskytuje hráči maximum možného průměrné výhry(nebo, což je totéž, minimální možná průměrná výhra).
Hra definovaná maticí A mít m linky a n sloupců se nazývá hra konečných párů dimenzí m* n;
Kde i=
- strategie prvního hráče s mstrategií;
j=
- strategie druhého hráče s n strategiemi;
ij– výhry prvního hráče i-strategie při použití druhým j strategie (nebo, co je totéž, ztráta druhého v jeho j-th strategie, když je použita jako první i th);
A = ij – platební matice hry.
1.1 Hraní s čistými strategiemi
Nízká cena hry (pro prvního hráče)
= max (min ij). (1.2)
i j
Nejlepší cena hry (pro druhého hráče):
= min
(max
ij)
. (1.3)
J i
Li = , hra se nazývá saddle point game (1.4), neboli hra s čistými strategiemi. V čem PROTI = = nazýváno hodnotnou hrou ( PROTI- cena hry).
Příklad. Je uvedena platební matice hry pro 2 osoby A. Určete optimální strategie pro každého hráče a cenu hry:
(1.4)
max 10 9 12 6
i
min 6
j
- strategie prvního hráče (řada).
Strategie druhého hráče (sloupce).
- cena hry.
Tím pádem má hra sedlovou pointu. Strategie j = 4 – optimální strategie pro druhého hráče i=2 - pro první. Máme hru s čistými strategiemi.
1.2 Hry se smíšenými strategiemi
Pokud platební matice nemá sedlový bod, tzn. 
a nikdo ve hře si nemůže vybrat jeden plán jako svou optimální strategii, hráči přecházejí na „smíšené strategie“. Navíc každý hráč použije každou ze svých strategií během hry několikrát.
Vektor, jehož každá složka ukazuje relativní frekvenci hráčského použití odpovídající čisté strategie, se nazývá smíšená strategie tohoto hráče.
X= (X 1 …X i …X m) – smíšená strategie prvního hráče.
U= (na 1 ...y j ...y n) – smíšená strategie druhého hráče.
Xi , y j– relativní četnosti (pravděpodobnosti) hráčů využívajících své strategie.
Podmínky použití smíšených strategií
.
(1.5)
Li X* = (X 1 * ….X já*… X m*) – optimální strategie zvolená prvním hráčem; Y* = (na 1 * …na j*... na n*) je optimální strategie zvolená druhým hráčem, pak číslo je cena hry.
(1.6)
V pořadí podle čísla PROTI byla cena hry a X* A na* - optimální strategie, je nutné a dostačující k uspokojení nerovností
(1.7)
Pokud jeden z hráčů použije optimální smíšenou strategii, pak se jeho výplata rovná ceně hry PROTI bez ohledu na frekvenci, s jakou bude druhý hráč používat strategie zahrnuté v optimální, včetně čistých strategií.
Redukce problémů teorie her na problémy lineárního programování.
Příklad. Najděte řešení hry definované výplatní maticí A.
A = 
(1.8)
y 1 y 2 y 3
Řešení:
Vytvořme duální pár úloh lineárního programování.
Pro prvního hráče
(1.9)
na 1 +na 2 +na 3 = 1 (1.10)
Osvobození se od proměnné PROTI(cena hry), rozdělte levou a pravou stranu výrazů (1.9), (1.10) na PROTI. Po přijetí na j /PROTI pro novou proměnnou z i, dostaneme nový systém omezení (1.11) a cílová funkce (1.12)
(1.11)
.
(1.12)
Podobně získáme herní model pro druhého hráče:
(1.13)
X 1 +X 2 +X 3 = 1 . (1.14)
Redukční model (1.13), (1.14) na formu bez proměnné PROTI, dostaneme
(1.15)
,
(1.16)
Kde 
.
Pokud potřebujeme určit strategii chování prvního hráče, tzn. relativní četnost používání jeho strategií ( X 1 ….X i …X m), použijeme druhý model přehrávače, protože tyto proměnné jsou v jeho výplatním modelu (1.13), (1.14).
Zredukujeme (1.15), (1.16) na kanonickou formu
(1.17)
Úkol:
Maticová hra je dána následující výplatní maticí:
| Strategie "B" | ||||||||
| Strategie "A" | B 1 | B 2 | ||||||
| A 1 | 3 | 5 | ||||||
| A 2 | 6 |
|
||||||
Najděte řešení maticové hry, konkrétně:
- najít nejvyšší cenu hry;
- nižší cena hry;
- čistá cena hry;
- naznačit optimální strategie hráčů;
- přinést grafické řešení(geometrická interpretace), je-li to nutné.
Krok 1
Stanovme nižší cenu hry - α
Nejnižší cena hryα je maximální výhra, kterou si můžeme zaručit ve hře proti rozumnému soupeři, pokud během celé hry použijeme pouze jednu strategii (tato strategie se nazývá „čistá“).Najdeme v každém řádku matice plateb minimální prvek a zapište jej do dalšího sloupce (Vybráno žlutá viz tabulka 1).
Pak najdeme maximum prvek doplňkového sloupce (označený hvězdičkou), bude to nižší cena hry.
stůl 1
| Strategie "B" | |||||||||||||||
| Strategie "A" | B 1 | B 2 | Minima řádku | ||||||||||||
| A 1 | 3 | 5 | 3 * | ||||||||||||
| A 2 | 6 |
|
|
||||||||||||
V našem případě je nižší cena hry: a = 3 a abychom zaručili výhru ne horší než 3, musíme se držet strategie A 1
Krok 2
Stanovme horní cenu hry - β
Nejlepší cena hryβ je minimální ztráta, kterou si hráč B může zaručit ve hře proti rozumnému soupeři, pokud v průběhu hry používá jednu a pouze jednu strategii.Najdeme v každém sloupci matice plateb maximum prvek a napište jej na další řádek níže (zvýrazněný žlutě, viz tabulka 2).
Pak najdeme minimální prvek doplňkové řady (označený plusem), bude to horní cena hry.
tabulka 2
| Strategie "B" | ||||||||||||
| Strategie "A" | B 1 | B 2 | Minima řádku | |||||||||
| A 1 | 3 | 5 | 3 * | |||||||||
| A 2 | 6 |
| V našem případě je horní cena hry: β = 5 a aby byla zaručena prohra ne horší než 5, musí soupeř (hráč „B“) dodržovat strategii B 2 Krok: 3 Smíšená strategie, jedná se o čisté strategie náhodně se střídající, s určitou pravděpodobností (četností). Budeme označovat smíšenou strategii hráče „A“
|
|||||||||
kde B 1, B 2 jsou strategie hráče „B“ a q 1, q 2 jsou pravděpodobnosti, se kterými jsou tyto strategie aplikovány, a q 1 + q 2 = 1.
Optimální smíšená strategie pro hráče „A“ je ta, která mu zajistí maximální výplatu. V souladu s tím je pro „B“ minimální ztráta. Tyto strategie jsou určeny S A* a S B* resp. Řešení hry tvoří dvojice optimálních strategií.
V obecný případ Hráčova optimální strategie nemusí zahrnovat všechny počáteční strategie, ale pouze některé z nich. Takové strategie se nazývají aktivní strategie.
Krok: 4
Kde: p 1 , p 2 - pravděpodobnosti (četnosti), se kterými jsou aplikovány strategie A 1 a A 2, resp.
Z teorie her je známo, že pokud hráč „A“ používá svou optimální strategii a hráč „B“ zůstává v rámci svých aktivních strategií, pak průměrná výplata zůstává nezměněna a rovná se ceně hry. proti bez ohledu na to, jak hráč B používá své aktivní strategie. A v našem případě jsou obě strategie aktivní, jinak by hra měla řešení v čistých strategiích. Pokud tedy předpokládáme, že hráč „B“ použije čistou strategii B 1, pak průměrná výplata proti bude:
k 11 p 1 + k 21 p 2 = v (1)
Kde: k ij - prvky platební matice.
Na druhou stranu, pokud předpokládáme, že hráč „B“ použije čistou strategii B 2, pak průměrná výplata bude:
k 12 p 1 + k 22 p 2 = v (2)
Srovnáním levých stran rovnic (1) a (2) dostaneme:
k 11 p 1 + k 21 p 2 = k 12 p 1 + k 22 p 2
A s přihlédnutím k faktu, že p 1 + p 2 = 1 my máme:
k 11 p 1 + k 21 (1 - p 1 ) = k 12 p 1 + k 22 (1 - p 1 )
Kde je snadné najít optimální frekvenci strategie A 1:
| p 1 = |
| (3) |
V tomto úkolu:
| p 1 = |
| = |
|
Pravděpodobnost R 2 najít odečtením R 1 z jednotky:
| p 2 = 1 - p 1 = | 1 | - |
| = | + | 6 | · |
Kde: q 1 , q 2 - pravděpodobnosti (četnosti), se kterými jsou aplikovány strategie B 1 a B 2, resp.
Z teorie her je známo, že pokud hráč „B“ používá svou optimální strategii a hráč „A“ zůstává v rámci svých aktivních strategií, pak průměrná výplata zůstává nezměněna a rovná se ceně hry. proti bez ohledu na to, jak hráč A používá své aktivní strategie. Pokud tedy předpokládáme, že hráč „A“ použije čistou strategii A 1, pak průměrná výplata proti bude:
k 11 q 1 + k 12 q 2 = v (4)
Vzhledem k ceně hry proti už víme a uvažujeme o tom q 1 + q 2 = 1 , pak optimální frekvenci strategie B 1 lze nalézt jako:
| q 1 = |
| (5) |
V tomto úkolu:
| q 1 = |
| = |
|
Pravděpodobnost q 2 najít odečtením q 1 z jednotky:
| q 2 = 1 - q 1 = | 1 | - |
| = |
|
Odpovědět:
| Nejnižší cena hry: | α = | 3 | |||
| Nejlepší cena hry: | β = | 5 | |||
| Cena hry: | proti = |
|
| Optimální strategie hráče A: |
|
|||||||||||||||
| Optimální strategie pro hráče "B": |
|
Geometrická interpretace (grafické řešení):
Uveďme geometrickou interpretaci uvažované hry. Vezměte část osy úsečky o jednotkové délce a nakreslete svislé přímky přes její konce A 1 A A 2 odpovídající našim strategiím A 1 a A 2 . Předpokládejme nyní, že hráč „B“ použije strategii B 1 in čistá forma. Pak, pokud (hráč „A“) použijeme čistou strategii A 1, bude naše výplata 3. Označme odpovídající bod na ose A 1 .Pokud použijeme čistou strategii A 2, bude naše výplata 6. Označme odpovídající bod na ose A 2
(viz obr. 1). Je zřejmé, že pokud použijeme smíchání strategií A 1 a A 2 v různých poměrech, naše výhry se budou měnit podél přímky procházející body se souřadnicemi (0, 3) a (1, 6), nazvěme to čára strategie B 1 (na obr. .1 znázorněn červeně). Úsečka libovolného bodu na dané přímce se rovná pravděpodobnosti p 2 (frekvence), se kterou aplikujeme strategii A 2, a pořadnice - výsledný zisk k (viz obr. 1).
Obrázek 1.
Výplatní graf k
z frekvence p 2
, když nepřítel použije strategii B 1.
Předpokládejme nyní, že hráč „B“ použije strategii B 2 v její čisté podobě. Pak, pokud (hráč „A“) použijeme čistou strategii A 1, bude naše výplata 5. Pokud použijeme čistou strategii A 2, bude naše výplata 3/2 (viz obr. 2). Podobně, pokud smícháme strategie A 1 a A 2 v různém poměru, naše výhry se budou měnit po přímce procházející body se souřadnicemi (0, 5) a (1, 3/2), říkejme tomu čára strategie B 2. Stejně jako v předchozím případě je úsečka libovolného bodu na této přímce rovna pravděpodobnosti, s jakou aplikujeme strategii A 2, a ordináta je výsledný zisk, ale pouze pro strategii B 2 (viz obr. 2).
Obrázek 2
proti
a optimální frekvenci p 2
pro hráče "A".
Ve skutečné hře, kdy rozumný hráč „B“ použije všechny své strategie, se naše výhry budou měnit podél přerušované čáry znázorněné na obr. 2 červeně. Tato linie vymezuje tzv spodní hranice výher. Jednoznačně nejvíc vysoký bod tato přerušovaná čára odpovídá naší optimální strategii. V v tomto případě, to je průsečík čar strategií B 1 a B 2. Vezměte prosím na vědomí, že pokud zvolíte frekvenci p 2 roven jeho úsečce, pak náš zisk zůstane nezměněn a stejný proti pro jakoukoli strategii hráče „B“ to navíc bude maximum, co můžeme sami garantovat. Frekvence (pravděpodobnost) p 2 , je v tomto případě odpovídající frekvence naší optimální smíšené strategie. Mimochodem, z obrázku 2 vidíte frekvenci p 1 , naší optimální smíšenou strategií, je délka segmentu [ p 2 ; 1] na ose x. (To je Protože p 1 + p 2 = 1 )
Pomocí zcela podobné úvahy můžeme najít frekvence optimální strategie pro hráče „B“, která je znázorněna na obrázku 3.
Obrázek 3
Grafické stanovení ceny hry proti
a optimální frekvenci q 2
pro hráče "V".
Pouze pro něj by měla být tzv horní limit prohrává(červená přerušovaná čára) a hledejte na ní nejnižší bod, protože pro hráče "B" je cílem minimalizovat ztráty. Stejná hodnota frekvence q 1 , to je délka segmentu [ q 2 ; 1] na ose x.
Obsah 1 Obecná informace 2 1.1 Hry. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Tahy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Strategie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Matrixová hra. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Trail point. Čisté strategie 7 2.1 Příklady. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Příklad 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Příklad 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Smíšené strategie 9 3.1 Hra 2×2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.1 Příklady . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Příklad 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Příklad 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1.2 Geometrická interpretace. . . . . . . . . . . . . . . . . . . . 12 3.2 Hry 2×n a m×2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Příklad 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1 1. Obecné informace z teorie her 1.1. Hry Teorie her je matematická teorie konfliktních situací, tzn. situace, ve kterých se střetávají zájmy dvou nebo více stran sledujících různé cíle. Hra je konfliktní situace regulovaná určitými pravidly, která musí udávat: možné možnosti jednání účastníků; kvantitativní výsledek hry nebo platby (výhra, prohra), ke které daný soubor tahů vede; množství informací každé strany o chování té druhé. Čtyřhra je hra, které se účastní pouze dvě strany (dva hráči). Párová hra s nulovým součtem je párová hra, ve které je součet plateb nulový, tzn. Ztráta jednoho hráče se rovná zisku druhého. V závislosti na postoji každého hráče k hodnotě výplatní funkce se párové hry dále dělí: Párová hra s nulovým součtem (antagonistická) - párová hra, ve které je výše plateb rovna nule, tzn. Ztráta jednoho hráče se rovná zisku druhého. Neantagonistická hra je párová hra, ve které hráči sledují různé, ale ne přímo opačné cíle. 2 1.2. Pohyby Pohyb - volba jedné z akcí stanovených pravidly hry; provedení této volby. Pohyby jsou dvou typů: Osobní pohyb - + vědomá volba jedné z akcí stanovených pravidly hry + provedení této volby Náhodný tah - Náhodný tah je výběr z řady možností, který se neprovádí rozhodnutím hráče, ale nějakým mechanismem náhodného výběru. Níže uvažujeme párové hry s nulovým součtem obsahující pouze osobní tahy. Každá strana postrádá informace o chování té druhé. 3 1.3. Strategie Strategie hráče je soubor pravidel, která určují volbu akcí pro každý osobní tah tohoto hráče v závislosti na situaci, která během hry nastane. Podle počtu možných strategií se hry dělí na konečné a nekonečné. Nekonečná hra je hra, ve které má alespoň jeden z hráčů nekonečné číslo strategie. Konečná hra je hra, ve které má každý hráč pouze konečný počet strategií. Počet po sobě jdoucích tahů u kteréhokoli hráče určuje rozdělení her na jednotahové a vícetahové, případně poziční. + Ve hře na jeden tah si každý hráč vybere z možných možností pouze jednu volbu a poté určí výsledek hry. + Vícetahová neboli poziční hra se postupem času vyvíjí a představuje sérii po sobě jdoucích fázích, z nichž každý nastává po tahu jednoho z hráčů a odpovídající změně situace. Ve hře na jeden tah má každý hráč pouze jednu volbu možné možnosti a poté určí výsledek hry. Optimální strategie hráče je strategie, která při mnohonásobném opakování hry tomuto hráči zajistí maximální možnou průměrnou výhru (nebo, co je stejné, minimální možnou průměrnou prohru). V teorii her jsou všechna doporučení formulována na základě předpokladu rozumného chování hráčů. Špatné výpočty a chyby hráčů, nevyhnutelné v každé konfliktní situaci, stejně jako prvky vzrušení a rizika nejsou v teorii her zohledněny. 4 1.4. Maticová hra Maticová hra je jednotahová hra s konečným nulovým součtem a maticová hra je teoretická herní model konfliktní situace, kdy protivníci, aby dosáhli diametrálně odlišných cílů, udělají jednu volbu (tah) z konečného počtu možné způsoby akce.V souladu se zvolenými metodami akce (strategiemi) je stanoven dosažený výsledek. Podívejme se na příklad. Nechť jsou dva hráči A a B, z nichž jeden si může vybrat i-tá strategie z m svých možných strategií A1, A2, ...Am, a druhý zvolí j-tou strategii ze svých možných strategií B1, B2, ...Bm. Výsledkem je, že první hráč vyhrává hodnotu aij a druhý hráč tuto hodnotu ztrácí. Z čísel aij vytvoříme matici a11 a11 · · · a1n a21 a22 · · · a2n A = (aij) = .. .. .. . . . . am1 am2 · · · amn Matice A = (aij), i = 1, m, j = 1, n se nazývá výplatní matice neboli matice hry m × n. V této matici jsou řádky vždy pro strategie vítězného (maximalizujícího) hráče A, tedy hráče, který usiluje o maximalizaci své výhry. Sloupce jsou přiděleny strategiím prohrávajícího hráče B, tedy hráče, který se snaží minimalizovat kritérium efektivity. Normalizace hry je proces redukce poziční hry na maticovou hru.Hra v normální formě je poziční hra redukovaná na maticovou hru.Připomeňme, že poziční vícetahová hra je herně-teoretický model hry konfliktní situace, ve které oponenti postupně udělají jednu volbu (tah) z konečného počtu možných způsobů jednání v každé fázi vývoje této situace. Řešením hry je nalezení optimálních strategií obou hráčů a stanovení ceny hry.Cena hry je očekávaný zisk (ztráta) hráčů. Řešení hry lze nalézt buď v čistých strategiích – kdy hráč musí dodržovat jednu jedinou strategii, nebo ve smíšených, kdy hráč musí používat dvě nebo více čistých strategií s určitou pravděpodobností. Ty druhé se v tomto případě nazývají aktivní. 5 Smíšená strategie jednoho hráče je vektor, jehož každá složka ukazuje frekvenci použití hráčem odpovídající čisté strategie. Maximin nebo nižší cena hry - číslo α = max min aij i j Maximin strategie (linie) - strategie, kterou hráč zvolil, aby maximalizoval svou minimální výhru. Je zřejmé, že při výběru nejopatrnější strategie maximin si hráč A poskytuje (bez ohledu na chování soupeře) zaručenou výplatu alespoň α. Maximin neboli horní cena hry - číslo β = min max aij j i Strategie Minimax (sloupec) - strategie, kterou hráč zvolil, aby minimalizoval svou maximální ztrátu. Je zřejmé, že při výběru nejopatrnější strategie minimaxu hráč B za žádných okolností nedovolí hráči A vyhrát více než β. Nižší cena hry vždy nepřesahuje horní cenu hry α = max min aij 6 min max aij = β i j j i Věta 1 (hlavní věta teorie maticových her). Každá konečná hra má alespoň jedno řešení, možná v oblasti smíšených strategií. 6 2. Hry se sedlovou špičkou. Řešení v čistých strategiích Hra se sedlovým bodem je hra, pro kterou platí α = max min aij = min max aij = β i j j i U her se sedlovým bodem spočívá hledání řešení ve výběru strategií maximin a minimax, které jsou optimální., Čistá cena hry - obecný význam spodní a horní ceny hry α=β=ν 2.1. Příklady Příklad 1 Najděte řešení v čistých strategiích hry dané maticí 8 4 7 A= 6 5 9 7 7 8 Řešení: určete horní a dolní cenu hry. K tomu najdeme minimum čísel aij in i-tý řádek αi = min aij j a maximum čísel aij v j-tém sloupci βj = max aij i Čísla αi (řádková minima) zapíšeme vedle matice plateb vpravo ve formě doplňkového sloupce. Čísla βi (maxima sloupců) zapíšeme pod matici ve tvaru doplňkového řádku: αi 8 4 7 4 6 5 9 5 7 7 8 7 βj 8 7 9 7 Najděte maximum čísel αi α = max αi = 7 i a minimum z čísel βj β = min βj = 7 j α = β - hra má sedlový bod. Optimální strategie pro hráče je strategie A3 a pro hráče B je strategie B2, čistá cena hry ν = 7 Příklad 2 Platební matice je dána: 2 2 1 1 2 0 1 1 1 1 A= 1 1 1 1 2 1 2 1 1 2 Najděte řešení hry v čistých strategiích. Řešení: 2 2 1 1 2 1 0 1 1 1 1 0 1 1 1 1 2 1 1 2 1 1 2 1 βj 2 2 1 1 2 α = β = 1. Hra má šest sedlových bodů. Optimální strategie budou: A1 a B3 nebo B4 A3 a B3 nebo B4 A4 a B3 nebo B4 8 3. Řešení hry ve smíšených strategiích Když α = β. V případě, kdy při volbě svých strategií oba hráči nemají informace o volbě toho druhého, má hra řešení ve smíšených strategiích. SA = (p1, p2, ..., pm) - smíšená strategie hráče A, ve které se uplatňují strategie A1, A2, ..., Am s pravděpodobnostmi ∑ m p1, p2, ..., pm, pi = 1, pi > 0, i = 1, m i=1 SB = (q1, q2, ..., qn) - smíšená strategie hráče B, ve které se uplatňují strategie B1, B2, ..., Bm s pravděpodobnostmi ∑ n q1, q2 , ..., qm , qi = 1, qi > 0, i = 1, n i=1 Jestliže: SA∗ je optimální strategie hráče A, SB∗ je optimální strategie hráče B, pak cena hry je ∑ n ∑ m ν = aij · p∗i · qi∗ j=1 i=1 Následující věta odpovídá na otázku, jak najít řešení pro hry 2 × 2, 2 × n, m × 2 Věta 2 (jak najít řešení pro hry 2 × 2, 2 × n, m × 2). Pokud jeden z hráčů používá optimální smíšenou strategii, pak se jeho výplata rovná ceně hry ν, bez ohledu na pravděpodobnost, s jakou druhý hráč použije strategie zahrnuté v optimální (včetně čistých strategií). 9 3.1. Hra 2 × 2 Uvažujme hru 2 × 2 s maticí: () a11 a21 a21 a22 Nechť hra nemá řešení v čistých strategiích. Pojďme najít optimální strategie SA∗ a SB∗. Nejprve definujeme strategii SA∗ = (p∗1 , p∗2). Podle teorému, pokud se strana A drží strategie ν, pak bez ohledu na postup strany B zůstane výplata rovna nákladům na hraní ν. Pokud tedy strana A dodržuje optimální strategii SA∗ = (p∗1 , p∗2), může strana B použít kteroukoli ze svých strategií, aniž by změnila svůj zisk. Když pak hráč B použije čistou strategii B1 nebo B2, hráč obdrží průměrnou výplatu rovnající se ceně hry: a11 p∗1 + a21 p∗2 = ν ← pro strategii B1 a12 p∗1 + a22 p∗ 2 = ν ← pro strategii B2 Vezmeme-li v úvahu, že p∗1 + p∗2 = 1: p∗1 = a2 2−a2 1 a11 +a22 −a12 −a21 p∗2 = a1 1−a1 2 a11 +a22 −a12 −a21 Cena hry: a22 a11 − a12 a21 ν= a11 + a22 − a12 − a21 Optimální strategii hráče B najdeme podobně: SB∗ = (q1∗ , q2∗). Vezmeme-li v úvahu, že q1∗ + q2∗ = 1: q1∗ = a2 2−a1 2 a11 +a22 −a12 −a21 q2∗ = a1 1−a2 1 a11 +a22 −a12 −a21 3.1.1. Příklady Příklad 3 Najděte řešení hry s maticí () −1 1 A= 1 −1 10 Řešení: hra nemá sedlový bod, protože α= -1, β = 1, α ̸= β. Hledáme řešení ve smíšených strategiích. Pomocí vzorců pro p∗ a q∗ získáme p∗1 = p∗2 = 0,5 a q1∗ = q2∗ = 0,5, ν = 0 Tedy SA∗ = (0,5, 0,5) SB∗ = (0,5, 0,5 ) Příklad 4 Najděte řešení hry s maticí () 2 5 A= 6 4 Řešení: hra nemá sedlový bod, protože α= 4, β = 5, α ̸= β. Hledáme řešení ve smíšených strategiích. Pomocí vzorců pro p∗ a q∗ získáme p∗1 = 0,4, p∗2 = 0,6 a q1∗ = 0,2 q2∗ = 0,8, ν = 4,4 Tedy SA∗ = (0,4, 0,6) SB∗ = ( 0,2, 0,8) 11 3.1.2. Geometrická interpretace Hra 2 × 2 může být podána jednoduchou geometrickou interpretací. Vezměme jeden řez osou úsečky, jehož každý bod spojíme s nějakou smíšenou strategií S = (p1, p2) = (p1, 1 − p1) a pravděpodobnost p1 strategie A1 bude rovna vzdálenosti od bod SA k pravému konci úseku a pravděpodobnost p2 , strategie A2 - vzdálenost k levému konci. .y .I .I I .B1′ .N .B1 .a21 .a11 .I I .I .∗ .x .P2 .SA∗ .P1∗ Zejména levý konec řezu (bod s úsečkou = 0) odpovídá ke strategii A1, pravý konec segmentu (x = 1) - strategie A2 Na koncích segmentu jsou obnoveny dvě kolmice k ose x: osa I − I - výplata pro strategii A1 je odložena, osa II − II - výplata za strategii A2 je odložena Nechte hráče B uplatnit strategii B1; dává na osách I − I a II − II body s pořadnicemi a11 a a21. Těmito body vedeme přímku B1 − B1′. Pro jakoukoli smíšenou strategii SA = (p1, p2) je výplata hráče určena bodem N na přímce B1 − B1′, odpovídající bodu SA na ose x rozdělující segment v poměru p2:p1. Je zřejmé, že přímka B2 − B2′, která určuje výplatu pro strategii B2, může být konstruována přesně stejným způsobem. 12 .y .I .I I .B2 .N .a21 .B2′ a . 22 .I I .I .∗ .x .P2 .SA∗ .P1∗ Je nutné najít optimální strategii SA∗, tzn. taková, že minimální výplata hráče A (za předpokladu nejhoršího chování hráče B pro něj) by se změnila na maximum. K tomu sestrojte spodní hranici pro výplatu hráče A pro strategie B1, B2, tzn. přerušovaná čára B1 N B2′ ;. Na této hranici bude ležet minimální výplata hráče A za jakoukoli jeho smíšenou strategii, bod N, ve kterém tato výplata dosahuje maxima a určuje rozhodnutí a cenu hry. .y .I .I I .B2 .B1′ .N .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S . 1∗ P Pořadnice bodu N není nic jiného než cena hry ν, její úsečka je rovna ∗2 a vzdálenost k pravému konci úsečky je rovna ∗1, tj. vzdálenost od bodu SA∗ ke koncům segmentu se rovná pravděpodobnostem ∗2 a ∗1 strategií A2 a A1 optimální smíšené strategie hráče A. v tomto případě bylo řešení hry určeno průsečík strategií B1 a B2. Níže je uveden případ, kdy je optimální strategií hráče čistá strategie A2. Zde je strategie A2 (pro jakoukoli nepřátelskou strategii) ziskovější než strategie A1, 13 .y .y .I .I I .I I. I .B2′ . 1'B .B1'B . 2.B2'B . 2 .B1 .ν = a21 .B1 .ν = a21 I. I I. I .I . .x .I . .X. 2∗ P . A∗S = A2. 2∗ P . A∗ S = A2 Vpravo je znázorněn případ, kdy má hráč B zjevně nerentabilní strategii. Geometrický výklad také umožňuje vizualizovat nižší cenu hry α a horní cenu β .y .I .I I .B2 .B1′ .N .B1 B2′ .β = a21 .α = a22 .I I .I .∗ .x .P2 . A∗ S . 1∗ P Na stejném grafu můžeme také podat geometrickou interpretaci optimálních strategií hráče B. Lze snadno ověřit, že podíl q1∗ strategie B1 optimální smíšené strategie SB∗ = (q1∗ , q2∗) je roven poměru délky segmentu KB2 k součtu délek segmentů KB1 a KB2 na ose I − I: .y .I .I I .B2 .B1′ .N .K .L .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S . 1∗ P 14 KB2 q1∗ = KB2 + KB1 nebo LB2′ q1∗ = LB2′ + LB1′ Optimální strategii SB∗ = (q1∗ , q2∗) lze najít jiným způsobem, pokud prohodíme hráče B a B, a místo maxima spodní hranice výher zvažte minimum horní hranice. .y .I .I I .A2 .A′1 .N .A1 .A′2 .I I .I . .x .q2∗ . B∗ S .q1∗ 15 3.2. Hry 2 × n a m × 2 Řešení her 2 × n a m × 2 je založeno na následující větě. Věta 3. Každá konečná hra m × n má řešení, ve kterém počet aktivních strategií každé strany nepřekročí nejmenší z čísel m a n. Podle této věty má hra 2 × n vždy řešení, ve kterém má každý hráč maximálně dvě aktivní strategie. Jakmile najdete tyto strategie, hra 2 × n se promění ve hru 2 × 2, kterou lze vyřešit elementárním způsobem. Hledání aktivních strategií lze provést graficky: 1) sestrojí se grafická interpretace; 2) je stanovena spodní hranice výher; 3) na spodní hranici výplaty jsou identifikovány dvě strategie druhého hráče, které odpovídají dvěma čarám protínajícím se v bodě s maximální pořadnicí (pokud se v tomto bodě protíná více než dvě čáry, bere se libovolný pár) - tyto strategie představují aktivní strategie hráče B. Hra 2 × n se tak redukuje na hru 2 × 2. Lze řešit i hru m × 2 s tím rozdílem, že ne spodní, ale horní mez výplaty je konstruováno, a ne maximum, ale hledá se na něm minimum. Příklad 5 Najděte řešení hry () 7 9 8 A= 10 6 9 Řešení: geometrickou metodou vybíráme aktivní strategie. Přímé linie B1 − B1′, B2 − B2′ a B3 − B3′ odpovídají strategiím B1, B2, B3. Přerušovaná čára B1 N B2 je spodní hranice výher hráče. Hra má řešení S∗A = (23, 31); S*B = (0,5; 0,5; 0); v = 8. 16 .y .I .I I . 1'B B. 2 .B3′ .N .B3 .B1 .B2′ .I I .I . .X. 2∗ P . A∗ S . 1∗ P 17 Indexová hra, 2 tahy, 3 2 × 2, 10 osobních, 3 2 × 2, 9 náhodných, 3 geometrie, 12 čistá cena hry, 7 příkladů, 10 2 × n, 9, 16 m × 2, 9 , 16 nekonečných, 4 v normální formě, 5 konečných, 4 vícetahové, 4 jednotahové, 4 maticové, 5 párových, 2 s nulovým součtem, 2 antagonistické, 2 neantagonistické, 2 řešení, 5 ve smíšených strategiích, 5 , 9 čistých strategií , 5 se sedlovým bodem, 7 cena, 5 horní, 6 nižší, 6 čistých, 7 maximinů, 6 herní matice, 5 výplata, 5 minimax, 6 normalizace hry, 5 strategie, 4 maximiny, 6 minimax, 6 optimální, 4 smíšené, 5 teorie her, 2 18
Z populárního amerického blogu Cracked.
Teorie her je o studiu způsobů, jak udělat ten nejlepší tah a v důsledku toho získat co největší část výherního koláče tím, že část z něj ukrojíte ostatním hráčům. Naučí vás analyzovat mnoho faktorů a vyvodit logicky vyvážené závěry. Myslím, že by se to mělo studovat po číslech a před abecedou. Jednoduše proto, že příliš mnoho lidí dělá důležitá rozhodnutí na základě intuice, tajných proroctví, umístění hvězd a podobně. Teorii her jsem důkladně prostudoval a nyní vám chci povědět o jejích základech. Možná vám to do života přidá zdravý rozum.
1. Dilema vězně
Berto a Robert byli zatčeni za bankovní loupež poté, co řádně nepoužili k útěku ukradené auto. Policie nemůže prokázat, že to byli oni, kdo vyloupili banku, ale přistihli je při činu v kradeném autě. Byli odvedeni do různých místností a každému byla nabídnuta dohoda: předat komplice a poslat ho na 10 let do vězení a sám být propuštěn. Ale pokud se oba zradí, pak každý dostane 7 let. Pokud nikdo nic neřekne, tak oba půjdou na 2 roky do vězení jen za krádež auta.
Ukáže se, že pokud Berto mlčí, ale Robert ho udá, Berto jde na 10 let do vězení a Robert jde na svobodu. Každý vězeň je hráč a prospěch každého lze vyjádřit jako „vzorec“ (co dostanou oba, co dostane ten druhý). Například, když tě trefím, můj vítězný vzor bude vypadat takto (dostanu hrubé vítězství, ty trpíš silná bolest). Protože každý vězeň má dvě možnosti, můžeme výsledky prezentovat v tabulce.
Praktická aplikace: Identifikace sociopatů
Zde vidíme hlavní aplikaci teorie her: identifikace sociopatů, kteří myslí jen na sebe. Skutečná teorie her je mocným analytickým nástrojem a amatérismus často slouží jako červená vlajka, která označí někoho, kdo nemá smysl pro čest. Lidé, kteří provádějí intuitivní výpočty, věří, že je lepší udělat něco ošklivého, protože to bude mít za následek kratší trest vězení bez ohledu na to, co druhý hráč udělá. Technicky je to správné, ale pouze v případě, že jste krátkozraký člověk, který dává čísla vyšší lidské životy. To je důvod, proč je teorie her ve financích tak populární.
Skutečným problémem vězňova dilematu je, že ignoruje data. Například nezohledňuje možnost, že se setkáte s přáteli, příbuznými nebo dokonce věřiteli osoby, kterou jste poslali na 10 let do vězení.
Nejhorší na tom je, že všichni zúčastnění vězňova dilematu se chovají, jako by o tom nikdy neslyšeli.
A nejlepší krok je mlčet a po dvou letech spolu s dobrým kamarádem použít stejné peníze.
2. Dominantní strategie
Toto je situace, ve které vaše činy dávají největší výhra bez ohledu na jednání soupeře. Bez ohledu na to, co se stalo, udělali jste všechno správně. To je důvod, proč mnoho lidí s vězeňským dilematem věří, že zrada vede k „nejlepšímu“ výsledku bez ohledu na to, co druhá osoba dělá, a neznalost reality vlastní této metodě to vypadá velmi snadno.
Většina her, které hrajeme, nemá striktně dominantní strategie, protože jinak by byly hrozné. Představte si, že byste vždy dělali to samé. Ve hře kámen-papír-nůžky neexistuje žádná dominantní strategie. Ale pokud byste si hráli s člověkem, který měl na rukou rukavice a uměl ukázat jen kámen nebo papír, měli byste dominantní strategii: papír. Váš papír obalí jeho kámen nebo vyústí v remízu a nemůžete prohrát, protože váš soupeř neumí ukázat nůžky. Nyní, když máte dominantní strategii, byl byste blázen, když byste zkusil něco jiného.
3. Bitva pohlaví
Hry jsou zajímavější, když nemají striktně dominantní strategii. Například bitva pohlaví. Anjali a Borislav jdou na rande, ale nemohou si vybrat mezi baletem a boxem. Anjali miluje box, protože ji baví vidět proudit krev k radosti ječícího davu diváků, kteří si myslí, že jsou civilizovaní jen proto, že zaplatili za to, že někomu rozbili hlavu.
Borislav se chce dívat na balet, protože chápe, čím si baletky procházejí velké množství zranění a nejtěžší trénink s vědomím, že jedním zraněním lze vše ukončit. Baletní tanečníci - největší sportovci na zemi. Balerína vás může kopnout do hlavy, ale nikdy to neudělá, protože její noha má mnohem větší cenu než váš obličej.
Každý z nich chce jít na svou oblíbenou akci, ale nechce si to užít sám, a tak vyhrávají: nejvyšší hodnotu- dělají, co se jim líbí, nejmenší hodnotu- jen být s jinou osobou a nula - být sám.
Někteří lidé naznačují tvrdohlavost: pokud děláte, co chcete, bez ohledu na to, co chcete, druhá osoba se musí podřídit vaší volbě, jinak o všechno přijde. Jak jsem již řekl, Zjednodušená teorie her je skvělá při identifikaci bláznů.
Praktické použití: Vyhněte se ostrým rohům
Tato strategie má samozřejmě i své významné nevýhody. Za prvé, pokud budete své seznamování brát jako „bitvu pohlaví“, nebude to fungovat. Rozejděte se, aby si každý z vás našel někoho, koho má rád. A druhým problémem je, že v této situaci si účastníci nejsou tak jisti sami sebou, že to nemohou udělat.
Skutečně vítěznou strategií pro každého je dělat to, co chce. a poté, nebo další den, až budou mít volno, jděte spolu do kavárny. Nebo střídejte box a balet, dokud nenastane revoluce ve světě zábavy a nebude vynalezen boxerský balet.
4. Nashova rovnováha
Nashova rovnováha je soubor pohybů, kde nikdo nechce dělat nic jinak. A pokud se nám to podaří, teorie her nahradí celý filozofický, náboženský a finanční systém na planetě, protože „vůle nezkrachovat“ se pro lidstvo stala silnější. hnací silou než oheň.
Rychle si rozdělme 100 dolarů. Vy a já rozhodneme, kolik ze stovek požadujeme, a zároveň oznámíme částky. Pokud naše Celková částka méně než sto, každý dostane, co chtěl. Li celkový více než sto, ten, kdo požádal o nejmenší částku, dostane požadovanou částku a chamtivější dostane to, co zbyde. Pokud požádáme o stejnou částku, každý dostane 50 dolarů. Kolik budete chtít? Jak si rozdělíte peníze? Existuje pouze jeden vítězný tah.
Nárokováním 51 USD získáte maximální částka bez ohledu na to, co si váš soupeř vybere. Pokud požádá o více, dostanete 51 dolarů. Pokud požádá o 50 nebo 51 dolarů, dostanete 50 dolarů. A pokud požádá o méně než 50 dolarů, dostanete 51 dolarů. Ať tak či onak, neexistuje žádná jiná možnost, která vám vydělá více peněz než tato. Nashova rovnováha – situace, kdy si oba vybereme 51 dolarů.
Praktická aplikace: Nejprve myslete
To je celý smysl teorie her. Nemusíte vyhrávat, tím méně ubližovat ostatním hráčům, ale musíte udělat ten nejlepší krok pro sebe, bez ohledu na to, co pro vás mají lidé kolem vás připraveni. A ještě lepší je, když je tento krok výhodný pro ostatní hráče. Toto je druh matematiky, který by mohl změnit společnost.
Zajímavou variací této myšlenky je pití, které lze nazvat časově závislou Nashovou rovnováhou. Když dostatečně pijete, nestaráte se o činy druhých, ať dělají, co dělají, ale druhý den opravdu litujete, že jste něco neudělali jinak.
5. Přehazovačka
Los se hraje mezi hráčem 1 a hráčem 2. Každý hráč současně volí hlavy nebo ocasy. Pokud uhodnou správně, hráč 1 dostane penny hráče 2. Pokud ne, hráč 2 dostane minci hráče 1.
Vítězná matice je jednoduchá...
...optimální strategie: hrajte zcela náhodně. Je to těžší, než si myslíte, protože výběr musí být zcela náhodný. Pokud dáváte přednost hlavám nebo ocasům, váš soupeř je může použít k tomu, aby vám vzal peníze.
Samozřejmě, skutečný problém je v tom, že by bylo mnohem lepší, kdyby po sobě házeli jeden cent. Ve výsledku by jejich zisky byly stejné a výsledné trauma by těmto nešťastníkům mohlo pomoci cítit něco jiného než strašnou nudu. Koneckonců tohle nejhorší hra vůbec existující. A to je ideální model pro penaltový rozstřel.
Praktické použití: Penalta
Ve fotbale, hokeji a mnoha dalších hrách je prodloužení penaltovým rozstřelem. A byly by zajímavější, kdyby vycházely z toho, kolikrát hráči plná forma by byli schopni udělat kolo, protože by to bylo přinejmenším známkou jejich fyzických schopností a bylo by zábavné to sledovat. Brankáři nemohou jednoznačně určit pohyb míče nebo puku na samém začátku jeho pohybu, protože roboti se bohužel stále našich sportovních soutěží neúčastní. Brankář musí zvolit levý nebo pravý směr a doufat, že jeho volba odpovídá volbě soupeře, který střílí na branku. To má něco společného s hraním mincí.
Všimněte si však, že to není dokonalý příklad podobnosti s hrou hlavy a ocasu, protože i kdyby udělat správnou volbu ve směru, brankář nesmí chytit míč a útočník nesmí zasáhnout branku.
Jaký je tedy náš závěr podle teorie her? Míčové hry by měly končit způsobem „multi-ball“, kdy hráči jeden na jednoho dostanou každou minutu míč/puk navíc, dokud jedna strana nedosáhne určitého výsledku, který je známkou skutečné dovednosti hráčů, a není to velkolepá náhodná náhoda.
Na konci dne by měla být použita teorie her, aby byla hra chytřejší. Což znamená, že je to lepší.
Herní teorie jako obor operačního výzkumu je to teorie matematických modelů pro přijímání optimálních rozhodnutí v podmínkách nejistoty nebo konfliktu několika stran s různými zájmy. Teorie her studuje optimální strategie v herních situacích. Patří sem situace související s volbou nejvýnosnějších výrobních řešení pro systém vědeckých a ekonomických experimentů, organizace statistická kontrola, ekonomické vztahy mezi průmyslovými podniky a ostatními odvětvími. Formalizace konfliktní situace matematicky mohou být reprezentovány jako hra dvou, tří atd. hráči, z nichž každý sleduje cíl maximalizovat svůj prospěch, své výhry na úkor toho druhého.Část "Teorie her" je zastoupena třemi online kalkulačky:
- Optimální strategie hráčů. V takových problémech je specifikována platební matice. Je nutné najít čisté nebo smíšené strategie hráčů a, cena hry. Chcete-li vyřešit, musíte zadat rozměr matice a metodu řešení. Služba implementuje následující metodyřešení hry pro dva hráče:
- Minimax. Pokud potřebujete najít čistou strategii hráčů nebo odpovědět na otázku ohledně sedla hry, zvolte tento způsob řešení.
- Simplexní metoda. Používá se k řešení smíšených strategických her pomocí metod lineárního programování.
- Grafická metoda. Používá se k řešení smíšených strategických her. Pokud existuje sedlový bod, řešení se zastaví. Příklad: Pro danou platební matici najděte optimální smíšené strategie hráčů a cenu hry, kterou používáte grafická metoda herní řešení.
- Brown-Robinsonova iterační metoda. Iterační metoda se používá, když grafická metoda není použitelná a když algebraická a maticové metody. Tato metoda poskytuje přibližnou hodnotu ceny hry a skutečnou hodnotu lze získat s jakýmkoli požadovaným stupněm přesnosti. Tato metoda nestačí k nalezení optimálních strategií, ale umožňuje sledovat dynamiku tahové hry a určit cenu hry pro každého hráče v každém kroku.
Všechny metody používají kontrolu dominantních řádků a sloupců. - Hra Bimatrix. Obvykle jsou v takové hře zadány dvě matice stejné velikosti výplat prvního a druhého hráče. Řádky těchto matic odpovídají strategiím prvního hráče a sloupce matic odpovídají strategiím druhého hráče. V tomto případě první matice představuje výhru prvního hráče a druhá matice představuje výhru druhého hráče.
- Hry s přírodou. Používá se, když potřebujete vybrat manažerské rozhodnutí podle kritérií Maximax, Bayes, Laplace, Wald, Savage, Hurwitz.
U Bayesova kritéria bude také nutné zadat pravděpodobnost výskytu událostí. Pokud nejsou zadány, ponechte výchozí hodnoty (budou existovat ekvivalentní události).
U Hurwitzova kritéria uveďte úroveň optimismu λ. Pokud tento parametr není uveden v podmínkách, můžete použít hodnoty 0, 0,5 a 1.
Mnoho problémů vyžaduje hledání řešení pomocí počítačů. Výše uvedené služby a funkce jsou jedním z nástrojů.
