Antagonističke igre s kontinuiranim strategijama. Rješavanje matričnih antagonističkih igara Rješavanje antagonističkih igara online

Poziva se igra s nultim zbrojem za dvije osobe u kojoj svaka od njih ima konačan skup strategija. Pravila matrične igre određena su matricom dobitaka čiji su elementi dobitci prvog igrača, a koji su ujedno i gubici drugog igrača.

Matrix igra je antagonistička igra. Prvi igrač dobiva maksimalnu zajamčenu (neovisno o ponašanju drugog igrača) isplatu jednaku cijeni igre, slično tome, drugi igrač ostvaruje minimalni zajamčeni gubitak.

Pod, ispod strategija shvaća se kao skup pravila (načela) koji određuju izbor varijante radnji za svaki osobni potez igrača, ovisno o trenutnoj situaciji.

Sada o svemu po redu i detaljno.

Isplatna matrica, čiste strategije, cijena igre

NA igra matrice određena su njegova pravila isplatna matrica .

Razmotrimo igru ​​u kojoj sudjeluju dva igrača: prvi i drugi igrač. Neka ima prvi igrač mčiste strategije, a na raspolaganju drugom igraču - nčiste strategije. Budući da se igra razmatra, prirodno je da u ovoj igri postoje dobici i gubici.

NA platna matrica elementi su brojevi koji izražavaju dobitke i gubitke igrača. Dobici i gubici mogu se izraziti u bodovima, novcu ili drugim jedinicama.

Kreirajmo matricu isplate:

Ako prvi igrač odabere ja-th čista strategija, a drugi igrač j-th čista strategija, tada je isplata prvog igrača ai J jedinice, a gubitak drugog igrača je također ai J jedinice.

Jer aij + (- a ij ) = 0, tada je opisana igra matrična igra s nultim zbrojem.

Najjednostavniji primjer matrix igre je bacanje novčića. Pravila igre su sljedeća. Prvi i drugi igrač bacaju novčić i rezultat je glava ili rep. Ako se u isto vrijeme bacaju glave i glave ili repovi ili repovi, tada će prvi igrač osvojiti jednu jedinicu, au ostalim slučajevima će izgubiti jednu jedinicu (drugi igrač će osvojiti jednu jedinicu). Iste dvije strategije stoje na raspolaganju drugom igraču. Odgovarajuća matrica isplate bila bi:

Zadatak teorije igara je odrediti izbor strategije prvog igrača, koja bi mu jamčila najveći prosječni dobitak, kao i izbor strategije drugog igrača, koja bi mu jamčila najveći prosječni gubitak.

Kako se odabire strategija u matrix igri?

Pogledajmo ponovo matricu isplata:

Prvo, utvrđujemo isplatu prvog igrača ako ga koristi jačista strategija. Ako prvi igrač koristi ja-tu čistu strategiju, onda je logično pretpostaviti da će drugi igrač koristiti takvu čistu strategiju, zbog koje bi dobitak prvog igrača bio minimalan. Zauzvrat, prvi igrač će koristiti takvu čistu strategiju koja bi mu omogućila maksimalnu isplatu. Na temelju ovih uvjeta, isplata prvog igrača, koju označavamo kao v1 , Zove se maksimalna pobjeda ili niža cijena igre .

Na za ove vrijednosti, prvi igrač treba postupiti na sljedeći način. Iz svakog retka ispišite vrijednost minimalnog elementa i odaberite najveći među njima. Stoga će isplata prvog igrača biti maksimum od minimuma. Otuda i naziv - maximin win. Broj linije ovog elementa bit će broj čiste strategije koju je izabrao prvi igrač.

Sada odredimo gubitak drugog igrača ako ga koristi j-ta strategija. U ovom slučaju prvi igrač koristi svoju čistu strategiju, u kojoj bi gubitak drugog igrača bio maksimalan. Drugi igrač mora odabrati takvu čistu strategiju u kojoj bi njegov gubitak bio minimalan. Gubitak drugog igrača, što označavamo kao v2 , Zove se minimalni gubitak ili najviša cijena igre .

Na rješavanje problema o cijeni igre i određivanje strategije da biste odredili ove vrijednosti za drugog igrača, postupite na sljedeći način. Iz svakog stupca ispišite vrijednost maksimalnog elementa i odaberite minimalni među njima. Tako će gubitak drugog igrača biti minimum od maksimuma. Otuda i naziv - minimax gain. Broj stupca ovog elementa bit će broj čiste strategije koju je izabrao drugi igrač. Ako drugi igrač koristi "minimax", tada će bez obzira na izbor strategije od strane prvog igrača izgubiti najviše v2 jedinice.

Primjer 1

.

Najveći od najmanjih elemenata redaka je 2, to je niža cijena igre, prvi red odgovara tome, dakle, maksimalna strategija prvog igrača je prva. Najmanji od najvećih elemenata stupaca je 5, to je gornja cijena igre, drugi stupac odgovara njemu, dakle, minimax strategija drugog igrača je druga.

Sada kada smo naučili kako pronaći donju i gornju cijenu igre, maximin i minimax strategije, vrijeme je da naučimo kako formalno označiti ove koncepte.

Dakle, zajamčena isplata prvog igrača je:

Prvi igrač mora odabrati čistu strategiju koja bi mu omogućila maksimum od minimalnih dobitaka. Ovaj dobitak (maksimin) označava se na sljedeći način:

.

Prvi igrač koristi svoju čistu strategiju tako da gubitak drugog igrača bude maksimalan. Ovaj gubitak se definira na sljedeći način:

Drugi igrač mora odabrati svoju čistu strategiju tako da njegov gubitak bude minimalan. Ovaj gubitak (minimax) označava se na sljedeći način:

.

Još jedan primjer iz iste serije.

Primjer 2 Zadana je matrična igra s matricom isplate

.

Odredite maximin strategiju prvog igrača, minimax strategiju drugog igrača, donju i gornju cijenu igre.

Riješenje. Desno od matrice isplate ispisujemo najmanje elemente u njezine retke i označavamo njihov maksimum, a s dna matrice - najveće elemente u stupcima i odabiremo najmanji od njih:

Najveći od najmanjih elemenata redova je 3, to je niža cijena igre, drugi red odgovara tome, dakle, maksimalna strategija prvog igrača je drugi. Najmanji od najvećih elemenata stupaca je 5, ovo je gornja cijena igre, prvi stupac odgovara njemu, dakle, minimax strategija drugog igrača je prva.

Sedlasta točka u matrix igrama

Ako su gornja i donja cijena igre iste, tada se smatra da matrična igra ima sedlu točku. Vrijedi i obrnuto: ako matrična igra ima sjedište, tada su gornja i donja cijena matrične igre iste. Odgovarajući element je i najmanji u retku i najveći u stupcu i jednak je cijeni igre.

Dakle, ako je , tada je optimalna čista strategija prvog igrača, a optimalna je čista strategija drugog igrača. To jest, iste donje i gornje cijene igre postižu se na istom paru strategija.

U ovom slučaju matrix igra ima rješenje u čistim strategijama .

Primjer 3 Zadana je matrična igra s matricom isplate

.

Riješenje. Desno od matrice isplate ispisujemo najmanje elemente u njezine retke i označavamo njihov maksimum, a s dna matrice - najveće elemente u stupcima i odabiremo najmanji od njih:

Donja cijena igre jednaka je gornjoj cijeni igre. Dakle, cijena igre je 5. To je . Cijena igre jednaka je vrijednosti sedla. Maximin strategija prvog igrača je druga čista strategija, a minimax strategija drugog igrača je treća čista strategija. Ova matrična igra ima rješenje u čistim strategijama.

Sami riješite problem igre matrica, a zatim pogledajte rješenje

Primjer 4 Zadana je matrična igra s matricom isplate

.

Pronađite donju i gornju cijenu igre. Ima li ova matrica igra sedlu?

Matrix igre s optimalnom mješovitom strategijom

U većini slučajeva matrix igra nema sedlu točku, tako da odgovarajuća matrix igra nema čista strateška rješenja.

Ali ima rješenje u optimalnim mješovitim strategijama. Da bi ih pronašli, mora se pretpostaviti da se igra ponavlja dovoljno puta da se na temelju iskustva može pogoditi koja je strategija poželjnija. Stoga je odluka povezana s pojmom vjerojatnosti i prosjeka (očekivanja). U konačnom rješenju postoji i analog sedlaste točke (odnosno, jednakost donje i gornje cijene igre), i analog njima odgovarajućih strategija.

Dakle, kako bi prvi igrač ostvario najveći prosječni dobitak, a drugi igrač imao minimalni prosječni gubitak, treba s određenom vjerojatnošću koristiti čiste strategije.

Ako prvi igrač koristi čiste strategije s vjerojatnostima , zatim vektor naziva se mješovita strategija prvog igrača. Drugim riječima, radi se o "mješavini" čistih strategija. Zbroj ovih vjerojatnosti jednak je jedan:

.

Ako drugi igrač koristi čiste strategije s vjerojatnostima , zatim vektor naziva se mješovita strategija drugog igrača. Zbroj ovih vjerojatnosti jednak je jedan:

.

Ako prvi igrač koristi mješovitu strategiju str, a drugi igrač - mješovita strategija q, onda ima smisla očekivana vrijednost prvi igrač pobjeđuje (drugi igrač gubi). Da biste ga pronašli, trebate pomnožiti vektor mješovite strategije prvog igrača (koji će biti matrica s jednim redom), matricu isplate i vektor mješovite strategije drugog igrača (koji će biti matrica s jednim stupcem):

.

Primjer 5 Zadana je matrična igra s matricom isplate

.

Odredite matematičko očekivanje dobitka prvog igrača (gubitak drugog igrača), ako je mješovita strategija prvog igrača , a mješovita strategija drugog igrača .

Riješenje. Prema formuli za matematičko očekivanje dobitka prvog igrača (gubitak drugog igrača), ono je jednako umnošku vektora mješovite strategije prvog igrača, matrice isplate i vektora mješovite strategije drugog igrača:

Prvi igrač naziva se takva mješovita strategija koja bi mu osigurala maksimalni prosječni dobitak ako se igra ponovi dovoljan broj puta.

Optimalna mješovita strategija Drugi igrač naziva se takva mješovita strategija koja bi mu osigurala najmanji prosječni gubitak ako se igra ponavlja dovoljan broj puta.

Po analogiji s oznakom maximin i minimax u slučajevima čistih strategija, optimalne mješovite strategije označavaju se na sljedeći način (i povezane su s matematičkim očekivanjem, to jest prosjekom, dobitka prvog igrača i gubitka drugog igrača):

,

.

U ovom slučaju, za funkciju E postoji sedlasta točka , što znači jednakost.

Kako bi se pronašle optimalne mješovite strategije i sedla, tj. riješiti matričnu igru ​​u mješovitim strategijama , trebate matričnu igru ​​svesti na problem linearnog programiranja, odnosno na problem optimizacije i riješiti odgovarajući problem linearnog programiranja.

