Hrvatski matematički elektronski časopis math.e

http://www.math.hr/~mathe/

Teorija igara - matematičko modeliranje konfliktnih situacija

Vedran Krčadinac

Sadržaj:

1. Uvod
2. Osnovni pojmovi
3. Strogo određene igre
4. Optimalne miješane strategije
5. Giapponese
6. Zadaci
Literatura

1. Uvod

Teorija igara je matematička disciplina koja se razvila sredinom 20. stoljeća. Početkom se može smatrati knjiga Theory of games and economic behavior (Teorija igara i ekonomsko ponašanje) matematičara Johna von Neumanna i ekonomista Oskara Morgensterna [3]. Još jedan od fundamentalnih doprinosa je rad Johna Nasha [2], za koji mu je kasnije dodijeljena Nobelova nagrada za ekonomiju (Nobelova nagrada ne dodjeljuje se za matematiku). O Johnu Nashu nedavno je snimljen biografski film Genijalni um. U početku je glavna motivacija za razvoj bila ekonomska, ali je teorija igara našla primjene i u drugim društvenim znanostima, vojne primjene, pa čak i primjene u biologiji. Zanimljivi primjeri iz biologije mogu se naći u knjizi Richarda Dawkinsa Sebični gen [1].

Pojednostavljeno rečeno, teorija igara bavi se situacijama konflikta između dvaju ili više sudionika. Cilj je odrediti ponašanje sudionika koje je za njih najpovoljnije, pod pretpostavkom da su racionalni. Konflikt je reguliran strogo definiranim pravilima kao u društvenim igrama poput pokera, monopola, "čovječe ne ljuti se" i sličnim. Teorija igara omogućuje preciznu analizu takvih igara, po čemu je dobila ime. Konflikti u stvarnom životu obično nisu podložni jednostavnim pravilima. Zbog toga je teorija igara uglavnom ostala u okvirima akademskih primjera, a u praksi se dosta rijetko koristi. Ipak, radi se o lijepoj teoriji koja povezuje nekoliko grana matematike i dala je važne doprinose razumijevanju ponašanja u ekonomiji, sociologiji, psihologiji i teoriji evolucije.

2. Osnovni pojmovi

Osnovne pojmove teorije igara objasnit ćemo u slučaju igre za dva igrača sume nula. Riječ igra odnosi se na bilo kakav konflikt dviju suprostavljenih strana koji želimo analizirati. To ne mora biti društvena igra, niti sudionici moraju biti osobe, usprkos tome što ih nazivamo igračima. Ograničenje na igre sume nula znači da je gubitak prvog igrača jednak dobitku drugog, i obrnuto. Taj dobitak/gubitak treba biti izražen numerički, što nije uvijek jednostavno u realnim situacijama. Još jedno ograničenje koje namećemo jest da igrači imaju konačno mnogo strategija, tj. mogućnosti za ponašanje u sukobu.

Promotrimo jednostavan primjer, igru "par - nepar". Igrači istovremeno pokazuju šaku s nekoliko ispruženih prstiju. Ako je zbroj ispruženih prstiju paran, pobjeđuje prvi igrač ("par"); u suprotnom pobjeđuje drugi igrač ("nepar"). Igrači zapravo imaju samo dvije bitno različite mogućnosti: pokazati paran broj prstiju ili pokazati neparan broj prstiju. Za prvog i za drugog igrača potpuno je svejedno hoće li pokazati jedan, tri ili svih pet prstiju. Zato u ovoj igri svaki igrač ima dvije strategije (točnije bi bilo reći čiste strategije, što ćemo uskoro objasniti). Igrač koji je pobijedio dobiva određenu količinu novca od igrača koji je izgubio, recimo jednu kunu. Radi se o igri sume nula jer je iznos koji osvaja pobjednik jednak iznosu koji njegov protivnik gubi. U nekim igrama to nije slučaj, na primjer dio novca može zadržati organizator igre (kockarnica).

Sa stanovišta prvog igrača svi mogući ishodi igre par - nepar su:

