Igra se zove igra sa nultom sumom, ili antagonistički, 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- dobici jednog od igrača, b- dobitak 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 je nasumično odabrana radnja (na primjer, odabir karte iz promiješanog špila). U svom radu razmatraću 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 krajnji, ako svaki igrač ima konačan broj strategija, i beskrajno- inače.

Da biste riješili igru, odnosno pronašli rješenje za igru, trebate odabrati strategiju za svakog igrača koja zadovoljava uvjet optimalnost, tj. 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 strategije su pozvani optimalno. Optimalne strategije takođe mora zadovoljiti stanje stabilnosti, tj. Mora da je nepovoljno za bilo kojeg igrača da napusti svoju strategiju u ovoj igri.

Svrha teorije igara: Određivanje optimalne strategije za svakog igrača. Prilikom odabira optimalne strategije, prirodno je pretpostaviti da se oba igrača ponašaju razumno u smislu svojih interesa.

Zovu se antagonističke igre u kojima svaki igrač ima konačan skup strategija matrične igre. Ovaj naziv se objašnjava sljedećom mogućnošću opisa igara ove vrste. Sastavljamo pravokutnu tabelu u kojoj redovi odgovaraju strategijama prvog igrača, stupci strategijama drugog, a ćelije tablice koje se nalaze na sjecištu redova i stupaca odgovaraju situacijama u igri. Ako dobitak prvog igrača u odgovarajućoj situaciji stavimo u svaku ćeliju, dobijamo opis igre u obliku određene matrice. Ova matrica se zove matrica igre ili matrica isplate.

Ista igra sa konačnim nultom sumom može se opisati različitim matricama, koje se međusobno razlikuju samo po redoslijedu redova i stupaca.

Razmotrite igru m x 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 Bj, 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 V i-th liniju platne matrice), tj.

a i = a ij , j = 1,..., n.

Među svim brojevima a i (i = 1,2, ... , m ) izaberite najveću. Hajde da pozovemo a dnu po cijenu igre ili maksimalni dobitak (maximin). Ovo zagarantovana pobeda igrač A za bilo koju strategiju igrača IN. Stoga, , i = 1,... , m; j = 1,..., n

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

Označimo: β i = a ij , i = 1,... , m

Među svim brojevima Bj izaberite najmanju i pozovite je β najviša cijena igre ili minimalna pobjeda (minimax). Ovo je zagarantovan gubitak za igrača IN.

dakle, i = 1,... , m; j = 1,..., n.

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 od cilja njegovog protivnika.

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 voditi računa o unaprijed nepoznatim odlukama 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 pojedinoj 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 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 oblik takva matrica je predstavljena 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 u i -i linija matrice plaćanja), tj.

, j =1,…n . (1)

Među svim brojevima Odaberimo najveće: . Hajde da pozovemo najniža cijena igre, ili maksimalni dobici (maximin). Ovo zagarantovan dobitak za 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 minimax pobjeda (minimax). Ovo zagarantovan gubitak igrača IN. stoga,

(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 od cilja njegovog protivnika.

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) minimalni dobici jednaki 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 jednak 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 garantovan minimalni gubitak igrača IN jednaka najvišoj cijeni igre.

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

	-1		-1
		-1	-1
		1

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

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 igračeve strategije 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 mogu 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 minimax 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 od cilja njegovog protivnika. Odredimo donju i gornju cijenu igre i odgovarajuće strategije u problemu 1. Razmotrimo 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čev maksimalni gubitak je 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 cisto 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 redom.

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.

Zamislite igru ​​s matricom

Slovo i označavaće broj naše strategije, a slovo broj strategije neprijatelja.

Odbacimo pitanje o mješovite strategije a mi ćemo za sada uzeti u obzir samo čiste. Hajde da postavimo zadatak: da odredimo najbolju među našim strategijama, analizirajmo svaku od njih uzastopno, počevši od i završavajući sa, moramo očekivati ​​da će neprijatelj na nju odgovoriti strategijom za koju je naš dobitak minimalan. Nađimo minimalni broj u redu i označimo ga

