Teorie her: Matrixové hry. Příklad řešení problému teorie her ve smíšených strategiích naší službou

27.09.2019 | Konstrukce

Nazývá se hra pro dvě osoby s nulovým součtem, ve které má každý z nich omezenou sadu strategií. Pravidla maticové hry určuje matice výplat, jejíž prvky jsou výplaty prvního hráče, které jsou zároveň prohrami druhého hráče.

Maticová hra je antagonistická hra. První hráč obdrží maximální garantovanou (nezávislou na chování druhého hráče) výplatu rovnající se ceně hry, podobně druhý hráč dosáhne minimální garantované ztráty.

Pod strategie je chápán jako soubor pravidel (principů), které určují volbu varianty akcí pro každý osobní tah hráče v závislosti na aktuální situaci.

Nyní o všem v pořádku a podrobně.

Výplatní matice, čisté strategie, cena hry

V maticová hra jsou určena jeho pravidla výplatní matice .

Představte si hru, ve které jsou dva účastníci: první hráč a druhý hráč. Ať má první hráč mčisté strategie, které má k dispozici druhý hráč - nčisté strategie. Vzhledem k tomu, že se uvažuje o hře, je přirozené, že v této hře dochází k výhrám a prohrám.

V platební matice prvky jsou čísla vyjadřující zisky a ztráty hráčů. Výhry a prohry mohou být vyjádřeny v bodech, penězích nebo jiných jednotkách.

Vytvořme výplatní matici:

Pokud se první hráč rozhodne ičistá strategie a druhý hráč j-th čistá strategie, pak je odměna prvního hráče Aij jednotek a ztráta druhého hráče je také Aij Jednotky.

Protože Aij + (- A ij) = 0, pak je popsaná hra maticová hra s nulovým součtem.

Nejjednodušším příkladem maticové hry je házení mincí. Pravidla hry jsou následující. První a druhý hráč si hodí mincí a výsledkem jsou hlavy nebo ocasy. Pokud jsou házeny hlavy a hlavy nebo ocasy nebo ocasy současně, pak první hráč vyhraje jednu jednotku, v ostatních případech jednu jednotku ztratí (druhý hráč vyhraje jednu jednotku). Druhý hráč má k dispozici dvě stejné strategie. Odpovídající výplatní matice by byla:

Úkolem teorie her je určit volbu strategie prvního hráče, která by mu zaručila maximální průměrný zisk, a také volbu strategie druhého hráče, která by mu zaručila maximální průměrnou ztrátu.

Jak se volí strategie v maticové hře?

Podívejme se znovu na výplatní matici:

Nejprve určíme výplatu prvního hráče, pokud použije ičistá strategie. Pokud první hráč použije i-th čisté strategie, pak je logické předpokládat, že druhý hráč použije takovou čistou strategii, díky které by byla výplata prvního hráče minimální. První hráč zase použije tak čistou strategii, která by mu zajistila maximální výplatu. Na základě těchto podmínek výplata prvního hráče, kterou označujeme jako proti1 , je nazýván maximální výhra nebo nižší cena hry .

Na pro tyto hodnoty by měl první hráč postupovat následovně. Z každého řádku vypište hodnotu minimálního prvku a vyberte z nich maximum. Výplata prvního hráče tedy bude maximum z minima. Odtud název - maximin win. Číslo řádku tohoto prvku bude číslo čisté strategie zvolené prvním hráčem.

Nyní určíme ztrátu druhého hráče, pokud použije j-tá strategie. V tomto případě první hráč používá svou vlastní čistou strategii, ve které by ztráta druhého hráče byla maximální. Druhý hráč musí zvolit tak čistou strategii, ve které by jeho ztráta byla minimální. Ztráta druhého hráče, kterou označujeme jako proti2 , je nazýván minimální maximální ztráta nebo nejvyšší cena hry .

Na řešení problémů s cenou hry a stanovení strategie pro určení těchto hodnot pro druhého hráče postupujte následovně. Z každého sloupce vypište hodnotu maximálního prvku a vyberte z nich minimum. Ztráta druhého hráče tedy bude minimem z maxima. Odtud název – minimax gain. Číslo sloupce tohoto prvku bude číslo čisté strategie zvolené druhým hráčem. Pokud druhý hráč použije „minimax“, pak bez ohledu na volbu strategie prvním hráčem maximálně prohraje proti2 Jednotky.

Příklad 1

Největší z nejmenších prvků řad je 2, to je nižší cena hry, tomu odpovídá první řada, proto je strategie maximin prvního hráče první. Nejmenší z největších prvků sloupců je 5, to je horní cena hry, tomu odpovídá druhý sloupec, proto je minimax strategie druhého hráče druhá.

Nyní, když jsme se naučili, jak najít spodní a horní cenu hry, strategie maximin a minimax, je čas naučit se tyto pojmy formálně označovat.

Takže zaručená výplata prvního hráče je:

První hráč musí zvolit čistou strategii, která by mu zajistila maximum z minimálních výplat. Tento zisk (maximin) je označen následovně:

První hráč používá svou čistou strategii tak, aby ztráta druhého hráče byla maximální. Tato ztráta je definována takto:

Druhý hráč musí zvolit svou čistou strategii tak, aby jeho ztráta byla minimální. Tato ztráta (minimax) je označena následovně:

Další příklad ze stejné série.

Příklad 2 Daná maticová hra s výplatní maticí

