Matematičke metode i modeli u ekonomiji

Matrične igre

Uvod

U ekonomskoj praksi često se javljaju situacije u kojima različite strane težiti različitim ciljevima. Na primjer, odnos između prodavca i kupca, dobavljača i potrošača, banke i deponenta, itd. Takve konfliktne situacije nastaju ne samo u privredi, već iu drugim vrstama djelatnosti. Na primjer, kada igrate šah, dame, domine, loto itd.

Igra je matematički model konfliktne situacije koji uključuje najmanje dvije osobe koje koriste nekoliko različitih metoda za postizanje svojih ciljeva. Igra se zove parna soba, ako uključuje dva igrača. Igra se zove antagonistički, ako je dobitak jednog igrača jednak gubitku drugog. Stoga je za postavljanje igre dovoljno postaviti dobitne vrijednosti jednog igrača u različitim situacijama.

Poziva se bilo koja metoda djelovanja igrača ovisno o trenutnoj situaciji strategija. Svaki igrač ima specifičan skup strategija. Ako je broj strategija konačan, onda se igra zove krajnji, inače - beskrajno . Strategije se zovu čisto, ako svaki igrač odabere samo jednu strategiju na specifičan, a ne nasumičan način.

Rešenje za igru je odabrati strategiju koja zadovoljava stanje optimalnosti. Ovaj uslov je da jedan igrač dobije maksimalna pobeda, ako se drugi drži svoje strategije. Suprotno tome, drugi igrač prima minimalni gubitak, ako se prvi igrač drži svoje strategije. Takve strategije se nazivaju optimalno . dakle, Cilj igre je odrediti optimalnu strategiju za svakog igrača.

Čista strateška igra

Zamislite igru ​​sa dva igrača A I IN. Pretpostavimo da je igrač A Ima m strategije A 1, A 2, …, A m, i plejer IN Ima n strategije B 1, B 2, …, B n. Pretpostavićemo da je izbor igrača A strategije A i, i plejer IN strategije Bj jednoznačno određuje ishod utakmice, tj. dobitke a ij igrač A i dobitke b ij igrač IN. Evo i=1,2,…,m, j=1,2,…,n.

Najjednostavnija igra sa dva igrača je igra sa nultom sumom , one. igra u kojoj su interesi igrača direktno suprotstavljeni. U ovom slučaju, isplate igrača su povezane jednakošću

b ij =-a ij

Ova jednakost znači da je dobitak jednog igrača jednak gubitku drugog. U ovom slučaju, dovoljno je uzeti u obzir samo dobitke jednog od igrača, na primjer, igrača A.

Svaki par strategija A i I Bj odgovara dobitku a ij igrač A. Zgodno je sve ove dobitke zapisati u obliku tzv matrica plaćanja

Redovi ove matrice odgovaraju strategijama igrača A, a kolone – strategije igrača IN. Općenito, takva igra se zove (m×n)-igra.

Primjer 1. Dva igraca A I IN baci novčić. Ako se strane novčića poklapaju, onda on pobjeđuje A, tj. igrač IN plaća igraču A određeni iznos jednak 1, a ako se ne poklapaju, onda igrač B pobjeđuje, tj. naprotiv, igrač A plaća igraču IN isti iznos , jednak 1. Kreirajte matricu plaćanja.

Rješenje. Prema uslovima problema

Iako sam završio Fizičko-tehnološki fakultet, na fakultetu me nisu predavali teoriju igara. Ali, pošto sam u studentskim godinama mnogo igrao prvo preferans, a zatim bridž, teorija igara me je zainteresovala i savladao sam mali udžbenik. A nedavno je čitač sajta Mikhail rešio problem teorije igara. Shvativši da mi zadatak nije lak, odlučio sam da dopunim svoje znanje o teoriji igara. Nudim vam malu knjigu - popularan prikaz elemenata teorije igara i nekih metoda za rješavanje matričnih igara. Ne sadrži gotovo nikakve dokaze i ilustruje glavne odredbe teorije primjerima. Knjigu je napisala matematičarka i popularizatorka nauke Elena Sergeevna Ventzel. Nekoliko generacija sovjetskih inženjera učilo je iz njenog udžbenika “Teorija vjerovatnoće”. Elena Sergejevna je takođe napisala nekoliko književna djela pod pseudonimom I. Grekova.

Elena Ventzel. Elementi teorije igara. – M.: Fizmatgiz, 1961. – 68 str.

Skinuti kratak sažetak u formatu ili

§ 1. Predmet teorije igara. Osnovni koncepti

Prilikom rješavanja niza praktičnih problema (iz oblasti ekonomije, vojnih poslova itd.) potrebno je analizirati situacije u kojima postoje dvije (ili više) zaraćene strane koje teže suprotstavljenim ciljevima, a rezultat svake akcije jedne od strana zavisi od toga kakav će pravac akcije izabrati neprijatelj. Takve ćemo situacije nazvati „konfliktnim situacijama“.

Mogu se navesti brojni primjeri konfliktnih situacija raznim oblastima prakse. Svaka situacija koja nastane tokom vojnih operacija spada u konfliktne situacije: svaka od zaraćenih strana preduzima sve mere koje joj stoje na raspolaganju kako bi sprečila neprijatelja da postigne uspeh. U konfliktne situacije spadaju i situacije koje nastaju prilikom izbora sistema naoružanja, načina njegove borbene upotrebe i općenito pri planiranju vojnih operacija: svaka od odluka u ovoj oblasti mora se donijeti uzimajući u obzir akcije neprijatelja koje su najmanje korisne za nas. Brojne situacije u oblasti ekonomije (posebno u prisustvu slobodne konkurencije) spadaju u konfliktne situacije; trgovačke firme, industrijska preduzeća, itd. djeluju kao sukobljene strane.

Potreba za analizom ovakvih situacija izazvala je poseban matematički aparat. Teorija igara u suštini nije ništa drugo do matematička teorija konfliktnih situacija. Svrha teorije je da razvije preporuke o racionalnom toku akcije za svakog od protivnika tokom konfliktne situacije. Svaka konfliktna situacija direktno preuzeta iz prakse je veoma složena, a njena analiza je komplikovana prisustvom brojnih faktora koji doprinose tome. Da bi se omogućila matematička analiza situacije, potrebno je apstrahovati od sekundarnih, usputnih faktora i izgraditi pojednostavljeni, formalizovani model situacije. Ovaj model ćemo nazvati "igra".

Igra se razlikuje od stvarne konfliktne situacije po tome što se igra u potpunosti određena pravila. Čovječanstvo već dugo koristi takve formalizirane modele konfliktnih situacija koje su igre u doslovnom smislu riječi. Primjeri uključuju šah, dame, kartaške igre itd. Sve ove igre su po prirodi takmičenja, koje se odvijaju po poznatim pravilima i završavaju „pobjedom“ (pobjedom) jednog ili drugog igrača.

Takve formalno uređene, umjetno organizirane igre predstavljaju najpogodniji materijal za ilustraciju i savladavanje osnovnih pojmova teorije igara. Terminologija posuđena iz prakse ovakvih igara koristi se i u analizi drugih konfliktnih situacija: strane koje su uključene u njih se konvencionalno nazivaju "igrači", a rezultat kolizije je "pobjeda" jedne od strana.

Interesi dva ili više protivnika se mogu sukobiti u igri; u prvom slučaju igra se zove "uparena", u drugom - "višestruka". Učesnici višestruke igre mogu formirati koalicije tokom igre - stalne ili privremene. U prisustvu dvije stalne koalicije, višestruka igra se pretvara u igru ​​u paru. Igre u parovima su od najveće praktične važnosti; Ovdje ćemo se ograničiti na razmatranje samo takvih igara.

Započnimo prezentaciju elementarna teorija igre sa formulisanjem nekih osnovnih pojmova. Razmotrićemo igru ​​u parovima u kojoj učestvuju dva igrača A i B sa suprotnim interesima. Pod „igrom“ podrazumevamo događaj koji se sastoji od niza akcija strana A i B. Da bi igra bila podvrgnuta matematičkoj analizi, pravila igre moraju biti precizno formulisana. „Pravila igre” znače sistem uslova koji reguliše moguće opcije za akcije obe strane, količinu informacija koje svaka strana ima o ponašanju druge, redosled naizmeničnih „poteza” (pojedinačne odluke donete tokom igra), kao i rezultat ili ishod igre do koje to vodi.set poteza. Ovaj rezultat (pobjeda ili poraz) nema uvijek kvantitativni izraz, ali ga je obično moguće, uspostavljanjem neke skale mjerenja, izraziti određenim brojem. Na primjer, u partiji šaha, pobjedi se može uvjetno dodijeliti vrijednost od +1, gubitku –1, remiju 0.

Igra se naziva igrom sa nultom sumom ako jedan igrač dobije ono što drugi izgubi, tj. zbir dobitaka obe strane je nula. U igri sa nultom sumom, interesi igrača su direktno suprotstavljeni. Ovdje ćemo razmotriti samo takve igre.

Pošto je u igri sa nultom sumom isplata jednog od igrača jednaka isplati drugog sa suprotnim predznakom, onda, očigledno, kada analiziramo takvu igru, možemo uzeti u obzir isplatu samo jednog od igrača. Neka to bude, na primjer, igrač A. U budućnosti, radi praktičnosti, stranu A ćemo konvencionalno zvati "mi", a stranu B - "neprijatelj".

U ovom slučaju, strana A (“mi”) će se uvijek smatrati “pobjednikom”, a strana B (”neprijatelj”) kao “gubitnikom”. Ovaj formalni uslov očigledno ne znači nikakvu stvarnu prednost za prvog igrača; lako je vidjeti da je zamijenjen svojom suprotnošću ako je predznak dobitka obrnut.

Zamišljaćemo razvoj igre tokom vremena kao da se sastoji od niza uzastopnih faza ili „poteza“. U teoriji igara, potez je izbor jedne od opcija predviđenih pravilima igre. Potezi se dijele na lične i nasumične. Lični potez je svjestan izbor jednog od igrača jednog od mogućih poteza u datoj situaciji i njegova implementacija. Primjer ličnog poteza je bilo koji od poteza u partiji šaha. Prilikom izvođenja sljedećeg poteza, igrač svjesno bira jednu od mogućih opcija sa datim rasporedom figura na tabli. Skup mogućih opcija za svaki lični potez regulisan je pravilima igre i zavisi od ukupnosti prethodnih poteza obe strane.

Nasumični potez je izbor između brojnih mogućnosti, koji se ne provodi odlukom igrača, već nekim mehanizmom slučajni odabir(bacanje novčića, kockice, miješanje i dijeljenje karata, itd.). Na primjer, dijeljenje prve karte jednom od preferiranih igrača je nasumičan potez sa 32 jednako moguće opcije. Da bi igra bila matematički definisana, pravila igre moraju specificirati distribuciju vjerovatnoće mogućih ishoda za svaki slučajni potez.

Neke igre se mogu sastojati samo od nasumičnih poteza (tzv. pure kockanje) ili samo iz ličnih poteza (šah, dame). Većina kartaške igre pripada igricama mješoviti tip, tj. sadrži i nasumične i lične poteze.

Igre se klasifikuju ne samo po prirodi poteza (lični, slučajni), već i po prirodi i količini informacija dostupnih svakom igraču u vezi sa akcijama drugog. Posebnu klasu igara čine takozvane „igre sa potpune informacije" Igra sa potpunim informacijama je igra u kojoj svaki igrač, svakim ličnim potezom, zna rezultate svih prethodnih poteza, ličnih i slučajnih. Primjeri igara s potpunim informacijama uključuju šah, dame i dobro poznatu igru ​​"tik-tak-toe".

Većina igara od praktične važnosti ne spada u klasu igara sa potpunim informacijama, jer je neizvjesnost o neprijateljskim akcijama obično bitan element konfliktnih situacija.

Jedan od osnovnih koncepata teorije igara je koncept „strategije“. Igračeva strategija je skup pravila koja na jedinstven način određuju izbor za svaki lični potez datog igrača, u zavisnosti od situacije koja se pojavi tokom igre. Obično odluku (izbor) za svaki lični potez donosi igrač tokom same igre, u zavisnosti od konkretne situacije. Međutim, teoretski, stvar se neće promijeniti ako zamislimo da sve ove odluke igrač donosi unaprijed. Da bi to učinio, igrač bi morao unaprijed sastaviti listu svih mogućih situacija tokom igre i dati svoje rješenje za svaku od njih. U principu (ako ne i praktično) to je moguće za svaku igru. Ako se takav sistem odlučivanja prihvati, to će značiti da je igrač izabrao određenu strategiju.

Igrač koji je odabrao strategiju sada ne može lično učestvovati u igri, već svoje učešće zamijeni listom pravila koja će neka nezainteresovana osoba (sudija) primijeniti za njega. Strategija se takođe može specificirati automatskoj mašini u obliku specifičnog programa. Ovako se trenutno igra kompjuterski šah. Da bi koncept „strategije“ imao smisla, moraju postojati lični potezi u igri; U igrama koje se sastoje samo od nasumičnih poteza, ne postoje strategije.

U zavisnosti od broja mogućih strategija, igre se dijele na "konačne" i "beskonačne". Igra u kojoj svaki igrač ima samo konačan broj strategija naziva se konačna igra. Konačna igra u kojoj igrač A ima m strategije, a igrač B - n strategije se naziva mxn igra.

Razmotrimo igru ​​mxn dva igrača A i B („nas“ i „protivnik“). Označićemo naše strategije A 1 , A 2 , …, A m i strategije protivnika B 1 , B 2 , …, B n . Neka svaka strana izabere specifičnu strategiju; za nas će to biti A i, za neprijatelja B j. Ako se igra sastoji samo od ličnih poteza, tada izbor strategija A i, B j na jedinstven način određuje ishod igre – naš dobitak. Označimo ga sa ij. Ako igra sadrži, pored ličnih, i nasumične poteze, tada je isplata za par strategija A i, B j slučajna vrijednost, ovisno o ishodu svih slučajnih poteza. U ovom slučaju, prirodna procjena očekivanog dobitka je njegova prosječna vrijednost (matematičko očekivanje). Istim znakom ćemo označiti i samu pobjedu (u igri bez nasumičnih poteza) i njenu prosječnu vrijednost (u igri sa slučajnim potezima).

Javite nam vrijednosti a ij isplate (ili prosječne isplate) za svaki par strategija. Vrijednosti se mogu zapisati u obliku pravokutne tablice (matrice), čiji redovi odgovaraju našim strategijama (A i), a stupci odgovaraju strategijama protivnika (B j). Ova tabela se zove matrica isplate ili jednostavno matrica igre. Matrica igre mxn prikazana je na Sl. 1.