To možemo tablično zapisati ovako:
Drugi igrač ("nepar")
Paran brojNeparan broj
Prvi igrač
("par")
Paran broj
       1              -1       
      -1               1       
Neparan broj
Ova tablica naziva se matrica isplata i njome je igra potpuno određena. Općenito, igra sume nula u kojoj prvi igrač ima m čistih strategija, a drugi igrač n čistih strategija zadaje se m x n matricom:
A   =  




a11
a12
 ... 
a1n
a21
a22
...
a2n
:
:
:
am1
am2
...
amn





Reci odgovaraju strategijama prvog igrača, stupci strategijama drugog igrača, a broj aij određuje isplatu prvom igraču ako on odabere i-tu, a njegov protivnik j-tu strategiju. Pozitivan broj znači da prvi igrač dobiva odgovarajući iznos, a negativan da ga gubi.

Važna pretpostavka koju do sada nismo spomenuli je da se igra ponavlja. Ako se par - nepar igra samo jednom, nema smisla govoriti o optimalnom ponašanju igrača. U slučaju kad se igra ponavlja, igrači mogu igrati dobro ili loše i daljnja analiza ima smisla. Pretpostavimo da prvi igrač uvijek pokazuje paran broj prstiju. Njegov će protivnik brzo shvatiti da pokazivanjem neparnog broja uvijek pobjeđuje. Zapravo, ako prvi igrač samo malo češće pokazuje parne nego neparne brojeve, drugi igrač može uvijek pokazivati neparne brojeve i pobjeđivat će češće. Zaključujemo da prvi igrač treba jednakom frekvencijom birati parne i neparne brojeve, a isto naravno vrijedi i za drugog igrača.

Pretpostavimo sada da prvi igrač pokazuje redom paran broj, zatim neparan, pa paran, pa neparan i tako dalje. Čim drugi igrač uoči pravilnost, pokazivat će brojeve suprotne parnosti i uvijek pobjeđivati. Prema tome, igrači ne smiju dozvoliti da protivnik uoči pravilnost u njihovom nizu brojeva. Najbolje im je parnost brojeva birati na slučajan način, bacanjem novčića ili slično. Tako dolazimo do pojma miješane strategije. Radi se o vjerojatnostima prema kojima igrači biraju retke, odnosno stupce matrice isplata. Uobičajeno je za prvog igrača vjerojatnosti zapisivati u vektor-redak P, a za drugog u vektor-stupac Q. Optimalne miješane strategije u igri par - nepar su, dakle,

P   =     1/2   1/2       i      Q   =  

1/2
1/2


Zaključak vrijedi općenito: igračima nije u interesu da protivnik uoči pravilnost u njihovoj igri, zato retke i stupce matrice isplata biraju slučajno. Miješanu strategiju čine vjerojatnosti prema kojima ih biraju. Za prvog igrača zapisujemo ih horizontalno, a za drugog vertikalno:
P   =     p1  p2  ...  pm       i      Q   =  




q1
q2
:
qn





kolo sreće Brojevi pi ,  qj su vjerojatnosti, tj. ne smiju biti negativni ni veći od jedan. Osim toga mora vrijediti p1+ ... + pm = q1+ ... + qn = 1 jer igrači u svakom ponavljanju igre biraju točno jednu čistu strategiju. Izbor se, na primjer, može realizirati "kolom sreće" prikazanim na slici.

Miješane strategije zapisuju se na opisan način da bismo mogli množiti matrice P, A i Q. Produkt P * A * Q jednak je matematičkom očekivanju dobitka prvog igrača i označava se E(PQ). Radi se o broju koji mjeri prosječan dobitak prvog igrača. Prvom igraču je u interesu da broj bude što veći, a drugom da bude što manji. Igrači utječu na njega izborom svojih miješanih strategija (prvi igrač bira P, a drugi Q).

Za igru par - nepar već smo našli optimalne strategije. Vrijednost igre je očekivani dobitak kad oba igrača igraju optimalno, u našem slučaju