Určete strategii maximin pro prvního hráče, strategii minimax pro druhého hráče, spodní a horní cenu hry.

Řešení. Napravo od výplatní matice vypíšeme nejmenší prvky v jejích řádcích a označíme maximum z nich a zespodu matice - největší prvky ve sloupcích a vybereme minimum z nich:

Největší z nejmenších prvků řad je 3, to je nižší cena hry, tomu odpovídá druhý řádek, proto je strategie maximin prvního hráče druhého. Nejmenší z největších prvků sloupců je 5, to je horní cena hry, tomu odpovídá první sloupec, proto je strategie minimax druhého hráče první.

Sedlový bod v maticových hrách

Pokud je horní a dolní cena hry stejná, pak se má za to, že maticová hra má sedlový bod. Platí to i naopak: pokud má maticová hra sedlový bod, pak jsou horní a dolní ceny maticové hry stejné. Odpovídající prvek je nejmenší v řadě i největší ve sloupci a rovná se ceně hry.

Pokud tedy , pak je optimální čistá strategie prvního hráče a je optimální čistá strategie druhého hráče. To znamená, že stejné nižší a vyšší ceny hry jsou dosaženy na stejném páru strategií.

V tomto případě maticová hra má řešení v čistých strategiích .

Příklad 3 Daná maticová hra s výplatní maticí

Řešení. Napravo od výplatní matice vypíšeme nejmenší prvky v jejích řádcích a označíme maximum z nich a zespodu matice - největší prvky ve sloupcích a vybereme minimum z nich:

Nižší cena hry je stejná jako horní cena hry. Cena hry je tedy 5. To je . Cena hry se rovná hodnotě sedlového bodu. Maximinová strategie prvního hráče je druhou čistou strategií a minimax strategie druhého hráče je třetí čistou strategií. Tato maticová hra má řešení v čistých strategiích.

Vyřešte problém maticové hry sami a pak se podívejte na řešení

Příklad 4 Daná maticová hra s výplatní maticí

Najděte spodní a horní cenu hry. Má tato maticová hra sedlovou pointu?

Matrixové hry s optimální smíšenou strategií

Ve většině případů maticová hra nemá sedlový bod, takže odpovídající maticová hra nemá čistě strategická řešení.

Má ale řešení v optimálních smíšených strategiích. Pro jejich nalezení je třeba předpokládat, že se hra opakuje tolikrát, aby se na základě zkušeností dalo odhadnout, která strategie je výhodnější. Proto je rozhodnutí spojeno s pojmem pravděpodobnost a průměr (očekávání). V konečném řešení je jak analog sedlového bodu (tedy rovnost spodní a horní ceny hry), tak obdoba jim odpovídajících strategií.

Aby tedy první hráč získal maximální průměrný zisk a druhý hráč měl minimální průměrnou ztrátu, měly by se s určitou pravděpodobností používat čisté strategie.

Pokud první hráč používá čisté strategie s pravděpodobnostmi , pak vektor se nazývá smíšená strategie prvního hráče. Jinými slovy, je to „směs“ čistých strategií. Součet těchto pravděpodobností je roven jedné:

Pokud druhý hráč používá čisté strategie s pravděpodobnostmi , pak vektor se nazývá smíšená strategie druhého hráče. Součet těchto pravděpodobností je roven jedné:

Pokud první hráč používá smíšenou strategii p, a druhý hráč - smíšená strategie q, pak to dává smysl očekávaná hodnota první hráč vyhrává (druhý hráč prohrává). Chcete-li jej najít, musíte vynásobit vektor smíšené strategie prvního hráče (což bude jednořádková matice), matici výplaty a vektor smíšené strategie druhého hráče (což bude matice s jedním sloupcem):

Příklad 5 Daná maticová hra s výplatní maticí

Určete matematické očekávání zisku prvního hráče (prohry druhého hráče), pokud smíšená strategie prvního hráče je , a smíšená strategie druhého hráče je .

Řešení. Podle vzorce pro matematické očekávání zisku prvního hráče (ztráta druhého hráče) se rovná součinu vektoru smíšené strategie prvního hráče, výplatní matice a vektoru smíšené strategie druhého hráče:

První hráč se nazývá taková smíšená strategie, která by mu zajistila maximální průměrnou výplatu při dostatečném počtu opakování hry.

Optimální smíšená strategie Druhý hráč se nazývá taková smíšená strategie, která by mu zajistila minimální průměrnou ztrátu při dostatečném počtu opakování hry.

Analogicky k zápisu maximinu a minimaxu v případě čistých strategií jsou optimální smíšené strategie označovány následovně (a jsou spojeny s matematické očekávání, tedy průměr zisku prvního hráče a ztráty druhého hráče):

V tomto případě pro funkci E je tam sedlový bod , což znamená rovnost.

Aby se našly optimální smíšené strategie a sedlový bod, tzn. řešit maticovou hru ve smíšených strategiích , musíme zredukovat maticovou hru na problém lineární programování, tedy k optimalizačnímu problému, a vyřešit odpovídající problém lineárního programování.

Redukce maticové hry na problém lineárního programování

Abyste mohli vyřešit maticovou hru ve smíšených strategiích, musíte sestavit přímku problém lineárního programování A svůj dvojí úkol. V duálním problému je transponována rozšířená matice, která ukládá koeficienty proměnných v systému omezení, konstantní členy a koeficienty proměnných v cílové funkci. V tomto případě je minimum cílové funkce původního problému spojeno s maximem v duálním problému.