Rice. 1. Matrica mxn

Ukratko, matricu igre ćemo označiti ‖a ij‖. Pogledajmo nekoliko osnovnih primjera igara.

Primjer 1. Dva igrača A i B, ne gledajući jedan drugog, stavljaju novčić na sto, glavom ili repom, prema vlastitom nahođenju. Ako su igrači izabrali iste strane (obojica imaju grb ili oba imaju glave), tada igrač A uzima oba novčića; inače ih preuzima igrač B. Potrebno je analizirati igru ​​i kreirati njenu matricu. Rješenje. Igra se sastoji od samo dva poteza: našeg poteza i poteza protivnika, oba lična. Igra ne spada u igre sa potpunim informacijama, jer u trenutku poteza igrač koji je pravi ne zna šta je drugi uradio. Pošto svaki igrač ima samo jedan lični potez, igračeva strategija je izbor sa ovim pojedinačnim ličnim potezom.

Imamo dvije strategije: A 1 - izaberite grb i A 2 - izaberite repove; Neprijatelj ima iste dvije strategije: B 1 - grb i B 2 - rep. Dakle, ova igra je igra 2x2. Dobit ćemo novčić kao +1. Matrica igre:

Na primjeru ove igre, ma koliko ona bila elementarna, mogu se razumjeti neke bitne ideje teorije igara. Pretpostavimo prvo da se ova igra igra samo jednom. Onda, očigledno, nema smisla govoriti o bilo kakvim “strategijama” igrača koji su inteligentniji od drugih. Svaki od igrača sa istim razlogom može donijeti bilo koju odluku. Međutim, kada se igra ponovi, situacija se mijenja.

Zaista, pretpostavimo da smo mi (igrač A) odabrali neku strategiju za sebe (recimo, A 1) i da je se držimo. Tada će, na osnovu rezultata prvih nekoliko poteza, neprijatelj pogoditi našu strategiju i na nju će odgovoriti na najnepovoljniji način za nas, tj. izaberite repove. Jasno je da nam nije u korist da uvijek usvajamo jednu strategiju; Da ne bismo bili gubitnik, nekad moramo izabrati grb, nekad rep. Međutim, ako izmjenjujemo grb i rep u određenom nizu (npr. kroz jedan), i neprijatelj to može pogoditi i na tu strategiju odgovoriti na najgori način za nas. Očigledno, pouzdan način da se jamči da neprijatelj neće znati našu strategiju je organiziranje izbora pri svakom potezu kada ga sami ne znamo unaprijed (to se može osigurati, na primjer, bacanjem novčića). Tako se kroz intuitivno rasuđivanje približavamo jednom od bitnih koncepata teorije igara – konceptu „mješovite strategije“, tj. kao kada su “čiste” strategije - u u ovom slučaju A 1 i A 2 – nasumično se izmjenjuju sa određenim frekvencijama. U ovom primeru, iz razloga simetrije, unapred je jasno da strategije A 1 i A 2 treba da se smenjuju sa istom frekvencijom; u složenijim igrama rješenje može biti daleko od trivijalnog.

Primjer 2. Igrači A i B istovremeno i nezavisno jedan od drugog zapisuju jedan od tri broja: 1, 2 ili 3. Ako je zbir zapisanih brojeva paran, onda B plaća A ovaj iznos u rubljama; ako je neparan, onda, naprotiv, A plaća B-u ovaj iznos. Potrebno je analizirati igru ​​i kreirati njenu matricu.

Rješenje. Igra se sastoji od dva okreta; oba su lična. Mi (A) imamo tri strategije: A 1 - upiši 1; A 2 - upiši 2; A 3 - upiši 3. Neprijatelj (B) ima iste tri strategije. Igra je 3x3 igra:

Očigledno, kao iu prethodnom slučaju, neprijatelj može odgovoriti na bilo koju strategiju koju odaberemo na način koji je najgori za nas. Zaista, ako odaberemo, na primjer, strategiju A 1, neprijatelj će na nju uvijek odgovoriti strategijom B 2; strategiji A 2 - strategiji B 3; strategiji A 3 - strategiji B 2; pa će nas svaki izbor određene strategije neminovno dovesti do gubitka (međutim, ne smijemo zaboraviti da na isti način nevolja postoji i neprijatelj). Rješenje ove igre (tj. skup najprofitabilnijih strategija oba igrača) će biti dato u § 5.

Primjer 3. Na raspolaganju imamo tri vrste oružja: A 1, A 2, A 3; Neprijatelj ima tri tipa aviona: B 1, B 2, B 3. Naš zadatak je da udarimo u avion; Zadatak neprijatelja je da ga zadrži neporaženim. Prilikom upotrebe oružja A 1, avioni B 1, B 2, B 3 su pogođeni respektivno sa vjerovatnoćom od 0,9, 0,4 i 0,2; sa naoružanjem A 2 - sa verovatnoćama 0,3, 0,6 i 0,8; sa naoružanjem A 3 - sa vjerovatnoćama 0,5, 0,7 i 0,2. Potrebno je formulisati situaciju u terminima teorije igara.

Rješenje. Situacija se može posmatrati kao igra 3x3 sa dva lična poteza i jednim slučajnim. Naš lični potez je izbor vrste oružja; Lični potez neprijatelja je izbor aviona za učešće u bitci. Slučajni potez - upotreba oružja; ovaj potez može ili ne mora rezultirati porazom aviona. Naši dobici jednako jedan, ako je avion pogođen, a u suprotnom je nula. Naše strategije su tri opcije oružja; neprijateljske strategije - tri opcije aviona. Prosječna isplata za bilo koji par strategija nije ništa drugo do vjerovatnoća gubitka ovog aviona sa ovim oružjem. Matrica igre:

Svrha teorije igara je da razvije preporuke za razumno ponašanje igrača u konfliktnim situacijama, tj. određivanje “optimalne strategije” za svaku od njih. Optimalna strategija igrača u teoriji igara je strategija koja, kada se igra mnogo puta ponovi, daje datom igraču maksimalnu moguću prosječnu pobjedu (ili minimalni mogući prosječni gubitak). Prilikom odabira ove strategije, osnova rasuđivanja je pretpostavka da je neprijatelj barem toliko inteligentan kao mi sami i da čini sve da nas spriječi u ostvarenju cilja.

U teoriji igara, sve preporuke su razvijene na osnovu ovih principa; dakle, ne uzima u obzir elemente rizika koji su neizbežno prisutni u svakoj realnoj strategiji, kao ni moguće pogrešne procene i greške svakog igrača. Teorija igara, kao i svaki matematički model složenog fenomena, ima svoja ograničenja. Najvažniji od njih je da se dobici umjetno svode na jedan jedini broj. U većini praktičnih konfliktnih situacija, prilikom izrade razumne strategije, potrebno je uzeti u obzir ne jedan, već nekoliko brojčanih parametara - kriterija za uspjeh događaja. Strategija koja je optimalna prema jednom kriteriju neće nužno biti optimalna prema drugim kriterijima. Međutim, biti svjestan ovih ograničenja i stoga se ne pridržavati slijepo primljenih preporuka metode igre, još uvijek možete inteligentno koristiti matematički aparat teorije igara za razvoj, ako ne baš „optimalne“, onda barem „prihvatljive“ strategije.

§ 2. Donja i gornja cijena igre. Minimaks princip

Razmotrimo igru ​​mxn sa matricom kao na sl. 1. Broj naše strategije ćemo označiti slovom i; slovo j je broj neprijateljske strategije. Postavimo sebi zadatak: odrediti našu optimalnu strategiju. Analizirajmo svaku od naših strategija uzastopno, počevši od A 1 .

Prilikom odabira strategije A i, uvijek moramo računati na činjenicu da će neprijatelj na nju odgovoriti jednom od strategija B j za koju je naša isplata a ij minimalna. Odredimo ovu dobitnu vrijednost, tj. minimum brojeva a ij in i th line. Označimo ga α i:

Ovdje znak min (minimum u j) označava minimum vrijednosti ovog parametra za sve moguće j. Zapišimo brojeve α i ; pored matrice na desnoj strani kao dodatna kolona:

Prilikom odabira bilo koje strategije A i , moramo računati na činjenicu da kao rezultat razumnih akcija neprijatelja nećemo dobiti više od α i . Naravno, djelujući najopreznije i računajući na najrazumnijeg protivnika (tj. izbjegavajući svaki rizik), moramo izabrati strategiju za koju je broj α i maksimalan. Označimo ovu maksimalnu vrijednost α:

ili, uzimajući u obzir formulu (2.1),

Vrijednost α se naziva niža cijena igre, inače maksiminska isplata ili jednostavno maksimin. Broj α leži u određenom redu matrice; strategija igrača A koja odgovara ovoj liniji naziva se maksiminska strategija. Očigledno, ako se pridržavamo maksiminske strategije, tada nam je zagarantovana pobjeda, barem ne manja od α, bez obzira na ponašanje neprijatelja. Stoga se vrijednost α naziva „niža cijena igre“. Ovo je zagarantovani minimum koji možemo sebi obezbediti pridržavajući se najopreznije („reosiguranja“) strategije.

Očigledno, slično razmišljanje se može izvesti i za protivnika B. Pošto je protivnik zainteresovan da minimizira naš dobitak, on mora razmotriti svaku svoju strategiju sa stanovišta maksimalnog dobitka za ovu strategiju. Stoga ćemo na dnu matrice zapisati maksimalne vrijednosti za svaku kolonu:

i pronađite minimum β j:

Vrijednost β se naziva gornja cijena igre, inače poznata kao “minimax”. Protivnikova strategija koja odgovara minimalnoj isplati naziva se njegova „minimaks strategija“. Pridržavajući se svoje najopreznije minimaks strategije, neprijatelj sebi garantuje sledeće: šta god da uradimo protiv njega, on će u svakom slučaju izgubiti iznos ne veći od β. Načelo opreza, koje nalaže da igrači odaberu odgovarajuće strategije (maksimin i minimaks), često se u teoriji igara i njenim primjenama naziva „principom minimaksa“. Najopreznije maksiminske i minimaks strategije igrača ponekad se nazivaju općim terminom "minimaks strategije".

Kao primjere definiramo donje i top cijena igre i minimaks strategije za primjere 1, 2 i 3 § 1.

Primjer 1. U primjeru 1 § 1, data je igra sa sljedećom matricom:

Budući da su vrijednosti α i i β j konstantne i jednake –1 i +1, respektivno, donja i gornja cijena igre su također jednake –1 i +1: α = –1, β = +1 . Bilo koja strategija igrača A je njegova maksimalna strategija, a svaka strategija igrača B je njegova minimaks strategija. Zaključak je trivijalan: pridržavajući se bilo koje svoje strategije, igrač A može garantovati da neće izgubiti više od 1; Igrač B može garantovati isto.

Primjer 2. U primjeru 2 § 1 data je igra s matricom:

Niska cijena igre α = –3; gornja cijena igre je β = 4. Naša maksimalna strategija je A 1 ; Sistematskom primjenom možemo čvrsto očekivati ​​da ćemo pobijediti najmanje -3 (izgubiti ne više od 3). Neprijateljeva minimaks strategija je bilo koja od strategija B 1 i B 2; ako ih sistematično primjenjuje, on, u svakom slučaju, može garantirati da neće izgubiti više od 4. Ako odstupimo od naše maksimalne strategije (na primjer, izaberemo strategiju A 2), neprijatelj nas za to može “kazniti” primjenom strategija B 3 i smanjenje našeg dobitka su -5; Isto tako, protivnikovo povlačenje od njegove minimaks strategije može povećati njegov gubitak na 6.

Primjer 3. U primjeru 3 § 1 data je igra s matricom:

Niska cijena igre α = 0,3; gornja cijena igre je β = 0,7. Naša najopreznija (maksiminalna) strategija je A 2 ; Korišćenjem oružja A2 garantujemo da ćemo u prosjeku pogoditi avion u najmanje 0,3 svih slučajeva. Najopreznija (minimaks) strategija neprijatelja je B 2 ; Korišćenjem ovog aviona, neprijatelj može biti siguran da će biti pogođen u najviše 0,7 slučajeva.

Koristeći posljednji primjer, zgodno je pokazati jedno važno svojstvo minimaks strategija – njihovu nestabilnost. Koristimo našu najoprezniju (maksiminsku) strategiju A 2 , a neprijatelj svoju najoprezniju (minimaks) strategiju B 2 . Sve dok se oba protivnika pridržavaju ovih strategija, prosječna isplata je 0,6; to je više od donje cijene, ali manje od gornje cijene igre. Sada pretpostavimo da neprijatelj zna da koristimo strategiju A 2 ; on će odmah odgovoriti strategijom B 1 i smanjiti dobitak na 0,3. Zauzvrat, imamo dobar odgovor na strategiju B 1: strategija A 1, koja nam daje isplatu od 0,9, itd.

Dakle, situacija u kojoj oba igrača koriste svoje minimaks strategije je nestabilna i može biti narušena primljenim informacijama o strategiji druge strane. Međutim, postoje neke igre za koje su minimaks strategije stabilne. To su igre za koje je donja cijena jednaka gornjoj: α = β. Ako je donja cijena igre jednaka gornjoj cijeni, onda je njihova opšte značenje se naziva neto cijena igre (ponekad jednostavno cijena igre), označit ćemo je slovom ν.

Pogledajmo primjer. Neka je igra 4x4 data matricom:

Nađimo nižu cijenu igre: α = 0,6. Nađimo gornju cijenu igre: β = 0,6. Ispostavilo se da su isti, pa igra ima neto cijenu jednaku α = β = ν = 0,6. Element 0.6, istaknut u matrici plaćanja, je i minimum u svom redu i maksimum u svojoj koloni. U geometriji, tačka na površini koja ima slično svojstvo (istovremeni minimum u jednoj koordinati i maksimum u drugoj) naziva se sedla; po analogiji, ovaj termin se koristi u teoriji igara. Element matrice koji ima ovo svojstvo naziva se sedlo matrice, a igra se kaže da ima sedlo.

Tačka sedla odgovara paru minimaksnih strategija (u ovom primjeru, A 3 i B 2). Ove strategije se nazivaju optimalnim, a njihova kombinacija se naziva rješenjem igre. Rješenje igre ima sljedeće izvanredno svojstvo. Ako se jedan od igrača (na primjer, A) pridržava svoje optimalne strategije, a drugi igrač (B) na bilo koji način odstupi od svoje optimalne strategije, onda za igrača koji je napravio odstupanje to nikada ne može biti isplativo; npr. odstupanje igrača B može, u najboljem slučaju, ostaviti dobitak nepromijenjenim, au najgorem slučaju ga povećati. Naprotiv, ako se B pridržava svoje optimalne strategije, a A odstupa od svoje, onda to ni na koji način ne može biti od koristi za A.

