Design a site like this with WordPress.com
Rozpocznij

Gry niekooperacyjne: gry dwuosobowe: gry o sumie niestałej: równowaga Nasha: strategie czyste

Równowaga Nasha to taki punkt gry, w którym strategia każdego gracza maksymalizuje jego wypłatę, jeżeli strategie pozostałych graczy nie zmieniają się [1]. Jest to najlepsza odpowiedź każdego gracza na wybór pozostałych [2].

Chociaż omawiany już dylemat więźnia standardowo prezentuje się jako wstęp do równowagi Nasha, to – jak zwróciłem uwagę w poprzednim wpisie – jest to trochę na wyrost, bo ów dylemat daje się rozwiązać zwyczajnie przy pomocy strategii dominującej. W dylemacie więźnia istniała jedna strategia dominująca i jedna zdominowana dla każdego gracza, dlatego wystarczyło odrzucić zdominowaną, aby znaleźć rozwiązanie. To nie jest istota tej równowagi. Aby zrozumieć jej istotę, pokażę gry bez strategii dominujących.

Przykład 1.

Gra jest niesymetryczna, tzn. gracze mogą się różnić wypłatami i nie być w żaden sposób kompensowani innym wyborem. Gracz 1 rozumuje następująco: jeżeli Gracz 2 wybierze A, to muszę wybrać C i dostanę 3. Jednak Gracz 2 wiedząc o tym co zrobię, zmieni decyzję i wybierze C, aby zwiększyć wypłatę z 3 do 5. Wtedy ja widząc to, zmienię strategię na A, bo dostanę 10 zamiast 2. Pozornie Gracz 2 może być zadowolony, bo dostanie nawet więcej niż gdybym wybrał C – dostanie 6 zamiast 5. Jednak pozostać przy C nie będzie dla niego racjonalne, bo przecież gdyby wybrał znowu A, dostałby 10… i powróciliśmy do punktu wyjścia. Czyli tą drogą nie dostaliśmy rozwiązania, tylko kręcimy się w kółko. To była jednak próba przy początkowym założeniu, że Gracz 2 wybiera A. Powiedzmy więc teraz, że wybiera on B. Jako Gracz 1 też wybiorę B, ponieważ 4 jest największą dla mnie wartością w kolumnie B. Gracz 2 wiedząc to, porównuje strategie A, B i C i widzi, że B nadal jest najlepsza dla niego w wierszu B. Wobec tego nie będzie chciał z niej wychodzić. W ten sposób znaleźliśmy równowagę Nasha: jest to przecięcie {B, B}, czyli punkt {4, 4}:

Pytanie, czy skoro znaleźliśmy punkt równowagi, to czy rozwiązaliśmy grę? Nie do końca. Nie jest wcale powiedziane, że istnieje tylko jeden punkt równowagi. Na szczęście nie dotyczy to tej gry, ale generalnie nie możemy być pewni jednego rozwiązania. Musimy sprawdzić wszystkie przypadki początkowego wyboru Graczy. Szybko zauważymy, że ostatni przypadek, tzn. gdy Gracz 2 zaczyna od wyboru C został już sprawdzony pośrednio, gdy zaczynał od A (wykonaliśmy pętlę). Stąd wiemy na 100%, że rozwiązanie to jeden punkt {B, B}.

Zwróćmy uwagę na dwie rzeczy. Po pierwsze, tak jak w dylemacie więźnia, równowaga nie jest optymalna w sensie Pareto: obaj mogliby uzyskać lepszy rezultat wybierając punkt {10 ; 6}. Tylko że optimum Pareto zakłada, że gracze mogą się porozumiewać. A nie mogą. Po drugie w tej grze nie ma w ogóle strategii dominującej ani zdominowanej, co pozwala uchwycić ideę równowagi Nasha.

Przykład 2.

Gracz 1 rozumuje następująco: jeżeli Gracz 2 wybiera A, to wybieram B albo C (dostanę w obu przypadkach 3). Rozbijam więc problem na dwie części:

1) jeżeli wybieram B, to Gracz 2 wybierze B, aby dostać 4. Wtedy ja też dostanę 4. Ale mogę też z tej pozycji wybrać C, aby także dostać 4. Znowu więc muszę rozbić pod-problem na 2 części:

  • a) Wybieram B. Wtedy Gracz 2 nie zmieni już pozycji (osiągamy równowagę).
  • b) Wybieram C. Wtedy Gracz 2 wybierze C. Wtedy ja wybiorę A. Wtedy on wybierze A. Wtedy ja wybiorę B lub C. I wracamy do punktu wyjścia.

W tym pod-problemie wybieram więc B (tylko tu istnieje równowaga).

2) jeżeli wybieram C, to dostajemy powtórkę tego co w (1b) -> wracamy do punktu wyjścia.

Jednak jesteśmy dopiero na początku – wszystko było przy założeniu, że Gracz 2 początkowo wybiera A, chociaż widzieliśmy, że i tak zmieni strategię na B. Pozostałe natomiast pod-problemy pośrednio rozwiązały inne możliwe początkowe założenia. Równowaga ustali się więc znów w punkcie {4, 4}, tj. gracze wybierają {B, B}.

Przykład 3.

Podobny przykład, jak dwa poprzednie, ale ta gra nie posiada równowagi Nasha. Cokolwiek Gracz 2 początkowo wybierze, wybór Gracza 1 skłoni go do zmiany decyzji. I na odwrót. Gracze wpadną w pętlę bez punktu stałego.

Przykład 4.

Mężczyzna (M) i kobieta (K) chcą wyjść razem, albo na mecz piłkarski, albo na przedstawienie baletowe. Zapomnieli uzgodnić, gdzie pójdą tego wieczoru, są w różnych miejscach i muszą sami zdecydować, gdzie pójdą; nie mają możliwości porozumiewania się. Mężczyzna preferuje piłkę nożną, a kobieta balet. Poza tym woleliby bawić się razem niż samotnie. Co powinni zrobić?

Jeśli K wybierze piłkę, to M powinien wybrać piłkę (dostanie 2), a jeśli K wybierze balet, to M powinien również wybrać balet (dostanie 1). W pozostałych przypadkach dostanie 0, ponieważ M musiałby spędzić wieczór samotnie. Ponieważ gra jest symetryczna, analogicznie sytuacja wygląda dla K. Łatwo zauważyć, że w tej grze nie ma jednego rozwiązania. Z punktu widzenia M najlepiej byłoby iść na football, ale z punktu widzenia K na balet. W sumie mamy tu dwie równowagi Nasha w strategiach czystych:

Tę grę można rozwiązać jednoznacznie za pomocą strategii mieszanej, ale ten temat będzie omówiony później.

Literatura:

[1] Nash, J., Non-Cooperative Games, Annals of Mathematics, Second Series, Vol. 54, No. 2 (Sep., 1951), s. 287.

[2] Peters, H. (2015), Game Theory—A Multi-Leveled Approach, Springer-Verlag, Berlin, s. 7.

Reklama

Gry niekooperacyjne: gry dwuosobowe: gry o sumie niestałej: strategie czyste: dylemat więźnia

Ledwo minęło 5 lat od napisania Theory of Games and Economic Behavior przez von Neumanna i Morgensterna (N-M), gdy John Nash [2] pokazał swoje rozwiązanie problemu w grach niekooperacyjnych o sumie niezerowej (niestałej). U N-M zarówno gra niekooperacyjna, jak i kooperacyjna była de facto grą o sumie stałej. Jak opisałem w poprzednim artykule, zaproponowali oni również rozwiązanie gry o sumie niestałej wykorzystując ideę gracza fikcyjnego, ale nawet ten pomysł zakładał, że gracze prawdziwi mogą ze sobą kooperować, a wiadomo, że nie zawsze jest to możliwe. To co jest niezwykle istotne to fakt, że Nash uogólnił rozwiązanie gry o sumie stałej (u N-M w postaci maximin), rozszerzając pojęcie równowagi. W strategiach czystych punkt siodłowy powstawał, gdy gracze minimalizowali straty lub maksymalizowali minimalne zyski, co wiązało się z założeniem, że przeciwnik wybierze najlepszy możliwy ruch. Zysk jednego był zawsze stratą drugiego i dlatego gracze byli jakby zależni od siebie nawzajem. Równowaga Nasha odrzuca konieczność takiej zależności.

Dylemat więźnia

Słynna opowieść o więźniach, którzy powinni podjąć paradoksalną decyzję, nie została wymyślona przez Nasha, ale przez M. Dreshera i M. Flooda w 1950 r., a następnie rozpowszechniona przez A. W. Tuckera [3]. W oryginalnym eksperymencie Dreshera i Flooda nie użyto nawet dwuwartościowej macierzy wypłat, ale dwóch obok siebie pojedynczych macierzy (jednej dla gracza 1, drugiej dla gracza 2) [1].

Dwóch więźniów jest oskarżonych o przestępstwo i są przesłuchiwani oddzielnie. Każdy więzień ma dwa wyjścia: „współpracować” z drugim więźniem (nie przyznawać się) lub zdradzić go (przyznać się). Kara za przestępstwo wynosi 1 rok więzienia, jeżeli obaj się przyznają (tj. będą zdradzać). Jeżeli jeden więzień zdradzi, a drugi nie, to pierwszy zostanie w nagrodę zwolniony z kary, a drugi posiedzi dodatkowy rok za pierwszego, czyli 2 lata. W końcu jeśli żaden z nich się nie przyzna – będą współpracować – zacznie się proces sądowy przeciw nim i szansa, że przegrają wynosi 1/2, a stąd wartość oczekiwana kary (0 – 1)/2 = -0,5. Macierz wypłat ma postać

Pierwsza liczba danej komórki to wypłata Gracza 1, druga liczba to wypłata Gracza 2. Gra jest symetryczna, więc wystarczy znaleźć rozwiązanie dla jednego, a wtedy znajdziemy od razu dla drugiego. Rozumowanie Gracza 1 jest następujące: jeżeli Gracz 2 wybierze „Współpracuj”, to jeżeli ja wybiorę „Współpracuj” dostanę -0,5, a jeżeli wybiorę „Zdradzaj”, to dostanę 0. Czyli wtedy lepiej jest zdradzić. Jeżeli Gracz 2 wybierze „Zdradzaj”, to jeżeli ja wybiorę „Współpracuj” dostanę -2, a jeżeli wybiorę „Zdradzaj”, to dostanę -1. Czyli znowu lepiej zdradzać. W sumie Gracz 1 powinien zdradzać. Ze względu na symetrię Gracz 2 będzie miał to samo rozwiązanie. Obaj będą zdradzać. To znaczy, że powstała równowaga Nasha: jest to wybór {wiersz – Zdradzaj, kolumna – Zdradzaj}.

