http://emm. *****/lect/lect5.html#vopros2

(bolje izgleda na internetu od ove kopije)

Elementi teorije igara

1. Osnovni pojmovi i definicije. Predmet teorije igara.
2. Igre sa nultom sumom. Rješenje je u čistim strategijama.
3. Rješavanje igara u mješovitim strategijama.
4. Geometrijska interpretacija igara.
5. Svođenje igre parova na problem linearno programiranje.
6. Opća shema rješenja uparenih igara sa nultom sumom.
7. Upotreba alternativnih kriterijuma za određivanje optimalnih strategija.

1. Osnovni pojmovi i definicije. Predmet teorije igara

Vrlo često u mom praktične aktivnosti osoba se mora suočiti s problemima u kojima je potrebno donijeti odluku u uslovima kada dvije ili više strana imaju različite ciljeve, a rezultati svake akcije svake strane zavise od aktivnosti partnera. Takve situacije, koje nastaju, na primjer, prilikom igranja šaha, dama ili domina, klasificiraju se kao konfliktno: Rezultat poteza svakog igrača zavisi od kontra poteza protivnika. Kakav će to biti odgovor nije poznato unaprijed, pa kažu da se odluka mora donijeti u uslovima neizvjesnosti. Cilj igre je da jedan od učesnika pobedi.

U ekonomiji se konfliktne situacije javljaju često i različite su prirode. To uključuje, na primjer, odnose između dobavljača i potrošača, kupca i prodavca, banke i klijenta. U ovim primjerima konfliktnu situaciju generira razlika u interesima partnera i želja svakog od njih da donese odluke koje ostvaruju svoje ciljeve u u najvećoj meri. Pri tome, svako mora voditi računa ne samo o svojim ciljevima, već i o ciljevima svog partnera, te uzeti u obzir unaprijed nepoznate odluke koje će ti partneri donijeti.

Situacija se zove sukob, ako se radi o strankama čiji su interesi potpuno ili djelimično suprotni.

Za racionalna odluka problema sa konfliktnim situacijama, postoje naučno utemeljene metode. Takve metode razvija matematička teorija konfliktnih situacija, tzv teorija igara.

Igra- radi se o stvarnom ili formalnom sukobu u kojem postoje najmanje dva učesnika (igrača), od kojih svaki teži ostvarivanju vlastitih ciljeva.

Zovu se dozvoljene radnje svakog igrača usmjerene na postizanje određenog cilja pravila igre.

Igra se zove parna soba, ako uključuje dva igrača, i višestruko, ako je broj igrača veći od dva. U nastavku ćemo razmatrati samo igre parova. Ova igra uključuje dva igrača - A i B, čiji su interesi suprotni. Igra (proces igre) će se shvatiti kao niz radnji od strane A i B.

Kvantifikacija rezultata igre se zove plaćanje.

Zove se igra parova igra sa nultom sumom, ili antagonistički, ako je iznos uplata nula, odnosno dobitak jednog igrača jednak je gubitku drugog. U ovom slučaju, da biste dovršili zadatak igre, dovoljno je naznačiti jednu od količina. ako npr. a– dobitak jednog od igrača, b- dobitak drugog, zatim za igru sa nultom sumom b = -a, stoga je dovoljno razmotriti npr. a.

U ovom kursu ćemo razmotriti uparene igre sa nultom sumom.

Izbor i provedba jedne od radnji predviđenih pravilima naziva se napredak igrač. Pokreti mogu biti lični i nasumični.

Lični potez- ovo je svjestan izbor igrača jedne od mogućih radnji (na primjer, prelazak na šahovska igra).

Slučajni potez je nasumično odabrana radnja (na primjer, odabir karte iz promiješanog špila).

U budućnosti ćemo razmatrati samo lične poteze igrača.

Strategija igrača je skup pravila koja određuju izbor njegove akcije pri svakom ličnom potezu, u zavisnosti od trenutne situacije.

Obično tokom igre, svakim ličnim potezom, igrač pravi izbor u zavisnosti od konkretne situacije. Međutim, u principu je moguće da igrač donosi odluke unaprijed (kao odgovor na bilo koju situaciju). To znači da je igrač odabrao određenu strategiju, koja se može specificirati kao lista pravila ili program.

Igra se zove krajnji, ako svaki igrač ima konačan broj strategija, i beskrajno- inače.

Zove se strategija igrača optimalno, ako pruža igraču maksimalnu pobjedu (ili, što je isto, minimalni gubitak), pod uslovom da se drugi igrač pridržava svoje strategije.

Ako se igra ponovi mnogo puta, onda igrači mogu biti zainteresirani ne za pobjedu i poraz u svakoj određenoj igri, već za prosječna pobjeda (gubitak) u svim serijama.

Da bi riješio igru, odnosno pronašao rješenje za igru, potrebno je da svaki igrač odabere optimalnu strategiju.

dakle, predmet teorije igara predstavljaju metode za pronalaženje optimalnih strategija igrača.