Cílová funkce v problému přímého lineárního programování:

Systém omezení v přímém problému lineárního programování:

Cílová funkce v duálním problému:

Systém omezení v duálním problému:

Označte optimální plán úlohy přímého lineárního programování

a optimální plán duálního problému je označen

Lineární formy pro odpovídající optimální návrhy budou označeny a ,

a musíte je najít jako součet odpovídajících souřadnic optimálních plánů.

V souladu s definicemi v předchozí části a souřadnicemi optimálních plánů jsou platné následující smíšené strategie prvního a druhého hráče:

Matematici to dokázali cena hry je vyjádřena pomocí lineárních forem optimálních plánů takto:

to znamená, že je to převrácená hodnota součtů souřadnic optimálních plánů.

My, praktici, můžeme tento vzorec použít pouze k řešení maticových her ve smíšených strategiích. Jako vzorce pro nalezení optimálních smíšených strategií respektive první a druhý hráč:

ve kterém jsou druhými faktory vektory. Optimální smíšené strategie jsou také vektory, jak jsme již definovali v předchozím odstavci. Vynásobením čísla (ceny hry) vektorem (se souřadnicemi optimálních plánů) tedy získáme také vektor.

Příklad 6 Daná maticová hra s výplatní maticí

Najděte cenu hry PROTI a optimální smíšené strategie a .

Řešení. Sestavíme problém lineárního programování odpovídající této maticové hře:

Získáme řešení přímého problému:

Lineární tvar optimálních plánů najdeme jako součet nalezených souřadnic.

Obsah 1 Obecná informace 2 1.1 Hry. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Tahy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Strategie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Matrixová hra. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Bod sledování. Č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í situace, tzn. takové 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á by měla naznačovat: možné možnosti jednání účastníků, kvantitativní výsledek hry nebo platbu (výhra, prohra), ke které daný soubor tahů vede k výši informace každé strany o chování té druhé. Párová hra – hra, které se účastní pouze dvě strany (dva hráči). Párová hra s nulovým součtem - párová hra, ve které je výše 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 jsou párové hry rozděleny: 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 Existují dva typy tahů: Osobní tah - + vědomá volba jedné z akcí stanovených pravidly hry + implementace 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 nemá žádné 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á se během hry vyvinula. 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ý počet strategií. 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 z hráčů určuje rozdělení her na jednotahové a vícetahové, případně poziční. + Ve hře na jeden tah udělá každý hráč pouze jednu volbu z možných možností a poté určí výsledek hry. + Vícetahová neboli poziční hra se vyvíjí v čase a představuje řadu po sobě jdoucích fází, z nichž každá přichází po tahu jednoho z hráčů a odpovídající změně situace. Ve hře na jeden tah udělá každý hráč pouze jednu volbu z možných možností a poté určí výsledek hry. Optimální strategie hráče je strategie, která při mnohonásobném opakování hry poskytuje danému hráči maximální možný průměrný zisk (nebo ekvivalentně minimální možnou průměrnou ztrátu). V teorii her jsou všechna doporučení učiněna na základě předpokladu rozumného chování hráčů. Chybné výpočty a chyby hráčů, nevyhnutelné v každé konfliktní situaci, stejně jako prvky vzrušení a rizika v teorii her nejsou brány v úvahu. 4 1.4. Maticová hra Maticová hra je jednotahová hra s konečným nulovým součtem. 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 možných strategií A1 , A2 , ...Am , a druhý volí j-tá strategie jejich možných strategií B1 , B2 , ...Bm . Výsledkem je, že první hráč vyhrává aij a druhý hráč tuto hodnotu ztrácí. Z čísel aij poskládá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ý se snaží maximalizovat svůj zisk. Sloupce jsou vyhrazeny pro strategie 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 zredukovaná na maticovou hru jednou volbou (tahem) z konečného počtu možných způsobů jednání v každé fázi vývoje tohoto situace. Řešení hry - nalezení optimálních strategií obou hráčů a stanovení hodnoty hry Hodnotou 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žít 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 (řetězec) - strategie zvolená hráčem pro maximalizaci jeho minimální výplaty. 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 zvolená hráčem pro minimalizaci jeho maximální ztráty. 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í. - 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 in j-tý sloupec βj = max aij i Čísla αi (minima řádků) zapíšeme vedle výplatní matice vpravo jako další sloupec. Čísla βi (maxima sloupců) zapíšeme pod matici jako další řádek: α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 - strategie B2, čisté náklady na hru ν = 7 Příklad 2 Výplatová matice je dána: 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 jsou: 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 Pro α ̸= β. 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) je smíšená strategie hráče A, ve které jsou strategie A1 , A2 , ..., Am aplikovány s pravděpodobnostmi ∑ m p1 , p2 , ..., pm , pi = 1, pi > 0, i = 1, m i=1 SB = (q1 , q2 , ..., qn) je smíšená strategie hráče B, ve které jsou s pravděpodobnostmi aplikovány strategie B1 , B2 , ..., Bm ∑ n q1, q2, ..., qm, qi = 1, qi > 0, i = 1, n i=1 = aij p∗i qi∗ j=1 i=1 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 strana A dodrží strategii ν, pak bez ohledu na postup strany B zůstane výplata rovna ceně hry ν. 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 výplatu. 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 všimněte si, ž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 Hodnota hry: a22 a11 − a12 a21 a22= a11 + − a12 − a21 Obdobně je nalezena optimální strategie hráče B: 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. Podle vzorců pro p∗ a q 0,8) 11 3.1.2. Geometrická interpretace Hra 2×2 může být podána jednoduchou geometrickou interpretací. Vezměme jednotkový řez osy úsečky, ke každému bodu přiřadíme nějakou smíšenou strategii S = (p1 , p2) = (p1 , 1 − p1) 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∗ pravý konec úseku (x = 1) - strategie A2 Na koncích úseku jsou obnoveny dvě kolmice na osu úsečky: osa I - I - výplata se odkládá se strategií A1 osa II - II - výplata se odkládá strategií A2 Nechte hráče B aplikovat strategii B1 ; dává na osách I − I a II − II body s pořadnicemi a11 a a21 . Těmito body vedeme úsečku B1 − B1′. Pro libovolnou smíšenou strategii SA = (p1 , p2) je odměna hráče určena bodem N na přímce B1 − B1′ , odpovídajícím bodu SA na ose x rozdělující segment vzhledem k p2: p1 . Je zřejmé, že přímka B2 − B2′ , která určuje výplatu pro strategii B2 , může být sestrojena úplně 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 (s nejhorším chováním hráče B pro něj) by se proměnila v maximální. K tomu je pro strategie B1 , B2 konstruována spodní hranice výplaty hráče A, 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 dosáhne maxima a určuje řešení 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ž hodnota hry ν, její úsečka je rovna ∗2 a vzdálenost k pravému konci úsečky je rovna ∗1, tzn. 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 strategii soupeře) ziskovější než strategie A1 , 13 .y .y .I .I I .I I. I .B2′ . 1'B .B1'B . 2.B2'B . 2 .B1 .v = a21 .B1 .v = 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 záměrně nerentabilní strategii.Geometrická interpretace umožňuje vizualizovat i nižší cenu hry α a vyšší β .y .I .I I .B2 .B1′ .N .B1 B2′ .β = a21 .α = a22 .I I .I .∗ .x .P2 . A∗ S . 1∗ P Na stejném grafu lze také podat geometrickou interpretaci optimálních strategií hráče B . Je snadné vidět, ž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′ maximum spodní hranice výplaty uvažujte 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 m an. 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. Stačí jen najít tyto strategie a hra 2 × n se promění ve hru 2 × 2, která je vyřešena elementárně. Hledání aktivních strategií lze provést graficky: 1) sestaví se grafická interpretace; 2) je určena spodní hranice zisku; 3) na spodní hranici výplaty se rozlišují dvě strategie druhého hráče, které odpovídají dvěma čarám, které se protínají v bodě s maximální pořadnicí (pokud se na něm protíná více než dvě čáry, bere se libovolný pár) - tyto strategie jsou 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 se nekonstruuje horní hranice výplaty a ne maximum, ale hledá se na ní 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. Čáry B1 − B1′ , B2 − B2′ a B3 − B3′ odpovídají strategiím B1 , B2 , B3 . Přerušovaná čára B1 N B2 je dolní hranicí odměny 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á hodnota hry, 7 příkladů, 10 2 × n, 9, 16 m × 2, 9 , 16 nekonečný, 4 normální tvar, 5 konečný, 4 vícecestný, 4 jednosměrný, 4 maticový, 5 dvojitý, 2 nulový součet, 2 antagonistické, 2 neantagonistické, 2 řešení, 5 smíšených strategií, 5, 9 čisté strategie . 5 teorie her, 2 18

