Princípy riešenia maticových antagonistických hier. Maticové hry: príklady riešenia problémov

Účel služby. Pomocou online služby môžete:

• určiť cenu maticovej hry (dolná a horná hranica), skontrolovať prítomnosť sedlového bodu, nájsť riešenie zmiešanej stratégie, nájsť minimax stratégiu hráčov;
• zapísať matematický model dvojice úloh duálneho lineárneho programovania, vyriešiť maticovú hru metódami: minimax, simplexová metóda, grafická (geometrická) metóda, Brownova metóda.

Inštrukcie. Vyberte rozmer matice a kliknite na Ďalej. V novom dialógovom okne vyberte metódu riešenia maticovej hry. Príklad vyplnenia. Výsledky výpočtu sú prezentované v správe vo formáte Word.

Hra je matematický model reálnej konfliktnej situácie. Konfliktná situácia medzi dvoma hráčmi sa nazýva štvorhra. Je vhodné študovať párovú hru s nulovým súčtom, ak je opísaná vo forme matice. Táto hra sa volá matice; matica zložená z čísel a ij sa nazýva platba. V tabuľke sú uvedené možnosti riešenia hry špecifikovanej platobnou maticou A.

Popis algoritmu:

1. Na základe analýzy platobnej matice je potrebné určiť, či v nej dominujú stratégie a eliminovať ich.
2. Nájdite hornú a dolnú cenu hry a určte, či má táto hra sedlový bod (nižšia cena hry sa musí rovnať hornej cene hry).
3. Ak sedlový bod existuje, tak optimálne stratégie hráčov, ktoré sú riešením hry, budú ich čisté stratégie zodpovedajúce sedlovému bodu. Cena hry sa rovná hornej a dolnej cene hry, ktoré sa navzájom rovnajú.
4. Ak hra nemá sedlovú pointu, potom riešenie hry treba hľadať v zmiešaných stratégiách. Na určenie optimálnych zmiešaných stratégií v hrách m × n by sme mali použiť simplexnú metódu, ktorá najskôr preformulovala problém hry na problém lineárneho programovania.

Predstavme si algoritmus na grafické riešenie maticovej hry.

Obrázok - Schéma riešenia maticovej hry.

Metódy riešenia maticových hier v zmiešaných stratégiách

Ak teda neexistuje sedlový bod, hra sa rieši pomocou zmiešaných stratégií a rieši sa pomocou nasledujúcich metód:

1. Riešenie hry cez sústavu rovníc.
   Ak je daná štvorcová matica nxn (n=m), potom vektor pravdepodobnosti možno nájsť riešením sústavy rovníc. Táto metóda sa nepoužíva vždy a je použiteľná iba v určitých prípadoch (ak je matica 2x2, potom sa takmer vždy dosiahne riešenie hry). Ak riešenie produkuje záporné pravdepodobnosti, potom sa tento systém rieši simplexnou metódou.
2. Riešenie hry graficky.
   V prípadoch, kde n=2 alebo m=2, je možné maticovú hru vyriešiť graficky.
3. Riešenie maticovej hry simplexovou metódou.
   V tomto prípade sa maticová hra znižuje na

Prístup k riešeniu maticových hier možno zovšeobecniť na prípad hier s nulovým súčtom, v ktorých je výplata hráčov špecifikovaná ako spojitá funkcia (nekonečná hra s nulovým súčtom).

Táto hra je reprezentovaná ako hra pre dvoch hráčov, v ktorej si hráč 1 vyberie číslo X od mnohých X, hráč 2 si vyberie číslo y z množiny 7 a potom získajú výhry hráči 1 a 2 U(x, y) a -U(x, y). Výber určitého čísla hráčom znamená uplatnenie jeho čistej stratégie zodpovedajúcej tomuto číslu.

Analogicky s maticovými hrami možno nazvať čistú nižšiu cenu hry v ( = max min U(x, y), a čistá horná cena hry -v 2 =

min max U(x, y). Potom analogicky môžeme predpokladať, že ak pre niektoré

pri *

alebo nekonečná antagonistická hra veľkosti V A v 2 existujú a sú si navzájom rovné („i =v 2 =v), potom má takáto hra riešenie v čistých stratégiách, t.j. Optimálna stratégia hráča 1 je vybrať si číslo x° e X, a hráč 2 - čísla y 0 e 7, pre ktoré Shchh ( y 0) -v.

V tomto prípade v sa nazýva čistá cena hry a (x°, y 0) je sedlový bod nekonečnej hry s nulovým súčtom.

Pre maticové hry veľkosti v x A v 2 vždy existujú, ale v nekonečných antagonistických hrách nemusia existovať, t.j. nekonečná hra s nulovým súčtom nie je vždy riešiteľná.

Pri formalizácii reálnej situácie vo forme nekonečnej antagonistickej hry sa zvyčajne vyberie jeden strategický interval - jediný interval, z ktorého si hráči môžu vybrať. (X -číslo (stratégia) zvolená hráčom 1; -

číslo (stratégia) zvolená hráčom 2). Technicky to zjednodušuje riešenie, keďže jednoduchou transformáciou je možné ľubovoľný interval previesť na jednotkový interval a naopak. Táto hra sa volá antagonistická hra na jednotkovom štvorci.

Povedzme napríklad, že hráč 1 si vyberie číslo X od mnohých X=, hráč 2 si vyberie číslo y zo sady Y=. Potom hráč 2 zaplatí hráčovi 1 sumu Shx, y) -2x 2 -y 2. Keďže hráč 2 sa snaží minimalizovať platby hráča 1, určí min ( 2x 2 - y 2) = 2x 2- 1, t.j. v tomto prípade = 1. Hráč 1 sa snaží vytvoriť mtag

Simulujte svoju platbu, preto určuje max. min pšt, y)1 =

xGX a napr

- max (2x 2 - 1) = 2- 1 = 1, čo sa dosiahne, keď X = 1.

Teda nižšia čistá cena hry v x - 1. Vrchné čistenie

cena hryv 2 =min - min (2 - y2) = 2 - 1 = 1, t.j. v tomto

>naprheh u ey

hra vl =v2 =l. Preto čistá cena hry v= 1 a sedlový bod (x° = 1; y° = 1).

Predpokladajme to teraz Chi Y- otvorené intervaly, t.j. hráč 1 volí xeA"=(0; 1), hráč 2 volí ue 7= (0; 1). V tomto prípade X, dostatočne blízko k 1, hráč 1 si bude istý, že dostane odmenu nie menšiu ako číslo blízke "=1; ak zvolíte y blízko 1, hráč 2 nedovolí, aby odmena hráča 1 výrazne prevýšila čisté náklady na hru v= 1.

Stupeň blízkosti k cene hry možno charakterizovať číslom?>0. Preto v popisovanej hre môžeme hovoriť o optimálnosti čistých stratégií x°= 1, 0 = 1 hráči 1 a 2 až do ľubovoľného počtu?>0. Bodka (X", y E), kde x e e X, y (. eY, v nekonečnej hre s nulovým súčtom sa nazýva z-rovnovážny bod (s.-sedlový bod), ak pre nejaké stratégie xTiger 1, ue Tiger 2 platí nerovnosť pšt, u.) - ? Ш x r, у (.) U(x t., у) + ?. V tomto prípade stratégie x k. a u. sa volajú s,-optimálnymi stratégiami. Sú tieto stratégie optimálne? v tom zmysle, že ak odchýlka od optimálnej stratégie nemôže priniesť hráčovi žiaden úžitok, potom jej odchýlka od c-optimálnej stratégie môže zvýšiť jeho výplatu najviac o e.

Ak zver nemá sedlový bod (c-seddle point), t.j. riešenia v čistých stratégiách, potom možno optimálne stratégie hľadať medzi zmiešanými stratégiami, ktoré sa využívajú ako funkcie rozdelenia pravdepodobnosti hráčov využívajúcich čisté stratégie.

Nechaj F(x) je funkcia rozdelenia pravdepodobnosti použitia čistých stratégií hráčom 1. Ak je číslo E čistou stratégiou hráča 1, potom F(x) = P(q kde P(q -X)- pravdepodobnosť, že náhodne zvolená čistá stratégia E neprekročí X. Funkcia rozdelenia pravdepodobnosti pri použití čistých stratégií r| sa uvažuje podobným spôsobom. hráč 2: Q(y) = P(g.

Funkcie F(x) A Q(y) sa volajú zmiešané stratégie hráči 1 a 2. Ak Fx) A Q(y) sú diferencovateľné, potom existujú ich deriváty označené resp f(x) A q(y)(funkcie hustoty rozdelenia).

Vo všeobecnosti diferenciál distribučnej funkcie dF(x) vyjadruje pravdepodobnosť, že stratégia s, je medzi tým x E, Podobne pre hráča 2: dQ(y) znamená pravdepodobnosť, že jeho stratégia p je v intervale y g| y+dy. Potom bude platba hráča 1 Shx, y) dF(x), a platba hráča 2 je Shx, y) dQ(y).

Priemerná odmena hráča 1 vzhľadom na to, že hráč 2 používa svoju čistú stratégiu y, možno získať integráciou platieb cez všetky možné hodnoty X, tie. v jednotkovom intervale:

Priemerná odmena hráča 1 za predpokladu, že obaja hráči používajú svoje zmiešané stratégie F(x) A Q(y), budú rovné

Analogicky s maticovými hrami sa určujú optimálne zmiešané stratégie hráčov a cena hry: ak je pár zmiešaných stratégií F*(x) A Q*(y) pre hráčov 1 a 2 sú optimálne, potom pre akékoľvek zmiešané stratégie F(x) A Q(y) platia nasledujúce vzťahy:

Ak sa hráč 1 odchýli od svojej stratégie F*(x), potom sa jeho priemerná odmena nemôže zvýšiť, ale môže sa znížiť v dôsledku racionálnych krokov hráča 2. Ak hráč 2 ustúpi od svojej zmiešanej stratégie Q*(y), potom sa priemerná odmena hráča 1 môže zvýšiť, ale nie znížiť, vďaka rozumnejším činnostiam hráča 1. Priemerná odmena E(F*, Q*), dostane hráč 1, keď hráči aplikujú optimálne zmiešané stratégie, zodpovedá cene hry.

Potom možno definovať minimálnu cenu nekonečnej hry s nulovým súčtom vyriešenej v zmiešaných stratégiách ako v x= kontrola

min E(FQ), a najvyššia cena hry je ako v 2 = min max E(F, Q).

Q Q f

Ak takéto zmiešané stratégie existujú F* (x) A Q*(y) pre hráčov 1 a 2, pre ktorých sa spodná a horná cena hry zhoduje F*(x) A Q*(y) Optimálne zmiešané stratégie zodpovedajúcich hráčov je prirodzené nazývať a v = v x = v 2- za cenu hry.

