REŠENE NALOGE IZ TEORIJE IGER Martin Raič RAIČ, Martin Rešene naloge iz teorije iger c 2015 Martin Raič Samozaložil avtor. Prva izdaja Ljubljana, 2015 Elektronska knjiga, dostopna na http://valjhun.fmf.uni-lj.si/~raicm/Poucevanje/TI/TI vaje 2015.pdf ISBN 978-961-283-344-2 (pdf) CIP – kataložni zapis o publikaciji Narodna in univerzitetna knjižnica, Ljubljana 519.83(076.2)(0.034.2) RAIČ, Martin Rešene naloge iz teorije iger [Elektronski vir] / Martin Raič – 1. izd. – El. knjiga. – Ljubljana: samozal. avtor, 2015 Način dostopa (URL): http://valjhun.fmf.uni-lj.si/~raicm/Poucevanje/TI/TI vaje 2015.pdf ISBN 978-961-283-344-2 (pdf) 280008448 Predgovor Ta zbirka je nastala po vajah iz teorije iger, ki sem jih izvajal na prvi stopnji bolonjskega študija finančne matematike na Fakulteti za matematiko in fiziko Univerze v Ljubljani. Vaje sem prevzel od Sergia Cabella Justa. Kar nekaj nalog iz te zbirke je njegovih, za kar sem mu globoko hvaležen. Te naloge so zajete v gradivu [1], tu pa so dodane rešitve. Zbirka je namenjena študentom na začetnih tečajih iz teorije iger in pokriva vso po- trebno snov za osnovni nivo. Velika večina teorije je zajeta v [3], v pomoč pa so lahko tudi ostala gradiva. Za lažji priklic pa je potrebna teorija povzeta tudi v okvirih pred sklopi nalog; tam so definirane tudi oznake pojmov. Vse naloge so rešene, bralcu pa seveda priporočam, da čimveč reši sam. V Ljubljani, junija 2015 Martin Raič martin.raic@fmf.uni-lj.si Kazalo 1. Strateške igre 7 2. Igre z mešanimi strategijami 13 3. Bayesove igre 27 4. Ekstenzivne igre 31 5. Kooperativne igre 39 REŠITVE 45 1. Strateške igre 47 2. Igre z mešanimi strategijami 58 3. Bayesove igre 81 4. Ekstenzivne igre 89 5. Kooperativne igre 101 Literatura 111 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 7 1. Strateške igre Nashevo ravnovesje. Ekvivalentnost iger. Dominacija. Nekaj primerov uporabe. Osnovni pojmi Preferenčna funkcija na množici A je preslikava iz A v linearno urejeno množico. Strateška igra (s čistimi strategijami) je določena: • z množico igralcev, recimo kar {1, 2, . . . , n}; • z množicami akcij (strategij): i-ti igralec lahko ubira akcije iz množice Ai; • s preferenčnimi funkcijami na profilih: profil pove, katero akcijo bo ubral vsak igralec in je torej n-terica (a1, . . . , an), kjer ai ∈ Ai. Vsak igralec ima svojo preferenčno funkcijo ui(a1, . . . , an). Preferenčne funkcije lahko slikajo v različne linearno urejene množice. Za profil a = (a1, a2, . . . , an) in akcijo bi ∈ Ai označimo: ui(a | bi) = ui(a1, . . . , ai−1, bi, ai+1, . . . , an) . Profil (a1, . . . , an) je čisto Nashevo ravnovesje, če za vsak i in vsak bi ∈ Ai velja ui(a) ≥ ui(a | bi). Profil (a1, . . . , an) je strogo čisto Nashevo ravnovesje, če za vsak i in vsak bi ∈ Ai \ {ai} velja ui(a) > ui(a | bi). 1. Razdeli ali ukradi. Dva igralca se potegujeta za nagrado, ki jo je možno tudi razdeliti na pol. Vsak igralec lahko izbere strategijo ‘ukradi’ ali ‘razdeli’. Če oba igralca izbereta ‘razdeli’, si nagrado razdelita. Če eden od igralcev izbere ‘ukradi’, drugi pa ‘razdeli’, prvi dobi vse, drugi pa nič. Če pa oba igralca izbereta ‘ukradi’, nobeden od njiju ne dobi nič. Modelirajte to kot strateško igro in poiščite čista Nasheva ravnovesja. Ali obstaja kakšno strogo Nashevo ravnovesje? 2. Dilema zapornikov. Dva storilca zalotijo pri nekem kaznivem dejanju in ju ločeno zaslišujejo. Vsak od njiju ima možnost, da molči ali pa zatoži sostorilca. Kazni, ki jih lahko dobi posamezen storilec, si sledijo glede na naslednje situacije (od najmilejše do najhujše): • storilec zatoži sostorilca, ki molči; • oba storilca molčita; • vsak od storilcev zatoži sostorilca; • storilec molči, sostorilec pa ga zatoži. Modelirajte to kot strateško igro in poiščite čista Nasheva ravnovesja. Ali obstaja kakšno strogo Nashevo ravnovesje? 8 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Ekvivalenca preferenčnih funkcij Preferenčni funkciji u in v na množici A (ki lahko slikata v različni linearno urejeni množici) sta ekvivalentni, če za poljubna a, b ∈ A velja ekvivalenca u(a) ≤ u(b) ⇐⇒ v(a) ≤ v(b). Definicija ekvivalentnosti se ne spremeni, če namesto ≤ vzamemo ≥, < ali >. Iz ekvivalentnosti preferenčnih funkcij sledi u(a) = u(b) ⇐⇒ v(a) = v(b). 3. Delo na skupnem projektu. Vsak od dveh sodelavcev se mora odločiti, ali bo v projekt vložil določeno vsoto, ki je za oba igralca enaka, ali pa ne bo vložil ničesar. Zaslužek od projekta je enak s(1 + r), kjer je s skupna vložena vsota in r > 0. Igralca si zaslužek vselej razdelita na pol. Modelirajte to kot strateško igro in poiščite čista Nasheva ravnovesja. Pri katerih vrednostih parametra r obstaja kakšna smiselna ekvivalenca med to igro in dilemo zapornikov? Glejte zgornjo definicijo ekvivalentnosti preferenčnih funkcij. Dominacija Akcija bi pri i-tem igralcu dominira akcijo ci, če za poljuben profil a velja ui(a | bi) ≥ ui(a | ci). Akcija bi strogo dominira akcijo ci, če za poljuben profil a velja ui(a | bi) > ui(a | ci). Akcije, ki so dominirane, ne morejo nastopati v strogih Nashevih ravnovesjih. Akcije, ki so strogo dominirane, ne morejo nastopati v Nashevih ravnovesjih. Če je torej akcija strogo dominirana, se (stroga) Nasheva ravnovesja igre uje- majo s (strogimi) Nashevimi ravnovesji igre z izločeno akcijo, ki je strogo do- minirana. Če igri odstranimo dominirano akcijo in če ima okleščena igra Nashevo rav- novesje, je to tudi Nashevo ravnovesje izvirne igre (ki pa ima lahko še kakšno Nashevo ravnovesje več). 4. Ali se lahko zgodi, da z odstranitvijo dominirane akcije izgubimo vsa Nasheva rav- novesja igre? 5. Dana je strateška igra za tri igralce, kjer ima i-ti igralec možni akciji Ti in Bi: T2 B2 T2 B2 T1 3, 4, 4 1, 3, 3 T1 4, 0, 5 0, 1, 6 . B1 8, 1, 4 2, 0, 6 B1 5, 1, 3 1, 2, 5 a3 = T3 a3 = B3 Določite dominacije in čista Nasheva ravnovesja igre. 6. Konstruirajte diskretno strateško igro za tri igralce brez čistih Nashevih ravnovesij. Preference vsakega igralca naj bodo za vse profile različne. M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 9 7. Dana je strateška igra za tri igralce z naslednjimi preferenčnimi funkcijami: X Y X Y X Y A 2, 0, 6 b, 1, 6 A 4, 0, 5 1, 3, 3 A 8, 5, 4 1, 6, 4 . B 8, b, 4 4, 2, a B 5, 1, 3 1, 2, 5 B 3, 4, 4 2, 5, 3 a3 = L a3 = M a3 = R Določite čista Nasheva ravnovesja in dominacije v odvisnosti od parametrov a in b. Največ koliko je čistih Nashevih ravnovesij in pri katerih vrednostih parametrov a in b je to število doseženo? 8. Dana je strateška igra za dva igralca. Množica akcij prvega je interval [0, 1], drugi igralec pa ima na voljo akciji in r. Preference so podane v naslednji tabeli: r . a1 ∈ [0, 1] 2 − 2a1, a1 a1, 1 − a1 Določite čista Nasheva ravnovesja igre. 9. Dana je strateška igra za dva igralca, kjer vsak igralec izbere točko iz daljice: D = {(x, y) ; x + y = 1, x ≥ 0, y ≥ 0} . Drugi igralec plača prvemu znesek, ki je enak skalarnemu produktu krajevnih vek- torjev izbranih točk. Določite čista Nasheva ravnovesja igre. 10. Iz spalnega naselja do poslovne četrti se mora vsak dan pripeljati v službo 5000 pre- bivalcev. Vsakemu je pomemben le čas potovanja: hitreje kot pride, bolje je. Vsak lahko izbere bodisi prevoz z osebnim avtomobilom bodisi prevoz z mestno železnico. Če z osebnim avtomobilom potuje x uslužbencev, je čas potovanja enak 20 + x/200 minut. Nadalje, če z javnim prevozom potuje y uslužbencev, je čas potovanja enak 15 + y/200 + 12/v minut, kjer je v število vlakov, ki peljejo. Posamezen vlak sprejme 2000 uslužbencev, kar pomeni, da v primeru, ko vlak izbere od 1 do 2000 uslužben- cev, pelje en vlak, če vlak izbere od 2001 do 4000 uslužbencev, peljeta dva vlaka, pri več kot 4000 uslužbencih pa peljejo trije vlaki. Modelirajte to kot strateško igro in poiščite čista Nasheva ravnovesja. Koliko časa v njih potujejo posamezni uslužbenci? 11. Dani sta naslednji omrežji enosmernih cest: GORI GORI a/100 45 a/100 45 START CILJ START 0 CILJ 45 a/100 45 a/100 DOLI DOLI 10 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Ob vsaki cesti je napisan čas potovanja, če se po njej pelje a avtomobilov (to si lahko zamišljamo tudi kot število avtomobilov na uro ali pa kot pretok bitov po računalniški mreži). 4000 voznikov (vsak s svojim avtomobilom) želi priti od starta do cilja. Vsak voznik je igralec in se mora odločiti, po kateri poti bo šel. a) Oglejmo si najprej levo omrežje. Ali obstaja Nashevo ravnovesje? Ali jih je več? Koliko časa porabi vsak avto od starta do cilja, če smo v Nashevem ravnovesju? b) Neverjetno hitra cesta, ki povezuje lokaciji GORI in DOLI, je končno dograjena (glej desno omrežje). Čas potovanja po novi cesti je enak nič. Kako je zdaj z Nashevimi ravnovesji? Koliko časa porabi vsak avto od starta do cilja? Ta fenomen je poznan kot Braessov paradoks. Zadostni pogoji za obstoj Nashevega ravnovesja Naj bodo množice akcij Ai kompaktne in konveksne podmnožice ev- klidskih prostorov. Nadalje naj imajo preferenčne funkcije ui vrednosti v R in naj bodo zvezne. Za vsak nabor akcij a1, . . . , ai−1, ai+1, . . . , an naj bo množica najboljših odgovorov: Bi(a1, . . . , ai−1, ai+1, . . . , an) := := a∗ ∈ A i i ; (∀ai ∈ Ai) ui(a1, . . . , ai−1, ai, ai+1, . . . , an) ≤ ≤ ui(a1, . . . , ai−1, a∗, a i i+1, . . . , an) konveksna. Tedaj obstaja vsaj eno Nashevo ravnovesje. Opomba. Konveksnost množice najboljših odgovorov je zagotovo iz- polnjena, če je za vsak nabor akcij a1, . . . , ai−1, ai+1, . . . , an izraz ui(a1, . . . , ai−1, ai, ai+1, . . . , an) konkavna funkcija spremenljivke ai. 12. Dana je igra za dva igralca. Akcije vsakega tvorijo interval [0, 1], preferenčni funkciji pa sta: u1(a1, a2) = a1(a1 − 3a2) , u2(a1, a2) = a2(2a1 + a2 − 1) . Kako je z množico Nashevih ravnovesij in pogoji izreka o obstoju Nashevega ravno- vesja? M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 11 Cournotov model duopola/oligopola Duopol je sestavljen iz dveh, oligopol pa iz več (recimo n) proizvajalcev istega produkta, od katerih vsak, ne da bi vedel za druge, določi količino qi ≥ 0 produkta, ki ga proizvaja. Če je skupna količina blaga, ki ga proizvajalci dajo na trg, enaka Q = q1 + q2 + · · · + qn, se na trgu oblikuje cena P (Q), kjer je P neka funkcija. Posamezen proizvajalec ima s proizvodnjo svojega blaga stroške Ci(qi). Njegov dobiček je tako enak: ui(q1, . . . , qn) = P (Q) qi − Ci(qi) . 13. Dan je Cournotov model oligopola, kjer je cena produkta določena s formulo P (Q) = (a − Q)+, funkcija proizvodnih stroškov posameznega proizvajalca pa je enaka Ci(q) = ciq. Tu je x+ := max{x, 0}. Privzamemo, da je a > 0 in ci > 0. a) Dokažite, da obstaja vsaj eno Nashevo ravnovesje. b) Za duopol poiščite vsa Nasheva ravnovesja. 14. Poiščite vsa čista Nasheva ravnovesja pri Cournotovem modelu duopola, kjer je cena produkta prav tako določena s formulo P (Q) = (a − Q)+, funkcija proizvodnih stroškov obeh proizvajalcev pa je enaka Ci(q) = q2. 15. Poiščite vsa čista Nasheva ravnovesja pri Cournotovem modelu oligopola, kjer je cena produkta spet določena s formulo P (Q) = (a − Q)+, funkcija proizvodnih stroškov pa je enaka za vse proizvajalce enaka Ci(q) = cq. 16. Za isti vir se poteguje n plemen. Če i-to pleme terja količino qi ≥ 0 tega vira, je njegov izkupiček enak: ui(q1, q2, . . . , qn) = qi(1 − Q)+ , kjer je Q = q1 + q2 + · · · + qn. Določite vsa Nasheva ravnovesja in pokažite, da obstaja profil (q1, . . . , qn), pri katerem vsa plemena dobijo več, kot bi pri katerem koli Nashevem ravnovesju. Bertrandov model duopola/oligopola Na razpis se prijavi n ponudnikov določenega blaga, vsak določi svojo ceno pi. Razpisodajalec kupi D(p) blaga po najnižji ponujeni ceni p = min{p1, . . . , pn}. Od vsakega ponudnika, ki ponudi minimalno ceno p, kupi enako, od ostalih pa ne kupi nič. Šele po končanem razpisu ponudniki proizvedejo količino blaga, ki jo bo razpisodajalec od njih kupil. Če i-ti ponudnik proda qi blaga, je njegov dobiček določen podobno kot pri Cournotovem modelu: ui(p1, . . . , pn) = pqi − Ci(qi) . 12 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 17. Poiščite vsa čista Nasheva ravnovesja v Bertrandovem modelu duopola, kjer je funk- cija povpraševanja enaka: 1 D(p) = , (1 + p)2 proizvodni stroški q enot blaga so za vsakega proizvajalca enaki q/4, dovoljene pa so le nenegativne celoštevilske cene. 18. Dražba druge cene z zaprtimi ponudbami. Za neki predmet se poteguje n kupcev. Vsak pripisuje predmetu dražbe neko subjektivno vrednost. Označimo te vrednosti z v1, v2, . . . , vn > 0. Na dražbi je vsak kupec pripravljen ponuditi določeno maksi- malno ceno: te cene označimo z b1, b2, . . . , bn ≥ 0. Če je cena, ki jo je določen kupec pripravljen ponuditi, strogo najvišja, ta kupec dobi predmet, zanj pa plača drugo najvišjo ceno (to se zgodi, če se cena na dražbi postopoma viša in brž ko preseže drugo najvišjo ceno, ostane le še kupec, ki je pripravljen ponuditi najvišjo ceno; temu kupcu se predmet tedaj proda). Primer, ko je isto najvišjo ceno pripravljeno ponuditi več kupcev (vez ), lahko in- terpretiramo na več načinov. Privzemimo, da v tem primeru žrebajo in vsak dobi predmet z enako verjetnostjo, nakar gledamo pričakovani dobiček. Modelirajte to kot strateško igro in opišite Nasheva ravnovesja. Pokažite, da ne glede na subjektivne vrednosti vi za vsakega kupca obstaja Nashevo ravnovesje, v katerem ta kupec zagotovo dobi dražbo. 19. Dražba prve cene z zaprtimi ponudbami. Spet se za neki predmet se poteguje n kupcev, ki pripisujejo predmetu subjektivne vrednosti v1, v2, . . . , vn > 0, zanj pa so pripravljeni ponuditi cene b1, b2, . . . , bn ≥ 0. Tokrat pa zmagovalec dražbe za predmet plača polno ceno, ki jo je pripravljen ponuditi (to se zgodi, če se cena na dražbi postopoma niža). Opišite Nasheva ravnovesja igre, ki izhaja iz take dražbe. M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 13 2. Igre z mešanimi strategijami Preferenčne funkcije za loterije, dobljene iz koristnostnih funkcij za čiste strategije. Mešano Nashevo ravnovesje, princip indiferentnosti. Izločanje s pomočjo stroge dominacije. Bimatrične igre, igre m × 2. Matrične igre, stopnja varnosti, vrednost igre. Kvadratne, diagonalne in simetrične matrične igre. Loterije in funkcije koristnosti Loterija je verjetnostna porazdelitev na končni (ali števno neskončni) množici A, recimo na množici akcij. Opišemo jo z verjetnostno shemo: a1 a2 a3 · · · , p1 p2 p3 · · · kjer je seveda p1 + p2 + p3 + · · · = 1. Posamezen element a množice A identificiramo z loterijo δa, ki ima v točki a verjetnost 1. Funkcija koristnosti na množici A je preslikava iz A v R. Vsaki funkciji kori- stnosti u na končni ali števno neskončni množici A lahko priredimo preferenčno funkcijo U na množici loterij na A, ki loteriji priredi pričakovano vrednost funk- cije u. Natančneje, če loterija π ustreza shemi od prej, definiramo: U (π) = p1 u(a1) + p2 u(a2) + p3 u(a3) + · · · To je edina razširitev funkcije u do afine funkcije na množici loterij. 1. Na množici A = {a, b, c} so definirane naslednje funkcije koristnosti: u(a) = 1 , v(a) = 3 , w(a) = 3 , u(b) = 2 , v(b) = 5 , w(b) = 5 , u(c) = 4 , v(c) = 9 , w(c) = 8 . Naj bodo U , V in W pripadajoče preferenčne funkcije na množici loterij na A. a b c a) Za loterijo π = . . . izračunajte U (π), V (π) in W (π). 0 32 0 5 0 18 b) Funkcije u, v in w so kot preferenčne funkcije ekvivalentne. Kaj pa U , V in W ? 2. Dokažite, da funkciji koristnosti u in v na isti množici določata ekvivalentni pre- ferenčni funkciji natanko tedaj, ko je v = cu + b za neki c > 0 in b ∈ R. Zaradi enostavnosti lahko privzamete, da je množica A končna. 14 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Mešanje strategij Mešana razširitev strateške igre, katere preferenčne funkcije so tudi funkcije koristnosti, je igra, katere akcije so loterije na akcijah prvotne igre (mešane strategije), preferenčne funkcije pa so definirane tako, da, če i-ti igralec igra mešano strategijo: a π i1 ai2 ai3 · · · i = , pi1 pi2 pi3 · · · velja: Ui(π1, π2, . . . , πn) = p1j p · · · p u , a , . . . , a ) . 1 2j2 njn i(a1j1 2j2 njn j1,j2,...,jn To si lahko predstavljamo tudi tako, da vsakemu profilu iz loterij priredimo loterijo na profilih, pri čemer privzamemo, da igralci mešajo neodvisno drug od drugega. Vrednost preferenčne funkcije Ui na danem profilu je vrednost naravne razširitve funkcije ui na prirejeni loteriji iz profilov. Nashevim ravnovesjem mešane razširitve igre pravimo mešana Nasheva rav- novesja igre. Vsaka strateška igra s končno mnogo akcijami ima vsaj eno mešano Nashevo ravnovesje. 3. Dva igralca igrata igro, pri kateri vsak izmed njiju pokaže eno stran svojega kovanca. Če oba pokažeta isto stran (oba cifro ali oba grb), drugi igralec plača prvemu en evro, sicer pa plača ta znesek prvi drugemu. Modelirajte to kot strateško igro. Pokažite, da čistih Nashevih ravnovesij ni, in poiščite mešana Nasheva ravnovesja. Karakterizacija mešanega Nashevega ravnovesja Profil mešanih strategij (π1, π2, . . . , πn) je mešano Nashevo ravnovesje natanko tedaj, ko za vsak i = 1, 2, . . . , n velja, da so vrednosti: Ui(π1, . . . , πi−1, a, πi+1, . . . , πn) , za vse a s πi(a) > 0 med seboj enake (princip indiferentnosti) in večje ali enake vrednostim zgornjega izraza za ostale a. 4. Poiščite mešana Nasheva ravnovesja igre: X Y A 1, 0 0, 0 . B 0, 0 2, 1 5. V neki študiji (Palacios-Huerta: Professionals play minimax, Review of Economic Studies 70 (2003), 395–415) so opazovali izvajanje več kot 1400 enajstmetrovk pri M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 15 nogometu. Tipično strelec meri levo ali desno, vratar pa prav tako skoči na svojo levo ali desno stran. V spodnji tabeli so podane empirične verjetnosti zadetka za vse možne kombinacije: Vratar L D . . . L 94 97% 58 30% Strelec . . D 69 92% 92 91% (v resnici je bila študija še natančnejša in je razlikovala levo- in desnonožne strelce: oznaki L in D pomenita levo oz. desno stran pri desnonožnih strelcih, pri levonožnih pa sta strani zamenjani; študija je torej privzela, da vratarji dobro poznajo strelce). Modelirajte to kot strateško igro z mešanimi strategijami (ob predpostavki, da se strelec in vratar vnaprej odločita, kaj bosta storila) in poiščite Nasheva ravnovesja. Primerjajte to z opaženimi frekvencami: L D L D Strelci: . . Vratarji: . . 39 98% 60 02% 57 69% 42 31% 6. Določite, pri katerih vrednostih parametrov a, b, c, d, e in f je profil: T B C R , 3/4 1/4 1/3 2/3 mešano Nashevo ravnovesje igre: L C R T 1, 2 3, 3 1, 1 . M a, b c, 3 2, 4 B d, 4 e, f 0, 7 7. Poiščite mešana Nasheva ravnovesja igre: X Y A a, a 2, 4 . B 1, 3 a, a v odvisnosti od parametra a. 8. Določite mešana Nasheva ravnovesja igre: X Y Z A 0, 4 3, 3 5, 0 . B 1, 3 2, 7 3, 5 C 3, 0 1, 2 1, 3 16 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Izločanje mešanih strategij s pomočjo (stroge) dominacije Akcija (čista strategija), ki je strogo dominirana s kakšno mešano strategijo, ne more nastopati v mešanem Nashevem ravnovesju (t. j. njen delež je enak nič). Mešana Nasheva ravnovesja igre, v kateri se to zgodi, se ujemajo z mešanimi Nashevimi ravnovesji igre z izločeno akcijo. Tako lahko tudi mešane strategije izločamo zaporedoma. Če ima igra mešano Nashevo ravnovesje, obstaja tudi mešano Nashevo ravno- vesje, kjer dominirane akcije ne nastopajo. Z drugimi besedami, če je dovolj poiskati vsaj eno Nashevo ravnovesje (ne pa vseh), lahko dominirane akcije izločimo. 9. Raziščite, katere akcije v prejšnji nalogi so strogo dominirane; za vsako tako akcijo poiščite še vse mešane strategije, ki jo strogo dominirajo. A B 10. Denimo, da mešana strategija . . strogo dominira čisto strategijo C. Po- 0 4 0 6 iščite mešano strategijo, ki strogo dominira mešano strategijo A B C D . . . . in ne vsebuje akcije C. 0 15 0 25 0 5 0 1 11. Določite mešana Nasheva ravnovesja igre: X Y Z A 4, 2 3, 3 1, 5 . B 0, 4 4, 1 2, 0 C 1, 4 3, 9 1, 7 12. Poiščite vsaj eno mešano Nashevo ravnovesje igre: X Y Z W A 3, 6 3, 5 4, 8 5, 7 B 3, 6 3, 5 5, 0 4, 3 C 2, 6 3, 5 5, 0 4, 3 D 3, 6 2, 9 5, 0 5, 7 E 2, 6 4, 5 3, 8 7, 7 F 5, 6 1, 9 9, 0 1, 3 13. Določite mešana Nasheva ravnovesja igre: X Y Z A 4, 2 3, 5 1, 3 . B 0, 0 4, 1 2, 4 C 1, 4 3, 1 3, 2 Ali je v tej igri kakšna akcija (strogo) dominirana? M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 17 14. Poiščite vsa mešana Nasheva ravnovesja igre: X Y Z W A 0, 0 3, 3 3, 2 3, 1 . B 2, 1 0, 0 2, 3 3, 0 C 3, 3 4, 2 0, 0 3, 2 15. Dana je igra za dva igralca, ki imata oba na voljo vsak svoj nabor samih različnih kart. Oba nabora sta enaka. Vsaka karta ima neko strogo pozitivno vrednost. Hkrati pokažeta vsak svojo karto in če sta karti enaki, drugi igralec plača prvemu vrednost karte. Sicer nihče ne plača nič. Modelirajte to kot strateško igro in poiščite mešana Nasheva ravnovesja. 16. Poiščite mešana Nasheva ravnovesja igre: X Y X Y T 2, 1, 1 2, 2, 1 T 2, 1, 0 2, 4, 0 . B 3, 1, 1 0, 0, 1 B 6, 1, 0 3, 2, 2 a3 = L a3 = R 17. Poiščite mešana Nasheva ravnovesja igre: X Y X Y T 1, 2, 3 1, 1, 3 T 1, 2, 4 1, 3, 1 . B 1, 1, 4 0, 2, 2 B 0, 4, 2 1, 2, 3 a3 = L a3 = R Namig: raziščite, kdaj se prvemu igralcu določene akcije ne splača igrati. 18. Trije igralci hkrati vržejo vsak svoj kovanec. Če vsi trije vržejo enako, nihče ne plača nič. Če eden od igralcev vrže grb, druga dva pa cifro, ta dva tistemu, ki je vrgel grb, plačata vsak po en evro. Če pa eden od igralcev vrže cifro, druga dva pa grb, ta dva tistemu, ki je vrgel cifro, plačata vsak po dva evra. Poiščite vsa mešana Nasheva ravnovesja, pri katerih vsi igralci, ki strogo mešajo, mešajo z enakimi verjetnostmi. 19. Podjetje povabi k skupnemu projektu pet sodelavcev. Vsak sodelavec lahko priza- devno sodeluje, kar ga stane eno enoto, ali pa lenari, kar ga ne stane nič. Če je pri projektu p prizadevnih sodelavcev, le-ti ustvarijo dobiček v višini 15 ln(1 + p). Dobiček si vseh pet sodelavcev razdeli na enake dele (ne glede na to, ali sodelujejo ali ne). a) Modelirajte to kot strateško igro in poiščite čista Nasheva ravnovesja. Koliko jih je? b) Ali obstaja kakšno mešano ravnovesje, kjer vsi sodelavci prizadevno sodelujejo z enakimi verjetnostmi? 18 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 20. V soseski se zgodi zločin, ki ga vidi n mimoidočih. Vsak izmed njih ima možnost, da pokliče policijo. To predstavlja dodatno delo in tveganje, kar vsak mimoidoči oceni s c; ta vrednost se odšteje od njegove koristnostne funkcije. Če nihče ne pokliče, to predstavlja sramoto, ki od koristnostne funkcije vsakega mimoidočega odšteje s. Privzemimo, da je s > c > 0. a) Modelirajte to kot strateško igro. b) Poiščite čista Nasheva ravnovesja. c) Določite simetrična mešana Nasheva ravnovesja (Nashevo ravnovesje je sime- trično, če vsi igralci uberejo isto mešano strategijo). d) Pokažite, da pri Nashevem ravnovesju iz prejšnje točke verjetnost, da vsaj en mimoidoči pokliče policijo, pada s številom mimoidočih. 21. Prizor iz filma A Beautiful Mind, biografskega filma o Johnu Nashu: skupini fantov se v baru pridruži skupina deklet, med katerimi izstopa privlačna blondinka. Vsak fant ima na voljo dve akciji: lahko gre osvajat blondinko ali pa manj privlačno dekle. Če gre osvajat manj privlačno dekle, jo zagotovo dobi; korist od tega je enaka 2. Če pa gre osvajat blondinko, uspeh ni zagotovljen: blondinka bo namreč na slepo izbrala samo enega od tistih, ki jo bodo šli osvajat. Fant, ki dobi blondinko, ima korist 3, fant, ki gre osvajat blondinko, a je ne dobi, pa ima korist 0. Kot korist pri akciji, da gre fant osvajat blondinko, štejemo matematično upanje glede na blondinkin odgovor. a) Dokažite, da v mešanem Nashevem ravnovesju vsi fantje, ki gredo s strogo pozitivno verjetnostjo osvajat blondinko, to počnejo z enakimi verjetnostmi. Namig: za poljubna dva zapišite princip indiferentnosti in primerjajte. b) Dokažite, da za poljubno neprazno podmnožico fantov moči m obstaja mešano Nashevo ravnovesje, pri katerem gredo fantje iz te podmnožice osvajat blon- dinko z verjetnostjo qm > 0, ostali pa gredo osvajat manj privlačna dekleta. Dokažite, da je ta verjetnost natančno določena z m in da torej ni odvisna od skupnega števila fantov. Koliko mešanih Nashevih ravnovesij ima torej igra? c) Izračunajte q1, q2 in q3. M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 19 Igre m × 2 in 2 × m Če ima drugi igralec na voljo le dve akciji (recimo X in Y ), pogoji za Nashevo ravnovesje, ki jih določa koristnostna funkcija prvega igralca (U1), ustrezajo X Y zgornji ovojnici daljic q → U1 i, . V okviru te ovojnice potem 1 − q q pogledamo, kje koristnostna funkcija drugega igralca (U2) ustreza standardnim kriterijem: • V profilih, ki ustrezajo posameznemu krajišču ovojnice, mora biti U2 večja ali enaka, kot če bi zamenjali akcijo drugega igralca. • V profilih, ki ustrezajo notranjosti ovojnice, mora biti U2 enaka za obe akciji drugega igralca (posebej gledamo notranjosti daljic in prelome). Analogno obravnavamo tudi bimatrične igre, kjer ima prvi igralec na voljo le dve akciji. Konstrukcija zgornje ovojnice • Kolikor zmoremo, izločimo daljice (akcije), ki so strogo dominirane z mešanico ostalih: le-teh ni v zgornji ovojnici. Vsekakor pa pri daljicah z enakimi strminami pustimo le tisto, ki leži najvišje. Enake daljice gledamo skupaj, kot eno samo daljico (dejstvo, da izvirajo iz različnih akcij prvega igralca, pride do izraza šele pri pogojih, ki jih določa U2). • Daljice uredimo po strminah U1(i, Y ) − U1(i, X). • Začnemo z daljico z najmanjšo strmino, ki je zgornja ovojnica same sebe. • Ko smo že konstruirali zgornjo ovojnico prvih nekaj daljic, za vsako na- slednjo daljico najprej pogledamo, ali je morda v X (t. j. pri q = 0) nad zgornjo ovojnico prejšnjih daljic. V tem primeru je povsod nad zgornjo ovojnico, torej strogo dominira vse daljice iz nje, zato vse prejšnje daljice izločimo: v novi zgornji ovojnici je samo nova daljica. • Če je nova daljica v Y pod zgornjo ovojnico, jo daljica, ki je v Y na zgor- nji ovojnici, strogo dominira. Novo daljico lahko tako izločimo, zgornja ovojnica ostane nespremenjena. • Sicer nova daljica seka zgornjo ovojnico prejšnjih v natanko eni točki. Presečišča nove daljice z daljicami, ki imajo v ovojnici vsaj eno točko, si sledijo v enakem vrstnem redu kot njihove strmine, zato lahko iščemo z binarno bisekcijo. • Nova zgornja ovojnica daljic je sestavljena iz zgornje ovojnice prejšnjih daljic do presečišča in nove daljice od presečišča naprej. Daljice, ki imajo vse točke v zgornji ovojnici naprej od presečišča z novo daljico, izločimo (le-te so strogo dominirane). 20 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 22. Poiščite mešana Nasheva ravnovesja igre: X Y A 4, 1 0, 3 B 2, 3 1, 5 . C 0, 0 6, 2 D 2, 2 3, 1 E 6, 2 −6, 0 23. Poiščite mešana Nasheva ravnovesja igre: I J K L M N A 2, 5 3, 4 4, 9 4, 7 2, 6 2, 3 B 3, 11 2, 12 5, 8 3, 2 4, 10 4, 1 C 3, 5 4, 1 4, 10 5, 12 2, 8 2, 12 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 21 Matrične igre Matrične igre so igre za dva igralca s končno mnogo akcijami in ničelno vsoto: pri vsakem paru akcij (in posledično pri vsakem profilu) je dobitek drugega igralca nasprotno enak dobitku prvega. Dobitke v taki igri lahko predstavimo z matriko iz dobitkov prvega igralca, recimo A = [aij]m,n . Če akcije prvega i=1,j=1 igralca označimo z V1, . . . , Vm, akcije drugega pa z S1, . . . , Sn, torej velja: U1(Vi, Sj) = aij , U2(Vi, Sj) = −aij . Mešane strategije lahko opišemo kar z vektorji. Če mešanima strategijama π in ρ ustrezata vektorja p in q tako kot spodaj:     p1 q1 V  p2  S q2  π = 1 V2 · · · Vm ↔ p = 1 S2 · · · Sn  .  , ρ = ↔ q =  .  , p  .   .  1 p2 · · · pm . q1 q2 · · · qn .     pm qn velja U1(π, ρ) = pTAq. Pri matričnih igrah ima posamezen igralec pri vseh Nashevih ravnovesjih enak dobitek. To je maksimalni dobitek, ki mu je zagotovljen ne glede na to, kaj dela drugi igralec. Pravimo mu stopnja varnosti za danega igralca. Stopnji varnosti za prvega igralca pravimo tudi vrednost igre. Stopnja varnosti za prvega igralca je enaka v = maxp minq pTAq = = maxp minj pTAej, kjer je ej vektor, ki ima j-to komponento enako 1, druge pa 0. Mešana strategija p∗ je max-min, če velja minq(p∗)TAq = maxp minq pTAq. Stopnja varnosti za drugega igralca je enaka maxq minp(−pTAq) = = − minq maxp pTAq = −v. Mešana strategija q∗ je min-max, če velja maxp pTAq∗ = minq maxp pTAq. Profil (p∗, q∗ je mešano Nashevo ravnovesje natanko tedaj, ko je strategija p∗ max-min, strategija q∗ pa min-max. 24. Določite vrednost in eno mešano Nashevo ravnovesje v matrični igri: 8 5 2 2 4 4 3 4   . 6 3 0 9 22 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Matrične igre m × 2 Tako kot pri splošnih igrah za dva igralca lahko tudi tu akcijam prvega igralca priredimo daljice in poiščemo zgornjo ovojnico. Nashevo ravnovesje je na mini- mumu zgornje ovojnice (to je max v min-max strategiji drugega igralca; prvi igralec pa meša tiste akcije, ki so vpletene v ta minimum). Namesto konstrukcije cele zgornje ovojnice pa lahko upoštevamo tudi dejstvo, da je min-max dosežen v eni izmed naslednjih točk: • v levem krajišču daljice s pozitivno ali ničelno strmino; • v desnem krajišču daljice s pozitivno ali ničelno strmino; • na presečišču daljice s pozitivno ali ničelno strmino in daljice z negativno ali ničelno strmino. Min-max je dosežen v tistih izmed zgoraj omenjenih točk, ki ležijo na zgornji ovojnici, ali, ekvivalentno, tam, kjer je vrednost koristnostne funkcije najvišja. Ta vrednost je tudi vrednost igre. 25. Poiščite mešana Nasheva ravnovesja in vrednost matrične igre: 4 3 2 4   5 2 26. Poiščite mešana Nasheva ravnovesja in vrednost matrične igre: 2 4 6 4 0 . 6 5 0 3 12 27. Določite vrednost matrične igre: 2 3 5 4 6 4 2 3 .   0 1 2 3 1 2 3 4 4 3 2 1 28. Določite vrednost matrične igre    . 2 1 4 3   3 4 1 2 Namig: računanje skoraj ni potrebno. 5 a b 29. Naj bo a, b, c, d ∈ R. Dokažite, da je vrednost matrične igre a a b   enaka c c d a b vrednosti matrične igre . c d M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 23 Kvadratne matrične igre s stičnimi točkami v simpleksu Pri kvadratnih matričnih igrah se splača najprej ravnati, kot da oba igralca strogo mešata vse akcije. Po principu indiferentnosti so mešana Nasheva rav- novesja v tem primeru stične točke: pTA = α1T (t. j. U2(p, j) so enaki za vse j) (1) Aq = β1 (t. j. U1(i, q) so enaki za vse i) . (2) Tu je 1 stolpec iz samih enic. Rešitve iščemo v prostoru H = {p ; pT1 = 1} = {q ; 1Tq = 1}, prave pa bodo, če se bodo nahajale v simpleksu ∆ = {p ∈ H ; p ≥ 0}. Neenakost med vektorji je tu mišljena po komponentah. Če imata obe enačbi rešitev v H, sta α in β enolično določena ter velja α = β. Če imata obe enačbi rešitev v ∆, je v = α = β, (p, q) pa je mešano Nashevo ravnovesje. Če je rešitev obeh enačb enolična (glede na p, q ∈ H) ter če p in q ležita v notranjosti simpleksa ∆, je to edino mešano Nashevo ravnovesje. Če je matrika A obrnljiva ter v komponentah nobenega od vektorjev 1TA−1 1 in A−11 ne pride do menjave predznaka, je v = ter pT = v1TA−1 in 1TA−11 q = vA−11. Opomba. Enačbi (1) in (2) imata lahko enolično rešitev v R × H, tudi če matrika A ni obrnljiva. Ključna je namreč obrnljivost matrike ˜ 0 1T A = . Naslednje trditve so ekvivalentne: 1 A • ˜ A je obrnljiva. • Sistem (1) ima natanko eno rešitev v α ∈ R, p ∈ H. • Sistem (2) ima natanko eno rešitev v β ∈ R, q ∈ H. −β 1 1 Sistem (1) je namreč možno zapisati v obliki ˜ A = , sistem (2) pa v obliki ˜ AT −α = . q 0 q 0  2 4 0 30. Izračunajte vrednost igre −2 6 2  . 4 −1 3  1 −1 1  31. Izračunajte vrednost igre −8 4 0 .   3 −1 −1 32. Alfred in Bernard igrata igro, pri kateri oba hkrati izbereta naravno število od 1 do n. Če oba izbereta enako, Bernard plača Alfredu en evro. Če Bernard izbere število, ki je za eno večje od Alfredovega, Alfred Bernardu plača en evro. Sicer nihče ne plača nič. a) Poiščite mešana Nasheva ravnovesja igre, v katerih oba igralca strogo mešata vse akcije. b) Ali obstaja kakšno mešano Nashevo ravnovesje, kjer kateri od igralcev kakšne akcije ne meša? 24 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Vsako iskanje vrednosti igre se da (z manjšo ali večjo zahtevnostjo) prevesti na eno ali več kvadratnih iger z enoličnima stičnima točkama v simpleksu. • Če ima matrika več vrstic kot stolpcev, lahko odstranimo toliko vrstic, kot znaša razlika, ni pa s tem povedano, katere. • Če ima matrika več stolpcev kot vrstic, lahko odstranimo toliko stolpcev, kot znaša razlika, ni pa s tem povedano, katere. • Če ima enačba (1) nič ali pa neskončno rešitev v H, lahko odstranimo neko vrstico. • Če ima enačba (2) nič ali pa neskončno rešitev v H, lahko odstranimo neki stolpec. • Če ima enačba (1) rešitev v H \∆, lahko odstranimo neko vrstico. Če ima tedaj enačba (2) rešitev v ∆, lahko odstranimo neko vrstico, ki ustreza negativni komponenti v p. • Če ima enačba (2) rešitev v H \∆, lahko odstranimo neki stolpec. Če ima tedaj enačba (1) rešitev v ∆, lahko odstranimo neki stolpec, ki ustreza negativni komponenti v q. • Če lahko odstranimo določeno število vrstic, ne vemo pa, katere, je vre- dnost igre enaka maksimumu vrednosti iger z matrikami, ki imajo od- stranjenih ustrezno število vrstic. • Če lahko odstranimo določeno število stolpcev, ne vemo pa, katere, je vrednost igre enaka mimimumu vrednosti iger z matrikami, ki imajo od- stranjenih ustrezno število stolpcev. Sicer pa je iskanje vrednosti igre predmet linearnega programiranja. Pojasnila • Brž ko ima matrika več vrstic kot stolpcev, ima enačba (1) nič ali pa neskončno rešitev. • Brž ko ima enačba (1) nič ali pa neskončno rešitev, obstaja tak vektor δ = 0 z 1Tδ = 0, da je δTA = 0. Če je pri nekem p dosežena vrednost igre (maksimum minimuma), se to ohrani, če p premaknemo za kak večkratnik vektorja δ. Potem pa se lahko premaknemo za tak večkratnik, da se znajdemo na robu simpleksa, kar pomeni, da smo eno komponento vektorja p postavili na nič; z drugimi besedami, odstranili smo eno vrstico. • Naj enačbo (1) reši p0 / ∈ ∆. Vzemimo poljuben p1 ∈ ∆ in naj bo mink pTAe Ae Ae 1 k = pT 1 j . Ker je pT 0 k enako za vse k, mora tudi za vsak p na poltraku {(1−t)p0 +tp1} veljati mink pTAek = pTAej . Če je p1 v notranjosti simpleksa ∆, poltrak seka rob simpleksa v dveh točkah, recimo p2 = (1 − t2)p0 + t2p1 in p3 = (1 − t3)p0 + t3p1, pri čemer lahko privzamemo, da je 0 < t2 < 1 < t3. Če je pTAe Ae Ae Ae Ae Ae Ae Ae Ae Ae 1 j ≥ pT 0 j , je tudi pT 3 j ≥ pT 1 j , torej mink pT 3 k ≥ mink pT 1 k . Če pa je pT 1 j ≤ pT 0 j , je pT 2 j ≥ pT 1 j , torej mink pTAe Ae 2 k ≥ mink pT 1 k . To pa pomeni, da je maxp mink pT Aek zagotovo dosežen na robu simpleksa. • Če privzamemo prejšnje in če obstaja še q1 ∈ ∆, ki reši (2), velja pTAe Aq Aq Ae 1 j ≤ pT 1 1 = pT 0 1 = pT 0 j , torej velja prejšnja druga možnost, se pravi mink pTAe Ae 2 k ≥ mink pT 1 k . Od tod dobimo, da je maxp mink pT Aek dosežen v točki oblike p0 + tδ, kjer je 1Tδ = 0, t > 0 pa je najmanjši tak, da je p0 + tδ ∈ ∆. Pri takem vektorju pa mora biti ena izmed komponent, ki je pri p0 negativna, enaka nič. Tisto vrstico lahko torej izločimo. • Pri vseh zgornjih argumentih lahko zamenjamo (1) in (2), hkrati pa tudi vrstice in stolpce.  0 3 3  33. Izračunajte vrednost igre 4 −5 −1  . −8 7 −1 Vrednost igre 2 × 2 a b Če v matriki ni nobene stroge dominacije in niso vsi njeni c d elementi enaki, ima pripadajoča matrična igra vrednost: ad − bc . a − b − c + d M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 25 4 3 34. Določite vrednost matrične igre v odvisnosti od parametra x. −1 x 35. Določite vrednost diagonalne matrične igre, t. j. take z diagonalno matriko. 36. Matrična igra je simetrična, če je njena matrika poševno simetrična, t. j. AT = −A. Določite vrednost take igre. 26 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 27 3. Bayesove igre Bayesovo ravnovesje. Obravnava dominacij. Igre, podane z apriornimi verjetnostmi. Bayesova igra je igra z nepopolno informacijo, ki jo sestavljajo: • množica igralcev in za vsakega igralca množica akcij; • množica stanj in za vsako stanje strateška igra s koristnostnimi funkci- jami; • za vsakega igralca signalna funkcija, ki vsako stanje preslika v določen signal, in za vsak signal verjetnostna porazdelitev na množici stanj, ki se preslikajo v dani signal (torej aposteriorne verjetnosti). Signal torej predstavlja informacijo o stanju igre, ki jo dobi igralec. Vsaki Bayesovi igri priredimo strateško igro s popolno informacijo, kjer so: • igralci pari (igralec, signal) iz izvirne Bayesove igre; • koristnostne funkcije pričakovane vrednosti koristnostnih funkcij izvirne Bayesove igre glede na dane aposteriorne verjetnosti. Zaradi lažjega razločevanja akcijam v prirejeni strateški igri navadno v indeksu dodamo signale, ki jim pripadajo. Bayesovo ravnovesje (čisto ali mešano) je ustrezno Nashevo ravnovesje prirejene strateške igre s popolno informacijo. 1. Bayesova igra za dva igralca ima dve stanji, ω1 in ω2. Prvi igralec dobi isti od obeh stanj isti signal in verjame, da je igra v stanju ω1 z verjetnostjo 1/3, v stanju ω2 pa z verjetnostjo 2/3. Drugi igralec pa dobi od vsakega stanja drugačen signal. Prvi igralec lahko igra potezi A ali B, drugi pa potezi L ali D. Dobitki pri posameznih stanjih in potezah so prikazani spodaj: Stanje ω1: Stanje ω2: L D L D A 2, 3 5, 1 A 5, 1 2, 2 B 1, 1 4, 3 B 10, 2 7, 1 Poiščite mešana Bayesova ravnovesja igre. Dominacije pri Bayesovih igrah Če je neka akcija v posameznem stanju strogo dominirana v smislu strateških iger z mešanimi strategijami, še ne pomeni, da jo lahko izločimo iz Bayesove igre, saj tovrstna dominacija ne implicira nujno (stroge) dominacije v prirejeni strateški igri s popolno informacijo. Pač pa dominacija v prirejeni strateški igri s popolno informacijo sledi iz dominacije v vseh stanjih Bayesove igre, ki pripadajo danemu signalu. Implicirana dominacija je stroga, če je v izvirni Bayesovi igri stroga za vsaj eno stanje s strogo pozitivno aposteriorno verje- tnostjo. 28 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 2. Bayesova igra za dva igralca ima tri stanja, ω1, ω2 in ω3. Prvi igralec ve, v katerem stanju je igra, drugi igralec pa ne dobi nobene informacije o stanju, pač pa verjame v verjetnosti stanj Pr(ω1) = 1/2, Pr(ω2) = 1/4, Pr(ω3) = 1/4. Prvi igralec lahko igra potezi A ali B, drugi pa potezi L ali D. Dobitki pri posameznih stanjih in potezah so prikazani spodaj: Stanje ω1: Stanje ω2: Stanje ω3: L D L D L D A 3, 1 4, 2 A 0, 2 4, 5 A 0, 0 1, 1 B 2, 3 1, 4 B 3, 4 1, −11 B 2, 2 5, 3 Poiščite mešana Bayesova ravnovesja igre. 3. Bayesova igra za dva igralca ima tri stanja, ω1, ω2 in ω3. Prvi igralec dobi en signal od stanja ω1 in drugega od stanj ω2 in ω3; v slednjem primeru verjame, da je igra v stanju ω2 s pogojno verjetnostjo 3/4 in v stanju ω3 s pogojno verjetnostjo 1/4. Drugi igralec pa dobi en signal od stanja ω2 in drugega od stanj ω1 in ω3; v slednjem primeru verjame, da je igra v stanju ω1 z verjetnostjo 1/3 in v stanju ω3 z verjetnostjo 2/3. Dobitki pri posameznih stanjih in akcijah so prikazani spodaj: Stanje ω1: Stanje ω2: Stanje ω3: L R L R L R T 2, 2 3, 5 T 2, 2 1, 1 T 1, 2 2, 8 B 1, 5 2, 8 B 2, 4 3, 2 B 2, 5 3, 2 Poiščite mešana Bayesova ravnovesja igre. 4. Anita želi prodati svoj avto, Bojan pa ga želi kupiti. Avto je lahko v dobrem ali slabem stanju. Anita pozna njegovo stanje, Bojan pa ne, vendar misli, da je avto v dobrem stanju z verjetnostjo 2/3, v slabem pa z verjetnostjo 1/3. Če je avto v dobrem stanju, ima vrednost 6 za Anito in 9 za Bojana, če pa je v slabem stanju, ima vrednost 0 za Anito in 3 za Bojana. Označimo s c > 0 kupnino za avto. Privzamemo, da se obe stranki vsaka zase odločita, ali gresta v prodajo oz. nakup; kupčija je sklenjena, če se oba odločita pritrdilno. a) Modelirajte to kot Bayesovo igro. b) Kateri profili niso čista Bayesova ravnovesja pri nobeni ceni c? c) Pri katerih cenah c obstaja Bayesovo ravnovesje, pri katerem je kupčija lahko sklenjena (bodisi za dober bodisi za slab avto)? d) Pri katerih cenah je Bojan indiferenten med nakupom in odstopom pri vseh strategijah, ki se tedaj (t. j. pri tej ceni) pri obeh Bojanovih akcijah splačajo Aniti? M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 29 Pri Bayesovi igri lahko podamo tudi apriorne verjetnosti Pr(ω), t. j. verje- tnosti stanj, ki jih posamezen igralec privzema, preden dobi signal. Če je τ signalna funkcija in τ (ω) = s, so aposteriorne verjetnosti ustrezne pogojne verjetnosti: Pr(ω) Pr(ω | τ = s) = . Pr(τ = s) Na to lahko gledamo tudi kot na poseben primer Bayesove formule. 5. Bayesova igra za dva igralca ima tri stanja, ω1, ω2 in ω3. Prvi igralec dobi en signal od stanja ω1, drugega pa od stanj ω2 in ω3. Drugi igralec pa dobi en signal od stanja ω2, drugega pa od stanj ω1 in ω3. Na začetku oba igralca verjameta v verjetnosti stanj Pr(ω1) = 1/4, Pr(ω2) = 1/4, Pr(ω3) = 1/2. Prvi igralec lahko igra potezi A ali B, drugi pa potezi L ali D. Dobitki pri posameznih stanjih in potezah so prikazani spodaj: Stanje ω1: Stanje ω2: Stanje ω3: L D L D L D A 2, 0 3, 1 A 1, 1 1, 3 A 7, 0 1, 4 B 1, 5 0, 7 B 1, 2 1, 4 B 1, 3 5, 1 Poiščite mešana Bayesova ravnovesja igre. 6. Dva igralca dobita vsak po eno izmed treh možnih nagrad; nagradi, ki ju dobita, sta različni in izbrani na slepo. Vsak igralec ocenjuje vrednost nagrade po svoje – v spodnji tabeli so podane subjektivne vrednosti posameznih nagrad: Nagrada P1 P2 A 1 4 B 3 1 C 4 2 Po razdelitvi igralca lahko izmenjata svoji nagradi, če se oba s tem strinjata; pri tem pa posamezen igralec ve samo, katero nagrado je dobil on, ne pa tudi, katero nagrado je dobil drugi igralec. a) Modelirajte to kot Bayesovo igro. b) Določite, do katerih menjav lahko pride v čistih Bayesovih ravnovesjih. c) Ali obstaja čisto Bayesovo ravnovesje, pri katerem nikoli ne pride do menjave? 7. Dva igralca sta spet dobila vsak svojo nagrado in spet sta bili nagradi izbrani na slepo in brez vračanja iz iste množice nagrad. Tokrat oba igralca enako ocenju- jeta vrednost posamezne nagrade in vse nagrade imajo različne vrednosti. Spet imata igralca možnost, da nagradi izmenjata: vsak od njiju se odloči, ali je nagrado pripravljen zamenjati in do izmenjave, če sta oba pripravljena zamenjati. a) Modelirajte to kot Bayesovo igro. 30 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER b) Recimo, da so možne štiri nagrade. Zapišite vrednost koristnostne funkcije prvega igralca, ki dobi prvo nagrado, če je le-ta pripravljen zamenjati le prvo (dobljeno) nagrado, drugi igralec pa je pripravljen zamenjati le drugo nagrado. c) Poiščite čista Bayesova ravnovesja igre (v splošnem). 8. Dana je igra s šestimi kartami, kjer je na dveh kartah narisan kamen, na dveh kartah škarje in na dveh kartah papir. Igro igrata dva igralca, ki najprej iz dobro premešanega kupa teh šestih kart vzameta vsak po dve karti. Nato hkrati vržeta vsak eno od kart, ki ju imata. Kamen premaga škarje, škarje premagajo papir, papir pa premaga kamen. Če karta katerega igralca premaga drugo, zmagovalec dobi eno točko, poraženec pa nič. Sicer oba dobita pol točke. Modelirajte to kot Bayesovo igro. Posebej natančno opišite stanja, signale in strate- gije. Nato dokažite, da ima igra vsaj eno čisto Bayesovo ravnovesje: opišite ustrezni profil ter izračunajte koristnostne funkcije igralcev s signali in jih primerjajte z vre- dnostmi, ki jih dobijo, če zamenjajo akcijo iz opisanega profila. 9. Dan je kup 6 kart, med katerima sta dva fanta, dva kralja in dva asa. Fant je vreden nič točk, kralj eno točko, as pa dve točki. Dva igralca iz dobro premešanega kupa brez vračanja vzameta vsak eno karto. Nato se vsak odloči, ali bo karto vrgel ali ne. Če oba vržeta karto, igralec s karto nižje vrednosti plača nasprotniku razliko vrednosti obeh kart. Če eden karto vrže, drugi pa ne, tisti, ki je ni vrgel, plača nasprotniku vrednost svoje karte. Sicer nihče ne plača ničesar. Modelirajte to kot Bayesovo igro. Ali obstaja kakšno čisto Bayesovo ravnovesje? M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 31 4. Ekstenzivne igre Prevedba na strateške igre. Vgnezdeno Nashevo ravnovesje. Stackelbergov model duopola. Igre z nepopolno informacijo. Reducirane strategije. Randomizirane igre. Behavioristično mešane strategije, Kuhnov izrek, vgnezdena behavioristično mešana Nasheva ravnovesja. Ekstenzivne igre lahko predstavimo z drevesom s korenom: v vsakem vozlišču (s korenom vred), ki ni list, je na potezi določen igralec, njegove poteze (akcije) pa predstavljajo s povezave, ki gredo iz tega vozlišča stran od korena. Koren predstavlja začetek, listi pa možne izteke igre. Za vsak možen iztek igre morajo biti določene preferenčne funkcije posameznih igralcev. Vsaki ekstenzivni igri priredimo običajno strateško igro, kjer igralci ustrezajo igralcem v dani ekstenzivni igri, akcije posameznega igralca pa so vse možne kombinacije akcij v vseh vozliščih ekstenzivne igre, ko je na potezi. Nashevo ravnovesje ekstenzivne igre je Nashevo ravnovesje prirejene strateške igre. Če pri iztekih igre podamo koristnostne funkcije, je možno gledati tudi mešana ravnovesja. 1. Dana je ekstenzivna igra: P1 A B P2 P2 C D E F 1 3 2 4 1 2 2 1 Zapišite prirejeno strateško igro in izračunajte njena mešana Nasheva ravnovesja. Klasični koncept Nashevega ravnovesja ekstenzivni igri ne ustreza povsem. Ustrezal bi, če bi igro odigral avtomat, ki bi mu igralci vnaprej povedali, kako naj igra v posameznih vozliščih, na koncu pa bi poleg izplačila dobitka dobili tudi celotno informacijo o navodilih njihovih soigralcev avtomatu. 32 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Vsakemu vozlišču ekstenzivne igre priredimo podigro: to je ekstenzivna igra, sestavljena iz vseh možnih potekov od tega vozlišča naprej. Podigram torej pripadajo določena poddrevesa. Vgnezdeno Nashevo ravnovesje (angl. subgame perfect equilibrium – SPE) ekstenzivne igre je profil, ki nam da Na- shevo ravnovesje v vseh podigrah. Zaenkrat se omejimo le na čiste strategije. Vgnezdeno Nashevo ravnovesje končne ekstenzivne igre vedno obstaja in ga lahko poiščemo z indukcijo po podigrah od iztekov proti korenu. Ko imamo že določena vgnezdena Nasheva ravnovesja podiger za vse naslednike posame- znega vozlišča, za vsako kombinacijo teh ravnovesij po posameznih vozliščih naslednikih poiščemo množico optimalnih akcij in jih dodajamo prej omenje- nim kombinacijam. Tako dobimo nove kombinacije, ki so vgnezdena Nasheva ravnovesja podigre od tega vozlišča naprej. 2. Poiščite vgnezdena Nasheva ravnovesja igre iz prejšnje naloge. Se le-ta ujemajo s čistimi Nashevimi ravnovesji? 3. Poiščite vgnezdena Nasheva ravnovesja igre: P1 A B P2 P2 C D E F P1 P1 4 4 G I J L 4 2 H K 5 6 6 2 5 5 2 2 1 5 1 4 4. Hierarhično pleme n kanibalov je ujelo misionarja. Hierarhija plemena je linearna: na čelu plemena je glavni kanibal, sledi drugi kanibal, nato tretji in tako naprej do n-tega kanibala. Glavni kanibal je edini, ki ima možnost, da poje misionarja. Če ga ne poje, je konec igre. Če ga poje, pa bo šel spat in potem je drugi kanibal edini, ki ima možnost, da poje prvega. Če ga ne poje, je konec igre, če ga poje, bo šel spat in potem je na vrsti tretji kanibal. Tako se igra nadaljuje: če i-ti kanibal poje (i − 1)-tega, bo šel spat in potem je (i + 1)-ti kanibal edini, ki ima možnost, da ga poje. Edino zadnji kanibal lahko mirno zaspi, če poje predzadnjega. M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 33 Vsak kanibal lahko iz igre izide v treh stanjih: sit, lačen ali mrtev. Seveda je vsak kanibal raje sit kot lačen, a tudi raje lačen kot mrtev. Narišite drevo igre in poiščite vgnezdena Nasheva ravnovesja. 5. Skupina jedcev si mora razdeliti torto. Postopek delitve je sestavljen iz več korakov. Koraki so lahko dveh vrst: rezanje ali jemanje. Če je korak rezanje, mora igralec, ki je na potezi razdeliti enega od kosov, ki so še na voljo, na predpisano število delov. Če je korak jemanje, pa igralec, ki je na potezi, vzame enega od kosov, ki so še na voljo. a) Recimo, da sta jedca dva, postopek pa je naslednji: najprej prvi igralec razreže torto na dva dela, nato drugi igralec vzame enega izmed kosov po lastni izbiri, prvi igralec pa dobi preostali kos. Modelirajte to kot ekstenzivno igro. Kakšna je razdelitev pri vgnezdenem ravnovesju? b) Oblikujte postopek za n jedcev, pri katerem v vgnezdenem Nashevem ravno- vesju vsak dobi enako velik kos torte. 6. Albert in Egon se potegujeta za torto. Najprej Albert ponudi Egonu kos torte, zase pa zadrži preostanek. Egon lahko sprejme ponujeni kos, v tem primeru ga seveda dobi, preostanek pa dobi Albert. Lahko pa Egon ponujeni kos zavrne: v tem primeru Egon ponujeni kos uniči in Albertu izpuli četrtino njegovega kosa. Modelirajte to kot ekstenzivno igro in poiščite vgnezdena Nasheva ravnovesja. 7. Dana je naslednja modifikacija igre ultimat, ki ima dva kroga. V prvem krogu prvi igralec drugemu ponudi delež p1 ∈ [0, 1] neke dobrine, nakar drugi igralec ponudbo sprejme ali zavrne. Če drugi igralec ponudbo sprejme, je igre konec: drugi igralec dobi p1, prvi pa 1−p1. Če pa drugi igralec ponudbo zavrne, v drugem krogu pripravi protiponudbo, v kateri on ponudi prvemu igralcu delež p2 ∈ [0, 1]. Če prvi igralec sprejme to protiponudbo, je igre konec in prvi igralec dobi δp2, drugi pa δ(1 − p2); parameter δ ∈ (0, 1) interpretiramo kot zmanjšanje vrednosti dobrine (diskontni faktor). Če prvi igralec v drugem krogu ponudbo zavrne, pa nobeden ne dobi nič. Določite vgnezdena Nasheva ravnovesja igre. 8. Cesar potrebuje novo obleko, ki mu jo lahko sešije eden izmed dveh krojačev, Herbert ali Kaspar. Ker se ne more odločiti, pri katerem krojaču bi jo naročil, povpraša tri svetovalce in upošteva odločitev večine. Preden pa se to zgodi, krojača stopita do svetovalcev. Najprej pristopi Herbert. Vsakemu svetovalcu lahko da enega ali več zlatnikov, ni pa nujno. Kaspar to budno opazuje in nato še sam pristopi do svetovalcev, pri čemer jim lahko spet deli zlatnike, ni pa nujno. Če posamezen svetovalec od določenega krojača dobi strogo več kot drugega, se odloči v prid prvemu. Če dobi od obeh enako, pa se za vsakega odloči z verjetnostjo 1/2. Privzamemo, da so svetovalci pri tem neodvisni. Vemo še, da krojač, ki dobi posel, z njim zasluži 5 zlatnikov. Modelirajte to kot ekstenzivno igro, pri čemer privzemite, da krojača gledata priča- kovani dobiček in da so zlatniki nedeljivi. Poiščite vgnezdena Nasheva ravnovesja. 34 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Namig: recimo, da Herbert kateremu od svetovalcev plača neničelno podkupnino. Ali se Kasparju splača temu svetovalcu plačati isti znesek? Stackelbergov model duopola/oligopola Stackelbergov model je podoben Cournotovemu: vsak proizvajalec določi ko- ličino qi produkta, ki ga proizvede, na trgu se oblikuje cena P (Q), kjer je q = q1 + q2 + · · · + qn, posamezen proizvajalec pa ima s proizvodnjo stroške Ci(qi) in je njegov dobiček tako enak: ui(q1, . . . , qn) = P (Q) qi − Ci(qi) . Toda v nasprotju s Cournotovim modelom proizvajalci blaga ne proizvedejo hkrati: najprej blago proizvede prvi, nato drugi opazi, koliko je proizvedel prvi, in proizvede svoje blago, nato tretji opazi, koliko sta proizvedla prva dva, in proizvede svoje, in tako naprej do zadnjega proizvajalca, ki ima popolno informacijo o tem, koliko so proizvedli drugi. 9. Poiščite vgnezdena Nasheva ravnovesja v Stackelbergovem modelu duopola, pri ka- terem so stroški proizvodnje za oba proizvajalca enaki kar qi, tržna cena enote blaga pa je (17 − Q)+. Je bolje biti prvi ali drugi proizvajalec? 10. Dana je Stackelbergovega modela duopola, pri kateri tržna cena enote blaga znaša (5 − q1 − q2)+, stroški proizvodnje na enoto blaga pa so enaki kar 1. Poleg tega privzamemo, da lahko proizvajalca proizvedeta le nenegativno celoštevilsko koli- čino blaga: 0, 1, 2, . . .. Poiščite vgnezdena Nasheva ravnovesja te različice modela duopola. Je bolje biti prvi ali drugi proizvajalec? Deterministične ekstenzivne igre z nepopolno informacijo Ekstenzivna igra z nepopolno informacijo je prav tako podana z drevesom, a na vozliščih je definirana ekvivalenčna relacija. Ekvivalenčnim razredom pravimo informacijske množice. Pri tem mora biti na vseh vozliščih iz posamezne informacijske množice na potezi isti igralec in v vsakem vozlišču mora imeti isti nabor akcij. Ideja je, da igralec ve le, da se nahaja v informacijski množici, ne ve pa, v katerem vozlišču točno se nahaja. Taki igri prav tako priredimo strateško igro, le da so akcije posameznega igralca zdaj vse možne kombinacije akcij v vseh informacijskih množicah, v katerih je na potezi. Zdaj ni več nujno, da obstaja čisto Nashevo ravnovesje, v končnih igrah pa seveda obstaja mešano. 11. Poiščite mešana Nasheva ravnovesja naslednje ekstenzivne igre z nepopolno infor- macijo: M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 35 P1 A B P2 2 C D 1 P1 E F E F 2 2 3 1 2 0 0 1 Reducirane strategije Redukcija strategije danega igralca v ekstenzivni igri je zožitev te strategije na tiste informacijske množice, do katerih igralec, če ubere dano strategijo, lahko pride. Informacijska množica je torej zajeta v redukciji strategije na- tanko tedaj, ko obstajajo take strategije ostalih igralcev, da dani igralec pride do te informacijske množice. Reducirane strategije so redukcije vseh možnih strategij. Strategije z isto redukcijo so med seboj ekvivalentne: za poljuben fiksen nabor strategij ostalih igralcev dobimo za take strategije danega igralca isti nabor koristnostnih funkcij. Vsaki ekstenzivni igri lahko tako priredimo strateško igro, v kateri so akcije reducirane strategije. Reducirano Nashevo ravnovesje (čisto ali mešano) dane ekstenzivne igre je Nashevo ravnovesje strateške igre z reduciranimi stra- tegijami. Primer: pri igri iz prejšje naloge ima prvi igralec tri reducirane strategije, ki jih označimo z A∗, BE in BF . Reducirana Nasheva ravnovesja so oblike: A∗ BE BF , C ; b, c, d ≥ 0, b + c + d = 1, 2c ≥ d . b c d 12. Poiščite mešana reducirana in nereducirana Nasheva ravnovesja naslednje eksten- zivne igre z nepopolno informacijo: 36 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER P1 A B P2 P2 C D E F P1 P1 G H G H I J I J 2 0 3 0 0 4 1 0 5 7 3 4 4 3 1 7 13. Poiščite mešana reducirana Nasheva ravnovesja naslednje ekstenzivne igre z nepo- polno informacijo: P1 A B P2 P2 C D E F P1 G H G H G H G H 2 0 3 0 0 4 1 0 5 7 3 4 4 3 1 7 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 37 Randomizirane ekstenzivne igre Pri randomiziranih ekstenzivnih igrah lahko nastopajo tudi vozlišča, kjer na- mesto igralca nastopa slučaj. Tudi iz teh vozlišč izhajajo poteze in za vsako je predpisana verjetnost. Če je več takih vozlišč, privzamemo, da so dogajanja v njih verjetnostno neodvisna. Pri koristnostnih funkcijah gledamo pričakovane vrednosti. 14. Poiščite mešana Nasheva ravnovesja naslednje randomizirane ekstenzivne igre: 2/3 1/3 B C A D P1 P2 0 3 0 A B C D 0 0 3 3 −3 6 0 0 3 15. Lojze oddaja stanovanje. Zna se zgoditi, da mu najemnik nekega dne sporoči, da ne more poravnati najemnine za tekoči mesec, obljubi pa mu, da bo naslednji mesec poravnal vse za nazaj. Najemnik pa je lahko pošten ali goljufiv. Pošteni najemnik tisti mesec res nima denarja in mu naslednji mesec zagotovo poravna vse za nazaj. Goljufivi najemnik pa ima dve možnosti: bodisi da lastniku pošteno plača bodisi da se mu zlaže, da nima denarja. Če (goljufivi) najemnik pošteno plača, je konec igre in oba z lastnikom sta na ničli. Če pa (pošteni ali goljufivi) najemnik sporoči, da ne more plačati, se igra nadaljuje in v drugem koraku je na potezi lastnik, ki ima dve možnosti. Prva je, da najemnika takoj nažene iz stanovanja. V tem primeru imata oba z najemnikom eno enoto iz- gube. Druga možnost pa je, da ga pusti notri še en mesec. Če je najemnik pošten, bo plačal in bosta oba na ničli. Če pa je najemnik goljufiv, ne bo plačal in Lojze bo imel dve enoti izgube, najemnik pa dve enoti dobička, saj je že predvidel, kam bo šel. Privzemimo, da je najemnik pošten z verjetnostjo 1/3 in goljufiv z verjetnostjo 2/3. Modelirajte to kot randomizirano ekstenzivno igro z nepopolno informacijo. Če po- šteni ali goljufivi najemnik v določenem poteku igre ni udeležen, mu pripišite ničlo. Nato zapišite pripadajočo strateško igro in poiščite mešana Nasheva ravnovesja te igre. 38 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Igre s popolnim priklicem, behavioristično mešane strategije in vgnezdena behavioristično mešana Nasheva ravnovesja V ekstenzivni igri s popolno informacijo ima dani igralec popoln priklic, če za vsako informacijsko množico, kjer je on na potezi, velja, da vsem vozliščem v njej pripada isto zaporedje potez tega igralca. Z drugimi besedami, igralec se spomni vseh svojih prejšnjih potez. Ekstenzivna igra s popolnim priklicem je igra, kjer imajo vsi igralci popoln priklic. Behavioristično mešana strategija posameznega igralca je mešana strate- gija, ki jo dobimo z verjetnostno neodvisnim kombiniranjem mešanic akcij v posameznih vozliščih (strategij tu ne reduciramo). Behavioristično mešano Nashevo ravnovesje je mešano Nashevo ravnovesje, pri katerem vsi igralci uberejo behavioristično mešane strategije. Kuhnov izrek pravi, da je, če ima določen igralec popoln priklic, vsaka nje- gova mešana strategija ekvivalentna kakšni behavioristično mešani strategiji. Mešani strategiji posameznega igralca sta ekvivalentni, če za poljubne fiksne mešane strategije ostalih igralcev pri obeh strategijah dobimo enako verjetno- stno porazdelitev iztekov igre. Tako tudi vsako mešano Nashevo ravnovesje ustreza določenemu behavioristično mešanemu Nashevemu ravnovesju. Podigra ekstenzivne igre s popolnim priklicem je igra, ki ustreza poddre- vesu, ki od vsake informacijske množice vključuje bodisi vsa vozlišča bodisi nobenega. Vsako behavioristično mešano strategijo lahko naravno zožimo na podigre. Vgnezdeno behavioristično mešano Nashevo ravnovesje je profil iz behavioristično mešanih strategij, ki nam v vseh podigrah da mešano Nashevo ravnovesje. Ekvivalentno, to je vgnezdeno Nashevo ravnovesje eks- tenzivne igre, katere poteze v posameznem vozlišču so vse možne tamkajšnje mešanice potez izvirne igre. Vsaka končna ekstenzivna igra s popolnim priklicem ima vgnezdeno behavio- ristično mešano Nashevo ravnovesje. 16. Katere od prejšnjih ekstenzivnih iger z nepopolno informacijo imajo popoln pri- klic? Pri tistih, ki ga imajo, določite vgnezdena behavioristično mešana Nasheva ravnovesja. Določite še: • ali obstaja kakšno behavioristično mešano Nashevo ravnovesje, ki ni vgnezdeno; • ali obstaja kakšno mešano Nashevo ravnovesje, ki ni behavioristično mešano. M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 39 5. Kooperativne igre Nashev model pogajanja s fiksnim izhodiščem. Neprenosljive in prenosljive dobrine. Dvofazne igre z zavezujočim sporazumom. Koalicijske igre: imputacije, jedro, Shapleyjeve vrednosti. Prevedba strateških na koalicijske igre. Medtem ko rešitev strateške igre ali njene izvedenke sestoji iz nabora akcij/strategij posameznih igralcev, se rešitev kooperativne igre izraža kot sporazum med igralci. Nashev model pogajanja s fiksnim izhodiščem Dva igralca imata možnost, da se sporazumeta, da prvi igralec dobi x, drugi pa y, kjer je (x, y) ∈ S, S ⊆ 2 R pa je množica dopustnih sporazumov. Če se ne sporazumeta, prvi dobi u, drugi pa v. Točka (u, v) je torej pogajalsko izhodišče. Privzamemo, da je množica {(x, y) ∈ S ; x ≥ u, y ≥ v} konveksna in kompaktna. Nasheva rešitev tega modela pogajanja je, da v primeru, ko je množica {(x, y) ∈ S ; x ≥ u, y ≥ v} prazna, igralca ostaneta v pogajalskem izhodišču (u, v) (status quo), sicer pa se sporazumeta za točko (x, y) ∈ S, kjer je x ≥ u, y ≥ v, Nashev produkt (x − u)(y − v) pa maksimalen. Obstaja natanko ena taka točka (x∗, y∗) in ta se vedno nahaja na robu množice S glede na kvadrant {(x, y) ; x ≥ u, y ≥ v}. Pri Nashevi rešitvi torej nobeden od igralcev ne izgubi glede na pogajalsko izhodišče. Nasheva rešitev je edina rešitev (u, v, S) → f (u, v; S), ki zadošča naslednjim aksiomom: • Dopustnost: za vsako izhodišče (u, v) je f (u, v; S) ∈ S. • Optimalnost po Paretu: brž ko je (x, y) = f (u, v; S) za neko izhodišče (u, v) in ustrezno množico S ter (ξ, η) ∈ S, ξ ≥ x in η ≥ y, je ξ = x in η = y. • Simetrija: Če je S simetrična okoli simetrale lihih kvadrantov in (x, y) = f (u, u; S), je x = y. • Neodvisnost od irelevantnih alternativ: če je T ⊆ S zaprta in konveksna ter (u, v) ∈ T in f (u, v; S) ∈ T , je f (u, v; S) = f (u, v; T ). • Invariantnost za translacije in raztege: za poljubne a, c > 0 in b, d ∈ R iz f (u, v; S) = (x, y) sledi f (au + b, cv + d; T ) = (ax + b, cy + d), kjer je T = {(aξ + b, cη + d) ; (ξ, η) ∈ S}. Glej [2]. 1. Poiščite Nashevo rešitev pogajanja pri množici dopustnih sporazumov: 1 − x2 S = (x, y) ; y ≤ 4 za pogajalska izhodišča (0, −13/2), (−2, 1/4), (0, 1) in (0, 2). 40 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Prenosljiva dobrina Množica ˆ S dopustnih sporazumov ima prenosljivo dobrino, če za vsak par (x, y) ∈ S in za vsak t ∈ R velja (x+t, y −t) ∈ ˆ S. Taka množica je vedno oblike {(x, y) ; x + y ∈ I}, kjer je I podmnožica realne osi. Če je ˆ S konveksna, je I interval. Če obstaja maksimalni skupni sporazumni dobitek σ = max I = max{x + y ; (x, y) ∈ S} in je (u, v) pogajalsko izhodišče, je Nasheva rešitev igre kar (u, v), če je u+v > σ, sicer pa je to tista razdelitev maksimalnega skupnega sporazumnega dobitka σ, pri kateri se ohrani razlika dobitkov iz pogajalskega izhodišča, to pa je: σ + u − v σ − u + v x∗ = , y∗ = . 2 2 Množica ˆ S dopustnih sporazumov s prenosljivo dobrino izhaja iz množice S, če je enaka {(x + t, y − t) ; (x, y) ∈ S}. Velja σ = max{x + y ; (x, y) ∈ M }. V sporazumu določimo, iz katere točke množice S izhajamo ter koliko in v katero smer znaša prenos dobrine. 2. Poiščite Nashevo rešitev pogajanja pri množici dopustnih sporazumov, ki ima pre- nosljivo dobrino in izhaja iz množice v prejšnji nalogi, in sicer za vsa izhodišča iz prejšnje naloge. Dvofazna igra z zavezujočim sporazumom Gre za strateško igro za dva igralca, ki jo dobimo iz strateške igre za dva igralca na naslednji način: najprej vsak od igralcev zagrozi z mešano strategijo v prvotni igri. To predstavlja pogajalsko izhodišče (u, v) Nashevega modela pogajanja s prenosljivo ali neprenosljivo dobrino. Pri neprenosljivi dobrini je množica dopustnih sporazumov množica parov dobitkov, ki pripadajo vsem možnim loterijam na profilih (ne le profilom iz mešanih strategij). Igralca torej sporazumno mešata. Ekvivalentno, S je konveksna kombinacija točk, ki predstavljajo pare dobitkov v vseh možnih (čistih) profilih. Če pa je dobrina prenosljiva, je preprosto S = {(x, y) ; m ≤ x + y ≤ σ}, kjer je m minimalni, σ pa maksimalni skupni dobitek. Akcije igralcev v novi igri se ujemajo z mešanimi strategijami v prvotni igri. Dobitka igralcev pa sta dobitka (x∗, y∗), ki prideta iz Nashevega sporazuma glede na pogajalsko izhodišče (u, v) (sporazum je torej zavezujoč). Vsaka tako dobljena dvofazna igra ima Nashevo ravnovesje. V dobljeni dvofazni igri je dobitek posameznega igralca vedno monotona funkcija, če strategijo tega igralca spreminjamo linearno, strategijo drugega igralca pa pustimo pri miru. Zato je množica najboljših odgovorov konveksna, od koder sledi, da Nashevo ravnovesje obstaja. 3. Dana je strateška igra: L R T 6, 2 1, 1 B 2, 4 5, 3 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 41 a) Pri splošnem pogajalskem izhodišču (u, v) poiščite Nashevo rešitev pogajanja, če množica dopustnih sporazumov izhaja iz dane strateške igre in je dobrina prenosljiva. b) Rešite pripadajočo dvofazno igro z zavezujočim sporazumom; spet privzemite, da je dobrina prenosljiva. c) Zdaj pa privzemite, da so dobitki neprenosljivi. Poiščite Nashevo rešitev poga- janja za pogajalska izhodišča, ki nastanejo, če igralca zagrozita s pari strategij T B L R , L , T, in (T, R). Poiščite tudi sporazumne 1/2 1/2 3/5 2/5 mešanice profilov! d) Spet pri neprenosljivi dobrini poiščite Nashevo rešitev pogajanja še za splošno pogajalsko izhodišče. Namig: razmišljajte v obratni smeri: za dano točko (x∗, y∗) na zgornjem de- snem robu množice dopustnih sporazumov raziščite, za katera pogajalska iz- hodišča je sporazum dosežen ravno v (x∗, y∗). e) Spet pri neprenosljivi dobrini poiščite Nashevo rešitev pogajanja še za splo- šen par grozilnih strategij in rešite pripadajočo dvofazno igro z zavezujočim sporazumom. Koalicijske igre Koalicijska igra na množici igralcev I je določena s predpisom, ki pove, koliko vsaka podmnožica igralcev K ⊆ I skupaj dobi, če sklene koalicijo. To je torej preslikava v iz potenčne množice množice K v R. Pravimo ji karakteristična funkcija. Pri tem mora veljati v(∅) = 0 in še superaditivnost: če sta K in L disjunktni koaliciji, mora veljati v(K ∪ L) ≥ v(K) + v(L). Zaradi superaditivnosti je skupno gledano vedno najdonosnejša polna koalicija. Ključni problem pa je, kako naj si njeni člani razdelijo skupni dobitek. Če je I = {1, 2, . . . , n}, lahko delitev dobitka predstavimo z n-terico (x1, x2, . . . , xn), za katero velja x1 + x2 + · · · + xn = v(I). Imputacije so tiste delitve, za katere je xi ≥ v({i}) za vse i (torej nihče ne more profitirati, če sam izstopi iz koalicije). Zaradi superaditivnosti je množica imputacij vedno neprazna. Jedro sestavljajo tiste delitve, za katere je x i∈K k ≥ v(K ) za vse koalicije K (torej nobena koalicija ne more profitirati, če spodkoplje polno koalicijo). Jedro je lahko tudi prazno. 4. Dana je naslednja karakteristična funkcija: v(∅) = 0 , v({1}) = 1 , v({2}) = 2 , v({3}) = 1 , v({1, 2}) = a , v({1, 3}) = 3 , v({2, 3}) = 4 , v({1, 2, 3}) = 8 . Za katere a je ta funkcija superaditivna? Za najmanjši tak a skicirajte imputacije in jedro pripadajoče koalicijske igre. 42 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Shapleyjeve vrednosti Shapleyjeva vrednost φi je povprečni prispevek i-tega igralca h koaliciji, če si predstavljamo, da igralci pristopajo h koaliciji zaporedoma, drug za drugim. Pri tem vzamemo vse možne vrstne rede pristopanja. Če torej igralci pristopajo v vrstnem redu π(1), π(2), . . . , π(n) in je i = π(l), je prispevek i-tega igralca enak v({π(1), . . . , π(l)}) − v({π(1), . . . , π(l − 1)}). Shapleyjeve vrednosti so imputacija: zaradi superaditivnosti posamezen igralec pri vsakem vrstnem redu pristopanja h koaliciji prispeva vsaj toliko, kolikor dobi, če je sam. Shapleyjeve vrednosti so edina preslikava v → φ1(v), . . . , φn(v) , ki zadošča naslednjim aksiomom: • Učinkovitost: φ i∈I i (v) = v(I ). • Simetrija: brž ko za vse koalicije K, ki ne vsebujejo i in j, velja v(K ∪ {i}) = v(K ∪ {j}), je φi(v) = φj (v). • Neopaznost: brž ko za vse koalicije K, ki ne vsebujejo i, velja v(K ∪ {i}) = v(K), je φi(v) = 0. • Aditivnost: za poljubni karakteristični funkciji u in v velja φi(u + v) = φi(u) + φi(v) za vse i ∈ I. Glej [2]. 5. Določite imputacije, jedro in Shapleyjeve vrednosti koalicijske igre s karakteristično funkcijo: v({1}) = 2 , v({2}) = 1 , v({3}) = 2 , v({1, 2}) = 8 , v({1, 3}) = 9 , v({2, 3}) = 8 , v({1, 2, 3}) = 12 . 6. Dan je Nashev model pogajanja s fiksnim izhodiščem (u, v) in prenosljivo dobrino, kjer u + v ne presega maksimalnega skupnemu sporazumnega dobitka. Dokažite, da se sporazumni par dobitkov po Nashu ujema s Shapleyjevima vrednostma v koalicijski igri, kjer je dobitek koalicije iz posameznega igralca enak njegovemu iz- hodiščnemu dobitku, dobitek polne koalicije pa je enak maksimalnemu skupnemu sporazumnemu dobitku. Prevedba strateških iger na koalicijske Koalicijsko igro dobimo iz strateške tako, da v(K) definiramo kot stopnjo var- nosti za koalicijo K v izvirni strateški igri. Z drugimi besedami, to je vrednost matrične igre, ki jo dobimo, če koalicija K igra proti svoji protikoaliciji I \ K, pri čemer lahko obe koaliciji poljubno kombinirata svoje akcije, koristnostna funkcija koalicije pa je enaka vsoti koristnostnih funkcij vseh njenih članov. 7. Pretvorite igro: T2 B2 T2 B2 T1 0, 3, 6 1, 4, 6 T1 2, 3, 7 1, 3, 6 . B1 1, 3, 7 2, 3, 6 B1 1, 3, 5 1, 4, 6 a3 = T3 a3 = B3 v koalicijsko obliko ter določite imputacije in jedro. Določite še Shapleyjeve vredno- sti. M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 43 8. Kmet Ambrož ima odsluženega vola, ki je le še za zakol. V vasi sta dva mesarja, Boris in Cveto. Boris lahko od vola iztrži 90, Cveto pa 120 denarnih enot dobička. Glede na to, da Cveto iztrži več, je, če gledamo skupni dobiček, najbolj smiselno, da vola dobi on. A za koliko naj mu ga Ambrož proda? Si tudi Boris zasluži del dobička v zameno za izgubljeni posel? Modelirajte to kot koalicijsko igro ter na zgornji dve vprašanji odgovorite s stališča jedra in s stališča Shapleyjevih vrednosti. 9. Študent Aljaž je v Ljubljani najel stanovanje, ki ga ta hip, ko v njem živi sam, stane 650e na mesec, zato išče sostanovalce. Stanovanje je primerno za največ tri osebe, vsak dodatni sostanovalec pa poveča stroške za 50e. Aljažu se oglasita dva interesenta, ki se dnevno vozita iz oddaljenih krajev: Bojan, ki ga vožnja stane 200e, in Cveto, ki ga stane 300e na mesec (če smo natančni, pri obeh gledamo razliko med cenami vsakodnevnih voženj, če ne se preseli v Ljubljano, in cenami občasnih voženj, če se preseli v Ljubljano) a) Formulirajte to kot igro v koalicijski obliki in preverite superaditivnost (za karakteristično funkcijo vzemite negativno predznačene skupne stroške bivanja oz. dodatnih voženj, ki jih imajo študentje v koaliciji). b) Kako naj si v skladu Shapleyjevimi vrednostmi razdelijo stroške, če se Bojan in Cveto priselita k Aljažu? c) Določite še imputacije in jedro. a) Karakteristična funkcija je: v(∅) = 0 , v({A}) = −650 , v({B}) = −200 , v({C}) = −300 , v({A, B}) = −700 , v({A, C}) = −700 , v({B, C}) = −500 , v({A, B, C}) = −750 , b) Shapleyjeve vrednosti so: φA = −450 , φB = −125 , φC = −175 . V skladu s Shapleyjevimi vrednostmi bi moral torej Aljaž v skupno blagajno pri- spevati 450e, Bojan 125e, Cveto pa 175e. c) Imputacije in jedro so prikazani na naslednji sliki: 44 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER xB+xC ≥−500 xB≥−200 (−650,−200,100) (−500,−200,−50) (−650,−50,−50) xA+xB≥−700 xC ≥−300 (−250,−200,−300) (−400,−50,−300) (−650,200,−300) xA+xC ≥−700 xA≥−650 10. Odbor ima 4 člane, eden izmed njih je predsednik. Denimo, da odbor odloča o sprejetju določenega projekta. Projekt je sprejet, če se s tem strinjajo vsaj trije člani ali pa predsednik in še en član odbora. Recimo, da ima odbor od sprejetega projekta korist, ki si jo razdelijo le tisti, ki so se strinjali z njegovim sprejetjem (t. j. v(S) = 1, če je projekt sprejet, če se s tem strinjajo člani koalicije S, ostali pa ne). Poiščite Shapleyjeve vrednosti posameznih članov te odbora. Posplošite še na odbor iz 2n članov. 11. Adrijan, Brigita, Cveto, Damjana, Erik in Fedora igrajo koalicijsko igro, v kateri je vrednost koalicije enaka številu igralcev, če je res, da je notri Adrijan, in je hkrati res, da je notri Brigita ali Cveto. Sicer je vrednost koalicije enaka nič. Izračunajte Shapleyjeve vrednosti za vse igralce. REŠITVE 46 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Predgovor M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 47 1. Strateške igre 1. Zapis igre: U R U 0, 0 1, 0 . R 0, 1 1 , 1 2 2 Nasheva ravnovesja: (U, U ), (U, R), (R, U ). Strogih Nashevih ravnovesij ni. 2. Možen zapis igre: T M T −3, −3 −1, −4 . M −4, −1 −2, −2 Profil (T, T ) je edino Nashevo ravnovesje, in sicer strogo. 3. Možen zapis igre: V P V r, r r−1 , r+1 2 2 . P r+1 , r−1 0, 0 2 2 Če je r < 1, je edino Nashevo ravnovesje (P, P ), in sicer strogo. Pri r = 1 so vsi profili Nasheva ravnovesja, nobeno ni strogo. Pri r > 1 pa je edino Nashevo ravnovesje (V, V ), in sicer strogo. Pri r < 1 je igra ekvivalentna dilemi zapornikov: strategija V ustreza strategiji M , strategija P pa strategiji T . Nadalje preference r−1 < 0 < r < r+1 ustrezajo 2 2 preferencam −4 < −3 < −2 < −1. Pri r = 1 igra definitivno ni ekvivalentna dilemi zapornikov, ker ima drugačno šte- vilo Nashevih ravnovesij. Pri r > 1 pa ima igra sicer prav tako eno samo Nashevo ravnovesje, ki je strogo, a v njem oba igralca dobita najvišji možni izkupiček, med- tem ko pri dilemi zapornikov dobita tretji najvišji (predzadnji) izkupiček oz. drugo najstrožjo kazen. 4. Da, to se lahko zgodi. Primer: L D A 2, 2 0, 1 B 2, 1 1, 2 C 1, 2 2, 1 Igra ima Nashevo ravnovesje (A, L) in akcija A je dominirana z B. Če jo izločimo, zožena igra nima več Nashevih ravnovesij. 48 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Ilustrativna je tudi malenkost spremenjena zgornja igra, pri kateri dominacija po- stane stroga: L D A 2, 2 0, 1 B 3, 1 1, 2 C 1, 2 2, 1 Ta igra nima Nashevih ravnovesij. 5. Akcija B1 strogo dominira akcijo T1. Drugih dominacij ni. Edino Nashevo ravnovesje je (B1, T2, T3). Le-to je tudi strogo. 6. Tem pogojem ustreza npr. igra: T2 B2 T2 B2 T1 8, 1, 1 5, 2, 2 T1 4, 5, 5 1, 6, 6 . B1 7, 4, 3 6, 3, 4 B1 3, 8, 7 2, 7, 8 a3 = T3 a3 = B3 7. Nasheva ravnovesja so: • (A, Y, L), če je b ≥ 4 (ki je strogo, če je b > 4); • (B, X, L), če je b ≥ 2; • (B, Y, L), če je b ≤ 2 in a ≥ 5 (ki je strogo, če je b < 2 in a > 5) • (B, Y, M ), če je a ≤ 5. Igra ima lahko največ tri Nasheva ravnovesja, saj se (A, X, L) in (B, Y, L) izključu- jeta. Igra ima dejansko lahko tri Nasheva ravnovesja: pri a = 5 in b = 2 so to prej omenjeni profili z izjemo (A, Y, L), pri a ≤ 4 in b ≥ 4 pa z izjemo (B, Y, L). Če je b ≤ 2, akcija Y dominira akcijo X; dominacija je stroga, če je b < 2. Če je a ≥ 5, akcija L dominira akcijo M ; dominacija je stroga, če je a > 5. Če je a ≥ 3, akcija L dominira akcijo R. 8. V Nashevem ravnovesju smo natanko tedaj, ko velja naslednje: • Če drugi igralec igra , prvi igralec igra 0. • Če drugi igralec igra r, prvi igralec igra 1. • Če prvi igralec igra a1 < 1/2, drugi igralec igra r. • Če prvi igralec igra a1 > 1/2, drugi igralec igra . • Če prvi igralec igra a1 = 1/2, ne dobimo omejitev za strategijo drugega igralca. Slika: M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 49 a2 = a2 = r 0 1 a1 Od tod zaključimo, da čistih Nashevih ravnovesij ni. 9. Akcija posameznega igralca je natančno določena s koordinato x. Če prvi igralec igra x1, drugi pa x2, drugi igralec plača prvemu 2x1x2 − x1 − x2 + 1. V Nashevem ravnovesju smo natanko tedaj, ko velja naslednje: • Če je x2 < 1/2, je x1 = 0. • Če je x2 > 1/2, je x1 = 1. • Če je x1 < 1/2, je x2 = 1. • Če je x1 > 1/2, je x2 = 0. Od tod zaključimo, da je edino Nashevo ravnovesje pri x1 = y1 = x2 = y2 = 1/2. Slika: a2 1 a1 1 10. Pripadajoča strateška igra ima 5000 igralcev – uslužbencev, od katerih lahko vsak igra dve akciji (strategiji): vlak ali avto. Preferenčna funkcija je lahko čas, ki ga uslužbenec potrebuje za pot do službe, a je urejena nasprotno kot množica realnih števil: večje število pomeni nižjo preferenco in obratno. Če se vsi uslužbenci peljejo z avtomobilom, vsak od njih za pot potrebuje 45 minut. Če se eden od njih namesto tega odloči potovati z vlakom, bo za pot potreboval . 27 005 minute, kar je ugodneje, torej to ni Nashevo ravnovesje. Privzemimo zdaj, da se vsaj en uslužbenec pelje z vlakom, torej da je y ≥ 1. Če število vlakov v predstavimo kot funkcijo spremenljivke y, dobimo, da smo v Nashevem ravnovesju natanko tedaj, ko velja: x y + 1 12 y 12 x + 1 20 + ≤ 15 + + , 15 + + ≤ 20 + , x + y = 5000 , 200 200 v(y + 1) 200 v(y) 200 50 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER kar je (če obdržimo zadnjo zvezo) ekvivalentno: 12 y 12 ≤ 30 − ≤ v(y) 100 v(y + 1) Ker je v padajoča funkcija, je ta zveza možna le, če je: 12 y v(y) = v(y + 1) in = 30 − . v(y) 100 Od tod sledi pomembna ugotovitev, da je v čistem Nashevem ravnovesju vseeno, kateri način prevoza izbere uslužbenec: pri obeh načinih porabi za pot enako mnogo časa. Za 1 ≤ y ≤ 2000, torej v(y) = 1 dobimo y = 1800, kar je v skladu z začetnim pogojem. Za 2001 ≤ y ≤ 4000 dobimo y = 2400, kar je prav tako v redu, za 4001 ≤ y ≤ 5000 pa dobimo y = 2600, kar pa je v nasprotju z začetnim pogojem. Igra ima torej dve skupini Nashevih ravnovesij: pri prvi se z vlakom pelje 1800, z avtomobilom pa 3200 uslužbencev in oboji potujejo 36 minut, pri drugi pa se z vlakom pelje 2400, z avtomobilom pa 2600 uslužbencev in oboji potujejo 33 minut. . . Formalno gledano ima igra 5000 + 5000 = 2 92 · 101501 Nashevih ravnovesij. 1800 2400 11. a) Igralci so vozniki, vsak igralec ima dve možni akciji, recimo G in D. Vsak profil a = (a1, . . . , a4000) je torej kombinacija 4000 akcij, ki so lahko G ali D. Označimo s ti(a) čas, ki ga pri profilu a porabi i-ti voznik. Preferenčna funkcija je potem lahko ui(a) = −ti(a). Če analogno kot pri ui definiramo ti(a | bi), je torej profil a Nashevo ravnovesje natanko tedaj, ko za vsak i velja, da je, brž ko je ai = G, tudi ti(a) ≤ ti(ai | D), in brž ko je ai = D, tudi ti(a) ≤ ti(ai | G). Potovalni čas i-tega voznika lahko izrazimo že z akcijo, ki jo ubere on, in številom vseh voznikov, ki uberejo denimo akcijo G: označimo to število z g. Tedaj velja: g 4000 − g + 1 ai = G : ti(a) = + 45 , ti(a | D) = 45 + , 100 100 4000 − g g + 1 ai = D : ti(a) = 45 + , ti(a | G) = + 45 . 100 100 Profil je torej Nashevo ravnovesje natanko tedaj, ko velja dvoje: • Brž ko je g > 0, je g ≤ 4000 − g + 1. • Brž ko je g < 4000, je 4000 − g ≤ g + 1. Krajši premislek pokaže, da je to natanko tedaj, ko je g = 2000. Sklep: v edinem Nashevem ravnovesju, ki je tudi strogo, polovica voznikov ubere zgornjo, polovica pa spodnjo traso. Posamezen voznik v njem potrebuje 65 enot časa. b) Sedaj lahko vozniki ubirajo tri trase: zgornjo (G), spodnjo (D) in “hitro” (z uporabo hitre ceste – H). Recimo, da jih g ubere zgornjo, d spodnjo, in 4000 − g − d M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 51 pa hitro traso. Tedaj velja: 4000 − d 4000 − g + 1 ai = G : ti(a) = + 45 , ti(a | D) = 45 + , 100 100 4000 − d 4000 − g + 1 ti(a | H) = + , 100 100 4000 − g 4000 − d + 1 ai = D : ti(a) = 45 + , ti(a | G) = + 45 , 100 100 4000 − d + 1 4000 − g ti(a | H) = + . 100 100 4000 − d 4000 − g 4000 − d ai = H : ti(a) = + , ti(a | G) = + 45 , 100 100 100 4000 − g ti(a | D) = 45 + . 100 Krajši premislek pokaže, da je v vsakem primeru ti(a | H) < ti(a | G) in ti(a | H) < ti(a | D). Zato v edinem Nashevem ravnovesju, ki je tudi strogo, vsi vozniki uberejo hitro traso. Toda zdaj vsak voznik za pot potrebuje 80 enot časa, kar je več kot prej. Do tega pride zato, ker nova hitra cesta razbremeni le cesti, pri katerih je potovalni čas neodvisen od količine avtomobilov. Cesti, pri katerih je potovalni čas večji, več kot je avtomobilov, pa sta skupaj gledano z uvedbo hitre ceste obremenjeni še bolj: dokler hitre ceste ni, so vozniki uporabili kvečjemu eno od njih, voznik, ki uporabi hitro cesto, pa uporabi obe prej omenjeni cesti. 12. Pri a2 ≤ 1/3 se prvemu igralcu najbolj splača akcija 1, pri a2 ≥ 1/3 pa akcija 0 (t. j. pri a2 = 1/3 se enako splačata obe akciji). Nadalje se pri a1 ≤ 1/2 drugemu igralcu najbolj splača akcija 0, pri a1 ≥ 1/2 pa akcija 1 (spet se pri a1 = 1/2 enako splačata obe akciji). Slika: a2 1 a1 1 Od tod zaključimo, da Nashevih ravnovesij ni. Pogoji izreka o obstoju Nashevega ravnovesja niso vsi izpolnjeni. Množici akcij sta res konveksni in kompaktni in preferenčni funkciji sta zvezni. Toda množica najboljših odgovorov prvega igralca pri a2 = 1/3 ni konveksna, prav tako tudi ne množica najboljših odgovorov drugega igralca pri a1 = 1/2. 52 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 13. a) Očitno so preferenčne funkcije ui zvezne. Množice akcij so konveksne, niso pa kompaktne, torej izreka o obstoju Nashevega ravnovesja ne bomo mogli uporabiti čisto neposredno. Toda vse akcije iz intervala (a, ∞) so strogo dominirane z akcijo nič: proizvajalec, ki ubere akcijo qi > a, ima strogo izgubo, če pa ubere qi = 0, je na ničli. Zato se lahko pri akcijah omejimo na kompaktni interval [0, a]. Pišimo: ui(q1, . . . , qn) = (a − Qi − qi)+qi − ciqi , kjer je Qi = q1 + · · · + qi−1 + qi+1 + · · · + qn. Poiščimo množico najboljših odgovor i-tega proizvajalca pri danih akcijah ostalih. Ločimo dve možnosti: 1. Qi ≥ a. V tem primeru je u1(q1, . . . , qn) = −ciqi in maksimum je dosežen pri qi = 0. 2. Qi < a. V tem primeru je: (a − c u i − Qi − qi)qi ; qi ≤ a − Qi 1(q1, . . . , qn) = . −ciqi ; qi ≥ a − Qi Najprej opazimo, da drugi del funkcije doseže maksimum na levem krajišču, pri qi = a − Qi. Torej je maksimum dosežen za 0 ≤ qi ≤ a − Qi. Na levem kra- jišču je u1(q1, . . . , qi−1, 0, qi+1, . . . , qn) = 0, na desnem pa je ui(q1, . . . , qi−1, a − Qi, qi+1, . . . , qn) = −ci(a − Qi) < 0. Stacionarna točka je pri qi = (a − ci − Qi)/2, a ta leži znotraj intervala [0, a − Qi] le za Qi ≤ a − ci. Takrat je ui q1, . . . , qi−1, (a − ci − Qi)/2, qi+1, . . . , qn = (a − ci − Qi)2/4 ≥ 0, torej je maksimum dosežen tam. Za Qi > a − ci pa znotraj danega intervala ni stacio- narnih točk in maksimum je dosežen pri qi = 0. Če vse skupaj povzamemo, dobimo, da je najboljši odgovor en sam, in sicer: (a − c q i − Qi)+ i = . 2 Torej je množica najboljših odgovorov zagotovo konveksna. Skupaj z uvodnimi ugotovitvami dobimo, da so pogoji izreka o obstoju Nashevega ravnovesja izpolnjeni, zato obstaja vsaj eno Nashevo ravnovesje. b) Iz prejšnje točke dobimo, da Nashevo ravnovesje karakterizirata enačbi: (a − c (a − c q 1 − q2)+ 2 − q1)+ 1 = , q2 = . 2 2 Tako za posamezne primere dobimo naslednja Nasheva ravnovesja: (a − c (a − c • a − c 1)+ 2)+ 1 ≤ 0 ali a − c2 ≤ 0: q1 = , q2 = . 2 2 a − c a − c • 0 ≤ a − c 1 1 2 ≤ : q1 = , q2 = 0. Slika: 2 2 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 53 a2 a−c1 a−c2 2 a a−c1 a−c 1 1 2 a − c a + c a + c • 0 ≤ 1 ≤ a − c 2 − 2c1 1 − 2c2 2 ≤ 2(a − c1): q1 = , q2 = . Slika: 2 3 3 a2 a−c1 a−c2 2 a a−c a−c 1 1 1 2 a − c • 0 ≤ 2(a − c 2 1) ≤ a − c2: q1 = 0, q2 = . Slika: 2 a2 a−c2 2 a−c1 a a−c a−c 1 1 1 2 14. Najprej za Nashevo ravnovesje dobimo sistem enačb: (a − q (a − q q 2)+ 1)+ 1 = , q2 = , 4 4 ki ima edino rešitev q1 = q2 = a/5. 54 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 15. Najprej izračunamo, da smo v Nashevem ravnovesju natanko tedaj, ko za vse i = 1, 2, . . . , n velja: (a − c − Q q i)+ i = . (∗) 2 kjer smo označili Qi := Q − qi. Od tod naprej gre na vsaj dva načina. Prvi način. Če je c ≥ a, mora biti qi = 0 za vse i. Raziščimo še primer, ko je c < a. Če je qi > 0 za vse i, po seštetju enačb dobimo: n Q = (a − c) n + 1 in od tod, da je a − c qi = n + 1 za vse i. To je tudi Nashevo ravnovesje. Preostane nam le še primer, ko natanko r proizvajalcev ne proizvaja ničesar. Brez škode za splošnost lahko privzamemo, da je q1 = q2 = · · · = qr = 0, medtem ko je qr+1, qr+2, . . . , qn > 0 (r > 0). Po seštetju enačb tokrat dobimo: n − r Q = (a − c) , n − r + 1 od koder sledi q1 = (a − c)/(n + r − 1) > 0, kar je protislovje. Sklep: edino Nashevo ravnovesje je: (a − c) q + i = ; i = 1, 2, . . . , n . n + 1 Drugi način. Enačbe (∗) zapišemo v ekvivalentni obliki: qi = (a − c − Q)+ , iz katere razberemo, da morajo biti vse količine qi enake, kar pomeni, da mora veljati: qi = (a − c − nqi)+ , to pa ima edino rešitev qi = (a − c)+/(n + 1), tako kot prej. 16. Označimo Qi = Q − qi. Tedaj lahko pišemo ui(q1, . . . , qn) = qi(1 − Qi − qi)+. Če je Qi ≥ 1, je ui = 0 ne glede na qi. Če pa je Qi < 1, je funkcija ui (spremenljivke qi) znotraj intervala (0, Qi) strogo pozitivna, izven njega pa je enaka nič. Zato bo maksimum dosežen v stacionarni točki. Iz ∂ui = 1 − Q ∂q i − 2qi dobimo, da bo to pri i qi = (1 − Qi)/2. Ločimo tri možnosti. Prva možnost : Qi ≥ 1 za vse i. Ni težko videti, da je vsak tak profil Nashevo ravnovesje. Druga možnost : Qi < 1 za vse i. Tedaj za vse i velja qi = (1−Qi)/2 ali ekvivalentno qi = 1 − Q, torej so vse terjatve qi enake. To pomeni, da je qi = 1 − nqi oziroma qi = 1/(n + 1). Tedaj je tudi Qi = (n − 1)/(n + 1) in to je res Nashevo ravnovesje. M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 55 Tretja možnost : obstaja tak i, da je Qi < 1, a tudi tak j, da je Qj ≥ 1. V tem primeru je tudi Q ≥ 1. Iz qi = 1 − Q sklepamo, da je 1 = Q + qi ≥ Q ≥ 1, to pa je možno le, če je Q = 1 in qi = 0. Toda potem je tudi Qi = 1, kar je protislovje. V tem primeru torej ni Nashevih ravnovesij. Če povzamemo – Nashevo ravnovesje je: • kjer je qi = 1/(n + 1) za vse i; tam vsako pleme dobi 1/(n + 1)2; • kjer je Qi ≥ 1 za vse i; tam vsako pleme dobi 0. Oglejmo si zdaj, koliko plemena dobijo, če vsako terja enako količino vira q. V tem primeru vsako pleme dobi q(1 − nq)+, kar je maksimalno pri q = 1/(2n), ko vsako pleme dobi 1/(4n). Brž ko je n > 1, je to strogo večje od 1/(n + 1)2, kolikor največ dobi v Nashevem ravnovesju. 17. Iz:  4p1 − 1  ; p  1 < p2  4(1 + p  1)2  u 4p 1(p1, p2) = 1 − 1 ; p1 = p2  8(1 + p  1)2    0 ; p1 > p2 ter dejstva, da za funkcijo f (p) = (4p − 1)/(1 + p)2 velja maxp∈ f (p) = f (2) = 7/9 N0 in f (1) > f (2)/2 sklepamo, da mora v Nashevem ravnovesju veljati naslednje: • Če je p2 ≥ 3, je p1 = 2. • Če je p2 = 1 ali p2 = 2, je p1 = 1. • Če je p2 = 0, je p1 ≥ 1. Velja tudi obratno – če zamenjamo p1 in p2. Od tod po nekaj sklepanja dobimo, da je edino Nashevo ravnovesje pri p1 = p2 = 1. 18. Dražbo lahko modeliramo kot strateško igro, kjer so akcije ponudbe bi, preferenčna funkcija posameznega kupca pa je v primeru, ko dobi dražbo, enaka razliki med subjektivno vrednostjo vi in ceno, ki jo mora za predmet plačati; sicer je enaka nič. Označimo z m = max{bj ; j = 1, . . . , n} maksimalno ponudbo, s p pa ceno, po kateri se proda predmet dražbe. Če denimo i-ti kupec da maksimalno ponudbo, je p = max{bj ; j = i}. Naj bo km število kupcev, ki dajo maksimalno ponudbo m, kp pa število kupcev, ki ponudijo p. Če je km = 1, je p < m, če pa je km ≥ 2, je p = m in posledično tudi kp = km. Preferenčna funkcija posameznega kupca se izraža v obliki:  vi − p ; bi = m > p  ui(b1, . . . , bn) = (vi − p)/km ; bi = m = p .  0 ; bi < m 56 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Recimo zdaj, da i-ti kupec spremeni svojo maksimalno ponudbo z bi na b , ostali i pa ponudijo toliko kot prej. Novi dobitek i-tega kupca se potem izraža na naslednji način.  vi − p ; b > p  i • Za bi = m > p je ui(b | b ) = (v = p . i i − p)/(kp + 1) ; bi  0 ; b < p i  vi − m ; b > m  i • Za bi = m > p je ui(b | b ) = (v = m . i i − m)/km ; bi  0 ; b < m i  vi − m ; b > m  i • Za bi < p je ui(b | b ) = (v = m . i i − m)/(km + 1) ; bi  0 ; b < m i Od tod dobimo, da je profil (b1, b2, . . . , bn) Nashevo ravnovesje natanko tedaj, ko velja: • Brž ko je bi = m > p, je vi ≥ p. • Brž ko je bi = m = p, je vi = p = m. • Brž ko je bi < m, je vi ≤ m. Nashevo ravnovesje, v katerem posamezen kupec zagotovo dobi dražbo, torej na- stopi, brž ko ta kupec ponudi ceno, ki je višja od vseh subjektivnih vrednosti za ostale kupce, le-ti pa ponudijo ceno, ki je nižja tako od zmagovalne ponudbe kot od subjektivne vrednosti za zmagovalca dražbe. Primer Nashevega ravnovesja pri dražbi s tremi kupci, kjer predmet dražbe dobi kupec, ki predmetu pripisuje najnižjo možno vrednost: b1 v3 v2 v1 b2 b3 1. kupec 2. kupec 3. kupec 19. Spet naj i-ti kupec ponudi najvišjo ceno. Če je ta strogo najvišja, je njegov dobiček enak vi − bi in se poveča, brž ko kupec svojo ponudbo nekoliko zniža (dovolj malo, da še vedno zagotovo dobi dražbo). Tak položaj torej nikoli ni Nashevo ravnovesje: v Nashevem ravnovesju si mora najvišjo ponudbo deliti k ≥ 2 kupcev. Pričakovani dobiček zmagovalca je potem enak (vi − bi)/k. Če kupec naslednjič spremeni po- nudbo na b , se njegov dobiček spremeni, brž ko je b = b > b i i i: če je bi i, je novi (pričakovani) dobiček enak vi −bi, če je b < b i i, pa je novi (pričakovani) dobiček enak M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 57 nič. Krajši račun pokaže, da je Nashevo ravnovesje možno le tedaj, ko je vi = bi. Za ostale kupce mora veljati vj ≤ vi. Sklep: Nashevo ravnovesje lahko nastopi le tedaj, ko si najvišjo subjektivno oceno vrednosti predmeta delita vsaj dva kupca. Med kupci, ki najbolj cenijo predmet, morata spet vsaj dva ponuditi ceno, ki se ujema s subjektivno oceno vrednosti predmeta, ostali pa morajo ponuditi manj. 58 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 2. Igre z mešanimi strategijami . . . 1. a) U (π) = 2 04, V (π) = 5 08, W (π) = 4 9. b) Preferenčni funkciji U in V sta ekvivalentni, ker je v = 2u + 1 in zato tudi V = 2U + 1. Funkcija W pa jima ni ekvivalentna, ker je npr. V (π) > V (b), medtem ko je W (π) < W (b). 2. Naj bosta U in V pripadajoči preferenčni funkciji. Če je množica, na kateri vse funkcije delujejo, A = {a1, . . . , an}, označimo ui := u(ai) in vi := v(ai). Označimo izjavi, za kateri želimo dokazati, da sta ekvivalentni: • E: U in V sta kot preferenčni funkciji ekvivalentni. • L: Obstajata taka b ∈ R in c > 0, da je v = cu + b, t. j. vk = cuk + b za vse indekse k. a Prvi korak: L ⇒ E. Če je namreč v = cu + b in π = 1 · · · an , je tudi: p1 · · · pn n n n V (π) = pkvk = pk(cuk + b) = c piuk + b = c U (π) + b , k=1 k=1 k=1 zato sta U in V ekvivalentni. V nadaljnjih korakih bomo dokazali nasprotno implikacijo, t. j. E ⇒ L. Drugi korak. Implikacija velja, če je ena od funkcij u in v konstantna. Ker sta tudi u in v ekvivalentni, morata biti v tem primeru obe konstantni, denimo u ≡ u0 in v ≡ v0. Tedaj pa lahko pišemo v = 1 · u + (v0 − u0). Od tod naprej lahko privzamemo, da sta u in v obe nekonstantni. Tretji korak. Če sta u in v nekonstantni, je izjava L ekvivalentna izjavi: • D: obstajata taka indeksa i in j, da je ui < uj, vi < vj in da za vsak k velja: vk − vi u = k − ui . (∗) vj − vi uj − ui Najprej, če sta u in v nekonstantni, gotovo obstajata taka i in j, da je ui < uj. Če velja L, je tedaj tudi vi < vj in tudi (∗) zlahka preverimo. Torej iz L sledi D. Privzemimo zdaj D. Zvezo (∗) lahko zapišimo v obliki: v v v j − vi j − vi k = uk + vi − ui . uj − ui uj − ui Ker je vj−vi > 0, velja L. uj −ui Četrti korak. Če velja E, sta za poljubne koeficiente α1, . . . , αn, za katere je α1 + · · · + αn = 0, števili r := n α α i=1 iui in s := n i=1 ivi istega predznaka. Tu koeficienti αi predstavljajo spremembo loterije, r in s pa predstavljata spremembi ustreznih preferenčnih funkcij. Natančneje, privzemimo, da obstajata taki loteriji: a a π = 1 a2 · · · an in π = 1 a2 · · · an p1 p2 · · · pn p p · · · p 1 2 n M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 59 in tak M > 0, da je αi = M (p − p i i) za vse i. Tedaj je r = M U (π ) − U (π) in s = M V (π ) − V (π) in po trditvi E morata biti ti dve količini res istega predznaka. Preostane le še dokazati, da taka profila in konstanta M obstajajo. Zlahka se prepričamo, da konstrukcija: 1 1 α p i i := , M > n max{−α1, −α2, . . . , −αn} , p := + n i n M ustreza danim pogojem. S tem je korak zaključen. Peti korak. Če velja E ter sta u in v nekonstantni, velja D. Opazili smo že, da obstajata taka i in j, da je ui < uj. Ker sta tudi u in v kot preferenčni funkciji ekvivalentni, je tudi vi < vj. Dokazati moramo še zvezo (∗), ki jo lahko prepišemo v obliki: (uj − ui)(vk − vi) + (ui − uk)(vj − vi) = 0 oziroma αivi + αjvj + αkvk = 0, kjer je αi = uk − uj, αj = ui − uk in αk = uj − ui. Opazimo, da velja αi + αj + αk = 0, prav tako pa tudi αiui + αjuj + αkuk = 0. V četrtem koraku smo dokazali, da od tod sledi αivi + αjvj + αkvk = 0, torej velja D. Sklep. V prvem koraku smo dokazali, da velja L ⇒ E. V drugem koraku smo dokazali, da E ⇒ L velja, če je katera od funkcij u in v konstantna. Če sta obe nekonstantni, pa smo v petem koraku dokazali implikacijo E ⇒ D, v tretjem pa D ⇒ L. S tem je trditev dokazana. 3. Igro lahko opišemo s tabelo: C2 G2 C1 1, −1 −1, 1 , G1 −1, 1 1, −1 iz katere hitro vidimo, da čistih Nashevih ravnovesij ni. Oglejmo si zdaj profil mešanih strategij (π1, π2), kjer je: C C π 1 G1 2 G2 1 = , π . 1 − p p 2 = 1 − q q Iz: U1(π1, π2) = (1 − 2p)(1 − 2q) , U2(π1, π2) = −(1 − 2p)(1 − 2q) vidimo, da smo v mešanem Nashevem ravnovesju natanko tedaj, ko velja: • Če je q < 1/2, je p = 0. Če je q > 1/2, je p = 1. Če je q = 1/2, ni omejitev za p. • Če je p < 1/2, je q = 1. Če je p > 1/2, je q = 0. Če je p = 1/2, ni omejitev za q. To pa je možno natanko tedaj, ko je p = q = 1/2. 60 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 4. Najprej iz tabele razberemo, da sta (A, X) in (B, Y ) čisti Nashevi ravnovesji. Po- X Y iščimo zdaj mešana Nasheva ravnovesja oblike A, , kjer je 0 < q < 1. 1 − q q Princip indiferentnosti nam da pogoja: X Y X Y U1 A, ≥ U , U 1 − q q 1 B, 1 − q q 2(A, X ) = U2(A, Y ) . Drugi pogoj je očitno izpolnjen, iz prvega pa dobimo 1 − q ≥ 2q oziroma q ≤ 1/3. Pregled preostalih treh skupin profilov oblike, kjer eden izmed igralcev ubere čisto, drugi pa strogo mešano strategijo, pokaže, da v nobeni ni Nashevega ravnovesja, ker ne velja enakost, ki jo dobimo iz principa indiferentnosti. Poiščimo še Nasheva ravnovesja, pri katerih oba igralca strogo mešata, torej ra- A B X Y ziščimo profile oblike , , kjer je 0 < p, q < 1. Iz principa 1 − p p 1 − q q indiferentnosti dobimo: 1 − q = 2q , 0 = p , kar pomeni, da takih Nashevih ravnovesij ni. X Y Sklep: mešana Nasheva ravnovesja so natanko profili oblike A, , kjer 1 − q q je 0 ≤ q ≤ 1/3. 5. Koristnostna funkcija za strelca je verjetnost, da pride do gola, koristnostna funkcija za vratarja pa, da do gola ne pride. Zato lahko to modeliramo z naslednjo strateško igro (z mešanimi strategijami): Lv Dv . . . . Ls 94 97, 5 03 58 30, 41 70 . . . . . Ds 69 92, 30 08 92 91, 7 09 Iz tabele hitro razberemo, da ni čistih Nashevih ravnovesij, prav tako tudi ne ta- kih, kjer bi kateri od igralcev ubral čisto strategijo. Torej moramo mešana Nasheva L L ravnovesja iskati med profili s Ds , v Dv . Iz principa indiferen- 1 − p p 1 − q q tnosti dobimo enačbi: . . . . . . . . 5 03 + 25 05 p = 41 70 − 34 61 p , 94 97 − 36 67 q = 69 92 + 22 99 q , . . . . ki imata rešitvi p = 61 46%, q = 41 99%. Edino mešano Nashevo ravnovesje je torej: L D L D Strelci: . . Vratarji: . . , 38 54% 61 46% 58 01% 41 99% kar je zelo blizu opaženim frekvencam. M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 61 6. Iz principa indiferentnosti dobimo: C R C R C R U1 T, = U ≥ U , 1/3 2/3 1 B, 1/3 2/3 1 M, 1/3 2/3 T B T B T B U2 , C = U , R ≥ U , L , 3/4 1/4 2 3/4 1/4 2 3/4 1/4 od koder dobimo, da je dani profil mešano Nashevo ravnovesje natanko tedaj, ko je c ≤ 1, e = 5 in f = 1. Vrednosti ostalih parametrov so lahko poljubne. 7. Poiščimo najprej čista Nasheva ravnovesja. Profil (A, X) je Nashevo ravnovesje za a ≥ 4, profil (A, Y ) za a ≤ 2, profil (B, X) za a ≤ 1, profil (B, Y ) pa za a ≥ 3. Drugače povedano, čista Nasheva ravnovesja so: • Za a ≤ 1: (A, Y ) in (B, X). • Za 1 < a ≤ 2: (A, Y ). • Za 2 < a < 3 ni čistih Nashevih ravnovesij. • Za 3 ≤ a < 4: (B, Y ). • Za a ≥ 4: (A, X) in (B, Y ). Oglejmo si zdaj Nasheva ravnovesja, kjer eden izmed igralcev igra čisto strategijo, drugi pa strogo meša. Iz principa indiferentnosti dobimo, da se to zgodi kvečjemu takrat, ko je a ∈ {1, 2, 3, 4}. Podrobnosti: A B • a = 1: , X , p ≥ 3/5. 1 − p p A B • a = 2: , Y , p ≤ 2/3. 1 − p p X Y • a = 3: B, , q ≥ 2/3. 1 − q q X Y • a = 4: A, , q ≤ 3/5. 1 − q q Zdaj pa si oglejmo še primer, ko oba strogo mešata, torej profile oblike A B X Y , , kjer je 0 < p, q < 1. Iz principa indiferentnosti po 1 − p p 1 − q q krajšem računu dobimo: 4 − a 1 − a p = , q = , 7 − 2a 3 − 2a Verjetnost p pripada intervalu (0, 1), če je a ∈ (−∞, 3) ∪ (4, ∞), verjetnost q pa, če je a ∈ (−∞, 1) ∪ (2, ∞). Strogo mešano Nashevo ravnovesje torej obstaja natanko tedaj, ko je a ∈ (−∞, 1) ∪ (2, 3) ∪ (4, ∞). Mešana Nasheva ravnovesja glede na a so torej: 62 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER A B X Y • a < 1: (A, Y ), (B, X) in 3−a 4−a , 2−a 1−a . 7−2a 7−2a 3−2a 3−2a A B • a = 1: (A, Y ) in , X , p ≥ 3/5. 1 − p p • 1 < a < 2: (A, Y ). A B • a = 2: , Y , p ≤ 2/3. 1 − p p A B X Y • 2 < a < 3: 3−a 4−a , 2−a 1−a . 7−2a 7−2a 3−2a 3−2a X Y • a = 3: B, , q ≥ 2/3. 1 − q q • 3 < a < 4: (B, Y ). X Y • a = 4: (B, Y ) in A, , q ≤ 3/5. 1 − q q A B X Y • a > 4: (A, X), (B, Y ) in 3−a 4−a , 2−a 1−a . 7−2a 7−2a 3−2a 3−2a 8. Iz tabele hitro razberemo, da ni čistih Nashevih ravnovesij, prav tako tudi nobenega Nashevega ravnovesja, kjer bi kateri izmed igralcev ubral čisto strategijo. Raziščimo še ostale možnosti. Privzemimo splošni profil: A B C X Y Z , . a b c x y z Najprej raziščimo pogoje, ki izhajajo iz funkcije U1. To je potrebno narediti glede na to, katere akcije meša prvi igralec, dobljeni pogoji pa se nanašajo na profil drugega igralca. Izrazili bomo x = 1 − y − z. Izhodišče bo torej: A   3y + 5z  X Y Z U1 B , = 1 + y + 2z .   x y z    C 3 − 2y − 2z Če prvi igralec strogo meša akciji A in B, iz principa indiferentnosti dobimo: 3y + 5z = 1 + y + 2z ≥ 3 − 2y − 2z . Iz enačbe dobimo y = (1 − 3z)/2. Ko to vstavimo v neenačbo, dobimo z ≤ −1, kar ne sodi v profil. Če strogo meša A in C, dobimo: 3y + 5z = 3 − 2y − 2z ≥ 1 + y + 2z . Iz enačbe dobimo y = (3 − 7z)/5. Ko to vstavimo v neenačbo, dobimo z ≥ −1, kar je res za vsak profil. Poleg tega pa iz splošnih omejitev sledi tudi z ≤ 3/7. Če torej prvi igralec strogo meša A in C, nam njegova funkcija koristnosti postavi pogoje: 3 3 − 7z 2 + 2z 0 ≤ z ≤ , y = , x = . 7 5 5 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 63 Če strogo meša B in C, dobimo: 1 + y + 2z = 3 − 2y − 2z ≥ 3y + 5z . Iz enačbe dobimo y = (2 − 4z)/3. Ko to vstavimo v neenačbo, dobimo z ≤ −1, kar ne sodi v profil. Če pa strogo meša vse akcije, dobimo: 3y + 5z = 1 + y + 2z = 3 − 2y − 2z , kar ima rešitev y = 2, z = −1, kar spet ne sodi v profil (no, do tega bi lahko prišli brez reševanja sistema: pogoji za y in z so namreč tu strožji kot v primeru, ko prvi igralec meša npr. A in B, za ta primer pa vemo, da nima rešitve v profilih). V Nashevem ravnovesju lahko torej prvi igralec edino strogo meša A in C, torej lahko povsod postavimo b = 0. Iz rešitev za profil drugega igralca pa dobimo še, da le-ta ne more strogo mešati Y in Z. Raziščimo zdaj še pogoje, ki izhajajo iz funkcije U2. To je potrebno narediti glede na to, katere akcije meša drugi igralec, pri čemer lahko izločimo strogo mešanico Y in Z, ki ni v skladu s pogoji, ki smo jih dobili iz U1. Dobili bomo pogoje, ki se nanašajo na profil prvega igralca. Upoštevamo tudi, da prvi igralec meša le A in C, torej bo b = 0 in a = 1 − c. Izhodišče bo torej: A B C U2 , X Y Z = 4 − 4c 3 − c 3c . a b c Če drugi igralec strogo meša X in Y , iz principa indiferentnosti dobimo: 4 − 4c = 3 − c ≥ 3c , kar ima za rešitev c = 1/3, torej a = 2/3. Nadalje, ko upoštevamo, da je z = 0, dobimo še x = 2/5 in y = 3/5. To je mešano Nashevo ravnovesje. Če strogo meša X in Z, dobimo: 4 − 4c = 3c ≥ 3 − c , kar nima rešitve. Od tod dobimo tudi, da drugi igralec ne more strogo mešati vseh akcij, saj iz tega dobimo še strožje pogoje za b in c. A C X Y Sklep: edino mešano Nashevo ravnovesje je , . 2/3 1/3 2/5 3/5 9. Akcija A ne more biti dominirana, ker je U1(A, Z) > U1(B, Z) in U1(A, Z) > U1(C, Z). Podobno tudi akcije C, X, Y in Z ne morejo biti dominirane. Pač A C pa je akcija B strogo dominirana z mešano strategijo , brž ko je 1 − p p 3p > 1, 3 − 2p > 2 in 5 − 4p > 3, torej brž ko je 1/3 < p < 1/2. 64 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 10. To je strategija: A B D A B D . . . . . . . = . . . . 0 15 + 0 5 · 0 4 0 25 + 0 5 · 0 6 0 1 0 35 0 55 0 1 11. Najprej opazimo, da je akcija C strogo dominirana z mešano strategijo A B . Ko le-to izločimo, dobimo, da je v novi igri (ki ima ista Nasheva 1/2 1/2 X Z ravnovesja) akcija Y strogo dominirana z mešano strategijo ; čeprav 1/2 1/2 v prvotni igri ni dominirana, jo zdaj lahko izločimo iz iskanja Nashevih ravnovesij. A B X Z Po nekaj nadaljnjega računanja dobimo, da je , edino 4/7 3/7 1/5 4/5 mešano Nashevo ravnovesje. E F 12. Akcije A, B, C in D so dominirane z mešanico . Ko jih izločimo, 2/3 1/3 Y Z dobimo, da je akcija X dominirana z mešanico , akcija W pa z mešanico 2/3 1/3 Y Z (v obeh primerih gre celo za ekvivalenco glede na U 1/3 2/3 2). Ko za preostale akcije nastavimo princip indiferentnosti, dobimo, da je profil: E F Y Z , 3/4 1/4 2/3 1/3 mešano Nashevo ravnovesje igre. 13. V tej igri nobena akcija ni dominirana in je tako pri iskanju Nashevih ravnovesij ne moremo izločiti. Iz tabele razberemo, da čistih Nashevih ravnovesij ni. Med meša- nimi Nashevimi ravnovesji, pri katerih eden izmed igralcev ubere čisto strategijo, moramo pogledati profil, pri katerem prvi igralec meša A in C, drugi pa igra Y . Toda v tem primeru se prvemu igralcu bolj splača igrati B, zato ta profil ne more biti mešano Nashevo ravnovesje. Raziščimo še ostale možnosti. Privzemimo splošni profil: A B C X Y Z , . a b c x y z Najprej raziščimo pogoje, ki jih dobimo iz U1. Izrazili bomo x = 1 − y − z. Izhodišče bo torej: A   4 − y − 3z  X Y Z U1 B , = 4y + 2z .   x y z    C 1 + 2y + 2z Če prvi igralec strogo meša A in B, iz principa indiferentnosti dobimo: 4 − y − 3z = 4y + 2z ≥ 1 + 2y + 2z . M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 65 Iz enačbe dobimo y = 4/5 − z. Ko to vstavimo v neenačbo, dobimo z ≤ 3/10 in za vsak 0 ≤ z ≤ 3/10 tudi dejansko dobimo profil. Če torej prvi igralec meša A in B, nam funkcija koristnosti prvega igralca postavi pogoje: 3 4 1 0 ≤ z ≤ , y = − z , x = . 10 5 5 Če strogo meša A in C, dobimo: 4 − y − 3z = 1 + 2y + 2z ≥ 4y + 2z . Iz enačbe dobimo y = 1 − 5z/3. Ko to vstavimo v neenačbo, dobimo z ≥ 3/10. Iz splošnih omejitev dobimo še z ≤ 3/5. Funkcija koristnosti nam torej postavi pogoje: 3 3 5z 2z ≤ z ≤ , y = 1 − , x = . 10 5 3 3 Če strogo meša B in C, dobimo: 4y + 2z = 1 + 2y + 2z ≥ 4 − y − 3z . Iz enačbe dobimo y = 1/2. Ko to vstavimo v neenačbo, dobimo z ≥ 3/10. Iz splošnih omejitev dobimo še z ≤ 1/2. Funkcija koristnosti nam torej postavi pogoje: 3 1 1 1 ≤ z ≤ , y = , x = − z . 10 2 2 2 Če pa strogo meša vse tri akcije, dobimo: 4 − y − 3z = 4y + 2z = 1 + 2y + 2z , kar ima edino rešitev x = 1/5, y = 1/2, z = 3/10. Oglejmo si zdaj še pogoje, ki jih dobimo iz U2. Izrazili bomo a = 1 − b − c. Izhodišče bo torej: A B C U2 , X Y Z = 2 − 2b + 2c 5 − 4b − 4c 3 + b − c . a b c Če drugi igralec strogo meša X in Y , iz pogojev za U1 sledi, da prvi igralec meša le A in B, se pravi, da je c = 0. Iz principa indiferentnosti dobimo: 2 − 2b = 5 − 4b ≥ 3 + b , kar med profili nima rešitve. Če drugi igralec strogo meša X in Z, iz pogojev za U1 sledi, da prvi igralec meša le A in C, se pravi, da je b = 0. Iz principa indiferentnosti dobimo: 2 + 2c = 3 − c ≥ 5 − 4c . kar prav tako nima rešitve. 66 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Če drugi igralec strogo meša Y in Z, iz pogojev za U1 sledi, da prvi igralec meša le B in C, se pravi, da je b = 1 − c. Iz principa indiferentnosti dobimo: 1 = 4 − 2c ≥ 4c . kar prav tako nima rešitve med profili. Če pa drugi igralec strogo meša vse tri akcije, iz principa indiferentnosti dobimo: 2 − 2b + 2c = 5 − 4b − 4c = 3 + b − c , kar ima edino rešitev a = 5/12, b = 1/8, c = 11/24. To pomeni, da mora v tem primeru tudi prvi igralec strogo mešati vse akcije. Dobimo edino Nashevo ravnovesje: A B C X Y Z , . 5/12 1/8 11/24 1/5 1/2 3/10 14. Najprej opazimo, da pri drugem igralcu akcija X strogo dominira akcijo W , torej lahko slednjo odstranimo. Drugih dominacij ni. Profil (C, X) je edino čisto Nashevo ravnovesje. Ni nobenega Nashevega ravnovesja, kjer bi eden od igralcev ubral čisto strategijo, drugi pa bi strogo mešal vsaj dve akciji. Raziščimo še možnosti, kjer vsak od igralcev strogo meša vsaj dve akciji. Privze- mimo splošni profil: A B C X Y Z , . a b c x y z Najprej raziščimo pogoje, ki izhajajo iz funkcije U1. To je potrebno narediti glede na to, katere akcije meša prvi igralec, dobljeni pogoji pa se nanašajo na profil drugega igralca. Izrazili bomo x = 1 − y − z. Izhodišče bo torej: A   3y + 3z  X Y Z U1 B 2 − 2y   , x y z  =   . C 3 + y − 3z Če prvi igralec strogo meša A in B, iz principa indiferentnosti dobimo: 3y + 3z = 2 − 2y ≥ 3 + y − 3z . Iz enačbe dobimo z = (2 − 5y)/3. Ko to vstavimo v neenačbo, dobimo y ≤ 1/8. Brž ko je 0 ≤ y ≤ 1/8, se to sklada tudi s splošnimi omejitvami. Če torej prvi igralec strogo meša A in B, nam njegova funkcija koristnosti postavi pogoje: 1 2 − 5y 1 + 2y 0 ≤ y ≤ , z = , x = . 8 3 3 Drugi igralec lahko torej tedaj strogo meša bodisi akciji X in Z bodisi vse tri akcije. Če prvi igralec strogo meša A in C, dobimo: 3y + 3z = 3 + y − 3z ≥ 2 − 2y . M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 67 Iz enačbe dobimo y = 3/2 − 3z. Ko to vstavimo v neenačbo, dobimo z ≤ 11/24. Iz splošnih omejitev dobimo še z ≥ 1/4. Če torej prvi igralec strogo meša A in C, nam njegova funkcija koristnosti postavi pogoje: 1 11 3 1 ≤ z ≤ , y = − 3z , x = 2z − . 4 24 2 2 Drugi igralec lahko torej tedaj strogo meša bodisi akciji Y in Z bodisi vse tri akcije. Če prvi igralec strogo meša B in C, dobimo: 2 − 2y = 3 + y − 3z ≥ 3y + 3z . Iz enačbe dobimo y = z − 1/3. Ko to vstavimo v neenačbo, dobimo z ≤ 11/24. Iz splošnih pogojev dobimo še z ≥ 1/3. Če torej prvi igralec strogo meša B in C, nam njegova funkcija koristnosti postavi pogoje: 1 11 1 4 ≤ z ≤ , y = z − , x = − 2z . 3 24 3 3 Spet torej dobimo, da lahko tedaj drugi igralec strogo meša bodisi X in Z bodisi vse tri akcije. Če pa prvi igralec strogo meša vse tri akcije, dobimo: 3y + 3z = 2 − 2y = 3 + y − 3z , kar ima rešitev x = 5/12, y = 1/8, z = 11/24, se pravi, da mora drugi igralec strogo mešati vse tri akcije. Iz pogojev, ki izhajajo iz funkcije U1, smo dobili, da imamo pri Nashevih ravnovesjih kvečjemu še naslednji dve možnosti: • Prvi igralec strogo meša A in B ali B in C, drugi pa strogo meša X in Z. • Prvi igralec strogo meša A in C, drugi pa strogo meša Y in Z. • Drugi igralec strogo meša vse tri akcije. Raziščimo zdaj še pogoje, ki nam jih postavlja funkcija U2. Če izrazimo a = 1−b−c, velja:  b + 3c  A B C U2 , X Y Z = 3 − 3b − c a b c   . 2 + b − 2c Če drugi igralec strogo meša akciji X in Z, velja: b + 3c = 2 + b − 2c ≥ 3 − 3b − c Iz enačbe dobimo c = 2/5. To pomeni, da lahko prvi igralec strogo meša le B in C. V tem primeru je b = 3/5, velja pa tudi neenačba. Ko v pogoje pri U1 vstavimo B C X Z y = 0, dobimo mešano Nashevo ravnovesje , . 3/5 2/5 2/3 1/3 Če drugi igralec strogo meša akciji Y in Z, prvi meša le A in C, torej je b = 0. Dobimo: 3 − c = 2 − 2c ≥ 3c 68 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Iz enačbe dobimo c = −1, kar ni v redu. Če pa drugi igralec strogo meša vse tri akcije, velja: b + 3c = 2 + b − 2c = 3 − 3b − c , kar ima rešitev a = 1/4, b = 7/20, c = 2/5. Tedaj mora tudi prvi igralec strogo mešati vse akcije in dobimo še eno mešano Nashevo ravnovesje. Sklep: mešana Nasheva ravnovesja so: B C X Z (C, X) , , in 3/5 2/5 2/3 1/3 A B C X Y Z , . 1/4 7/20 2/5 5/12 1/8 11/24 15. Najprej si oglejmo, katere akcije igralca v Nashevem ravnovesju mešata. Opazimo naslednje: • Prvemu igralcu se splača mešati le tiste akcije, ki jih meša drugi igralec. Nata- nčneje, če bi v določenem profilu prvi igralec v mešanico vključil tudi akcijo, ki je drugi igralec ne bi, bi obstajala mešana strategija, kjer bi prvi igralec dobil strogo več. Zato tak profil ne more biti Nashevo ravnovesje. • Če prvi igralec ne meša vseh akcij, se drugemu splača mešati le tiste akcije, ki jih prvi igralec ne meša. Od tod najprej dobimo, da mora prvi igralec strogo mešati vse akcije, nato pa še, da mora vse akcije strogo mešati tudi drugi igralec. Označimo vrednosti kart z v1, v2, . . . , vm. Naj prvi igralec izbere i-to karto z verjetnostjo pi, drugi pa z verjetnostjo qi. Iz principa indiferentnosti za koristnostno funkcijo prvega igralca dobimo enačbe: q1v1 = q2v2 = · · · = qmvm , ki imajo edino rešitev: 1 q vi i = ; i = 1, 2, . . . , m . 1 + 1 + · · · + 1 v1 v2 vm Iz koristnostne funkcije drugega igralca pa dobimo analogne enačbe za verjetnosti pi, torej mora biti pi = qi. Opomba: kasneje bomo videli, da je to kvadratna igra z ničelno vsoto. Za te igre velja, da je, če imajo eno samo mešano Nashevo ravnovesje, kjer oba igralca strogo mešata vse akcije, to edino mešano Nashevo ravnovesje. 16. Najprej razberemo čista Nasheva ravnovesja (B, X, L), (T, Y, L) in (B, Y, R). Iz tabele tudi hitro razberemo, da ni Nashevih ravnovesij, pri katerem bi dva igralca igrala čisti strategiji, eden pa bi mešal. Pregledati moramo torej še primere, ko vsaj dva igralca (strogo) mešata. Označimo splošni profil: T B X Y L R , , . 1 − p p 1 − q q 1 − r r M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 69 Če prvi igralec igra T , druga dva pa mešata, dobimo: X L R 1 U2 T , , = , Y 1 − r r 2 + 2r od koder sledi, da takega Nashevega ravnovesja ni. Če prvi igralec igra B in druga dva mešata, dobimo: X L R 1 1 U2 B , , = =⇒ r = , Y 1 − r r 2r 2 X Y L 1 1 U3 B , , = =⇒ q = , 1 − q q R 2q 2 T X Y L R 2 U1 , , = , B 1/2 1/2 1/2 1/2 3 X Y L R od koder dobimo Nashevo ravnovesje B , , . 1/2 1/2 1/2 1/2 Če drugi igralec igra X, prvi in tretji pa mešata, dobimo: T L R 2 U1 , X , = , B 1 − r r 3 + 3r od koder sledi, da takega Nashevega ravnovesja ni. Če drugi igralec igra Y ter prvi in tretji mešata, dobimo: T L R 2 2 U1 , Y , = =⇒ r = , B 1 − r r 3r 3 T B L 1 1 U3 , Y , = =⇒ p = , 1 − p p R 2p 2 T B X L R 1 U2 , , = , 1/2 1/2 Y 1/3 2/3 7/3 T B L R od koder dobimo Nashevo ravnovesje , Y , . 1/2 1/2 1/3 2/3 Če tretji igralec igra L, prva dva pa mešata, dobimo: T X Y 2 1 U1 , , R = =⇒ q = , B 1 − q q 3 − 3q 3 T B X 1 1 U2 , , L = =⇒ p = , 1 − p p Y 2 − 2p 2 T B X Y L 1 U3 , , = , 1/2 1/2 2/3 1/3 R 1/6 T B X Y od koder dobimo Nashevo ravnovesje , , L . 1/2 1/2 2/3 1/3 70 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Če tretji igralec igra R, prva dva pa mešata, dobimo: T X Y 2 U1 , , R = , B 1 − q q 6 − 3r od koder sledi, da takega Nashevega ravnovesja ni. Privzemimo zdaj, da vsi trije igralci mešajo. Velja: T X Y L R 2 1 U1 , , = =⇒ q = r + , B 1 − q q 1 − r r 3 − 3q + 3r 3 T B X L R 1 1 U2 , , = =⇒ p = r + , 1 − p p Y 1 − r r 2 − 2p + 2r 2 T B X Y L 1 U3 , = =⇒ 2pq = 1 . 1 − p p 1 − q q R 2pq Ko prvi dve enačbi vstavimo v tretjo in uredimo, dobimo kvadratno enačbo 6r2 + √ 5r − 2 = 0, ki ima rešitvi r1,2 = (−5± 73)/12, a samo rešitev s pozitivnim korenom nam da profil. To je še zadnje Nashevo ravnovesje: T B X Y L R √ √ , √ √ , √ √ 11− 73 1+ 73 13− 73 −1+ 73 17− 73 −5+ 73 12 12 12 12 12 12 ali približno: T B X Y L R . . , . . , . . . 0 205 0 795 0 371 0 629 0 705 0 295 17. Opazimo, da pri prvem igralcu akcija T dominira akcijo B. Dominacija sicer ni stroga, nam pa vseeno pomaga izločiti kar nekaj profilov. Iz: X Y L R U1 T, , = 1 , 1 − q q 1 − r r X Y L R U1 B, , = (1 − q)(1 − r) + qr 1 − q q 1 − r r sledi, da lahko akcijo B izločimo, brž ko je (1 − q)(1 − r) + qr < 1. Zaradi dominacije je nujno (1 − q)(1 − r) + qr < 1, torej nova mešana Nasheva ravnovesja dobimo kvečjemu, če je (1 − q)(1 − r) + qr = 1. Nekaj analize pokaže, da je v okviru splošnih omejitev za q in r to res samo v dveh primerih: ko je q = r = 0 in ko je q = r = 1 ali z drugimi besedami, ko drugi in tretji igralec igrata (X, L) ali (Y, R). Ločimo torej tri možnosti: 1. Prvi igralec igra T . V tem primeru hitro vidimo, da morata oba igralca mešati. Če se držimo oznak od prej, iz principa indiferentnosti dobimo 2 = 1 + 3r in 3 = 4 − 3q, od koder dobimo mešano Nashevo ravnovesje: X Y L R T, , . 2/3 1/3 1/2 1/2 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 71 2. Drugi igralec igra X, tretji pa L. Iz pogojev: T B T B U2 , X, L ≥ U , Y, L , 1 − p p 2 1 − p p T B T B U3 , X, L ≥ U , X, R 1 − p p 2 1 − p p dobimo družino mešanih Nashevih ravnovesij: T B 1 1 , X, L ; ≤ p ≤ . 1 − p p 3 2 3. Drugi igralec igra Y , tretji pa R. Tu pa pogoja za koristnostni funkciji drugega in tretjega igralca nista izpolnjena in ne dobimo mešanih Nashevih ravnovesij. 18. Ločimo možnosti glede na to, koliko igralcev igra čisto in koliko jih strogo meša. Prva možnost: vsi igrajo čisto. Če vsi vržejo enako, se vsakemu splača zamenjati akcijo, saj pred zamenjavo ne dobi nič, po zamenjavi pa vsaj dva evra (seveda ob predpostavki, da druga dva igralca akcije ne zamenjata). Zato to ni Nashevo ravnovesje. Če dva igralca vržeta grb, eden pa cifro, se tistemu, ki vrže grb, prav tako splača zamenjati akcijo: pred zamenjavo plača dva evra, po zamenjavi pa le en evro. Zato tudi to ni Nashevo ravnovesje. Končno si oglejmo še primer, ko dva vržeta cifro, eden pa grb. Igralec, ki vrže grb, dobi dva evra, če bi zamenjal akcijo, pa ne bi dobil ničesar. Igralec, ki vrže cifro, pa plača en evro; če bi zamenjal akcijo, bi plačal dva evra. Zato ta možnost je Nashevo ravnovesje. Formalno gledano ima torej igra tri čista Nasheva ravnovesja, pri katerih dva vržeta cifro, eden pa grb. Druga možnost: dve igrata čisto, eden pa strogo meša. Takih Nashevih ravnovesij ni, ker za tistega, ki meša, nikoli ne dobimo indiferentnosti (glej prejšnji primer). Tretja možnost: eden igra čisto, dva pa strogo mešata. Recimo najprej, da eden ve- dno vrže cifro, od drugih dveh pa vsak vrže grb z verjetnostjo p in cifro z verjetnostjo 1 − p. Igralec, ki meša, ima pričakovani dobiček 2 − 4p, če namesto tega vedno vrže grb, in −p, če namesto tega vedno vrže cifro. Pri p = 2/3 je indiferenten. Takrat ima igralec, ki vedno vrže cifro, pričakovani dobiček 4/3, če zamenja strategijo, tako da vedno vrže grb, pa ima pričakovani dobiček −2/3. Dobimo torej še tri mešana Nasheva ravnovesja, kjer eden od igralcev vedno vrže cifro, od ostalih dveh pa vsak vrže grb z verjetnostjo 2/3 in cifro z verjetnostjo 1/3. Ne obstaja pa mešano Nashevo ravnovesje, kjer bi eden od igralcev vedno vrgel grb, preostala dva pa bi mešala z enakima verjetnostma za grb. Če je namreč ta enaka p, ima igralec, ki meša, pričakovani dobiček 2p − 2, če namesto tega vedno vrže grb, in 5p − 1, če namesto tega vedno vrže cifro. Indiferentnost dobimo pri p = −1/3, kar ni ustrezno. Četrta možnost: vsi trije strogo mešajo. Poiščimo mešano Nashevo ravnovesje, kjer vsak od igralcev vrže grb z verjetnostjo p, cifro pa z verjetnostjo 1 − p. Recimo, da 72 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER je to prvi igralec. Iz: C C G C G 6p2 − 2p U1 , , = G 1 − p p 1 − p p 6p2 − 8p + 2 dobimo, da Nashevo ravnovesje nastopi, če je 6p2 − 2p = 6p2 − 8p + 2, torej p = 1/3. Nashevo ravnovesje torej nastopi, brž ko vsak od igralcev vrže grb z verjetnostjo 1/3 in cifro z verjetnostjo 2/3. Opomba. Ta naloga je poučna, ker je to simetrična igra z ničelno vsoto, a vendar obstajajo Nasheva ravnovesja, kjer je prisoten transfer. Pri le dveh igralcih do tega ne more priti (glej 36. nalogo). 19. a) Če je sodelavec prizadeven, je njegova koristnostna funkcija enaka 3 ln(1 + p) − 1, če pa se iz prizadevnega spremeni v lenega, je njegova nova koristnost enaka 3 ln p. Podobno, če je sodelavec len, je njegova koristnostna funkcija enaka 3 ln(1 + p), če pa se spremeni v prizadevnega, je nova koristnost enaka 3 ln(2 + p) − 1. Profil je torej Nashevo ravnovesje natanko tedaj, ko velja: 3 ln(1 + p) − 1 ≥ 3 ln p , brž ko je p ≥ 1 , 3 ln(1 + p) ≥ 3 ln(2 + p) − 1 , brž ko je p ≤ 4 , . . Če je p > 0, je prvi pogoj ekvivalenten p ≤ 1/ e1/3 − 1 = 2 53, drugi pa p ≥ . . 2 − e1/3 / e1/3 − 1 = 1 53. Nashevo ravnovesje torej nastopi natanko tedaj, ko sta prizadevna delavca natanko dva. Takih profilov je 5 = 10. 2 b) Naj bo delavec prizadeven z verjetnostjo q in len z verjetnostjo 1 − q, kjer je 0 < q < 1. Po principu indiferentnosti mora veljati: 3 4q(1 − q)3 ln 2 + 6q2(1 − q)2 ln 3 + 4q3(1 − q)3 ln 4 + q4 ln 5 = = 3 q4 ln 2 + 4q(1 − q)3 ln 3 + 6q2(1 − q)2 ln 4 + 4q3(1 − q)3 ln 5 + q4 ln 6 − 1 oziroma: 3 4 5 6 3 q4 ln 2 + 4q(1 − q)3 ln + 6q2(1 − q)2 ln + 4q3(1 − q) ln + q4 ln = 1 . 2 3 4 5 . . Če vstavimo q = 0, je leva stran enaka 3 ln(6/5) = 0 547, če pa vstavimo q = 1, . . je enaka 3 ln 2 = 2 079. Ker je leva stran enačbe zvezna funkcija spremenljivke q, ima zgornja enačba za 0 < q < 1 vsaj eno rešitev. Podrobnejša numerična analiza . . pokaže, da ima enačba natanko eno rešitev, in sicer q = 0 515. 20. a) Igralci so mimoidoči, vsak ima dve akciji: K (klicati policijo) in I (ignorirati). Funkcije koristnosti lahko zapišemo s formulo: ui(a1, a2, . . . , an) = −c 1(ai = K) − s 1(a1 = a2 = · · · = an = I) , kjer je 1(A) = 1, če je izjava A pravilna, in 1(A) = 0, če je napačna. b) Ločimo več primerov glede na to, koliko mimoidočih pokliče policijo. M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 73 1) Nihče ne pokliče policije. V tem primeru so koristnostne funkcije vseh mi- moidočih enake −s; če se posamezen mimoidoči premisli in naslednjič kliče policijo, se njegova funkcije koristnosti poveča za s − c > 0, torej to ni Nashevo ravnovesje. 2) Natanko eden pokliče policijo. Koristnostna funkcija tistega, ki pokliče policijo, je −c in se zmanjša za s − c, če se premisli. Koristnostna funkcija tistega, ki ne pokliče policije, pa je 0 in se zmanjša za c, če se premisli. Torej je to Nashevo ravnovesje. 3) Vsaj dva pokličeta policijo. V tem primeru pa se koristnostna funkcija tistega, ki pokliče policijo, poveča za c, če se premisli, kar pomeni, da to ni Nashevo ravnovesje. c) Gledamo profil, pri katerem vsak pokliče policijo z verjetnostjo p ∈ (0, 1). Če posamezni mimoidoči svojo strategijo zamenja s čisto strategijo K, je njegova kori- stnostna funkcija enaka −c, če jo zamenja z I, pa je enaka −s(1−p)n−1. Po principu indiferentnosti mora biti oboje enako, kar je res za: c p = 1 − n−1 . s d) Verjetnost, da vsaj eden pokliče, je enaka: c n/(n−1) 1 − , s kar je res padajoča funkcija števila mimoidočih n. 21. a) Oglejmo si najprej primer, ko gre k fantov z gotovostjo osvajat blondinko, še m fantov z verjetnostmi q1, q2, . . . , qm (neodvisno drug od drugega), preostali pa gredo z gotovostjo osvajat manj privlačna dekleta. Verjetnost, da bo blondinka v tem primeru izbrala posameznega fanta, ki jo je šel osvajat, označimo s pk(q1, . . . , qm): to je pričakovana vrednost recipročne vrednosti števila fantov, ki so jo šli osvajat. Velja rekurzivna zveza: pk(q1, . . . , qm) = (1 − qm)pk(q1, . . . , qm−1) + qmpk+1(q1, . . . , qm−1) (ločimo primer, ko gre m-ti fant osvajat manj privlačno dekle, in primer, ko gre osvajat blondinko). Če z označimo prazen argument, seveda velja pk( ) = 1/k. Na ta način lahko vse vrednosti rekurzivno izračunamo. Opazimo pa še dvoje stvari: • Velja p1( ) > p2( ) > p3( ) > . . . Rekurzivno lahko dokažemo, da ta stroga monotonost velja za poljuben argument: p1(q1, . . . , qm) > p2(q1, . . . , qm) > . . .. • Iz prejšnjega in iz rekurzivne zveze sledi, da je pk(q1, . . . , qm) ≤ 1/k. Oboje sledi tudi iz dejstva, da je pk(q1, . . . , qm) pričakovana vrednost ustrezne reci- pročne vrednosti. 74 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Če zdaj z B označimo akcijo, da gre fant osvajat blondinko, z M pa akcijo, da gre osvajat manj privlačno dekle, velja: M B M B M B M B Ui , . . . , , M, , . . . , = 2 1 − q1 q1 1 − qi−1 qi+1 1 − qi+1 qi+1 1 − qn qn M B M B M B M B Ui , . . . , , B, , . . . , = 1 − q1 q1 1 − qi−1 qi+1 1 − qi+1 qi+1 1 − qn qn = 3p1(q1, . . . , qi−1, qi+1, . . . , qn) . Denimo najprej, da gre i-ti fant osvajat blondinko z verjetnostjo 1 in da ni edini, ki gre osvajat blondinko s strogo pozitivno verjetnostjo: naj bo še qj > 0. Če je qj = qi, je torej 0 < qj < 1 in v Nashevem ravnovesju velja princip indiferentnosti, iz katerega sledi: 2 p1(q1, . . . , qj−1, qj+1, . . . , qn) = . 3 Če označimo: p a k (q1, . . . , qi−1, qi+1, . . . , qj−1, qj+1, . . . , qn) ; i < j k := , pk(q1, . . . , qj−1, qj+1, . . . , qi−1, qi+1, . . . , qn) ; i > j iz rekurzivne formule sledi a2 = 2/3. Toda prej smo videli, da je a2 ≤ 1/2, kar je protislovje. V Nashevem ravnovesju torej noben fant ne gre z gotovostjo osvajat blondinke. Za poljubna dva, i-tega in j-tega, ki jo gresta osvajat s strogo pozitivnima verjetnostma, torej velja princip indiferentnosti, ki ga lahko podobno kot prej zapišemo v obliki: 2 (1 − qj)a1 + qja2 = (1 − qi)a1 + qia2 = , 3 od koder sledi (qj − qi)(a2 − a1) = 0. Prej smo dognali, da je a1 > a2, torej mora biti qi = qj. b) Za m ≥ 2 bo dani profil Nashevo ravnovesje natanko tedaj, ko bo veljalo: 2 2 p1(qm, . . . , qm) = in p1(qm, . . . , qm) ≤ , 3 3 m−1 m pri čemer je neenakost zahtevana le za primer, ko eden od fantov sploh ne gre osvajat blondinke. Toda ker je: p1(qm, . . . , qm) = (1 − qm)p1(qm, . . . , qm) + qmp2(qm, . . . , qm) ≤ p1(qm, . . . , qm) , m m−1 m−1 m−1 je neenakost avtomatično izpolnjena. Enakost pa je rešljiva, ker je: 1 p1(0, . . . , 0) = p1( ) = 1 in p1(1, . . . , 1) = pm( ) = , m m−1 m−1 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 75 iz rekurzivne formule pa sledi, da je p1 zvezna v vseh argumentih. Če več, rešitev je enolična, ker prav tako iz rekurzivne formule in stroge monotonosti sledi, da je p1 strogo padajoča v vseh argumentih. Primer, ko je m = 1, moramo obravnavati posebej, ker ne velja sklep, da mora biti verjetnost, da gre fant osvajat blondinko, strogo manjša od 1. Princip indiferen- tnosti ni izpolnjen, ker je p1( ) = 1 = 2/3. Edini fant, ki gre s strogo pozitivno verjetnostjo osvajat blondinko, lahko v mešanem Nashevem ravnovesju to počne le z verjetnostjo 1. To dejansko je mešano Nashevo ravnovesje: če se fant, ki gre osvajat blondinko, dobi 3, če se premisli, pa dobi 2. Nasprotno njegov kolega, ki ne gre osvajat blondinke, dobi 2, če se premisli, da dobi 3/2. Opazimo še, da profil, ko nobeden od fantov nikoli ne gre osvajat blondinke, ni mešano Nashevo ravnovesje: v tem primeru namreč vsi dobijo 2, kdor se premisli, pa dobi 3. Če je torej v skupini n fantov, obstaja 2n−1 mešanih Nashevih ravnovesij. c) Že v prejšnji točki smo izračunali, da je q1 = 1. Nadalje velja: q p1(q) = (1 − q)p1( ) + qp2( ) = 1 − , 2 . . od koder dobimo q2 = 2/3 = 0 667. Končno velja še: q p1(q, q) = (1 − q) p1(q) + q p2(q) = (1 − q) 1 − + q (1 − q) p2( ) + q p3( ) = 2 q2 = 1 − q + , 3 √ . . od koder dobimo q2 = 3 − 2 /2 = 0 382. 22. Najprej tabeliramo koristnostno funkcijo U1, kjer prvi igralec igra čisto strategijo, drugi pa meša: X Y a U1 a, 1 − q q A 4 − 4q B 2 − q C 6q D 2 + q E 6 − 12q Akcijo B lahko iz zgornje ovojnice takoj izločimo, saj je U1(B, X) < U1(E, X), za X Y X Y q > 0 pa velja U1 B, < U (da se tudi videti, da 1 − q q 1 D, 1 − q q je akcija B strogo dominirana). Preostale uredimo po strminah: E, A, D, C. Prvi korak. Za začetno zgornjo ovojnico postavimo E. Drugi korak. Daljici, ki pripadata E in A, se sekata pri q = 1 . Nova zgornja 4 ovojnica: • E za 0 ≤ q < 1 ; 4 • E in A za q = 1 ; 4 76 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER • A za 1 < q ≤ 1. 4 Tretji korak. Daljici, ki pripadata A in D, se sekata pri q = 2 , kar je več kot 1 . 5 4 Nova zgornja ovojnica: • E za 0 ≤ q < 1 ; 4 • E in A za q = 1 ; 4 • A za 1 < q < 2 ; 4 5 • A in D za q = 2 ; 5 • D za 2 < q < 1. 5 Četrti korak. Daljici, ki pripadata D in C, se sekata pri q = 2 , kar je isto kot prej. 5 Končna zgornja ovojnica je tako: • E za 0 ≤ q < 1 ; 4 • E in A za q = 1 ; 4 • A za 1 < q < 2 ; 4 5 • A, C in D za q = 2 ; 5 • C za 2 < q ≤ 1. 5 Slika: U1( , q) 6 C 4 D 2 B A q 0 (X) 1 (Y ) −2 −4 E −6 Zdaj pa pogledamo, kako se na zgornji ovojnici obnaša koristnostna funkcija drugega igralca. Za 0 ≤ q < 1/4 upoštevamo U2(E, X) > U2(E, Y ), kar pomeni, da mora biti q = 0. Dobimo čisto Nashevo ravnovesje: (E, X) . Za q = 1 iz principa indiferentnosti dobimo mešano Nashevo ravnovesje: 4 A E X Y 1 1 , 3 1 . 2 2 4 4 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 77 Za 1 < q < 2 ne dobimo ničesar, saj ni indiferentnosti. Za q = 2 po principu 4 5 5 indiferentnosti dobimo družino mešanih Nashevih ravnovesij: A C D X Y 1 1 , ; 0 ≤ c ≤ . − c c 2 3 2 3 3 3 5 5 Končno za 2 < q ≤ 1 upoštevamo U 5 2(C, X ) < U2(C, Y ), kar pomeni, da mora biti q = 1, in dobimo čisto Nashevo ravnovesje: (C, Y ) . B C 23. Najprej opazimo, da je akcija A strogo dominirana z mešanico , brž ko 1 − p p B C je 1/2 < p < 1. Zgornjo ovojnico koristnostne funkcije U2 na mešanicah 1 − p p tvorijo: • J za 0 ≤ p < 1 ; 5 • J in I za p = 1 ; 5 • I za 1 < p < 1 ; 5 4 • I in M za p = 1 ; 4 • M za 1 < p < 1 ; 4 2 • M in K za p = 1 ; 2 • K za 1 < p < 3 ; 2 4 • K in L za p = 3 ; 4 • L za 3 < p < 1. 4 • L in N za p = 1. Mešana Nasheva ravnovesja: B C 1 1 B C K L , I za ≤ p ≤ , , , 1 − p p 5 4 3/4 1/4 2/3 1/3 L N C, za 0 ≤ q ≤ 1/2 . 1 − q q 24. Vrednost je 3, dosežena pa je v čistem Nashevem ravnovesju, ko prvi igralec igra drugo, drugi pa tretjo akcijo. 25. Vrednost igre je: 4 3 1 − q min max 2 4 = min max{4 − q, 2 + 2q, 5 − 3q} =   0≤q≤1 q 0≤q≤1 5 2  5 − 3q ; 0 ≤ q ≤ 1/2  = min 4 − q ; 1/2 ≤ q ≤ 2/3 = 0≤q≤1  2 + 2q ; 2/3 ≤ q ≤ 1 10 = , 3 78 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER minimum zgornje ovojnice pa je dosežen pri q = 2/3 in vanj sta vpleteni prva in tretja vrstica. Strategijo prvega igralca v Nashevem ravnovesju torej lahko predsta- T vimo z vektorjem 1 − p p 0 . Iz principa indiferentnosti dobimo 4 − 2p = 3 + p, torej p = 1/3. Edino Nashevo ravnovesje je torej par vektorjev: 2/3  1/3 1/3 , .   2/3  0 26. To je igra z dvema vrsticama (namesto z dvema stolpcema); pri takih igrah lahko iščemo max-min strategije prvega igralca. Vrednost igre je torej: 2 4 6 4 0 max min 1 − p p = 0≤p≤1 6 5 0 3 12 = max min{2 + 4p, 4 + p, 6 − 6p, 4 − p, 12p} = 0≤p≤1  12p ; 0 ≤ p ≤ 1/4    2 + 4p ; 1/4 ≤ p ≤ 2/5 = max = 0≤p≤1 4 − p ; p = 2/5    6 − 6p ; 2/5 ≤ p ≤ 1 18 = , 5 maksimum spodnje ovojnice pa je dosežen pri p = 2/5 in vanj so vpleteni prvi, tretji in četrti stolpec. Strategijo drugega igralca v Nashevem ravnovesju torej T lahko predstavimo z vektorjem 1 − z − t 0 z t 0 . Iz principa indiferentnosti dobimo 2 + 4z + 2t = 6 − 6z − 3t, torej z = 2 − t . Nasheva ravnovesja so torej 5 2 oblike:   3 − t  5 2  3  0  4  5  2   , − t ; 0 ≤ t ≤ . 2  5 2     5 5   t  0 27. Tretja vrstica je dominirana s prvo in drugo. Ko jo odstranimo, je zadnji stolpec do- miniran z mešanico iz polovice drugega in polovice tretjega (dominacije tu razumemo glede na koristnostno funkcijo ustreznega igralca in ne glede na elemente matrike: dominacija pri stolpcih gre torej v nasprotno smer kot pri vrsticah). Vrednost igre: 7/2. 28. Označimo matriko igre z A, vrednost pa z v. Ker je 1 1 1 1 Aq = 5 ne glede na q, je v ≥ 5 . 4 4 4 4 2 2  1  4 1 Ker je pTA  4   1  = 5 ne glede na p, je v ≤ 5 . 2 2  4  1 4 Torej je v = 5/2. M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 79 29. Označimo z ∼ enakost vrednosti iger. Za a ≥ 5 iz dominacij dobimo: 5 a b a a b a b a a b ∼ ∼   , c c d c d c c d za a ≤ 5 pa iz dominacij dobimo: 5 a b a b a b a a b ∼ a b ∼ .     c d c c d c d 1/4 1/3 30. Dobimo p = 1/4 ∈ 1/3 ∈   ∆ in q =   ∆, torej je v = 2. Glede na to, da je 1/2 1/3 matrika igre, označimo jo z A, obrnljiva, lahko to storimo tudi s pomočjo inverzne  10 −6 4  1 matrike A−1 = 7 3 −2  , a se bolj splača neposredno rešiti oba sistema. 48 −11 9 10 31. Matrika igre ni obrnljiva, torej inverz ne obstaja. Lahko sicer vsem elementom matrike prištejemo določeno število (vsem isto), tako da je nova matrika obrnljiva; vrednost nove matrične igre je vsota vrednosti stare in števila, ki smo ga prišteli. Vendar pa je veliko ugodneje neposredno rešiti sistem. Njegova rešitev je 2/5 1/4 p = 1/5 ∈ ∆ in q = 1/2 ∈ ∆, torej je v = 0.     2/5 1/4 32. a) Naj Alfred izbere število i z verjetnostjo pi, Bernard pa z verjetnostjo qi. Iz principa indiferentnosti za Alfreda dobimo: q1 − q2 = q2 − q3 = · · · = qn−1 − qn = qn , kar ima za rešitev qi = (n − i + 1)qn. Ker mora biti vsota verjetnosti enaka 1, je 2(n − i + 1) končno qi = . n(n + 1) Iz principa indiferentnosti za Bernarda pa dobimo: −p1 = p1 − p2 = p2 − p3 = · · · = pn−1 − pn , 2i od koder podobno kot prej sledi pi = . n(n + 1) b) Opazimo, da je to kvadratna igra z ničelno vsoto (matrična igra) z enim samim mešanim Nashevim ravnovesjem, kjer oba igralca strogo mešata vse akcije. Teorija pa pravi, da je to v tem primeru edino mešano Nashevo ravnovesje nasploh, torej zahtevano mešano Nashevo ravnovesje ne obstaja. 80 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 1/4  1  33. Dobimo p = 1/2 ∈ 1   ∆ in q =   / ∈ ∆. 1/4 −1 To pomeni, da lahko odstranimo tretji stolpec (čeprav ni dominiran), dobimo igro 3 × 2 in velja: v = min max{3p, 4 − 9p, −8 + 15p} = 1 . p 3 ; x ≤ 3 34. v = 3+4x . ; x ≥ 3 2+x 35. Označimo diagonalne elemente z d1, d2, . . . , dn. Brž ko je di ≥ 0 in dj ≤ 0, je v i-ti vrstici in j-tem stolpcu sedlo; tamkajšnji element je enak 0, torej je v = 0. Preostane še primer, ko je bodisi di > 0 za vse i bodisi di < 0 za vse i. Tedaj imata enačbi pTA = α1T in Aq = β1 rešitvi:     p1 q1 . . 1 1 p =  ..  , q =  ..  , kjer je pi = qi = in α = β = .     d n 1 n 1 i p j=1 dj j=1 dj n qn −1 Vidimo, da je p = q ∈ ∆, torej je v tem primeru v = n d−1 . j=1 j 36. Velja: T v = max min pTAq = max min pTAq = max min qTATp = p q p q p q = max min −qTAp = − min max qTAp = − min max pTAq = p q p q q p = −v , torej je v = 0. M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 81 3. Bayesove igre 1. Prirejeno igro s popolno informacijo lahko zapišemo takole: L1L2 L1D2 D1L2 D1D2 A12 4; 3, 1 2; 3, 2 5; 1, 1 3; 1, 2 , B12 7; 1, 2 5; 1, 1 8; 3, 2 6; 3, 1 pri čemer prva številka pomeni (pričakovano) korist prvega igralca, druga številka korist drugega igralca, ki ve, da je v stanju ω1, tretja pa korist drugega igralca, ki ve, da je v stanju ω2. Opazimo, da akcija B12 strogo dominira akcijo A12 (čeprav v izvirni igri to velja le v stanju ω2, v stanju ω1 pa velja ravno nasprotno). Torej lahko problem prevedemo na iskanje mešanih ravnovesij naslednje igre: L2 D2 L1 1, 2 1, 1 . D1 3, 2 3, 1 V tej igri akcija D1 strogo dominira akcijo L1, akcija L2 pa strogo dominira akcijo D1. Edino mešano Bayesovo ravnovesje je torej čisto ravnovesje (B12, D1L2). 2. Najprej opazimo, da pri prvem igralcu, ki dobi signal stanja ω1, akcija A dominira akcijo B, če dobi signal stanja ω3, pa akcija B dominira akcijo A. Za prvega igralca s tema dvema signaloma je torej strategija jasna, za prvega igralca s signalom stanja ω2 in drugega igralca pa dobimo strateško igro z naslednjima funkcijama koristnosti: L123 D123 A2 0, 3 4, 3 2 . B2 3, 2 1, −1 Iz tabele razberemo, da sta (A2, D123) in (B2, L123) čisti Bayesovi ravnovesji in da Bayesovih ravnovesij tipa čisto–mešano ni. Nadalje iz principa indiferentnosti raz- A L beremo, da je profil 2 B2 , 123 D123 , kjer je 0 < p, q < 1, mešano 1 − p p 1 − q q Bayesovo ravnovesje natanko tedaj, ko velja 3 + 1 p = 3 − 4p in 4q = 3 − 2q, torej 2 2 p = 1 in q = 1 . Sklep: mešana Bayesova ravnovesja naše igre so (A 3 2 1A2B3, D123), A L (A 2 B2 123 D123 1B2B3, L123) in A1 2 1 B3, 1 1 . 3 3 2 2 3. Opazimo, da pri prvem igralcu, ki ve, da je v prvem stanju, akcija T strogo dominira akcijo B. Podobno pri drugem igralcu, ki je v drugem stanju, akcija L strogo dominira akcijo R. Tako lahko med akcijama izbirata le še prvi igralec, ki je v stanju ω2 ali ω3, in drugi igralec, ki je v stanju ω1 ali ω3. Za ta dva igralca dobimo naslednjo prirejeno strateško igro: L13 R13 T 7 23 , 2 2, 7 4 . B23 2, 4 9 , 3 4 82 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Vidimo, da akcija B23 strogo dominira akcijo T23 (medtem ko v imamo v stanju ω2 izvirne igre le navadno dominacijo). Ko akcijo T23 izločimo, vidimo, da se dru- gemu igralcu bolj splača igrati L13. Edino mešano Bayesovo ravnovesje igre je torej (T1, B23; L2, L13). 4. a) Anita ima na voljo akciji ‘prodaj’ (recimo P ) in ‘zadrži’ (recimo Z), Bojan pa ima na voljo akciji ‘kupi’ (recimo K) in ‘odkloni’ (recimo O). Igra ima dve stanji, recimo d, če je avto v dobrem stanju, in s, če je v slabem stanju. Tedaj lahko to zapišemo kot naslednjo Bayesovo igro: Stanje d: Stanje s: K O K O P c − 6, 9 − c 0, 0 P c, 3 − c 0, 0 Z 0, 0 0, 0 Z 0, 0 0, 0 b) Prirejena strateška igra s popolno informacijo je: Kds Ods PdPs c − 6, c, 7 − c 0, 0, 0 PdZs c − 6, 0, 6 − 2 c 0, 0, 0 3 . ZdPs 0, c, 1 − 1 c 0, 0, 0 3 ZdZs 0, 0, 0 0, 0, 0 Profila, ko želi Bojan kupiti avto, Anita pa zadržati avto v slabem stanju, nista nikoli Bayesovi ravnovesji. Vsi ostali profili čistih strategij so Bayesova ravnovesja za vsaj eno ceno. c) Pri 6 ≤ c ≤ 7 je iskano Bayesovo ravnovesje profil (PdPs, Kds), pri c ≤ 3 pa profil (ZdPs, Kds). d) Bojan je lahko ob primerni ceni indiferenten pri vsaki Anitini strategiji. Toda strategiji z Zs se Aniti ne splačata pri nobeni ceni, zato ju lahko izločimo. Pri stra- tegiji PdPs je Bojan indiferenten pri ceni c = 7 in pri tej ceni je to edina strategija, ki se pri tej ceni splača Aniti. Pri strategiji ZdPs pa je Bojan indiferenten pri ceni c = 3 in to je spet edina strategija, ki se pri tej ceni splača Aniti. Iskani ceni sta torej c = 3 in c = 7. 5. Najprej opazimo, da pri prvem igralcu, ki dobi signal stanja ω1, akcija A dominira akcijo B, pri drugem igralcu, ki dobi signal stanja ω2, pa akcija D dominira akcijo L. Za igralca s tema signaloma je torej strategija jasna, torej se lahko omejimo na prvega igralca, ki dobi signal stanj ω2 in ω3, in drugega igralca, ki dobi signal stanj ω ω ω 2 ω3 1 ω3 1 in ω3. Prvi ima aposteriorno porazdelitev , drugi pa . 1/3 2/3 1/3 2/3 Dobimo strateško igro z naslednjima funkcijama koristnosti: L13 D13 A23 5, 0 1, 3 . B23 1, 2 3, 1 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 83 S primerjanjem funkcij koristnosti hitro ugotovimo, da čistih Bayesovih ravnovesij ni, prav tako tudi ne kombinacij čisto–mešano. Iz principa indiferentnosti razbe- A L remo, da je profil 23 B23 , 13 D13 , kjer je 0 < p, q < 1, mešano 1 − p p 1 − q q Bayesovo ravnovesje natanko tedaj, ko velja 5 − 4q = 1 + 2q in 2p = 3 − 2p, torej p = 3 in q = 2 . Edino mešano Bayesovo ravnovesje dane igre je torej 4 3 A L A 23 B23 13 D13 1 1 3 , D2 1 2 . 4 4 3 3 6. a) Igra ima 6 stanj glede na to, katero nagrado dobi posamezen igralec – recimo AB, AC, BA, BC, CA in CB. Prvi igralec lahko dobi signale A∗, B∗ in C∗, drugi igralec pa ∗A, ∗B in ∗C, pač glede na to, katero nagrado je posamezen igralec dobil. Če prvi igralec prejme signal A∗, je aposteriorna (pogojna) porazdelitev stanj enaka AB AC in podobno tudi za ostala dva signala in za drugega igralca. 1/2 1/2 Vsak igralec ima dve možni akciji: menjati (M ) ali ne menjati (N ). Do menjave pride, če sta obe akciji enaki M . Od tod dobimo naslednje tabele koristnostnih funkcij po stanjih: AB AC BA N M N M N M N 1, 1 1, 1 N 1, 2 1, 2 N 3, 4 3, 4 M 1, 1 3, 4 M 1, 2 4, 4 M 3, 4 1, 1 BC CA CB N M N M N M N 3, 2 3, 2 N 4, 4 4, 4 N 4, 1 4, 1 M 3, 2 4, 1 M 4, 4 1, 2 M 4, 1 3, 2 b) V Bayesovem ravnovesju prav gotovo ne pride do menjave nagrad, ki imata za igralca najvišjo možno vrednost, t. j. prvi igralec ne bo zamenjal nagrade C, drugi igralec pa ne nagrade A. Oglejmo si zdaj profil, pri katerem je vsak igralec pripravljen zamenjati vsako nagrado razen najvišje, t. j. profil: (MA∗MB∗NC∗, N∗AM∗BM∗C) . Koristnostne funkcije igralcev z ustreznimi signali v prirejeni strateški igri s po- . . . . polno informacijo so za ta profil enake (3 5, 3 5, 4; 4, 2 5, 2 5), kar je večje ali enako . . (1, 3, 3 5; 2 5, 1, 2) – koristnostnim funkcijam posameznih igralcev s signali za pri- mer, ko zamenjajo akcijo. Zato je profil (MA∗MB∗NC∗, NA∗MB∗MC∗) Bayesovo rav- novesje, v njem pa lahko pride do vseh menjav, ki jih nismo izključili, t. j. A ↔ B, A ↔ C in B ↔ C. c) Profil, pri katerem nobeden ni nikoli pripravljen menjati, je Bayesovo ravnovesje, ker se, če je določen igralec pri določenem signalu (t. j. določeno nagrado) pripra- vljen menjati, njegova koristnostna funkcija ne spremeni. Ta profil je torej čisto Bayesovo ravnovesje, pri katerem nikoli ne pride do menjave. 84 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 7. Vsak igralec ima dve akciji: menjati (recimo M ) in ne menjati (recimo N ). Množica stanj je množica parov dobitkov, ki jih lahko dobita igralca. Če dobitke označimo kar z 1, 2, . . . , n, so torej stanja urejeni pari (i, j), kjer je i, j ∈ {1, . . . , n} in i = j. Porazdelitev na množici stanj je enakomerna, vsa stanja imajo verjetnost 1 . Iz n(n−1) stanja (i, j) dobi prvi igralec signal i∗, drugi pa signal ∗j. Označimo vrednosti dobitkov z x1, x2, . . . , xn. Brez škode za splošnost bomo privzeli, da je x1 < x2 < · · · < xn. Koristnostni funkciji Bayesove igre sta tedaj v stanju (i, j) enaki: U1(N, N ) = U1(N, M ) = U1(M, N ) = xi , U1(M, M ) = xj , U2(N, N ) = U2(N, M ) = U2(M, N ) = xj , U2(M, M ) = xi . Prirejena igra s popolno informacijo pa ima 2n igralcev: prvega igralca skupaj s svojo nagrado in še drugega igralca skupaj s svojo nagrado. Profili v tej prirejeni igri bodo torej vektorji (a1, . . . , an, b1, . . . , bn), kjer so ai in bj lahko enaki M ali N . Označimo koristnostne funkcije igralcev v prirejeni igri z U11, . . . , U1n, U21, . . . , U2n. Če so štiri možne nagrade, velja: U11(Z1∗N2∗N3∗N4∗, N∗1Z∗2N∗3N∗4) = 2 x x 3 1 + 1 3 2 . V splošnem pa lahko koristnostne funkcije zapišemo v obliki: U1i(a1, . . . , ai−1, N, ai+1, . . . , an; b1, . . . , bn) = xi , 1 U1i(a1, . . . , ai−1, M, ai+1, . . . , an; b1, . . . , bn) = xi + (xj − xi) , n − 1 j; j=i bj =M U2j(a1, . . . , an; b1, . . . , bj−1, N, bj+1, . . . , bn) = xj , 1 U2j(a1, . . . , an; b1, . . . , bj−1, M, bj+1, . . . , bn) = xj + (xi − xj) . n − 1 i; i=j ai=M Profil (a1, . . . , an, b1, . . . , bn) je torej čisto Bayesovo ravnovesje, če so izpolnjeni na- M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 85 slednji pogoji: (xj − xi) ≤ 0 , če je ai = N , (1) j; j=i bj =M (xj − xi) ≥ 0 , če je ai = M , (2) j; j=i bj =M (xi − xj) ≤ 0 , če je bj = N , (3) i; i=j ai=M (xi − xj) ≥ 0 , če je bj = M . (4) i; i=j ai=M Ločimo naslednje možnosti: • Nobeden nikoli ne menja. V tem primeru so vse štiri vsote enake nič in imamo Bayesovo ravnovesje. • Eden od igralcev nikoli ne menja, drugi pa je v določenih primerih pripravljen menjati. Recimo, da je prvi igralec tisti, ki nikoli ne menja. Tedaj se pogoji (1)–(4) zreducirajo na: (xj − xi) ≤ 0 za vse i . j; j=i bj =M Če sem vstavimo i = 1, dobimo, da mora biti bj = N za vse j > 1 (torej b1 = M ). Ni se težko prepričati, da to dejansko je Bayesovo ravnovesje. Po- dobno dobimo, če igralca zamenjamo. Skratka, v Bayesovem ravnovesju smo, če eden od igralcev ni pripravljen nikoli menjati, drugi pa je pripravljen menjati nagrado z najnižjo vrednostjo. • Oba igralca sta v določenih primerih pripravljena menjati. V tem primeru označimo z i∗ oz. j∗ dobitek z najvišjo vrednostjo, ki ga je prvi oz. drugi igralec še pripravljen zamenjati. Privzemimo najprej, da je i∗ < j∗. Če v pogoj (4) vstavimo j = j∗, dobimo: (xi − xj) ≥ 0 , i; i 1, bi torej veljalo b1 = N , potem pa bi iz pogoja (3) za j = 1 dobili: (xi − x1) ≤ 0 , i; i>1 ai=M kar ni res, saj je (xi − x1) ≥ xm − x1 > 0. i;i>1,ai=M Sklep: čista Bayesova ravnovesja so profili, kjer je vsak od igralcev pripravljen zamenjati kvečjemu nagrado z najnižjo vrednostjo. V čistem Bayesovem ravnovesju torej ne pride do menjave. 8. Stanja igre so vse možne delitve kart. Za vsako delitev kart signal posameznemu igralcu pove, kateri karti je dobil on. Strategija za vsakega igralca z znanima kar- tama pove, katero naj odvrže: strategije so vse možne kombinacije. Dovolj pa je povedati, katero karto posamezen igralec odvrže v primeru, ko dobi dve različni karti. Koristnostni funkciji sta jasni. Aposteriorne verjetnosti dobimo iz apriornih, pri katerih so vse možne delitve, kjer vse karte ločimo, enako verjetne. Čisto Bayesovo ravnovesje je profil, pri katerem ima vsak od igralcev naslednjo strategijo: • Če dobi kamen in škarje, odvrže škarje. • Če dobi škarje in papir, odvrže papir. • Če dobi papir in kamen, odvrže kamen. Izračunajmo pričakovano koristnost posameznega igralca s signalom za ta profil. Manj zanimiva možnost je, da je dobil dve enaki karti. Zaradi simetrije lahko brez škode za splošnost privzamemo, da je dobil dvakrat kamen. Preostanejo še dvakrat škarje in dvakrat papir. Možni nasprotnikovi nabori kart skupaj z aposteriornimi verjetnostmi in dobitki igralca so naslednji: nasprotnikovi karti aposteriorna verjetnost dobitek škarje, papir 2/3 0 škarje, škarje 1/6 1 papir, papir 1/6 0 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 87 Pričakovani dobitek znaša 1/6 točke. Zanimivejša pa je možnost, da je dobil dve različni karti. Spet lahko zaradi simetrije brez škode za splošnost privzamemo, da je dobil kamen in škarje. Preostanejo še karte kamen, škarje in dvakrat papir. Možni nasprotnikovi nabori kart skupaj z aposteriornimi verjetnostmi in dobitki igralca so naslednji: nasprotnikovi karti aposteriorna verjetnost dobitek kamen, škarje 1/6 1/2 kamen, papir 1/3 0 škarje, papir 1/3 1 papir, papir 1/6 1 Pričakovani dobitek znaša 7/12 točke. Zdaj pa moramo pričakovane dobitke primerjati s pričakovanimi dobitki v primerih, ko igralec s signalom zamenja strategijo. Formalno gledano strategija opisuje rav- nanje v vseh primerih: tako opis strategije igralca, ki dobi kamen in škarje, zajema tudi irelevantni primer, ko bi dobil škarje in papir. Toda koristnostna funkcija se bo spremenila le, če se bo spremenil predpis, kako naj ravna, če je dobil kamen in škarje. Torej se bo namesto ‘odvrzi škarje’ glasil ‘odvrzi kamen’. V tem primeru je situacija naslednja: nasprotnikovi karti aposteriorna verjetnost dobitek kamen, škarje 1/6 1 kamen, papir 1/3 1/2 škarje, papir 1/3 0 papir, papir 1/6 0 in pričakovani dobiček znaša 1/3, kar je manj od prejšnjih 7/12. Opomba. Ker je to simetrična igra s fiksno vsoto 1, mora apriorni pričakovani dobiček vsakega igralca nujno znašati 1/2. Možno je izračunati, da posamezen igralec dobi enaki karti z verjetnostjo 1/5 in različni z verjetnostjo 4/5. Apriorni 1 1 4 7 1 pričakovani dobiček torej znaša · + · = , tako kot mora biti. 5 6 5 12 2 88 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 9. Vsak od igralcev ima dve akciji: vreči ali ne vreči karto. Stanja igre je možno podati na več načinov. Lahko so to npr. kar razporeditve kart v kupu, za katere privzamemo, da so označene: v tem primeru imamo 5! = 120 enako verjetnih stanj. Lahko so to vsa možna jemanja dveh označenih kart s kupa: v tem primeru imamo 6 · 5 = 30 enako verjetnih stanj. Lahko pa stanje le pove, kateri igralec ima kakšno karto, npr. prvi igralec ima asa, drugi pa fanta (karte so neoznačene). V tem primeru pa imamo 9 stanj, a niso vsa enako verjetna: stanja, kjer imata oba igralca enaki karti, imajo verjetnosti 1/15, stanja, kjer imata različni karti, pa 2/15. Pri tej definiciji stanj sta koristnostni funkciji naslednji: F F F K F A V N V N V N V 0, 0 0, 0 V −1, 1 1, −1 V −2, 2 2, −2 N 0, 0 0, 0 N 0, 0 0, 0 N 0, 0 0, 0 KF KK KA V N V N V N V 1, −1 0, 0 V 0, 0 1, −1 V −1, 1 2, −2 N −1, 1 0, 0 N −1, 1 0, 0 N −1, 1 0, 0 AF AK AA V N V N V N V 2, −2 0, 0 V 1, −1 1, −1 V 0, 0 2, −2 N −2, 2 0, 0 N −2, 2 0, 0 N −2, 2 0, 0 Signal posameznemu igralcu pove, kakšno karto ima. Vsak igralec torej lahko dobi tri signale – ‘fant’, ‘kralj’ ali ‘as’. Iz tabele odčitamo, da pri igralcu, ki dobi asa, akcija ‘vreči’ v vseh stanjih strogo dominira akcijo ‘ne vreči’. Zato igralec asa vedno vrže. Podobno je pri igralcu, ki dobi kralja: akcija ‘vreči’ v vseh stanjih dominira akcijo ‘ne vreči’. To pomeni, da, če obstaja čisto Bayesovo ravnovesje, obstaja tudi tako, pri katerem nobeden od igralcev ne vrže kralja. Možno pa je tudi izračunati, da je v prirejeni strateški igri dominacija stroga, torej dejansko ni Bayesovega ravnovesja, pri katerem kakšen od igralcev ne bi vrgel asa. Končno, če zožimo igro, tako da igralec, ki dobi asa ali kralja, tega vrže, dobimo, da pri igralcu, ki vrže fanta, akcija ‘ne vreči’ dominira akcijo ‘vreči’. Spet je možno izračunati, da je v prirejeni strateški igri dominacija stroga. Od tod sledi, da ima igra čisto Bayesovo ravnovesje (NF 1VK1VA1, NF 2VK2VA2): vsak od igralcev igra tako, da fanta ne vrže, kralja ali asa pa vrže. Če upoštevamo strogost dominacij, dobimo, da je to tudi edino mešano Bayesovo ravnovesje. Opomba. Pri izračunu Bayesovega ravnovesja nismo čisto nič potrebovali aposteri- ornih verjetnosti. To pomeni, da rezultat velja ne glede na to, koliko fantov, kraljev ali asov je v kupu, z edino omejitvijo, da v kupu ni samih fantov. V slednjem primeru se namreč enako splača fanta vreči ali ne vreči. M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 89 4. Ekstenzivne igre 1. Prirejena strateška igra: CE CF DE DF A 1, 1 1, 1 3, 2 3, 2 B 2, 2 4, 1 2, 2 4, 1 ima naslednja mešana Nasheva ravnovesja: DE DF 1 CE DE 1 A, ; 0 ≤ q ≤ in B, ; 0 ≤ q ≤ . 1 − q q 2 1 − q q 2 2. Edino vgnezdeno Nashevo ravnovesje je (A, DE), prirejena strateška igra pa ima poleg tega še čisto Nashevo ravnovesje (B, CE). To pri vgnezdenih izpade, ker drugi igralec ve, kaj je igral prvi. Opomba. Pomembno je, da vemo, kako ravna drugi igralec tudi v situaciji, do katere dejansko sploh ne pride! 3. Drevo z ustreznimi vgnezdenimi Nashevimi ravnovesji podiger: (AHK,CE) (BHK,CE) (AIK,CE) (BIK,CE) (BHL,CF ) (BIL,CF ) A B (H,C) (K,E) (I,C) (L,F ) C D E F (H, ) (K, ) (I, ) (L, ) 4 4 G I J L 4 2 H K 5 6 6 2 5 5 2 2 1 5 1 4 Igra ima torej šest vgnezdenih Nashevih ravnovesij. 90 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 4. Tu gre za igro s preferenčno funkcijo, ki ima tri vrednosti: s > l > m. Vsak kanibal Ki ima dve akciji: Pi (poje misionarja ali kanibala) in Ni (ne poje). Spodaj sta prikazani drevesi igre za primer, ko je n sod, in primer, ko je n lih. Pri tem so s pikčasto črto označene akcije, ki jih kanibali ne izberejo, z neprekinjeno črto pa akcije, ki jih izberejo. Če je n sod, je drevo igre z izbranimi akcijami naslednje: N1 K1 (l, l, l, . . . , l, l, l, l, l) P1 N2 K2 (s, l, l, . . . , l, l, l, l, l) P2 N3 K3 (m, s, l, . . . , l, l, l, l, l) P3 ... Pn−3 Nn−2 Kn−2 (m, m, m, . . . , m, s, l, l, l) Pn−2 Nn−1 Kn−1 (m, m, m, . . . , m, m, s, l, l) Pn−1 Nn Kn (m, m, m, . . . , m, m, m, s, l) Pn (m, m, m, . . . , m, m, m, m, s) Vgnezdeno Nashevo ravnovesje je (N1, P2, N3, . . . , Pn−2, Nn−1, Pn), torej misionar ostane pri življenju. Če je n lih, pa je drevo igre z izbranimi akcijami naslednje: N1 K1 (l, l, l, . . . , l, l, l, l, l) P1 N2 K2 (s, l, l, . . . , l, l, l, l, l) P2 N3 K3 (m, s, l, . . . , l, l, l, l, l) P3 ... Pn−3 Nn−2 Kn−2 (m, m, m, . . . , m, s, l, l, l) Pn−2 Nn−1 Kn−1 (m, m, m, . . . , m, m, s, l, l) Pn−1 Nn Kn (m, m, m, . . . , m, m, m, s, l) Pn (m, m, m, . . . , m, m, m, m, s) M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 91 Vgnezdeno Nashevo ravnovesje je (P1, N2, P3, . . . , Pn−2, Nn−1, Pn), torej glavni kani- bal poje misionarja, drugi kanibal pa prvega pusti pri življenju. Tako vsi kanibali vselej ostanejo živi. 5. a) Delitev v prvem koraku ponazorimo s številom 0 < p < 1, kjer je recimo 1 − p delež levega, p pa delež desnega kosa torte. Na drugem koraku ima drugi jedec na voljo dve akciji, L in D – za jemanje levega in desnega kosa. Strogo gledano bi morali gledati še tretji korak, kjer prvi jedec vzame preostali kos torte, a ker je to edina možnost, tega ne bomo narisali. Drevo igre: J1 p J2 L D p 1 − p 1 − p p Na drugem koraku drugi jedec izbere L, če je p < 1/2, in D, če je p > 1/2; pri p = 1/2 mu je vseeno. To moramo zdaj pokombinirati. Dobimo dve kombinaciji: rekli bomo, da je drugi jedec levičarski, če pri p = 1/2 vzame levi kos, in desničarski, če pri p = 1/2 vzame desni kos. Opisa ‘levičarski’ in ‘desničarski’ določata ravnanje drugega jedca za vse možne p: pri p = 1/2 jedec seveda vzame večji kos. Ne glede na to, ali je drugi jedec levičarski ali desničarski, pa prvi dobi p za p ≤ 1/2 in 1 − p za p ≥ 1/2. Maksimum tega je dosežen pri p = 1/2. Igra ima torej dve vgnezdeni Nashevi ravnovesji: 1 1 , levičarski in , desničarski 2 2 in pri obeh vsak od jedcev dobi natančno polovico torte. b) Ustrezni postopek za n jedcev je naslednji: najprej prvi jedec razdeli torto na n kosov. Nato drugi jedec vzame enega izmed kosov, sledi mu tretji jedec, ki vzame enega izmed še preostalih kosov in tako naprej. Na koncu n-ti jedec vzame enega izmed dveh kosov, ki sta še na voljo, in prvi jedec dobi zadnji še preostali kos. Označimo delitev torte z n-terico (p1, p2, . . . , pn), kjer je p1, p2, . . . , pn > 0 in p1 + p2 + · · · + pn = 1. V vgnezdenem Nashevem ravnovesju na vsakem od naslednjih korakov jedec, ki je na potezi, vzame največji kos, ki je še na voljo (lahko ima več možnosti). To pomeni, da je dobitek prvega jedca enak min{p1, p2, . . . , pn}. To pa je maksimalno pri p1 = p2 = · · · = pn = 1/n, torej res vsi dobijo enako velike kose. 92 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 6. Gre za ekstenzivno igro, ki jo lahko ponazorimo z naslednjo sliko: Ponudba: A p Odgovor: E S Z 1 − p 3(1 − p)/4 p (1 − p)/4 Oglejmo si najprej, kaj se splača storiti Egonu. Če je p < 1/5, se mu bolj splača zavrniti, če je p > 1/5, se mu bolj splača sprejeti, pri p = 1/5 pa se mu oboje enako splača. Preden se lotimo vprašanja, kaj se najbolj splača storiti Albertu, moramo pokombi- nirati Egonove strategije v vseh možnih situacijah, v katerih se znajde. Možni sta le dve kombinaciji. Rekli bomo, da je Egon ustrežljiv, če zavrne pri p < 1/5 in sprejme pri p ≥ 1/5. Nadalje bomo rekli, da je zloben, če zavrne pri p ≤ 1/5 in sprejme pri p > 1/5. Albertov dobitek v odvisnosti od njegove ponudbe p ima naslednji graf: 1 4/5 3/4 p 1/5 1 pri čemer je vrednost pri p = 1/5 na zgornji črti, če je Egon ustrežljiv, in spodaj, če je Egon zloben. Če je Egon ustrežljiv, je maksimum v tej točki tudi dosežen, če je Egon zloben, pa maksimum ni dosežen. Edino vgnezdeno Nashevo ravnovesje je torej (p = 1/5, Egon ustrežljiv). 7. Gre za ekstenzivno igro, ki jo lahko ponazorimo z naslednjo sliko: M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 93 1. krog – ponudba: P1 p1 1. krog – odgovor: P2 S Z 2. krog – ponudba: P2 1 − p1 p2 p1 2. krog – odgovor: P1 S Z δp2 0 δ(1 − p2) 0 Oglejmo si najprej odgovor v drugem krogu. Če je p2 > 0, se prvemu igralcu splača ponudbo sprejeti, pri p2 = 0 pa mu je vseeno. Recimo, da je prvi igralec vdan, če sprejme vsako ponudbo (tudi ničelno), in ponosen, če sprejme ponudbo p2 > 0 in zavrne ponudbo 0. V ta dva pojma zajamemo tudi prej omenjene nedvoumne reakcije prvega igralca. Oglejmo si zdaj, kaj se drugemu igralcu splača ponuditi v drugem krogu. Če je prvi igralec vdan, drugi dobi δ(1 − p2), če je prvi ponosen, pa drugi dobi δ(1 − p2), če je p2 > 0, in 0, če je p2 = 0. Če je prvi igralec ponosen, maksimum ni dosežen, če je vdan, pa je maksimum dosežen pri p2 = 0. To je edino vgnezdeno Nashevo ravnovesje za to podigro. Oglejmo si zdaj odgovor v prvem krogu. Če prvi igralec ponudi več kot δ, se drugemu splača ponudbo sprejeti, če ponudi manj kot δ (in je prvi igralec v drugem krogu vdan), se mu jo splača zavrniti (in postaviti protiponudbo 0). Če pa prvi igralec ponudi točno δ, je drugemu igralcu vseeno, ali ponudbo sprejme ali pa zavrne. pripravi protiponudbo 0. V prvem primeru bomo rekli, da je ustrežljiv, v drugem pa, da je zloben. V ta dva pojma zajamemo tudi prej omenjene nedvoumne reakcije drugega igralca. Končno si oglejmo še, kaj se prvemu igralcu splača ponuditi v prvem krogu. Če je drugi igralec ustrežljiv (in nato prvi igralec v drugem krogu vdan), prvi dobi 0, če je p1 < δ, in 1 − p1, če je p1 ≥ δ. Če je drugi igralec zloben, pa prvi dobi 0, če je p1 ≤ δ, in 1 − p1, če je p1 ≥ δ. Če je drugi igralec zloben, maksimum ni dosežen, če je ustrežljiv, pa je maksimum dosežen pri p1 = δ. Edino vgnezdeno Nashevo ravnovesje igre je torej: (p1 = δ, vdan; p2 = 0, ustrežljiv) . 94 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 8. Najprej je na potezi Herbert, čigar akcije so urejene trojice (h1, h2, h3) – glede na to, koliko zlatnikov je dal posameznemu svetovalcu. Nato je na potezi Kaspar, čigar akcije naj bodo urejene trojice (k1, k2, k3). Naj bo H število svetovalcev, ki so so Herberta dobili strogo več kot od Kasparja. Nadalje naj bo K število svetovalcev, ki so od Kasparja dobili strogo več kot od Herberta. Velja H + K ≤ 3: preostanek je število svetovalcev, ki so od obeh dobili enako. Označimo z uH Herbertovo, z uK pa Kasparjevo koristnostno funkcijo. Njune vre- dnosti so prikazane v naslednji tabeli: Možnost Kdo dobi posel uH uK H ≥ K + 2 Herman 5 − h1 − h2 − h3 −k1 − k2 − k3 H = 2, K = 1 Herman 5 − h1 − h2 − h3 −k1 − k2 − k3 Herman z verjetnostjo 3 , H = 1, K = 0 4 15 − h 5 − k Kaspar z verjetnostjo 1 4 1 − h2 − h3 4 1 − k2 − k3 4 H = K vsak z verjetnostjo 1/2 5 − h 5 − k 2 1 − h2 − h3 2 1 − k2 − k3 Herman z verjetnostjo 1 , H = 0, K = 1 4 5 − h 15 − k Kaspar z verjetnostjo 3 4 1 − h2 − h3 4 1 − k2 − k3 4 H = 1, K = 2 Kaspar −h1 − h2 − h3 5 − k1 − k2 − k3 H ≤ K − 2 Kaspar −h1 − h2 − h3 5 − k1 − k2 − k3 Najprej si moramo ogledati, kaj se pri Herbertovi akciji (h1, h2, h3) najbolj splača narediti Kasparju. Opazimo, da ne more veljati 0 < ki < hi, saj se v tem primeru Kasparju strogo bolj splača i-temu svetovalcu nič dati. Nadalje ne more veljati ki > hi + 1, saj se v tem primeru Kasparju strogo bolj splača i-temu svetovalcu dati hi + 1. A tudi primer ki = hi = 0 je izključen: podrobnosti so v naslednji tabeli (s črtico, torej H , K , u , so označene ustrezne količine po spremembi): K H K uK k H K u i K 2 0 −k1 − k2 − k3 0 3 0 −k − k − k = u 1 2 3 K + ki 1 0 5 − k − k − k = k = 3 − k 4 1 − k2 − k3 ki + 1 1 1 5 2 1 2 2 2 1 − k2 − k3 0 0 5 − k − k − k − k = 11 − k 2 1 − k2 − k3 ki + 1 0 1 15 4 1 2 3 4 1 − k2 − k3 1 1 5 − k − k − k = 4 − k 2 1 − k2 − k3 ki + 1 1 2 5 − k1 2 3 1 − k2 − k3 0 1 15 − k − k − k = 4 − k 4 1 − k2 − k3 ki + 1 0 2 5 − k1 2 3 1 − k2 − k3 0 2 5 − k1 − k2 − k3 0 1 2 5 − k − k − k = u 1 2 3 K + ki Torej mora za vsak i veljati bodisi ki = 0 bodisi ki = hi + 1 (Kaspar svetovalca ne podkupi ali pa podkupi). Ni težko preveriti naslednje: • Če Herbert ne podkupi nobenega svetovalca, se Kasparju najbolj splača z enim zlatnikom podkupiti dva od treh svetovalcev. V tem primeru Herbert dobi 0. M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 95 • Če Herbert podkupi natanko enega svetovalca, se Kasparju najbolj splača z enim zlatnikom podkupiti preostala dva svetovalca. V tem primeru je Herbert v minusu. • Če Herbert podkupi natanko dva svetovalca in je m manjši znesek, ki ga da svetovalcu, ločimo tri podmnožnosti: – Pri m < 3 se Kasparju najbolj splača podkupiti še nepodkupljenega sve- tovalca (z enim zlatnikom) in tistega, ki dobi manjšo podkupnino (z m + 1 zlatniki). V tem primeru je Herbert v minusu. – Pri m > 3 se Kasparju na splača podkupiti nikogar. Herbert je spet v minusu, saj dobi 5 − 2m ali manj. – Pri m = 3 pa je Kaspar indiferenten med prejšnjima dvema možnostma. Pri obeh je Herbert v minusu. • Če Herbert podkupi vse tri svetovalce z zneski m ≤ s ≤ M , spet ločimo tri možnosti: – Pri m + s < 3 se Kasparju najbolj splača podkupiti tista dva, ki dobita manj, torej m in s (z m + 1 in s + 1 zlatniki). V tem primeru je Herbert v minusu. – Pri m + s > 3 se Kasparju ne splača podkupiti nikogar. Spet je Herbert v minusu, saj je bodisi m = s = 2 in Herbert dobi 5−m−s−M ≤ 5−2−2− 2 = −1, bodisi je s ≥ 3 in Herbert dobi 5 − m − s − M ≤ 5 − 1 − 3 − 3 = −2. – Pri m+s = 3 pa je Kaspar indiferenten med prejšnjima dvema možnostma. To je možno le, če je m = 1 in s = 2, se pravi, da Herbert dobi 5 − 1 − 2 − M ≤ 5 − 1 − 2 − 3 ≤ 0. Kasparjeva strategija je sestavljena iz vseh možnih kombinacij, ki zadostujejo zgor- njemu opisu: Za vsako Herbertovo strategijo (h1, h2, h3) ima lahko Kaspar eno ali več možnosti. V slednjem primeru bomo rekli, da je konservativen do Herber- tove strategije (h1, h2, h3), če ne podkupi nikogar, in aktiven, če ustrezno podkupi. Vgnezdena Nasheva ravnovesja so naslednja: • Herbert ne podkupi nikogar, Kaspar pa ubere katero koli od prej omenjenih strategij (torej se zgodi, da izbere dva izmed treh svetovalcev in ju podkupi s po enim zlatnikom). • Herbert enega svetovalca podkupi z enim zlatnikom, preostala dva pa s po dvema zlatnikoma, in Kaspar je do te Herbertove strategije konservativen (do ostalih pa lahko kar koli). 9. Po izteku igre sta dobitka enaka: u1(q1, q2) = (17 − q1 − q2)+ − 1 q1 , u2(q1, q2) = (17 − q1 − q2)+ − 1 q2 . Najprej moramo raziskati, kdaj pri danem q1 izraz u2(q1, q2) doseže maksimum. Ločimo dve možnosti: 1. q1 ≥ 17. V tem primeru je u2(q1, q2) = −q2 in maksimum je dosežen pri q2 = 0. 96 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 2. q1 < 17. V tem primeru je: (16 − q u 1 − q2)q2 ; q2 ≤ 17 − q1 2(q1, q2) = . −q2 ; q2 ≥ 17 − q1 Najprej opazimo, da drugi del funkcije doseže maksimum na levem krajišču, pri q2 = 17 − q1. Torej je maksimum dosežen za 0 ≤ q2 ≤ 17 − q1. Na levem krajišču je u2(q1, 0) = 0, na desnem pa je u2(q1, 17 − q1) = −(17 − q1) < 0. Stacionarna točka je pri q2 = 8 − q1/2, a ta leži znotraj intervala [0, 17 − q1] le za q1 ≤ 16. Takrat je u2(q1, 8 − q1/2) = (8 − q1/2)2 ≥ 0, torej je maksimum dosežen tam. Za q1 > 16 pa znotraj danega intervala ni stacionarnih točk in maksimum je dosežen pri q2 = 0. Vse primere lahko povzamemo tako, da je maksimum izraza u2(q1, q2) po q2 (pri danem q1) dosežen pri q2 = (8 − q1/2)+. Ko to vstavimo v koristnostno funkcijo prvega igralca, dobimo:  8q /2 ; q q 1 − q2 1 ≤ 16  1 u 1 1 q1, 8 − = (16 − q1)q1 ; 16 ≤ q1 ≤ 17 , 2 +  −q1 ; q1 ≥ 17 kar je maksimalno pri q1 = 8. V edinem vgnezdenem Nashevem ravnovesju torej prvi proizvajalec proizvede 8, drugi pa 4 enote blaga. Dobiček prvega proizvajalca je torej enak 32, drugega pa 16. Glede na to, da imata oba proizvajalca enako funkcijo proizvodnih stroškov, je torej bolje biti prvi proizvajalec. 10. Po izteku igre sta dobitka enaka: u1(q1, q2) = (5 − q1 − q2)+ − 1 q1 , u2(q1, q2) = (5 − q1 − q2)+ − 1 q2 . Najprej moramo raziskati, kdaj pri danem q1 izraz u2(q1, q2) doseže maksimum. Vrednosti in najboljše odgovore lahko tabeliramo: Najboljši q2 = 0 q2 = 1 q2 = 2 q2 = 3 q2 = 4 q2 ≥ 5 odgovor q1 = 0 0 3 4 3 0 < 0 2 q1 = 1 0 2 2 0 < 0 < 0 1, 2 q1 = 2 0 1 0 < 0 < 0 < 0 1 q1 = 3 0 0 < 0 < 0 < 0 < 0 0, 1 q1 ≥ 4 0 < 0 < 0 < 0 < 0 < 0 0 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 97 Označimo strategije prvega proizvajalca z Ai, i = 0, 1, 2, . . ., glede na to, koliko proizvede. Strategije drugega pa so vse kombinacije akcij Bij za i = 0, 1, 2, . . ., i kjer Bij pomeni, da, če prvi proizvede i, drugi proizvede j. Toda le za i = 1 in i = 3 imamo po dve možnosti, sicer vselej po eno. Zato v opisu strategije lahko navedemo le B11 ali B12 in še B30 ali B31 (tako recimo strategija B11B30 v resnici pomeni B02B11B21B30B40B50 . . . Končno iz vrednosti koristnostne funkcije prvega igralca za izbrane profile: u1(0, 2) = 0 , u1(1, 1) = 2 , u1(1, 2) = 1 , u1(2, 1) = 2 , u1(3, 0) = 3 , u1(3, 1) = 0 , u1(4, 0) = 0 , u1(q1, 0) < 0 za q1 ≥ 5 dobimo naslednja vgnezdena Nasheva ravnovesja skupaj s koristnostnimi funkcijami: (A3, B11B30) (A (A (A (A , 1, B11B31) , 2, B11B31) , 3, B12B30) , 2, B12B31) . (3, 0) (2, 2) (2, 1) (3, 0) (2, 1) Iz koristnostnih funkcij vidimo, da je bolje biti prvi proizvajalec (četudi ne strogo bolje, ker pri profilu (A2, B11B31) oba dobita enako). 11. Prirejena strateška igra: C D AE 2, 1 2, 1 AF 2, 1 2, 1 BE 2, 2 3, 0 BF 2, 0 1, 1 Opazimo, da mora, če drugi igralec igra količkaj strategije D, prvi igralec igrati BE. Toda potem mora drugi igralec igrati C. Torej drugi igralec v mešanem Nashevem ravnovesju obvezno igra C. Mešana Nasheva ravnovesja so oblike: AE AF BE BF , C ; a, b, c, d ≥ 0, a + b + c + d = 1, 2c ≥ d . a b c d Opomba. Strategiji AE in AF sta ekvivalentni: pri poljubni akciji drugega igralca (C ali D) dasta obe enaki koristnostni funkciji. To je zato, ker je, če prvi igralec igra A, vseeno, ali bi na ustrezni informacijski množici igral E ali F , saj do nje v tem primeru sploh ne pride. 12. Prirejena strateška igra z reduciranimi strategijami: CE CF DE DF AG∗ 2, 5 2, 5 3, 3 3, 3 AH∗ 0, 7 0, 7 0, 4 0, 4 B∗I 0, 4 1, 1 0, 4 1, 1 B∗J 4, 3 0, 7 4, 3 0, 7 98 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Strategiji AH∗ in B∗I sta strogo dominirani. Ko ju odstranimo, je strategija DE strogo dominirana. Po nekaj računanja dobimo, da ima igra z reduciranimi strate- gijami naslednja mešana Nasheva ravnovesja: CE CF 1 AG∗, ; ≤ q ≤ 1 , 1 − q q 2 igra z nereduciranimi strategijami pa ima naslednja mešana Nasheva ravnovesja: AGI AGJ CE CF 1 , ; 0 ≤ p ≤ 1 , ≤ q ≤ 1 . 1 − p p 1 − q q 2 13. Prirejena strateška igra: CE CF DE DF AG 2, 5 2, 5 3, 3 3, 3 AH 0, 7 0, 7 0, 4 0, 4 BG 0, 4 1, 1 0, 4 1, 1 BH 4, 3 0, 7 4, 3 0, 7 Tu ni nobenih netrivialnih redukcij. Sicer pa je igra drugačna od prirejene strateške igre iz prejšnje naloge samo po imenih potez. Mešana Nasheva ravnovesja so torej: CE CF 1 AG, ; ≤ q ≤ 1 . 1 − q q 2 14. Prirejena strateška igra: C D A 0, 2 1, 0 B 3, 0 −1, 2 A B C D Mešano Nashevo ravnovesje: , . 1/2 1/2 2/5 3/5 15. Igralci v tej randomizirani ekstenzivni igri s popolno informacijo so lastnik (L), pošteni najemnik (NP ) in goljufivi najemnik (NG). V tem vrstnem redu so prikazani tudi njihovi dobitki v drevesu igre: M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 99 1/3 2/3 NP NG P N L 0 0 V O V O 0 −1 0 −1 −2 −1 0 0 0 0 0 −1 2 Lastnik ima možnost izbire, da najemnika, ki mu je rekel, da nima denarja, vrže iz stanovanja (V ) ali pa ga obdrži še en mesec (O). Pošteni najemnik nima možnosti izbire. Goljufivi najemnik pa ima možnost izbire, da najemnino plača (P ) ali pa je ne plača (N ). Ker pošteni najemnik nima nobene možnosti izbire, ga v prirejeni strateški igri ni potrebno obravnavati. Prirejena strateška igra med lastnikom in goljufivim naje- mnikom pa je: P N V −1/3, 0 −1, −2/3 O 0, 0 −4/3, 4/3 V O P N in ima mešano Nashevo ravnovesje , . 2/3 1/3 1/2 1/2 16. Popoln priklic imajo igre iz 11., 12. in 14. naloge, pri igri iz 13. naloge pa prvi igralec nima popolnega priklica. Pri 11. nalogi so behavioristično mešana Nasheva ravnovesja oblike: A B E F 2 , C ; 0 ≤ p ≤ 1, ≤ q ≤ 1 . 1 − p p 1 − q q 3 in vsa so tudi vgnezdena. Mešano Nashevo ravnovesje: AE BE BF , C 1/2 1/4 1/4 pa ni behavioristično mešano. Pri 12. nalogi so vsa mešana Nasheva ravnovesja tudi behavioristično mešana, saj jih lahko zapišemo v obliki: I J E F 1 AG , C ; 0 ≤ p ≤ 1 , ≤ q ≤ 1 . 1 − p p 1 − q q 2 100 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Vgnezdeno pa je eno samo, in sicer: I J E F AG , C . 4/7 3/7 1/5 4/5 Pri 14. in 15. nalogi pa je edino mešano Nashevo ravnovesje tudi behavioristično mešano in vgnezdeno. M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 101 5. Kooperativne igre 1. Pri izhodišču (0, −13/2) je množica {(x, y) ∈ S ; x ≥ −2, y ≥ 0} neprazna, saj vsebuje recimo točko (0, 1/4), torej bomo iskali maksimum Nashevega produkta x(y + 27/4), in sicer na robu množice S, torej za y = (1 − x2)/4. Torej bo Nashev produkt enak: x(27 − x2) , 4 kar doseže maksimum pri x∗ = 3 in y∗ = −2. Pri izhodišču (−2, 1/4) je {(x, y) ∈ S ; x ≥ −2, y ≥ 1/4} = {(0, 1/4)}, torej bo Nashev sporazum pri x∗ = 0 in y∗ = 1/4. Pri izhodišču (0, 1) pa je {(x, y) ∈ S ; x ≥ 0, y ≥ 1} = ∅, torej ostane status quo. Prav tako ostane status quo pri izhodišču (0, 2). 2. Velja: 1 − x2 1 − x2 5 σ = max x + y ; y ≤ = max x + ; x ∈ R = , 4 4 4 in sicer je maksimum dosežen v (2, −3/4). Nasheve rešitve: Nasheva Izhodišče Prenos rešitev 0, − 13 31 , −21 Drugi plača prvemu 15 . 2 8 8 8 −2, 1 − 1 , 7 Prvi plača drugemu 5 . 4 2 4 2 (0, 1) 1 , 9 Prvi plača drugemu 15 . 8 8 8 (0, 2) status quo —  8 + u − v 8 − u + v  , ; u + v ≤ 8 3. a) (x∗, y∗) = 2 2 .  (u, v) ; u + v > 8 T B L R b) Profilu groženj , pripada pogajalsko izhodišče: 1 − p p 1 − q q u = 6 − 4p − 5q + 8pq , v = 2 + 2p − q (∗) in zavezujoč sporazum: x∗ = 6 − 3p − 2q + 4pq , y∗ = 2 + 3p + 2q − 4pq . 102 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Dobljena dvofazna igra je ekvivalentna naslednji igri z mešanimi strategijami, kjer izplačilu (u, v) v prvotni igri odgovarja izplačilo 8+u−v , 8−u+v : 2 2 L R T 6, 2 4, 4 B 3, 5 5, 3 To je igra s fiksno vsoto. Njeno mešano Nashevo ravnovesje je: T B L R , , 1/2 1/2 1/4 3/4 izkupička igralcev pa sta 9/2 in 7/2. Igralca ju dosežeta s katero koli sporazumno mešanico profilov (T, L) in (B, R) ter ustreznim prenosom dobrine. c) Množica dopustnih sporazumov: y 4 3 2 1 x 1 2 3 4 5 6 Nasheve rešitve skupaj s sporazumnimi mešanicami: Profil Pogajalsko Nasheva Sporazumna groženj izhodišče rešitev mešanica T B (B, L) (B, R) , L (4, 3) 9 , 19 1/2 1/2 2 6 1/6 5/6 L R (T, L) (B, R) T, 4, 8 26 , 14 3/5 2/5 5 5 5 1/5 4/5 (T, R) (1, 1) (5, 3) (B, R) d) Naj bo najprej (x∗, y∗) točka v notranjosti daljice, ki je del roba množice do- pustnih sporazumov in katere nosilka je premica y = n − kx, k > 0. Torej je y∗ = n − kx∗. Iščemo vsa pogajalska izhodišča (u, v), za katera je sporazum dosežen ravno v (x∗, y∗). Očitno je v ≤ n − ku, sicer bi imeli status quo. Ker je točka (x∗, y∗) M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 103 v notranjosti daljice, mora biti tam dosežen maksimum Nashevega produkta na celi premici y = n − kx, torej mora biti: d (x − u)(n − kx − v) = 0 , dx x=x∗ torej: n − 2kx∗ + ku − v = 0 . Z upoštevanjem, da je y∗ = n − kx∗, dobimo še lepšo obliko: v − y∗ = k(u − x∗) in ker mora biti v ≤ n − ku, mora biti tudi u ≤ x∗ in v ≤ y∗. Slika: (x∗, y∗) v − y∗ = k(u − x∗) y = n − kx Od tod dobimo naslednjo Nashevo rešitev pogajanja v odvisnosti od izhodišča: v v=4 4 3 v= 10+u 3 2 .................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................. O A B 1 v= 4+u 3 u 1 2 3 4 5 6 C D E v=u−2 v=u−4 u=6 O : status quo A : x∗ = 2, y∗ = 4 14 + u − 3v 14 − u + 3v B : x∗ = , y∗ = 2 6 C : x∗ = 5 y∗ = 3 8 + u − v 8 − u + v D : x∗ = , y∗ = 2 2 E : x∗ = 6, y∗ = 2 104 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER e) Za rešitev pripadajoče dvofazne igre z obvezujočim sporazumom so pomembna le pogajalska izhodišča, ki izhajajo iz prvotne strateške igre. Množica le-teh je različna od množice možnih sporazumov in je prikazana na naslednji sliki: y 4 3 : p narašča, q fiksen 2 : q narašča, p fiksen 1 x 1 2 3 4 5 6 Pri pogajalskih izhodiščih namreč igralca mešata vsak zase, medtem ko pri spora- zumu mešata vzajemno. ∂u ∂u Del roba množice pogajalskih izhodišč je tudi ogrinjača daljic, ki je določena z relacijo ∂u , ∂v ∂u , ∂v oziroma ∂p ∂q = 0. ∂p ∂p ∂q ∂q ∂v ∂v ∂p ∂q Odvisnost sporazuma od grozilnih strategij dobimo iz odvisnosti od pogajalskih izhodišč in zveze (∗): q 1 q = 5p−2 4p−1 C q = 3p−1 B 4p−2 D p 1 7 + 5p + q − 4pq B : x∗ = 7 − 5p − q + 4pq, y∗ = 3 C : x∗ = 5 y∗ = 3 D : x∗ = 6 − 3p − 2q + 4pq, y∗ = 2 + 3p + 2q − 4pq Z vodoravnimi puščicami je prikazana smer naraščanja izkupička prvega, z nav- pičnimi puščicami pa drugega igralca. Tako dobimo množico Nashevih ravnovesij, ki je prikazana šrafirano in je enaka: (p, q) ; 0 ≤ p ≤ 2 , 1 ≤ q ≤ 1 . 5 2 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 105 4. Funkcija v je superaditivna za 3 ≤ a ≤ 7. Za a = 3 so imputacije in jedro prikazani na naslednji skici: x2+x3≥4 x2≥2 (1,2,5) x1+x2≥3 (4,2,2) (1,5,2) x3≥1 (4,3,1) (2,5,1) (5,2,1) (1,6,1) x1+x3≥3 x1≥1 5. Imputacije tvorijo trikotnik z oglišči (9, 1, 2), (2, 8, 2) in (2, 1, 9). Jedro je prazno: iz x1 + x2 ≥ 8, x1 + x3 ≥ 9 in x2 + x3 ≥ 8 sledi x3 ≤ 4, x2 ≤ 3 in x1 ≤ 4, kar pomeni, da mora biti x1 + x2 + x3 ≤ 11. Slika: x2+x3≥8 x2≥1 (2,1,9) x1+x2≥8 x3≥2 (9,1,2) (2,8,2) x1+x3≥9 x1≥2 106 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Za izračun Shapleyjevih vrednosti tabelirajmo prispevke posameznikov h koaliciji za vse možne vrstne rede pristopanja: Vrstni red 1 2 3 1, 2, 3 2 6 4 1, 3, 2 2 3 7 2, 1, 3 7 1 4 2, 3, 1 4 1 7 3, 1, 2 7 3 2 3, 2, 1 4 6 2 Povprečje 13/3 10/3 13/3 Shapleyjeve vrednosti so torej φ1 = 13/3, φ2 = 10/3, φ3 = 13/3. 6. Naj bo σ maksimalni skupni sporazumni dobitek. Za izračun Shapleyjevih vredno- sti spet tabelirajmo prispevka obeh igralcev h koaliciji za oba možna vrstna reda pristopanja: Vrstni red 1 2 1, 2 u σ − u 2, 1 σ − v v Povprečje σ+u−v σ−u+v 2 2 Tako vidimo, da se Shapleyjevi vrednosti res ujemata z Nashevim sporazumom. 7. Če prvi igralec igra proti drugima dvema, igra igro (prikazani so le njegovi dobitki): T2T3 T2B3 B2T3 B2B3 T1 0 2 1 1 B1 1 1 2 1 in vrednost te igre je 1. Drugi igralec proti prvemu in tretjemu igra igro: T1T3 T1B3 B1T3 B1B3 T2 3 3 3 3 B2 4 3 3 4 in njena vrednost je 3. Tretji igralec proti prvima dvema igra igro: T2T3 T2B3 B2T3 B2B3 T3 6 6 7 6 B3 7 6 5 6 in njena vrednost je 6. Če se prvi in drugi igralec združita v koalicijo proti tretjemu, igrata igro: T3 B3 T1T2 3 5 T1B2 5 4 , B1T2 4 4 B1B2 5 5 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 107 katere vrednost je 5. Če se prvi in tretji igralec združita v koalicijo proti drugemu, igrata igro: T2 B2 T1T3 6 7 T1B3 9 7 , B1T3 8 8 B1B3 6 7 katere vrednost je 8. Če pa se drugi in tretji igralec združita v koalicijo proti prvemu, igrata igro: T1 B1 T2T3 9 10 T2B3 10 8 , B2T3 10 9 B2B3 9 10 katere vrednost je 19/2. Končno, če se vsi trije združijo v koalicijo, si lahko zago- tovijo največji skupni dobitek, ki znaša 12. Koalicijska oblika igre je torej: v({1}) = 1 , v({2}) = 3 , v({3}) = 6 , 19 v({1, 2}) = 5 , v({1, 3}) = 8 , v({2, 3}) = , 2 v({1, 2, 3}) = 12 . Imputacije tvorijo trikotnik z oglišči (3, 3, 6), (1, 5, 6) in (1, 3, 8). Jedro je petkotnik z oglišči (5/2, 7/2, 6), (2, 4, 6), (1, 4, 7), (2, 3, 7) in (5/2, 3, 13/2). Slika: x2+x3≥19/2 x2≥3 (1,3,8) (2,3,7) (1,4,7) x1+x2≥5 ( 5 ,3, 13 ) 2 2 x3≥6 (3,3,6) ( 5 , 7 ,6) (2,4,6) (1,5,6) 2 2 x1+x3≥8 x1≥1 108 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER Za izračun Shapleyjevih vrednosti tabelirajmo prispevke posameznikov h koaliciji za vse možne vrstne rede pristopanja: Vrstni red 1 2 3 1, 2, 3 1 4 7 1, 3, 2 1 4 7 2, 1, 3 2 3 7 2, 3, 1 5/2 3 13/2 3, 1, 2 2 4 6 3, 2, 1 5/2 7/2 6 Povprečje 11/6 43/12 79/12 Shapleyjeve vrednosti so torej φ1 = 11/6, φ2 = 43/12, φ3 = 79/12. 8. Če koalicija vsebuje Ambroža in še vsaj enega mesarja, dobi toliko, kolikor največ iztrži mesar, ki je v koaliciji. Sicer koalicija ne dobi ničesar. Torej velja: v({A}) = v({B}) = v({C}) = v({B, C}) = 0 , v({A, B}) = 90 , v({A, C}) = v({A, B, C}) = 120 . Pri delitvi dobička, ki je v jedru, Boris ne sme dobiti ničesar, sicer bi lahko Ambrož in Cveto izstopila iz velike koalicije in bi dobila več (120 denarnih enot). Toda Borisova prisotnost pomeni, da Cveto ne sme dobiti več kot 30 denarnih enot. V nasprotnem primeru bi namreč lahko Ambrož in Boris izstopila iz velike koalicije in bi dobila več (90 denarnih enot). Drugi izstopi iz koalicije pa pomenijo le, da na koncu nihče ne sme biti v minusu, saj je izkupiček drugih koalicij enak nič (ni pa negativen). Skratka, jedro predstavljajo natanko koalicije, pri katerih Ambrož dobi a, Boris nič, Cveto pa 120 − a, kjer je 90 ≤ a ≤ 120. Za izračun Shapleyjevih vrednosti tabelirajmo prispevke posameznikov h koaliciji za vse možne vrstne rede pristopanja: Vrstni red A B C A, B, C 0 90 30 A, C, B 0 0 120 B, A, C 90 0 30 B, C, A 120 0 0 C, A, B 120 0 0 C, B, A 120 0 0 Povprečje 75 15 30 Shapleyjeve vrednosti so torej φA = 75, φB = 15 in φ3 = 30, se pravi, da mora tudi Boris dobiti nekaj denarja. 10. Shapleyjeva vrednost posameznega člana odbora je tukaj kar verjetnost, da ta član odločilno prispeva k sprejetju projekta, če si predstavljamo, da so najprej vsi proti, M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 109 nato pa v na slepo izbranem vrstnem redu drug za drugim spremenijo svojo odlo- čitev v pozitivno. Predsednik odločilno prispeva, če je svoje mnenje spremenil kot drugi ali tretji, torej ima Shapleyjevo vrednost 2 = 1 . Vsak drug član pa odločilno 4 2 prispeva, če je bodisi spremenil svoje mnenje kot drugi in ga je pred njim že spre- menil predsednik bodisi je spremenil svoje mnenje kot tretji, predsednik pa ga je spremenil kasneje. Dobimo Shapleyjevo vrednost 1 · 1 + 1 · 1 = 1 . 4 3 4 3 6 Podobno velja, če je članov 2n in je projekt sprejet, če se s tem strinja bodisi več kot polovica članov bodisi polovica članov, med katerimi pa je tudi predsednik. Predsednik odločilno prispeva, če je svoje mnenje spremenil kot n-ti ali kot (n + 1)- ti, torej ima Shapleyjevo vrednost 2 = 1 . Vsak drug član pa odločilno prispeva, če 2n n je bodisi spremenil svoje mnenje kot n-ti in ga je pred njim že spremenil predsednik bodisi je spremenil svoje mnenje kot (n+1)-ti, predsednik pa ga je spremenil kasneje. Dobimo Shapleyjevo vrednost 1 · n−1 + 1 · n−1 = n−1 . 2n 2n−1 2n 2n−1 n(2n−1) 11. Za vse možne vrstne rede pristopanja h koaliciji moramo izračunati, koliko posame- zen igralec prispeva k skupnemu dobitku. Če je Adrijan v koalicijo stopil kot i-ti, je njegov prispevek enak i, če je pred njim že vstopila Brigita ali pa Cveto, sicer pa je enak nič. Verjetnost tega dogodka je: 1 i − 1 (i − 1)(i − 2) 11i − i2 − 10 2 · − = 6 5 5 · 4 120 in je za i = 1 seveda enaka nič. Torej je Adrijanova Shapleyjeva vrednost enaka: 6 5i − i2 − 4 8 14 18 20 20 35 i · = 2 · + 3 · + 4 · + 5 · + 6 · = . 120 120 120 120 120 120 12 i=2 Če je Brigita vstopila v koalicijo kot i-ta, je njen prispevek enak i, če je pred njo že 1 i − 1 6 − i vstopil Adrijan, ne pa tudi Cveto. Verjetnost tega dogodka je · · in je 6 5 4 za i = 1 in i = 6 seveda enaka nič. Če sta pred Brigito vstopila tako Adrijan kot 1 i − 1 (i − 2) tudi Cveto, je njen prispevek enak 1. Verjetnost tega dogodka je · · 6 5 4 in je za i = 1, 2 enaka nič. Sicer (če Adrijan ni vstopil pred Brigito) pa je njen prispevek enak nič. Torej je Brigitina Shapleyjeva vrednost enaka: 5 6 (i − 1)(6 − i) (i − 1)(i − 2) 11 i · + = . 120 120 12 i=2 i=3 To je tudi Cvetova Shapleyjeva vrednost. Za vsakega od preostalih igralcev pa velja, da je, če je pred njim že vstopil Adrijan ter tudi Brigita ali Cveto, njegov prispevek enak 1, sicer pa je enak nič. Verjetnost, da se to zgodi in da je dani igralec hkrati vstopil kot i-ti, je enaka: 1 i − 1 i − 2 (i − 2)(i − 3) (i − 1)(11i − i2 − 18) · · 2 · − = , 6 5 4 4 · 3 360 110 M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER in je za i = 1, 2 enaka nič. Torej je Shapleyjeva vrednost enaka: 6 (i − 1)(11i − i2 − 18) 12 30 48 60 5 = + + + = . 360 360 360 360 360 12 i=3 35 11 5 Opomba. Vsota vseh Shapleyjevih vrednosti je + 2 · + 3 · = 6, kar je 12 12 12 natančno skupni dobitek polne koalicije. Torej bi lahko enega od računov izpustili. M. RAIČ: REŠENE NALOGE IZ TEORIJE IGER 111 Literatura [1] S. Cabello: Vaje iz teorije iger. Elektronsko gradivo, dostopno na http://www.fmf.uni-lj.si/~cabello/gradiva/vajeteorijaiger.pdf. Ljubljana, 2010. [2] T. S. Ferguson: Game Theory. Elektronsko gradivo, dostopno na http://www.math.ucla.edu/~tom/Game Theory/Contents.html. Druga izdaja, Los Angeles, 2014. [3] M. Osborne, A. Rubinstein: A Course in Game Theory. MIT Press, Cambridge, MA, 1994. [4] B. von Stengel: Game Theory Basics. Elektronsko gradivo, dostopno na http://www.maths.lse.ac.uk/personal/stengel/lectnotes1-7.pdf. London School od Economics, 2011.