E(PQ)   =     1/2   1/2   * 

 1    -1
-1     1


 * 

1/2
1/2


  =     1/2   1/2   * 

0
0


  =  0.
Ako je, kao u igri par - nepar, vrijednost igre jednaka nuli, igra je poštena. Ako je vrijednost igre pozitivna prvi igrač ima prednost, a ako je negativna drugi igrač ima prednost. To, naravno, ne znači da u igri pozitivne vrijednosti prvi igrač uvijek pobjeđuje. Međutim, što se više puta igra ponavlja veća je vjerojatnost da njegov prosječni dobitak bude pozitivan. Prosječni dobitak prvog igrača teži vrijednosti igre kad broj ponavljanja igre raste.

U igri par - nepar vrlo je lako odrediti optimalne strategije i vrijednost igre, jer je igra potpuno simetrična. To nije uvijek tako, čak ni za igre u kojima igrači imaju samo dvije čiste strategije. Na primjer, promotrimo modifikaciju igre par - nepar sa sljedećom matricom isplata:

A   =  

 3    -2
-2     1


Ako oba igrača pokažu parne brojeve, prvi igrač dobiva tri kune; ako oba pokažu neparne brojeve, prvi igrač dobiva jednu kunu; ako pokažu brojeve suprotne parnosti, drugi igrač dobiva dvije kune. Čini se da je i ova igra poštena jer u dva od četiri ishoda prvi igrač dobiva ukupno četiri kune, a u preostala dva drugi igrač dobiva isti iznos. Međutim, kasnije ćemo vidjeti da je vrijednost igre negativna, tj. drugi igrač ima prednost. Prije toga razmotrimo jednu vrstu igara za koju je lako naći optimalne strategije i vrijednost igre.

3. Strogo određene igre

Dvije konkurentske međunarodne tvrtke žele otvoriti predstavništvo u Hrvatskoj. Predstavništvo mogu otvoriti u Osijeku, Rijeci, Splitu ili Zagrebu. Ako otvore predstavništva u istom gradu, podijelit će tržište popola. Za ostale slučaje provedeno je istraživanje i rezultat je prikazan u tablici.

Druga tvrtka
OsRi StZg
Prva
tvrtka
Os
50%30%20%25%
70%50%45%40%
80%55%50%45%
75%60%55%50%
Ri
St
Zg

Naveden je udio tržišta koji osvaja prva tvrtka ako otvori predstavništvo u gradu koji označava redak, a druga tvrtka u gradu koji označava stupac matrice. Na primjer, ako prva tvrtka otvori predstavništvo u Splitu, a druga u Rijeci, prva tvrtka osvaja 55% tržišta, a druga preostalih 45%. Pretpostavljamo da druga tvrtka uvijek osvaja cijeli preostali dio tržišta, tj. da imamo igru sume nula. To ima ekonomskog smisla ako se radi o djelatnosti koja do sada nije bila zastupljena u Hrvatskoj, pa će tvrtke među sobom podijeliti cijelo tržište. Pobjednikom smatramo tvrtku koja osvoji više od pola tržišta.

U prvoj tvrtki razmišljaju na sljedeći način. Za svaki od četiri svoja izbora traže protivnikov izbor koji je za njih najnepovoljniji. Drugim riječima, traže minimalne brojeve u recima matrice isplata:

Druga tvrtka
OsRi StZg
Prva
tvrtka
Os
50%30%20% 25%
70%50%45%40%
80%55%50%45%
75%60%55%50%
Ri
St
Zg

Od četiriju brojeva obojanih plavo najveći je 50%. Prema tome, prva tvrtka osvaja barem pola tržišta ako otvori predstavništvo u Zagrebu. Za ostale izbore njihov je garantirani dobitak manji, iako maksimalni dobitak može biti veći. Najpovoljniji slučaj za prvu tvrtku bio bi da otvore predstavništvo u Splitu, a njihovi protivnici u Osijeku (tada osvajaju 80% tržišta). Međutim, druga tvrtka također se ponaša racionalno i neće izabrati za sebe nepovoljnu mogućnost (Osijek).

