TGND:Gry dwuosobowe o sumie zerowej

Z Skrypty dla studentów Ekonofizyki UPGOW

Spis treści

Gry dwuosobowe o sumie zerowej

Gry oraz diagramy przesunięć

Gra
Przez grę rozumiemy zespół zasad określający wypłatę dla graczy jako funkcje wybranych opcji, które są możliwe dla danej gry.

Aby mówić o grze musimy wskazać co najmniej dwu graczy. Każdy z tych graczy ma możliwość wyboru spośród pewnej liczby możliwych opcji. Gracze podejmują swoje decyzję równocześnie lub, co na to samo wychodzi, nie znając wyborów pozostałych graczy - taką grę nazywamy symultaniczną. Mogą też wybierać swoje opcje jako odpowiedź na wybór dokonany przez pozostałych graczy, w takim przypadku mówimy o grach 'sekwencyjnych'. Gra może składać się z jednej lub wielu rund, w trakcie których gracze dokonują swoich wyborów. Przez strategię, jak już to wspomnieliśmy we wstępie, rozumiemy przyjęty przez gracza sposób wybierania jednej z możliwych opcji. Strategie mogą być proste, wówczas gracz po prostu wybiera jedną opcję lub mieszane, wówczas gracz decyduje się na wybór kilku opcji z określeniem prawdopodobieństwa wyboru każdej z nich.

Jeśli każdej możliwej kombinacji opcji wybranych przez graczy przyporządkujemy (jednoznacznie) wypłatę dla każdego z nich to taki przepis nazywamy zasadą gry. Wypłatą gracza nazywamy mierzalny sposób określenia jego wyniku. Wypłaty zazwyczaj określamy w sposób liczbowy aby ułatwić ich sumowanie i podliczanie wyników gry. Można jednak definiować gry w których wypłaty są dobrami materialnymi, zobowiązaniem do wykonania jakiejś czynności (np. że gracz, który przegra stanie na głowie), etc. Zasady gry mogą być przedstawione w postaci macierzowej tzw. tabeli wypłat. Poniżej przedstawiamy przykładową tabelę.

Przykład 2.1 Tabela gry.
Przykład macierzy wypłat dla gry dwuosobowej
2.1 Basia (Kolumna)
Adam (Wiersz) A B
A 1, -1 -2, 2
B -1, 1 0, 0
C -4, 4 5, -5

Graczami są Adam i Basia. W dalszej części odpersonalizujemy Adama i będziemy go nazywać (panem) Wierszem a Basię (panią) Kolumną. W grze 2.1 Adam ma do wybory trzy opcje (strategie proste): A, B oraz C a Basia dwie strategie: A oraz B. W zależności od dokonanych wyborów uzyskują wypłaty zapisane w tabeli. Wypłaty Adama są oznaczone kolorem niebieskim a wypłaty Basi kolorem czerwonym. Jak łatwo zauważyć wypłaty Adama są zawsze liczbami przeciwnymi do wypłat Basi. Tyle ile jedno z nich wygra drugie musi przegrać. Grę w której mamy do czynienia z taką sytuacją nazywamy grą o sumie zerowej. Dla gier o sumie zerowej przyjmujemy upraszczające konwencję zapisu, w której tabela wypłat zawiera tylko wypłaty Wiersza, wypłaty Kolumny są przeciwne do wypłat wiersza. W przypadku gry 2.1. uproszczona tabela ma postać

Uproszczona macierz pokazująca tylko wypłaty Wiersza
2.1 Kolumna
Wiersz A B
A 1 -2
B -1 0
C -4 5

Przeanalizujmy teraz, jak wygląda nasza przykładowa gra 2.1 z punktu widzenia opłacalności poszczególnych wyborów graczy. Jeśli Wiersz wybierze opcję A to kolumnie opłaca się wtedy wybrać B, gdyż dla opcji A Kolumna przegrywa \(1\) a w opcji B Kolumna wygrywa \(2\). Na diagramie przesunięć poniżej oznaczono ten fakt przy pomocy strzałki w prawo w polu (A,A). Zauważmy, że strzałka ta jest skierowana od wartości większej \((1)\) do mniejszej \((-2)\) zgodnie z konwencją, że wygrane Kolumny są liczbami przeciwnymi do wygranych wiersza. A zatem ta strzałka, tak naprawdę wskazuje preferencje Kolumny: zakładając, że Wiersz pozostanie przy opcji A, wybór B Kolumny jest dla niej korzystniejszy niż A \((2 > -1)\). Można podsumować, że poziome strzałki diagramu przesunięć są zawsze skierowane od wartości większych do mniejszych oraz wskazują preferowane opcje Kolumny.