Prilikom odabira optimalna strategija prirodno je pretpostaviti da se oba igrača ponašaju racionalno sa stanovišta svojih interesa. Najvažnije ograničenje teorije igara je jedinstvenost isplate kao pokazatelja efikasnosti, dok u većini realnih ekonomskih problema postoji više od jednog indikatora efikasnosti. Osim toga, u ekonomiji, po pravilu, postoje zadaci u kojima interesi partnera nisu nužno antagonistički. Međutim, rješavanje igrica u prisustvu velikog broja učesnika sa usaglašenim interesima je mnogo teži zadatak.

Ograničićemo se na razmatranje uparenih igara sa nultom sumom.

2. Igre sa nultom sumom. Rješenje u čistim strategijama

Razmotrimo uparenu konačnu igru.

Neka igrač A ima m ličnih strategija: A1, A2, …, Am. Neka igrač B ima n ličnih strategija. Označimo ih B1, B2, …, Bn. U ovom slučaju igra ima dimenziju mxn..gif" width="39" height="17 src=">) ishod igre je jednoznačno određen, tj. pobjednički aij igrača A (pozitivan ili negativan) i gubitak (- aij) igrača IN.

Pretpostavimo da su vrijednosti aij poznate za bilo koji par strategija (Ai, Bj).

Matrica A = (aij), 230" style="width:172.5pt">

a11 a12 ... a1n
a21 a22 ... a2n

Matrica plaćanja se takođe često prikazuje u obliku tabele (vidi tabelu 5.1).

Tabela 5.1 - Opšti oblik matrica plaćanja

Redovi matrice A odgovaraju strategijama prvog igrača, a stupci strategijama drugog.

Ove strategije se nazivaju čist.

Primjer 5.1. Kreirajte matricu plaćanja za sledeća utakmica(igra "Traži").

Igrač A može se sakriti u jednom od dva skloništa (I ili II); igrač B traži igrača A, i ako ga nađe, dobija kaznu od 1 novčane jedinice od A, u suprotnom plaća igraču A 1 novčanu jedinicu.

Rješenje.

Da biste kreirali matricu plaćanja, trebali biste analizirati ponašanje svakog igrača. Igrač A se može sakriti u skloništu I - označimo ovu strategiju sa A1, ili u skloništu II - strategijom A2.

Igrač B može tražiti prvog igrača u skloništu I - strategija B1, ili u skloništu II - strategija B2. Ako se igrač A nalazi u skloništu I, a igrač B ga tamo otkrije, tj. implementira se par strategija (A1, B1), tada igrač A plaća kaznu, tj. a11 = -1. Slično, a22 = -1.

Očigledno, kombinacije strategija (A1, B2) i (A2, B1) daju igraču A isplatu, jednako jedan, pa je a12 = a21 = 1.

Dakle, za igru "Traži" veličina 2x2 dobijamo sljedeću matricu plaćanja:

A (skrivanje) =

Razmotrimo igru veličine mxn sa matricom A = (aij), https://pandia.ru/text/78/456/images/image002_132.gif" width="39" height="17 src=">i odredimo najbolja među strategijama A1, A2, …, Am.

Prilikom odabira strategije Ai, igrač A mora očekivati da će igrač B na nju odgovoriti jednom od strategija Bj za koju je isplata igrača A minimalna (igrač B nastoji da "povredi" igrača A).

Označimo MsoNormalTable">

Među brojevima https://pandia.ru/text/78/456/images/image010_40.gif" width="44" height="16 src=">) izabraćemo najveći. Pozovimo dnu po cijenu igre ili maksimalni dobici (maksimin). Ovo zagarantovana pobeda igrač A za bilo koju strategiju igrača B.

Konačna formula se može napisati na sljedeći način:

Strategija koja odgovara maksiminu se zove maksiminska strategija.

Slično razmišljanje može se izvesti u odnosu na igrača B.

Igrač B je zainteresiran za smanjenje isplate igrača A.

Prilikom odabira strategije Bj uzima u obzir da će igrač A težiti maksimalnoj pobjedi.

Označimo https://pandia.ru/text/78/456/images/image015_30.gif" width="10" height="17 src=">.gif" width="58 height=23" height="23 " >i nazovimo najviša cijena igre ili minimax. Ovo minimalni garantovani gubitak za igrača B.

ovako:

Poziva se strategija koja odgovara minimaksu minimax strategija.

Princip koji nalaže igračima da odaberu "najopreznije" maksimin i minimaks strategije naziva se princip minimaksa. Ovaj princip proizilazi iz razumne pretpostavke da svaki igrač teži da postigne cilj suprotan cilju njegovog protivnika.

Igrač bira svoje postupke, pod pretpostavkom da će neprijatelj djelovati na nepovoljan način, odnosno pokušat će „naškoditi“.

Vratimo se na primjer 5.1 i odredite donju i gornju cijenu igre u zadatku “Traži”.

Razmotrite matricu plaćanja:

Prilikom odabira strategije A1 (prvi red matrice) minimalni dobici je jednako https://pandia.ru/text/78/456/images/image012_33.gif" width="10" height="8 src=">2 = min (-1; 1) = -1, to se postiže kada igrač B koristi strategiju B2.

Garantujete sebi maksimalnu pobedu za bilo koju strategiju igrača B, tj..gif" width="10" height="8 src=">.gif" width="7" height="14">1 = max (-1 ; 1) = 1.