Svođenje matrične igre na problem linearnog programiranja

Kako biste riješili matričnu igru ​​u mješovitim strategijama, trebate sastaviti ravnu liniju problem linearnog programiranja i njegova dvostruka zadaća. U dualnom problemu transponirana je proširena matrica koja pohranjuje koeficijente varijabli u sustavu ograničenja, konstantne članove i koeficijente varijabli u funkciji cilja. U ovom slučaju, minimum funkcije cilja izvornog problema pridružen je maksimumu u dualnom problemu.

Ciljna funkcija u problemu izravnog linearnog programiranja:

.

Sustav ograničenja u izravnom problemu linearnog programiranja:

Funkcija cilja u dualnom problemu:

.

Sustav ograničenja u dualnom problemu:

Označite optimalni plan problema izravnog linearnog programiranja

,

a optimalni plan dualnog problema označen je sa

Linearni oblici za odgovarajuće optimalne dizajne bit će označeni s i ,

a trebate ih pronaći kao zbroj odgovarajućih koordinata optimalnih planova.

U skladu s definicijama iz prethodnog odjeljka i koordinatama optimalnih planova vrijede sljedeće mješovite strategije prvog i drugog igrača:

.

Matematičari su to dokazali cijena igre izražava se kroz linearne oblike optimalnih planova kako slijedi:

,

odnosno recipročna je veličina suma koordinata optimalnih planova.

Mi, praktičari, ovu formulu možemo koristiti samo za rješavanje matričnih igara u mješovitim strategijama. Kao formule za pronalaženje optimalnih mješovitih strategija odnosno prvi i drugi igrač:

u kojoj su drugi faktori vektori. Optimalne mješovite strategije također su vektori, kao što smo već definirali u prethodnom paragrafu. Dakle, množenjem broja (cijene igre) s vektorom (s koordinatama optimalnih planova) također dobivamo vektor.

Primjer 6 Zadana je matrična igra s matricom isplate

.

Pronađite cijenu igre V te optimalne mješovite strategije i .

Riješenje. Sastavljamo problem linearnog programiranja koji odgovara ovoj matričnoj igri:

Dobivamo rješenje izravnog problema:

.

Linearni oblik optimalnih planova nalazimo kao zbroj pronađenih koordinata.

Pošaljite svoj dobar rad u bazu znanja jednostavno je. Koristite obrazac u nastavku

Studenti, diplomanti, mladi znanstvenici koji koriste bazu znanja u svom studiju i radu bit će vam vrlo zahvalni.

Uvod

1. Teorijski dio

1.3 Redoslijed igre 2v2

1.4 Algebarska metoda

1.5 Grafička metoda

1.6 Igre 2xn ili mx2

1.7 Rješavanje igara matričnom metodom

2. Praktični dio

2.2 2xn i mx2 igre

2.3 Metoda matrice

2.4 Brownova metoda

Analiza rezultata

Uvod

Antagonistička igra je igra s nultim zbrojem. Antagonistička igra je igra bez suradnje u kojoj sudjeluju dva igrača čiji su dobici suprotni.

Formalno, antagonistička igra može se prikazati trojkom , gdje su X i Y skupovi strategija prvog i drugog igrača, F je funkcija isplate prvog igrača, koja pridružuje svaki par strategija (x, y), gdje je realni broj koji odgovara korisnosti prvog igrača u realizaciji ove situacije.

Budući da su interesi igrača suprotni, funkcija F istovremeno predstavlja i gubitak drugog igrača.

Povijesno gledano, antagonističke igre su prva klasa matematičkih modela teorije igara, koji su korišteni za opisivanje Kockanje. Vjeruje se da je zahvaljujući ovom predmetu istraživanja teorija igara dobila svoje ime. Trenutno se antagonističke igre smatraju dijelom šire klase nekooperativnih igara.

1. Teorijski dio

1.1 Osnovne definicije i odredbe igre

Igru karakterizira sustav pravila koji određuju broj sudionika u igri, njihov moguće akcije i raspodjelu dobitaka ovisno o njihovom ponašanju i ishodima. Igračem se smatra jedan sudionik ili skupina sudionika u igri koji za sebe imaju neke zajedničke interese koji se ne poklapaju s interesima drugih skupina. Stoga se svaki sudionik ne smatra igračem.

Pravila ili uvjeti igre određuju moguća ponašanja, izbore i poteze igrača u bilo kojoj fazi razvoja igre. Napraviti izbor za igrača znači zaustaviti se na jednoj od njegovih mogućnosti ponašanja. Igrač tada odabire potezima. Povući potez znači u određenoj fazi igre odjednom napraviti cijeli ili dio izbora, ovisno o mogućnostima koje pravila igre daju. Svaki igrač u određenoj fazi igre povlači potez prema svom izboru. Drugi igrač, znajući ili ne znajući za izbor prvog igrača, također povlači potez. Svaki od igrača nastoji uzeti u obzir podatke o dosadašnjem razvoju igre, ako je takva mogućnost dopuštena pravilima igre.

Skup pravila koja nedvosmisleno govore igraču kakav odabir treba napraviti pri svakom potezu, ovisno o situaciji koja je nastala kao rezultat igre, naziva se igračeva strategija. Strategija u teoriji igara znači određeni cjeloviti plan akcije za igrača, koji pokazuje kako on treba djelovati u svim mogućim slučajevima razvoja igre. Strategija znači ukupnost svih indikacija za bilo koje stanje informacija dostupnih igraču u bilo kojoj fazi razvoja igre. To već pokazuje da strategije mogu biti dobre i loše, uspješne i neuspješne itd.

Igra s nultim zbrojem će biti kada je zbroj dobitaka svih igrača u svakoj od njegovih igara jednak nuli, tj. u igri s nultim zbrojem ukupni kapital svih igrača se ne mijenja, već se redistribuira među igračima ovisno o rezultirajućim ishodima. Stoga se mnoge ekonomske i vojne situacije mogu promatrati kao igre s nultom sumom.

Konkretno, igra dva igrača s nultim zbrojem naziva se antagonističkom, budući da su ciljevi igrača u njoj izravno suprotni: dobitak jednog igrača događa se samo na račun gubitka drugog.

1.1.1 Definicija, primjeri i rješenja matričnih igara u čistim strategijama

Matrična igra za dva igrača s nultim zbrojem može se promatrati kao sljedeća apstraktna igra za dva igrača.

Prvi igrač ima m strategija i =1, 2,…, m, drugi ima n strategija j = 1, 2,…, n. Svakom paru strategija (i, j) dodijeljen je broj a ij , koji izražava isplata prvog igrača pripada drugom igraču ako prvi igrač iskoristi svoju i-ta strategija, a drugi - svoju j-tu strategiju.

Svaki od igrača čini jedan potez: prvi igrač bira svoju i-tu strategiju (i = 1, 2, ..., m), drugi --tvoj j-ti strategija (j = 1, 2,…, n), nakon čega prvi igrač dobiva isplatu a ij na račun drugog igrača (ako je a ij< 0, то это значит, что первый игрок платит второму сумму a ij). На этом игра заканчивается.

Svaka strategija igrača i = 1, 2,…, t; j = 1, 2,…, n se često naziva čistom strategijom.

Matrična igra dva igrača s nultim zbrojem jednostavno će se nazivati ​​matrična igra. Očigledno, matrična igra spada u antagonističke igre. Iz njezine definicije slijedi da je za definiranje matrične igre dovoljno zadati matricu A = (a ij) reda m isplata prvog igrača.

Uzimajući u obzir matricu isplate

tada se izvođenje svake igre matrične igre s matricom A svodi na izbor prvog igrača i-ti redak, a drugi igrač u j-tom stupcu i prvi igrač (na račun drugog) dobiva isplatu koja se nalazi u matrici A na sjecištu i-tog retka i j-tog stupca.

Da bi se stvarna konfliktna situacija formalizirala u obliku matrične igre, potrebno je identificirati i prenumerirati čiste strategije svakog igrača i sastaviti matricu isplate.

Sljedeći korak je odrediti optimalne strategije i dobitke igrača.

Glavna stvar u proučavanju igara je koncept optimalnih strategija za igrače. Ovaj koncept intuitivno ima sljedeće značenje: strategija igrača je optimalna ako mu primjena te strategije osigurava najveći zajamčeni dobitak za sve moguće strategije drugog igrača. Na temelju ovih pozicija, prvi igrač ispituje matricu A svojih dobitaka prema formuli (1.1) na sljedeći način: za svaku vrijednost i (i = 1, 2, ..., m), minimalna vrijednost dobitka se određuje ovisno o o strategijama koje koristi drugi igrač

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

tj. određena je minimalna isplata za prvog igrača, pod uvjetom da on primijeni svoju i -tu čistu strategiju, tada se iz tih minimalnih isplata pronađe takva strategija i=i 0 za koju će ta minimalna isplata biti maksimalna, tj.

Definicija. Broj b određen formulom (1.3) naziva se niži neto trošak igre i pokazuje koliki minimalni dobitak si prvi igrač može jamčiti primjenom svojih čistih strategija za sve moguće akcije drugog igrača.

Drugi igrač bi svojim optimalnim ponašanjem trebao težiti, ako je moguće, minimizirati dobitak prvog igrača nauštrb njegovih strategija. Stoga, za drugog igrača, nalazimo

tj. određuje se maksimalni dobitak prvog igrača, pod uvjetom da drugi igrač primijeni svoje j-th čist strategiju, tada drugi igrač pronalazi vlastitu j = j 1 strategiju za koju prvi igrač dobiva minimalnu isplatu, tj. pronalazi

Definicija. Broj β određen formulom (1.5) naziva se neto gornji trošak igre i pokazuje koliki maksimalni dobitak si prvi igrač može jamčiti zahvaljujući svojim strategijama. Drugim riječima, primjenom svojih čistih strategija, prvi igrač može osigurati isplatu od najmanje b, a drugi igrač, primjenom svojih čistih strategija, može spriječiti prvog igrača da dobije više od c.

Definicija. Ako se u igri s matricom A donja i gornja neto cijena igre poklapaju, tj. b = c, tada se kaže da ova igra ima sjedište u čistim strategijama i neto cijenu igre:

n = b = c (1.6)

Sjedište je par čistih strategija () prvog i drugog igrača, prema kojima se postiže jednakost

Koncept sedla ima sljedeće značenje: ako se jedan od igrača pridržava strategije koja odgovara sedlu, onda drugi igrač ne može učiniti bolje nego da se pridržava strategije koja odgovara sedlu. Imajući na umu da najbolje ponašanje igrača ne bi trebalo dovesti do smanjenja njegove dobiti, a najlošije ponašanje može dovesti do smanjenja njegove dobiti, ovi se uvjeti mogu matematički napisati u obliku sljedećih odnosa:

gdje su i, j bilo koje čiste strategije prvog i drugog igrača; (i 0 , j 0) -- strategije koje tvore sedlo. U nastavku ćemo pokazati da je definicija sedlaste točke ekvivalentna uvjetima (1.8).

Dakle, na temelju (1.8), sedlasti element je minimum u i 0 -tom retku i maksimum u j 0 -tom stupcu u matrici A. Pronalaženje sedlaste točke matrice A je jednostavno: u matrici A, redom u svakom retku, pronađite minimalni element i provjerite je li taj element najveći u svom stupcu. Ako je takav, onda je to sedlasti element, a njemu odgovarajući par strategija čini sedlastu točku. Par čistih strategija (i 0 , j 0) prvog i drugog igrača, koji čine sedlo i sedlo, naziva se rješenjem igre.

Čiste strategije i 0 i j 0 koje tvore sedlo nazivaju se optimalne čiste strategije prvog i drugog igrača.

Teorem 1. Neka je f (x, y) realna funkcija dviju varijabli x A i y B i postoji

tada je b = c.

Dokaz. Iz definicije minimuma i maksimuma proizlazi da

Kako je x proizvoljan na lijevoj strani (1.11), tada

Na desnoj strani nejednakosti (1.12) y je proizvoljan, pa je

Q.E.D.

Konkretno, matrica () je poseban slučaj funkcije f (x, y), tj. ako stavimo x = i, y = j, = f (x, y), tada iz teorema 1 dobivamo da je niži neto cijena ne premašuje gornju neto vrijednost igre u matričnoj igri.

Definicija. Neka je f (x, y) realna funkcija dviju varijabli x A i y B. Točka (x 0, y 0) se naziva sedlom za funkciju f (x, y) ako vrijede sljedeće nejednakosti:

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

za bilo koje x A i y B.

1.2 Optimalne mješovite strategije i njihova svojstva

Proučavanje matrične igre počinje pronalaženjem njezine sedlaste točke u čistim strategijama. Ako matrična igra ima sjedište u čistim strategijama, pronalaženje ove točke završava proučavanje igre. Ako u matričnoj igri ne postoji sedla točka u čistim strategijama, tada možemo pronaći donju i gornju čistu cijenu ove igre, koje pokazuju da se prvi igrač ne treba nadati isplati većoj od gornje cijene igre, a možete biti sigurni da ćete dobiti ništa manje od niže cijene igre. Takve preporuke u vezi s ponašanjem igrača u matričnoj igri bez sedlaste točke u čistim strategijama ne mogu zadovoljiti istraživače i praktičare. Poboljšanje rješenja matričnih igara treba tražiti u korištenju tajnosti primjene čistih strategija i mogućnosti višekratnog ponavljanja igara u obliku partija. Tako se, primjerice, igra niz partija šaha, dame, nogometa i svaki put igrači primjenjuju svoje strategije na način da protivnici nisu svjesni njihovog sadržaja, a usput postižu određene dobitke u prosjeku za igrajući cijeli niz igara. Te su isplate u prosjeku veće od niže cijene igre i manje od gornje cijene igre. Što je ova prosječna vrijednost veća, to bolja strategija primjenjuje igrač. Stoga se javila ideja da se čiste strategije primjenjuju nasumično, s određenom vjerojatnošću. Time se u potpunosti osigurava tajnost njihove uporabe. Svaki igrač može promijeniti vjerojatnosti primjene svojih čistih strategija na takav način da maksimizira svoju prosječnu isplatu i usput dobije optimalne strategije. Ova ideja dovela je do koncepta mješovite strategije.

Definicija. Mješovita strategija igrača je kompletan skup vjerojatnosti primjene njegovih čistih strategija.

Dakle, ako prvi igrač ima m čistih strategija 1, 2, … i, … m, tada je njegova mješovita strategija x skup brojeva x = (x 1 , x 2 , ..., x i ,…, x t ) koji zadovoljavaju odnosima

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

Slično, za drugog igrača, koji ima n čistih strategija, mješovita strategija y je skup brojeva y = (y 1 ,…, y j , … y n) koji zadovoljavaju relacije

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

Budući da svaki put kada igrač koristi jednu čistu strategiju isključuje korištenje druge, čiste strategije su nekompatibilni događaji. Osim toga, oni su jedini mogući događaji.

Jasno je da je čista strategija poseban slučaj mješovite strategije. Doista, ako u mješovitoj strategiji bilo i-ta mreža strategija se primjenjuje s vjerojatnošću jedan, tada se sve ostale čiste strategije ne primjenjuju. A ova i-ta čista strategija poseban je slučaj mješovite strategije. Kako bi održao tajnost, svaki igrač primjenjuje vlastite strategije bez obzira na izbor drugog igrača.

Definicija. Prosječna isplata prvog igrača u matričnoj igri s matricom A izražava se kao matematičko očekivanje njegovih isplata.

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

Očito je da je prosječna isplata prvog igrača funkcija dva skupa varijabli x i y. Prvi igrač ima za cilj maksimizirati svoju prosječnu isplatu E (A, x, y) promjenom svojih mješovitih strategija x, a drugi igrač nastoji učiniti E (A, x, y) minimalnim kroz svoje mješovite strategije, tj. za rješavanje igre potrebno je pronaći takve x, y za koje se postiže gornja cijena igre.

1.3 Naručite igru ​​22

Matrična igra reda 22 dana je sljedećom matricom isplate za prvog igrača:

Rješenje ove igre trebalo bi započeti pronalaženjem sedla u čistim strategijama. U tu svrhu pronađite minimalni element u prvom retku i provjerite je li maksimalni u njegovom stupcu. Ako takav element nije pronađen, tada se drugi red provjerava na isti način. Ako se takav element nalazi u drugom redu, onda je to element sedla.

Pronalaženjem sedlastog elementa, ako postoji, završava proces pronalaženja njegovog rješenja, jer se u ovom slučaju nalazi cijena igre - sedlasti element i sedlasta točka, odnosno par čistih strategija za prvu i drugu igrača, tvoreći optimalne čiste strategije. Ako u čistim strategijama ne postoji sedlo, onda je u mješovitim strategijama potrebno pronaći sedlo, koje prema glavnom teoremu matričnih igara nužno postoji.

Označimo s x=(x 1 ,x 2), y=(y 1 ,y 2) mješovite strategije prvog i drugog igrača. Podsjetimo se da x 1 znači vjerojatnost da će prvi igrač koristiti svoju prvu strategiju, a x 2 \u003d 1 - x 1 je vjerojatnost da će koristiti svoju drugu strategiju. Slično za drugog igrača: 1 - vjerojatnost korištenja prve strategije, y 2 = 1 - 1 - vjerojatnost korištenja druge strategije.

Prema korolaru teorema, za optimalnost mješovitih strategija x i y potrebno je i dovoljno da za nenegativne x 1 , x 2 , y 1 , y 2 vrijede sljedeće relacije:

Sada pokazujemo da ako matrična igra nema sedlu u čistim strategijama, tada se ove nejednakosti moraju pretvoriti u jednakosti:

Doista. Neka igra nema sedlu u čistim strategijama, tada optimalne vrijednosti mješovitih strategija zadovoljavaju nejednakosti

0<<1, 0<< 1,

0< <1, 01. (1.25)

Pretpostavimo da su obje nejednakosti iz (1.22) stroge

tada je prema teoremu y 1 = y 2 = 0, što je u suprotnosti s uvjetima (1.25).

Slično se može dokazati da obje nejednakosti u (1.23) ne mogu biti stroge nejednakosti.

Pretpostavimo sada da jedna od nejednakosti (1.22) može biti stroga, npr. prva

To znači da prema teoremu y 1 = 0, y 2 =1. Stoga iz (1.23) dobivamo

Ako su obje nejednakosti (1.24) stroge, tada je po teoremu x1 = x2 = 0, što je u suprotnosti s (1.25). Ali ako je a 12 a 22 , tada je jedna od nejednakosti (1.27) stroga, a druga je jednakost. Štoviše, jednakost će vrijediti za veći element iz a 12 i a 22 , tj. jedna nejednakost iz (1.27) mora biti stroga. Na primjer 12< а 22 . Тогда справедливо а 12 < v, а это равносильно тому, что первое неравенство из (1.24) строгое. Тогда согласно теореме должно х 1 = 0, что противоречит условию (1.25). Если а 12 = а 22 , то оба неравенства (1.27) превращаются в равенства и тогда можно положить х 1 = 0, что противоречит (1.25). Итак, предположение о том, что первое неравенство из (1.22) может быть строгим, не справедливо. Аналогично можно показать, что второе неравенство из (1.22) также не может быть строгим.

Dakle, pokazuje se da ako matrična igra nema sedlišnu točku u čistim strategijama, tada se nejednakosti (1.22) pretvaraju u jednakosti za optimalne strategije prvog igrača. Slični argumenti o nejednakostima (1.23) dovest će do činjenice da u ovom slučaju nejednakosti (1.23) moraju biti jednakosti.

Dakle, ako matrična igra reda 22 nema sedlu, tada se optimalne mješovite strategije igrača i cijena igre mogu odrediti rješavanjem sustava jednadžbi (1.24). Također je utvrđeno da ako u matričnoj igri 2x2 jedan od igrača ima optimalnu čistu strategiju, tada i drugi igrač ima optimalnu čistu strategiju.

Stoga, ako matrična igra nema sedlo u čistim strategijama, onda mora imati rješenje u mješovitim strategijama, koje se određuju iz jednadžbi (1.24). Sustavno rješenje (1.25)

1.4 Algebarska metoda

Postoje dva slučaja rješavanja problema algebarskom metodom:

1. matrica ima sedlo;

2. matrica nema sedlu.

U prvom slučaju, rješenje je par strategija koje čine sedlo točke igre. Razmotrimo drugi slučaj. Rješenja ovdje treba tražiti u mješovitim strategijama:

Pronađite strategije i Kada prvi igrač koristi svoju optimalnu strategiju, drugi igrač može, na primjer, primijeniti dvije takve čiste strategije

U isto vrijeme, na temelju svojstva, ako jedan od igrača koristi optimalnu mješovitu strategiju, a drugi - bilo koju čistu, uključenu u njegovu optimalnu mješovitu strategiju s vjerojatnošću koja nije nula, tada matematičko očekivanje isplate uvijek ostaje nepromijenjena i jednaka cijeni igre, tj.

Isplata mora u svakom od ovih slučajeva biti jednaka vrijednosti igre V. U ovom slučaju vrijede sljedeće relacije:

Sustav jednadžbi sličan (2.5), (2.6) također se može sastaviti za optimalnu strategiju drugog igrača:

Uzimajući u obzir uvjet normalizacije:

Riješimo jednadžbu (1.37) - (1.41) zajedno s obzirom na nepoznanice, i to ne sve odjednom, nego po tri: zasebno (1.36), (1.38), (1.40) i (1.37), (1.39) , (1,41). Kao rezultat rješenja dobivamo:

1.5 Grafička metoda

Približno rješenje igre 22 može se vrlo lako dobiti grafičkom metodom. Njegova suština je sljedeća:

Slika 1.1 - nalaženje odsječka jedinične duljine

Odaberite dio jedinične duljine na apscisnoj osi. Lijevi kraj će prikazati prvu strategiju prvog igrača, a desni kraj drugog. Sve međutočke odgovaraju mješovitim strategijama prvog igrača, a duljina segmenta desno od točke jednaka je vjerojatnosti korištenja prve strategije, a duljina segmenta lijevo je vjerojatnost korištenja drugu strategiju prvog igrača.

Izvode se dvije ose I-I i II-II. Na I-I ćemo odgoditi isplatu kada prvi igrač koristi prvu strategiju, na II-II kada koristi drugu strategiju. Neka je, na primjer, drugi igrač primijenio svoju prvu strategiju, tada vrijednost treba iscrtati na I-I osi, a vrijednost na II-II osi

Za bilo koju mješovitu strategiju prvog igrača, njegov dobitak će biti određen veličinom segmenta. Linija I-I odgovara primjeni prve strategije od strane drugog igrača, nazvat ćemo je prva strategija drugog igrača. Druga strategija drugog igrača može se konstruirati na sličan način. Tada će, općenito, grafički prikaz matrice igre imati sljedeći oblik:

Slika 1.2 - pronalaženje cijene igre

Međutim, treba napomenuti da je ova konstrukcija izvedena za prvog igrača. Ovdje je duljina segmenta jednaka vrijednosti igre V.

Linija 1N2 naziva se niža linija isplate. Ovdje se jasno vidi da točka N odgovara maksimalnoj vrijednosti zajamčenog dobitka prvog igrača.

Općenito govoreći, strategija drugog igrača također se može odrediti iz ove brojke, na primjer na takve načine. Na I-I osi:

odnosno na osi II-II

Međutim, strategija drugog igrača također se može definirati na isti način kao što je to učinjeno za prvog igrača, tj. izgraditi takav grafikon.

Slika 1.3 - definicija strategije drugog igrača

Ovdje je linija 1N2 gornja granica gubitka. Točka N odgovara minimalnom mogućem gubitku drugog igrača i određuje strategiju.

Ovisno o specifičnim vrijednostima koeficijenata, matrice grafikona također mogu imati drugačiji oblik, na primjer, kako slijedi:

Slika 1.4 - određuje optimalnu strategiju prvog igrača

U takvoj situaciji optimalna strategija prvog igrača je čista:

1.6 Igre 2n ili m2

U igrama reda 2n prvi igrač ima 2 čiste strategije, a drugi igrač ima n čistih strategija, tj. Matrica isplate za prvog igrača je:

Ako takva igra ima sedlo, onda ju je lako pronaći i dobiti rješenje.

Pretpostavimo da igra ima sedlaste točke. Tada je potrebno pronaći takve mješovite strategije, odnosno prvog i drugog igrača i cijenu igre v, koje zadovoljavaju relacije:

Budući da igra nema sjedište, nejednakost (1.54) se zamjenjuje nejednakostima

Za rješavanje sustava (1.56), (1.55), (1.53) svrsishodno je koristiti se grafičkom metodom. U tu svrhu uvodimo oznaku za lijevu stranu nejednadžbe (1.53)

matrična igra matematički model

ili, postavljajući iz (1.55) i izvodeći jednostavne transformacije, dobivamo

gdje je prosječna isplata prvog igrača, pod uvjetom da koristi svoju mješovitu strategiju, a drugog - svoju j-tu čistu strategiju.

Prema izrazu, svaka vrijednost j=1, 2, …, n odgovara ravnoj liniji u pravokutnom koordinatnom sustavu.

Cilj drugog igrača je minimizirati dobitak prvog igrača odabirom njegovih strategija. Stoga izračunavamo

gdje je donja granica skupa ograničenja. Na slici 1.6 debelom linijom prikazan je graf funkcije.

Domaćin na http://www.allbest.ru/

Slika 1.6 - graf funkcije

Cilj prvog igrača je maksimizirati svoju isplatu putem izbora, tj. izračunati

Na slici 1.6 točka označava najveću vrijednost koja se dobiva na. Cijena igre, jer:

Tako je grafički određena optimalna mješovita strategija prvog igrača i par čistih strategija drugog igrača koji čine točku na presjeku.Slika 1.6 prikazuje 2. i 3. strategiju drugog igrača. Za takve strategije nejednakosti (1.53) se pretvaraju u jednakosti. Na slici 1.6 to su strategije j=2, j=3.

Sada možemo riješiti sustav jednadžbi

te precizno odrediti vrijednosti i (grafički se određuju približno). Zatim stavljamo sve vrijednosti na one j za koje ne čine točku, rješavajući sustav jednadžbi (1.56). Za primjer prikazan na slici 1.6, ovo je sljedeći sustav:

i ostatak Ovaj sustav se može riješiti nagibom Ako, za neki j=j 0, strategije drugog igrača tvore točku M 0 i tada je maksimalna vrijednost donje granice skupova ograničenja predstavljena segmentom paralelnim s os U ovom slučaju, prvi igrač ima beskonačno mnogo optimalnih vrijednosti i cijena igre Ovaj slučaj prikazan na slici 1.7, gdje i segment MN predstavljaju gornju granicu, optimalne vrijednosti su unutar granica. drugi igrač ima čistu optimalnu strategiju j=j 0 .

Matrične igre reda m2 također se rješavaju grafičkom metodom. Isplatna matrica prvog igrača u ovom slučaju ima oblik

Mješovite strategije prvog i drugog igrača definirane su na isti način kao u slučaju igara reda 2n. Neka se vrijednost od 0 do 1 iscrta duž vodoravne osi, a vrijednost prosječne isplate) prvog igrača na okomitoj osi pod uvjetima da prvi igrač primjenjuje svoju čistu i-tu strategiju (i=1, 2, ..., m), drugi - njegova mješovita strategija (y 1 , 1- y 1) =y. Na primjer, kada je m=4 grafički) može se prikazati kao što je prikazano na slici 1.7.

Slika 1.7 - grafikon funkcije)

Prvi igrač pokušava maksimizirati svoju prosječnu isplatu, pa pokušava pronaći

Funkcija je prikazana kao debela linija i predstavlja gornju granicu skupa ograničenja. Drugi igrač pokušava minimizirati odabirom svoje strategije, tj. vrijednost odgovara

Na slici je vrijednost označena točkom. Drugim riječima, definirane su takve dvije strategije prvog igrača i vjerojatnost za drugog igrača za koje se postiže jednakost

Iz slike vidimo da je cijena igre ordinata boda, vjerojatnost je apscisa boda. Za ostale čiste strategije prvog igrača u optimalnoj mješovitoj strategiji mora ().

Tako rješavanjem sustava (1.69) dobivamo optimalnu strategiju drugog igrača i vrijednost igre. Pronalazimo optimalnu mješovitu strategiju za prvog igrača rješavanjem sljedećeg sustava jednadžbi:

1.7 Matrična metoda za rješavanje igara

Oznake:

Bilo koja kvadratna podmatrica matrice reda

Matrica (1);

Matrica transponirana u;

Matrica pričvršćena na B;

- (1) matrica dobivena iz X brisanjem elemenata koji odgovaraju recima koji su izbrisani iz primljenih;

- (1) matrica dobivena brisanjem elemenata koji odgovaraju recima koji su izbrisani kada su primljeni.

Algoritam:

1. Odaberite kvadratnu podmatricu matrice reda () i izračunajte

2. Ako ima ili, tada odbacite pronađenu matricu i pokušajte s drugom matricom.

3. Ako (), (), izračunavamo i gradimo X i iz i, dodajući nule na odgovarajuća mjesta.

Provjera jesu li nejednakosti zadovoljene

za svaki (1,75)

i nejednakosti

za svaki (1,76)

Ako jedan od omjera nije zadovoljen, tada pokušavamo s drugim. Ako su sve relacije valjane, onda je X i željena rješenja.

1.8 Metoda sukcesivne aproksimacije cijene igre

U proučavanju situacija u igri često se može dogoditi da nije potrebno dobiti točno rješenje igre ili je iz nekog razloga nemoguće ili vrlo teško pronaći točnu vrijednost cijene igre i optimalne mješovite strategije. Zatim možete upotrijebiti približne metode za rješavanje matrične igre.

Opišimo jednu od tih metoda - metodu uzastopne aproksimacije cijene igre. Broj isplata izračunatih ovom metodom povećava se približno proporcionalno broju redaka i stupaca matrice isplata.

Suština metode je sljedeća: igra se mentalno igra mnogo puta, tj. sekvencijalno, u svakoj partiji igre, igrač odabire strategiju koja mu daje najveći ukupni (ukupni) dobitak.

Nakon takve implementacije nekih igara izračunava prosječnu vrijednost dobitka prvog igrača i gubitka drugog igrača, a njihovu aritmetičku sredinu uzima kao približnu vrijednost cijene igre. Metoda omogućuje pronalaženje približne vrijednosti optimalnih mješovitih strategija oba igrača: potrebno je izračunati učestalost primjene svake čiste strategije i uzeti je kao približnu vrijednost u optimalnoj mješovitoj strategiji odgovarajućeg igrača.

Može se dokazati da će se s neograničenim povećanjem broja programskih igara prosječni dobitak prvog igrača i prosječni gubitak drugog igrača neograničeno približavati cijeni igre, a približne vrijednosti mješovitih strategija u slučaj kada je rješenje igre jedinstveno težit će optimalnim mješovitim strategijama svakog igrača. Općenito govoreći, približavanje vrijednosti iznad navedenih vrijednosti stvarnim vrijednostima je sporo. Međutim, ovaj se proces može lako mehanizirati i tako pomoći da se dobije rješenje igre sa potrebnim stupnjem točnosti čak i s matricama isplata relativno velikog reda.

2. Praktični dio

Par odlučuje gdje će otići u šetnju i provesti vrijeme za dobrobit dvoje.

Djevojka odlučuje prošetati parkom kako bi udahnula svježi zrak, a navečer otići pogledati film u najbliže kino.

Tip nudi odlazak u tehnopark nakon gledanja utakmice nogometaša lokalnog kluba na središnjem stadionu.

U skladu s tim, potrebno je pronaći koliko dugo će cilj jednog od igrača biti postignut. Matrica isplate će izgledati ovako:

Tablica 1. Matrica isplata

Od 1 2 , očito nema sedla u ovoj igri u čistim strategijama. Stoga koristimo sljedeće formule i dobivamo:

Domaćin na http://www.allbest.ru/

2.2 Igranje 2xn i mx2

Problem 1(2xn)

Za suhu i vlažnu klimu uzgajaju se dvije kulture.

A prirodno stanje može se smatrati: suho, vlažno, umjereno.

Domaćin na http://www.allbest.ru/

