Teoria Gier - Przemysław Juszczuk

Transcript

Teoria gier dr Przemysław Juszczuk Instytut Informatyki Uniwersytetu Śląskiego Wykład 2 - Gry o sumie zero dr Przemysław Juszczuk Teoria gier Gry o sumie zero Dwuosobowe gry o sumie zero (ogólniej: o sumie stałej) były pierwszym typem gier dla których podjęto próby ich rozwiązania. często określane są też jako ściśle konkurencyjne, gdzie interesy graczy są przeciwstawne. u1 (a) = −u2 (a), a ∈ A Teoria gier Gry o sumie zerowej były podstawą matematycznej teorii gier opracowanej przez J. von Neumanna i O Morgensterna dr Przemysław Juszczuk Teoria gier Jeden z pionierów informatyki; Twórca teorii gier oraz teorii automatów komórkowych; Istotny wkład w dziedzinach; logika matematyczna, teoria mnogości, analiza matematyczna, mechaniki kwantowej; udowodnił twierdzenie min-max; Rysunek : John von Neumann dr Przemysław Juszczuk Teoria gier Wspólnie z von Neumannem stworzył podstawy teorii gier; Istotny wkład w dziedzinie ekonomii; Rysunek : Oskar Morgenstern dr Przemysław Juszczuk Teoria gier Przykłady gier o sumie zero: Szachy; Warcaby; GO; gry karciane; Kamień-Papier-Nożyczki; Orzeł-Reszka; Należy pamiętać, że gry w postaci ekstensywnej takie jak szachy czy warcaby, mogą zostać przedstawione jako gra w postaci macierzowej. dr Przemysław Juszczuk Teoria gier Rysunek : Gra o sumie zero dr Przemysław Juszczuk Teoria gier W grze o sumie zero: Gry o sumie zero każdy z graczy posiada skończoną liczbę strategii; strategie poszczególnych graczy wybierane są jednocześnie; przy wyborze strategii gracz może za każdym razem wybierać tylko jedną strategię - w takiej sytuacji jest to strategia czysta; profil strategii czystych, to sytuacja, w której gracze wybrali jedną ze swoich strategii czystych: s = (xn , ym ), gdzie xn ∈ X oraz ym ∈ Y . xn oraz ym oznaczają odpowiednio n-tą oraz m-tą strategię czystą graczy. dr Przemysław Juszczuk Teoria gier Jeszcze o grach w postaci normalnej W postaci normalnej da się zapisać tylko proste gry, gdzie ilość możliwych strategii poszczególnych graczy jest niezbyt duża. Jest to postać bardzo czytelna, w której widać wyraźnie jaki będzie wynik gry przy wyborze określonych strategii poprzez graczy. Dla gier w postaci normalnej nie ma podanej historii rozgrywki - gry jednoetapowe; dr Przemysław Juszczuk Teoria gier W przeciwieństwie do strategii czystej, strategia mieszana określa częstotliwość wyboru danej strategii czystej w n kolejnych grach. Rysunek : Gra o sumie zero Wartości obok wierszy gracza niebieskiego oraz wartości pod kolumnami gracza czerwonego oznaczają częstości wyboru poszczególnych strategii. W tym wypadku strategię mieszaną można odczytać następująco: na każde 12 gier, 5 razy stosuj strategię pierwszą, natomiast pozostałe 7 razy strategię drugą. dr Przemysław Juszczuk Teoria gier Twierdzenie o minmaksie Dla każdej 2-osobowej skończonej gry o sumie zero: 1 Istnieje v ∗ taka, że v1 = v2 = v ∗ , gdzie v1 oznacza maksimum z minimów dla wierszy, natomiast v2 to minimum z maksimów kolumn; 2 Jeżeli s = (xn , ym ) jest punktem siodłowym to wypłata graczy stosujących strategie xn orazym wynosi v ∗ ; 3 s = (xn , ym ) jest punktem siodłowym, gdy pierwszy z graczy gra strategię maksminową, natomist gracz drugi - minmaksową. dr Przemysław Juszczuk Teoria gier Rysunek : Przykład wyznaczania punktu siodłowego Wiersze : Maksimum z minimów : max z {4, 1} Kolumny : Minimum z maksimów : min z {7, 4} Siodło istnieje, jeżeli : max min = min max dr Przemysław Juszczuk Teoria gier Procedura wyznaczania strategii w grze 2x2 1 2 3 4 5 6 Czy gra ma punkt siodłowy? Jeżeli gra nie ma punktu siodłowego, to przechodzimy dalej: Dla czerwonego: odejmujemy od liczb z 1 wierwsza wartości z 2 wiersza. Wyniki zapisujemy w dwóch nowych kratkach poniżej. Częstotliwość stosowania strategii 1 jest w kratce 2 (i na odwrót) Próbujemy skrócić wartości w obydwu kratkach. Uwaga Metoda stosowana do wyznaczania strategii mieszanych daje często błędne wyniki, jeżeli okaże się, że gra ma punkt siodłowy. dr Przemysław Juszczuk Teoria gier Rysunek : Obliczanie strategii mieszanych w grze 2x2 dr Przemysław Juszczuk Teoria gier Rysunek : Przykład wyznaczania punktu siodłowego Rysunek : Przykład wyznaczania strategii bez punktu siodłowego dr Przemysław Juszczuk Teoria gier Rysunek : Dodanie stałej do komórek macierzy Dodanie określonej stałej c do każdej z komórek macierzy wypłat nie wpływa w żaden sposób na częstość wyboru strategii poszczególnych graczy. Uwaga Dodanie stałej do wybranej gry wpływa na koszt gry. dr Przemysław Juszczuk Teoria gier Rysunek : Istnienie punktów siodłowych w grach 2xm dr Przemysław Juszczuk Teoria gier Rysunek : Dominowanie strategii w grach 2xm - istnienie strategii zdominowanych dr Przemysław Juszczuk Teoria gier Rysunek : Dominowanie strategii w grach mx2 - istnienie strategii dominujących dr Przemysław Juszczuk Teoria gier Rysunek : Graficzna metoda rozwiązywania gier dr Przemysław Juszczuk Teoria gier Rysunek : Graficzna metoda rozwiązywania gier poprzedzona usuwaniem strategii zdominowanych dr Przemysław Juszczuk Teoria gier Rysunek : Graficzna metoda rozwiązywania gier 2xm dr Przemysław Juszczuk Teoria gier Rysunek : Punkt siodłowy w grze 3x3 dr Przemysław Juszczuk Teoria gier Koszt gry w grze z punktem siodłowym koszt gry to wartość w punkcie siodłowym; po dodaniu wartości stałej w grze z punktem siodłowym - koszt gry to również wartość w punkcie siodłowym; w pozostałych sytuacjach koszt gry, to średnia wypłata, którą gracz otrzymuje w rezultacje zastosowania strategii optymalnej. dr Przemysław Juszczuk Teoria gier Rysunek : Koszt gry Załóżmy, iż gracz 2 stosuje strategię: 3 : 5 : 5 : 2. Wtedy jego wypłatę przeciwko 1 strategii czystej gracza 1 możemy obliczyć następująco: 30 F (X : x1 ) = 3·2+5·1+3·2+2·4 = 15 , 3+5+5+2 dr Przemysław Juszczuk Teoria gier Analogicznie dla pozostałych strategii: przeciwko drugiej strategii I : F (X : x2 ) = 3·3+5·2+5·3+2·2 3+5+5+2 = 38 15 , 3·1+5·5+5·4+2·2 3+5+5+2 = 52 15 , 3·4+5·4+5·1+2·2 3+5+5+2 = 41 15 , przeciwko trzeciej strategii I : F (X : x3 ) = przeciwko czwartej strategii I : F (X : x4 ) = dr Przemysław Juszczuk Teoria gier Natomiast, gdzy gracz 2 stosuje strategię optymalną 8 : 3 : 7 : 9 przciwko strategii 1: F (X : x1 ) = 8·2+3·1+7·2+9·4 8+3+7+9 = 69 27 , 8·3+3·2+7·3+9·2 8+3+7+9 = 69 27 , 8·1+3·5+7·4+9·2 8+3+7+9 = 69 27 , 8·4+3·4+7·1+9·2 8+3+7+9 = 69 27 , przciwko strategii 2: F (X : x2 ) = przciwko strategii 3: F (X : x3 ) = przciwko strategii 4: F (X : x4 ) = dr Przemysław Juszczuk Teoria gier Ogólne zasady postępowania: 1 Czy istnieje punkt siodłowy? 2 Czy można usunąć strategie zdominowane oraz dominujące? 3 Wyznacz częstości stosowania strategii poszczególnych graczy. 4 Wybierz losowo po 2 strategie graczy sprowadzając problem do gry 2x2. 5 W przypadku dużych gier zastosuj rozwiązanie przybliżone. dr Przemysław Juszczuk Teoria gier Rysunek : Gry 3x3 dr Przemysław Juszczuk Teoria gier Rysunek : Gry 3x3 dr Przemysław Juszczuk Teoria gier Rysunek : Gry 3x3 dr Przemysław Juszczuk Teoria gier Rysunek : Gry 3x3 dr Przemysław Juszczuk Teoria gier Rysunek : Gry 3x3 dr Przemysław Juszczuk Teoria gier Rysunek : Gry 3x3 dr Przemysław Juszczuk Teoria gier Rysunek : Gry 3x3 dr Przemysław Juszczuk Teoria gier Rysunek : Gry 3x3 dr Przemysław Juszczuk Teoria gier dr Przemysław Juszczuk Teoria gier Rysunek : Algorytm przybliżony - krok 1 dr Przemysław Juszczuk Teoria gier Rysunek : Algorytm przybliżony - po 6 kroku dr Przemysław Juszczuk Teoria gier Rysunek : Algorytm przybliżony - po 14 krokach dr Przemysław Juszczuk Teoria gier Dziękuję za uwagę. dr Przemysław Juszczuk Teoria gier