Iz teorije igara je poznato da ako igrač “A” koristi svoju optimalnu strategiju, a igrač “B” ostaje u okviru svojih aktivnih strategija, tada prosječna isplata ostaje nepromijenjena i jednaka je cijeni igre. v bez obzira na to kako igrač "B" ​​koristi svoje aktivne strategije. A u našem slučaju obje strategije su aktivne, inače bi igra imala rješenje u čistim strategijama. Stoga, ako pretpostavimo da će igrač "B" ​​koristiti čistu strategiju B 1, tada je prosječna isplata v bit će:

k 11 p 1 + k 21 p 2 = v (1)

Gdje: k ij - elementi matrice plaćanja.

S druge strane, ako pretpostavimo da će igrač "B" ​​koristiti čistu strategiju B 2, tada će prosječna isplata biti:

k 12 p 1 + k 22 p 2 = v (2)

Izjednačavanjem lijevih strana jednadžbi (1) i (2) dobivamo:

k 11 p 1 + k 21 p 2 = k 12 p 1 + k 22 p 2

A uzimajući u obzir činjenicu da str 1 + str 2 = 1 imamo:

k 11 p 1 + k 21 (1 - p 1 ) = k 12 p 1 + k 22 (1 - p 1 )

U ovom zadatku:

Iz teorije igara je poznato da ako igrač "B" ​​koristi svoju optimalnu strategiju, a igrač "A" ostaje u okviru svojih aktivnih strategija, tada prosječna isplata ostaje nepromijenjena i jednaka je cijeni igre. v bez obzira na to kako igrač A koristi svoje aktivne strategije. Stoga, ako pretpostavimo da će igrač "A" koristiti čistu strategiju A 1, tada je prosječna isplata v bit će:

k 11 q 1 + k 12 q 2 = v (4)

U ovom zadatku:

Odgovor:

Geometrijska interpretacija (grafičko rješenje):

Slika 1.
Grafikon isplata k od frekvencije str 2 , kada neprijatelj koristi strategiju B 1.

Pretpostavimo sada da će igrač "B" ​​koristiti strategiju B 2 u svom čistom obliku. Tada, ako mi (igrač “A”) koristimo čistu strategiju A 1, tada će naša isplata biti 5. Ako koristimo čistu strategiju A 2, tada će naša isplata biti 3/2 (vidi sliku 2). Slično tome, ako pomiješamo strategije A 1 i A 2 u različitim omjerima, naši će se dobici mijenjati duž ravne linije koja prolazi kroz točke s koordinatama (0, 5) i (1, 3/2), nazovimo to linijom strategije B 2. Kao iu prethodnom slučaju, apscisa bilo koje točke na ovoj liniji jednaka je vjerojatnosti s kojom primjenjujemo strategiju A 2, a ordinata je rezultirajući dobitak, ali samo za strategiju B 2 (vidi sliku 2).

Slika 2.
v i optimalnu frekvenciju str 2 za igrača "A".

U stvarnoj igri, kada razuman igrač "B" ​​koristi sve svoje strategije, naši će se dobici mijenjati duž isprekidane linije prikazane na slici 2 crvenom bojom. Ova linija definira tzv donja granica dobitaka. Očito, najviša točka ove isprekidane linije odgovara našoj optimalnoj strategiji. U ovom slučaju to je točka sjecišta linija strategija B 1 i B 2. Imajte na umu da ako odaberete učestalost str 2 jednak svojoj apscisi, tada će naš dobitak ostati nepromijenjen i jednak v za bilo koju strategiju igrača "B", osim toga, to će biti maksimum koji sami sebi možemo jamčiti. Učestalost (vjerojatnost) str 2 , u ovom slučaju, je odgovarajuća učestalost naše optimalne mješovite strategije. Usput, sa slike 2 možete vidjeti frekvenciju str 1 , naša optimalna mješovita strategija, duljina je segmenta [ str 2 ; 1] na x-osi. (To je zato što str 1 + str 2 = 1 )

Koristeći potpuno sličan način razmišljanja, možemo pronaći frekvencije optimalne strategije za igrača "B", što je ilustrirano na slici 3.

Slika 3.
Grafičko određivanje cijene igre v i optimalnu frekvenciju q 2 za igrača "U".

Samo za njega treba tzv gornja granica gubitka(crvena isprekidana linija) i potražite najnižu točku na njoj, jer za igrača "B" cilj je minimizirati gubitke. Ista vrijednost frekvencije q 1 , ovo je duljina segmenta [ q 2 ; 1] na x-osi.

Odjeljak "Teorija igara" predstavljen je s tri online kalkulatori:

1. Optimalne strategije igrača. U takvim problemima navedena je matrica plaćanja. Potrebno je pronaći čiste ili mješovite strategije igrača i, cijena igre. Za rješavanje morate navesti dimenziju matrice i metodu rješenja. Usluga implementira sljedeće metode za rješavanje igre za dva igrača:
   1. Minimax. Ako trebate pronaći čistu strategiju igrača ili odgovoriti na pitanje o sedloj točki igre, odaberite ovu metodu rješenja.
   2. Simpleks metoda. Koristi se za rješavanje mješovitih strateških igara pomoću metoda linearnog programiranja.
   3. Grafička metoda. Koristi se za rješavanje mješovitih strateških igara. Ako postoji sedlasta točka, rješenje se zaustavlja. Primjer: Zadana je matrica isplate, pronađite optimalne mješovite strategije igrača i cijenu igre pomoću grafičke metode rješavanja igre.
   4. Brown-Robinsonova iterativna metoda. Iterativna metoda se koristi kada je grafička metoda neprimjenjiva i kada algebarska i matrična metoda nisu praktički primjenjive. Ova metoda daje približnu vrijednost cijene igre, a prava vrijednost može se dobiti s bilo kojim željenim stupnjem točnosti. Ova metoda nije dovoljna za pronalaženje optimalnih strategija, ali vam omogućuje da pratite dinamiku igre na poteze i odredite cijenu igre za svakog igrača na svakom koraku.
   Na primjer, zadatak može zvučati kao "naznačite optimalne strategije igrača za igru ​​dane matricom isplate".
   Sve metode koriste provjeru dominantnih redaka i stupaca.