Maksimalna vrijednost M() se postiže u točki M formiranoj sjecištem linija koje odgovaraju j=1, j"=2. Stoga pretpostavljamo: ,

Problem 2 (mx2)

Momak i djevojka razmatraju mogućnosti gdje otići za vikend.

Izbor mjesta za odmor može se predstaviti kao: park, kino, restoran.

Domaćin na http://www.allbest.ru/

Maksimalna vrijednost M() se postiže u točki E formiranoj sjecištem linija koje odgovaraju j=1, j"=2. Stoga pretpostavljamo: ,

Da biste odredili vrijednost, v, trebate riješiti sljedeće jednadžbe:

2.5 Metoda matrice

Dva konkurentska restorana (ugostiteljska objekta) pružaju sljedeće skupove usluga. Prvi restoran se nalazi u centru, a drugi na periferiji grada.

Centralni restoran uključuje sljedeće usluge:

1) skuplja i bolja usluga kupcima;

2) jela su usmjerena na francusku kuhinju;

Drugi restoran nudi:

1) nije skupa i kvalitetna usluga;

2) jelovnik kombinira razne poznate kuhinje svijeta;

3) također redovite akcije i popusti;

4) vrši dostavu i prima narudžbe za dostavu na kućnu adresu.

U skladu sa zadatkom, dobit za jedan dan između dva restorana će se rasporediti na sljedeći način:

Tablica 2. Matrica isplata

Rješavanje igre oblika na matrični način:

Postoji šest podmatrica i:

Razmotrite matricu:

x 1 =? 0,x2=? 0

Budući da je x 2 =< 0, то мы отбрасываем.

Razmotrimo sada matricu:

x 1 =? 0,x2=? 0

Cijena igre.

Ovaj omjer je u suprotnosti sa zahtjevom, stoga nije prikladan.

Razmotrimo sada matricu:

x 1 = , x 2 = ? 0,

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

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

Razmotrimo sada matricu:

x 1 \u003d, x 2 \u003d 0, budući da je x 2 \u003d 0, tada odbacujemo i.

Razmotrimo sada matricu:

x 1 = , x 2 = ? 0. Budući da je x 1 \u003d 0, tada odbacujemo i.

Razmotrimo sada matricu:

x 1 = , x 2 =, y 1 = , y 2 =, pa nastavljamo dalje:

x 1 = , x 2 =, y 1 = , y 2 = ili

Cijena igre.

Sada se provjeravaju glavni odnosi:

Domaćin na http://www.allbest.ru/

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

Brown metoda

Na zahtjev radnika pojedinog poduzeća, sindikat pregovara s upravom poduzeća o organiziranju toplog obroka na teret poduzeća. Sindikat koji zastupa interese radnika brine da obrok bude što kvalitetniji, a time i skuplji. Uprava tvrtke ima suprotstavljene interese. Na kraju su se strane složile oko sljedećeg. Sindikat (igrač 1) odabire jednu od tri tvrtke (A 1 , A 2 , A 3) za opskrbu toplim obrokom, a uprava poduzeća (igrač 2) odabire set posuđa od tri moguće opcije (B 1 , B 2 , B 3) . Nakon potpisivanja ugovora, Sindikat formira sljedeću matricu plaćanja čiji elementi predstavljaju cijenu kompleta posuđa:

Neka je igra dana sljedećom matricom isplate:

Pretpostavimo da je drugi igrač odabrao svoju drugu strategiju, tada će prvi dobiti:

2 ako koristi svoju prvu strategiju,

3 ako koristi svoju 3. strategiju.

Dobivene vrijednosti su sažete u tablici 1.

Tablica 3. Strategija drugog igrača

Tablica 3 pokazuje da će s 2. strategijom drugog igrača prvi igrač dobiti najveću isplatu 3 koristeći svoju 2. ili 3. strategiju. Budući da prvi igrač želi dobiti najveću dobit, on na drugu strategiju drugog igrača odgovara svojom drugom strategijom. S 2. strategijom prvog igrača, drugi će izgubiti:

1 ako primijeni svoju 1. strategiju,

3 ako koristi svoju drugu strategiju,

4 ako koristi svoju 3. strategiju.

Tablica 4. Strategija prvog igrača

Tablica 2 pokazuje da će uz 2. strategiju prvog igrača, drugi igrač imati najmanji gubitak 1 ako primijeni svoju 1. strategiju. Budući da drugi igrač želi manje izgubiti, tada će kao odgovor na 2. strategiju prvog igrača primijeniti svoju 1. strategiju. Dobiveni rezultati sažeti su u tablici 5.

Tablica 5. Strategije prvog, odnosno drugog igrača

U tablici. 5 u stupcu strategije drugog igrača u drugom redu je broj 1, što označava da je u drugoj igri korisno da drugi igrač koristi svoju 1. strategiju; u stupcu i je najveća prosječna isplata 3 prvog igrača koju je primio u prvoj igri; stupac w sadrži najmanji prosječni gubitak 1 koji je ostvario drugi igrač u prvoj igri; stupac v sadrži aritmetičku sredinu v = (u + w) -- odnosno približnu vrijednost cijene igre, dobivenu kao rezultat igranja jedne partije igre. Ako drugi igrač koristi svoju 1. strategiju, tada će prvi igrač dobiti 3, 1, 2, redom, sa svojom 1., 2., 3. strategijom, a ukupni dobitak prvog igrača za obje igre bit će:

2 + 3=5 sa svojom prvom strategijom,

3 + 1=4 sa svojom drugom strategijom,

3 + 2=5 sa svojom trećom strategijom.

Ovi ukupni dobici bilježe se u drugom retku tablice. 3 i u stupcima koji odgovaraju strategijama prvog igrača: 1, 2, 3.

Od svih ukupnih dobitaka, najveći je 5. Dobiva se s 1. i 3. strategijom prvog igrača, zatim on može izabrati bilo koju od njih; recimo, u takvim slučajevima kada postoje dva (ili više) identična ukupna dobitka, odabire se strategija s najmanjim brojem (u našem slučaju trebamo uzeti 1. strategiju).

S 1. strategijom prvog igrača, drugi igrač će izgubiti 3, 2, 3, redom, u odnosu na svoju 1., 2., 3. strategiju, a ukupni gubitak drugog igrača za obje igre bit će:

1 + 3=4 sa svojom prvom strategijom,

3 + 2=5 sa svojom drugom strategijom,

4 + 3=7 sa svojom trećom strategijom.

Ovi ukupni gubici bilježe se u drugom retku tablice. 5 i u stupcima koji odgovaraju 1., 2., 3. strategiji drugog igrača.

Od svih ukupnih gubitaka drugog igrača, najmanji je 4. Dobiva se njegovom 1. strategijom, stoga u trećoj igri drugi igrač mora primijeniti svoju 1. strategiju. U stupac i stavite najveći ukupni dobitak prvog igrača u dvije igre, podijeljen s brojem igara, tj.; stupac w sadrži najmanji ukupni gubitak drugog igrača u dvije igre, podijeljen s brojem partija, tj.; aritmetička sredina ovih vrijednosti stavlja se u stupac v, tj. = Ovaj broj se uzima kao približna vrijednost cijene igre s dvije "odigrane" igre.

Tako se dobiva sljedeća tablica 4, za dva seta igre.

Tablica 6. Ukupni dobici i gubici igrača u dvije odigrane utakmice

U trećem redu tablice 6, u stupcu strategija drugog igrača, nalazi se broj 1, što označava da u trećoj igri drugi igrač mora primijeniti svoju 1. strategiju. U ovom slučaju, prvi igrač osvaja 3, 1, 2, koristeći svoju 1., 2., 3. strategiju, redom, a njegov ukupni dobitak za tri igre bit će:

3 + 5 = 8 u njegovoj prvoj strategiji,

1 +4 = 5 sa svojom drugom strategijom,

2 + 5 = 7 za njegovu treću strategiju.

Ove ukupne isplate prvog igrača bilježe se u trećem retku tablice 6 i stupcima koji odgovaraju njegovim strategijama 1, 2, 3. Budući da je najveća ukupna isplata 8 prvog igrača dobivena s 1. strategijom, on odabire 1. u skladu s tim. .

S 1. strategijom prvog igrača, drugi igrač će izgubiti 3, 1, 2, redom, na 1., 2., 3. strategiju, a ukupni gubitak drugog igrača za obje igre bit će:

3 + 4=7 sa svojom prvom strategijom,

2 + 5=7 sa svojom drugom strategijom,

3 + 7=10 sa svojom trećom strategijom.

Ovi ukupni gubici bilježe se u trećem retku tablice. 6 i u stupcima koji odgovaraju 1., 2., 3. strategiji drugog igrača. Od svih njegovih ukupnih gubitaka, 7 je najmanji i dobiva se njegovom 1. i 2. strategijom, tada drugi igrač mora primijeniti svoju 1. strategiju.

U tablici. 6 u trećem redu u stupcu i najveći ukupni dobitak prvog igrača u tri igre, podijeljen s brojem igre, tj.; stupac w sadrži najmanji ukupni gubitak drugog igrača u tri igre, podijeljen s brojem partija, tj. ; u stupac v stavite njihovu aritmetičku sredinu

Tako dobivamo tablicu. 7 za tri stranke.

Tablica 7. Ukupni dobici i gubici igrača u tri odigrane utakmice

Tablica 8. Finalni stol s dvadeset odigranih partija

Iz tablice. 7 i 8, može se vidjeti da se u 20 izgubljenih igara, strategije 1, 2, 3 za prvog igrača pojavljuju 12, 3, 5 puta, prema tome, njihove relativne učestalosti su redom jednake; strategije 1, 2, 3 za drugog igrača pojavljuju se redom 7, odnosno 11,2 puta, stoga su njihove relativne učestalosti redom jednake; približna vrijednost cijene igre. Ova aproksimacija je dovoljno dobra.

Zaključno, napominjemo da ako igra ima više od jednog rješenja, tada će se približne vrijednosti cijene igre i dalje neograničeno približavati stvarnoj cijeni igre, a relativne učestalosti pojavljivanja strategija igrači se više neće nužno približavati pravim optimalnim mješovitim strategijama igrača.

Analiza rezultata

U ovom se kolegiju gradivo za pronalaženje rješenja antagonističkih igara proučava grafičkom, matričnom metodom, metodom sukcesivne aproksimacije cijene igre. Pronađene su optimalne strategije prvog i drugog igrača, kao i cijena igre u igrama 2x2, 2xn i mx2, kao iu igrama koje koriste matričnu metodu i Brownovu metodu.

Na primjeru para modelirana je igra 2x2 koja je riješena algebarskom i grafičkom metodom. Rješavajući igru ​​algebarskom metodom, rješenje pokazuje da će primjenom svojih optimalnih mješovitih strategija prvi i drugi igrač provesti zajedno 4,6 sati. Grafičko rješenje problema pokazalo se s malom greškom i iznosilo je 4,5 sata.

