Podręcznik: Niekooperatywna teoria gier - gry o sumie zerowej

1. Elementy teorii gier

1.2. Niekooperatywna teoria gier - gry o sumie zerowej

W tym rozdziale zajmiemy się gramai o sumie zerowej. Jak można zdefiniować taką grę? Otóż dla gier dwuosobowych można posłużyć się następującą defnicją:

W grze dwuosobowej o sumie zerowej wygrana gracza pierwszego oznacza stratę gracza drugiego.

Dla gier wieloosobowych, definicja jest następująca:

Gra jest grą o sumie zerowej, gdy dla każdej kombinacji decyzji graczy, suma wypłat dla wszystkich graczy wynosi zero.

Przykładowe gry o sumie zerowej to gra w rzut monetą, gra w "papier-kamień-nożyce".

Gra w "papier-kamień-nożyce"

$q_X$ $p^K$ $n^K$ $k^K$

$p^W$ 0,0 -1,1 1,-1

$n^W$ 1,-1 0,0 -1,1

$k^W$ -1,1 1,-1 0,0

Postać ogólna dwuosobowej gry o sumie zerowej przedstawia się następująco:

Gra w "papier-kamień-nożyce"
$q_X$	$p^K$	$n^K$	$k^K$
$p^W$	0,0	-1,1	1,-1
$n^W$	1,-1	0,0	-1,1
$k^W$	-1,1	1,-1	0,0

Postać ogólna gry o sumie zerowej

$q_X$ $d_1^K$ $d_2^K$

$d_1^W$ $x_1,-x_1$ $x_2,-x_2$

$d_2^K$ $x_3,-x_3$ $x_4,-x_4$

Taka postać wynika wprost z defnicji - wygrana Pana Wiersza ( $x_n)$ odpowiada stracie Pani Kolumny ( $-x_n)$ .

Postać ogólna gry o sumie zerowej
$q_X$	$d_1^K$	$d_2^K$
$d_1^W$	$x_1,-x_1$	$x_2,-x_2$
$d_2^K$	$x_3,-x_3$	$x_4,-x_4$

Dlatego też, dla tych gier (dwuosobowych) wygodnie jest opisywać jest w podstaci skróconej, w której przedstawiamy jedynie wypłaty Pana Wiersza (pierwszego z graczy):

Postać ogólna gry o sumie zerowej

$q_X$ $d_1^K$ $d_2^K$

$d_1^W$ $x_1$ $x_2$

$d_2^K$ $x_3$ $x_4$

Problem "rozwiązywania" gier o sumie zerowej rozwiązał John von Neumann w 1928 r. Sformułował on algorytm podejmowania decyzji tzw. strategię minimaks, która maksymalizuje zyski gracza i minimalizuje straty przeciwnika. Algorytm ten został stworzony dla gier dwuosobowych o sumie zerowej i kompletnej informacji.

Postać ogólna gry o sumie zerowej
$q_X$	$d_1^K$	$d_2^K$
$d_1^W$	$x_1$	$x_2$
$d_2^K$	$x_3$	$x_4$

Założenie o kompletnej infomacji oznacza, że gracze mają pełną informację o możliwych wynikach gry, czyli znają funkcje wypłat swoją i pozostałych graczy, znają także zbiory możliwych decyzji wszyskich graczy.

Minimaks jest to największa wartość, którą określony gracz (z którego punktu widzenia analizujemy grę, zazwyczaj jest to Pan Wiersz) może uzyskać nie wiedząc, którą decyzję wybiorą przeciwnicy.

W grach dwuosobowych można wyznaczyć także maksimin (analizując grę z punktu widzenia przeciwnika Pana Wiersza).

Należy pamiętać, że maksimin jest ujemną wypłatą dla Pani Kolumny.

Przykład - graficzne obliczanie wartości minimaks
$q_X$	$d_1^K$	$d_1^K$	min. wiersza
$d_1^W$	1	4	1	maksimin
$d_2^W$	0	2	0
maks. kolumny	1	4
	minimaks

