Teorija igara: Matrične igre. Primjer rješavanja problema teorije igara u mješovitim strategijama od strane našeg servisa

27.09.2019 | Izgradnja

Zove se igra sa nultom sumom za dvije osobe u kojoj svaka od njih ima konačan skup strategija. Pravila matrične igre određena su matricom isplate, čiji su elementi isplate prvog igrača, a to su i gubici drugog igrača.

Matrix game je antagonistička igra. Prvi igrač dobija maksimalnu zagarantovanu (ne zavisi od ponašanja drugog igrača) isplatu jednaku ceni igre, shodno tome, drugi igrač ostvaruje minimalni garantovani gubitak.

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

Sada o svemu po redu i detaljno.

Matrica isplate, čiste strategije, cijena igre

IN matrična igra njegova pravila su određena matrica isplate .

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

IN matrica plaćanja elementi su brojevi koji izražavaju dobitke i gubitke igrača. Pobjede i gubici mogu biti izraženi u bodovima, novcu ili drugim jedinicama.

Kreirajmo matricu isplate:

Ako prvi igrač odabere i-ta čista strategija i drugi igrač j-th čista strategija, onda je isplata prvog igrača aij jedinica, a gubitak drugog igrača je također aij jedinice.

Jer aij + (- a ij ) = 0, tada je opisana igra matrična igra nulte sume.

Najjednostavniji primjer matrične igre je bacanje novčića. Pravila igre su sljedeća. Prvi i drugi igrač bacaju novčić i rezultat je glava ili rep. Ako se istovremeno bacaju glave i glave ili repovi ili repovi, tada će prvi igrač osvojiti jednu jedinicu, au ostalim slučajevima će izgubiti jednu jedinicu (drugi igrač će osvojiti jednu jedinicu). Iste dvije strategije su na raspolaganju drugom igraču. Odgovarajuća matrica isplate bi bila:

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

Kako se bira strategija u matričnoj igri?

Pogledajmo ponovo matricu isplate:

Prvo, određujemo isplatu prvog igrača ako koristi ičista strategija. Ako prvi igrač koristi i-tu čistu strategiju, onda je logično pretpostaviti da će drugi igrač koristiti tako čistu strategiju, zbog čega bi isplata prvog igrača bila minimalna. Zauzvrat, prvi igrač će koristiti tako čistu strategiju koja bi mu pružila maksimalnu isplatu. Na osnovu ovih uslova, isplata prvog igrača, koju označavamo kao v1 , zove se maximin win ili niža cijena igre .

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

Sada odredimo gubitak 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 tako čistu strategiju u kojoj bi njegov gubitak bio minimalan. Gubitak drugog igrača koji označavamo kao v2 , zove se minimalni gubitak ili vrhunska 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 napišite vrijednost maksimalnog elementa i od njih odaberite minimum. Tako će gubitak drugog igrača biti minimum od maksimuma. Otuda i naziv - minimax gain. Broj kolone ovog elementa će biti broj čiste strategije koju je izabrao drugi igrač. Ako drugi igrač koristi "minimax", tada će bez obzira na izbor strategije od strane prvog igrača izgubiti najviše 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 kako pronaći donju i gornju cijenu igre, maksimin i minimaks strategije, vrijeme je da naučimo kako formalno označiti ove koncepte.

Dakle, zagarantovana isplata prvog igrača je:

Prvi igrač mora izabrati čistu strategiju koja bi mu pružila maksimum od minimalnih isplata. 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 definisan na sledeći način:

Drugi igrač mora izabrati svoju čistu strategiju tako da njegov gubitak bude minimalan. Ovaj gubitak (minimaks) se označava na sljedeći način:

Još jedan primjer iz iste serije.

Primjer 2 Zadana je matrična igra s matricom isplate

Odredite maksimalnu strategiju prvog igrača, minimax strategiju drugog igrača, donju i gornju cijenu igre.

Rješenje. Desno od matrice isplate ispisujemo najmanje elemente u njene redove i označavamo maksimum od njih, a sa dna matrice - najveće elemente u kolonama i biramo minimum od njih:

Najveći od najmanjih elemenata redova je 3, ovo je niža cijena igre, drugi red 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. Odnosno, jednake donje i gornje cijene igre postižu se na istom paru 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 isplate ispisujemo najmanje elemente u njene redove i označavamo maksimum od njih, a sa dna matrice - najveće elemente u kolonama i biramo minimum od njih:

Donja cijena igre je ista kao i gornja cijena 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.

Riješite sami 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 čista strateška rješenja.

Ali ima rješenje u optimalnim mješovitim strategijama. Da bi ih pronašli, potrebno je pretpostaviti da se igra ponavlja dovoljno puta da se na osnovu iskustva može pogoditi koja je strategija poželjnija. Stoga je odluka povezana sa konceptom vjerovatnoće i prosjeka (očekivanja). 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 maksimalan prosječan dobitak, a drugi najmanji 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. 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. Zbir ovih vjerovatnoća jednak je jedan:

Ako prvi igrač koristi mješovitu strategiju str, a drugi igrač - mješovita strategija q, onda ima smisla očekivanu vrijednost prvi igrač pobjeđuje (drugi igrač gubi). 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 dobitka 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 dobitka prvog igrača (gubitak drugog igrača), ono je jednako umnošku vektora mješovite strategije prvog igrača, matrice isplate 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 partija ponovi dovoljan broj puta.

