TGND:Gry dwuosobowe o sumie zerowej

Z Skrypty dla studentów Ekonofizyki UPGOW

(Różnice między wersjami)

Wersja z 10:18, 5 wrz 2010

Gry dwuosobowe o sumie zerowej

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.

Punkt siodłowy: Punkt macierzy wypłat, którego wartość jest nie mniejsza od innych wartości w jego wierszu oraz nie większa od innych wartości w jego kolumnie nazywamy punktem siodłowym a wartość wygranej \( \nu \) w tym punkcie 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 Kolumny. Jednak 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\)