Antagonistične igre z neprekinjenimi strategijami. Reševanje matričnih antagonističnih iger Reševanje antagonističnih iger na spletu

Pokliče se igra dveh oseb z ničelno vsoto, v kateri ima vsaka od njiju končen nabor strategij. Pravila matrične igre določa matrika izplačil, katere elementi so izkupički prvega igralca, ki so hkrati tudi izgube drugega igralca.

Igra Matrix je antagonistična igra. Prvi igralec prejme največji zajamčeni (neodvisen od vedenja drugega igralca) izkupiček, ki je enak ceni igre, podobno pa drugi igralec doseže minimalno zajamčeno izgubo.

Spodaj strategijo razumemo kot niz pravil (načel), ki določajo izbiro različice dejanj za vsako osebno potezo igralca, odvisno od trenutne situacije.

Zdaj o vsem po vrstnem redu in podrobno.

Izplačilna matrika, čiste strategije, cena igre

AT matrična igra njegova pravila so določena izplačilna matrika .

Razmislite o igri, v kateri sta dva udeleženca: prvi in ​​drugi igralec. Naj ima prvi igralec mčiste strategije in na razpolago drugemu igralcu - nčiste strategije. Ker gre za igro, je naravno, da so v tej igri zmage in izgube.

AT plačilna matrika elementi so številke, ki izražajo dobičke in izgube igralcev. Dobitki in porazi so lahko izraženi v točkah, denarju ali drugih enotah.

Ustvarimo matriko izplačil:

Če prvi igralec izbere jaz-th čista strategija in drugi igralec j-th čista strategija, potem je izplačilo prvega igralca aij enote, izpad drugega igralca pa tudi aij enote.

Ker aij + (- a ij ) = 0, potem je opisana igra matrična igra z ničelno vsoto.

Najenostavnejši primer matrične igre je met kovanca. Pravila igre so naslednja. Prvi in ​​drugi igralec vržeta kovanec in rezultat je glava ali rep. Če so istočasno vržene glave in glave ali repi ali repi, bo prvi igralec dobil eno enoto, v drugih primerih pa bo izgubil eno enoto (drugi igralec bo dobil eno enoto). Drugemu igralcu sta na voljo isti dve strategiji. Ustrezna matrika izplačil bi bila:

Naloga teorije iger je določiti izbiro strategije prvega igralca, ki bi mu zagotovila največji povprečni dobiček, kot tudi izbiro strategije drugega igralca, ki bi mu zagotovila največjo povprečno izgubo.

Kako se izbere strategija v matrični igri?

Ponovno poglejmo matriko izplačil:

Najprej določimo izplačilo prvega igralca, če ga uporabi jazčista strategija. Če prvi igralec uporabi jaz-th čisto strategijo, potem je logično domnevati, da bo drugi igralec uporabil tako čisto strategijo, zaradi katere bi bil izkupiček prvega igralca minimalen. Po drugi strani bo prvi igralec uporabil tako čisto strategijo, ki bi mu zagotovila največji izkupiček. Na podlagi teh pogojev se dobiček prvega igralca, ki ga označujemo kot v1 , je poklican maximin zmaga oz nižja cena igre .

pri za te vrednosti mora prvi igralec postopati na naslednji način. Iz vsake vrstice izpišite vrednost minimalnega elementa in med njimi izberite največjega. Tako bo izplačilo prvega igralca največje ali najmanjše. Od tod tudi ime - maximin win. Številka vrstice tega elementa bo številka čiste strategije, ki jo je izbral prvi igralec.

Zdaj pa določimo izgubo drugega igralca, če uporabi j-ta strategija. V tem primeru prvi igralec uporablja svojo čisto strategijo, pri kateri bi bila izguba drugega igralca največja. Drugi igralec mora izbrati tako čisto strategijo, pri kateri bi bila njegova izguba minimalna. Izpad drugega igralca, kar označujemo kot v2 , je poklican minimalna izguba oz najvišja cena igre .

pri reševanje problemov o ceni igre in določanje strategije če želite določiti te vrednosti za drugega igralca, nadaljujte na naslednji način. Iz vsakega stolpca izpišite vrednost največjega elementa in med njimi izberite najmanjšega. Tako bo izguba drugega igralca najmanjša ali največja. Od tod tudi ime - minimax gain. Številka stolpca tega elementa bo številka čiste strategije, ki jo je izbral drugi igralec. Če drugi igralec uporabi "minimax", bo ne glede na izbiro strategije prvega igralca izgubil največ v2 enote.

Primer 1

.

Največji od najmanjših elementov vrstic je 2, to je nižja cena igre, prva vrstica ji ustreza, zato je maksimalna strategija prvega igralca prva. Najmanjši od največjih elementov stolpcev je 5, to je zgornja cena igre, drugi stolpec ji ustreza, zato je minimax strategija drugega igralca druga.

Zdaj, ko smo se naučili najti spodnjo in zgornjo ceno igre, strategiji maximin in minimax, je čas, da se naučimo, kako te koncepte formalno označiti.

Torej je zajamčeno izplačilo prvega igralca:

Prvi igralec mora izbrati čisto strategijo, ki bi mu zagotovila največ minimalnih izplačil. Ta dobiček (maksimin) je označen na naslednji način:

.

Prvi igralec uporablja svojo čisto strategijo, tako da je izguba drugega igralca največja. Ta izguba je opredeljena na naslednji način:

Drugi igralec mora izbrati svojo čisto strategijo, tako da je njegova izguba minimalna. Ta izguba (minimax) je označena na naslednji način:

.

Še en primer iz iste serije.

Primer 2 Podana je matrična igra z matriko izplačil

