Teoria Gier: Równowaga Nasha i Dylemat Więźnia

Trzy składniki, jedna macierz

Teoria gier jest matematyką sytuacji, w której wynik agenta zależy nie tylko od jego własnego wyboru, ale także od wyborów innych. Każda gra opiera się na trzech składnikach: zbioru graczy, zbiorze strategii dostępnych dla każdego oraz funkcji wypłaty, która mapuje każdą kombinację wyborów na wartość dla każdego gracza. Dla dwóch graczy ta funkcja wypłaty wygodnie jest przedstawiana w postaci macierzy: wiersze to opcje Gracza 1, kolumny to opcje Gracza 2, a każdy komórka zawiera parę wynikowych wyników.

Najbardziej znaną macierzą wypłat w tej dziedzinie jest Utrata Wyboru. Dwóch podejrzanych, przesłuchiwanych osobno, może każda Współpracować (być cicho) lub Zdradać (zwidecz nię). Jeśli oboje współpracują, każdy odbywa jeden rok więzienia. Jeśli oboje zdradzą, każdy odbyje dwa lata. Jeśli jeden zdradza, a drugi współpracuje, zdrajca zostaje zwolniony, a współpracownik odbywa trzy lata więzienia. Rozważ to z perspektywy każdego gracza: niezależnie od tego, co robi drugi gracz, zdradzenie zawsze skrótuje swój wyrok o rok. Zdrada jest strategią dominującą – wybór, który jest najlepszy bez względu na to, co robi przeciwnik, więc nie ma potrzeby przewidywania jego wyborów.

Gracz 2: C Gracz 2: D Gracz 1: C (-1, -1) (-3, 0) Gracz 1: D ( 0, -3) (-2, -2) Obie dominujące strategie -> (D, D), wypłata (-2,-2) Jednak (C, C) z wypłatą (-1,-1) jest korzystniejsze dla obu graczy Obaj gracze, rozumiejąc prawidłowo sytuację, znajdują się w gorszej sytuacji niż gdyby jakimś cudem zgodzili się współpracować. Ta przepaść między indywidualnie opłacalnymi wyborami a zbiorowym lepszym wynikiem to centralne napięcie, które teoria gier ma formalizować – i pojawia się wszędzie, od wyścigów zbrojenia po wydatki na reklamę, po nadmierny połap do wspólnych wód.

              Player 2: C        Player 2: D
Player 1: C    (-1, -1)          (-3,  0)
Player 1: D    ( 0, -3)          (-2, -2)

both dominant strategies -> (D, D), payoff (-2,-2)
yet (C, C) with payoff (-1,-1) is better for both

Równowaga Nasha: nikt nie może zrobić tego lepiej sam

