Antagonistične matrične igre. Reševanje matrične igre Antagonistične matrične igre

Kot osnovna predpostavka v teoriji iger se domneva, da si vsak igralec prizadeva zagotoviti največjo možno zmago zase ob kakršnih koli dejanjih svojega partnerja. Predpostavimo, da obstaja končna igra z ničelno vsoto z matriko izplačil prvega igralca in s tem matriko izplačil drugega igralca. Naj igralec 1 verjame, da bo ne glede na strategijo, ki jo izbere, igralec 2 izbral strategijo, ki poveča njegov izkupiček in s tem zmanjša izkupiček igralca 1.

Torej igralec 1 izbere jaz

Igralec 2 si prav tako prizadeva zagotoviti najvišji znesek zmage (ali, kar je enako, najmanjši znesek izgube) ne glede na nasprotnikovo izbrano strategijo. Njegova optimalna strategija bi bila kolona H 0 z najnižjim najvišjim plačilom. Torej igralec 2 bo izbral j-ta strategija, ki je rešitev problema

Posledično, če igralec 1 sledi izbrani strategiji (imenovani maximin strategija ), bo njegov izkupiček v vsakem primeru manjši od maksimalne vrednosti (imenovane "najnižja cena igre" ), tj.

V skladu s tem, če se igralec 2 drži svoje minimax strategije, potem njegova izguba ne bo večja od največje vrednosti (imenovane "najvišja cena igre" ), tj.

V primeru, ko je zgornji tečaj igre enak spodnjemu, tj. = , oba igralca prejmeta zajamčena plačila in vrednost h ij * klical na ceno igre .

Matrični element h ij se imenuje matrika izplačil, ki ustreza strategijam sedlo matrice n.

Če je strošek antagonistične igre 0, je igra klicana pošteno .

Razmislite o igri, v kateri ima igralec 1 dve strategiji, igralec 2 pa tri. Izplačilna matrika igralca 1 izgleda takole:

Komentiraj . Ker razmišljamo o primeru igre z ničelno vsoto, bo izplačilna matrika 2. igralca N 2 = -H 1.

Igralec 1 izračuna, da če izbere prvo strategijo (tj. prvo vrstico matrike H 1), potem bo nasprotnik izbral svojo drugo strategijo (tj. drugi stolpec), tako da bo izkupiček enak 1 . Če izbere drugo strategijo, lahko nasprotnik izbere prvo strategijo, tako da bo izplačilo enako -1.

Po analizi dobljenih vrednosti: Igralec 1 se odloči za svojo prvo strategijo, ki mu zagotavlja največjo zajamčeno zmago, ki je enaka 1.

Podobno 2. igralec upošteva svoje najslabše možnosti, ko nasprotnik izbere prvo ali drugo strategijo, ali ko nasprotnik izbere drugo strategijo, ko 2. igralec izbere tretji stolpec. Te možnosti ustrezajo največjim vrednostim stolpcev 2, 1 in 6.

Ob minimalnih vrednostih teh maksimumov se igralec 2 odloči za svojo drugo strategijo, pri kateri je njegova izguba minimalna in enaka:

Posledično so v tej igri skupne izbire strategij, tj. E

Zato je v tej igri razumno pričakovati, da bodo nasprotniki vztrajali pri svojih izbranih strategijah. Matrična antagonistična igra, za katero - se imenuje popolnoma določena igra ali igra, ki ima rešitev v čistih strategijah.

Vendar niso vse matrične antagonistične igre dobro definirane.

Igre, v katerih velja stroga neenakost, imenujemo nepopolno določene igre (oz. igre, ki nimajo rešitve v čistih strategijah).

Poglejmo primer te igre:

Za to igro.

Posledično, če igralci upoštevajo zgoraj predlagana pravila, bo igralec 1 izbral strategijo 1 in pričakoval, da bo igralec 2 izbral strategijo 2, kjer je izguba -2, medtem ko bo igralec 2 izbral strategijo 3 in pričakoval, da bo igralec 1 izberite strategijo 2 z izplačilom enakim 4.

Če pa 2. igralec izbere svojo tretjo strategijo, bi bil igralec 1 boljši, če bi izbral drugo strategijo namesto prve. Podobno, če igralec 1 izbere prvo strategijo, je bolje, da igralec 2 izbere drugo strategijo kot tretjo. Očitno se v igrah zahrbtnega tipa načelo rešitve v čistih strategijah izkaže za neprimerno.

V opisani situaciji postane za igralce pomembno, da sovražnik ne ugiba, kakšno strategijo bo uporabil. Za izvedbo tega načrta bi morali igralci uporabiti tako imenovano mešano strategijo.

V bistvu je igralčeva mešana strategija shema za naključno izbiro čiste strategije. Matematično jo lahko predstavimo kot porazdelitev verjetnosti na nizu čistih strategij danega igralca. Posledično vektor , kjer ustreza verjetnosti, da igralec 1 uporablja strategijo in , določa mešano strategijo tega igralca. Mešana strategija igralca 2 je določena podobno .

Predpostavili bomo, da igralci uporabljajo svoje mešane strategije neodvisno, tako da je verjetnost, s katero igralec 1 izbere to strategijo in igralec 2, enaka. V tem primeru plačilo. Če seštejemo in dobimo matematično pričakovanje dobitka igralca 1:

ali matrični zapis

Pri naboru mešanih strategij igralec 1, ki želi doseči največji od zajamčenih dobitkov, izbere vektor verjetnosti, tako da dobi največjo najmanjšo vrednost pričakovanih dobitkov, tj. rešuje problem:

.

Podobno je cilj igralca 2 doseči najmanjše največje vrednosti svojih izgub, tj. on reši problem

.

Temeljni rezultat teorije iger je tako imenovani teorem Minimax, ki trdi, da imajo formulirani problemi igralca 1 in igralca 2 vedno rešitev za katero koli matriko izplačil in poleg tega .

Pri dobro definiranih igrah se imenuje strategija igralca 1 Strategija Maximin , strategija igralca 2 - strategija minimax, vrednost - po ceni igre ; v primeru, ko se igra imenuje poštena.

Očitna posledica Minimaxovega izreka je razmerje:

.

kar pomeni, da nobena strategija igralca 1 ne bo omogočila, da bi osvojil znesek, večji od cene igre, če igralec 2 uporabi svojo minimax strategijo, in nobena strategija igralca 2 mu ne bo omogočila, da bi izgubil znesek, ki je manjši od cene igre. če igralec 1 uporabi svojo maximin strategijo.

To velja tudi za čiste strategije, kot poseben primer mešanih strategij. (Ker je čista strategija strategija, ki se uporablja z verjetnostjo 1): Uporaba katere koli čiste strategije, če nasprotnik uporablja svojo optimalno strategijo, vam ne dovoli zmagati več (manj izgubiti), kot je cena igre.

To dejstvo se pogosto uporablja za razvoj posebnih algoritmov za reševanje antagonističnih matričnih iger.

Izračun optimalnih strategij postane veliko težji, ko se število strategij poveča. Za iskanje optimalnih strategij je mogoče uporabiti več pristopov.

Za zmanjšanje razsežnosti igre se uporablja prevlada vrstic in stolpcev. Običajno rečemo, da i-ta vrstica matrike prevladuje nad i-to vrstico (tj. ena čista vrstica prevladuje nad drugo), če je za vse , vsaj ena .

Podobno th stolpec prevladuje nad th stolpcem, če je za vse , vsaj eden .

Bistvo te definicije je, da prevladujoča strategija ni nikoli slabša, v nekaterih primerih celo boljša od prevladujoče strategije. Zato je pomembna ugotovitev, da igralcu ni treba uporabljati prevladujoče strategije. To v praksi omogoča, da se zavržejo vse prevladujoče vrstice in stolpci, kar bo zmanjšalo velikost matrike (upoštevajte, da se ta pristop lahko uporablja tudi pri iskanju rešitve v čistih strategijah).

Primer. Razmislite o igri z naslednjo matriko:

Če izločimo drugo vrstico, dobimo matriko: v tretjem stolpcu te obrezane matrike prevladuje drugi, izpustitev drugega stolpca pa daje: .

Posledično, če je mogoče najti rešitev za nastalo igro, jo je mogoče preprosto uporabiti za rešitev izvirne igre tako, da preprosto dodelite ničelne verjetnosti izključenim vrsticam in stolpcem.

Druga metoda poenostavitve matrike temelji na lastnosti, po kateri afina transformacija izplačilne matrike (tj. transformacija vseh elementov matrike po pravilu , kjer ) ne spremeni rešitve igre; poleg tega je mogoče ceno pretvorjene igre pridobiti iz cene izvirne igre z uporabo istega pravila: . To pomeni, da za nalogo igre načeloma ni pomembno, v kakšnih enotah se meri dobitek (v rubljih ali dolarjih); dodajanje (odštevanje) nekega fiksnega zneska bo spremenilo dobitek (izgubo) vsakega igralca za enako količino brez spreminjanja rešitve igre.

To lastnost je mogoče uporabiti za poenostavitev in jasnejšo zmagovalno matriko (uporablja se po analogiji z operacijami na matrikah – množenje matrike s stalnim številom, seštevanje in odštevanje vrstic, poleg tega pa ta lastnost omogoča izvedbo katere koli matrične igre z ničelno vsoto pošteno, za to je treba izračunati cenovne igre iz vseh elementov izplačilne matrike).

Poleg tega lahko za reševanje igre (in iger na splošno) uporabimo grafično metodo.

Na primer, izplačilna matrika izgleda takole: .

Naj igralec 1 izbere svojo prvo strategijo z verjetnostjo in svojo drugo z verjetnostjo. Če 2. igralec izbere svojo prvo strategijo, bo (iz prvega stolpca matrike) pričakovanje za 1. igralca . Če igralec 2 izbere svojo drugo strategijo, potem v skladu z drugim stolpcem matrike: .

Vsako od teh enačb je mogoče grafično predstaviti z odsekom ravne črte v območju na grafu s koordinatama in .