Po analogiji sa notacijom maksimina i minimaksa u slučajevima čistih strategija, optimalne mješovite strategije se označavaju na sljedeći način (i povezane su sa matematičko očekivanje, odnosno prosjek dobitka 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šite matričnu igru u mješovitim strategijama , moramo matričnu igru svesti na problem linearno programiranje, odnosno na problem optimizacije, i riješiti odgovarajući problem linearnog programiranja.

Svođenje matrične igre na problem linearnog programiranja

Da biste riješili matričnu igru u mješovitim strategijama, morate sastaviti pravu liniju problem linearnog programiranja I njegov dvostruki zadatak. U dualnom problemu transponuje se proširena matrica koja pohranjuje koeficijente varijabli u sistemu ograničenja, konstantne članove i koeficijente varijabli u funkciji cilja. U ovom slučaju, minimum funkcije cilja izvornog problema povezan je s maksimumom u dualnom problemu.

Funkcija cilja u problemu direktnog linearnog programiranja:

Sistem ograničenja u direktnom problemu linearnog programiranja:

Funkcija cilja u dvojnom problemu:

Sistem ograničenja u dualnom problemu:

Označiti optimalni plan problema direktnog linearnog programiranja

a optimalni plan dualnog problema je označen sa

Linearni oblici za odgovarajuće optimalne dizajne će biti označeni sa i ,

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

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

Matematičari su to dokazali cijena igre izražava se u linearnim oblicima optimalnih planova kako slijedi:

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 vektori, kao što smo već definirali u prethodnom paragrafu. 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. Sastavljamo problem linearnog programiranja koji odgovara ovoj matričnoj igri:

Dobijamo rješenje direktnog problema:

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

Sadržaj 1 Opće informacije 2 1.1 Igre. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Pokreti. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Strategije. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Matrična igra. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Tačka traga. Čiste strategije 7 2.1 Primjeri. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Primjer 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Primjer 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Mješovite strategije 9 3.1 Igra 2×2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.1 Primjeri. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Primjer 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Primjer 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1.2 Geometrijska interpretacija. . . . . . . . . . . . . . . . . . . . 12 3.2 Igre 2×n i m×2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Primjer 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1 1. Opći podaci iz teorije igara 1.1. Igre Teorija igara je matematička teorija konfliktne situacije, tj. takve situacije u kojima se sukobljavaju interesi dvije ili više strana koje teže različitim ciljevima. Igra je konfliktna situacija regulisana određenim pravilima, koja treba da ukažu na: moguće opcije za radnje učesnika, kvantitativni rezultat igre ili isplatu (pobeda, poraz) do koje dati set poteza dovodi do iznosa informacije svake strane o ponašanju druge. Igra u parovima - igra u kojoj učestvuju samo dvije strane (dva igrača). Zero-sum pair game - igra u paru u kojoj je iznos uplata jednak nuli, tj. Gubitak jednog igrača jednak je dobitku drugog. Ovisno o stavu svakog igrača prema vrijednosti funkcije isplate, uparene igre se dijele: Gubitak jednog igrača jednak je dobitku drugog. Neantagonistička igra je igra u paru u kojoj igrači teže različitim, ali ne direktno suprotnim ciljevima. 2 1.2. Pokreti Pokret - izbor jedne od radnji predviđenih pravilima igre, implementacija ovog izbora Postoje dvije vrste poteza: Lični potez - + svjestan izbor jedne od radnji predviđenih pravilima igre + implementacija ovog izbora Slučajni potez - Nasumični potez je izbor iz niza mogućnosti, koji se ne vrši odlukom igrača, već nekim mehanizmom slučajnog odabira. U nastavku razmatramo uparene igre sa nultom sumom koje sadrže samo lične poteze. Svaka strana nema informacije o ponašanju druge. 3 1.3. Strategije Igračeva strategija je skup pravila koja određuju izbor akcija za svaki lični potez ovog igrača, u zavisnosti od situacije koja se razvila tokom igre. U zavisnosti od broja mogućih strategija, igre se dijele na konačne i beskonačne. Beskonačna igra je igra u kojoj barem jedan od igrača ima beskonačan broj strategija. Konačna igra je igra u kojoj svaki igrač ima samo konačan broj strategija. Broj uzastopnih poteza za bilo kog od igrača određuje podjelu igara na jednopokretne i višepokretne, odnosno pozicijske. + U igri u jednom potezu, svaki igrač donosi samo jedan izbor od mogućih opcija, a zatim određuje ishod igre. + Igra sa više poteza, ili poziciona, razvija se u vremenu, predstavljajući niz uzastopnih faza, od kojih svaka dolazi nakon poteza jednog od igrača i odgovarajuće promjene situacije. U igri u jednom potezu, svaki igrač donosi samo jedan izbor od mogućih opcija, a zatim određuje ishod igre. Optimalna strategija igrača je strategija koja, kada se igra ponovi mnogo puta, daje datom igraču maksimalan mogući prosječan dobitak (ili, ekvivalentno, minimalni mogući prosječni gubitak). U teoriji igara, sve preporuke su date na osnovu pretpostavke razumnog ponašanja igrača. Ne uzimaju se u obzir pogrešne procene i greške igrača, neizbežne u svakoj konfliktnoj situaciji, kao i elementi uzbuđenja i rizika u teoriji igara. 4 1.4. Matrična igra Matrična igra je igra sa konačnim nultom sumom u jednom potezu. mogući načini U skladu sa odabranim metodama djelovanja (strategijama) utvrđuje se postignuti rezultat. Pogledajmo primjer. Neka postoje dva igrača A i B, od kojih jedan može birati i-ta strategija od m mogućih strategija A1 , A2 , ...Am , a druga bira j-ta strategija njihovih mogućih strategija B1 , B2 , ...Bm . Kao rezultat, prvi igrač osvaja aij, a drugi igrač gubi ovu vrijednost. Od brojeva aij , sastavljamo matricu   a11 a11 · · · a1n  a21 a22 · · · a2n    A = (aij) =  .. .. .. ..   . . . .  am1 am2 · · · amn Matrica A = (aij), i = 1, m, j = 1, n naziva se matrica isplate ili matrica igre m × n. U ovoj matrici, redovi su uvijek za strategije pobjedničkog (maksimizirajućeg) igrača A, odnosno igrača koji želi maksimizirati svoju isplatu. Kolone su rezervisane za strategije igrača B koji gubi, odnosno igrača koji nastoji da minimizira kriterijum efikasnosti. Normalizacija igre je proces svođenja pozicijske igre na matričnu igru Igra u normalnom obliku je poziciona igra svedena na matričnu igru jednim izborom (pokretom) iz konačnog broja mogućih načina djelovanja u svakoj fazi razvoja ovog situacija. Rešenje igre – pronalaženje optimalnih strategija oba igrača i određivanje vrednosti igre Vrednost igre je očekivani dobitak (gubitak) igrača. Rješenje igre se može naći ili u čistim strategijama - kada igrač mora slijediti jednu strategiju, ili u mješovitim, kada igrač mora koristiti dvije ili više čistih strategija sa određenim vjerovatnoćama. Potonji se u ovom slučaju nazivaju aktivnim. 5 Mješovita strategija jednog igrača je vektor, čija svaka komponenta pokazuje učestalost korištenja odgovarajuće čiste strategije od strane igrača. Maksimalna ili niža cijena igre - broj α = max min aij i j Maksimalna strategija (string) - strategija koju je igrač izabrao da maksimizira svoju minimalnu isplatu. Očigledno, pri odabiru najopreznije maksiminske strategije, igrač A sebi obezbjeđuje (bez obzira na ponašanje protivnika) zagarantovanu isplatu od najmanje α. Maximin ili gornji trošak igre - broj β = min max aij j i Minimax strategija (kolona) - strategija koju je igrač izabrao da smanji svoj maksimalni gubitak. Očigledno, pri odabiru najopreznije minimaks strategije, igrač B ne dozvoljava igraču A da osvoji više od β ni pod kojim okolnostima. Donja cijena igre uvijek ne prelazi gornju cijenu igre α = max min aij 6 min max aij = β i j j i Teorem 1 (glavni teorem teorije matričnih igara). Svaka konačna igra ima barem jedno rješenje, možda u području mješovitih strategija. 6 2. Igre sa sedlom. Rješenje u čistim strategijama Igra sa sedlom je igra za koju je α = max min aij = min max aij = β i j j i Za igre sa sedlom, pronalaženje rješenja sastoji se u odabiru maksiminskih i minimaksnih strategija koje su optimalne. - opšte značenje donja i gornja cijena igre α=β=ν 2.1. Primjeri Primjer 1 Pronađite rješenje u čistim strategijama igre datim matricom   8 4 7 A= 6 5 9  7 7 8 Rješenje: odredite gornju i donju cijenu igre. Da bismo to učinili, nalazimo minimum brojeva aij u i-ti redαi = min aij j i maksimum brojeva aij in j-ta kolona βj = max aij i Zapisujemo brojeve αi (minimum redova) pored matrice isplate na desnoj strani kao dodatnu kolonu. Upisujemo brojeve βi (maksimumi stupca) ispod matrice kao dodatni red: αi 8 4 7 4 6 5 9 5 7 7 8 7 βj 8 7 9 7 Nađi maksimum brojeva αi α = max αi = 7 i i minimum brojeva βj β = min βj = 7 j α = β - igra ima sedlo. Optimalna strategija za igrača je strategija A3, a za igrača B - strategija B2, neto trošak igre ν = 7 Primjer 2 Matrica isplate je data: 1 1 2   1 2 1 1 2 Pronađite rješenje igre u čistim strategijama. Rješenje: 2 2 1 1 2 1 0 1 1 1 1 0 1 1 1 1 2 1 1 2 1 1 2 1 βj 2 2 1 1 2 α = β = 1. Igra ima šest sedla. Optimalne strategije su: A1 i B3 ili B4 A3 i B3 ili B4 A4 i B3 ili B4 8 3. Rješenje igre u mješovitim strategijama Za α ̸= β. U slučaju kada pri izboru svojih strategija oba igrača nemaju informacije o izboru drugog, igra ima rješenje u mješovitim strategijama. SA = (p1 , p2 , ..., pm) je mješovita strategija igrača A u kojoj se primjenjuju strategije A1 , A2 , ..., Am sa vjerovatnoćama ∑ m p1 , p2 , ..., pm , pi = 1, pi > 0, i = 1, m i=1 SB = (q1 , q2 , ..., qn) je mješovita strategija igrača B u kojoj se strategije B1 , B2 , ..., Bm primjenjuju sa vjerovatnoćama ∑ n q1 , q2 , ..., qm , qi = 1, qi > 0, i = 1, n i=1 = aij p∗i qi∗ j=1 i=1 2 × n, m × 2). Ako jedan od igrača koristi optimalnu mješovitu strategiju, tada je njegova isplata jednaka cijeni igre ν, bez obzira na vjerovatnoću s kojom će drugi igrač koristiti strategije uključene u optimalnu (uključujući i čiste strategije). 9 3.1. 2 × 2 igra Razmotrimo igru 2 × 2 sa matricom: () a11 a21 a21 a22 Neka igra nema rješenja u čistim strategijama. Nađimo optimalne strategije SA∗ i SB∗. Prvo definišemo strategiju SA∗ = (p∗1, p∗2). Prema teoremi, ako se stranka A pridržava strategije ν, tada će bez obzira na tok akcije stranke B, isplata ostati jednaka cijeni igre ν. Stoga, ako se stranka A pridržava optimalne strategije SA∗ = (p∗1, p∗2), onda strana B može primijeniti bilo koju od svojih strategija bez promjene isplate. Zatim, kada igrač B primijeni čistu strategiju B1 ili B2, igrač će dobiti prosječnu isplatu jednaku cijeni igre: a11 p∗1 + a21 p∗2 = ν ← za strategiju B1 imajte na umu da je p∗1 + p ∗2 = 1: p∗1 = a2 2−a2 1 a11 +a22 −a12 −a21 p∗2 = a1 1−a1 2 a11 +a22 −a12 −a21 Vrijednost igre: a22 a11 − a12 a21 ν= a11 + a22 − a12 − a21 Slično, pronađena je optimalna strategija igrača B: SB∗ = (q1∗, q2∗). Uzimajući u obzir da je q1∗ + q2∗ = 1: q1∗ = a2 2 − a1 2 a11 + a22 − a12 − a21 q2∗ = a1 1 − a2 1 a11 + a22 − a12 − a21 3.1.1. Primjeri Primjer 3 Naći rješenje za igru sa matricom () −1 1 A= 1 −1 10 Rješenje: igra nema sedlo, jer je α= -1, β = 1, α ̸= β. Tražimo rješenje u mješovitim strategijama. Koristeći formule za p∗ i q∗ dobijamo p∗1 = p∗2 = 0,5 i q1∗ = q2∗ = 0,5, ν = 0 Dakle, SA∗ = (0,5, 0,5) SB∗ = (0,5, 0,5) Primjer 4 Naći rješenje za igru sa matricom () 2 5 A= 6 4 Rješenje: igra nema sedlo, jer je α= 4, β = 5, α ̸= β. Tražimo rješenje u mješovitim strategijama. Po formulama za p∗ i q 0.8) 11 3.1.2. Geometrijska interpretacija Igri 2×2 može se dati jednostavna geometrijska interpretacija. Uzmimo jedinični presjek ose apscise, čijoj tački pridružujemo neku mješovitu strategiju S = (p1 , p2) = (p1 , 1 − p1) p2 , strategije A2 - udaljenost do lijevog kraja. .y .I .I I .B1′ .N .B1 .a21 .a11 .I I .I .∗ .x .P2 .SA∗ .P1∗ desni kraj preseka (x = 1) - strategija A2 Na krajevima preseka se vraćaju dve okomice na osu apscise: os I - I - isplata se odlaže strategijom A1 osa II - II - isplata se odlaže strategijom A2 Neka igrač B primeni strategiju B1 ; daje na osama I − I i II − II, redom, tačke sa ordinatama a11 i a21 . Kroz ove tačke povlačimo pravu B1 − B1′. Za bilo koju mješovitu strategiju SA = (p1, p2), igračeva isplata je određena tačkom N na pravoj B1 − B1′, koja odgovara tački SA na x-osi koja dijeli segment u odnosu na p2: p1. Očigledno, prava linija B2 − B2′, koja određuje isplatu za strategiju B2, može se konstruisati na potpuno isti način. 12 .y .I .I .B2 .N .a21 .B2′ a . 22 .I I .I .∗ .x .P2 .SA∗ .P1∗ Potrebno je pronaći optimalnu strategiju SA∗ , tj. tako da bi se minimalna isplata igrača A (sa najgorim ponašanjem igrača B za njega) pretvorila u maksimum. Za to se konstruiše donja granica isplate igrača A za strategije B1, B2, tj. izlomljena linija B1 N B2′ ;. Na ovoj granici će ležati minimalna isplata igrača A za bilo koju od njegovih mješovitih strategija, tačka N, u kojoj ova isplata dostiže maksimum i određuje rješenje i cijenu igre. .y .I .I I .B2 .B1′ .N .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S . 1∗ P Ordinata tačke N nije ništa drugo do vrednost igre ν, njena apscisa je jednaka ∗2, a rastojanje do desnog kraja segmenta je jednako ∗1, tj. udaljenost od tačke SA∗ do krajeva segmenta jednaka je vjerovatnoćama ∗2 i ∗1 strategija A2 i A1 optimalne mješovite strategije igrača A. U ovom slučaju rješenje igre je određeno pomoću tačka preseka strategija B1 i B2 . U nastavku je prikazan slučaj kada je igračeva optimalna strategija čista strategija A2. Ovde je strategija A2 (za bilo koju strategiju protivnika) isplativija od strategije A1 , 13 .y .y .I .I I .I I. I .B2′ . 1′ B .B1′ B . 2 .B2′ B . 2 .B1 .v = a21 .B1 .v = a21 I. I I. I .I . .x .I . .x 2∗ P . A∗ S = A2. 2∗ P . A∗ S = A2 Desno je prikazan slučaj kada igrač B ima namjerno neisplativu strategiju.Geometrijska interpretacija omogućava vizualizaciju i donje cijene igre α i gornje β .y .I .I I .B2 .B1′ .N .B1 .B2′ .β = a21 .α = a22 .I I .I .∗ .x .P2 . A∗ S . 1∗ P Na istom grafikonu može se dati i geometrijska interpretacija optimalnih strategija igrača B. Lako je vidjeti da je udio q1∗ strategije B1 optimalne mješovite strategije SB∗ = (q1∗, q2∗) jednak omjeru dužine segmenta KB2 i zbiru dužina segmenata KB1 i KB2 na osi I − I: .y .I .I I .B2 .B1′ .N .K .L .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S . 1∗ P 14 KB2 q1∗ = KB2 + KB1 ili LB2′ q1∗ = LB2′ + LB1′ maksimum donje granice isplate smatra se minimumom gornje granice. .y .I .I I .A2 .A′1 .N .A1 .A′2 .I I .I . .x .q2∗ . B∗ S .q1∗ 15 3.2. Igre 2 × n i m × 2 Rješenje igara 2 × n i m × 2 zasniva se na sljedećem teoremu. Teorem 3. Svaka konačna igra m × n ima rješenje u kojem broj aktivnih strategija svake strane ne prelazi najmanji od m i n. Prema ovoj teoremi, igra 2 × n uvijek ima rješenje u kojem svaki igrač ima najviše dvije aktivne strategije. Potrebno je samo pronaći ove strategije i igra 2 × n se pretvara u igru 2 × 2, koja se rješava elementarno. Pronalaženje aktivnih strategija može se obaviti grafički: 1) gradi se grafička interpretacija; 2) utvrđuje se donja granica dobitka; 3) na donjoj granici isplate razlikuju se dvije strategije drugog igrača, koje odgovaraju dvije prave koje se sijeku u tački s maksimalnom ordinatom (ako se u njoj siječe više od dvije prave, uzima se bilo koji par) - ove strategije su aktivne strategije igrača B. Tako se igra 2 × n svodi na igru 2 × 2. Igra m × 2 također se može riješiti, s tom razlikom što se ne konstruiše gornja granica isplate, a ne maksimum, već se na njoj traži minimum . Primjer 5 Pronađite rješenje za igru () 7 9 8 A= 10 6 9 Rješenje: geometrijskom metodom biramo aktivne strategije. Prave B1 − B1′ , B2 − B2′ i B3 − B3′ odgovaraju strategijama B1 , B2 , B3 . Izlomljena linija B1 N B2 je donja granica igračeve isplate. Igra ima rješenje S∗A = (23 , 31); S∗B = (0,5; 0,5; 0); v = 8,16 .y .I .I I . 1′ B B . 2 .B3′ .N .B3 .B1 .B2′ .I I .I . .x 2∗ P . A∗ S . 1∗ P 17 Indeksna igra, 2 poteza, 3 2 × 2, 10 ličnih, 3 2 × 2, 9 nasumično, 3 geometrija, 12 čista igra vrijednost, 7 primjera, 10 2 × n, 9, 16 m × 2, 9 , 16 beskonačno, 4 normalna forma, 5 konačnih, 4 višesmjerna, 4 jednosmjerna, 4 matrica, 5 dvostruka, 2 nulta suma, 2 antagonistička, 2 neantagonistička, 2 rješenja, 5 mješovitih strategija, 5, 9 čiste strategije 5 teorija igara, 2 18