Wkład Johna Nha z 1950 roku to ogólne określenie stabilnego wyniku, które ma zastosowanie do każdej gry, a nie tylko do dylematu więźnia. Równowaga Nasha to zestaw strategii, po jednym na gracza, taki że żaden gracz nie może poprawić swojej własnej wypłaty, zmieniając strategię, podczas gdy pozostali gracze trzymają się swoich wyborów. Ruch każdego gracza jest najlepszą odpowiedzią na to, co robią wszyscy inni. Nha udowodniono (korzystając z twierdzenia o punkcie stałym Kakutani'ego) że każda skończona gra ma przynajmniej jedno takie równowaga, być może taka, w której gracze losują swoje opcje zamiast zobowiązywać się do pojedynczego czystego wyboru (strategia mieszana).

W dylemacie więźnia (Zdrada, Zdrada) jest to jedyna równowaga Nasha: biorąc pod uwagę, że przeciwnik zdradza, zdrada nadal jest najlepszą odpowiedzią dla gracza, więc żaden z graczy nie ma motywacji do zmiany strategii jednostronnie. W grze Kamień, Nożyce, Papier żadna czysta strategia nie przetrwa przewidywania, więc jedyną równowagą Nasha jest taki, że każdy gracz losuje równomiernie spośród trzech opcji – każdy ruch wykonywany jest z częstotliwością trzeciej części, dokładnie taka jak pozostawia niezdecydowanego przeciwnika wobec wszystkich własnych wyborów. Niektóre gry mają więcej niż jedną równowagę; w polowaniu na dzikie zwierzę dwa łowcy mogą wspólnie zwabić dzika (wysoka nagroda, wymaga zaufania) lub każdy złapać króliczka osobno (niższa, ale gwarantowana). Zarówno (Polowanie na dzika, Polowanie na dzika) jak i (Króliki, Króliki) są równowagami Nasha, a to, na którą z nich spoczywa populacja, jest kwestią historii i oczekiwań, a nie tylko maksymalizacji wypłaty.

Powtarzanie wszystko zmienia

Jednorazowe rozwiązanie Problemu Więźnia Przestrzennego nie pozostawia miejsca na budowanie reputacji. Graj w to wielokrotnie z tym samym przeciwnikiem, a zdrajstwo dzisiaj może zostać ukaranute jutro – groźba przyszłych represji staje się sama w sobie strategicznym atutem. W 1980 roku polityczny naukowiec Robert Axelrod przeprowadził komputerowy turniej, zapraszając badaczy do zgłaszania strategii dla iterowanego Problemu Więźnia Przestrzennego. Najprostsza propozycja, Tit-for-Tat – współpraca jako pierwsza, a następnie kopiowanie tego, co zrobił ostatniego przeciwnik – wygrała przekonująco i wygrała również ponownie w ponownym turnieju z większą liczbą uczestników. Jego cztery cechy (dobre, retaliacyjne, przebaczające, proste) okazały się ważniejsze niż jakiekolwiek ilość sprytu przeciwko różnorodnej populacji rywali.

Strategie przetrwania: teoria gry ewolucyjnej

John Maynard Smith i George Price przeformułowali pytanie biologicznie: zamiast pytać, jaką strategię powinien wybrać racjonalny jednostka, należy zapytać, jaka strategia może przetrwać w populacji poddawanej selekcji naturalnej. Strategia to Ewolucyjnie Stabilna Strategia (ESS), jeśli po przejęciu dominacji przez populację, niewielka grupa mutantów grająca coś innego nie jest w stanie inwazji i rozprzestrzeniania się. Przykładem z podręcznika są Sokoły i Gołębie: sokoły zawsze eskalują pojedynek o zasób i walczą do momentu, aż ktoś zostaje raniony; gołębie wykazują się, ale wycofują się natychmiast po eskalacji przez słonia. Populacja składająca się wyłącznie z gołębi jest nieinwazyjna dla mutantnego słonia, który wygrywa każdy pojedynek bez obrażeń. Populacja składająca się wyłącznie z sokóła jest nieinwazyjna dla mutantnego gołębia, który unika kosztownych walk. Żadna czysta strategia nie jest stabilna — zamiast tego populacja ustala mieszany poziom częstotliwości równowagi.

Warunek ESS: payoff(I, I) > payoff(J, I) dla każdej mutantnej strategii J Częstość występowania równowagi Sokoł-Gołąb: p* = V / C (gdy V < C) W = wartość zasobu, C = koszt przegranej walki Ten pogląd na poziomie populacji generalizuje się dalej: agenci umieszczani na przestrzennej siatce, którzy wchodzą w interakcje tylko z sąsiadami, mogą utrzymać współpracę nawet bez powtórnego pojedynczego grania lub wzajemności, ponieważ kooperanci zgrupowują się razem i chronią przed wykorzystywaniem przez pobliskich defectorów. Lokalna struktura sama w sobie może uratować współpracę od losu, którego nie może uniknąć dobrze wymieszana populacja.

ESS condition: payoff(I, I) > payoff(J, I)  for every mutant strategy J

Hawk-Dove equilibrium frequency of hawks:
  p* = V / C     (when V < C)
  V = value of the resource, C = cost of losing a fight

Jak symulacja tutaj to modeluje

Symulacja Teorii Gier na tej stronie umieszcza populację agentów na planszy, każdy z własną strategią – współpraca lub ucieczka, albo prawdopodobieństwo każdej z nich, i grają w grze o rodzaju więziennego wyboru przeciwko sąsiadom za każdym razem. Po każdym kole agent może naśladować bardziej udanych sąsiadów lub mutować, co jest dokładnie zasadą aktualizacji badaną w teorii gier ewolucyjnych: nagroda decyduje o reprodukcji, a nie o racjonalnej deliberacji. Obserwowanie skupisk współpracowników przetrwalających, kurczących się lub rozprzestrzeniających się w miarę jak zmieniają się parametry nagrody jest bezpośrednim wizualnym dowodem na tworzenie się, łamanie się lub brak istnienia ESS – można delikatnie zmienić wartość nagrody za wykorzystywanie współpracownika i zobaczyć, jak cała populacja zachowania skręci.

Zasięg Teorii Gier wykracza daleko poza dwukrotne plansze. W ekonomii, równowaga Nasha przewiduje ceny w oligopolach i leży u podstaw projektowania aukcji – aukcja Vickrey’a (z drugą ceną) sprawia, że ​​oferowanie prawdziwej wartości jest dominującą strategią. W naukach politycznych, wzajemnie zagwarantowana zniszczenie jest analizowane jako równowaga Nasha utrzymywana wyłącznie przez katastrofalne koszty odchylenia. W informatyce, paradoks Braessa pokazuje, że dodanie drogi do sieci może pogorszyć podróż każdego kierowcy, gdy wszyscy działają w sposób egoistyczny, prowadząc do nowej równowagi. Wspólnym mianownikiem we wszystkich tych przypadkach jest ta sama logika macierzy przedstawiona powyżej: zdefiniuj graczy, strategie, nagrody i zapytaj, co nikt nie może poprawić samodzielnie.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz the simulation i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.