Testi za končno kontrolo

1. Antagonistično igro je mogoče nastaviti:

a) nabor strategij za oba igralca in sedlo.

b) nabor strategij za oba igralca in funkcijo izplačila prvega igralca.

2. Cena igre vedno obstaja za matrične igre v mešanih strategijah.

a) da.

3. Če so vsi stolpci v izplačilni matriki enaki in imajo obliko (4 5 0 1), katera strategija je potem optimalna za 1. igralca?

a) najprej.

b) drugič.

c) katerega koli od štirih.

4. Naj ima v matrični igri ena od mešanih strategij 1. igralca obliko (0,3, 0,7), ena od mešanih strategij 2. igralca pa obliko (0,4, 0, 0,6). Kakšna je dimenzija te matrice?

a) 2*3.

c) druga dimenzija.

5. Načelo prevlade vam omogoča, da odstranite iz matrike v enem koraku:

a) cele vrstice.

b) posamezne številke.

6. Pri grafični metodi za reševanje iger 2*m neposredno iz grafa ugotovimo:

a) optimalne strategije obeh igralcev.

b) ceno igre in optimalne strategije 2. igralca.

c) cena igre in optimalne strategije 1. igralca.

7. Graf spodnje ovojnice za grafično metodo reševanja iger 2*m je v splošnem primeru:

a) pokvarjen.

b) naravnost.

c) parabolo.

8. V matrični igri 2*2 sta dve komponenti igralčeve mešane strategije:

a) določata vrednote drug drugega.

b) neodvisen.

9. V matrični igri je element aij:

a) dobitek 1. igralca, ko uporablja i-to strategijo, in 2. - j-to strategijo.

b) optimalna strategija 1. igralca, ko nasprotnik uporabi i-to ali j-to strategijo.

c) izguba 1. igralca, ko uporablja j-to strategijo, in 2. - i-to strategijo.

10.Matrični element aij ustreza sedlu. Možne so naslednje situacije:

a) ta element je strogo najmanjši od vseh v liniji.

b) ta element je drugi po vrsti v vrstici.

11. Pri metodi Brown-Robinson se vsak igralec pri izbiri strategije v naslednjem koraku vodi po:

a) sovražnikove strategije v prejšnjih korakih.

b) vaše strategije v prejšnjih korakih.

c) nekaj drugega.

12. Po kriteriju matematičnega pričakovanja vsak igralec izhaja iz dejstva, da:

a) zgodila se bo najslabša situacija zanj.

c) vse ali nekatere situacije so možne z nekaterimi danimi verjetnostmi.

13. Naj bo matrična igra podana z matriko, v kateri so vsi elementi negativni. Cena igre je pozitivna:

b) št.

c) ni jasnega odgovora.

14. Cena igre je:

številka.

b) vektor.

c) matriko.

15. Kakšno je največje število sedlnih točk, ki so lahko v igri dimenzije 5*5 (matrika lahko vsebuje poljubna števila):

16. Naj ima v matrični igri dimenzije 2*3 ena od mešanih strategij 1. igralca obliko (0,3, 0,7), ena od mešanih strategij 2. igralca pa obliko (0,3, x, 0,5) . Kaj je število x?

c) drugo številko.

17. Za katero dimenzijo matrike igre se Waldov kriterij spremeni v Laplaceov kriterij?

c) samo v drugih primerih.

18. Zgornja cena igre je vedno nižja od spodnje cene igre.

b) št.

b) vprašanje ni pravilno.

19. Katere strategije so v matrični igri:

a) čista.

b) mešano.

c) oboje.

20. Ali so lahko v neki antagonistični igri vrednosti izplačilne funkcije obeh igralcev za nekatere vrednosti spremenljivk enake 1?

a) vedno.

b) včasih.

c) nikoli.

21. V matrični igri naj bo ena od mešanih strategij 1. igralca v obliki (0.3, 0.7), ena od mešanih strategij 2. igralca pa v obliki (0.4, 0.1, 0.1, 0.4) . Kakšna je dimenzija te matrice?

c) druga dimenzija.

22. Načelo prevlade vam omogoča, da odstranite iz matrice v enem koraku:

a) celotne stolpce,

b) posamezne številke.

c) podmatrike manjših velikosti.

23. V matrični igri 3*3 sta dve komponenti igralčeve mešane strategije:

a) določi tretjo.

b) ne definirajo.

24. V matrični igri je element aij:

a) izguba 2. igralca, ko uporablja j-to strategijo, in 2. - i-to strategijo.

b) optimalna strategija 2. igralca, ko nasprotnik uporabi i-to ali j-to strategijo,

c) dobitek 1. igralca, ko uporablja j-to strategijo, in 2. - i-to strategijo,

25. Matrični element aij ustreza sedlu. Možne so naslednje situacije:

a) ta element je največji v stolpcu.

b) ta element je strogo največji v vrstici.

c) niz vsebuje tako večje kot manjše elemente od tega elementa.

26. V skladu z Waldovim kriterijem vsak igralec predpostavlja, da:

a) zgodila se bo najslabša situacija zanj.

b) vse situacije so enako možne.

c) vse situacije so možne z določenimi danimi verjetnostmi.

27. Spodnja cena je nižja od zgornje cene igre:

b) ne vedno.

c) nikoli.

28. Vsota komponent mešane strategije za matrično igro je vedno:

a) je enako 1.

b) nenegativni.

c) pozitivno.

d) ne vedno.

29. Naj ima v matrični igri dimenzije 2*3 ena od mešanih strategij 1. igralca obliko (0,3, 0,7), ena od mešanih strategij 2. igralca pa obliko (0,2, x, x) . Kaj je število x?

Pošljite svoje dobro delo v bazo znanja je preprosto. Uporabite spodnji obrazec

Študenti, podiplomski študenti, mladi znanstveniki, ki bazo znanja uporabljajo pri študiju in delu, vam bodo zelo hvaležni.

Uvod

1. Teoretični del

1.3 Igralni red 2x2

1.4 Algebraična metoda

1.5 Grafična metoda

1.6 Igre 2xn ali mx2

1.7 Reševanje iger z matrično metodo

2. Praktični del

2.2 Igre 2xn in mx2

2.3 Matrična metoda

2.4 Brownova metoda

Analiza rezultatov

Uvod

Igra z ničelno vsoto je igra z ničelno vsoto. Igra z ničelno vsoto je nekooperativna igra, ki vključuje dva igralca, katerih izplačila so si nasprotna.

Formalno lahko antagonistično igro predstavlja trojka , kjer sta X in Y niza strategij prvega oziroma drugega igralca, F je izplačilna funkcija prvega igralca, ki vsakemu paru strategij dodeli (x,y), kjer je realno število, ki ustreza uporabnosti prvi igralec pri izvajanju dane situacije.

Ker so interesi igralcev nasprotni, funkcija F hkrati predstavlja izgubo drugega igralca.

Zgodovinsko gledano so igre z ničelno vsoto prvi razred modelov matematične teorije iger, s katerimi so bile opisane igre na srečo. Menijo, da je ta predmet študija, kjer je teorija iger dobila ime. Dandanes se antagonistične igre štejejo za del širšega razreda nekooperativnih iger.

1. Teoretični del

1.1 Osnovne definicije in določbe igre

Za igro je značilen sistem pravil, ki določajo število udeležencev v igri, njihova možna dejanja in razdelitev dobitkov glede na njihovo obnašanje in rezultate. Za igralca se šteje en udeleženec ali skupina udeležencev igre, ki imajo skupne interese, ki ne sovpadajo z interesi drugih skupin. Zato se vsak udeleženec ne šteje za igralca.

Pravila ali pogoji igre določajo možna vedenja, izbire in poteze igralcev na kateri koli stopnji razvoja igre. Izbira za igralca pomeni izbiro ene od njegovih možnosti obnašanja. Igralec nato te odločitve naredi s potezami. Poteza pomeni, da v določeni fazi igre naredite celotno izbiro ali njen del naenkrat, odvisno od možnosti, ki jih ponujajo pravila igre. Vsak igralec v določeni fazi igre naredi potezo glede na izbrano izbiro. Drugi igralec, vedoč ali ne vedoč za izbiro prvega igralca, prav tako naredi potezo. Vsak igralec poskuša upoštevati podatke o preteklem razvoju igre, če tako možnost dovoljujejo pravila igre.

Niz pravil, ki igralcu jasno nakazujejo, kakšno izbiro mora narediti pri vsaki potezi glede na situacijo, ki nastane kot rezultat igre, imenujemo igralčeva strategija. Strategija v teoriji iger pomeni določen popoln akcijski načrt za igralca, ki prikazuje, kako mora ravnati v vseh možnih primerih razvoja igre. Strategija pomeni celoto vseh navodil za katero koli stanje informacij, ki so na voljo igralcu na kateri koli stopnji razvoja igre. Že iz tega je jasno, da so strategije lahko dobre in slabe, uspešne in neuspešne itd.

Igra z ničelno vsoto bo takrat, ko je vsota dobitkov vseh igralcev v vsaki njeni igri enaka nič, tj. v igri z ničelno vsoto se skupni kapital vseh igralcev ne spremeni, ampak se prerazporedi med igralce. odvisno od posledičnih rezultatov. Tako je na številne gospodarske in vojaške situacije mogoče gledati kot na igre z ničelno vsoto.

Zlasti igra z ničelno vsoto med dvema igralcema se imenuje antagonistična, saj so cilji igralcev v njej neposredno nasprotni: dobiček enega igralca se zgodi le na račun izgube drugega.

1.1.1 Definicija, primeri in rešitve matričnih iger v čistih strategijah

Matrično igro z ničelno vsoto za dva igralca si lahko predstavljamo kot naslednjo abstraktno igro za dva igralca.

Prvi igralec ima t strategij i =1, 2,…, t, drugi ima n strategij j = 1, 2,…, p. Vsakemu paru strategij (i, j) je pridruženo število a ij, ki izraža dobitek prvega igralca zaradi drugega igralca, če prvi igralec uporabi svojo i-to strategijo, drugi igralec pa svojo j-to strategijo.