U drugoj tvrtki razmišljaju analogno. Za svaki svoj izbor nalaze najgoru mogućnost za sebe, a među njima onu koja je najpovoljnija. Drugim riječima, traže maksimume stupaca i biraju najmanji od tih maksimuma:

Druga tvrtka
OsRi StZg
Prva
tvrtka
Os
50%30%20% 25%
70%50%45%40%
80%55%50%45%
75%60%55%50%
Ri
St
Zg

Ljubičasto obojani broj označile su obje tvrtke. Za jednu i za drugu najbolje je predstavništvo otvoriti u Zagrebu, jer tada sigurno osvajaju 50% tržišta. To je vrijednost ove igre, a optimalne strategije mogu se matrično zapisati kao

P   =     0  0  0  1  ,          Q   =  




0
0
0
1





"Otvaranje predstavništva" očito se igra samo jednom, no to u ovom slučaju ne smeta. Tvrtke s vjerojatnošću 1 trebaju otvoriti predstavništvo u Zagrebu. Za razliku od igre par - nepar, u ovoj igri sreća ne igra ulogu. Takve igre nazivaju se strogo određenima.

Sedlasta točka je element matrice koji je ujedno minimum retka i maksimum stupca u kojem se nalazi. Igra kojoj matrica isplata sadrži sedlastu točku naziva se strogo određenom.

Optimalne strategije strogo određene igre imaju jedinicu na mjestu koje odgovara retku, odnosno stupcu u kojem je sedlasta točka, a na svim ostalim mjestima nule. Vrijednost igre je broj upisan u sedlastu točku. Za strogo određene igre lako je naći optimalne strategije i vrijednost igre, ali nisu sve igre takve. Na primjer, modificirana igra par - nepar nema sedlastu točku:

A   =  

 3    -2
-2     1


Promotrimo još jedan primjer igre koja nije strogo određena.

4. Optimalne miješane strategije

Dućan za ekstremne sportove nabavlja snowboarde i bicikle za iduću sezonu. Ako iduće zime padne mnogo snijega, zaradit će prosječno 500 kuna po naručenom snowboardu i 100 kuna po naručenom biciklu. Ako ne padne snijeg, prosječno će izgubiti 100 kuna po naručenom snowboardu i zaraditi 400 kuna po naručenom biciklu. U kojem omjeru trebaju naručiti robu tako da garantirana zarada bude što veća, bez obzira na vremenske prilike?

Ovaj problem također možemo modelirati kao igru sume nula za dva igrača. Prvi igrač je dućan, a drugi priroda. Jasno, priroda nije svjestan igrač koji nastoji smanjiti zaradu dućana, ali sjetimo se da dućan želi maksimizirati garantiranu zaradu. Vlasnik dućana vjeruje u Murphyjev zakon prema kojem će vremenske prilike biti upravo onakve kakve njemu najmanje odgovaraju.

Miješane strategije u ovom primjeru interpretiramo drugačije. Strategija prvog igrača P =  p1  p2  određuje udio naručenih snowboarda (p1) i bicikla (p2). Strategija drugog igrača, Q, određuje intenzitet kojim će padati snijeg. Prva komponenta (q1) odgovara zimi bez snijega, a druga komponenta (q2) zimi s iznimno mnogo snijega. Uz ovakav dogovor matrica isplata glasi:

Priroda
nema snijegaima snijega
Dućansnowboardi
     -100              500       
      400              100       
bicikli
Ako označimo minimume redaka plavo, a maksimume stupaca crveno, vidimo da ni ova matrica nema sedlastu točku.
A   =  

-100    500
  400    100


Veći od dvaju plavih brojeva nalazi se u drugom retku. Prema dosadašnjem načinu razmišljanja dućan bi trebao naručiti samo bicikle, što mu garantira zaradu od 100 kuna po komadu. Međutim, postoji miješana strategija za koju je očekivana zarada dućana veća.

