≡× MENI

• POP
• Windows
• Antivirus
• Antivirus
• Graficka umjetnost

antagonistička igra. Rješavanje matričnih antagonističkih igara Principi rješavanja matričnih antagonističkih igara

Teorija igara je teorija matematičkih modela donošenja odluka u uslovima konflikta ili neizvjesnosti. Pretpostavlja se da akcije strana u igri karakterišu određene strategije – skupovi akcionih pravila. Ako dobitak jedne strane neminovno vodi gubitku druge strane, onda govore o antagonističkim igrama. Ako je skup strategija ograničen, onda se igra naziva matrična igra i rješenje se može dobiti vrlo jednostavno. Rješenja dobivena uz pomoć teorije igara korisna su u izradi planova u slučaju mogućeg protivljenja konkurenata ili neizvjesnosti u vanjskom okruženju.

Ako je bimatrična igra antagonistička, tada je matrica isplate igrača 2 u potpunosti određena matricom isplate igrača 1 (odgovarajući elementi ove dvije matrice razlikuju se samo po predznacima). Stoga je bimatrična antagonistička igra u potpunosti opisana jednom matricom (matrica isplate igrača 1) i, shodno tome, naziva se matrična igra.

Ova igra je antagonistička. U njemu j = x2 - O, P i R (O, O] \u003d H (P, P) = -I i R (O, P) = R (P, O) = 1, ili u matričnom obliku o str

Neka je neka klasa igara G "zrcalno zatvorena", tj. zajedno sa svakom od svojih igara sadrži zrcalnu izomorfnu igru ​​(pošto su sve igre koje su zrcalno izomorfne datoj su jedna drugoj izomorfne, u skladu sa ovim što je rečeno, možemo govoriti o jednoj zrcalnoj izomorfnoj igri). Takva klasa je, na primjer, klasa svih antagonističkih igara ili klasa svih matričnih igara.

Podsjećajući na definiciju prihvatljivih situacija u antagonističkoj igri, dobivamo da je situacija (X, Y) u mješovitom proširenju matrične igre prihvatljiva za igrača 1 ako i samo ako je za bilo koji x G x nejednakost

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

Dakle, početni termini i oznake teorije opštih antagonističkih igara poklapaju se sa odgovarajućim terminima i oznakama teorije matričnih igara.

Za konačne antagonističke (matrične) igre, postojanje ovih ekstrema smo dokazali u 10. poglavlju. 1, a cijela poenta je bila uspostaviti njihovu jednakost, ili barem pronaći načine za prevazilaženje njihove nejednakosti.

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

Ali svaka konačna (matrična) igra može se proširiti na beskonačnu igru, na primjer, pružanjem svakom igraču bilo kojim brojem dominiranih strategija (vidi 22. poglavlje 1). Očigledno, takvo proširenje igračevog skupa strategija zapravo neće značiti proširenje njegovih mogućnosti, a njegovo stvarno ponašanje u proširenoj igri ne bi trebalo da se razlikuje od ponašanja u originalnoj igri. Tako smo odmah dobili dovoljan broj primjera beskonačnih antagonističkih igara koje nemaju sedla. Ima i takvih primjera.

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

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

Konačno, imajte na umu da je skup svih mješovitih strategija igrača 1 u proizvoljnoj antagonističkoj igri, kao u matrici

Čak i razmatranje antagonističkih igara pokazuje da veliki broj takvih igara, uključujući one sa konačnim, matrične igre imaju ravnotežne situacije ne u originalnim, čistim strategijama, već samo u generaliziranim, mješovitim strategijama. Stoga je za opšte, neantagonističke, nekooperativne igre prirodno tražiti ravnotežne situacije upravo u mješovitim strategijama.

Tako, na primjer (vidi Sliku 3.1), već smo primijetili da "Izvođač" gotovo nikada ne mora da se bavi nesigurnošću ponašanja. Ali ako uzmemo konceptualni nivo tipa "Administrator", onda je sve upravo suprotno. U pravilu, glavna vrsta neizvjesnosti sa kojom se takav "naš donosilac odluka" mora suočiti je "konflikt". Sada možemo razjasniti da je to obično rivalstvo koje nije strogo. Nešto rjeđe "Administrator" donosi odluke u uslovima "prirodne neizvjesnosti", a još rjeđe se susreće sa strogim, antagonističkim sukobom. Osim toga, sukob interesa pri donošenju odluka od strane "Administratora" se dešava, da tako kažem, "jednom", tj. u našoj klasifikaciji često igra samo jednu (ponekad vrlo mali broj) partija igre. Skale za procjenu posljedica su češće kvalitativne nego kvantitativne. Strateška nezavisnost "Administratora" je prilično ograničena. Uzimajući u obzir gore navedeno, može se tvrditi da se problemske situacije ove veličine najčešće moraju analizirati korištenjem nekooperativnih neantagonističkih bi-matrix igara, štoviše, u čistim strategijama.