Na rozdiel od maticových hier neexistuje riešenie nekonečnej hry s nulovým súčtom pre každú funkciu Psst, uh). Ale veta bola dokázaná, že každá nekonečná hra s nulovým súčtom s plynulou výplatnou funkciou Psst, uh) na jednotkovej štvorci má riešenie (hráči majú optimálne zmiešané stratégie), aj keď neexistujú žiadne všeobecné metódy na riešenie nekonečných hier s nulovým súčtom, vrátane kontinuálnych hier. Avšak antagonistické nekonečné hry s konvexnými a konkávnymi spojitými výplatnými funkciami (nazývajú sa resp konvexné A konkávne hry).

Uvažujme o riešení hier s konvexnou výplatnou funkciou. Riešenie hier s konkávnou výplatnou funkciou je symetrické.

Konvexné funkcia/premenná X v intervale ( A; b) je funkcia, pre ktorú platí nerovnosť

Kde Xx A x 2 -ľubovoľné dva body z intervalu (a; b);

X.1, A.2 > 0 a +X.2 = 1.

Ak pre / h * 0 D 2 * 0, vždy platí prísna nerovnosť

potom sa zavolá funkcia/ prísne konvexné na (a; b).

Geometricky konvexná funkcia znázorňuje oblúk, ktorého graf sa nachádza pod tetivou, ktorá ho pretne. Analyticky konvexnosť dvakrát diferencovateľnej funkcie zodpovedá nezápornosti (a v prípade striktnej konvexity kladnosti) jej druhej derivácie.

Pre konkávne funkcie sú vlastnosti opačné, pre ne nerovnosť /(/4X1 +A.2X2) > Kf(xi) +)-ak(x 2) (> s prísnou konkávnosťou) a druhá derivácia / "(x)

Je dokázané, že spojitá a striktne konvexná funkcia na uzavretom intervale nadobúda minimálnu hodnotu iba v jednom bode intervalu. Ak pšt, y) je nepretržitá funkcia odmien hráča 1 na jednotkovom poli a prísne konvexné pozdĺž pri pre ľubovoľné x potom existuje jedinečná optimálna čistá stratégia y=y° e pre hráča 2 je cena hry určená vzorcom

a význam y 0 je definovaná ako riešenie nasledujúcej rovnice:

Ak funkcia pšt, y) nie je striktne konvexné v y, potom hráč 2 nebude mať jedinú optimálnu čistú stratégiu.

Symetrická vlastnosť platí aj pre striktne konkávne funkcie. Ak funkcia pšt, y) je spojité v oboch argumentoch a striktne konkávne v x pre ľubovoľné y, potom má hráč 1 jedinečnú optimálnu stratégiu.

Cena hry je určená vzorcom

a čistá optimálna stratégia x 0 hráča 1 je určená z rovnice

Na základe týchto vlastností nekonečných hier s nulovým súčtom s konvexnými alebo konkávnymi výplatnými funkciami je skonštruovaná všeobecná schéma riešenia takýchto hier na jednotkovom štvorci (хе, уе). Túto schému uvádzame iba pre konvexné hry, pretože pre konkávne hry je symetrická.

1. Skontrolujte funkciu pšt, y) pre konvexnosť v y (druhá parciálna derivácia musí byť väčšia alebo rovná 0).

2. Určte y 0 zo vzťahu v- min max Psst, uh) ako význam

y, pri ktorej sa dosiahne minimax.

3. Nájdite riešenie rovnice v = U(x, y 0) a vytvorte dvojice jeho riešení X A x 2, pre ktoré

4. Nájdite parameter A z rov.

Parameter A určuje optimálnu stratégiu hráča 1 a má význam pravdepodobnosti jeho voľby jeho čistej stratégie x x. Hodnota 1 - a znamená pravdepodobnosť, že hráč 1 zvolí svoju čistú stratégiu x 2.

Ukážme si na príklade použitie tejto schémy na riešenie hry tohto typu. Nech je výplatná funkcia v nekonečnej hre s nulovým súčtom uvedená na jednotkovej štvorci a rovná sa Shchh, y) = =(x - y) 2 = x 2 - 2 xy ch-y 2.

1. Táto funkcia je nepretržitá X A y, a preto má táto hra riešenie. Funkcia Psst, uh) pozdĺž prísne konvexné y, pretože

Preto má hráč 2 jedinú čisto optimálnu stratégiu 0.

2. Máme v= min. max (x - y) 2. Na určenie max (x 2 - 2xy Ch-y 2)

Nájdime postupne prvú a druhú parciálnu deriváciu platobnej funkcie vzhľadom na x:

Takže funkcia U má minimum pre ľubovoľné y v x=y. To znamená, že ako xy - rastie a jeho maximum by malo byť dosiahnuté v jednom z extrémnych bodov x = 0 alebo x = 1. Poďme určiť hodnoty funkcie U v týchto bodoch:

Potom skontrolujte (x - y) 2 = max (y 2; 1 - 2y + y 2). Porovnanie "interného"

maxima v zložených zátvorkách, je to dobre vidieť o 2 > 1 - - 2y+y 2, Ak y >*/ 2 a y 2 1 - 2 y+y 2, Ak y "/ 2. Toto je jasnejšie znázornené v grafe (obr. 2.5).

Ryža. 2.5. Interné maximá platobnej funkcie U(x, y) = (x- pri) 2

Preto výraz (x - y) 2 dosiahne svoje maximum pri x=0, ak y > 7 2 a pri x= 1 ak na U 2:

teda v= min (min y2; min (1 - y)2). Každý z

ranné minimá dosahujú o hod y=*/ 2 a nadobúda hodnotu Y 4. Cena hry r = Y 4 a optimálna stratégia hráča 2:

3. Určte optimálnu stratégiu hráča 1 z rovnice U(x, y 0)= v, tie. pre túto hru (x - Y 2) 2 = Y 4. Riešením tejto rovnice SÚ X| = 0, x 2 = 1.

Podmienky sú pre nich splnené

4. Určme parameter a, t.j. pravdepodobnosť, že hráč 1 použije svoju čistú stratégiu X] = 0. Vytvorme rovnicu a-1 + (1 - a) (-1) = 0, z ktorej a = Y 2. Optimálnou stratégiou hráča 1 je teda vybrať si svoje čisté stratégie 0 a 1 s pravdepodobnosťou 1 / 2 každý. Problém je vyriešený.

Najjednoduchším prípadom, ktorý je podrobne rozpracovaný v teórii hier, je hra párov s konečným nulovým súčtom (antagonická hra dvoch osôb alebo dvoch koalícií). Uvažujme hru G, v ktorej sa zúčastňujú dvaja hráči A a B, ktorí majú protichodné záujmy: zisk jedného sa rovná strate druhého. Keďže výplata hráča A sa rovná výplate hráča B s opačným znamienkom, môže nás zaujímať iba výplata hráča a. Prirodzene, A chce maximalizovať a B chce minimalizovať a.

Pre jednoduchosť sa mentálne stotožnme s jedným z hráčov (nech je to A) a nazvime ho „my“ a hráča B „súperom“ (samozrejme, z toho nevyplývajú žiadne skutočné výhody pre A). Majme možné stratégie a protivník - možné stratégie (takejto hre sa hovorí hra). Označme našu výhru, ak my používame stratégiu a súper používa stratégiu

Tabuľka 26.1

Predpokladajme, že pre každý pár stratégií je nám známy výnos (alebo priemerný výnos) a. Potom je v princípe možné zostrojiť obdĺžnikovú tabuľku (maticu), ktorá uvádza stratégie hráčov a zodpovedajúce výplaty (pozri tabuľku 26.1).

Ak je takáto tabuľka zostavená, potom hovoria, že hra G bola zredukovaná na maticovú formu (doviesť hru do takejto formy už samo o sebe môže byť náročná úloha a niekedy takmer nemožná, kvôli obrovskej rozmanitosti stratégií ). Všimnite si, že ak je hra zredukovaná na maticovú formu, potom sa hra s viacerými ťahmi v skutočnosti zredukuje na hru s jedným ťahom – hráč musí urobiť iba jeden ťah: zvoliť si stratégiu. Hernú maticu stručne označíme

Pozrime sa na príklad hry G (4X5) v maticovej forme. Máme k dispozícii štyri stratégie (na výber), kým nepriateľ má päť stratégií. Matica hry je uvedená v tabuľke 26.2

Zamyslime sa nad tým, akú stratégiu by sme mali (hráč A) použiť? V Matrixe 26.2 je lákavá odmena „10“; sme v pokušení zvoliť si stratégiu, ktorou túto „lahôdku“ dostaneme.

Ale počkajte: ani nepriateľ nie je blázon! Ak si zvolíme stratégiu, on si napriek nám vyberie stratégiu a my dostaneme nejakú žalostnú odmenu „1“. Nie, nemôžete si zvoliť stratégiu! Ako byť? Je zrejmé, že na základe princípu opatrnosti (a to je základný princíp teórie hier) si musíme zvoliť stratégiu, pri ktorej je náš minimálny zisk maximálny.

Tabuľka 26.2

Toto je takzvaný „princíp mini-maxu“: konajte tak, aby ste pri najhoršom správaní súpera pre vás získali maximálnu výhru.

Prepíšme tabuľku 26.2 a do pravého doplnkového stĺpca zapíšme minimálnu výhernú hodnotu v každom riadku (minimum riadku); označme ho pre riadok a (pozri tabuľku 26.3).

Tabuľka 26.3

Zo všetkých hodnôt (pravý stĺpec) je zvýraznená najväčšia (3). Stratégia tomu zodpovedá. Výberom tejto stratégie si môžeme byť v každom prípade istí, že (za akékoľvek správanie nepriateľa) vyhráme nie menej ako 3. Táto hodnota je naša zaručená výhra; Keď sa budeme správať opatrne, nemôžeme dostať menej ako toto, možno dostaneme viac).

Táto výhra sa nazýva nižšia cena hry (alebo „maximin“ - maximum minimálnych výhier). Budeme ho označovať ako a. V našom prípade

Teraz sa pozrime na nepriateľov pohľad a dôvod. Nie je to nejaký pešiak, ale je tiež šikovný! Pri výbere stratégie by chcel dať menej, no musí rátať s naším pre neho najhorším správaním. Ak zvolí stratégiu, odpovieme mu a dá 10; ak si vyberie, my mu odpovieme a on dá, atď.. Do tabuľky 26.3 pridáme dodatočný spodný riadok a zapíšeme do nej maximá stĺpcov.Je zrejmé, že opatrný protivník by si mal zvoliť stratégiu, v ktorej je táto hodnota minimálne (zodpovedajúca hodnota 5 je zvýraznená v tabuľke 26.3) . Táto hodnota P je hodnota zisku, viac ako nám rozumný súper určite nedá. Nazýva sa horná cena hry (alebo „mi-nimax“ - minimum maximálnej výhry). V našom príklade a je dosiahnuté pomocou stratégie nepriateľa