Također su modelirana dva zadatka 2xn i mx2. U problemu 2xn razmatrana je poljoprivredna kultura i strategija pokazuje da je bolje zasaditi polje 50 puta 50, a cijena igre bila je 3,75 milijuna rubalja. A u problemu mx2 razmatran je par, čija je strategija pokazala da je jeftinije ići u park i kino, a cijena i trošak bit će 4,3 rublja.

Zadatak je modeliran za matričnu metodu, u kojoj su razmatrana dva restorana, rješenje problema je pokazalo da će pri primjeni optimalne mješovite strategije dobit prvog restorana biti 15,6 milijuna rubalja, a pri korištenju njegove optimalne mješovite strategije prema drugi restoran, neće dopustiti da prvi zaradi više od 15,6 milijuna rubalja. Rješenje grafičkom metodom dalo je pogrešku, a cijena igre bila je 14,9 milijuna rubalja.

Za Brownovu metodu izrađen je zadatak u kojem se uzimaju u obzir sindikat i uprava poduzeća čija je zadaća osigurati hranu radnicima. Kada oba igrača koriste svoje optimalne strategije, hrana po osobi bit će 2,45 tisuća rubalja.

Popis korištenih izvora

1) Vilisov V.Ya. Bilješke s predavanja "Teorija igara i statistička rješenja", - Ogranak - "Voskhod" MAI. 1979. 146 str.

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

3) Cherchmen U., Akof R., Arnof L., Uvod u operacijska istraživanja. - 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

Domaćin na Allbest.ru

Slični dokumenti

Odlučivanje kao posebna vrsta ljudske djelatnosti. Racionalni prikaz matrice igre. Primjeri matričnih igara u čistim i mješovitim strategijama. Operacijska istraživanja: odnos problema linearnog programiranja s modelom teorije igara.

seminarski rad, dodan 05.05.2010


Igre koje se ponavljaju mnogo puta, njihova karakteristična svojstva i faze. Mješovite strategije, uvjeti i mogućnosti njihove primjene u praksi. Analitička metoda za rješavanje igre 2 x 2. Osnovni teoremi za pravokutne igre. Algebarska rješenja.

prezentacija, dodano 23.10.2013


Osnovne definicije teorije bimatričnih igara. Primjer bimatrične igre "Učenik-učitelj". Mješovite strategije u bimatričnim igrama. Potražite "situaciju ravnoteže". 2x2 bimatrične igre i formule za slučaj kada svaki igrač ima dvije strategije.

sažetak, dodan 13.02.2011


Proučavanje općih informacija o matričnim i antagonističkim igrama. Koncept pozicijske igre, stablo, skup informacija. Razmatranje principa maksimina i principa ravnoteže. Pareto optimalnost. Pozicijska neantagonistička igra, njena svojstva.

seminarski rad, dodan 17.10.2014


Teorija igara je grana matematike čiji je predmet proučavanje matematičkih modela za donošenje optimalnih odluka u sukobu. Iterativna Brown-Robinsonova metoda. Monotoni iterativni algoritam za rješavanje matričnih igara.

diplomski rad, dodan 08.08.2007


Sastavljanje matrice isplata, traženje donje i gornje neto cijene igre, maximin i minimax strategije igrača. Pojednostavljenje matrice plaćanja. Rješavanje matrične igre svođenjem na problem linearnog programiranja i dodatkom "Traži rješenje".

test, dodan 10.11.2014


Teorija igara je matematička teorija konfliktnih situacija. Razvoj matematičkog modela igre s nultim zbrojem za dvije osobe, njegova implementacija u obliku programskih kodova. Metoda rješavanja problema. Ulazni i izlazni podaci. Program, uputstvo za upotrebu.

seminarski rad, dodan 17.08.2013


Osnove simpleks metode, ocjena njezine uloge i značaja u linearnom programiranju. Geometrijska interpretacija i algebarsko značenje. Određivanje maksimuma i minimuma linearne funkcije, posebni slučajevi. Rješenje problema matrično simpleks metodom.

diplomski rad, dodan 01.06.2015


Tehnike konstruiranja matematičkih modela računalnih sustava koji odražavaju strukturu i procese njihova funkcioniranja. Broj pristupa datotekama tijekom prosječnog zadatka. Utvrđivanje mogućnosti smještaja datoteka u vanjske memorijske pogone.

laboratorijski rad, dodano 21.06.2013


Projektiranje matematičkog modela. Opis igre tic-tac-toe. Model logičke igre temeljen na Booleovoj algebri. Digitalni elektronički uređaji i razvoj njihovog matematičkog modela. Igraća konzola, kontroler za igru, žica za ploču za igru.

Teorija igara je teorija matematičkih modela donošenja odluka u uvjetima sukoba ili neizvjesnosti. Pretpostavlja se da akcije stranaka u igri karakteriziraju određene strategije – skupovi pravila djelovanja. Ako dobitak jedne strane neizbježno dovodi do gubitka druge strane, onda se govori o antagonističkim igrama. Ako je skup strategija ograničen, tada se igra naziva matričnom i rješenje se može dobiti vrlo jednostavno. Rješenja dobivena uz pomoć teorije igara korisna su u izradi planova u slučaju mogućeg protivljenja konkurenata ili neizvjesnosti u vanjskom okruženju.

Ako je bimatrična igra antagonistička, tada je isplatna matrica igrača 2 potpuno određena isplatnom matricom igrača 1 (odgovarajući elementi ove dvije matrice razlikuju se samo u predznaku). Stoga je bimatrična antagonistička igra u potpunosti opisana jednom jedinom matricom (matrica isplate igrača 1) i prema tome se naziva matrična igra.

Ova igra je antagonistička. U njemu j \u003d x2 - O, P i R (O, O] = H (P, P) = -I i R (O, P) = R (P, O) = 1, ili u matričnom obliku o str

Neka je neka klasa igara G "zrcalno zatvorena", tj. zajedno sa svakom svojom igrom sadrži zrcalno izomorfnu igru ​​(budući da su sve igre koje su zrcalno izomorfne datoj međusobno izomorfne, mi, u skladu s upravo rečenim, možemo govoriti o jednoj zrcalno izomorfnoj igri). Takva klasa je, na primjer, klasa svih antagonističkih igara ili klasa svih matričnih igara.

Prisjećajući se definicije prihvatljivih situacija u antagonističkoj igri, dobivamo da je situacija (X, Y) u mješovitom proširenju matrične igre prihvatljiva za igrača 1 ako i samo ako za bilo koji x G x nejednakost

Proces pretvaranja igara u simetrične naziva se simetrizacija. Ovdje opisujemo jednu metodu simetrizacije. Druga, bitno drugačija verzija simetrizacije bit će dana u odjeljku 26.7. Obje ove varijante simetrizacije zapravo su primjenjive na proizvoljne antagonističke igre, ali će biti formulirane i dokazane samo za matrične igre.

Dakle, početni pojmovi i oznake teorije općih antagonističkih igara podudaraju se s odgovarajućim pojmovima i oznakama teorije matričnih igara.

Za konačne antagonističke (matrične) igre, postojanje ovih ekstrema smo dokazali u 10. poglavlju. 1, a cijela je poanta bila uspostaviti njihovu ravnopravnost ili barem pronaći načine za prevladavanje njihove nejednakosti.

Razmatranje matričnih igara već pokazuje da postoje antagonističke igre bez ravnotežnih situacija (pa čak i bez e-ravnotežnih situacija za dovoljno male e > 0) u početno zadanim strategijama igrača.

Ali svaka konačna (matrična) igra može se proširiti na beskonačnu igru, na primjer, davanjem svakom igraču bilo kojeg broja dominirajućih strategija (vidi 22. poglavlje 1). Očito, takvo proširenje igračevog skupa strategija zapravo neće značiti proširenje njegovih mogućnosti, a njegovo stvarno ponašanje u proširenoj igri ne bi se trebalo razlikovati od ponašanja u originalnoj igri. Tako smo odmah dobili dovoljan broj primjera beskonačnih antagonističkih igara koje nemaju sedlaste točke. Ima i ovakvih primjera.

Dakle, da bi se implementirao maksimin princip u beskonačnoj antagonističkoj igri, potrebno je, kao iu slučaju konačne (matrične) igre, neko proširenje strateških mogućnosti igrača. Za 96

Kao i u slučaju matričnih igara (vidi Poglavlje 1, 17), za opće antagonističke igre važnu ulogu igra koncept spektra mješovite strategije, koji ovdje, međutim, treba dati općenitiju definiciju.

Konačno, primijetite da je skup svih mješovitih strategija igrača 1 u proizvoljnoj antagonističkoj igri, kao u matrici

Čak i razmatranje antagonističkih igara pokazuje da veliki broj takvih igara, uključujući one konačne, matrične igre, imaju ravnotežne situacije ne u izvornim, čistim strategijama, već samo u generaliziranim, mješovitim strategijama. Stoga je za općenite, neantagonističke, nekooperativne igre prirodno ravnotežne situacije tražiti upravo u mješovitim strategijama.

Tako smo, na primjer (vidi sliku 3.1), već primijetili da se "Izvođač" gotovo nikada ne mora nositi s neizvjesnošću ponašanja. Ali ako uzmemo konceptualnu razinu tipa "Administrator", onda je sve upravo suprotno. U pravilu, glavna vrsta neizvjesnosti s kojom se takav "naš donositelj odluka" mora suočiti je "Konflikt". Sada možemo pojasniti da se obično radi o nestriktnom rivalstvu. Nešto rjeđe "Administrator" donosi odluke u uvjetima "prirodne neizvjesnosti", a još rjeđe nailazi na strogi, antagonistički sukob. Osim toga, sukob interesa pri donošenju odluka od strane "Administratora" događa se takoreći "jednom", tj. po našoj klasifikaciji, on često igra samo jednu (ponekad vrlo mali broj) partija igre. Ljestvice za procjenu posljedica češće su kvalitativne nego kvantitativne. Strateška neovisnost "Administratora" prilično je ograničena. Uzimajući u obzir gore navedeno, može se tvrditi da se problemske situacije ove veličine najčešće moraju analizirati korištenjem nekooperativnih neantagonističkih bi-matričnih igara, štoviše, u čistim strategijama.

Principi rješavanja matričnih antagonističkih igara

Kao rezultat toga, razumno je očekivati ​​da će se u gore opisanoj igri protivnici pridržavati svojih odabranih strategija. Matrična antagonistička igra za koju je max min fiv = min max Aiy>

Međutim, nisu sve matrične antagonističke igre sasvim određene, i to u općem slučaju

Dakle, u općem slučaju, za rješavanje matrične antagonističke igre dimenzije /uxl, potrebno je riješiti par dualnih problema linearnog programiranja, što rezultira skupom optimalnih strategija, / i troškom igre v.

Kako je definirana matrična antagonistička igra dviju osoba?