2. Igra Bimatrix. Obično se u takvoj igri zadaju dvije matrice iste veličine isplata prvog i drugog igrača. Redovi ovih matrica odgovaraju strategijama prvog igrača, a stupci matrica odgovaraju strategijama drugog igrača. U ovom slučaju prva matrica predstavlja dobitak prvog igrača, a druga matrica predstavlja dobitak drugog.
3. Igre s prirodom. Koristi se kada je potrebno odabrati upravljačku odluku prema kriterijima Maximaxa, Bayesa, Laplacea, Walda, Savagea, Hurwitza.
   Za Bayesov kriterij također će biti potrebno unijeti vjerojatnosti događanja događaja. Ako nisu navedeni, ostavite zadane vrijednosti (bit će ekvivalentni događaji).
   Za Hurwitzov kriterij navedite razinu optimizma λ. Ako ovaj parametar nije naveden u uvjetima, možete koristiti vrijednosti 0, 0,5 i 1.

Mnogi problemi zahtijevaju pronalaženje rješenja pomoću računala. Navedene usluge i funkcije jedan su od alata.

Teorija igara - skup matematičkih metoda za rješavanje konfliktnih situacija (sukoba interesa). U teoriji igara igra se naziva matematički model konfliktne situacije. Predmet od posebnog interesa teorije igara je proučavanje strategija donošenja odluka sudionika igre u uvjetima neizvjesnosti. Neizvjesnost proizlazi iz činjenice da dvije ili više strana teže suprotnim ciljevima, a rezultati svake akcije svake strane ovise o potezima partnera. Pritom svaka strana nastoji donositi optimalne odluke koje u najvećoj mjeri ostvaruju postavljene ciljeve.

Teorija igara najdosljednije se primjenjuje u ekonomiji, gdje dolazi do konfliktnih situacija, primjerice, u odnosu dobavljača i potrošača, kupca i prodavača, banke i klijenta. Primjena teorije igara nalazi se iu politici, sociologiji, biologiji i vojnoj umjetnosti.

Iz povijesti teorije igara

Povijest teorije igara kao samostalna disciplina započela je 1944. godine, kada su John von Neumann i Oscar Morgenstern objavili knjigu “The Theory of Games and Economic Behavior”. Iako su se primjeri teorije igara susreli i ranije: rasprava Babilonskog Talmuda o podjeli imovine preminulog muža između njegovih žena, kartaške igre u 18. stoljeću, razvoj teorije šaha početkom 20. stoljeća, dokaz teorema o minimaksu istog Johna von Neumanna iz 1928. godine, bez kojeg ne bi bilo teorije igara.

50-ih godina 20. stoljeća Melvin Drescher i Meryl Flood iz Rand Corporation John Nash, prvi koji je eksperimentalno primijenio zatvorenikovu dilemu, razvio je koncept Nashove ravnoteže u svojim radovima o stanju ravnoteže u igrama dvoje ljudi.

Reinhard Salten objavio je 1965. godine knjigu "Tretman oligopola u teoriji igara na zahtjev" ("Spieltheoretische Behandlung eines Oligomodells mit Nachfrageträgheit"), kojom je primjena teorije igara u ekonomiji dobila novi pokretač. Korak naprijed u evoluciji teorije igara povezan je s radom Johna Maynarda Smitha, “Evolutionary Stable Strategy” (1974). Zatvorenikova dilema popularizirana je u knjizi Roberta Axelroda The Evolution of Cooperation iz 1984. godine. Godine 1994. John Nash, John Harsanyi i Reinhard Selten dobili su Nobelovu nagradu za svoj doprinos teoriji igara.

Teorija igara u životu i poslovanju

Zadržimo se detaljnije na suštini konfliktne situacije (sukoba interesa) u smislu kako se ona shvaća u teoriji igara za daljnje modeliranje različitih situacija u životu i poslovanju. Neka je pojedinac u poziciji koja vodi do jednog od nekoliko mogućih ishoda, a pojedinac ima neke osobne preferencije u vezi s tim ishodima. No iako može donekle kontrolirati varijable koje određuju ishod, on nema potpunu moć nad njima. Ponekad je kontrola u rukama nekoliko pojedinaca koji, poput njega, imaju neke preferencije u odnosu na moguće ishode, ali općenito interesi tih pojedinaca nisu konzistentni. U drugim slučajevima, konačni ishod može ovisiti i o slučaju (koji se u pravnoj znanosti ponekad naziva prirodnim katastrofama) i o drugim pojedincima. Teorija igara sistematizira opažanja takvih situacija i formuliranje općih načela za vođenje inteligentnih radnji u takvim situacijama.

U nekim aspektima, naziv "teorija igara" je nesretan, jer sugerira da se teorija igara bavi samo društveno beznačajnim susretima koji se događaju u salonskim igrama, ali unatoč tome teorija ima mnogo šire značenje.