Na základe zásady opatrnosti (pravidlo zaistenia „vždy rátajte s najhorším!“) teda musíme zvoliť stratégiu A a nepriateľa – stratégiu Takéto stratégie sa nazývajú „minimax“ (podľa princípu minimax). Pokiaľ sa obe strany v našom príklade budú držať svojich minimax stratégií, prínos bude

Teraz si na chvíľu predstavme, že sme sa dozvedeli, že nepriateľ sleduje stratégiu. Poď, potrestáme ho za to a zvolíme stratégiu, dostaneme 5, a to nie je také zlé. Ale nepriateľ tiež nie je zlyhanie; dajte mu vedieť, že naša stratégia je , bude sa tiež ponáhľať s výberom, zníži naše výhry na 2 atď. (partneri sa „nahnali so stratégiami“). Stručne povedané, stratégie minimaxu v našom príklade sú nestabilné vzhľadom na informácie o správaní druhej strany; tieto stratégie nemajú vlastnosť rovnováhy.

Je to tak vždy? Nie vždy. Zvážte príklad s maticou uvedenou v tabuľke 26.4.

V tomto príklade sa spodná cena hry rovná hornej cene: . Čo z toho vyplýva? Stratégie minimax hráčov A a B budú stabilné. Pokiaľ ich obaja hráči dodržiavajú, výplata je 6. Pozrime sa, čo sa stane, ak (A) zistíme, že súper (B) dodržiava stratégiu B?

Tabuľka 26.4

Ale nezmení sa absolútne nič, pretože akákoľvek odchýlka od stratégie môže našu situáciu len zhoršiť. Rovnako informácie, ktoré dostane protivník, ho nedonútia odchýliť sa od svojej stratégie Dvojica stratégií má vlastnosť rovnováhy (vyvážená dvojica stratégií) a výplata (v našom prípade 6) dosiahnutá touto dvojicou stratégií sa nazýva „sedlový bod matrice“. Znakom prítomnosti sedlového bodu a vyváženej dvojice stratégií je rovnosť spodnej a hornej ceny hry; celková hodnota sa nazýva cena hry. Označíme to

Stratégie (v tomto prípade), ktorými sa tento zisk dosahuje, sa nazývajú optimálne čisté stratégie a ich súhrn sa nazýva riešenie hry. V tomto prípade o hre samotnej hovoria, že je riešená v čistých stratégiách. Obe strany A aj B môžu dostať svoje optimálne stratégie, v ktorých je ich pozícia najlepšia možná. A ak hráč A vyhrá 6 a hráč B prehrá, nuž, toto sú podmienky hry: sú výhodné pre A a nevýhodné pre B.

Čitateľ môže mať otázku: prečo sa optimálne stratégie nazývajú „čisté“? Keď sa pozrieme trochu dopredu, odpovieme na túto otázku: existujú „zmiešané“ stratégie, ktoré spočívajú v tom, že hráč nepoužíva iba jednu stratégiu, ale niekoľko, pričom ich náhodne prelína. Ak teda pripustíme okrem čistých aj zmiešané stratégie, každá konečná hra má riešenie – rovnovážny bod. Ale o tom je ešte potrebné diskutovať.

Prítomnosť sedlového bodu v hre nie je ani zďaleka pravidlom, ale skôr výnimkou. Väčšina hier nemá sedlový bod. Existuje však typ hry, ktorá má vždy sedlovú pointu, a preto je riešená čisto stratégiou. Ide o takzvané „hry s úplnými informáciami“. Hra s úplnými informáciami je hra, v ktorej každý hráč pri každom osobnom ťahu pozná celé pozadie svojho vývoja, t. j. výsledky všetkých predchádzajúcich ťahov, osobných aj náhodných. Príklady hier s úplnými informáciami zahŕňajú: dámu, šach, piškvorky atď.

V teórii hier je dokázané, že každá hra s kompletnými informáciami má sedlový bod, a preto je riešená čisto stratégiou. V každej hre s úplnými informáciami existuje pár optimálnych stratégií, ktoré poskytujú stabilnú výplatu rovnajúcu sa nákladom na hru a. Ak takáto hra pozostáva len z osobných ťahov, tak keď každý hráč použije svoju optimálnu stratégiu, mala by skončiť veľmi definitívnym spôsobom – výhrou rovnajúcou sa cene hry. To znamená, že ak je známe riešenie hry, samotná hra stráca zmysel!

Uveďme si základný príklad hry s úplnými informáciami: dvaja hráči striedavo umiestňujú nikláky na okrúhly stôl a náhodne si vyberajú polohu stredu mince (vzájomné prekrývanie mincí nie je povolené). Vyhráva ten, kto vloží posledný nikel (keď už nezostane miesto pre ostatných). Je ľahké vidieť, že výsledok tejto hry je v podstate vopred daný. Existuje určitá stratégia, ktorá zabezpečuje, že hráč, ktorý umiestni mincu ako prvý, vyhrá.

Totiž, najprv musí umiestniť nikel do stredu stola a potom reagovať na každý súperov ťah symetrickým ťahom. Je zrejmé, že bez ohľadu na to, ako sa nepriateľ správa, nemôže sa vyhnúť prehre. Situácia je úplne rovnaká so šachom a hrami vo všeobecnosti s úplnými informáciami: ktorákoľvek z nich, napísaná v maticovej forme, má sedlový bod, čo znamená, že riešenie je v čistých stratégiách, a preto má zmysel len dovtedy, kým toto riešenie nenájde. Povedzme, že šachová partia buď vždy skončí výhrou bieleho, alebo vždy výhrou čierneho, alebo vždy remízou, ale ešte nevieme čo presne (našťastie pre milovníkov šachu). Dodajme tiež: v dohľadnej dobe sa to pravdepodobne nedozvieme, pretože počet stratégií je taký obrovský, že je mimoriadne ťažké (ak nie nemožné) doviesť hru do matricovej podoby a nájsť v nej sedlový bod.

Teraz si položme otázku, čo robiť, ak hra nemá sedlovú pointu: No, ak je každý hráč nútený zvoliť si jednu jedinú čistú stratégiu, potom sa nedá nič robiť: musíme sa riadiť princípom minimaxu. Iná vec je, ak dokážete „zmiešať“ svoje stratégie, náhodne ich striedať s určitými pravdepodobnosťami. Použitie zmiešaných stratégií je myslené týmto spôsobom: hra sa mnohokrát opakuje; pred každou partiou hry, keď je hráč na osobnom ťahu, „zverí“ svoju voľbu náhode, „hádže žreb“ a zvolí stratégiu, ktorá prišla (už vieme, ako organizovať žreb z predchádzajúcej kapitoly ).

Zmiešané stratégie v teórii hier sú modelom premenlivej, flexibilnej taktiky, keď nikto z hráčov nevie, ako sa v danej hre zachová súper. Táto taktika (aj keď zvyčajne bez akéhokoľvek matematického opodstatnenia) sa často používa v kartových hrách. Zároveň podotýkame, že najlepší spôsob, ako skryť svoje správanie pred nepriateľom, je dať mu náhodný charakter, a teda vopred nevedieť, čo urobíte.

Poďme sa teda baviť o zmiešaných stratégiách. Budeme označovať zmiešané stratégie hráčov A a B, kde (tvorí celkom jednu) - pravdepodobnosť, že hráč A použije stratégie - pravdepodobnosť, že hráč B použije stratégie

V špeciálnom prípade, keď sa všetky pravdepodobnosti okrem jednej rovnajú nule a táto sa rovná jednej, sa zmiešaná stratégia zmení na čistú.

Existuje základný teorém teórie hier: každá konečná hra s nulovým súčtom pre dve osoby má aspoň jedno riešenie - pár optimálnych stratégií, všeobecne zmiešaných, a zodpovedajúcu cenu.

Dvojica optimálnych stratégií, ktoré tvoria riešenie hry, má nasledujúcu vlastnosť: ak jeden z hráčov dodrží svoju optimálnu stratégiu, potom nemôže byť pre druhého výhodné odchýliť sa od tej svojej. Táto dvojica stratégií tvorí určitú rovnovážnu pozíciu v hre: jeden hráč chce premeniť zisk na maximum, druhý na minimum, každý ťahá vlastným smerom a pri rozumnom správaní oboch rovnovážny a stabilný zisk. v sú založené. Ak je potom hra prospešná pre nás, ak - pre nepriateľa; keď je hra „férová“, rovnako výhodná pre oboch účastníkov.

Uvažujme príklad hry bez sedlového bodu a uveďme (bez dôkazu) jej riešenie. Hra je nasledovná: dvaja hráči A a B súčasne a bez slova ukážu jeden, dva alebo tri prsty. O výhre rozhoduje celkový počet prstov: ak je párny, vyhrá A a dostane od B sumu rovnajúcu sa tomuto číslu; ak je nepárne, potom naopak A zaplatí B sumu rovnajúcu sa tomuto číslu. Čo by mali hráči robiť?

Vytvorme hernú maticu. V jednej hre má každý hráč tri stratégie: ukázať jeden, dva alebo tri prsty. Matica 3x3 je uvedená v tabuľke 26.5; ďalší pravý stĺpec zobrazuje minimá riadkov a ďalší spodný riadok zobrazuje maximá stĺpcov.

Stratégii zodpovedá nižšia cena hry.To znamená, že pri rozumnom, opatrnom správaní garantujeme, že neprehráme viac ako 3. Malá útecha, ale stále lepšia ako povedzme výhra 5, nájdená v niektorých bunkách matice. Je to pre nás zlé, hráč L... Ale uspokojme sa: pozícia nepriateľa sa zdá byť ešte horšia: nižšia cena hry. rozumné správanie nám dá aspoň 4.

Problém rozhodovania, posudzovaný v rámci systémového prístupu, obsahuje tri hlavné zložky: rozlišuje systém, riadiaci subsystém a prostredie. Teraz prejdeme k štúdiu rozhodovacích problémov, pri ktorých je systém ovplyvňovaný nie jedným, ale viacerými riadiacimi subsystémami, z ktorých každý má svoje ciele a možnosti pôsobenia. Tento prístup k rozhodovaniu sa nazýva teoretický a matematické modely zodpovedajúcich interakcií hry. Vzhľadom na rozdiely v cieľoch riadiacich subsystémov, ako aj na určité obmedzenia možnosti výmeny informácií medzi nimi, sú tieto interakcie konfliktného charakteru. Preto je každá hra matematickým modelom konfliktu. Obmedzme sa na prípad, keď existujú dva riadiace podsystémy. Ak sú ciele systémov opačné, konflikt sa nazýva antagonistický a matematický model takéhoto konfliktu sa nazýva antagonistická hra..