Vsak igralec naredi eno potezo: prvi igralec izbere svojo i-to strategijo (i = 1, 2,..., m), drugi izbere svojo j-to strategijo (j = 1, 2,..., n) , po katerem prvi igralec prejme dobitek a ij na račun drugega igralca (če je ij< 0, то это значит, что первый игрок платит второму сумму a ij). На этом игра заканчивается.

Vsaka strategija igralca i = 1, 2,…, t; j = 1, 2,…, n pogosto imenujemo čista strategija.

Matrična igra z ničelno vsoto za dva igralca se bo odslej preprosto imenovala matrična igra. Očitno matrična igra spada med antagonistične igre. Iz njene definicije sledi, da je za definiranje matrične igre dovolj, da določimo matriko A = (a ij) vrstnega reda izplačil prvega igralca.

Če upoštevamo matriko izplačil

potem je igranje vsake igre matrične igre z matriko A zmanjšano na izbiro prvega igralca i-te vrstice in drugega igralca j-tega stolpca, pri čemer prvi igralec prejme (na račun drugega ) dobitki, ki se nahajajo v matriki A na presečišču i-te vrstice in j-tega stolpca.

Za formalizacijo resnične konfliktne situacije v obliki matrične igre je treba identificirati in preštevilčiti čiste strategije vsakega igralca ter ustvariti matriko izplačil.

Naslednja faza je določitev optimalnih strategij in dobitkov igralcev.

Glavna stvar pri preučevanju iger je koncept optimalnih strategij igralcev. Ta koncept ima intuitivno naslednji pomen: igralčeva strategija je optimalna, če mu uporaba te strategije zagotavlja največji zajamčeni dobitek za vse možne strategije drugega igralca. Na podlagi teh pozicij prvi igralec preuči matriko A svojih izplačil z uporabo formule (1.1) na naslednji način: za vsako vrednost i (i = 1, 2,..., t) se minimalna vrednost izplačila določi glede na strategije, ki jih uporablja drugi igralec

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

tj. določen je najmanjši izkupiček za prvega igralca, pod pogojem, da uporabi svojo i -to čisto strategijo, nato pa se iz teh minimalnih izplačil najde strategija i = i 0, za katero bo ta najmanjši izkupiček največji, tj.

Opredelitev. Število b, določeno s formulo (1.3), se imenuje nižja neto cena igre in kaže, kakšen minimalni dobitek si lahko prvi igralec zagotovi z uporabo svojih čistih strategij za vsa možna dejanja drugega igralca.

Drugi igralec naj si s svojim optimalnim vedenjem prizadeva, če je le mogoče, s svojimi strategijami minimizirati dobitke prvega igralca. Zato za drugega igralca najdemo

t.j. določen je največji izkupiček prvega igralca, pod pogojem, da drugi igralec uporabi svojo j-to čisto strategijo, potem drugi igralec najde svojo j = j 1 strategijo, po kateri bo prvi igralec prejel minimalni izkupiček, tj. najde

Opredelitev. Število b, določeno s formulo (1.5), se imenuje neto zgornja cena igre in kaže, koliko največjih dobitkov si lahko s svojimi strategijami zagotovi prvi igralec. Z drugimi besedami, z uporabo svojih čistih strategij lahko prvi igralec zagotovi izkupiček, ki ni manjši od b, drugi igralec pa lahko z uporabo svojih čistih strategij prepreči, da bi prvi igralec zmagal več kot b.

Opredelitev. Če v igri z matriko A spodnja in zgornja neto cena igre sovpadata, tj. b = c, potem pravimo, da ima ta igra sedlo v čistih strategijah in neto ceno igre:

n = b = v (1.6)

Sedežna točka je par čistih strategij () prvega oziroma drugega igralca, pri katerih je dosežena enakost

Koncept sedla ima naslednji pomen: če se eden od igralcev drži strategije, ki ustreza sedlu, potem drugi igralec ne more storiti bolje, kot da se drži strategije, ki ustreza sedlu. Ob upoštevanju, da najboljše vedenje igralca ne bi smelo povzročiti zmanjšanja njegovih dobitkov, najslabše vedenje pa lahko povzroči zmanjšanje njegovih dobitkov, lahko te pogoje matematično zapišemo v obliki naslednjih razmerij:

kjer sta i, j poljubni čisti strategiji prvega oziroma drugega igralca; (i 0 , j 0) so strategije, ki tvorijo sedlo. V nadaljevanju bomo pokazali, da je definicija sedla enakovredna pogojem (1.8).

Tako je na podlagi (1.8) sedlasti element minimalen v i 0. vrstici in maksimalen v j 0. stolpcu v matriki A. Iskanje sedla matrike A je enostavno: v matriki A je minimalni element zaporedoma najden v vsako vrstico in preverite, ali je ta element največji v svojem stolpcu. Če je tak, potem je to sedlo, par strategij, ki mu ustreza, pa tvori sedlo. Par čistih strategij (i 0 , j 0) prvega in drugega igralca, ki tvorita sedlo in sedlo, se imenuje rešitev igre.

Čisti strategiji i 0 in j 0, ki tvorita sedlo, imenujemo optimalne čiste strategije prvega oziroma drugega igralca.

Izrek 1. Naj bo f (x, y) realna funkcija dveh spremenljivk x A in y B in obstaja

potem je b = c.

Dokaz. Iz definicije minimuma in maksimuma sledi, da

Ker je na levi strani (1.11) x poljuben, potem

Na desni strani neenakosti (1.12) je torej y poljuben

Q.E.D.

Zlasti matrika () je poseben primer funkcije f (x, y), tj. če postavimo x = i, y = j, = f (x, y), potem iz izreka 1 dobimo, da je spodnja mreža cena ne presega zgornje neto cene igranja v matrični igri.

Opredelitev. Naj bo f (x, y) realna funkcija dveh spremenljivk x A in y B. Točko (x 0, y 0) imenujemo sedlo za funkcijo f (x, y), če so izpolnjene naslednje neenakosti

f (x, y 0) f (x 0, y 0)f (x 0, y) (1.14)

za katerikoli x A in y B.

1.2 Optimalne mešane strategije in njihove lastnosti

Študija matrične igre se začne z iskanjem njene sedla v čistih strategijah. Če ima matrična igra sedlo v čistih strategijah, se študija igre konča z iskanjem te točke. Če v matrični igri pri čistih strategijah ni sedla, potem lahko najdemo spodnjo in zgornjo neto ceno te igre, ki nakazujeta, da prvi igralec ne sme upati, da bo zmagal več kot je zgornja cena igre, in lahko bodite prepričani, da boste prejeli zmago po nič manj nižji ceni igre. Takšna priporočila glede obnašanja igralcev v matrični igri brez sedla v čistih strategijah ne morejo zadovoljiti raziskovalcev in praktikov. Izboljšanje rešitev matričnih iger je treba iskati v uporabi tajnosti uporabe čistih strategij in možnosti večkratnega ponavljanja iger v obliki iger. Tako se na primer igra serija iger šaha, dame in nogometa, pri čemer igralci vsakič uporabijo svoje strategije tako, da nasprotniki nimajo pojma o njihovi vsebini, in na tej poti v povprečju doseči določene dobitke z igranjem celotne serije iger. Ti dobitki so v povprečju večji od spodnje cene igre in manjši od zgornje cene igre. Višja kot je ta povprečna vrednost, boljša je strategija, ki jo igralec uporablja. Zato se je pojavila ideja, da bi čiste strategije uporabljali naključno, z določeno verjetnostjo. S tem je popolnoma zagotovljena tajnost njihove uporabe. Vsak igralec lahko spremeni verjetnost uporabe svojih čistih strategij tako, da poveča svoj povprečni izkupiček in ob tem pridobi optimalne strategije. Ta ideja je vodila do koncepta mešane strategije.

Opredelitev. Igralčeva mešana strategija je celoten niz verjetnosti uporabe njegovih čistih strategij.

Torej, če ima prvi igralec m čistih strategij 1, 2, … i, … m, potem je njegova mešana strategija x niz števil x = (x 1, x 2, ..., x i,…, x m ), ki izpolnjujejo odnosi

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

Podobno je za drugega igralca, ki ima n čistih strategij, mešana strategija y niz števil y = (y 1, ..., y j, ... y n), ki izpolnjuje razmerja

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

Ker vsakič, ko igralec uporabi eno čisto strategijo, izključi uporabo druge, so čiste strategije nekompatibilni dogodki. Še več, to so edini možni dogodki.

Očitno je čista strategija poseben primer mešane strategije. Dejansko, če se v mešani strategiji katera koli i-ta čista strategija uporabi z verjetnostjo ena, potem se vse druge čiste strategije ne uporabijo. In ta i-ta čista strategija je poseben primer mešane strategije. Za ohranitev tajnosti vsak igralec uporablja svoje lastne strategije ne glede na izbire drugega igralca.

Opredelitev. Povprečni izkupiček prvega igralca v matrični igri z matriko A je izražen kot matematično pričakovanje njegovih izplačil

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

Očitno je povprečni izkupiček prvega igralca funkcija dveh nizov spremenljivk x in y. Prvi igralec želi s spreminjanjem svojih mešanih strategij x povečati svoj povprečni izkupiček E (A, x, y), drugi igralec pa si s svojimi mešanimi strategijami prizadeva narediti E (A, x, y) minimalen, tj. Za rešitev igre je treba najti takšne x, y, pri katerih je dosežena zgornja cena igre.

1.3 Igra reda 22

Matrična igra reda 22 je podana z naslednjo matriko izplačil za prvega igralca:

Rešitev te igre bi se morala začeti z iskanjem sedla v čistih strategijah. Če želite to narediti, poiščite najmanjši element v prvi vrstici in preverite, ali je največji v njenem stolpcu. Če takega elementa ne najdemo, se druga vrstica preveri na enak način. Če je tak element v drugi vrstici, potem je to sedlo.