Teorem (von Neumann). Za svaku igru sume nula za dva igrača postoji par strategija P0, Q0 i broj v sa svojstvima:
  1. ako prvi igrač koristi strategiju P0 njegov očekivani dobitak je barem v, tj. E(P0,Q) >= v  za svaki Q;
  2. ako drugi igrač koristi strategiju Q0 očekivani dobitak prvog igrača nije veći od v, tj. E(P,Q0) <= v  za svaki P.

Zbog ovog teorema pojmovi optimalnih strategija i vrijednosti igre imaju smisla za sve igre, a ne samo za strogo određene. Racionalni igrači izabrat će strategije P0Q0 i tada će očekivani dobitak prvog igrača biti jednak vrijednosti igre v. Ako prvi igrač izabere strategiju koja nije optimalna, njegov očekivani dobitak može biti veći od v za pojedine strategije drugog igrača, ali postoji strategija Q za koju je očekivani dobitak manji od v. Analogno, ako drugi igrač izabere strategiju koja nije optimalna, prvi igrač ima strategiju P za koju je očekivani dobitak veći od v.

Von Neumannov teorem može se dokazati svođenjem na problem linearnog programiranja. Taj dokaz je jednostavniji od von Neumannovog originalnog dokaza i daje nam postupak za nalaženje optimalnih strategija i vrijednosti igre. Linearno programiranje bavi se minimizacijom i maksimizacijom linearnih funkcija više varijabli uz uvjete zadane linearnim nejednakostima. Postoji više efikasnih algoritama za rješavanje takvih problema, među kojima je najpopularniji simpleks algoritam. Pokazuje se da je za igru s matricom isplata A =  aij  nalaženje optimalne strategije prvog igrača P0 =  p1  p2  ...  pm  ekvivalentno problemu linearnog programiranja

v --> max
v <= a1j p1 + .. + amj pm,   j = 1,.., n
p1 + .. + pm = 1
pi <= 0,   i = 1,.., m
Nalaženje optimalne strategije drugog igrača Q0 ekvivalentno je sljedećem problemu linearnog programiranja.
u --> min
u <= ai1 q1 + .. + ain qn,   i = 1,.., m
q1 + .. + qn = 1
qj <= 0,   j = 1,.., n
Prema jednom od osnovnih teorema linearnog programiranja, teoremu dualnosti, maksimum iz prvog problema jednak je minimumu iz drugog problema, v = u. To je vrijednost igre, a iznosi varijabli p1,.., pm i q1,.., qn za koje se maksimum i minimum postižu su komponente optimalnih strategija prvog i drugog igrača. U našem slučaju problemi linearnog programiranja glase
v --> max
v <= -100 p1 + 400 p2
v <= 500 p1 + 100 p2
p1 + p2 = 1
p1 >= 0,   p2 >= 0
            
u --> min
u >= -100 q1 + 500 q2
u >= 400 q1 + 100 q2
q1 + q2 = 1
q1 >= 0,   q2 >= 0

Prikaz metoda za rješavanje problema linearnog programiranja prelazi okvire ovog članka. Probleme ćemo riješiti pomoću programa Mathematica, koji ima efikasne naredbe za optimizaciju Maximize i Minimize. Dovoljno je prepisati funkciju cilja i uvjete u Mathematica notaciji.

ducan.nb

Vidimo da je vrijednost igre v = u = 700/3, a optimalne strategije su

P0   =     1/3   2/3       i      Q0   =  

4/9
5/9


Prema tome, dućan može postići očekivanu zaradu od 233.33 kune po komadu, bez obzira na vremenske prilike. Treba naručiti dva puta više bicikla nego snowboarda.

Postoje formule za optimalne strategije i vrijednost igre u kojoj igrači imaju samo dvije čiste strategije.

Neka je
A   =  

 a    b
 c    d


matrica bez sedlaste točke i N = a + d - b - c. Rješenje igre kojoj je matrica isplata A dano je s
v  =  ad - bc
N
,      P0  = 