Pokud existuje více konfliktních stran (osob), z nichž každá učiní nějaké rozhodnutí určené daným souborem pravidel a každá ze stran zná konečný stav konfliktní situace s platbami předem určenými pro každou ze stran, pak říkáme, že existuje hra.

Úkolem teorie her je zvolit pro daného hráče takovou linii chování, od které odchylka může jen snížit jeho výplatu.

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á hráčská strategie .

Strategie hráče se nazývá optimální, pokud při mnohonásobném opakování hry poskytuje hráči maximální možnou průměrnou výplatu (nebo, což je totéž, minimální možnou průměrnou výplatu).

Hra definovaná maticí A, který má m linky a n sloupců se nazývá hra konečných párů dimenzí m* n;

Kde i=
je strategie prvního hráče s m strategiemi; j=je strategie druhého hráče s n strategiemi; ij je odměnou prvního hráče i-tá strategie, když ji použije druhá j-tá strategie (nebo, co je totéž, ztráta druhé j strategie, je-li použita jako první i th);

A =   ij je výplatní matice hry.

1.1 Hraní s čistými strategiemi

Nižší cena hry (pro prvního hráče)

 = max (min ij). (1.2)

i j

Horní cena hry (pro druhého hráče):

= min (max ij) . (1.3)

J i

Li  =  , hra se nazývá se sedlovým bodem (1.4), nebo hra s čistými strategiemi. V čem PROTI =  =  nazývaná cenná hra ( PROTI- cena hry).

Příklad. Daná výplatní matice pro hru pro 2 osoby A. Určete optimální strategie pro každého z hráčů a cenu hry:

(1.4)

max 10 9 12 6

min 6

je strategie prvního hráče (řady).

Strategie druhého hráče (sloupce).