Koje su metode za pojednostavljenje i rješavanje matričnih antagonističkih igara

U slučaju igre dviju osoba, prirodno je njihove interese smatrati izravno suprotnim – igra je antagonistička. Dakle, isplata jednog igrača jednaka je gubitku drugog (zbroj dobitaka oba igrača je nula, otuda i naziv, igra s nultom sumom). Razmotrit ćemo igre u kojima svaki igrač ima konačan broj alternativa. Funkcija isplate za takvu igru ​​za dvije osobe s nultim zbrojem može se dati u obliku matrice (u obliku matrice isplate).

Kao što je već navedeno, konačna antagonistička igra naziva se matrica.

MATRIČNE IGRE - klasa antagonističkih igara u kojima sudjeluju dva igrača, a svaki igrač ima konačan broj strategija. Ako jedan igrač ima m strategija, a drugi igrač ima n strategija, tada možemo konstruirati matricu igre dimenzije txn. Mi. može i ne mora imati sedlo. U potonjem slučaju

Razmotrimo igru ​​parova s ​​konačnim nultim zbrojem. Označimo sa a isplata igrača A, i kroz b- pobjeda igrača B. Jer a = –b, onda pri analizi takve igre nema potrebe razmatrati oba ova broja - dovoljno je uzeti u obzir isplatu jednog od igrača. Neka bude npr. A. U nastavku, radi lakšeg prikaza, strana A nazvat ćemo uvjetno " mi"i sa strane B – "neprijatelj".

Pustite nas m moguće strategije A 1 , A 2 , …, A m, i neprijatelja n moguće strategije B 1 , B 2 , …, B n(takva igra se zove igra m×n). Pretpostavimo da je svaka strana odabrala određenu strategiju: mi smo odabrali A i, protivnik Bj. Ako se igra sastoji samo od osobnih poteza, onda izbor strategija A i i Bj jedinstveno određuje ishod igre - naš dobitak (pozitivan ili negativan). Označimo ovaj dobitak kao aij(pobjeda kada izaberemo strategiju A i, a neprijatelj - strategije Bj).

Ako igra sadrži, osim osobnih nasumičnih poteza, isplatu za par strategija A i, Bj je slučajna varijabla koja ovisi o ishodima svih slučajnih poteza. U ovom slučaju, prirodna procjena očekivanog dobitka je matematičko očekivanje slučajnog dobitka. Radi praktičnosti, označit ćemo sa aij i sam dobitak (u igri bez slučajnih poteza) i njegovo matematičko očekivanje (u igri sa slučajnim potezima).

Pretpostavimo da znamo vrijednosti aij za svaki par strategija. Ove vrijednosti mogu se napisati kao matrica čiji redovi odgovaraju našim strategijama ( A i), a stupci prikazuju strategije protivnika ( Bj):

Takva matrica se zove isplatna matrica igre ili jednostavno matrica igre.

Imajte na umu da izrada matrice isplate za igre s velikim brojem strategija može biti težak zadatak. Na primjer, za partiju šaha, broj mogućih strategija je toliko velik da je konstrukcija matrice isplate praktički nemoguća. Međutim, u načelu se svaka konačna igra može svesti na matrični oblik.

Smatrati primjer 1 4×5 antagonistička igra. Mi imamo četiri strategije na raspolaganju, neprijatelj ima pet strategija. Matrica igre je sljedeća:

Koju bismo strategiju trebali imati (tj. igrač A) koristiti? Koju god strategiju odabrali, razuman protivnik će na nju odgovoriti strategijom za koju će naša dobit biti minimalna. Na primjer, ako odaberemo strategiju A 3 (iskušan pobjedom od 10), protivnik će odabrati strategiju kao odgovor B 1 , a naš dobitak će biti samo 1. Očito, na temelju načela opreza (a to je glavno načelo teorije igara), moramo odabrati strategiju u kojoj naš minimalni dobitak je maksimalan.

Označimo sa a ja minimalna vrijednost isplate za strategiju A i:

i dodajte stupac koji sadrži ove vrijednosti u matricu igre:

Prilikom odabira strategije moramo odabrati onu za koju vrijednost a ja maksimum. Označimo ovu najveću vrijednost sa α :

Vrijednost α nazvao niža cijena igre ili maksimin(maksimalni minimalni dobitak). Strategija igrača A koji odgovara maksiminu α , Zove se maximin strategija.

U ovom primjeru maksimin α jednaka je 3 (odgovarajuća ćelija u tablici označena je sivom bojom), a maksimin strategija je Ačetiri . Odabravši ovu strategiju, možemo biti sigurni da ćemo za bilo koje ponašanje neprijatelja dobiti ne manje od 3 (a možda i više s "nerazumnim" ponašanjem neprijatelja). Ova vrijednost je naš zajamčeni minimum, koji možemo osigurati za sami, pridržavajući se najopreznije strategije ("reosiguranje").

Sada ćemo izvesti slično obrazloženje za neprijatelja B B A B 2 - odgovorit ćemo mu A .

Označimo sa βj A B) za strategiju A i:

βj β :

7. ŠTO JE IGRA VEĆE VRIJEDNOSTI Sada ćemo izvesti slično razmišljanje za protivnika B. Njemu je u interesu minimalizirati naš dobitak, odnosno dati nam manje, ali mora računati na naše ponašanje, što je za njega najgore. Na primjer, ako on bira strategiju B 1 , onda ćemo mu odgovoriti strategijom A 3 , a dat će nam 10. Ako hoće B 2 - odgovorit ćemo mu A 2 , a on će dati 8 itd. Očito, oprezan protivnik mora izabrati strategiju u kojoj naš maksimalni dobitak bit će minimalan.

Označimo sa βj maksimalne vrijednosti u stupcima matrice isplate (maksimalna isplata igrača A, ili, što je isto, najveći gubitak igrača B) za strategiju A i:

i dodajte redak koji sadrži ove vrijednosti u matricu igre:

Odabirom strategije, neprijatelj će preferirati onu za koju je vrijednost βj minimum. Označimo to sa β :

Vrijednost β nazvao najviša cijena igre ili minimax(minimalni maksimalni dobitak). Strategija protivnika (igrača) koja odgovara minimaksu B), Zove se minimax strategija.

Minimax je vrijednost dobitka, više od koje nam razuman protivnik sigurno neće dati (drugim riječima, razuman protivnik neće izgubiti više od β ). U ovom primjeru, minimax β jednak je 5 (odgovarajuća ćelija u tablici označena je sivom bojom) i postiže se strategijom protivnika B 3 .

Dakle, po načelu opreza ("uvijek očekuj najgore!") moramo odabrati strategiju A 4 , a neprijatelj - strategija B 3 . Načelo opreza temeljno je u teoriji igara i zove se minimaks princip.

Smatrati primjer 2. Neka igrači A i NA jedan od tri broja napisan je istovremeno i neovisno jedan o drugom: ili "1", ili "2", ili "3". Ako je zbroj napisanih brojeva paran, tada igrač B plaća igrača A ovaj iznos. Ako je iznos neparan, tada igrač plaća ovaj iznos A igrač NA.

Zapišimo matricu isplate igre i pronađimo donju i gornju cijenu igre (broj strategije odgovara napisanom broju):

Igrač A moraju se pridržavati maksimin strategije A 1 za pobjedu najmanje -3 (tj. za poraz najviše 3). Minimax strategija igrača B bilo koju od strategija B 1 i B 2, što jamči da neće dati više od 4.

Dobit ćemo isti rezultat ako isplatnu matricu napišemo sa stajališta igrača NA. Zapravo, ova matrica je dobivena transponiranjem matrice konstruirane sa stajališta igrača A, te mijenjanje predznaka elemenata u suprotno (budući da je isplata igrača A je gubitak igrača NA):

Na temelju ove matrice proizlazi da igrač B moraju slijediti bilo koju od strategija B 1 i B 2 (i tada neće izgubiti više od 4), i igrač A- strategije A 1 (i tada neće izgubiti više od 3). Kao što vidite, rezultat je potpuno isti kao i gore dobiveni, tako da analiza nije bitna s gledišta kojeg igrača provodimo.

8 ŠTO JE VRIJEDNA IGRA.

9. OD ČEGA SE SASTOJI PRINCIP MINIMAX. 2. Donja i gornja cijena igre. Minimax princip

Razmotrimo matričnu igru ​​tipa s matricom isplate

Ako igrač ALIće izabrati strategiju A i, tada će sve njegove moguće isplate biti elementi ja-ti redak matrice IZ. Najgore za igrača ALI slučaj kada igrač NA primjenjuje strategiju prikladnu za minimum element ove linije, isplata igrača ALI bit će jednak broju.

Stoga, kako bi dobili maksimalnu isplatu, igrač ALI potrebno je odabrati jednu od strategija za koje broj maksimum.

Najjednostavniji slučaj, detaljno razrađen u teoriji igara, je igra konačnih parova s ​​nultim zbrojem (antagonistička igra dviju osoba ili dviju koalicija). Razmotrimo igru ​​G u kojoj sudjeluju dva igrača A i B, koji imaju suprotne interese: dobitak jednog jednak je gubitku drugog. Budući da je dobitak igrača A jednak dobitku igrača B sa suprotnim predznakom, može nas zanimati samo dobitak igrača a. Naravno, A želi maksimizirati, a B želi minimizirati a.

Radi jednostavnosti, mentalno se identificirajmo s jednim od igrača (neka to bude A) i nazovimo ga "mi", a igrača B - "protivnik" (naravno, iz toga ne proizlaze nikakve stvarne prednosti za A). Neka nam budu moguće strategije i protivnik - moguće strategije (takva igra se zove igra). Označimo naš dobitak ako mi koristimo strategiju i protivnik koristi strategiju

Tablica 26.1

Pretpostavimo da nam je za svaki par strategija isplata (ili prosječna isplata) a poznata. Tada je, u načelu, moguće sastaviti pravokutnu tablicu (matricu) u kojoj su navedene strategije igrača i odgovarajući dobici (vidi tablicu 26.1).

Ako se sastavi takva tablica, onda se kaže da je igra G svedena na matrični oblik (samo po sebi, dovođenje igre u takav oblik već može biti težak zadatak, a ponekad i praktički nemoguć, zbog ogromnog broja strategija ). Imajte na umu da ako je igra svedena na matrični oblik, tada je igra s više poteza zapravo svedena na igru ​​s jednim potezom - od igrača se traži samo jedan potez: odabrati strategiju. Ukratko ćemo označiti matricu igre

Razmotrimo primjer igre G (4X5) u matričnom obliku. Nama su na raspolaganju (na izbor) četiri strategije, neprijatelj ima pet strategija. Matrica igre data je u tablici 26.2

Razmislimo koju strategiju mi ​​(igrač A) koristimo? Matrix 26.2 ima primamljivu isplatu "10"; povučeni smo da odaberemo strategiju u kojoj ćemo dobiti ovu “slacicu”.