Ako postoji više sukobljenih strana (osoba), od kojih svaka donosi neku odluku utvrđenu datim skupom pravila, a svaka od strana zna konačno stanje konfliktne situacije sa unaprijed određenim isplatama za svaku od strana, onda kažemo da postoji igra.

Zadatak teorije igara je odabrati takvu liniju ponašanja za datog igrača, odstupanje od koje može samo smanjiti njegovu isplatu.

Neke definicije igre

Kvantitativna procjena rezultata igre naziva se plaćanje.

Parovi (dvije osobe) naziva se igra sa nultom sumom ako je zbir uplata nula, tj. ako je gubitak jednog igrača jednak dobitku drugog.

Nedvosmislen opis igračevog izbora u svakoj od mogućih situacija u kojoj mora napraviti lični potez naziva se strategija igrača .

Igračeva strategija se naziva optimalnom ako, kada se igra ponovi mnogo puta, daje igraču maksimalnu moguću prosječnu isplatu (ili, što je isto, minimalnu moguću prosječnu isplatu).

Matrix Defined Game A, koji ima m linije i n kolone naziva se igra konačnih parova dimenzija m* n;

Gdje i=
je strategija prvog igrača sa m strategija; j=je strategija drugog igrača sa n strategija; ij je isplata prvog igrača i-ta strategija kada se koristi od strane druge j-tu strategiju (ili, što je isto, gubljenje druge j strategije, kada se prvi put koristi i th);