Sljedeća ekonomska situacija može dati ideju o primjeni teorije igara. Pretpostavimo da postoji nekoliko poduzetnika, od kojih svaki teži postizanju najvećeg profita, dok ima samo ograničenu moć nad varijablama koje određuju taj profit. Poduzetnik nema moć nad varijablama koje drugi poduzetnik kontrolira, ali koje mogu uvelike utjecati na prihode prvog. Tretiranje ove situacije kao igre može izazvati sljedeći prigovor. U modelu igre pretpostavlja se da svaki poduzetnik donosi jedan izbor iz niza mogućih izbora, a ti pojedinačni izbori određuju profit. Očito, to se gotovo ne može dogoditi u stvarnosti, jer u tom slučaju u industriji ne bi bili potrebni složeni aparati za upravljanje. Jednostavno postoji niz odluka i modifikacija tih odluka koje ovise o izborima drugih sudionika u ekonomskom sustavu (igrača). Ali u načelu se može zamisliti da neki administrator predviđa sve moguće nepredviđene situacije i detaljno opisuje radnje koje treba poduzeti u svakom slučaju, umjesto da svaki problem rješava kako se pojavi.

Vojni sukob, po definiciji, je sukob interesa u kojem niti jedna strana nema potpunu kontrolu nad varijablama koje određuju ishod, koji se odlučuje nizom bitaka. Ishod možete jednostavno smatrati pobjedom ili gubitkom i dodijeliti im brojčane vrijednosti 1 i 0.

Jedna od najjednostavnijih konfliktnih situacija koja se može zapisati i riješiti u teoriji igara je dvoboj, koji je sukob između dva igrača 1 i 2, koji imaju redom str I q snimke. Za svakog igrača postoji funkcija koja pokazuje vjerojatnost da je igrač pogodio ja u određenom trenutku t zadat će udarac koji će biti koban.

Kao rezultat toga, teorija igara dolazi do sljedeće formulacije određene klase sukoba interesa: postoje n igrača, a svaki treba izabrati jednu opciju iz stotinjak određenih skupova, a prilikom odabira igrač nema informacije o izborima ostalih igrača. Područje mogućeg izbora igrača može sadržavati elemente kao što su "igranje asa pik", "proizvodnja tenkova umjesto automobila", ili općenito, strategiju koja definira sve akcije koje treba poduzeti u svim mogućim okolnostima. Svaki se igrač nalazi pred zadatkom: što odabrati kako bi njegov osobni utjecaj na ishod donio najveću moguću pobjedu?

Matematički model u teoriji igara i formalizacija problema

Kao što smo već primijetili, igra je matematički model konfliktne situacije i zahtijeva sljedeće komponente:

1. zainteresirane stranke;
2. moguće akcije na svakoj strani;
3. interese stranaka.

Strane zainteresirane za igru ​​nazivaju se igrači , svaki od njih može poduzeti najmanje dvije akcije (ako igrač ima samo jednu akciju na raspolaganju, onda on zapravo ne sudjeluje u igri, jer se unaprijed zna što će poduzeti). Ishod igre naziva se dobitak .

Prava konfliktna situacija nije uvijek, ali se igra (u konceptu teorije igara) uvijek odvija prema određena pravila , koji precizno određuju:

1. opcije za akcije igrača;
2. količinu informacija koje svaki igrač ima o ponašanju svog partnera;
3. isplativost do koje vodi svaki skup radnji.

Primjeri formaliziranih igara uključuju nogomet, kartaške igre i šah.

Ali u ekonomiji se pojavljuje model ponašanja igrača, na primjer, kada nekoliko tvrtki nastoji zauzeti povoljnije mjesto na tržištu, nekoliko pojedinaca pokušava među sobom podijeliti neko dobro (resurse, financije) tako da svatko dobije što je više moguće . Sudionici u konfliktnim situacijama u gospodarstvu, koje se mogu modelirati kao igra, su poduzeća, banke, pojedinci i drugi gospodarski subjekti. S druge strane, u ratnim uvjetima, model igre se koristi, primjerice, u odabiru najboljeg oružja (od postojećeg ili potencijalnog) za poraz neprijatelja ili zaštitu od napada.

Igru karakterizira neizvjesnost ishoda . Razlozi nesigurnosti mogu se podijeliti u sljedeće skupine:

1. kombinatorika (kao u šahu);
2. utjecaj slučajnih čimbenika (kao u igri "glava ili rep", kocke, kartaške igre);
3. strateški (igrač ne zna koju će akciju poduzeti neprijatelj).

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

Svrha teorije igara je odrediti optimalnu strategiju za svakog igrača. Određivanje takve strategije znači rješavanje igre. Optimalnost strategije se postiže kada jedan od igrača treba ostvariti maksimalnu pobjedu, dok se drugi drži svoje strategije. I drugi bi igrač trebao imati minimalan gubitak ako se prvi drži svoje strategije.

Klasifikacija igara

