antagonistična igra. Reševanje matričnih antagonističnih iger Principi reševanja matričnih antagonističnih iger
Teorija iger je teorija matematičnih modelov odločanja v razmerah konflikta ali negotovosti. Predpostavlja se, da so za dejanja udeležencev v igri značilne določene strategije – sklopi akcijskih pravil. Če pridobitev ene strani neizogibno vodi v izgubo druge strani, potem govorimo o antagonističnih igrah. Če je nabor strategij omejen, se igra imenuje matrična igra in rešitev je mogoče dobiti zelo preprosto. Rešitve, pridobljene s pomočjo teorije iger, so uporabne pri snovanju načrtov ob morebitnem nasprotovanju konkurentov ali negotovosti v zunanjem okolju.
Če je bimatrična igra antagonistična, potem je izplačilna matrika igralca 2 popolnoma določena z izplačilno matriko igralca 1 (ustrezna elementa teh dveh matrik se razlikujeta le v predznakih). Zato je bimatrična antagonistična igra popolnoma opisana z eno samo matriko (izplačilna matrika igralca 1) in se zato imenuje matrična igra.
Ta igra je antagonistična. V njem j \u003d x2 - O, P in R (O, O] = H (P, P) \u003d -I in R (O, P) \u003d R (P, O) \u003d 1 ali v matrični obliki o str
Naj bo nek razred iger G "zrcalno zaprt", tj. skupaj z vsako svojo igro vsebuje zrcalno izomorfno igro (ker so vse igre, ki so zrcalno izomorfne dani, izomorfne druga drugi, lahko v skladu s pravkar povedanim govorimo o eni zrcalno izomorfni igri). Tak razred je na primer razred vseh antagonističnih iger ali razred vseh matričnih iger.
Če se spomnimo definicije sprejemljivih situacij v antagonistični igri, dobimo, da je situacija (X, Y) v mešani razširitvi matrične igre sprejemljiva za igralca 1, če in samo če za katero koli x G x neenakost
Proces pretvorbe iger v simetrične se imenuje simetrizacija. Tukaj opisujemo eno metodo simetrizacije. Druga, bistveno drugačna različica simetrizacije bo podana v razdelku 26.7. Obe različici simetrizacije sta dejansko uporabni za poljubne antagonistične igre, vendar bosta formulirani in dokazani samo za matrične igre.
Tako začetni izrazi in poimenovanja teorije splošnih antagonističnih iger sovpadajo z ustreznimi izrazi in poimenovanji teorije matričnih iger.
Za končne antagonistične (matrične) igre smo obstoj teh ekstremov dokazali v 10. poglavju. 1, bistvo pa je bilo vzpostaviti njihovo enakost ali vsaj najti načine za preseganje njihove neenakosti.
Že obravnava matričnih iger pokaže, da v prvotno danih strategijah igralcev obstajajo antagonistične igre brez ravnotežnih situacij (in celo brez e-ravnovesnih situacij za dovolj majhne e > 0).
Toda vsako končno (matrično) igro je mogoče razširiti na neskončno igro, na primer tako, da vsakemu igralcu zagotovite poljubno število prevladujočih strategij (glejte 22. poglavje 1). Očitno takšna razširitev igralčevega nabora strategij v resnici ne bo pomenila razširitve njegovih možnosti in njegovo dejansko vedenje v razširjeni igri se ne bi smelo razlikovati od njegovega vedenja v izvirni igri. Tako smo takoj dobili zadostno število primerov neskončnih antagonističnih iger, ki nimajo sedlišč. Obstajajo tudi tovrstni primeri.
Tako je za izvajanje načela maximina v neskončni antagonistični igri potrebno, tako kot v primeru končne (matrične) igre, nekaj razširitve strateških zmožnosti igralcev. Za 96
Tako kot v primeru matričnih iger (glej pogl. 1, 17) ima tudi pri splošnih antagonističnih igrah pomembno vlogo koncept spektra mešane strategije, ki pa ga je tu treba bolj splošno opredeliti.
Na koncu upoštevajte, da je nabor vseh mešanih strategij igralca 1 v poljubni antagonistični igri, kot v matriki
Tudi upoštevanje antagonističnih iger kaže, da veliko število takšnih iger, vključno s končnimi, matričnimi igrami, nimajo ravnotežnih situacij v prvotnih, čistih strategijah, ampak le v posplošenih, mešanih strategijah. Zato je za splošne, neantagonistične, nekooperativne igre naravno iskati ravnotežne situacije ravno v mešanih strategijah.
Tako smo na primer (glej sliko 3.1) že ugotovili, da se "izvajalec" skoraj nikoli ne spopada z vedenjsko negotovostjo. Če pa vzamemo konceptualno raven tipa "Administrator", potem je vse ravno obratno. Praviloma je glavna vrsta negotovosti, s katero se mora tak "naš odločevalec" soočiti, "konflikt". Zdaj lahko pojasnimo, da gre običajno za nestrogo rivalstvo. Nekoliko redkeje se »Administrator« odloča v pogojih »naravne negotovosti«, še redkeje pa naleti na strog, antagonističen konflikt. Poleg tega se navzkrižje interesov pri odločanju "Administratorja" zgodi tako rekoč "enkrat", tj. po naši klasifikaciji pogosto igra le eno (včasih zelo majhno število) iger igre. Lestvice za ocenjevanje posledic so pogosteje kvalitativne kot kvantitativne. Strateška neodvisnost "Administratorja" je precej omejena. Ob upoštevanju zgoraj navedenega je mogoče trditi, da je treba problemske situacije te velikosti najpogosteje analizirati z uporabo nekooperativnih neantagonističnih dvomatričnih iger, poleg tega v čistih strategijah.
Načela za reševanje matričnih antagonističnih iger
Posledično je razumno pričakovati, da se bodo nasprotniki v zgoraj opisani igri držali svojih izbranih strategij. Matrična antagonistična igra, za katero je max min fiv = min max Aiy>
Vendar pa niso vse matrične antagonistične igre povsem določene in v splošnem primeru
Tako je v splošnem primeru za rešitev matrične antagonistične igre dimenzije /uxl potrebno rešiti par problemov dvojnega linearnega programiranja, kar ima za posledico niz optimalnih strategij / in stroške igre v.
Kako je definirana matrična antagonistična igra dveh oseb?
Kakšne so metode za poenostavitev in reševanje matričnih antagonističnih iger
V primeru igre dveh oseb je naravno, da se njuni interesi obravnavajo kot neposredno nasprotni - igra je antagonistična. Tako je izkupiček enega igralca enak izgubi drugega (vsota izplačil obeh igralcev je nič, od tod tudi ime, igra z ničelno vsoto). Upoštevali bomo igre, v katerih ima vsak igralec končno število alternativ. Funkcijo izplačila za takšno igro dveh oseb z ničelno vsoto je mogoče podati v matrični obliki (v obliki matrike izplačil).
Kot smo že omenili, se zadnja antagonistična igra imenuje matrika.
MATRIČNE IGRE - razred antagonističnih iger, v katerih sodelujeta dva igralca, vsak igralec pa ima končno število strategij. Če ima en igralec m strategij in drugi igralec n strategij, potem lahko sestavimo matriko igre dimenzije txn. M.i. lahko ima ali ne sme imeti sedla. V slednjem primeru
Moskovski inštitut za elektrotehniko
(Tehnična univerza)
Laboratorijski izvid
v teoriji iger
"Iskalni program za optimalne strategije za seznanjeno antagonistično igro, podano v matrični obliki"
Izpolnili učenci
skupina A5-01
Ašrapov Daler
Olga Ašrapova
Osnovni koncepti teorije iger
Teorija iger, zasnovana za razrešitev konfliktne situacije , tj. situacije, v katerih nasprotujejo interesi dveh ali več strani, ki zasledujejo različne cilje.
Če so cilji strank neposredno nasprotni, potem govorijo o antagonistični konflikt .
igra imenujemo poenostavljen formaliziran model konfliktne situacije.
Igranje igre enkrat od začetka do konca se imenuje zabava . Rezultat zabave je plačilo (oz zmaga ).
Stranko sestavljajo premika , tj. izbiranje igralcev iz nabora možnih alternativ.
Premiki so lahko osebno in naključen.osebna poteza , Za razliko od naključen , pomeni igralčevo zavestno izbiro neke možnosti.
Igre, v katerih je vsaj ena osebna poteza, se imenujejo strateško .
Igre, v katerih so vse poteze naključne, se imenujejo igre na srečo .
Pri osebni potezi spregovorijo tudi o strategije igralec, tj. o pravilu ali nizu pravil, ki določajo izbiro igralca. Hkrati naj bo strategija celovita, tj. izbira mora biti določena za vsako možno situacijo med potekom igre.
Izziv teorije iger– iskanje optimalnih strategij igralcev, tj. strategije, ki jim zagotavljajo največji dobiček ali najmanjšo izgubo.
Klasifikacija teoretičnih modelov iger
igra n osebe se običajno imenujejo, kje 
je množica strategij i-tega igralca, 
- plačilo igre.
V skladu s to oznako je mogoče predlagati naslednjo klasifikacijo teoretičnih modelov iger:
Diskretni (nabori strategij 
diskretno)
Končno
Neskončno
Neprekinjeno (nabori strategij 
neprekinjeno)
Neskončno
n osebe ( 
)
Koalicija (zadruga)
nekooperativen (nesodelujoč)
2 osebi (v paru)
Antagonistične (igre z ničelno vsoto)
(interesi strank so nasprotni, tj. izguba enega igralca je enaka dobičku drugega)
Neantagonistično
S popolnimi informacijami (če igralec, ki dela osebno potezo, pozna celotno zgodovino igre, tj. vse poteze nasprotnika)
Z nepopolnimi informacijami
Z ničelnim zneskom (skupno plačilo je nič)
Z vsoto, ki ni nič
Enosmerna (loterija)
večsmerni
Matrična predstavitev antagonistične igre v paru
V tej vadnici bomo razmislili antagonistične igre dveh oseb
podan v matrični obliki. To pomeni, da poznamo nabor strategij prvega igralca (player A){
A jaz },
jaz = 1,…,
m in nabor strategij drugega igralca (player B){
B j },
j = 1,...,
n, in matriko A
= ||
a ij ||
izplačila prvega igralca. Ker govorimo o antagonistični igri, se predpostavlja, da je dobiček prvega igralca enak izgubi drugega. Menimo, da je matrični element a ij je izplačilo prvega igralca, ko izbere strategijo A jaz in odgovor drugega igralca s strategijo B j. Takšno igro bomo označili kot 
, kje m
- število strategij igralcev AMPAK,n
- število strategij igralcev AT. Na splošno ga lahko predstavi naslednja tabela:
|
B 1 |
|
B j |
|
B n |
|
|
A 1 |
|
| |||
|
|
|
|
|
|
|
|
A jaz |
|
| |||
|
|
|
|
|
|
|
|
A m |
|
|
Primer 1
Kot preprost primer razmislite o igri, v kateri je igra sestavljena iz dveh potez.
1. poteza: igralec AMPAK izbere eno od številk (1 ali 2), ne da bi o svoji izbiri povedal nasprotniku.
2. poteza: igralec AT izbere eno izmed številk (3 ali 4).
Izid: Izbira igralca AMPAK in AT seštejte. Če je vsota soda, potem AT plača svojo vrednost igralcu AMPAK, če je liho - obratno, AMPAK plača igralca AT.
To igro lahko predstavljamo kot 
na naslednji način:
|
|
|
|
|
| ||
|
|
(izbira 3)
(izbira 4)
(izbira 1)
(izbira 2)To je enostavno videti ta igra je antagonistična, poleg tega je igra s nepopolnimi informacijami, saj igralec AT, naredil osebno potezo, ni znano, kakšno izbiro je igralec izbral AMPAK.
Kot je navedeno zgoraj, je naloga teorije iger najti optimalne strategije igralcev, tj. strategije, ki jim zagotavljajo največji dobiček ali najmanjšo izgubo. Ta proces se imenuje odločitev o igri .
Pri reševanju igre v matrični obliki je treba preveriti prisotnost igre sedlo . Za to sta uvedeni dve vrednosti:
je spodnja meja za ceno igre in
je zgornja ocena cene igre.
Prvi igralec bo najverjetneje izbral tisto strategijo, pri kateri bo med vsemi možnimi odgovori drugega igralca dosegel največji dobiček, drugi pa bo, nasprotno, izbral tisto, ki minimizira lastno izgubo, tj. morebitno zmago prvega.
To je mogoče dokazati α ≤ V ≤ β , kje V–cena igre , tj. verjeten izkupiček prvega igralca.
Če razmerje α
=
β
=
V, potem pravijo, da igra ima sedlo
, in rešujejo v čistih strategijah
. Z drugimi besedami, obstaja nekaj strategij 
, ki daje igralcu AMPAKV.
Primer 2
Vrnimo se k igri, ki smo jo obravnavali v primeru 1, in jo preverimo glede prisotnosti sedla.
|
|
|
|
|
|
| |||
|
| |||
|
|
(izbira 3)
(izbira 4)
(izbira 1)
(izbira 2)
Za to igro 
=
-5,
=
4,
, torej nima sedla.
Še enkrat, upoštevajte, da je ta igra igra nepopolnih informacij. V tem primeru lahko igralcu le svetuješ AMPAK izberite strategijo 
, Ker v tem primeru lahko dobi največje izplačilo, vendar pod pogojem, da se igralec odloči AT strategije 
.
Primer 3
Naredimo nekaj sprememb v pravilih igre iz primera 1. Dajmo igralca AT informacije o izbiri igralca AMPAK. Potem AT Obstajata dve dodatni strategiji:
- strategijo, ki je koristna za AMPAK.Če izbira A - 1, potem AT izbere 3 po izbiri A - 2, potem AT izbere 4;
- strategija, ki ni koristna za AMPAK.Če izbira A - 1, potem AT izbere 4 po izbiri A - 2, potem AT izbere 3.
|
|
|
|
|
|
|
|
| |||||
|
| |||||
|
|
(izbira 3)
(izbira 4)
(izbira 1)
(izbira 2)
Ta igra je polna informacij.
V tem primeru 
=
-5,
=
-5,
, zato ima igra sedlo 
. Ta sedlna točka ustreza dvema paroma optimalnih strategij: 
in 
. Cena igre V= -5.
Očitno je, da za AMPAK ta igra je neuporabna.
Primera 2 in 3 sta dobra ilustracija naslednjega izreka, dokazanega v teoriji iger:
1. izrek
Vsaka seznanjena antagonistična igra s popolnimi informacijami je rešena v čistih strategijah.
to. Izrek 1 pravi, da ima vsaka igra za dve osebi s popolnimi informacijami sedlo in da obstaja par čistih strategij 
, ki daje igralcu AMPAK trajnostni dobiček, ki je enak ceni igre V.
V primeru odsotnosti sedla je t.i mešane strategije
:, kje str jaz inq j so verjetnosti izbire strategij A jaz
in
B j prvi oziroma drugi igralec. Rešitev igre v tem primeru je par mešanih strategij 
maksimiranje matematičnega pričakovanja cene igre.
Posplošitev izreka 1 na primer igre z nepopolnimi informacijami je naslednji izrek:
2. izrek
Vsaka antagonistična igra v paru ima vsaj eno optimalno rešitev, t.j. par mešanih strategij v splošnem primeru. 
, ki daje igralcu AMPAK trajnostni dobiček, ki je enak ceni igre V, poleg tega α ≤
V ≤
β
.
V posebnem primeru, za igro s sedlo, je rešitev v mešanih strategijah videti kot par vektorjev, v katerih je en element enak ena, ostali pa so enaki nič.
Najenostavnejši primer, ki je podrobno razdelan v teoriji iger, je igra končnih parov z ničelno vsoto (antagonistična igra dveh oseb ali dveh koalicij). Razmislite o tej igri G, v katerem dva igralca AMPAK in AT, imajo nasprotne interese: dobiček enega je enak izgubi drugega. Od izplačila igralca AMPAK je enak izplačilu igralca V z v nasprotnem predznaku nas lahko zanima samo izplačilo a igralec AMPAK. seveda, AMPAKželi maksimirati in V - minimizirati a. Za poenostavitev se miselno identificirajmo z enim od igralcev (naj bo AMPAK) in ga bomo imenovali "mi", in igralec V -"nasprotnik" (seveda brez pravih prednosti za AMPAK iz tega ne sledi). Pustite nam t možne strategije AMPAK 1 , A 2 , ..., AMPAK m, in sovražnik n možne strategije AT 1 , AT 2 , ..; AT n(takšna igra se imenuje igra t × n). Označimo a ij naše izplačilo, če uporabimo strategijo A jaz , in sovražnik je strategija B j .
Tabela 26.1
|
A jaz B j |
B 1 |
B 2 |
B n |
|
|
A 1 A 2 A m |
a 11 a 21 a m1 |
a 21 a m |
a 1 n a 2 n a mn |
Recimo, da je za vsak par strategij A<, AT, zmaga (ali povprečna zmaga) a, j vemo. Nato je načeloma možno sestaviti pravokotno tabelo (matriko), v kateri so navedene strategije igralcev in pripadajoči izkupički (glej tabelo 26.1).
Če je taka tabela sestavljena, potem pravimo, da je igra G zreducirano na matrično obliko (samo po sebi je lahko spraviti igro v takšno obliko že težka naloga, včasih pa skoraj nemogoča zaradi ogromnega števila strategij). Upoštevajte, da če je igra zmanjšana na matrično obliko, potem je igra z več potezami dejansko zmanjšana na igro z eno potezo - igralec mora narediti samo eno potezo: izbrati strategijo. Na kratko bomo označili matrico igre ( a ij).
Razmislite o primeru igre G(4×5) v matrični obliki. Na voljo imamo (na izbiro) štiri strategije, sovražnik ima pet strategij. Matrica igre je podana v tabeli 26.2
Pomislimo, kakšno strategijo imamo (igralec AMPAK) izkoristiti? Matrix 26.2 ima vabljivo izplačilo "10"; vleče nas k izbiri strategije AMPAK 3 , pri katerem bomo dobili tole "sladico". Toda počakaj, tudi sovražnik ni neumen! Če izberemo strategijo AMPAK 3 , on nam bo navkljub izbral strategijo AT 3 , in dobimo neko mizerno plačilo "1". Ne, izberite strategijo AMPAK 3 je prepovedano! Kako biti? Očitno moramo na podlagi načela previdnosti (in to je glavno načelo teorije iger) izbrati
Tabela 26.2
|
B j A jaz |
B 1 |
B 2 |
B 3 |
B 4 |
B 5 |
|
A 1 A 2 A 3 A 4 |
strategija, ki naš minimalni dobiček je največji. To je tako imenovani "načelo minimaksa": ravnaj tako, da z najslabšim vedenjem sovražnika zate dosežeš največjo korist.
Prepišemo tabelo 26.2 in v desni dodatni stolpec zapišemo minimalno vrednost izplačila v vsaki vrstici, (vrstica minimum); določimo ga za jaz- vrstica α jaz(glej tabelo 26.3).
Tabela 26.3
|
B j A jaz |
B 1 |
B 2 |
B 3 |
B 4 |
B 5 | |
|
A 1 A 2 A 3 A 4 | ||||||
|
β j |
Vseh vrednot α jaz(desni stolpec) največji (3) je označen. Ujema se s strategijo Aštiri . Ko smo izbrali to strategijo, smo v vsakem primeru lahko prepričani, da (za kakršno koli vedenje sovražnika) ne bomo pridobili manj kot 3. Ta vrednost je naš zajamčeni dobiček; pazimo, ne moremo dobiti manj od tega (lahko dobim več). To izplačilo se imenuje nižja cena igre (ali "maximin" - največje izmed najmanjših izplačil). Označili ga bomo a. V našem primeru α = 3.
Zdaj pa zavzemimo stališče sovražnika in se zagovarjajmo. Ni nekakšen pajdaš, ampak tudi razumen! Pri izbiri strategije bi rad dal manj, a mora računati na naše vedenje, kar je zanj najslabše. Če izbere strategijo AT 1 , mu bomo odgovorili AMPAK 3 , in dal bo 10; če se odloči B 2 - mu bomo odgovorili AMPAK 2 , in bo dal 8 itd. Tabeli 26.3 dodamo dodatno spodnjo vrstico in vanjo zapišemo maksimume stolpcev β j. Očitno bi moral previden nasprotnik izbrati strategijo, ki minimizira to vrednost (ustrezna vrednost 5 je označena v tabeli 26.3). Ta vrednost β je vrednost dobitka, več od katere nam razumen nasprotnik zagotovo ne bo dal. Imenuje se zgornja cena igre (ali "minimax" - najmanjši od največjih dobitkov). V našem primeru je β = 5 in je dosežen z nasprotnikovo strategijo B 3 .
Torej, na podlagi načela previdnosti (pravilo pozavarovanja »vedno računaj na najslabše!«) moramo izbrati strategijo AMPAK 4 , in sovražnik - strategija AT 3 . Takšne strategije se imenujejo "minimax" (izhaja iz načela minimax). Dokler se obe strani v našem primeru držita svojih minimax strategij, bo izplačilo a 43 = 3.
Zdaj pa si za trenutek predstavljajte, da smo izvedeli, da sovražnik sledi strategiji AT 3 . Daj no, kaznovajmo ga za to in izberimo strategijo AMPAK 1 - dobili jih bomo 5, kar ni tako slabo. A konec koncev tudi sovražnik ni miss; naj ve, da je naša strategija AMPAK 1 ; tudi hitro izbira AT 4 , znižanje našega izplačila na 2 itd. (partnerji so »hiteli s strategijami«). Z eno besedo, minimax strategije v našem primeru nestabilen glede na do informacije o ravnanju nasprotne stranke; te strategije nimajo lastnosti ravnovesja.
Je vedno tako? Ne ne vedno. Razmislite o primeru z matriko, podano v tabeli 26.4.
V tem primeru je spodnja cena igre enaka zgornji: α = β = 6. Kaj iz tega sledi? Minimax igralne strategije AMPAK in AT bo vzdržen. Dokler se jih oba igralca držita, je izkupiček 6. Poglejmo, kaj se zgodi, če se (AMPAK) vedeti, da sovražnik (AT)
Tabela 26.4
|
Bj A jaz |
B 1 |
B 2 |
B 3 |
B 4 | |
|
A 1 A 2 A 3 | |||||
|
β j |
drži se strategije B 2 ? In prav nič se ne bo spremenilo. Ker vsako odstopanje od strategije AMPAK 2 lahko naš položaj samo poslabša. Prav tako informacije, ki jih prejme sovražnik, ne bodo povzročile, da bi se umaknil iz svoje strategije. AT 2 . Par strategij AMPAK 2 , B 2 ima lastnost ravnovesja (uravnotežen par strategij), izkupiček (v našem primeru 6), dosežen s tem parom strategij, pa se imenuje "sedlišče matrike" 1). Znak prisotnosti sedla in uravnoteženega para strategij je enakost spodnje in zgornje cene igre; skupna vrednost α in β se imenuje cena igre. Označili ga bomo v:
α = β = v
strategije A jaz , B j(v tem primeru AMPAK 2 , AT 2 ), za katere je ta izkupiček dosežen, se imenujejo optimalne čiste strategije, njihova celota pa se imenuje rešitev igre. V tem primeru naj bi bila igra sama rešena v čistih strategijah. Obe strani AMPAK in AT lahko navedemo njihove optimalne strategije, pri katerih je njihov položaj najboljši možni. Kaj je igralec AMPAK v tem primeru zmaga 6 in igralec V - izgubi 6, - no, To so pogoji igre: koristni so za AMPAK in neugodno za AT
1) Izraz "sedlska točka" je vzet iz geometrije - tako se imenuje točka na površini, kjer sta istočasno dosežena minimum na eni koordinati in maksimum na drugi.
Bralec se lahko vpraša: zakaj se optimalne strategije imenujejo "čiste"? Če pogledamo malo naprej, odgovorimo na to vprašanje: obstajajo "mešane" strategije, ki so sestavljene iz dejstva, da igralec ne uporablja ene strategije, ampak več, ki jih naključno izmenjujejo. Torej, če dovolimo poleg čistih tudi mešane strategije, poljubne konec igre ima rešitev – ravnotežno točko. Ampak še vedno govorimo o atomu.
Prisotnost sedla v igri še zdaleč ni pravilo, temveč je izjema. Večina iger nima sedla. Vendar pa obstaja vrsta iger, ki imajo vedno sedlo in se zato rešujejo v čistih strategijah. To so tako imenovane »igre s popolnimi informacijami«. Igra s polico informacij je igra, pri kateri vsak igralec ob vsaki osebni potezi pozna celotno zgodovino svojega razvoja, torej rezultate vseh prejšnjih potez, osebnih in naključnih. Primeri iger s popolnimi informacijami so dama, šah, tic-tac-toe itd.
V teoriji iger je to dokazano vsaka igra s popolnimi informacijami ima sedlo, in jih je zato mogoče rešiti v čistih strategijah. V vsaki igri s popolnimi informacijami obstaja par optimalnih strategij, ki zagotavlja stabilen izkupiček, enak verigi igre v. Če je taka igra sestavljena le iz osebnih potez, potem se mora, ko vsak igralec uporabi svojo optimalno strategijo, končati na povsem določen način - z izplačilom, ki je enako ceni igre. Torej, če je rešitev igre znana, sama igra izgubi smisel!
Vzemimo elementarni primer igre s popolnimi informacijami: dva igralca izmenično polagata niklja na okroglo mizo, pri čemer poljubno izbereta položaj središča kovanca (medsebojno prekrivanje kovancev ni dovoljeno). Zmagovalec je tisti, ki vloži zadnji peni (če za druge ni prostora). Zlahka je videti, da je izid te igre v bistvu vnaprej določen. Obstaja določena strategija, ki zagotavlja, da igralec, ki prvi položi kovanec, zmaga. Namreč, najprej mora postaviti nikelj na sredino mize, nato pa na vsako potezo nasprotnika odgovoriti s simetrično potezo. Očitno se nasprotnik ne more izogniti porazu, ne glede na to, kako se obnaša. Povsem enako je s šahom in igrami s popolnimi informacijami nasploh: vsaka od njih, zapisana v matrični obliki, ima sedlo, zato je rešitev v čistih strategijah in je zato smiselna le, dokler ta rešitev ni najdena. Recimo tudi šahovska partija nenehno konča z zmago belih, oz nenehno -črni zmaga, oz nenehno - remijem, le s čim točno - še ne vemo (na srečo ljubiteljev šaha). Naj dodamo še nekaj: tega v doglednem času ne bomo izvedeli, saj je število strategij tako ogromno, da je izjemno težko (če ne nemogoče) igro reducirati na matrično obliko in v njej najti sedlo.
Sedaj pa se vprašajmo, kaj storiti, če igra nima sedla: α ≠ β ? No, če je vsak igralec prisiljen izbrati eno - edino čisto strategijo, potem ni kaj storiti: voditi se mora načelo minimax. Druga stvar je, če je mogoče "zmešati" niz strategij, ki se naključno izmenjujejo z nekaj verjetnostmi. Uporaba mešanih strategij je zasnovana na ta način: igra se večkrat ponovi; pred vsako partijo igre, ko igralec dobi osebno potezo, svojo izbiro "zaupa" naključju, "vrže žreb" in izbere izpadlo strategijo (žreb vemo že iz prejšnjega poglavja ).
Mešane strategije v teoriji iger so model spremenljivih, fleksibilnih taktik, ko nobeden od igralcev ne ve, kako se bo nasprotnik obnašal v dani igri. Ta taktika (čeprav običajno brez matematične utemeljitve) se pogosto uporablja v igrah s kartami. Naj hkrati opozorimo, da je najboljši način, da skrijete svoje vedenje pred sovražnikom, da mu date naključen značaj in zato ne veste vnaprej, kaj boste storili.
Torej, pogovorimo se o mešanih strategijah. Označili bomo mešane strategije igralcev AMPAK in AT oz S A = ( str 1 , R 2 , ..., str m), S B = (q 1 , q 2 , …, q n), kje str 1 , str 2 , …, str m(skupaj ena) - verjetnosti igralčeve uporabe AMPAK strategije AMPAK 1 , A 2 ,… , A m ; q 1 , q 2 , …, q n- verjetnosti uporabe s strani igralca AT strategije AT 1 , AT 2 , ..., AT n . V posameznem primeru, ko so vse verjetnosti, razen ene, enake nič, ta pa je enaka 1, se mešana strategija spremeni v čisto.
Obstaja osnovni izrek teorije iger: katera koli končna igra z ničelno vsoto za dve osebi ima vsaj eno rešitev - par optimalnih strategij, na splošno mešanih 
in temu primerno ceno v.
Par optimalnih strategij 
oblikovanje rešitve igre ima naslednje lastnosti: če se eden od igralcev drži svoje optimalne strategije, potem drugemu ne more biti donosno odstopati od svoje. Ta par strategij tvori nekakšno ravnotežje v igri: en igralec želi pridobitev obrniti na maksimum, drugi na minimum, vsak vleče v svojo smer in ob razumnem vedenju obeh se vzpostavita ravnotežje in stabilen dobiček. v.Če v > 0, potem je igra za nas donosna, če v<
0
-
za sovražnika; pri v= 0 je igra »poštena«, enako koristna za oba udeleženca.
Razmislite o primeru igre brez sedla in podajte (brez dokaza) njeno rešitev. Igra je naslednja: dva igralca AMPAK in AT istočasno in brez besed pokažite enega, dva ali tri prste. O zmagi odloča skupno število prstov: če je sodo, zmaga AMPAK in prejema od AT znesek, ki je enak tej številki; če je liho, potem obratno AMPAK plača AT znesek, ki je enak temu številu. Kaj naj naredijo igralci?
Ustvarimo matrico igre. V eni igri ima vsak igralec tri strategije: pokaži enega, dva ali tri prste. Matrika 3 × 3 je podana v tabeli 26.5; dodatni desni stolpec prikazuje minimume vrstic, dodatna spodnja vrstica pa prikazuje maksimume stolpcev.
Nižja cena igre α = - 3 in ustreza strategiji A 1 . To pomeni, da si z razumnim, previdnim ravnanjem zagotovimo, da ne bomo izgubili več kot 3. Slaba tolažba, a vseeno boljša kot recimo dobitek 5, ki se pojavi v nekaterih celicah matrike. Slabo za nas, igralca AMPAK ... A naj se potolažimo:
zdi se, da je nasprotnikov položaj še slabši: nižji strošek igre je β = 4, tj. ob razumnem vedenju nam bo dal vsaj 4. Na splošno položaj ni zelo dober - ne za enega ne za druga stran. Toda poglejmo, ali je to mogoče izboljšati? Izkazalo se je, da lahko. Če vsaka stran ne uporablja ene čiste strategije, ampak mešano, v kateri
Tabela 26.5
|
Bj A jaz |
B 1 |
B 2 |
B 3 | |
|
A 1 A 2 A 3 | ||||
|
β j |
prvi in tretji vstopita z verjetnostjo 1/4, drugi pa z verjetnostjo 1/2, tj.
potem bo povprečni izkupiček enakomerno enak nič (kar pomeni, da je igra "poštena" in enako koristna za obe strani). strategije 
oblika rešitve igre in njena cena v= 0. Kako smo našli to rešitev? To je drugo vprašanje. V naslednjem razdelku pokažemo, kako se na splošno rešujejo končne igre.
Razmislite o igri parov s končno ničelno vsoto. Označimo z a igralčev izkupiček A, in skozi b- zmaga igralca B. Ker a = –b, potem pri analizi takšne igre ni treba upoštevati obeh teh številk - dovolj je, da upoštevamo izplačilo enega od igralcev. Naj bo npr. A. V nadaljevanju, za lažjo predstavitev, stran A bomo pogojno imenovali " mi"in stran B – "sovražnik".
Pustite nam m možne strategije A 1 , A 2 , …, A m, in sovražnik n možne strategije B 1 , B 2 , …, B n(takšna igra se imenuje igra m×n). Predpostavimo, da je vsaka stran izbrala določeno strategijo: mi smo izbrali Ai, nasprotnik Bj. Če je igra sestavljena samo iz osebnih potez, potem izbira strategij Ai in Bj enolično določa izid igre – naš izkupiček (pozitiven ali negativen). Označimo ta dobiček kot aij(zmaga, ko izberemo strategijo Ai, in sovražnik - strategije Bj).
Če igra poleg osebnih naključnih potez vsebuje izplačilo za par strategij Ai, Bj je naključna spremenljivka, ki je odvisna od rezultatov vseh naključnih potez. V tem primeru je naravna ocena pričakovanega izplačila matematično pričakovanje naključnega dobitka. Za udobje bomo označili z aij tako sam izkupiček (v igri brez naključnih potez) kot njegovo matematično pričakovanje (v igri z naključnimi potezami).
Recimo, da poznamo vrednosti aij za vsak par strategij. Te vrednosti lahko zapišemo kot matriko, katere vrstice ustrezajo našim strategijam ( Ai), stolpci pa prikazujejo nasprotnikove strategije ( Bj):
| B j A i | B 1 | B 2 | … | B n |
| A 1 | a 11 | a 12 | … | a 1n |
| A 2 | a 21 | a 22 | … | a 2n |
| … | … | … | … | … |
| A m | a m 1 | a m 2 | … | amn |
Takšna matrika se imenuje izplačilna matrika igre ali preprosto igralna matrica.
Upoštevajte, da je izdelava izplačilne matrike za igre z velikim številom strategij lahko težka naloga. Na primer za igra šahaŠtevilo možnih strategij je tako veliko, da je konstrukcija izplačilne matrike praktično nemogoča. Vendar pa je načeloma vsako končno igro mogoče reducirati na matrično obliko.
Razmislite primer 1 4×5 antagonistična igra. Na voljo imamo štiri strategije, sovražnik ima pet strategij. Matrica igre je naslednja:
| B j A i | B 1 | B 2 | B 3 | B 4 | B 5 |
| A 1 | |||||
| A 2 | |||||
| A 3 | |||||
| A 4 |
Kakšno strategijo naj uporabimo (tj. igralec A) uporabiti? Ne glede na to, katero strategijo izberemo, bo razumni nasprotnik nanjo odgovoril s strategijo, za katero bo naš izkupiček minimalen. Na primer, če izberemo strategijo A 3 (v skušnjavi z zmago 10), bo nasprotnik kot odgovor izbral strategijo B 1 in naš dobiček bo samo 1. Očitno moramo na podlagi načela previdnosti (in to je glavno načelo teorije iger) izbrati strategijo, v kateri naš minimalni dobiček je največji.
Označimo z a i minimalna vrednost izplačila za strategijo Ai:
in v matriko igre dodajte stolpec, ki vsebuje te vrednosti:
| B j A i | B 1 | B 2 | B 3 | B 4 | B 5 | najmanj v vrsticah a i | |
| A 1 | |||||||
| A 2 | |||||||
| A 3 | |||||||
| A 4 | maksimin |
Pri izbiri strategije moramo izbrati tisto, za katero vrednost a i maksimum. To največjo vrednost označimo z α :
Vrednost α klical nižja cena igre oz maksimin(največji minimalni dobitek). Strategija igralca A ki ustreza maksiminu α , je poklican maximin strategija.
V tem primeru maksimin α je enaka 3 (ustrezna celica v tabeli je označena s sivo), maksimin strategija pa je Aštiri . Ko smo izbrali to strategijo, smo lahko prepričani, da bomo za kakršno koli vedenje sovražnika zmagali nič manj kot 3 (in morda več z "nerazumnim" vedenjem sovražnika). Ta vrednost je naš zajamčeni minimum, ki ga lahko zagotovimo za sami, pri čemer se držimo najprevidnejše ("pozavarovalne") strategije.
Zdaj bomo podobno sklepanje izvedli za sovražnika B B A B 2 - odgovorili mu bomo A .
Označimo z βj A B) za strategijo Ai:
βj β :
7. KAJ JE IGRA ZGORNJE VREDNOSTI Zdaj bomo izvedli podobno sklepanje za nasprotnika B. Zanima ga, da minimizira naš dobiček, torej da nam da manj, vendar mora računati na naše vedenje, ki je zanj najslabše. Na primer, če izbere strategijo B 1 , potem mu bomo odgovorili s strategijo A 3 , dal pa nam bo 10. Če se odloči B 2 - odgovorili mu bomo A 2 in bo dal 8 itd.. Očitno mora previden nasprotnik izbrati strategijo, v kateri naš največji dobiček bo minimalen.
Označimo z βj največje vrednosti v stolpcih matrike izplačil (največji izkupiček igralca A, ali, kar je isto, največja igralčeva izguba B) za strategijo Ai:
in v matriko igre dodajte vrstico, ki vsebuje te vrednosti:
Izbira strategije, bo sovražnik raje tisto, za katero vrednost βj najmanj. Označimo ga z β :
Vrednost β klical najvišja cena igre oz minimax(najmanjši največji dobitek). Nasprotnikova (igralčeva) strategija, ki ustreza minimaxu B), je poklican strategija minimax.
Minimax je vrednost dobička, več od katere nam razumen nasprotnik zagotovo ne bo dal (z drugimi besedami, razumen nasprotnik ne bo izgubil več kot β ). V tem primeru minimax β je enak 5 (ustrezna celica v tabeli je označena sivo) in je dosežen z nasprotnikovo strategijo B 3 .
Torej, po načelu previdnosti ("vedno pričakuj najslabše!") moramo izbrati strategijo A 4 , in sovražnik - strategija B 3. Načelo previdnosti je temeljno v teoriji iger in se imenuje minimax princip.
Razmislite primer 2. Naj igralci A in AT ena od treh številk je zapisana hkrati in neodvisno druga od druge: bodisi "1", bodisi "2" ali "3". Če je vsota napisanih števil soda, potem igralec B plača igralca A ta znesek. Če je znesek lih, igralec plača ta znesek A igralec AT.
Zapišimo izplačilno matriko igre in poiščimo spodnjo in zgornjo ceno igre (številka strategije ustreza zapisanemu številu):
Igralec A mora upoštevati strategijo maximin A 1 za zmago vsaj -3 (to je za največ 3 poraze). Strategija igralcev Minimax B katera od strategij B 1 in B 2, kar zagotavlja, da ne bo dal več kot 4.
Enak rezultat bomo dobili, če izplačilno matriko zapišemo z vidika igralca AT. Pravzaprav je ta matrika pridobljena s transponiranjem matrike, zgrajene z vidika igralca A, in spreminjanje predznakov elementov v nasprotno (od izplačila igralca A je izguba igralca AT):
Na podlagi te matrike sledi, da igralec B mora slediti kateri koli od strategij B 1 in B 2 (in potem ne bo izgubil več kot 4), in igralca A– strategije A 1 (in potem ne bo izgubil več kot 3). Kot lahko vidite, je rezultat popolnoma enak zgornjemu, tako da analiza ni pomembna z vidika katerega igralca jo izvajamo.
8 KAJ JE VREDNA IGRA.
9. KAJ SESTAVLJA PRINCIP MINIMAX. 2. Spodnja in zgornja cena igre. Minimax princip
Razmislite o matrični igri tipa z matriko izplačil
Če igralec AMPAK bo izbral strategijo A i, potem bodo vsi njegovi možni izplačili elementi jaz-ta vrstica matrike OD. Najslabše za igralca AMPAK primeru, ko igralec AT uporablja strategijo, primerno za najmanj element te linije, igralčev izkupiček AMPAK bo enako številu.
Zato, da bi dobili največje izplačilo, igralec AMPAK morate izbrati eno od strategij, za katere število maksimum.
Problem odločanja, obravnavan v okviru sistemskega pristopa, vsebuje tri glavne komponente: v njem ločimo sistem, krmilni podsistem in okolje. Zdaj se obrnemo na študijo problemov odločanja, pri katerem na sistem ne vpliva en, ampak več krmilnih podsistemov, od katerih ima vsak svoje cilje in možnosti delovanja. Ta pristop k odločanju se imenuje teoretični iger, matematični modeli ustreznih interakcij pa se imenujejo igre. Zaradi razlike v ciljih nadzornih podsistemov, pa tudi zaradi določenih omejitev možnosti izmenjave informacij med njimi, so te interakcije konfliktne narave. Zato je vsaka igra matematični model konflikta. Omejimo se na primer, ko sta krmilna podsistema dva. Če so cilji sistemov nasprotni, se konflikt imenuje antagonističen, matematični model takšnega konflikta pa imenujemo antagonistična igra..
V terminologiji teorije iger se imenuje 1. krmilni podsistem igralec 1, 2. krmilni podsistem - igralec 2, kompleti
njihova alternativna dejanja se imenujejo nizi strategij teh igralcev. Pustiti X- niz strategij igralca 1, Y- veliko strategij
igralec 2. Stanje sistema je enolično določeno z izbiro krmilnih dejanj podsistemov 1 in 2, to je z izbiro strategij
x∈X in l∈Y. Pustiti F(x,l) - ocena uporabnosti za igralca 1 tega stanja
sistem, v katerega preide, ko igralec 1 izbere strategijo X in
strategija igralca 2 pri. številka F(x,l) je poklican zmagovalni igralec 1 v situaciji ( x,l), in funkcijo F- izplačilna funkcija igralca 1. Zmaga igralca
1 je tudi izguba igralca 2, to je vrednost, ki jo želi prvi igralec povečati, drugi pa zmanjšati. Tako je
manifestacija antagonistične narave konflikta: interesi igralcev so popolnoma nasprotni (kar eden zmaga, drugi izgubi).
Antagonistično igro seveda postavlja sistem G=(X, Y, F).
Upoštevajte, da je formalno antagonistična igra dejansko postavljena na enak način kot problem odločanja v pogojih negotovosti - če
identificira krmilni podsistem 2 z okoljem. Vsebinska razlika med krmilnim podsistemom in okoljem je v tem, da
vedenje prvega je namensko. Če imamo pri sestavljanju matematičnega modela realnega konflikta razlog (ali namen), da okolje obravnavamo kot nasprotnika, katerega namen je prinesti
največjo škodo, potem lahko takšno situacijo predstavimo kot antagonistično igro. Z drugimi besedami, antagonistično igro lahko razlagamo kot skrajni primer ZPR v pogojih negotovosti,
za katero je značilno, da okolje vidi kot nasprotnika s ciljem. Hkrati moramo omejiti vrste hipotez o obnašanju okolja.
Pri tem je najbolj utemeljena hipoteza o skrajni previdnosti, ko se pri odločanju zanašamo na najslabši možni scenarij našega delovanja v okolju.
Opredelitev.Če X in Y so končne, potem se antagonistična igra imenuje matrika. V matrični igri lahko domnevamo, da X={1,…,n},
Y={1,…,m) in postavite aij=F(jaz,j). Tako je matrična igra popolnoma določena z matriko A=(aij), jaz=1,…,n, j=1,…,m.
Primer 3.1. Igra z dvema prstoma.
Dve osebi hkrati pokažeta en ali dva prsta in pokličeta številko 1 ali 2, ki po besedah govorca pomeni št.
prste pokazal drugim. Ko se pokažejo prsti in poimenujejo številke, se dobitek razdeli po naslednjih pravilih:
če sta oba uganila ali oba nista uganila, koliko prstov je pokazal nasprotnik, je izkupiček vsakega enak nič; če je samo eden pravilno uganil, potem nasprotnik plača ugibalcu znesek denarja, sorazmeren skupnemu številu prikazanih
To je antagonistična matrična igra. Vsak igralec ima štiri strategije: 1- pokaži 1 prst in reci 1, 2- pokaži 1 prst in reci 2, 3-
pokažite 2 prsta in recite 1, 4 - pokažite 2 prsta in recite 2. Nato izplačilna matrika A=(aij), i= 1,…, 4, j= 1,…, 4 je opredeljeno na naslednji način:
a12= 2, a21 = – 2, a13=a42=–3, a24=a31= 3, a34 = – 4, a43= 4,aij= 0 drugače.
Primer 3.2. Diskretna igra dvoboja.
Naloge tipa dvoboj opisujejo na primer boj dveh igralcev,
od katerih vsak želi opraviti neko enkratno dejanje (sprostitev pošiljke blaga v promet, prijava za nakup na dražbi) in si za to izbere čas. Naj se igralci premikajo drug proti drugemu n koraki. Po vsakem koraku lahko igralec strelja na nasprotnika ali pa tudi ne. Vsaka oseba ima lahko le en strel. Menijo, da je verjetnost, da zadenete sovražnika, če napredujete z k n =5 ima obliko
