Igre sa sedlom u čistim strategijama. Klasifikacija igara

Igre se mogu klasificirati prema broju igrača, broju strategija, prirodi interakcije između igrača, prirodi pobjede, broju poteza, stanju informacija itd.

U zavisnosti od broja igrača, igre se dijele na dva i n igrači. Prvi od njih su najviše proučavani. Igre tri ili više igrača su manje proučavane zbog fundamentalnih poteškoća i tehničkih mogućnosti dobivanja rješenja. Što više igrača ima više problema.

Na osnovu broja strategija, igre se dijele na konačne i beskonačne. Ako svi igrači u igri imaju konačan broj mogućih strategija, onda se ona zove krajnji. Ako barem jedan od igrača ima beskonačan broj mogućih strategija, igra se poziva beskrajno.

Na osnovu prirode interakcije, igre se dijele na:

nekoaliciona: igrači nemaju pravo sklapati dogovore ili koalicije;

koalicija(zadruga) – može se pridružiti koalicijama.

U kooperativnim igrama koalicije su unaprijed određene.

Prema prirodi dobitaka, igre se dijele na: igre sa nula suma(ukupni kapital svih igrača se ne mijenja, već se redistribuira između igrača; zbir dobitaka svih igrača je nula) i igre sa zbir različit od nule.

Na osnovu vrste pobjedničkih funkcija igre se dijele na: matrične, bimatrične, kontinuirane, konveksne, odvojive, dvobojne itd.

Definicija . Ako je u igri s matricom A = (donja neto cijena jednaka gornjoj neto cijeni), onda se kaže da ova igra ima sedlo tačka V čiste strategije I neto cijena igre==.

Saddle point je par čistih strategija (i O , j O ) respektivno, igrači 1 i 2, pri čemu se postiže jednakost =. 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. Matematički, ovo se može napisati na drugi način: , Gdje i, j– sve čiste strategije igrača 1 i 2, respektivno; (i O , j O ) – strategije koje formiraju sedlo.

Dakle, element sedla je minimum u io-tom redu i maksimum u j-tom stupcu u matrici A. Pronalaženje sedla matrice A se dešava na sledeći način: u matrici A sekvencijalno u svakoj linija pronađite minimalni element i provjerite da li je ovaj element maksimalni u svom kolona. Ako je odgovor da, onda je to element sedla, a par strategija koje mu odgovaraju formiraju sedlo. Par čistih strategija (i O , j O ) igrači 1 i 2, koji formiraju sedlo i sedlasti element se poziva rešenje igre . Gde i O I j O su pozvani optimalno čišćenje strategije igrači 1 i 2.

Svojstva sedla:

1. Ekvivalencija. Ako u igri postoji nekoliko točaka sedla, tada su vrijednosti funkcije isplate u njima iste.

2. Zamjenjivost optimalnih strategija. Igrači mogu zamijeniti svoje optimalne strategije drugim optimalnim strategijama, pri čemu se ravnoteža neće poremetiti, a dobitak (gubitak) će ostati nepromijenjen.

13. Definicija mješovite strategije. Rješenje igre 2*2 u mješovitim strategijama.

Mješovita strategija je kada, umjesto primjene bilo koje specifične strategije, učesnici u igri mogu nasumično mijenjati (miješati) svoje strategije u skladu sa posebno dizajniranom šemom koja obezbjeđuje željenu učestalost, ili vjerovatnoću, implementacije svakog od strategije.

Za svakog igrača možete postaviti sljedeće komponente:

Pia – vjerovatnoća korištenja i-te strategije od strane A.

Ako odaberete takav set Pia , koji obezbeđuje najveća pobeda bez obzira na akcije druge strane, tada će se ovaj skup vjerovatnoća (p 1 a, p 2 a, ..., p ma) = S A i zvati mješovita strategija.

S * A = (p * 1 a, p * 2 a, …, p * ma) – optimalna mješovita strategija.

( S A ) – skup mešovitih strategija na strani A, od kojih se mora izabrati optimalna.

Igra 2*2 u mješovitim strategijama.

Ako barem jedna strana ima samo 2 akcije, primjenjujemo metodu grafsko-analitičkog rješenja. Definirajmo igru u obliku sljedeće matrice:

Za ovu igru se može uzeti u obzir sljedeće: igrač svaki put igra protiv neke čiste strategije druge strane. U ovom slučaju, on može odabrati omjer vjerovatnoće koji će mu dati zagarantovana pobeda, veličina cijene igre.