- cena hry.

Hra má tedy sedlovou pointu. Strategie j = 4 je optimální strategie pro druhého hráče i=2 - pro první. Máme hru s čistými strategiemi.

1.2 Smíšené strategické hry

Pokud výplatní matice nemá sedlový bod, tzn.
, a žádný z účastníků hry si nemůže zvolit jeden plán jako svou optimální strategii, hráči přecházejí na „smíšené strategie“. V tomto případě každý z 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á hráčova smíšená strategie.

X= (X 1 …X i …X m) je smíšená strategie prvního hráče.

Na= (na 1 ...na j ...na n) je 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*) je 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 cenou hry.

(1.6)

V pořadí podle čísla PROTI byla cena hry a X* A na* - optimální strategie, je nutné a postačující, aby nerovnosti

(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áč uplatňovat 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í:

Sestavme 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), dělíme levou a pravou stranu výrazů (1.9), (1.10) PROTI. Po přijetí na j /PROTI pro novou proměnnou z i, dostaneme nový systém omezení (1.11) a Objektivní 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) do podoby 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 model druhého hráče, protože tyto proměnné jsou v jeho výplatním modelu (1.13), (1.14).

Redukujeme (1.15), (1.16) na kanonickou formu

(1.17)

Herní teorie - agregát matematické metodyřešení konfliktních situací (střet zájmů). V teorii her je hra matematický model konfliktní situace. Předmětem zvláštního zájmu v teorii her je studium rozhodovacích strategií účastníků hry v podmínkách nejistoty. Nejistota je způsobena skutečností, že dvě nebo více stran sledují opačné cíle a výsledky jakékoli akce každé ze stran závisí na tahech partnera. Každá ze stran přitom usiluje o optimální rozhodnutí, která v největší míře realizují stanovené cíle.

Nejdůsledněji se teorie her uplatňuje v ekonomice, kde vznikají konfliktní situace např. ve vztazích mezi dodavatelem a spotřebitelem, kupujícím a prodávajícím, bankou a klientem. Aplikaci teorie her lze nalézt také v politice, sociologii, biologii a vojenském umění.

Z historie teorie her

Historie teorie her jako samostatná disciplína začíná v roce 1944, kdy John von Neumann a Oscar Morgenstern vydali knihu „Teorie her a ekonomické chování“ („Teorie her a ekonomické chování“). Ačkoli se s příklady teorie her setkali již dříve: pojednání babylonského Talmudu o dělení majetku zesnulého manžela mezi jeho manželky, karetní hry v 18. století, vývoj teorie šachu na počátku 20. století, důkaz minimax teorému téhož Johna von Neumanna v roce 1928, bez kterého by neexistovala teorie her.

V 50. letech 20. století Melvin Drescher a Meryl Flood z Rand Corporation První, kdo experimentálně aplikoval vězňovo dilema, John Nash, ve své práci o stavu rovnováhy ve hrách pro dvě osoby, vyvinul koncept Nashovy rovnováhy.

Reinhard Salten v roce 1965 vydal knihu „Oligopoly processing in game theory on demand“ („Spieltheoretische Behandlung eines Oligomodells mit Nachfrageträgheit“), s níž aplikace teorie her v ekonomii dostala novou hnací sílu. Krok vpřed ve vývoji teorie her je spojen s prací Johna Maynarda Smitha „Evolutionary Stable Strategy“ („Evolutionary Stable Strategy“, 1974). Vězeňovo dilema bylo popularizováno v knize Roberta Axelroda The Evolution of Cooperation, vydané v roce 1984. V roce 1994 získali John Nash, John Harsanyi a Reinhard Salten Nobelovu cenu za teorii her.

Teorie her v životě a podnikání

Zastavme se podrobněji u podstaty konfliktní situace (střetu zájmů) ve smyslu, jak je chápána v teorii her pro další modelování různých situací v životě a podnikání. Nechte jednotlivce být v pozici, která vede k jednomu z několika možných výsledků, a jednotlivec má ve vztahu k těmto výsledkům určité osobní preference. Ale ačkoliv může do jisté míry ovládat proměnlivé faktory, které určují výsledek, nemá nad nimi úplnou kontrolu. Někdy je kontrola v rukou několika jedinců, kteří stejně jako on upřednostňují možné výsledky, ale v obecný případ zájmy těchto jedinců nesouhlasí. V jiných případech může konečný výsledek záviset jak na nehodách (někdy v právních vědách nazývaných přírodní katastrofy), tak na dalších jednotlivcích. Teorie her systematizuje pozorování takových situací a formuluje obecné zásady vést v takových situacích rozumné jednání.

V některých ohledech je název „teorie her“ nešťastný, protože naznačuje, že teorie her se zabývá pouze společenská hodnota střety, ke kterým dochází v společenských hrách, ale přesto má tato teorie mnohem širší význam.