Ova izjava se može lako provjeriti na primjeru igre koja se razmatra sa sedlom. Vidimo da u slučaju igre sa sedlom, minimaks strategije imaju neku vrstu “stabilnosti”: ako se jedna strana pridržava svoje minimaks strategije, onda drugoj strani može biti samo štetno da odstupi od svoje. Imajte na umu da u ovom slučaju znanje bilo kojeg igrača da je protivnik izabrao njegovu optimalnu strategiju ne može promijeniti igračevo vlastito ponašanje: ako ne želi djelovati protiv svojih interesa, mora se pridržavati svoje optimalne strategije. Par optimalnih strategija u igri na sedlo je poput „ravnotežne pozicije“: svako odstupanje od optimalne strategije dovodi do nepovoljnih posljedica za igrača koji odstupa, prisiljavajući ga da se vrati u prvobitni položaj.

Dakle, za svaku igru ​​sa sedlom postoji rješenje koje određuje par optimalnih strategija za obje strane, koje se razlikuju u sljedećim svojstvima.

1) Ako se obje strane pridržavaju svojih optimalnih strategija, tada je prosječna isplata jednaka neto cijeni igre ν, koja je ujedno i njena donja i gornja cijena.

2) Ako se jedna od strana pridržava svoje optimalne strategije, a druga odstupi od svoje, strana koja odstupa može samo izgubiti i ni u kom slučaju ne može povećati dobitak.

Klasa igara koje imaju sedlo je od velikog interesa i sa teorijske i sa praktične tačke gledišta. U teoriji igara je dokazano da, posebno, svaka igra sa kompletnom informacijom ima sedlo, pa stoga svaka takva igra ima rješenje, tj. postoji par optimalnih strategija za obje strane koje daju prosječnu isplatu jednaku cijeni igre. Ako se igra sa potpunim informacijama sastoji samo od ličnih poteza, onda kada svaka strana primijeni svoju optimalnu strategiju, uvijek bi trebala završiti dobro definiranim ishodom, odnosno pobjedom točno jednakom cijeni igre.

Kao primjer igre sa potpunim informacijama dajemo poznata igra sa novčićima postavljenim na okrugli sto. Dva igrača naizmjenično stavljaju identične novčiće na okrugli sto, svaki put birajući proizvoljan položaj za centar novčića; međusobno pokrivanje kovanica nije dozvoljeno. Igrač koji ubaci zadnji novčić pobjeđuje (kada više nema mjesta za druge). Očigledno je da je ishod ove igre uvijek unaprijed određen, a postoji i dobro definirana strategija koja osigurava sigurnu pobjedu za igrača koji prvi ubaci novčić. Naime, on mora prvi put staviti novčić u centar stola, a zatim na svaki potez protivnika odgovoriti simetričnim potezom. U ovom slučaju, drugi igrač se može ponašati kako želi bez promjene unaprijed određenog ishoda igre. Stoga ova igra ima smisla samo za igrače koji ne znaju optimalnu strategiju. Slična je situacija i sa šahom i drugim igrama sa potpunim informacijama; bilo koja od ovih igara ima sedlo i rješenje koje svakom igraču ukazuje na njegovu optimalnu strategiju; rješenje šahovske partije nije pronađeno samo zbog broja kombinacija mogućim potezima u šahu je prevelika da bi se mogla konstruirati matrica isplate i pronaći sedlo u njoj.

§ 3. Čista i mješovite strategije. Rješavanje mješovite strateške igre

Među konačnim igrama od praktične važnosti, igre sa sedlom su relativno rijetke; tipičniji slučaj je kada se donja i gornja cijena igre razlikuju. Analizirajući matrice ovakvih igara, došli smo do zaključka da ako se svakom igraču pruži izbor jedne strategije, onda, računajući na razumno djelotvornog protivnika, ovaj izbor treba odrediti po principu minimaksa. Pridržavajući se naše maksiminske strategije, svakako si garantiramo dobitak jednak nižoj cijeni igre α, bez obzira na ponašanje neprijatelja. Postavlja se prirodno pitanje: da li je moguće garantovati prosječnu isplatu veću od α ako koristite ne samo jednu „čistu“ strategiju, već nasumično mijenjate nekoliko strategija? Takve kombinovane strategije, koje se sastoje od upotrebe nekoliko čistih strategija, koje se izmjenjuju prema slučajnom zakonu sa određenim omjerom frekvencija, u teoriji igara se nazivaju mješovite strategije.

Očigledno, svaka čista strategija je poseban slučaj mješovite, u kojoj se sve strategije osim jedne primjenjuju sa nultom frekvencijom, a ova sa frekvencijom 1. Ispada da je korištenjem ne samo čistih, već i mješovitih strategija, moguće dobiti za svaku konačnu igru ​​odluku, tj. par (generalno mješovitih) strategija tako da kada ih oba igrača koriste, isplata će biti jednaka cijeni igre, a uz svako jednostrano odstupanje od optimalne strategije, isplata se može promijeniti samo u smjeru nepovoljnom za devijantni.

Navedena tvrdnja čini sadržaj tzv. fundamentalne teoreme teorije igara. Ovu teoremu je prvi dokazao von Neumann 1928. Poznati dokazi teoreme su relativno složeni; Stoga ćemo dati samo njegovu formulaciju.

Svaka konačna igra ima barem jedno rješenje (moguće u području mješovitih strategija).

Isplata koja je rezultat odluke naziva se troškom igre. Iz glavne teoreme slijedi da svaka konačna igra ima cijenu. Očigledno, cijena igre ν uvijek leži između donje cijene igre α i gornje cijene igre β:

(3.1) α ≤ ν ≤ β

Zaista, α je maksimum zagarantovana pobeda, koje sami sebi možemo osigurati primjenom samo naših čistih strategija. Pošto mješovite strategije uključuju, kao poseban slučaj, sve čiste strategije, onda dopuštajući, pored čistih, i mješovite strategije, mi, u svakom slučaju, ne pogoršavamo svoje mogućnosti; dakle, ν ≥ α. Slično tome, s obzirom na mogućnosti neprijatelja, pokazaćemo da je ν ≤ β, što implicira da je nejednakost (3.1) dokazana.

Uvedemo posebnu notaciju za mješovite strategije. Ako se, na primjer, naša mješovita strategija sastoji od korištenja strategija A 1, A 2, A 3 sa frekvencijama p 1, p 2, p 3 i p 1 + p 2 + p 3 = 1, ovu strategiju ćemo označiti

Slično, označit ćemo neprijateljsku mješovitu strategiju:

gdje su q 1, q 2, q 3 frekvencije na kojima se miješaju strategije B 1, B 2, B 3; q 1 + q 2 + q 3 = 1.

Pretpostavimo da smo pronašli rješenje za igru ​​koja se sastoji od dvije optimalne mješovite strategije S A *, S B *. Općenito, nisu sve čiste strategije dostupne datom igraču uključene u njegovu optimalnu mješovitu strategiju, već samo neke. Strategije uključene u igračevu optimalnu mješovitu strategiju nazvat ćemo njegovim „korisnim“ strategijama. Ispostavilo se da rješenje igre ima još jedno izvanredno svojstvo: ako se jedan od igrača drži svoje optimalne mješovite strategije S A * (S B *), tada isplata ostaje nepromijenjena i jednaka je cijeni igre ν, bez obzira na to što drugi igrač to čini, osim ako ne ide dalje od svojih „korisnih“ strategija. Na primjer, može koristiti bilo koju od svojih „korisnih“ strategija u čistom obliku, a može ih i miješati u bilo kojoj proporciji.

§ 4. Elementarne metode rješavanja igrica. Igre 2x2 i 2xn

Ako igra mxn nema sedlo, onda je pronalaženje rješenja općenito prilično težak zadatak, posebno za velike m i n. Ponekad se ovaj zadatak može pojednostaviti ako prvo smanjite broj strategija brisanjem nekih nepotrebnih. Pretjerane strategije su a) duplikativne i b) očigledno neisplative. Razmotrimo, na primjer, matričnu igru:

Lako je provjeriti da strategija A 3 tačno ponavlja („duplira“) strategiju A 1, tako da se bilo koja od ove dvije strategije može eliminisati. Zatim, poredeći nizove A 1 i A 2, vidimo da je svaki element niza A 2 manji (ili jednak) odgovarajućem elementu niza A 1. Očigledno, nikada ne treba koristiti strategiju A2, ona je očigledno neisplativa. Precrtavanjem A 3 i A 2 smanjujemo matricu na više jednostavan pogled. Zatim, napominjemo da je strategija B 3 očigledno neisplativa za neprijatelja; Precrtavanjem matricu dovodimo do njenog konačnog oblika:

Dakle, igra 4x4 se svodi na igru ​​2x3 eliminacijom duplih i očigledno neisplativih strategija.

Procedura za eliminisanje duplih i očigledno neisplativih strategija uvek treba da prethodi rešenju igre. Većina jednostavnim slučajevima Konačne igre koje se uvijek mogu riješiti elementarnim metodama su igre 2x2 i 2xn.

Zamislite igru ​​2x2 sa matricom:

Ovdje se mogu pojaviti dva slučaja: 1) igra ima sedlo; 2) igra nema sedlo. U prvom slučaju, rješenje je očigledno: radi se o paru strategija koje se ukrštaju u tački sedla. Napomenimo uzgred da u igri 2x2 prisustvo sedla uvek odgovara postojanju očigledno neisplativih strategija koje se moraju eliminisati tokom preliminarne analize.

Neka nema sedla i, stoga, donja cijena igre nije jednaka gornjoj: α ≠ β. Moramo pronaći optimalnu mješovitu strategiju za igrača A:

Odlikuje se svojstvom da će, bez obzira na akcije protivnika (osim ako ne pređe granice svojih „korisnih“ strategija), isplata biti jednaka cijeni igre ν. U igri 2x2, obje su protivničke strategije "korisne" - inače bi igra imala čisto strateško rješenje (sedla). To znači da ako se pridržavamo naše optimalne strategije (4.1), onda protivnik može koristiti bilo koju od svojih čistih strategija B 1, B 2 bez promjene prosječne isplate ν. Odavde imamo dvije jednačine:

iz čega, uzimajući u obzir da je p 1 + p 2 = 1, dobijamo:

Cijenu igre ν nalazimo zamjenom vrijednosti p 1, p 2 u bilo koju od jednadžbi (4.2).

Ako je poznata cijena igre, onda odrediti optimalnu strategiju protivnika

Jedna jednadžba je dovoljna, na primjer:

odakle, uzimajući u obzir da je q 1 + q 2 = 1, imamo:

Primjer 1. Nađimo rješenje za igru ​​2×2 razmatranu u primjeru 1 iz § 1 sa matricom:

Igra nema tačku sedla (α = –1; β = +1), pa stoga rješenje mora biti u području mješovitih strategija:

Moramo pronaći p 1, p 2, q 1 i q 2. Za p 1 imamo jednačinu

1*p 1 + (–1)(1 – p 1) = (–1)p 1 + 1(1 – p 1)

odakle je p 1 = 1/2, p 2 = 1/2.

Slično nalazimo: q 1 = 1/2, q 2 = 1/2, ν = 0.

Stoga je optimalna strategija za svakog igrača da nasumično mijenja svoje dvije čiste strategije, koristeći svaku jednako često; u ovom slučaju prosječna dobit će biti nula.

Zaključak je bio dovoljno jasan unaprijed. IN sljedeći primjer Pogledat ćemo složeniju igru, čije rješenje nije tako očigledno. Primjer je rudimentarni primjer igara poznatih kao igre "obmana" ili "prevara". U praksi se često koriste u konfliktnim situacijama Različiti putevi dovođenje neprijatelja u zabludu (dezinformacije, postavljanje lažnih ciljeva, itd.). Primjer je, uprkos svojoj jednostavnosti, prilično poučan.

Primjer 2. Igra je sljedeća. Postoje dvije karte: as i dvojka. Igrač A izvlači jednu nasumično; B ne vidi koju je kartu izvadio. Ako je A izvadio keca, on izjavljuje: “Imam keca” i traži 1 rublju od svog protivnika. Ako je A izvadio dvojku, onda može ili A 1) reći „Imam keca“ i tražiti 1 rublju od protivnika, ili A 2) priznati da ima dvojku i platiti protivniku 1 rublju.

Neprijatelj, ako mu se dobrovoljno plati 1 rublja, može je samo prihvatiti. Ako se od njega traži 1 rublja, onda može ili B 1) vjerovati igraču A da ima keca i dati mu 1 rublju, ili B 2) zahtijevati ček kako bi se uvjerio da je izjava A tačna. Ako je rezultat je Nakon provjere, ispostavilo se da A zaista ima asa, B mora platiti A 2 rublje. Ako se ispostavi da A vara i ima dvojku, igrač A plaća igraču B 2 rublje. Potrebno je analizirati igru ​​i pronaći optimalnu strategiju za svakog igrača.

Rješenje. Igra ima relativno složenu strukturu; sastoji se od jednog obaveznog slučajnog poteza - igrač A bira jednu od dvije karte - i dva lična poteza, koji se, međutim, ne moraju nužno izvesti. Zaista, ako je A izvadio keca, onda ne povlači nikakav lični potez: daje mu se samo jedna prilika - da traži 1 rublju, što on i čini. U ovom slučaju, lični potez - vjerovati ili ne vjerovati (tj. platiti ili ne platiti 1 rublju) - se daje igraču B. Ako je A dobio dvojku kao rezultat prvog slučajnog poteza, tada mu se daje lični potez : platite 1 rublju ili pokušajte prevariti neprijatelja i zatražiti 1 rublju (ukratko: „ne prevariti“ ili „prevariti“). Ako A odabere prvo, onda B može prihvatiti samo 1 rublju; ako je A odabrao drugo, igraču B se daje lični izbor: da veruje ili ne veruje A (tj. plati A 1 rublju ili zahteva verifikaciju).

Strategije svakog igrača su pravila koja pokazuju šta igrač treba da uradi kada dobije lični red. Očigledno, A ima samo dvije strategije: A 1 - prevariti, A 2 - ne prevariti. B takođe ima dve strategije: B 1 - veruj, B 2 - ne veruj. Hajde da napravimo matricu igre. Da bismo to učinili, izračunavamo prosječne dobitke za svaku kombinaciju strategija.