A =   ij je matrica isplate igre.

1.1 Igranje čistim strategijama

Niža cijena igre (za prvog igrača)

 = max (min ij). (1.2)

i j

Gornja cijena igre (za drugog igrača):

= min (max ij) . (1.3)

J i

Ako  =  , igra se zove sa sedlom (1.4), ili igra sa čistim strategijama. Gde V =  =  zove se vrijedna igra ( V- cijena igre).

Primjer. Date matricu isplate za igru 2 osobe A. Odredite optimalne strategije za svakog od igrača i cijenu igre:

(1.4)

max 10 9 12 6

min 6

je strategija prvog igrača (red).

Strategija drugog igrača (kolone).

- cijena igre.

Dakle, igra ima sedlo. Strategija j = 4 je optimalna strategija za drugog igrača i=2 - za prvu. Imamo igru sa čistim strategijama.

1.2 Mješovite strateške igre

Ako matrica isplate nema tačku sedla, tj.
, a niko od učesnika u igrici ne može izabrati jedan plan kao svoju optimalnu strategiju, igrači prelaze na "mešovite strategije". U ovom slučaju svaki od igrača koristi svaku svoju strategiju nekoliko puta tokom igre.

Vektor, čija svaka komponenta pokazuje relativnu učestalost igračeve upotrebe odgovarajuće čiste strategije, naziva se igračeva mješovita strategija.