Iskanje elementa sedla, če obstaja, konča proces iskanja njegove rešitve, saj je bila v tem primeru najdena cena igre – element sedla in točka sedla, to je par čistih strategij za prvo in drugi igralec, ki tvori optimalne čiste strategije. Če v čistih strategijah ni sedla, potem moramo v mešanih strategijah najti sedlo, ki v skladu z glavnim izrekom matričnih iger nujno obstaja.

Označimo z x = (x 1 , x 2), y = (y 1 , y 2) mešane strategije prvega oziroma drugega igralca. Spomnimo se, da x 1 pomeni verjetnost, da bo prvi igralec uporabil svojo prvo strategijo, x 2 = 1 - x 1 pa je verjetnost, da bo uporabil svojo drugo strategijo. Podobno za drugega igralca: 1 je verjetnost, da bo uporabil prvo strategijo, 2 = 1 - 1 je verjetnost, da bo uporabil drugo strategijo.

V skladu s posledico izreka je za optimalno mešano strategijo x in y potrebno in zadostno, da za nenegativne x 1, x 2, y 1, y 2 veljajo naslednje relacije:

Pokažimo zdaj, da če matrična igra nima sedla v čistih strategijah, potem se morajo te neenakosti spremeniti v enakosti:

Prav zares. Naj igra nima sedla v čistih strategijah, potem optimalne vrednosti mešanih strategij zadovoljujejo neenakosti

0<<1, 0<< 1,

0< <1, 01. (1.25)

Predpostavimo, da sta obe neenakosti iz (1.22) strogi

potem je po izreku y 1 = y 2 = 0, kar je v nasprotju s pogoji (1.25).

Podobno je dokazano, da obe neenakosti iz (1.23) ne moreta biti strogi neenakosti.

Predpostavimo zdaj, da je ena od neenakosti (1.22) lahko stroga, na primer prva

To pomeni, da je po izreku y 1 = 0, y 2 = 1. Posledično iz (1.23) dobimo

Če sta obe neenakosti (1.24) strogi, potem je po izreku x 1 = x 2 = 0, kar je v nasprotju z (1.25). Če je a 12 a 22, potem je ena od neenakosti (1.27) stroga, druga pa enakost. Poleg tega bo enakost veljala za večji element 12 in 22, tj. ena neenakost iz (1.27) mora biti stroga. Na primer 12< а 22 . Тогда справедливо а 12 < v, а это равносильно тому, что первое неравенство из (1.24) строгое. Тогда согласно теореме должно х 1 = 0, что противоречит условию (1.25). Если а 12 = а 22 , то оба неравенства (1.27) превращаются в равенства и тогда можно положить х 1 = 0, что противоречит (1.25). Итак, предположение о том, что первое неравенство из (1.22) может быть строгим, не справедливо. Аналогично можно показать, что второе неравенство из (1.22) также не может быть строгим.

Tako je prikazano, da če matrična igra nima sedla v čistih strategijah, potem se za optimalne strategije prvega igralca neenakosti (1.22) spremenijo v enakosti. Podobno sklepanje glede neenakosti (1.23) bo vodilo do dejstva, da morajo biti v tem primeru neenakosti (1.23) enakosti.

Torej, če matrična igra reda 22 nima sedla, potem lahko optimalne mešane strategije igralcev in ceno igre določimo z reševanjem sistema enačb (1.24). Ugotovljeno je bilo tudi, da če ima v matrični igri reda 2x2 eden od igralcev optimalno čisto strategijo, potem ima tudi drugi igralec optimalno čisto strategijo.

Posledično, če matrična igra nima sedla v čistih strategijah, mora imeti rešitev v mešanih strategijah, ki so določene iz enačb (1.24). Rešitev sistema (1.25)

1.4 Algebraična metoda

Obstajata dva možna primera reševanja problemov z uporabo algebraične metode:

1. matrika ima sedlo;

2. matrika nima sedla.

V prvem primeru je rešitev par strategij, ki tvorita sedlo igre. Razmislimo o drugem primeru. Rešitve je treba iskati v mešanih strategijah:

Poiščimo strategije in... Ko prvi igralec uporabi svojo optimalno strategijo, lahko drugi igralec na primer uporabi dve takšni čisti strategiji

Poleg tega zaradi lastnosti, če eden od igralcev uporablja optimalno mešano strategijo, drugi pa katero koli čisto strategijo, vključeno v njegovo optimalno mešano strategijo z verjetnostjo, ki ni enaka nič, potem matematično pričakovanje zmage vedno ostane nespremenjeno in enako na ceno igre, tj.

Dobitek v vsakem od teh primerov mora biti enak ceni igre V. V tem primeru veljajo naslednje relacije:

Za optimalno strategijo drugega igralca je mogoče sestaviti sistem enačb, podoben (2.5), (2.6):

Ob upoštevanju pogoja normalizacije:

Rešimo enačbo (1.37) - (1.41) skupaj glede na neznanke, ne morete rešiti vseh naenkrat, ampak tri naenkrat: ločeno (1.36), (1.38), (1.40) in (1.37), ( 1,39), (1,41). Kot rezultat rešitve dobimo:

1.5 Grafična metoda

Približno rešitev igre 22 lahko dobimo povsem preprosto z grafično metodo. Njegovo bistvo je naslednje:

Slika 1.1 - iskanje odseka enote dolžine

Izberite del enote dolžine na osi x. Levi konec bo upodabljal prvo strategijo prvega igralca, desni konec pa drugo. Vse vmesne točke ustrezajo mešanim strategijam prvega igralca, dolžina segmenta desno od točke pa je enaka verjetnosti uporabe prve strategije, dolžina segmenta levo pa je verjetnosti uporabe druga strategija prvega igralca.

Narisani sta osi I-I in II-II. Dobitke bomo uvrstili na I-I, ko bo prvi igralec uporabil prvo strategijo, na II-II, ko bo uporabil drugo strategijo. Recimo, da drugi igralec uporabi svojo prvo strategijo, potem je treba vrednost narisati na osi I-I, vrednost pa na osi II-II.

Za katero koli mešano strategijo prvega igralca bo njegov izkupiček določen z vrednostjo segmenta. Vrstica I-I ustreza uporabi prve strategije s strani drugega igralca; imenovali jo bomo prva strategija drugega igralca. Podobno lahko sestavite drugo strategijo drugega igralca. Nato bo na splošno grafični prikaz matrike igre imel naslednjo obliko:

Slika 1.2 - iskanje cene igre

Vendar je treba opozoriti, da je bila ta konstrukcija izvedena za prvega igralca. Tu je dolžina segmenta enaka ceni igre V.

Linija 1N2 se imenuje spodnja zmagovalna meja. Tukaj lahko jasno vidite, da točka N ustreza največjemu znesku zajamčenega dobitka prvega igralca.

Na splošno lahko iz te številke določimo tudi strategijo drugega igralca, na primer na naslednje načine. Na osi I-I:

ali na osi II-II

Vendar pa lahko strategijo drugega igralca določimo podobno, kot se to naredi za prvega igralca, tj. zgraditi tak graf.

Slika 1.3 - določanje strategije drugega igralca

Tu je vrstica 1N2 zgornja meja izgube. Točka N ustreza najmanjši možni izgubi drugega igralca in določa strategijo.

Glede na specifične vrednosti matričnih koeficientov imajo lahko grafi drugačno obliko, na primer to:

Slika 1.4 - določa optimalno strategijo prvega igralca

V takšni situaciji je optimalna strategija prvega igralca čista:

1.6 Igre 2n ali m2

Pri igrah reda 2n ima prvi igralec 2 čisti strategiji, drugi igralec pa n čistih strategij, tj. Izplačilna matrika prvega igralca ima obliko:

Če ima taka igra sedlo, potem jo je enostavno najti in dobiti rešitev.

Predpostavimo, da ima igra sedla. Potem je treba najti takšne mešane strategije in temu primerno prvega in drugega igralca ter ceno igre v, ki zadoščajo razmerjem:

Ker igra nima sedla, neenakost (1.54) nadomestimo z neenačbami

Za reševanje sistemov (1.56), (1.55), (1.53) je priporočljivo uporabiti grafično metodo. V ta namen uvedemo zapis za levo stran neenačbe (1.53)

matrična igra matematični model

ali, če postavimo iz (1.55) in izvedemo preproste transformacije, dobimo

kje je povprečni izkupiček prvega igralca pod pogojem, da uporablja svojo mešano strategijo, drugega igralca pa svojo j-to čisto strategijo.

Po izrazu vsaka vrednost j=1, 2, …, n ustreza ravni črti v pravokotnem koordinatnem sistemu.

Cilj drugega igralca je minimizirati dobitke prvega igralca z izbiro njegovih strategij. Zato računamo

kjer je spodnja meja nabora omejitev. Na sliki 1.6 je graf funkcije prikazan z debelo črto.

Objavljeno na http://www.allbest.ru/

Slika 1.6 - graf funkcije

Cilj prvega igralca je povečati svoj dobitek z izbiro, tj. izračunati

Na sliki 1.6 pika pomeni največjo vrednost, ki jo dobimo pri. Cena igre je zato, ker:

Na ta način se grafično določita optimalna mešana strategija prvega igralca in par čistih strategij drugega igralca, ki na presečišču tvorita točko Slika 1.6 prikazuje 2. in 3. strategijo drugega igralca. Pri takšnih strategijah se neenakosti (1.53) spremenijo v enakosti. Na sliki 1.6 sta to strategiji j=2, j=3.

Zdaj lahko rešimo sistem enačb

in natančno določite vrednosti in (grafično so približno določene). Nato dodamo vse vrednosti za tiste j, za katere ne tvorijo točke, rešimo sistem enačb (1.56). Za primer, prikazan na sliki 1.6, je to naslednji sistem:

in ostalo. Ta sistem je mogoče rešiti z nagibom Če za nekaj j=j 0 strategije drugega igralca tvorijo točko M 0 in potem je največja vrednost spodnje meje nizov omejitev prikazana z odsekom, vzporednim z os V tem primeru ima prvi igralec neskončno veliko optimalnih vrednosti in ceno igre. Ta primer je prikazan na sliki 1.7, kjer segment MN prikazuje zgornje meje, optimalne vrednosti pa so v mejah Drugi igralec ima čisto optimalno strategijo j=j 0 .

Matrične igre reda m2 lahko rešujemo tudi z grafično metodo. Izplačilna matrika prvega igralca ima v tem primeru obliko

Mešane strategije prvega oziroma drugega igralca so definirane podobno kot v primeru iger reda 2n. Naj bo vrednost od 0 do 1 narisana vzdolž vodoravne osi, vrednost povprečnega dobitka) prvega igralca pa vzdolž navpične osi, pod pogoji, da prvi igralec uporabi svojo čisto i-to strategijo (i=1, 2, ..., m), drugi - njegova mešana strategija (y 1, 1- y 1) =y. Na primer, ko je m=4 grafično) lahko predstavimo, kot je prikazano na sliki 1.7.

Slika 1.7 - graf funkcije)

Prvi igralec poskuša povečati svoj povprečni izkupiček, zato si prizadeva najti

Funkcija je predstavljena z debelo črto in predstavlja zgornjo mejo nabora omejitev. Drugi igralec poskuša minimizirati tako, da izbere svojo strategijo, tj. vrednost ustreza

Na sliki je vrednost označena s piko. Z drugimi besedami, dve strategiji prvega igralca in verjetnost za drugega igralca sta določeni, pri katerih je dosežena enakost

Iz slike vidimo, da je cena igre ordinata točke, verjetnost je abscisa točke. Za preostale čiste strategije prvega igralca mora biti optimalna mešana strategija ().

Tako z reševanjem sistema (1.69) dobimo optimalno strategijo drugega igralca in ceno igre. Optimalno mešano strategijo za prvega igralca poiščemo tako, da rešimo naslednji sistem enačb:

1.7 Matrična metoda za reševanje iger

Oznake:

Katera koli kvadratna podmatrika matrike reda

Matrika (1);

Matrika prenesena v;

Matrika, adjungirana na B;

- (1) matriko, pridobljeno iz X z brisanjem elementov, ki ustrezajo vrsticam, izbrisanim iz ob prejemu;

- (1) matriko, dobljeno z brisanjem elementov, ki ustrezajo vrsticam, izbrisanim iz ob prejemu.

Algoritem:

1. Izberite kvadratno podmatriko matrike reda () in izračunajte

2. Če nekaj ali, zavrzite najdeno matriko in poskusite z drugo matriko.

3. Če (), (), izračunamo in konstruiramo X in iz in ter dodamo ničle na ustreznih mestih.

Preverjanje, ali so neenakosti izpolnjene

za vsakogar (1,75)

in neenakosti

za vsakogar (1,76)

Če eno od razmerij ni zadovoljeno, poskusimo z drugim. Če so vse relacije veljavne, potem X in zahtevane rešitve.

1.8 Metoda zaporednega približevanja cene igre

Pri proučevanju situacij v igri se lahko pogosto zgodi, da ni treba dobiti natančne rešitve igre ali pa je iz nekega razloga nemogoče ali zelo težko najti točno vrednost cene igre in optimalne mešane strategije. Nato lahko uporabite približne metode za reševanje matrične igre.

Naj opišemo eno od teh metod - metodo zaporednega približevanja cene igre. Število, izračunano pri uporabi metode, narašča približno sorazmerno s številom vrstic in stolpcev izplačilne matrike.

Bistvo metode je naslednje: igra se miselno igra večkrat, tj. Zaporedoma v vsaki igri igralec izbere strategijo, ki mu prinese največje skupne (skupne) dobitke.

Po takšni izvedbi nekaterih iger se izračuna povprečna vrednost dobitkov prvega igralca in izgub drugega igralca, njuno aritmetično povprečje pa se vzame kot približna vrednost stroškov igre. Metoda omogoča iskanje približne vrednosti optimalnih mešanih strategij obeh igralcev: potrebno je izračunati pogostost uporabe vsake čiste strategije in jo vzeti kot približno vrednost v optimalni mešani strategiji ustreznega igralca.

Dokazati je mogoče, da se bosta z neomejenim povečanjem števila programskih iger povprečni dobiček prvega igralca in povprečna izguba drugega igralca neomejeno približevali ceni igre, približne vrednosti mešanih strategij v primer, ko ima igra edinstveno rešitev, bo težil k optimalnim mešanim strategijam vsakega igralca. Na splošno je težnja približnih vrednosti nad temi vrednostmi, da se približajo pravim vrednostim, počasna. Vendar je ta postopek enostavno mehanizirati in s tem pomagati pridobiti rešitev igre z zahtevano stopnjo natančnosti tudi z izplačilnimi matrikami relativno velikega reda.

2. Praktični del

Par se odloči, kam bo šel na sprehod in čas preživljal koristno za oba.

Deklica se odloči, da gre na sprehod v park, da se naužije svežega zraka, zvečer pa si ogleda film v najbližjem kinu.

Tip predlaga, da greste v tehnološki park in si nato na osrednjem stadionu ogledate tekmo nogometašev lokalnega kluba.

V skladu s tem morate ugotoviti, koliko časa bo trajalo, da doseže cilj enega od igralcev. Zmagovalna matrika bo videti takole:

Tabela 1. Izplačilna matrika

Od 1 2 , Očitno ta igra nima sedla v čistih strategijah. Zato uporabimo naslednje formule in dobimo:

Objavljeno na http://www.allbest.ru/

2.2 Igra 2xn in mx2

Problem 1(2xn)

Za suho in mokro podnebje se gojita dva žita.

In naravno stanje lahko obravnavamo kot: suho, mokro, zmerno.

Objavljeno na http://www.allbest.ru/

Največja vrednost M() je dosežena v točki M, ki jo tvori presečišče črt, ki ustrezajo j=1, j"=2. Glede na to predpostavimo:

Problem 2 (mx2)

Fant in punca razmišljata o možnostih, kam bi šla čez vikend.

Izbira počitniškega kraja si lahko predstavljamo kot: park, kino, restavracija.

Objavljeno na http://www.allbest.ru/

Največja vrednost M() je dosežena v točki E, ki jo tvori presečišče črt, ki ustrezajo j=1, j"=2. Glede na to predpostavimo:

Za določitev vrednosti v je treba rešiti naslednje enačbe:

2.5 Matrična metoda

Dva gostinska lokala, ki si med seboj konkurirata, ponujata naslednje sklope storitev. Prva restavracija se nahaja v centru, druga pa na obrobju mesta.

Centralna restavracija vključuje naslednje storitve:

1) dražje in kakovostnejše storitve za stranke;

2) jedi so osredotočene na francosko kuhinjo;

Druga restavracija ponuja:

1) poceni in kakovostna storitev;

2) jedilnik združuje različne znane kuhinje sveta;

3) tudi stalne promocije in popusti;

4) dostavlja in sprejema naročila za dostavo na dom.

V skladu z nalogo bo dobiček za en dan med dvema restavracijama razdeljen na naslednji način:

Tabela 2. Izplačilna matrika

Reševanje igre oblike z uporabo matrične metode:

Obstaja šest podmatric in:

Razmislite o matriki:

x 1 = ? 0, x 2 = ? 0

Ker je x 2 =< 0, то мы отбрасываем.

Poglejmo zdaj matriko:

x 1 = ? 0, x 2 = ? 0

Cena igre.

To razmerje je v nasprotju z zahtevo in zato ni primerno.

Poglejmo zdaj matriko:

x 1 = , x 2 = ? 0,

y 1 =< 0, y 2 = ? 0.

Ker je y 1 =< 0, то мы отбрасываем и.

Poglejmo zdaj matriko:

x 1 = , x 2 = 0, ker je x 2 = 0, potem zavržemo in.

Poglejmo zdaj matriko:

x 1 = , x 2 = ? 0. Ker je x 1 = 0, zavržemo in.

Poglejmo zdaj matriko:

x 1 = , x 2 =, y 1 = , y 2 =, potem pa nadaljujemo naprej:

x 1 = , x 2 = , y 1 = , y 2 = ali

Cena igre.

Zdaj so osnovna razmerja preverjena:

Objavljeno na http://www.allbest.ru/

Odgovor: x 1 = , x 2 =, y 1 = , y 2 = , y 3 =0, y 4 =0,.

Rjava metoda

Na željo delavcev določenega podjetja se sindikat pogaja z njegovim vodstvom o organizaciji toplih kosil na stroške podjetja. Sindikat, ki zastopa delavce, želi zagotoviti, da bo kosilo čim bolj kakovostno in zato dražje. Vodstvo podjetja ima nasprotne interese. Strani sta se na koncu dogovorili o naslednjem. Sindikat (igralec 1) izbere enega izmed treh podjetij (A 1, A 2, A 3), ki dobavljajo tople obroke, vodstvo podjetja (igralec 2) pa izbere nabor jedi izmed treh možnih možnosti (B 1, B 2). , B 3) . Po podpisu pogodbe sindikat generira naslednjo plačilno matriko, katere elementi predstavljajo stroške kompleta posode:

Naj bo igra definirana z naslednjo izplačilno matriko:

Recimo, da je drugi igralec izbral svojo 2. strategijo, potem bo prvi prejel:

2, če uporabi svojo 1. strategijo,

3, če uporabi svojo 3. strategijo.

Dobljene vrednosti so povzete v tabeli 1.

Tabela 3. Strategija drugega igralca

Iz tabele 3 je razvidno, da bo z 2. strategijo drugega igralca prvi prejel največje izplačilo 3 z uporabo svoje 2. ali 3. strategije. Ker prvi igralec želi doseči največji dobitek, se na 2. strategijo drugega igralca odzove s svojo 2. strategijo. Z 2. strategijo prvega igralca bo drugi izgubil:

1, če uporabi svojo 1. strategijo,

3, če uporabi svojo 2. strategijo,