.

Določite maximin strategijo prvega igralca, minimax strategijo drugega igralca, spodnjo in zgornjo ceno igre.

rešitev. Desno od izplačilne matrike izpišemo najmanjše elemente v njenih vrsticah in označimo največje od njih, na dnu matrike pa največje elemente v stolpcih in izberemo najmanjše od njih:

Največji od najmanjših elementov vrstic je 3, to je nižja cena igre, druga vrstica ji ustreza, zato je maximin strategija prvega igralca druga. Najmanjši od največjih elementov stolpcev je 5, to je zgornja cena igre, prvi stolpec ji ustreza, zato je minimax strategija drugega igralca prva.

Sedlo v matričnih igrah

Če sta zgornja in spodnja cena igre enaki, se šteje, da ima matrična igra sedlo. Velja tudi obratno: če ima matrična igra sedlo, potem sta zgornja in spodnja cena matrične igre enaki. Ustrezni element je tako najmanjši v vrstici kot največji v stolpcu in je enak ceni igre.

Torej, če je , potem je optimalna čista strategija prvega igralca in je optimalna čista strategija drugega igralca. To pomeni, da sta enaki nižja in zgornja cena igre doseženi na istem paru strategij.

V tem primeru matrična igra ima rešitev v čistih strategijah .

Primer 3 Podana je matrična igra z matriko izplačil

.

rešitev. Desno od izplačilne matrike izpišemo najmanjše elemente v njenih vrsticah in označimo največje od njih, na dnu matrike pa največje elemente v stolpcih in izberemo najmanjše od njih:

Spodnja cena igre je enaka zgornji ceni igre. Tako je cena igre 5. To je . Cena igre je enaka vrednosti sedla. Maximin strategija prvega igralca je druga čista strategija, minimax strategija drugega igralca pa tretja čista strategija. Ta matrična igra ima rešitev v čistih strategijah.

Sami rešite problem matrične igre in si nato oglejte rešitev

Primer 4 Podana je matrična igra z matriko izplačil

.

Poiščite spodnjo in zgornjo ceno igre. Ali ima ta matrična igra sedlo?

Matrične igre z optimalno mešano strategijo

V večini primerov matrična igra nima sedla, zato ustrezna matrična igra nima čistih strateških rešitev.

Ima pa rešitev v optimalnih mešanih strategijah. Da bi jih našli, je treba predpostaviti, da se igra ponovi tolikokrat, da je na podlagi izkušenj mogoče uganiti, katera strategija je boljša. Zato je odločitev povezana s konceptom verjetnosti in povprečja (pričakovanja). V končni rešitvi je tako analog sedla (to je enakost spodnje in zgornje cene igre) kot analog strategij, ki jim ustrezajo.

Torej, da bi prvi igralec dosegel največji povprečni dobiček in da bi imel drugi igralec najmanjšo povprečno izgubo, je treba z določeno verjetnostjo uporabljati čiste strategije.

Če prvi igralec uporablja čiste strategije z verjetnostmi , nato vektor se imenuje mešana strategija prvega igralca. Z drugimi besedami, gre za »mešanico« čistih strategij. Vsota teh verjetnosti je enaka ena:

.

Če drugi igralec uporablja čiste strategije z verjetnostmi , nato vektor se imenuje mešana strategija drugega igralca. Vsota teh verjetnosti je enaka ena:

.

Če prvi igralec uporablja mešano strategijo str, in drugi igralec - mešana strategija q, potem je smiselno pričakovana vrednost prvi igralec zmaga (drugi igralec izgubi). Če ga želite najti, morate pomnožiti vektor mešane strategije prvega igralca (ki bo matrika z eno vrstico), matriko izplačila in vektor mešane strategije drugega igralca (ki bo matrika z enim stolpcem):

.

Primer 5 Podana je matrična igra z matriko izplačil

.

Določite matematično pričakovanje dobička prvega igralca (izgube drugega igralca), če je mešana strategija prvega igralca , mešana strategija drugega igralca pa .

rešitev. Po formuli za matematično pričakovanje dobička prvega igralca (izgube drugega igralca) je enako zmnožku vektorja mešane strategije prvega igralca, matrike izplačila in vektorja mešane strategije drugega igralca:

Prvi igralec se imenuje takšna mešana strategija, ki bi mu zagotovila največji povprečni izkupiček, če se igra dovoljkrat ponovi.

Optimalna mešana strategija Drugi igralec se imenuje takšna mešana strategija, ki bi mu zagotovila najmanjšo povprečno izgubo, če se igra ponovi dovoljkrat.

Po analogiji z zapisom maximin in minimax v primerih čistih strategij so optimalne mešane strategije označene kot sledi (in so povezane z matematičnim pričakovanjem, to je povprečjem, dobička prvega igralca in izgube drugega igralca):

,

.

V tem primeru za funkcijo E tam je sedlo , kar pomeni enakost.

Da bi našli optimalne mešane strategije in sedlo, tj. reši matrično igro v mešanih strategijah , morate matrično igro reducirati na problem linearnega programiranja, to je na problem optimizacije, in rešiti ustrezen problem linearnega programiranja.

Redukcija matrične igre na problem linearnega programiranja

Če želite rešiti matrično igro v mešanih strategijah, morate sestaviti ravno črto problem linearnega programiranja in njegova dvojna naloga. V dualnem problemu je razširjena matrika, ki shranjuje koeficiente spremenljivk v sistemu omejitev, konstantne člene in koeficiente spremenljivk v ciljni funkciji, transponirana. V tem primeru je minimum ciljne funkcije prvotnega problema povezan z maksimumom v dvojnem problemu.

