Vaje iz teorije iger Sergio Cabello 9. november 2010 naslov: Vaje iz teorije iger avtorske pravice: Sergio Cabello izdaja: prva izdaja založnik: samozaložba avtor: Sergio Cabello leto izida: 2010 (v Ljubljani) natis: elektronsko gradivo http://www.fmf.uni-lj.si/~cabello/gradiva/vajeteorijaiger.pdf CIP - Kataložni zapis o publikaciji Narodna in univerzitetna knjiznica, Ljubljana 519.83(075.8)(076.1) CABELLO, Sergio Vaje iz teorije iger [Elektronski vir] / Sergio Cabello. - 1. izd. - El. knjiga. - V Ljubljani : samozal., 2010 NaCin dostopa (URL): http://www.fmf.uni-lj.si/~cabello/gradiva/vajeteorijaiger.pdf ISBN 978-961-276-044-1 253229312 Kazalo 1 Strateške igre 4 1.1 Strateške igre s funkcijami preferenc..........................................4 1.2 Strateške igre s funkcijami koristnosti ........................................8 1.3 Bayesove igre....................................................................14 2 Ekstenzivne igre 16 3 Kooperativne igre 21 Za studiranje priporoCam naslednje knjige: • Martin J. Osborne. Introduction to Game Theory. Oxford University Press, 2002. • Thomas S. Ferguson. Game Theory. Elektronska knjiga dostopna na http://www. math.ucla.edu/~tom/Game_Theory/Contents.html • Bernhard von Stengel. Game Theory Basics. Osnutek knjige dostopen na http: //www.maths.lse.ac.uk/Courses/MA301/lectnotes.pdf Na svetovnem spletu je moc najti zelo dobre skripte in prosojnice, ki so vcasih lažje za razumevanje in bolj neformalne. Poisci! V najslabsem primeru bos nasel druge zanimive stvari. Zahvala. Zahvaljujem se Martinu Juvanu za stevilne popravke. Seveda pa je avtor odgovoren za vse preostale napake. 1 Strateške igre 1.1 Strateške igre s funkcijami preferenc Vse igre v tem razdelku so igre s funkcijami preferenc in igralci lahko izberejo samo ciste strategije. 1.1. Študenti boste igrali naslednjo igro. Vsak student bo napisal eno celo stevilo med 0 in 100. Ucitelj bo izracunal povprecno vrednost vasih stevil, ki jo oznacimo z m. Študenti, ki bodo izbrali najmanjse stevilo nad 2m/3, si bodo razdelili eno tocko pri koncni oceni vaj. Na primer, ce studenti izberejo 0, 20, 20, 30, 30, 45, potem je m = 145/6 = 24.166..., in 2m/3 je 16.111.... Tako bo vsak student, ki je izbral 20, dobil 1/2 tocke pri koncni oceni vaj. Katero stevilo bos izbral? 1.2. Ali sta naslednja strateska igra in zapornikova dilema ekvivalentni? X Y W 3, 3 1, 5 Z 4, 1 0, 0 Zapisi nakljucno 2 x 2 stratesko igro za dva igralca. Ali je igra ekvivalentna zapornikovi dilemi? 1.3. Doloci smiselno definicijo ekvivalentnosti med strateskimi igrami. Dokazi, da ima definicija naslednje lastnosti1: (a) Definicija ekvivalentnosti je ekvivalencna relacija: refleksivna, simetricna in tranzi-tivna. (b) Ce sta igri r in r' ekvivalentni in ima igra r k Nashevih ravnovesij, potem ima igra r' tudi k Nashevih ravnovesij. 1.4. Doloci diskretno stratesko igro za 3 igralce, ki nima nobenih Nashevih ravnovesij. Igra naj ima naslednjo lastnost: Ui(a) = Ui(a') za poljubne profile a = a' in poljubnega igralca Pi. 1.5. Opazujemo naslednjo igro za 3 igralce, kjer ima vsak igralec Pi mnozico akciji Ai = {Ti, Bi}. T2 B2 T2 B2 Ti 3, 4,4 1,3,3 Ti 4, 0, 5 0, 1, 6 B2 8, 1,4 2, 0,6 B2 5, 1, 3 1, 2, 5 ce a3 = = t3 ce a3 = = Ba 1(5e definicija nima takih lastnosti, najverjetneje ni smiselna. (a) Določi Nasheva ravnovesja igre. (b) Določi vse pare akcij, kjer prva akcija dominira drugo akcijo. 1.6. Zanima nas strateska igra, kjer imamo 3 igralce in Ai = {A,B}, A2 = {X, Y} in A3 = {L, M, R}. Funkcije preferenc so dolocene s spodnjimi tabelami, 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 ce a3 = L ce a3 = M ce a3 = R (a) Kaksna so cista Nasheva ravnovesja? Odgovor je odvisen od parametrov a,b G R. (b) Ali kaka cista akcija dominira drugo cisto akcijo? Odgovor mora biti tudi odvisen od parametrov a, b. 1.7. Zanima nas strateska igra, dolocena s spodnjo tabelo. Prvi igralec ima zvezno množico akcij, drugi igralec pa ima samo dve moZni akciji. Doloci Nasheva ravnovesja igre. £ r ai G [0,1] 2 — 2 a1, a1 a1,1 — a1 1.8. Opazujemo naslednjo stratesko igro za dva igralca. Množica akcij vsakega igralca je (0, to). Funkciji preferenc igralcev sta ui(ai,a2) = ai(a2 — ai) in u2(ai,a2) = a2(1 — ai — a2). Doloci Nasheva ravnovesja igre. 1.9. Zanima nas naslednja modifikacija Cournotovega modela duopola. Vsak igralec Pi doloci kolicino qi > 0 produkta, ki ga proizvaja. Cena produkta je odvisna od skupne kolicine Q, ki jo proizvajajo, po formuli P(Q) = { a — Q, ce0 - Q - a; 0, sicer. Funkcija preferenc igralca Pi je enaka dobicku, ki ga dobi. Gledamo primer, kjer ima vsak igralec Pi razlicen strosek ci za eno enoto produkcije. Predpostavimo, da je a > ci > c2. Potem je dobicek igralca Pi podan z Ui(qi,q2) = qi ■ (P(qi, q2) — Ci). Doloci vsa Nasheva ravnovesja igre. 1.10. Uporabimo notacijo iz vaje 1.9, vendar predpostavimo, da so stroski za produkcijo kolicine qi enaki q2. Doloci funkcijo, ki pove dobicek vsakega igralca, in doloci vsa Nasheva ravnovesja igre. 1.11. Doloci Nasheva ravnovesja modifikacije Cournotovega modela oligopola za n igralcev, kjer imajo vsi igralci enake stroske za produkcijo ene enote proizvoda. 1.12. Opazujemo modifikacijo Cournotovega modela duopola, kjer ima vsak igralec zacetne stroske cstart. Torej so stroski proizvodnje kolicine qi enaki cstart + cq^ Doloci vsa Nasheva ravnovesja igre. 1.13. Uporabimo notacijo iz vaje 1.9, vendar je cena produkta dolocena po p fQ2/4 - 5Q + 26, ce 0 < Q < 10; 1, sicer. Predpostavimo, da so stroski proizvodnje ene enote c = 1. (a) Ce je igra monopol, kaksna je optimalna resitev igre? (b) Doloci vsa Nasheva ravnovesja duopola. Treba je razmisljati samo o primeru 0 < qi + q2 < 10. 1.14. Gledali bomo modifikacijo Cournotovega modela duopola. Dve firmi (Pi in P2) sta na trgu in proizvajata isti produkt. Vsaka firma Pi mora dolociti kolicino qi > 0 produkta, ki ga naredi. Cena produkta je potem podana s formulo Df , /20 - 2qi - 3q2, ce 20 - 2qi - 3q2 > 0; p (qi,q2) = 0. Funkcija preferenc igralca Pi je ti, ce ti < tj; Vi/2 — ti, ce ti = tj; vi — tj, ce ti > tj, kjer je P j = Pi drugi igralec. V opisu igre imamo parametra v1 in v2. Predpostavimo, da velja v1 > v2 > 0. Doloci najboljsi odgovor vsakega igralca in vsa Nasheva ravnovesja igre. 1.20. Opazujemo mrezo cest, ki je na levi strani naslednje slike. Pri vsaki usmerjeni povezavi je napisan cas za potovanje po povezavi, kjer je a stevilo avtomobilov na povezavi. Predpostavimo, da je 4000 avtomobilov, ki potujejo hkrati po omrezju2. Vsak avto je igralec, ki mora dolociti svojo pot od START do END. (a) Ali obstaja Nashevo ravnovesje? Ali jih je vec? Koliko casa porabi posamezni avto za potovanje od START do END pri vsakem Nashevem ravnovesju? (b) Neverjetno hitra cesta, ki povezuje TOP in BOT, je koncno dokoncana. Glej desno stran slike. Cas potovanja po novi cesti je enak nic. Ali obstajajo Nasheva ravnovesja v novem cestnem omrezju? Koliko casa porabi posamezni avto v novem omrezju za potovanje od START do END pri Nashevem ravnovesju? (c) Primerjaj (a) in (b). Ta fenomen je poznan kot Braessov paradoks. Preberi clanek v Wikipediji. 1.21. V skupini je deset oseb. Vsaka oseba ima dve moznosti: sodelovanje pri skupnem velikem projektu (BIG) ali narediti svoj majhen samostojen projekt (SMALL). Projekt BIG bo uspesen samo, ce bodo pri njem sodelovale vse osebe. Ce igralec Pi izbere SMALL, je uspesen v svojem majhnem projektu. Preference vsakega igralca so naslednje: izbira BIG, ko je projekt BIG uspesen, je najboljsi izid; izbira SMALL je naslednji izid; najslabsi izid je izbira BIG, ko projekt BIG ni uspesen. 2Mogoče je bolj primerno upoštevati, da je stalen dotok avtomobilov z gostoto 4000. Ali ce razmišljamo o internetu, da je stalen dotok bitov. (a) Opisi ta scenarij kot strateško igro. (b) DoloCi Nasheva ravnovesja igre. (c) Posplosi scenarij na n igralcev. (d) Spremenimo scenarij na naslednji nacin. V skupini je n oseb in projekt BIG bo uspesen, ce ga izbere vsaj k oseb. Vsak majhen projekt ima isti dobicek s. Projekt BIG ima vecji dobicek b. Dobicek uspe snega projekta bo razdeljen med osebe, ki so sodelovale na projektu. Doloci Nasheva ravnovesja igre v odvisnosti od parametrov n, k, s, b. 1.22. Opazujemo stratesko igro, ki smo jo spoznali na predavanju in modelira draZbo tipa druge cene z zaprtimi ponudbami (second-price sealed-bid). Ali je naslednja trditev pravilna: za vsakega igralca Pi obstaja Nashevo ravnovesje, pri katerem igralec Pi dobi predmet drazbe. 1.23. Zanima nas drazba tipa prve cene z zaprtimi ponudbami (first-price sealed-bid). Podobne drazbe so uporabili za cvetje na Nizozemskem ali ribe v Španiji. Števec pokaze trenutno ceno, ki se zmanjsuje, dokler neki igralec ne rece, da bo placal prikazano ceno. Modeliraj tak scenarij kot stratesko igro in doloci vsa Nasheva ravnovesja. Lahko pred-postavis, da imajo vrednosti igralcev lastnost v1 > v2 > • • • > vn. 1.2 Strateške igre s funkcijami koristnosti Vse igre v tem razdelku so igre s funkcijami koristnosti in igralci lahko izberejo mesane strategije. 1.24. Pokazi naslednjo trditev: funkciji koristnosti u, u' : A ^ R dolocata iste preference na n(A) natanko tedaj, ko velja u' = au + P za neki konstanti a > 0 in p. 1.25. Naj bo r igra za n igralcev, pri cemer velja |Ai| = 2 za vsako mnozico akcij Ai. Naj bo (ni,... , nn) profil mesanih strategij, ki zadosca Ui(n i, ...,nn | S (a)) = Ui(n i, ...,nn | S(b)) Vi, Va,b G Ai. Pokazi, da je (n1,..., nn) Nashevo ravnovesje. 1.26. Opazujemo igro, doloceno s spodnjo tabelo. A B X a, b 2,4 Y 1,3 a, b Kaksna so (mesana) Nasheva ravnovesja igre? Odgovor je odvisen od parametrov a, b. 1.27. Opazujemo stratesko igro, doloceno s spodnjo tabelo, kjer ima prvi igralec zvezno mnozico akcij, drugi igralec pa ima samo dve mozni akciji. £ r ai G [0,1] 2 — 2ai, ai ai, 1 — ai (a) Ce vsak igralec izbere akcijo enakomerno nakljucno, kaksna je pricakovana koristnost vsakega igralca? (b) Ce prvi igralec izbere akcijo enakomerno nakljucno, kaksen je najboljsi odgovor drugega igralca? 1.28. Doloci Nasheva ravnovesja iger, dolocenih s spodnjimi tabelami. B S A B A B C B 2, 1 0, 0 X 5, 1 0,2 X 5, 1 0,2 3, 1 S 0, 0 1, 2 Y 1,0 2,3 Y 1,0 2,3 2,4 Z 0, 0 1,3 1, 5 1.29. Opazujemo izvajanje enajstmetrovk pri nogometu. Igralec se mora odločiti, ali bo streljal levo ali desno, in vratar se mora odlociti, ali bo skocil levo ali desno. Predpostavimo, da igralec in vratar vnaprej odlocita, kaj bosta storila. Za vsako kombinacijo je v spodnji tabeli verjetnost gola, ki jo je s pregledom velikega stevila izvajanj poklicnih nogometasev dolocil Palacios-Huerta (Professionals Play Minimax; Review of Economic Studies 70, str. 395-415). Poi sci Nasheva ravnovesja. Vratar Igralec L D L .90 .60 D .75 .95 1.30. Z uporabo strogih dominacij doloci Nasheva ravnovesja igre, dolocene s spodnjo tabelo. L C R T 4,2 3, 3 1, 5 M 0,4 4, 1 2,0 B 1,4 3, 1 1,7 1.31. Opazujemo igro, doloceno s spodnjo tabelo. Ali je profil me sanih strategij (3/4,0,1/4),(0,1/3,2/3) Nashevo ravnovesje? L C R T 1,2 3, 3 1, 1 M ? ? • 1 • 0, 3 2,4 B ?,4 5, 1 0,7 1.32. Opazujemo strateško igro za 3 igralce, določeno s spodnjo tabelo. Množica akcij igralca P3 je A3 = {A, B, C}. L R L R L R T 1,2, 1 1, 1,4 T 2,4 ,0 5, 2,0 T 4, 4,0 0, 0,2 M 0, 0,4 3, 2,4 M 0, 3, 1 0, 1, 3 M 3, 0, 3 2, 2, 4 ce a3 = A ce a3 = B ce a3 = C Ali je profil mešanih strategij (3/4,1/4), (1/3,2/3), (1/2,0,1/2) Nashevo ravnovesje? Ali je profil mesanih strategij (0,1), (1/3,2/3), (1/2,0,1/2) Nashevo ravnovesje? 1.33. Opazujemo naslednjo igro. Igralca P\ in P2 hkrati izbereta celo stevilo med 1 in K. Ce izbereta isto stevilo, potem placa igralec P2 en evro igralcu P\; sicer nihce ne placa nic. (a) Dokazi, da je Nashevo ravnovesje profil strategij, pri katerih vsak igralec izbere stevilo enakomerno nakljucno. (b) Dokazi, da je profil strategij iz tocke (a) edino Nashevo ravnovesje. (c) Ce si igralec P2 in se moras odlociti, koliko naj ti vnaprej placa igralec P1 za igranje igre, kaksne cene so smiselne? (d) Opazujemo varianto, kjer je K = 2 ali K = 3 in kjer v primeru, da izbereta isto stevilo a, igralec P2 placa igralcu P1 a evrov. Kaksna so Nasheva ravnovesja? 1.34. Pokazi, da je vsaka predpostavka Brouwerjevega ireka o negibni tocki potrebna. (Dovolj je, da pogledas dimenzijo ena.) 1.35. Dokazi Brouwerjev izrek o negibni tocki za eno dimenzijo, to je za R. 1.36. Poisci varnostne nivoje (safety levels) in maxmin strategije vsakega igralca v naslednji bimatricni igri. / 2,1 5, 0 \ /2, 3 4, 2 \ V 0, 8 4, 6 ) V 3, 2 2, 4 ) 1.37. Zapisi linearni program, ki doloci varnostni nivo v1 naslednje matricne igre: 2354 6 4 2 3 I . 0123 Ce nekdo rece, da je (1/2,1/2, 0)T maxmin strategija igralca P1 in vi = 3.5, ali imamo dovolj podatkov, da hitro odlocimo, ali je to res? Kaksno dodatno informacijo bi potreboval, da bi lahko hitro odlocil, ali je res? 1.38. Doloci vrednost in eno Nashevo ravnovesje v naslednji matricni igri: 5 2 -1 -1 \ 1 1 0 1 I . 3 0 -3 7 J 1.39. Doloci vrednost in vsa Nasheva ravnovesja v naslednji matricni igri v odvisnosti od parametra a G R: 43 1a 1.40. Doloci vrednost in vsa Nasheva ravnovesja naslednje matricne igre v odvisnosti od parametra a G R: ' 4 — a —1 0a 1.41. Opazujemo naslednjo matricno igro: 2 —16 0 1 —1 —2 2 1 Ali obstaja Nashevo ravnovesje oblike (a, b, 0), (a', b', 0)? 1.42. Opazujemo naslednjo matricno igro: 2 —3 1 5 1 4 3 —1 2 0 —2 4 (a) Ali obstaja Nashevo ravnovesje oblike (a, b, 1/4), (a', b', 1/4,0)? (b) Ali obstaja Nashevo ravnovesje oblike (8/33, a, b), (a', b', 1/11,0)? 1.43. Opazujemo naslednjo matricno igro, kjer je a parameter: 2378 765a 3464 (a) Doloci, za katere vrednosti parametra a obstaja strategija n1 = (p, 1 — p, 0) G n1 igralca Pi, ki dominira strategijo (0,0,1). (b) Predpostavimo, da parameter a zadosca a > 0. Kaksna je vrednost igre glede na parameter a > 0? (c) Doloci vse maxmin strategije za igralca P1 in P2, ko je a = 3. 1.44. Opazujemo naslednjo matricno igro: 1 2 3 4 4 3 2 1 2 1 4 3 3 4 1 2 (a) Doloci vrednost igre in eno Nashevo ravnovesje. (Namig: racunanje skoraj ni potrebno.) (b) Ali lahko ugotovi s kako splosno pravilo? (c) Ali obstaja samo eno Nashevo ravnovesje? 1.45. Opazujemo naslednji matricni igri: 2 a 3 4 4322 -2 a 3 -2 0 3- a Za vsako doloci vrednost igre in vsa Nasheva ravnovesja. 1.46. Doloci vrednost in eno Nashevo ravnovesje naslednje matricne igre: 1 -2 3 -4 0 1 -2 3 0 0 1 -2 0 0 0 1 1.47. Doloci vrednost in eno Nashevo ravnovesje za naslednje matricne igre. Uporabi trditve, ki zmanj sajo stevilo racunov. 4 2 2 2 4 2 2 2 / 2 5 4 1 2 3 2 2 3 3 2 2 -1 2 5 4 2 2 5 2 3 3 6 2 0 -1 2 5 2 2 2 10 3 3 3 10 V 3 0 -1 2 1.48. Ali lahko doloci s a, b tako, da bo profil (1/4,1/2,1/4), (1/2,1/4,1/4) Nashevo ravnovesje naslednje matricne igre: 2 -16 0 1 -1 a b 1 1.49. Poi sci matricno igro, kjer ima prvi igralec 5 cistih akcij, drugi igralec 6 cistih akcij, igra pa izpolnjuje vse naslednje pogoje: • vsak koeficient matrike je pozitiven; • vrednost igre je 2; • nima sedla. Kako si konstruiral tako igro? 1.50. Ali je naslednja trditev pravilna: ce sta matriki A in B iste velikosti, velja v(A) + v(B) = v(A + B). 1.51. Poisci Nasheva ravnovesja iger, dolocenih s spodnjima tabelama. A B C A B C X 4,2 0, 0 0,1 X 1,0 0,2 3, 3 Y 0, 0 2,4 1,3 Y 0, 6 2, 5 4, 3 1.52. Poisci vsa Nasheva ravnovesja naslednje bimatricne igre: / 6, 0 0, 5 3, a \ 0, 6 4, 1 2, 2 . 1.53. Opazujemo naslednjo bimatricno igro: 0, 3 2, 0 1, 7 3, 3 2,4 a, b 2,0 4, c I . 1, 3 2, 4 0, 3 1, 3 (a) Doloci trojke (a, b, c) G R3, za katere je profil strategij (1, 3, 3), (7, 7, f, 0) Nashevo ravnovesje. (b) Izberemo a = c = 3. Doloci vsa mesana Nasheva ravnovesja v odvisnosti od vrednosti parametra b. 1.54. Opazujemo naslednjo igro. Igralca P1 in P2 hkrati izbereta naravno stevilo iz mnozice {1,2,...,n}. Ce izbereta isto stevilo x, potem igralec P2 placa 2x — 1 evrov igralcu P1. Ce izbereta razlicni stevili, potem igralec P1 placa 1 evro igralcu P2. Doloci (kako) optimalno strategijo za vsakega igralca. Ali bi bil raje igralec P1 ali P2? 1.55. Opazujemo naslednjo bimatricno igro: (A B) f 5,a b,b + 1 \ (A,B) = ^ 3,1 4,4 ) ■ (a) Za vsak par (a, b) G R2 doloci vsa cista Nasheva ravnovesja. (b) Doloci pare (a, b) G R2, za katere je profil (3, 3), (3, 1) mesano Nashevo ravnovesje. (c) Izberemo b = 1. Doloci vsa mesana Nasheva ravnovesja v odvisnosti od vrednosti parametra a. 1.56. Opazujemo stratesko igro, doloceno s spodnjo tabelo, kjer imamo parameter a G R. X Y (a) Za katere vrednosti parametra a obstaja cisto Nashevo ravnovesje? A B C 0,4 1,3 1, a + 1 2, 1 a, 6 — a 2, a (b) Ali obstaja vrednost parametra a, za katero je profil strategij (p, 1 — p), (1, 3,1) Nashevo ravnovesje? (c) Izberemo a = 0. Doloci vsa Nasheva ravnovesja. 1.57. DoloCi vsa mesana Nasheva ravnovesja naslednje bimatriCne igre: 8,12 10,12 6,8 12,16 8,6 8,10 10,14 10,4 1.58. Opazujemo naslednjo bimatriCno igro ( . ( 1, 5 2,4 0,3 3,2 (A,B)= ^ 3, 2 a, 3 4, 5 4, 6 Doloci Nasheva ravnovesja v odvisnosti od vrednosti parametra a. 1.3 Bayesove igre 1.59. Anita Zeli prodati svojo avto in Bojan Zeli kupiti avto. Avto je lahko v dobrem ali v slabem stanju. Anita pozna njegovo stanje, Bojan pa ga ne pozna, vendar misli, da je v dobrem stanju z verjetnostjo p. Ce je avto v dobrem stanju, ima vrednost 2000 za Anito in 3000 za Bojana. Ce pa je v slabem stanju, ima vrednost 0 za Anito in 1000 za Bojana. Ce Bojan kupi avto, bo plaCal K evrov Aniti. Igralca hkrati in neodvisno izbereta akcijo "trgovanje"ali "ne trgovanje". Anita proda avto Bojanu, ce oba izbereta "trgovanje". Modeliraj tako situacijo kot Bayesovo igro. Za katere vrednosti parametra K je Bojan indiferenten med akcijama "trgovanje"in "ne trgovanje". Doloci vsa mesana Bayesova ravnovesja igre. 1.60. Opazujemo Bayesovo igro za dva igralca, ki ima dve mozni stanji: Q = {wi,w2}. Funkciji koristnosti za obe stanji sta doloceni s spodnjima tabelama: P2 P2 Pi L D A 2,4 3, 3 B 1, 3 3, 1 Pi L D A 1, 3 2, 2 B 0, 2 4, 3 stanje u1 stanje Igralec P1 dobi isti signal od stanj w1,w2. Igralec P2 dobi razlicna signala od stanj w1 in w2. Igralca verjameta, da je Pr[w1 ] = ^ G (0,1) in Pr[w2j = 1 — (a) Doloci vsa cista Bayesova ravnovesja igre. (b) Doloci vsa mesana Bayesova ravnovesja igre. (c) Za kaksne vrednosti parametra ^ akcija A dominira akcijo B? 1.61. Opazujemo Bayesovo igro za dva igralca, ki ima tri mozna stanja: Q = |wi, w2, w3}. Funkciji koristnosti za vsako stanje sta doloceni s spodnjimi tabelami: L D L D L D A 4,0 0,4 A 1,0 0,2 A 0,2 2,0 B 0,4 4,0 B 0,2 1, 0 B 4,0 0, 4 stanje stanje u2 stanje u3 Igralec P1 dobi isti signal a od stanj w1, w2 in signal b od w3. Igralec P2 dobi isti signal d od stanj w2, w3 in signal c od w1. Igralca mislita, da velja Pr[w1 ] = Pr[w2] = Pr[w3] = 1/3. • Narisi diagram situacije. • Ko P1 dobi signal a, kaksna je verjetnost, da prihaja iz stanja w1 ? • Ali obstaja čisto Bayesovo ravnovesje, kjer je a(1a) = A in a2,d = L? • Ali obstaja čisto Bayesovo ravnovesje, kjer je a(1a) = A? • Izberemo naslednje me s ane strategije: a(1a) = 2A + 1 B, a(1b) = §A + 3B, a(2,c) = M L +11 D, a(2,d) = i L + f D. Pokazi, da je profil (a(M), a(1,6), a(2,c), a(2,c)) Bayesovo ravnovesje. 1.62. Opazujemo Bayesovo igro za dva igralca, ki ima tri mozna stanja: Q = |w1, w2, w3}. Funkciji koristnosti za vsako stanje sta doloceni z naslednjimi tabelami: P2 Pi L D A 2,4 3, 3 B 1, 3 3, 1 P2 Pi P2 L D L D A 1, 3 2, 2 Pi A 0, 2 -1, 3 B 0, 2 4, 3 B 4, 2 2, 4 stanje stanje stanje w3 Igralec P1 dobi isti signal od stanj w1,w2,w3. Igralec P2 dobi razlicne signale od stanj w1,w2,w3. Igralca verjameta, da je Pr[w1] = 1/2 in Pr[w2] = ^ G (0,1/2) ter Pr[w3] = 1/2 - (a) Doloci vsa cista Bayesova ravnovesja igre. (b) Doloci vsa mes ana Bayesova ravnovesja igre. 1.63. Opazujemo naslednjo igro za dva igralca. Vsak igralec dobi nagrado, ki ima nakljucno vrednost enakomerno porazdeljeno na {1, 2,..., 10}. Igralec ne ve, kaks no nagrado je dobil drugi igralec. Igralca hkrati in neodvisno odlocita, ali bi izmenjala nagrado z drugim igralcem ali ne. Ce oba izbereta izmenjavo, potem izmenjata nagradi. Vsak igralec zeli maksimizirati pricakovano vrednost nagrade, ki jo ima na koncu. Modeliraj tako situacijo kot Bayesovo igro. Doloci cista Bayesova ravnovesja igre. 2 Ekstenzivne igre 2.1. Ali lahko v ekstenzivni igri predpostavimo, da za vsako povezavo uv G T — L (T) velja P(u) = P(v)? 2.2. Opazujemo ekstenzivno igro na sliki: 4 5 3 5 -2 1 -2 3 (a) Koliko strategij ima vsak igralec? (b) Doloci vgnezdena ravnovesja igre. (c) Ali obstaja kako Nashevo ravnovesje, ki ni vgnezdeno ravnovesje? 2.3. Opazujemo ekstenzivno igro na sliki: 5 2 1 5 14 (a) Koliko strategij ima vsak igralec? (b) Doloci vgnezdena ravnovesja igre. (c) Ali obstaja kako Nashevo ravnovesje, ki ni vgnezdeno ravnovesje? 2.4. Zanima nas ekstenzivna igra na sliki, kjer parametri a, b, c niso cela stevila. To je, predpostavimo, da a, b, c ^ Z. Opi si vgnezdena ravnovesja igre v odvisnosti od vrednosti parametrov a, b, c. Ali obstajajo Nasheva ravnovesja, ki niso vgnezdena ravnovesja? ■ Pi P3 P2 a b c ,P3 \p2 1 P3 ,P2 2.5. Hierarhicno urejeno pleme n kanibalov je ujelo misionarja. Hierahija plema je linearna: na celu plemena je glavni kanibal, sledi mu drugi kanibal, potem tretji kanibal in tako naprej do n-tega kanibala. Glavni kanibal ima moznost, da poje misionarja, in samo on ima tako moznost. Ce ga ne poje, potem je konec igre. Ce pa glavni kanibal poje misionarja, potem bo od sel spati in mogoce bo drugi kanibal med spanjem pojedel njega. V splosnem, ce i-ti kanibal poje (i — 1)-tega kanibala, potem bo ossel spati in mogoce bo (i + 1)-vi kanibal pojedel tega med spanjem. Vsak kanibal bi raje jedel kot bite lacen, ampak se rajsi pa bi bil ziv. Nari si drevo igre in doloci vgnezdena ravnovesja. 2.6. Opazujemo problem razdelitve torte, kjer je torta predstavljena kot interval [0,1]. I scemo postopek, ki bo sestavljen iz vec korakov. Postopek na vsakem koraku doloci, ali mora igralec na potezi razrezati ali izbrati kos. Vsak igralec bi rad dobil cim vecji kos. (a) Opazujemo primer, kjer sta dva igralca, postopek pa je naslednji: prvi igralec razreze torto na dva kosa in drugi igralec izbere kos. Modeliraj tak postopek kot ekstenzivno igro. Kaksna je razdelitev pri vgnezdenem ravnovesju? (b) Tokrat imamo tri igralce. Ali lahko oblikujes postopek za razdelitev torte, pri cemer dobi vsak igralec 1/3 torte v vgnezdenem ravnovesju? (c) Ali lahko dosezes isto kot v tocki (b) tudi za n igralcev? 2.7. Opazujemo naslednjo variacijo Stackelbergovega modela duopola. Prva firma P1 mora dolociti kolicino > 0 produkta, ki ga proizvaja. Druga firma P2 opazuje trg in potem doloci kolicino q2 > 0 produkta, ki ga proizvaja. Stros ki produkcije so c(qj) = 4q^ in cena produkta je P(q1, q2) = (160 — 4(q1 — q2))+. (a) Doloci vgnezdena ravnovesja igre. (b) Kaksen dobicek dobi vsaka firma pri vgnezdenem ravnovesju? Ali bi bil rajsi firma P1 ali P2? (c) Poisci Nashevo ravnovesje igre, kjer prva firma P1 dobi cel trg kupcev. 2.8. Zanima nas variacija Stackelbergovega modela duopola, kjer je cena P(Q) = (a—Q)+ in so stroski ci(qi) = qf. Doloci vgnezdena ravnovesja igre. 2.9. Gledali bomo modifikacijo Stackelbergovega modela duopola. Stiri firme (P1 do P4) bodo proizvajale isti produkt. Vsaka firma Pi mora dolociti kolicino qi > 0 produkta, ki ga proizvaja. Cena produkta je podana s formulo (a — q1 — q2 — q3 — q4, ce je pozitivno; P (q1,q2,q3,q4) = < 0, sicer. Dobicek firme Pi je ui = qi(P(q1,q2, q3, q4) — c). Dobicek uporabljamo kot funkcijo preferenc. Tukaj sza a in c konstanti in zadoscata a > c > 0. Modeliramo situacijo kot ekstenzivno igro, ki ima tri korake. V prvem koraku igre doloci firma P1 svojo kolicino q1. V drugem koraku igre doloci firma P2 svojo kolicino q2. V tretjem koraku igre hkrati in neodvisno dolocita firmi P3 in P4 svoji kolicini q3, q4. Doloci vgnezdena ravnovesja igre. 2.10. Gledali bomo modifikacijo Stackelbergovega modela duopola. Dve firmi (P1 in P2) bosta na trgu in bosta proizvajali isti produkt. Vsaka firma Pi mora dolociti kolicino qi > 0 produkta, ki ga naredi. Cena produkta je potem podana s . ) 33 — 3q1 — 5q2, ce 33 — 3q1 — 5q2 > 0; P (q1,q2) = 0 produkta, ki ga naredi. Cena produkta je potem podana s Df , /20 — q1 — 2q2, ce 20 — q1 — 2q2 > 0; P (q1,q2) = kL. Ce izbere kos ki, potem placa igralec P2 ceno ci, kjer je cH > cL. To je, kos kH je drazji kot kL. Nato igralca P1 in P2 igrata igro ultimata, kjer razdelita kos ki, ki ga je izbral P2. Doloci vgnezdena ravnovesja igre v odvisnosti od vrednosti parametrov kH, kL, cH, cL. 2.15. Opazujemo modifikacijo igre ultimata, za katero velja ui(x1,x2) = xi — (1/10)|x1 — x2|, kjer je xi del igralca Pi. Doloci vgnezdena ravnovesja igre. 2.16. Opazujemo modifikacijo igre ultimata, kjer sta dva kroga. Igralec P1 izbere stevilo x1 g [0,1]. Nato igralec P2 sprejme ali zavrne ponudbo. Ce P2 sprejme ponudbo, dobi 1 — x1 in igralec P1 dobi x1. Ce P2 zavrne ponudbo, potem on ponudi drugo razdelitev s stevilo x2, ki jo igralec P1 sprejme ali zavrne. Ce igralec P1 sprejme protiponudbo, dobi 5(1 — x2) in igralec P2 dobi 5x2. Ce igralec P1 zavrne protiponudbo, potem oba igralca dobita 0. Tukaj je 5 < 1 parameter za to, da igralca placata za porabljen cas (stevilo krogev). Lahko razmisljamo, da v drugem krogu razdelita 5 evrov, ker sta ze izgubila (1 — 5) evrov zaradi porabljenega casa. Doloci vgnezdena ravnovesja igre. Ali lahko razsiris igro tako, da bodo 3 krogi ponudb? (V zadnjem krogu razdelita 52 evrov.) 2.17. Doloci vgnezdena ravnovesja naslednje ekstenzivne igre za dva igralca. Igralec P1 izbere realno Stevilo a > 0, nato igralec P2 izbere realno Stevilo b > 0. Ko igralec P2 izbira b, ze pozna S tevilo a, ki ga je izbral igralec P1. Funkcija preferenc igralca P1 je u1(a, b) = 3a(10 — 3b2 — 5a). Funkcija preferenc igralca P2 je u2(a, b) = b((10 — a)2 — b2). 2.18. Imamo sklad denarja, ki na t-tem krogu vsebuje 2t evrov. Igro igrata dva igralca. V vsakem krogu igralca izbereta akcijo, ki je lahko 'wait' ali 'steal'. Ce oba igralca izbereta 'wait', potem gre igra v naslednji krog. C e oba igralca izbereta 'steal', potem vsak igralec dobi polovico denarja iz sklada in igra je koncana. Ce en igralec izbere 'steal' in drugi izbere 'wait', gre denar iz sklada igralcu, ki je izbral 'steal', in igra je koncana. C e igra pride do kroga 1000, potem se konca in vsak igralec dobi polovico denarja iz sklada. Doloci vgnezdena ravnovesja igre. 2.19. Doloci res itev naslednje igre: 10 Gn =( 0 Gn_ J Gi = (1) 2.20. Doloci resitev naslednje igre: 10 Gn = ( 1/2 Gn-1 Gi = (1) 2.21. Opazujemo naslednjo igro za dva igralca s funkcijami preferenc. V strate ski podigri uporabljata me sane strategije. Doloci vgnezdena ravnovesja igre v odvisnosti od vrednosti parametra a G R. 2.22. Opazujemo naslednjo igro za 2 igralca. V strateskih podigrah uporabljata mesane strategije. Doloci vgnezdena ravnovesja igre v odvisnosti od vrednosti parametra a G R. 3 Kooperativne igre 3.1. Določi resitev in točko nesporazuma naslednje bimatrične igre. Določi tudi Dtu in Dntu . '3,1 2,2 0, 5 4,3 3.2. Določi reSitev in točko nesporazuma naslednje bimatrične igre. a, 1 2,2 0, 5 5, 3 3.3. Določi resitev in točko nesporazuma naslednje bimatrične igre. 1, 5 2, 2 0, 1 4, 2 1, 0 2, 1 5, 0 2, 3 0, 0 3.4. Določi resitev in točko nesporazuma naslednje bimatrične igre. 3, 2 4, 1 4, 2 4, 2 2, 3 4, 1 1, 3 3, 0 4, 3 3.5. Za naslednjo bimatrično igro določi resitev in točko nesporazuma. (i + j, i + j), če i = j; (A, B) = (aij,bij)i,j=i,...,n, kjer (aj, bij) = (4, 3), sičer. 3.6. Opazujemo stratesko igro za 3 igralče, določeno s spodnjo tabelo. Katero koaličijsko igro določi? ce a3 = A L R L R T -1,0,0 0, 1,0 T 1, 0, 1 0, 0, 0 M 0, 0, 1 1, 0, 0 M 0, 0, -1 0, 1, 0 ce a3 = B 3.7. Opazujemo stratesko igro za 3 igralče, določeno s spodnjo tabelo. Kaksno karakteristično funkčijo določi? L R T 2, -1, 1 3, 1, 0 M 3, 0,2 -1, 2, 1 če a3 = A L R T 1,2,3 2, 2, 2 M 0, -1,0 0, -2, 4 ce a3 = B L R T -2, 1, 0 1,2, -2 M 0, 0,2 1, 1, 1 če a3 = C 3.8. Opazujemo naslednjo bimatrično igro: 1, 5 2, 4 0, 3 3, 2 (A,B) 1 3,2 a, 3 4,5 4,6 (a) KakSno karakteristično funkcijo koalicijske igre določi igra (A, B)? (b) Preveri,ali je karakteristična funkcija iz točke (a) superaditivna. 3.9. Opazujemo funkčijo v : 2{1'2'3} ^ R z vrednostmi v({1}) = a v({1, 2}) = 6 v(0) = 0 v({2}) = b v({1, 3}) = 10 - a v({1,2,3}) = 15 v({3})=3 v({2, 3}) = 8 - b Za katere vrednosti parametrov a, b je funkčija v karakteristična funkčija? Resitev lahko opisises z uporabo slike. 3.10. Kaksna je mnoziča imputačij, kaksno je jedro in kaksne so Shapleyeve vrednosti za naslednjo koaličijsko igro? v({1}) = -2 v({1, 2}) = 2 v(0) = 0 v({2}) = -1 v({1, 3}) = 1 v({1, 2, 3}) = 3 v({3}) = 0 v({2, 3}) = 1 3.11. Za katere trojke (a,b,c) je naslednja funkčija karakteristična? Nato opisi mnoziče imputačij. v({1}) = a v({1, 2}) = 5 - a v(0) = 0 v({2}) = b v({1, 3}) = a v({1,2,3}) = 10 - a v({3}) = c v({2, 3}) = b + 2c 3.12. Za katere pare (a, b) je naslednja funkčija karakteristična in je jedro igre petkotnik? v({1}) = a v({1, 2}) = 5 - a v(0) = 0 v({2}) = b v({1,3}) = a + 4 v({1,2,3}) = 12 - a v({3}) = 4 v({2, 3}) = 7 3.13. Kaksna je mnoziča imputačij, kaksno je jedro in kaksne so Shapleyeve vrednosti za naslednjo koaličijsko igro? v({1}) = 0 v({1, 2}) = 2 v(0) = 0 v({2}) = 1 v({1, 3}) = 3 v({1, 2, 3}) = 10 v({3}) = 2 v({2, 3}) = 6 3.14. Ali lahko dolocis jedro za naslednjo koalicijsko igro, kjer velja 0 < a1 < a2 < a3? Kaksno je jedro, ce velja v({2,3}) = a2 namesto v({2,3}) = 0? 3.15. Pokazi, da so Shapleyeve vrednosti imputacija. 3.16. Varnostni svet Organizacije Zdruzenih Narodov (OZN) ima 15 clanic. Pet clanic je stalnih. Glede na wikipedijo, "za sprejem odlocitve zadostuje, da se strinja 9 od 15 clanic, med katerimi mora biti vseh 5 stalnih clanic". To lahko modeliramo z naslednjo karakteristicno funkcijo: v(S) = 1, ce S vsebuje vsaj 9 clanic in vseh 5 stalnih clanic; sicer je v(S) = 0. Doloci Shapleyeve vrednosti vseh clanic varnostnega sveta. 3.17. Opazujemo koalicijsko igro z n igralci in karakteristicno funkcijo: v(S) = k, ce velja {1, 2,..., k} C S in k + 1 / S. Na primer: v({2, 3, 4}) = 0, v({1, 2, 4, 5}) = 2 in v({1, 3}) = 1. Naj bo & Shapleyeva vrednost igralca i. (a) Ali bo < 0i+1 ali > 0i+1? (b) Doloci vrednost za vsak i, ko je n = 5. Preveri, ali je vsota + + ■ ■ ■ + prava. (Lahko uporabljas kalkulator.) (c) Kaksna je v splosnem primeru? 3.18. Doloci Shapleyeve vrednosti naslednje koalicijske igre. Igra je za 5 igralcev, ki so razdeljeni na dve skupini A, B. Velja |A| = 2 in |B| = 3. Karakteristicna funkcija v : 2AuB ^ R je dolocena takole: 3.19. Doloci, ali obstaja koalicijska igra za 3 igralce, ki izpolnjuje naslednje pogoje: • Velja = 1, = 2 in = 3, pri cemer je Shapleyeva vrednost igralca i. 3.20. Opazujemo naslednjo bimatricno igro v({1}) = a1 v({1,2})= a2 v(0) = 0 v({2}) = 0 v({1,3}) = af v({1,2,3}) = af v({3}) = 0 v({2,3})=0 1, ce velja S n A = 0 in S n B = 0; 0, sicer. • v({1})= v({2})= v({3}). (A, B) 8, 2 1, 0 4, -1 3, 3 6, 3 4, 0 1, -1 0, 1 2, 0 (a) Doloci resitev (sporazum) in tocko nesporazuma, ko igralca sodelujeta in je koristnost prenosljiva. (b) Kaksno karakteristicno funkcijo koalicijske igre doloci igra (A, B)? (c) Resi tocki (a) in (b) se za bimatricno igro / 15, 2 (A',B) = I 10,3 \ 8, —1 3.21. Opazujemo naslednjo bimatricno igro =(2:6 (a) Doloci resitev (sporazum) in tocko nesporazuma, ko igralca sodelujeta in je koristnost prenosljiva. (b) Kaks no karakteristicno funkcijo koalicijske igre doloci igra (A, B)? 8, 0 11, —1 13, 3 11, 0 7,1 9, 0 a, 0 4, 2