V herno-teoretickej terminológii sa 1. riadiaci subsystém nazýva hráč 1, 2. riadiaci subsystém - hráč 2, súpravy

ich alternatívne akcie sa nazývajú sady stratégií títo hráči. Nechaj X- veľa stratégií pre hráča 1, Y- veľa stratégií

hráč 2. Stav systému je jednoznačne určený výberom kontrolných akcií podsystémami 1 a 2, teda výberom stratégií

X∈X A r∈Y. Nechaj F(X,r) - posúdenie užitočnosti pre hráča 1 tohto štátu

systém, do ktorého ide, keď si hráč zvolí 1 stratégiu X A

Stratégia hráča 2 pri. číslo F(X,r) sa nazýva vyhrať hráč 1 v situácii ( X,r) a funkciu F- výplatná funkcia hráča 1. Výhry hráča

1 je súčasne strata hráča 2, teda hodnota, ktorú chce prvý hráč zvýšiť a druhý - znížiť. Tak to je

prejav antagonistickej povahy konfliktu: záujmy hráčov sú úplne opačné (čo jeden vyhrá, druhý stratí).

Antagonistická hra je prirodzene definovaná systémom G=(X, Y, F).

Všimnite si, že formálne je hra s nulovým súčtom nastavená prakticky rovnakým spôsobom ako rozhodovacia úloha v podmienkach neistoty – ak

identifikovať riadiaci subsystém 2 s prostredím. Podstatný rozdiel medzi riadiacim subsystémom a prostredím je v tom

správanie prvého je účelové. Ak pri zostavovaní matematického modelu skutočného konfliktu máme dôvod (alebo zámer) považovať prostredie za nepriateľa, ktorého cieľom je priniesť

nám maximálne uškodí, potom môže byť takáto situácia prezentovaná formou antagonistickej hry. Inými slovami, hru s nulovým súčtom možno interpretovať ako extrémny prípad ZPR v podmienkach neistoty,

charakterizované tým, že sa k životnému prostrediu správa ako k protivníkovi s cieľom. Zároveň musíme obmedziť typy hypotéz o správaní okolia.

Najviac opodstatnená je tu hypotéza extrémnej opatrnosti, kedy pri rozhodovaní počítame s tým, že pre nás okolie bude najhoršie.

Definícia. Ak X A Y sú konečné, potom sa antagonistická hra nazýva maticová hra. V maticovej hre to môžeme predpokladať X={1,…,n},

Y={1,…,m) a dať aij=F(i,j). Maticová hra je teda úplne určená maticou A=(aij), i=1,…,n, j=1,…,m.

Príklad 3.1. Hra na dva prsty.

Dvaja ľudia súčasne ukazujú jeden alebo dva prsty a volajú číslo 1 alebo 2, čo podľa hovorcu znamená číslo

prsty ukázané ostatným. Po ukázaní prstov a pomenovaní čísel sa výhry rozdelia podľa nasledujúcich pravidiel:

ak obaja uhádli alebo obaja neuhádli, koľko prstov ukázal ich súper, výhry všetkých sú nulové; ak uhádol iba jeden, potom súper zaplatí hádajúcemu sumu peňazí úmernú celkovému zobrazenému počtu

Toto je maticová hra s nulovým súčtom. Každý hráč má štyri stratégie: 1- ukáž 1 prst a zavolaj 1, 2- ukáž 1 prst a zavolaj 2, 3-

ukáž 2 prsty a zavolaj 1, 4 - ukáž 2 prsty a zavol 2. Potom výplatná matica A=(aij), i= 1,…, 4j= 1,…, 4 je definovaný takto:

a12= 2, a21 = – 2, a13=a42=–3, a24=a31= 3, a34 = – 4, a43= 4,aij= 0 v ostatných prípadoch.

Príklad 3.2. Hra typu diskrétneho súboja.

Problémy typu duel popisujú napríklad súboj dvoch hráčov,

každý z nich chce vykonať nejakú jednorazovú akciu (uviesť dávku tovaru na trh, požiadať o nákup v aukcii) a zvolí si na to čas. Nechajte hráčov pohybovať sa smerom k sebe n kroky. Po každom vykonanom kroku sa hráč môže rozhodnúť strieľať alebo nestreliť na nepriateľa. Každá osoba môže mať iba jeden výstrel. Predpokladá sa, že pravdepodobnosť zasiahnutia nepriateľa, ak postúpite k n = 5 má tvar

Odoslanie dobrej práce do databázy znalostí je jednoduché. Použite nižšie uvedený formulár

Študenti, postgraduálni študenti, mladí vedci, ktorí pri štúdiu a práci využívajú vedomostnú základňu, vám budú veľmi vďační.

Úvod

1. Teoretická časť

1.3 Poradie hry 2x2

1.4 Algebraická metóda

1.5 Grafická metóda

1.6 Hry 2xn alebo mx2

1.7 Riešenie hier maticovou metódou

2. Praktická časť

2.2 Hry 2xn a mx2

2.3 Maticová metóda

2.4 Hnedá metóda

Analýza výsledkov

Úvod

Hra s nulovým súčtom je hra s nulovým súčtom. Hra s nulovým súčtom je nekooperatívna hra zahŕňajúca dvoch hráčov, ktorých výplaty sú opačné.

Formálne môže byť antagonistická hra reprezentovaná trojkou , kde X a Y sú množiny stratégií prvého a druhého hráča, F je výplatná funkcia prvého hráča, ktorá priraďuje každému páru stratégií (x, y), kde reálne číslo zodpovedajúce užitočnosti prvým hráčom pri realizácii danej situácie.

Keďže záujmy hráčov sú opačné, funkcia F zároveň predstavuje stratu druhého hráča.

Historicky sú hry s nulovým súčtom prvou triedou modelov matematickej teórie hier, pomocou ktorých boli hazardné hry opísané. Predpokladá sa, že tento predmet štúdia je miestom, kde teória hier dostala svoje meno. V súčasnosti sú antagonistické hry považované za súčasť širšej triedy nekooperatívnych hier.

1. Teoretická časť

1.1 Základné definície a ustanovenia hry

Hra sa vyznačuje systémom pravidiel, ktoré určujú počet účastníkov hry, ich možné akcie a rozdelenie výhier v závislosti od ich správania a výsledkov. Za hráča sa považuje jeden účastník alebo skupina účastníkov hry, ktorí majú nejaké spoločné záujmy, ktoré sa nezhodujú so záujmami iných skupín. Preto nie každý účastník je považovaný za hráča.

Pravidlá alebo podmienky hry určujú možné správanie, voľby a pohyby hráčov v ktorejkoľvek fáze vývoja hry. Vybrať si pre hráča znamená vybrať si jednu z možností jeho správania. Hráč potom robí tieto voľby pomocou ťahov. Urobiť ťah znamená v určitej fáze hry urobiť celý výber alebo jeho časť naraz, v závislosti od možností, ktoré poskytujú pravidlá hry. Každý hráč v určitej fáze hry vykoná ťah podľa vykonanej voľby. Druhý hráč, ktorý vie alebo nevie o voľbe prvého hráča, tiež urobí ťah. Každý hráč sa snaží brať do úvahy informácie o minulom vývoji hry, ak takúto možnosť pravidlá hry pripúšťajú.

Súbor pravidiel, ktoré hráčovi jasne naznačujú, akú voľbu musí urobiť pri každom ťahu v závislosti od situácie, ktorá v dôsledku hry nastane, sa nazýva stratégia hráča. Stratégia v teórii hier znamená pre hráča určitý ucelený akčný plán, ktorý ukazuje, ako by mal konať vo všetkých možných prípadoch vývoja hry. Stratégia znamená súhrn všetkých pokynov pre akýkoľvek stav informácií dostupných hráčovi v ktorejkoľvek fáze vývoja hry. Už z toho je jasné, že stratégie môžu byť dobré aj zlé, úspešné aj neúspešné atď.

Hra s nulovým súčtom bude vtedy, keď sa súčet výhier všetkých hráčov v každej z jej hier rovná nule, t.j. v hre s nulovým súčtom sa celkový kapitál všetkých hráčov nemení, ale je prerozdelený medzi hráčov. v závislosti od výsledných výsledkov. Mnohé ekonomické a vojenské situácie možno teda považovať za hry s nulovým súčtom.

Najmä hra s nulovým súčtom medzi dvoma hráčmi sa nazýva antagonistická, pretože ciele hráčov v nej sú priamo opačné: zisk jedného hráča nastáva iba na úkor straty druhého.

1.1.1 Definícia, príklady a riešenia maticových hier v čistých stratégiách

Maticovú hru pre dvoch hráčov s nulovým súčtom si možno predstaviť ako nasledujúcu abstraktnú hru pre dvoch hráčov.

Prvý hráč má t stratégií i =1, 2,…, t, druhý má n stratégií j = 1, 2,…, p. Každá dvojica stratégií (i, j) je spojená s číslom a ij , ktoré vyjadruje výhry prvého hráča v dôsledku druhého hráča, ak prvý hráč použije svoju i-tu stratégiu a druhý hráč použije svoju j-tu stratégiu.

Každý hráč urobí jeden ťah: prvý si zvolí svoju i-tu stratégiu (i = 1, 2,..., m), druhý zvolí j-tu stratégiu (j = 1, 2,..., n) , po ktorom prvý hráč získa výhru a ij na úkor druhého hráča (ak ij< 0, то это значит, что первый игрок платит второму сумму a ij). На этом игра заканчивается.

Každá stratégia hráča i = 1, 2,…, t; j = 1, 2,…, n sa často nazýva čistá stratégia.

Maticová hra pre dvoch hráčov s nulovým súčtom sa bude odteraz jednoducho nazývať maticová hra. Je zrejmé, že maticová hra patrí k antagonistickým hrám. Z jej definície vyplýva, že na definovanie maticovej hry stačí zadať maticu A = (a ij) v poradí výplat prvého hráča.

Ak vezmeme do úvahy výplatnú maticu

potom sa hranie každej hry maticovej hry s maticou A obmedzí na výber prvého hráča i-teho radu a druhého hráča j-tého stĺpca a prvého hráča, ktorý dostane (na úkor druhého hráča). ) výhry nachádzajúce sa v matici A na priesečníku i-tého riadku a j-tého stĺpca.

Na formalizáciu skutočnej konfliktnej situácie vo forme maticovej hry je potrebné identifikovať a prečíslovať čisté stratégie každého hráča a vytvoriť výplatnú maticu.

Ďalšou fázou je určenie optimálnych stratégií a výhier hráčov.