Ciljna funkcija v problemu neposrednega linearnega programiranja:

.

Sistem omejitev v neposrednem problemu linearnega programiranja:

Ciljna funkcija v dvojnem problemu:

.

Sistem omejitev v dvojnem problemu:

Označite optimalni načrt problema neposrednega linearnega programiranja

,

in optimalni načrt dualnega problema je označen z

Linearne oblike za ustrezne optimalne načrte bomo označili z in ,

in jih morate najti kot vsoto ustreznih koordinat optimalnih načrtov.

V skladu z definicijami prejšnjega razdelka in koordinatami optimalnih načrtov veljajo naslednje mešane strategije prvega in drugega igralca:

.

Matematiki so to dokazali cena igre je izražena v smislu linearnih oblik optimalnih načrtov, kot sledi:

,

to je recipročna vrednost vsot koordinat optimalnih načrtov.

Mi, praktiki, lahko to formulo uporabimo le za reševanje matričnih iger v mešanih strategijah. Všeč mi je formule za iskanje optimalnih mešanih strategij prvi oziroma drugi igralec:

v kateri so drugi faktorji vektorji. Optimalne mešane strategije so tudi vektorji, kot smo definirali že v prejšnjem odstavku. Če torej število (ceno igre) pomnožimo z vektorjem (s koordinatami optimalnih načrtov), ​​dobimo tudi vektor.

Primer 6 Podana je matrična igra z matriko izplačil

.

Poiščite ceno igre V in optimalne mešane strategije in .

rešitev. Sestavimo problem linearnega programiranja, ki ustreza tej matrični igri:

Dobimo rešitev neposrednega problema:

.

Linearno obliko optimalnih načrtov najdemo kot vsoto najdenih koordinat.

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 Vrstni red igre 2v2

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 2xn in mx2 igre

2.3 Matrična metoda

2.4 Brownova metoda

Analiza rezultatov

Uvod

Antagonistična igra je igra z ničelno vsoto. Antagonistična igra je nekooperativna igra, v kateri sodelujeta dva igralca, katerih izplačila so 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 pridružuje vsakemu paru strategij (x, y), kjer je realno število, ki ustreza koristnosti prvega igralca pri realizaciji te situacije.

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

Zgodovinsko gledano so antagonistične igre prvi razred matematičnih modelov teorije iger, ki so bili uporabljeni za opis igre na srečo. Menijo, da je zahvaljujoč temu predmetu raziskav teorija iger dobila ime. Trenutno 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, njihovo možna dejanja in razdelitev dobitkov glede na njihovo vedenje in rezultate. Igralec se šteje za enega udeleženca ali skupino udeležencev v igri, ki imajo zanje 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 ustaviti se pri eni od njegovih možnosti vedenja. Igralec nato to izbiro naredi s potezami. Narediti potezo pomeni v določeni fazi igre narediti celotno ali delno izbiro 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 od igralcev poskuša upoštevati podatke o preteklem razvoju igre, če tako možnost dovoljujejo pravila igre.

Niz pravil, ki igralcu nedvoumno povedo, kakšno izbiro naj naredi pri vsaki potezi glede na situacijo, ki je nastala kot rezultat igre, se imenuje 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 indikacij za katero koli stanje informacij, ki so na voljo igralcu na kateri koli stopnji razvoja igre. Že to kaže, da so strategije lahko dobre in slabe, uspešne in neuspešne itd.

Igra z ničelno vsoto bo potekala, ko bo vsota izplačil vseh igralcev v vsaki 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 dveh igralcev z ničelno vsoto 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

Na igro matrike z ničelno vsoto za dva igralca lahko gledamo kot na naslednjo abstraktno igro dveh igralcev.

Prvi igralec ima m strategij i =1, 2,…, m, drugi ima n strategij j = 1, 2,…, n. Vsakemu paru strategij (i, j) je dodeljeno število a ij , ki izraža izplačilo prvega igralca pripada drugemu igralcu, če prvi uporabi svojega i-ta strategija, in drugi - svojo j-to strategijo.

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

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

Matrična igra dveh igralcev z ničelno vsoto se bo imenovala preprosto 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) reda m izplačil prvega igralca.

Ob upoštevanju izplačilne matrike

potem se izvedba vsake igre matrične igre z matriko A zmanjša na izbiro prvega igralca i-ta vrstica, in s strani drugega igralca v j-tem stolpcu in prvi igralec (na račun drugega) prejme izplačilo, ki se nahaja 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 sestaviti matriko izplačil.

Naslednji korak je določitev optimalnih strategij in izplačil igralcev.

Glavna stvar pri preučevanju iger je koncept optimalnih strategij za igralce. Ta koncept ima intuitivno naslednji pomen: igralčeva strategija je optimalna, če mu uporaba te strategije zagotavlja največji zajamčeni izkupiček za vse možne strategije drugega igralca. Na podlagi teh pozicij prvi igralec preuči matriko A svojih izplačil v skladu s formulo (1.1), kot sledi: za vsako vrednost i (i = 1, 2, ..., m) se minimalna vrednost izplačila določi glede na o strategijah, 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 najmanjših izplačil najde taka 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žji neto strošek igre in kaže, kakšen minimalni izkupiček si lahko prvi igralec zagotovi z uporabo svojih čistih strategij za vsa možna dejanja drugega igralca.

Drugi igralec naj si s svojim optimalnim obnašanjem prizadeva, če je le mogoče, zmanjšati izkupiček prvega igralca na račun njegovih strategij. Zato za drugega igralca najdemo