4, če uporabi svojo 3. strategijo.

Tabela 4. Strategija prvega igralca

Iz tabele 2 je razvidno, da bo pri 2. strategiji prvega igralca drugi igralec imel najmanjšo izgubo 1, če bo uporabil svojo 1. strategijo. Ker drugi igralec želi manj izgubiti, bo kot odgovor na 2. strategijo prvega igralca uporabil svojo 1. strategijo. Dobljeni rezultati so povzeti v tabeli 5.

Tabela 5. Strategije prvega oziroma drugega igralca

V tabeli 5 v stolpcu strategije drugega igralca v drugi vrstici je številka 1, ki označuje, da je v drugi igri koristno, da drugi igralec uporabi svojo 1. strategijo; v stolpcu je največji povprečni dobitek 3 prvega igralca, ki ga je prejel v prvi igri; stolpec w vsebuje najmanjšo povprečno izgubo 1, ki jo je prejel drugi igralec v prvi igri; stolpec v vsebuje aritmetično sredino v = (u + w) - t.j. približna vrednost cene igre, dobljene zaradi izgube ene igre v igri. Če drugi igralec uporabi svojo 1. strategijo, bo prvi prejel 3, 1, 2 s svojo 1., 2. in 3. strategijo, skupni dobitek prvega igralca za obe igri pa bo:

2 + 3=5 s svojo 1. strategijo,

3 + 1=4 s svojo 2. strategijo,

3 + 2=5 s svojo 3. strategijo.

Ti skupni dobitki so zabeleženi v drugi vrstici tabele. 3 in v stolpcih, ki ustrezajo strategijam prvega igralca: 1, 2, 3.

Od vseh skupnih dobitkov je največji 5. Pridobi se s 1. in 3. strategijo prvega igralca, nato pa lahko izbere katero koli izmed njih; Recimo, da v takih primerih, ko sta dva (ali več) enakih skupnih dobitkov, izberite strategijo z najnižjo številko (v našem primeru moramo vzeti 1. strategijo).

S 1. strategijo prvega igralca bo drugi izgubil 3, 2, 3 glede na svojo 1., 2., 3. strategijo, skupna izguba drugega igralca za obe igri pa bo:

1 + 3=4 s svojo 1. strategijo,

3 + 2=5 s svojo 2. strategijo,

4 + 3=7 s svojo 3. strategijo.

Te skupne izgube so zabeležene v drugi vrstici tabele. 5 in v stolpcih, ki ustrezajo 1., 2., 3. strategiji drugega igralca.

Od vseh skupnih izgub drugega igralca je najmanjša 4. Dobljena je z njegovo 1. strategijo, zato mora drugi igralec v tretji igri uporabiti svojo 1. strategijo. Največji skupni dobitek prvega igralca v dveh igrah, deljen s številom iger, je postavljen v stolpec, tj. Stolpec w vsebuje najmanjši skupni poraz drugega igralca v dveh igrah, deljen s številom iger, tj. v stolpcu v je podana aritmetična sredina teh vrednosti, tj. = Ta številka je vzeta kot približna vrednost cene igre z dvema "odigranima" igrama.

Tako dobimo naslednjo tabelo 4 za dve igri.

Tabela 6. Skupni dobitki in porazi igralcev po dveh odigranih igrah

V tretji vrstici tabele 6 v stolpcu strategije drugega igralca je številka 1, ki pomeni, da mora drugi igralec v tretji igri uporabiti svojo 1. strategijo. V tem primeru prvi igralec zmaga 3, 1, 2 z uporabo svoje 1., 2., 3. strategije, njegov skupni dobitek v treh igrah pa bo:

3 + 5 = 8 s svojo 1. strategijo,

1 +4 = 5 s svojo 2. strategijo,

2 + 5 = 7 s svojo 3. strategijo.

Ti skupni dobitki prvega igralca so zabeleženi v tretji vrstici tabele 6 in v stolpcih, ki ustrezajo njegovim strategijam 1, 2, 3. Ker je največji skupni dobitek 8 prvega igralca dosežen s 1. strategijo, je izbrana 1. temu primerno.

S 1. strategijo prvega igralca bo drugi izgubil 3, 1, 2 glede na svojo 1., 2., 3. strategijo, skupna izguba drugega igralca za obe igri pa bo:

3 + 4=7 s svojo 1. strategijo,

2 + 5=7 s svojo 2. strategijo,

3 + 7 = 10 s svojo 3. strategijo.

Te skupne izgube so zabeležene v tretji vrstici tabele. 6 in v stolpcih, ki ustrezajo 1., 2., 3. strategiji drugega igralca. Od vseh njegovih skupnih izgub je 7 najmanjša in jo doseže s svojo 1. in 2. strategijo, potem mora drugi igralec uporabiti svojo 1. strategijo.

V tabeli 6 v tretji vrstici v stolpcu in beleži največje skupne dobitke prvega igralca v treh igrah, deljeno s številom iger, tj. v stolpec w je vpisan najmanjši skupni poraz drugega igralca v treh igrah, deljen s številom iger, tj. stolpec v vsebuje njihovo aritmetično sredino

Tako dobimo mizo. 7 za tri igre.

Tabela 7. Skupni dobitki in porazi igralcev po treh odigranih igrah

Tabela 8. Finalna miza po dvajsetih odigranih igrah

Iz mize 7 in 8 je razvidno, da se v 20 izgubljenih igrah strategije 1, 2, 3 za prvega igralca pojavijo 12-krat, 3-krat, 5-krat, torej so njihove relativne frekvence enake; strategije 1, 2, 3 za drugega igralca se pojavijo 7, 11, 2-krat, zato so njihove relativne frekvence vsakokrat enake; približna cena igre. Ta približek je kar dober.

Nazadnje upoštevajte, da če ima igra več kot eno rešitev, bodo približki stroškov igre še vedno približali dejanske stroške igre za nedoločen čas, relativne frekvence strategij igralcev pa ne bodo več nujno približale dejanski optimalni mešanici igralcev strategije.

Analiza rezultatov

V tem tečaju smo proučevali gradivo iskanja rešitev iger z ničelno vsoto z uporabo grafične, matrične metode in metode zaporednega približevanja cene igre. Ugotovljene so bile optimalne strategije prvega in drugega igralca ter stroški igranja v igrah 2x2, 2xn in mx2 ter v igrah po matrični metodi in Brownovi metodi.

Na primeru para je bila simulirana igra 2x2, ki smo jo reševali z algebraično in grafično metodo. Če igro rešimo algebraično, rešitev pokaže, da bosta z uporabo svojih optimalnih mešanih strategij prvi in ​​drugi igralec skupaj preživela 4,6 ure. Grafična rešitev problema je bila pridobljena z majhno napako in je znašala 4,5 ure.

Prav tako sta bila simulirana dva problema 2xn in mx2. V problemu 2xn je bil upoštevan kmetijski pridelek in strategija kaže, da je bolje zasaditi polje 50 proti 50, cena igre pa je bila 3,75 milijona rubljev. In v problemu mx2 je bil obravnavan par, katerega strategija je pokazala, da je ceneje iti v park in kino, stroški pa bi bili 4,3 rublja.

Za matrično metodo je bil modeliran problem, pri katerem sta bili obravnavani dve restavraciji; reševanje problema je pokazalo, da bo pri uporabi optimalne mešane strategije dobiček prve restavracije 15,6 milijona rubljev, pri uporabi optimalne mešane strategije druge restavracije pa dobiček 15,6 milijona rubljev. restavraciji, ne bo dovolil, da bi prvi zaslužil več kot 15,6 milijona rubljev. Grafična rešitev je povzročila napako in cena igre je bila 14,9 milijona rubljev.

Za Brownovo metodo je bila sestavljena naloga, v kateri sta upoštevana sindikat in vodstvo podjetja, njihova naloga je zagotoviti delavcem hrano. Če oba igralca uporabljata svoje optimalne strategije, bo hrana na osebo 2,45 tisoč rubljev.

Seznam uporabljenih virov

1) Vilisov V.Ya. Zapiski predavanj “Teorija iger in statistične odločitve”, - podružnica - “Voskhod” MAI. 1979. 146 str.

2) Kruševski A.V. Teorija iger, - Kijev: Vishcha School, 1977. - 216 str.

3) Churchmen U., Akof R., Arnof L., Uvod v operacijske raziskave. - M.: Znanost. 1967. - 488 str.

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

Objavljeno na Allbest.ru

Podobni dokumenti

Odločanje kot posebna vrsta človekove dejavnosti. Racionalna predstavitev matrike igre. Primeri matričnih iger v čistih in mešanih strategijah. Operacijske raziskave: odnos problemov linearnega programiranja z modelom teorije iger.

tečajna naloga, dodana 05.05.2010


Večkrat ponovljene igre, njihove značilne lastnosti in stopnje. Mešane strategije, pogoji in možnosti njihove uporabe v praksi. Analitična metoda za reševanje igre tipa 2 x 2. Osnovni izreki za pravokotne igre. Algebraične rešitve.

predstavitev, dodana 23.10.2013


Osnovne definicije teorije bimatričnih iger. Primer bimatrične igre "Učenec-učitelj". Mešane strategije v bimatričnih igrah. Poiščite "ravnotežno situacijo". 2x2 bimatrične igre in formule za primer, ko ima vsak igralec dve strategiji.

povzetek, dodan 13.02.2011


Naučite se splošnih informacij o matričnih igrah in igrah z ničelno vsoto. Koncept pozicijske igre, drevesa, množice informacij. Upoštevanje načela maksimina in načela ravnotežja. Paretova optimalnost. Pozicijska neantagonistična igra, njene lastnosti.

predmetno delo, dodano 17.10.2014


Teorija iger je veja matematike, katere predmet je preučevanje matematičnih modelov za sprejemanje optimalnih odločitev v razmerah konflikta. Iterativna Brown-Robinsonova metoda. Monotoni iterativni algoritem za reševanje matričnih iger.

diplomsko delo, dodano 08.08.2007


