Teorija igara je matematička disciplina čiji su predmet proučavanja metode odlučivanja u konfliktnim situacijama.

Situacija se zove sukob, ako se sukobe interesi više (obično dvoje) osoba koje teže suprotstavljenim ciljevima. Svaka strana može preduzeti niz aktivnosti kako bi ostvarila svoje ciljeve, pri čemu uspjeh jedne strane znači neuspjeh druge.

U ekonomiji se vrlo često javljaju konfliktne situacije (odnosi između dobavljača i potrošača, kupca i prodavca, bankara i klijenta). Konfliktne situacije se javljaju u mnogim drugim oblastima.

Konfliktnu situaciju generiše razlika u interesima partnera i želja svakog od njih da donese optimalne 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 voditi računa o unaprijed nepoznatim odlukama koje će partneri donijeti.

Obično je konfliktne situacije teško direktno analizirati zbog brojnih sekundarnih faktora koji su uključeni. Da bi se omogućila matematička analiza konfliktne situacije, potrebno je pojednostaviti je, uzimajući u obzir samo glavne faktore. Pojednostavljeni formalizovani model konfliktne situacije se naziva igra, strane uključene u sukob - igrači, a ishod sukoba je pobijediti. Obično se dobitak (ili poraz) može kvantifikovati; na primjer, možete procijeniti gubitak kao nula, pobjedu kao jedan, a neriješeno kao 1/2.

Igra je zbirka pravila, koji opisuje ponašanje igrača. Svaki slučaj igranja igre na neki specifičan način od početka do kraja predstavlja igra igra. 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- ovo je također izbor jedne od mnogih opcija, ali ovdje opciju ne bira igrač, već neki mehanizam slučajni odabir(bacanje novčića, biranje karte iz promešanog špila).

Strategija Igračem se naziva skup pravila koja određuju izbor njegovih akcija pri svakom ličnom potezu, ovisno o trenutnoj situaciji.

Ako se igra sastoji samo od ličnih poteza, onda je ishod igre određen ako svaki igrač odabere svoju strategiju. Međutim, ako igra ima nasumične poteze, tada će igra biti vjerovatnoće po prirodi i izbor strategija igrača još uvijek neće konačno odrediti ishod igre.

Da bi odlučiti igre, ili pronaći rješenje za igru, treba izabrati strategiju za svakog igrača koja zadovoljava uvjet optimalnost, 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 strategije se nazivaju optimalnim. Optimalne strategije moraju zadovoljiti uslov stabilnosti, tj. Mora da je nepovoljno za bilo kojeg igrača da napusti svoju strategiju u ovoj igri.

Cilj teorije igara je odrediti optimalna strategija za svakog igrača.

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

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

Ishod utakmice je jasno određen, tj. dobitke a ij igrač A (pozitivan ili negativan) i gubitak ( - a ij ) igrač IN . Pretpostavimo da su vrijednosti OU poznat po bilo kojem paru strategija (A i ,B j ). Matrix , čiji su elementi dobici koji odgovaraju strategijama A i I Bj , zvao matrica plaćanja ili matrica igre. Opšti oblik takva matrica je predstavljena u tabeli 3.1.

Tabela 3.1

Redovi ove tabele odgovaraju strategijama igrača A , a kolone su igračeve strategije IN . Kreirajmo matricu plaćanja za sledeća utakmica.

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 , ..., Am . 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 αi , najmanji dobitak igrača A prilikom odabira strategije A i za sve moguće strategije igrača IN (najmanji broj V i red matrice plaćanja), tj.

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

Strategija koja odgovara minimaxu naziva se 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.

Ako se gornja i donja cijena igre poklapaju, onda opšte značenje gornje i donje cijene igre α = β = v pozvao cisto po cijenu igre , ili po cijenu igre . Minimaks strategije koje odgovaraju cijeni igre su optimalne strategije, a njihova ukupnost je optimalno rešenje , ili rešenje za igru. U ovom slučaju igrač A dobija zagarantovani maksimum (nezavisno od ponašanja igrača) IN ) dobitak v , i plejer IN postiže zagarantovani minimum (bez obzira na ponašanje igrača A ) gubitak v . Kažu da rješenje za igru ​​ima stabilnost , tj. Ako se jedan igrač drži svoje optimalne strategije, onda ne može biti isplativo za drugog da odstupi od svoje optimalne strategije.