Slično, maksimalni gubitak igrača B kada odabere strategiju B2 (druga kolona) je 2 = max (1; -1) = 1.

Dakle, za bilo koju strategiju igrača A, garantovani minimalni gubitak igrača B je = min (1, 2) = min (1, 1) = 1 - gornja cijena igre.

Svaka strategija igrača B je minimaks.

Rezultate našeg razmišljanja sumiramo u tabeli 5.2, koja je matrica plaćanja sa dodatnim redom j i kolonom i. Na njihovoj raskrsnici ćemo zapisati gornju i donju cijenu igre.

Tabela 5.2 - Matrica plaćanja igre "Traži" sa dodatnim redom i kolonom

Dakle, u problemu koji se razmatra, donja i gornja cijena igre se razlikuju: https://pandia.ru/text/78/456/images/image017_28.gif" height="14 src=">.

Ako se gornja i donja cijena igre poklapaju, onda opšte značenje gornje i donje cijene v = https://pandia.ru/text/78/456/images/image017_28.gif" height="14 src=">se zove po čistoj cijeni igre, ili jednostavno po cijenu igre. Maksimin i minimaks strategije koje odgovaraju cijeni igre su optimalne strategije, i njihova ukupnost – optimalno rešenje, ili jednostavno rešenje igre.

U ovom slučaju igrač A prima maksimalni zagarantovani (nezavisno od ponašanja igrača B) dobitak v, a igrač B postiže minimalni zagarantovani (nezavisno od ponašanja igrača A) gubitak v. Kažu da rješenje za igru ima održivost, tj. ako se jedan od igrača pridržava svoje optimalne strategije, onda ne može biti isplativo da drugi odstupi od svoje optimalne strategije.

Par čiste strategije Ai i Bj daje optimalno rešenje igre ako i samo ako je njen odgovarajući element aij i najveći u svom stupcu i najmanji u svom redu.

Ova situacija, ako postoji, zove se sedlo(slično površini sedla, koja se u jednom smjeru savija prema gore, a u drugom prema dolje).

Dakle, za igru sa sedlom, pronalaženje rješenja uključuje odabir maksiminske i minimaks strategije, koje su optimalne.

Primjer 5.2. Odredite donju i gornju cijenu igre, koja je data sljedećom matricom isplate:

0,5 0,6 0,8
0,9 0,7 0,8
0,7 0,6 0,6

Rješenje.

Hajde da saznamo da li igra ima tačku sedla. Pogodno je rješenje provesti u tabeli. Tabela 5.3 uključuje matricu isplate igre, kao i dodatni red i kolonu koji ilustruju proces pronalaženja optimalnih strategija.

Tabela 5.3 - Matrica plaćanja primjera 5.2 sa dodatnim redom i stupcem

Hajde da damo neka objašnjenja.

Kolona https://pandia.ru/text/78/456/images/image012_33.gif" width="10" height="8 src=">1 = 0,5; 2 = 0,7; 3 = 0, 6 - minimalni brojevi u redovima.

Slično, https://pandia.ru/text/78/456/images/image017_28.gif" width="7 height=14" height="14">2 = 0,7; 3 = 0,8 - maksimalni brojevi u kolonama.

3. Rješavanje igara u mješovitim strategijama

Dakle, za igru sa sedlom, pronalaženje rješenja sastoji se od odabira maksimin i minimaks strategija, koje su optimalne.

Ako igra nema sedlo, onda upotreba čistih strategija ne pruža optimalno rješenje za igru. Na primjer, u igri "Traži" ( primjer 5.1) nema sedla.

U ovom slučaju moguće je dobiti optimalno rješenje naizmjeničnim čistim strategijama.

Mješovita strategija za igrača A je korištenje čistih strategija A1, A2, …, Am sa vjerovatnoćama u1, u2, …, um.

Obično se mješovita strategija prvog igrača označava kao vektor: U = (u1, u2, ..., um), a strategija drugog igrača kao vektor: Z = (z1, z2, ..., zm).

Očigledno je da:

ui ≥ 0, ,
zj ≥ 0, ,
ui = 1, zj = 1.

Optimalno rješenje za igru(ili jednostavno - rešenje za igru) je par optimalnih strategija U*, Z*, generalno mješovitih, koji imaju 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. Poziva se isplata koja odgovara optimalnom rješenju po cijenu igre v. Cijena igre zadovoljava nejednakost:

Sljedeća fundamentalna teorema teorije igara je tačna.

Neumannova teorema. Svaka igra s konačnim nultom sumom ima mješovito strateško rješenje..