Hlavnou vecou pri štúdiu hier je koncept optimálnych stratégií hráčov. Tento koncept má intuitívne nasledujúci význam: stratégia hráča je optimálna, ak mu použitie tejto stratégie poskytuje najväčšiu zaručenú výhru pre všetky možné stratégie druhého hráča. Na základe týchto pozícií prvý hráč skúma maticu A svojich výplat pomocou vzorca (1.1) takto: pre každú hodnotu i (i = 1, 2,..., t) sa určí minimálna hodnota výplaty v závislosti od stratégie používané druhým hráčom

(i = 1, 2,..., m) (1,2)

t.j. určí sa minimálna odmena pre prvého hráča, za predpokladu, že uplatní svoju i -tu čistú stratégiu, potom sa z týchto minimálnych odmien nájde stratégia i = i 0, pre ktorú bude táto minimálna odmena maximálna, t.j.

Definícia. Číslo b, určené vzorcom (1.3), sa nazýva dolná čistá cena hry a ukazuje, akú minimálnu výhru si prvý hráč môže zaručiť tým, že použije svoje čisté stratégie na všetky možné akcie druhého hráča.

Druhý hráč by sa mal svojím optimálnym správaním snažiť, pokiaľ je to možné, prostredníctvom svojich stratégií minimalizovať výhry prvého hráča. Preto pre druhého hráča nájdeme

t.j. určí sa maximálna výhra prvého hráča, za predpokladu, že druhý hráč použije svoju j-tu čistú stratégiu, potom druhý hráč nájde svoju stratégiu j = j 1, podľa ktorej prvý hráč dostane minimálnu výplatu, t.j.

Definícia. Číslo b určené podľa vzorca (1.5) sa nazýva čistá horná cena hry a ukazuje, aké maximálne výhry si môže prvý hráč zaručiť prostredníctvom svojich stratégií. Inými slovami, použitím svojich čistých stratégií môže prvý hráč zabezpečiť výplatu minimálne b a druhý hráč môže použitím svojich čistých stratégií zabrániť prvému hráčovi vyhrať viac ako b.

Definícia. Ak sa v hre s maticou A spodná a horná čistá cena hry zhoduje, t. j. b = c, potom sa hovorí, že táto hra má sedlový bod v čistých stratégiách a čistú cenu hry:

n = b = v (1,6)

Sedlový bod je pár čistých stratégií () prvého a druhého hráča, pri ktorých sa dosiahne rovnosť

Pojem sedlového bodu má nasledovný význam: ak jeden z hráčov dodržiava stratégiu zodpovedajúcu sedlovému bodu, potom druhý hráč nemôže urobiť lepšie, ako dodržiavať stratégiu zodpovedajúcu sedlovému bodu. Vzhľadom na to, že najlepšie správanie hráča by nemalo viesť k zníženiu jeho výhier a najhoršie správanie môže viesť k zníženiu jeho výhier, možno tieto podmienky zapísať matematicky vo forme nasledujúcich vzťahov:

kde i, j sú ľubovoľné čisté stratégie prvého a druhého hráča; (i 0 , j 0) sú stratégie, ktoré tvoria sedlový bod. Nižšie ukážeme, že definícia sedlového bodu je ekvivalentná podmienkam (1.8).

Sedlový prvok je teda na základe (1.8) minimálny v i 0. riadku a maximálny v j 0. stĺpci matice A. Nájdenie sedlového bodu matice A je jednoduché: v matici A sa minimálny prvok postupne nachádza v každý riadok a skontrolujte, či je tento prvok v jeho stĺpci maximálny. Ak je taký, potom ide o sedlový prvok a jemu zodpovedajúca dvojica stratégií tvorí sedlový bod. Dvojica čistých stratégií (i 0 , j 0) prvého a druhého hráča, ktoré tvoria sedlový bod a sedlový prvok, sa nazýva riešenie hry.

Čisté stratégie i 0 a j 0 tvoriace sedlový bod sa nazývajú optimálne čisté stratégie prvého a druhého hráča.

Veta 1. Nech f (x, y) je reálna funkcia dvoch premenných x A a y B a existuje

potom b = c.

Dôkaz. Z definície minima a maxima vyplýva, že

Keďže na ľavej strane (1.11) je x ľubovoľné, potom

Na pravej strane nerovnosti (1.12) je teda y ľubovoľné

Q.E.D.

Najmä matica () je špeciálny prípad funkcie f (x, y), t.j. ak dáme x = i, y = j, = f (x, y), potom z vety 1 dostaneme, že dolná sieť cena nepresiahne hornú čistú cenu hry v maticovej hre.

Definícia. Nech f (x, y) je reálna funkcia dvoch premenných x A a y B. Bod (x 0, y 0) sa nazýva sedlový bod pre funkciu f (x, y), ak sú splnené nasledujúce nerovnosti:

f (x, y 0) f (x 0, y 0) f (x 0, y) (1,14)

pre ľubovoľné x A a y B.

1.2 Optimálne zmiešané stratégie a ich vlastnosti

Štúdium maticovej hry začína nájdením jej sedla v čistých stratégiách. Ak má maticová hra sedlový bod v čistých stratégiách, potom sa štúdium hry končí nájdením tohto bodu. Ak v maticovej hre nie je sedlový bod v čistých stratégiách, potom je možné nájsť dolnú a hornú čistú cenu tejto hry, čo naznačuje, že prvý hráč by nemal dúfať, že vyhrá viac, ako je horná cena hry, a môže buďte si istí, že dostanete výhru, nie menej nižšiu cenu hry. Takéto odporúčania týkajúce sa správania hráčov v maticovej hre bez sedlového bodu v čistých stratégiách nemôžu uspokojiť výskumníkov a odborníkov z praxe. Zlepšenie riešení maticových hier treba hľadať vo využívaní utajenia používania čistých stratégií a možnosti mnohonásobného opakovania hier formou hier. Hrá sa teda napríklad séria hier šach, dáma, futbal a hráči zakaždým aplikujú svoje stratégie tak, že súperi o ich obsahu nemajú ani potuchy, a takto v priemere dosiahnuť určité výhry hraním celej série hier. Tieto výhry sú v priemere vyššie ako spodná cena hry a nižšie ako horná cena hry. Čím je táto priemerná hodnota vyššia, tým lepšiu stratégiu hráč používa. Preto vznikla myšlienka aplikovať čisté stratégie náhodne, s určitou pravdepodobnosťou. To úplne zabezpečuje utajenie ich použitia. Každý hráč môže zmeniť pravdepodobnosti používania svojich čistých stratégií tak, aby maximalizoval svoj priemerný zisk a zároveň získal optimálne stratégie. Táto myšlienka viedla ku konceptu zmiešanej stratégie.

Definícia. Zmiešaná stratégia hráča predstavuje úplný súbor pravdepodobností použitia jeho čistých stratégií.

Ak má teda prvý hráč m čistých stratégií 1, 2, … i, … m, potom jeho zmiešaná stratégia x je množina čísel x = (x 1, x 2, ..., x i,…, x m ) vyhovujúcich vzťahy

x i 0 (i = 1, 2, ... , t), = 1. (1,15)

Podobne pre druhého hráča, ktorý má n čistých stratégií, je zmiešaná stratégia y množinou čísel y = (y 1, ..., y j, ... y n) spĺňajúcich vzťahy

y j 0 (j = 1, 2, ... , n), = 1. (1,16)

Keďže zakaždým, keď hráč použije jednu čistú stratégiu, vylučuje použitie inej, čisté stratégie sú nezlučiteľné udalosti. Navyše sú to jediné možné udalosti.

Je zrejmé, že čistá stratégia je špeciálnym prípadom zmiešanej stratégie. V skutočnosti, ak sa v zmiešanej stratégii použije akákoľvek i-tá čistá stratégia s pravdepodobnosťou jedna, potom sa nepoužijú všetky ostatné čisté stratégie. A táto i-tá čistá stratégia je špeciálnym prípadom zmiešanej stratégie. Aby sa zachovalo tajomstvo, každý hráč uplatňuje svoje vlastné stratégie bez ohľadu na voľby druhého hráča.

Definícia. Priemerná výplata prvého hráča v maticovej hre s maticou A je vyjadrená ako matematické očakávanie jeho výplat

E (A, x, y) = (1,20)

Je zrejmé, že priemerný zisk prvého hráča je funkciou dvoch súborov premenných x a y. Prvý hráč sa snaží zmenou svojich zmiešaných stratégií x maximalizovať svoj priemerný výnos E (A, x, y) a druhý hráč sa prostredníctvom svojich zmiešaných stratégií snaží dosiahnuť, aby E (A, x, y) bolo minimálne, t.j. Na vyriešenie hry je potrebné nájsť také x, y, pri ktorých sa dosiahne horná cena hry.

1.3 Hra o poriadok 22

Maticová hra poradia 22 je daná nasledujúcou výplatnou maticou pre prvého hráča:

Riešenie tejto hry by malo začať nájdením sedlového bodu v čistých stratégiách. Za týmto účelom nájdite minimálny prvok v prvom riadku a skontrolujte, či je v jeho stĺpci maximálny. Ak sa takýto prvok nenájde, druhý riadok sa skontroluje rovnakým spôsobom. Ak sa takýto prvok nachádza v druhom riadku, potom je to sedlo.

Nájdením sedlového prvku, ak existuje, sa ukončí proces hľadania jeho riešenia, keďže v tomto prípade bola nájdená cena hry — sedlový prvok a sedlový bod, teda dvojica čistých stratégií pre prvý resp. druhého hráča, čo predstavuje optimálne čisté stratégie. Ak v čistých stratégiách neexistuje sedlový bod, potom musíme nájsť sedlový bod v zmiešaných stratégiách, ktorý nevyhnutne existuje podľa hlavnej vety maticových hier.

Označme x = (x 1 , x 2), y = (y 1 , y 2) zmiešané stratégie prvého a druhého hráča. Pripomeňme, že x 1 znamená pravdepodobnosť, že prvý hráč použije svoju prvú stratégiu, a x 2 = 1 – x 1 je pravdepodobnosť, že použije druhú stratégiu. Podobne pre druhého hráča: 1 je pravdepodobnosť, že použije prvú stratégiu, 2 = 1 - 1 je pravdepodobnosť, že použije druhú stratégiu.

Podľa záveru vety, aby boli zmiešané stratégie x a y optimálne, je potrebné a postačujúce, aby pre nezáporné x 1, x 2, y 1, y 2 platili tieto vzťahy:

Teraz ukážme, že ak maticová hra nemá sedlový bod v čistých stratégiách, potom sa tieto nerovnosti musia zmeniť na rovnosti:

Naozaj. Nech hra nemá sedlový bod v čistých stratégiách, potom optimálne hodnoty zmiešaných stratégií uspokoja nerovnosti

0<<1, 0<< 1,

0< <1, 01. (1.25)