Principi rješavanja matričnih antagonističkih igara

Kao rezultat toga, razumno je očekivati ​​da će se u gore opisanoj igri protivnici pridržavati strategija koje su odabrali. Matrična antagonistička igra za koju max min fiv = min max Aiy>

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

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

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

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

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

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

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

Moskovski energetski institut

(Tehnički univerzitet)

Lab report

u teoriji igara

"Program za pretragu optimalnih strategija za uparenu antagonističku igru ​​datu u matričnom obliku"

Završili studenti

grupa A5-01

Ashrapov Daler

Ashrapova Olga

Osnovni koncepti teorije igara

Teorija igara dizajnirana za rješavanje konfliktne situacije , tj. situacije u kojima se sukobljavaju interesi dvije ili više strana koje teže različitim ciljevima.

Ako su ciljevi stranaka direktno suprotni, onda pričaju o tome antagonistički sukob .

igra nazvan pojednostavljenim formalizovanim modelom konfliktne situacije.

Zove se igranje igre jednom od početka do kraja party . Rezultat zabave je plaćanje (ili pobijediti ).

Zabava je sastavljena od potezi , tj. biranje igrača iz niza mogućih alternativa.

Pokreti mogu biti lični i nasumično.lični potez , Za razliku od nasumično , podrazumijeva svjestan izbor neke opcije od strane igrača.

Igre u kojima postoji barem jedan lični potez se nazivaju strateški .

Igre u kojima su svi potezi nasumični se nazivaju kockanje .

Kada povlače lični potez, razgovaraju i o tome strategije igrač, tj. o pravilu ili skupu pravila koja određuju izbor igrača. Istovremeno, strategija treba da bude sveobuhvatna, tj. izbor mora biti određen za svaku moguću situaciju tokom igre.

Izazov teorije igara– pronalaženje optimalnih strategija igrača, tj. strategije koje im pružaju maksimalan dobitak ili minimalni gubitak.

Klasifikacija teorijskih modela igara

igra n osobe se obično nazivaju gdje
je skup strategija i-tog igrača,
- plaćanje igre.

U skladu s ovom oznakom, može se predložiti sljedeća klasifikacija modela teorijske igre:

Diskretni (skupovi strategija diskretno)

Final

Beskrajno

Kontinuirano (skupovi strategija kontinuirano)

Beskrajno

n osobe (
)

koalicija (zadruga)

Nekooperativan (nekooperativan)

2 osobe (u paru)

Antagonistički (igre s nultom sumom)

(interesi strana su suprotni, tj. gubitak jednog igrača jednak je dobitku drugog)

Neantagonistički

Sa potpunim informacijama (ako igrač koji napravi lični potez zna cijelu historiju igre, tj. sve poteze protivnika)

Sa nepotpunim informacijama

Sa nultim iznosom (ukupna uplata je nula)

Sa sumom koja nije nula

Jednosmjerno (lutrije)

višesmjerna

Matrična reprezentacija uparene antagonističke igre

U ovom vodiču ćemo razmotriti antagonističke igre dve osobe dato u matričnom obliku. To znači da znamo skup strategija prvog igrača (igrača A){ A i }, i = 1,…, m i skup strategija drugog igrača (igrača B){ B j }, j = 1,..., n, i matrica A = || a ij || isplate prvog igrača. Pošto je riječ o antagonističkoj igri, pretpostavlja se da je dobitak prvog igrača jednak gubitku drugog. Smatramo da je matrični element a ij je isplata prvog igrača kada odabere strategiju A i i odgovor drugog igrača sa strategijom B j. Takvu igru ​​ćemo nazvati kao
, gdje m - broj strategija igrača ALI,n - broj strategija igrača AT. Generalno, može se predstaviti sljedećom tabelom:

	B 1		B j		B n
A 1
A i
A m

Primjer 1

Kao jednostavan primjer, razmotrite igru ​​u kojoj se igra sastoji od dva poteza.