X= (X 1 …X i …X m) je mješovita strategija prvog igrača.

At= (at 1 ...at j ...at n) je mješovita strategija drugog igrača.

xi , y j– relativne frekvencije (vjerovatnosti) igrača koji koriste svoje strategije.

Uslovi za korištenje mješovitih strategija

. (1.5)

Ako X* = (X 1 * ….X ja * ... X m*) je optimalna strategija koju odabere prvi igrač; Y* = (at 1 * …at j * ... at n*) je optimalna strategija koju odabere drugi igrač, tada je broj cijena igre.

(1.6)

U redu za broj V bila je cijena igre, i X* I at* - optimalne strategije, potrebno je i dovoljno da nejednakosti

(1.7)

Ako jedan od igrača koristi optimalnu mješovitu strategiju, onda je njegova isplata jednaka cijeni igre V bez obzira na učestalost kojom će drugi igrač primjenjivati strategije uključene u optimalnu, uključujući i čiste strategije.

Svođenje problema teorije igara na probleme linearnog programiranja.

Primjer. Pronađite rješenje za igru definiranu matricom isplate A.

A = (1.8)

y 1 y 2 y 3

Rješenje:

Hajde da sastavimo dualni par zadataka linearnog programiranja.

Za prvog igrača

(1.9)

at 1 +at 2 +at 3 = 1 (1.10)

Oslobodite se varijable V(cijena igre), lijevu i desnu stranu izraza (1.9), (1.10) podijelimo sa V. Prihvativši at j /V za novu varijablu z i, dobijamo novi sistem ograničenja (1.11) i ciljna funkcija (1.12)

(1.11)

. (1.12)

Slično, dobijamo model igre za drugog igrača:

(1.13)

X 1 +X 2 +X 3 = 1 . (1.14)

Svođenje modela (1.13), (1.14) na oblik bez varijable V, dobijamo

(1.15)

, (1.16)

Gdje
.

Ako trebamo odrediti strategiju ponašanja prvog igrača, tj. relativna učestalost korištenja njegovih strategija ( X 1 ….X i …X m), koristićemo model drugog igrača, jer ove varijable su u njegovom modelu isplate (1.13), (1.14).

(1.15), (1.16) svodimo na kanonski oblik

(1.17)

Teorija igara - agregat matematičke metode rješavanje konfliktnih situacija (sukoba interesa). U teoriji igara, igra je matematički model konfliktne situacije. Predmet od posebnog interesa u teoriji igara je proučavanje strategija donošenja odluka učesnika igre u uslovima neizvesnosti. Neizvjesnost je zbog činjenice da dvije ili više strana teže suprotnim ciljevima, a rezultati bilo koje akcije svake od strana zavise od poteza partnera. Istovremeno, svaka od strana nastoji donijeti optimalne odluke koje u najvećoj mjeri ostvaruju postavljene ciljeve.

Teorija igara se najdosljednije primjenjuje u privredi, gdje nastaju konfliktne situacije, na primjer, u odnosima između dobavljača i potrošača, kupca i prodavca, banke i klijenta. Primjena teorije igara može se naći i u politici, sociologiji, biologiji i vojnoj umjetnosti.

Iz istorije teorije igara

Istorija teorije igara kao samostalna disciplina počinje 1944. godine, kada su John von Neumann i Oscar Morgenstern objavili knjigu "Theory of Games and Economic Behavior" ("Theory of Games and Economic Behavior"). Iako su se primjeri teorije igara susretali i ranije: babilonski Talmudski traktat o podjeli imovine pokojnog muža između njegovih žena, kartaške igre u 18. stoljeću, razvoj teorije šaha početkom 20. stoljeća, dokaz minimaks teoreme istog Džona fon Nojmana 1928. godine, bez koje ne bi bilo teorije igara.

1950-ih Melvin Drescher i Meryl Flood iz Rand Corporation Prvi koji je eksperimentalno primijenio zatvoreničku dilemu, John Nash, u svom radu o stanju ravnoteže u igrama za dvije osobe, razvio je koncept Nešove ravnoteže.