Diagram przesunięć
Macierzy pokazująca dla każdej pary wyborów preferencje graczy
2.1 Kolumna
Wiersz A B
A \(\rightarrow\) \(\downarrow\)
B \(\uparrow\) \(\leftarrow \; \downarrow\)
C \(\uparrow\) \(\leftarrow\)

Preferowane opcje Wiersza wskazują strzałki pionowe, które są zawsze skierowane od wartości mniejszych do większych, zgodnie z preferencjami Wiersza. Strzałka skierowana w dół w polu (B,B) oznacza, że przy zadanym wyborze B Kolumny, opcja C jest dla Wiersza korzystniejsza niż B. Zauważmy, że w polu (B,B) znajduje się również strzałka skierowana w lewo. Oznacza ona, że przy zadanym wyborze B Wiersza, opcja A jest dla Kolumny korzystniejsza niż B. W każdym polu diagramu przesunięć gry 2.1 znajduje się jakaś strzałka. Oznacza to, że nie ma w tej grze pary wyborów, która byłaby korzystna dla oby graczy: dla każdej pary wyborów jeden z graczy może znaleźć opcję korzystniejszą, przy założeniu, że partner pozostanie przy swojej. Ta sytuacja jednak nie zawsze ma miejsce, zobaczmy bowiem kolejną grę:

Przykład 2.2 Gra z punktem równowagi.
Macierz wypłat 2.2
2.2 Kolumna
Wiersz A B C
A -1 3 1
B 0 2 0

Diagram przesunięć dla tej gry wygląda następująco:

Diagram przesunięć dla gry 2.2
2.2 Kolumna
Wiersz A B C
A \(\downarrow\) \(\leftarrow \; \; \; \; \rightarrow\)
B \(\leftarrow \; \uparrow \; \rightarrow\) \(\uparrow\)

Jak widzimy w polach (B,A) i (A,C) nie ma żadnych strzałek. Oznacza to, że jeśli gracze znajdą się w jednym z tych punktów, to żadnemu z nich nie opłaca się jednostronnie zmieniać swojej opcji na sąsiednią. Takie miejsca nazywamy punktami równowagi. Zauważmy, że punkty równowagi jest określony lokalnie, poprzez wartości wypłat pól sąsiednich. Jaką strategię powinni obrać graczy w tej grze? Dla Wiersza korzystniejszą jest równowaga (A,C) - wygrana \(1\) niż (B,A) - wygrana \(0\). Załóżmy więc, że wybierze on opcję A. Wtedy jednak Kolumna szybko zauważy, że lepiej jej jest nie grać swojej opcji C dla równowagi (A,C) gdyż opcja A jest dla nie korzystniejsza. Jeśli Wiersz to zauważy to sam powinien zagrać B, co doprowadzi graczy do drugiej równowagi (B,A). Po osiągnięciu tej równowagi, żaden z graczy nie jest zainteresowany zmianą swojej strategii: wygrana \(0\) jest bowiem dla wiersza najwyższa w kolumnie A, natomiast dla Kolumny jest ona nie mniej korzystna niż inne w wierszu B. Żaden z graczy nie może wygrać więcej przez jednostonną zmianę swojej strategii.

Punkty siodłowe oraz dominacje

Rozpoczniemy od definicji punktu siodłowego

Punkt siodłowy
Punkt macierzy wypłat, którego wartość jest nie większa od innych wartości w jego wierszu oraz nie mniejsza od innych wartości w jego kolumnie nazywamy punktem siodłowym. Na punkt siodłowy składa się para zawierających go strategii oraz jego wartość \( \nu \) nazywamy wartością gry.

W grze 2.2 punktem siodłowym jest równowaga (B,A). Wiersz grając należącą do punktu siodłowego strategię B może być pewien, że nie wygra mniej niż wynosi wartość gry \(0\) a Kolumna grając należącą do punktu siodłowego strategię A ma pewność, że Wiersz nie wygra więcej niż wynosi wartość gry.