Razmotrite igru m×n sa matricom P = (a ij ), i = 1, 2, ..., m; j = 1, 2, ..., n i odrediti najbolju među strategijama A 1 , A 2 , ..., A m . Odabir strategije A i igrač A mora očekivati da igrač IN će odgovoriti koristeći jednu od strategija B j , za koji je isplata za igrača A minimalno (igrač IN nastoji da "povredi" igrača A ). Označimo sa α i , najmanji dobitak igrača A prilikom odabira strategije A i za sve moguće strategije igrača IN (najmanji broj u i red matrice plaćanja), tj.

Među svim brojevima α i (i = 1, 2, ..., m) Odaberimo najveće: . Hajde da pozovemo α niža cijena igre, ili maksimalni dobici (maximin). Ovo je zagarantovana pobeda za igrača A za bilo koju strategiju igrača IN . dakle,

13. Sedlo.

Sedlo je najveći element stupca matrice igre, koji je ujedno i najmanji element odgovarajućeg reda (u igri sa nultom sumom za dvije osobe). U ovom trenutku, dakle, maksimin jednog igrača je jednak minimaksu drugog; S. t. je tačka ravnoteže.

Koncept sedla

Ako se u igri s matricom A donja i gornja, neto cijene igre poklapaju, tj. , onda se kaže da ova igra ima tačku sedla, u čistim terminima, i neto vrijednost igre:

Sedlo je par čistih strategija (i 0 , j 0) prvog i drugog igrača, u kojima se postiže jednakost.

Koncept sedla ima sljedeće značenje:

ako jedan igrač slijedi strategiju sedla, onda drugi igrač ne može učiniti ništa bolje nego slijediti strategiju sedla.

Odstupanje prvog igrača od sedla može dovesti samo do smanjenja njegovog dobitka.

Odstupanje drugog igrača od sedla može dovesti do povećanja njegovog gubitka.

Element sedla je minimalni element u redu i maksimalni element u koloni.

Za određivanje elementa sedla potrebno je uzastopno odrediti minimalni element u svakoj tački, a zatim provjeriti da li je to maksimalni element stupa, i ako jeste, onda se sedlo nalazi na ovaj način - cijena igra, optimalne strategije prvog i drugog igrača:

14. Optimalne strategije.

U matričnoj igri, svaki igrač bira svoje strategije, a da ne zna za akcije drugog igrača. Hajde da saznamo koji su najbolji zagarantovani dobici za njih. Prvi igrač, odabravši neku strategiju i, može dobiti kao isplatu jedan od dva elementa ai1, ai2 matrice A, ovisno o tome koju strategiju koristi drugi igrač. U najgorem slučaju mora računati na minimalni dobitak, tj.

U isto vrijeme, uz uspješan izbor strategije i = i*, prvi igrač može dobiti maksimalnu pobjedu od minimalne:

Drugi igrač raspravlja na sličan način. Prilikom odabira strategije j, njen maksimalni gubitak od dva moguća a1 j, a2 j je jednak

Ako je izbor strategije j = j* bio uspješan, tada može računati na minimalni gubitak od maksimuma:

Formule (5.2), (5.3) određuju najbolji zagarantovani dobitak za igrače. Ako se poklapaju, onda oni opšte značenje može se smatrati prihvatljivim kompromisom za igrače, a odgovarajuće strategije i*, j* se mogu smatrati optimalnim strategijama.

Direktni proračuni koristeći formule (5.2), (5.3) koristeći (5.1) daju

Ovdje najbolje zagarantovane pobjede nisu jednake i ne postoje optimalne strategije.

Razlog za nedostatak optimalnih strategija očito leži u njihovoj definiciji. Pokušajmo promijeniti definiciju optimalnih strategija ne gubeći iz vida igrački smisao zadatka i ciljeve igrača.

Klasifikacija igara. Definicija sedla.

Igre se mogu klasificirati prema broju igrača, broju strategija, prirodi interakcije između igrača, prirodi pobjede, broju poteza, stanju informacija itd.

Na osnovu prirode interakcije, igre se dijele na:

1) nekoaliciona: igrači nemaju pravo sklapati dogovore ili koalicije;

2) koalicija(zadruga) - može se pridružiti koalicijama.

U kooperativnim igrama koalicije su unaprijed određene.

Na osnovu vrste pobjedničkih funkcija igre se dijele na: matrične, bimatrične, kontinuirane, konveksne, odvojive, dvobojne itd.