Aby obliczyć wartość minimaks, można posłużyć się macierzą wypłat. Obliczamy wartość maksymalną w każdej kolumnie, a następnie wybieramy najmniejszą z tych wartości (w przykładzie jest to wartość 1, odpowiadająca decyzji $d_1^K$ ). Analogicznie, obliczemy wartość minimalną w każdym wierszu i wybieramy największą z tych wartości (w przykładzie jest to wartość 1, odpowiadająca decyzji $d_1^W$ ).

Wynik gry nazywamy punktem siodłowym jeśli jego wartość jest:

mniejsza lub równa każdej wartości w jego wierszu

większa lub równa każdej wartości w jego kolumnie

W naszym przykładzie punkt siodłowy istnieje i jego wartość wynosi 1. Decyzje które prowadzą do jego wyboru to

$d_1^W$ i

$d_1^K$ .

Wykres 3D obrazujący ideę punktu siodłowego. Oś X to decyzje Pana Wiersza, oś Y to decyzje Pani Kolumny.

Wykres 3D obrazujący ideę punktu siodłowego. Oś X to wybory Pana Wiersza, oś Y Pani Kolumny.

Jeżeli gra ma punkt siodłowy wówczas obydwoje graczy powinni wybrać decyzje, które prowadzą do jego wyboru.

Punkt siodłowy nie zawsze istnieje. Taka sytuacja zachodzi wówczas, gdy wartości minimaks i maksimin się różnią.

Przykład - brak punktu siodłowego
$q_X$	$d_1^K$	$d_1^K$	min. wiersza
$d_1^W$	4	2	2	maksimin
$d_2^W$	0	3	0
maks. kolumny	4	3
		minimaks

Istnieje także możliwość, że jest wiele takich punktów.

Wiele punktów siodłowych
$q_X$	$d_1^k$	$d_2^k$	$d_3^k$	min. wiersza
$d_1^W$	6	0	-1	-1
$d_2^W$	3	1	1	1	maksimin
$d_3^W$	4	1	1	1	maksimin
maks. kolumny	6	1	1
		minimaks	minimaks

Zdefiniujmy pojęcie strategii czystej.

Strategia, w której gracz podejmuje jedną, konkretną decyzję i jej nie zmienia nazywamy strategią czystą.

Przykład
$q_X$	$d_1^K$	$d_1^K$	min. wiersza
$d_1^W$	1	4	1	maksimin
$d_2^W$	0	2	0
maks. kolumny	1	4
	minimaks

Przykładem strategii czystej dla Pana Wiersza jest $d_1^W$ , zaś dla Pani Kolumny strategią czystą to $d_1^K$ . W przypadku istnienia dokładnie jednego punktu siodłowego, obydwoje graczy posiada strategie czyste, które odpowiadają punktowi siodłowemu. Stosując strategię czystą, gracz powoduje maksymalizację swoich zysków (minimalizację strat).

Jednak, gdy nie istnieje dokładnie jeden punkt siodłowy, gracze mogą stosować strategię mieszaną.

Strategia mieszana określa rozkład prawdopodobieństwa nad zbiorem decyzji, z jakim dokonuje on wyboru.

Przykład - strategia mieszana
$q_X$	$d_1^K$	$d_1^K$	min. wiersza
$d_1^W$	4	2	2	maksimin
$d_2^W$	0	3	0
maks. kolumny	4	3
		minimaks

Jak jednak wyznaczyć taki rozkład prawdopodobieństwa? Zastanówmy się najpierw jaki wynik przyniosłoby stosowanie przez Panią Kolumnę decyzji w oparciu o rzut monetą - czyli wybieranie decyzji $d_1^K$ z prawdopodobieństwem 1/2 i $d_2^K$ z prawdopodobieństwem 1/2.

Wówczas, wybór $d_1^W$ przez Pan Wiersza powodowałby oczekiwaną wypłatę dla niego równą: $1/2 \cdot 4 + 1/2 \cdot 2 = 3$ .

Zaś wybór $d^2_W$ dawałby Panu Wierszowi wypłatę równą $1/2 \cdot 0 + 1/2 \cdot 3 = 3/2$ .

Z tych prostych kalkulacji wynika, że Pan Wiersz, wiedząc że Pani Kolumna stosuje strategię mieszaną: $d_1^K$ z prawd. = 1/2, i $d_2^K$ z prawd. = 1/2, zawsze wybierze $d_1^W$ .