Neka je U* = (, https://pandia.ru/text/78/456/images/image030_23.gif" width="15" height="17 src=">) i Z* = (, https:// pandia.ru/text/78/456/images/image033_22.gif" width="13" height="17 src=">) - par optimalnih strategija. Ako je čista strategija uključena u optimalnu mješovitu strategiju s vjerovatnoćom različitom od nule, onda se zove aktivan.

Teorema aktivnih strategija. Ako se jedan od igrača drži svoje optimalne mješovite strategije, tada isplata ostaje nepromijenjena i jednaka cijeni igre v, ako drugi igrač ne prelazi granice svojih aktivnih strategija..

Ova teorema je od velike praktične važnosti – pruža specifične modele za pronalaženje optimalnih strategija u odsustvu sedla.

Razmotrite igru veličine 2 x2 .

Ova igra je najjednostavniji slučaj konačne igre. Ako takva igra ima tačku sedla, onda je optimalno rješenje par čistih strategija koje odgovaraju ovoj tački.

Za igru u kojoj nema sedla u skladu s Neumannovom teoremom, postoji optimalno rješenje i određeno je parom mješovitih strategija U* = (https://pandia.ru/text/78/456/images/image029_24 .gif" width="13 " height="17 src=">) i Z* = (, https://pandia.ru/text/78/456/images/image029_24.gif" width="13" height= "17"> = v. Uzimajući u obzir da je + = 1, dobijamo sistem jednačina:

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č dobija maksimalni zagarantovani (nezavisno od ponašanja drugog igrača) dobitak, jednak ceni igre, shodno tome, drugi igrač ostvaruje minimalni garantovani 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čista strategija, tada će prvi igrač biti isplata 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 o cijeni 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 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 kolone je 5, što je top cijena igri, druga kolona joj odgovara, dakle, minimaks 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 obezbedila maksimum od minimalnog dobitka. 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 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:

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 (tj. jednakost donje i gornje cijene igre), i analog strategija koje im odgovaraju.

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 , 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, trebate kreirati ravnu 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 je uparen 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 dualnom 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

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

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

Dobijamo rješenje direktnog problema:

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

Predavanje 4

Tema: “ELEMENTI TEORIJE IGRE”

Koncept od gaming modeli

U praksi se često susrećemo sa problemima u kojima je potrebno donositi odluke u uslovima neizvjesnosti, tj. Nastaju situacije u kojima dvije (ili više) strana teže različitim ciljevima, a rezultati bilo koje akcije svake strane zavise od aktivnosti partnera. Takve situacije koje nastaju prilikom igranja šaha, dama, domina itd., smatraju se konfliktnim situacijama: rezultat poteza svakog igrača ovisi o potezu odgovora protivnika, cilj igre je pobijediti jednog od partnera. U ekonomiji se konfliktne situacije javljaju vrlo često i raznolike su prirode. To uključuje, na primjer, odnose između dobavljača i potrošača, kupca i prodavca, banke i klijenta. U svim ovim primjerima konfliktnu situaciju generira razlika u interesima partnera i želja svakog od njih da donese optimalne odluke koje u najvećoj mjeri ostvaruju svoje ciljeve. Pri tome, svako mora voditi računa ne samo o svojim ciljevima, već i o ciljevima svog partnera, te uzeti u obzir unaprijed nepoznate odluke koje će ti partneri donijeti.

Za kompetentno rješavanje problema u konfliktnim situacijama potrebne su naučno utemeljene metode. Takve metode razvija matematička teorija konfliktnih situacija, tzv teorija igara .

Upoznajmo se sa osnovnim konceptima teorije igara. Matematički model konfliktne situacije se zove igra , strane uključene u sukob - igrači i, a ishod sukoba je pobijediti . Za svaku formalizovanu igru, pravila A, one. sistem uslova koji definišu:

1) opcije za akcije igrača;

2) količinu informacija koje svaki igrač ima o ponašanju svojih partnera;

3) dobitak do kojeg vodi svaki niz radnji. Obično se dobitak (ili poraz) može kvantifikovati; na primjer, gubitak možete vrednovati kao nula, pobjedu kao jedan, a neriješeno kao 1/2.

Igra se zove parna soba , ako uključuje dva igrača, i višestruko , ako je broj igrača veći od dva. Razmotrićemo samo igre parova. Uključuju dva igrača A I IN,čiji su interesi suprotni, a pod igrom podrazumevamo niz akcija od strane A I IN.

Igra se zove igra sa nultom sumom , ili antagonistički th, ako je dobitak jednog od igrača jednak gubitku drugog, tj. Da biste dovršili zadatak igre, dovoljno je naznačiti vrijednost jednog od njih. Ako odredimo A - dobitak jednog od igrača, b - dobitke drugog, zatim za igru sa nultom sumom b = -A, Stoga je dovoljno razmotriti npr A .

Izbor i provedba jedne od radnji predviđenih pravilima naziva se napredak igrač. Pokreti mogu biti lični i nasumični. Lični potez - ovo je svjestan izbor igrača jedne od mogućih radnji (na primjer, potez u partiji šaha). Slučajni potez - to je nasumično odabrana akcija (na primjer, odabir karte iz promiješanog špila). U budućnosti ćemo razmatrati samo lične poteze igrača.

Strategija Igrač je skup pravila koja određuju izbor njegove akcije pri svakom ličnom potezu, ovisno o trenutnoj situaciji. Obično tokom igre, svakim ličnim potezom, igrač pravi izbor u zavisnosti od konkretne situacije. Međutim, u principu je moguće da sve odluke igrač donosi unaprijed (kao odgovor na bilo koju situaciju). To znači da je igrač odabrao određenu strategiju, koja se može specificirati kao lista pravila ili program. (Na ovaj način možete igrati igru pomoću računara.) Igra se zove Svakako th, ako svaki igrač ima konačan broj strategija, i beskrajno - inače.