Definicija. Ako je u igri s matricom A = (donja neto cijena jednaka gornjoj neto cijeni), onda se kaže da ova igra ima sedlo tačka u čistim strategijama i neto cijena igre u = =.

Saddle point je par čistih strategija (i o, j o) respektivno, igrači 1 i 2, pri čemu se postiže jednakost = . 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 sedlu. Matematički, ovo se može napisati na drugi način: , Gdje i, j– sve čiste strategije igrača 1 i 2, respektivno; (i o, j o)– strategije koje formiraju sedlo.

Dakle, element sedla je minimalan u io-tom redu i maksimalan u jo-tom stupcu u matrici A. Pronalaženje sedla matrice A se dešava na sledeći način: u matrici A sekvencijalno u svakoj linija pronađite minimalni element i provjerite da li je ovaj element maksimalni u svom kolona. Ako je odgovor da, onda je to element sedla, a par strategija koje mu odgovaraju formiraju sedlo. Par čistih strategija (i o, j o) igrači 1 i 2, koji formiraju sedlo i element sedla, se pozivaju rešenje igre . Gde i o I j o su pozvani optimalno čišćenje strategije igrači 1 i 2.

Svojstva sedla:

1. Ekvivalencija. Ako u igri postoji nekoliko točaka sedla, tada su vrijednosti funkcije isplate u njima iste.

13. Definicija mješovite strategije. Rješenje igre 2*2 u mješovitim strategijama.

Mješovita strategija je kada, umjesto primjene bilo koje specifične strategije, učesnici u igri mogu nasumično mijenjati (miješati) svoje strategije u skladu sa posebno dizajniranom shemom koja obezbjeđuje željenu učestalost, ili vjerovatnoću, implementacije svakog od strategije.

Za svakog igrača možete postaviti sljedeće komponente:

Pia– vjerovatnoća korištenja i-te strategije od strane A.

Ako odaberete takav set Pia, koji obezbeđuje najveći dobitak bez obzira na akcije druge strane, onda će ovaj skup verovatnoća (p 1 a, p 2 a, ..., p ma) = S A i zvati se mešovita strategija.

S * A = (p * 1 a, p * 2 a, …, p * ma) – optimalna mješovita strategija.

( S A ) – skup mešovitih strategija na strani A, od kojih se mora izabrati optimalna.

Igra 2*2 u mješovitim strategijama.

Ako barem jedna strana ima samo 2 akcije, primjenjujemo metodu grafsko-analitičkog rješenja. Definirajmo igru u obliku sljedeće matrice:

a 11	a 12
a 21	a 22

Za ovu igru se može uzeti u obzir sljedeće: igrač svaki put igra protiv neke čiste strategije druge strane. Istovremeno, on može odabrati omjer vjerovatnoće koji će mu dati zagarantovan dobitak jednak cijeni igre.

A 11 p * 1 a + a 21 p * 2 a = γ - kada se igra protiv prve čiste strategije strane B.

a 12 p * 1 a + a 22 p * 2 a = γ – protiv druge čiste strategije strane B.

p * 1 a + p * 2 a = 1

Isto tako za B:

A 11 p * 1 b + a 12 p * 2 b = γ - kada se igra protiv prve čiste strategije strane B.

a 21 p * 1 b + a 22 p * 2 b = γ – protiv druge čiste strategije strane B.

p * 1 b + p * 2 b = 1

Rješenje sistema jednačina:

Da bi dobijena rješenja imala smisla, moraju biti potrebni sljedeći odnosi:

Ako je jedno ili drugo tačno, tada se vjerovatnoće kreću od 0 do 1.

Za stranu A: Za stranu B:

U problemima teorije statistička rješenja razmatraju se matrice plaćanja (za diskretni slučaj) ili funkcija plaćanja (u kontinuiranom slučaju). Vrijednosti u plaćanju. matrici, ili u naplati. funkcije zavise od 2 faktora: 1. prirodnog stanja, 2. opcija donosioca odluka.

Za razliku od teorije igara, ovdje se samo jedna od strana smatra strankom s racionalnim ponašanjem. dr. strana se smatra prirodnim faktorom sa elementom neizvjesnosti. U ovom slučaju se konvencionalno smatra da se igramo sa prirodom, pa se u pogledu druge strane prave različite pretpostavke o tome kako će se birati opcije za njeno stanje.

Matrica plaćanja se može formirati kao rezultat rješavanja problema optimizacije kada se, na primjer, može dobiti nekoliko ekvivalentnih rješenja. Za odabir najbolja opcija neophodno je uvesti funkciju kriterijuma koja odražava sistem preferencija donosioca odluka.