t.j. določen je največji izkupiček prvega igralca, pod pogojem, da drugi igralec uporabi svoje j-th čist strategijo, potem drugi igralec najde svojo strategijo j = j 1, za katero prvi igralec prejme minimalno izplačilo, tj. najde

Opredelitev. Število β, določeno s formulo (1.5), se imenuje neto zgornji strošek igre in kaže, kakšen največji dobiček si prvi igralec lahko zagotovi zaradi svojih strategij. Z drugimi besedami, z uporabo svojih čistih strategij lahko prvi igralec zagotovi izplačilo vsaj b, drugi igralec pa lahko z uporabo svojih čistih strategij prepreči, da bi prvi igralec zmagal več kot c.

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 = c (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 njegovega izplačila, najslabše vedenje pa lahko povzroči zmanjšanje njegovega izplačila, 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) -- strategije, ki tvorijo sedlo. V nadaljevanju bomo pokazali, da je definicija sedla enakovredna pogojem (1.8).

Tako je na podlagi (1.8) element sedla najmanj v i 0 -ti vrstici in maksimum v j 0 -tem stolpcu v matriki A. Iskanje sedla matrike A je enostavno: v matriki A, zaporedoma v vsaki vrstici poiščite najmanjši element 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 izhaja, da

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

Na desni strani neenakosti (1.12) je y poljuben, torej

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 spodnji neto cena ne presega zgornje neto vrednosti igre 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 veljajo 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 z iskanjem te točke študij igre konča. Če v matrični igri v čistih strategijah ni sedla, potem lahko najdemo spodnjo in zgornjo čisto ceno te igre, ki nakazujeta, da prvi igralec ne sme upati na izplačilo, večje od zgornje cene igre, in ste lahko prepričani, da boste prejeli izplačilo, ki ni manjše od nižje cene 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šitve matričnih iger je treba iskati v uporabi tajnosti uporabe čistih strategij in možnosti večkratnega ponavljanja iger v obliki partij. Tako se na primer igra serija iger šaha, dame, nogometa in vsakič igralci svoje strategije uporabijo tako, da se nasprotniki ne zavedajo njihove vsebine, in na tej poti dosegajo določene dobitke v povprečju z igranje celotne serije iger. Ti izkupički so v povprečju večji od nižje cene igre in manjši od zgornje cene igre. Večja kot je ta povprečna vrednost, tem boljša strategija uporabi igralec. Zato se je pojavila ideja, da bi čiste strategije uporabljali naključno, z določeno verjetnostjo. To v celoti zagotavlja tajnost njihove uporabe. Vsak igralec lahko spremeni verjetnost uporabe svojih čistih strategij na tak način, da maksimira svoj povprečni izkupiček in ob tem pridobi optimalne strategije. Ta ideja je vodila do koncepta mešane strategije.

Opredelitev. Mešana strategija igralca 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 t ), ki izpolnjujejo odnosi

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

Podobno je za drugega igralca, ki ima n čistih strategij, mešana strategija y množica števil y = (y 1 ,…, y j , … y n), ki izpolnjujejo 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. Poleg tega so edini možni dogodki.

Jasno je, da je čista strategija poseben primer mešane strategije. Dejansko, če v mešani strategiji koli i-ta mreža strategija uporabljena z verjetnostjo ena, potem vse druge čiste strategije niso uporabljene. In ta i-ta čista strategija je poseben primer mešane strategije. Za ohranitev tajnosti vsak igralec uporablja svoje lastne strategije ne glede na izbiro 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 povečati svoj povprečni izkupiček E (A, x, y) s spreminjanjem svojih mešanih strategij x, drugi igralec pa želi narediti E (A, x, y) minimalen s svojimi mešanimi strategijami, tj. za rešitev igre je treba najti takšne x, y, za katere je dosežena zgornja cena igre.

1.3 Naročite igro 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. V ta namen 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 se tak element nahaja v drugi vrstici, potem je to element sedla.

Z najdbo sedla, če ta obstaja, se postopek iskanja njegove rešitve zaključi, saj se v tem primeru najde cena igre - sedlo in sedlo, torej par čistih strategij za prvo in drugo. igralcev, ki sestavljajo optimalne čiste strategije. Če v čistih strategijah ni sedla, potem je treba najti sedlo v mešanih strategijah, ki po glavnem izreku 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 \u003d 1 - x 1 pa je verjetnost, da bo uporabil svojo drugo strategijo. Podobno za drugega igralca: 1 - verjetnost uporabe prve strategije, y 2 = 1 - 1 - verjetnost uporabe druge strategije.

Glede na posledico izreka je za optimalnost mešanih strategij x in y nujno in zadostno, da za nenegativne x 1 , x 2 , y 1 , y 2 veljajo naslednje relacije:

Zdaj pokažemo, da če matrična igra nima sedla v čistih strategijah, potem se morajo te neenakosti spremeniti v enakosti:

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

0<<1, 0<< 1,

0< <1, 01. (1.25)

Recimo, 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 lahko dokažemo, da obe neenakosti v (1.23) ne moreta biti strogi neenakosti.

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

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

Če sta obe neenakosti (1.24) strogi, potem po izreku x1 = x2 = 0, kar je v nasprotju z (1.25). Če pa je a 12 a 22 , potem je ena od neenakosti (1.27) stroga, druga pa je enakost. Poleg tega bo enakost veljala za večji element iz 12 in 22, kar pomeni, da mora biti ena neenakost iz (1.27) 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, se neenakosti (1.22) spremenijo v enakosti za optimalne strategije prvega igralca. Podobni argumenti o neenakosti (1.23) bodo vodili 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 tudi, da če ima v matrični igri 2x2 eden od igralcev optimalno čisto strategijo, potem ima tudi drugi igralec optimalno čisto strategijo.