1. potez: Player ALI bira jedan od brojeva (1 ili 2) bez da kaže protivniku o svom izboru.

2. potez: Player AT bira jedan od brojeva (3 ili 4).

Ishod: Izbor igrača ALI i AT dodaj. Ako je zbroj paran, onda AT plaća svoju vrijednost igraču ALI, ako je neparno - obrnuto, ALI plaća igraču AT.

Ova igra se može predstaviti kao
na sljedeći način:

	(izbor 3)	(izbor 4)
(izbor 1)
(izbor 2)

Lako je to vidjeti ovu igru je antagonistički, osim toga, to je igra s nepotpunim informacijama, jer igrač AT, povlačeći lični potez, nije poznato kakav je izbor igrač napravio ALI.

Kao što je gore navedeno, zadatak teorije igara je da pronađe optimalne strategije igrača, tj. strategije koje im pružaju maksimalan dobitak ili minimalni gubitak. Ovaj proces se zove odluka u igri .

Prilikom rješavanja igre u matričnom obliku treba provjeriti prisutnost igre sedlo . Za to se uvode dvije vrijednosti:

je donja granica za cijenu igre, i

je gornja procjena cijene igre.

Prvi igrač će najvjerovatnije izabrati strategiju u kojoj će dobiti maksimalan dobitak među svim mogućim odgovorima drugog igrača, a drugi će, naprotiv, izabrati onu koja minimizira svoj gubitak, tj. moguća pobeda prvog.

To se može dokazati α ≤ V ≤ β , gdje V–cijena igre , tj. vjerovatna isplata prvog igrača.

Ako je odnos α = β = V, onda to kažu igra ima sedlo
, i riješeno u čistim strategijama . Drugim riječima, postoji nekoliko strategija
, dajući igraču ALIV.

Primjer 2

Vratimo se igri koju smo razmatrali u primjeru 1 i provjerimo ima li sedla.

	(izbor 3)	(izbor 4)
(izbor 1)
(izbor 2)

Za ovu igru
= -5,
= 4,
, dakle, nema tačku sedla.

Opet, imajte na umu da je ova igra nepotpuna informativna igra. U tom slučaju možete samo savjetovati igrača ALI izabrati strategiju , jer u ovom slučaju, on može dobiti najveću isplatu, međutim, pod uslovom da igrač izabere AT strategije .

Primjer 3

Učinimo neke promjene u pravilima igre iz primjera 1. Dajmo igrača AT informacije o izboru igrača ALI. Onda AT Postoje dvije dodatne strategije:

- strategija koja je korisna za ALI. Ako izbor A - 1, onda AT bira 3 ako je izbor A - 2, onda AT bira 4;

- strategija koja nije korisna za ALI. Ako izbor A - 1, onda AT bira 4 ako je izbor A - 2, onda AT bira 3.

	(izbor 3)	(izbor 4)
(izbor 1)
(izbor 2)

Ova igra je puna informacija.

U ovom slučaju
= -5,
= -5,
, stoga igra ima sedlo
. Ova sedla odgovara dva para optimalnih strategija:
i
. Cijena igre V= -5. Očigledno je da za ALI ova igra je beskorisna.

Primjeri 2 i 3 su dobra ilustracija sljedeće teoreme, dokazane u teoriji igara:

Teorema 1

Svaka uparena antagonistička igra sa savršenim informacijama rješava se čistim strategijama.

To. Teorema 1 kaže da svaka igra dvije osobe sa savršenim informacijama ima sedlo i postoji par čistih strategija
, dajući igraču ALI održivi dobitak jednak cijeni igre V.

U slučaju odsustva sedla, tzv mješovite strategije :, gdje str i iq j su vjerovatnoće izbora strategija A i i B j prvi i drugi igrači. Rješenje igre u ovom slučaju je par mješovitih strategija
maksimiziranje matematičkog očekivanja cijene igre.

Generalizacija teoreme 1 na slučaj igre sa nepotpunim informacijama je sljedeća teorema:

Teorema 2

Svaka uparena antagonistička igra ima barem jedno optimalno rješenje, tj. par mješovitih strategija u općem slučaju
, dajući igraču ALI održivi dobitak jednak cijeni igre V, štaviše α ≤ V ≤ β .

U posebnom slučaju, za igru ​​sa sedlom, rješenje u mješovitim strategijama izgleda kao par vektora u kojima je jedan element jednak jedan, a ostali jednaki nuli.