Geometrijska interpretacija.

e 11	e 12
e 21	e 22
…	…
e n 1	e n2

F i – prirodno stanje.

E i – opcije rješenja.

Ako odvojite tačke (e i 1, e i 2), one će ispuniti određeni prostor ograničen pravokutnikom. RT – radna tačka. Unutar ovog pravougaonika formirana su 4 kvadranta ili 4 konusa. Razmotrimo svojstva tačaka iz ovih čunjeva.

I: sve tačke u barem jednoj koordinati su bolje od razmatrane RT. Stoga je konus I konus preferencije.

III: sve tačke u najmanje jednoj koordinati su očigledno gore od RT.

II i IV: sve tačke duž jedne koordinate mogu biti bolje, ali gore duž druge. Stoga su ovi stošci konusi neizvjesnosti.

Da bi se odredilo koje su tačke više ili manje poželjnije od PT, potrebno je razmotriti različite linije koje predstavljaju linije jednačina ili linije ekvivalentnih rješenja.

Simetrala (linija 1) odgovara funkciji neutralnog kriterija. Red 2 – funkcija pesimističkog kriterijuma. Red 3 – funkcija optimističkog kriterija.

Bilo koja od linija 1, 2, 3 povezuje tačke koje su ekvivalentne po želji. Tačke desno i iznad bilo koje od ovih linija su poželjnije od tačaka lijevo i ispod.

Granični slučaj za pesimističku funkciju su linije koje ograničavaju prvi kvadrant. Za optimiste – treći kvadrant.

Matrične igre i koncept sedla. Pogledajmo bliže antagonističke igre i njihova glavna svojstva. Na zgodan način Zadatak igre s nultom sumom za dva igrača je matrica plaćanja. Odatle, inače, dolazi još jedno ime - matrične igre. Svaki element matrice plaćanja i ij sadrži numerička vrijednost dobitak igrača I (igrač II gubi) ako prvi primijeni strategiju i, a drugi - strategija j. Uslovi dobitke I gubitak treba shvatiti u u širem smislu, jer mogu prihvatiti negativne vrijednosti a sa svakodnevne tačke gledišta znači suprotno. Netrivijalnost problema leži prvenstveno u činjenici da svaki igrač pravi svoj izbor ne znajući za izbor drugog, što značajno otežava proces optimizacije odabrane strategije.

Klasičan primjer Antagonistička igra je igra u kojoj dva učesnika pogađaju brojeve nezavisno jedan od drugog. Pretpostavlja se da ako se njihov zbir pokaže paran, onda dobitak jednak 1 ide prvom igraču, a ako je neparan, onda drugom. Pod pretpostavkom da je za oba igrača pogađanje neparnog broja prva strategija, a paran broj druga, možemo napisati matricu isplate ove igre:

Redovi matrice (6.1) odgovaraju strategijama igrača I, kolone - strategijama igrača II, a njeni elementi - rezultatima prvog igrača. Takođe iz definicije igre proizilazi da elementi ove matrice, uzeti sa suprotnim predznakom, odgovaraju dobitku drugog igrača.

Složenija i smislenija matrica plaćanja može se dobiti ako se predložena igra malo modificira. Pretpostavimo da oba učesnika imaju pravo da pogode brojeve od 1 do 4, koji čine njihove strategije. Ako je rezultat zbrajanja predviđenih brojeva paran, tada drugi igrač plaća dobijeni iznos prvom, a ako je neparan, onda prvi igrač plaća drugog. Zapišimo matricu plaćanja za takvu igru:

Neke konvencionalnosti i izvještačenosti u formulaciji problema ne bi trebalo biti u ovom slučaju zbunjuju nas, jer se model koji opisuje, na primjer, konkurenciju između dvije firme za novootvoreno tržište proizvoda itd., može svesti na sličan oblik.

Kao što je već napomenuto, najvažnije pitanje u teoriji igara je optimalnost rješenja (izbor strategije) za svakog igrača. Sa ove tačke gledišta, analizirajmo određenu matričnu igru za koju je data matrica plaćanja A=║a ij║m x n. Kada igrač odabere strategiju i njegov garantovani prihod bez obzira na radnje igrača II biće min a i,j. Jer on može da bira i samostalno, onda je preporučljivo napraviti ovaj izbor na način da za bilo koju neprijateljsku strategiju maksimizira iznos zagarantovanog prihoda, tj. da osigura primanje max (min a i,j). Ovaj princip izbora strategije naziva se „ princip maksimina" S druge strane, slično razmišljanje se može provesti u vezi sa postupcima drugog igrača. Njegovo najveći gubitak prilikom odabira strategije j bit će max a i,j, te stoga treba da izabere strategiju na način da minimalizira iznos gubitka za bilo koju akciju protivnika, tj. osigura min (max. a i,j). to je poenta princip minimaksa.