Následující ekonomická situace může poskytnout představu o aplikaci teorie her. Předpokládejme, že existuje několik podnikatelů, z nichž každý se snaží maximalizovat zisk, přičemž má pouze omezenou moc nad proměnnými, které tento zisk určují. Podnikatel nemá kontrolu nad proměnnými, které kontroluje jiný podnikatel, ale které mohou velmi ovlivnit příjem toho prvního. Interpretace této situace jako hry může vést k následující námitce. Herní model předpokládá, že každý podnikatel udělá jednu volbu z oblasti možných voleb a zisky jsou určeny těmito jednotlivými volbami. Je zřejmé, že ve skutečnosti je to téměř nemožné, protože v tomto případě by v průmyslu nebyly potřeba složité administrativní aparáty. Jde jen o to, že existuje řada rozhodnutí a modifikací těchto rozhodnutí, které závisí na volbách ostatních účastníků. ekonomický systém(hráči). Ale v zásadě si lze představit, že každý administrátor předvídá všechny možné nepředvídatelné události a podrobně popisuje akci, která má být v každém případě provedena, namísto toho, aby řešil každý úkol tak, jak se objeví.

Vojenský konflikt je podle definice střetem zájmů, ve kterém ani jedna strana nemá plnou kontrolu nad proměnnými, které určují výsledek, o kterém rozhoduje série bitev. Výsledek můžete jednoduše považovat za výhru nebo prohru a přiřadit jim číselné hodnoty 1 a 0.

Jednou z nejjednodušších konfliktních situací, které lze v teorii her zapsat a vyřešit, je souboj, což je konflikt mezi dvěma hráči 1 a 2, kteří mají resp. p A q výstřely. Pro každého hráče existuje funkce udávající pravděpodobnost, že hráč trefil i v době, kdy t dá zásah, který se stane osudným.

V důsledku toho teorie her dospívá k následující formulaci určité třídy střetů zájmů: existují n hráčů a každý hráč si musí vybrat jednu možnost z určité sady 100 a při výběru nemá hráč žádné informace o volbách ostatních hráčů. Oblast s možnými volbami hráče může obsahovat položky jako „přesunout pikové eso“, „vyrobit tanky místo aut“ nebo obecný smysl, strategie, která definuje všechny akce, které je třeba podniknout za všech možných okolností. Každý hráč stojí před úkolem: jakou volbu by měl učinit, aby mu jeho soukromý vliv na výsledek přinesl co největší zisk?

Matematický model v teorii her a formalizaci problémů

Jak jsme již poznamenali, hra je matematický model konfliktní situace a vyžaduje následující komponenty:

zainteresované strany;
možné akce na každé straně;
zájmy stran.

Zájemci o hru se nazývají hráči. , každý z nich může provést minimálně dvě akce (pokud má hráč pouze jednu akci, tak se ve skutečnosti hry neúčastní, protože je předem známo, co provede). Výsledek hry se nazývá výhra. .

Skutečná konfliktní situace není vždy, ale hra (v pojetí teorie her) - vždy - pokračuje určitá pravidla , které přesně definují:

možnosti hráče;
množství informací, které má každý hráč o chování partnera;
přínos, ke kterému vede každá sada akcí.

Příklady formalizovaných her jsou fotbal, karetní hra, šachy.

V ekonomii ale vzniká model chování hráčů, například když se několik firem snaží zaujmout výhodnější místo na trhu, několik jedinců se snaží mezi sebou sdílet nějaké statky (zdroje, finance), aby každý dostal co nejvíce. . Hráči v konfliktních situacích v ekonomice, které lze modelovat jako hru, jsou firmy, banky, jednotlivci a další ekonomické subjekty. Ve válečných podmínkách se zase herní model využívá například při výběru více nejlepší zbraň(z dostupných nebo potenciálně možných) porazit nepřítele nebo chránit před útokem.

Pro hru je charakteristická nejistota výsledku . Příčiny nejistoty lze rozdělit do následujících skupin:

kombinatorický (jako v šachu);
vliv náhodných faktorů (jako ve hře „hlavy nebo ocasy“, kostky, karetní hry);
strategické (hráč neví, jakou akci soupeř provede).

Strategie hráče je soubor pravidel, která určují jeho akce při každém pohybu v závislosti na situaci.

Cíl teorie her je určit optimální strategii pro každého hráče. Určit takovou strategii znamená vyřešit hru. Optimalizace strategie je dosaženo, když jeden z hráčů musí získat maximální výplatu, zatímco druhý dodržuje svou strategii. A druhý hráč by měl mít minimální ztrátu, pokud se první drží své strategie.

Klasifikace hry

Rozdělení podle počtu hráčů (hra dvou a více osob). Hry pro dvě osoby jsou ústředním bodem celé teorie her. Základní koncept teorie her pro hry pro dvě osoby je zobecněním velmi podstatné myšlenky rovnováhy, která se přirozeně objevuje ve hrách pro dvě osoby. Co se týče her n osob, pak je jedna část teorie her věnována hrám, ve kterých je zakázána spolupráce mezi hráči. V další části teorie her n osob se předpokládá, že hráči mohou spolupracovat pro vzájemný prospěch (viz dále v tomto odstavci o nekooperativních a kooperativních hrách).
Klasifikace podle počtu hráčů a jejich strategií (počet strategií je alespoň dvě, může být nekonečno).
Klasifikace podle množství informací týkající se minulých tahů: hry s úplnými informacemi a neúplnými informacemi. Nechť je hráč 1 - kupující a hráč 2 - prodávající. Pokud hráč 1 nemá úplné informace o akcích hráče 2, pak hráč 1 nemusí rozlišovat mezi dvěma alternativami, mezi kterými si musí vybrat. Například vybrat si mezi dvěma typy určitého produktu a nevědět, že podle některých vlastností produkt A horší než zboží B, hráč 1 nemusí vidět rozdíl mezi alternativami.
Rozdělení podle zásad dělení výher : družstevní, koaliční na jedné straně a nespolupracující, nespolupracující na straně druhé. V nekooperativní hra , nebo jinak - nekooperativní hra , hráči volí strategie současně, aniž by věděli, jakou strategii zvolí druhý hráč. Komunikace mezi hráči není možná. V kooperativní hra , nebo jinak - koaliční hru , hráči mohou vytvářet koalice a podnikat kolektivní akce ke zvýšení svých výher.
Hra pro dvě osoby s konečným nulovým součtem nebo antagonistická hra je strategická hra s úplnými informacemi zahrnujícími strany s opačnými zájmy. Antagonistické hry jsou maticové hry .