1. A 1 B 1 (A vara, B vjeruje). Ako je A dobio keca (vjerovatnoća za to je ½), onda mu nije dat lični potez; on zahtijeva 1 rublju, a igrač B mu vjeruje; A-ova isplata u rubljama je 1. Ako je A dobio dvojku (vjerovatnoća ovo je također ½), on vara prema svojoj strategiji i traži 1 rublju; B vjeruje i plaća; dobitak A je također jednak 1. Prosječan dobitak: a 11 = ½*1 + ½*1 = 1.

2. A 1 B 2 (A vara, B ne vjeruje). Ako A dobije keca, on nema lični potez; traži 1 rublju; B, prema svojoj strategiji, ne vjeruje u to i, kao rezultat provjere, plaća 2 rublje (isplata A je +2). Ako je A dobio lošu ocjenu, on, prema svojoj strategiji, traži 1 rublju; U, prema svojima, ne vjeruje; kao rezultat, A plaća 2 rublje (A-ova isplata je -2). Prosječan dobitak je: a 12 = ½*(+2) + ½*(–2) = 0.

3. A 2 B 1 (A ne vara, B vjeruje). Ako A izvadi keca, traži 1 rublju; B plaća u skladu sa svojom strategijom; Isplata A je +1. Ako A izvadi dvojku, prema svojoj strategiji plaća 1 rublju; B može samo prihvatiti (A-ova isplata je –1). Prosječan dobitak je: a 21 = ½*(+1) + ½*(–1) = 0.

4. A 2 B 2 (A ne vara, B ne vjeruje). Ako A izvadi keca, traži 1 rublju; B provjerava i kao rezultat provjere plaća 2 rublje (dobitak je +2). Ako A izvadi dvojku, plaća 1 rublju; Sve što ostaje je prihvatiti (isplata je 1). Prosječan dobitak je: a 22 = ½*(+2) + ½*(–1) = ½.

Gradimo matricu igre:

Matrica nema tačku sedla. Donja cijena igre je α = 0, gornja cijena igre je β = ½. Nađimo rješenje za igru ​​u polju mješovitih strategija. Primjenom formule (4.3) dobijamo:

one. Igrač A mora koristiti svoju prvu strategiju (varanje) u jednoj trećini svih slučajeva, a svoju drugu strategiju (ne varanje) u dvije trećine svih slučajeva. U ovom slučaju, on će dobiti u prosjeku cijenu igre ν = 1/3.

Vrijednost ν = 1/3 ukazuje da je pod ovim uvjetima igra isplativa za A i nepovoljna za B. Koristeći svoju optimalnu strategiju, A uvijek može osigurati pozitivnu prosječnu isplatu. Imajte na umu da ako bi A koristio svoju najoprezniju (maksiminalnu) strategiju (u ovom slučaju, obje strategije A 1 i A 2 su maksimalne), on bi imao prosječnu isplatu nula. Dakle, upotreba mješovite strategije daje mogućnost A da ostvari svoju prednost nad B, koja nastaje prema datim pravilima igre.

Odredimo optimalnu strategiju B. Imamo: q 1 *1 + q 2 *0 = 1/3, q 1 = 1/3, q 2 = 2/3. Gdje

tj. igrač B mora vjerovati A u jednoj trećini svih slučajeva i platiti mu 1 rublju bez čeka, au dvije trećine slučajeva - ček. Tada će gubiti u prosjeku 1/3 svake utakmice. Da je koristio svoju minimaks čistu strategiju B 2 (ne vjerujem), gubio bi u prosjeku 1/2 za svaku utakmicu.

Rješenje za igru ​​2x2 može se dati jednostavnom geometrijskom interpretacijom. Neka postoji igra 2x2 sa matricom

Uzmimo presjek ose apscise dužine 1 (slika 4.1). Levi kraj preseka (tačka sa apscisom x = 0) će prikazati strategiju A 1; desni kraj sekcije (x = 1) - strategija A 2. Nacrtajmo dvije okomice na osu apscise kroz tačke A 1 i A 2: os I–I i osovina II–II. Na osi I–I dobit ćemo odložiti za strategiju A 1; na osi II–II-isplate za strategiju A 2. Razmotrite strategiju neprijatelja B 1; daje dvije tačke na osi I–I I II–II sa ordinatama a 11 i a 21, respektivno. Povučemo pravu liniju B 1 B 1 kroz ove tačke. Očigledno, ako koristimo mješovitu strategiju sa neprijateljskom strategijom B 1

tada će naš prosječni dobitak, u ovom slučaju jednak a 11 p 1 + a 21 p 2, biti predstavljen tačkom M na pravoj liniji B 1 B 1; Apscisa ove tačke je jednaka p 2. Prava linija B 1 B 1, koja prikazuje isplatu za strategiju B 1, konvencionalno će se zvati "strategija B 1".

Očigledno, strategija B 2 se može konstruisati na potpuno isti način (slika 4.2).

Moramo pronaći optimalnu strategiju S A *, tj. onu za koju minimalni dobici(za bilo koje ponašanje B) bi se pretvorilo u maksimum. Da bismo to uradili, konstruisaćemo donju granicu za dobitke za strategije B 1, B 2, tj. isprekidana linija B 1 NB 2 označena na sl. 4.2 sa debelom linijom. Ova donja granica će izraziti minimalnu isplatu igrača A za bilo koju od njegovih mješovitih strategija; tačka N u kojoj ova minimalna isplata dostiže maksimum određuje odluku i cijenu igre. Lako je provjeriti da je ordinata tačke N cijena igre ν, a njena apscisa je jednaka p 2 - učestalosti primjene strategije A 2 u optimalnoj mješovitoj strategiji S A *.

U našem slučaju, rješenje igre je određeno presječnom točkom strategija. Međutim, to neće uvijek biti slučaj; na sl. Na slici 4.3 prikazan je slučaj kada, uprkos prisustvu preseka strategija, rešenje daje čiste strategije za oba igrača (A 2 i B 2), a cena igre je ν = a 22. U ovom slučaju, matrica ima sedlo, a strategija A 1 je očigledno neisplativa, jer za bilo koju čistu strategiju protivnika, daje manju isplatu od A 2.

U slučaju kada neprijatelj ima očigledno neisplativu strategiju, geometrijska interpretacija ima oblik prikazan na sl. 4.4.

U ovom slučaju, donja granica dobitka poklapa se sa strategijom B 1, strategija B 2 je očigledno neisplativa za protivnika.

Geometrijska interpretacija takođe omogućava vizualizaciju donje i gornje cene igre (slika 4.5).

Za ilustraciju, konstruirajmo geometrijske interpretacije 2×2 igara o kojima se govori u primjerima 1 i 2 (sl. 4.6 i 4.7).

Pobrinuli smo se da se svaka 2x2 igra može riješiti osnovnim tehnikama. Svaka 2xn igra se može riješiti na potpuno isti način. gdje imamo samo dvije strategije, a neprijatelj ima proizvoljan broj.

Neka imamo dvije strategije: A 1, A 2, a neprijatelj ima n strategija: B 1, B 2, ..., B n. Matrica ‖a ij‖ je data; sastoji se od dva reda i n kolona. Slično kao u slučaju dvije strategije, dajmo problemu geometrijsku interpretaciju; n neprijateljskih strategija će biti prikazano kao n pravih linija (slika 4.8). Konstruišemo donju granicu dobitka (izlomljena linija B 1 MNB 2) i na njoj nalazimo tačku N sa maksimalnom ordinatom. Ova tačka daje rješenje za igru ​​(strategiju ) ordinata tačke N jednaka je cijeni igre ν, a apscisa je jednaka frekvenciji p 2 strategije A 2 .

U ovom slučaju, optimalna strategija neprijatelja se dobija primenom mešavine dve „korisne“ strategije: B 2 i B 4, koje se ukrštaju u tački N. Strategija B 3 je očigledno neisplativa, a strategija B 1 je neisplativa sa optimalnom strategijom S A. *. Ako se A drži svoje optimalne strategije, onda se isplata neće promijeniti, bez obzira koju od njegovih "korisnih" strategija B koristi, međutim, promijenit će se ako B pređe na strategije B 1 ili B 3. U teoriji igara, dokazano je da svaka konačna igra mxn ima rješenje u kojem broj „korisnih“ strategija na obje strane ne prelazi manji od dva broja m i n. Konkretno, iz ovoga proizilazi da igra 2xm uvijek ima rješenje u kojem nije uključeno više od dvije „korisne“ strategije s obje strane.

Koristeći geometrijsku interpretaciju, možemo dati jednostavan način rješavanja bilo koje igre 2xm. Direktno sa crteža nalazimo par „korisnih“ neprijateljskih strategija Bj i Bk koje se ukrštaju u tački N (ako se više od dvije strategije seku u tački N, uzmite bilo koje dvije od njih). Znamo da ako se igrač A pridržava svoje optimalne strategije, onda isplata ne zavisi od omjera u kojem B koristi svoje „korisne“ strategije, dakle,

Iz ovih jednačina i uvjeta p 2 = 1 – p 1 nalazimo p1, p2 i cijenu igre ν. Znajući cijenu igre, možete odmah odrediti optimalnu strategiju igrač B. Da biste to uradili, rešite, na primer, jednačinu: q j a 1 j + q k a 1 k = ν, gde je q j + q k = 1. U slučaju kada imamo m strategija, a neprijatelj ima samo dve, očigledno, problem se rješava na potpuno sličan način; Dovoljno je napomenuti da obrnutim predznakom dobitka možete igrača A pretvoriti iz „pobjednika“ u „gubitnika“. Možete riješiti igru ​​bez promjene pobjedničkog znaka; tada se problem rješava direktno za B, ali ne konstruiše se donja, već gornja granica pojačanja (slika 4.9). Na granici se traži tačka N sa minimalnom ordinatom, što je cena igre ν.

Razmotrimo i riješimo nekoliko primjera igara 2x2 i 2xm, koji su pojednostavljeni primjeri igara koje imaju praktični značaj.

Primjer 3. Strana A šalje dva bombardera na lokaciju neprijatelja B I I II; I leti ispred II- iza. Jedan od bombardera - ne zna se unapred koji - mora da nosi bombu, drugi služi kao pratnja. U neprijateljskom području bombardere napada lovac sa strane B. Bombarderi su naoružani topovima različite brzine vatre. Ako lovac napadne zadnji bombarder II, onda na njega pucaju samo topovi ovog bombardera; ako napadne prednji bombarder, onda na njega pucaju topovi oba bombardera. Verovatnoća da ćete pogoditi borca ​​u prvom slučaju je 0,3, u drugom 0,7.

Ako lovac nije oboren odbrambenom vatrom bombardera, pogodi izabranu metu sa vjerovatnoćom od 0,6. Zadatak bombardera je da isporuče bombu do cilja; Zadatak borca ​​je da to spriječi, tj. oborite noseći bombarder. Potrebno je odabrati optimalne strategije stranaka:

a) za stranu A: koji bombarder treba koristiti kao nosač?

b) za stranu B: koji bombarder napasti?

Rješenje. Imamo jednostavan slučaj igre 2x2; pobjeda - vjerovatnoća neinfekcija domaćina. Naše strategije: A 1 - nosač - bombarder I; A 2 - nosač - bombarder II. Neprijateljske strategije: B 1 - napad bombardera I; B 2 - napadi bombardera II. Kreirajmo matricu igre, tj. Nađimo prosječnu isplatu za svaku kombinaciju strategija.

1. A 1 B 1 (nosač I, napadnut I). Nosač neće biti pogođen ako bombarderi obore lovac, ili ne, ali neće pogoditi svoju metu: a 11 = 0,7 + 0,3 * 0,4 = 0,82.

2. A 2 B 1 (nosač II, napadnut I). a 21 = 1

3. A 1 B 2 (nosač I, napadnut II). A 12 = 1

4. A 2 B 2 (nosač II, napadnut II). A 22 = 0,3 + 0,7*0,4 = 0,58

Matrica igre izgleda ovako:

Niska cijena igre 0,82; gornja cijena 1. Matrica nema sedlo; Tražimo rješenje u području mješovitih strategija. Imamo:

p 1 *0,82 + p 2 *1 = ν

p 1 *1 + p 2 *0,58 = ν

p 1 = 0,7; p 2 = 0,3

Naša optimalna strategija da, tj. morate češće birati kao nosioca I, kako II. Cijena igre je ν = 0,874. Znajući ν, određujemo q 1 i q 2 - frekvencije strategija B 1 i B 2 u optimalnoj strategiji protivnika S B *. Imamo: q 1 *0,82 + q 2 *1 = 0,874 i q 2 = 1 – q 1, odakle je q 1 = 0,7; q 2 = 0,3, tj. optimalna strategija neprijatelja je .

Primjer 4. Strana A napada objekat, strana B ga brani. Strana A ima dvije ravni; strana B ima tri protivavionska topa. Svaki avion je nosilac moćnog smrtonosnog oružja; Da bi neki objekat bio pogođen, dovoljno je da se do njega probije barem jedan avion. Zrakoplov sa strane A može izabrati bilo koji od tri smjera da se približi objektu: I, II, III(Sl. 4.10). Neprijatelj (strana B) može postaviti bilo koje svoje oružje u bilo kojem smjeru; u ovom slučaju, svako oružje gađa samo područje prostora koje se odnosi na ovom pravcu, i ne puca kroz susjedne smjerove. Svaki top može ispaliti samo jedan avion; ispaljeni avion je pogođen sa vjerovatnoćom 1. Strana A ne zna gdje se nalaze topovi; Strana B ne zna odakle će avioni doći. Zadatak strane A je da pogodi metu; Zadatak strane B je spriječiti njegov poraz. Pronađite rješenje za igru.

Rješenje. Igra je 2x3 igra. Pobjeda je vjerovatnoća da ćete pogoditi predmet. Naše moguće strategije: A 1 - poslati jedan avion na dva raznim pravcima. A 2 - poslati oba aviona u istom pravcu. Neprijateljske strategije: B 1 - postavite po jednu pušku u svakom smjeru; B 2 - postaviti dvije puške u jednom smjeru i jednu u drugom; Na 3 - postavite sva tri pištolja u istom smjeru. Kreirajmo matricu igre.

1. A 1 B 1 (avioni lete različitim pravcima; puške se postavljaju jedno po jedno). Očigledno, u ovom slučaju, niti jedna ravan neće se probiti do objekta: a 11 = 0.