Na czym więc polega paradoks? Gdyby obaj współpracowali, to dostaliby tylko pół roku więzienia zamiast 1 roku, czyli zmniejszyliby karę do minimum. A więc mogliby uzyskać lepszy wynik, niż wybór zgodny z równowagą Nasha. Innymi słowy równowaga Nasha nie musi być efektywna w sensie Pareta. Efektywność w sensie Pareta oznacza, że nie można poprawić sytuacji jednego bez pogorszenia sytuacji kogoś innego. Równowaga Nasha maksymalizuje wypłaty graczy warunkowo, a nie globalnie; warunkiem jest uniezależnienie się od wyboru drugiej strony. Czyli gracze nie mogą się kontaktować między sobą ani w żaden sposób nie zgadują co robi drugi – to jest powód występowania tego paradoksu.

Dylemat więźnia nie jest specjalnie odkrywczy, bo strategia zdradzania jest jedyną dominującą, a dominację wprowadzili sami N-M. Gdybyśmy zastąpili wypłatę drugiego gracza wartością przeciwną pierwszego (a więc grą o sumie zero), dostalibyśmy to samo rozwiązanie. Dlatego omówiony przykład należy bardziej traktować jako wstęp do teorii gier niekooperacyjnych niż samej równowagi Nasha.

Literatura:

[1] Flood, M.M. (1958) Some Experimental Games, Research Memorandum. RM-789, RAND Corporation,” Management Science (5)

[2] Nash, J., Non-Cooperative Games, Annals of Mathematics, Second Series, Vol. 54, No. 2 (Sep., 1951), pp. 286-295

[3] Walker, P. (1995). An outline of the history of game theory, Discussion Paper No. 9504,
Department of Economics, University of Canterbury, Christchurch, New Zealand ;

[4] von Neumann, J., Morgenstern, O., (1944), Theory of Games and Economic Behavior.
Princeton: Princeton University Press

Gry niekooperacyjne: gry dwuosobowe: gry o sumie niestałej: gracz fikcyjny

Powoli docieramy do tematu, który zrewolucjonizował myślenie o ekonomii, tzn. równowagi Nasha i gier o sumie niestałej czy niezerowej. Prace Johna Nasha całkowicie zdominowały teorie gier w nauce ekonomii i w zasadzie w niewielkim zakresie naukowcy współcześnie zajmują się jeszcze Von Neumannem i Morgensternem. Główna odpowiedź na pytanie, dlaczego tak się stało, leży w tym, że równowaga Nasha okazała się uogólnieniem maksiminu w grach o sumie stałej – rozwiązania, na którym skupili się jego poprzednicy.

Interesujące jest to, że w większości współczesnych opracowań i podręczników autorzy błędnie albo nie do końca zgodnie z prawdą nauczają, że, o ile Neumann i Morgenstern stworzyli teorie gier o sumie stałej, o tyle Nash i jego następcy zaproponowali teorie o sumie niestałej. W rzeczywistości ci pierwsi również dotknęli temat sumy niestałej, choć niewielu o tym przypomina. Wynika to z tego, że założenia jakie stoją u podłoża ich rozumowania okazały się nieprzekonujące.

Neumann i Morgenstern wpadli na pomysł, aby z n-osobowej gry o sumie stałej wyłuskać ogólną grę (n-1)-osobową, co stanie się możliwe, jeśli do gry wprowadzimy fikcyjnego gracza, który traci pewną wartość na korzyść pozostałych. Fikcyjny gracz jest jedynie konstrukcją teoretyczną, nie mającą bezpośredniego wpływu na przebieg gry. To oznacza, że on sam nie ma możliwości wyboru, który przekładałby się na sytuację pozostałych graczy. Jednak miałby on wpływ pośredni na nich. W jaki sposób? Żeby to wyjaśnić trzeba się odwołać do innego założenia Neumanna-Morgensterna, a mianowicie, że gdy w grze bierze udział co najmniej trzech graczy, może powstać koalicja dwóch przeciw trzeciemu. Taka koalicja miałaby zachodzić oczywiście wtedy, gdyby się graczom opłacała; gdyby się nie opłacała, wtedy graliby wszyscy przeciw sobie. Wchodzimy więc w obszar gier kooperacyjnych, czego jednak chcemy uniknąć, ale widzimy teraz, że podział na gry niekooperacyjne i kooperacyjne może być sztuczne. Nasi pionierzy rzeczywiście nie rozdzielali w ten sposób gier, a ten podział zaproponował dopiero Nash [2]. Ponieważ nie wchodzę tutaj szczegółowo w gry kooperacyjne, nie będę też zagłębiał się w pomysł Neumanna-Morgensterna, a jedynie zarysuję go. Tak więc w grze 3-osobowej z fikcyjnym graczem, prawdziwi gracze podejmują decyzję czy wejść w koalicję z którymś z pozostałych. Gracz fikcyjny nie gra z nimi, ale oferuje im pewną zapłatę w zamian za to, że powstrzymają się od kooperacji między sobą. Gracze prawdziwi podejmują zatem decyzję, czy kooperują ze sobą czy konkurują. Konkurowanie implikuje automatycznie kooperację z graczem fikcyjnym i gracz fikcyjny zapłaci im za to, że będą właśnie z nim kooperować, a nie ze sobą. Ale ponieważ gracz fikcyjny istnieje jedynie w głowach graczy, to znaczy, że jeśli wybiorą konkurowanie, to otrzymamy grę niekooperacyjną o sumie niezerowej / niestałej.

Spójrzmy na taką grę 3-osobową:

Pierwsza wartość każdej komórki (wypłata) przynależy do gracza A, druga wartość do B, trzecia do C. Sumarycznie wartość każdej komórki równa się zero. Stało się to możliwe dzięki dodaniu gracza fikcyjnego, czyli gracza C. którego wypłata wyrównuje wypłaty pozostałych do zera. Skoro gracz C jest graczem fikcyjnym, on sam nie ma żadnego wyboru strategii. Dostanie to, co mu niejako przyniosą ruchy A i B. Gdyby miał wybór strategii, to na jego osi pojawiłby się dodatkowy wybór (w trzecim wymiarze).

Jeżeli A i B podejmą decyzję, że wejdą ze sobą w koalicję, to otrzymają po 1/2, ale wtedy C straci 1. Jeżeli zdecydują, że zostaną konkurentami, to stracą po 1/2, ale C dostanie wypłatę równą 1.

Gdyby rozpatrywać grę tylko przez pryzmat dwóch realnych graczy, to wydaje się oczywiste, że obaj powinni wybrać koalicję:

Gracz C powoduje pewne zamieszanie, które należałoby przeanalizować. Pewne jest, że interpretacja tej postaci ma znaczenie dla rozwiązania. Wprowadzenie jej służyło tylko do uzasadnienia rozwiązania maximinowego, którego w grze o sumie niestałej nie można zastosować. Ale zwróćmy uwagę, że to nawet nie dotyczy powyższego przykładu – maximin jest tu zbędny, bo rozwiązanie (1/2, 1/2) dominuje nad każdym innym. W bardziej skomplikowanych przypadkach trzeba by użyć maksiminu, ale nie będziemy się tym teraz zajmować. 3-osobowa gra nas jeszcze nie interesuje.

Główne zastrzeżenie do zaproponowanego rozwiązania dotyczy założenia, że sztuczne wprowadzenie fikcyjnego gracza umożliwia prawdziwym graczom utworzenie realnej koalicji. Nawet prawdziwy trzeci gracz nie implikuje automatycznie takiej możliwości. Poza tym, Schmidt [3] spostrzegł, że nie można zagwarantować, że rekompensata zysków i strat, za które fikcyjny gracz jest fikcyjnie odpowiedzialny, nie będzie miała wpływu na przebieg gry.

Mimo tych wątpliwości sam pomysł fikcyjnego gracza jest bardzo ciekawy. Można go interpretować jako Naturę [1], która jest tak samo obserwowana przez drugą stronę i stąd nawet bez kontaktu między sobą, można przewidywać jej dobrostan (działanie na jej korzyść lub niekorzyść).

Literatura:

[1] McClennen, E. F., Rational Cooperation on Rules, 2000

[2] Nash, J., Non-Cooperative Games, Annals of Mathematics, Second Series, Vol. 54, No. 2 (Sep., 1951), pp. 286-295

[3] Schmidt, , C., Game Theory and Economic Analysis, 2002

[4] von Neumann, J., Morgenstern, O., (1944), Theory of Games and Economic Behavior.
Princeton: Princeton University Press

Gry niekooperacyjne: gry dwuosobowe: gry o sumie stałej: strategie mieszane

Kontynuujemy grę o stałej sumie. Powiedzmy, że mamy dwa państwa, które prowadzą wojnę. Zniszczenie maszyny lub zabicie żołnierza jednej strony to strata tej strony równa zyskowi drugiej strony. Jest to typowy przykład gry o sumie stałej równej zero. Powiedzmy, że dodatkowo nad oboma krajami wystąpi huragan. Sumarycznie więc gra będzie mieć ujemną sumę wypłat niezależnie od wygranej. Powiedzmy, że kraj A się broni, a kraj B atakuje. Kraje muszą wybrać, gdzie skoncentrować wojska: na północy, wschodzie czy zachodzie. Mamy macierz wypłat:

Jak widać suma wypłat jest w każdym scenariuszu stała i wynosi -2. Spróbujmy rozwiązać zadanie za pomocą maximin:

W nawiasach podano prawdopodobieństwa zdarzeń dla danego kraju. Kraj A, który się broni, ma łatwiej, ponieważ wie, że najlepiej wysłać wojska na północ. Dzieje się tak, ponieważ od północy szybciej przesunie wojska na wschód lub zachód, w razie gdyby B stamtąd zaatakował. Z kolei jeśli B zaatakuje z północy, to A wygra. Jasne więc, że A wybierze północ, stąd maximin równa się -2.

Kraj B nie posiada maximin, ale wie, że A wybiera północ. Wobec tego B ma do wyboru atak ze wschodu lub atak z zachodu. Skoro dla obydwu wariantów dostaje tyle samo (zero), to znaczy, że wybiera strategię mieszaną, z takim samym prawdopodobieństwem, tj. 1/2.

Pokażmy to ściślej. Wiemy, że A wybiera zawsze północ. Wypłata dla A zależy jednak od wyboru B, który wybiera P – północ, W – wschód albo Z – zachód. Całkowita wartość oczekiwana A wynosi:

E(A) = q1*P + q2*W + (1-q1-q2)*Z

Wiemy, że B nie wybiera P, czyli q1 = 0:

E(A) = q2*W + (1-q2)*Z

Skoro A wybiera zawsze północ, to możemy podstawić wartości do W i Z:

E(A) = q2*(-2) + (1-q2)*(-2) = -2*q2 + 2*q2 + 1 = 1

Wartość oczekiwana A wynosi 1. Jak jednak znaleźć q2? Musimy wartość oczekiwaną podzielić na warunkowe wartości oczekiwane. Pierwsza – wartość oczekiwana pod warunkiem, że B wybiera W:

