Antagonističke igre sa kontinuiranim strategijama. Rješavanje matričnih antagonističkih igara Rješavanje antagonističkih igara na mreži

Zove se igra sa nultom sumom za dvije osobe u kojoj svaka od njih ima konačan skup strategija. Pravila matrične igre određena su matricom isplate, čiji su elementi isplate prvog igrača, a to su i gubici drugog igrača.

Matrix game je antagonistička igra. Prvi igrač dobija maksimalnu zagarantovanu (ne zavisi od ponašanja drugog igrača) isplatu jednaku ceni igre, shodno tome, drugi igrač ostvaruje minimalni garantovani gubitak.

Ispod strategija se shvata kao skup pravila (principa) koji određuju izbor varijante radnji za svaki lični potez igrača, u zavisnosti od trenutne situacije.

Sada o svemu po redu i detaljno.

Matrica isplate, čiste strategije, cijena igre

AT matrična igra njegova pravila su određena matrica isplate .

Zamislite igru ​​u kojoj su dva učesnika: prvi igrač i drugi igrač. Neka ima prvi igrač mčiste strategije, a na raspolaganju drugom igraču - nčiste strategije. Pošto se igra razmatra, prirodno je da u ovoj igri ima pobeda i poraza.

AT matrica plaćanja elementi su brojevi koji izražavaju dobitke i gubitke igrača. Pobjede i gubici mogu biti izraženi u bodovima, novcu ili drugim jedinicama.

Kreirajmo matricu isplate:

Ako prvi igrač odabere i-ta čista strategija i drugi igrač j-th čista strategija, onda je isplata prvog igrača aij jedinica, a gubitak drugog igrača je također aij jedinice.

Jer aij + (- a ij ) = 0, tada je opisana igra matrična igra nulte sume.

Najjednostavniji primjer matrične 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 istovremeno 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 su na raspolaganju drugom igraču. Odgovarajuća matrica isplate bi bila:

Zadatak teorije igara je da odredi izbor strategije prvog igrača, koja bi mu garantovala maksimalan prosječan dobitak, kao i izbor strategije drugog igrača, koja bi mu garantovala maksimalan prosječan gubitak.

Kako se bira strategija u matričnoj igri?

Pogledajmo ponovo matricu isplate:

Prvo, određujemo isplatu prvog igrača ako koristi ičista strategija. Ako prvi igrač koristi i-tu čistu strategiju, onda je logično pretpostaviti da će drugi igrač koristiti tako čistu strategiju, zbog čega bi isplata prvog igrača bila minimalna. Zauzvrat, prvi igrač će koristiti tako čistu strategiju koja bi mu pružila maksimalnu isplatu. Na osnovu ovih uslova, isplata prvog igrača, koju označavamo kao v1 , zove se maximin win ili niža cijena igre .

At za ove vrijednosti, prvi igrač treba postupiti na sljedeći način. Iz svake linije napišite vrijednost minimalnog elementa i od njih odaberite maksimum. Tako će isplata prvog igrača biti maksimum od minimuma. Otuda i naziv - maximin win. Broj linije ovog elementa će biti broj čiste strategije koju odabere prvi igrač.

Sada odredimo gubitak drugog igrača ako koristi j-th strategija. U ovom slučaju, prvi igrač koristi svoju čistu strategiju, u kojoj bi gubitak drugog igrača bio maksimalan. Drugi igrač mora izabrati tako čistu strategiju u kojoj bi njegov gubitak bio minimalan. Gubitak drugog igrača koji označavamo kao v2 , zove se minimalni gubitak ili vrhunska cijena igre .

At rješavanje problema oko cijene igre i određivanje strategije da biste odredili ove vrijednosti za drugog igrača, postupite na sljedeći način. Iz svake kolone napišite vrijednost maksimalnog elementa i od njih odaberite minimum. Tako će gubitak drugog igrača biti minimum od maksimuma. Otuda i naziv - minimax gain. Broj kolone ovog elementa će biti 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 redova je 2, ovo je niža cijena igre, njoj odgovara prvi red, dakle, maksimalna strategija prvog igrača je prva. Najmanji od najvećih elemenata kolona je 5, ovo je gornja cijena igre, druga kolona joj odgovara, dakle, minimax strategija drugog igrača je druga.

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

Dakle, zagarantovana isplata prvog igrača je:

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

.

Prvi igrač koristi svoju čistu strategiju tako da je gubitak drugog igrača maksimalan. Ovaj gubitak je definisan na sledeći način:

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

.

Još jedan primjer iz iste serije.

Primjer 2 Zadana je matrična igra s matricom isplate

.

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

Rješenje. Desno od matrice isplate ispisujemo najmanje elemente u njene redove i označavamo maksimum od njih, a sa dna matrice - najveće elemente u kolonama i biramo minimum od njih:

Najveći od najmanjih elemenata redova je 3, ovo je niža cijena igre, drugi red joj odgovara, dakle, maksimalna strategija prvog igrača je drugi. Najmanji od najvećih elemenata kolona je 5, ovo je gornja cijena igre, prva kolona joj odgovara, dakle, minimalna strategija drugog igrača je prva.

Sedlo u matričnim igrama

Ako su gornja i donja cijena igre iste, onda se smatra da matrična igra ima sedlo. Isto tako vrijedi i obrnuto: ako matrična igra ima sedlo, tada su gornja i donja cijena matrične igre iste. Odgovarajući element je i najmanji u redu i najveći u koloni i jednak je cijeni igre.

Dakle, ako je , onda je optimalna čista strategija prvog igrača, a optimalna čista strategija drugog igrača. Odnosno, jednake donje i gornje cijene igre postižu se na istom paru strategija.

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

Primjer 3 Zadana je matrična igra s matricom isplate

.

Rješenje. Desno od matrice isplate ispisujemo najmanje elemente u njene redove i označavamo maksimum od njih, a sa dna matrice - najveće elemente u kolonama i biramo minimum od njih:

Donja cijena igre je ista kao i gornja cijena igre. Dakle, cijena igre je 5. To je . Cijena igre jednaka je vrijednosti sedla. Maksimalna strategija prvog igrača je druga čista strategija, a minimalna strategija drugog igrača je treća čista strategija. Ova matrična igra ima rješenje u čistim strategijama.

Riješite sami problem matrične igre, a zatim pogledajte rješenje

Primjer 4 Zadana je matrična igra s matricom isplate

.

Pronađite donju i gornju cijenu igre. Da li ova matrična igra ima točku sedla?

Matrične igre sa optimalnom mješovitom strategijom

U većini slučajeva, matrična igra nema sedlo, tako da odgovarajuća matrična igra nema čista strateška rješenja.

Ali ima rješenje u optimalnim mješovitim strategijama. Da bi ih pronašli, potrebno je pretpostaviti da se igra ponavlja dovoljno puta da se na osnovu iskustva može pogoditi koja je strategija poželjnija. Stoga je odluka povezana sa konceptom vjerovatnoće i prosjeka (očekivanja). U konačnom rješenju postoji i analog sedla (tj. jednakost donje i gornje cijene igre) i analog strategija koje im odgovaraju.

Dakle, da bi prvi igrač dobio maksimalan prosječan dobitak, a drugi najmanji prosječan gubitak, sa određenom vjerovatnoćom treba koristiti čiste strategije.

Ako prvi igrač koristi čiste strategije sa vjerovatnoćama , zatim vektor se naziva mješovita strategija prvog igrača. Drugim riječima, to je "mješavina" čistih strategija. Zbir ovih vjerovatnoća jednak je jedan:

.

Ako drugi igrač koristi čiste strategije sa vjerovatnoćama , zatim vektor se naziva mješovita strategija drugog igrača. Zbir ovih vjerovatnoća jednak je jedan:

.

Ako prvi igrač koristi mješovitu strategiju str, a drugi igrač - mješovita strategija q, onda ima smisla očekivanu vrijednost prvi igrač pobjeđuje (drugi igrač gubi). Da biste ga pronašli, morate pomnožiti vektor mješovite strategije prvog igrača (koji će biti matrica od jednog reda), 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 .