Par čistih strategija A i I Bj 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, zove se sedlo (slično površini sedla, koja se u jednom smjeru savija prema gore, a u drugom prema dolje).

Osnovni koncepti modela upravljanja zalihama.

I u poslovanju iu proizvodnji, uobičajena je praksa održavati razumne zalihe materijalna sredstva ili komponente kako bi se osigurao kontinuitet proizvodni proces. Tradicionalno, zalihe se posmatraju kao neizbježni trošak, pri čemu su nivoi zaliha preniski što dovode do skupih obustava proizvodnje, a nivoi zaliha koji su previsoki dovode do “smrti” kapitala. Cilj upravljanja zalihama je da se utvrdi nivo zaliha koji balansira dva navedena ekstremna slučaja.

Razmotrimo glavne karakteristike modela upravljanja zalihama.

Potražnja. Potražnja za zalihama proizvoda može biti deterministički(u najjednostavnijem slučaju - konstanta u vremenu) ili nasumično. Slučajnost potražnje opisuje se ili slučajnim momentom potražnje ili slučajnim iznosom potražnje u determinističkim ili slučajnim vremenima.

Dopuna skladišta. Dopunjavanje skladišta može se vršiti ili periodično u određenim intervalima, ili po trošenju zaliha, tj. svodeći ih na određeni nivo.

Količina narudžbe. Uz periodično dopunjavanje i povremeno trošenje zaliha, količina narudžbe može zavisiti od stanja uočenog u trenutku narudžbe. Narudžbina se obično postavlja za isti iznos kada zaliha dostigne zadati nivo - tzv narudžbe bodova.

Vrijeme dostave. Idealizirani modeli upravljanja zalihama pretpostavljaju da se naručena dopuna odmah isporučuje u skladište. Drugi modeli uzimaju u obzir kašnjenja u isporukama za fiksni ili nasumični vremenski period.

Trošak dostave. U pravilu se pretpostavlja da se trošak svake isporuke sastoji od dvije komponente - jednokratnih troškova koji ne ovise o obimu naručene serije i troškova koji (najčešće linearno) zavise od količine serije.

Troškovi skladištenja. U većini modela upravljanja zalihama, zapremina skladišta se smatra praktično neograničenom, a zapremina uskladištenih zaliha služi kao kontrolna varijabla. Pretpostavlja se da se naplaćuje određena naknada za čuvanje svake jedinice zaliha po jedinici vremena.

Kazna za nedostatak. Svako skladište se kreira kako bi se spriječile nestašice određene vrste proizvoda u servisiranom sistemu. Nedostatak zaliha u pravo vrijeme dovodi do gubitaka povezanih sa zastojima opreme, neredovnom proizvodnjom itd. Ovi gubici se nazivaju kazna za deficit.

Nomenklatura dionica. U najjednostavnijim slučajevima pretpostavlja se da skladište skladišti zalihe sličnih proizvoda ili homogenog proizvoda. U više teški slučajevi se razmatra zaliha sa više stavki.

Struktura skladišnog sistema. Najpotpunije razvijeni matematički modeli jednog skladišta. Međutim, u praksi postoje i složenije strukture: hijerarhijski sistemi skladišta sa različitim periodima dopune i rokovima isporuke narudžbi, sa mogućnošću razmene zaliha između skladišta istog hijerarhijskog nivoa, itd.

Kriterijum za efektivnost usvojene strategije upravljanja zalihama je funkcija troškova (troškovi), predstavlja ukupne troškove snabdijevanja zalihama proizvoda, njegovog skladištenja i troškove kazni.

Upravljanje zalihama se sastoji u pronalaženju strategije dopune i potrošnje zaliha u kojoj funkcija troškova poprima minimalnu vrijednost.

Neka funkcije , i izraziti redom:

obnavljanje zaliha,

Potrošnja zaliha,

Potražnja za proizvodom koji se skladišti

na određeno vreme.