Ali čekaj, ni neprijatelj nije glup! Ako mi izaberemo strategiju, on će, nama u inat, izabrati strategiju, a mi ćemo dobiti neku mizernu "1". Ne, ne možete birati strategiju! Kako biti? Očito, polazeći od načela opreza (a ono je glavno načelo teorije igara), moramo odabrati strategiju za koju je naš minimalni dobitak maksimalan.

Tablica 26.2

To je takozvani “mini-max princip”: ponašaj se tako da uz najlošije ponašanje svog protivnika dobiješ maksimalnu dobit.

Prepišimo tablicu 26.2 iu desnom dodatnom stupcu upisat ćemo minimalnu vrijednost dobitka u svakom retku (minimum retka); označimo ga redom a (vidi tablicu 26.3).

Tablica 26.3

Od svih vrijednosti (desni stupac) odabrana je najveća (3). Odgovara strategiji. Odabravši ovu strategiju, u svakom slučaju možemo biti sigurni da (za bilo koje ponašanje neprijatelja) nećemo dobiti manje od 3. Ova vrijednost je naš zajamčeni dobitak; ponašajući se pažljivo, ne možemo dobiti manje od ovoga, možemo dobiti više).

Ova isplata se naziva niža cijena igre (ili "maximin" - maksimum od minimalnih isplata). Označit ćemo ga kao a. U našem slučaju

Sada zauzmimo gledište neprijatelja i zastupajmo ga. Nije on nekakav pijun, ali i razuman! Birajući strategiju, želio bi dati manje, ali mora računati na naše ponašanje, što je za njega najgore. Ako odabere strategiju, mi ćemo mu odgovoriti i on će dati 10; ako odabere, mi ćemo mu odgovoriti i on će to vratiti, itd. Dodajemo dodatni donji red u tablicu 26.3 i upisujemo maksimalne stupce u njega. Očito, oprezan protivnik mora odabrati strategiju za koju je ova vrijednost minimalna (odgovarajuća vrijednost 5 označena je u tablici 26.3) . Ova vrijednost P je vrijednost dobitka, više od koje nam razuman protivnik sigurno neće dati. Zove se gornja cijena igre (ili "mi-nimax" - minimum od maksimalnih dobitaka). U našem primjeru, i postiže se protivnikovom strategijom

Dakle, temeljem načela opreza (pravilo reosiguranja “uvijek računaj na najgore!”) moramo izabrati strategiju A, a neprijatelja - strategiju.Takve strategije se nazivaju “minimaks” (načelo minimaksa). Sve dok se obje strane u našem primjeru drže svojih minimax strategija, dobit će biti

Sada zamislite na trenutak da smo naučili da neprijatelj slijedi strategiju. Hajde, kaznimo ga za ovo i izaberemo strategiju, dobijemo 5, a ovo i nije tako loše. Ali na kraju krajeva, ni neprijatelj nije promašaj; dajte mu do znanja da je naša strategija , on će također požuriti da odabere , smanjujući našu isplatu na 2, itd. (partneri su "jurili oko strategija"). Ukratko, minimaks strategije u našem primjeru su nestabilne u odnosu na informacije o ponašanju druge strane; te strategije nemaju svojstvo ravnoteže.

Je li uvijek ovako? Ne, ne uvijek. Razmotrimo primjer s matricom danom u tablici 26.4.

U ovom primjeru donja cijena igre jednaka je gornjoj: . Što iz ovoga slijedi? Minimaks strategije igrača A i B će biti stabilne. Sve dok ih se oba igrača drže, isplata je 6. Da vidimo što će se dogoditi ako (A) saznamo da se protivnik (B) drži strategije B?

Tablica 26.4

I baš ništa se neće promijeniti, jer svako odstupanje od strategije može samo pogoršati našu situaciju. Jednako tako, informacije koje primi protivnik neće ga natjerati da odstupi od svoje strategije. Znak prisutnosti sedlaste točke i uravnoteženog para strategija je jednakost donje i gornje cijene igre; ukupna vrijednost naziva se cijena igre. Mi ćemo to označiti

Strategije (u ovom slučaju ) kod kojih se ostvaruje taj dobitak nazivaju se optimalne čiste strategije, a njihova kombinacija je rješenje igre. U ovom slučaju se kaže da je sama igra riješena u čistim strategijama. Obje strane A i B mogu dobiti svoje optimalne strategije u kojima je njihova pozicija najbolja moguća. I da igrač A dobije 6, a igrač B izgubi, pa, ovo su uvjeti igre: oni su korisni za A, a nepovoljni za B.

Čitatelj može imati pitanje: zašto se optimalne strategije nazivaju "čistim"? Gledajući malo unaprijed, odgovorimo na ovo pitanje: postoje "mješovite" strategije, koje se sastoje u činjenici da igrač ne koristi jednu strategiju, već nekoliko, izmjenjujući ih nasumično. Dakle, ako priznamo, osim čistih, i mješovite strategije, svaka konačna igra ima rješenje - točku ravnoteže. No više o tome tek slijedi.

Prisutnost sedla u igri daleko je od toga da je pravilo, to je iznimka. Većina igara nema sedlo. Međutim, postoji niz igara koje uvijek imaju sedlo i stoga se rješavaju u čistim strategijama. To su takozvane “igrice s potpunom informacijom”. Igra s potpunom informacijom je igra u kojoj svaki igrač na svakom osobnom potezu zna cijelu pretpovijest svog razvoja, odnosno rezultate svih prethodnih poteza, osobnih i slučajnih. Primjeri igara s potpunim informacijama su dama, šah, tic-tac-toe itd.

U teoriji igara je dokazano da svaka igra s potpunom informacijom ima sedlišnu točku, te se stoga može riješiti u čistim strategijama. U svakoj igri sa savršenim informacijama, postoji par optimalnih strategija koje daju stabilnu isplatu jednaku cijeni igre i. Ako se takva igra sastoji samo od osobnih poteza, onda kada svaki igrač primijeni svoju optimalnu strategiju, ona mora završiti na sasvim određen način - isplatom jednakom cijeni igre. Dakle, ako se zna rješenje igre, sama igra gubi smisao!

Uzmimo elementarni primjer igre s potpunom informacijom: dva igrača naizmjenično stavljaju novčiće na okrugli stol, proizvoljno birajući položaj središta novčića (međusobno preklapanje novčića nije dopušteno). Pobjednik je onaj koji stavi zadnji novčić (kada za druge nema mjesta). Lako je vidjeti da je ishod ove igre u suštini gotov zaključak. Postoji određena strategija koja osigurava da igrač koji prvi stavi novčić pobijedi.

Naime, on mora prvi put staviti peticu u sredinu stola, a potom na svaki potez protivnika odgovoriti simetričnim potezom. Očito, kako god se protivnik ponašao, ne može izbjeći poraz. Potpuno je ista situacija sa šahom i igrama s potpunom informacijom općenito: bilo koja od njih, zapisana u matričnom obliku, ima sedlišnu točku, pa je stoga rješenje u čistim strategijama i stoga ima smisla samo dok to rješenje ima nije pronađeno. Recimo partija šaha ili uvijek završi pobjedom bijelog, ili uvijek završi pobjedom crnog, ili uvijek završi remijem, ali što točno - još ne znamo (na sreću ljubitelja šaha). Dodajmo još nešto: teško da ćemo to znati u dogledno vrijeme, jer je broj strategija toliki da je iznimno teško (ako ne i nemoguće) igru ​​svesti na matrični oblik i u njemu pronaći sedlo.

A sada se zapitajmo što učiniti ako igra nema sedlu točku: Pa, ako je svaki igrač prisiljen odabrati jednu čistu strategiju, onda nema što učiniti: moramo se voditi načelom minimaksa. Druga stvar je ako možete "pomiješati" svoje strategije, izmjenjivati ​​ih nasumično s nekim vjerojatnostima. Korištenje mješovitih strategija zamišljeno je na sljedeći način: igra se ponavlja mnogo puta; prije svake partije igre, kada igrač dobije osobni potez, on svoj izbor "povjerava" slučaju, "baca ždrijeb", uzima strategiju koja mu je ispala (već znamo kako organizirati ždrijeb iz prethodnog poglavlja ).

Mješovite strategije u teoriji igara model su promjenjivih, fleksibilnih taktika, kada nitko od igrača ne zna kako će se protivnik ponašati u datoj igri. Ova se taktika (iako obično bez ikakvog matematičkog opravdanja) često koristi u kartaške igre. Napomenimo u isto vrijeme da je najbolji način da sakrijete svoje ponašanje od neprijatelja da mu date nasumičan karakter i, prema tome, ne znate unaprijed što ćete učiniti.

Dakle, razgovarajmo o mješovitim strategijama. Označit ćemo mješovite strategije igrača A i B

U konkretnom slučaju, kada su sve vjerojatnosti, osim jedne, jednake nuli, a ova je jednaka jedinici, mješovita strategija prelazi u čistu.

Postoji temeljni teorem teorije igara: svaka igra s konačnim zero-sumom za dva igrača ima barem jedno rješenje - par optimalnih strategija, općenito izmiješanih, i odgovarajuću cijenu

Par optimalnih strategija koje tvore rješenje igre ima sljedeće svojstvo: ako se jedan od igrača pridržava svoje optimalne strategije, drugome ne može biti isplativo odstupiti od svoje. Ovaj par strategija čini neku vrstu ravnoteže u igri: jedan igrač želi isplatu okrenuti na maksimum, drugi - na minimum, svatko vuče u svom smjeru, te se, uz razumno ponašanje obojice, uspostavlja ravnoteža i uspostavljena je stabilna isplata v. Ako je onda igra korisna za nas, ako - za neprijatelja; kada je igra "poštena", podjednako korisna za oba sudionika.

Razmotrite primjer igre bez sedla i dajte (bez dokaza) njezino rješenje. Igra je sljedeća: dva igrača A i B istovremeno i bez riječi pokazuju jedan, dva ili tri prsta. O dobitku odlučuje ukupan broj prstiju: ako je paran, A pobjeđuje i od B dobiva iznos jednak tom broju; ako je neparan, tada, naprotiv, A plaća B-u iznos jednak ovom broju. Što bi igrači trebali učiniti?

Kreirajmo matricu igre. U jednoj igri svaki igrač ima tri strategije: pokaži jedan, dva ili tri prsta. Matrica 3x3 data je u tablici 26.5; dodatni desni stupac prikazuje minimume reda, a dodatni donji red prikazuje maksimume stupca.

Niža cijena igre je u skladu sa strategijom. To znači da razumnim, opreznim ponašanjem jamčimo da nećemo izgubiti više od 3. Slaba utjeha, ali ipak bolja od recimo pobjede - 5, koja se nalazi u nekim stanice matriksa. Loše je za nas, igrač L... No, tješimo se: čini se da je položaj protivnika još gori: niža cijena igre na. razumno ponašanje, dat će nam najmanje 4.