Sestavljanje plačilne matrike, iskanje spodnjih in zgornjih neto cen igre, maximin in minimax strategij igralcev. Poenostavitev plačilne matrike. Reševanje matrične igre z redukcijo na problem linearnega programiranja in dodatkom »Išči rešitev«.

test, dodan 10.11.2014


Teorija iger je matematična teorija konfliktnih situacij. Razvoj matematičnega modela igre dveh oseb z ničelno vsoto, njegova implementacija v obliki programskih kod. Metoda za rešitev problema. Vhodni in izhodni podatki. Program, navodila za uporabo.

tečajna naloga, dodana 17.08.2013


Osnove simpleksne metode, ocena njene vloge in pomena v linearnem programiranju. Geometrična interpretacija in algebraični pomen. Iskanje maksimuma in minimuma linearne funkcije, posebni primeri. Reševanje problema z matrično simpleksno metodo.

diplomsko delo, dodano 01.06.2015


Tehnike za konstruiranje matematičnih modelov računalniških sistemov, ki odražajo strukturo in procese njihovega delovanja. Število dostopov do datoteke v procesu reševanja povprečnega problema. Ugotavljanje možnosti polaganja datotek v zunanje pomnilniške pogone.

laboratorijske vaje, dodano 21.06.2013


Oblikovanje matematičnega modela. Opis igre tic-tac-toe. Model logične igre, ki temelji na Boolovi algebri. Digitalne elektronske naprave in razvoj njihovega matematičnega modela. Igralna konzola, igralni krmilnik, linija igralnega polja.

Moskovski energetski inštitut

(Tehnična univerza)

Laboratorijski izvid

v teoriji iger

“Program za iskanje optimalnih strategij za seznanjeno igro z ničelno vsoto, podano v matrični obliki”

Izpolnili učenci

skupina A5-01

Ašrapov Daler

Olga Ašrapova

Osnovni koncepti teorije iger

Teorija iger je zasnovana za razrešitev konfliktne situacije , tj. situacije, v katerih se srečajo 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.

Pokliče se eno samo igranje igre od začetka do konca zabava . Rezultat igre je plačilo (oz dobitki ).

Zabavo sestavljajo premika , tj. izbire igralcev iz določenega nabora možnih alternativ.

Premiki so lahko osebno in naključen.Osebna poteza , Za razliko od naključen , vključuje 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 govorijo tudi o strategije igralec, tj. o pravilu ali nizu pravil, ki določajo igralčevo izbiro. Hkrati mora biti strategija celovita, tj. izbira mora biti določena za vsako možno situacijo med igro.

Problem teorije iger– iskanje optimalnih strategij za igralce, tj. strategije, ki jim zagotavljajo največji dobiček ali minimalno izgubo.

Klasifikacija teoretičnih modelov iger

Igra n osebe so običajno označene kot, kje
- nabor strategij i-tega igralca,
- plačilo za igro.

V skladu s to oznako je mogoče predlagati naslednjo klasifikacijo teoretičnih modelov iger:

Diskretno (več strategij diskretno)

Končno

Neskončno

Neprekinjeno (več strategij neprekinjeno)

Neskončno

n osebe (
)

Koalicija (zadruga)

Nekoalicijski (nesodelujoči)

2 osebi (pari)

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 ozadje igre, tj. vse poteze nasprotnika)

Z nepopolnimi informacijami

Z ničelnim zneskom (skupno plačilo je enako nič)

Neničelna vsota

Ena poteza (loterija)

Večkratni prehod

Matrična predstavitev igre z ničelno vsoto v paru

V tej vadnici si bomo ogledali antagonistične igre dveh oseb , podan v matrični obliki. To pomeni, da poznamo veliko strategij prvega igralca (player A){ A jaz }, jaz = 1,…, m in različne strategije za drugega igralca (igralec B){ B j }, j = 1,..., n, in tudi glede na matriko A = || a ij || dobitek prvega igralca. Ker govorimo o antagonistični igri, se predpostavlja, da je dobiček prvega igralca enak izgubi drugega. Predpostavimo, da je matrični element a ij– dobitek prvega igralca, ko izbere strategijo A jaz in odgovor drugega igralca nanj s strategijo B j. Takšno igro bomo označili kot
, Kje m - število strategij igralcev A,n - število strategij igralcev IN. Na splošno ga lahko predstavi naslednja tabela:

Primer 1

Kot preprost primer razmislite o igri, v kateri je igra sestavljena iz dveh potez.

1. poteza: igralec A izbere eno izmed številk (1 ali 2), ne da bi o svoji izbiri obvestil nasprotnika.

2. poteza: igralec IN izbere eno od številk (3 ali 4).

Spodnja črta: Izbira igralcev A in IN zložite. Če je vsota soda, potem IN plača svojo vrednost igralcu A, če je liho - obratno, A plača znesek igralcu IN.

To igro lahko predstavimo v obliki
na naslednji način:

Lahko vidimo, da je ta igra antagonistična, poleg tega je igra z nepopolnimi informacijami, ker igralcu IN, naredil osebno potezo, ni znano, kakšno izbiro je igralec izbral A.

Kot je navedeno zgoraj, je naloga teorije iger najti optimalne strategije igralcev, tj. strategije, ki jim zagotavljajo največji dobiček ali minimalno izgubo. Ta proces se imenuje rešitev igre .

Ko rešujete igro v matrični obliki, preverite prisotnost igre sedlo . Če želite to narediti, se vneseta dve vrednosti:

– nižja ocena cene igre in

– zgornja ocena cene igre.

Prvi igralec bo med vsemi možnimi odgovori drugega igralca najverjetneje izbral strategijo, pri kateri bo prejel največjo zmago, drugi igralec pa bo, nasprotno, izbral tisto, ki minimizira lastno izgubo, tj. morebitna zmaga prvega.

To je mogoče dokazati α ≤ V ≤ β , Kje V–cena igre , tj. verjetna zmaga prvega igralca.

Če relacija drži α = β = V, potem pravijo, da igra ima sedlo
, In mogoče rešiti v čistih strategijah . Z drugimi besedami, obstaja nekaj strategij
, ki daje igralcu AV.

Primer 2

Vrnimo se k igri, ki smo jo obravnavali v primeru 1, in jo preverimo glede prisotnosti sedla.

Za to igro
= -5,
= 4,
, torej nima sedla.

Naj še enkrat opozorimo na dejstvo, da je ta igra igra z nepopolnimi informacijami. V tem primeru lahko igralcu le svetujemo A izberite strategijo , Ker v tem primeru lahko dobi največji dobitek, vendar glede na igralčevo izbiro IN strategije .

Primer 3

Naredimo nekaj sprememb v pravilih igre iz primera 1. Priskrbeli bomo igralca IN informacije o izbiri igralca A. Potem imejte IN pojavili se bosta dve dodatni strategiji:

- strategija, ki je koristna za A.Če izbira A - 1, to IN izbere 3 po izbiri A - 2, to IN izbere 4;

- strategija, ki ni koristna za A.Če izbira A - 1, to IN izbere 4 po izbiri A - 2, to IN izbere 3.

Ta igra je s popolnimi informacijami.

V tem primeru
= -5,
= -5,
, torej ima igra sedlo
. Ta sedlna točka ustreza dvema paroma optimalnih strategij:
in
. Cena igre V= -5. Očitno je, da za A taka igra je nerentabilna.

Primera 2 in 3 sta dobra ilustracija naslednjega izreka, dokazanega v teoriji iger:

1. izrek

Vsako seznanjeno antagonistično igro s popolnimi informacijami je mogoče rešiti v čistih strategijah.

to. Izrek 1 pravi, da ima vsaka igra za dva igralca s popolnimi informacijami sedlo in da obstaja par čistih strategij
, ki daje igralcu A trajnih dobitkov, ki so enaki ceni igre V.

V primeru odsotnosti sedla je t.i mešane strategije :, Kje str jaz inq j– verjetnosti izbire strategij A jaz in B j prvi oziroma drugi igralec. Rešitev igre v tem primeru je par mešanih strategij
, kar poveča matematično pričakovanje cene igre.

Naslednji izrek posplošuje izrek 1 na primer igre z nepopolnimi informacijami:

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 A trajnih dobitkov, ki so enaki ceni igre V, in α ≤ 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 nič.

Najenostavnejši primer, ki je podrobno razvit v teoriji iger, je igra parov s končno ničelno vsoto (antagonistična igra dveh oseb ali dveh koalicij). Razmislite o igri G, v kateri sodelujeta dva igralca A in B, ki imata nasprotne interese: dobiček enega je enak izgubi drugega. Ker je izkupiček igralca A enak izkupičku igralca B z nasprotnim predznakom, nas lahko zanima samo izkupiček igralca a. Seveda A želi maksimizirati, B pa želi minimizirati a.

Za poenostavitev se miselno poistovetimo z enim od igralcev (naj bo to A) in ga imenujemo »mi«, igralca B pa »nasprotnik« (seveda iz tega ne izhajajo nobene prave prednosti za A). Naj imamo možne strategije in nasprotnika - možne strategije (takšni igri pravimo igra). Označimo svoj dobitek, če uporabljamo strategijo in nasprotnik uporablja strategijo

Tabela 26.1

Predpostavimo, da nam je izkupiček (ali povprečni izkupiček) a znan za vsak par strategij. Potem je načeloma mogoče sestaviti pravokotno tabelo (matriko), ki navaja strategije igralcev in pripadajoče izplačila (glej tabelo 26.1).

