Čisté strategické hry. Teória hier a štatistické rozhodnutia

Popis bimatrixovej hry. Všetky hry, ktoré boli recenzované, patrili do triedy hry s nulovým súčtom. Množstvo konfliktných situácií, ktoré vznikajú pri konaní, sa však vyznačuje tým, že zisk jednej strany sa presne nerovná strate druhej. Herno-teoretické modely Takéto situácie sú nekooperatívne hry s nenulovým súčtom. Takéto hry sa nazývajú bimatice, pretože úloha každej takejto hry je redukovaná na úlohu dvoch matíc rovnakého tvaru: .

Proces bimatická hra spočíva v nezávislom výbere čísla hráčom I a hráčom II, po ktorom získa výhru hráč I a hráč II.

Zavolajú sa čísla riadkov matíc čisté hráčske stratégie I a čísla stĺpcov týchto matíc sú čisté hráčske stratégie II. Potom páry formy budú situácie v čistých stratégiách bimatická hra, a čísla a sú výplaty hráčov I a II v situácii. Podľa toho je rozdelenie pravdepodobnosti používania čistých stratégií hráča I a hráč II - zavoláme zmiešané stratégie. Potom dvojice formulárov predstavujú situácie bimatická hra V zmiešané stratégie a čísla A sú matematické očakávania výhry pre hráčov I. a II.

Rovnovážna situácia bimaticovej hry v zmiešaných stratégiách budeme volať taký pár, pre ktorý:

(8.2)

,

Kde - očakávaná hodnota výhry hráča I;

Matematické očakávanie výhry pre hráča II;

Optimálne zmiešané hráčska stratégia I;

Optimálne zmiešané hráčska stratégia II.

Úloha

Konštrukcia a riešenie bimaticovej hry. Predpokladajme, že protiponorková ponorka krajiny hľadá raketovú ponorku krajiny, ktorá manévruje v presne vymedzenej časti bojovej hliadkovej oblasti. Zvyšok priestoru obsluhuje protiponorková ponorka, ktorá vykonáva protiponorkové pátracie akcie. Nechajte každý protiponorkový čln použiť svoju vlastnú hydroakustickú stanicu na detekciu nepriateľa buď v aktívnom režime, periodicky ho zapínať, alebo len v pasívnom režime vykonávaním nepretržitého vyhľadávania.

Ako protiponorková ponorka, tak aj raketová ponorka s detekciou sonaru sa môžu nepriateľovi vyhnúť. Frekvencia aktivácie sonaru však umožňuje detekciu, ale je nespoľahlivá.

V podobnom konfliktná situácia jeden z hráčov je protiponorková ponorka a druhý je protiponorková ponorka. Je zrejmé, že raketová ponorka nemôže byť hráčom, pretože má iba jeden spôsob akcie, ktorým je nenápadné manévrovanie a vyhýbanie sa detekcia sonarových signálov.

Charakteristickým znakom tu je, že každý z hráčov sleduje iné, no nie protichodné ciele. Účelom protiponorkovej ponorky je totiž odhaliť raketovú ponorku a účelom protiponorkovej ponorky je odhaliť protiponorkovú ponorku. Preto na posúdenie dosiahnutia cieľa každým hráčom je v závislosti od zvolených metód konania (stratégií) potrebné mať dve kritériá efektívnosti a podľa toho aj dve výplatné funkcie. Potom modelom takejto konfliktnej situácie bude konečná hra s nenulovým súčtom, popísaná dvoma maticami rovnakého tvaru A , nazývaný bimatrix.

Zoberme si to ako výkonnostné kritérium protiponorková ponorka (hráč I) pravdepodobnosť odhalenia raketovej ponorky a za výkonnostné kritérium protiponorková ponorka (hráč II) – pravdepodobnosť odhalenia protiponorkovej ponorky. Potom bude dvojmaticová hra daná maticou (obrázok 9.a) a maticou (obrázok 9.b).

Ryža. 9.a.

Ryža. 9.b.

Kde - použitie aktívneho režimu;

Použitie pasívneho režimu.

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á m stratégií i = 1,2,...,m, druhý má n stratégií j= 1,2,...,n. Každá dvojica stratégií ( i, j) zhodné číslo A ij , vyjadrenie zisku hráča 1 na úkor hráča 2, ak prvý hráč prijme jeho i- yu stratégiu a 2 – jeho vlastnú j stratégiu.

Každý hráč urobí jeden ťah: hráč 1 si vyberie ten svoj i stratégia ( i= ), 2 – váš j stratégia ( j=
), potom získa výhru hráč 1 A ij na úkor hráča 2 (ak A ij < 0, potom to znamená, že hráč 1 zaplatí druhú čiastku | A ij|). Tu sa hra končí.

Stratégia každého hráča i=
; j =
často nazývaná čistá stratégia.

Ak vezmeme do úvahy maticu

A=

potom vedenie každej hry maticovej hry s maticou A závisí od výberu hráča 1 i riadok a hráč 2 j stĺpec a hráč 1 (na úkor hráča 2) získa výhry a ij .

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í hráč 1 skúma výplatnú maticu A takto: pre každú hodnotu i (i =
) minimálna výherná hodnota je určená v závislosti od stratégií používaných hráčom 2

A ij (i=
)

tie. určený minimálne výhry pre hráča 1 za predpokladu, že akceptuje jeho ičistej stratégie, potom sa z týchto minimálnych výnosov takáto stratégia nájde i = i O, pri ktorej bude tento minimálny zisk maximálny, t.j. Nachádza

A ij =
=(1)

Definícia . číslo , definovaný vzorcom (1) sa nazýva nižšia čistá cena hry a ukazuje, aké minimálne výhry si môže hráč 1 zaručiť použitím svojich čistých stratégií na všetky možné akcie hráča 2.

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

A ij

tie. určí sa maximálna výhra hráča 1 za predpokladu, že hráč 2 použije svoje jčistá stratégia, potom hráč 2 hľadá svoju vlastnú j = j 1 stratégia, v ktorej hráč 1 získa min výhru, t.j. nájde