Zauważmy, że niezależnie od strategii Wiersza, Kolumna może z góry wykluczyć swoją strategię B. Istotnie, Strategia B jest zawsze gorsza od strategii A i strategii C Kolumny. Obrazują to poziome strzałki na diagramie przesunięć gry 2.2. Ten przypadek ilustruje ważne pojęcie strategii zdominowanej.

Strategia zdominowana
Mówimy, że strategia X gracza jest zdominowana przez strategię Y tego gracza jeżeli X i Y nie są identyczne a niezależnie od strategii przeciwnika wypłata przy wyborze X jest niewiększa od wypłaty przy wyborze Y. W tym przypadku mówimy również, że strategia Y gracza dominuje strategię X.

Jak widzimy na przykładzie 2.2 strategia B Kolumny jest zdominowana przez strategię A oraz przez strategię C. Istotnie dla wypłaty Kolumny porównując B z A mamy \(-3<1\) i \(-2<0\). Podobnie rzecz się ma przy porównaniu B z C. Jeśli jakaś strategia jest zdominowana przez inną to gracz może tej strategii nie brać pod uwagę w rozgrywce. Rzeczywiście zamiast tej strategii może zawsze wybrać inną, która ją dominuje a jego wygrana będzie co najmniej równa wygranej dla strategii zdominowanej.

Załóżmy, że mamy do czynienia z racjonalnymi graczami, którzy nie wybierają strategii dla siebie niekorzystnych. W tym przypadku analizując grę możemy ją uprościć usuwając z niej wszystkie strategie zdominowane. W przypadku gry 2.2 możemy spokojnie usunąć strategię B Kolumny. W tym przypadku gra przybierze postać


Przykład 2.2' Gra 2.2 bez strategii zdominowanej.
Macierz wypłat 2.2'
2.2' Kolumna
Wiersz A C
A -1 1
B 0 0

Na diagramie przesunięć dla tej gry znajdziemy jeden punkt równowagi (B,A):

Diagram przesunięć dla gry 2.2'
2.2 Kolumna
Wiersz A C
A \(\downarrow\) \(\leftarrow\)
B \( \uparrow\)

Zauważmy, że punkt równowagi (B,A) jest jednocześnie punktem siodłowym. Wyeliminowanie z gry strategii zdominowanej uprościło jej analizę i z dwu punktów równowago pozostał tylko jeden - ten który jest jednocześnie punktem siodłowym. Przeanalizujmy na koniec bardziej złożoną grę, w której każdy z graczy ma po 4 opcje wyboru.

Przykład 2.3 Gra z kilkoma punktami siodłowymi.
Macierz wypłat 2.3
2.3 Kolumna
Wiersz A B C D
A 2 1 3 1
B -1 0 7 -5
C 9 1 5 1
D 1 0 7 -2

Diagram przesunięć dla tej gry wygląda następująco:

Diagram przesunięć dla gry 2.3
2.3 Kolumna
Wiersz A B C D
A \(\rightarrow\) \(\leftarrow \; \downarrow \; \rightarrow\)
B \(\updownarrow\) \(\leftarrow \; \updownarrow\) \(\leftarrow \; \; \; \; \rightarrow\) \(\updownarrow\)
C \(\rightarrow\) \(\leftarrow \; \updownarrow \; \rightarrow\)
D \(\uparrow \; \rightarrow\) \(\uparrow\) \(\leftarrow \; \; \; \; \rightarrow\) \(\uparrow\)

W tej grze można wyeliminować strategię C Kolumny, jest ona zdominowana zarówno przez strategię B jak i D a zatem racjonalny gracz nie powinien grać tej strategii. Po wyeliminowaniu strategii C Kolumny uzyskamy grę


Przykład 2.3' Gra z kilkoma punktami siodłowymi.
Macierz wypłat 2.3'
2.3 Kolumna
Wiersz A B D
A 2 1 1
B -1 0 -5
C 9 1 1
D 1 0 -2

dla której diagram przesunięć jest

Diagram przesunięć dla gry 2.3'
2.3' Kolumna
Wiersz A B D
A \(\rightarrow\)
B \(\updownarrow\) \(\leftarrow \; \updownarrow \; \rightarrow\) \(\updownarrow\)
C \(\rightarrow\)
D \(\uparrow \; \rightarrow\) \(\uparrow \; \rightarrow\) \(\uparrow\)

