Dla dwuosobowych, skończonych gier o sumie zerowej, różne koncepcje teoretycznych rozwiązań gier: równowaga Nasha, minimax i maximin dają to samo rozwiązanie. Jeśli gracze mogą grać strategią mieszaną, gra zawsze ma równowagę.
PrzykładEdit
|
Blue
Red
|
A | B | C |
|---|---|---|---|
| 1 |
-30
30
|
10
-10
|
-20
20
|
| 2 |
10
-10
|
-20
20
|
20
-20
|
Macierz wypłat w grze jest wygodną reprezentacją. Rozważmy na przykład grę dwuosobową o sumie zerowej, przedstawioną po prawej lub powyżej.
Kolejność gry jest następująca: Pierwszy gracz (czerwony) wybiera w tajemnicy jedną z dwóch akcji 1 lub 2; drugi gracz (niebieski), nieświadomy wyboru pierwszego gracza, wybiera w tajemnicy jedną z trzech akcji A, B lub C. Następnie wybory są ujawniane, a suma punktów każdego gracza jest dotknięta zgodnie z wypłatą za te wybory.
Przykład: Czerwony wybiera akcję 2, a Niebieski akcję B. Po przydzieleniu wypłaty, Czerwony zyskuje 20 punktów, a Niebieski traci 20 punktów.
W tej przykładowej grze obaj gracze znają macierz wypłat i starają się zmaksymalizować liczbę swoich punktów. Czerwony mógłby rozumować w następujący sposób: „Z akcją 2, mogę stracić do 20 punktów i mogę wygrać tylko 20, a z akcją 1 mogę stracić tylko 10, ale mogę wygrać do 30, więc akcja 1 wygląda dużo lepiej”. Z podobnym rozumowaniem Niebieski wybrałby akcję C. Jeśli obaj gracze podejmą te akcje, Czerwony wygra 20 punktów. Jeśli Niebieski przewidzi sposób rozumowania Czerwonego i jego wybór akcji 1, może wybrać akcję B, aby zdobyć 10 punktów. Jeśli Czerwony, z kolei, przewiduje tę sztuczkę i idzie na działanie 2, to wygrywa Czerwony 20 punktów.
Émile Borel i John von Neumann miał fundamentalne spostrzeżenie, że prawdopodobieństwo zapewnia drogę wyjścia z tej zagadki. Zamiast decydować się na konkretną akcję do podjęcia, dwaj gracze przypisują prawdopodobieństwa do swoich działań, a następnie używają losowego urządzenia, które, zgodnie z tymi prawdopodobieństwami, wybiera akcję dla nich. Każdy gracz oblicza prawdopodobieństwa tak, aby zminimalizować maksymalną oczekiwaną stratę punktową, niezależnie od strategii przeciwnika. Prowadzi to do problemu programowania liniowego z optymalnymi strategiami dla każdego gracza. Ta minimax metoda może obliczyć prawdopodobnie optymalne strategie dla wszystkich dwuosobowych gier o sumie zerowej.
Dla przykładu podanego powyżej, okazuje się, że Czerwony powinien wybrać akcję 1 z prawdopodobieństwem 4/7 i akcję 2 z prawdopodobieństwem 3/7, a Niebieski powinien przypisać prawdopodobieństwa 0, 4/7 i 3/7 do trzech akcji A, B i C. Czerwony wygra wtedy średnio 20/7 punktów na grę.
SolvingEdit
Równowaga Nasha dla dwuosobowej gry o sumie zerowej może być znaleziona przez rozwiązanie problemu programowania liniowego. Załóżmy, że gra o sumie zerowej ma macierz wypłat M, w której element Mi,j jest wypłatą otrzymaną, gdy gracz minimalizujący wybierze czystą strategię i, a gracz maksymalizujący wybierze czystą strategię j (tzn. gracz próbujący zminimalizować wypłatę wybiera wiersz, a gracz próbujący zmaksymalizować wypłatę wybiera kolumnę). Przyjmijmy, że każdy element M jest dodatni. Gra będzie miała co najmniej jedną równowagę Nasha. Równowagę Nasha można znaleźć (Raghavan 1994, s. 740) rozwiązując następujący program liniowy w celu znalezienia wektora u:
Minimalizuj: ∑ i u i {{displaystyle ∑sum _{i}u_{i}} Z zastrzeżeniem ograniczeń: u ≥ 0 M u ≥ 1.
Pierwsze ograniczenie mówi, że każdy element wektora u musi być nieujemny, a drugie, że każdy element wektora M u musi wynosić co najmniej 1. Dla wynikowego wektora u, odwrotność sumy jego elementów jest wartością gry. Pomnożenie u przez tę wartość daje wektor prawdopodobieństwa, dając prawdopodobieństwo, że maksymalizujący gracz wybierze każdą z możliwych czystych strategii.
Jeśli macierz gry nie ma wszystkich dodatnich elementów, po prostu dodaj stałą do każdego elementu, który jest wystarczająco duży, aby wszystkie były dodatnie. To zwiększy wartość gry o tę stałą i nie będzie miało żadnego wpływu na strategie mieszane dla równowagi.
Strategie mieszane dla minimalizującego gracza można znaleźć rozwiązując dual danego programu liniowego. Można ją też znaleźć poprzez zastosowanie powyższej procedury do rozwiązania zmodyfikowanej macierzy wypłat, która jest transpozycją i negacją M (dodając stałą, aby była dodatnia), a następnie rozwiązanie wynikowej gry.
Jeśli wszystkie rozwiązania programu liniowego zostaną znalezione, będą one stanowić wszystkie równowagi Nasha dla gry. I odwrotnie, każdy program liniowy może być przekształcony w grę dwuosobową o sumie zerowej poprzez zmianę zmiennych, która sprowadza go do postaci powyższych równań. Zatem takie gry są równoważne programom liniowym, w ogólności.
Uniwersalne rozwiązanieEdit
Jeśli unikanie gry o sumie zerowej jest wyborem działania z pewnym prawdopodobieństwem dla graczy, to unikanie jest zawsze strategią równowagi dla co najmniej jednego gracza w grze o sumie zerowej. Dla każdej gry o sumie zerowej, w której losowanie zera jest niemożliwe lub niewiarygodne po rozpoczęciu gry, takiej jak poker, nie ma strategii równowagi Nasha innej niż unikanie gry. Nawet jeśli istnieje wiarygodny zerowy remis po rozpoczęciu gry o sumie zerowej, nie jest on lepszy niż strategia unikania. W tym sensie, to jest interesujące, aby znaleźć reward-as-you-go w optymalnych obliczeń wyboru przeważa nad wszystkich dwóch graczy zero-sum gry w odniesieniu do rozpoczęcia gry lub nie.
Najbardziej powszechne lub prosty przykład z subfield psychologii społecznej jest pojęcie „pułapek społecznych”. W niektórych przypadkach dążenie do indywidualnego interesu osobistego może zwiększyć zbiorowy dobrobyt grupy, ale w innych sytuacjach wszystkie strony dążące do osobistego interesu powoduje wzajemnie destrukcyjne zachowanie.
ComplexityEdit
To zostało teoretyzowane przez Roberta Wrighta w jego książce Nonzero: The Logic of Human Destiny, że społeczeństwo staje się coraz bardziej non-zero-sum as it becomes more complex, specialized, and interdependent.
.