Če torej matrična igra nima sedla v čistih strategijah, potem mora imeti rešitev v mešanih strategijah, ki so določene iz enačb (1.24). Sistemska rešitev (1.25)

1.4 Algebraična metoda

Obstajata dva primera reševanja problemov z algebraično metodo:

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ščite strategije in Ko prvi igralec uporabi svojo optimalno strategijo, lahko drugi igralec na primer uporabi dve takšni čisti strategiji

Hkrati pa na podlagi lastnosti, če eden od igralcev uporablja optimalno mešano strategijo, drugi pa katero koli čisto, vključeno v njegovo optimalno mešano strategijo z neničelno verjetnostjo, potem matematično pričakovanje izplačila vedno ostane nespremenjena in enaka ceni igre, tj.

Izkupiček mora biti v vsakem od teh primerov enak vrednosti igre V. V tem primeru veljajo naslednje relacije:

Sistem enačb, podoben (2.5), (2.6), je mogoče sestaviti tudi za optimalno strategijo drugega igralca:

Ob upoštevanju pogoja normalizacije:

Rešimo enačbo (1.37) - (1.41) skupaj glede na neznanke in ne vseh naenkrat, ampak po tri: 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 zelo enostavno dobimo z grafično metodo. Njegovo bistvo je naslednje:

Slika 1.1 - iskanje odseka enote dolžine

Izberite odsek enote dolžine na abscisni osi. Na levem koncu bo prikazana prva strategija prvega igralca, na desnem koncu pa drugega. Vse vmesne točke ustrezajo mešanim strategijam prvega igralca, dolžina segmenta na desni strani točke pa je enaka verjetnosti uporabe prve strategije, dolžina segmenta na levi pa je verjetnosti uporabe druga strategija prvega igralca.

Izvedeni sta dve osi I-I in II-II. Na I-I bomo izplačilo odložili, ko bo prvi igralec uporabil prvo strategijo, na II-II, ko bo uporabil drugo strategijo. Recimo, da je drugi igralec uporabil 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 odvisen od velikosti segmenta. Vrstica I-I ustreza uporabi prve strategije s strani drugega igralca, imenovali jo bomo prva strategija drugega igralca. Drugo strategijo drugega igralca je mogoče sestaviti podobno. 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 vrednosti igre V.

Linija 1N2 se imenuje spodnja črta izplačila. Tukaj je jasno razvidno, da točka N ustreza največji vrednosti zajamčenega izplačila prvega igralca.

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

ali na osi II-II

Vendar pa lahko tudi strategijo drugega igralca definiramo na enak način kot za prvega igralca, tj. zgraditi takšen grafikon.

Slika 1.3 - opredelitev strategije drugega igralca

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

Glede na specifične vrednosti koeficientov imajo lahko grafične matrike tudi drugačno obliko, na primer, kot sledi:

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 za prvega igralca je:

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

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

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

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

matrična igra matematični model

ali z nastavitvijo iz (1.55) in izvajanjem preprostih transformacij dobimo

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

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

Cilj drugega igralca je zmanjšati dobiček 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.

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

Slika 1.6 - graf funkcije

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

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

Tako sta grafično določena optimalna mešana strategija prvega igralca in par čistih strategij drugega igralca, ki tvorita točko na presečišču 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 določene približno). Nato postavite vse vrednosti na tiste j, za katere ne tvorijo točke, in rešite 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 naklonom. Če za nekaj j=j 0 strategije drugega igralca tvorijo točko M 0 in potem je največja vrednost spodnje meje nizov omejitev predstavljena z odsekom, vzporednim z V tem primeru ima prvi igralec neskončno veliko optimalnih vrednosti in ceno igre. Ta primer, prikazan na sliki 1.7, kjer in segment MN predstavljata zgornjo mejo, optimalne vrednosti so v mejah. drugi igralec ima čisto optimalno strategijo j=j 0 .

Matrične igre reda m2 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 na enak način kot v primeru iger reda 2n. Naj bo vrednost od 0 do 1 narisana vzdolž vodoravne osi, vrednost povprečnega izplačila) prvega igralca na navpični osi pod pogoji, da prvi igralec uporablja 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 poskuša najti

Funkcija je prikazana kot debela črta 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, definirani sta taki dve strategiji prvega igralca in verjetnost za drugega igralca, pri katerih je dosežena enakost

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

Tako z reševanjem sistema (1.69) dobimo optimalno strategijo drugega igralca in vrednost 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

Matrica (1);

Matrika prenesena v;

Matrica pritrjena na B;

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

- (1) matriko, pridobljeno z brisanjem elementov, ki ustrezajo vrsticam, ki so bile izbrisane 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 zgradimo X in iz in ter dodamo ničle na ustreznih mestih.

Preverjanje, ali so neenakosti izpolnjene

za vsako (1,75)

in neenakosti

za vsako (1,76)

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

1.8 Metoda zaporednega približevanja cene igre

Pri preučevanju igralnih situacij se lahko pogosto zgodi, da ni potrebno dobiti natančne rešitve igre ali pa je iz nekega razloga nemogoče ali zelo težko najti točno vrednost stroškov 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 izplačil, izračunanih z metodo, narašča približno sorazmerno s številom vrstic in stolpcev izplačilne matrike.

Bistvo metode je naslednje: miselno se igra igra večkrat, tj. zaporedoma v vsaki igri igralec izbere strategijo, ki mu daje največji skupni (skupni) izkupiček.

Po takšni izvedbi nekaterih iger izračuna povprečno vrednost dobitka prvega igralca in poraza drugega igralca, njuno aritmetično sredino pa vzame kot okvirno vrednost cene 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.

