Przejdź do treści
Wróć do wyników wyszukiwania

Równowaga Nasha

Autor metody
John Nash
Rok
1950
Typ
algorithm
Rodzina
Game-theoretic

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Równowaga Nasha to koncepcja rozwiązania w teorii gier, w której żaden gracz nie może jednostronnie odejść od swojej strategii, aby poprawić swoją wypłatę.

Sformalizowany przez Johna Nasha w 1950 roku, algorytm Lemke-Howsona obliczeniowo znajduje równowagi w grach dwumatrycowych, identyfikując pary wierzchołków całkowicie oznakowanych w poltopach strategii.

Intuicja stojąca za metodą

W równowadze Nasha strategia każdego gracza jest najlepszą odpowiedzią na strategię każdego innego gracza. Wyobraźmy sobie sytuację, w której obaj gracze znają strategię drugiego: żaden nie chciałby jej zmienić, ponieważ zrobiłby to tylko na swoją niekorzyść. Algorytm Lemke-Howsona wykorzystuje geometrię wielościanów gry, śledząc etykiety (niespełnione ograniczenia) i dokonując obrotów przez wierzchołki, aż do znalezienia pary całkowicie oznakowanej – konfiguracji, w której żaden z graczy nie ma opłacalnych odejść.

Historia

John Nash udowodnił w swojej dysertacji z 1950 roku, że każda skończona gra posiada co najmniej jedną równowagę Nasha strategii mieszanej. W 1964 roku Lemke i Howson opublikowali pierwszy algorytm konstruktywny do znajdowania tych równowag, przekształcając dowód istnienia Nasha w praktyczną metodę obliczeniową. Ich praca stała się podstawą teorii gier obliczeniowych i ekonomii algorytmicznej.

Kiedy stosować

Użyj analizy równowagi Nasha przy badaniu gier z dwoma graczami i dyskretnymi przestrzeniami strategii lub przy poszukiwaniu w pełni mieszanych równowag. Nadaje się do modelowania problemów konkurencji, negocjacji i koordynacji, gdzie interakcja strategiczna jest kluczowa. Metoda Lemke-Howsona najlepiej działa dla niedegenerowanych gier dwumatrycowych; przypadki zdegenerowane mogą wymagać obliczeń symbolicznych lub perturbacji.

Ograniczenia i uwagi

  • Ograniczony do gier dwumatrycowych (dwóch graczy); rozszerzenie na gry n-osobowe jest problemem NP-trudnym
  • Zawodzi lub staje się nieefektywny w grach zdegenerowanych, gdzie możliwe są wielokrotne obroty wchodzące
  • Może znaleźć tylko jedną równowagę; wiele równowag często istnieje w grach o sumie niezerowej
  • Nie obsługuje bezpośrednio gier dynamicznych ani gier w postaci ekstensywnej bez reformulacji

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Obliczeniowo wydajny do znajdowania równowag Nasha w skończonych grach dwumatrycowych
  • Gwarantuje zbieżność do pary wierzchołków całkowicie oznakowanych dla gier niedegenerowanych
  • Stanowi teoretyczną podstawę łączącą geometrię kombinatoryczną z teorią gier
  • Ma zastosowanie do równowag strategii mieszanych, które są często bardziej realistyczne niż wyniki strategii czystych

Zastosowania

  • Ekonomia: modelowanie konkurencji oligopolistycznej i zachowań cenowych na rynkach
  • Aukcje i projektowanie mechanizmów: analiza strategii licytacji w aukcjach pierwszej ceny i ofertach zamkniętych
  • Cyberbezpieczeństwo: przewidywanie równowag atakujący-obrońca w grach bezpieczeństwa sieci
  • Biologia dzikiej przyrody: analiza ewolucyjnie stabilnych strategii w interakcjach drapieżnik-ofiara

Jak to działa

Jak to działa

1

Przekształć grę dwumatrycową na dwa problemy komplementarności liniowej (LCP), po jednym dla każdego gracza, reprezentujące ich warunki najlepszej odpowiedzi.

2

Przypisz etykiety do krawędzi i wierzchołków poltopów strategii na podstawie tego, które ograniczenia motywacyjne gracza są naruszone.

3

Rozpoczynając od wierzchołka wszystkich jedynek (całkowicie oznakowanego), wykonuj obroty podobne do sympleksu, aby nawigować po poltopie, usuwając i dodając etykiety, aż do odkrycia pary całkowicie oznakowanej.

4

Potwierdź, że strategie obu graczy stanowią wzajemne najlepsze odpowiedzi, sprawdzając, czy żaden z nich nie może poprawić swojej wypłaty, biorąc pod uwagę strategię drugiego gracza.

Częste pułapki

  • Zakładając istnienie unikalnej równowagi; wiele gier ma wiele równowag Nasha o różnych implikacjach wypłat
  • Mylenie równowag strategii mieszanych (losowa gra) z równowagami strategii czystych, prowadzące do błędnej interpretacji zachowań agentów
  • Pomijanie rozróżnienia między warunkami koniecznymi a wystarczającymi dla równowagi; para całkowicie oznakowana spełnia optymalność, ale może nie zostać zrealizowana, jeśli gracze nie mogą koordynować działań

Najczęściej zadawane pytania

Czy gra może nie mieć równowagi Nasha?

Równowagi Nasha strategii czystych mogą nie istnieć (np. Kamień-Papier-Nożyce), ale każda skończona gra ma co najmniej jedną równowagę strategii mieszanej, w której gracze losują akcje z określonymi prawdopodobieństwami.

Czym różni się równowaga strategii mieszanej od równowagi strategii czystej?

W równowadze strategii czystej każdy gracz zobowiązuje się do konkretnej akcji z pewnością. W równowadze strategii mieszanej każdy gracz używa rozkładu prawdopodobieństwa nad akcjami. Równowagi mieszane są często bardziej ogólne i istnieją, gdy czyste nie istnieją.

Dlaczego algorytm Lemke-Howsona jest preferowany nad przeszukiwaniem siłowym?

Algorytm wykorzystuje strukturę poltopową przestrzeni strategii, wykładniczo redukując przestrzeń poszukiwań i osiągając zbieżność w czasie wielomianowym dla gier niedegenerowanych, podczas gdy wyliczenie siłowe staje się niewykonalne wraz ze wzrostem przestrzeni strategii.

Pokrewne metody

Źródła

  1. Nash, J. F. (1950). Equilibrium points in N-person games. Proceedings of the National Academy of Sciences, 36(1), 48-49.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Lemke, C. E., & Howson Jr, J. T. (1964). Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(2), 413-423.

    Otwórz odnośnik DOI
    Skopiowano.