Predpokladajme, že obe nerovnosti z (1.22) sú prísne

potom podľa vety y 1 = y 2 = 0, čo je v rozpore s podmienkami (1.25).

Podobne je dokázané, že obe nerovnosti z (1,23) nemôžu byť striktné nerovnosti.

Predpokladajme teraz, že jedna z nerovností (1,22) môže byť prísna, napríklad prvá

To znamená, že podľa vety y 1 = 0, y 2 = 1. Následne z (1.23) dostaneme

Ak sú obe nerovnosti (1.24) prísne, potom podľa vety x 1 = x 2 = 0, čo je v rozpore s (1.25). Ak je 12 a 22, potom jedna z nerovností (1,27) je prísna a druhá je rovnosť. Navyše, rovnosť bude platiť pre väčší prvok 12 a 22, t.j. jedna nerovnosť z (1.27) musí byť prísna. Napríklad 12< а 22 . Тогда справедливо а 12 < v, а это равносильно тому, что первое неравенство из (1.24) строгое. Тогда согласно теореме должно х 1 = 0, что противоречит условию (1.25). Если а 12 = а 22 , то оба неравенства (1.27) превращаются в равенства и тогда можно положить х 1 = 0, что противоречит (1.25). Итак, предположение о том, что первое неравенство из (1.22) может быть строгим, не справедливо. Аналогично можно показать, что второе неравенство из (1.22) также не может быть строгим.

Ukazuje sa teda, že ak maticová hra nemá sedlový bod v čistých stratégiách, tak pre optimálne stratégie prvého hráča sa nerovnosti (1,22) zmenia na rovnosti. Podobné uvažovanie o nerovnostiach (1.23) povedie k tomu, že v tomto prípade musia byť nerovnosti (1.23) rovnosťami.

Ak teda maticová hra rádu 22 nemá sedlový bod, optimálne zmiešané stratégie hráčov a cenu hry možno určiť riešením sústavy rovníc (1.24). Zistilo sa tiež, že ak má v maticovej hre 2x2 jeden z hráčov optimálnu čistú stratégiu, potom aj druhý hráč má optimálnu čistú stratégiu.

Následne, ak maticová hra nemá sedlový bod v čistých stratégiách, potom musí mať riešenie v zmiešaných stratégiách, ktoré sú určené z rovníc (1.24). Riešenie systému (1.25)

1.4 Algebraická metóda

Existujú dva možné prípady riešenia problémov pomocou algebraickej metódy:

1. matrica má sedlový hrot;

2. matrica nemá sedlový hrot.

V prvom prípade je riešením dvojica stratégií, ktoré tvoria sedlovú pointu hry. Zoberme si druhý prípad. Riešenia tu treba hľadať v zmiešaných stratégiách:

Poďme nájsť stratégie a... Keď prvý hráč použije svoju optimálnu stratégiu, druhý hráč môže použiť napríklad dve takéto čisté stratégie

Navyše, vďaka vlastnosti, ak jeden z hráčov používa optimálnu zmiešanú stratégiu a druhý používa akúkoľvek čistú stratégiu zahrnutú v jeho optimálnej zmiešanej stratégii s pravdepodobnosťou nerovnajúcou sa nule, potom matematické očakávania výhry vždy zostávajú nezmenené a rovnaké. k cene hry, t.j.

Výhry v každom z týchto prípadov sa musia rovnať cene hry V. V tomto prípade platia nasledujúce vzťahy:

Pre optimálnu stratégiu druhého hráča je možné zostaviť systém rovníc podobný (2.5), (2.6):

Berúc do úvahy podmienky normalizácie:

Poďme riešiť rovnicu (1,37) - (1,41) spolu vzhľadom na neznáme, môžete vyriešiť nie všetky naraz, ale tri naraz: samostatne (1,36), (1,38), (1,40) a (1,37), ( 1,39), (1,41). Výsledkom riešenia je:

1.5 Grafická metóda

Približné riešenie hry 22 možno získať celkom jednoducho pomocou grafickej metódy. Jeho podstata je nasledovná:

Obrázok 1.1 - nájdenie úseku jednotkovej dĺžky

Vyberte časť jednotky dĺžky na osi x. Ľavý koniec bude zobrazovať prvú stratégiu prvého hráča a pravý koniec bude predstavovať druhú. Všetky medziľahlé body zodpovedajú zmiešaným stratégiám prvého hráča a dĺžka segmentu napravo od bodu sa rovná pravdepodobnosti použitia prvej stratégie a dĺžka segmentu naľavo je pravdepodobnosť použitia druhá stratégia prvým hráčom.

Sú nakreslené dve osi I-I a II-II. Výhry dáme na I-I, keď prvý hráč použije prvú stratégiu, na II-II, keď použije druhú stratégiu. Nech napríklad druhý hráč použije svoju prvú stratégiu, potom by mala byť hodnota vynesená na osi I-I a hodnota by mala byť vynesená na osi II-II.

Pre akúkoľvek zmiešanú stratégiu prvého hráča bude jeho výplata určená hodnotou segmentu. Línia I-I zodpovedá použitiu prvej stratégie druhým hráčom, budeme ju nazývať prvou stratégiou druhého hráča. Podobne môžete postaviť druhú stratégiu druhého hráča. Potom bude mať grafické zobrazenie hernej matice vo všeobecnosti nasledujúcu formu:

Obrázok 1.2 - zistenie ceny hry

Treba však poznamenať, že táto konštrukcia bola realizovaná pre prvého hráča. Tu sa dĺžka segmentu rovná cene hry V.

Línia 1N2 sa nazýva dolný výherný limit. Tu jasne vidíte, že bod N zodpovedá maximálnej výške garantovanej výhry prvého hráča.

Vo všeobecnosti možno z tohto obrázku určiť aj stratégiu druhého hráča, napríklad nasledujúcimi spôsobmi. Na osi I-I:

alebo na osi II-II

Stratégia druhého hráča sa však dá určiť podobne, ako sa to robí u prvého hráča, t.j. vytvoriť takýto graf.

Obrázok 1.3 - určenie stratégie druhého hráča

Tu je riadok 1N2 hornou hranicou straty. Bod N zodpovedá minimálnej možnej strate druhého hráča a určuje stratégiu.

V závislosti od konkrétnych hodnôt maticových koeficientov môžu mať grafy inú formu, napríklad:

Obrázok 1.4 - určuje optimálnu stratégiu prvého hráča

V takejto situácii je optimálna stratégia prvého hráča čistá:

1.6 Hry 2n alebo m2

V hrách poradia 2n má prvý hráč 2 čisté stratégie a druhý hráč má n čistých stratégií, t.j. Výplatná matica prvého hráča má tvar:

Ak má takáto hra sedlový bod, potom je ľahké ho nájsť a získať riešenie.

Predpokladajme, že hra má sedlové body. Potom je potrebné nájsť také zmiešané stratégie a podľa toho prvého a druhého hráča a cenu hry v, ktoré spĺňajú vzťahy:

Keďže hra nemá sedlový bod, nerovnosť (1,54) je nahradená nerovnosťami

Na riešenie systémov (1.56), (1.55), (1.53) je vhodné použiť grafickú metódu. Na tento účel zavedieme označenie pre ľavú stranu nerovnosti (1.53)

maticový matematický model hry

alebo položením z (1.55) a vykonaním jednoduchých transformácií dostaneme

kde je priemerná výplata prvého hráča za predpokladu, že používa svoju zmiešanú stratégiu, a druhého jeho j-tej čistej stratégie.

Podľa výrazu každá hodnota j=1, 2, …, n zodpovedá priamke v pravouhlom súradnicovom systéme.

Cieľom druhého hráča je minimalizovať výhru prvého hráča výberom jeho stratégií. Preto počítame

kde je spodná hranica množiny obmedzení. Na obrázku 1.6 je graf funkcie znázornený hrubou čiarou.

Uverejnené na http://www.allbest.ru/

Obrázok 1.6 - graf funkcie

Cieľom prvého hráča je maximalizovať svoju výhru prostredníctvom výberu, t.j. vypočítať

Na obrázku 1.6 bodka znamená maximálnu hodnotu, ktorá sa získa pri. Cena hry je preto, lebo:

Takto sa graficky určí optimálna zmiešaná stratégia prvého hráča a dvojica čistých stratégií druhého hráča, ktoré v priesečníku tvoria bod Obrázok 1.6 znázorňuje 2. a 3. stratégiu druhého hráča. Pre takéto stratégie sa nerovnosti (1,53) zmenia na rovnosť. Na obrázku 1.6 sú to stratégie j=2, j=3.

Teraz môžeme vyriešiť systém rovníc

a presne určiť hodnoty a (graficky sú určené približne). Potom zadaním všetkých hodnôt pre tie j, pre ktoré netvoria bod, vyriešte systém rovníc (1.56) Pre príklad zobrazený na obrázku 1.6 je to nasledujúci systém:

a zvyšok Tento systém je možné vyriešiť šikmým Ak pre nejaké j=j 0 stratégie druhého hráča tvoria bod M 0 a potom maximálna hodnota dolnej hranice množín obmedzení je znázornená úsečkou rovnobežnou s os V tomto prípade má prvý hráč nekonečne veľa optimálnych hodnôt a ceny hry Tento prípad je znázornený na obrázku 1.7, kde segment MN znázorňuje horné hranice, optimálne hodnoty sú v medziach Druhý hráč má čistú optimálnu stratégiu j=j 0 .

Maticové hry rádu m2 je možné riešiť aj grafickou metódou. Výplatná matica prvého hráča má v tomto prípade podobu

Zmiešané stratégie prvého a druhého hráča sú definované podobne ako v prípade hier poradia 2n. Nech je hodnota od 0 do 1 vynesená pozdĺž horizontálnej osi a hodnota priemernej výhry) prvého hráča pozdĺž vertikálnej osi za podmienky, že prvý hráč použije svoju čistú i-tú stratégiu (i=1, 2, ..., m), druhá - jeho zmiešaná stratégia (y 1, 1- y 1) =y. Napríklad, keď m=4 graficky) možno znázorniť, ako je znázornené na obrázku 1.7.

Obrázok 1.7 - funkčný graf)

Prvý hráč sa snaží maximalizovať svoju priemernú výplatu, preto sa snaží nájsť

Funkcia je znázornená hrubou čiarou a predstavuje hornú hranicu množiny obmedzení. Druhý hráč sa snaží minimalizovať výberom svojej stratégie, t.j. hodnota zodpovedá

Na obrázku je hodnota označená bodkou. Inými slovami, sú určené dve stratégie prvého hráča a pravdepodobnosť pre druhého hráča, pri ktorej sa dosiahne rovnosť.