Dokaže se lahko, 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 je rešitev igre edinstvena, bo težil k optimalnim mešanim strategijam vsakega igralca. Na splošno je približevanje vrednosti nad določenimi vrednostmi pravim vrednostim počasno. Vendar pa je ta proces mogoče enostavno mehanizirati in tako 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 preživljal čas v korist dveh.

Deklica se odloči, da gre na sprehod v park, da se naužije svežega zraka, zvečer pa gre na ogled filma v najbližji kino.

Tip se ponudi, da gre v tehnopark, potem ko si ogleda tekmo nogometašev lokalnega kluba na osrednjem stadionu.

V skladu s tem morate ugotoviti, kako dolgo bo cilj enega od igralcev dosežen. Izplačilna matrika bo videti takole:

Tabela 1. Matrika izplačil

Od 1 2 naprej v tej igri v čistih strategijah očitno ni sedla. Zato uporabimo naslednje formule in dobimo:

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

2.2 Igranje 2xn in mx2

Problem 1(2xn)

Za suho in vlažno podnebje se gojita dva pridelka.

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

Gostuje 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. Zato predpostavimo: ,

Problem 2 (mx2)

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

Izbira kraja počitka je lahko predstavljena kot: park, kino, restavracija.

Gostuje 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. Zato predpostavimo: ,

Če želite določiti vrednost v, morate rešiti naslednje enačbe:

2.5 Matrična metoda

Dva konkurenčna gostinska lokala (catering) 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 boljš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 redne akcije in popusti;

4) izvaja dostavo 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. Matrika izplačil

Reševanje igre oblike na matričen način:

Obstaja šest podmatric in:

Razmislite o matriki:

x 1 =? 0,x2=? 0

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

Razmislite zdaj o matriki:

x 1 =? 0,x2=? 0

Cena igre.

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

Razmislite zdaj o matriki:

x 1 = , x 2 = ? 0,

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

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

Razmislite zdaj o matriki:

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

Razmislite zdaj o matriki:

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

Razmislite zdaj o matriki:

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 glavne relacije preverjene:

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

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

Rjava metoda

Na zahtevo delavcev določenega podjetja se sindikat pogaja z njegovim vodstvom o organizaciji tople prehrane na stroške podjetja. Sindikat, ki zastopa interese delavcev, skrbi, da je obrok čim bolj kakovosten in zato dražji. Vodstvo podjetja ima nasprotujoče si interese. Strani sta se na koncu dogovorili o naslednjem. Sindikat (1. igralec) izbere enega od treh podjetij (A 1, A 2, A 3), ki dobavljajo tople obroke, vodstvo podjetja (2. igralec) pa izbere nabor jedi izmed treh možnih možnosti (B 1, B 2, B 3) . Po podpisu pogodbe sindikat oblikuje naslednjo plačilno matriko, katere elementi predstavljajo stroške kompleta posode:

Naj bo igra podana z naslednjo izplačilno matriko:

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

2, če uporabi svojo 1. strategijo,

3, če uporabi svojo 3. strategijo.

Dobljene vrednosti so povzete v tabeli 1.

Tabela 3. Strategija drugega igralca

Tabela 3 kaže, da bo z 2. strategijo drugega igralca prvi igralec prejel največje izplačilo 3 z uporabo svoje 2. ali 3. strategije. Ker prvi igralec želi doseči največji izkupiček, 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

Tabela 2 kaže, da bo imel drugi igralec z 2. strategijo prvega igralca 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, kar pomeni, da je v drugi igri koristno, da drugi igralec uporabi svojo 1. strategijo; v stolpcu in je največji povprečni izkupiček 3 prvega igralca, ki ga je prejel v prvi igri; stolpec w vsebuje najmanjšo povprečno izgubo 1 drugega igralca v prvi igri; stolpec v vsebuje aritmetično sredino v = (u + w) -- to je približna vrednost cene igre, ki jo dobimo kot rezultat igranja ene igre v igri. Če drugi igralec uporabi svojo 1. strategijo, bo prvi igralec s svojo 1., 2. in 3. strategijo prejel 3, 1, 2, skupni izkupiček 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 izplačil je največji 5. Dobi se s 1. in 3. strategijo prvega igralca, nato lahko izbere katero koli izmed njih; recimo, v takih primerih, ko sta dva (ali več) enakih skupnih izplačil, se izbere strategija z najmanjšim številom (v našem primeru moramo vzeti 1. strategijo).

S 1. strategijo prvega igralca bo drugi igralec izgubil 3, 2, 3 v tem zaporedju s svojo 1., 2. in 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 v tretji igri drugi igralec uporabiti svojo 1. strategijo. V stolpec in vnesite največji skupni izkupiček prvega igralca v dveh igrah, deljen s številom iger, tj. stolpec w vsebuje najmanjšo skupno izgubo drugega igralca v dveh igrah, deljeno s številom iger, tj. aritmetična sredina teh vrednosti se vnese v stolpec v, tj. = Ta številka se vzame kot približna vrednost cene igre z dvema "odigranima" igrama.

Tako dobimo naslednjo tabelo 4, za dva niza igre.

Tabela 6. Skupni dobički in porazi igralcev v dveh odigranih igrah

V tretji vrstici tabele 6 je v stolpcu strategije drugega igralca številka 1, kar 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 izkupiček za tri igre pa bo:

3 + 5 = 8 pri njegovi prvi strategiji,

1 +4 = 5 s svojo 2. strategijo,

2 + 5 = 7 za njegovo 3. strategijo.