Može se dokazati valjanost sljedeće relacije:

Međutim, od očiglednog interesa je situacija u kojoj je vrijednost isplate (isplate) koju je primio igrač I kada odabere maksimalnu strategiju jednaka isplati (gubitku) igrača II sa minimax strategijom

U ovom slučaju se kaže da igra ima sedlo. Podudaranje vrijednosti zagarantovanih isplata igrača pod maksimin i minimaks strategijama znači mogućnost postizanja nekog optimalnog (stabilnog, ravnotežnog) stanja u igri, od kojeg je neisplativo bilo kome od učesnika da odstupi. Koncept “optimalnosti” ovdje znači da nijedan razuman (oprezni) igrač ne želi promijeniti svoju strategiju, jer će njegov protivnik, u principu, moći odabrati strategiju koja će dati najgori rezultat za prvu. Strategije ja* I j* formiranje sedla se nazivaju optimalno, i vrijednost v = a i*j* pozvao po cijenu igre. trojka ( ja*, j*, v) računa se rješavanje matrične igre sa sedlom.

Lako je uočiti da svaka igra nema tačku sedla. Konkretno, i divljač (6.1) i divljač (6.2) nemaju sedlo. Primjer igre koja ima sedlo je igra sa matricom isplate (6.5).

U ovoj matrici, minimalni (zagarantovani) dobici prvog igrača u redovima su 1, 5 i (-3). Shodno tome, njegov maksiminski izbor će odgovarati strategiji 2, što garantuje pobedu od 5. Za drugog igrača, maksimalni gubici u kolonama matrice će biti 8, 10, 5, 17, tako da ima smisla izabrati strategiju 3 , pod kojim će izgubiti samo 5. Dakle, druga strategija prvog igrača i treća strategija drugog čine sedlo sa vrijednošću 5, odnosno za igru sa matricom (6.5) ima rješenje ( 2; 3; 5).

Igra sa nultom sumom u kojoj svaki igrač ima na raspolaganju konačan skup strategija. Pravila matrične igre određena su matricom plaćanja, čiji su elementi dobici prvog igrača, koji su ujedno i gubici drugog igrača.

Matrix game je antagonistička igra. Prvi igrač dobiva maksimalni zajamčeni (neovisno o ponašanju drugog igrača) dobitak, jednak cijeni igre; shodno tome, drugi igrač ostvaruje minimalni zajamčeni gubitak.

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

Sada o svemu po redu i detaljno.

Matrica plaćanja, čiste strategije, cijena igre

IN matrična igra njegova pravila su određena matrica plaćanja .

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

IN matrica plaćanja elementi su brojevi koji izražavaju pobjede i poraze igrača. Pobjede i gubici mogu biti izraženi u bodovima, novčanoj količini ili drugim jedinicama.

Kreirajmo matricu plaćanja:

Ako prvi igrač odabere i-ta čista strategija, a drugi igrač - j th čista strategija, onda će isplata prvog igrača biti 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 ili glava ili rep. Ako se "glave" i "glave" ili "repovi" ili "repovi" bacaju u isto vrijeme, tada će prvi igrač osvojiti jednu jedinicu, au ostalim slučajevima izgubit će jednu jedinicu (drugi igrač će osvojiti jednu jedinicu) . Iste dvije strategije su na raspolaganju drugom igraču. Odgovarajuća matrica plaćanja će biti sljedeća:

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

Kako birate strategiju u matričnoj igri?

Pogledajmo ponovo matricu plaćanja:

Prvo, odredimo iznos dobitka za prvog igrača ako koristi ičista strategija. Ako prvi igrač koristi ičistu strategiju, onda je logično pretpostaviti da će drugi igrač koristiti takvu čistu strategiju zbog koje bi isplata prvog igrača bila minimalna. Zauzvrat, prvi igrač će koristiti tako čistu strategiju koja bi mu omogućila maksimalnu pobjedu. Na osnovu ovih uslova, dobici prvog igrača, koje označavamo kao v1 , zvao maksimalni dobici ili niža cijena igre .

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