Najjednostavniji slučaj, detaljno razrađen u teoriji igara, je igra konačnih parova sa nultom sumom (antagonistička igra dvije osobe ili dvije koalicije). Razmotrite ovu igru G, u kojoj dva igrača ALI i AT, imaju suprotstavljene interese: dobitak jednog jednak je gubitku drugog. Od igračeve isplate ALI jednaka je isplati igrača In with suprotnom predznaku, možemo biti zainteresovani samo za isplatu a igrač ALI. naravno, ALIželi maksimizirati i AT - minimizirati a. Radi jednostavnosti, hajde da se mentalno identifikujemo sa nekim od igrača (neka bude ALI) a mi ćemo ga zvati "mi", a igrač AT -"protivnik" (naravno, bez stvarnih prednosti za ALI iz ovoga ne proizlazi). Pustite nas t moguće strategije ALI 1 , A 2 , ..., ALI m, i neprijatelja n moguće strategije AT 1 , AT 2 , ..; AT n(takva igra se zove igra t × n). Označite a ij naša isplata ako koristimo strategiju A i , a neprijatelj je strategija B j .

Tabela 26.1

A i B j	B 1	B 2		B n
A 1 A 2 A m	a 11 a 21 a m1	a 21 a m		a 1 n a 2 n a mn

Pretpostavimo da je za svaki par strategija A<, AT, pobjeda (ili prosječna pobjeda) a, j mi znamo. Tada je, u principu, moguće sastaviti pravougaonu tabelu (matricu), koja navodi strategije igrača i odgovarajuće isplate (vidi tabelu 26.1).

Ako je takva tabela sastavljena, onda kažemo da je igra G svedeno na matrični oblik (samo po sebi, dovođenje igre u takav oblik već može biti težak zadatak, a ponekad i gotovo nemoguć, zbog velikog broja strategija). Imajte na umu da ako se igra svede na matričnu formu, onda se igra s više poteza zapravo svodi na igru ​​s jednim potezom - od igrača se traži da napravi samo jedan potez: odabere strategiju. Ukratko ćemo označiti matricu igre ( a ij).

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

Hajde da razmislimo koju strategiju mi ​​(igrač ALI) uzeti prednost? Matrica 26.2 ima primamljivu isplatu "10"; privučeni smo da izaberemo strategiju ALI 3 , na kojoj ćemo dobiti ovaj "slatki komad". Ali čekajte, ni neprijatelj nije glup! Ako izaberemo strategiju ALI 3 , on će, u inat, izabrati strategiju AT 3 , i dobijamo mizernu isplatu "1". Ne, izaberite strategiju ALI 3 zabranjeno je! Kako biti? Očigledno, na osnovu principa opreza (a to je glavni princip teorije igara), moramo izabrati

Tabela 26.2

B j A i	B 1	B 2	B 3	B 4	B 5
A 1 A 2 A 3 A 4

strategija koja naš minimalni dobitak je maksimalan. Ovo je takozvani "minimax princip": ponašajte se tako da uz najgore ponašanje neprijatelja za vas dobijete maksimalan dobitak.

Prepisujemo tabelu 26.2 iu desnu dodatnu kolonu upisujemo minimalnu vrijednost isplate u svakom redu, (red minimum); označimo ga za i-ti red α i(vidi tabelu 26.3).

Tabela 26.3

B j A i	B 1	B 2	B 3	B 4	B 5
A 1 A 2 A 3 A 4
β j

Od svih vrednosti α i(desna kolona) najveći (3) je istaknut. To odgovara strategiji Ačetiri . Odabravši ovu strategiju, mi, u svakom slučaju, možemo biti sigurni da ćemo (za svako ponašanje neprijatelja) dobiti ne manje od 3. Ova vrijednost je naš zagarantovani dobitak; pazeći, ne možemo dobiti manje od ovoga (možda i više). Ova isplata se naziva niža cijena igre (ili "maximin" - maksimum minimalnih isplata). Mi ćemo ga označiti a. U našem slučaju α = 3.