Rješ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č se zove takva mješovita strategija koja bi mu omogućila maksimalnu prosječnu isplatu ako se igra ponovi dovoljan broj puta.

Optimalna mješovita strategija Drugi igrač se zove takva mješovita strategija koja bi mu omogućila minimalan prosječan gubitak ako se partija ponovi dovoljan broj puta.

Po analogiji sa zapisom maksimina i minimaksa u slučajevima čistih strategija, optimalne mješovite strategije se označavaju na sljedeći način (i povezane su s matematičkim očekivanjem, odnosno prosjekom, dobitka prvog igrača i gubitka drugog igrača):

,

.

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

Da bi se pronašle optimalne mješovite strategije i sedla, tj. riješite matričnu igru ​​u mješovitim strategijama , morate 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

Da biste riješili matričnu igru ​​u mješovitim strategijama, morate sastaviti pravu liniju problem linearnog programiranja i njegov dvostruki zadatak. U dualnom problemu transponuje se proširena matrica koja pohranjuje koeficijente varijabli u sistemu ograničenja, konstantne članove i koeficijente varijabli u funkciji cilja. U ovom slučaju, minimum funkcije cilja izvornog problema povezan je s maksimumom u dualnom problemu.

Funkcija cilja u problemu direktnog linearnog programiranja:

.

Sistem ograničenja u direktnom problemu linearnog programiranja:

Funkcija cilja u dvojnom problemu:

.

Sistem ograničenja u dualnom problemu:

Označiti optimalni plan problema direktnog linearnog programiranja

,

a optimalni plan dualnog problema je označen sa

Linearni oblici za odgovarajuće optimalne dizajne će biti označeni sa i ,

i trebate ih pronaći kao zbir odgovarajućih koordinata optimalnih planova.

U skladu sa definicijama iz prethodnog odeljka i koordinatama optimalnih planova, važe sledeće mešovite strategije prvog i drugog igrača:

.

Matematičari su to dokazali cijena igre izražava se u linearnim oblicima optimalnih planova kako slijedi:

,

odnosno recipročna vrijednost zbira koordinata optimalnih planova.

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

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

Primjer 6 Zadana je matrična igra s matricom isplate

.

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

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

Dobijamo rješenje direktnog problema:

.

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

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

Studenti, postdiplomci, mladi naučnici koji koriste bazu znanja u svom studiranju i radu biće vam veoma 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 Matrična metoda

2.4 Brown metoda

Analiza rezultata

Uvod

Antagonistička igra je igra sa nultom sumom. Antagonistička igra je nekooperativna igra u kojoj učestvuju dva igrača, čije su isplate suprotne.

Formalno, antagonistička igra može biti predstavljena trojkom , gdje su X i Y skupovi strategija prvog i drugog igrača, respektivno, F je funkcija isplate prvog igrača, koja povezuje svaki par strategija (x, y), gdje je realan broj koji odgovara korisnosti prvog igrača koji je shvatio ovu situaciju.

Pošto su interesi igrača suprotni, funkcija F istovremeno predstavlja gubitak drugog igrača.

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

1. Teorijski dio

1.1 Osnovne definicije i odredbe igre

Igru karakteriše sistem pravila koja određuju broj učesnika u igri, njihov moguće radnje i raspodjelu dobitaka u zavisnosti od njihovog ponašanja i ishoda. Igračem se smatra jedan učesnik ili grupa učesnika u igri koji za sebe imaju neke zajedničke interese koji se ne poklapaju sa interesima drugih grupa. Stoga se svaki učesnik ne smatra igračem.

Pravila ili uslovi 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č zatim donosi taj izbor potezima. Napraviti potez znači u određenoj fazi igre napraviti cijeli ili dio izbora odjednom, ovisno o mogućnostima koje su predviđene pravilima igre. Svaki igrač u određenoj fazi igre čini potez prema napravljenom 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 informacije o prošlom razvoju igre, ako je takva mogućnost dopuštena pravilima igre.

Skup pravila koja nedvosmisleno govore igraču koji izbor treba napraviti pri svakom potezu, ovisno o situaciji koja se razvila kao rezultat igre, naziva se igračeva strategija. Strategija u teoriji igara znači određeni potpuni plan akcije za igrača, koji pokazuje kako 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.

Postojaće igra sa nultom sumom kada je zbir isplata svih igrača u svakoj od igara jednak nuli, tj. u igri sa nultom sumom ukupni kapital svih igrača se ne menja, već se redistribuira među igračima zavisno od nastalih ishoda. Stoga se mnoge ekonomske i vojne situacije mogu posmatrati kao igre s nultom sumom.

Konkretno, igra dva igrača sa nultom sumom naziva se antagonističkom, jer su ciljevi igrača u njoj direktno suprotni: dobitak jednog igrača nastaje 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 sa nultom sumom može se posmatrati 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) je dodijeljen broj a ij, koji izražava isplata prvog igrača drugom igraču ako prvi igrač iskoristi svoju i-ta strategija, a drugi - svoju j-tu strategiju.

Svaki od igrača napravi 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č prima 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 nulte sume dva igrača nazivat će se jednostavno matrična igra. Očigledno, matrična igra spada u antagonističke igre. Iz njegove definicije slijedi da je za definiranje matrične igre dovoljno specificirati 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 red, a drugi igrač u j-toj koloni i prvi igrač (na račun drugog) prima isplatu koja se nalazi u matrici A na raskrsnici i-tog reda i j-te kolone.

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 određivanje optimalnih strategija i isplata igrača.

Glavna stvar u proučavanju igara je koncept optimalnih strategija za igrače. Ovaj koncept intuitivno ima sledeće značenje: igračeva strategija je optimalna ako mu primena ove strategije obezbeđuje najveću zagarantovanu isplatu za sve moguće strategije drugog igrača. Na osnovu ovih pozicija, prvi igrač ispituje matricu A svojih isplata prema formuli (1.1) na sljedeći način: za svaku vrijednost i (i = 1, 2, ..., m) određuje se minimalna vrijednost isplate u zavisnosti na strategije koje koristi drugi igrač

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

odnosno odredi se minimalna isplata za prvog igrača, pod uslovom da on primeni svoju i -tu čistu strategiju, onda se od ovih minimalnih isplata nađe takva strategija i=i 0 za koju će ova minimalna isplata biti maksimalna, tj.

Definicija. Broj b određen formulom (1.3) naziva se nižim neto troškom igre i pokazuje koliku minimalnu isplatu može sebi garantirati prvi igrač primjenom svojih čistih strategija za sve moguće akcije drugog igrača.

Drugi igrač, svojim optimalnim ponašanjem, treba da teži, ako je moguće, da minimizira isplatu prvog igrača nauštrb njegovih strategija. Dakle, za drugog igrača nalazimo

odnosno utvrđuje se maksimalna isplata prvog igrača, pod uslovom da drugi igrač primijeni svoju j-to čišćenje strategiju, onda drugi igrač pronalazi svoju j = j 1 strategiju za koju prvi igrač dobija minimalnu isplatu, tj.

Definicija. Broj β određen formulom (1.5) naziva se neto gornji trošak igre i pokazuje koliki maksimalni dobitak može sebi garantirati prvi igrač 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 osvoji više od c.

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

n = b = c (1.6)

Sedlo je par čistih strategija () prvog i drugog igrača, respektivno, pod kojima se postiže jednakost

Koncept sedla ima sledeće značenje: ako se jedan od igrača pridržava strategije koja odgovara tački sedla, onda drugi igrač ne može učiniti bolje nego da se pridržava strategije koja odgovara tački sedla. Imajući u vidu da najbolje ponašanje igrača ne bi trebalo da dovede do smanjenja njegove isplate, a najgore ponašanje može dovesti do smanjenja njegove isplate, ovi uslovi se mogu matematički zapisati u obliku sledećih relacija:

gdje su i, j bilo koje čiste strategije prvog i drugog igrača, respektivno; (i 0 , j 0) -- strategije koje formiraju sedlo. U nastavku ćemo pokazati da je definicija sedla ekvivalentna uslovima (1.8).

Dakle, na osnovu (1.8), element sedla je minimum u i 0 -tom redu i maksimum u j 0 -tom stupcu u matrici A. Pronalaženje sedla matrice A je lako: u matrici A, sukcesivno u svakom redu, pronađite minimalni element i provjerite da li je ovaj element maksimum u svojoj koloni. Ako je takav, onda je to sedlo, a par strategija koje mu odgovaraju formiraju sedlo. Par čistih strategija (i 0 , j 0) prvog i drugog igrača, koji formiraju sedlo i element sedla, naziva se rješenjem igre.

Čiste strategije i 0 i j 0 koje formiraju sedlo zovu se optimalne čiste strategije prvog i drugog igrača, respektivno.

Teorema 1. Neka je f (x, y) realna funkcija dvije varijable x A i y B i postoji

onda je b = c.

Dokaz. Iz definicije minimuma i maksimuma proizilazi da

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

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

Q.E.D.

Konkretno, matrica () je poseban slučaj funkcije f (x, y), tj. ako stavimo x = i, y = j, = f (x, y), onda iz teoreme 1 dobijamo da je niži neto cijena ne prelazi gornju neto vrijednost igre u matričnoj igri.

Definicija. Neka je f (x, y) realna funkcija dviju varijabli x A i y B. Tačka (x 0, y 0) se naziva sedlo 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 njene sedla u čistim strategijama. Ako matrična igra ima sedlo u čistim strategijama, tada pronalaženje ove tačke završava proučavanje igre. Ako u matričnoj igri nema sedla u čistim strategijama, tada možemo pronaći donju i gornju čistu cijenu ove igre, što ukazuje da se prvi igrač ne treba nadati isplati većoj od gornje cijene igre, a može biti siguran da će dobiti isplatu ne manju od niže cijene igre. Takve preporuke o ponašanju igrača u matričnoj igri bez sedla u čistim strategijama ne mogu zadovoljiti istraživače i praktičare. Poboljšanje u rješenju matričnih igara treba tražiti u korištenju tajnosti primjene čistih strategija i mogućnosti ponovnog ponavljanja igara u formi partija. Tako se, na primjer, igra niz partija šaha, dama, fudbala i svaki put igrači primjenjuju svoje strategije na način da njihovi protivnici nisu svjesni njihovog sadržaja, te usput ostvaruju određene isplate u prosjeku po igranje čitave serije igara. Ove isplate su u prosjeku veće od donje cijene igre i manje od gornje cijene igre. Što je veća ova prosječna vrijednost, to bolja strategija primijenjen od strane igrača. Stoga se pojavila ideja da se čiste strategije primjenjuju nasumično, sa određenom vjerovatnoćom. Time se u potpunosti osigurava tajnost njihove upotrebe. Svaki igrač može promijeniti vjerovatnoću primjene svojih čistih strategija na takav način da maksimizira svoju prosječnu isplatu i usput dobije optimalne strategije. Ova ideja je dovela do koncepta mješovite strategije.

Definicija. Mešovita strategija igrača je kompletan skup verovatnoća primene njegovih čistih strategija.

Dakle, ako prvi igrač ima m čistih strategija 1, 2, … i, … m, onda je njegova mješovita strategija x skup brojeva x = (x 1 , x 2 , ..., x i ,…, x t ) koji zadovoljava 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 zadovoljava 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. Zaista, ako u mješovitoj strategiji postoji i-ta mreža strategija se primenjuje sa verovatnoćom jedan, onda se sve ostale čiste strategije ne primenjuju. A ova i-ta čista strategija je poseban slučaj mješovite strategije. Da bi održao tajnost, svaki igrač primjenjuje svoje strategije bez obzira na izbor drugog igrača.

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

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

Očigledno, prosječna isplata prvog igrača je funkcija dva skupa varijabli x i y. Prvi igrač ima za cilj da maksimizira svoju prosječnu isplatu E (A, x, y) mijenjajući svoje mješovite strategije x, a drugi igrač nastoji da E (A, x, y) učini 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 Igra Red 22

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

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

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

Označiti sa x=(x 1 ,x 2), y=(y 1 ,y 2) mješovite strategije prvog i drugog igrača, respektivno. Podsjetimo da x 1 znači vjerojatnost da će prvi igrač koristiti svoju prvu strategiju, a x 2 = 1 - x 1 je vjerovatnoća korištenja njegove druge strategije. Slično za drugog igrača: 1 - vjerovatnoća korištenja prve strategije, y 2 = 1 - 1 - vjerovatnoća korištenja druge strategije.

Prema posledicama teoreme, za optimalnost mešovitih strategija x i y potrebno je i dovoljno da za nenegativne x 1 , x 2 , y 1 , y 2 važe sledeće relacije:

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

Zaista. Neka igra nema sedla 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 teoremi, y 1 = y 2 = 0, što je u suprotnosti sa uslovima (1.25).

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

Pretpostavimo sada da jedna od nejednačina (1.22) može biti stroga, na primjer, prva

To znači da je prema teoremi y 1 = 0, y 2 =1. Dakle, iz (1.23) dobijamo

Ako su obje nejednakosti (1.24) stroge, onda je po teoremi x1 = x2 = 0, što je u suprotnosti (1.25). Ali ako je a 12 a 22 , tada je jedna od nejednakosti (1.27) stroga, a druga je jednakost. Štaviše, jednakost će vrijediti za veći element od 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) также не может быть строгим.

Tako se pokazuje da ako matrična igra nema sedla u čistim strategijama, onda se nejednakosti (1.22) pretvaraju u jednakosti za optimalne strategije prvog igrača. Slični argumenti o nejednačinama (1.23) će dovesti do toga da u ovom slučaju nejednakosti (1.23) moraju biti jednakosti.

Dakle, ako matrična igra reda 22 nema sedlo, tada se optimalne mješovite strategije igrača i cijena igre mogu odrediti rješavanjem sistema jednačina (1.24). Također je utvrđeno da ako u matričnoj igri 2x2 jedan od igrača ima optimalnu čistu strategiju, onda i drugi igrač također 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 jednačina (1.24). Sistemsko rješenje (1.25)

1.4 Algebarska metoda

Postoje dva slučaja za rješavanje problema algebarskom metodom:

1. matrica ima sedlo;

2. matrica nema tačku sedla.

U prvom slučaju, rješenje je par strategija koje čine središnju točku 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

Istovremeno, na osnovu 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 vjerovatnoćom različitom od nule, 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:

Sistem jednačina sličan (2.5), (2.6) takođe se može sastaviti za optimalnu strategiju drugog igrača:

Uzimajući u obzir uslov normalizacije:

Rešimo jednačinu (1.37) - (1.41) zajedno u odnosu na nepoznanice, i to ne sve odjednom, već po tri: odvojeno (1.36), (1.38), (1.40) i (1.37), (1.39) , (1.41). Kao rezultat rješenja dobijamo:

1.5 Grafička metoda

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

Slika 1.1 - pronalaženje presjeka jedinične dužine

Odaberite dio jedinične dužine na osi apscise. Lijevi kraj će prikazati prvu strategiju prvog igrača, a desni kraj drugog. Sve međutačke odgovaraju mješovitim strategijama prvog igrača, a dužina segmenta desno od točke jednaka je vjerovatnoći korištenja prve strategije, a dužina segmenta lijevo je vjerovatnoća korištenja druga strategija od strane 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, na primjer, drugi igrač primijeni 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, njegova isplata će biti određena veličinom segmenta. Linija I-I odgovara primeni prve strategije od strane drugog igrača, nazvaćemo je prvom strategijom drugog igrača. Slično se može konstruirati i druga strategija drugog igrača. Tada će, općenito gledano, grafički prikaz matrice igre poprimiti 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 dužina segmenta jednaka vrijednosti igre V.