Wiedząc o tym Wiersz również wyciągnie wnioski. Zauważmy, że w zmodyfikowanej grze 2.3' strategie B i D Wiersza są zdominowane na przykład przez strategię C. Dla Wiersza oznacza to, że może tych strategii nie brać pod uwagę, co dodatkowo znacznie uprości grę do postaci


Przykład 2.3\(''\) Gra z kilkoma punktami siodłowymi.
Macierz wypłat 2.3\(''\)
2.3\(''\) Kolumna
Wiersz A B D
A 2 1 1
C 9 1 1

dla której diagram przesunięć jest

Diagram przesunięć dla gry 2.3\(''\)
2.3\(''\) Kolumna
Wiersz A B D
A \(\rightarrow\)
C \(\rightarrow\)

A teraz już tylko jeden krok do rozwiązania gry, które otrzymamy po wyeliminowaniu zdominowanej strategii A Kolumny (zauważmy, że Kolumna nie mogła wyeliminować swojej strategii A już w pierwszym kroku, gdyż w pierwotnej postaci gry 2.3 ta strategia nie jest zdominowana). Gra 2.3 sprowadza się więc do prostej formy

Przykład 2.3\('''\) Gra z kilkoma punktami siodłowymi.
Macierz wypłat 2.3\('''\)
2.3\('''\) Kolumna
Wiersz B D
A 1 1
C 1 1

dla której diagram przesunięć jest oczywiście pusty. Rozwiązanie gry 2.3 mówi nam, że Wiersz powinien grać strategię A lub C a Kolumna strategię B lub D. Grając te strategie obaj gracze mają gwarancję, że ich wynik będzie nie gorszy niż wynosi wartość gry, którą jest w tym przypadku \( \nu=1 \). Zauważmy, że pary strategii (A,B), (A,D), (C,B) i (C,D) są punktami siodłowymi gry w każdej jej postać od 2.3 do 2.3\('''\). W pierwotnej postaci gry para strategii (D,A) również dawała wygraną równą wartości gry \( \nu=1 \) ale para ta nie jest punktem siodłowym. Istotnie, gdyby na przykład wiersz zdecydował się zagrać strategię D to Kolumna mogłaby zagrać również D uzyskując dla siebie wynik \(2\) dużo korzystniejszy niż wartość gry.

Gra 2.3 ma zatem 4 punkty siodłowe, odpowiadające wartości gry \( \nu=1 \). Czy możliwa jest sytuacja w której gra ma kilka punktów siodłowych odpowiadających różnym wartościom wygranej? Gdyby tak było, to nie można by jednoznacznie określić wartości gry. Na szczęście taka sytuacja nie może mieć miejsca. Zachodzi bowiem twierdzenie

Twierdzenie. Każde dwa punkty siodłowe tej samej gry odpowiadają tej samej wypłacie.
Dowód
załóżmy, że para strategii (X\(_{1}\),Y\(_{1}\)) odpowiada wypłacie \( \nu_{1,1}\) a para strategii (X\(_{2}\),Y\(_{2}\)) odpowiada wypłacie \( \nu_{2,2}\) oraz (X\(_{1}\),Y\(_{1}\)) i (X\(_{2}\),Y\(_{2}\)) są punktami siodłowymi. Pokażemy, że \( \nu_{1,1}=\nu_{2,2}\). Gdyby X\(_{1}\) = X\(_{2}\) to \( \nu_{1,1}=\nu_{1,2}\) gdyż z definicji żaden z dwu punktów siodłowych w jednym wierszu nie może być większy od drugiego. Podobnie pokazujemy tezę dla Y\(_{1}\) = Y\(_{2}\). Możemy więc założyć, że strategie X\(_{1}\) i X\(_{2}\) są różne podobnie jak Y\(_{1}\) i Y\(_{2}\). Rozważmy dodatkowe pary strategii (X\(_{1}\),Y\(_{2}\)) i (X\(_{2}\),Y\(_{1}\)), oraz odpowiadające im wypłaty \( \nu_{1,2}\) i \( \nu_{2,1}\) (por. tabela 2.4). Zauważmy, że z definicji punktu siodłowego wynika, że wszystkie wartości w wierszu są nie mniejsze od \( \nu_{1,1} \) i \( \nu_{2,2}\) więc
Tabela 2.4
2.4 Kolumna
Wiersz ... Y\(_{1}\) ... Y\(_{2}\) ...
... ... ... ... ... ...
X\(_{1}\) ... \(\nu_{1,1}\) ... \(\nu_{1,2}\) ...
... ... ... ... ... ...
X\(_{2}\) ... \(\nu_{2,1}\) ... \(\nu_{2,2}\) ...
... ... ... ... ... ...