Hajde sada da zauzmemo tačku gledišta neprijatelja i da se založimo za njega. On nije nekakav pion, ali i razuman! Birajući strategiju, želio bi dati manje, ali mora računati na naše ponašanje, koje je za njega najgore. Ako odabere strategiju AT 1 , mi ćemo mu odgovoriti ALI 3 , i on će dati 10; ako odabere B 2 - odgovorićemo mu ALI 2 , a on će dati 8 itd. Tabelu 26.3 dodajemo dodatni donji red i upisujemo maksimume kolona β j. Očigledno, oprezan protivnik treba da izabere strategiju koja minimizira ovu vrijednost (odgovarajuća vrijednost 5 je istaknuta u tabeli 26.3). Ova vrijednost β je vrijednost dobitka, više od koje nam razuman protivnik sigurno neće dati. Zove se gornja cijena igre (ili "minimax" - minimum od maksimalnog dobitka). U našem primjeru, β = 5 i postiže se strategijom protivnika B 3 .

Dakle, na osnovu principa opreza (pravilo reosiguranja „uvek računaj na najgore!”), moramo izabrati strategiju ALI 4 , a neprijatelj - strategija AT 3 . Takve strategije se nazivaju "minimaks" (slijedeći princip minimaksa). Sve dok se obje strane u našem primjeru drže svojih minimaks strategija, isplata će biti a 43 = 3.

Sada zamislite na trenutak da smo saznali da neprijatelj slijedi strategiju AT 3 . Hajde, kaznimo ga za ovo i izaberimo strategiju ALI 1 - dobićemo 5, što i nije tako loše. Ali na kraju krajeva, neprijatelj takođe nije promašaj; neka zna da je naša strategija ALI 1 ; on takođe brzo bira AT 4 , smanjenje naše isplate na 2, itd. (partneri su „žurili oko strategija“). Jednom riječju, minimaks strategije u našem primjeru nestabilan u odnosu na to informacije o ponašanju druge strane; ove strategije nemaju svojstvo ravnoteže.

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

U ovom primjeru, donja cijena igre jednaka je gornjoj: α = β = 6. Šta iz ovoga slijedi? Minimax Player strategije ALI i ATće biti održiv. Sve dok ih se oba igrača drže, isplata je 6. Da vidimo šta će se desiti ako mi (ALI) znaj da je neprijatelj (AT)

Tabela 26.4

Bj A i	B 1	B 2	B 3	B 4
A 1 A 2 A 3
β j

drži se strategije B 2 ? I tačno se ništa neće promijeniti. Jer svako odstupanje od strategije ALI 2 može samo pogoršati našu situaciju. Isto tako, informacije koje primi neprijatelj neće ga natjerati da se povuče od svoje strategije. AT 2 . Par strategija ALI 2 , B 2 posjeduje svojstvo ravnoteže (uravnotežen par strategija), a isplata (u našem slučaju 6) postignuta ovim parom strategija naziva se „sedlo matrice“ 1). Znak prisustva sedla i uravnoteženog para strategija je jednakost donje i gornje cijene igre; zajednička vrijednost α i β naziva se cijena igre. Mi ćemo to označiti v:

α = β = v

Strategije A i , B j(u ovom slučaju ALI 2 , AT 2 ), za koje se ova isplata ostvaruje nazivaju se optimalnim čistim strategijama, a njihova ukupnost se naziva rješenjem igre. U ovom slučaju se kaže da se sama igra rješava u čistim strategijama. Obje strane ALI i AT može se naznačiti njihove optimalne strategije prema kojima je njihova pozicija najbolja moguća. Šta je igrač ALI u ovom slučaju 6 pobjeda i igrač AT - gubi 6, - pa, ovo su uslovi igre: oni su korisni za ALI i nepovoljno za AT

1) Termin "sedlasta tačka" je preuzet iz geometrije - to je naziv tačke na površini, gde se istovremeno postižu minimum duž jedne koordinate i maksimum duž druge.

Čitalac može imati pitanje: zašto se optimalne strategije nazivaju „čiste“? Gledajući malo unaprijed, odgovorimo na ovo pitanje: postoje "mješovite" strategije, koje se sastoje u činjenici da igrač ne koristi jednu strategiju, već nekoliko, nasumično ih izmjenjujući. Dakle, ako dozvolimo, osim čistih, i mješovite strategije, bilo koje kraj igre ima rješenje - tačku ravnoteže. Ali još uvijek govorimo o atomu.

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

U teoriji igara je to dokazano svaka igra sa kompletnim informacijama ima sedlo, i stoga se može riješiti u čistim strategijama. U svakoj igri sa savršenim informacijama postoji par optimalnih strategija koje daju stabilnu isplatu jednaku lancu igre v. Ako se takva igra sastoji samo od ličnih poteza, onda kada svaki igrač primijeni sopstvenu optimalnu strategiju, ona mora završiti na sasvim određen način - isplatom jednakom cijeni igre. Dakle, ako se zna rješenje igre, sama igra gubi smisao!