Linija 1N2 se naziva donjom isplatnom linijom. Ovdje se jasno vidi da tačka N odgovara maksimalnoj vrijednosti zagarantovane isplate prvog igrača.

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

ili na osi II-II

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

Slika 1.3 - definicija strategije drugog igrača

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

Ovisno o specifičnim vrijednostima koeficijenata, matrice grafa mogu imati i 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č n čistih strategija, tj. Matrica isplate za prvog igrača je:

Ako takva igra ima tačku sedla, onda je lako pronaći i dobiti rješenje.

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

Kako igra nema sedlo, nejednakost (1.54) se zamjenjuje nejednakostima

Za rješavanje sistema (1.56), (1.55), (1.53) svrsishodno je koristiti grafičku metodu. U tu svrhu uvodimo zapis za lijevu stranu nejednakosti (1.53)

matematički model matrične igre

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

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

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

Cilj drugog igrača je minimizirati isplatu prvog igrača odabirom njegovih strategija. Stoga računamo

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

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

Slika 1.6 - graf funkcije

Cilj prvog igrača je maksimizirati svoju isplatu kroz izbor, tj. izračunati

Na slici 1.6, tačka označava maksimalnu vrijednost koja se dobija. Cijena igre, jer:

Tako se grafički određuju optimalna mješovita strategija prvog igrača i par čistih strategija drugog igrača, koje formiraju tačku na sjecištu.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 sistem jednačina

i precizno odrediti vrijednosti i (grafički su određene približno). Zatim stavljajući sve vrijednosti na one j za koje ne čine tačku, rješavajući sistem jednačina (1.56) Za primjer prikazan na slici 1.6, ovo je sljedeći sistem:

a ostalo Ovaj sistem se može riješiti nagibom Ako, za neki j=j 0, strategije drugog igrača formiraju tačku M 0 i tada je maksimalna vrijednost donje granice skupova ograničenja predstavljena segmentom paralelnim sa osa U ovom slučaju, prvi igrač ima beskonačno mnogo optimalnih vrijednosti i cijene igre Ovaj slučaj je 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. Matrica isplate 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 vrijednost od 0 do 1 bude nacrtana duž horizontalne ose, vrijednost prosječne isplate) prvog igrača na vertikalnoj osi pod uslovima 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 predstaviti kao što je prikazano na slici 1.7.

Slika 1.7 - graf 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 da minimizira odabirom svoje strategije, tj. vrijednost odgovara

Na slici je vrijednost označena tačkom. Drugim riječima, definiraju se takve dvije strategije prvog igrača i vjerovatnoća za drugog igrača za koje se postiže jednakost

Sa slike vidimo da je cijena igre ordinata tačke, vjerovatnoća apscisa tačke. Za ostale čiste strategije prvog igrača u optimalnoj mješovitoj strategiji mora ().

Tako, rješavajući sistem (1.69), dobijamo optimalnu strategiju drugog igrača i vrijednost igre. Pronalazimo optimalnu mješovitu strategiju za prvog igrača rješavanjem sljedećeg sistema jednačina:

1.7 Matrična metoda za rješavanje igara

Oznake:

Bilo koja kvadratna podmatrica matrice reda

Matrica (1);

Matrix transponed to;

Matrica vezana za B;

- (1) matrica dobijena od X brisanjem elemenata koji odgovaraju redovima izbrisanim kada su primljeni;

- (1) matrica dobijena brisanjem elemenata koji odgovaraju redovima izbrisanim kada su primljeni.

algoritam:

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

2. Ako neki ili, onda odbacite pronađenu matricu i pokušajte drugu matricu.

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

Provjerava se da li su nejednakosti zadovoljene

za svaki (1.75)

i nejednakosti

za svaki (1.76)

Ako jedan od omjera nije zadovoljen, onda pokušavamo drugi. Ako su sve relacije važeće, onda X i željena rješenja.

1.8 Metoda uzastopne 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 tačnu vrijednost cijene igre i optimalne mješovite strategije. Tada možete koristiti približne metode za rješavanje matrične igre.

Hajde da opišemo jednu od ovih metoda - metodu uzastopne aproksimacije cene igre. Broj isplata izračunat ovom metodom raste približno proporcionalno broju redova i stupaca matrice isplata.

Suština metode je sljedeća: mentalno se igra mnogo puta, tj. sekvencijalno, u svakoj igrici igre, igrač bira strategiju koja mu daje najveću ukupnu (ukupnu) isplatu.

Nakon takve implementacije nekih igara, izračunava prosječnu vrijednost pobjede prvog igrača i gubitka drugog igrača, a njihova aritmetička sredina se uzima kao približna vrijednost cijene igre. Metoda omogućava da se pronađe približna vrijednost 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čan dobitak prvog igrača i prosječan 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. Uopšteno govoreći, aproksimacija vrijednosti iznad navedenih vrijednosti pravim vrijednostima je spora. Međutim, ovaj proces se može lako mehanizirati i na taj način pomoći da se dobije rješenje igre sa potrebnim stepenom tačnosti čak i sa isplatnim matricama relativno velikog reda.

2. Praktični dio

Par odlučuje gdje će prošetati i provesti vrijeme za dvoje.

Devojka odlučuje da ode u šetnju parkom da udahne svež vazduh, a uveče da pogleda film u najbližem bioskopu.

Momak se nudi da ode u tehnopark, nakon što pogleda utakmicu fudbalera lokalnog kluba na centralnom stadionu.

U skladu s tim, morate pronaći koliko dugo će se postići cilj jednog od igrača. Matrica isplate će izgledati ovako:

Tabela 1. Matrica isplate

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

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

2.2 Igranje 2xn i mx2

Problem 1(2xn)

Dva useva se uzgajaju za suvu i vlažnu klimu.

A stanje prirode može se smatrati: suvo, vlažno, umjereno.

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

Maksimalna vrijednost M() se postiže u tački M formiranoj presjekom pravih koje odgovaraju j=1, j"=2. Stoga pretpostavljamo: ,

Problem 2(mx2)

Momak i devojka razmatraju opcije gde da odu za vikend.

Izbor mesta za odmor može se predstaviti kao: park, bioskop, restoran.

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

Maksimalna vrijednost M() se postiže u tački E formiranoj presjekom pravih koje odgovaraju j=1, j"=2. Stoga pretpostavljamo: ,

Da biste odredili vrijednost v, morate riješiti sljedeće jednačine:

2.5 Matrična metoda

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

Centralni restoran uključuje sljedeće usluge:

1) skuplja i bolja usluga korisnicima;

2) jela su usmerena na francusku kuhinju;

Drugi restoran nudi:

1) nije skupa i kvalitetna usluga;

2) jelovnik kombinuje različite poznate svetske kuhinje;

3) takođe redovne promocije i popusti;

4) vrši dostavu i prima porudžbine za kućnu dostavu.

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

Tabela 2. Matrica isplate

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

Postoji šest podmatrica i:

Razmotrite matricu:

x 1 =? 0,x2=? 0

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

Razmotrite sada matricu:

x 1 =? 0,x2=? 0

Cijena igre.

Ovaj omjer je u suprotnosti sa zahtjevom, tako da nije prikladan.

Razmotrite sada matricu:

x 1 = , x 2 = ? 0,

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

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

Razmotrite sada matricu:

x 1 =, x 2 = 0, budući da je x 2 = 0, onda odbacujemo i.

Razmotrite sada matricu:

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

Razmotrite sada matricu:

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

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

Cijena igre.

Sada se provjeravaju glavni odnosi:

Hostirano 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 određenog preduzeća, sindikat pregovara sa svojim rukovodstvom o organizaciji toplog obroka o trošku preduzeća. Sindikat koji zastupa interese radnika osigurava da obrok bude što kvalitetniji, a samim tim i skuplji. Uprava kompanije ima suprotstavljene interese. Na kraju, strane su se složile oko sledećeg. Sindikat (igrač 1) bira jednu od tri firme (A 1 , A 2 , A 3) za snabdevanje toplim jelima, a menadžment kompanije (igrač 2) bira set jela od tri moguće opcije (B 1, B 2, B 3) . Nakon potpisivanja sporazuma, sindikat formira sljedeću matricu plaćanja čiji elementi predstavljaju cijenu kompleta posuđa:

Neka je igra data sljedećom matricom isplate:

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

2 ako koristi svoju prvu strategiju,

3 ako koristi svoju 3. strategiju.

Dobijene vrijednosti su sumirane u tabeli 1.

Tabela 3. Strategija drugog igrača

Tabela 3 pokazuje da će sa 2. strategijom drugog igrača, prvi igrač dobiti najveću isplatu 3 koristeći svoju 2. ili 3. strategiju. Pošto prvi igrač želi da dobije maksimalnu isplatu, on na 2. strategiju drugog igrača odgovara svojom 2. strategijom. Sa 2. strategijom prvog igrača, drugi će izgubiti:

1 ako primijeni svoju prvu strategiju,

3 ako koristi svoju 2. strategiju,

4 ako koristi svoju 3. strategiju.

Tabela 4. Strategija prvog igrača

Tabela 2 pokazuje da će s 2. strategijom prvog igrača, drugi igrač imati najmanji gubitak 1 ako primijeni svoju 1. strategiju. Pošto drugi igrač želi manje izgubiti, onda će kao odgovor na 2. strategiju prvog igrača primijeniti svoju 1. strategiju. Dobijeni rezultati su sažeti u tabeli 5.

Tabela 5. Strategije prvog i drugog igrača

U tabeli. 5 u koloni 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 koloni i najveća je prosječna isplata 3 prvog igrača, koju je primio u prvoj utakmici; kolona w sadrži najmanji prosječni gubitak 1 koji je drugi igrač primio u prvoj igri; kolona v sadrži aritmetičku sredinu v = (u + w) -- odnosno približnu vrijednost cijene igre, dobijenu kao rezultat igranja jedne igre igre. Ako drugi igrač koristi svoju 1. strategiju, tada će prvi igrač dobiti 3, 1, 2, redom, sa svojim 1., 2., 3. strategijama, a ukupna isplata prvog igrača za obje igre će biti:

2 + 3=5 sa njegovom prvom strategijom,

3 + 1=4 sa svojom 2. strategijom,

3 + 2=5 sa njegovom 3. strategijom.

Ovi ukupni dobici se bilježe u drugom redu tabele. 3 i u kolonama koje odgovaraju strategijama prvog igrača: 1, 2, 3.

Od svih ukupnih isplata, najveća je 5. Dobiva se sa 1. i 3. strategijom prvog igrača, tada on može izabrati bilo koju od njih; recimo, u slučajevima kada postoje dva (ili više) identičnih ukupnih isplata, bira se strategija sa najmanjim brojem (u našem slučaju treba uzeti 1. strategiju).

Sa 1. strategijom prvog igrača, drugi igrač će izgubiti 3, 2, 3, respektivno, od svoje 1., 2., 3. strategije, a ukupan gubitak drugog igrača za obje igre će biti:

1 + 3=4 sa svojom prvom strategijom,

3 + 2=5 sa njegovom 2. strategijom,

4 + 3=7 sa njegovom 3. strategijom.

Ovi ukupni gubici su evidentirani u drugom redu tabele. 5 i u kolonama koje odgovaraju 1., 2., 3. strategijama drugog igrača.

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

Tako se dobija sledeća tabela 4, za dva seta igre.

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

U trećem redu tabele 6, u koloni strategije drugog igrača, nalazi se broj 1, koji 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, respektivno, a njegova ukupna isplata za tri igre će biti:

3 + 5 = 8 u njegovoj prvoj strategiji,

1 +4 = 5 sa svojom 2. strategijom,

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

Ove ukupne isplate prvog igrača se bilježe u trećem redu tabele 6 i kolonama koje odgovaraju njegovim strategijama 1, 2, 3. Budući da se najveća ukupna isplata 8 prvog igrača dobije s 1. strategijom, on u skladu s tim bira 1. .

Sa 1. strategijom prvog igrača, drugi igrač će izgubiti 3, 1, 2, respektivno, od 1., 2., 3. strategije, a ukupan gubitak drugog igrača za obje igre će biti:

3 + 4=7 sa njegovom prvom strategijom,

2 + 5=7 sa njegovom 2. strategijom,

3 + 7=10 sa njegovom 3. strategijom.

Ovi ukupni gubici su evidentirani u trećem redu tabele. 6 i u kolonama koje odgovaraju 1., 2., 3. strategijama drugog igrača. Od svih njegovih ukupnih gubitaka, 7 je najmanji i dobije se njegovom 1. i 2. strategijom, tada drugi igrač mora primijeniti svoju 1. strategiju.

U tabeli. 6 u trećem redu u koloni i najveći ukupni dobitak prvog igrača u tri igre, podijeljen sa brojem igre, tj. kolona w sadrži najmanji ukupan gubitak drugog igrača u tri utakmice, podijeljen sa brojem partija, tj. u kolonu v stavite njihovu aritmetičku sredinu

Tako dobijamo tabelu. 7 za tri strane.

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

Tabela 8. Finalni sto sa dvadeset odigranih utakmica

Iz tabele. 7 i 8, može se vidjeti da se u 20 izgubljenih partija strategije 1, 2, 3 za prvog igrača javljaju 12, 3, 5 puta, dakle, njihove relativne frekvencije su respektivno jednake; strategije 1, 2, 3 za drugog igrača se javljaju 7, 11,2 puta, pa su njihove relativne frekvencije respektivno jednake; približnu vrijednost cijene igre. Ova aproksimacija je dovoljno dobra.

U zaključku, napominjemo da ako igra ima više od jednog rješenja, tada će se približne vrijednosti cijene igre i dalje približavati stvarnoj cijeni igre na neodređeno vrijeme, a relativne frekvencije pojavljivanja strategija igrači se više neće nužno približavati pravim optimalnim mješovitim strategijama igrača.

Analiza rezultata

U ovom predmetnom radu proučava se materijal za pronalaženje rješenja za antagonističke igre grafičkom, matričnom metodom, metodom uzastopne aproksimacije cijene igre. Pronađene su optimalne strategije prvog i drugog igrača, kao i cijena igre u igrama 2x2, 2xn i mx2, kao i u 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č zajedno provesti 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 njivu 50 puta 50, a cijena igre je bila 3,75 miliona 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 će biti 4,3 rublja.

Modeliran je zadatak za matričnu metodu u kojoj su razmatrana dva restorana, a rješenje problema je pokazalo da će primjenom njegove optimalne mješovite strategije profit prvog restorana iznositi 15,6 miliona rubalja, a kada se koristi njegova optimalna mješovita strategija od drugi restoran, neće dozvoliti prvom da zaradi više od 15,6 miliona rubalja. Rešenje grafičkom metodom dalo je grešku i cena igre je bila 14,9 miliona rubalja.

Za Brown metodu sastavljen je zadatak u kojem se razmatraju sindikat i menadžment kompanije, njihov zadatak je da obezbijede hranu za radnike. Kada oba igrača koriste svoje optimalne strategije, hrana po osobi će biti 2,45 hiljada rubalja.

Spisak korištenih izvora

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

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

3) Cherchmen U., Akof R., Arnof L., Uvod u istraživanje operacija. - M.: Nauka. 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

Hostirano na Allbest.ru

Slični dokumenti

Donošenje odluka kao posebna vrsta ljudske aktivnosti. Racionalno predstavljanje matrice igre. Primjeri matričnih igara u čistim i mješovitim strategijama. Istraživanje operacija: odnos problema linearnog programiranja s modelom teorijske igre.