1. Razvrstavanje po broju igrača (igra dvije ili više osoba). Igre za dvije osobe zauzimaju središnje mjesto u cjelokupnoj teoriji igara. Temeljni koncept teorije igara za igre u dvoje je generalizacija vrlo značajne ideje o ravnoteži koja se prirodno pojavljuje u igrama u dvoje. Što se igrica tiče n pojedinaca, onda je jedan dio teorije igara posvećen igrama u kojima je zabranjena suradnja između igrača. U drugom dijelu teorije igara n pojedinci pretpostavljaju da igrači mogu surađivati ​​na obostranu korist (vidi kasnije u ovom paragrafu o nekooperativnim i kooperativnim igrama).
2. Klasifikacija prema broju igrača i njihovim strategijama (broj strategija je najmanje dvije, može biti beskonačan).
3. Klasifikacija prema količini informacija u odnosu na prošle poteze: igre s potpunim informacijama i nepotpunim informacijama. Neka postoje igrač 1 - kupac i igrač 2 - prodavač. Ako igrač 1 nema potpunu informaciju o postupcima igrača 2, tada igrač 1 možda neće razlikovati dvije alternative između kojih mora napraviti izbor. Na primjer, birati između dvije vrste nekog proizvoda, a ne znati da je, prema nekim karakteristikama, proizvod A lošiji proizvod B, igrač 1 možda neće vidjeti razliku između alternativa.
4. Klasifikacija prema načelima podjele dobitaka : kooperativni, koalicijski s jedne strane i nekooperativni, nekoalicijski s druge strane. U nekooperativna igra , ili drugačije - nekooperativna igra , igrači biraju strategije istovremeno ne znajući koju će strategiju izabrati drugi igrač. Komunikacija između igrača je nemoguća. U kooperativna igra , ili drugačije - koalicijsku igru , igrači mogu formirati koalicije i poduzimati zajedničke akcije kako bi povećali svoje dobitke.
5. Konačna igra s nultim zbrojem za dvije osobe ili antagonistička igra je strateška igra s potpunim informacijama, koja uključuje strane sa suprotnim interesima. Antagonističke igre su matrice igre.

Klasičan primjer iz teorije igara je zatvorenikova dilema.

Dvojica osumnjičenih su privedeni i odvojeni jedan od drugog. Okružno državno odvjetništvo uvjereno je da su počinili teško kazneno djelo, ali nema dovoljno dokaza da ih optuži na suđenju. Svakom zatvoreniku govori da ima dvije mogućnosti: priznati zločin za koji policija vjeruje da je počinio ili ne priznati. Ako oboje ne priznaju, tužitelj će ih optužiti za neki manji zločin, poput sitne krađe ili ilegalnog posjedovanja oružja, i obojica će dobiti malu kaznu. Ako oboje priznaju, bit će kazneno gonjeni, ali on neće tražiti najstrožu kaznu. Ako jedan prizna, a drugi ne, onda će se onome tko je priznao ublažiti kaznu za izručenje suučesnika, a onaj tko bude uporan dobit će “do kraja”.

Ako se ovaj strateški zadatak formulira zaključno, onda se on svodi na sljedeće:

Dakle, ako oba zatvorenika ne priznaju, dobit će po 1 godinu. Ako oboje priznaju, svaki će dobiti 8 godina. A ako jedan prizna, drugi ne prizna, onda će onaj koji je priznao dobiti tri mjeseca zatvora, a onaj koji ne prizna dobit će 10 godina. Gornja matrica ispravno odražava dilemu zatvorenika: svatko je suočen s pitanjem priznati ili ne priznati. Igra koju okružni tužitelj nudi zatvorenicima je nekooperativna igra ili drugačije - nekooperativna igra . Ako su oba zatvorenika imala priliku surađivati ​​(tj. igra bi bila co-op ili drugo koalicijsku igru ), onda obojica ne bi priznali i dobili bi po godinu dana zatvora.

Primjeri korištenja matematičkih alata teorije igara

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

Primjer formalizacije nekooperativne (nekooperativne) igre dviju osoba

U prethodnom odlomku već smo pogledali primjer nekooperativne (nekooperativne) igre (zatvorenikova dilema). Ojačajmo naše vještine. Za to je prikladan i klasični zaplet inspiriran "Avanturama Sherlocka Holmesa" Arthura Conana Doylea. Može se, naravno, prigovoriti: primjer nije iz života, nego iz književnosti, ali Conan Doyle nije se afirmirao kao pisac znanstvene fantastike! Klasik i zato što je zadatak izvršio Oskar Morgenstern, kako smo već utvrdili, jedan od utemeljitelja teorije igara.

Primjer 1. Bit će dat skraćeni sažetak fragmenta jedne od “Avantura Sherlocka Holmesa”. Prema poznatim konceptima teorije igara izraditi model konfliktne situacije i formalno zapisati igru.

Sherlock Holmes namjerava otputovati iz Londona u Dover s daljnjim ciljem da stigne na kontinent (europski) kako bi pobjegao od profesora Moriartyja koji ga progoni. Nakon što je ušao u vlak, ugledao je profesora Moriartyja na peronu stanice. Sherlock Holmes priznaje da Moriarty može izabrati poseban vlak i prestići ga. Sherlock Holmes ima dvije mogućnosti: nastaviti put do Dovera ili sići na stanici Canterbury, koja je jedina međustanica na njegovoj ruti. Prihvaćamo da je njegov protivnik dovoljno inteligentan da odredi Holmesove sposobnosti, tako da ima iste dvije alternative. Oba protivnika moraju izabrati stanicu na kojoj će izaći iz vlaka, ne znajući kakvu će odluku svaki od njih donijeti. Ako, kao rezultat donošenja odluke, obojica završe na istoj postaji, onda možemo sa sigurnošću pretpostaviti da će Sherlocka Holmesa ubiti profesor Moriarty. Ako Sherlock Holmes sigurno stigne u Dover, bit će spašen.

Riješenje. Junake Conana Doylea možemo smatrati sudionicima igre, odnosno igračima. Dostupno svakom igraču ja (ja=1,2) dvije čiste strategije:

• sići u Doveru (strategija si1 ( ja=1,2) );
• sići na međustanici (strategija si2 ( ja=1,2) )

Ovisno o tome koju od dviju strategija odabere svaki od dva igrača, kreirat će se posebna kombinacija strategija u paru s = (s1 , s 2 ) .

Svaka kombinacija može se povezati s događajem - ishodom pokušaja ubojstva Sherlocka Holmesa od strane profesora Moriartyja. Mi stvaramo matricu ove igre s mogućim događajima.

Ispod svakog od događaja nalazi se indeks koji označava stjecanje profesora Moriartyja, a izračunava se ovisno o spasenju Holmesa. Oba heroja biraju strategiju u isto vrijeme, ne znajući što će neprijatelj odabrati. Dakle, igra je nekooperativna jer su, prvo, igrači u različitim vlakovima, a drugo, imaju suprotne interese.

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

U ovom trenutku će praktičnom dijelu, odnosno procesu rješavanja jednog primjera problema, prethoditi teorijski dio u kojem ćemo se upoznati s pojmovima teorije igara za rješavanje kooperativnih (nekooperativnih) igara. Za ovaj zadatak, teorija igara predlaže:

• karakteristična funkcija (jednostavnije rečeno, odražava veličinu koristi od udruživanja igrača u koaliciju);
• koncept aditivnosti (svojstvo količ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 particija objekta na dijelove) i superaditivnost (vrijednost veličine koja odgovara cijelom objektu veća je od zbroja vrijednosti veličina koje odgovaraju njegovim dijelovima) karakteristične funkcije.

Superaditivnost karakteristične funkcije sugerira da je pridruživanje koaliciji korisno za igrače, jer u ovom slučaju vrijednost koalicionog dobitka raste s brojem igrača.

Kako bismo formalizirali igru, moramo uvesti formalne oznake za gornje koncepte.

Za igru n označimo skup svih njegovih igrača kao N= (1,2,...,n) Svaki neprazan podskup skupa N označimo to kao T(uključujući sebe N i svi podskupovi koji se sastoje od jednog elementa). Postoji lekcija na web mjestu " Skupovi i operacije na skupovima“, koji se otvara u novom prozoru kada kliknete na link.

Karakteristična funkcija se označava kao v a njegova domena definicije sastoji se od mogućih podskupova skupa N. v(T) - vrijednost karakteristične funkcije za određeni podskup, na primjer, prihod koji prima koalicija, koja po mogućnosti uključuje onu koja se sastoji od jednog igrača. Ovo je važno jer teorija igara zahtijeva provjeru prisutnosti superaditivnosti za vrijednosti karakteristične funkcije svih disjunktnih koalicija.

Za dvije neprazne koalicije podskupa T1 I T2 Aditivnost karakteristične funkcije kooperativne (koalicijske) igre piše se na sljedeći način:

A superaditivnost je ovakva:

Primjer 2. Troje učenika glazbene škole honorarno rade u različitim klubovima, a prihode ostvaruju od posjetitelja kluba. Utvrditi je li im isplativo udružiti snage (ako da, pod kojim uvjetima), koristeći koncepte teorije igara za rješavanje kooperativnih igara n osobe, sa sljedećim početnim podacima.

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

• violinist ima 600 jedinica;
• gitarist ima 700 jedinica;
• pjevačica ima 900 jedinica.

Kako bi povećali prihode, studenti su tijekom nekoliko mjeseci stvarali različite grupe. Rezultati su pokazali da bi udruživanjem mogli povećati svoj večernji prihod za:

• violinist + gitarist zaradio 1500 jedinica;
• violinist + pjevač zaradio 1800 jedinica;
• gitarist + pjevač zaradio 1900 jedinica;
• violinist + gitarist + pjevač zaradio 3000 jedinica.

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

• koalicije jednog elementa od kojih se svaka sastoji od jednog svirača - glazbenika: T{1} , T{2} , T{3} ;
• koalicija dva elementa: T{1,2} , T{1,3} , T{2,3} ;
• koalicija tri elementa: T{1,2,3} .

Svakom igraču ćemo dodijeliti serijski broj:

• violinist - 1. svirač;
• gitarist - 2. svirač;
• pjevač – 3. svirač.

Na temelju podataka o problemu 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 temelju dobitaka prvog, drugog i trećeg igrača, kada se ne ujedine u koaliciju;

v(T(1,2)) = 1500; v(T(1,3)) = 1800; v(T(2,3)) = 1900; ove vrijednosti karakteristične funkcije određene su prihodom svakog para igrača ujedinjenih u koaliciju;

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

Dakle, popisali smo sve moguće koalicije igrača, a ima ih osam, kako i treba biti, budući da se domena definiranja karakteristične funkcije igre sastoji od točno osam mogućih podskupova skupa svih igrača. To zahtijeva teorija igara, budući da moramo provjeriti prisutnost superaditivnosti za vrijednosti karakteristične funkcije svih disjunktnih koalicija.

Kako su uvjeti superaditivnosti zadovoljeni u ovom primjeru? Odredimo kako igrači formiraju nepovezane koalicije T1 I T2 . Ako su neki igrači dio koalicije T1 , tada su svi ostali igrači dio koalicije T2 i po definiciji, ova koalicija se formira kao razlika cijelog skupa igrača i skupa T1 . Onda ako T1 - koalicija jednog igrača, pa u koaliciji T2 bit će drugi i treći igrač ako su u koaliciji T1 bit će prvi i treći igrač, pa koalicija T2 sastojat će se samo od drugog igrača, i tako dalje.