Uzmimo elementarni primjer igre s potpunim informacijama: dva igrača naizmjenično stavljaju novčiće na okrugli sto, birajući proizvoljno poziciju centra novčića (međusobno preklapanje novčića nije dozvoljeno). Pobjednik je onaj koji uloži zadnji peni (kada nema mjesta za druge). Lako je vidjeti da je ishod ove utakmice u suštini unaprijed gotov zaključak. Postoji određena strategija koja osigurava da igrač koji prvi stavi novčić pobjeđuje. Naime, on prvo mora staviti novčić na sredinu stola, a zatim na svaki potez protivnika odgovoriti simetričnim potezom. Očigledno, kako god se protivnik ponašao, ne može izbjeći poraz. Sasvim je ista situacija sa šahom i partijama sa potpunim informacijama uopšte: ​​bilo koja od njih, napisana u matričnom obliku, ima sedlo, pa je rešenje u čistim strategijama, pa stoga ima smisla samo dok je ovo rješenje nije pronađeno. Recimo da je šahovska partija uvijek završava pobjedom bijelih, ili uvijek - crne pobjede, ili uvijek - nerešeno, samo po čemu tačno - još ne znamo (na sreću ljubitelja šaha). Dodajmo još nešto: teško da ćemo znati u dogledno vrijeme, jer je broj strategija toliko ogroman da je izuzetno teško (ako ne i nemoguće) igru ​​svesti na matrični oblik i u njoj pronaći sedlo.

Sada se zapitajmo šta da radimo ako igra nema tačku sedla: α ≠ β ? Pa, ako je svaki igrač primoran da izabere jednu - jedinu čistu strategiju, onda nema šta da se radi: mora se voditi principom minimaksa. Druga stvar je da li je moguće "pomiješati" set strategija, nasumično izmjenjivati ​​s nekim vjerovatnoćama. Upotreba mješovitih strategija je zamišljena na ovaj način: igra se ponavlja mnogo puta; prije svake partije u igri, kada igrač dobije lični potez, "povjerava" svoj izbor slučaju, "baca ždrijeb" i uzima strategiju koja je ispala (već znamo kako organizirati žrijeb iz prethodnog poglavlja ).

Mješovite strategije u teoriji igara su model promjenjive, fleksibilne taktike, kada niko od igrača ne zna kako će se protivnik ponašati u datoj igri. Ova se taktika (iako obično bez ikakvog matematičkog opravdanja) često koristi u kartaškim igrama. Napominjemo istovremeno da je najbolji način da sakrijete svoje ponašanje od neprijatelja da mu date nasumičan karakter i, prema tome, da ne znate unaprijed šta ćete učiniti.

Dakle, hajde da pričamo o mešovitim strategijama. Označit ćemo mješovite strategije igrača ALI i AT respektivno S A = ( str 1 , R 2 , ..., str m), S B = (q 1 , q 2 , …, q n), gdje str 1 , str 2 , …, str m(formirajući ukupno jedan) - vjerovatnoće koje igrač koristi ALI strategije ALI 1 , A 2 ,… , A m ; q 1 , q 2 , …, q n- vjerovatnoće korištenja od strane igrača AT strategije AT 1 , AT 2 , ..., AT n . U konkretnom slučaju, kada su sve vjerovatnoće, osim jedne, jednake nuli, a ova jednaka jedan, mješovita strategija se pretvara u čistu.

Postoji osnovna teorema teorije igara: svaka igra za dvije osobe sa konačnim nultom sumom ima barem jedno rješenje - par optimalnih strategija, uglavnom mješovitih
i odgovarajuću cijenu v.

Par optimalnih strategija
formiranje rješenja igre ima sljedeće svojstvo: ako se jedan od igrača pridržava svoje optimalne strategije, onda ne može biti isplativo da drugi odstupi od svoje. Ovaj par strategija stvara neku vrstu ravnoteže u igri: jedan igrač želi da dobitak okrene na maksimum, drugi na minimum, svaki vuče u svom smjeru, i, uz razumno ponašanje oba, ravnotežu i stabilnu dobitak se utvrđuje. v. Ako a v > 0, onda je igra isplativa za nas ako v< 0 - za neprijatelja; at v= 0 igra je “fer”, podjednako korisna za oba učesnika.

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

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