seminarski rad, dodan 05.05.2010


Igre koje se ponavljaju mnogo puta, njihova karakteristična svojstva i faze. Mješovite strategije, uslovi i mogućnosti za njihovu primjenu u praksi. Analitička metoda za rješavanje igre 2 x 2. Osnovne teoreme za pravokutne igre. Algebarska rješenja.

prezentacija, dodano 23.10.2013


Osnovne definicije teorije bimatričnih igara. Primjer bimatrične igre "Učenik-nastavnik". 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. Poziciona 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. Iterativni Brown-Robinsonov metod. Monotoni iterativni algoritam za rješavanje matričnih igara.

teza, dodana 08.08.2007


Sastavljanje matrice isplate, traženje donje i gornje neto cijene igre, maksiminske i minimaksne strategije igrača. Pojednostavljenje matrice plaćanja. Rješavanje matrične igre korištenjem redukcije na problem linearnog programiranja i dodatka "Traži rješenje".

test, dodano 10.11.2014


Teorija igara je matematička teorija konfliktnih situacija. Razvoj matematičkog modela igre sa nultom sumom 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


Osnovne informacije o simpleks metodi, evaluacija njene uloge i značaja u linearnom programiranju. Geometrijska interpretacija i algebarsko značenje. Pronalaženje maksimuma i minimuma linearne funkcije, posebni slučajevi. Rješenje zadatka matričnim simpleks metodom.

teze, dodato 01.06.2015


Tehnike konstruisanja matematičkih modela računarskih sistema koji odražavaju strukturu i procese njihovog funkcionisanja. Broj pristupa fajlu tokom prosečnog zadatka. Određivanje mogućnosti postavljanja datoteka u eksterne memorijske diskove.

laboratorijski rad, dodano 21.06.2013


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

Teorija igara je teorija matematičkih modela donošenja odluka u uslovima konflikta ili neizvjesnosti. Pretpostavlja se da akcije strana u igri karakterišu određene strategije – skupovi akcionih pravila. Ako dobitak jedne strane neminovno vodi gubitku druge strane, onda govore o antagonističkim igrama. Ako je skup strategija ograničen, onda se igra naziva matrična igra 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 matrica isplate igrača 2 u potpunosti određena matricom isplate igrača 1 (odgovarajući elementi ove dvije matrice razlikuju se samo po predznacima). Stoga je bimatrična antagonistička igra u potpunosti opisana jednom matricom (matrica isplate igrača 1) i, shodno tome, naziva se matrična igra.

Ova igra je antagonistička. U njemu j = x2 - O, P i R (O, O] \u003d 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 od svojih igara sadrži zrcalnu izomorfnu igru ​​(pošto su sve igre koje su zrcalno izomorfne datoj su jedna drugoj izomorfne, u skladu sa ovim što je rečeno, možemo govoriti o jednoj zrcalnoj izomorfnoj igri). Takva klasa je, na primjer, klasa svih antagonističkih igara ili klasa svih matričnih igara.

Podsjećajući na definiciju 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 je za bilo koji x G x nejednakost

Proces pretvaranja igara u simetrične naziva se simetrija. Ovdje opisujemo jednu metodu simetrizacije. Druga, fundamentalno drugačija verzija simetrizacije biće data u odeljku 26.7. Obje ove varijante simetrizacije su zapravo primjenjive na proizvoljne antagonističke igre, ali će biti formulisane i dokazane samo za matrične igre.

Dakle, početni termini i oznake teorije opštih antagonističkih igara poklapaju se sa odgovarajućim terminima 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 poenta je bila uspostaviti njihovu jednakost, ili barem pronaći načine za prevazilaženje njihove nejednakosti.

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

Ali svaka konačna (matrična) igra može se proširiti na beskonačnu igru, na primjer, pružanjem svakom igraču bilo kojim brojem dominiranih strategija (vidi 22. poglavlje 1). Očigledno, 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 trebalo da se razlikuje od ponašanja u originalnoj igri. Tako smo odmah dobili dovoljan broj primjera beskonačnih antagonističkih igara koje nemaju sedla. Ima i takvih primjera.

Dakle, da bi se princip maksimina implementirao u beskonačnoj antagonističkoj igri, potrebno je, kao u slučaju konačne (matrične) igre, određeno proširenje strateških sposobnosti igrača. Za 96

Kao iu slučaju matričnih igara (vidi pogl. 1, 17), za opšte antagonističke igre važnu ulogu igra koncept mešovitog strateškog spektra, koji se ovde, međutim, mora dati opštijom definicijom.

Konačno, imajte na umu 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 sa konačnim, matrične igre imaju ravnotežne situacije ne u originalnim, čistim strategijama, već samo u generaliziranim, mješovitim strategijama. Stoga je za opšte, neantagonističke, nekooperativne igre prirodno tražiti ravnotežne situacije upravo u mješovitim strategijama.

Tako, na primjer (vidi Sliku 3.1), već smo primijetili da "Izvođač" gotovo nikada ne mora da se bavi nesigurnošću ponašanja. Ali ako uzmemo konceptualni nivo tipa "Administrator", onda je sve upravo suprotno. U pravilu, glavna vrsta neizvjesnosti sa kojom se takav "naš donosilac odluka" mora suočiti je "konflikt". Sada možemo razjasniti da je to obično rivalstvo koje nije strogo. Nešto rjeđe "Administrator" donosi odluke u uslovima "prirodne neizvjesnosti", a još rjeđe se susreće sa strogim, antagonističkim sukobom. Osim toga, sukob interesa pri donošenju odluka od strane "Administratora" se dešava, da tako kažem, "jednom", tj. u našoj klasifikaciji često igra samo jednu (ponekad vrlo mali broj) partija igre. Skale za procjenu posljedica su češće kvalitativne nego kvantitativne. Strateška nezavisnost "Administratora" je prilično 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-matrix 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 strategija koje su odabrali. Matrična antagonistička igra za koju max min fiv = min max Aiy>

Međutim, nisu sve matrične antagonističke igre sasvim određene, iu opštem slučaju

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

Kako se definira matrična antagonistička igra dvije osobe?

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

U slučaju igre dvije osobe, prirodno je smatrati da su njihovi interesi direktno suprotni – igra je antagonistička. Dakle, isplata jednog igrača jednaka je gubitku drugog (zbir isplata oba igrača je nula, otuda i naziv, igra sa nultom sumom). Razmotrit ćemo igre u kojima svaki igrač ima konačan broj alternativa. Funkcija isplate za takvu igru ​​sa nultom sumom za dvije osobe može se dati u matričnom obliku (u obliku matrice isplate).

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

MATRIX IGRE - klasa antagonističkih igara u kojima učestvuju dva igrača, a svaki igrač ima konačan broj strategija. Ako jedan igrač ima m strategija, a drugi igrač ima n strategija, onda možemo konstruirati matricu igre dimenzije txn. M.i. može ili ne mora imati sedlo. U potonjem slučaju

Razmotrimo igru ​​u paru s konačnim nultom sumom. Označiti sa a isplata igrača A, i kroz b- pobjeda igrača B. Jer a = –b, onda prilikom analize takve igre nema potrebe uzimati u obzir oba ova broja - dovoljno je uzeti u obzir isplatu jednog od igrača. Neka bude npr. A. U nastavku, radi lakšeg predstavljanja, strana A uslovno ćemo imenovati " mi"i sa strane B – "neprijatelja".

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 izabrala određenu strategiju: mi smo izabrali Ai, protivnik B j. Ako se igra sastoji samo od ličnih poteza, onda je izbor strategija Ai i B j jedinstveno određuje ishod igre - našu isplatu (pozitivnu ili negativnu). Označimo ovaj dobitak kao aij(pobjeda kada odaberemo strategiju Ai, a neprijatelj - strategije B j).