2. A 2 B 1 (avioni lete zajedno u jednom pravcu; topovi se postavljaju jedno po jedno). Očigledno je da će u ovom slučaju jedan avion proći do objekta bez pucanja na njega: a 21 = 1.

3. A 1 B 2 (avioni lete jedan po jedan; neprijatelj štiti dva pravca, a treći ostavlja nezaštićenim). Vjerovatnoća da će se barem jedan avion probiti do objekta jednaka je vjerovatnoći da će jedan od njih izabrati nezaštićeni pravac: a 12 = 2/3.

4. A 2 B 2 (avioni lete zajedno u jednom pravcu; neprijatelj štiti jedan pravac sa dva topa i jedan sa jednim, tj. zapravo štiti jedan pravac a dva ostavlja nezaštićena). Vjerovatnoća da će se barem jedna ravnina probiti do objekta jednaka je vjerovatnoći da će par aviona izabrati stvarno nezaštićeni smjer: a 22 = 2/3.

5. A 1 B 3 (avioni lete jedan po jedan; neprijatelj brani samo jedan pravac sa tri topa): a 13 = 1.

6. A 2 B 3 (oba aviona lete zajedno; neprijatelj brani samo jedan pravac sa tri topa). Da bi objekat bio pogođen, avion mora izabrati nezaštićeni pravac: a 23 = 2/3.

Matrica igre:

Iz matrice je jasno da je strategija B 3 očigledno neisplativa u odnosu na B 2 (ovo se moglo unaprijed odlučiti). Eliminacijom strategije B 3 igra se svodi na igru ​​2x2:

Matrica ima sedlo: donja cijena igre 2/3 poklapa se s gornjom. Istovremeno, napominjemo da je za nas (A) strategija A 1 očigledno neisplativa. Zaključak: obje strane A i B uvijek trebaju koristiti svoje čiste strategije A 2 i B 2, tj. moramo poslati avione u 2s, nasumično birajući smjer u kojem se par šalje; neprijatelj mora postaviti puške ovako: dva - u jednom smjeru, jedan u drugom, a izbor ovih pravaca također mora biti napravljen nasumično (ovdje, kao što vidimo, "čiste strategije" već uključuju element slučajnosti). Primjenom ovih optimalnih strategija uvijek ćemo dobiti konstantnu prosječnu isplatu od 2/3 (tj., objekt će biti pogođen sa vjerovatnoćom od 2/3). Imajte na umu da pronađeno rješenje za igru ​​nije jedinstveno; pored rešenja u čistim strategijama, postoji čitav deo mešovitih strategija igrača A koje su optimalne, od p 1 = 0 do p 1 = 1/3 (slika 4.11).

Lako je, na primjer, direktno provjeriti da će se isti prosječni dobitak od 2/3 dobiti ako primijenimo naše strategije A 1 i A 2 u omjeru 1/3 i 2/3.

Primjer 5. Isti uslovi kao u prethodnom primjeru, ali su nam moguća četiri pravca napada, a neprijatelj ima četiri topa.

Rješenje. Još uvijek imamo dvije moguće strategije: A 1 - poslati avione jedan po jedan, A 2 - poslati dva aviona zajedno. Neprijatelj ima pet mogućih strategija: B 1 - postavite po jednu pušku u svakom smjeru; U 2 - postavite dva pištolja u dva različita smjera; U 3 - postavite dvije puške u jednom smjeru i po jednu u druga dva; B 4 - postaviti tri puške u jednom smjeru i jedan u drugom; Na 5 - postavite sva četiri pištolja u jednom smjeru. Strategije B 4 i B 5 unapred ćemo odbaciti kao očigledno neisplative. Rezonirajući slično prethodnom primjeru, gradimo matricu igre:

Donja cijena igre je 1/2, gornja 3/4. Matrica nema tačku sedla; rješenje leži u području mješovitih strategija. Koristeći geometrijsku interpretaciju (slika 4.12), ističemo neprijateljske „korisne“ strategije: B 1 i B 2.

Određujemo frekvencije p 1 i p 2 iz jednačina: p 1 *0 + (1 – p 1)*1 = ν i p 1 *5/6 + (1 – p 1)*1/2 = ν; odakle je p 1 = 3/8; p 2 = 5/8; ν = 5/8, tj. naša optimalna strategija je . Koristeći ga, garantujemo sebi prosječnu pobjedu od 5/8. Znajući cijenu igre ν = 5/8, nalazimo frekvencije q 1 i q 2 protivnikovih „korisnih“ strategija: q 1 *0 + (1 – q 1)*5/6 = 5/8, q 1 = ¼, q 2 = ¾. Optimalna strategija neprijatelja će biti: .

Primjer 6. Strana A ima dve strategije A 1 i A 2, strana B ima četiri strategije B 1, B 2, B 3 i B 4. Matrica igre izgleda ovako:

Pronađite rješenje za igru.

Rješenje. Igra najniže cijene 3; vrh 4. Geometrijska interpretacija (slika 4.13) pokazuje da su korisne strategije za igrača B B 1 i B 2 ili B 2 i B 4:

Igrač A ima beskonačno mnogo optimalnih mješovitih strategija: u optimalnoj strategiji, p 1 može varirati od 1/5 do 4/5. Cijena igre je ν = 4. Igrač B ima čistu optimalnu strategiju B 2 .

§ 5. Opće metode rješenja konačnih igara

Do sada smo razmatrali samo najelementarnije igre tipa 2xn, koje se mogu vrlo jednostavno riješiti i omogućavaju zgodnu i vizualnu geometrijsku interpretaciju. Općenito, rješenje za igru ​​mxn je prilično težak zadatak, a složenost problema i količina proračuna potrebnih za njegovo rješavanje naglo raste s povećanjem m i n. Međutim, ove poteškoće nisu fundamentalne prirode i povezane su samo s vrlo velikim obimom proračuna, što se u nekim slučajevima može pokazati praktički nemogućim. Osnovni aspekt metode za pronalaženje rješenja ostaje isti za bilo koje m.

Ilustrujmo to na primjeru igre 3xn. Hajde da mu damo geometrijsku interpretaciju - već prostornu. Naše tri strategije A 1 , A 2 i A 3 će biti predstavljene sa tri tačke na ravni xOy; prvi leži na početku koordinata (slika 5.1), drugi i treći - na osi Oh I OU na udaljenosti 1 od početka.

Ose se povlače kroz tačke A 1, A 2 i A 3 I – I, II – II I III – III, okomito na ravan xOy. Na osi I – I dobici za strategiju A 1 se odlažu na osi II – II I III – III- dobici za strategije A 2, A 3. Svaka neprijateljska strategija B j će biti predstavljena ravninom koja odsijeca ose I – I, II – II I III – III segmente jednake dobicima za odgovarajuće strategije A 1, A 2 i A 3 i strategiju B j. Nakon što smo na ovaj način konstruisali sve neprijateljske strategije, dobijamo familiju aviona iznad trougla A 1, A 2 i A 3 (slika 5.2). Za ovu porodicu možete konstruisati i donju granicu za isplatu, kao što smo uradili u slučaju 2xn, i pronaći na ovoj granici tačku N sa maksimalnom visinom iznad ravni xOy. Ova visina će biti trošak igre ν.

Frekvencije p 1 , p 2 , p 3 strategija A 1 , A 2 i A 3 u optimalnoj strategiji S A * će biti određene koordinatama (x, y) tačke N, odnosno: p 2 = x, p 3 = y, p 1 = 1 – p 2 – p 3 . Međutim, ovo geometrijska konstrukcijačak ni za slučaj 3xn nije lako implementirati i zahtijeva puno vremena i truda mašte. U opštem slučaju igre, ona se prenosi u m-dimenzionalni prostor i gubi svaku jasnoću, iako upotreba geometrijske terminologije u brojnim slučajevima može biti korisna. Prilikom rješavanja mxn igara u praksi, pogodnije je koristiti ne geometrijske analogije, već izračunate analitičke metode, pogotovo jer su ove metode jedine prikladne za rješavanje problema na računalima.

Sve ove metode u suštini se svode na rješavanje problema kroz uzastopne pokušaje, ali redoslijed pokušaja vam omogućava da izgradite algoritam koji vodi do rješenja na najekonomičniji način. Ovdje ćemo se ukratko zadržati na jednoj metodi proračuna za rješavanje mxn igara - tzv. linearno programiranje" Da bismo to učinili, prvo ćemo dati opću formulaciju problema nalaženja rješenja za igru ​​mxn. Neka je data igra mxn sa m strategija A 1 , A 2 , …, A m igrača A i n strategija B 1 , B 2 , …, B n igrača B i data je matrica plaćanja ‖a i j ‖. Potrebno je pronaći rješenje za igru, tj. dvije optimalne mješovite strategije igrača A i B

gdje je p 1 + p 2 + … + p m = 1; q 1 + q 2 + … + q n = 1 (neki od brojeva p i i q j mogu biti nula).

Naša optimalna strategija S A * mora nam osigurati dobitak ne manji od ν za bilo koje ponašanje neprijatelja, i dobitak jednak ν za njegovo optimalno ponašanje (strategija S B *). Slično, strategija S B * treba da obezbedi neprijatelju gubitak koji nije veći od ν za bilo koje naše ponašanje i jednak ν za naše optimalno ponašanje (strategija S A *).

Vrijednost igre ν u ovom slučaju nam je nepoznata; pretpostavićemo da je jednak nekom pozitivnom broju. Vjerujući na ovaj način, mi ne kršimo općenitost rezonovanja; Da bi ν > 0, očigledno je dovoljno da su svi elementi matrice ‖a i j‖ nenegativni. To se uvijek može postići dodavanjem dovoljno velike pozitivne vrijednosti elementima ‖a i j ‖ L; cijena igre će porasti za L, ali odluka se neće mijenjati.

Odaberimo našu optimalnu strategiju S A *. Tada će naša prosječna isplata za protivničku strategiju B j biti jednaka: a j = p 1 a 1j + p 2 a 2j + … + p m a mj . Naša optimalna strategija S A * ima svojstvo da, za bilo koje ponašanje neprijatelja, daje isplatu ne manju od ν; prema tome, bilo koji od brojeva a j ne može biti manji od ν. Dobijamo niz uslova:

Podijelimo nejednačine (5.1) pozitivnom vrijednošću ν i označimo

Tada će uslovi (5.1) biti upisani u formu

gdje su ξ 1, ξ 2, …, ξ m nenegativni brojevi. Pošto je r 1 + p 2 + … + p m = 1, tada veličine ξ 1, ξ 2, …, ξ m zadovoljavaju uslov

(5.3) ξ 1 + ξ 2 + … + ξ m = 1/ν.

Želimo da naši zagarantovani dobici budu što veći; očigledno, u isto vreme desni deo jednakost (5.3) uzima minimalnu vrijednost. Dakle, problem nalaženja rješenja igre svodi se na sljedeći matematički problem: odrediti nenegativne veličine ξ 1, ξ 2, ..., ξ m, koje zadovoljavaju uvjete (5.2), tako da njihov zbir Φ = ξ 1 + ξ 2 + ... + ξ m je bio minimalan.

Obično, kada se rješavaju problemi vezani za pronalaženje ekstremnih vrijednosti (maksimuma i minimuma), funkcija se diferencira i derivacije se postavljaju jednake nuli. Ali takva tehnika je u ovom slučaju beskorisna, jer je funkcija Φ, koju treba minimizirati, linearna, a njeni derivati ​​u odnosu na sve argumente jednaki su jedinici, tj. ne nestati nigde. Shodno tome, maksimum funkcije se postiže negdje na granici raspona promjena argumenata, što je određeno zahtjevom nenegativnosti argumenata i uslova (5.2). Tehnika pronalaženja ekstremnih vrijednosti korištenjem diferencijacije također je neprikladna u slučajevima kada je određen maksimum donje (ili minimuma gornje) granice dobitka za rješavanje igre, kao što smo, na primjer, radili pri rješavanju 2xn igara . Zaista, donju granicu čine dijelovi pravih linija, a maksimum se ne postiže u tački gdje je derivacija jednaka nuli (takve tačke uopće nema), već na granici intervala ili na tačka preseka pravih deonica.

Za rješavanje ovakvih problema, koji se često susreću u praksi, razvijen je poseban aparat za linearno programiranje u matematici. Problem linearnog programiranja je formuliran na sljedeći način. Dat sistem linearnih jednačina:

Potrebno je pronaći nenegativne vrijednosti veličina ξ 1, ξ 2, …, ξ m, koje zadovoljavaju uslove (5.4) i istovremeno minimiziraju datu homogenu linearnu funkciju veličina ξ 1, ξ 2, …, ξ m (linearni oblik): Φ = c 1 ξ 1 + c 2 ξ 2 + … + c m ξ m

Lako je vidjeti da je gore postavljeni problem teorije igara poseban slučaj problema linearnog programiranja sa c 1 = c 2 = ... = c m = 1. Na prvi pogled može izgledati da uslovi (5.2) nisu ekvivalentni na uslove (5.4), budući da umjesto znakova jednakosti sadrže znakove nejednakosti. Međutim, lako se riješiti znakova nejednakosti uvođenjem novih fiktivnih nenegativnih varijabli z 1, z 2, ..., z n i pisanjem uslova (5.2) u obliku:

Oblik Φ koji treba minimizirati je Φ = ξ 1 + ξ 2 + … + ξ m. Aparat za linearno programiranje omogućava da se pomoću relativno malog broja uzastopnih uzoraka odaberu vrednosti ξ 1, ξ 2, ..., ξ m koje zadovoljavaju postavljene zahteve. Radi veće jasnoće, ovdje ćemo demonstrirati upotrebu ovog aparata direktno na materijalu rješavanja konkretnih igara.

Primjer 1. Potrebno je pronaći rješenje za igru ​​3×3 datu u primjeru 2 iz § 1, sa matricom:

Da bi sve a ij bilo nenegativno, svim elementima matrice dodajemo L = 5. Dobijamo matricu:

U tom slučaju cijena igre će porasti za 5, ali rješenje se neće promijeniti.

Odredimo optimalnu strategiju S A *. Uslovi (5.2) imaju oblik:

gdje je ξ 1 = p 1 /ν, ξ 2 = p 2 /ν, ξ 3 = p 3 /ν. Da bismo se riješili znakova nejednakosti, uvodimo lažne varijable z 1, z 2, z 3; uslovi (5.6) biće zapisani kao:

Linearni oblik Φ je: Φ = ξ 1 + ξ 2 + ξ 3 i treba ga učiniti što manjim. Ako su sve tri strategije B „korisne“, tada će sve tri lažne varijable z 1 , z 2 , z 3 nestati (tj., isplatit će se jednak trošku igre ν za svaku strategiju B j). Ali još nemamo razloga da kažemo da su sve tri strategije „korisne“. Da bismo to proverili, pokušajmo da izrazimo oblik Φ u terminima lažnih varijabli z 1, z 2, z 3 i vidimo da li postižemo minimum forme tako što ćemo ih postaviti jednakim nuli. Da bismo to učinili, riješimo jednačine (5.7) u odnosu na varijable ξ 1, ξ 2, ξ 3 (tj. izrazimo ξ 1, ξ 2, ξ 3 kroz fiktivne varijable z 1, z 2, z 3):

Sabiranjem ξ 1, ξ 2, ξ 3 dobijamo: Φ = 1/5 + z 1/20 + z 2/10 + z 3/20. Ovdje su koeficijenti za sve z pozitivni; To znači da svako povećanje z 1, z 2, z 3 iznad nule može dovesti samo do povećanja oblika Φ, a mi želimo da ono bude minimalno. Prema tome, vrijednosti z 1, z 2, z 3, pretvarajući oblik Φ na minimum, su z 1 = z 2 = z 3 = 0. Dakle, minimalna vrijednost oblika Φ: 1/ν = 1/5, odakle je cijena igre ν = 5. Zamjenom nultih vrijednosti z 1, z 2, z 3 u formule (5.8) nalazimo: ξ 1 = 1/20, ξ 2 = 1/10, ξ 3 = 1/20, ili, množeći ih sa ν, p 1 = 1/4, p 2 = 1/2, p 3 = 1/4. Tako se pronalazi optimalna strategija A: , tj. treba da upišemo broj 1 u jednoj četvrtini svih slučajeva, 2 u polovini slučajeva i 3 u preostaloj četvrtini slučajeva.

Znajući cijenu igre ν = 5, već možemo poznatim metodama pronaći optimalnu strategiju neprijatelja . Da bismo to učinili, koristit ćemo naše bilo koje dvije „korisne“ strategije (na primjer, A 2 i A 3) i napisati jednadžbe:

9q 1 + 11 (1-q 2 -q 1) = 5,

odakle je q 1 = q3 = 1/4; q 2 = 1/2. Optimalna strategija neprijatelja će biti ista kao i naša: . Sada se vratimo na originalnu (nekonvertovanu) igru. Da biste to učinili, trebate samo oduzeti vrijednost L = 5 dodanu elementima matrice od cijene igre ν = 5. Dobijmo cijenu originalne igre v 0 = 0. Prema tome, optimalne strategije obje strane daju prosječnu isplatu jednaku nuli; igra je podjednako korisna ili štetna za obje strane.

Primjer 2. Sportski klub A ima tri opcije za sastav tima: A 1, A 2 i A 3. Klub B - takođe sa tri opcije B 1, B 2 i B 3. Prilikom prijave za učešće u takmičenju, nijedan klub ne zna koji će sastav protivnik izabrati. Vjerojatnosti pobjede kluba A za različite sastave timova, približno poznate iz iskustva prošlih susreta, date su matricom:

Pronađite učestalost kojom bi klubovi trebali igrati svaki od svojih timova u međusobnim utakmicama kako bi postigli najveći prosječan broj pobjeda.

Rješenje. Niska cijena igre 0,4; vrh 0,6; Tražimo rješenje u području mješovitih strategija. Da ne bismo imali posla sa razlomcima, pomnožimo sve elemente matrice sa 10; u ovom slučaju cijena igre će porasti 10 puta, ali odluka se neće promijeniti. Dobijamo matricu:

Uslovi (5.5) imaju oblik:

a minimalni uslov je Φ = ξ 1 + ξ 2 + ξ 3 = min.

Provjeravamo da li su sve tri neprijateljske strategije “korisne”. Kao hipotezu, prvo pretpostavljamo da su lažne varijable z 1, z 2, z 3 jednake nuli, a radi provjere rješavamo jednadžbe (5.10) za ξ 1, ξ 2, ξ 3:

(5.12) 136Φ = 30 +13z 1 +18z 2 – 51z 3

Formula (5.12) pokazuje da povećanje varijabli z 1 i z 2 od njihove pretpostavljene vrijednosti od nule može samo povećati Φ, dok povećanje z 3 može smanjiti Φ. Međutim, povećanje z 3 mora se obaviti pažljivo kako vrijednosti ξ 1, ξ 2, ξ 3, u zavisnosti od z 3, ne bi postale negativne. Stoga, postavimo vrijednosti z 1 i z 2 jednake nuli na desnoj strani jednakosti (5.11) i povećamo vrijednost z 3 do prihvatljivih granica (sve dok bilo koja od vrijednosti ξ 1 , ξ 2 , ξ 3 ide na nulu). Iz druge jednakosti (5.11) jasno je da je povećanje z 3 „sigurno“ za vrijednost ξ 2 – od ovoga samo raste. Što se tiče vrijednosti ξ 1 i ξ 3, ovdje je povećanje z 3 moguće samo do određene granice. Vrijednost ξ 1 postaje nula pri z 3 = 10/23; vrijednost ξ 3 nestaje ranije, već kod z 3 = 1/4. Prema tome, dajući z 3 njegovu maksimalnu dozvoljenu vrijednost z 3 = 1/4, vrijednost ξ 3 ćemo okrenuti na nulu.

Da bismo provjerili da li se oblik Φ pretvara u minimum pri z 1 = 0, z 2 = 0, ξ 3 = 0, izražavamo preostale (ne-nulte) varijable u terminima navodno nula z 1, z 2, ξ 3. Rješavajući jednadžbe (5.10) za ξ 1, ξ 2 i z 3, dobijamo:

(5.13) 32Φ = 7 + Zz 1 + 4z 2 + ξ 3

Iz formule (5.13) jasno je da svako povećanje z 1, z 2, ξ 3 iznad njihovih pretpostavljenih nultih vrijednosti može samo povećati oblik Φ. Shodno tome, rješenje za igru ​​je pronađeno; određen je vrijednostima z 1 = z 2 = ξ 3 = 0, odakle je ξ 1 = 1/32, ξ 2 = 3/16, z 3 = 1/4. Zamjenom u formulu (5.13) nalazimo cijenu igre ν: 32Φ = 7 = 32/ν; ν = 32/7. Naša optimalna strategija: . „Korisne“ strategije (kompozicije A 1 i A 2) treba primenjivati ​​na frekvencijama od 1/7 i 6/7; sastav A 3 - nikada ne koristiti.

Da biste pronašli optimalnu strategiju protivnika, u opštem slučaju, možete učiniti ovo: promijeniti predznak isplate u suprotan, dodati konstantnu vrijednost L elementima matrice kako bi bili nenegativni i riješili problem za protivnika na isti način kako smo to sami riješili. Međutim, činjenica da već znamo cijenu igre ν donekle pojednostavljuje problem. Osim toga, u ovom konkretnom slučaju, problem je dodatno pojednostavljen činjenicom da su u rješenje uključene samo dvije „korisne“ neprijateljske strategije B 1 i B 2, budući da vrijednost z 3 nije jednaka nuli, pa stoga , sa strategijom B 3 trošak igre nije postignut. Odabirom bilo koje "korisne" strategije igrača A, na primjer A 1, možete pronaći frekvencije q 1 i q 2. Da bismo to uradili, pišemo jednačinu 8q 1 + 2(1 – q 1) = 32/7, iz koje je q 1 = 3/7, q 2 = 4/7; Optimalna strategija neprijatelja će biti: , tj. neprijatelj ne treba koristiti kompoziciju B 3, a kompozicije B 1 i B 2 treba koristiti sa frekvencijama 3/7 i 4/7.

vraćajući se u originalna matrica, odredimo pravu cijenu igre ν 0 = 32/7:10 = 0,457. To znači da će uz veliki broj susreta broj pobjeda kluba A biti 0,457 od svih susreta.

§ 6. Približne metode rješavanja igrica

Često u praktičnim problemima nema potrebe da se pronađe tačno rešenje za igru; Dovoljno je pronaći približno rješenje koje daje prosječnu isplatu blizu cijene igre. Približno znanje o cijeni igre ν može se dobiti jednostavnom analizom matrice i određivanjem donje (α) i gornje (β) cijene igre. Ako su α i β bliski, praktički nema potrebe tražiti egzaktno rješenje, već će biti dovoljno odabrati čiste minimaksne strategije. U slučajevima kada α i β nisu bliski, moguće je dobiti praktično rješenje pomoću numeričkih metoda za rješavanje igara, od kojih ćemo ukratko istaknuti metodu iteracije.

Ideja metode iteracije svodi se na sljedeće. Izvodi se “misaoni eksperiment” u kojem protivnici A i B koriste svoje strategije jedni protiv drugih. Eksperiment se sastoji od niza elementarnih igara, od kojih svaka ima matricu date igre. Počinje činjenicom da mi (igrač A) nasumično biramo jednu od naših strategija, na primjer A i. Neprijatelj na to odgovara svojom strategijom B j , koja je za nas najmanje korisna, tj. smanjuje isplatu za strategiju A i na minimum. Na ovaj potez odgovaramo našom strategijom A k, koja daje maksimalan prosječan dobitak kada protivnik koristi strategiju B j. Zatim, opet je red na neprijatelja. On na naš par poteza A i i A k odgovara svojom strategijom B j, što nam daje najmanju prosječnu isplatu za ove dvije strategije (A i, A k), i tako dalje. U svakom koraku iterativnog procesa, svaki igrač odgovara na bilo koji potez drugog igrača svojom strategijom, koja je optimalna u odnosu na sve njegove prethodne poteze, smatra se nekom mješovitom strategijom u kojoj su čiste strategije predstavljene u proporcijama koje odgovaraju učestalosti njihovu upotrebu.

Ova metoda je kao model pravog praktičnog „treninga“ igrača, kada svaki od njih doživljava ponašanje neprijatelja i pokušava na njega odgovoriti na sebi koristan način. Ako se takva imitacija procesa učenja nastavi dovoljno dugo, tada će prosječan dobitak po jednom paru poteza (elementarna igra) težiti cijeni igre, a frekvencije p 1 ... p m ; q 1 ... q n , na koje se strategije igrača susreću u ovoj igri, približit će se frekvencijama koje određuju optimalne strategije. Proračuni pokazuju da je konvergencija metode vrlo spora, ali to nije prepreka za brze računske mašine.

Ilustrujmo primjenu iterativne metode na primjeru igre 3x3 riješene u primjeru 2 prethodnog pasusa. Igra je data matricom:

Tabela 6.1 prikazuje prvih 18 koraka iterativnog procesa. Prva kolona daje broj elementarna igra(parovi poteza) n; u drugom - broj i izabrana strategija igrača A; u naredna tri - "akumulirani dobici" za prvu n igre sa protivničkim strategijama B 1, B 2, B 3. Minimum ovih vrijednosti je podvučen. Zatim dolazi broj j strategiju koju odabere protivnik i, shodno tome, akumulirani dobitak za n igre za strategije A 1 , A 2 , A 3 od ovih vrijednosti maksimum je podvučen iznad. Podvučene vrijednosti određuju izbor strategije odgovora drugog igrača. Sljedeće kolone redom prikazuju: minimalni prosječni dobici ν, jednak minimalnom akumuliranom dobitku podijeljenom sa brojem igara n; maksimalni prosječni dobici, jednak maksimalnom akumuliranom dobitku podijeljenom sa n, i njihova aritmetička sredina ν* = (ν + )/2. Prilikom povećanja n sve tri vrijednosti ν i ν* će se približiti cijeni igre ν, ali će joj se vrijednost ν* prirodno približiti relativno brže.

Tabela 6.1.

Kao što se može vidjeti iz primjera, konvergencija iteracija je vrlo spora, ali ipak čak i tako mala kalkulacija omogućava da se pronađe približna vrijednost cijene igre i utvrdi prevlast „korisnih“ strategija. Kada se koriste računske mašine, vrijednost metode se značajno povećava. Prednost iterativne metode rješavanja igara je da se obim i složenost proračuna relativno malo povećavaju kako se broj strategija povećava. m I n.

§ 7. Metode rješavanja nekih beskonačnih igara

Beskonačna igra je igra u kojoj barem jedna od strana ima beskonačan broj strategija. Opće metode rješavanja ovakvih igara još uvijek su slabo razvijene. Međutim, neki posebni slučajevi koji omogućavaju relativno jednostavno rješenje mogu biti od interesa za praksu. Razmotrimo igru ​​dva protivnika A i B, od kojih svaki ima beskonačan (nebrojiv) skup strategija; ove strategije za igrača A odgovaraju različita značenja parametar koji se kontinuirano mijenja X, a za B - parametar at. U ovom slučaju, umjesto matrice ‖a ij‖ igra je određena određenom funkcijom dva argumenta koji se kontinuirano mijenjaju a(x, y), koju ćemo nazvati funkcijom isplate (imajte na umu da sama funkcija a(x, y) ne mora biti kontinuiran). Win funkcija a(x, y) može se geometrijski predstaviti nekom površinom a(x, y) iznad područja promjene argumenta (x, y)(Sl. 7.1)

Analiza funkcije isplate a(x, y) vrši se slično kao i analiza platne matrice. Prvo, pronađena je niža cijena igre α; u tu svrhu se određuje za svaku X minimalna funkcija a(x, y) na sve at: , tada se traži maksimum od ovih vrijednosti preko svih X(maksimalno):

Gornja cijena igre (minimax) se određuje na sličan način:

Razmotrimo slučaj kada je α = β. Budući da je cijena igre ν uvijek između α i β, njihova ukupna vrijednost je ν. Jednakost α = β znači da je površina a(x, y) ima tačku sedla, tj. tačku sa koordinatama x 0, y 0, u kojoj a(x, y) je istovremeno minimalan in at i maksimum X(Sl. 7.2).

Značenje a(x, y) u ovom trenutku je cijena igre ν: ν = a(x 0, y 0). Prisutnost sedla znači da data beskonačna igra ima čisto strateško rješenje; x 0, y 0 predstavljaju optimalne čiste strategije A i B. U opštem slučaju, kada je α ≠ β, igra može imati rešenje samo u domenu mešovitih strategija (možda ne i jedino). Mješovita strategija za beskonačne igre postoji određena distribucija vjerovatnoće za strategije X I at, smatra se slučajnim varijablama. Ova raspodjela može biti kontinuirana i određena gustoćama f 1 (X) I f 2 (y); mogu biti diskretne, a onda se optimalne strategije sastoje od skupa pojedinačnih čistih strategija izabranih sa nekim nenultim vjerovatnoćama.

