Hra s nulovým súčtom, v ktorej má každý hráč k dispozícii konečný súbor stratégií. Pravidlá maticovej hry určuje platobná matica, ktorej prvkami sú výhry prvého hráča, ktoré sú zároveň prehrami druhého hráča.
Maticová hra je antagonistická hra. Prvý hráč získa maximálnu garantovanú (nezávisle od správania druhého hráča) výhru rovnú cene hry, podobne druhý hráč dosiahne minimálnu garantovanú prehru.
Pod stratégie sa chápe ako súbor pravidiel (princípov), ktoré určujú výber akcie pre každý osobný ťah hráča v závislosti od aktuálnej situácie.
Teraz o všetkom v poriadku a podrobne.
Platobná matica, čisté stratégie, cena hry
IN maticová hra sú určené jeho pravidlá platobná matica .
Predstavte si hru, v ktorej sú dvaja účastníci: prvý hráč a druhý hráč. Nech má k dispozícii prvý hráč m čisté stratégie a druhý hráč má k dispozícii - nčisté stratégie. Keďže sa o hre uvažuje, je prirodzené, že v tejto hre sú výhry a prehry.
IN platobná matica prvkami sú čísla vyjadrujúce výhry a prehry hráčov. Výhry a prehry môžu byť vyjadrené v bodoch, množstve peňazí alebo iných jednotkách.
Vytvorme platobnú maticu:
Ak sa prvý hráč rozhodne i- čistá stratégia a druhý hráč - jčistá stratégia, potom bude odmena prvého hráča aij jednotiek a strata druhého hráča je tiež aij Jednotky.
Pretože aij + (- a ij) = 0, potom je opísaná hra maticová hra s nulovým súčtom.
Najjednoduchším príkladom maticovej hry je hádzanie mincou. Pravidlá hry sú nasledovné. Prvý a druhý hráč hodí mincou a výsledkom sú buď hlavy alebo chvosty. Ak sú „hlavy“ a „hlavy“ alebo „chvosty“ alebo „chvosty“ hádzané súčasne, potom prvý hráč vyhrá jednu jednotku a v ostatných prípadoch stratí jednu jednotku (druhý hráč vyhrá jednu jednotku) . Druhý hráč má k dispozícii dve rovnaké stratégie. Zodpovedajúca platobná matica bude takáto:
Úlohou teórie hier je určiť voľbu stratégie prvého hráča, ktorá by mu zaručila maximálnu priemernú výhru, ako aj voľbu stratégie druhého hráča, ktorá by mu zaručila maximálnu priemernú prehru.
Ako si vyberáte stratégiu v maticovej hre?
Pozrime sa ešte raz na platobnú maticu:
Najprv určme výšku výhry pre prvého hráča, ak použije ičistá stratégia. Ak prvý hráč použije ičistej stratégie, potom je logické predpokladať, že druhý hráč použije takú čistú stratégiu, vďaka ktorej by bol zisk prvého hráča minimálny. Prvý hráč zase použije takú čistú stratégiu, ktorá by mu zabezpečila maximálna výhra. Na základe týchto podmienok výhra prvého hráča, ktorú označujeme ako v1 , volal maximálne výhry alebo dno za cenu hry .
O pre tieto hodnoty by mal prvý hráč postupovať nasledovne. Z každého riadku si zapíšte hodnotu minimálneho prvku a vyberte z nich maximálny. Výhra prvého hráča teda bude maximálna z minima. Odtiaľ pochádza názov - maximin win. Číslo riadku tohto prvku bude číslom čistej stratégie, ktorú si zvolí prvý hráč.
Teraz určme výšku straty pre druhého hráča, ak použije j stratégiu. V tomto prípade prvý hráč používa vlastnú čistú stratégiu, v ktorej by strata druhého hráča bola maximálna. Druhý hráč musí zvoliť čistú stratégiu, pri ktorej by bola jeho strata minimálna. Strata druhého hráča, ktorú označujeme ako v2 , volal minimax strata alebo najvyššia cena hry .
O riešenie problémov o cene hry a určenie stratégie Ak chcete určiť tieto hodnoty pre druhého hráča, postupujte takto. Z každého stĺpca si zapíšte hodnotu maximálneho prvku a vyberte z neho minimum. Strata druhého hráča bude teda minimom z maxima. Odtiaľ pochádza názov - minimax win. Číslo stĺpca tohto prvku bude číslom čistej stratégie, ktorú si zvolí druhý hráč. Ak druhý hráč použije „minimax“, potom bez ohľadu na výber stratégie prvým hráčom nestratí viac ako v2 Jednotky.
Príklad 1
.
Najväčší z najmenších prvkov radov je 2, to je nižšia cena hry, tomu zodpovedá prvý riadok, preto je stratégia maximin prvého hráča prvá. Najmenší z najväčších prvkov stĺpcov je 5, to je horná cena hry, tomu zodpovedá druhý stĺpec, preto je minimaxová stratégia druhého hráča druhá.
Teraz, keď sme sa naučili nájsť spodnú a hornú cenu hry, stratégie maximin a minimax, je čas naučiť sa formálne definovať tieto pojmy.
Takže zaručená výhra pre prvého hráča je:
Prvý hráč si musí zvoliť čistú stratégiu, ktorá by mu zabezpečila maximum z minimálnych výhier. Tento zisk (maximum) je označený takto:
.
Prvý hráč používa svoju čistú stratégiu tak, aby strata druhého hráča bola maximálna. Táto strata je označená takto:
Druhý hráč musí zvoliť svoju čistú stratégiu tak, aby jeho strata bola minimálna. Táto strata (minimax) je indikovaná nasledovne:
.
Ďalší príklad z rovnakej série.
Príklad 2 Daná maticová hra s výplatnou maticou
.
Určite stratégiu maxima prvého hráča, stratégiu minimaxu druhého hráča, dolnú a hornú cenu hry.
Riešenie. Napravo od matice platieb vypíšeme najmenšie prvky v jej riadkoch a označíme ich maximum a pod maticou - najväčšie prvky v stĺpcoch a vyberte najmenší z nich:
Najväčší z najmenších prvkov línií je 3, to je nižšia cena hry, tomu zodpovedá druhý riadok, preto je maximálna stratégia prvého hráča druhá. Najmenší z najväčších prvkov stĺpcov je 5, to je horná cena hry, tomu zodpovedá prvý stĺpec, preto je minimax stratégia druhého hráča prvá.
Sedlový bod v maticových hrách
Ak sú horné a dolné ceny hry rovnaké, potom sa maticová hra považuje za sedlovú. Platí to aj naopak: ak má maticová hra sedlový bod, horná a dolná cena maticovej hry sú rovnaké. Príslušný prvok je najmenší v riadku a najväčší v stĺpci a rovná cene hry.
Ak teda , potom je optimálna čistá stratégia prvého hráča a optimálna čistá stratégia druhého hráča. To znamená, že rovnaké nižšie a vyššie ceny hier sa dosahujú pomocou rovnakého páru stratégií.
V tomto prípade maticová hra má riešenie v čistých stratégiách .
Príklad 3 Daná maticová hra s výplatnou maticou
.
Riešenie. Napravo od matice platieb vypíšeme najmenšie prvky v jej riadkoch a zaznamenáme ich maximum a pod maticou - najväčšie prvky v stĺpcoch a vyberieme ich minimum:
Nižšia cena hry sa zhoduje s hornou cenou hry. Cena hry je teda 5. To znamená . Cena hry sa rovná hodnote sedlového bodu. Maxin stratégia prvého hráča je druhá čistá stratégia a minimax stratégia druhého hráča je tretia čistá stratégia. Táto maticová hra má riešenie v čistých stratégiách.
Vyriešte problém maticovej hry sami a potom sa pozrite na riešenie
Príklad 4. Daná maticová hra s výplatnou maticou
.
Nájdite spodnú a hornú cenu hry. Má táto maticová hra sedlovú pointu?
Matrixové hry s optimálnou zmiešanou stratégiou
Vo väčšine prípadov maticová hra nemá sedlový bod, takže zodpovedajúca maticová hra nemá žiadne riešenia v čistých stratégiách.
Ale má riešenie v optimálnych zmiešaných stratégiách. Aby ste ich našli, musíte predpokladať, že sa hra opakuje toľkokrát, aby ste na základe skúseností vedeli odhadnúť, ktorá stratégia je vhodnejšia. Preto je rozhodnutie spojené s pojmom pravdepodobnosť a priemer (matematické očakávanie). V konečnom riešení je analóg sedlového bodu (to znamená rovnosť dolnej a hornej ceny hry), ako aj analóg stratégií, ktoré im zodpovedajú.
Aby teda prvý hráč získal maximálnu priemernú výhru a druhý hráč mal minimálnu priemernú prehru, mali by sa s určitou pravdepodobnosťou používať čisté stratégie.
Ak prvý hráč používa čisté stratégie s pravdepodobnosťou 
, potom vektor 
sa nazýva zmiešaná stratégia prvého hráča. Inými slovami, je to „zmes“ čistých stratégií. V tomto prípade sa súčet týchto pravdepodobností rovná jednej:
.
Ak druhý hráč používa čisté stratégie s pravdepodobnosťou 
, potom vektor 
sa nazýva zmiešaná stratégia pre druhého hráča. V tomto prípade sa súčet týchto pravdepodobností rovná jednej:
.
Ak prvý hráč používa zmiešanú stratégiu p, a druhý hráč - zmiešaná stratégia q, potom to dáva zmysel očakávaná hodnota výhra prvého hráča (prehra druhého hráča). Aby ste to našli, musíte vynásobiť vektor zmiešanej stratégie prvého hráča (čo bude jednoriadková matica), maticu výplaty a vektor zmiešanej stratégie druhého hráča (čo bude matica s jedným stĺpcom):
.
Príklad 5. Daná maticová hra s výplatnou maticou
.
Určte matematické očakávanie výhry prvého hráča (prehry druhého hráča), ak zmiešaná stratégia prvého hráča je , a zmiešaná stratégia druhého hráča je .
Riešenie. Podľa vzorca pre matematické očakávanie výhry prvého hráča (prehry druhého hráča) sa rovná súčinu vektora zmiešanej stratégie prvého hráča, platobnej matice a vektora zmiešanej stratégie druhého hráča:
Prvý hráč sa nazýva taká zmiešaná stratégia, ktorá by mu pri dostatočnom počte opakovaní zabezpečila maximálnu priemernú výplatu.
Optimálna zmiešaná stratégia druhý hráč sa nazýva taká zmiešaná stratégia, ktorá by mu zabezpečila minimálnu priemernú stratu, ak by sa hra opakovala dostatočný počet krát.
Analogicky so zápisom maximínu a minimaxu v prípade čistých stratégií sa optimálne zmiešané stratégie označujú nasledovne (a súvisia s matematické očakávanie, teda priemer výhier prvého hráča a prehier druhého hráča):
,
.
V tomto prípade pre funkciu E je tam sedlový bod , čo znamená rovnosť.
Aby sa našli optimálne zmiešané stratégie a sedlový bod, tj. vyriešiť maticovú hru v zmiešaných stratégiách , musíte zredukovať maticovú hru na problém lineárneho programovania, teda na problém optimalizácie, a vyriešiť zodpovedajúci problém lineárneho programovania.
Redukcia maticovej hry na problém lineárneho programovania
Ak chcete vyriešiť maticovú hru v zmiešaných stratégiách, musíte vytvoriť priamku problém lineárneho programovania A dvojitá úloha. V duálnom probléme sa transponuje rozšírená matica, ktorá ukladá koeficienty premenných v systéme obmedzení, voľných členov a koeficientov premenných v cieľovej funkcii. V tomto prípade sa minimum cieľovej funkcie pôvodného problému zhoduje s maximom v duálnom probléme.
Cieľová funkcia v úlohe priameho lineárneho programovania:
.
Systém obmedzení v úlohe priameho lineárneho programovania:
Cieľová funkcia v duálnom probléme je:
.
Systém obmedzení v duálnom probléme:
Optimálny plán pre problém priameho lineárneho programovania je označený
,
a optimálny plán pre duálny problém je označený
Lineárne formy pre zodpovedajúce optimálne plány označme a,
a je potrebné ich nájsť ako súčty zodpovedajúcich súradníc optimálnych plánov.
V súlade s definíciami predchádzajúceho odseku a súradnicami optimálnych plánov platia nasledujúce zmiešané stratégie prvého a druhého hráča:
.
Teoretickí matematici to dokázali cena hry sa vyjadruje nasledujúcim spôsobom prostredníctvom lineárnych foriem optimálnych plánov:
,
to znamená, že ide o prevrátenú hodnotu súčtu súradníc optimálnych plánov.
My, praktizujúci, môžeme použiť tento vzorec iba na riešenie maticových hier v zmiešaných stratégiách. Páči sa mi to vzorce na hľadanie optimálnych zmiešaných stratégií prvý a druhý hráč:
v ktorých sú druhými faktormi vektory. Optimálne zmiešané stratégie sú tiež, ako sme už definovali v predchádzajúcom odseku, vektory. Preto vynásobením čísla (ceny hry) vektorom (so súradnicami optimálnych plánov) získame aj vektor.
Príklad 6. Daná maticová hra s výplatnou maticou
.
Zistite cenu hry V a optimálne zmiešané stratégie a .
Riešenie. Vytvárame problém lineárneho programovania zodpovedajúci tejto maticovej hre:
Získame riešenie priameho problému:
.
Lineárny tvar optimálnych plánov nájdeme ako súčet nájdených súradníc.
Zvážte párovú konečnú hru. Nechajte hráča A má T osobné stratégie, ktoré označujeme
Nechajte hráča IN k dispozícii P osobné stratégie, označme ich. Hovorí sa, že hra má rozmery T X P.
V dôsledku toho, že si hráči zvolia ľubovoľnú dvojicu stratégií, je výsledok hry jednoznačne určený, t.j. výhry A;. hráč A(pozitívne alebo negatívne) a straty (-ay) hráč IN. Predpokladajme, že hodnoty A.. známy pre akúkoľvek dvojicu stratégií (A:, B;). Matrix P =(a..), i = = 1, 2, ..., m j = 1, 2, ..., P, ktorých prvkami sú výhry zodpovedajúce stratégiám A. A Bj, volal platobná matica, alebo matice hry. Všeobecná forma takáto matica je uvedená v tabuľke. 12.1. Riadky tejto tabuľky zodpovedajú stratégiám hráča A, a stĺpce – stratégie hráča IN.
Tabuľka 12.1
Vytvorme platobnú maticu pre ďalšiu hru.
12.1. Hľadanie hry.
Hráč A môže sa ukryť v jednom z dvoch úkrytov (I a II); hráč IN hľadá hráča A, a ak ho nájde, dostane pokutu 1 den. Jednotky od A, inak zaplatí hráč A 1 deň Jednotky Je potrebné zostaviť platobnú maticu hry.
RIEŠENIE. Kompilovať platobná matica malo by sa analyzovať správanie každého hráča. Hráč A môže sa skrývať v úkryte I - túto stratégiu označujeme A v alebo do úkrytu II – stratégia A. d Prehrávač IN môže hľadať prvého hráča v úkryte I – stratégia IN(alebo do útulku II - stratégia IN.,. Ak hráč A sa nachádza vo Vault I a tam ho objaví hráč IN, tie. implementuje sa niekoľko stratégií (Α ν IN{), potom hráč A zaplatí pokutu, t.j. A n = -1. Podobne dostaneme A. n = -1 (A 2, IN.,). Je zrejmé, že stratégie (A, IN.,) a (L2, /1,) dajte hráčovi A odmena je 1, teda A P = a. n = I. Pre vyhľadávaciu hru s veľkosťou 2x2 teda získame výplatnú maticu:
Zvážte hru T X P s matricou P = a j) , i = 1,2, ..., τη; j= 1, 2, ..., a určiť najlepšiu spomedzi stratégií A pri A v..., A t) Výber stratégie A jy prehrávač A musí očakávať, že hráč IN odpovie pomocou jednej zo stratégií IN., za čo je odmena pre hráča A minimálne (hráč IN snaží sa hráčovi „ublížiť“. A).
Označme a; najmenšie výhry hráča A keď zvolí stratégiu L; pre všetky možné hráčske stratégie IN(najmenšie číslo v i-tý riadok platobná matica), t.j.
Medzi všetkými číslami a (r = 1,2,..., T) Vyberme najväčšie: . Zavolajme a nižšia cena hry, alebo maximálne výhry (maximum). Toto zaručená výhra pre hráča A pre akúkoľvek stratégiu hráča B. teda
(12.2)
Stratégia zodpovedajúca maximínu sa nazýva stratégia maximin. Hráč IN záujem o zníženie výhier hráča A; výber stratégie IN., berie do úvahy maximálny možný zisk pre A. Označme
Medzi všetkými číslami β. vyberme si toho najmenšieho,
a zavolajte β najvyššia cena hry, alebo minimax výhra (minimax). Toto garantovaná strata pre hráča B. teda
(12.4)
Stratégia zodpovedajúca minimaxu sa nazýva minimax stratégiu.
Princíp, ktorý diktuje hráčom, aby si zvolili „najopatrnejšie“ stratégie minimaxu a maxima, sa nazýva princíp minimax. Tento princíp vyplýva z rozumného predpokladu, že každý hráč sa snaží dosiahnuť cieľ opačný ako jeho súper. Stanovme spodnú a hornú cenu hry a zodpovedajúce stratégie v úlohe 12.1. Zvážte platobnú maticu
od problému 12.1. Pri výbere stratégie L, (prvý riadok matice) minimálne výhry sa rovná a, =min(-l; 1) = -1 a zodpovedá stratégii β1 hráča IN. Pri výbere stratégie L 2 (druhý riadok matice) je minimálna výhra A 2 = min(l; -1) = -1, dosiahne sa stratégiou IN.,.
Zaručenie maximálnej výhry pre akúkoľvek hráčsku stratégiu IN, t.j. nižšia cena hry a = max(a, a2) = = max(-l; -1) = -1, hráč A môže zvoliť akúkoľvek stratégiu: Aj alebo A 2, t.j. niektorá z jeho stratégií je maximálna.
Výber stratégie B, (stĺpec 1), hráča IN chápe, že hráč A bude reagovať stratégiou A 2, aby ste maximalizovali svoje výhry (prehra IN). Preto je maximálna strata hráča IN keď zvolí stratégiu B, rovná sa β, = kontrola (-1; 1) = 1.
Podobne aj maximálna strata hráča B (výhra A) keď si zvolí stratégiu B2 (stĺpec 2) sa rovná β2 = max(l; -1) = 1.
Teda pre akúkoľvek hráčsku stratégiu A garantovaná minimálna strata hráča B sa rovná β = = πιίη(β1, β2) = min(l; 1) = 1 - horná cena hry.
Akákoľvek stratégia hráča B je minimax. Po pridaní tabuľky 12,1 čiara β; a stĺpec a;, dostaneme tabuľku. 12.2. Na priesečníku doplnkových riadkov a stĺpcov si zapíšeme hornú a dolnú cenu hier.
Tabuľka 12.2
Vo vyššie uvedenom probléme 12.1 sú horné a dolné ceny hry odlišné: a F β.
Ak sa horná a dolná cena hry zhodujú, potom všeobecný význam horná a dolná cena hry α = β = υ sa nazýva čistá cena hry, alebo za cenu hry. Minimax stratégie zodpovedajúce cene hry sú optimálne stratégie, a ich totalita - optimálne riešenie, alebo rozhodnutie hry. V tomto prípade prehrávač A dostane garantované maximum (nezávisle od správania hráča) IN) odmena je υ a hráč IN dosiahne minimálnu garantovanú (bez ohľadu na správanie hráča A) stratu υ. Hovorí sa, že riešenie hry má stabilita, tie. ak sa jeden z hráčov drží svojho optimálna stratégia, potom nemôže byť pre druhého výhodné odchýliť sa od jeho optimálnej stratégie.
Pár čistých stratégií A. a V. dáva optimálne riešenie hry práve vtedy, ak jej zodpovedajúci prvok y je zároveň najväčší v stĺpci a najmenší v riadku. Táto situácia, ak existuje, sa nazýva sedlový bod(podobne ako povrch sedla, ktorý sa jedným smerom ohýba hore a druhým smerom dole).
Označme A* A IN*– dvojica čistých stratégií, ktoré dosahujú riešenie hry v probléme sedlového bodu. Predstavme si výplatnú funkciu prvého hráča pre každú dvojicu stratégií: P(A:, IN-) = a y. Potom z podmienky optimality v sedlovom bode platí dvojitá nerovnosť: P(Aj, B*)<Р(А*, В*)<Р(А", В ), čo je spravodlivé pre všetkých i = 1, 2, ..., m;j = 1, 2, ..., P. Naozaj, výber stratégie A* prvý hráč s optimálnou stratégiou IN" druhý hráč maximalizuje minimálnu možnú výplatu: P(A*, B")> P(A G IN"), a výber stratégie B" druhý hráč s optimálnou stratégiou prvého minimalizuje maximálnu stratu: P(D, IN*)<Р(А", В).
12.2. Určte spodnú a hornú cenu hry danú platobnou maticou
Má hra sedlovú pointu?
Tabuľka 12. 3
Riešenie. Je vhodné vykonávať všetky výpočty v tabuľke, ktorá okrem matice R, je zadaný stĺpec a; a reťazec)