Ako igra sadrži, pored ličnih nasumičnih poteza, onda isplatu za par strategija Ai, B j je slučajna varijabla koja ovisi o ishodima svih nasumičnih poteza. U ovom slučaju, prirodna procjena očekivane isplate je matematičko očekivanje nasumične pobjede. Radi praktičnosti, označićemo sa aij i samu isplatu (u igri bez nasumičnih poteza) i njeno matematičko očekivanje (u igri sa nasumičnim potezima).

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

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

Imajte na umu da izgradnja matrice isplate za igre sa 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 principu se svaka konačna igra može svesti na matrični oblik.

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

Koju strategiju trebamo (tj. igrač A) koristiti? Koju god strategiju da odaberemo, razuman protivnik će na nju odgovoriti strategijom za koju će naša isplata biti minimalna. Na primjer, ako odaberemo strategiju A 3 (iskušana pobjedom od 10), protivnik će odabrati strategiju kao odgovor B 1 , a naša isplata će biti samo 1. Očigledno, na osnovu principa opreza (a to je glavni princip teorije igara), moramo izabrati strategiju u kojoj naš minimalni dobitak je maksimalan.

Označiti sa a i minimalna isplativost za strategiju Ai:

i dodajte kolonu koja sadrži ove vrijednosti u matricu igre:

Prilikom odabira strategije moramo odabrati onu za koju je vrijednost a i maksimum. Označimo ovu maksimalnu vrijednost sa α :

Vrijednost α pozvao niža cijena igre ili maximin(maksimalni minimalni dobitak). Strategija igrača A odgovara maksiminu α , zove se maksiminska strategija.

U ovom primjeru, maksimin α jednaka je 3 (odgovarajuća ćelija u tabeli je označena sivom bojom), a maksiminska strategija je Ačetiri . Odabravši ovu strategiju, možemo biti sigurni da ćemo za svako ponašanje neprijatelja dobiti ne manje od 3 (a možda i više uz „nerazumno“ ponašanje neprijatelja).Ova vrijednost je naš zagarantovani minimum koji možemo osigurati za sebe, pridržavajući se najopreznije („reosiguranja“) strategije.

Sada ćemo sprovesti slično rezonovanje za neprijatelja B B A B 2 - odgovorićemo mu A .

Označiti sa βj A B) za strategiju Ai:

βj β :

7. KOJA JE IGRA GORNJE VRIJEDNOSTI Sada ćemo sprovesti slično rezonovanje za protivnika B. On je zainteresovan da minimizira naš dobitak, odnosno da nam da manje, ali mora da računa na naše ponašanje, koje je za njega najgore. Na primjer, ako odabere strategiju B 1, onda ćemo mu odgovoriti strategijom A 3, a on će nam dati 10. Ako želi B 2 - odgovorićemo mu A 2 , a on će dati 8 itd. Očigledno, oprezan protivnik mora izabrati strategiju u kojoj naš maksimalni dobitak će biti minimalan.

Označiti sa βj maksimalne vrijednosti u stupcima matrice isplate (maksimalna isplata igrača A, ili, što je isto, igračev maksimalni gubitak B) za strategiju Ai:

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

Odabirom strategije, neprijatelj će preferirati onu za koju vrijedi βj minimum. Označimo ga sa β :

Vrijednost β pozvao vrhunska cijena igre ili minimax(minimalni maksimalni dobitak). Protivnikova (igračeva) strategija koja odgovara minimaksu B), se zove minimax strategija.

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

Dakle, na osnovu principa opreza ("uvijek očekuj najgore!"), moramo odabrati strategiju A 4, a neprijatelj - strategija B 3 . Princip opreza je fundamentalan u teoriji igara i zove se princip minimaksa.

Razmislite primjer 2. Pustite igrače A i AT jedan od tri broja piše se istovremeno i nezavisno jedan od drugog: ili "1", ili "2", ili "3". Ako je zbir napisanih brojeva paran, tada je igrač B plaća igraču A ovaj iznos. Ako je iznos neparan, igrač plaća ovaj iznos A igrač AT.

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

Player A moraju se pridržavati maksiminske strategije A 1 osvojiti najmanje -3 (tj. izgubiti najviše 3). Minimax Player strategija B bilo koju od strategija B 1 i B 2, što garantuje da neće dati više od 4.

Dobit ćemo isti rezultat ako zapišemo matricu isplate sa stanovišta igrača AT. Zapravo, ova matrica se dobija transponovanjem matrice konstruisane sa tačke gledišta igrača A, i mijenjanje znakova elemenata u suprotno (od isplate igrača A je gubitak igrača AT):

Na osnovu ove matrice proizilazi da je igrač B mora 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 onaj koji smo dobili gore, tako da analiza nije bitna sa gledišta kojeg igrača ćemo je provesti.

8 ŠTA JE VRIJEDNA IGRA.

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

Razmotrimo matričnu igru ​​tipa sa matricom isplate

Ako igrač ALIće izabrati strategiju A i, tada će sve njegove moguće isplate biti elementi i-ti red matrice OD. Najgore za igrača ALI slučaju kada igrač AT primjenjuje strategiju prikladnu za minimum element ove linije, igračeva isplata ALI biće jednak broju.

Stoga, kako bi se dobila maksimalna isplata, igrač ALI potrebno je da odaberete jednu od strategija za koju je broj maksimum.

Najjednostavniji slučaj, detaljno razrađen u teoriji igara, je igra konačnih parova sa nultom sumom (antagonistička igra dvije osobe ili dvije koalicije). Zamislimo igru ​​G u kojoj učestvuju dva igrača A i B, koji imaju suprotne interese: dobitak jednog jednak je gubitku drugog. Pošto je isplata igrača A jednaka isplati igrača B sa suprotnim predznakom, nas može zanimati samo isplata igrača a. Naravno, A želi da maksimizira, a B želi da minimizira a.

Radi jednostavnosti, hajde da se mentalno identifikujemo sa jednim od igrača (neka bude A) i nazovemo ga "mi", a igrača B - "protivnik" (naravno, iz ovoga ne proizilaze nikakve stvarne prednosti za A). Neka imamo moguće strategije, a protivnika - moguće strategije (takva igra se zove igra). Označimo našu isplatu ako mi koristimo strategiju, a protivnik strategiju

Tabela 26.1

Pretpostavimo da nam je za svaki par strategija isplata (ili prosječna isplata) a poznata. Tada je, u principu, moguće sastaviti pravougaonu tabelu (matricu), koja navodi strategije igrača i odgovarajuće isplate (vidi tabelu 26.1).

Ako se sastavi takva tabela, onda se kaže da je igra G svedena na matrični oblik (sama 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 se igra svede na matričnu formu, onda se igra s više poteza zapravo svodi na igru ​​s jednim potezom - od igrača se traži da napravi samo jedan potez: odabere strategiju. Ukratko ćemo označiti matricu igre

Razmotrimo primjer igre G (4X5) u matričnom obliku. Na raspolaganju nam (da biramo) četiri strategije, neprijatelj ima pet strategija. Matrica igre je data u tabeli 26.2

Hajde da razmislimo koju strategiju koristimo (igrač A)? Matrica 26.2 ima primamljivu isplatu "10"; privučeni smo da izaberemo strategiju u kojoj ćemo dobiti ovaj „slatki komad“.

Ali čekajte, ni neprijatelj nije glup! Ako mi izaberemo strategiju, on će, u inat, izabrati strategiju, a mi ćemo dobiti mizernu isplatu "1". Ne, ne možete birati strategiju! Kako biti? Očigledno, polazeći od principa opreza (a to je glavni princip teorije igara), moramo izabrati strategiju za koju je naš minimalni dobitak maksimalan.

Tabela 26.2

To je takozvani “mini-max princip”: ponašajte se tako da uz najgore ponašanje protivnika dobijete maksimalan dobitak.

Prepišimo tabelu 26.2 iu desnu dodatnu kolonu upisaćemo minimalnu vrijednost dobitka u svakom redu (minimum reda); označimo ga za red a (vidi tabelu 26.3).

Tabela 26.3

Od svih vrijednosti (desni stupac) odabire se najveća (3). To odgovara strategiji. Odabravši ovu strategiju, u svakom slučaju možemo biti sigurni da ćemo (za svako ponašanje neprijatelja) dobiti ne manje od 3. Ova vrijednost je naš zagarantovani 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 minimalnih isplata). Označićemo ga kao a. U našem slučaju