Wprowadźmy kryterium wartości oczekiwanej. Jeśli gracz W wie, że jego przeciwnik (gracz K) gra określoną strategią mieszaną i gracz K będzie ją stosował niezależnie od tego, jaką strategią gra gracz W, wówczas gracz W powinien stosować strategię dającą największą wartość oczekiwaną wypłaty.

Wobec kryterium wartości oczekiwanej, zastanówmy się, czy istnieje taka strategia mieszana dla Pani Kolumny, że Pan Wiersz nie będzie mógł wykorzystać tego, że ją zna przeciwko Pani Kolumnie.

Załóżmy, że Pani Kolumna wybiera

$d_1^K$ z prawdopodobieństwem

$p$ , zaś

$d_2^K$ z prawdopodobieństwem

$1-p$ .

Jeśli Pan Wiersz wybierze $d_1^W$ , wówczas jego oczekiwana wypłata będzie równa: $4 \cdot p + 2 \cdot (1-p) = 2 \cdot p + 2$

Jeśli Pan Wiersz wybierze $d_w^W$ , wówczas jego oczekiwana wypłata będzie równa: $0 \cdot p + 3 \cdot (1-p) = -3 \cdot p + 3$

Aby Pan Wiersz nie mógł wykorzystać wiedzy o znajomości strategii Pani Kolumny, należy znaleźć takie

$p$ , aby jego wybór niczego nie zmienił, czyli:

$2 \cdot p + 2 = -3 \cdot p + 3 \Rightarrow p =1/5$
Sprawdźmy wypłaty dla Pana Wiersza dla

$p=1/5$ :

Pan Wiersz wybiera $d_1^W$ , jego oczekiwana wypłata: $4 \cdot 1/5 + 2 \cdot 4/5 = 12/5$

Pan Wiersz wybiera $d_2^W$ , jego oczekiwana wypłata: $0 \cdot 1/5 + 3 \cdot 4/5 = 12/5$

W takiej sytuacji Pan Wiersz, niezależnie od decyzji otrzyma oczekiwaną wypłatę

$12/5$ .

W analogiczny sposób można wyznaczyć strategię mieszaną dla Pana Wiersza, zakładając, że wybiera decyzję $d_1^W$ z prawdopodobieństwem $q$ i $d_2^W$ z prawdopodobieństwem $1-q$ . Wówczas:

jeśli Pani Kolumna zagra $d_1^K$ otrzyma oczekiwaną wypłatę: $-4 \cdot q + 0 \cdot (1-q) = -4 \cdot q$
jeśli Pani Kolumna zagra $d_2^K$ otrzyma oczekiwaną wypłatę: $-2 \cdot q - 3 \cdot (1-q) = -3 + q$

Pani Kolumna nie wykorzysta znajomości strategii Pana Wiersza gdy: $-4 \cdot q = -3 + q \Rightarrow q = 3/5$ .

Sprawdź, jakie będą oczekiwane wypłaty dla Pana Wiersza dla

$q = 3/5$ .

Na koniec kilka wniosków i twierdzeń.

Strategia czysta jest szczególnym przypadkiem strategii mieszanej.

Twierdzeniem o minimaksie (John von Neumann, 1928).
Każda gra

$n \times m$ (n wyborach Pana Wiersza i m wyborach Pani Kolumny) o sumie zerowej ma rozwiązanie w strategiach mieszanych (lub czystych).

Podczas gdy znalezienie strategii mieszanej dla gry $2 \times 2$ jest proste, to znalezienie jej dla gier $n \times m$ jest bardziej skomplikowane. Jednak literatura podaje na to kilka sposobów:

redukcja gry poprzez wykreślanie rozwiązań zdominowanych (por. rozdział 7.3)
rozwiązanie algebraiczne układu równań (por. Straffin P. "Teoria Gier, 2001, rozdział 3)
rozwiązanie zadania metodą graficzną (por. Straffin P. "Teoria Gier, 2001, rozdział 3)
Rozwiązanie zadania programowania liniowego (por. Raghavan, T. E. S. "Zero-sum two-person games." Handbook of game theory with economic applications 2 (1994): 735-768)