d - c
N
    a - b
N


,      Q0  = 






d - b
N
a - c
N






Uvrštavanjem u formule vidimo da je vrijednost modificirane igre par - nepar v = -1/8, a optimalne strategije su

P0   =     3/8   5/8       i      Q0   =  

3/8
5/8


Kao što smo najavili, ova igra nije poštena, nego drugi igrač ("nepar") ima prednost. Oba igrača trebaju pokazivati parne brojeve s vjerojatnošću 3/8, a neparne s vjerojatnošću 5/8.

5. Giapponese

Na kraju članka analizirat ćemo igru koju je autor naučio na odsluženju vojnog roka pod imenom "giapponese". Igraju dva igrača, a kao pribor svaki ima tri novčića. Igrači iza leđa zatvore određen broj novčića u šaku (nula, jedan, dva ili tri) i pokažu zatvorenu šaku protivniku. Cilj je pogoditi zbroj novčića u obje šake. Prvi igrač govori broj između nula i šest. Nakon toga pogađa drugi igrač. On ima više informacija jer je čuo prvog igrača, ali ne smije reći isti broj. Igrač koji je pogodio zbroj u idućem ponavljanju igre pogađa prvi, a ako nitko nije pogodio, igra se ponavlja istim redoslijedom.

Iako su pravila jednostavna, možemo postaviti nekoliko zanimljivih pitanja o ovoj igri. Pravila nisu ista za prvog i za drugog igrača, pa nije jasno je li igra poštena ili nije. Čini se da prednost ima drugi igrač, jer ima više informacija kad pogađa zbroj. Tome u prilog ide pravilo prema kojem pobjednik u idućoj igri pogađa prvi. Prvi igrač može pokušati prevariti drugog "blefiranjem", na primjer tako da u šaku zatvori tri novčića i kaže broj nula. Isplati li se prvom igraču kao dio svoje strategije povremeno blefirati? Da bismo odgovorili na ova pitanja, postavimo igru u okviru modela teorije igara.

Na prvi pogled čini se da je igra vrlo različita od prethodnih primjera. Do sada su igrači odluke uvijek donosili istovremeno i nisu imali informaciju o protivnikovom izboru. U igri giapponese i u svim igrama u kojima igrači naizmjence vuku poteze njihove odluke ovise o prethodnom tijeku igre. Treba razlikovati poteze od strategija. Strategije u sebi uključuju odgovor na svaki protivnikov potez u bilo kojem trenutku igre.

U igri giapponese prvi igrač donosi dvije odluke: koliko novčića zatvoriti u šaku i koji broj reći. Njegove čiste strategije možemo identificirati s parovima (x, y), pri čemu je x broj iz skupa {0,1,2,3}, a y iz skupa {0,1,2,3,4,5,6}. Na prvoj koordinati imamo 4 moguća izbora, na drugoj 7, pa prvi igrač ima ukupno 4 * 7 = 28 čistih strategija. Drugi igrač donosi iste odluke, ali broj koji će reći ovisi o broju koji je rekao prvi igrač. Njegovu drugu odluku identificiramo s funkcijom f : {0,1,2,3,4,5,6} --> {0,1,2,3,4,5,6}. Ako prvi igrač kaže broj y, drugi igrač govori f (y). Po pravilima igre brojevi y i f (y) moraju biti različiti, tj. funkcija f ne smije imati fiksnu točku. Takvih funkcija ima 67 = 279936. Prema tome, ukupan broj čistih strategija drugog igrača je 4 * 279936 = 1119744.

Matrica isplata igre giapponese ima 28 redaka i više od milijun stupaca. Odgovarajući problemi linearnog programiranja sadrže previše varijabli za rješavanje pomoću Mathematice. Na istu bi zapreku naišli kod analiziranja bilo koje imalo složenije igre. Na primjer, broj čistih strategija igre šah nezamislivo je velik. Šah sa stanovišta teorije igara zapravo nije jako zanimljiv, jer je kao i sve ostale igre s potpunom informacijom strogo određena igra. Jedan od igrača (vjerojatno prvi) ima pobjedničku strategiju koju treba uvijek slijediti ili postoje strategije koje igračima uvijek omogućuju remi. Na sreću mnogih šahista, današnja računala nisu dovoljno snažna za određivanje optimalnih šahovskih strategija.