Ti skupni izkupički prvega igralca so zabeleženi v tretji vrstici tabele 6 in stolpcih, ki ustrezajo njegovim strategijam 1, 2, 3. Ker je največji skupni izkupiček 8 prvega igralca dosežen s 1. strategijo, izbere prvo ustrezno. .

Pri 1. strategiji prvega igralca bo drugi igralec izgubil 3, 1, 2 oziroma pri 1., 2., 3. strategiji, 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 največji skupni dobitek prvega igralca v treh igrah, deljen s številko igre, tj. stolpec w vsebuje najmanjši skupni poraz drugega igralca v treh igrah, deljen s številom iger, tj. v stolpec v vpišite njihovo aritmetično sredino

Tako dobimo tabelo. 7 za tri stranke.

Tabela 7. Skupni dobički in porazi igralcev v treh odigranih igrah

Tabela 8. Finalna miza z dvajsetimi odigranimi igrami

Iz tabele. 7 in 8 je razvidno, da se v 20 izgubljenih igrah strategije 1, 2, 3 za prvega igralca pojavijo 12, 3, 5-krat, torej so njihove relativne frekvence enake; strategije 1, 2, 3 se za drugega igralca pojavijo 7 oziroma 11,2-krat, zato sta njihovi relativni frekvenci enaki; približna vrednost cene igre. Ta približek je dovolj dober.

Na koncu ugotavljamo, da če ima igra več kot eno rešitev, se bodo približne vrednosti stroškov igre še vedno približevale resničnim stroškom igre za nedoločen čas, relativne frekvence pojavljanja strategij igre igralci se ne bodo več nujno približali resničnim optimalnim mešanim strategijam igralcev.

Analiza rezultatov

V tem predmetu se gradivo za iskanje rešitve antagonističnih iger preučuje z grafično, matrično metodo, metodo zaporednega približevanja cene igre. Najdene so optimalne strategije prvega in drugega igralca ter cena igre v igrah 2x2, 2xn in mx2 ter v igrah z uporabo matrične metode in Brownove metode.

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

Prav tako sta bili modelirani dve nalogi 2xn in mx2. V problemu 2xn je bila upoštevana kmetijska kultura in strategija kaže, da je bolje zasaditi polje 50 krat 50, cena igre pa je bila 3,75 milijona rubljev. In v problemu mx2 je bil upoštevan par, katerega strategija je pokazala, da je ceneje iti v park in kino, cena in stroški pa bodo 4,3 rublja.

Naloga je bila modelirana za matrično metodo, v kateri sta bili obravnavani dve restavraciji, rešitev problema je pokazala, da bo dobiček prve restavracije pri uporabi optimalne mešane strategije 15,6 milijona rubljev, pri uporabi optimalne mešane strategije pa druga restavracija, ne bo dovolila, da bi prva zaslužila več kot 15,6 milijona rubljev. Rešitev z grafično metodo je dala napako in cena igre je bila 14,9 milijona rubljev.

Za Brownovo metodo je bila izdelana naloga, v kateri sta upoštevana sindikat in vodstvo podjetja, katerih naloga je zagotoviti prehrano delavcev. Ko oba igralca uporabita svoje optimalne strategije, bo hrana na osebo znašala 2,45 tisoč rubljev.

Seznam uporabljenih virov

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

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

3) Cherchmen 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

Gostuje 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.

seminarska naloga, dodana 05.05.2010


Večkrat ponovljene igre, njihove značilne lastnosti in stopnje. Mešane strategije, pogoji in možnosti za njihovo uporabo v praksi. Analitična metoda za reševanje igre 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 stanje". 2x2 bimatrične igre in formule za primer, ko ima vsak igralec dve strategiji.

povzetek, dodan 13.02.2011


Študij splošnih informacij o matričnih in antagonističnih igrah. Koncept pozicijske igre, drevesa, niza informacij. Upoštevanje načela maksimina in načela ravnotežja. Paretova optimalnost. Pozicijska neantagonistična igra, njene lastnosti.

seminarska naloga, dodana 17.10.2014


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

diplomsko delo, dodano 08.08.2007


Sestavljanje matrike izplačil, 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 reševanja problema. Vhodni in izhodni podatki. Program, navodila za uporabo.

seminarska 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šitev 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 datotek med povprečno nalogo. 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. Logični model igre, ki temelji na Boolovi algebri. Digitalne elektronske naprave in razvoj njihovega matematičnega modela. Igralna konzola, igralni krmilnik, vrvica za igralno ploščo.

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

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 A i, nasprotnik B j. Če je igra sestavljena samo iz osebnih potez, potem izbira strategij A i in B j enolično določa izid igre – naš izkupiček (pozitiven ali negativen). Označimo ta dobiček kot aij(zmaga, ko izberemo strategijo A i, in sovražnik - strategije B j).

Če igra poleg osebnih naključnih potez vsebuje izplačilo za par strategij A i, B j 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 ( A i), stolpci pa prikazujejo nasprotnikove strategije ( B j):

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 šahovsko partijo je število možnih strategij 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:

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 A i:

in v matriko igre dodajte stolpec, ki vsebuje te vrednosti:

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 A i:

β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 A i:

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.

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 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 poimenujemo "mi", igralca B pa "nasprotnik" (seveda iz tega ne sledijo nobene prave prednosti za A). Naj imamo možne strategije in nasprotnika - možne strategije (takšni igri pravimo igra). Označimo naš izkupiček, če uporabljamo strategijo in nasprotnik uporablja strategijo

Tabela 26.1

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

Če je taka tabela sestavljena, potem naj bi bila igra G zreducirana na matrično obliko (samo po sebi je lahko že zaradi ogromnega števila strategij spraviti igro v takšno obliko težka naloga, včasih pa tudi praktično nemogoča). ). 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