Sadržaj 1 Opće informacije 2 1.1 Igre. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Potezi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Strategije. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Matrix igra. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Točka staze. Č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ćenito iz teorije igara 1.1. Igre Teorija igara je matematička teorija konfliktnih situacija, tj. situacije u kojima se sukobljavaju interesi dviju ili više strana koje teže različitim ciljevima. Igra je konfliktna situacija regulirana određenim pravilima, koja moraju naznačiti: moguće mogućnosti postupanja sudionika; kvantitativni rezultat igre ili plaćanja (dobitak, gubitak) do kojeg dovodi zadani niz poteza; količinu informacija svake strane o ponašanju one druge. Igra parova je igra u kojoj sudjeluju samo dvije strane (dva igrača). Igra s parovima s nultim zbrojem je igra s parovima u kojoj je zbroj uplata nula, tj. Gubitak jednog igrača jednak je dobitku drugog. Ovisno o stavu svakog igrača prema vrijednosti funkcije isplate, igre u paru se dijele na: Igra u paru s nultom sumom (antagonistička) - igra u paru u kojoj je iznos isplata jednak nuli, tj. Gubitak jednog igrača jednak je dobitku drugog. Neantagonistička igra je igra u parovima u kojoj igrači slijede različite, ali ne izravno suprotne ciljeve. 2 1.2. Potezi Potez - izbor jedne od radnji predviđenih pravilima igre; provedba tog izbora. Potezi su dvije vrste: Osobni potez - + svjesni izbor jedne od radnji predviđenih pravilima igre + provedba ovog izbora Slučajni potez - Slučajni potez je izbor između niza mogućnosti, koji se ne provodi odlukom igrača, već nekim mehanizmom slučajnog odabira. U nastavku razmatramo uparene igre s nultim zbrojem koje sadrže samo osobne poteze. Obojoj strani nedostaju informacije o ponašanju one druge. 3 1.3. Strategije Igračeva strategija je skup pravila koja određuju izbor akcija za svaki osobni potez ovog igrača, ovisno o situaciji koja se pojavljuje tijekom igre. Ovisno o broju 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 kojeg igrača određuje podjelu igara na jednopotezne i višepotezne, odnosno pozicijske. + U igri s jednim potezom svaki igrač odabire samo jednu opciju od mogućih opcija i zatim određuje ishod igre. + Igra s više poteza ili položajna igra razvija se tijekom vremena, predstavljajući niz uzastopnih faza, od kojih se svaka događa nakon poteza jednog od igrača i odgovarajuće promjene situacije. U igri s jednim potezom svaki igrač odabire samo jednu opciju od mogućih opcija i zatim određuje ishod igre. Optimalna strategija igrača je strategija koja, kada se igra ponavlja više puta, ovom igraču osigurava maksimalnu moguću prosječnu pobjedu (ili, što je isto, minimalni mogući prosječni gubitak). U teoriji igara sve preporuke se temelje na pretpostavci razumnog ponašanja igrača. Pogrešne procjene i pogreške igrača, neizbježne u svakoj konfliktnoj situaciji, kao i elementi uzbuđenja i rizika ne uzimaju se u obzir u teoriji igre. 4 1.4. Matrična igra Matrična igra je igra jednog poteza konačnog zero-sum igre Matrična igra je teorijski model konfliktne situacije u kojoj protivnici, da bi postigli dijametralno suprotne ciljeve, čine jedan izbor (potez) od konačnog broj mogućih smjerova djelovanja.U skladu s odabranim načinima djelovanja (strategijama) utvrđuje se postignuti rezultat. Pogledajmo primjer. Neka postoje dva igrača A i B, od kojih jedan može izabrati i-tu strategiju od m svojih mogućih strategija A1, A2, ...Am, a drugi bira j-tu strategiju od svojih mogućih strategija B1, B2. , .. .Bm. Kao rezultat toga, prvi igrač dobiva vrijednost aij, a drugi igrač gubi tu vrijednost. Od brojeva aij kreiramo 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 nastoji maksimizirati svoje dobitke. Stupci su raspoređeni za strategije igrača gubitnika B, odnosno igrača koji nastoji minimizirati kriterij učinkovitosti. Normalizacija igre je proces svođenja pozicijske igre na matričnu igru. Igra u normalnom obliku pozicijska je igra reducirana na matričnu igru. Podsjetimo se da je pozicijska igra s više poteza teorijski model igre konfliktna situacija u kojoj protivnici uzastopno čine jedan izbor (potez) iz konačnog broja mogućih smjerova djelovanja u svakoj fazi razvoja ove situacije. Rješenje igre je pronalaženje optimalne strategije oba igrača i određivanje cijene igre.Cijena igre je očekivani dobitak (gubitak) igrača. Rješenje igre može se pronać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 s određenim vjerojatnostima. 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. Maximin ili niža cijena igre - broj α = max min aij i j Maximin strategija (linija) - strategija koju je igrač odabrao kako bi maksimizirao svoje minimalne dobitke. Očito, pri odabiru najopreznije maksimin strategije, igrač A osigurava sebi (bez obzira na ponašanje protivnika) zajamčenu isplatu od najmanje α. Maximin ili gornja cijena igre - broj β = min max aij j i Minimax strategija (stupac) - strategija koju je igrač odabrao kako bi smanjio svoj maksimalni gubitak. Očito, pri odabiru najopreznije minimax strategije, igrač B ni pod kojim okolnostima ne dopušta igraču A da osvoji više od β. Donja cijena igre uvijek ne premašuje 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, moguće u području mješovitih strategija. 6 2. Igre sa sedlom. Rješenje u čistim strategijama Igra sa sedlom točkom je igra za koju je α = max min aij = min max aij = β i j j i Za igre sa sedlom točkom pronalaženje rješenja sastoji se od odabira maximin i minimax strategija koje su optimalne. , Neto cijena igre - ukupna vrijednost donje i gornje cijene igre α=β=ν 2.1. Primjeri Primjer 1 Naći rješenje u čistim strategijama igre zadanim matricom   8 4 7 A= 6 5 9  7 7 8 Rješenje: odrediti gornju i donju cijenu igre. Da bismo to učinili, pronaći ćemo najmanji broj aij u i-tom redu αi = min aij j i maksimum brojeva aij u j-tom stupcu βj = max aij i Napisat ćemo brojeve αi (redak minimumi) pokraj matrice plaćanja s desne strane u obliku dodatnog stupca. Brojeve βi (maksimumi stupaca) upisujemo ispod matrice u obliku dodatnog retka: α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 minimalni broj βj β = min βj = 7 j α = β - igra ima sjedište. Optimalna strategija za igrača je strategija A3, a za igrača B je strategija B2, neto cijena igre ν = 7. Primjer 2 Data je matrica plaćanja:   2 2 1 1 2  0 1 1 1 1  A=  1 1 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 sedlišnih točaka. Optimalne strategije bit će: A1 i B3 ili B4 A3 i B3 ili B4 A4 i B3 ili B4 8 3. Rješenje igre u mješovitim strategijama Kada je α = β. U slučaju kada pri odabiru svojih strategija oba igrača nemaju informaciju o izboru onog drugog, igra ima rješenje u mješovitim strategijama. SA = (p1, p2, ..., pm) - mješovita strategija igrača A, u kojoj se primjenjuju strategije A1, A2, ..., Am s vjerojatnostima ∑ m p1, p2, ..., pm, pi = 1, pi > 0, i = 1, m i=1 SB = (q1, q2, ..., qn) - mješovita strategija igrača B, u kojoj se strategije B1, B2, ..., Bm primjenjuju s vjerojatnostima ∑ n q1, q2 , ..., qm , qi = 1, qi > 0, i = 1, n i=1 Ako je: SA∗ optimalna strategija igrača A, SB∗ optimalna strategija igrača B, tada je trošak igre je ∑ n ∑ m ν = aij · p∗i · qi∗ j=1 i=1 Sljedeći teorem odgovara na pitanje kako pronaći rješenje za igre 2 × 2, 2 × n, m × 2 Teorem 2 (kako pronaći rješenje za igre 2 × 2, 2 × n, m × 2). Ako jedan od igrača koristi optimalnu mješovitu strategiju, tada je njegov dobitak jednak cijeni igre ν, bez obzira na vjerojatnosti s kojima će drugi igrač koristiti strategije uključene u optimalnu (uključujući i čiste strategije). 9 3.1. Igra 2 × 2 Razmotrimo igru ​​2 × 2 s matricom: () a11 a21 a21 a22 Neka igra nema rješenja u čistim strategijama. Nađimo optimalne strategije SA∗ i SB∗. Prvo, definiramo strategiju SA∗ = (p∗1 , p∗2). Prema teoremu, ako se stranka A pridržava strategije ν, tada će bez obzira na smjer akcije stranke B, dobitak ostati jednak cijeni igranja ν. Posljedično, ako se strana A pridržava optimalne strategije SA∗ = (p∗1, p∗2), tada strana B može primijeniti bilo koju od svojih strategija bez promjene svoje dobiti. Zatim, kada igrač B koristi čistu strategiju B1 ili B2, igrač će dobiti prosječnu isplatu jednaku cijeni igre: a11 p∗1 + a21 p∗2 = ν ← za strategiju B1 a12 p∗1 + a22 p∗ 2 = ν ← za strategiju B2 Uzimajući u obzir 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 Cijena igre: a22 a11 − a12 a21 ν= a11 + a22 − a12 − a21 Optimalna strategija igrača B nalazi se na sličan način: 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 Pronađite rješenje igre s matricom () −1 1 A= 1 −1 10 Rješenje: igra nema sedlišnu točku jer je α= -1, β = 1, α ̸= β. Rješenje tražimo u mješovitim strategijama. Koristeći formule za p∗ i q∗, dobivamo 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 Pronađite rješenje igre s matricom () 2 5 A= 6 4 Rješenje: igra nema sedlišnu točku jer je α= 4, β = 5, α ̸= β. Rješenje tražimo u mješovitim strategijama. Koristeći formule za p∗ i q∗, dobivamo p∗1 = 0,4, p∗2 = 0,6 i q1∗ = 0,2 q2∗ = 0,8, ν = 4,4 Dakle, SA∗ = (0,4, 0,6) SB∗ = ( 0,2, 0,8) 11 3.1.2. Geometrijska interpretacija Igri 2 × 2 može se dati jednostavna geometrijska interpretacija. Uzmimo jedan presjek osi apscisa, čiju svaku točku pridružujemo nekoj mješovitoj strategiji S = (p1, p2) = (p1, 1 − p1) i vjerojatnost p1 strategije A1 bit će jednaka udaljenosti od točka SA do desnog kraja presjeka, a vjerojatnost p2 , strategija A2 - udaljenost do lijevog kraja. .y .I .I I .B1′ .N .B1 .a21 .a11 .I I .I .∗ .x .P2 .SA∗ .P1∗ Konkretno, lijevi kraj presjeka (točka s apscisom = 0) odgovara na strategiju A1, desni kraj segmenta (x = 1) - strategija A2 Na krajevima segmenta vraćaju se dvije okomice na x-os: os I − I - isplata za strategiju A1 je odgođena; os II − II - isplata za strategiju A2 je odgođena Neka igrač B primijeni strategiju B1; daje na osi I − I odnosno II − II točke s ordinatama a11 i a21. Kroz te točke povučemo ravnu liniju B1 − B1′. Za bilo koju mješovitu strategiju SA = (p1, p2), isplata igrača određena je točkom N na ravnoj liniji B1 − B1′, koja odgovara točki SA na x-osi koja dijeli segment u omjeru p2: p1. Očito, pravac B2 − B2′, koji određuje dobit za strategiju B2, može se konstruirati na potpuno isti način. 12 .y .I .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 minimalni dobitak igrača A (s obzirom na najlošije ponašanje igrača B) pretvorio u maksimum. Da biste to učinili, konstruirajte donju granicu za isplatu igrača A za strategije B1, B2, tj. izlomljena linija B1 N B2′ ;. Na ovoj će granici ležati minimalni dobitak igrača A za bilo koju njegovu mješovitu strategiju, točka N, u kojoj ovaj dobitak doseže maksimum i određuje odluku i cijenu igre. .y .I .I I .B2 .B1′ .N .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S . 1∗ P Ordinata točke N nije ništa drugo nego trošak igre ν, njezina apscisa je jednaka ∗2, a udaljenost do desnog kraja segmenta jednaka je ∗1, tj. udaljenost od točke SA∗ do krajeva segmenta jednaka je vjerojatnostima ∗2 i ∗1 strategija A2 i A1 optimalne mješovite strategije igrača A. u ovom slučaju rješenje igre određeno je sjecište strategija B1 i B2. Ispod je slučaj u kojem je igračeva optimalna strategija čista strategija A2. Ovdje je strategija A2 (za bilo koju strategiju neprijatelja) isplativija od strategije A1, 13 .y .y .I .I I .I I. I .B2′ . 1′ B .B1′ B . 2 .B2′ B . 2 .B1 .ν = a21 .B1 .ν = a21 I. I I. I .I . .x .ja . .x. 2∗ P . A∗S = A2. 2∗ P . A∗ S = A2 Desno je prikazan slučaj kada igrač B ima očito neprofitabilnu strategiju.Geometrijska interpretacija također omogućuje vizualizaciju donje cijene igre α i gornje cijene β .y .I .I I .B2 .B1′ .N .B1 .B2′ .β = a21 .α = a22 .I I .I .∗ .x .P2 . A∗ S . 1∗ P Na istom grafu možemo dati i geometrijsku interpretaciju optimalnih strategija igrača B. Lako je provjeriti da je udio q1∗ strategije B1 optimalne mješovite strategije SB∗ = (q1∗ , q2∗) jednak omjeru duljine segmenta KB2 i zbroja duljina segmenta 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′ Optimalna strategija SB∗ = (q1∗ , q2∗) može se pronaći na drugi način, ako zamijenimo igrače B i B, i umjesto maksimuma donje granice dobitaka, uzmite u obzir minimum 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 temelji 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 brojeva m i n. Prema ovom teoremu, igra 2 × n uvijek ima rješenje u kojem svaki igrač ima najviše dvije aktivne strategije. Jednom kada pronađete te strategije, igra 2 × n pretvara se u igru ​​2 × 2, koja se može riješiti na elementaran način. Pronalaženje aktivnih strategija može se izvršiti grafički: 1) konstruira se grafička interpretacija; 2) utvrđuje se donja granica dobitaka; 3) identificirane su dvije strategije drugog igrača na donjoj granici isplate, koje odgovaraju dvjema linijama koje se sijeku u točki s najvećom ordinatom (ako se više od dvije linije sijeku u ovoj točki, uzima se bilo koji par) - ove strategije predstavljaju aktivne strategije igrača B. Time se igra 2 × n svodi na igru ​​2 × 2. Igra m × 2 također se može riješiti, s tom razlikom što nije donja, već gornja granica isplate izgrađena, a na njoj se ne traži maksimum, nego minimum. Primjer 5 Pronađite rješenje igre () 7 9 8 A= 10 6 9 Rješenje: geometrijskom metodom biramo aktivne strategije. Direktne linije B1 − B1′, B2 − B2′ i B3 − B3′ odgovaraju strategijama B1, B2, B3. Isprekidana linija B1 N B2 donja je granica dobitka igrača. 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 osobnih, 3 2 × 2, 9 nasumičnih, 3 geometrija, 12 neto cijena igre, 7 primjera, 10 2 × n, 9, 16 m × 2, 9 , 16 beskonačnih, 4 u normalnom obliku, 5 konačnih, 4 s više poteza, 4 s jednim potezom, 4 matričnih, 5 uparenih, 2 s nultim zbrojem, 2 antagonističkih, 2 neantagonističkih, 2 rješenja, 5 u mješovitim strategijama, 5 , 9 u čistim strategijama , 5 sa sjedištem, 7 cijena, 5 gornja, 6 donja, 6 čista, 7 maksimin, 6 matrica igre, 5 isplata, 5 minimaks, 6 normalizacija igre, 5 strategija, 4 maksimin, 6 minimaks, 6 optimalno, 4 mješovito, 5 teorija igara, 2 18