Klasickým příkladem z teorie her je vězňovo dilema.

Oba podezřelí jsou vzati do vazby a izolováni od sebe. Okresní státní zástupce je přesvědčen, že spáchali závažný trestný čin, ale nemá dostatek důkazů, aby je u soudu obvinil. Každému z vězňů říká, že má dvě alternativy: přiznat se k činu, o kterém se policie domnívá, že spáchal, nebo se nepřiznat. Pokud se oba nepřiznají, pak je okresní státní zástupce obviní z nějakého drobného trestného činu, jako jsou drobné krádeže nebo nedovolené držení zbraně, a oba dostanou malý trest. Pokud se oba přiznají, budou stíháni, ale nebude to vyžadovat nejpřísnější trest. Pokud se jeden přizná a druhý ne, pak bude mít přiznaný zmírněný trest za vydání spolupachatele, zatímco tvrdohlavý dostane „naplno“.

Pokud je tento strategický úkol formulován ve smyslu závěru, pak se scvrkává na následující:

Pokud se tedy oba vězni nepřiznají, dostanou každý 1 rok. Pokud se oba přiznají, pak každý dostane 8 let. A když se jeden přizná, druhý ne, tak ten, kdo se přizná, dostane tři měsíce vězení, a kdo se nepřizná, dostane 10 let. Výše uvedená matice správně odráží vězňovo dilema: každý stojí před otázkou, zda se přiznat či nepřiznat. Hra, kterou okresní prokurátor vězňům nabízí, je nekooperativní hra nebo jinak - nekoaliční hra . Pokud by oba vězni byli schopni spolupracovat (tj. hra bude kooperativní nebo jinak koaliční hru ), pak se oba nepřiznali a každý dostal rok vězení.

Příklady použití matematických prostředků teorie her

Nyní přejdeme k úvahám o řešení příkladů běžných tříd her, pro které existují metody zkoumání a řešení v teorii her.

Příklad formalizace nekooperativní (nekooperativní) hry dvou osob

V předchozím odstavci jsme již uvažovali o příkladu nekooperativní (nekooperativní) hry (vězeňské dilema). Upevněme své dovednosti. K tomu se hodí i klasická zápletka inspirovaná Dobrodružství Sherlocka Holmese Arthura Conana Doyla. Lze samozřejmě namítnout: příklad není ze života, ale z literatury, ale Conan Doyle se neprosadil jako spisovatel sci-fi! Klasické také proto, že úkol splnil Oscar Morgenstern, jak jsme již utvrdili - jeden ze zakladatelů teorie her.

Příklad 1 Bude uveden zkrácený úryvek z jednoho z Dobrodružství Sherlocka Holmese. Vytvořte si podle známých pojmů teorie her model konfliktní situace a hru formálně zapište.

Sherlock Holmes hodlá jít z Londýna do Doveru s dalším cílem dostat se na kontinent (evropský), aby unikl profesoru Moriartymu, který ho pronásleduje. Když nastoupil do vlaku, uviděl na nástupišti profesora Moriartyho. Sherlock Holmes připouští, že Moriarty si umí vybrat speciální vlak a předjet ho. Sherlock Holmes má dvě alternativy: pokračovat do Doveru nebo vystoupit na stanici Canterbury, která je jedinou mezistanicí na jeho trase. Předpokládáme, že jeho protivník je dostatečně inteligentní, aby určil Holmesovy možnosti, takže má dvě stejné alternativy. Oba soupeři si musí vybrat stanici, ve které vystoupí z vlaku, aniž by věděli, jaké rozhodnutí každý z nich učiní. Pokud v důsledku rozhodnutí skončí oba na stejné stanici, pak můžeme definitivně předpokládat, že Sherlocka Holmese zabije profesor Moriarty. Pokud se Sherlock Holmes dostane bezpečně do Doveru, bude zachráněn.

Řešení. Hrdiny Conana Doyla lze považovat za účastníky hry, tedy hráče. K dispozici každému hráči i (i=1,2) dvě čisté strategie:

vystupte v Doveru (strategie si1 ( i=1,2) );
vystupte na mezistanici (strategie si2 ( i=1,2) )

V závislosti na tom, kterou ze dvou strategií si každý ze dvou hráčů zvolí, bude vytvořena speciální kombinace strategií jako pár s = (s1 , s 2 ) .

Každá kombinace může být spojena s událostí – výsledkem pokusu profesora Moriartyho zabít Sherlocka Holmese. Vytváříme matici této hry s možnými událostmi.

Pod každou z událostí je uveden index, který znamená získání profesora Moriartyho a vypočítává se v závislosti na spáse Holmese. Oba hrdinové volí strategii zároveň, nevědí, jakou zvolí protivník. Hra je tedy nekooperativní, protože za prvé jsou hráči v různých vlacích a za druhé mají opačné zájmy.