a ij =
=(2).

Definícia . číslo , určený vzorcom (2), sa nazýva čistá horná cena hry a ukazuje, aké maximálne výhry si hráč 1 môže zaručiť vďaka svojim stratégiám.

Inými slovami, pomocou svojich čistých stratégií môže hráč 1 zabezpečiť výhru nie menej ako a hráč 2 môže pomocou svojich čistých stratégií zabrániť hráčovi 1 vyhrať viac ako .

Definícia . Ak v hre s maticou A =potom hovoria, že táto hra má sedlo bod v čistých stratégiách a internetová cena hry

 = =.

Sedlový bod je dvojica čistých stratégií (i O , j O ) hráči 1 a 2, pri ktorých sa dosiahne rovnosť =. Tento pojem má nasledovný význam: ak jeden z hráčov dodrží stratégiu zodpovedajúcu sedlovému bodu, potom druhý hráč nemôže urobiť lepšie, ako dodržať stratégiu zodpovedajúcu sedlovému bodu. Matematicky sa to dá napísať aj inak:

Kde i, j– akékoľvek čisté stratégie hráčov 1 a 2; (i O , j O ) – stratégie, ktoré tvoria sedlový bod.

Teda na základe (3) sedlového prvku
je minimálna v i o -tom riadku a maximum v j o -tom stĺpci matice A. Hľadanie sedlového bodu matice A prebieha nasledovne: v matici A postupne v každom riadok nájdite minimálny prvok a skontrolujte, či je tento prvok maximálny stĺpec. Ak áno, potom ide o sedlový prvok a jemu zodpovedajúca dvojica stratégií tvorí sedlový bod. Pár čistých stratégií (i O , j O ) hráčov 1 a 2, tvoriacich sedlový hrot a sedlový prvok
, volal riešenie hry . V čom i O A j O sa volajú optimálne čistenie stratégií hráči 1 a 2.

Príklad 1

Sedlový bod je pár ( i O = 3;j O= 1), pri ktorom = == 2.

Všimnite si, že hoci odmena v situácii (3;3) sa tiež rovná 2 = =, nejde o sedlový bod, pretože táto výhra nie je maximálna medzi výhrami v treťom stĺpci.

Príklad 2

Z analýzy výplatnej matice je zrejmé, že
, t.j. táto matrica nemá sedlový hrot. Ak si hráč 1 zvolí svoju stratégiu čistého maxima i = 2, potom hráč 2, ktorý si zvolí svoj minimax j= 2, prehrá len 20. V tomto prípade je pre hráča 1 výhodné zvoliť stratégiu i = 1, t.j. odchýliť sa od svojej čistej maximalinovej stratégie a vyhrať 30. Potom bude pre hráča 2 výhodné zvoliť stratégiu j = 1, t.j. odchýliť sa od svojej čistej minimax stratégie a stratiť 10. Na druhej strane si hráč 1 musí zvoliť svoju 2. stratégiu, aby vyhral 40, a hráč 2 zareaguje výberom 2. stratégie atď.

Pozrime sa na príklad. Nech je daná herná matica (4):

Musíme nájsť spodnú cenu hry α, hornú cenu hry β a stratégie minimax a skontrolovať, či sú stabilné. Riešenie. Z analýzy dodatočného stĺpca a riadku dostaneme: α = 5, β = 5. Maximin sa rovná minimaxu! Toto je špeciálny prípad. Čo z toho vyplýva? Zoberme si niekoľko minimax stratégií: K 2 a C 3. Ak sa obaja budú držať týchto stratégií, potom bude odmena 5. Teraz povedzme, že sme sa dozvedeli o správaní nepriateľa. Čo urobíme? Nič! Naďalej sa budeme držať stratégie K2, pretože akékoľvek odklonenie od nej je pre nás nerentabilné. Či už vieme alebo nevieme o správaní nepriateľa, stále sa budeme držať stratégie K 2! To isté platí pre „modrých“ – nemá zmysel meniť svoju stratégiu C3. V tomto príklade je dvojica stratégií K 2 a C 3 stabilná, to znamená, že predstavuje rovnovážnu polohu a poskytuje riešenie hry. Prečo sa to stalo? Pretože v matici je špeciálny prvok 5; je minimálny vo svojom riadku a zároveň maximálny vo svojom stĺpci. Takýto prvok je tzv sedlový bod. Ak má matica sedlový bod (to znamená, že spodná cena hry sa rovná hornej), hra má riešenie v čistých stratégiách: ide o dvojicu stratégií, ktoré sa pretínajú v sedlovom bode. Samotný sedlový bod udáva cenu hry – v našom príklade sa rovná 5. Trieda hier, ktoré majú sedlový bod, má v teórii hier veľký význam. Predovšetkým je dokázané, že ak podľa pravidiel hry každý hráč pozná výsledok všetkých doterajších ťahov, svojich aj súperových (tzv. hra s kompletnými informáciami), potom hra má sedlovú pointu, a preto má riešenie v čistých stratégiách. Príklady hier s úplnými informáciami zahŕňajú: šach, dámu, piškvorky atď. Uveďme príklad hry s úplnými informáciami, ktorej riešenie sa dá ľahko nájsť. Dvaja hráči - K a C - striedavo kladú na okrúhly stôl rovnaké mince. Pozícia každej mince je zvolená ľubovoľne, pokiaľ sa neprekrýva s ostatnými. Hráč, ktorý umiestni mincu ako posledný, vyhráva (keď už nezostane miesto pre ostatných). Stojí za to sa trochu zamyslieť, aby ste sa uistili, že výsledok tejto hry je vždy vopred stanovený záver a že existuje dobre definovaná stratégia, ktorá zaručí výhru hráčovi, ktorý vhodí mincu ako prvý (nech je to K). Totiž, K musí umiestniť prvú mincu do stredu stola a potom na každý ťah C musí reagovať ťahom presne symetrickým vzhľadom na stred stola! Chudák S sa môže správať ako chce, no aj tak pre neho niet úniku... Evidentne má takáto hra zmysel len pre toho, kto nepozná riešenie. Je zvláštne, že situácia je úplne rovnaká ako u takýchto populárna hra ako šach! Táto hra má zmysel len dovtedy, kým sa nenájde riešenie. Teoreticky sa dokázalo, že riešenie existuje a výsledok šachovej partie je v podstate vopred daný: ak každá strana použije svoju optimálnu stratégiu, potom sa hra buď vždy skončí výhrou bieleho, alebo vždy výhrou čierneho, alebo vždy v remíze! Ale čo presne? To ešte nevieme, keďže počet možných stratégií je príliš veľký na to, aby sme dokázali zostrojiť maticu šachovej partie a nájsť v nej sedlový bod... Pravdepodobne šachových fanúšikov zaujíma, že šach hra sa tak skoro nevyrieši. Na záver si všimnime, že v matici môže byť nie jeden, ale niekoľko sedlových bodov; potom je toľko riešení hry v čistých stratégiách, koľko je sedlových bodov. Každý z nich vyhrá, rovná cene hry.