Z obrázku vidíme, že cena hry je ordináta bodu, pravdepodobnosť je úsečka bodu. Pre zostávajúce čisté stratégie prvého hráča v optimálnej zmiešanej stratégii musí ().

Riešením systému (1.69) teda získame optimálnu stratégiu druhého hráča a cenu hry. Optimálnu zmiešanú stratégiu pre prvého hráča nájdeme riešením nasledujúceho systému rovníc:

1.7 Maticová metóda riešenia hier

Označenia:

Ľubovoľná štvorcová podmatica matice objednávky

Matica(1);

Matica transponovaná do;

Matica pripojená k B;

- (1) maticu získanú z X vymazaním prvkov, ktoré zodpovedajú riadkom vymazaným po prijatí;

- (1) matica získaná vymazaním prvkov, ktoré zodpovedajú riadkom vymazaným z po prijatí.

Algoritmus:

1. Vyberte štvorcovú podmaticu matice poriadku () a vypočítajte

2. Ak nejaké alebo, tak nájdenú maticu zahoďte a skúste inú maticu.

3. Ak (), (), vypočítame a zostrojíme X a od a s pridaním núl na vhodné miesta.

Kontrola, či sú nerovnosti splnené

pre všetkých (1,75)

a nerovnosti

pre každého (1,76)

Ak jeden zo vzťahov nie je spokojný, skúsime ďalší. Ak sú všetky vzťahy platné, potom X a požadované riešenia.

1.8 Spôsob postupného približovania sa ceny hry

Pri štúdiu herných situácií sa často môže stať, že nie je potrebné získať presné riešenie hry alebo je z nejakého dôvodu nemožné alebo veľmi ťažké nájsť presnú hodnotu ceny hry a optimálne zmiešané stratégie. Potom môžete použiť približné metódy na riešenie maticovej hry.

Opíšme si jednu z týchto metód - metódu postupného približovania sa k cene hry. Počet vypočítaný pri použití metódy sa zvyšuje približne úmerne počtu riadkov a stĺpcov výplatnej matice.

Podstata metódy je nasledovná: hra sa veľakrát hrá mentálne, t.j. postupne si hráč v každej hre vyberá stratégiu, ktorá mu dáva najväčšie celkové (celkové) výhry.

Po takejto implementácii niektorých hier sa vypočíta priemerná hodnota výhier prvého hráča a prehier druhého hráča a ich aritmetický priemer sa berie ako približná hodnota ceny hry. Metóda umožňuje nájsť približnú hodnotu optimálnych zmiešaných stratégií oboch hráčov: je potrebné vypočítať frekvenciu aplikácie každej čistej stratégie a brať ju ako približnú hodnotu v optimálnej zmiešanej stratégii príslušného hráča.

Preukázateľne pri neobmedzenom zvyšovaní počtu programových hier sa priemerný zisk prvého hráča a priemerná strata druhého hráča budú neobmedzene blížiť k cene hry a približné hodnoty zmiešaných stratégií v r. prípad, keď má hra jedinečné riešenie, bude smerovať k optimálnym zmiešaným stratégiám každého hráča. Všeobecne povedané, tendencia približných hodnôt nad týmito hodnotami približovať sa skutočným hodnotám je pomalá. Tento proces je však ľahko mechanizovateľný a tým pomáha získať riešenie hry s požadovaným stupňom presnosti aj s výplatnými maticami relatívne veľkého rádu.

2. Praktická časť

Pár sa rozhodne, kam sa pôjde prejsť a strávi čas užitočne pre oboch.

Dievča sa rozhodne ísť na prechádzku do parku na čerstvý vzduch a večer si pozrieť film v najbližšom kine.

Chlapík navrhuje ísť do technologického parku a potom si pozrieť zápas miestnych klubových futbalistov na centrálnom štadióne.

V súlade s tým musíte zistiť, ako dlho bude trvať dosiahnutie cieľa jedného z hráčov. Víťazná matica bude vyzerať takto:

Tabuľka 1. Výplatná matica

Stratégie

Od 1 2 , Je zrejmé, že táto hra nemá sedlový bod v čistých stratégiách. Preto používame nasledujúce vzorce a získame:

Uverejnené na http://www.allbest.ru/

2.2 Hra 2xn a mx2

Problém 1 (2xn)

Pre suché a vlhké podnebie sa pestujú dve obilniny.

A stav prírody možno považovať za: suchý, vlhký, mierny.

Uverejnené na http://www.allbest.ru/

Maximálna hodnota M() sa dosiahne v bode M, ktorý je tvorený priesečníkom priamok zodpovedajúcich j=1, j"=2. Podľa toho predpokladáme:

Problém 2 (mx2)

Chlap a dievča zvažujú možnosti, kam ísť cez víkend.

Výber miesta na dovolenku si možno predstaviť ako: park, kino, reštaurácia.

Uverejnené na http://www.allbest.ru/

Maximálna hodnota M() sa dosiahne v bode E, ktorý je tvorený priesečníkom priamok zodpovedajúcich j=1, j"=2. Podľa toho predpokladáme:

Na určenie hodnoty v je potrebné vyriešiť nasledujúce rovnice:

2.5 Maticová metóda

Dve reštaurácie (stravovacie zariadenia), ktoré si navzájom konkurujú, poskytujú nasledujúce súbory služieb. Prvá reštaurácia sa nachádza v centre a druhá na okraji mesta.

Centrálna reštaurácia zahŕňa tieto služby:

1) drahšie a kvalitnejšie služby zákazníkom;

2) jedlá sú zamerané na francúzsku kuchyňu;

Druhá reštaurácia ponúka:

1) lacné a vysoko kvalitné služby;

2) menu kombinuje rôzne slávne kuchyne sveta;

3) tiež neustále akcie a zľavy;

4) doručuje a prijíma objednávky na doručenie domov.

V súlade s úlohou bude zisk za jeden deň rozdelený medzi dve reštaurácie takto:

Tabuľka 2. Výplatná matica

Stratégie

Riešenie hry s formulárom pomocou maticovej metódy:

Existuje šesť podmatíc a:

Zvážte maticu:

x 1 = ? 0, x 2 = ? 0

Pretože x 2 =< 0, то мы отбрасываем.

Pozrime sa teraz na maticu:

x 1 = ? 0, x 2 = ? 0

Cena hry.

Tento pomer je v rozpore s požiadavkou, a preto nie je vhodný.

Pozrime sa teraz na maticu:

x 1 =, x 2 =? 0,

y1 =< 0, y 2 = ? 0.

Keďže y 1 =< 0, то мы отбрасываем и.

Pozrime sa teraz na maticu:

x 1 = , x 2 = 0, keďže x 2 = 0, potom vyradíme a.

Pozrime sa teraz na maticu:

x 1 =, x 2 =? 0. Keďže x 1 = 0, zahodíme a.

Pozrime sa teraz na maticu:

x 1 = , x 2 =, y 1 = , y 2 =, potom pokračujeme ďalej:

x 1 = , x 2 = , y 1 = , y 2 = alebo

Cena hry.

Teraz sú skontrolované základné vzťahy:

Uverejnené na http://www.allbest.ru/

Odpoveď: x 1 =, x 2 =, y 1 =, y 2 =, y 3 = 0, y 4 = 0,.

Hnedá metóda

Na žiadosť pracovníkov istej firmy odborová organizácia rokuje s jej vedením o organizovaní teplých obedov na náklady firmy. Odborový zväz zastupujúci pracujúcich chce zabezpečiť, aby obed bol čo najkvalitnejší, a teda aj drahší. Vedenie spoločnosti má protichodné záujmy. Nakoniec sa strany dohodli na nasledujúcom. Odborová organizácia (hráč 1) vyberie jeden z troch podnikov (A 1, A 2, A 3), ktoré dodávajú teplé jedlá, a vedenie podniku (hráč 2) vyberie sadu jedál z troch možností (B 1, B 2 , B3). Po podpísaní zmluvy zväz vygeneruje nasledujúcu platobnú maticu, ktorej prvky predstavujú náklady na sadu riadu:

Nech je hra definovaná nasledujúcou výplatnou maticou:

Predpokladajme, že druhý hráč si vybral svoju 2. stratégiu, potom prvý dostane:

2, ak použije svoju 1. stratégiu,

3, ak použije svoju 3. stratégiu.

Získané hodnoty sú zhrnuté v tabuľke 1.

Tabuľka 3. Stratégia druhého hráča

Číslo šarže	Stratégia hráča 2	Výhra 1. hráča

Z tabuľky 3 je vidieť, že s 2. stratégiou druhého hráča, prvý získa najväčšiu výplatu 3 pomocou svojej 2. alebo 3. stratégie. Keďže prvý hráč chce získať maximálnu výhru, reaguje na 2. stratégiu druhého hráča svojou 2. stratégiou. S druhou stratégiou prvého hráča prehrá druhý:

1, ak použije svoju 1. stratégiu,

3, ak použije svoju druhú stratégiu,

4, ak použije svoju 3. stratégiu.

Tabuľka 4. Stratégia prvého hráča

Číslo šarže	Stratégia 1. hráča	2. hráč prehráva

Z tabuľky 2 je vidieť, že pri 2. stratégii prvého hráča bude mať druhý hráč najmenšiu stratu 1, ak uplatní svoju 1. stratégiu. Keďže druhý hráč chce stratiť menej, v reakcii na 2. stratégiu prvého hráča použije svoju 1. stratégiu. Získané výsledky sú zhrnuté v tabuľke 5.

Tabuľka 5. Stratégie prvého a druhého hráča

Číslo šarže

Stratégia hráča 2

Celkové výhry 1. hráča

Stratégia 1. hráča

V tabuľke 5 v stĺpci stratégie druhého hráča v druhom riadku je číslo 1, ktoré označuje, že v druhej hre je výhodné, aby druhý hráč použil svoju 1. stratégiu; v stĺpci je najväčšia priemerná výhra 3 prvého hráča, ktorú získal v prvej hre; stĺpec w obsahuje najmenšiu priemernú stratu 1, ktorú získal druhý hráč v prvej hre; stĺpec v obsahuje aritmetický priemer v = (u + w) - t.j. približnú hodnotu ceny hry získanú v dôsledku prehry jednej hry v hre. Ak druhý hráč použije svoju 1. stratégiu, potom prvý dostane 3, 1, 2, v tomto poradí, so svojou 1., 2., 3. stratégiou a celkové výhry prvého hráča za obe hry budú:

2 + 3=5 s jeho 1. stratégiou,

3 + 1=4 s jeho 2. stratégiou,

3 + 2=5 s jeho 3. stratégiou.

Tieto celkové výhry sú zaznamenané v druhom riadku tabuľky. 3 a v stĺpcoch zodpovedajúcich stratégiám prvého hráča: 1, 2, 3.