Hajde sada da zauzmemo tačku gledišta neprijatelja i da se založimo za njega. On nije nekakav pion, ali i razuman! Birajući strategiju, želio bi dati manje, ali mora računati na naše ponašanje, koje je za njega najgore. Ako izabere strategiju, mi ćemo mu odgovoriti i on će dati 10; ako izabere, mi ćemo mu odgovoriti i on će to vratiti itd. Dodajemo dodatni donji red u tabelu 26.3 i upisujemo maksimume kolona u nju.Očigledno, oprezan protivnik mora izabrati strategiju za koju je ova vrijednost minimalna (odgovarajuća vrijednost 5 je istaknuta u tabeli 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 maksimalnog dobitka). U našem primjeru, a postiže se i protivničkom strategijom

Dakle, na osnovu principa opreza (pravilo reosiguranja „uvek računaj na najgore!“) moramo izabrati strategiju A, a neprijatelja – strategiju. Takve strategije se nazivaju „minimaks“ (sledeći iz principa minimaks). Sve dok se obje strane u našem primjeru drže svojih minimaks strategija, isplata će biti

Sada zamislite na trenutak da smo saznali 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, neprijatelj takođe nije promašaj; neka zna da je naša strategija , on će također požuriti da izabere , smanjivši nam isplatu na 2 itd. (partneri su se „jurili oko strategija“). Ukratko, minimaks strategije u našem primjeru su nestabilne u odnosu na informacije o ponašanju druge strane; ove strategije nemaju svojstvo ravnoteže.

Je li uvijek ovako? Ne, ne uvek. Razmotrimo primjer sa matricom datom u tabeli 26.4.

U ovom primjeru, donja cijena igre jednaka je gornjoj: . Šta 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 šta će se desiti ako (A) saznamo da se protivnik (B) drži strategije B?

Tabela 26.4

I baš se ništa neće promijeniti, jer svako odstupanje od strategije može samo pogoršati našu situaciju. Jednako tako, informacije koje primi protivnik ga neće natjerati da se povuče od svoje strategije. Znak prisustva sedla 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, ) kojima se ovaj dobitak postiže nazivaju se optimalnim čistim strategijama, a njihova kombinacija je rješenje za igru. U ovom slučaju se kaže da se sama igra rješava 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, e, ovo su uslovi igre: oni su korisni za A, a štetni za B.

Čitalac može imati pitanje: zašto se optimalne strategije nazivaju „čiste“? 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, nasumično ih izmjenjujući. Dakle, ako priznamo, pored čistih, i mešovite strategije, svaka konačna igra ima rešenje – tačku ravnoteže. Ali više o ovome tek dolazi.

Prisustvo sedla u igri daleko je od pravila, već je izuzetak. Većina igara nema sedlo. Međutim, postoji niz igara koje uvijek imaju sedlo i stoga se rješavaju čistim strategijama. To su takozvane "igre sa potpunim informacijama". Igra sa potpunim informacijama je igra u kojoj svaki igrač pri svakom ličnom potezu zna čitavu predistoriju svog razvoja, odnosno rezultate svih prethodnih poteza, ličnih i slučajnih. Primjeri igara s potpunim informacijama su dame, šah, tik-tak-toe itd.

U teoriji igara je dokazano da svaka igra sa kompletnom informacijom ima sedlo, pa se stoga može riješiti č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 ličnih poteza, onda kada svaki igrač primijeni sopstvenu 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 potpunim informacijama: dva igrača naizmjenično stavljaju novčiće na okrugli sto, birajući proizvoljno poziciju centra novčića (međusobno preklapanje novčića nije dozvoljeno). Pobjednik je onaj koji uloži zadnji peni (kada nema mjesta za druge). Lako je vidjeti da je ishod ove utakmice u suštini unaprijed gotov zaključak. Postoji određena strategija koja osigurava da igrač koji prvi stavi novčić pobjeđuje.

Naime, on mora prvi put staviti novčić u centar tabele, a zatim na svaki potez protivnika odgovoriti simetričnim potezom. Očigledno, kako god se protivnik ponašao, ne može izbjeći poraz. Potpuno ista situacija je i sa šahom i partijama sa potpunim informacijama uopšte: ​​bilo koja od njih, napisana u matričnom obliku, ima sedlo, pa je rešenje u čistim strategijama, i stoga ima smisla samo dok to rešenje ima nije pronađeno. Recimo šahovska igra ili se uvek završi pobedom belih, ili uvek završi pobedom crnih, ili se uvek završi nerešeno, ali šta tačno - još ne znamo (na sreću ljubitelja šaha). Dodajmo još nešto: teško da ćemo znati u dogledno vrijeme, jer je broj strategija toliko ogroman da je izuzetno teško (ako ne i nemoguće) igru ​​svesti na matrični oblik i u njoj pronaći sedlo.

A sada se zapitajmo šta da radimo ako igra nema tačku sedla: Pa, ako je svaki igrač primoran da izabere jednu čistu strategiju, onda nema šta da radimo: moramo se rukovoditi principom minimaksa. Druga stvar je ako možete da "pomiješate" svoje strategije, nasumično ih izmjenjujte s određenim vjerovatnoćama. Upotreba mješovitih strategija je zamišljena na ovaj način: igra se ponavlja mnogo puta; prije svake partije u igri, kada igrač dobije lični potez, "povjerava" svoj izbor slučaju, "baca ždrijeb" i uzima strategiju koja je ispala (već znamo kako organizirati žrijeb iz prethodnog poglavlja ).

Mješovite strategije u teoriji igara su model promjenjive, fleksibilne taktike, kada niko 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. Napominjemo istovremeno da je najbolji način da sakrijete svoje ponašanje od neprijatelja da mu date nasumičan karakter i, prema tome, da ne znate unaprijed šta ćete učiniti.

Dakle, hajde da pričamo o mešovitim strategijama. Mi ćemo označiti mješovite strategije igrača A i B, respektivno

U konkretnom slučaju, kada su sve vjerovatnoće, osim jedne, jednake nuli, a ova jednaka jedan, mješovita strategija se pretvara u čistu.

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

Par optimalnih strategija koje formiraju rješenje igre ima sljedeće svojstvo: ako se jedan od igrača pridržava svoje optimalne strategije, onda drugome ne može biti isplativo da odstupi od njegove. Ovaj par strategija čini neku vrstu ravnoteže u igri: jedan igrač želi da isplatu okrene na maksimum, drugi - na minimum, svaki vuče u svom smjeru i, uz razumno ponašanje oba, ravnotežu i uspostavljena je stabilna isplata v. Ako je onda igra od koristi za nas, ako - za neprijatelja; kada je igra "fer", podjednako korisna za oba učesnika.

Razmotrite primjer igre bez sedla i navedite (bez dokaza) njeno rješenje. Igra je sledeća: dva igrača A i B istovremeno i bez reči pokazuju jedan, dva ili tri prsta. O dobitku odlučuje ukupan broj prstiju: ako je paran, A pobjeđuje i prima od B iznos jednak ovom broju; ako je neparan, onda, naprotiv, A plaća B iznos jednak ovom broju. Šta bi igrači trebali učiniti?

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

Niža cijena igre je u skladu sa strategijom.To znači da razumnim, opreznim ponašanjem garantujemo da nećemo izgubiti više od 3. Mala utjeha, ali ipak bolja od, recimo, pobjede - 5, nalazi se u nekim ćelije matriksa. Loše je za nas, igraču L... Ali da se tješimo: pozicija protivnika izgleda još gora: niža cijena igre. razumnog ponašanja, on će nam dati minimalno 4.