Reinhard Salten je 1965. objavio knjigu "Oligopolska obrada u teoriji igara na zahtjev" ("Spieltheoretische Behandlung eines Oligomodells mit Nachfrageträgheit"), kojom je primjena teorije igara u ekonomiji dobila novu pokretačku snagu. Korak naprijed u evoluciji teorije igara povezan je s radom Johna Maynarda Smitha "Evolutionary Stable Strategy" ("Evolutionary Stable Strategy", 1974). Zatvorenikova dilema popularizovana je u knjizi Roberta Akselroda Evolucija saradnje, objavljenoj 1984. Godine 1994., John Nash, John Harsanyi i Reinhard Salten dobili su Nobelovu nagradu za teoriju igara.

Teorija igara u životu i poslu

Zaustavimo se detaljnije na suštini konfliktne situacije (sukoba interesa) u smislu kako se ona shvata u teoriji igara za dalje modelovanje različitih situacija u životu i poslu. Neka pojedinac bude u poziciji koja vodi do jednog od nekoliko mogućih ishoda, a pojedinac ima neke lične preferencije u odnosu na te ishode. Ali iako može u određenoj mjeri kontrolisati varijabilne faktore koji određuju ishod, on nema potpunu kontrolu nad njima. Ponekad je kontrola u rukama nekoliko pojedinaca koji, poput njega, imaju određene preferencije za moguće ishode, ali u opšti slučaj interesi ovih pojedinaca se ne slažu. U drugim slučajevima, konačni ishod može zavisiti i od nesreća (koje se u pravnim naukama ponekad nazivaju prirodne katastrofe) i od drugih pojedinaca. Teorija igara sistematizira opažanja takvih situacija i formuliše opšti principi da vodi razumnu akciju u takvim situacijama.

U nekim aspektima, naziv "teorija igara" je nesretan, jer sugeriše da se teorija igara bavi samo društvena vrijednost sukobi koji se dešavaju u salonskim igrama, ali ipak ova teorija ima mnogo šire značenje.

Sljedeća ekonomska situacija može dati ideju o primjeni teorije igara. Pretpostavimo da postoji nekoliko preduzetnika, od kojih svaki nastoji da maksimizira profit, dok ima samo ograničenu moć nad varijablama koje određuju ovaj profit. Preduzetnik nema kontrolu nad varijablama koje kontroliše drugi preduzetnik, ali koje mogu u velikoj meri uticati na prihod prvog. Tumačenje ove situacije kao igre može dovesti do sljedećeg prigovora. Model igre pretpostavlja da svaki poduzetnik napravi jedan izbor iz područja mogućih izbora, a profit je određen tim pojedinačnim izborima. Očigledno je da je to u stvarnosti gotovo nemoguće, jer u ovom slučaju u industriji ne bi bili potrebni složeni administrativni aparati. Samo što postoji niz odluka i modifikacija ovih odluka koje zavise od izbora drugih učesnika. ekonomski sistem(igrači). Ali u principu, može se zamisliti da svaki administrator predviđa sve moguće nepredviđene situacije i detaljno opisuje radnju koju treba poduzeti u svakom slučaju, umjesto da rješava svaki zadatak kako se pojavi.

Vojni sukob, po definiciji, je sukob interesa u kojem nijedna strana nema potpunu kontrolu nad varijablama koje određuju ishod, o čemu odlučuje niz bitaka. Možete jednostavno smatrati ishod kao pobjedu ili poraz i dodijeliti im numeričke vrijednosti 1 i 0.

Jedna od najjednostavnijih konfliktnih situacija koja se može zapisati i riješiti u teoriji igara je dvoboj, koji predstavlja sukob između dva igrača 1 i 2, koji imaju str I q shots. Za svakog igrača postoji funkcija koja pokazuje vjerovatnoću da je igrač pogodio i u to vrijeme tće dati pogodak koji će se pokazati fatalnim.

Kao rezultat, teorija igara dolazi do sljedeće formulacije određene klase sukoba interesa: postoje n igrača, a svaki igrač mora izabrati jednu mogućnost iz određenog skupa od 100, a prilikom izbora igrač nema nikakve informacije o izborima drugih igrača. Područje mogućeg izbora igrača može sadržavati stavke kao što su "pomicanje pikovog asa", "proizvodi tenkove umjesto automobila" ili u opšti smisao, strategija koja definiše sve radnje koje treba preduzeti u svim mogućim okolnostima. Svaki igrač je suočen sa zadatkom: kakav izbor treba da napravi da bi mu njegov privatni uticaj na ishod doneo što veći dobitak?

Matematički model u teoriji igara i formalizacija problema

Kao što smo već primetili, igra je matematički model konfliktna situacija i zahtijeva sljedeće komponente:

zainteresovane strane;
moguće akcije na svakoj strani;
interese stranaka.

Stranke zainteresirane za igru nazivaju se igračima. , svaki od njih može poduzeti najmanje dvije akcije (ako igrač ima samo jednu akciju, onda on zapravo ne učestvuje u igri, jer se unaprijed zna šta će poduzeti). Ishod igre se zove pobjeda. .

Prava konfliktna situacija nije uvijek, ali igra (u konceptu teorije igara) - uvijek - teče određena pravila , koji tačno definišu:

opcije igrača;
količina informacija koje svaki igrač ima o ponašanju partnera;
isplati do koje svaki skup radnji vodi.

Primjeri formaliziranih igara su fudbal, kartaška igra, šah.

Ali u ekonomiji se javlja model ponašanja igrača, na primjer, kada nekoliko firmi nastoji zauzeti povoljnije mjesto na tržištu, nekoliko pojedinaca pokušava podijeliti neko dobro (resurse, finansije) među sobom kako bi svi dobili što više . Učesnici u konfliktnim situacijama u ekonomiji koji se mogu modelirati kao igra su firme, banke, pojedinci i drugi ekonomski subjekti. Zauzvrat, u ratnim uslovima, model igre se koristi, na primjer, u odabiru više najbolje oružje(od dostupnih ili potencijalno mogućih) za poraz neprijatelja ili zaštitu od napada.

Igru karakterizira neizvjesnost rezultata . Uzroci nesigurnosti mogu se podijeliti u sljedeće grupe:

kombinatorni (kao u šahu);
utjecaj nasumičnih faktora (kao u igri "glava ili rep", kockice, kartaške igre);
strateški (igrač ne zna koju će akciju protivnik preduzeti).

Strategija igrača je skup pravila koja određuju njegove akcije pri svakom potezu, ovisno o situaciji.