Zo všetkých celkových výhier je najväčšia 5. Získava sa 1. a 3. stratégiou prvého hráča, potom si môže vybrať ktorúkoľvek z nich; Povedzme, že v takých prípadoch, keď sú dve (alebo viaceré) rovnaké celkové výhry, zvoľte stratégiu s najnižším číslom (v našom prípade musíme zvoliť 1. stratégiu).

Pri 1. stratégii prvého hráča prehrá druhý 3, 2, 3 v tomto poradí so svojimi 1., 2., 3. stratégiou a celková strata druhého hráča v oboch hrách bude:

1 + 3=4 s jeho 1. stratégiou,

3 + 2 = 5 s jeho druhou stratégiou,

4 + 3=7 s jeho 3. stratégiou.

Tieto celkové straty sú zaznamenané v druhom riadku tabuľky. 5 a v stĺpcoch zodpovedajúcich 1., 2., 3. stratégii druhého hráča.

Zo všetkých celkových prehier druhého hráča je najmenšia 4. Získava ju svojou 1. stratégiou, preto v tretej hre musí druhý hráč uplatniť svoju 1. stratégiu. Najväčšia celková výhra prvého hráča z dvoch hier delená počtom hier je umiestnená v stĺpci, t.j. Stĺpec w obsahuje najmenšiu celkovú stratu druhého hráča počas dvoch hier, vydelenú počtom hier, t.j. v stĺpci v je uvedený aritmetický priemer týchto hodnôt, t.j. = Toto číslo sa berie ako približná hodnota ceny hry s dvoma „ohranými“ hrami.

Takto sa získa nasledujúca tabuľka 4 pre dve hry.

Tabuľka 6. Celkové výhry a prehry hráčov po dvoch odohraných hrách

Stratégia hráča 2

Celkové výhry 1. hráča

Stratégia 1. hráča

Celková strata 2. hráča

V treťom riadku tabuľky 6 v stĺpci stratégie druhého hráča je číslo 1, ktoré znamená, že v tretej hre musí druhý hráč uplatniť svoju 1. stratégiu. V tomto prípade prvý hráč vyhrá 3, 1, 2 pomocou svojej 1., 2., 3. stratégie a jeho celkové výhry v troch hrách budú:

3 + 5 = 8 s jeho prvou stratégiou,

1 + 4 = 5 s jeho druhou stratégiou,

2 + 5 = 7 s jeho 3. stratégiou.

Tieto celkové výhry prvého hráča sú zaznamenané v treťom riadku tabuľky 6 a stĺpcoch zodpovedajúcich jeho stratégiám 1, 2, 3. Keďže s 1. stratégiou sa získa najväčšia celková výhra 8 prvého hráča, vyberie sa 1. podľa toho.

Pri 1. stratégii prvého hráča, druhý prehrá 3, 1, 2 v tomto poradí so svojou 1., 2., 3. stratégiou a celková strata druhého hráča pre obe hry bude:

3 + 4=7 s jeho 1. stratégiou,

2 + 5 = 7 s jeho 2. stratégiou,

3 + 7 = 10 s jeho 3. stratégiou.

Tieto celkové straty sú zaznamenané v treťom riadku tabuľky. 6 a v stĺpcoch zodpovedajúcich 1., 2., 3. stratégii druhého hráča. Zo všetkých jeho celkových strát je 7 najmenších a získa sa pomocou 1. a 2. stratégie, potom musí druhý hráč uplatniť svoju 1. stratégiu.

V tabuľke 6 v treťom riadku v stĺpci a zaznamenáva najväčšiu celkovú výhru prvého hráča za tri hry vydelenú číslom hry, t.j.; v stĺpci w je umiestnená najmenšia celková prehra druhého hráča počas troch hier, delená počtom hier, t.j.; stĺpec v obsahuje ich aritmetický priemer

Tak dostaneme tabuľku. 7 na tri zápasy.

Tabuľka 7. Celkové výhry a prehry hráčov po troch odohraných hrách

Číslo šarže

Stratégia hráča 2

Celkové výhry 1. hráča

Stratégia 1. hráča

Celková strata 2. hráča

Tabuľka 8. Konečná tabuľka po dvadsiatich odohraných zápasoch

Číslo šarže

Stratégia hráča 2

Celkové výhry 1. hráča

Stratégia 1. hráča

Celková strata 2. hráča

Od stola 7 a 8 je možné vidieť, že v 20 prehratých hrách sa stratégie 1, 2, 3 pre prvého hráča vyskytnú 12, 3, 5 krát, preto sú ich relatívne frekvencie v tomto poradí rovnaké; stratégie 1, 2, 3 pre druhého hráča sa vyskytujú 7, 11, 2 krát, preto sú ich relatívne frekvencie v tomto poradí rovnaké; približná cena hry. Táto aproximácia je celkom dobrá.

Nakoniec si všimnite, že ak má hra viac ako jedno riešenie, potom sa aproximácie ceny hry budú stále približovať skutočným nákladom hry a relatívne frekvencie stratégií hráčov sa už nebudú nevyhnutne približovať skutočným optimálnym hráčom. zmiešané stratégie.

Analýza výsledkov

V tejto práci sme študovali materiál na hľadanie riešení hier s nulovým súčtom pomocou grafickej, maticovej metódy a metódy postupnej aproximácie ceny hry. Zistili sa optimálne stratégie prvého a druhého hráča, ako aj náklady na hranie v hrách 2x2, 2xn a mx2, ako aj v hrách maticovou metódou a Brownovou metódou.

Na príklade dvojice bola simulovaná hra 2x2, ktorá bola riešená pomocou algebraických a grafických metód. Pri algebraickom riešení hry riešenie ukazuje, že pri použití ich optimálnych zmiešaných stratégií strávia prvý a druhý hráč spolu 4,6 hodiny. Grafické riešenie problému bolo získané s malou chybou a trvalo 4,5 hodiny.

A tiež boli simulované dva problémy 2xn a mx2. V probléme 2xn sa uvažovalo o poľnohospodárskej plodine a stratégia ukazuje, že je lepšie zasadiť pole 50 až 50 a cena hry bola 3,75 milióna rubľov. A v probléme mx2 sa zvažoval pár, ktorého stratégia ukázala, že je lacnejšie ísť do parku a kina a cena by bola 4,3 rubľov.

Pre maticovú metódu bol modelovaný problém, v ktorom boli uvažované dve reštaurácie, riešenie problému ukázalo, že pri použití jej optimálnej zmiešanej stratégie bude zisk prvej reštaurácie 15,6 milióna rubľov a pri použití jej optimálnej zmiešanej stratégie o druhá reštaurácia, nedovolí prvej zarobiť viac ako 15,6 milióna rubľov. Grafické riešenie malo za následok chybu a cena hry bola 14,9 milióna rubľov.

Pre Brownovu metódu bola vypracovaná úloha, v ktorej sa uvažuje s odborovou organizáciou a vedením spoločnosti, ich úlohou je zabezpečiť pracovníkom stravu. Ak obaja hráči použijú svoje optimálne stratégie, jedlo na osobu bude 2,45 tisíc rubľov.

Zoznam použitých zdrojov

1) Vilisov V.Ya. Poznámky k prednáške „Teória hier a štatistické rozhodnutia“, - odbor - „Voskhod“ MAI. 1979. 146 s.

2) Krushevsky A.V. Teória hier, - Kyjev: Vishcha School, 1977. - 216 s.

3) Cirkevníci U., Akof R., Arnof L., Úvod do operačného výskumu. - M.: Veda. 1967. - 488 s.

4) http://www.math-pr.com/exampl_gt2.htm

5) http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D1% 82%D0%B0%D0 %B3%D0%BE%D0%BD%D0%B8%D1%81 %D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0

Uverejnené na Allbest.ru

Podobné dokumenty

Rozhodovanie ako osobitný druh ľudskej činnosti. Racionálne znázornenie hernej matice. Príklady maticových hier v čistých a zmiešaných stratégiách. Operačný výskum: vzťah problémov lineárneho programovania s herno-teoretickým modelom.

kurzová práca, pridané 05.05.2010


Mnohokrát opakované hry, ich charakteristické vlastnosti a fázy. Zmiešané stratégie, podmienky a možnosti ich využitia v praxi. Analytická metóda na riešenie hry typu 2 x 2. Základné vety pre pravouhlé hry. Algebraické riešenia.

prezentácia, pridané 23.10.2013


Základné definície teórie bimaticových hier. Príklad bimatrixovej hry „Študent-Učiteľ“. Zmiešané stratégie v bimaticových hrách. Hľadajte „rovnovážnu situáciu“. 2x2 bimaticové hry a vzorce pre prípad, keď má každý hráč dve stratégie.

abstrakt, pridaný 13.02.2011


Získajte všeobecné informácie o maticových hrách a hrách s nulovým súčtom. Pojem pozičná hra, strom, informačná množina. Zohľadnenie princípu maxima a princípu rovnováhy. Paretova optimálnosť. Pozičná neantagonistická hra, jej vlastnosti.

kurzová práca, pridané 17.10.2014


Teória hier je oblasť matematiky, ktorej predmetom je štúdium matematických modelov na prijímanie optimálnych rozhodnutí v podmienkach konfliktu. Iteratívna Brown-Robinsonova metóda. Monotónny iteračný algoritmus na riešenie maticových hier.

práca, pridané 8.8.2007


Zostavenie platobnej matice, hľadanie spodnej a hornej čistej ceny hry, stratégie maximin a minimax hráčov. Zjednodušenie platobnej matice. Riešenie maticovej hry pomocou redukcie na úlohu lineárneho programovania a doplnku „Hľadaj riešenie“.

test, pridaný 10.11.2014


Teória hier je matematická teória konfliktných situácií. Vývoj matematického modelu dvojčlennej hry s nulovým súčtom, jeho implementácia vo forme programových kódov. Spôsob riešenia problému. Vstupné a výstupné dáta. Program, návod na použitie.

kurzová práca, pridané 17.08.2013


Základné informácie o simplexovej metóde, posúdenie jej úlohy a významu v lineárnom programovaní. Geometrická interpretácia a algebraický význam. Hľadanie maxima a minima lineárnej funkcie, špeciálne prípady. Riešenie úlohy pomocou maticovej simplexovej metódy.

práca, pridané 01.06.2015


Techniky konštrukcie matematických modelov počítačových systémov, ktoré odrážajú štruktúru a procesy ich fungovania. Počet prístupov k súborom v procese riešenia priemerného problému. Určenie možnosti umiestnenia súborov na externé pamäťové jednotky.

laboratórne práce, doplnené 21.06.2013


Návrh matematického modelu. Popis hry tic-tac-toe. Model logickej hry založenej na booleovskej algebre. Digitálne elektronické zariadenia a vývoj ich matematického modelu. Herná konzola, herný ovládač, herná línia.