Da bi odlučiti igre, ili pronaći rješenje za igru, treba izabrati strategiju za svakog igrača koja zadovoljava uvjet optimalnost i, one. jedan od igrača mora primiti maksimalna pobeda , kada se drugi drži svoje strategije. U isto vrijeme, drugi igrač mora imati minimalni gubitak , ako se prvi drži svoje strategije. Takve stratezi I su pozvani optimalno. Optimalne strategije takođe moraju zadovoljiti uslov održivost , one. Mora da je nepovoljno za bilo kojeg igrača da napusti svoju strategiju u ovoj igri.

Ako se igra ponovi dosta puta, onda igrači mogu biti zainteresirani ne za pobjedu i poraz u svakoj određenoj igri, već za prosječna pobjeda (gubitak) u svim serijama.

Cilj teorije igara je odrediti optimalnu strategiju za svakog igrača. Prilikom odabira optimalne strategije, prirodno je pretpostaviti da se oba igrača ponašaju razumno u smislu svojih interesa. Najvažnije ograničenje teorije igara je jedinstvenost isplate kao pokazatelja efikasnosti, dok u većini realnih ekonomskih problema postoji više od jednog indikatora efikasnosti. Osim toga, u ekonomiji se po pravilu javljaju problemi u kojima interesi partnera nisu nužno antagonistički. Razvoj aparata za teoriju igara za rješavanje problema sa velikim brojem učesnika koji imaju konzistentne interese je van okvira predavanja.

Matrica plaćanja.

Donja i gornja cijena igre

Razmotrimo uparenu konačnu igru. Pustite igrača A ima T lične strategije, koje označavamo sa . Pustite igrača IN dostupan P lične strategije, označimo ih . Kažu da igra ima dimenzije t x p . Kao rezultat odabira igrača bilo kojeg para strategija, ishod igre je jednoznačno određen, tj. dobitak igrača A (pozitivan ili negativan) i gubitak igrača IN . Pretpostavimo da su vrijednosti poznate za bilo koji par strategija . Matrix R=(), i = 1,2, ..., t; j = 1, 2, ..., n , čiji elementi su dobici koji odgovaraju strategijama i , pozvao matrica plaćanja ili matrica igre . Opšti izgled takve matrice predstavljen je u tabeli:

			…
			…
			…
…	…	…	…	…
			…

Redovi ove tabele odgovaraju strategijama igrača A , a kolone - strategije igrača IN .

Primjer.Kreirajte matricu isplate za sljedeću igru. Search game.

Player A može se sakriti u jednom od dva skloništa (I i II); igrač IN tražim igrača A , i ako ga nađe, dobija kaznu od 1 den. jedinice od A , inače plaća igraču A 1 dan jedinice Za igru je potrebno izgraditi matricu plaćanja.

Rješenje. Da biste sastavili matricu plaćanja, trebali biste analizirati ponašanje svakog igrača. Player A može se sakriti u skloništu I - označimo ovu strategiju sa ili u skloništu II - strategija.

Player IN može potražiti prvog igrača u skloništu I - strategija , ili skloništu II - strategija. Ako igrač A nalazi se u trezoru I i tamo ga otkriva igrač IN , one. tada se igrač implementira par strategija A plati kaznu, tj. . Slično dobijamo . Očigledno, strategije daju igraču A pobijediti 1, dakle . Dakle za igru" traži"veličine 2x2 dobijamo matricu plaćanja

Razmotrite igru t p sa matricom, i =1, 2, ..., T ; j =1, 2, ..., P i odrediti najbolju među strategijama . Odabir strategije igrača A mora očekivati da igrač IN će odgovoriti koristeći jednu od strategija , za koji je isplata za igrača A minimalno (igrač IN nastoji da "povredi" igrača A ).

Označimo sa , najmanja isplata igrača A prilikom odabira strategije , za sve moguće strategije igrača IN (najmanji broj V i -i linija platne matrice), tj.

, j =1,…n . (1)

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

. (2)

Strategija koja odgovara maksiminu se zove maksiminska strategija . Player IN zainteresovani za smanjenje dobitaka igrača A ; odabir strategije , uzima u obzir maksimalnu moguću dobit za A . Označimo

Među svim brojevima odaberite najmanji i nazovite ga najviša cijena igre ili minimaks pobjeda (minimax). Ovo zagarantovan gubitak igrača IN. stoga,

(4)

Poziva se strategija koja odgovara minimaksu minimax strategija.

Primjer. Odredite donju i gornju cijenu igre i odgovarajuće strategije u igri" Traži" Razmotrite matricu plaćanja:

Prilikom odabira strategije (prvi red matrice), minimalna isplata je i odgovara strategiji igrača IN . Prilikom odabira strategije (drugi red matrice), minimalna isplata je jednaka , to se postiže strategijom.