Čistá stratégia hráč I si vyberie jeden z n riadkov výplatnej matice A a čistou stratégiou hráča II je vybrať si jeden zo stĺpcov tej istej matice.

Optimálne čisté hráčske stratégie sa od zmiešaných líšia prítomnosťou povinnej jednotky p i = 1, q i = 1. Napríklad: P(1,0), Q(1,0). Tu p 1 = 1, q 1 = 1.

Problém 1
Pomocou platobnej matice nájdite optimálne čisté stratégie využívajúce princíp striktnej dominancie. Ako odpoveď napíšte vektory P*, Q*.

	R1	R2	R3	R4
S1	3	1	2	5
S2	2	0	0	3
S3	-3	-5	-5	-2
S4	0	-2	-2	1

Riešenie:

Všetky problémy riešime pomocou maticovej hry s kalkulačkou.

Predpokladáme, že hráč I volí svoju stratégiu tak, aby maximalizoval svoju výplatu, a hráč II volí stratégiu tak, aby minimalizoval výplatu hráča I.

Hráči	B 1	B 2	B 3	B 4	a = min (A i)
A 1	3	1	2	5	1
A 2	2	0	0	3	0
A 3	-3	-5	-5	-2	-5
A 4	0	-2	-2	1	-2
b = max (B i)	3	1	2	5

Nájdeme garantovanú výplatu definovanú podľa nižšia cena hra a = max(a i) = 1, čo označuje maximálnu čistú stratégiu A 1 .
Horná cena hry b = min(b j) = 1.
Sedlový bod (1, 2) označuje riešenie dvojice alternatív (A1, B2). Cena hry je 1.
2. Skontrolujte, či v matici platieb nie sú dominantné riadky a dominantné stĺpce.
Niekedy sa na základe jednoduchého skúmania hernej matice dá povedať, že niektoré čisté stratégie možno do optimálnej zmiešanej stratégie zaradiť len s nulovou pravdepodobnosťou.
To hovoria i-tý Dominuje mu stratégia hráča 1 kth ak a ij ≥ a kj pre všetkých j E N a aspoň na jednu j a ij > a kj . V tomto prípade sa to tiež hovorí i-tý stratégia (alebo línia) – dominantná, k-tý– dominoval.
To hovoria j-i Dominuje mu stratégia 2. hráča lth stratégia ako pre každého j E M a ij ≤ a il a aspoň pre jedno i a ij< a il . В этом случае j-tý stratégia (stĺpec) sa nazýva dominantná, lth– dominoval.
Stratégia A 1 dominuje nad stratégiou A 2 (všetky prvky v riadku 1 sú väčšie alebo rovné hodnotám v 2. riadku), preto vylučujeme 2. riadok matice. Pravdepodobnosť p 2 = 0.
Stratégia A 1 dominuje nad stratégiou A 3 (všetky prvky riadku 1 sú väčšie alebo rovné hodnotám 3. riadku), preto vylučujeme 3. riadok matice. Pravdepodobnosť p 3 = 0.

3	1	2	5
0	-2	-2	1

Z pohľadu strát hráča B dominuje stratégia B 1 nad stratégiou B 2 (všetky prvky stĺpca 1 sú väčšie ako prvky stĺpca 2), preto vylučujeme 1. stĺpec matice. Pravdepodobnosť q 1 = 0.
Z pohľadu strát hráča B dominuje stratégia B 4 nad stratégiou B 1 (všetky prvky stĺpca 4 sú väčšie ako prvky stĺpca 1), preto vylučujeme 4. stĺpec matice. Pravdepodobnosť q 4 = 0.

1	2
-2	-2

Hru 4x4 sme zredukovali na hru 2x2.