Razmislite o primeru igre G (4X5) 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 uporabljamo (igralec A)? Matrix 26.2 ima vabljivo izplačilo "10"; vleče nas, da izberemo strategijo, v kateri bomo dobili to »sladkost«.

Toda počakaj, tudi sovražnik ni neumen! Če bomo izbrali strategijo, bo on, nam navkljub, izbral strategijo, mi pa bomo dobili neko mizerno izplačilo "1". Ne, ne morete izbrati strategije! Kako biti? Očitno moramo, izhajajoč iz načela previdnosti (in to je glavno načelo teorije iger), izbrati strategijo, pri kateri je naš minimalni dobiček največji.

Tabela 26.2

To je tako imenovani "mini-max princip": ravnaj tako, da z najslabšim vedenjem nasprotnika dosežeš največjo korist.

Prepišemo tabelo 26.2 in v desni dodatni stolpec zapišemo minimalno vrednost dobička v vsaki vrstici (minimum vrstice); označimo za vrstico a (glej tabelo 26.3).

Tabela 26.3

Od vseh vrednosti (desni stolpec) je izbrana največja (3). Ujema se s strategijo. Ko smo izbrali to strategijo, smo lahko v vsakem primeru prepričani, da (za kakršno koli vedenje sovražnika) ne bomo pridobili manj kot 3. Ta vrednost je naš zajamčeni dobiček; če se obnašamo previdno, ne moremo dobiti manj od tega, lahko dobimo več).

To izplačilo se imenuje nižja cena igre (ali "maximin" - največje izmed najmanjših izplačil). Označili ga bomo kot a. V našem primeru

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 bo izbral strategijo, mu bomo odgovorili in dal bo 10; če se bo odločil, mu bomo odgovorili in nam bo vrnil itd. V tabelo 26.3 dodamo dodatno spodnjo vrstico in vanjo zapišemo največje število stolpcev. Očitno mora previden nasprotnik izbrati strategijo, za katero 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 z nasprotnikovo strategijo

Torej, na podlagi načela previdnosti (pravilo pozavarovanja »vedno računaj na najslabše!«) moramo izbrati strategijo A in sovražnika - strategijo.Takšne 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 predstavljajte, da smo izvedeli, da sovražnik sledi strategiji. Daj no, kaznujmo ga za to in izberimo strategijo, dobimo 5 in to ni tako slabo. A konec koncev tudi sovražnik ni miss; mu sporočite, da je naša strategija , bo tudi pohitel z izbiro , zmanjšal naš izplačilo na 2 itd. (partnerji so "hiteli okoli strategij"). Skratka, minimax strategije v našem primeru so nestabilne glede na informacije o obnašanju nasprotne strani; 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: . Kaj iz tega sledi? Minimax strategiji igralcev A in B bosta stabilni. Dokler se jih oba igralca držita, je izkupiček 6. Poglejmo, kaj se zgodi, če (A) ugotovimo, da se nasprotnik (B) drži strategije B?

Tabela 26.4

In prav nič se ne bo spremenilo, kajti vsako odstopanje od strategije lahko samo poslabša naše stanje. Prav tako informacije, ki jih prejme nasprotnik, ga ne bodo prisilile, da bi odstopil od svoje strategije. 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 se ta dobiček doseže, imenujemo optimalne čiste strategije, njihova kombinacija pa je rešitev igre. V tem primeru naj bi bila igra sama rešena v čistih strategijah. Obema stranema A in B je mogoče dati svoje optimalne strategije, v katerih je njun položaj najboljši možni. In da igralec A zmaga 6 in igralec B izgubi, no, to so pogoji igre: so koristni za A in neugodni za B.

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 priznamo poleg čistih tudi mešane strategije, ima vsaka končna igra rešitev - ravnotežno točko. A več o tem šele sledi.

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 popolnimi informacijami je igra, pri kateri vsak igralec ob vsaki osebni potezi pozna celotno predzgodovino 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 dokazano, da ima vsaka igra s popolnimi informacijami sedlo in jo je zato mogoče rešiti v čistih strategijah. V vsaki igri s popolnimi informacijami obstaja par optimalnih strategij, ki daje stabilen izkupiček, ki je enak ceni igre in. Č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.

Prvič mora namreč postaviti nikl 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. Popolnoma enaka je situacija 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 najden. Recimo igra šaha ali se vedno konča z zmago belih, ali se vedno konča z zmago črnih, ali se vedno konča z remijem, a kaj 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.

In zdaj 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 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 so v teoriji iger 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 igre 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šani strategiji igralcev A oziroma B

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

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

Par optimalnih strategij, ki tvorijo 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 nekakšno ravnotežje v igri: en igralec želi izkupiček obrniti na maksimum, drugi na minimum, vsak vleče v svojo smer in ob razumnem vedenju obeh se vzpostavita ravnovesje in stabilen izkupiček v. Če je potem igra koristna za nas, če - za sovražnika; ko je igra "poštena", enako koristna za oba udeleženca.

Razmislite o primeru 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. O dobitku odloča skupno število prstov: če je sodo, zmaga A 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 je skladna s strategijo, kar pomeni, da z razumnim, previdnim ravnanjem zagotavljamo, da ne bomo izgubili več kot 3. Slaba tolažba, a vseeno boljša od recimo zmage - 5, najdemo v nekaterih celice matriksa. Hudo je za nas, igralec L ... Toda potolažimo se: nasprotnikov položaj se zdi še slabši: nižja cena igre pri. razumnega vedenja, nam bo dal najmanj 4.