Cilj teorije igara je odrediti optimalnu strategiju za svakog igrača. Odrediti takvu strategiju znači riješiti igru. Optimalnost strategije se postiže kada jedan od igrača mora dobiti maksimalnu isplatu, dok se drugi pridržava svoje strategije. A drugi igrač bi trebao imati minimalan gubitak ako se prvi drži svoje strategije.

Klasifikacija igre

Klasifikacija po broju igrača (igra dvije ili više osoba). Igre za dvije osobe su centralne za svu teoriju igara. Osnovni koncept teorije igara za igre s dvije osobe je generalizacija vrlo bitne ideje ravnoteže, koja se prirodno pojavljuje u igrama dvije osobe. Što se igara tiče n osoba, onda je jedan dio teorije igara posvećen igrama u kojima je zabranjena saradnja između igrača. U drugom dijelu teorije igara n osoba, pretpostavlja se da igrači mogu sarađivati na obostranu korist (vidi dalje u ovom paragrafu o nekooperativnim i kooperativnim igrama).
Klasifikacija prema broju igrača i njihovim strategijama (broj strategija je najmanje dvije, može biti beskonačan).
Klasifikacija prema količini informacija u vezi prošlih poteza: igre sa potpunim informacijama i nepotpunim informacijama. Neka postoje igrač 1 - kupac i igrač 2 - prodavac. Ako igrač 1 nema potpune informacije o akcijama igrača 2, tada igrač 1 možda neće razlikovati dvije alternative između kojih mora birati. Na primjer, birati između dvije vrste određenog proizvoda, a ne znati da je, prema nekim karakteristikama, proizvod A gore od robe B, igrač 1 možda neće vidjeti razliku između alternativa.
Klasifikacija prema principima podjele dobitaka : zadružni, koalicioni s jedne strane i nekooperativni, nekooperativni s druge strane. IN nekooperativna igra , ili na drugi način - nekooperativna igra , igrači biraju strategije istovremeno, a da ne znaju koju će strategiju izabrati drugi igrač. Komunikacija između igrača nije moguća. IN kooperativna igra , ili na drugi način - koaliciona igra , igrači mogu formirati koalicije i poduzeti kolektivne akcije kako bi povećali svoje dobitke.
Igra za dvije osobe s konačnom nultom sumom ili je antagonistička igra strateška igra sa potpunim informacijama koje uključuju strane sa suprotnim interesima. Antagonističke igre su matrične igre .

Klasičan primjer iz teorije igara je dilema zatvorenika.

Dvojica osumnjičenih su privedeni i izolovani jedan od drugog. Okružni tužilac je uvjeren da su počinili teško krivično djelo, ali nema dovoljno dokaza da ih optuži na suđenju. Svakom od zatvorenika kaže da ima dvije alternative: priznati zločin za koji policija vjeruje da ga je počinio ili ne priznati. Ako oboje ne priznaju, onda će ih okružni tužilac optužiti za neko lakše krivično djelo, poput sitne krađe ili nedozvoljenog posjedovanja oružja, a oboje će dobiti malu kaznu. Ako oboje priznaju, biće krivično gonjeni, ali za to neće biti potrebna najstroža kazna. Ako jedan prizna, a drugi ne prizna, onda će priznatom licu biti ublažena kazna za izručenje saučesnika, dok će tvrdoglavi dobiti "do kraja".

Ako se ovaj strateški zadatak formuliše u smislu zaključka, onda se on svodi na sljedeće:

Dakle, ako oba zatvorenika ne priznaju, dobiće po 1 godinu. Ako oboje priznaju, onda će svaki dobiti 8 godina. A ako jedan prizna, drugi ne, onda će onaj ko prizna dobiti tri mjeseca zatvora, a onaj koji ne prizna će dobiti 10 godina. Gornja matrica ispravno odražava dilemu zatvorenika: svako je suočen sa pitanjem priznati ili ne priznati. Igra koju okružni tužilac nudi zatvorenicima je nekooperativna igra ili na drugi način - nekoalicionoj igri . Ako su oba zatvorenika bila u mogućnosti da sarađuju (tj. igra bi bila kooperativna ili na neki drugi način koaliciona igra ), tada oboje nisu htjeli priznati i dobili su po godinu dana zatvora.

Primjeri upotrebe matematičkih sredstava teorije igara

Sada prelazimo na razmatranje rješenja primjera uobičajenih klasa igara za koje postoje metode istraživanja i rješenja u teoriji igara.

Primjer formalizacije nekooperativne (nekooperativne) igre dvije osobe

U prethodnom pasusu smo već razmatrali primjer nekooperativne (nekooperativne) igre (zatvorenika dilema). Učvrstimo svoje vještine. Za to je prikladna i klasična radnja inspirirana Avanturama Šerloka Holmesa Artura Konana Dojla. Može se, naravno, prigovoriti: primjer nije iz života, već iz književnosti, ali Conan Doyle se nije etablirao kao pisac naučne fantastike! Klasičan i po tome što je zadatak izvršio Oscar Morgenstern, kao što smo već utvrdili - jedan od osnivača teorije igara.

Primjer 1 Biće dat skraćeni odlomak iz jedne od Avantura Šerloka Holmesa. Prema poznatim konceptima teorije igara, kreirajte model konfliktne situacije i formalno zapišite igru.

Sherlock Holmes namjerava otići iz Londona u Dover s daljnjim ciljem da stigne do kontinenta (evropskog) kako bi pobjegao od profesora Moriartyja koji ga juri. Ušavši u voz, ugleda profesora Moriartyja na peronu stanice. Sherlock Holmes priznaje da Moriarty može izabrati poseban voz i prestići ga. Sherlock Holmes ima dvije alternative: nastaviti do Dovera ili sići na stanici Canterbury, koja je jedina međustanica na njegovoj ruti. Pretpostavljamo da je njegov protivnik dovoljno inteligentan da odredi Holmesove opcije, tako da ima iste dvije alternative. Oba protivnika moraju izabrati stanicu u kojoj će izaći iz voza, ne znajući kakvu će odluku svako od njih donijeti. Ako, kao rezultat odluke, oboje završe na istoj stanici, onda definitivno možemo pretpostaviti da će Sherlocka Holmesa ubiti profesor Moriarty. Ako Sherlock Holmes bezbedno stigne u Dover, biće spašen.

Rješenje. Heroji Conan Doylea mogu se smatrati učesnicima u igri, odnosno igračima. Na raspolaganju svakom igraču i (i=1,2) dvije čiste strategije:

sići u Doveru (strategija si1 ( i=1,2) );
sići na usputnoj stanici (strategija si2 ( i=1,2) )

Ovisno o tome koju od dvije strategije svaki od dva igrača odabere, kreirat će se posebna kombinacija strategija kao par s = (s1 , s 2 ) .

Svaka kombinacija može biti povezana s događajem - ishodom pokušaja ubistva Sherlocka Holmesa od strane profesora Moriartyja. Pravimo matricu ove igre sa mogućim događajima.

Ispod svakog od događaja naveden je indeks, koji označava nabavku profesora Moriartyja, a izračunava se ovisno o Holmesovom spasu. Oba heroja biraju strategiju istovremeno, ne znajući šta će protivnik izabrati. Dakle, igra je nekooperativna, jer, prvo, igrači su u različitim vozovima, a drugo, imaju suprotne interese.

Primjer formalizacije i rješenja kooperativne (koalicione) igre n osobe

U ovom trenutku, praktičnom dijelu, odnosno toku rješavanja primjera zadatka, prethodiće teorijski dio u kojem ćemo se upoznati sa konceptima teorije igara za rješavanje kooperativnih (nekooperativnih) igara. Za ovaj zadatak teorija igara predlaže:

karakteristična funkcija (jednostavno rečeno, odražava vrijednost koristi od udruživanja igrača u koaliciju);
koncept aditivnosti (svojstvo veličina, koje se sastoji u činjenici da je vrijednost količine koja odgovara cijelom objektu jednaka zbroju vrijednosti količina koje odgovaraju njegovim dijelovima, u određenoj klasi podjele objekta na dijelove) i superaditivnost (vrijednost količine koja odgovara cijelom objektu veća je od zbira vrijednosti veličina koje odgovaraju njegovim dijelovima) karakteristične funkcije.

Superaditivnost karakteristične funkcije ukazuje da su koalicije korisne za igrače, jer u ovom slučaju isplata koalicije raste sa brojem igrača.

Da bismo formalizirali igru, moramo uvesti formalnu notaciju za gornje koncepte.

Za igru n označimo skup svih njegovih igrača kao N= (1,2,...,n) Bilo koji neprazan podskup skupa N označeno kao T(uključujući i sebe N i svi podskupovi koji se sastoje od jednog elementa). Postoji aktivnost na stranici Skupovi i operacije nad skupovima, koji se otvara u novom prozoru kada kliknete na vezu.

Karakteristična funkcija je označena kao v a njegov domen definicije se sastoji od mogućih podskupova skupa N. v(T) - vrijednost karakteristične funkcije za određeni podskup, na primjer, prihod koji je primila koalicija, uključujući, eventualno, jednog igrača. Ovo je važno jer teorija igara zahtijeva provjeru prisutnosti superaditivnosti za vrijednosti karakteristične funkcije svih koalicija koje se ne preklapaju.

Za dvije neprazne koalicije podskupova T1 I T2 aditivnost karakteristične funkcije kooperativne (koalicione) igre zapisuje se na sljedeći način:

A superaditivnost je ovakva:

Primjer 2 Troje učenika muzičke škole dodatno zarađuje u različitim klubovima, prihod primaju od posetilaca kluba. Utvrdite da li im je isplativo udružiti snage (ako jeste, pod kojim uslovima), koristeći koncepte teorije igara za rješavanje kooperativnih igara n lica, sa sljedećim početnim podacima.

U prosjeku, njihov prihod po večeri je bio:

violinista ima 600 jedinica;
gitarista ima 700 jedinica;
pevač ima 900 jedinica.

U pokušaju da povećaju prihod, studenti su nekoliko mjeseci stvarali različite grupe. Rezultati su pokazali da bi, udruživanjem, mogli povećati svoj večernji prihod na sljedeći način:

violinista + gitarista zaradio 1500 jedinica;
violinista + pjevač zaradio 1800 jedinica;
gitarista + pjevač zaradio 1900 jedinica;
violinista + gitarista + pjevač zaradio 3000 jedinica.

Rješenje. U ovom primjeru, broj učesnika u igri n= 3, dakle, domen karakteristične funkcije igre sastoji se od 2³ = 8 mogućih podskupova skupa svih igrača. Nabrojimo sve moguće koalicije T:

koalicije jednog elementa, od kojih se svaki sastoji od jednog igrača - muzičara: T{1} , T{2} , T{3} ;
koalicije dva elementa: T{1,2} , T{1,3} , T{2,3} ;
koalicija tri elementa: T{1,2,3} .

Svakom od igrača dodjeljujemo serijski broj:

violinista - 1. svirač;
gitarista - 2. svirač;
pevač je treći igrač.

Prema podacima problema određujemo karakterističnu funkciju igre v:

v(T(1)) = 600; v(T(2)) = 700; v(T(3)) = 900; ove vrijednosti karakteristične funkcije određuju se na osnovu isplata prvog, drugog i trećeg igrača, respektivno, kada nisu udruženi u koalicije;

v(T(1,2)) = 1500; v(T(1,3)) = 1800; v(T(2,3)) = 1900; ove vrijednosti karakteristične funkcije određene su prihodima svakog para igrača udruženih u koalicije;

v(T(1,2,3)) = 3000; ova vrijednost karakteristične funkcije određena je prosječnim prihodom u slučaju kada su igrači bili ujedinjeni u trojke.

Dakle, naveli smo sve moguće koalicije igrača, njih je osam, kako bi i trebalo biti, budući da se domen definicije karakteristične funkcije igre sastoji od tačno osam mogućih podskupova skupa svih igrača. To je ono što teorija igara zahtijeva, budući da moramo provjeriti prisustvo superaditivnosti za vrijednosti karakteristične funkcije svih koalicija koje se ne preklapaju.

Kako su ispunjeni uvjeti superaditivnosti u ovom primjeru? Hajde da definišemo kako igrači formiraju koalicije koje se ne preklapaju T1 I T2 . Ako su neki od igrača u koaliciji T1 , onda su svi ostali igrači u koaliciji T2 a po definiciji se ova koalicija formira kao razlika između ukupnog skupa igrača i seta T1 . Onda ako T1 - koalicija od jednog igrača, pa u koaliciji T2 biće drugi i treći igrač, ako su u koaliciji T1 biće prvi i treći igrač, zatim koalicija T2 će se sastojati samo od drugog igrača i tako dalje.