Sada odredimo iznos gubitka za 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 čistu strategiju u kojoj bi njegov gubitak bio minimalan. Gubitak drugog igrača koji označavamo kao v2 , zvao minimalni gubitak ili najviša 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 zapišite vrijednost maksimalnog elementa i od njih odaberite minimum. Tako će gubitak drugog igrača biti minimum od maksimuma. Otuda i naziv - minimax pobjeda. Broj kolone ovog elementa će biti broj čiste strategije koju odabere drugi igrač. Ako drugi igrač koristi "minimax", onda bez obzira na izbor strategije od strane prvog igrača, neće izgubiti više od v2 jedinice.

Primjer 1.

Najveći od najmanjih elemenata nizova je 2, to jest najniza cijena igri, njoj odgovara prva linija, dakle, maksiminska 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 pronaći donju i gornju cijenu igre, maksimin i minimaks strategije, vrijeme je da naučimo kako formalno definirati ove koncepte.

Dakle, zagarantovana pobeda za prvog igrača je:

Prvi igrač mora izabrati čistu strategiju koja bi mu pružila maksimum minimalni dobici. 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 prikazan na sljedeći način:

Drugi igrač mora izabrati svoju čistu strategiju tako da njegov gubitak bude minimalan. Ovaj gubitak (minimaks) je prikazan 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 matrica plaćanja Zapišimo najmanje elemente u njegove redove i označimo maksimum od njih, a ispod matrice - najveće elemente u kolonama i odaberimo minimum od njih:

Najveći od najmanjih elemenata linija je 3, ovo je niža cijena igre, druga linija 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. To jest, jednake niže i gornje cijene igre se postižu korištenjem istog para 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 plaćanja ispisaćemo najmanje elemente u njene redove i zabeležiti maksimum od njih, a ispod matrice - najveće elemente u kolonama i odabrati minimum od njih:

Donja cijena igre poklapa se s gornjom cijenom 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.

Sami riješite 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 rješenja u čistim strategijama.

Ali ima rješenje u optimalnim mješovitim strategijama. Da biste ih pronašli, morate pretpostaviti da se igra ponavlja dovoljan broj puta kako biste, na osnovu iskustva, mogli pogoditi koja je strategija poželjnija. Stoga je odluka povezana sa konceptom vjerovatnoće i prosjeka (matematičko očekivanje). U konačnom rješenju postoji i analog sedla (odnosno jednakost donjeg i top cijena igre) i analogiju njihovih odgovarajućih strategija.

Dakle, da bi prvi igrač dobio maksimalnu prosječnu pobjedu, a drugi igrač minimalan 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. U ovom slučaju, 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. U ovom slučaju, 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 pobjeda prvog igrača (gubitak drugog igrača). 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 pobjede 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 pobjede prvog igrača (gubitak drugog igrača), ono je jednako umnošku vektora mješovite strategije prvog igrača, matrice plaćanja 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 igra ponovi dovoljan broj puta.

Po analogiji sa maksiminskom i minimaksnom notacijom, u slučaju čistih strategija optimalno mješovite strategije označeni su na sljedeći način (i povezani su s matematičkim očekivanjem, odnosno prosjekom pobjede 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šiti matričnu igru u mješovitim strategijama , moramo matričnu igru svesti na problem linearno programiranje, 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 konstruirati pravu liniju problem linearnog programiranja I dvostruki zadatak. U dualnom problemu transponuje se proširena matrica koja pohranjuje koeficijente varijabli u sistemu ograničenja, slobodne termine i koeficijente varijabli u funkciji cilja. U ovom slučaju, minimum funkcije cilja originalnog problema se uparuje sa maksimumom u dualnom problemu.

Funkcija cilja u problemu direktnog linearnog programiranja:

Sistem ograničenja u problemu direktnog linearnog programiranja:

Funkcija cilja u dualnom problemu je:

Sistem ograničenja u dvojnom problemu:

Optimalni plan za problem direktnog linearnog programiranja označava se sa

a optimalni plan za dualni problem je označen sa

Linearne forme za odgovarajuće optimalne planove označavamo sa i ,

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

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

Teoretski matematičari su to dokazali cijena igre izražava se na sljedeći način kroz linearne forme optimalnih planova:

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, kao što smo već definirali u prethodnom paragrafu, vektori. Dakle, množenjem broja (cijene igre) vektorom (sa koordinatama optimalnih planova) dobijamo i vektor.

Primjer 6. Zadana je matrična igra s matricom isplate