Příklad formalizace a řešení kooperativní (koaliční) hry n osob

Na tomto místě bude praktické části, tedy průběhu řešení příkladové úlohy, předcházet část teoretická, ve které se seznámíme s pojmy teorie her pro řešení kooperativních (nekooperativních) her. Pro tento úkol teorie her navrhuje:

charakteristická funkce (zjednodušeně řečeno odráží hodnotu výhod spojení hráčů do koalice);
koncept aditivity (vlastnost množství, spočívající ve skutečnosti, že hodnota množství odpovídající celému objektu se rovná součtu hodnot množství odpovídajících jeho částem, v určité třídě rozdělení objektu na části) a superaditivitu (hodnota veličiny odpovídající celému objektu je větší než součet hodnot veličin odpovídajících jejím částem) charakteristické funkce.

Superaditivita charakteristické funkce naznačuje, že koalice jsou pro hráče výhodné, protože v tomto případě se s počtem hráčů zvyšuje výnos koalice.

Abychom hru formalizovali, musíme zavést formální zápis pro výše uvedené pojmy.

Pro hru n označte množinu všech jejích hráčů jako N= (1,2,...,n) Libovolná neprázdná podmnožina množiny N označený jako T(včetně sebe N a všechny podmnožiny sestávající z jednoho prvku). Na webu probíhá aktivita Množiny a operace na množinách, které se po kliknutí na odkaz otevře v novém okně.

Charakteristická funkce je označena jako proti a jeho doména definice se skládá z možných podmnožin množiny N. proti(T) - hodnota charakteristické funkce pro konkrétní podmnožinu, například příjem obdržený koalicí, případně sestávající z jednoho hráče. To je důležité, protože teorie her vyžaduje kontrolu přítomnosti superaditivity pro hodnoty charakteristické funkce všech nepřekrývajících se koalic.

Pro dvě neprázdné koalice podmnožin T1 A T2 aditivnost charakteristické funkce kooperativní (koaliční) hry se píše takto:

A superadditivita je taková:

Příklad 2 Tři studenti hudební školy si přivydělávají v různých klubech, výtěžek dostávají od návštěvníků klubu. Zjistěte, zda je pro ně výhodné spojit síly (pokud ano, za jakých podmínek), s využitím konceptů teorie her k řešení kooperativních her n osob s následujícími výchozími údaji.

V průměru jejich tržby za večer byly:

houslista má 600 jednotek;
kytarista má 700 jednotek;
zpěvák má 900 jednotek.

Ve snaze zvýšit příjmy vytvořili studenti několik měsíců různé skupiny. Výsledky ukázaly, že spojením by mohli zvýšit své večerní tržby následovně:

houslista + kytarista vydělali 1500 jednotek;
houslista + zpěvák vydělal 1800 jednotek;
kytarista + zpěvák vydělali 1900 jednotek;
houslista + kytarista + zpěvák vydělali 3000 jednotek.

Řešení. V tomto příkladu počet účastníků ve hře n= 3 , tedy obor charakteristické funkce hry sestává z 2³ = 8 možných podmnožin množiny všech hráčů. Uveďme všechny možné koalice T:

koalice jednoho prvku, z nichž každý se skládá z jednoho hráče - hudebníka: T{1} , T{2} , T{3} ;
koalice dvou prvků: T{1,2} , T{1,3} , T{2,3} ;
koalice z tři prvky: T{1,2,3} .

Každému z hráčů přidělujeme sériové číslo:

houslista - 1. hráč;
kytarista - 2. hráč;
zpěvák je 3. hráč.

Podle problémových údajů určíme charakteristickou funkci zvěře proti:

v(T(l)) = 600; v(T(2)) = 700; v(T(3)) = 900; tyto hodnoty charakteristické funkce jsou určeny na základě výplat prvního, druhého a třetího hráče, pokud nejsou spojeni v koalicích;

v(T(1,2)) = 1500; v(T(1,3)) = 1800; v(T(2,3)) = 1900; tyto hodnoty charakteristické funkce jsou určeny příjmem každé dvojice hráčů spojených v koalicích;

v(T(1,2,3)) = 3000; tato hodnota charakteristické funkce je určena průměrným výnosem v případě, kdy byli hráči spojeni do trojic.

Vyjmenovali jsme tedy všechny možné koalice hráčů, je jich osm, jak má být, neboť doménu definice charakteristické funkce hry tvoří právě osm možných podmnožin množiny všech hráčů. Což je to, co teorie her vyžaduje, protože musíme zkontrolovat přítomnost superaditivity pro hodnoty charakteristické funkce všech nepřekrývajících se koalic.

Jak jsou v tomto příkladu splněny podmínky superaditivity? Pojďme definovat, jak hráči tvoří nepřekrývající se koalice T1 A T2 . Pokud jsou někteří hráči v koalici T1 , pak jsou všichni ostatní hráči v koalici T2 a podle definice je tato koalice tvořena jako rozdíl mezi celkovou množinou hráčů a množinou T1 . Pak pokud T1 - koalice jednoho hráče, poté v koalici T2 bude druhý a třetí hráč, pokud bude v koalici T1 bude prvním a třetím hráčem, pak koalice T2 se bude skládat pouze z druhého hráče a tak dále.