E(A | B(W)) = -2*q2.

Druga, że że B wybiera Z:

E(A | B(Z)) = -2*(1-q2) = -2 + 2*q2

Punkt maximin wyznacza punkt przecięcia obu funkcji:

-2*q2 = -2 + 2*q2

q2 = 1/2.

Rozwiązanie wynosi q2 = 1/2 oraz 1-q2-q3 = 1/2, tak jak wcześniej intuicyjnie do tego doszliśmy. Kraj B powinien zatem atakować ze wschodu lub zachodu z prawdopodobieństwem 0,5.

Gry niekooperacyjne: gry dwuosobowe: gry o sumie stałej: strategie czyste

Powoli dochodzimy do gier bardziej ogólnych, już nie wymagających, aby zysk jednej strony był stratą drugiej. Pośrednią formą są gry o sumie stałej – suma wypłat w każdym scenariuszu jest zawsze równa tyle samo. Okazuje się, że takie gry rozwiązuje się dokładnie tak samo jak gry o sumie zerowej. Po prostu gra o sumie zerowej jest szczególnym przypadkiem gry o sumie stałej. Współcześnie uznaje się wręcz, że określenie „gra o sumie zerowej” i o „sumie stałej” są synonimami. Wynika to z prostego spostrzeżenia, że dodanie tej samej wartości do każdego scenariusza powoduje, że w grze dwuosobowej każdy gracz dostaje o połowę tej wartości więcej – w każdym napotkanym scenariuszu, a więc nie zmienia się jego względne położenie. A skoro tak, to będzie grał tak samo. Jednak Morgenstern i Neumann – jako pionierzy – sporo poświecili temu zagadnieniu w swojej książce [2]. Autorzy zauważają, że taką grę można podzielić na dwie części: najpierw gracze grają w grę o sumie zerowej, a na końcu obaj dostają jeszcze „premię” o stałej wysokości niezależnie od poprzednich wyborów. Wynika z tego, że nie martwią się już o premię, która jest 100% pewna, a więc skupiają się wyłącznie na grze o sumie zerowej. Popatrzmy na taką grę:

Standardowo przedstawione scenariusze to wypłaty dla gracza A, które stanowią przeciwieństwo wypłat dla B. Gracz A stosuje maximin, a gracz B minimax:

Istnieje punkt siodłowy, więc otrzymujemy rozwiązanie w strategiach czystych: 2 dla A i -2 dla B.

Na koniec jednak dajemy każdemu premię w wysokości 5. To znaczy, że A uzyskuje w sumie 7, a B 3. Nie możemy więc zapisać punktu siodłowego jako wypłaty 7, bo to by oznaczało, że B traci 7. Musimy więc zapisać obie wartości obok siebie: 7 i 3. Ponieważ premia nie zależy od niczyjego wyboru, to należy tak zrobić w każdym scenariuszu – dodać po 5 dla A i B. Macierz wypłat przybierze postać:

Otrzymaliśmy więc postać macierzy dwuwartościowej. W każdym polu znajduje się para liczb, z których pierwsza to wypłata gracza A (zawsze po wierszach), druga liczba to wypłata gracza B (zawsze po kolumnach). Teraz ważna uwaga: aby znaleźć rozwiązania dla obu graczy, nie stosujemy dla B min-max, tylko dla obydwu max-min. W grze o sumie zerowej moglibyśmy dla B równie dobrze zastosować max-min, gdybyśmy operowali wypłatami do B, a nie do A. Zastosowanie min-max wynikało jedynie z twierdzenia Neumanna o minimaxie [1], że w grze o sumie zerowej max-min gracza A jest równy min-max gracza B, co wynikało z przeciwności wypłat. De facto w dotychczasowej analizie minimax w ogóle był zbędny. Dlaczego więc stosowaliśmy go? Wynika to z jego interpretacji: gracz B dążył do minimalizacji zysku gracza A, ale przewidując jednocześnie jego ruchy. Prowadziło go to do maksymalizacji jego własnego zysku przy tych organiczeniach. Mówiąc inaczej, Neumann i Morgenstern dali wgląd w analizę zysków (lub strat) przeciwnika. Gra Neumanna-Morgensterna charakteryzuje się więc tym, że wypłaty graczy są zawsze jakoś ze sobą powiązane.

Gdybyśmy chcieli jakby przerwać to powiązanie wypłat między graczami, to naszą początkową grę o sumie zerowej (bez premii) zapisalibyśmy w formie:

Wówczas obaj gracze szukają optimum za pomocą max-min. I tak dla A znajdujemy minimum porównując pierwszą liczbę z każdej pary danego wiersza: 2 < 3, więc 2 to min dla 1 wiersza oraz -3 < 0, więc -3 to min w 2 wierszu. Z otrzymanych wartości (2, -3) obliczamy max, otrzymując 2, które stanowi maximin dla A. Analogicznie robimy dla B: po kolumnach szukamy najpierw minimum porównując drugą liczbę z każdej pary danej kolumny: po 1 kolumnie obliczamy min(-2, 3) = -2 oraz po 2 kolumnie min(-3, 0) = -3. Na koniec wyciągamy max(-2, -3) = -2. Dostajemy rozwiązanie (2, -2), czyli to samo co poprzednio w zapisie macierzy jednowartościowej. Poniższy rysunek pokazuje graficznie sposób rozwiązania:

Teraz przejdźmy do rozwiązania gry z premią. Poniższa tabelka pokazuje rozwiązanie:

Schemat więc pozostaje identyczny: 7 < 8, więc 7 to min dla 1 wiersza oraz 2 < 5, więc 2 to min w 2 wierszu. Z otrzymanych wartości (7, 2) obliczamy max, otrzymując 7. To jest maximin dla A. Dla B: po kolumnach szukamy najpierw minimum porównując drugą liczbę z każdej pary danej kolumny: po 1 kolumnie obliczamy min(3, 8) = 3 oraz po 2 kolumnie min(2, 5) = 2. Na koniec wyciągamy max(3, 2) = 3. Dostaliśmy punkt siodłowy, ponieważ gracze zgodzili się co do optymalnego rozwiązania. W ten sposób wiemy, że A wybierze 1 wiersz, a B 1 kolumnę.

Literatura:

[1] von Neumann, J. (1928) Zur théorie der gesellschaftsspiele, Math. Annalen vol. 100, 295–320, in S. Bargmann (trans.) as On the theory of games of strategy, Contributions to the Theory of Games vol. 4, A.W. Tucker and R.D.Luce (eds) Annals of Mathematics Studies 40, Princeton, NJ: Princeton University Press (1959), 13–42;

[2] von Neumann, J., Morgenstern, O., (1944), Theory of Games and Economic Behavior.
Princeton: Princeton University Press.

Gry niekooperacyjne: gry dwuosobowe: gry o sumie zerowej: strategie mieszane: mxn

Powróćmy teraz do naszej gry wojennej z przykładu 2, który rozpocząłem tutaj. Mieliśmy macierz wypłat:

Zacznijmy standardem minimaksowym:

Punkt siodłowy, czyli równowaga, nie istnieje w strategiach czystych. Oczywiście A mógłby wybrać wiersz 1, B kolumnę 1, jednak gdyby gracze to przewidywali, to mogliby poprawić swoją sytuację: A wybrałby 3 wiersz (dostałby 2 a nie 1), a wtedy B przewidując ten ruch A, wybrałby 2 kolumnę (dostałby 0 a nie -2) itd.

Znajdujemy więc rozwiązanie w strategiach mieszanych (zob. ten wpis). W nawiasach zapisuję więc prawdopodobieństwa stosowania strategii czystych. Gracz A stosuje strategie z p-wem p1, p2 i p3. Ponieważ p1 + p2 + p3 = 1, to p3 = 1 – p1 – p2. Analogicznie B stosuje strategie z p-wem q1 i q2, ale skoro q2 = 1 – q1, to wystarczy, że użyjemy q i 1-q.

Zaczynamy od gracza A. Zapiszmy jego ogólną wartość oczekiwaną:

E(A) = p1*WNZ + p2*WNW + (1-p1-p2)*PBR

gdzie: WNZ – wysłać na zachód, WNW – wysłać na wschód, PBR – pozostawić bez ruchu.

E(A) można podzielić na dwie części: gdy B wybiera atak lub gdy wybiera wycofanie się:

E(A | B atakuje) = p1*WNZ(A | B atakuje) + p2*WNW(A | B atakuje) + (1-p1-p2)*PBR(A | B atakuje)

E(A | B wycofuje się) = p1*WNZ(A | B wycofuje się) + p2*WNW(A | B wycofuje się) + (1-p1-p2)*PBR(A | B wycofuje się)

Gdy B wybiera atak, to gdy A wyśle wojska na zachód, to A dostanie 1, a gdy A wyśle na wschód, to A dostanie -1 oraz gdy A pozostanie bez ruchu, to A dostanie 2. Czyli zapiszemy:

E(A | B atakuje) = p1*1 + p2*(-1) + (1-p1-p2)*2 = = p1 – p2 + 2 – 2*p1 – 2*p2 = -p1 – 3*p2 + 2.

Z kolei gdy B wybiera wycofanie się, to gdy A wyśle wojska na zachód, to A dostanie 2, a gdy A wyśle na wschód, to A dostanie 1 oraz gdy A pozostanie bez ruchu, to A dostanie 0:

E(A | B wycofuje się) = p1*2 + p2*1 + (1-p1-p2)*0 = p1*2 + p2

Gdybyśmy szli tym samym sposobem jak w grze 2×2, to powinniśmy narysować dwa wykresy funkcji liniowych, tzn. dwie powyższe warunkowe wartości oczekiwane i sprawdzić w którym punkcie się przecinają. Problem polega na tym, wtedy była tylko jedna zmienna niezależna, p, a teraz mamy dwie zmienne niezależne, p1 i p2, co powoduje, że musielibyśmy narysować wykres trójwymiarowy. Pominiemy ten krok, ponieważ wystarczy matematyka i wyobraźnia. Otrzymamy układ:

E(A | B atakuje) = -p1 – 3*p2 + 2

E(A | B wycofuje się) = 2*p1 + p2.

Zauważmy, że p1 i p2 zachowuje się przeciwnie dla obu funkcji. Pierwsza ma nachylenie ujemne, czyli jest spada wraz ze wzrostem zmiennych. Druga ma nachylenie dodatnie, czyli rośnie wraz ze wzrostem zmiennych. Sytuacja więc już przypomina tę z gry 2×2, gdzie mieliśmy wykres dwuwymiarowy. Wtedy korzystaliśmy w kolejnym kroku z algorytmu maximin, polegającego na wyborze tej części wykresu (czyli tej funkcji), która dla danego p jest minimalna. Obecnie mamy p1 i p2, stąd musi się to odbyć w dwóch kierunkach jednocześnie. Weźmy przykład: jeśli p1 = 0 i p2 = 0, to dostaniemy odpowiednio 2 i 0. Bierzemy niższą część, czyli 0, co odpowiadałoby wycofaniu się B. Zróbmy parę takich przykładów. W nawiasie podano warunek zachowania się B:

