Transcript
UNIWERSYTET WROCAWSKI Wydziaª Matematyki i Informatyki Instytut Matematyczny
M.Majsnerowska
semestr letni 2016/2017 r.
WSTP DO TEORII GIER Plan wykªadu
1. Wprowadzenie i przykªady gier gry wielosobowe, dwuosobowe, dwuosobowe o sumie zero, wieloetapowe, losowe 2. Podstawowe poj¦cia i twierdzenia strategia: czysta, mieszana, warto±¢ gry i:gracza, punkt równowagi Nasha, dominowanie, twierdzenie Nasha o istnieniu punktu RN, twierdzenie Nasha o no±nikach 3. Gry o sumie zero wªasno±ci strategii optymalnych metody rozwi¡zywania niektórych typów gier dwuosobowych 4. Gry z niepeªn¡ informacj¡ 5. Schemat arbitra»owy Nasha 6. Posuni¦cia strategiczne uzgodnienia kolejno±ci ruchów graczy, obietnice, gro¹by 7. Gry n-osobowe i koalicje gry w postaci funkcji charakterystycznej, imputacje, dominacje, rdze«, warto±¢ Shapleya
Literatura
1. R. D. Luce, H. Rai a, Gry i decyzje 2. Ph. Stran, Game Theory and Strategy 3. T. Pªatkowski, Wst¦p do teorii gier 4. S. Tadelis, Game Theory
Zasady zaliczenia ¢wicze« b¦d¡ podane na pierwszym wykªadzie
Wst¦p do teorii gier Lista zada« nr 1
Dla opisanych poni»ej gier okre±l zbiory strategii graczy, funkcj¦ (macierz) wypªat oraz warto±ci gry ka»dego gracza. Zakªadamy, »e trzy ostatnie s¡ grami dwuosobowymi o sumie zero. 1. Dwóch my±liwych mo»e polowa¢ na jelenia (J) lub zaj¡ce (Z). Ich decyzje zapadaj¡ równocze±nie i niezale»nie (tzn. bez wiedzy o decyzji drugiego). Jele« ma warto±¢ 4, zaj¡ce po 1. Je±li obaj zapoluj¡ na jelenia, upoluj¡ go, otrzymuj¡c po 2. Je±li jeden wybierze J, a drugi Z, to pierwszy nic nie upoluje, a drugi upoluje zaj¡ca. Je±li obaj wybior¡ Z, otrzymuj¡ po 1. 2. Dwóch pracowników wykonuje pewn¡ prac¦, przy czym ka»dy z nich mo»e pracowa¢ (wtedy si = 1) lub udawa¢ prac¦ (wtedy si = 0), i = 1; 2: Je±li gracz pracuje, ponosi koszt 3, je±li tylko udaje 0. Wynik pracy wynosi 2(s1 + s2 ) dla ka»dego z nich, niezale»nie od tego, czy pracowaª, czy udawaª. 3. Dwóch kierowców stoi na drodze zasypanej przez lawin¦. Caªkowity nakªad energii potrzebny do od±nie»enia drogi wynosi c > 0, korzy±¢ ka»dego z nich z dojechania do domu to b > c. Energia (wypªata) ka»dego gracza, gdy obaj nic nie robi¡ wynosi a < b c: 4. Dwóch graczy ma do podziaªu kwot¦ 100: A proponuje B podziaª: x dla B, reszta dla A, gdzie x 2 f1; 2; : : : ; 100g: Gracz B mo»e si¦ zgodzi¢ i wtedy wypªaty s¡ takie, jak zaproponowaª A, albo nie zgodzi¢ i wtedy ka»dy otrzymuje zero. 5. Uczestnicy tej wieloosobowej gry rozwa»aj¡ podj¦cie pewnej inicjatywy { akcji. Ka»dy z nich ma do wyboru jedn¡ z dwóch decyzji: "wzi¡¢ w niej udziaª" lub "pozosta¢ z boku". Je±li wi¦cej ni» poªowa uczestników przyª¡czy si¦ do akcji, to ka»dy z nich otrzymuje wypªat¦ 100. Gdy uczestnicy, którzy tak zdecyduj¡, nie osi¡gn¡ wi¦kszo±ci, to ka»dy z nich zapªaci "kar¦" wysoko±ci 10. W ka»dym przypadku gracze, którzy nie przyª¡cz¡ si¦ do akcji, ani nie otrzymuj¡ premii, ani nie pªac¡ kary. 6. Ka»dy gracz rzuca dwoma lub trzema kostkami i jednocze±nie jedn¡ monet¡. Je±li I gracz wybierze l1 kostek, a drugi gracz l2 kostek oraz n jest liczb¡ orªów, które pojawiªy si¦ w rzutach obu graczy, to I gracz otrzymuje wygran¡ równ¡
Wn(l1 ; l2) = jl1 2nj + jl2 2nj: 7. Gracz I zapisuje na kartce jedn¡ z 26 liter alfabetu. Nie pokazuj¡c tej kartki graczowi II, mówi, co napisaª, ale mo»e skªama¢. Gracz II zgaduje, czy przeciwnik powiedziaª prawd¦, stwierdzaj¡c: prawda lub faªsz. Je±li gracz I zostanie przyªapany na kªamstwie, to pªaci garczowi II kwot¦ 100. Gdy gracz II odgadnie prawidªowo, »e gracz I mówi prawd¦, to gracz I pªaci 20. Je±li gracz II pomyli si¦, to gracz I otrzymuje 60. 8. Gracz I wybiera jedn¡ z trzech kart: króla, 10 lub 2. Wtedy gracz II zgaduje S lub M . Je±li ma racj¦ (król jest kart¡ starsz¡ S , a 2 { mªodsz¡ M ), otrzymuje kwot¦ 3 od gracza I, a pªaci mu kwot¦ 2, gdy si¦ pomyli. Je±li I gracz wybraª 10, to gracz II wygra kwot¦ 2, je±li oceni j¡ jako M , ale gracz I b¦dzie musiaª wybiera¢ mi¦dzy królem a 2, je±li gracz II oceni 10 jako S . Wtedy gracz II znów zgaduje: S lub M i wygra kwot¦ 1, je±li ma racj¦, a traci kwot¦ 3 w przeciwnym razie.
Wst¦p do teorii gier Lista zada« nr 2
1. Wyznacz punkty równowagi Nasha (punkty RN) dla gier opisanych w zadaniach 1 - 5 listy 1: 2. Poka», »e para strategii mieszanych ((0:5; 0:5); (0:5; 0:5)) stanowi punkt RN w grze Kot
Mysz:
3. Uzasadnij, »e w grze dwuosobowej o sumie zero okre±lenie punktu RN sprowadza si¦ do:
W1(x; y) W1 (x; y) W1(x; y); x 2 X; y 2 Y: 4. Sprawd¹, czy istniej¡ punkty siodªowe dla gier opisanych w zadaniach 6 - 8 listy 1: 5. Udowodnij tw. Brouwera o punkcie staªym dla funkcji ci¡gªej na prostej rzeczywistej. Wsk. Zauwa», »e A = [a; b] i rozwa» funkcj¦ g(x) = (x) x: 6. Uzasadnij, »e zbiór strategii mieszanych gracza jest zbiorem wypukªym, ograniczonym i domkni¦tym. 7. Udowodnij nast¦puj¡cy lemat: Je±li X = fx = (x1 ; : : : ; xn ); Pni=1 xi = 1; xi 0g, to dla dowolnych s1; : : : ; sn zachodzi max x2X
n X i=1
xi si = maxfs1; : : : ; sng:
8. Dla gier o nast¦puj¡cych macierzach wypªat wyznacz wszystkie punkty RN:
!
!
!
; 4) (1; 0) (3; 3) ( 1; 5) (0; 1) (1; 1) M = (2 (3; 1) (0; 4) ; N = (5; 1) (0; 0) ; P = (2; 2) (0; 0) ; 1 0 (0; 1) (0; 1) (2; 4) Q = B@ (5; 1) (4; 2) (1; 0) CA (4; 3) (1; 4) (1; 0)
9. Rozwa»aj¡c maksima funkcji wypªat obu graczy wyznacz wszystkie punkty RN dla gry o nast¦puj¡cej macierzy wypªat
1 0 (3; 3) (0; 2) (0; 2) P = B@ (2; 0) (2; 2) (2; 0) CA : (2; 0) (0; 2) (3; 3)
10. Stosuj¡c twierdzenie Nasha o no±nikach wyznacz wszystkie punkty RN dla gry:
!
; 2) (2; 7) (3; 6) R = (7 (2; 7) (7; 2) (4; 5) : 11. Sprawd¹, czy dla poni»szej gry istniej¡ punkty RN o no±nikach postaci a) f1; 3g f1; 2g; b) f1; 2; 3g f1; 2; 3g; 0 1 (0; 1) (0; 2) (2; 3) V = B@ (0; 0) (2; 1) (1; 1) CA : (2; 2) (1; 4) (1; 1)
Wyznacz ponadto wszystkie punkty RN w zbiorze strategii czystych. 12. Uzasadnij, »e wypªata dla punktu RN jest równa wypªacie dla dowolnej strategii czystej z no±nika strategii mieszanej wyst¦puj¡cej w tym punkcie RN. 13. Sprawd¹, czy znalezione w poprzednich zadaniach punkty RN w zbiorach strategii czystych s¡ optymalne w sensie Pareto. 14. Uzasadnij, »e w grach o sumie zero wszystkie strategie s¡ optymalne w sensie Pareto.
Wst¦p do teorii gier Lista zada« nr 3
Wszystkie zadania tej listy dotycz¡ gier dwuosobowych o sumie zero. 1. Poka», »e dodanie staªej do wszystkich wyrazów macierzy wypªat nie zmienia zbioru strategii optymalnych obu graczy. Jak zmienia warto±¢ gry? A je±li pomno»ymy wyrazy macierzy wypªat przez staª¡ ró»n¡ od zera? 2. Sprawd¹, czy wektory 1 1 1 1 5 1 x = 4; 2; 4 ; y = 4; 8; 8 s¡ optymalnymi strategiami w grze o macierzy wypªat postaci
0 1 5 1 3 W = B@ 1 3 1 CA : 2 2 4
Je±li tak, to podaj warto±¢ tej gry, je±li nie, jej oszacowanie. 3. Sprawd¹, czy wektory 1 5 1 1 1 1 x = 4; 2; 4 ; y = 4; 8; 8 s¡ optymalnymi strategiami w grze o macierzy wypªat postaci
0 2 B V =@ 2 0
2 0 1
1
0 1C A: 1
Je±li tak, to podaj warto±¢ tej gry, je±li nie, jej oszacowanie. 4. Znajd¹ rozwi¡zania gier o nast¦puj¡cych macierzach wypªat:
A=
4 0 6 2
4 2
0 a E=B @0 0
0 2 14 1 B C C H = BB@ 28 100 C A; 10
8
0 1 0 2 1 0 5 6 3 2 ; B=B C B @ 2 0 3 A; C = @ 7 5 3 1 1 3 3 8 8 1 0 1 0 a aC 3 2 7 1 a a A ; a 6= 0; F = B@ 8 4 0 CA ; G = B@ 0 0 a 1 6 5 0 02 3 3 31 02 3 1 41 BB 3 2 3 3 CC B 6 4 1 5 CC I =B B C ; K = B@ 3 3 2 3 CA ; @4 3 3 2A !
2
3 2
4
3 3 3 0
5. Wiedz¡c, »e x = 21 ; 0; 0; 21 jest strategi¡ optymaln¡ I gracza oraz y = jest strategi¡ optymaln¡ II gracza w grze o macierzy wypªat
1
0
6 0 C B 7 A; D = @ 1 5 3
1
3 2 0
1
2 0C A 1
0 0 2 0C A; 0 3
0 BB B L = BB B@
1
4 4 0 5 3
3 4 1 2 2
;4 u; w ; u; w > 0;
2 4 3 7 2
4 2 2 2 2
1 CC CC CC A
0a B C = BB@ 15
1 b1 5 0C CC ; 1 0A 4 4 1 znajd¹ warto±ci parametrów a; b; u; w oraz warto±¢ gry.
Wst¦p do teorii gier Lista zada« nr 4
1. Dla rozwa»anej na wykªadzie gry wej±cia wylicz pozostaªe elementy macierzy wypªat. 2. Przyjmuj¡c w powy»szej grze p = 2=3 poka», »e macierz wypªat jest postaci
!
(0; 2) (0; 2) (0; 2) (0; 2) : (1; 1) (4=3; 4=3) ( 1=3; 1=3) ( 1; 0) Sprawd¹, »e w zbiorach strategii czystych X = fO; E g oraz Y = fAA; AF; FA; FF g; odpowiednio, gra ma punkty RN postaci: (O; FA), (O; FF ) oraz (E; AF ): 3. Korzystaj¡c z drzewa gry "game of chicken" omawianej na wykªadzie wyznacz macierz wypªat, a potem przyjmuj¡c R = 8; H = 16; L = 0; czyli dla macierzy postaci
0 (0; 0) (0; 4) B (4; 0) ( 1; 1) B B @ (4; 0) (3; 1) (8; 0) (2; 6)
(0; 4) (0; 8) ( 1; 3) ( 6; 2) (3; 3) (2; 2) (2; 2) ( 4; 4)
1 CC CA
wszystkie punkty RN. 4. Wyznacz punkty RN dla dwuosobowej gry z niepeªn¡ informacj¡ okre±lonej przez zbiory typów graczy 1 = ftg; 2 = ft1 ; t2g; zbiory akcji A1 = fa; bg; A2 = fc; dg; przekonania graczy: 1(t1 jt) = 0:6; 2(tjti ) = 1; i = 1; 2 macierze wypªat w zale»no±ci od poszczególnych typów II gracza, tzn. dla t1; t2 , odpowiednio: ! ! (1; 2) (0; 1) ; (1; 3) (0; 4) : (0; 4) (1; 3) (0; 1) (1; 2) 5. Znajd¹ rozwi¡zanie przetargowe Nasha dla gry o macierzy wypªat postaci:
!
(2; 6) (10; 5) ; (4; 8) (0; 0) przyjmuj¡c za wspóªrz¦dne punktu SQ poziomy bezpiecze«stwa ka»dego z graczy. 6. Przypu±¢my, »e dwaj gracze maj¡ w wyniku negocjacji wybra¢ jeden z wyników: a) A(0; 0); B (2; 0); C (4; 2); D(1; 5), b) A(1; 8); B (6; 7); C (8; 6); D(9; 5); E (10; 3); F (11; 1); G( 1; 1) b¡d¹ pewien rozkªad probabilistyczny na nich. W obu przypadkach, je±li nie dojd¡ do porozumienia, maj¡ zagwarantowane wypªaty (2,1). Wyznacz dla obu zagadnie« rozwi¡zanie przetargowe Nasha. 7. Dla ka»dej z poni»szych macierzy wypªat porównaj rozwi¡zania przetargowe Nasha dla punktów SQ b¦d¡cych poziomami bezpiecze« stwa z rozwi¡zaniami dla punktów SQ odpowiadaj¡cych strategiom gró¹b:
!
!
!
; 12) (10; 10) ; N = (2; 7) (7; 2) ; P = (0; 10) (10; 0) : M = (2 (4; 16) (0; 0) (0; 1) (1; 0) (0; 10) ( 10; 0)
Wst¦p do teorii gier Lista zada« nr 5
1. Dla rozwa»anych na wykªadzie gier w przykªadach: 2.4. oraz 2.5. poka», »e jakakolwiek kolejno±¢ wyboru strategii przez poszczególnych graczy nie zmieni rezultatu gry uzyskanego w wyniku jednoczesnego podejmowania decyzji przez graczy. 2. Nawi¡zuj¡c ponownie do gier omawianych na wykªadzie uzasadnij, »e gracz I mo»e uwiarygodni¢ swoje posuni¦cia strategiczne (obietnice, gro¹by) obni»aj¡c swoj¡ wypªat¦: a) za strategi¦ Ba z 5 do 2 w grze z przykªadu 2.5.; b) za strategi¦ Ab z 1 do -1 oraz za Ba z 4 do 2 w grze z przykªadu 2.6. 3. Wyniki w poni»szych grach nie pozwalaj¡ osi¡gn¡¢ I graczowi jego maksymalnej wypªaty. Dla ka»dej z nich sprawd¹, czy gracz I mo»e zyska¢ wykonuj¡c co najmniej jedno z nast¦puj¡cych posuni¦¢ strategicznych: a) zagwarantowa¢ sobie pierwszy ruch, b) zmusi¢ do wykonania pierwszego ruchu gracza II, c) sformuªowa¢ gro¹b¦, d) sformuªowa¢ obietnic¦, e) sformuªowa¢ obietnic¦ i gro¹b¦. W jaki sposób gracz I mo»e uwiarygodni¢ swoj¡ deklaracj¦?
!
!
!
; 4) (4; 3) ; N = (3; 4) (4; 2) ; P = (2; 4) (3; 3) ; M = (3 (1; 2) (4; 1) (2; 3) (1; 1) (2; 2) (1; 1) !
!
; 2) (4; 1) ; S = (3; 2) (1; 1) : Q = (2 (2; 4) (4; 3) (1; 3) (3; 4) 4. Podaj przykªad gry maj¡cej rozwi¡zanie w ±cisªym sensie, niewra»liwej ani na uzgodnienia kolejno±ci ruchów graczy, ani na gro¹by, ani na obietnice. 5. Rozwa»my gr¦, w której stronami s¡: porywacz i wzi¦ty przez niego zakªadnik. Porywacz mo»e zabi¢ zakªadnika b¡d¹ go uwolni¢, zakªadnik mo»e zapªaci¢ okup b¡d¹ nie, a w razie uwolnienia zgªosi¢ porawnie policji b¡d¹ nie. Wypªaty dla porywacza wynosz¡ kolejno: 5, gdy dostanie okup, 2, gdy porwanie zostanie zgªoszone oraz 1, gdy zabije zakªadnika. Wypªaty zakªadnika to, odpowiednio: -10, gdy zostanie zabity, 2, gdy zapªaci okup oraz 1, gdy zgªosi porwanie policji. Zakªadamy, »e wypªaty ka»dego gracza dodaj¡ si¦, tzn. gdy, na przykªad porywacz dostanie okup, ale porwanie zostanie zgªoszone, to jego wypªata wynosi 5 2 = 3: a) Utwórz drzewo gry oraz macierz wypªat; b) wyznacz punkty RN; c) przyjmuj¡c, »e zakªadnik jest w stanie przekona¢ porywacza obietnic¡ lub gro¹b¡, zaproponuj jej sformuªowanie i wyznacz nowe rozwi¡znie gry; d) wykonaj podpunkt c) w odniesieniu do porywacza.
Wst¦p do teorii gier Lista zada« nr 6
1. W nawi¡zaniu do rozwa»anej na wykªadzie gry w przykªadzie 2:7 rozwa» dwie mo»liwe pozostaªe koalicje, wyznacz ich warto±ci, strategie optymalne graczy tworz¡cych koalicje oraz graj¡cych samodzielnie. 2. Korzystaj¡c z wyników poprzedniego zadania wyznacz oczekiwane wypªaty poszczególnych graczy. Czy na ich podstawie mo»emy przewidywa¢, jakie powstan¡ koalicje? 3. Dwie poni»sze macierze odpowiadaj¡ wypªatom w grze trzyosobowej dla strategii czystych oraz III gracza, odpowiednio:
!
(4; 3; 3) (1; 2; 7) (3; 5; 2) (0; 4; 6) ;
!
(3; 6; 1) (2; 5; 3) : (2; 7; 1) (1; 6; 3)
a) Wyznacz dla tej gry o staªej sumie punkty RN (wykorzystuj¡c diagram ruchu oraz ewentualne dominacje); b) uªó» i rozwi¡» gr¦ odpowiadaj¡c¡ sytuacji, gdy powstaje koalicja II i III gracza przeciwko I graczowi oraz wyznacz oczekiwane wypªaty poszczególnych graczy; c) to samo dla dwóch pozostaªych koalicji; d) wyznacz najbardziej po»¡danego partnera koalicyjnego ka»dego z graczy; e) wyznacz funkcj¦ charakterystyczn¡ gry dla sytuacji, gdy dopuszczamy wypªaty uboczne. 4. Skonstruuj gr¦ w postaci funkcji charakterystycznej modeluj¡c¡ nast¦puj¡c¡ sytuacj¦: A. jest przewodnicz¡cym komisji, w skªad której wchodz¡ tak»e B., C. oraz D. Komisja podejmuje decyzje poprzez gªosowanie wi¦kszo±ciowe, w przypadku równego rozkªadu gªosów decyduje gªos przewodnicz¡cego. 5. Wyznacz normalizacj¦ wzgl¦dem 0 1 gry:
v(;) = 0; v(I ) = 1; v(II ) = 2; v(III ) = 3; v(fI; II g) = 5; v(fI; III g) = 7; v(fII; III g) = 9; v(fI; II; III g) = 12: 6. Dla gry w postaci funkcji charakterystycznej
v(;) = v(I ) = v(II ) = v(III ) = 0; v(fI; II g) = 5; v(fII; III g) = 3; v(fI; III g) = 2; v(fI; II; III g) = 6 zaznacz na trójk¡cie imputacji rdze«. Które imputacje wyznaczaj¡ jego wierzchoªki? 7. Wyznacz dla rozwa»anej na wykªadzie gry satelitów komunikacyjnych normalizacj¦ wzgl¦dem 0 1 i poka», »e rdze« jest pusty. 8. Wyznacz warto±¢ Shapleya dla a) gry satelitów komunikacyjnych; b) gry opisanej w zadaniu 4. Czy nale»y ona do rdzenia?