U slučaju kada beskonačna igra nema sedlo, možemo dati jasnu geometrijsku interpretaciju donje i gornje cijene igre. Razmislite o beskonačnoj igri s funkcijom isplate a(x, y) i strategije x, y, ispunjavajući kontinuirano segmente osi (x 1, x 2) I (y 1, y 2). Da biste odredili nižu cijenu igre α, morate „pogledati“ na površinu a(x, y) sa strane osovine at, tj. projektovati na ravan xOa(Sl. 7.3). Dobijamo određenu figuru ograničenu na stranama pravim linijama x = x 1 i x = x 2, a na vrhu i dnu krivuljama K B i K H. Niža cijena igre α, očito, nije ništa više od maksimalne ordinate krive K H.

Slično tome, da biste pronašli gornju cijenu igre β, morate „pogledati“ na površinu a(x, y) sa strane osovine X(projicirati površinu na ravan uOa) i pronađite minimalnu ordinatu gornje granice K B projekcije (slika 7.4).

Pogledajmo dva elementarna primjera beskonačnih igara.

Primjer 1. Svaki igrač A i B imaju nebrojen skup mogućih strategija X I at, i 0 ≤ x ≤ 1; 0 ≤ y ≤ 1. Funkcija isplate za a data je izrazom a (x, y) – (x – y) 2 . Pronađite rješenje za igru.

Rješenje: Površina a(x, y) je parabolički cilindar (slika 7.5) i nema sedlo. Odredimo nižu cijenu igre; očigledno za sve X; dakle = 0. Odredimo gornju cijenu igre. Da bismo to učinili, nalazimo za fiksni at

U ovom slučaju, maksimum se uvijek postiže na granici intervala (na x = 0 ili x = 1), tj. jednaka je količini y 2; (1 – y) 2, što je veće. Hajde da prikažemo grafove ovih funkcija (slika 7.6), tj. površinska projekcija a(x, y) u avion uOa. Debela linija na sl. 7.6 prikazuje funkciju. Očigledno, njegova minimalna vrijednost se postiže pri y = 1/2 i jednaka je 1/4. Stoga je gornja cijena igre β = 1/4. U ovom slučaju, gornja cijena igre se poklapa sa cijenom igre ν. Zaista, igrač A može primijeniti mješovitu strategiju S A = , u kojem se ekstremne vrijednosti x = 0 i x = 1 javljaju s istim frekvencijama; tada će za bilo koju strategiju igrača B prosječna isplata igrača A biti jednaka: ½u 2 + ½(1 – y) 2. Lako je provjeriti da li je ova količina za bilo koju vrijednost at između 0 i 1 ima vrijednost od najmanje ¼: ½u 2 + ½(1 – y) 2 ≥ ¼.

Dakle, igrač A, koristeći ovu mješovitu strategiju, može sebi garantirati pobjedu jednaku gornjoj cijeni igre; budući da cijena igre ne može biti veća od gornje cijene, onda je ova strategija S A optimalna: S A = S A *.

Ostaje pronaći optimalnu strategiju igrača B. Očigledno, ako je cijena igre ν jednaka gornjoj cijeni igre β, tada će optimalna strategija igrača B uvijek biti njegova čista minimaks strategija, koja mu garantuje gornja cijena igre. U ovom slučaju, takva strategija je 0 = ½. Zaista, sa ovom strategijom, bez obzira šta igrač A uradi, njegova isplata neće biti veća od ¼. Ovo slijedi iz očigledne nejednakosti (x – ½) 2 = x(x –1) + ¼ ≤ ¼

Primjer 2. Strana A (“mi”) puca na neprijateljski avion B. Da bi izbjegao vatru, neprijatelj može manevrirati s određenim preopterećenjem at, kojem on, po svom nahođenju, može dodijeliti vrijednosti iz at= 0 (linearno kretanje) do at = atmax(let duž kruga maksimalne zakrivljenosti). Pretpostavljamo atmax jedinica mjere, tj. stavimo atmax= 1. U borbi protiv neprijatelja možemo koristiti nišanske uređaje na osnovu jedne ili druge hipoteze o kretanju mete tokom leta projektila. Preopterećenje X u ovom hipotetičkom manevru može se pretpostaviti da je jednako bilo kojoj vrijednosti od 0 do 1. Naš zadatak je da pogodimo neprijatelja; Zadatak neprijatelja je da ostane neporažen. Vjerovatnoća poraza za podatke X I at je približno izraženo formulom: a(x, y) = , Gdje at- preopterećenje od strane neprijatelja; x - preopterećenje uzeto u obzir u nišanu. Potrebno je odrediti optimalne strategije obe strane.

Rješenje. Očigledno, rješenje igre se neće promijeniti ako postavimo p = 1. Funkcija isplate a(x, y) predstavljena površinom prikazanom na sl. 7.7.

Ovo je cilindrična površina, čiji su generatori paralelni sa simetralom koordinatnog ugla xOy, a presjek ravninom okomitom na generatrisu je kriva poput krive normalne raspodjele. Koristeći geometrijsku interpretaciju donje i gornje cijene igre koja je gore predložena, nalazimo β = 1 (slika 7.8) i (slika 7.9). Igra nema sedlo; rješenje se mora tražiti u oblasti mješovitih strategija. Zadatak je donekle sličan problemu u prethodnom primjeru. Zaista, pri malim vrijednostima k funkcija se ponaša otprilike kao funkcija –(x – y) 2, a rješenje igre će se dobiti ako u rješenju prethodnog primjera zamijenimo uloge igrača A i B; one. naša optimalna strategija će biti čista strategija x = 1/2, a optimalna strategija neprijatelja S B = će biti korištenje ekstremnih strategija y = 0 i y = 1 sa jednakim frekvencijama. To znači da moramo koristiti cilj u svim slučajevima projektovano za preopterećenje od x = 1/2, a neprijatelj u polovini svih slučajeva ne sme da koristi nikakav manevar, au polovini - maksimalno mogući manevar.

Rice. 7.8 Sl. 7.9.

Lako je dokazati da će ovo rješenje vrijediti za vrijednosti k ≤ 2. Zaista, prosječna isplata za strategiju protivnika S B = i za našu strategiju X izraženo funkcijom , koja za vrijednosti k ≤ 2 ima jedan maksimum pri x = 1/2, jednak nižoj cijeni igre α. Posljedično, korištenje strategije S B garantuje protivniku gubitak koji nije veći od α, iz čega je jasno da je α - niža cijena igre - cijena igre ν.

Za k > 2, funkcija a(x) ima dva maksimuma (slika 7.10), smještena simetrično u odnosu na x = 1/2 u tačkama x 0 i 1 – x 0, a vrijednost x 0 zavisi od k.

Očigledno, kada k= 2 x 0 = 1 – x 0 = ½; sa povećanjem k tačke x 0 i 1 – x 0 se odmiču, približavajući se ekstremne tačke(0 i 1). Stoga će rješenje igre zavisiti od k. Postavimo određenu vrijednost k, na primjer k = 3, i pronađemo rješenje za igru; Da bismo to učinili, odredimo apscisu x 0 maksimuma krive a(x). Izjednačavajući derivaciju funkcije a(x) sa nulom, pišemo jednačinu za određivanje x 0:

Ova jednadžba ima tri korijena: x = 1/2 (gdje je dostignut minimum) i x 0, 1 – x 0, gdje se dostižu maksimumi. Rješavajući jednačinu numerički, nalazimo približno x 0 ≈ 0,07; 1 – x 0 ≈ 0,93.

Dokažimo da će rješenje igre u ovom slučaju biti sljedeći par strategija:

Sa našom strategijom i strategijom neprijatelja at prosječan dobitak je

Nađimo minimum a 1 (y) na 0< у < 1. Функция a 1 (y) симметрична относительно y = 1/2 и может иметь только один или два максимума; ее минимум, во всяком случае, достигается либо в середине отрезка (0, 1), либо на его концах. Полагая у = 0 (или у = 1), найдем

Postavljanje y = 1/2, dobijamo

koji je veći od 1 (0); stoga, cijena igre nije manja od 1 (0):

Sada recimo da neprijatelj koristi strategiju S B *, a mi strategiju x. Tada će prosječan dobitak biti

Ali mi smo odabrali x 0 upravo tako da se pri x = x 0 postigne maksimum izraza (7.2); dakle,

one. protivnik koji koristi strategiju S B * može spriječiti gubitak veći od 0,530; dakle, ν = 0,530 je cijena igre, a strategije S A * i S B * pružaju rješenje. To znači da moramo koristiti nišane sa x = 0,07 i x = 0,93 sa istom frekvencijom, a neprijatelj ne smije manevrirati istom frekvencijom i manevrirati sa maksimalnim preopterećenjem.

Imajte na umu da je isplata ν = 0,530 primjetno veća od niže cijene igre , koju bismo mogli sami osigurati primjenom naše maksiminske strategije x 0 = 1/2.

Jedan od praktičnih načina za rješavanje beskonačnih igara je da ih svedete na približne konačne. U ovom slučaju, cijeli niz mogućih strategija za svakog igrača uvjetno se kombinira u jednu strategiju. Na ovaj način, naravno, možete dobiti samo približno rješenje igre, ali u većini slučajeva nije potrebno točno rješenje.

Međutim, mora se imati na umu da se prilikom primjene ove tehnike mogu pojaviti rješenja iz oblasti mješovitih strategija čak iu slučajevima kada je rješenje izvorne beskonačne igre moguće u čistim strategijama, tj. kada beskonačna igra ima tačku sedla. Ako se svođenjem beskonačne igre na konačnu dobije mešoviti rastvor, koji uključuje samo dvije susjedne „korisne“ strategije, onda ima smisla pokušati primijeniti srednju čistu strategiju originalne beskonačne igre.

U zaključku, napominjemo da beskonačne igre, za razliku od konačnih, možda nemaju rješenje. Navedimo primjer beskonačne igre koja nema rješenja. Svaki od dva igrača imenuje bilo koji cijeli broj. Imenovano veći broj prima 1 rublju od drugog. Ako oboje pozovu isti broj, igra se završava neriješeno. Igra očito ne može imati rješenje. Međutim, postoje klase beskonačnih igara za koje sigurno postoji rješenje.

Poziva se igračev izbor jedne ili druge akcije napredak. Postoje potezi lični(igrač svjesno donosi jednu ili drugu odluku) i nasumično(ishod igre ne zavisi od volje igrača). Poziva se skup pravila koja određuju koji potez igrač mora napraviti strategija. Postoje strategije cisto(neslučajne odluke igrača) i mješovito(strategija se može posmatrati kao slučajna varijabla).

Saddle point

IN teorija igara S. t. ( sedlasti element) je najveći element kolone matrična igra, koji je ujedno i najmanji element odgovarajućeg reda (in igra za dvije osobe sa nultom sumom). U ovom trenutku, dakle, maksimin jednog igrača je jednak minimaksu drugog; S. t. je poenta ravnoteža.

Minimax teorema

Poziva se strategija koja odgovara minimaksu minimax strategija.

Princip koji nalaže igračima da odaberu "najopreznije" maksiminske i minimaks strategije naziva se princip minimaksa. Ovaj princip proizilazi iz razumne pretpostavke da svaki igrač teži da postigne cilj suprotan cilju njegovog protivnika.

Igrač bira svoje postupke, pod pretpostavkom da će protivnik djelovati na nepovoljan način, tj. pokušaće da "naškodi".

Funkcija gubitka

Funkcija gubitka– funkcija koja u teoriji statistička rješenja karakteriše gubitke zbog pogrešnog donošenja odluka na osnovu posmatranih podataka. Ako se rješava problem procjene parametra signala u pozadini buke, tada je funkcija gubitka mjera neslaganja između prave vrijednosti procijenjenog parametra i procjene parametra

Optimalna mješovita strategija igrača- ovo je kompletan set primjene njegovih čistih strategija kada se igra ponavlja više puta pod istim uslovima sa datim vjerovatnoćama.

Mešovita strategija igrača je kompletan skup primene njegovih čistih strategija kada se igra ponavlja mnogo puta pod istim uslovima sa datim verovatnoćama.

1. Ako svi elementi reda nisu veći od odgovarajućih elemenata drugog reda, tada se originalni red može izbrisati iz matrice plaćanja. Isto za kolone.

2. Cijena igre je jedinstvena.

dokument: Recimo da postoje 2 cijene igara v i , koji se postižu na paru i respektivno, tada

3. Ako se svim elementima matrice isplate doda isti broj, onda se optimalne mješovite strategije neće promijeniti, ali će cijena igre porasti za ovaj broj.

dokument:
, Gdje

4. Ako se svi elementi matrice plaćanja pomnože sa istim brojem koji nije jednak nuli, cijena igre će se pomnožiti ovim brojem, ali se optimalne strategije neće promijeniti.

Matrična igra za dva igrača sa nultom sumom može se smatrati sljedećom apstraktnom igrom za dva igrača.

Prvi igrač ima m strategije i = 1,2,...,m, drugi ima n strategije j= 1,2,...,n. Svaki par strategija ( i, j) odgovarajući broj A ij , izražavajući dobitak igrača 1 na račun igrača 2 ako prvi igrač prihvati njegov i- yu strategiju, a 2 – svoju j th strategija.

Svaki igrač čini jedan potez: igrač 1 bira svoj i ta strategija ( i= ), 2– tvoj j ta strategija ( j=
), nakon čega igrač 1 prima dobitak A ij o trošku igrača 2 (ako A ij < 0, to znači da igrač 1 plaća drugi iznos | A ij|). Ovdje se igra završava.

Strategija svakog igrača i=
; j =
često se naziva čistom strategijom.

Ako uzmemo u obzir matricu

A=

zatim provođenje svake igre matrične igre sa matricom A svodi se na izbor igrača 1 i red i igrač 2 j kolona i igrač 1 (na trošak igrača 2) prima dobitak a ij .

Glavna stvar u proučavanju igara je koncept optimalnih strategija igrača. Ovaj koncept intuitivno ima sljedeće značenje: igračeva strategija je optimalna ako mu korištenje ove strategije osigurava najveći zajamčeni dobitak za sve moguće strategije drugog igrača. Na osnovu ovih pozicija, igrač 1 ispituje matricu isplate A kako slijedi: za svaku vrijednost i (i =
) minimalna dobitna vrijednost se određuje ovisno o strategijama koje koristi igrač 2

A ij (i=
)

one. određuju se minimalni dobici za igrača 1, pod uslovom da on prihvati svoj ičistu strategiju, onda se iz ovih minimalnih isplata takva strategija nalazi i = i O, pri čemu će ovaj minimalni dobitak biti maksimalan, tj. nalazi