Garantujete sebi maksimalnu pobedu za bilo koju strategiju igrača IN, one. niža cijena igre, igrač A može izabrati bilo koju strategiju: ili , one. bilo koja od njegovih strategija je maksiminska.

Prilikom odabira strategije (kolona 1), igrač IN razumije da igrač A će odgovoriti strategijom da maksimizira svoj dobitak (gubitak IN ). Dakle, igračev maksimalni gubitak je IN pri odabiru strategije jednaka je max (-l; 1) = 1.

Slično, maksimalni gubitak igrača IN (pobjeda A ) kada odabere strategiju (kolona 2) jednaka je .

Dakle, za bilo koju strategiju igrača A zagarantovan minimalni gubitak igrača IN jednaka najvišoj cijeni igre.

Bilo koja strategija igrača IN je minimax. Dodavanjem reda i kolone u tablicu, dobijamo novu tabelu:


-1		-1
	-1	-1
	1

Na raskrsnici dodatnih redova i kolona upisaćemo gornju i donju cijenu igara.

Naći ćemo najbolja strategija igrač A, za koji analiziramo sve njegove strategije uzastopno. Odabir strategije A i, moramo računati na igrača Bće odgovoriti takvom strategijom Bj, za koji dobitak A biće minimalan. Stoga, među brojevima u prvom redu biramo najmanji, označavamo ga i upisujemo u dodatni stupac. Slično za svaku strategiju A i birati, tj. αi– minimalni dobici pri primeni strategije A i.
U primjeru 1:
α 1= min (0, –1, –2) = –2;
α 2= min (1, 0, –1) = –1;
α 3= min (0, –1, –2) = 0.
Ove brojeve ćemo upisati u dodatnu kolonu. Koju strategiju bi igrač trebao izabrati? A? Naravno, strategija za koju αi maksimum. Označimo . Ovo je zagarantovana pobeda koju igrač može sebi da obezbedi A, tj. ; ovaj dobitak se zove niža cijena igre ili maximin . Strategija A i, osiguravajući prijem niže cijene igre zove se maximin(reosiguranje). Ako igrač Aće se pridržavati ove strategije, tada je zagarantovana pobeda ≥ α za bilo kakvo ponašanje igrača B.
U primjeru 1. To znači da ako Aće napisati "3", onda barem neće izgubiti. Player B zainteresovani za smanjenje dobitaka A. Odabir strategije B 1, iz razloga opreza, uzima u obzir maksimalnu moguću dobit A. Označimo . Slično i pri odabiru strategije Bj maksimalni mogući dobici A–; Zapišimo ove brojeve u dodatni red. Da smanjite svoje dobitke A, potrebno je izabrati najmanji od brojeva β j. Broj je pozvan najviša cijena igre ili minimax . Ovo je zagarantovan gubitak za igrača B(tj. neće izgubiti više od β). Strategija igrača B, pružajući isplatu ≥ - β naziva se njenim minimax strategija.
U primjeru 1:
;
;
;
.
To znači da je optimalna strategija B– napišite „3“, onda barem neće izgubiti.

BA	B 1	B 2	B 3
A 1	0	– 1	–2	–2
A 2	1	0	–1	–1
A 3	2	1	0	0
	2	1	0	0 0

Princip koji nalaže igračima da izaberu "najopreznije" minimax i maximin strategije naziva se princip minimaksa . Ovaj princip proizilazi iz razumne pretpostavke da svaki igrač teži da postigne cilj suprotan cilju njegovog protivnika.
Može se dokazati da, tj.
U primjeru 1 α = β. Ako one. minimax se poklapa sa maksiminom, tada se ova igra zove saddle point igra. Saddle point je par optimalnih strategija ( Ai,Bj). U primjeru 1, igra ima sedlo ( A 3, B 3). U ovom slučaju, broj α = β se naziva (čisti) po cijenu igre(donja i gornja cijena igre su iste). To znači da matrica sadrži element koji je minimum u svom redu i istovremeno maksimum u njenom stupcu. U primjeru 1, ovo je element 0. Cijena igre je 0.
Optimalne strategije u bilo kojoj igri imaju važna imovina, naime - održivost . To znači da svaki igrač nije zainteresiran da odstupi od svoje optimalne strategije, jer je to za njega neisplativo. Odstupanje od optimalne strategije igrača A dovodi do smanjenja njegovog dobitka i jednostranog odstupanja igrača IN- za povećanje gubitaka. Kažu da sedlo daje ravnotežni položaj .
Primjer 2. Prva strana (igrač A) bira jednu od tri vrste oružja – A 1, A 2, A 3, i protivnik (igrač IN) - jedan od tri tipa aviona: U 1, U 2, U 3. Target IN– proboj fronta odbrane, gol A- uništenje aviona. Verovatnoća da će avion biti pogođen U 1 oružje A 1 jednak 0,5, avion U 2 oružje A 1 jednak 0,6, avion U 3 oružje A 1 jednako 0,8, itd., tj. element a ij matrica plaćanja – vjerovatnoća da će avion biti pogođen INj oružje Ai. Matrica isplate ima oblik: Riješite igru, tj. pronađite donju i gornju cijenu igre i optimalne strategije.
Rješenje. U svakom redu nalazimo minimalni element i upisujemo ga u dodatnu kolonu. U svakoj koloni nalazimo maksimalni element i upisujemo ga u dodatni red.