p1 = 0 i p2 = 0 => 2 i 0 => min(2; 0) = 0 (wycofanie się B)

p1 = 1/2 i p2 = 0 => 1,5 i 1 => min(1,5; 1) = 1 (wycofanie się B)

p1 = 1 i p2 = 0 => 1 i 2 => min((1; 2) = 1 (atak B)

p1 = 0 i p2 = 1/2 => 1/2 i 1/2 => są równe

p1 = 1/2 i p2 = 1/2 => 0 i 1,5 => min(0; 1,5) = 0 (atak B)

p1 = 1 i p2 = 1/2 => -1/2 i 2,5 => min(-1/2; 2,5) = -1/2 (atak B)

p1 = 0 i p2 = 1 => -1 i 1 => min(-1; 1) = -1 (atak B)

p1 = 1/2 i p2 = 1 => -1,5 i 2 => min(-1,5; 2) = -1,5 (atak B)

p1 = 1 i p2 = 1 => -2 i 3 => min(-2; 3) = -2 (atak B).

Gdyby na podstawie tej listy chcieć w przybliżony sposób szukać maksimin, to wybralibyśmy z niej wartość maksymalną, czyli 1 (tj. max-min = 1). Byłyby jednak dwa takie rozwiązania w zależności od tego, co by wybrał gracz B. Gdyby B wybrał atak, to A wybrałby {p1 = 1, p2 = 0}, zaś gdyby B wybrał wycofanie się, to A wybrałby {p1=1/2, p2 = 0}. W obu przypadkach p2 = 0. Co to by znaczyło? Że niezależnie od wyboru B, A nie wybierze nigdy WNW (wysłać na wschód). Jeżeli by było to prawdą, to ta strategia czysta musiałaby zostać odrzucona. Rzeczywiście, jeśli przypatrzymy się naszej macierzy wypłat, to zauważymy, że WNW jest zdominowana przez pozostałe strategie. Jeśli B wybierze atak, to A wybierając WNW straci 1, a wybierając WNZ lub PBR osiągnie zysk. Jeśli B wycofa się, to A wybierając WNW zyska 1, dla WNZ dostanie 2, a dla PBR 0. Skoro WNZ jest zawsze lepsze od WNW – w tym sensie, że niezależnie od wyboru B WNZ będzie dawał większą wypłatę – to znaczy, że WNW należy odrzucić.

Może w tym miejscu warto zauważyć, że dominacja ma związek z przechodniością preferencji, ale nie będę teraz tego rozwijał. Zwrócę tylko uwagę, że wcale nie jest intuicyjnie oczywiste odrzucenie WNW, ponieważ gdy porównamy PBR z WNW, to przy wycofaniu się B lepsze jest WNW. Nie możemy jednak odrywać tych dwóch wyborów od pozostałych. Jeżeli bowiem WNZ będzie zawsze lepsze od WNW, to jaki sens porównywać PBR z tym gorszym? Nie wydaje się to sensowne, dlatego powinniśmy porównać każdy z każdym nieodrzuconym. Na sprawę możemy też spojrzeć z takiej oto perspektywy: jeżeli dana strategia czysta będzie zawsze lepsza od jakiejś innej, a ta inna nie gorsza od pozostałych czystych, to i tak ją odrzucamy, bo niejako wybór gorszy bardziej obciąża cały wynik „portfela” niż dodaje mu dywersyfikacji.

Czyli A wybiera między WNZ (wysłać na zachód) oraz PZB (pozostawić bez ruchu).Macierz wypłat przybierze postać:

Ponieważ wybór PZB całkowicie zależy od p1 i p2, ponieważ p3 = 1 – p1 – p2 = 1 – p1, to znaczy, że powracamy do problemu z jedną zmienną, p1. Tym samym dostajemy dwa równania z warunkową wartością oczekiwaną A z jedną zmienną niezależną:

E(A | B atakuje) = -p1 + 2.

E(A | B wycofuje się) = 2*p1

Szukamy maksimin. Rysujemy obie funkcje, oznaczamy minima dla każdego p, wyłuskujemy z nich wartość maksymalną i sprawdzamy jakiemu p przypisana jest ta wartość:

Tak jak wcześniej zauważyliśmy, funkcje się przecinają, teraz jednak możemy wyznaczyć maksimum, które powstaje w punkcie ich przecięcia:

-p1 + 2 = 2*p1 => p1 = 2/3

W sumie rozwiązanie dla A to p1 = 2/3, p2 = 0 i p3 = 1/3.

Ponadto można obliczyć z drugiego równania, że E(A) = 4/3.

Znaleźliśmy rozwiązanie, ale tylko dla A. Trzeba jeszcze poszukać dla B. Oczywiście wszystko będzie analogicznie, jednak trzeba mieć na uwadze, że są na to dwa sposoby. Pierwszy polega na tym, że bierzemy wypłaty ze znakiem przeciwnym i dalsze obliczenia są identyczne – szukamy maksimin. Drugi polega na tym, że nie zmieniamy znaku wypłat na przeciwny, tylko obliczamy minimaks. Dość ważna jest sprawa zapisu rachunków, która wpływa na wybór sposobu. W powyższych przykładach używałem warunkowych wartości oczekiwanych, więc żeby nie wprowadzać w błąd, lepiej zastosować ten pierwszy sposób. Ponieważ sprowadziliśmy macierz do 2×2, to rozwiązanie jest proste. Warunkowe wartości oczekiwana dla B będą mieć postać:

E(B | A wybiera WNZ) = q*(-1) + (1-q)*(-2) = -q + 2q – 2 = q – 2

E(B | A wybiera PBR) = q*(-2) + (1-q)*0 = -2q

Szukamy maximin dla B. Sprowadza się to znalezienia punktu przecięcia obu funkcji (już nie rysujemy):

q – 2 = -2q => q = 1/3.

W sumie rozwiązanie dla B to q = 1/3 i 1-q = 2/3, a E(B) = -2/3.

Znaleźliśmy rozwiązanie dla obu graczy.

Trudniejszy przykład

Powiedzmy, że mamy następującą macierz:

Sprawdzając rozwiązania w strategiach czystych zobaczymy, że punkt siodłowy znów nie istnieje i trzeba rozwiązać problem za pomocą strategii mieszanych. Zaczynamy od gracza A. Zapiszemy jego warunkowe wartości oczekiwane:

E(A | B atakuje) = p1*1 + p2*(-1) + (1-p1-p2)*2 = p1 – p2 – 2p1 – 2p2 + 2 = -p1 – 3p2 + 2

E(A | B wycofuje się) = p1*2 + p2*3 + (1-p1-p2)*0 = 2p1 + 3p2

Następnie moglibyśmy znów wykonać przykładowe podstawienia i próbować znaleźć maksimin:

p1 = 0 i p2 = 0 => 2 i 0 => min((2; 0) = 0 (wycofanie się B)

p1 = 1/2 i p2 = 0 => 3/2 i 1 => min = 1 (wycofanie się B)

p1 = 1 i p2 = 0 => 1 i 2 => min = 1 (atak B)

p1 = 0 i p2 = 1/2 => 1/2 i 3/2 => min = 1/2 (atak B)

p1 = 1/2 i p2 = 1/2 => 0 i 5/2 => min = 0 (atak B)

p1 = 1 i p2 = 1/2 => -1/2 i 7/2 => min = -1/2 (atak B)

p1 = 0 i p2 = 1 => -1 i 3 => min = -1 (atak B)

p1 = 1/2 i p2 = 1 => -3/2 i 4 => min = -3/2 (atak B)

p1 = 1 i p2 = 1 => -2 i 5 => min = -2 (atak B)

Gdyby chcieć w ten przybliżony sposób szukać maksimin, to wybralibyśmy z powyższej listy max-min = 1, ale znów występuje dwukrotnie. W obu przypadkach p2 = 0. Znów wygląda na to, że A odrzuci WNW. O ile jednak w poprzednim przykładzie WNW można było łatwo ją odrzucić, o tyle tutaj już tak nie jest, ponieważ nie jest ona strategią zdominowaną. Mimo że powyższa analiza jest pewnym rozwiązaniem, to po pierwsze jest czasochłonna, a po drugie takie przybliżenia – jeśli nie są naprawdę dokładne – to są rodzajem zgadywania, a nie o to przecież chodzi. Aby pokonać te trudności, moglibyśmy znaleźć rozwiązanie za pomocą algorytmu szukającego maksimin dla każdej pary p1 i p2 w przedziale <0,1>. Tak trzeba by było zrobić w bardziej złożonych przypadkach, ale w tym istnieje sprytniejszy sposób.

Ponieważ teoria gier opiera się na przewidywaniu ruchów przeciwnika, to do zadania można podejść najpierw od jego strony. Spróbujmy w takim razie znaleźć rozwiązania dla B. Zapisujemy warunkowe wartości oczekiwane:

E(B | A wybiera WNZ) = q*(-1) + (1-q)*(-2) = q – 2

E(B | A wybiera WNW) = q*1 + (1-q)*(-3) = 4q – 3

E(B | A wybiera PBR) = q*(-2) + (1-q)*0 = -2q

Rysujemy wykresy tych funkcji:

Stosujemy maximin (przypominam, że jest to minimax dla przeciwnych wypłat). Odrzucamy najwyższe wartości oczekiwane dla każdego q:

W końcu znajdujemy maksimum, które, jak rysunek wskazuje, okazuje się przecięciem -2q i q-2:

-2q = q – 2 => q = 2/3.

Stąd wiemy, że q = 2/3 i E(B) = -4/3.

Wróćmy do A. Wiemy, że oczekiwana wypłata dla B powstała przez przecięcie -2q i q-2, tzn. odrzucona została funkcja 4q – 3. Ale ta funkcja wynika ze scenariusza zakładającego, że A wybiera WNW. Wiedząc, że B chce osiągnąć wypłatę, która nie zależy od 4q – 3, A również powinien odrzucić tę strategię. Wynika to z faktu, że wypłaty obu graczy są przeciwne. Dla q = 2/3 funkcja 4q – 3 (czyli WNW) leży powyżej maximin (czyli przecięcia WNZ i PBR), a więc dla A będzie leżeć poniżej. Skoro dla A WNW leży poniżej przecięcia WNZ i PBR, to jasne jest, że WNW jest gorsze. Sprawdźmy czy ma to sens. Jeśli A wybrałby WNW, to dostałby -1 dla q=2/3 i 3 dla 1-q = 1/3. Wartość oczekiwana wyniosłaby 2/3*(-1) + 1/3*3 = 1/3. Powiedzmy teraz, że A wybiera WNZ. Wartość oczekiwana = 2/3*1 + 1/3*2 = 4/3. W końcu jeśli A wybierze PBR wartość oczekiwana = 2/3*2 + 1/3*0 = 4/3. Ponieważ 1/3 < 4/3, to rzeczywiście WNW okaże się najgorszym wyborem i trzeba ją odrzucić.

Rozwiązanie dla A jest już proste. Zostaje nam znów funkcja jednej zmiennej. Warunkowe wartości oczekiwane A będą następujące:

E(A | B atakuje) = p1*1 + (1-p1)*2 = -p1 + 2

E(A | B wycofuje się) = p1*2 + (1-p1)*0 = 2p1

Rozwiązanie maksimin wynika standardowo z przecięcia obu funkcji:

-p1 + 2 = 2p1 => p1 = 2/3.

W ten sposób udało się rozwiązać zadanie także dla gracza A: p1 = 2/3, p2 = 0, p3 = 1/3 i E(A) = 4/3.

Strategia czysta jako szczególny przypadek strategii mieszanej

W tym artykule pokażę, jak ze strategii mieszanej można przejść do strategii czystej. Jest to de facto kontynuacja poprzedniego wywodu. Mieliśmy grę w pasujące monety (matching pennies), w której gracze A i B wybierają orła lub reszkę. Macierz wypłat jest następująca:

Ponieważ zauważyliśmy, że jest to gra probabilistyczna, dodaliśmy zmienne p i q do macierzy:

Analizę rozpoczęliśmy od gracza A i stwierdziliśmy, że z jego perspektywy p jest zmienną, której rozwiązanie on poszukuje, natomiast q uznaje za stałą, zakładając, że jego przeciwnik ustalił jakiś poziom q. Następnie stwierdziliśmy, że w zasadzie są dwa poziomy stałych u B – q oraz 1-q. Dla uproszczenia zapisaliśmy je odpowiednio q1 i q2. Przypomnijmy 3-wymiarowy rysunek z prawdopodobieństwami p i q jako oddzielnymi osiami odciętych oraz warunkową wartością oczekiwaną na osi rzędnych:

Gracz A uzyskuje taką perspektywę, biorąc pod uwagę q1 i q2 gracza B. Jeżeli obrócimy ten wykres, tak aby uzyskać wykres 2-wymiarowy, z pojedynczą osią odciętych, obie funkcje funkcje nałożą się na siebie i dostaniemy taki obrazek:

Załóżmy teraz, że A wybiera zawsze orła, czyli p = 1. Zmienna p staje się stałą, czyli oś p kurczy się do punktu 1. Jedocześnie wartości oczekiwane wynoszą odpowiednio -2*1 + 1 = -1 oraz 2*1 – 1 = 1. Tak więc ostatni wykres staje się jednowymiarową osią pionową o punktach -1 i 1:

Co się dzieje na wykresie trójwymiarowym, z osią q? Wystarczy podstawić p = 1 za funkcje liniowe i otrzymamy:

Macierz wypłat dla A pozostaje taka sama, po prostu dla O należy podstawić p = 1 i dla R 1-p = 0. Oczywiście A może wybrać też reszkę i wtedy p = 0 i 1-p = 1.

W ten sposób dostajemy szczególny przypadek strategii mieszanej – strategię czystą. Można by zadać pytanie dlaczego strategia mieszana przekształciła się do czystej bez ruszania q? Rzecz w tym, że z punktu widzenia A q jest stałą, której przyporządkowany jest jeden konkretny wybór – orzeł oraz 1-q jest stałą, której przyporządkowana jest zawsze reszka. Z tego wynika, że A traktuje q i 1-q jak strategie czyste gracza B. I stąd cała gra staje się dla A grą z rozwiązaniami w strategiach czystych. Ale traktujemy wybory A tak samo jak wybory B, to znaczy, że możemy tak samo jak oś q, przeciąć oś p dwiema ścianami. Najpierw przetnijmy ścianą p1 = 1:

I drugą ścianą p2:

Skoro p2 = 1-p = 0, to może się wydawać zbędne rysowanie drugiej ściany, która nie przyniesie żadnego rozwiązania. Ponieważ jednak gra jest tak skonstruowana, że wybory A i B są w pewnym sensie zależne od siebie, to aby ocenić co wybierze B oraz obliczyć wartość oczekiwaną dla A, musimy przestudiować każdy scenariusz.

Analiza graficzna staje się coraz bardziej skomplikowana, jednak użycie macierzy wypłat ułatwi zadanie. Stosujemy algorytm max-min. Powiedzmy, że A wybiera O, czyli p1. Jeżeli B wybiera O, czyli q1, to dostajemy punkt (p1, q1), a jeżeli B wybiera R, czyli q2, to dostajemy (p1, q2). Z tego wybieramy minimum wartości oczekiwanej, tj. wybieramy najmniejszą wartość na osi pionowej. Z rysunku wynika, że jest to E(p1, q2). Powiedzmy teraz, że A wybiera R, czyli p2. Jeśli B wybiera q1, to dostajemy (p2, q1), a jeżeli B wybiera q2, to dostajemy (p2, q2). Wybieramy z tych punktów minimum – z rysunku wynika, że na osi pionowej niżej leży (p2, q1), czyli dostajemy E(p2, q1). Z tego obliczamy max{E(p1, q2) , E(p2, q1)}, uzyskując max-min.

Dla gry w monety rozwiązanie wynosi -1. Skoro A wybiera zawsze orła (ewentualnie reszkę, jeśli odwróci kolejność), to B – wiedząc co zrobi A – zawsze wybierze reszkę, bo to mu przyniesie najwyższą wypłatę (+1). Ponieważ wygrana jest stratą drugiego, A dostanie -1. W ten sposób rozwiązanie maximin zgadza się z tym rozumowaniem.

Przy strategiach mieszanych używaliśmy uproszczony dwuwymiarowy wykres z osią p dla A i q dla B. Skoro zobaczyliśmy, że strategia czysta jest szczególnym przypadkiem mieszanej, to możemy to samo pokazać na przykładzie z monetami. Idąc ciągle tym samym sposobem co w strategiach mieszanych, przechodzimy z wykresu 3-wymiarowego do wykresu o dwóch wymiarach z jedną osią odciętych, p:

Wybieramy najniżej położoną część wykresu – punkty (p2, q1) i (p1, q2). Wartości oczekiwane w obu tych punktach są takie same – jest to -1, które jest właśnie rozwiązaniem.

Inny przykład

Powyższy przykład nie jest dobry z punktu widzenia analizy strategii czystych, więc przypatrzmy się następującej macierzy wypłat:

Dla p = 1, tj. wyboru O, wartość oczekiwana A pod warunkiem q wynosi

E(O | q) = 1*1 + 0*2 = 1

oraz wartość oczekiwana A(O) pod warunkiem 1-q wynosi

E(O | 1-q) = 1*(-1) + 0*3 = -1.

Dla p = 0, tj. wyboru R, E(A(R)) pod warunkiem q wynosi

E(R | q) = 0*1 + 1*2 = 2

oraz E(A(R)) pod warunkiem 1-q wynosi

E(R | 1-q) = 0*(-1) + 1*3 = 3.

Przechodzimy od razu do wykresu 2-wymiarowego z osią p:

Pogrubione odcinki to ściany przecinające oś q. Stosujemy więc maximin. Szukamy najniżej położoną „krzywą” – a w tym wypadku najniżej położone punkty na osi rzędnych – dla każdego punktu p. Dla p1 = 1 to jest -1, dla p2 = 0 to jest 2. Obliczamy max(-1; 2) = 2. To jest właśnie maximin:

Gracz A wybierze więc zawsze p = 0, tzn. wybiera R. Ten przykład ma rozwiązanie tylko w strategiach czystych, więc nie ma tu problemu z arbitralnym ustalaniem p, co było konieczne w pierwszym przykładzie, aby sztucznie dojść do rozwiązania w strategiach czystych. Dla gracza B cała analiza będzie identyczna, a jedynie zamienione miejscami będą p i q, a zamiast maximin używamy minimax. W ten sposób dowiedliśmy, że max-min i min-max można w ten sposób stosować w strategiach mieszanych i czystych.

Gry niekooperacyjne: gry dwuosobowe: gry o sumie zerowej: strategie mieszane: 2×2

Powiedzmy, że jest dwóch graczy: A i B i każdy z nich trzyma monetę. W pewnym momencie obaj rzucają swoją monetą jednocześnie. Jeśli na obu monetach wypadł orzeł albo reszka (czyli monety pasują do siebie), to A wygrywa (zabiera obie monety), a jeżeli na jednej wypadł orzeł, a na drugiej reszka (monety nie pasują), to B wygrywa. Ta gra, zwana po ang. matching pennies (która nie ma odpowiednika w polskim nazewnictwie), jest najprostszym przykładem gier 2-osobowych ze strategiami mieszanymi – pojawia się u Neumanna i Morgensterna (1944). Ważne, by mieć na uwadze, że nie jest to zwyczajna gra w orła i reszkę. De facto ta ostatnia to gra 1-osobowa (nawet jeżeli jest dwóch graczy, to ruch jednego całkowicie determinuje ruch drugiego).

Jeżeli moneta jest sprawiedliwa, to szansa wygrania jest taka sama dla obu graczy, tzn. że wynosi 1/2. Powiedzmy jednak, że nie wiemy czy moneta jest sprawiedliwa. Gracze muszą racjonalnie ustalić prawdopodobieństwo, z jakim wybiorą orła albo reszkę. Z pomocą przychodzi teoria gier.

Mamy następującą macierz wypłat:

Każdy z graczy może wybrać orła (O) lub reszkę (R). Po wybraniu strony obaj rzucają monetę i jeśli monety do siebie pasują (mają te same strony), to Gracz A wygrywa 1, a gracz B tyle samo przegrywa. Jeżeli z kolei monety nie będą do siebie pasować (jedna wylosuje O, druga R), to Gracz A przegrywa (dostaje -1), a B wygrywa +1.

Najpierw spróbujmy zastosować algorytm minimax, tak jak dotychczas:

Gracz A wybiera z każdego wiersza minimum, czyli zapisze dwa razy -1. Teraz powinien wybrać wartość maksymalną z pary {-1, -1}, ale nie ma takiej możliwości, bo obie są maksymalne. Gracz B z każdej kolumny wybiera maksimum, czyli zapisze dwa razy +1. Z pary {1, 1} powinien wybrać minimum , ale ponownie obie liczby są minimalne. Wniosek: najlepsza strategia czysta nie istnieje.

Aby rozwiązać problem, gracze muszą użyć prawdopodobieństwa danego wyboru, czyli zastosować strategię mieszaną. Strategia mieszana jest mieszaniną strategii czystych. Gracz A wybiera orła z prawdopodobieństwem p i reszkę z prawdopodobieństwem 1-p. Graczowi B analogicznie przypisujemy prawdopodobieństwo q:

Błędne podejścia

Teraz pewna rzecz, która przez pewien czas sprawiała mi problem, a którą warto podkreślić nawet jeśli to tylko dygresja, ponieważ będzie to dobre przygotowanie do dalszej analizy. Otóż na początku wydawało mi się, że można uprościć zapisy poprzez pominięcie O i R. Czyli początkowo zapisałem:

Dlaczego tak jest źle? Bo zmienia to kompletnie interpretację wierszy i kolumn. Zdefiniowaliśmy wiersze jako strategie czyste gracza A, a kolumny jako strategie czyste gracza B. Stąd nie można opisać wierszy i kolumn przez prawdopodobieństwa, które same w sobie powodują powstanie strategii mieszanej. No dobrze, ale ktoś powie, że to po prostu uproszczenie, a tak naprawdę wiadomo o co chodzi. Problem polega na tym, że w ten sposób można łatwo pobłądzić.

Powiedzmy, że uznajemy (błędnie) p za zwykły wybór (strategię czystą) gracza A. I teraz:

Pierwsze błędne podejście

Poprzez analogię do naszego p uznajemy q za zwykły wybór gracza B. Bierzemy wiersz (p) i szukamy minimum, oddzielnie dla q i 1-q. Dostajemy -1. To samo robimy dla wiersza drugiego – i znowu minimum wynosi -1. I teraz sobie myślimy, że skoro to strategia statystyczna, to obliczamy z obu wyborów wartość oczekiwaną:

p*(-1) + (1-p)*(-1) = -p -1 + p = -1.

Otrzymaliśmy nonsens: dla dowolnego p mielibyśmy dostać najgorszą możliwą wartość.

Drugie błędne podejście

Skoro pierwsze nie wyszło, to spróbujemy uznać, że q nie jest oddzielnym wyborem tak jak nasze p, ale że gracz B stosuje strategię mieszaną – wybiera trochę q i trochę 1-q. To znaczy, że jeśli wybieramy p wartość oczekiwana dla A wyniosłaby:

q*1 + (1-q)*(-1) = q – 1 + q = -1 + 2*q

Dobrze, ale mieliśmy zastosować algorytm max-min, a więc poszukać wpierw jakiegoś minimum. Tutaj dostaliśmy funkcję -1 + 2q, która zależy od q , które jednak ustala przeciwnik. Wiemy tylko, że 0 <= q <= 1.

Analogicznie, jeśli wybieramy 1-p, wartość oczekiwana dla A wyniesie:

q*(-1) + (1-q)*1 = -q + 1 – q = 1 – 2*q

Dostaliśmy więc dwie wartości: -1 + 2*q oraz 1 – 2*q , z których należałoby uzyskać minimum. Widać, że nie możemy wybrać wartości minimalnej, bo ta zależy od wyboru q, na które nie mamy wpływu. Np. dla q = 0 pierwszy wiersz będzie min, dla q = 1 drugi wiersz będzie min, a dla q = 1/2 nie dostaniemy żadnego min (będą równe).

Prawidłowe podejście

Nasze rozumowanie musimy przestawić trochę na inne tory. Dla A każdy wiersz stanowi część rozwiązania, dlatego rozbijanie problemu na strategie czyste musi być ostrożne. Przede wszystkim musimy znaleźć jakiś punkt zaczepienia, ustalić jakąś stałą. Możemy zacząć od A lub B. I teraz tak: ponieważ jesteśmy graczem A, to szukamy dla niego rozwiązania, a to znaczy, że p jest naszą zmienną. To stanowi już poszlakę, że ustalamy stałe u gracza B – w jego przypadku jest tylko parametr q. Postawmy się na miejscu A – z jego perspektywy przeciwnik ustalił jakiś poziom q. Tak więc zakładamy, że B ma jakieś q stałe. Aby dobrze zrozumieć min-max w strategiach mieszanych trzeba to sobie przyswoić.

Czyli jeszcze raz – gracz A – zmienne. gracz B – stałe:

Poniższy rysunek ilustruje ten schemat:

Na tym rysunku mamy trzy osie: p, q oraz wartości z perspektywy gracza A. Zmienną niezależną jest p, zaś q – chociaż też leży na osi odciętych – to reprezentuje jakiś parametr w zaresie od 0 do 1. Oś q przecinamy ścianą – w punkcie naszego parametru. Czyli dla osi q mamy tylko jedną liczbę. Natomiast przez oś p przechodzi nieskończenie wiele punktów od 0 do 1.

Gracz A wie, że B wybiera O z prawdopodobieństwem q, a R 1-q. Ta informacja pozwala wysnuć wniosek, że każdy wybór B ma przypisany q, ale jednocześnie q jest stałe. Każdemu zdarzeniu przypisujemy określone q.

Kolejną informacją jest to, że wypłata dla A zależy od wyboru B. Ale wiemy też, że wypłata dla A zależy w jakiś sposób od p. Pytanie w jaki? Tu przychodzi z pomocą pojęcie wartości oczekiwanej. Możemy ją zapisać ogólnie w następującej formie:

E = p*W(O) + (1-p)*W(R), gdzie

W(O) – wypłata przy wyborze orła zależna od wyboru B

W(R) – wypłata przy wyborze reszki zależna od wyboru B.

E jest funkcją liniową zmiennej p, zapiszmy więc ją w formie:

E(p) = p*[W(O) – W(R)] + W(R)

Funkcja E(p) tak naprawdę zależy od dwóch zmiennych: p i q, ponieważ W(O) i W(R) zależą od wyboru B, czyli też od q. Ale ponieważ q traktujemy jak parametr, który przyjmuje różne wartości, to otrzymujemy wartość oczekiwaną pod pewnymi warunkami. Naszą wartość oczekiwaną możemy rozbić na dwie części, uzyskując dwie warunkowe wartości oczekiwane. Wiadomo przecież, że W(O) i W(R) zależą od tego, którą kolumnę B wybierze. Zaczynamy analizę od kolumny pierwszej macierzy wypłat (B wybiera orła). Wtedy E zapiszemy w postaci:

E(p | B wybiera orła) = p*[W(O | B wybiera orła) – W(R | B wybiera orła)] + W(R | B wybiera orła)

Pionowa kreska | oznacza „pod warunkiem że”.

Gracz A dostanie W(O) = 1 lub W(R) = -1. Ale wyżej stwierdzono, że każdemu wyborowi B przypisujemy jakieś stałe q. Czyli gdy B wybiera orła, przypisujemy mu q – wstawiamy ścianę w tym punkcie q. Dla tego q dostaniemy 1 i -1. Czyli te dwie wartości zapisujemy na ścianie:

Jednocześnie, do wartości oczekiwanej podstawiamy W(O | B wybiera orła) = 1 i W(R | B wybiera orła) = -1:

E(p | B wybiera orła) = p(1 + 1) – 1 = 2*p – 1

Wykreślamy funkcję E(p | B wybiera orła):

Została nam druga część wartości oczekiwanej – gdy B wybiera reszkę. I teraz tak. Wiemy, że to drugie zdarzenie B wybiera z prawdopodobieństwem 1-q. Ale dla lepszego zrozumienia wywodu, zamiast 1-q wpiszemy q2, a dla pierwszego zdarzenia z orłem – q1. Ogólnie możemy przypisać pierwsze zdarzenie q1 (ze ścianą q1), a drugie q2. Ponieważ q2 to kolejna wartość stała, to znaczy, że oś q przecinamy drugą ścianą w punkcie q2:

Dla q2 Zaczynamy więc analizę dla drugiej kolumny macierzy. To znaczy bierzemy drugą warunkową wartość oczekiwaną:

E(p | B wybiera reszkę) = p*[W(O | B wybiera reszkę) – W(R | B wybiera reszkę)] + W(R | B wybiera reszkę)

Jeśli A wybierze orła, dostanie -1, co zapisujemy: W(O | B wybiera reszkę) = -1. Gdy A wybiera reszkę, dostaje 1, czyli: W(R | B wybiera reszkę) = 1. W sumie warunkowa wartość oczekiwana wynosi

E(p | B wybiera reszkę) = p(-1 – 1) + 1 = -2*p + 1.

Podobnie wykreślamy wartości -1 i 1 oraz funkcję E(p | B wybiera orła), tym razem na ścianie q2:

Kiedy w końcu narysowaliśmy te wykresy, możemy przejść do max-min. W zasadzie to teraz można zastosować analogię do znajdowania minimum i maksimum w strategiach czystych. Wtedy było tak, że dla każdego wiersza szukaliśmy najpierw minimum porównując wartości z kolejnych kolumn. Wiemy jednak, że wiersz został zastąpiony przez funkcję zależną od p – wartość oczekiwaną. To co zostało takie samo, to kolumny, które odpowiadają kolejnym dwóm wyborom B. Te kolumny to nic innego jak nasze dwie ściany, q1 i q2, a dokładniej nasze dwie funkcje liniowe. Szukamy więc minimum z sumy tych dwóch funkcji względem p. Czyli nakładamy je na siebie, tak aby można było im przypisać określone p. Ponieważ mamy tylko jedną zmienną niezależną, to znaczy, że obie funkcje – (warunkowe) oczekiwane wygrane gracza A – możemy pokazać na wykresie z jedną zmienną:

Idąc tokiem rozumowania max-min, poszukujemy najpierw minimum wiersza, ale dla każdego punktu – to znaczy znajdujemy minimum między 2p-1 i -2p+1 po wstawieniu za p kolejne liczby od 0 do 1. Czyli najpierw dla p = 0 mamy min(2*0-1, -2*0+1) = -1. Dla ostatniej wartości q = 1, min(2*1-1, -2*1+1) = -1. Poniższy wykres pokazuje jak to wygląda dla przykładowych punktów:

Zgodnie z algorytmem maksimin, wybieramy tę część część wykresu, która stanowi to minimum z obu funkcji:

W końcu szukamy maksimum tej części, ponieważ A maksymalizuje swoją wartość oczekiwaną. Z wykresu powyżej wynika, że jest to punkt przecięcia się obu funkcji. Ponieważ są to funkcje liniowe, to istnieje tylko jeden punkt przecięcia, a zatem do rozwiązania zadania wystarczy wprowadzić warunek zrównania się obu funkcji:

2p – 1 = -2p + 1.

Rozwiązanie wynosi p = 1/2. Gracz A wybierze orła z p = 1/2 i reszkę z 1-p = 1/2.

Całą analizę można powtórzyć dla B. Różnica polega na tym, że zmienną staje się q zamiast p, a wypłaty mają znak przeciwny w stosunku wypłat A. Jeżeli nie zmieniamy znaku na przeciwny, to zamiast maximin stosujemy minimax: zaznaczamy wszystkie maksima z układu {2q – 1, -2q + 1} względem każdego q i z tak utworzonego wykresu wyznaczamy minimum. Na poniższym wykresie zilustrowałem właśnie procedurę minimax:

Zgodnie z minimax po zaznaczeniu wszystkich maksimów, czyli najwyżej położonych krawędzi wykresu, znajdujemy najmniejszą wartość z tej maksymalnej części. Jest to przecięcie funkcji 2q – 1 oraz -2q + 1, czyli ich zrównanie. Znów więc rozwiązaniem równania jest q = 1/2. To rozwiązanie wykorzystuje gracz B do swojej strategii mieszanej: już wie, że powinien wybrać orła z q = 1/2 i reszkę z 1-q = 1/2.

Literatura:

von Neumann, J., Morgenstern, O., (1944), Theory of Games and Economic Behavior.
Princeton: Princeton University Press.

Gry niekooperacyjne: gry dwuosobowe: gry o sumie zerowej: strategie czyste: mxn

W ogólnym przypadku każdy gracz ma do wyboru wiele strategii:

W takich bardziej skomplikowanych układach algorytm minimax może się okazać szczególnie przydatny.

Przykład 1.

Mamy grę wojenną i następującą macierz wypłat (3×2):

Gracz A i Gracz B kierują swoimi wojskami. Gracz A ma przewagę nad Graczem B, dlatego spotkanie się obu wojsk zawsze skończy się wygraną Gracza A. Jednak Gracz A ma różne możliwości, tak że zła decyzja może przynieść mu nawet stratę. Gracz B musi zminimalizować straty, ewentualnie sięgnąć po ryzykowny zysk. Może albo zaatakować z zachodu, albo wycofać się. Powiedzmy, że atakuje. Wtedy, jeżeli Gracz A wyśle na niego wojska (czyli na zachód), to uzyska +1, a Gracz B straci 1. Jeśli jednak A wyśle wojska w tym czasie na wschód, to B zniszczy jego bazę (A straci 1, a B wygra 1). Jeżeli jednak A pozostawi wojska bez ruchu na 1 dzień, to będzie w stanie okrążyć wojska nieprzyjaciela (wykorzystując np. lepszą znajomość terenu) i zniszczyć je, osiągając zysk +2, czyli B poniesie największą stratę (-2). Sytuacja się trochę zmieni, gdy B wycofa wojska. Wtedy wysłanie wojsk na zachód przez A zakończy się jego wygraną +1. Jeżeli jednak A wyśle wojska na wschód, aby spenetrować teren, ewentualnie aby poszerzyć terytorium, to znów uzyska 1. W końcu, jeśli A pozostawi wojska w bazie, to obaj dostaną 0, ponieważ Gracz B wycofał się.

Przeanalizujmy teraz ruchy gracza A niezależnie od ruchów B. Od razu widać, że A nie wybierze wiersza 2 (wysłać na wschód), bo zawsze daje albo gorsze, albo takie same wyniki jak wiersz 1 (wysłać na zachód). Mówimy w takiej sytuacji, że strategia-wiersz 1 dominuje nad strategią-wierszem 2. Z drugiej strony trzeci wiersz (pozostawić) nie jest gorszy od pierwszego ani drugiego. Gracz A prawdopodobnie odrzuci wiersz 2, ale nie jest jasne, czy powinien przyjąć wiersz 1 czy 3.

Z punktu widzenia Gracza B również wybór nie jest oczywisty. Przypuszcza on, że A wybierze wiersz 1 lub 3. Jeżeli wybierze 1, to dla B obojętne będzie którą kolumnę wybrać. Jeżeli A wybierze trzecie rozwiązanie, to dla B lepiej wybrać drugą kolumnę (Wycofać się).

Aby rozwiązać problem, zastosujmy algorytm minimax-maximin (sposób opisałem poprzednio):

Dzięki minimaxowi wiemy, że najlepszym rozwiązaniem będzie dla Gracza A wysłanie wojsk na zachód, a dla Gracza B wycofanie się. Pozycja s(1,2), która daje zysk 1 dla A i -1 dla B, to punkt siodłowy. Niestety nie zawsze punkt siodłowy istnieje.

Przykład 2.

Przykład 1 pozostaje w mocy, a jedynie zmieńmy wartość s(1,2) z 1 na 2:

Tym razem zakładamy, że gdy Gracz B wycofuje wojska, to jeśli Gracz A w tym czasie atakuje na zachód, podwoi sukces. Zastosujmy maximin/minimax:

Maksimin dla gracza A wynosi 1. Minimaks dla gracza B wynosi 2, które jednak występuje dwukrotnie. Ale skoro B wie, że A wybiera wiersz 1, to B wybierze kolumnę 1, minimalizując straty (dostanie -1 zamiast -2). Czyli dostajemy:

Pozornie wydaje się, że wszystko jest w porządku. Dla gracza B wybór kolumny 1 wydaje się najlepszy także dlatego, że gdyby gracz A zachował się nieracjonalnie i wybrał wiersz 2, to B wyszedłby jeszcze na plus. Jednak punkt siodłowy nie istnieje. Dlaczego? Przypomnijmy definicję tego punktu:

Punkt siodłowy to pozycja maksymalna w jego kolumnie i minimalna w jego wierszu. W takim punkcie żaden z graczy nie ma motywacji do jednostronnej zmiany pozycji. 

Punkt s(1,1) spełnia warunek minimum wiersza, ale nie spełnia warunku maksimum kolumny. Pomyślmy teraz praktycznie, co się stanie, jeśli gracze wybierają punkt s(1, 1). Gracz A wiedząc, że B wybierze kolumnę 1, będzie mógł poprawić swoją sytuację, wybierając wiersz 3 – wtedy uzyska +2. Jednak Gracz B domyślając się tego sposobu rozumowania, będzie chciał przechytrzyć A wybierając kolumnę 2 – wtedy obaj dostaną 0. To jednak także przewidzi A, tak że przesunie się z powrotem do wiersza 1 – dostałby +2. Ale wówczas oczywiście B będzie mógł zminimalizować straty wybierając ponownie kolumnę 1. To jednak oznacza powrót to punktu s(1,1). I wszystko zaczyna się od początku. Gra więc nie ma stabilnego punktu, czyli właśnie punktu siodłowego.

Zauważmy, że z punktu widzenia A wiersz 1 nadal dominuje nad wierszem 2 (lub inaczej wiersz 2 jest zdominowany przez 1). A więc mogą istnieć strategie dominujące i zdominowane, a mimo to nie zostanie osiągnięty punkt siodłowy.

Prawidłowym rozwiązaniem jest użycie danej strategii z określonym prawdopodobieństwem – takim, aby zmaksymalizować wartość oczekiwaną. Innymi słowy stosuje się strategie mieszane zamiast czystych. Do tego przykładu jeszcze wrócę.

Literatura:

[1] Luce, R.D., Raiffa, H. (1957), Games and decisions: Introduction and critical surveys, Dover Publications;

[2] von Neumann, J., Morgenstern, O., (1944), Theory of Games and Economic Behavior.
Princeton: Princeton University Press.

Gry niekooperacyjne: gry dwuosobowe: gry o sumie zerowej: strategie czyste: 2×2

Studiujemy grę niesekwencyjną (gracze wykonują ruchy jednocześnie), niekooperacyjną (nie współpracują ze sobą), dwuosobową, o zerowej sumie wypłat (zysk jednego to strata drugiego). Jest to część pierwsza, dlatego:

(1) rozwiązania uzyskamy w strategiach czystych, co oznacza, że będzie możliwy jeden konkretny wybór, który będzie najlepszy,

(2) omawiane przykłady dotyczą gier 2×2, tzn. takich, w których każdy gracz ma dwie strategie czyste do wyboru (macierz wypłat ma dwa wiersze i dwie kolumny).

Przykład 1.

Jest dwóch graczy – firmę i konsumenta. Firma stoi przed dylematem czy podwyższyć, czy obniżyć ceny produktów. Konsument zastanawia się, który produkt kupić: A czy B. Firma chce sprzedać produkt jak najdrożej, a konsument kupić jak najtaniej. Podniesienie ceny zwiększa zysk firmy, ale też zwiększa koszt konsumenta. Obniżenie ceny, zmniejsza zysk firmy, ale też podnosi satysfakcję klienta, któremu zostaje więcej w kieszeni. Wybór jest ostateczny i nie może się zmienić.

Mamy macierz wypłat postaci:

W komórkach są przedstawione wypłaty dla Firmy. Wypłata dla Konsumenta to zawsze przeciwieństwo wypłaty Firmy, np. jeśli Firma osiąga wypłatę równą 5, to Konsument osiąga wypłatę równą -5, czyli ponosi koszt równy 5. Jeśli Firma osiąga wypłatę równą -4 (obniża cenę o 4), to Konsument osiąga wypłatę +4.

Oczywiste jest, że Firma wybierze strategię „Podnieść ceny”, która niezależnie od tego co zrobi Konsument, jest zawsze lepsza od „Obniżyć ceny”.

Równie łatwo jest określić strategię Konsumenta, który analizuje sytuację następująco. Jeżeli Firma podniesie ceny, to jeżeli wybiorę A, utracę 5, a jeżeli wybiorę B, utracę 6. Czyli w tym wypadku lepiej wybrać Produkt A. Jeżeli z kolei Firma obniży ceny, to jeżeli wybiorę A, zyskam 4, a jeżeli wybiorę B, zyskam 3. Ponownie lepszy jest wybór produktu A. Czyli niezależnie od tego, co zrobi Firma wybór A jest lepszy.

Wynika z tego, że Firma wybiera „Podnieść ceny”, a Konsument Produkt A.

Przykład 2.

Jest to niemal identyczny przykład co pierwszy, ale z małą zmianą, która nieco komplikuje zadanie.

Firma ponownie wybierze strategię „Podnieść ceny” (zawsze daje więcej niż obniżenie). Ale Konsument znajduje się w trudniejszym położeniu. Nie wiedząc, jaką decyzję firma podejmie, analizuje on sytuację następująco. Jeżeli Firma podniesie ceny, to wybierając Produkt A, Konsument utraci 5, a wybierając Produkt B utraci 6. Lepsza byłaby w tym wypadku strategia A. Jeżeli Firma obniży ceny, to wybierając A Konsument zyska 3, a wybierając B, zyska 4. Czyli w tym wypadku lepsza jest strategia B. W zależności od zachowania Firmy Konsument podejmie inną decyzję. A Konsument nie wie tak naprawdę, czy Firma jest racjonalna i podniesie ceny.

Gdyby Konsument założył, że Firma maksymalizuje zyski, to miałby pewność, że podniesie ceny i wtedy wybrałby Produkt A, aby zminimalizować straty. Gdyby Konsument był pewny, że Firma zachowa się irracjonalnie i wybierze „Obniżyć ceny”, wybrałby Produkt B. Chociaż Konsument pewności nie ma, to jednak wybór Produktu A wydaje się najlepszy.

Gdyby okazało się, że się mylimy i Firma obniżyłaby ceny, to najprawdopodobniej wynikałoby to z innych warunków, o których nie mamy wiedzy. Być może Firma jest skłonna czasowo obniżyć ceny, aby przyciągnąć klientów i zrekompensować sobie straty wyższymi przychodami w przyszłości. Może też obniżyć ceny, szacując, że się to bardziej opłaca, jeśli klient kupi więcej towaru. Te dodatkowe informacje mogłyby zmienić tak warunki gry, że sumaryczna wypłata nie byłaby już zerowa.

Przykład 3. Bitwa na Morzu Bismarcka

W 1954 r. O. G. Haywood pokazał jak teorię 2-osobowych gier o sumie zerowej można zastosować w praktyce militarnej.

Akcja gry toczy się na południowym Pacyfiku w 1943 roku. Japoński admirał Imamura musi przetransportować wojska przez Morze Bismarcka do Nowej Gwinei, a amerykański admirał Kenney chce zbombardować ten transport. Imamura ma dwie możliwości: krótką trasę północną (2 dni) lub długą trasę południową (3 dni), a Kenney musi wybrać jedną z tych tras, na którą wyśle swoje samoloty. Jeśli wybierze złą trasę, może odwołać samoloty i wysłać je na drugą trasę, ale liczba dni bombardowania zmniejsza się o 1. Zakładamy, że liczba dni bombardowania reprezentuje wypłatę dla Kenneya w sensie pozytywnym, a dla Imamury w sensie negatywnym. Oto oryginalna tabelka Haywooda:

Jeżeli USA (Kenney) wybierze 1-Północny szlak (wiersz 1), to niezależnie od tego co wybierze Japonia (Imamura), USA będzie bombardować ją przez 2 dni. Jednocześnie oznacza to -2 dni dla Japonii. Jeżeli jednak USA wybierze 2-Południowy szlak (wiersz 2), to wszystko zależy od zachowania Japonii. Jeśli wybierze ona 1-Północny szlak (kolumna 1), to USA dostanie +1, a więc Japonia -1. Jeśli z kolei Japonia wybierze 2-Południowy szlak (kolumna 2), to USA dostanie +3 a Japonia -3.

Widzimy, że zadaniem USA jest maksymalizacja wypłaty, a Japonii minimalizacja strat. Jak zachować się powinny kraje? Gdyby jeden kraj wiedział, co zrobi drugi, to oczywiście nie byłoby problemu. Jednak nie wiedzą tego, stąd potrzebna odpowiednia strategia.

Analizę zaczniemy od USA. Jeżeli Japonia wybiera kolumnę (1), to – jeżeli USA wybierze wiersz (1) – to otrzyma +2, a jeżeli wybierze wiersz (2), to otrzyma +1. Czyli w tym wypadku lepiej wybrać wiersz (1). Ale jeżeli Japonia wybierze kolumnę (2), to jeżeli USA wybierze wiersz (1), dostanie +2, a jeżeli wybierze wiersz (2), to dostanie +3. Czyli tym razem lepszy jest wiersz (2). W ten sposób nie dostaniemy rozwiązania dla USA, bo wszystko zależy od zachowania Japonii. Powstaje pytanie czy USA nie powinno w takim razie wysłać części wojsk na północ, a część na południe, czyli zastosować strategię mieszaną? Otóż byłoby to nieracjonalne! Dlaczego? Zachowanie USA zależy przecież od zachowania Japonii. A to znaczy, że należy jeszcze prześledzić analizę dla tego kraju.

Japonia myśli symetrycznie. Jeżeli USA wybiera wiersz (1), to jeżeli Japonia wybierze kolumnę (1), to dostanie -2, a jeżeli wybierze kolumnę (2), to też dostanie -2. Czyli w tym przypadku nie ma znaczenia co wybierze Japonia. Jeżeli jednak USA wybierze wiersz (2), to jeżeli Japonia wybierze kolumnę (1), to dostanie -1, a jeżeli wybierze kolumnę (2), to dostanie -3. Lepsza jest więc tutaj kolumna (1), ponieważ -1 > -3. Dalsze rozumowanie jest proste. Skoro dla wiersza (1) mieliśmy -2 niezależnie od wyboru, a dla wiersza (2) mieliśmy -1, które jest większe od -2, to znaczy, że zawsze Japonia zawsze wybierze kolumnę (1), która minimalizuje stratę.

Teraz możemy wrócić do USA. Skoro Japonia wybiera kolumnę (1), to USA oczywiście wybierze wiersz (1), który maksymalizuje zysk.

Ale tak naprawdę to jeszcze nie koniec. Wracamy znowu do Japonii, która tym razem wie, co wybierze USA. Zachowanie Japonii mogłoby się zmienić, pod wpływem wiedzy o wyborze USA. Jednak szybko przypominamy sobie, że gdy USA wybierze wiersz (1), to Japonia zawsze otrzyma -2, niezależnie od wybranej kolumny. Zatem pozostaje przy kolumnie (1).

Tym samym otrzymujemy rozwiązanie wiersz (1)-kolumna(1) i wypłata 2 dni.

Ciągle oczywiście pozostaje wątpliwość czy strony powinny zakładać racjonalność drugiej strony. Gdyby USA nie było pewne, że Japonia wybierze kolumnę (1), to mogłoby zastosować strategię mieszaną. Powiedzmy, że USA część wojska wysłało na północ i pozostałą na południe, ponieważ nie wie czy Japonia zachowa się racjonalnie. Ale gdyby Japonia zrobiła podobnie i podzieliła transport na kolumnę (1) i (2) postąpiłaby kompletnie bez sensu, bo przecież wybór kolumny (2) jest zawsze gorszy. Dlatego rozsądek wymaga, aby wybrała kolumnę (1). Ale USA musi to wiedzieć, a zatem wybór strategii mieszanej jest dla USA także bez sensu, ponieważ zawsze zmniejsza zysk (otrzyma częściowo 2 i częściowo 1, a mógłby w 100% dostać 2).

Przedstawiony sposób rozwiązania jest logiczny, ale w porównaniu z dwoma pierwszymi przykładami staje się bardziej skomplikowany. Z pomocą przychodzi algorytm oparty na twierdzeniu minimax (min-max) lub inaczej maximin (max-min). W grach o sumie zerowej rozwiązanie minimax danego gracza jest równe maximin tego gracza. Twierdzenie to zostało po raz pierwszy dowiedzione przez von Neumanna (1928). Jednak pierwotnie było ono stworzone dla strategii mieszanych. Natomiast poniższy algorytm dotyczy tylko strategii czystych. Wszystkie 3 przykłady można właśnie rozwiązać za jego pomocą.

Algorytm minimax / maximin

Zaczynamy od dopisania dodatkowego wiersza i dodatkowej kolumny. Kenney, gracz maksymalizujący, wybiera wiersz. Wybierając minimum z każdego wiersza, zapewnia siebie, że mniej nie dostanie. Wpisuje minimum każdego wiersza w nowej kolumnie. W końcu z tej kolumny wybiera maksimum – tj. maksimum ze wszystkich minimów – czyli maximin.

Podobnie japoński dowódca chce zminimalizować swoje narażenie na bombardowanie. Patrzy na każdą kolumnę i notuje najgorsze, co mogłoby mu się przytrafić – maksymalną wartość w kolumnie. Maksima te zapisane w dodanym wierszu – maksimum z każdej kolumny. Aby japoński dowódca zapewnił sobie minimalne narażenie na bombardowanie, wybiera minimum z tych maksimów – minimax.

Poniżej oryginalna tabelka Haywooda z algorytmem minimax/maximin:

Przecięcie wiersza maximin i kolumny minimax stanowi rozwiązanie dla obydwu stron. W teorii gier nazywane jest ono punktem siodłowym (ang. saddlepoint). Punkt siodłowy to pozycja wynikająca z kombinacji (Północ, Północ), która jest maksymalna w jego kolumnie (2 >= 1) i minimalna w jego wierszu (2 <= 2). W takim punkcie żaden z graczy nie ma motywacji do jednostronnej zmiany pozycji. Wartość punktu siodłowego (+2) nazywana jest wartością gry i jest to wypłata Japończyków na rzecz Amerykanów.

Dotarliśmy w ten sposób do tzw. strategii maximin oraz strategii minimax. Strategia maximin gracza 1 (USA) maksymalizuje minimalną (w odniesieniu do strategii gracza 2 – Japonia) wypłatę gracza 1, a strategia minimax gracza 2 minimalizuje maksymalną (w odniesieniu do strategii gracza 1) wypłatę, jaką gracz 2 musi zapłacić graczowi 1 [Peters (2015), s. 26]. Strategie te pozwalają zminimalizować straty lub ryzyko. Należy zaznaczyć, że opisany algorytm dotyczy strategii czystych.

Chociaż historia bitwy na Morzu Bismarcka stanowi tylko tło dla prezentowanego problemu, to zapewne niejeden zadaje sobie pytanie, jak to się skończyło naprawdę? Okazuje się, że skończyło się tak jak teoria przewiduje. Haywood wyjaśnia, że Kenney skoncentrował swoje rozpoznanie na szlaku północnym oraz japoński konwój popłynął szlakiem północnym; konwój został zauważony około jeden dzień po wypłynięciu; wkrótce potem rozpoczęły się alianckie bombardowania. Chociaż bitwa zakończyła się katastrofalną porażką Japończyków, nie można powiedzieć, że japoński dowódca popełnił błąd w swojej decyzji. Podobny konwój dotarł do Lae z niewielkimi stratami dwa miesiące wcześniej. Potrzeba była krytyczna, a Japończycy byli gotowi zapłacić wysoką cenę. Nie wiedzieli, że Kenney zmodyfikował kilka swoich samolotów do bombardowania z niskiego pułapu i doprowadził do perfekcji zabójczą technikę. Zwycięstwo USA było wynikiem starannego planowania, gruntownego szkolenia, zdecydowanego wykonania i taktycznego zaskoczenia nową bronią – a nie błędem w decyzji Japończyków. [Haywood (1954). Cytat przetłumaczono z http://www.DeepL.com/Translator (wersja darmowa)].

Literatura:

Haywood Jr., O. G., Military Decision and Game Theory, Nov. 1954;

Peters, H. (2015), Game Theory—A Multi-Leveled Approach, Springer-Verlag, Berlin;

von Neumann, J. (1928) Zur théorie der gesellschaftsspiele, Math. Annalen vol. 100, 295–320, in S. Bargmann (trans.) as On the theory of games of strategy, Contributions to the Theory of Games vol. 4, A.W. Tucker and R.D.Luce (eds) Annals of Mathematics Studies 40, Princeton, NJ: Princeton University Press (1959), 13–42.