\[ \nu_{1,1} \leqslant \nu_{1,2} \] oraz \( \nu_{2,2} \leqslant \nu_{2,1} \).

Podobnie z definicji punktu siodłowego wynika, że wszystkie wartości w kolumnie są nie większe od \( \nu_{1,1}\) i \( \nu_{2,2}\) więc

\[ \nu_{2,1}\leqslant\nu_{1,1} \] oraz \( \nu_{1,2} \leqslant \nu_{2,2} \).

Z nierówności tych wynika bezpośrednio, że

\[ \nu_{1,1}=\nu_{1,2}=\nu_{2,2}=\nu_{2,1} \;\]

A zatem udowodniliśmy twierdzenie pokazując ponadto dodatkowe dwa punkty siodłowe, które wraz z pierwotnie wybranymi tworzą prostokąt w tabeli wypłat.

Maksimin i minimaks

Poszukiwanie punktów siodłowych metodą redukcji strategii zdominowanych tak jak to pokazaliśmy w przykładzie 2.3 udaje się tylko dla niektórych gier. W ogólnym przypadku taka metoda jest nieskuteczna. W tym rozdziale zajmiemy się ogólną metodą poszukiwania punktów siodłowych za pomocą wyznaczania maksiminu i minimaksu. W tabeli z przykładu 2.3 zmienimy tylko jedną wypłatę, odpowiadającą strategii (C,C) wartość 5 zamienimy na 0. Jak widać z przedstawionej poniżej tabeli wypłat po takiej zmianie żaden a wierszy ani żadna z kolumn nie jest zdominowana przez inne.

Przykład 2.5 Wyznaczanie punktów siodłowych metodą maksiminu i minimaksu.
Maksimin jest maksymalną spośród wypłat minimalnych w wierszach a minimaks jest minimalną spośród wypłat maksymalnych w kolumnach macierzy
2.5 Kolumna minima
wierszy		 maksimin
Wiersz A B C D
A 2 1 3 1 1 1
B -1 0 7 -5 -5
C 9 1 0 1 0
D 1 0 7 -2 -2
maksima kolumn 9 1 7 1
minimaks 1 1

Z definicji punkt siodłowy ta taki, którego wartość jest nie większa on innych w jego wierszu. Poszukajmy zatem najmniejszych wartości w każdym wierszu. W przykładzie 2.5 pokazano je jako "minima wierszy", jeśli gra miałaby punkt siodłowy to musiałby on znaleźć się na tej liście. Z drugiej jednak strony punkt siodłowy to taki, którego wartość jest nie mniejsza od innych w jego kolumnie. Poszukajmy więc maksymalnych wartości w poszczególnych kolumnach. W tabeli 2.5 pokazano je jako "maksima kolumn". Teraz jest jasne, że aby gra miała punkt siodłowy, musi on należeć do obu tych list. Ale maksima kolumn są nie mniejsze niż minima wierszy dlatego jedyną możliwością znalezienia części wspólnej obu tych list jest porównanie minimalnego maksimum kolumn i maksymalnego minimum wierszy. Jeśli te dwie liczby są równe to ich wspólna wartość jest punktem siodłowym oraz wartością gry \( \nu \). Udowodniliśmy w ten sposób twierdzenie

Twierdzenie o maksiminie i minimaksie
Jeśli maksimin i minimaks gry macierzowej są równe to gra posiada punkt lub punkty siodłowe o tej wartości. Punkty te leżą na przecięciu wierszy i kolumn których minima i maksima są równe tej wartości. Jeśli maksimin jest mniejszy od minimaksu to gra nie posiada punktów siodłowych.

Jak widać w przypadku gry 2.5 ma ona dwa punkty siodłowe (A,B) i (A,D) o wartości wspólnej maksiminu i minimaksu \( \nu=1 \). Inne pary strategii o wartości 1, t.j (C,B), (C,D) i (A,E) nie są punktami siodłowymi gdyż nie leżą na przecięciu wierszy i kolumn których zarówno minima jak i maksima są równe 1.

Strategie mieszane

Przykłady gier

przyklado.

Źródło „http://172.16.3.1/ekonofizyka/index.php/TGND:Gry_dwuosobowe_o_sumie_zerowej”