(znak označava minimalnu vrijednost ovog parametra za sve moguće

Zapišimo brojeve (minimume reda) pored matrice s desne strane u obliku dodatne kolone:

Prilikom odabira strategije moramo računati na to da ćemo kao rezultat razumnih akcija neprijatelja samo pobijediti. maksimum. Označimo ovu maksimalnu vrijednost

ili. uzimajući u obzir formulu (4.1),

Vrijednost a naziva se niža cijena igre, inače maksiminska isplata ili maksimin. Strategija igrača A koja odgovara maksiminu a naziva se maksiminska strategija.

Očigledno, ako se pridržavamo maksiminske strategije, onda nam je bez obzira na ponašanje neprijatelja zagarantovana pobjeda, barem ne manja od a. Stoga se vrijednost a naziva „niža cijena igre“. Ovo je zagarantovani minimum koji možemo sebi obezbediti pridržavajući se naše najopreznije („reosiguranja“) strategije.

Očigledno, slično razmišljanje može se izvesti i za protivnika B. On je zainteresiran da svede naše dobitke na minimum, to znači da mora proučiti sve svoje strategije, ističući maksimalnu dobitnu vrijednost za svaku od njih matrica (4.2) maksimalne vrijednosti po stupcima:

i pronađite njihov minimum:

(4.4)

Vrijednost se naziva gornjom cijenom igre, inače minimaks dobitka ili minimaks. Protivnikova pobjednička strategija naziva se njegova minimaks strategija. Držeći se svoje najopreznije minimaks strategije, protivniku je zagarantovano da u svakom slučaju neće izgubiti više od p.

Princip opreza, koji nalaže da igrači odaberu odgovarajuće strategije (maksimin i minimaks), fundamentalan je u teoriji igara i naziva se princip minimaksa. Iz pretpostavke proizilazi da je svaki igrač razuman, nastojeći postići cilj suprotan od protivničkog. „Najopreznije“ maksiminske i minimaks strategije se često nazivaju „minimaks strategijama“.

Odredimo donju i gornju cijenu igre, kao i minimaks strategije, za tri primjera o kojima smo govorili u prethodnom paragrafu.

Primjer 1. (Igra pretraživanja). Određivanjem minimuma reda i maksimuma kolone dobijamo

Budući da su vrijednosti, konstantne i jednake -1, respektivno, a donja i gornja cijena igre su također jednake -1 i

Bilo koja strategija igrača A je njegova maksimalna strategija, a svaka strategija igrača B je njegova minimaks strategija. Zaključak je trivijalan: pridržavajući se bilo koje od svojih strategija, igrač A može garantovati da neće izgubiti više od 1 rublje; Igrač B može garantovati isto za bilo koju od svojih strategija.

Primjer 2. (Igra sa tri prsta). Ispisivanjem minimuma redova i maksimuma kolona, ​​naći ćemo donju cijenu igre i gornju (u tabeli je podebljano). Naša maksimalna strategija (sistematskom primjenom garantiramo da ćemo pobijediti ne manje od -3, tj. nećemo izgubiti više od 3).

Neprijateljeva minimaks strategija je bilo koja od strategija, koristeći ih sistematski, on može garantovati da neće odustati od više od 4. Ako odstupimo od naše maksiminske strategije (na primjer, izaberemo A 2), onda neprijatelj može "kazniti" nas za ovo primjenom i smanjenjem naše pobjede i povlačenje protivnika od njegove minimaks strategije možemo “kazniti” povećanjem njegovog gubitka na 6.

Obratimo pažnju na činjenicu da su minimaks strategije u u ovom slučaju nije stabilan. Zaista, neka, na primjer, protivnik odabere jednu od svojih minimaks strategija i drži je se. Naučivši ovo, preći ćemo na strategiju i pobijediti 4. Neprijatelj će odgovoriti strategijom i pobijediti 5; na to ćemo mi, zauzvrat, odgovoriti strategijom i dobiti 4 itd. Dakle, situacija u kojoj oba igrača koriste svoje minimaks strategije je nestabilna i može biti narušena primljenim informacijama o strategiji koju koristi druga strana. Međutim, takva nestabilnost se ne uočava uvijek; To ćemo vidjeti u sljedećem primjeru.

Primjer 3. (Igra “oružje i zrakoplov”). Odredite minimum redova i maksimum kolona:

U ovom slučaju, donja cijena igre jednaka je gornjoj:

Minimax strategije su stabilne: ako se jedan od igrača pridržava svoje minimaks (maksimin) strategije, onda drugi igrač ne može poboljšati svoju poziciju odstupanjem od svoje.

Dakle, vidimo da postoje igre za koje je donja cijena jednaka gornjoj:

Ove igre zauzimaju posebno mjesto u teoriji igara i nazivaju se igrama na sedlu. U matrici takve igre postoji element koji je i minimalan u svom redu i maksimalan u svom stupcu; takav element se naziva sedlo“ (po analogiji sa sedlom na površini, gde se minimum postiže duž jedne koordinate, a maksimum duž druge).

Ukupna vrijednost donje i gornje cijene igre

nazvana neto cijena igre.

Točka sedla odgovara paru minimaksnih strategija, te se strategije nazivaju optimalnim, a njihova kombinacija se naziva rješenjem igre. 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 svoje optimalne (takvo odstupanje će ili ostaviti situaciju nepromijenjenom ili je pogoršati).

Zaista, u igri sa sedlom, neka se igrač A drži svoje optimalne strategije, a igrač B drži svoje. Sve dok je to tako, isplata ostaje konstantna i jednaka cijeni igre v. Pretpostavimo sada da je B odstupio od svoje optimalne strategije. Pošto je v minimalni element u svom redu, takvo odstupanje ne može biti korisno za B; Isto tako, za A, ako se B pridržava svoje optimalne strategije, odstupanje od njegove ne može biti od koristi.

Vidimo da su za igru ​​sa sedlom, minimaks strategije stabilne. Par optimalnih strategija u igri sa sedlom je kao ravnotežna pozicija: odstupanje od optimalne strategije uzrokuje promjenu isplate koja je nepovoljna za igrača koji odstupa i prisiljava ga da se vrati svojoj optimalnoj strategiji.

Neto cijena igre v u igri sa sedlom je vrijednost isplate koju, u igri protiv razumnog protivnika, igrač A ne može povećati, a igrač B ne može smanjiti.

Imajte na umu da može postojati više od jedne sedla u matrici plaćanja, ali nekoliko.

Na primjer, postoji šest sedla u matrici, sa opšte značenje dobici i odgovarajući parovi optimalnih strategija: Lako je dokazati (nećemo to učiniti) da ako postoji nekoliko sedla u matrici igre, onda sve daju istu vrijednost isplate.

Primjer. Strana A – sistemi protivvazdušne odbrane – brani deo teritorije od vazdušnog napada, ima dva topa br. 1 i br. 2, čija se područja pokrivanja ne preklapaju (slika 9.1). Svako oružje može pucati samo na avion koji prolazi kroz njegovo područje pokrivanja, ali da bi to učinio mora ga pratiti unaprijed (prije nego što meta uđe u područje) i generirati podatke o ciljanju, ako je meta pogođena s vjerovatnoćom Strana B ima dva aviona, od kojih se svaki može usmjeriti u bilo koju zonu. djelovanja topa br. 1, a meta br. 2 usmjerena je u domet djelovanja topa br. 2. Međutim, nakon donošenja odluke o ciljanju, svaka meta može manevrirati korištenjem „manevra obmane“ (vidi isprekidane strelice na slici 9.1).

Zadatak strane A je da maksimizira, a zadatak strane B je da minimizira broj pogođenih meta Pronađi rješenje za igru ​​(optimalne strategije strana).

Rješenje. Strana A (oružje protivvazdušne odbrane) ima četiri moguće strategije - svaki top prati metu koja ide u svoju zonu,

Puške prate mete "poprečno" (svako prati metu koja ide prema susjedu),

Oba topa prate metu br. 1,

Oba topa prate metu br. 2. Strana B (zrakoplov mete) također ima četiri strategije:

Oba netaknuta ne mijenjaju smjer,

Obje mete koriste prevaru.

Prva meta koristi manevar obmane, ali druga ne,

Druga meta koristi manevar obmane, ali prva ne.

Rezultat je igra 4X4, čija je matrica data u tabeli:

Pronalaženjem minimuma redova i maksimuma kolona, ​​uvjeravamo se da je donja cijena igre jednaka gornjoj cijeni igre: to znači da igra ima sedlo i rješenje u čistim strategijama, što dovodi do neto cijene igre. U ovom slučaju ne postoji jedna, već četiri sedla. Svaka od njih odgovara paru optimalnih strategija koje daju rješenje za igru izgube jedan avion, a nikakvi trikovi im neće pomoći da izgube manje, a znači protivvazdušna odbrana - oborite više od jednog aviona Ovo stanje ravnoteže se postiže kada obje strane koriste svoje optimalne strategije: oba topova prate isti avion (bilo koji), i avion se šalje nakon distribucije cilja u istu zonu (bilo koju)

Klasa igara koje imaju sedlo veoma je interesantna i sa teorijske i sa praktične tačke gledišta. To uključuje, posebno, sve takozvane „igre sa potpune informacije».

Igra sa potpunim informacijama je igra u kojoj svaki igrač, svakim ličnim potezom, zna rezultate svih prethodnih poteza – i ličnih i nasumičnih. Primjeri igara sa potpunim informacijama uključuju: dame, šah, poznata igra u "takovima i prstima" itd.

U teoriji igara je dokazano da svaka igra sa potpunim informacijama ima sedlo i stoga rješenje u čistim strategijama. Drugim riječima, u svakoj igri sa potpunim informacijama postoji par optimalnih strategija na obje strane koje daju stabilnu isplatu jednaku neto cijeni igre. Ako se igra sa potpunim informacijama sastoji samo od ličnih poteza, onda kada svaka strana primijeni svoju optimalnu strategiju, igra uvijek treba završiti s dobro definiranim ishodom jednakim cijeni igre

Kao primjer, dajmo sledeća utakmica sa kompletnim informacijama. Dva igrača naizmjenično stavljaju identične novčiće na okrugli sto, nasumično birajući poziciju novčića (međusobno preklapanje novčića nije dozvoljeno). Pobjednik je onaj koji ubaci zadnji novčić (kada više nema mjesta za druge). Nije teško uočiti da je ishod ove igre unaprijed određen i da postoji određena strategija koja osigurava sigurnu pobjedu za igrača koji prvi ubaci novčić. Naime, on mora prvi put staviti novčić u centar stola, a zatim na svaki potez protivnika odgovoriti simetričnim potezom. Očigledno, kako god se neprijatelj ponašao, ne može izbjeći gubitak. Stoga igra ima smisla samo za ljude koji ne znaju njeno rješenje. Potpuno ista situacija je i sa šahom i drugim igrama sa potpunim informacijama; bilo koja od ovih igara ima sedlo i, prema tome, rješenje koje svakom igraču ukazuje na njegovu optimalnu strategiju, tako da igra ima smisla samo dok je rješenje nepoznato. Rješenje šahovska igra nije pronađena (i malo je vjerovatno da će biti pronađena u doglednoj budućnosti) samo zato što je broj strategija (kombinacija poteza) u šahu prevelik da bi se mogla konstruirati matrica isplate i pronaći sedlo u njoj.

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 odabiremo 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 igrač treba da odabere? 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 od cilja 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 točku sedla ( A 3, B 3). U ovom slučaju, broj α = β se naziva (čistim) 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 - stabilnost . 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- avion pogođen. 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 dodatnom stupcu 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 i optimalno rešenje ne mogu se naći u čistim strategijama.

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