Sa stanovišta teorije igara zanimljivije su igre s nepotpunom informacijom, na primjer poker i bridge. One vrlo vjerojatno nisu strogo određene. Zbog prevelikog broja čistih strategija ni te dvije igre nije moguće potpuno analizirati. Međutim, analizirane su razne pojednostavljene verzije, a to nam može nešto reći o pravoj igri. Tako ćemo i mi postupiti.

Promotrimo varijantu igre giapponese u kojoj svaki igrač ima samo jedan novčić. Čiste strategije prvog igrača su parovi (x, y) za x iz {0,1} i y iz {0,1,2}; ima ih 6. Čiste strategije drugog igrača su parovi (x, f ), gdje je x iz {0,1}, a f : {0,1,2} --> {0,1,2} je funkcija bez fiksne točke. Takvih funkcija ima 23 = 8, pa drugi igrač ima ukupno 2 * 8 = 16 čistih strategija. Element matrice isplata u retku označenim s (x1, y) i stupcu označenim s (x2, f ) jednak je 1 ako je x1 + x2 = y; ako je x1 + x2 = f (y) jednak je -1, a inače je 0. U prvom slučaju pobjeđuje prvi igrač, u drugom drugi, a u trećem je neodlučeno. Cijelu matricu konstruirat ćemo s nekoliko Mathematica naredbi.

giapponese.nb

Čitaocu prepuštamo formulirati pripadne probleme linearnog programiranja i riješiti ih. Doći će do neočekivanog zaključka da je giapponese ipak poštena igra. Objašnjenje ovog fenomena također ostavljamo za zadatke.

6. Zadaci

  1. Nađite optimalne strategije i vrijednosti igara zadanih matricama isplata:
    A   =  




     3    -2     5    -3     1
     1     0     1     0     2
    -1    -1   10    -2   -3
     4     0     7     0     1





    B   =  

    -5     2
     3    -1


                C   =  

     1    -4     5
    -2     1    10


    D   =  


     3     0    -3     4
    -2     3     2     3
     2     0    -3     3



  2. Dokažite: ako matrica ima više od jedne sedlaste točke, njihove vrijednosti su jednake. Opišite skup svih optimalnih strategija prvog i drugog igrača u tom slučaju.

  3. Promotrite formule za rješenje 2x2 igre. Ako je izraz N = a + d - b - c iz nazivnika jednak nuli, dokažite da matrica isplata ima sedlastu točku.

  4. Nađite optimalne strategije prvog i drugog igrača u pojednostavljenoj igri giapponese. Objasnite kako prvi igrač onemogućuje drugome da dobije korisnu informaciju na temelju njegovog pogađanja.

  5. Opišite analognu strategiju prvog igrača za giapponese koji se igra s tri novčića. Pokažite da je igra poštena. Isplati li se prvom igraču blefirati?

  6. Generalizirajte zaključke iz prethodna dva zadatka na giapponese u kojem prvi igrač ima m novčića, a drugi n novčića. Je li igra uvijek poštena, bez obzira na broj novčića?

Literatura

  1. R. Dawkins, Sebični gen, Izvori, 1997.

  2. J. Nash, Non-cooperative games, Annals of Mathematics 54 (1951), 286-295.

  3. J. von Neumann, O. Morgenstern, Theory of games and economic behavior, Princeton University Press, 1947.

  4. S. Stahl, A gentle introduction to game theory, American Mathematical Society, 1999.

  5. J.D. Williams, The compleat strategyst, Dover Publications, 1986.


1. Uvod
2. Osnovni pojmovi
3. Strogo određene igre
4. Optimalne miješane strategije
5. Giapponese
6. Zadaci
Literatura