IN A	U 1	U 2	U 3	αi
A 1	0,5	0,6	0,8	0,5
A 2	0,9	0,7	0,8	0,7
A 3	0,7	0,5	0,6	0,5
β j	0,9	0,7	0,8	0,7 0,7

U dodatnoj koloni nalazimo maksimalni element = 0,7, u dodatnom redu nalazimo minimalni element = 0,7.
Odgovor: = 0,7. Optimalne strategije - A 2 I U 2.

Primjer 3. Igra bacanja. Svaki igrač može izabrati jednu od dvije strategije tokom svog poteza: glavu ili rep. Ako se odabrane strategije poklapaju A prima pobjedu +1, ako postoji neusklađenost B prima isplatu 1 (tj. A prima isplatu –1). Matrica plaćanja:
Pronađite donju i gornju cijenu igre. Da li igra ima tačku sedla?

Rješenje.

IN A	U 1	U 2
A 1	1	-1	-1
A 2	-1	1	1
	1	1	-1 1

α = -1, β = 1, tj. A neće izgubiti više od 1, i B neće izgubiti više od 1. Pošto je α ≠ β, igra nema sedla. U ovoj igri nema ravnotežnog položaja, a optimalno rješenje se ne može naći u čistim strategijama.

Primjer. Pronađite donju cijenu igre, gornju cijenu igre, odredite sedla, optimalne čiste strategije i cijenu igre (ako postoje).

Razmotrimo uparenu konačnu igru. Pustite igrača A ima m lične strategije, koje označavamo A 1 , A 2 , …,A m . Pustite igrača IN dostupan n lične strategije, označimo ih IN 1 ,IN 2 , …, IN n. Kažu da je igra imena dimenzija mn. Kao rezultat toga što igrači biraju bilo koji par strategija

A i I B i (I = 1, 2, …, m; j = 1, 2, …, n)

ishod igre je jasno određen, tj. pobjeda a ij igrač A(pozitivan ili negativan) i gubitak (- a ij) igrač IN. Pretpostavimo da su vrijednosti a ij poznat po bilo kojem paru strategija ( Ai,Bj). Matrix R = (A ij), i = 1, 2, …, m; j = 1, 2, …, n, čiji su elementi dobici koji odgovaraju strategijama A i I B j, zvao plaćanje matrica ili matrica igre. Opšti izgled takve matrice prikazan je u tabeli. 1. Redovi ove tabele odgovaraju strategijama igrača A, a kolone su strategije igrača IN.

Kreirajmo matricu isplate za sljedeću igru.

Tabela 1

A j B i
		a 1n
		a 2n

	a m 1	a mn

1. Igra pretraživanja.

Player A može se sakriti u jednom od skloništa (I i II); igrač IN tražim igrača A, a ako se nađe, dobija kaznu od 1 den. jedinice od A, inače plaća igraču A 1 dan jedinice Za igru je potrebno izgraditi matricu plaćanja.

Rješenje. Da biste sastavili matricu plaćanja, trebali biste analizirati ponašanje svakog igrača. Player A mogu se sakriti u sklonište I - ovu strategiju označavamo sa A 1 ili skloništu II - strategija A 2 .

Player IN može potražiti prvog igrača u skloništu I - strategija IN 1, odnosno u skloništu II - strategija IN 2. Ako igrač A nalazi se u trezoru I i tamo ga otkriva igrač IN, tj. implementirano je nekoliko strategija ( A 1 , IN 1), zatim plejer A plati kaznu, tj. A 11 = -1. slično dobijamo A 22 = -1 (A 2 , IN 2). Očigledno je da strategije ( A 1 , IN 1) i ( A 2 , IN 2) dati igraču A isplata je 1, dakle A 12 = A 21 = 1.

Početak problematičnog stanja; - završetak rješenja problema.

Dakle, za igru „pretraživanja“ veličine 2 2 dobijamo matricu isplate

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 jednom od strategija B j , za koji je isplata za igrača A minimalno (igrač IN nastoji da "povredi" igrača A).

Označimo sa A i najmanji dobitak igrača A prilikom odabira strategije A i za sve moguće strategije igrača IN(najmanji broj u i-ti red matrice plaćanja), tj.

A ij = i . (1.1)

među svim brojevima? i (i = 1, 2, …, m) izaberite najveće: ? = ? i. Hoćemo li to nazvati? niža cijena igre, ili maksimalni dobici (maximin). Ovo je zagarantovana pobjeda igrača A za bilo koju strategiju igrača IN. dakle,

? = a ij . (1.2)

Strategija koja odgovara maksiminu se zove maximin strategija. Player IN zainteresovani za smanjenje dobitaka igrača A; odabir strategije B j, uzima u obzir maksimalnu moguću dobit za A. Označimo

? j = a ij (1.3)

Među svim brojevima? j Hoćemo li izabrati najmanju? = ? j i nazovimo to? najviša cijena igre ili minimaks pobjeda (minimax). Ovo je zagarantovan gubitak za igrača IN. dakle,