A ij =
=(1)

Definicija . Broj , definisan formulom (1) se zove niža neto cijena igrice i pokazuje koji minimalni dobitak igrač 1 može garantirati za sebe primjenom svojih čistih strategija za sve moguće akcije igrača 2.

Igrač 2, svojim optimalnim ponašanjem, treba da teži, ako je moguće, kroz svoje strategije, da minimizira isplatu igrača 1. Dakle, za igrača 2 nalazimo

A ij

one. određuje se maksimalni dobitak igrača 1, pod uslovom da igrač 2 koristi svoj j th čista strategija, tada igrač 2 traži svoju j = j 1 strategija u kojoj će igrač 1 dobiti minimalnu pobjedu, tj. nalazi

a ij =
=(2).

Definicija . Broj , određeno formulom (2), se zove neto najviša cijena igrice i pokazuje koji maksimalni dobitak igrač 1 može garantirati za sebe zahvaljujući svojim strategijama.

Drugim riječima, koristeći svoje čiste strategije, igrač 1 može osigurati pobjedu ne manje od , a igrač 2, koristeći svoje čiste strategije, može spriječiti igrača 1 da osvoji više od .

Definicija . Ako u igri sa matricom A =onda kažu da ova igra ima sedlo tačka u čistim strategijama i neto cijena igrice

 = =.

Saddle point je par čistih strategija (i O , j O ) igrači 1 i 2, kod kojih se postiže jednakost =. Ovaj koncept ima sljedeće značenje: ako se jedan od igrača pridržava strategije koja odgovara tački sedla, onda drugi igrač ne može učiniti bolje nego da se pridržava strategije koja odgovara tački sedla. Matematički, ovo se može napisati na drugi način:

Gdje i, j– sve čiste strategije igrača 1 i 2, respektivno; (i O , j O ) – strategije koje formiraju sedlo.

Dakle, na osnovu (3), element sedla
je minimalna u i o -tom redu i maksimalna u j o -toj koloni u matrici A. Pronalaženje sedla matrice A odvija se na sljedeći način: u matrici A sekvencijalno u svakoj linija pronađite minimalni element i provjerite da li je ovaj element maksimalni u svom kolona. Ako je odgovor da, onda je to element sedla, a par strategija koje mu odgovaraju formiraju sedlo. Par čistih strategija (i O , j O ) igrači 1 i 2, formirajući sedlo i element sedla
, zvao rešenje igre . Gde i O I j O su pozvani optimalno čišćenje strategije igrači 1 i 2.

Primjer 1

Tačka sedla je par ( i O = 3;j O= 1), pri čemu je = == 2.

Imajte na umu da iako je isplata u situaciji (3;3) takođe jednaka 2 = =, nije sedlo, jer ovaj dobitak nije maksimalni među dobicima treće kolone.

Primjer 2

Iz analize matrice isplate jasno je da
, tj. ova matrica nema tačku sedla. Ako igrač 1 odabere svoju čistu maksiminsku strategiju i = 2, zatim igrač 2, birajući svoj minimaks j= 2, izgubiće samo 20. U ovom slučaju je isplativo da igrač 1 izabere strategiju i = 1, tj. odstupiti od svoje čiste maksiminske strategije i osvojiti 30. Tada će igraču 2 biti isplativo da odabere strategiju j = 1, tj. odstupiti od svoje čiste minimaks strategije i izgubiti 10. Zauzvrat, igrač 1 mora izabrati svoju 2. strategiju da bi dobio 40, a igrač 2 će odgovoriti odabirom svoje 2. strategije itd.

Pogledajmo primjer. Neka je data matrica igre (4):

Moramo pronaći donju cijenu igre α, gornju cijenu igre β i minimaks strategije i provjeriti jesu li stabilne. Rješenje. Analizom dodatne kolone i reda dobijamo: α = 5, β = 5. Maksimin je jednak minimumu! Ovo je poseban slučaj. Šta iz ovoga slijedi? Uzmimo nekoliko minimaks strategija: K 2 i C 3. Ako se oboje drže ove strategije, onda će isplata biti 5. Sada, recimo da smo naučili o ponašanju neprijatelja. Šta da radimo? Ništa! I dalje ćemo se pridržavati strategije K2, jer je svako odstupanje od nje za nas neisplativo. Bilo da znamo ili ne znamo za ponašanje neprijatelja, i dalje ćemo se držati K 2 strategije! Isto važi i za "plave" - ​​nema smisla da menjaju svoju C 3 strategiju. U ovom primeru, par strategija K 2 i C 3 je stabilan, odnosno predstavlja ravnotežni položaj i daje rešenje za igru. Zašto se to dogodilo? Zato što postoji poseban element 5 u matrici; minimalna je u svom redu i istovremeno maksimalna u svom stupcu. Takav element se zove sedlo. Ako matrica ima sedlo (to jest, donja cijena igre je jednaka gornjoj), tada igra ima rješenje u čistim strategijama: ovo je par strategija koje se sijeku u tački sedla. Sama tačka sedla daje cenu igre - u našem primeru je jednaka 5. Klasa igara koje imaju sedlo je od velikog značaja u teoriji igara. Konkretno, dokazano je da ako, prema pravilima igre, svaki igrač zna rezultat svih prethodnih poteza, kako svojih tako i protivničkih (tzv. igra sa potpunim informacijama), tada igra ima sedlo i stoga ima rješenje u čistim strategijama. Primjeri igara sa potpunim informacijama su: šah, dame, tik-tak-toe, itd. Navedimo primjer igre sa potpunim informacijama, čije je rješenje lako pronaći. Dva igrača - K i C - naizmjenično stavljaju identične novčiće na okrugli sto. Položaj svakog novčića bira se proizvoljno, sve dok se ne preklapa s ostalima. Pobjeđuje posljednji igrač koji stavi novčić (kada nema mjesta za druge). Vrijedi malo razmisliti kako bismo bili sigurni da je ishod ove igre uvijek unaprijed zaključen i da postoji dobro definirana strategija koja garantuje pobjedu za igrača koji prvi ubaci novčić (neka bude K). Naime, K mora staviti prvi novčić u centar stola, a zatim na svaki potez C mora odgovoriti potezom tačno simetričnim u odnosu na centar stola! Jadni S može da se ponaša kako hoće, ali mu ipak nema spasa... Očigledno, takva igra ima smisla samo za one koji ne znaju rešenje. Zanimljivo je da je s takvima potpuno ista situacija popularna igra kao šah! Ova igra ima smisla samo dok se ne pronađe rješenje. Teorijski je dokazano da rješenje postoji i da je ishod šahovske partije u suštini unaprijed određen: ako svaka strana koristi svoju optimalnu strategiju, onda će partija ili uvijek završiti pobjedom bijelih, ili uvijek pobjedom crnih, ili uvek nerešeno! Ali šta tačno? To još ne znamo, jer je broj mogućih strategija prevelik da bismo mogli konstruisati matricu šahovske partije i u njoj pronaći sedlo... Vjerovatno ljubitelje šaha zanima šahovska partija nije uskoro riješen. Napominjemo u zaključku da sedla u matrici može biti ne jedan, već nekoliko; onda postoji onoliko rješenja za igru ​​u čistim strategijama koliko ima sedla. Svaki od njih daje dobitak jednak cijeni igre.

"Čiste" strategije

Već smo upoznati sa dovratnicima. Međutim, šta se događa ako se uklone dovratnici iz lanca bilo koje strategije? Dobićemo „čistu strategiju“. Čiste strategije su one u čijem lancu delovanja, od samog korena do efektivnog dela, nema neefikasnih supstrategija (dovratnika), a to se često može dokazati samo prisustvom svih karika u svesti.

Naravno, sa stanovišta svih mogućih ishoda korišćenja strategije, teško nam je govoriti o najefikasnijoj, jer možda jednostavno nemamo određeno iskustvo, pa samim tim i određene međustrategije, ali je upravo od stanovište našeg iskustva da strategija treba da bude što je moguće efikasnija.

Koncept čistih strategija je također jedan od ključnih u ovim materijalima, pa ću dati primjer:

Večernje. Vi ste u svom rodnom kraju i žurite kući. Mlijeko bježi. Proleteći pored „mnogo sumnjivih tipova“ čujete da vam se obraćaju: „Hej, ti, [izrezano cenzurom]. Ne hodajte ovamo, pašće vam snijeg na glavu!”

Šta ćeš uraditi? Može biti mnogo opcija. Neko će otići da sredi stvari, neko će se uplašiti i ubrzati korak, neko će nešto viknuti. Međutim, razmislimo o tome koja je čista strategija ponašanja u ovom slučaju?

Osoba koju ne poznajete viče vam nešto na ulici. Imate svoje poslove, kojima se zapravo bavite. Sudeći po tekstu, pozitivne koristi za vas od komunikacije s ovom osobom su malo vjerovatne. Logičan zaključak: mirno nastavite sa svojim poslom. Skrećem pažnju šta je tačno „mirno“, bez senke negativne emocije, ali sa zdravom ravnodušnošću prema onome što se dešava. Koliko bi ljudi to uradilo? Pretpostavljam da je velika manjina. Zašto?

Jer većina ljudi ima čitav sloj podsvjesnih strategija vezanih u nižim slojevima za samoodržanje, a posebno to mogu biti: „Uvijek odgovorite grubošću“, „Ako neko kaže ružne stvari, onda morate bježati“, „Ako neko ako je bezobrazan, treba ga udariti šakom u lice”, “Ako je neko bezobrazan, onda postoji opasnost” i slično u različitim varijantama. Naravno, neće svi poduzeti neku aktivnu akciju, ali će to emocionalno utjecati na gotovo sve. A ovo je dovratak.

Čiste strategije su uvijek emocionalno neutralne ili pozitivne, i to je ugrađeno u vaš mozak, samo to morate koristiti.

Možete pročitati malo o čistim strategijama u bilješkama „Zašto čiste strategije?“ i "House, Hopkins, itd."

Iz knjige Strategije genija. Albert Einstein od Diltsa Roberta

Strategije 1. Definicija pojma „strategija“: a) Dolazi iz grčka riječ“strategos”, što znači: “vojskovođa”, “nauka, umjetnost ratovanja”, “umjetnost vođenja društvene, političke borbe”. b) Detaljan plan za postizanje cilja ili prednosti

Iz knjige Strategije genija (Aristotel Sherlock Holmes Walt Disney Wolfgang Amadeus Mozart) od Diltsa Roberta

Iz knjige Možeš li dobro učiti?! Korisna knjiga za neoprezne studente autor Karpov Aleksej

STRATEGIJE Vaše studije će se odvijati na potpuno drugačijem nivou kvaliteta ako razmislite i odaberete akcionu strategiju.Strategija je sveobuhvatni plan. Ovo je generalna linija koja uzima u obzir stvarne uslove. To su ciljevi, rokovi, vodeći računa o nepredvidivosti i različitosti... To je sam osjećaj pulsa

Iz knjige Strategija uma i uspjeha autor Antipov Anatolij

Iz knjige Emocionalna inteligencija od Daniela Golemana

IQ i emocionalna inteligencija: čisti tipovi IQ i emocionalna inteligencija nisu u suprotnosti, već su odvojene kompetencije. Svi mi kombinujemo inteligenciju sa akutnim iskustvom; ljudi sa visokim

Iz knjige 12 kršćanskih vjerovanja koja vas mogu izluditi by Townsend John

Ispravne namjere ili čiste misli Ispravna namjera je odluka da se učini ispravna stvar. Odabiremo dobru akciju koja se sviđa Bogu, obično bez razmišljanja o tome da li to zaista želimo učiniti. Samo to radimo - to je sve. Mnogi evanđeoski propovednici

Iz knjige Ulazak u život: zbirka autor autor nepoznat

Rudolf Ivanovič ABEL: „ZAPAMTITE KAKO JE DŽERŽINSKI REKAO: „ČISTE RUKE, HLADNA GLAVA I TOPLO SRCE...“ Rudolf Ivanovič Abel proveo je više od trideset godina radeći u sovjetskoj obaveštajnoj službi. Odlikovan je Ordenom Lenjina, dva ordena Crvene zastave, Ordenom rada

Iz knjige Homo Sapiens 2.0 [Homo Sapiens 2.0 http://hs2.me] od Sapiens Homo

Strategije

Iz knjige Homo Sapiens 2.0 od Sapiens 2.0 Homo

„Čiste“ strategije Već smo upoznati sa dovratnicima. Međutim, šta se događa ako se uklone dovratnici iz lanca bilo koje strategije? Dobićemo „čistu strategiju“. Čiste strategije su one u čijem lancu delovanja, počevši od samog korena do efektivnog dela, nema

Iz knjige Započnite. Udarite strah u lice, prestanite biti „normalni“ i uradite nešto vrijedno truda. od Acuff John

Iz knjige Čovjek kao životinja autor Nikonov Aleksandar Petrovič

Strategije Opšti koncept strategija U principu, svako u ovoj ili onoj meri razume šta je strategija. Posjedujući određeni skup znanja stečenih kao rezultat sticanja i obrade iskustva, gradimo određene modele ponašanja.Strategija je model za postizanje cilja.

Iz knjige Uključite svoju radnu memoriju do njenog punog potencijala od Alloway Tracy

Zašto čiste strategije? Lavovski dio materijala u ovom projektu stalno ističe da je potrebno koristiti čiste strategije za prepisivanje i na njima obavezno tražiti dovratak. Ovaj trenutak nije očigledno na prvi pogled i

Iz knjige Introvert u ekstrovertnom svijetu autor Romantseva Elizaveta

Iz knjige autora

Iz knjige autora

Strategije Kompjuterske strategije zahtevaju koncentraciju od igrača, sposobnost planiranja svojih akcija i rešavanja raznih problema. Nedavna istraživanja sugeriraju da strategije mogu pomoći u poboljšanju kognitivnih vještina igrača svih uzrasta. Prema

Iz knjige autora

Čisti tipovi Postoji takav koncept - "čisti psihološki tip". Zapravo, koncept postoji, ali praktično nema objekata, odnosno ljudi koji se idealno uklapaju u ovaj koncept. Ne postoje čisti introverti i čisti ekstroverti. Štaviše, složili smo se

Preporučujemo čitanje

• Ramon Mercader: ubica ili heroj?
• Istinita priča o Valji Kotik (5 fotografija)
• odvajanje Rusije od SSSR-a
• Kako položiti ispit u tehničkoj školi i na fakultetu: preporuke stručnjaka