Modeli upravljanja zalihama obično koriste derivate ovih funkcija s obzirom na vrijeme , , , nazvani u skladu s tim,

Predavanje 4

Tema: “ELEMENTI TEORIJE IGRE”

Koncept modela igre

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, odnos 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.

Donji i top cijena igrice

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 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 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 zagarantovana pobeda igrač 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.

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 sedlo (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).

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 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, onda 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 dobitak 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 redova je 2, ovo je niža cijena igre, njoj odgovara prvi red, dakle, maksimalna strategija prvog igrača je prva. Najmanji od najvećih elemenata kolona je 5, ovo je gornja cijena igre, druga kolona joj odgovara, dakle, minimax strategija drugog igrača je druga.

Sada kada smo naučili 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, minimaks 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 donje 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čekivana 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 maksiminskim i minimaksnim zapisima, 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 svesti matričnu igru ​​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 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 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

.

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.

Igračeva strategija je plan kojim on donosi izbore u svakoj mogućoj situaciji i daje sve moguće činjenične informacije. Naravno, igrač donosi odluke kako igra napreduje. Međutim, teoretski se može pretpostaviti da sve ove odluke igrač donosi unaprijed. Tada cjelokupnost ovih odluka čini njegovu strategiju. U zavisnosti od broja mogućih strategija, igre se dijele na konačne i beskonačne. Zadatak teorije igara je da razvije preporuke za igrače, odnosno da odredi optimalnu strategiju za njih. Optimalna strategija je ona koja, kada se igra ponavlja mnogo puta, daje datom igraču maksimalni mogući prosječni dobitak.

Najjednostavniji tip strateške igre je igra sa nultom sumom za dvije osobe (zbir isplata strana je nula). Igra se sastoji od dva poteza: igrač A bira jednu od svojih mogućih strategija Ai (i = 1, 2, m), a igrač B bira strategiju Bj (j = 1, 2, ., n), a svaki izbor se vrši sa potpuno neznanje o izboru drugog igrača.

Cilj igrača A je da maksimizira funkciju φ (Ai, Bj), a cilj igrača B je da minimizira istu funkciju. Svaki igrač može izabrati jednu od varijabli o kojoj ovisi vrijednost funkcije. Ako igrač A odabere neku od strategija Ai, to samo po sebi ne može utjecati na vrijednost funkcije φ (Ai, Bj).

Utjecaj Ai na vrijednost φ (Ai, Bj) je neizvjestan; Sigurnost se javlja tek nakon izbora, na osnovu principa minimiziranja φ (Ai, Bj), od strane drugog igrača varijable Bj. U ovom slučaju, Bj određuje drugi igrač. Neka je φ (Ai, Bj)= aij. Kreirajmo matricu A:

Redovi matrice odgovaraju strategijama Ai, kolone strategijama Bj. Matrica A se naziva matrica isplate ili igre. Element aij matrice je isplata igrača A ako je izabrao strategiju Ai, a igrač B je izabrao strategiju Bj.

Neka igrač A odabere neku strategiju Ai; onda u najgorem slučaju (na primjer, ako izbor postane poznato igraču C) on će dobiti isplatu jednaku min aij. Predviđajući ovu mogućnost, igrač A mora odabrati strategiju kako bi maksimizirao svoju minimalnu isplatu:

a = max min aij

Vrijednost a - zagarantovani dobitak igrača A - naziva se niža cijena igre. Strategija Ai0 koja osigurava dobijanje a naziva se maximin.

Igrač B, pri odabiru strategije, polazi od sljedećeg principa: pri odabiru određene strategije Bj, njegov gubitak neće premašiti maksimum vrijednosti elemenata j-te kolone matrice, tj. manji ili jednak max aij

Uzimajući u obzir skup max aij za različita značenja j, igrač B, će prirodno izabrati vrijednost j koja minimizira njegov maksimalni gubitak β:

β = min miax aij

Vrijednost β naziva se gornja cijena igre, a strategija Bj0 koja odgovara isplati β naziva se minimax.

Stvarni dobici igrača A, uz razumne akcije partnera, ograničeni su donjom i gornjom cijenom igre. Ako su ovi izrazi jednaki, tj.