Ako postoji više sukobljenih strana (osoba), od kojih svaka donosi određenu odluku utvrđenu datim skupom pravila, a svaka od osoba zna konačno stanje konfliktne situacije sa unaprijed određenim isplatama za svaku od strana, tada se igra kaže se da će se održati.
Zadatak teorije igara je odabrati liniju ponašanja za datog igrača, odstupanje od koje može samo umanjiti njegov dobitak.
Neke definicije igre
Kvantitativna procjena rezultata igre naziva se plaćanje.
Parovi (dvije osobe) naziva se igra sa nultom sumom ako je zbir uplata nula, tj. ako je gubitak jednog igrača jednak dobitku drugog.
Nedvosmislen opis igračevog izbora u svakoj od mogućih situacija u kojoj mora napraviti lični potez naziva se strategija igrača .
Igračeva strategija se naziva optimalnom ako, kada se igra ponavlja mnogo puta, pruža igraču maksimum mogućih prosječne dobitke(ili, što je isto, minimalni mogući prosječni dobitak).
Igra definisana matricom A vlasništvo m linije i n kolone naziva se igra konačnih parova dimenzija m* n;
Gdje i=
- strategija prvog igrača sa mstrategijom;
j=
- strategija drugog igrača koji ima n strategija;
ij– dobitak prvog igrača i-strategija kada se koristi od strane drugog j strategije (ili, što je isto, gubitak druge u njenom j-ta strategija, kada se koristi prva i th);
A = ij– matrica plaćanja igre.
1.1 Igranje čistim strategijama
Niska cijena igre (za prvog igrača)
= max (min ij). (1.2)
i j
Najbolja cijena igre (za drugog igrača):
= min
(max
ij)
. (1.3)
J i
Ako = , igra se naziva sedlo (1.4) ili igra sa čistim strategijama. Gde V = = naziva se vrijednom igrom ( V- cijena igre).
Primjer. Zadata je matrica plaćanja igre 2 osobe A. Odredite optimalne strategije za svakog igrača i cijenu igre:
(1.4)
max 10 9 12 6
i
min 6
j
- strategija prvog igrača (red).
Strategija drugog igrača (kolone).
- cijena igre.
Dakle, igra ima sedlo. Strategija j = 4 – optimalna strategija za drugog igrača i=2 - za prvi. Imamo igru sa čistim strategijama.
1.2 Igre s mješovitim strategijama
Ako matrica plaćanja nema sedlo, tj. 
, i niko u igri ne može izabrati jedan plan kao svoju optimalnu strategiju, igrači prelaze na „mešovite strategije“. Štaviše, svaki igrač koristi svaku od svojih strategija nekoliko puta tokom igre.
Vektor, čija svaka komponenta pokazuje relativnu učestalost igračeve upotrebe odgovarajuće čiste strategije, naziva se mješovita strategija ovog igrača.
X= (X 1 …X i …X m) – mješovita strategija prvog igrača.
U= (at 1 ...y j ...y n) – mješovita strategija drugog igrača.
xi , y j– relativne frekvencije (vjerovatnosti) igrača koji koriste svoje strategije.
Uslovi za korištenje mješovitih strategija
.
(1.5)
Ako X* = (X 1 * ….X ja*… X m*) – optimalna strategija koju odabere prvi igrač; Y* = (at 1 * …at j*... at n*) je optimalna strategija koju je izabrao drugi igrač, tada je broj trošak igre.
(1.6)
U redu za broj V bila je cijena igre, i X* I at* - optimalne strategije, neophodno je i dovoljno da se zadovolje nejednakosti
(1.7)
Ako jedan od igrača koristi optimalnu mješovitu strategiju, onda je njegova isplata jednaka cijeni igre V bez obzira na učestalost kojom će drugi igrač koristiti strategije uključene u optimalnu, uključujući i čiste strategije.
Svođenje problema teorije igara na probleme linearnog programiranja.
Primjer. Pronađite rješenje za igru definiranu matricom isplate A.
A = 
(1.8)
y 1 y 2 y 3
Rješenje:
Hajde da napravimo dvostruki par problema linearnog programiranja.
Za prvog igrača
(1.9)
at 1 +at 2 +at 3 = 1 (1.10)
Oslobodite se varijable V(cijena igre), podijelite lijevu i desnu stranu izraza (1.9), (1.10) na V. Prihvativši at j /V za novu varijablu z i, dobijamo novi sistem ograničenja (1.11) i ciljna funkcija (1.12)
(1.11)
.
(1.12)
Slično, dobijamo model igre za drugog igrača:
(1.13)
X 1 +X 2 +X 3 = 1 . (1.14)
Svođenje modela (1.13), (1.14) na oblik bez varijable V, dobijamo
(1.15)
,
(1.16)
Gdje 
.
Ako trebamo odrediti strategiju ponašanja prvog igrača, tj. relativna učestalost upotrebe njegovih strategija ( X 1 ….X i …X m), koristićemo model drugog igrača, jer ove varijable su u njegovom modelu isplate (1.13), (1.14).
Svedujmo (1.15), (1.16) na kanonski oblik
(1.17)
zadatak:
Matrična igra je data sljedećom matricom isplate:
| Strategije "B" | ||||||||
| Strategije "A" | B 1 | B 2 | ||||||
| A 1 | 3 | 5 | ||||||
| A 2 | 6 |
|
||||||
Pronađite rješenje matrične igre, i to:
- pronađite najvišu cijenu igre;
- niža cijena igre;
- neto cijena igre;
- ukazati na optimalne strategije igrača;
- donesi grafičko rješenje(geometrijska interpretacija), ako je potrebno.
Korak 1
Odredimo nižu cijenu igre - α
Najniža cijena igreα je maksimalna pobeda koju sebi možemo garantovati u igri protiv razumnog protivnika ako koristimo jednu i jedinu strategiju tokom čitave igre (ova strategija se zove “čista”).Pronađimo u svakom redu matrice plaćanja minimum element i upišite ga u dodatnu kolonu (Odabrano žuta vidi tabelu 1).
Onda ćemo naći maksimum element dodatne kolone (označen zvjezdicom), to će biti niža cijena igre.
Tabela 1
| Strategije "B" | |||||||||||||||
| Strategije "A" | B 1 | B 2 | Red Minima | ||||||||||||
| A 1 | 3 | 5 | 3 * | ||||||||||||
| A 2 | 6 |
|
|
||||||||||||
U našem slučaju, niža cijena igre je: α = 3, a kako bismo garantirali pobjedu ne lošiju od 3 moramo se držati strategije A 1
Korak:2
Odredimo gornju cijenu igre - β
Top cijena igreβ je minimalni gubitak koji igrač B može sebi garantovati u igri protiv razumnog protivnika ako koristi jednu i samo jednu strategiju tokom igre.Pronađimo u svakoj koloni matrice plaćanja maksimum element i upišite ga u dodatni red ispod (označeno žutom bojom, vidi tabelu 2).
Onda ćemo naći minimum element dodatne linije (označen plusom), to će biti gornja cijena igre.
tabela 2
| Strategije "B" | ||||||||||||
| Strategije "A" | B 1 | B 2 | Red Minima | |||||||||
| A 1 | 3 | 5 | 3 * | |||||||||
| A 2 | 6 |
| U našem slučaju, gornja cijena igre je: β = 5, a da bi se garantovao gubitak ne gori od 5, protivnik (igrač “B”) mora se pridržavati strategije B 2 Korak:3 Mješovita strategija, to su čiste strategije koje se nasumično izmjenjuju, sa određenim vjerovatnoćama (frekvencijama). Mi ćemo označiti mješovitu strategiju igrača “A”
|
|||||||||
gdje su B 1, B 2 strategije igrača “B”, a q 1, q 2 su vjerovatnoće sa kojima se ove strategije primjenjuju, a q 1 + q 2 = 1.
Optimalna mješovita strategija za igrača “A” je ona koja mu obezbjeđuje maksimalnu isplatu. Shodno tome, za „B” postoji minimalni gubitak. Ove strategije su određene S A* i S B* respektivno. Par optimalnih strategija čini rješenje za igru.
IN opšti slučaj Igračeva optimalna strategija možda ne uključuje sve početne strategije, već samo neke od njih. Takve strategije se nazivaju aktivne strategije.
Korak:4
gdje: str 1 , str 2 - vjerovatnoće (učestalosti) sa kojima se primjenjuju strategije A 1 i A 2, respektivno
Iz teorije igara je poznato da ako igrač "A" koristi svoju optimalnu strategiju, a igrač "B" ostane u okviru svojih aktivnih strategija, tada prosječna isplata ostaje nepromijenjena i jednaka je cijeni igre v bez obzira na to kako igrač "B" koristi svoje aktivne strategije. A u našem slučaju su obje strategije aktivne, inače bi igra imala rješenje u čistim strategijama. Stoga, ako pretpostavimo da će igrač “B” koristiti čistu strategiju B 1, onda je prosječna isplata v bice:
k 11 p 1 + k 21 p 2 = v (1)
gdje: k ij - elementi matrice plaćanja.
S druge strane, ako pretpostavimo da će igrač “B” koristiti čistu strategiju B 2, tada će prosječna isplata biti:
k 12 p 1 + k 22 p 2 = v (2)
Izjednačavanjem leve strane jednadžbi (1) i (2) dobijamo:
k 11 p 1 + k 21 p 2 = k 12 p 1 + k 22 p 2
I uzimajući u obzir činjenicu da str 1 + str 2 = 1 imamo:
k 11 p 1 + k 21 (1 - p 1 ) = k 12 p 1 + k 22 (1 - p 1 )
Gdje je lako pronaći optimalnu frekvenciju strategije A 1:
| str 1 = |
| (3) |
U ovom zadatku:
| str 1 = |
| = |
|
Vjerovatnoća R 2 naći oduzimanjem R 1 iz jedinice:
| str 2 = 1 - str 1 = | 1 | - |
| = | + | 6 | · |
gdje: q 1 , q 2 - vjerovatnoće (učestalosti) sa kojima se primjenjuju strategije B 1 i B 2, respektivno
Iz teorije igara je poznato da ako igrač "B" koristi svoju optimalnu strategiju, a igrač "A" ostane u okviru svojih aktivnih strategija, tada prosječna isplata ostaje nepromijenjena i jednaka je cijeni igre v bez obzira na to kako igrač A koristi svoje aktivne strategije. Stoga, ako pretpostavimo da će igrač “A” koristiti čistu strategiju A 1, onda je prosječna isplata v bice:
k 11 q 1 + k 12 q 2 = v (4)
Od cijene igre v to već znamo i razmatramo q 1 + q 2 = 1 , tada se optimalna frekvencija strategije B 1 može naći kao:
| q 1 = |
| (5) |
U ovom zadatku:
| q 1 = |
| = |
|
Vjerovatnoća q 2 naći oduzimanjem q 1 iz jedinice:
| q 2 = 1 - q 1 = | 1 | - |
| = |
|
odgovor:
| Najniža cijena igre: | α = | 3 | |||
| Najbolja cijena igre: | β = | 5 | |||
| Cijena igre: | v = |
|
| Optimalna strategija igrača A: |
|
|||||||||||||||
| Optimalna strategija za igrača "B": |
|
Geometrijska interpretacija (grafičko rješenje):
Hajde da damo geometrijsku interpretaciju razmatrane igre. Uzmite presjek ose apscise jedinične dužine i povucite okomite prave linije kroz njene krajeve a 1 I a 2 što odgovara našim strategijama A 1 i A 2 . Pretpostavimo sada da će igrač "B" koristiti strategiju B 1 in čista forma. Zatim, ako mi (igrač “A”) koristimo čistu strategiju A 1, onda će naša isplata biti 3. Označimo odgovarajuću tačku na osi a 1 .Ako koristimo čistu strategiju A 2, onda će naša isplata biti 6. Označimo odgovarajuću tačku na osi a 2
(vidi sliku 1). Očigledno, ako primenimo, mešajući strategije A 1 i A 2 u različitim proporcijama, naši dobici će se menjati duž prave linije koja prolazi kroz tačke sa koordinatama (0, 3) i (1, 6), nazovimo to linijom strategije B 1 (na sl. 1 prikazano crvenom bojom). Apscisa bilo koje tačke na datoj pravoj jednaka je vjerovatnoći str 2 (frekvencija) sa kojom primenjujemo strategiju A 2, a ordinata - rezultujući dobitak k (vidi sliku 1).
Slika 1.
Grafikon isplate k
od frekvencije p 2
, kada neprijatelj koristi strategiju B 1.
Pretpostavimo sada da će igrač “B” koristiti strategiju B 2 u njenom čistom obliku. Zatim, ako mi (igrač “A”) koristimo čistu strategiju A 1, onda će naša isplata biti 5. Ako koristimo čistu strategiju A 2, onda će naša isplata biti 3/2 (vidi sliku 2). Slično, ako pomiješamo strategije A 1 i A 2 u različitim omjerima, naši dobici će se mijenjati duž prave linije koja prolazi kroz tačke sa koordinatama (0, 5) i (1, 3/2), nazovimo to linijom strategije B 2. Kao iu prethodnom slučaju, apscisa bilo koje tačke na ovoj pravoj jednaka je vjerovatnoći s kojom primjenjujemo strategiju A 2, a ordinata je rezultirajući dobitak, ali samo za strategiju B 2 (vidi sliku 2).
Slika 2.
v
i optimalnu frekvenciju p 2
za igrača "A".
U pravoj igri, kada razuman igrač “B” koristi sve svoje strategije, naši dobici će se mijenjati duž izlomljene linije prikazane na slici 2 crvenom bojom. Ova linija definira tzv donja granica dobitaka. Očigledno najviše high point ova isprekidana linija odgovara našoj optimalnoj strategiji. IN u ovom slučaju, ovo je tačka preseka linija strategija B 1 i B 2. Imajte na umu da ako odaberete frekvenciju str 2 jednaka njegovoj apscisi, tada će naš dobitak ostati nepromijenjen i jednak v za bilo koju strategiju igrača „B“, pored toga, to će biti maksimum koji možemo sebi garantovati. Učestalost (vjerovatnoća) str 2 , u ovom slučaju, je odgovarajuća frekvencija naše optimalne mješovite strategije. Usput, sa slike 2 možete vidjeti frekvenciju str 1 , naša optimalna mješovita strategija, je dužina segmenta [ str 2 ; 1] na x-osi. (To je zato str 1 + str 2 = 1 )
Koristeći potpuno slično razmišljanje, možemo pronaći frekvencije optimalne strategije za igrača „B“, što je ilustrovano na slici 3.
Slika 3.
Grafičko određivanje cijene igre v
i optimalnu frekvenciju q 2
za igrača "IN".
Samo za njega treba tzv gornja granica gubljenje(crvena izlomljena linija) i potražite najnižu tačku na njoj, jer za igrača "B" cilj je minimizirati gubitke. Ista frekvencijska vrijednost q 1 , ovo je dužina segmenta [ q 2 ; 1] na x-osi.
Sadržaj 1 Opće informacije 2 1.1 Igre. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Pokreti. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Strategije. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Matrična igra. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Tačka staze. Čiste strategije 7 2.1 Primjeri. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Primjer 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Primjer 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Mješovite strategije 9 3.1 Igra 2×2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.1 Primjeri. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Primjer 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Primjer 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1.2 Geometrijska interpretacija. . . . . . . . . . . . . . . . . . . . 12 3.2 Igre 2×n i m×2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Primjer 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1 1. Opći podaci iz teorije igara 1.1. Igre Teorija igara je matematička teorija konfliktnih situacija, tj. situacije u kojima se sukobljavaju interesi dvije ili više strana koje teže različitim ciljevima. Igra je konfliktna situacija regulisana određenim pravilima, koja moraju naznačiti: moguće opcije za radnje učesnika; kvantitativni rezultat igre ili isplate (pobeda, poraz) do kojeg vodi dati set poteza; količinu informacija svake strane o ponašanju druge. Igra parova je igra u kojoj učestvuju samo dvije strane (dva igrača). Uparena igra sa nultom sumom je uparena igra u kojoj je zbir uplata nula, tj. Gubitak jednog igrača jednak je dobitku drugog. U zavisnosti od stava svakog igrača prema vrijednosti funkcije isplate, uparene igre se dijele: Parna igra sa nultom sumom (antagonistička) - uparena igra u kojoj je iznos uplata jednak nuli, tj. Gubitak jednog igrača jednak je dobitku drugog. Neantagonistička igra je igra u paru u kojoj igrači teže različitim, ali ne direktno suprotnim ciljevima. 2 1.2. Pokreti Pokret - izbor jedne od radnji predviđenih pravilima igre; implementacija ovog izbora. Potezi su dvije vrste: Lični potez - + svjestan izbor jedne od radnji predviđenih pravilima igre + implementacija ovog izbora Slučajni potez - Nasumični potez je izbor iz niza mogućnosti, koji se ne vrši odlukom igrača, već nekim mehanizmom nasumične selekcije. U nastavku razmatramo uparene igre sa nultom sumom koje sadrže samo lične poteze. Svaka strana nema informacije o ponašanju druge. 3 1.3. Strategije Igračeva strategija je skup pravila koja određuju izbor akcija za svaki lični potez ovog igrača, u zavisnosti od situacije koja se pojavi tokom igre. U zavisnosti od broja mogućih strategija, igre se dijele na konačne i beskonačne. Beskonačna igra je igra u kojoj barem jedan od igrača ima beskonačan broj strategije. Konačna igra je igra u kojoj svaki igrač ima samo konačan broj strategija. Broj uzastopnih poteza za bilo kog igrača određuje podjelu igara na pojedinačne i višepokretne ili pozicijske. + U igri s jednim okretom, svaki igrač donosi samo jedan izbor od mogućih opcija, a zatim određuje ishod igre. + Igra sa više poteza ili poziciona igra se razvija tokom vremena, predstavljajući niz uzastopnih faza, od kojih se svaka dešava nakon poteza jednog od igrača i odgovarajuće promjene situacije. U igri sa jednim okretom, svaki igrač ima samo jedan izbor moguće opcije a zatim određuje ishod utakmice. Optimalna strategija igrača je strategija koja, kada se igra mnogo puta ponovi, daje ovom igraču maksimalnu moguću prosječnu pobjedu (ili, što je isto, minimalni mogući prosječni gubitak). U teoriji igara, sve preporuke se daju na osnovu pretpostavke razumnog ponašanja igrača. Pogreške i greške igrača, neizbježne u svakoj konfliktnoj situaciji, kao i elementi uzbuđenja i rizika ne uzimaju se u obzir u teoriji igara. 4 1.4. Matrična igra Matrična igra je igra s konačnim nultim sumom u jednom potezu. Matrična igra je teorijski model konfliktne situacije u kojoj protivnici, da bi postigli dijametralno suprotne ciljeve, čine jedan izbor (pokret) iz konačnog broj mogući načini U skladu sa odabranim metodama djelovanja (strategijama) utvrđuje se postignuti rezultat. Pogledajmo primjer. Neka postoje dva igrača A i B, od kojih jedan može birati i-ta strategija od m svojih mogućih strategija A1, A2, ...Am, a drugi bira j-tu strategiju od svojih mogućih strategija B1, B2, ...Bm. Kao rezultat toga, prvi igrač osvaja vrijednost aij, a drugi igrač gubi ovu vrijednost. Od brojeva aij kreiramo matricu a11 a11 · · · a1n a21 a22 · · · a2n A = (aij) = .. .. .. . . . . am1 am2 · · · amn Matrica A = (aij), i = 1, m, j = 1, n se naziva matrica isplate ili matrica igre m × n. U ovoj matrici, redovi su uvijek za strategije pobjedničkog (maksimizirajućeg) igrača A, odnosno igrača koji nastoji da maksimizira svoj dobitak. Kolone se dodeljuju za strategije igrača koji gubi B, odnosno igrača koji teži da minimizira kriterijum efikasnosti. Normalizacija igre je proces svođenja pozicijske igre na matričnu igru. Igra u normalnom obliku je poziciona igra svedena na matričnu igru. Podsjetimo da je pozicijska igra s više poteza teoretski model igre konfliktna situacija u kojoj protivnici uzastopno čine jedan izbor (pokret) iz konačnog broja mogućih pravaca djelovanja u svakoj fazi razvoja ove situacije. Rješenje igre je pronalaženje optimalnih strategija oba igrača i određivanje cijene igre.Cijena igre je očekivani dobitak (gubitak) igrača. Rješenje igre se može naći ili u čistim strategijama - kada igrač mora slijediti jednu strategiju, ili u mješovitim, kada igrač mora koristiti dvije ili više čistih strategija sa određenim vjerovatnoćama. Potonji se u ovom slučaju nazivaju aktivnim. 5 Mješovita strategija jednog igrača je vektor, čija svaka komponenta pokazuje učestalost korištenja odgovarajuće čiste strategije od strane igrača. Maksimalna ili niža cijena igre - broj α = max min aij i j Maksimalna strategija (linija) - strategija koju je igrač izabrao da maksimizira svoj minimalni dobitak. Očigledno, pri odabiru najopreznije maksiminske strategije, igrač A sebi obezbjeđuje (bez obzira na ponašanje protivnika) zagarantovanu isplatu od najmanje α. Maksimalna ili gornja cijena igre - broj β = min max aij j i Minimax strategija (kolona) - strategija koju je igrač izabrao da minimizira svoj maksimalni gubitak. Očigledno, pri odabiru najopreznije minimaks strategije, igrač B ni pod kojim okolnostima ne dozvoljava igraču A da osvoji više od β. Donja cijena igre uvijek ne prelazi gornju cijenu igre α = max min aij 6 min max aij = β i j j i Teorem 1 (glavni teorem teorije matričnih igara). Svaka konačna igra ima barem jedno rješenje, moguće u području mješovitih strategija. 6 2. Igre sa sedlom. Rješenje u čistim strategijama Igra sa sedlom je igra za koju je α = max min aij = min max aij = β i j j i Za igre sa sedlom, pronalaženje rješenja sastoji se u odabiru maksiminske i minimaksne strategije koje su optimalne., Čisti trošak igre - opšte značenje donja i gornja cijena igre α=β=ν 2.1. Primjeri Primjer 1 Pronađite rješenje u čistim strategijama igre datim matricom 8 4 7 A= 6 5 9 7 7 8 Rješenje: odredite gornju i donju cijenu igre. Da bismo to učinili, nalazimo minimum brojeva aij u i-ti red αi = min aij j i maksimum brojeva aij u j-toj koloni βj = max aij i Brojeve αi (minimum reda) upisaćemo pored matrice plaćanja na desnoj strani u vidu dodatne kolone. Brojeve βi (maksimumi stupca) upisujemo ispod matrice u obliku dodatne linije: αi 8 4 7 4 6 5 9 5 7 7 8 7 βj 8 7 9 7 Nađi maksimum brojeva αi α = max αi = 7 i i minimum brojeva βj β = min βj = 7 j α = β - igra ima sedlo. Optimalna strategija za igrača je strategija A3, a za igrača B je strategija B2, neto cijena igre ν = 7 Primjer 2 Matrica plaćanja je data: 2 2 1 1 2 0 1 1 1 1 A= 1 1 1 1 2 1 2 1 1 2 Pronađite rješenje za igru u čistim strategijama. Rješenje: 2 2 1 1 2 1 0 1 1 1 1 0 1 1 1 1 2 1 1 2 1 1 2 1 βj 2 2 1 1 2 α = β = 1. Igra ima šest sedla. Optimalne strategije će biti: A1 i B3 ili B4 A3 i B3 ili B4 A4 i B3 ili B4 8 3. Rješenje igre u mješovitim strategijama Kada je α = β. U slučaju kada pri izboru svojih strategija oba igrača nemaju informaciju o izboru drugog, igra ima rješenje u mješovitim strategijama. SA = (p1, p2, ..., pm) - mješovita strategija igrača A, u kojoj se primjenjuju strategije A1, A2, ..., Am sa vjerovatnoćama ∑ m p1, p2, ..., pm, pi = 1, pi > 0, i = 1, m i=1 SB = (q1, q2, ..., qn) - mješovita strategija igrača B, u kojoj se primjenjuju strategije B1, B2, ..., Bm sa vjerovatnoćama ∑ n q1, q2 , ..., qm , qi = 1, qi > 0, i = 1, n i=1 Ako je: SA∗ optimalna strategija igrača A, SB∗ je optimalna strategija igrača B, tada cijena igre je ∑ n ∑ m ν = aij · p∗i · qi∗ j=1 i=1 Sljedeća teorema odgovara na pitanje kako pronaći rješenje za igre 2 × 2, 2 × n, m × 2 Teorema 2 (kako pronaći rješenje za igre 2 × 2, 2 × n, m × 2). Ako jedan od igrača koristi optimalnu mješovitu strategiju, onda je njegova isplata jednaka cijeni igre ν, bez obzira na vjerovatnoću s kojom će drugi igrač koristiti strategije uključene u optimalnu (uključujući i čiste strategije). 9 3.1. Igra 2 × 2 Razmotrimo igru 2 × 2 sa matricom: () a11 a21 a21 a22 Neka igra nema rješenja u čistim strategijama. Nađimo optimalne strategije SA∗ i SB∗. Prvo definišemo strategiju SA∗ = (p∗1, p∗2). Prema teoremi, ako se stranka A pridržava strategije ν, tada će bez obzira na tok akcije stranke B, isplata ostati jednaka cijeni igranja ν. Prema tome, ako se strana A pridržava optimalne strategije SA∗ = (p∗1, p∗2), onda strana B može primijeniti bilo koju od svojih strategija bez promjene svoje isplate. Zatim, kada igrač B koristi čistu strategiju B1 ili B2, igrač će dobiti prosječnu isplatu jednaku cijeni igre: a11 p∗1 + a21 p∗2 = ν ← za strategiju B1 a12 p∗1 + a22 p∗ 2 = ν ← za strategiju B2 Uzimajući u obzir da je p∗1 + p∗2 = 1: p∗1 = a2 2−a2 1 a11 +a22 −a12 −a21 p∗2 = a1 1−a1 2 a11 +a22 −a12 −a21 Cijena igre: a22 a11 − a12 a21 ν= a11 + a22 − a12 − a21 Optimalna strategija igrača B nalazi se na sličan način: SB∗ = (q1∗, q2∗). Uzimajući u obzir da je q1∗ + q2∗ = 1: q1∗ = a2 2−a1 2 a11 +a22 −a12 −a21 q2∗ = a1 1−a2 1 a11 +a22 −a12 −a21 3.1.1. Primjeri Primjer 3 Naći rješenje za igru sa matricom () −1 1 A= 1 −1 10 Rješenje: igra nema sedlo, jer je α= -1, β = 1, α ̸= β. Tražimo rješenje u mješovitim strategijama. Koristeći formule za p∗ i q∗, dobijamo p∗1 = p∗2 = 0,5 i q1∗ = q2∗ = 0,5, ν = 0 Dakle, SA∗ = (0,5, 0,5) SB∗ = (0,5, 0,5 ) Primjer 4 Naći rješenje igre sa matricom () 2 5 A= 6 4 Rješenje: igra nema sedlo, jer je α= 4, β = 5, α ̸= β. Tražimo rješenje u mješovitim strategijama. Koristeći formule za p∗ i q∗, dobijamo p∗1 = 0,4, p∗2 = 0,6 i q1∗ = 0,2 q2∗ = 0,8, ν = 4,4 Dakle, SA∗ = (0,4, 0,6) SB∗ = ( 0,2, 0,8) 11 3.1.2. Geometrijska interpretacija Igri 2 × 2 može se dati jednostavna geometrijska interpretacija. Uzmimo jedan odsječak apscisne ose, čiju svaku tačku povezujemo s nekom mješovitom strategijom S = (p1, p2) = (p1, 1 − p1) i vjerovatnoća p1 strategije A1 će biti jednaka udaljenosti od tačka SA do desnog kraja preseka, a verovatnoća p2 , strategija A2 - rastojanje do levog kraja. .y .I .I I .B1′ .N .B1 .a21 .a11 .I I .I .∗ .x .P2 .SA∗ .P1∗ Konkretno, levi kraj preseka (tačka sa apscisom = 0) odgovara na strategiju A1, desni kraj segmenta (x = 1) - strategija A2 Na krajevima segmenta vraćaju se dvije okomice na x-osu: os I − I - isplata za strategiju A1 se odlaže; os II − II - odgađa se isplata za strategiju A2. Neka igrač B primeni strategiju B1; daje na osama I − I i II − II, redom, tačke sa ordinatama a11 i a21. Kroz ove tačke povlačimo pravu liniju B1 − B1′. Za bilo koju mješovitu strategiju SA = (p1, p2), igračeva isplata je određena tačkom N na pravoj liniji B1 − B1′, koja odgovara tački SA na x-osi koja dijeli segment u omjeru p2: p1. Očigledno, prava linija B2 − B2′, koja određuje isplatu za strategiju B2, može se konstruisati na potpuno isti način. 12 .y .I .I I .B2 .N .a21 .B2′ a . 22 .I I .I .∗ .x .P2 .SA∗ .P1∗ Potrebno je pronaći optimalnu strategiju SA∗ , tj. tako da bi se minimalna isplata igrača A (s obzirom na najgore ponašanje igrača B) pretvorila u maksimum. Da biste to učinili, konstruirajte donju granicu za isplatu igrača A za strategije B1, B2, tj. izlomljena linija B1 N B2′ ;. Na ovoj granici će ležati minimalna isplata igrača A za bilo koju od njegovih mješovitih strategija, tačka N, u kojoj ova isplata dostiže maksimum i određuje odluku i cijenu igre. .y .I .I I .B2 .B1′ .N .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S . 1∗ P Ordinata tačke N nije ništa drugo do trošak igre ν, njena apscisa je jednaka ∗2, a rastojanje do desnog kraja segmenta je jednako ∗1, tj. udaljenost od tačke SA∗ do krajeva segmenta jednaka je vjerovatnoćama ∗2 i ∗1 strategija A2 i A1 optimalne mješovite strategije igrača A. u ovom slučaju rješenje igre je određeno presjekom tačka strategija B1 i B2. Ispod je slučaj kada je igračeva optimalna strategija čista strategija A2. Ovdje je strategija A2 (za bilo koju neprijateljsku strategiju) isplativija od strategije A1, 13 .y .y .I .I I .I I. I .B2′ . 1′ B .B1′ B . 2 .B2′ B . 2 .B1 .ν = a21 .B1 .ν = a21 I. I I. I .I . .x .I . .x. 2∗ P . A∗S = A2. 2∗ P . A∗ S = A2 Desno je prikazan slučaj kada igrač B ima očigledno neisplativu strategiju. Geometrijska interpretacija takođe omogućava vizualizaciju donje cijene igre α i gornje cijene β .y .I .I I .B2 .B1′ .N .B1 .B2′ .β = a21 .α = a22 .I I .I .∗ .x .P2 . A∗ S . 1∗ P Na istom grafikonu možemo dati i geometrijsku interpretaciju optimalnih strategija igrača B. Lako je provjeriti da je udio q1∗ strategije B1 optimalne mješovite strategije SB∗ = (q1∗, q2∗) jednak omjeru dužine segmenta KB2 i zbira dužina segmenata KB1 i KB2 na I − I osi: .y .I .I I .B2 .B1′ .N .K .L .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S . 1∗ P 14 KB2 q1∗ = KB2 + KB1 ili LB2′ q1∗ = LB2′ + LB1′ Optimalna strategija SB∗ = (q1∗, q2∗) se može naći na drugi način, ako zamijenimo igrače B i B, i umjesto maksimuma donje granice dobitaka, uzmite u obzir minimum gornje granice. .y .I .I I .A2 .A′1 .N .A1 .A′2 .I I .I . .x .q2∗ . B∗ S .q1∗ 15 3.2. Igre 2 × n i m × 2 Rješenje za igre 2 × n i m × 2 zasniva se na sljedećem teoremu. Teorem 3. Svaka konačna igra m × n ima rješenje u kojem broj aktivnih strategija svake strane ne prelazi najmanji od brojeva m i n. Prema ovoj teoremi, igra 2 × n uvijek ima rješenje u kojem svaki igrač ima najviše dvije aktivne strategije. Jednom kada pronađete ove strategije, igra 2 × n pretvara se u igru 2 × 2, koja se može riješiti na elementaran način. Pronalaženje aktivnih strategija može se obaviti grafički: 1) konstruisana je grafička interpretacija; 2) utvrđuje se donja granica dobitka; 3) dvije strategije drugog igrača identificiraju se na donjoj granici isplate, koje odgovaraju dvije prave koje se sijeku u tački sa maksimalnom ordinatom (ako se više od dvije prave seku u ovoj tački, uzima se bilo koji par) - ove strategije predstavljaju aktivne strategije igrača B. Dakle, igra 2 × n se svodi na igru 2 × 2. Igra m × 2 također se može riješiti, s tom razlikom što nije donja, već gornja granica isplate konstruisan, a na njemu se ne traži maksimum, nego minimum. Primjer 5 Pronađite rješenje za igru () 7 9 8 A= 10 6 9 Rješenje: geometrijskom metodom biramo aktivne strategije. Direktne linije B1 − B1′, B2 − B2′ i B3 − B3′ odgovaraju strategijama B1, B2, B3. Izlomljena linija B1 N B2 je donja granica igračevog dobitka. Igra ima rješenje S∗A = (23, 31); S∗B = (0,5; 0,5; 0); v = 8. 16 .y .I .I I . 1′ B B . 2 .B3′ .N .B3 .B1 .B2′ .I I .I . .x. 2∗ P . A∗ S . 1∗ P 17 Indeksna igra, 2 poteza, 3 2 × 2, 10 ličnih, 3 2 × 2, 9 nasumično, 3 geometrija, 12 neto cijena igre, 7 primjera, 10 2 × n, 9, 16 m × 2, 9 , 16 beskonačno, 4 u normalnom obliku, 5 konačnih, 4 više poteza, 4 jednokretni, 4 matrica, 5 upareni, 2 nulta zbroj, 2 antagonistička, 2 neantagonistička, 2 rješenja, 5 u mješovitim strategijama, 5 , 9 u čistim strategijama , 5 sa točkom sedla, 7 cijena, 5 gornjih, 6 donjih, 6 čistih, 7 maksimalnih, 6 matrica igre, 5 isplata, 5 minimaksa, 6 normalizacija igre, 5 strategija, 4 maksimana, 6 minimaksa, 6 optimalna, 4 mješovita, 5 teorija igara, 2 18
Sa popularnog američkog bloga Cracked.
Teorija igara je proučavanje načina na koji se može napraviti najbolji potez i, kao rezultat, dobiti što je više moguće pobjedničke kolače tako što ćete odsjeći dio od drugih igrača. Uči vas da analizirate mnoge faktore i donesete logički uravnotežene zaključke. Mislim da bi to trebalo proučavati nakon brojeva i prije abecede. Jednostavno zato što previše ljudi donosi važne odluke na osnovu intuicije, tajnih proročanstava, lokacije zvijezda i slično. Temeljito sam proučio teoriju igara, a sada želim da vam kažem o njenim osnovama. Možda će ovo dodati malo zdravog razuma vašem životu.
1. Zatvorenikova dilema
Berto i Robert su uhapšeni zbog pljačke banke nakon što nisu pravilno iskoristili ukradeni automobil da pobjegnu. Policija ne može da dokaže da su oni opljačkali banku, ali ih je uhvatila na crvenom u ukradenom automobilu. Odvedeni su u različite prostorije i svakom je ponuđen dogovor: da preda saučesnika i pošalje ga u zatvor na 10 godina, a da sam bude pušten. Ali ako oboje izdaju jedno drugo, onda će svaki dobiti 7 godina. Ako niko ništa ne kaže, onda će oboje u zatvor na 2 godine samo zbog krađe auta.
Ispostavilo se da ako Berto šuti, ali ga Robert preda, Berto odlazi u zatvor na 10 godina, a Robert izlazi na slobodu. Svaki zatvorenik je igrač, a svačija korist se može izraziti kao "formula" (šta dobijaju obojica, šta dobija drugi). Na primjer, ako te udarim, moj pobjednički obrazac bi izgledao ovako (ja dobijem grubu pobjedu, ti patiš od jak bol). Pošto svaki zatvorenik ima dvije mogućnosti, rezultate možemo prikazati u tabeli.
Praktična primjena: Identifikacija sociopata
Ovdje vidimo glavnu primjenu teorije igara: prepoznavanje sociopata koji misle samo o sebi. Prava teorija igara je moćno analitičko oruđe, a amaterizam često služi kao crvena zastava koja označava nekoga ko nema osjećaj časti. Ljudi koji intuitivno kalkuliraju smatraju da je bolje učiniti nešto ružno jer će to rezultirati kraćom zatvorskom kaznom bez obzira šta drugi igrač uradi. Tehnički, ovo je tačno, ali samo ako ste kratkovida osoba koja stavlja brojeve više ljudski životi. Zbog toga je teorija igara toliko popularna u finansijama.
Pravi problem sa dilemom zatvorenika je to što ignoriše podatke. Na primjer, ne razmatra mogućnost da se sretnete sa prijateljima, rođacima, pa čak ni povjeriocima osobe koju ste poslali u zatvor na 10 godina.
Najgore je što se svi koji su uključeni u dilemu zatvorenika ponašaju kao da nikada nisu čuli za nju.
A najbolji potez je šutjeti i nakon dvije godine zajedno sa dobrim prijateljem koristiti isti novac.
2. Dominantna strategija
Ovo je situacija u kojoj vaši postupci daju najveća pobeda, bez obzira na akcije protivnika.Šta god da se desi, uradili ste sve kako treba. Zbog toga mnogi ljudi sa dilemom zatvorenika vjeruju da izdaja vodi do "najboljeg" ishoda bez obzira na to što druga osoba radi, a nepoznavanje stvarnosti svojstveno ovoj metodi čini da to izgleda super lako.
Većina igara koje igramo nemaju strogo dominantne strategije jer bi inače bile strašne. Zamislite da uvijek radite istu stvar. U igri kamen-papir-makaze nema dominantne strategije. Ali ako biste se igrali s osobom koja je imala rukavice za pećnicu i mogla je pokazati samo kamen ili papir, imali biste dominantnu strategiju: papir. Vaš papir će zamotati njegov kamen ili rezultirati neriješenim rezultatom, a ne možete izgubiti jer vaš protivnik ne može pokazati makaze. Sada kada imate dominantnu strategiju, bili biste budala da pokušate nešto drugačije.
3. Bitka polova
Igre su zanimljivije kada nemaju striktno dominantnu strategiju. Na primjer, bitka polova. Anjali i Borislav idu na spoj, ali ne mogu da biraju između baleta i boksa. Anjali voli boks jer uživa da vidi kako krv teče na radost vrišteće gomile gledalaca koji misle da su civilizovani samo zato što su platili da se nečija glava razbije.
Borislav želi da gleda balet jer razume kroz šta balerine prolaze velika količina povrede i najteži trening, znajući da jedna povreda može sve da završi. baletani - najvećim sportistima na zemlji. Balerina može da te udari nogom u glavu, ali to nikada neće učiniti, jer njena noga vredi mnogo više od tvog lica.
Svako od njih želi da ide na svoj omiljeni događaj, ali ne želi da uživa sam, pa evo kako pobjeđuje: najveća vrijednost- rade šta vole, najmanju vrijednost- samo biti sa drugom osobom, a nula - biti sam.
Neki ljudi sugeriraju tvrdoglavo prepoznavanje: ako radite ono što želite bez obzira na sve, druga osoba se mora povinovati vašem izboru ili izgubiti sve. kao što sam već rekao, pojednostavljena teorija igara je odlična u prepoznavanju budala.
Praktična primjena: Izbjegavajte oštre uglove
Naravno, ova strategija ima i svoje značajne nedostatke. Prije svega, ako svoje izlaske tretirate kao "bitku polova", to neće uspjeti. Raskinite se da svako od vas pronađe nekoga ko mu se sviđa. A drugi problem je što su u ovoj situaciji učesnici toliko nesigurni u sebe da to ne mogu učiniti.
Zaista pobjednička strategija za svakoga je da radi ono što želi. a posle ili sutradan, kada budu slobodni, odemo zajedno u kafić. Ili naizmjenično između boksa i baleta sve dok se ne dogodi revolucija u svijetu zabave i izmisli balet boksa.
4. Nashova ravnoteža
Nash ekvilibrijum je skup poteza u kojima niko ne želi učiniti ništa drugačije nakon činjenice. I ako to uspemo da uspemo, teorija igara će zameniti ceo filozofski, verski i finansijski sistem na planeti, jer je "volja da se ne propadne" postala moćnija za čovečanstvo pokretačka snaga nego vatra.
Hajde da brzo podelimo 100 dolara. Vi i ja odlučujemo koliko od stotina trebamo i istovremeno objavljujemo iznose. Ako naše ukupan iznos manje od sto, svako dobije ono što želi. Ako ukupno više od stotinu, onaj koji je tražio najmanju količinu dobija željeni iznos, a pohlepnijoj ono što ostane. Ako tražimo isti iznos, svi dobijaju 50 dolara. Koliko ćeš tražiti? Kako ćete podijeliti novac? Postoji samo jedan pobjednički potez.
Uzimanje 51 dolara dobit ćete maksimalni iznos bez obzira šta vaš protivnik odabere. Ako zatraži više, dobit ćete 51 $. Ako zatraži 50 ili 51 dolara, dobićete 50 dolara. A ako traži manje od 50 dolara, dobićete 51 dolar. U svakom slučaju, ne postoji druga opcija koja će vam zaraditi više novca od ove. Nash ravnoteža - situacija u kojoj oboje biramo 51 dolar.
Praktična primjena: Prvo razmisli
Ovo je cela poenta teorije igara. Ne morate pobjeđivati, a još manje nanositi štetu drugim igračima, ali morate napraviti najbolji potez za sebe, bez obzira na to što oni oko vas spremaju za vas. A još je bolje ako ovaj potez bude koristan za druge igrače. Ovo je vrsta matematike koja bi mogla promijeniti društvo.
Zanimljiva varijacija ove ideje je pijenje, koje se može nazvati vremenski zavisnim Nashovim ekvilibrijumom. Kada dovoljno popijete, nije vas briga za postupke drugih ljudi bez obzira šta oni rade, ali sutradan zaista požalite što niste uradili nešto drugačije.
5. Igra bacanja
Izbacivanje se igra između igrača 1 i igrača 2. Svaki igrač istovremeno bira glavu ili rep. Ako pogode tačno, igrač 1 dobija peni igrača 2. Ako ne, igrač 2 dobija novčić igrača 1.
Pobednička matrica je jednostavna...
...optimalna strategija: igrajte potpuno nasumično. Teže je nego što mislite jer izbor mora biti potpuno slučajan. Ako imate prednost ili prednost, vaš protivnik to može iskoristiti da vam uzme novac.
Naravno, pravi problem ovdje je u tome što bi bilo mnogo bolje kada bi se samo bacili jedan na drugoga. Kao rezultat toga, njihov profit bi bio isti, a trauma koja je nastala mogla bi pomoći ovim nesretnim ljudima da osjete nešto drugo osim užasne dosade. Na kraju krajeva, ovo najgora igra ikada postojao. A ovo je idealan model za izvođenje jedanaesteraca.
Praktična primjena: Kazna
U fudbalu, hokeju i mnogim drugim igrama produžeci su izvođenje jedanaesteraca. I bili bi zanimljiviji da se baziraju na tome koliko su puta igrači puna forma bi mogli da rade točak jer bi to barem bio pokazatelj njihove fizičke sposobnosti i bilo bi zabavno gledati. Golmani ne mogu jasno odrediti kretanje lopte ili paka na samom početku njenog kretanja, jer, nažalost, roboti još uvijek ne učestvuju u našim sportskim takmičenjima. Golman mora da izabere levi ili desni pravac i da se nada da se njegov izbor poklapa sa izborom protivnika koji šutira na gol. Ovo ima nešto zajedničko sa igranjem novčića.
Međutim, imajte na umu da ovo nije savršen primjer sličnosti sa igrom glave i repa, jer čak i ako praveći pravi izbor smjeru, golman ne smije uhvatiti loptu, a napadač ne smije pogoditi gol.
Dakle, koji je naš zaključak prema teoriji igara? Igre s loptom treba da se završavaju na način "više lopti", pri čemu se svake minute jedan na jedan igrači daje po jedna dodatna lopta/pak dok jedna strana ne postigne određeni rezultat, što je pokazatelj prave vještine igrača, a nije spektakularna slučajnost.
Na kraju krajeva, teoriju igara treba koristiti kako bi igru učinili pametnijom. Što znači da je bolje.
Teorija igara kao grana istraživanja operacija, to je teorija matematičkih modela za donošenje optimalnih odluka u uslovima neizvjesnosti ili sukoba više strana s različitim interesima. Teorija igara proučava optimalne strategije u situacijama igre. To uključuje situacije vezane za izbor najprofitabilnijih proizvodnih rješenja za sistem naučnih i ekonomskih eksperimenata, organizaciju statistička kontrola, ekonomski odnosi između industrijskih preduzeća i drugih sektora. Formaliziranje konfliktne situacije matematički se mogu predstaviti kao igra dvojke, trojke itd. igrači, od kojih svaki teži cilju da maksimizira svoju korist, svoj dobitak na račun drugog.Odjeljak "Teorija igara" predstavljen je sa tri online kalkulatori:
- Optimalne strategije igrača. U takvim problemima specificira se matrica plaćanja. Potrebno je pronaći čiste ili mješovite strategije igrača i, cijena igre. Da biste riješili, morate specificirati dimenziju matrice i metodu rješenja. Servis implementira sledećim metodama rješenja za igru za dva igrača:
- Minimax. Ako trebate pronaći čistu strategiju igrača ili odgovoriti na pitanje o sedlu u igri, odaberite ovu metodu rješenja.
- Simpleks metoda. Koristi se za rješavanje mješovitih strateških igara korištenjem metoda linearnog programiranja.
- Grafička metoda. Koristi se za rješavanje mješovitih strateških igara. Ako postoji sedlo, rješenje se zaustavlja. Primjer: Za datu matricu plaćanja pronađite optimalne mješovite strategije igrača i cijenu igre koristeći grafička metoda igrica rešenja.
- Brown-Robinsonova iterativna metoda. Iterativni metod se koristi kada grafička metoda nije primenljiva i kada je algebarska i matrične metode. Ova metoda daje približnu vrijednost cijene igre, a prava vrijednost se može dobiti sa bilo kojim željenim stepenom tačnosti. Ova metoda nije dovoljna za pronalaženje optimalnih strategija, ali vam omogućava da pratite dinamiku potezne igre i odredite cijenu igre za svakog igrača na svakom koraku.
Sve metode koriste provjeru dominantnih redova i kolona. - Bimatrix igra. Obično se u takvoj igri specificiraju dvije matrice iste veličine isplata prvog i drugog igrača. Redovi ovih matrica odgovaraju strategijama prvog igrača, a stupci matrica odgovaraju strategijama drugog igrača. U ovom slučaju, prva matrica predstavlja dobitak prvog igrača, a druga matrica predstavlja dobitke drugog.
- Igre sa prirodom. Koristi se kada trebate odabrati odluka menadžmenta prema kriterijima Maximaxa, Bayesa, Laplacea, Walda, Savagea, Hurwitza.
Za Bayesov kriterij također će biti potrebno unijeti vjerovatnoće događaja. Ako nisu specificirane, ostavite zadane vrijednosti (postojat će ekvivalentni događaji).
Za Hurwitzov kriterijum navedite nivo optimizma λ. Ako ovaj parametar nije naveden u uvjetima, možete koristiti vrijednosti 0, 0,5 i 1.
Mnogi problemi zahtijevaju pronalaženje rješenja pomoću računara. Gore navedene usluge i funkcije su jedan od alata.