? = a ij . (1.4)

Poziva se strategija koja odgovara minimaksu minimax strategija.

Princip koji nalaže igračima da izaberu "najopreznije" minimax i maximin strategije naziva se princip minimaksa. Ovaj princip proizilazi iz razumne pretpostavke da svaki igrač teži da postigne cilj suprotan cilju njegovog protivnika. Odredimo donju i gornju cijenu igre i odgovarajuće strategije u problemu 1. Razmotrite matricu plaćanja

od problema 1. Prilikom odabira strategije A 1 (prvi red matrice) je minimalni dobitak? 1 = min(-1;1) = -1 i odgovara strategiji? 1 igrač IN. Prilikom odabira strategije A 2 (drugi red matrice) je minimalni dobitak? 2 = min(1;-1) = -1, postiže se strategijom IN 2 .

Garantujete sebi maksimalnu pobedu za bilo koju strategiju igrača IN, tj. niža cijena za igru? = max(? 1 , ? 2) = max(-1,-1) = -1, igrač A može izabrati bilo koju strategiju: A 1 ili A 2, tj. bilo koja od njegovih strategija je maksiminska.

Odabir strategije IN 1 (kolona 1), igrač IN razumije da igrač Aće odgovoriti strategijom A 2 da maksimizirate svoj dobitak (gubitak IN). Dakle, igrač je maksimalni gubitak IN prilikom odabira strategije IN Je li 1 jednako? 1 = max(-1;1) = 1.

Slično, maksimalni gubitak igrača IN(pobjeda A) prilikom odabira strategije IN 2 (kolona 2) jednako? 2 = max(1;-1) = 1.

Dakle, za bilo koju strategiju igrača A garantovan minimalni gubitak igrača IN jednak? = min (? 1; ? 2) = min(1;1) = 1 - najviša cijena igre.

Bilo koja strategija igrača IN je minimax. Nakon dodavanja tabele 1 red? j i kolona? i, dobijamo sto. 2. Na raskrsnici dodatnih redova i kolona upisaćemo gornju i donju cijenu igara.

Tabela 2.

A j B i			? i


? j

U problemu 1 , o kojoj smo gore govorili, da li se gornja i donja cijena igre razlikuju? ? ?.

Ako su gornja i donja cijena igre iste, onda je ukupna vrijednost gornje i donje cijene igre? = ? = v se poziva čist po cijenu igre, ili po cijenu igre. Minimaks strategije koje odgovaraju cijeni igre su optimalne strategije, a njihova ukupnost je optimalno odluka, ili odluka igrice. U ovom slučaju igrač A dobija zagarantovani maksimum (nezavisno od ponašanja igrača) IN) isplata v, i igrač IN postiže zagarantovani minimum (bez obzira na ponašanje igrača A) gubitak v. Kažu da je rješenje igre stabilno, tj. Ako se jedan igrač pridržava svoje optimalne strategije, onda ne može biti isplativo za drugog da odstupi od svoje optimalne strategije.

Par čistih strategija A j I B i daje optimalno rješenje igri ako i samo ako je odgovarajući element a ij je i najveći u svojoj koloni i najmanji u svom redu. Ova situacija, ako postoji oan, zove se sedlo(slično površini sedla, koja se u jednom smjeru savija prema gore, a u drugom prema dolje).

Označimo A * I B * - par čistih strategija kojima se postiže rješenje igre u problemu sa sedlom. Hajde da uvedemo funkciju isplate prvog igrača za svaki par strategija: R(A i , B j) = a ij. Zatim, iz uslova optimalnosti u tački sedla, imamo dvostruka nejednakost: R(A i , B *) ? R(A * , B * ) ? R(A * , B j), što važi za sve i = 1, …, m; j = 1, …, n. zaista, izbor strategije A * prvi igrač sa optimalnom strategijom B * drugi igrač maksimizira minimalnu moguću isplatu: R(A * , B * ) ? R(A * , B).

2. odrediti donju i gornju cijenu igre datu matricom plaćanja

P = 0,9 0,7 0,8

Tabela 3.

A i B j

Da li igra ima tačku sedla?

Rješenje. Pogodno je sve proračune izvršiti u tabeli, u koju se pored matrice P unosi i kolona? i i linija? j(Tabela 3). Analiziranje redova matrice (strategije igrača A), popuniti kolonu? i: ? 1 = 0,5, ? 2 = 0,7, ? 3 = 0,6 - minimalni brojevi u redovima 1, 2, 3. Slično? 1 = 0,9, ? 2 = 0,7, ? 3 = 0,8 - maksimalni brojevi u kolonama 1, 2, 3 respektivno.

Najniža cijena igre? = ? i= max (0,5; 0,7; 0,6) = 0,7 ( najveći broj u koloni ? i) i najviša cijena igre? = ? j= min(0,9, 0,7, 0,8) = 0,7 (najmanji broj u redu? j). Ove vrijednosti su jednake, tj. ? = ?, a postižu se korištenjem istog para strategija ( A 2 , IN 2). Dakle, igra ima sedlo ( A 2 , IN 2) i cijena igre = 0,7.