Če je taka tabela sestavljena, potem pravijo, da je bila igra G reducirana na matrično obliko (spraviti igro v takšno obliko je že sama po sebi lahko težka naloga, včasih pa skoraj nemogoča, zaradi ogromne raznolikosti 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

Oglejmo si primer igre G (4X5) v matrični obliki. Na voljo imamo štiri strategije (na izbiro), sovražnik pa pet strategij. Matrica igre je podana v tabeli 26.2

Pomislimo, kakšno strategijo naj uporabimo (igralec A)? V Matrix 26.2 je mamljivo izplačilo "10"; smo v skušnjavi, da bi izbrali strategijo, v kateri bomo dobili to »sladkost«.

Toda počakajte: tudi sovražnik ni bedak! Če bomo izbrali strategijo, bo on, nam navkljub, izbral strategijo, mi pa bomo dobili neko patetično izplačilo "1". Ne, ne morete izbrati strategije! Kako biti? Očitno je, da moramo na podlagi načela previdnosti (in to je osnovno načelo teorije iger) izbrati strategijo, pri kateri je naš najmanjši dobiček največji.

Tabela 26.2

To je tako imenovano "mini-max načelo": ravnajte tako, da glede na za vas najslabše vedenje vašega nasprotnika dobite največjo zmago.

Prepišimo tabelo 26.2 in v desni dodatni stolpec zapišimo najmanjšo dobitno vrednost v vsaki vrstici (minimum vrstice); označimo jo za vrstico a (glej tabelo 26.3).

Tabela 26.3

Od vseh vrednosti (desni stolpec) je največja (3) označena. Strategija temu ustreza. Z izbiro te strategije smo lahko v vsakem primeru prepričani, da bomo (za kakršno koli obnašanje sovražnika) zmagali nič manj kot 3. Ta vrednost je naša zajamčena zmaga; Če se obnašamo previdno, manj od tega ne moremo dobiti, morda bomo dobili več).

Ta dobitek se imenuje nižja cena igre (ali "maximin" - največji od najmanjših dobitkov). Označili ga bomo kot a. V našem primeru

Zdaj pa vzemimo sovražnikovo stališče in razlog zanj. Ni nekakšen pajdaš, je pa tudi pameten! Pri izbiri strategije bi rad dal manj, a mora računati na naše najslabše obnašanje zanj. Če bo izbral strategijo, mu bomo odgovorili in dal bo 10; če se bo odločil, mu bomo odgovorili in bo dal, itd. Tabeli 26.3 bomo dodali dodatno spodnjo vrstico in vanjo zapisali maksimume stolpcev. Očitno mora previden nasprotnik izbrati strategijo, v kateri je ta vrednost minimalna (ustrezna vrednost 5 je označena v tabeli 26.3) . Ta vrednost P je vrednost dobitka, več od katere nam razumen nasprotnik zagotovo ne bo dal. Imenuje se zgornja cena igre (ali "mi-nimax" - najmanjši največji dobitek). V našem primeru in se doseže s sovražnikovo strategijo

Torej, na podlagi načela previdnosti (pozavarovalno pravilo »vedno računaj na najslabše!«) moramo izbrati strategijo A in sovražnika - strategijo. Take strategije imenujemo »minimax« (izhaja iz načela minimax). Dokler se obe strani v našem primeru držita svojih minimax strategij, bo izplačilo

Zdaj pa si za trenutek predstavljajmo, da smo izvedeli, da sovražnik sledi strategiji. Daj no, kaznovajmo ga za to in izberimo strategijo, dobili bomo 5 in to ni tako slabo. Toda sovražnik tudi ni neuspeh; mu sporočite, da je naša strategija , bo tudi on pohitel z izbiro, naš dobitek zmanjšal na 2 itd. (partnerja sta "hitela s strategijami"). Skratka, minimax strategije v našem primeru so nestabilne glede na informacije o vedenju druge strani; te strategije nimajo lastnosti ravnotežja.

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 ceni: . Kaj iz tega sledi? Minimax strategiji igralcev A in B bosta stabilni. Dokler se jih držita oba igralca, je izkupiček 6. Poglejmo, kaj se zgodi, če (A) ugotovimo, da se nasprotnik (B) drži strategije B?

Tabela 26.4

Spremenilo pa se ne bo popolnoma nič, saj lahko vsako odstopanje od strategije naš položaj samo poslabša. Prav tako informacije, ki jih prejme nasprotnik, ga ne bodo prisilile, da odstopa od svoje strategije.Par strategij ima lastnost ravnovesja (uravnotežen par strategij), izkupiček (v našem primeru 6), dosežen s tem parom strategij se imenuje "sedlo točke matrike". Znak prisotnosti sedla in uravnoteženega para strategij je enakost spodnje in zgornje cene igre; skupna vrednost se imenuje cena igre. Označili ga bomo

Strategije (v tem primeru), pri katerih je ta dobiček dosežen, se imenujejo optimalne čiste strategije, njihova celota pa rešitev igre. V tem primeru za samo igro pravijo, da je rešena v čistih strategijah. Obema strankama A in B je mogoče dati svoje optimalne strategije, v katerih je njun položaj najboljši možni. In če igralec A zmaga 6 in igralec B izgubi, so to pogoji igre: za A so koristni, za B pa neugodni.

Bralec se lahko vpraša: zakaj se optimalne strategije imenujejo "čiste"? Če pogledamo malo naprej, bomo odgovorili na to vprašanje: obstajajo "mešane" strategije, ki so sestavljene iz dejstva, da igralec ne uporablja samo ene strategije, ampak več, ki jih naključno prepletajo. Če torej poleg čistih dovolimo tudi mešane strategije, ima vsaka končna igra rešitev – ravnotežno točko. Toda o tem je treba še razpravljati.

Prisotnost sedla v igri še zdaleč ni pravilo, temveč izjema. Večina iger nima sedla. Vendar pa obstaja vrsta igre, ki ima vedno sedlo in se zato rešuje v čistih strategijah. To so tako imenovane »igre s popolnimi informacijami«. Igra s popolnimi informacijami je igra, pri kateri vsak igralec ob vsaki osebni potezi pozna celotno ozadje svojega razvoja, torej rezultate vseh predhodnih potez, osebnih in naključnih. Primeri iger s popolnimi informacijami so: dama, šah, tic-tac-toe itd.

V teoriji iger je dokazano, da ima vsaka igra s popolnimi informacijami sedlo in se zato rešuje v čistih strategijah. V vsaki igri s popolnimi informacijami obstaja par optimalnih strategij, ki dajejo stabilen izkupiček, ki je enak stroškom igre in. Če je taka igra sestavljena samo iz osebnih potez, potem bi se morala, ko vsak igralec uporabi svojo optimalno strategijo, končati na zelo določen način - z zmago, ki je enaka ceni igre. To pomeni, da č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 naključno izbereta položaj središča kovanca (medsebojno prekrivanje kovancev ni dovoljeno). Zmaga tisti, ki vloži zadnji cent (če za druge ni več prostora). Preprosto 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 nasprotnikovo potezo odgovoriti s simetrično potezo. Očitno se ne glede na to, kako se sovražnik obnaša, izgubi ne more izogniti. Popolnoma enaka je situacija s šahom in igrami na splošno s popolnimi informacijami: vsaka od njih, zapisana v matrični obliki, ima sedlo, kar pomeni, da je rešitev v čistih strategijah in je torej smiselna le, dokler je ta rešitev ne najde. Recimo, da se šahovska partija ali vedno konča z zmago belih, ali vedno z zmago črnih, ali vedno z remijem, vendar še ne vemo, kaj točno (na srečo ljubiteljev šaha). Naj še dodamo: v doglednem času verjetno ne bomo vedeli, saj je število strategij tako ogromno, da je igro izjemno težko (če ne nemogoče) spraviti v matrično obliko in v njej najti sedlo.

Zdaj pa se vprašajmo, kaj storiti, če igra nima sedla: No, če je vsak igralec prisiljen izbrati eno samo čisto strategijo, potem ni kaj storiti: voditi nas mora načelo minimaksa. Druga stvar je, če lahko "mešate" svoje strategije, jih naključno izmenjujete z nekaj verjetnosti. Uporaba mešanih strategij je mišljena na naslednji 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 strategijo, ki se je pojavila (žerebanje 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.

Pogovorimo se torej o mešanih strategijah. Označili bomo mešani strategiji igralcev A oziroma B, pri čemer je (ki tvori skupno eno) - verjetnost, da bo igralec A uporabljal strategije - verjetnost, da bo igralec B uporabljal strategije

V posebnem primeru, ko so vse verjetnosti razen ena enake nič, ta pa je enaka ena, se mešana strategija spremeni v čisto.

Obstaja temeljni izrek teorije iger: vsaka končna igra dveh oseb z ničelno vsoto ima vsaj eno rešitev - par optimalnih strategij, na splošno mešanih, in ustrezno ceno

Par optimalnih strategij, ki tvorita rešitev igre, ima naslednjo lastnost: če se eden od igralcev drži svoje optimalne strategije, potem drugemu ne more biti donosno odstopati od svoje. Ta par strategij tvori določeno ravnotežno pozicijo v igri: en igralec želi dobiček spremeniti v maksimum, drugi - v minimum, vsak vleče v svojo smer in z razumnim vedenjem obeh doseže ravnotežje in stabilen dobiček. v so vzpostavljeni. Če je potem igra koristna za nas, če - za sovražnika; ko je igra »poštena«, enako koristna za oba udeleženca.

Oglejmo si primer igre brez sedla in podajte (brez dokaza) njeno rešitev. Igra poteka takole: dva igralca A in B hkrati in brez besed pokažeta en, dva ali tri prste. Skupno število prstov odloča o dobitku: če je sodo, A zmaga in prejme od B znesek, ki je enak temu številu; če je liho, potem, nasprotno, A plača B-ju 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 3x3 je podana v tabeli 26.5; dodatni desni stolpec prikazuje minimume vrstic, dodatna spodnja vrstica pa prikazuje maksimume stolpcev.

Nižja cena igre ustreza strategiji, kar pomeni, da z razumnim, previdnim ravnanjem zagotavljamo, da ne bomo izgubili več kot 3. Slaba tolažba, a še vedno boljša kot recimo dobitek 5, ki ga najdemo v nekaterih celicah matrice. Hudo nam je, igralec L ... A naj se tolažimo: zdi se, da je položaj sovražnika še slabši: nižja cena igre je pri. razumno vedenje nam bo dal vsaj 4.