Herné riešenie ( 2 x n

p1 = 1
p2 = 0
Cena hry, y = 1
Teraz môžeme nájsť minimax stratégiu hráča B napísaním zodpovedajúceho systému rovníc
q 1 = 1
q1 + q2 = 1
Pri riešení tohto systému zistíme:
q 1 = 1.
odpoveď:
Cena hry: y = 1, vektory hráčskej stratégie:
Q(1; 0), P(1; 0)

∑a ij q j ≤ v
∑a ij p i ≥ v
M(P1;Q) = (11) + (20) = 1 = v
M(P2;Q) = (-2 1) + (-2 0) = -2 ≤ v
M(P;Q1) = (11) + (-20) = 1 = v
M(P;Q 2) = (2 1) + (-2 0) = 2 ≥ v

Keďže riadky a stĺpce boli z pôvodnej matice odstránené, nájdené pravdepodobnostné vektory možno zapísať ako:
P(1;0;0;0)
Q(0;1;0;0)

Problém 2
Pomocou platobnej matice nájdite spodnú a hornú cenu hry. Ak existuje sedlový bod, zapíšte si vektory optimálnych čistých stratégií P*, Q*.

	R1	R2	R3
S1	-6	-5	0
S2	-8	-3	-2
S3	-3	-2	3

Riešenie:
1. Skontrolujte, či má platobná matica sedlový bod. Ak áno, potom vypíšeme riešenie hry v čistých stratégiách.

Hráči	B 1	B 2	B 3	a = min (A i)
A 1	-6	-5	0	-6
A 2	-8	-3	-2	-8
A 3	-3	-2	3	-3
b = max (B i)	-3	-2	3

Nájdeme garantovaný výnos určený nižšou cenou hry a = max(a i) = -3, čo udáva maximálnu čistú stratégiu A 3 .
Horná cena hry b = min(b j) = -3.
Sedlový bod (3, 1) označuje riešenie dvojice alternatív (A3, B1). Cena hry je -3.
Odpoveď: P(0,0,1), Q(1,0,0)

Problém 3
Pomocou platobnej matice nájdite vektory optimálnych stratégií P*, Q* a cenu hry. Ktorý hráč vyhrá?

	R1	R2	R3	R4
S1	-6	-6	2	4
S2	2	-2	7	-1

Riešenie:
1. Skontrolujte, či má platobná matica sedlový bod. Ak áno, potom vypíšeme riešenie hry v čistých stratégiách.
Predpokladáme, že hráč I volí svoju stratégiu tak, aby maximalizoval svoju výplatu, a hráč II volí stratégiu tak, aby minimalizoval výplatu hráča I.

Hráči	B 1	B 2	B 3	B 4	a = min (A i)
A 1	-6	-6	2	4	-6
A 2	2	-2	7	-1	-2
b = max (B i)	2	-2	7	4

Nájdeme garantovaný výnos určený nižšou cenou hry a = max(a i) = -2, čo udáva maximálnu čistú stratégiu A 2 .
Horná cena hry b = min(b j) = -2.
Sedlový bod (2, 2) označuje riešenie dvojice alternatív (A2, B2). Cena hry je -2.
3. Nájdite riešenie hry v zmiešaných stratégiách.
Vyriešme problém pomocou geometrickej metódy, ktorá zahŕňa nasledujúce kroky:
1. V karteziánskom súradnicovom systéme je pozdĺž osi x vynesený segment, ktorého dĺžka sa rovná 1. Ľavý koniec segmentu (bod x = 0) zodpovedá stratégii A 1, pravý koniec stratégii A 2 (x = 1). Medziľahlé body x zodpovedajú pravdepodobnostiam niektorých zmiešaných stratégií S 1 = (p 1 ,p 2).
2. Výplaty stratégie A 1 sú vynesené na ľavej osi. Na priamku rovnobežnú s ordinátou od bodu 1 sú vynesené výhry stratégie A 2.
Herné riešenie ( 2 x n) realizujeme z pozície hráča A, pričom dodržiavame stratégiu maximin. Žiadny z hráčov nemá dominantné alebo duplicitné stratégie.

Maximálna optimálna stratégia hráča A zodpovedá bodu N, pre ktorý môžeme písať nasledujúci systém rovnice:
p1 = 0
p2 = 1
Cena hry, y = -2
Teraz môžeme nájsť minimaxovú stratégiu hráča B napísaním zodpovedajúceho systému rovníc, s vylúčením stratégie B 1, B 3, B 4, ktorá jednoznačne dáva väčšiu stratu hráčovi B, a preto q 1 = 0,q 3 = 0, q4 = 0.
-2q2 = -2
q2 = 1
Pri riešení tohto systému zistíme:
q2 = 1.
odpoveď:
Cena hry: y = -2, vektory hráčskej stratégie:
Q(0; 1; 0; 0); P(0; 1)
4. Skontrolujme správnosť riešenia hry pomocou kritéria optimálnosti stratégie.
∑a ij q j ≤ v
∑a ij p i ≥ v
M(P1;Q) = (-6 0) + (-6 1) + (2 0) + (4 0) = -6 ≤ v
M(P2;Q) = (2 0) + (-2 1) + (7 0) + (-1 0) = -2 = v
M(P;Q 1) = (-6 0) + (2 1) = 2 ≥ v
M(P;Q2) = (-60) + (-21) = -2 = v
M(P;Q 3) = (2 0) + (7 1) = 7 ≥ v
M(P;Q 4) = (4 0) + (-1 1) = -1 ≥ v
Všetky nerovnosti sú splnené ako rovnosť alebo prísne nerovnosti, preto je riešenie hry nájdené správne.

Problém 4
Uveďte podrobnú odpoveď na otázku

Čistá stratégia- deterministický (okrem náhodnosti) akčný plán. V predchádzajúcej kapitole sme uvažovali iba o čistých stratégiách. O zmiešaných stratégiách sa bude diskutovať v časti 2.2, ale zatiaľ, ak nie je uvedené inak, pod pojmom stratégia máme vždy na mysli čistú stratégiu.

Veľmi často počas prezentácie budeme ilustrovať koncepty riešenia na príkladoch bimaticových hier, preto uvedieme zodpovedajúce definície.

Definícia 2.1. Ultimátna hra je hra, v ktorej množina hráčov a množina stratégií každého hráča obsahuje konečný počet prvkov. Konečná hra dvoch osôb sa nazýva bimatická hra.

Priezvisko pochádza z pohodlnej formy zaznamenávania výhier v takejto hre – pomocou dvojitej matice.

Pre následnú analýzu je vhodné rozdeliť stratégie v ľubovoľnom strategickom profile s na stratégiu niektorých i-tých hráčov s a stratégie všetkých ostatných hráčov s_ (. Formálne s = (.у, s,). Nemyslí sa tu, že zamieňame súradnice profilu stratégie, len zavádzame iný spôsob jeho označenia.

Prvý koncept riešenia hry, na ktorý sa pozrieme, je rovnováha v dominantných stratégiách.

Definícia 2.2. Stratégia /-tého hráča prísne dominuje jeho stratégia s“ ak Uj(s jt s ,) > h,(s", s ,) pre ľubovoľnú množinu s , stratégie zostávajúcich hráčov. V tomto prípade sa stratégia s" nazýva prísne dominoval.

V podstate to znamená, že pre akékoľvek pevné v množine stratégií ostatných hráčov i-tý hráč, ktorý si zvolí stratégiu s, prísne dostáva väčšia výhra než pri voľbe stratégie s". Je logické predpokladať, že racionálny hráč by si nemal vyberať striktne dominované stratégie. Takýto predpoklad v najjednoduchších hrách môže stačiť na nájdenie riešenia hry.

Definícia 2.3. Profil stratégií s* =(s*, s^,..., s*) sa nazýva rovnováhu v (prísne) dominantné stratégie, ak pre ktoréhokoľvek i-tého hráča stratégia s“ striktne dominuje nad niektorou z jeho ostatných stratégií.

Môže sa zdať, že tento koncept riešenia môže viesť len k triviálnym záverom. Každý hráč má medzi svojimi stratégiami jednu, ktorá mu prinesie viac výhier ako ktorákoľvek iná, bez ohľadu na to, ako sa jeho súperi správajú. Potom použije presne túto stratégiu v rovnováhe. Všetko je celkom zrejmé. Ale toto je presne situácia, ktorá je typická pre možno najznámejšiu a veľmi dôležitú hru na analýzu množstva praktických situácií, „dilemu väzňov“.

Príklad 2.1 (dilema väzňov). Dvaja zločinci sú vo väzbe v oddelených celách a nemôžu komunikovať. Vyšetrovanie má dostatok dôkazov na to, aby každého z nich odsúdili za menší trestný čin na jeden rok. No na veľký zločin, za ktorý kriminalníkom hrozí desať rokov väzenia, vyšetrovanie nemá dostatok dôkazov. Zástupcovia vyšetrovania ponúkajú každému zo zločincov dohodu: zločinec dostane trest

o rok menej, ak predloží dôkazy proti svojmu partnerovi, čo bude stačiť na jeho obvinenie zo závažného zločinu. Za predpokladu, že zločincom záleží len na počte rokov strávených vo väzení, každý ďalší rok vyprodukuje mínus jeden nástroj. Potom môžu byť výhry zločincov reprezentované nasledujúcou dvojitou maticou:

V prípade, že účastníci hry nie sú uvedení, budeme predpokladať, že rôzne stratégie prvého účastníka zodpovedajú riadkom dvojitej matice a stratégie druhého účastníka zodpovedajú stĺpcom. Ak v našom príklade prvý väzeň vypovedá, ale druhý nie, prvý bude prepustený a druhý dostane desať rokov väzenia.

Je ľahké vidieť, že bez ohľadu na to, ako sa správa druhý väzeň, odmena je väčšia (trest väzenia je kratší), ak poskytnete dôkaz (pre prvého hráča sú prvé súradnice v prvom riadku dvojitej matice striktne vyššie). ako v druhom riadku, pre druhého hráča sú druhé súradnice v prvom stĺpci dvojitá matica je striktne väčšia ako v druhom stĺpci). Potom bude rovnováha v dominantných stratégiách profil stratégií (vydať svedectvo, vydať svedectvo).

Zaujímavosťou tohto príkladu je, že hráči sa výberom správania, ktoré zvyšuje ich výplatu, dostanú do situácie, kedy sú ich výplaty nízke v porovnaní s opačnou situáciou – keď sa obaja rozhodnú mlčať. Vysvetlenie spočíva v prítomnosti silného vonkajšieho účinku, t.j. silný vplyv konania jedného hráča na výhry iného hráča. V dôsledku toho sa rovnovážny profil stratégií ukazuje ako jediný paretovsky neefektívny profil v tejto hre. Upozorňujeme, že Paretova efektivita, žiaduca z pohľadu účastníkov hry, nemusí byť žiaduca zo sociálneho hľadiska, ako v tomto prípade.

Pri analýze ekonomickej situácie sa často vyskytujú situácie, ako je dilema väzňov. Zoberme si napríklad konkurenciu medzi dvoma obchodmi predávajúcimi podobný súbor produktov. Pre zjednodušenie predpokladajme, že obchody môžu účtovať len dve cenové úrovne – vysokú alebo nízku. Spotrebitelia prirodzene uprednostňujú nákup v obchode s nižšími cenami. Potom môžu výhry obchodov, charakterizované ich ziskom, vyzerať napríklad takto:

Z hľadiska rovnováhy je tu situácia podobná dileme väzňov - rovnováha v dominantných stratégiách (nízke ceny, nízke ceny) je jediným paretovo neefektívnym profilom (a tiež žiaducim zo sociálneho hľadiska).

Už spomínaná široká obľúbenosť dilemy väzňov bola dôvodom, že sa na jej príklade pokúsili experimentálne otestovať správnosť predpovedí teórie hier. Kontrola bola, že dva cudzinci ponúkol hrať hru o peniaze s cenami (napríklad v dolároch) blízkymi tým, ktoré sú uvedené pre hru v dvoch obchodoch. Každý účastník sa rozhodol samostatne (často anonymne) a nepoznal rozhodnutie druhého hráča, kým nezískal výhru. Ukázalo sa, že v takýchto podmienkach v mnohých hrách nedospeli hráči k rovnovážnemu výsledku, ak predpokladáme, že peňažné ceny správne posúdiť svoje výhry. Z výsledkov týchto experimentov samozrejme nevyplýva, že predpovede teórie hier sú nesprávne, ale len to, že hráči pri posudzovaní svojich výhier brali do úvahy aj nepeňažné faktory – úvahy o altruizme, spravodlivosti atď. Ak sú výplaty hráčov odhadnuté správne, potom by hráči mali preferovať dominantnú stratégiu a teda ju zvoliť (v duchu odhalených preferencií v mikroekonómii). Preto hodnota experimentov tohto druhu nespočíva v testovaní herných teoretických predpovedí, ale v hodnotení úlohy nemateriálnej motivácie v konaní jednotlivcov.

Oveľa menej ako pojem striktnej dominancie sa v teórii hier používa pojem slabá dominancia.

Definícia 2.4. Stratégia i-tého hráča, slabo dominuje jeho stratégia s“ ak m,(s, s ,) > m; (sJ, s,) pre ľubovoľný súbor stratégií zostávajúcich hráčov s_j, Navyše, pre aspoň jednu sadu stratégií iných hráčov je nerovnosť striktne splnená. Potom sa nazýva stratégia s slabo dominoval.

V prípade nestriktných nerovností sa už nedá povedať, že racionálny hráč nezvolí slabo dominovanú stratégiu, hoci takéto správanie vyzerá celkom logicky. Existuje, hoci zriedkavo používaná, definícia rovnováhy v slabo dominantných stratégiách podobná prípadu striktnej dominancie.

Definícia 2.5. Volá sa strategický profil s* = (s*, Sj,..., s*). rovnováha v slabo dominantných stratégiách, ak pre ktoréhokoľvek i-tého hráča stratégia s“ slabo dominuje nad niektorou z jeho ostatných stratégií.

Príklad 2.2 (uzavretá aukcia druhej ceny). Uzavretá aukcia druhej ceny sa koná medzi dvoma osobami. Aukcia je štruktúrovaná nasledovne. Každý účastník uvedie nezápornú ponuku bez toho, aby poznal ponuky ostatných účastníkov (v obálke). Účastník, ktorý urobil najvyššia ponuka, zaplatí maximálnu sumu spomedzi stávok ostatných účastníkov (t. j. sumu druhej, ale veľkosť stávky) a získa nejakú položku. Ak boli napríklad ponuky hráčov 100 a 90, potom účastník, ktorý ponúkol 100, vyhrá aukciu a kúpi položku za 90 – veľkosť druhej ponuky. Každý účastník nech má hodnotenie predmetu vyjadrené v peňažných jednotiek, v 2> 0. Tieto odhady sú známe všetkým účastníkom. V tomto prípade, z dôvodu jednoduchosti pri opise hry, ak obaja účastníci uvedú rovnakú stávku, položka pripadne prvému účastníkovi.

V tejto hre bude stratégia prvého hráča s veľkosťou jeho stávky. Keďže stávka je nezáporná, množina všetkých jej možných stratégií

5, = splnené 0 = u,(o, s 2) > w,(s, s 2) = = q, - s 2 v x slabo dominuje v stratégii s,.

Ukázali sme, že pre prvého hráča stratégia nazvať svoj odhad ako stávka slabo dominuje akejkoľvek inej stratégii. Je ľahké skontrolovať, či podobné tvrdenie platí aj pre druhého hráča. Upozorňujeme, že v našich úvahách sme nikdy nepoužili skutočnosť, že hráč pozná hodnotenie druhého hráča, a preto v prípade hry s neúplnými informáciami v uzavretá aukcia druhú cenu, zaplatenie vášho odhadu nebude o nič menej ziskové ako uskutočnenie akejkoľvek inej stávky.

Môže sa zdať, že pre predávajúceho je nerentabilné usporiadať aukciu druhej ceny, keď môže usporiadať aukciu s prvou cenou a získať hodnotu nie druhej, ale prvej ponuky. Hodnota ponúk v prípade rovnovážnej aukcie prvej ceny však bude nižšia. Viac o ziskovosti aukcií si povieme v kapitole. 5. Nateraz si všimnime, že druhá cenová aukcia je veľmi populárna a hojne ju využívajú napríklad firmy Google a „Yandex“ pri predaji kontextovej reklamy na internete.

Rovnováha v dominantných stratégiách existuje len v malá trieda hry. Hráči zvyčajne nemajú jedinú stratégiu, ktorá by dominovala všetkým ostatným. Ale koncept dominancie nám umožňuje nájsť riešenia v širšej triede hier. Aby ste to dosiahli, musíte dôsledne uvažovať o činnostiach hráčov. Už sme poznamenali, že racionálny hráč nezvolí striktne dominovanú stratégiu. To však znamená, že druhý hráč môže analyzovať hru, pričom ignoruje možnosť, že si jeho súper zvolí takúto stratégiu. Možno táto analýza odhalí, že druhý hráč má dominantnú stratégiu, ktorá v pôvodnej hre dominantná nebola. A tak ďalej. Uveďme formálnu definíciu.

Proces dôsledné vylúčenie striktne dominovaných stratégií sa uvádza nasledovne. Vylúčme z úvahy všetky striktne dominované hráčske stratégie, t.j. Zvážte novú hru, v ktorej sú všetky dominantné stratégie vylúčené zo súboru možných stratégií hráčov. Potom v tomto Nová hra vylúčme všetky striktne dominované stratégie atď.

Je možné, že takýto proces skončí, keď hráčom zostane niekoľko stratégií, ale je možné, že každý hráč bude mať len jednu nevylúčenú stratégiu, potom je logické považovať súbor týchto stratégií za riešenie hra.

Definícia 2.6. Ak v dôsledku postupnej eliminácie striktne dominovaných stratégií ostane každému hráčovi jediná stratégia, potom sa profil týchto stratégií nazýva tzv. rovnováha dominancie.

V príklade 1.1 sme získali práve takúto rovnováhu. Pozrime sa na ďalší príklad.

Strategický profil (N, P) predstavuje jedinú Nashovu rovnováhu v tejto hre. Ale pozor: na to, aby si vybral P, musí si byť druhý hráč istý, že prvý hráč nezvolí B. Ale výplata prvého hráča je rovnaká, ak si druhý hráč vyberie II. Navyše, keď si prvý hráč vybral B, nemusí sa báť, že druhý hráč si vyberie A. Možno sa racionálny druhý hráč zamyslí nad voľbou stratégie C.

Druhá otázka, na ktorú sa zatiaľ nenašla jednoznačná odpoveď: ako sa hráči dostanú do Nashovej rovnováhy?

Ideálny teoretický scenár je tento. Hráči nezávisle vytvárajú očakávania týkajúce sa akcií iných hráčov a potom si vyberajú akcie, ktoré maximalizujú ich zisk vzhľadom na ich očakávania. Ak očakávania zodpovedajú akciám, ktoré si hráči skutočne vybrali, získame Nashovu rovnováhu. Tento spôsob uvažovania nám umožňuje nazvať Nashovu rovnováhu situáciou s sebanaplňujúce očakávania. Odkiaľ však pochádzajú samotné očakávania? A ktorá z Nashových rovnováh, ak ich je niekoľko, sa vyberie ako výsledok opísaného procesu? V uvažovanom scenári zostávajú tieto otázky nezodpovedané.

Ďalší prístup zahŕňa tréning hráčov. Hráči sa buď teoreticky učia, ako hrať danú hru (predstavte si študentov Ekonomická fakulta), alebo majú skúsenosti s podobnými interakciami (napríklad skúsený zamestnanec príde na nový tím), čo im umožňuje správne formulovať očakávania a zvoliť optimálne správanie. Tento scenár pomáha vysvetliť formovanie očakávaní, ale v prvom rade znižuje rozsah aplikácie herné modely len k štandardným, študovaným a často sa vyskytujúcim interakčným situáciám, a po druhé to môže viesť k tomu, že situácie jednorazovej a opakovanej interakcie nie sú diferencované a tie sa výrazne líšia z pohľadu stratégií a spôsobov riešenia v rámci rámec teórie hier, o ktorom bude podrobnejšie popísané v kap. 4.

Tretím scenárom je, že medzi hráčmi existuje predchádzajúca dohoda alebo zvyky, zákony alebo pokyny tretích strán, ktoré regulujú interakciu hráčov. V tomto prípade dohody alebo pokyny nemusia byť povinné, ale ak sa odporúča hrať Nashovu rovnováhu, potom žiadny z hráčov nemá túžbu (sám) odchýliť sa od predpísaného správania. Je jasné, že takýto scenár nie je možný v každej situácii. Okrem toho sa súčasťou hry môže stať aj samotný proces vytvárania dohody alebo zapojenia tretích strán.

Nakoniec, tretia prirodzená otázka, ktorá vyvstáva pri štúdiu konceptu Nashovej rovnováhy, je nasledujúca: existujú empirické dôkazy, že skutoční hráči si zvyčajne vyberajú rovnovážne stratégie? Aj tu je mimoriadne ťažké dať stručnú a jednoznačnú odpoveď. Povaha problémov, ktoré vznikajú, je zároveň viac v súlade s témami experimentálnej ekonómie. Preto sa obmedzíme len na odporúčanie obrátiť sa na odbornú literatúru, napríklad na knihu, kde je výborne rozobratá problematika experimentálnej metodológie a prezentované množstvo výsledkov.

Existujú hry, ktoré nemajú čisté strategické rovnováhy (pozri príklad 3.1), a tak vzniká otázka: aké podmienky sú dostatočné na to, aby takáto rovnováha existovala? Sformulujme a dokážme tvrdenie o existencii Nashovej rovnováhy v čistých stratégiách v hrách, ktoré nie sú konečné.

Vyhlásenie 2.3. Ak sú sady stratégií pre každého hráča S t sú neprázdne konvexné kompaktné sady v euklidovskom priestore a výplatná funkcia každého hráča a- nepretržitý v s a je kvázi-konkávna v 5, potom má hra Nashovu rovnováhu v čistých stratégiách.

Dôkaz. Pripomeňme si formuláciu Kakutaiove vety, ktorý použijeme pri dôkaze. Nechaj X- neprázdny konvexný kompaktný zasadený v Rn, X* je množina jeho podmnožín a/ je horné polospojité zobrazenie z X V X*,že za každý bod x e X kopa f(x) neprázdne, uzavreté a konvexné. Potom má mapovanie / pevný bod.

Myšlienkou dokázať naše tvrdenie je vytvoriť mapovanie, ktoré spĺňa podmienky Kakutaniho vety. Aby sme to dosiahli, mierne predefinujme zobrazenie najlepšej odpovede. Predpokladajme čisto technicky, že najlepšia odpoveď závisí nielen od stratégií ostatných hráčov, ale aj od vlastnej stratégie hráča s y (s). So zmenou vlastnej stratégie hráča, vzhľadom na pevné stratégie ostatných hráčov, sa najlepšia odpoveď samozrejme nezmení. Teraz predstavíme notáciu, ktorá zobrazí najlepšiu odpoveď pre všetkých hráčov ako karteziánsky produkt s(s) = s,(s) x s2(s) x... x s n (s). Toto mapovanie priraďuje každému profilu množinu profilov, v ktorých má každý hráč najlepšia cesta reaguje na stratégie ostatných hráčov. Pevný bod mapovania S, t.j. profilu s také že s e s(s)> podľa definície je Nashova rovnováha. Ukážme, že zobrazenie 5 spĺňa podmienky Kakutaniho vety. Overenie každej podmienky bude predstavovať samostatný dôkazný bod.

• 1. Ukážme, že množina S všetky profily - konvexné kompaktné. Keďže množina stratégií každého z hráčov S je neprázdna konvexná kompaktná množina, potom karteziánsky súčin S = S t X S 2 X...x S n je konvexný kompakt.
• 2. Displej s má neprázdne obrázky. Podľa Weierstrassovej vety spojitá funkcia a- dosiahne svoj cieľ na uzavretej ohraničenej množine 5 maximálna hodnota. teda s má neprázdne obrázky.
• 3. Zobrazte obrázky s uzavreté a konvexné. Keďže výplatná funkcia každého hráča je u t kvázi konkávne v s ak potom vlastnosťou kvázikonkávnej funkcie množina $. = (s. | u t (s i9 s .) > k) pri pevnom s .a k uzavretý, ak je definičný obor uzavretý a konvexný, ak nie je prázdny. Keďže toto platí pre každého k, potom tiež platí, že množina 5. = (5/1 u t(s", 5 ,) > max. hm. (s., s .)}

konvexné. Ale potom karteziánsky súčin 5(5) = s x (s) X s 2(S) x... X s n CS) je uzavretý a konvexný.

4. Ukážme, že mapovanie § polosúvislý zhora. Používame podmienku spojitosti funkcie a od s. Dokážeme to protirečením. Predpokladajme, že mapovanie § ns je horná polospojitá. Potom sú tu sekvencie strategických profilov s m A s m Kde T -číslo sekvenčného prvku, také, že pre ľubovoľné T s"" e S, s m e s(s""), lim s"" = s° e S, ale lim s"" = s° g lim s(s""). To znamená, že existuje hra

t~* oo t->/A -? oo

osud, pre ktorý stratégia s f ° nie je najlepšou reakciou na s 0, t.j. existuje stratégia s" také že a,(s", s 0,) > u,(y] s° ;). Potom môžeme nájsť e > 0 také, že m,(s/, s 0 ,) > m, (s ; °, s 0 ,) + Ze, odkiaľ

Keďže podľa podmienky je funkcia m spojitá, lim s m = s°, lim s"" = s°,

m*oo m-*oo

s dostatočne veľkým m správny

Zlúčením nerovností (2.8)-(2.10) do jedného reťazca dostaneme

Zo vzťahov (2.11) vyplýva, že u,(s", s"") > m,(s/", s"") + s, ale to je v rozpore s podmienkou s"" е s(s""), pretože s" poskytuje striktne väčšiu odmenu ako s/", ako odpoveď na s"". Dospeli sme k rozporu. Preto náš pôvodný predpoklad, že mapa s nie je horná polospojitá, bol nesprávny.

Ukázali sme, že mapovanie S spĺňa všetky podmienky Kakutaniho vety, čo znamená, že má pevný bod. Tento pevný bod je Nashova rovnováha. Vyhlásenie 2.3 je dokázané. ?

Najmä vyhlásenie 2.3 zaručuje existenciu Nashovej rovnováhy v príklade 2.7, ale nie v príklade 2.8, kde sú výplatné funkcie hráčov nespojité.

„Príklad z práce.

Matematické metódy a modely v ekonomike

Maticové hry

Úvod

V hospodárskej praxi často vznikajú situácie, v ktorých rôzne strany sledujú rôzne ciele. Napríklad vzťah medzi predávajúcim a kupujúcim, dodávateľom a spotrebiteľom, bankou a vkladateľom atď. Takéto konfliktné situácie vznikajú nielen v ekonomike, ale aj v iných typoch činností. Napríklad pri hraní šachu, dáma, domino, loto atď.

Hra je matematický model konfliktnej situácie zahŕňajúcej najmenej dve osoby s použitím viacerých rôznymi spôsobmi aby ste dosiahli svoje ciele. Hra sa volá parný kúpeľ, ak ide o dvoch hráčov. Hra sa volá antagonistický, ak sa zisk jedného hráča rovná strate druhého hráča. Preto na nastavenie hry stačí nastaviť výherné hodnoty jedného hráča v rôznych situáciách.

Volá sa akákoľvek metóda akcie hráča v závislosti od aktuálnej situácie stratégie. Každý hráč má určitú sadu stratégií. Ak je počet stratégií konečný, potom sa volá hra konečný, inak - nekonečné . Stratégie sú tzv čistý, ak si každý hráč vyberie iba jednu stratégiu špecifickým a nie náhodným spôsobom.

Riešenie hry je zvoliť stratégiu, ktorá vyhovuje stav optimality. Touto podmienkou je, že dostane jeden hráč maximálna výhra, ak sa druhý bude držať svojej stratégie. Naopak, druhý hráč dostáva minimálna strata, ak prvý hráč dodrží svoju stratégiu. Takéto stratégie sú tzv optimálne . teda Cieľom hry je určiť optimálnu stratégiu pre každého hráča.

Čistá strategická hra

Predstavte si hru s dvoma hráčmi A A IN. Predpokladajme, že hráč A Má m stratégií A 1, A 2, …, A m a prehrávač IN Má n stratégií B 1, B 2, …, B n. Budeme predpokladať, že výber hráča A stratégií A i, a hráč IN stratégií Bj jednoznačne určuje výsledok hry, t.j. výhry a ij hráč A a výhry b ij hráč IN. Tu i=1,2,…,m, j=1,2,…,n.

Najjednoduchšia hra s dvoma hráčmi je hra s nulovým súčtom. , tie. hra, v ktorej sú záujmy hráčov priamo protikladné. V tomto prípade sú odmeny hráčov spojené s rovnosťou

b ij =-a ij

Táto rovnosť znamená, že zisk jedného hráča sa rovná strate druhého. V tomto prípade stačí brať do úvahy iba výhru jedného z hráčov, napríklad hráča A.

Každá dvojica stratégií A i A Bj zodpovedá výhre a ij hráč A. Všetky tieto výhry je vhodné zapisovať formou tzv platobná matica

Riadky tejto matice zodpovedajú stratégiám hráča A, a stĺpce – stratégie hráča IN. Vo všeobecnosti sa takáto hra tzv (m×n)-hra.

Príklad 1 Dvaja hráči A A IN hodiť si mincou. Ak sa strany mince zhodujú, vyhráva A, t.j. hráč IN platí hráč A určitú sumu rovnajúcu sa 1 a ak sa nezhodujú, tak vyhráva hráč B, t.j. naopak, hráč A platí hráč IN rovnaké množstvo , rovná 1. Vytvorte platobnú maticu.

Riešenie. Podľa podmienok problému