Niža cijena igre α = - 3 i odgovara strategiji A 1 . To znači da razumnim, opreznim ponašanjem garantujemo da nećemo izgubiti više od 3. Mala uteha, ali ipak bolja od, recimo, pobede od 5, koja se javlja u nekim ćelijama matrice. Loše za nas, igrača ALI... Ali da se tješimo:

čini se da je pozicija protivnika još gora: niži trošak igre je β = 4, tj. uz razumno ponašanje, on će nam dati najmanje 4. Generalno, pozicija nije baš dobra - ni za jednog ni za druga strana. Ali hajde da vidimo da li se to može poboljšati? Ispostavilo se da možeš. Ako svaka strana koristi ne jednu čistu strategiju, već mješovitu, u kojoj

Tabela 26.5

Bj A i	B 1	B 2	B 3
A 1 A 2 A 3
β j

prvi i treći ulaze sa verovatnoćom 1/4, a drugi - sa verovatnoćom 1/2, tj.

tada će prosječna isplata biti konstantno jednaka nuli (što znači da je igra “fer” i podjednako korisna za obje strane). Strategije
formiraju rješenje za igru ​​i njenu cijenu v= 0. Kako smo pronašli ovo rješenje? Ovo je drugo pitanje. U sljedećem odjeljku pokazujemo kako se općenito rješavaju konačne igre.

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

Pustite nas m moguće strategije A 1 , A 2 , …, A m, i neprijatelja n moguće strategije B 1 , B 2 , …, B n(takva igra se zove igra m×n). Pretpostavimo da je svaka strana izabrala određenu strategiju: mi smo izabrali Ai, protivnik B j. Ako se igra sastoji samo od ličnih poteza, onda je izbor strategija Ai i B j jedinstveno određuje ishod igre - našu isplatu (pozitivnu ili negativnu). Označimo ovaj dobitak kao aij(pobjeda kada odaberemo strategiju Ai, a neprijatelj - strategije B j).

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

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

B j A i	B 1	B 2	…	B n
A 1	a 11	a 12	…	a 1n
A 2	a 21	a 22	…	a 2n
…	…	…	…	…
A m	a m 1	a m 2	…	amn

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

Imajte na umu da izgradnja matrice isplate za igre sa velikim brojem strategija može biti težak zadatak. Na primjer, za šahovska igra broj mogućih strategija je toliko velik da je konstrukcija matrice isplate praktički nemoguća. Međutim, u principu se svaka konačna igra može svesti na matrični oblik.

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

B j A i	B 1	B 2	B 3	B 4	B 5
A 1
A 2
A 3
A 4

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

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

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

B j A i	B 1	B 2	B 3	B 4	B 5	minimum u redovima a i
A 1
A 2
A 3
A 4							maximin

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

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

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

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

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

βj β :

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

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

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

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

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

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

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

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

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

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

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

Na osnovu ove matrice proizilazi da je igrač B mora slijediti bilo koju od strategija B 1 i B 2 (i tada neće izgubiti više od 4), i igrač A– strategije A 1 (i tada neće izgubiti više od 3). Kao što vidite, rezultat je potpuno isti kao onaj koji smo dobili gore, tako da analiza nije bitna sa gledišta kojeg igrača ćemo je provesti.

8 ŠTA JE VRIJEDNA IGRA.

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

Razmotrimo matričnu igru ​​tipa sa matricom isplate

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

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

Problem donošenja odluka, razmatran u okviru sistemskog pristupa, sadrži tri glavne komponente: u njemu se identifikuju sistem, upravljački podsistem i okruženje. Sada prelazimo na proučavanje problema donošenja odluka, u kojima na sistem utiče ne jedan, već nekoliko kontrolnih podsistema, od kojih svaki ima svoje ciljeve i mogućnosti djelovanja. Ovaj pristup donošenju odluka naziva se teorijskim igara, a matematički modeli odgovarajućih interakcija nazivaju se igrice. Zbog razlike u ciljevima upravljačkih podsistema, kao i određenih ograničenja mogućnosti međusobne razmjene informacija, ove interakcije su konfliktne prirode. Stoga je svaka igra matematički model sukoba. Ograničavamo se na slučaj kada postoje dva upravljačka podsistema. Ako su ciljevi sistema suprotni, sukob se naziva antagonističkim, a matematički model takvog sukoba naziva se antagonistička igra..

U terminologiji teorije igara, 1. kontrolni podsistem se naziva igrač 1, 2. upravljački podsistem - igrač 2, setovi

nazivaju se njihove alternativne akcije setove strategija ovi igrači. Neka X- set strategija igrača 1, Y- mnoge strategije

igrač 2. ​​Stanje sistema je jednoznačno određeno izborom kontrolnih akcija po podsistemima 1 i 2, odnosno izborom strategija

x∈X i y∈Y. Neka F(x,y) - procjena korisnosti za igrača 1 tog stanja

sistem na koji prelazi kada igrač 1 odabere strategiju X i

strategija igrača 2 at. Broj F(x,y) se zove pobjeda igrač 1 u situaciji ( x,y), i funkciju F- funkcija isplate igrača 1. Pobjeda igrača

1 je i gubitak igrača 2, odnosno vrijednost koju prvi igrač želi povećati, a drugi - smanjiti. To je ono što je

manifestacija antagonističke prirode sukoba: interesi igrača su potpuno suprotni (što jedan dobija, drugi gubi).

Antagonističku igru ​​prirodno postavlja sistem G=(X, Y, F).

Imajte na umu da je formalno antagonistička igra zapravo postavljena na isti način kao i problem donošenja odluke u uvjetima neizvjesnosti - ako

identifikuju kontrolni podsistem 2 sa okruženjem. Suštinska razlika između kontrolnog podsistema i okruženja je u tome

ponašanje prvog je svrsishodno. Ako pri sastavljanju matematičkog modela stvarnog sukoba imamo razlog (ili namjeru) da okruženje smatramo protivnikom, čija je svrha da dovede

nama maksimalna šteta, onda se takva situacija može predstaviti kao antagonistička igra. Drugim riječima, antagonistička igra se može tumačiti kao ekstremni slučaj ZPR-a u uvjetima neizvjesnosti,

karakteriše činjenica da se okolina posmatra kao protivnik sa ciljem. Istovremeno, moramo ograničiti vrste hipoteza o ponašanju okoline.

Ovdje je najpouzdanija hipoteza krajnjeg opreza, kada se pri donošenju odluke oslanjamo na najgori mogući scenario za djelovanje u okruženju.

Definicija. Ako a X i Y su konačni, onda se antagonistička igra naziva matrična. U matričnoj igri to možemo pretpostaviti X={1,…,n},

Y={1,…,m) i stavite aij=F(i,j). Dakle, matrična igra je u potpunosti određena matricom A=(aij), i=1,…,n, j=1,…,m.

Primjer 3.1. Igra sa dva prsta.

Dvije osobe u isto vrijeme pokazuju jedan ili dva prsta i zovu broj 1 ili 2, što, prema govorniku, znači broj

prste pokazivati ​​drugima. Nakon što se pokažu prsti i imenuju brojevi, dobici se dijele prema sljedećim pravilima:

ako su obojica pogodili ili oboje nisu pogodili koliko je prstiju pokazao njihov protivnik, isplata svakog je jednaka nuli; ako je samo jedan pogodio tačno, onda protivnik plaća pogađaču iznos novca proporcionalan ukupnom broju prikazanih

Ovo je antagonistička matrična igra. Svaki igrač ima četiri strategije: 1- pokazati 1 prst i reći 1, 2- pokazati 1 prst i reći 2, 3-

pokaži 2 prsta i reci 1, 4 - pokaži 2 prsta i reci 2. Zatim matrica isplate A=(aij), i= 1,…, 4, j= 1,…, 4 je definisan na sljedeći način:

a12= 2, a21 = – 2, a13=a42=–3, a24=a31= 3, a34 = – 4, a43= 4,aij= 0 inače.

Primjer 3.2. Diskretna igra tipa duel.

Zadaci tipa duel opisuju, na primjer, borbu dva igrača,

od kojih svaki želi izvršiti neku jednokratnu radnju (puštanje pošiljke robe na tržište, prijava za kupovinu na aukciji) i bira vrijeme za to. Pustite igrače da se kreću jedni prema drugima n stepenice. Nakon svakog napravljenog koraka, igrač može ili ne mora pucati u protivnika. Svaka osoba može imati samo jedan pogodak. Vjeruje se da je vjerovatnoća da ćete pogoditi neprijatelja ako napredujete k n =5 ima oblik