Pierwszy model gry, któremu przyjrzymy się, to taki, w którym wszyscy gracze podejmują działania jednocześnie, a wynik gry opiera się na profilu działań wybranych w ten sposób. (Właściwie nie jest istotne, aby akcje odbywały się w tym samym czasie; ważne jest to, że żaden gracz nie ma wiedzy o wyborach innych graczy.) Te gry nazywane są grami w normalnej formie. Gra w normalnej formie jest zdefiniowana przez trzy elementy:
- Gracze lub agenci, którzy będą podejmować decyzje. Najwięcej uwagi poświęcono grom dla dwóch graczy, chociaż gry dla n-osoby dla n > 2 są również powszechne. Graczom podajemy nazwiska pisane wielkimi literami, takie jak Ali i Bo lub O i E.
- Akcje, które gracze mogą wybrać. Podamy akcje małymi nazwami, takimi jak jeden lub zeznaj. Gracze mogą, ale nie muszą mieć dostępnego tego samego zestawu akcji.
- Funkcja wypłaty, która daje każdemu graczowi użyteczność dla każdej kombinacji działań wszystkich graczy. W grach dwuosobowych funkcję wypłat dla gracza można przedstawić za pomocą macierzy, w której znajduje się wiersz dla każdej możliwej akcji jednego gracza oraz kolumna dla każdego możliwego wyboru drugiego gracza: wybrany wiersz i wybrany kolumna definiuje komórkę macierzy, która jest oznaczona wypłatą dla odpowiedniego gracza. W przypadku dwóch graczy konwencjonalnie łączy się dwie macierze w jedną macierz wypłat, w której każda komórka jest oznaczona wypłatami dla obu graczy.
Aby zilustrować te pomysły, spójrzmy na przykładową grę o nazwie Morra z dwoma palcami. W tej grze dwóch graczy, O i E, pokazuje jednocześnie jeden lub dwa palce. Niech łączna liczba wyświetlanych palców wynosi f . Jeśli f jest nieparzyste, O pobiera f dolarów od E; a jeśli f jest parzyste, E pobiera f dolarów od O.1 Macierz wypłat dla dwupalcowej Morry wygląda następująco:
Mówimy, że E jest odtwarzaczem wierszy, a O jest odtwarzaczem kolumn. Na przykład prawy dolny róg pokazuje, że gdy gracz O wybiera akcję drugą, a E również wybiera dwie, wypłata wynosi +4 dla E i 4 dla O. Przed analizą dwupalcowej Morry warto zastanowić się, dlaczego gra -idee teoretyczne są w ogóle potrzebne: dlaczego nie możemy sprostać wyzwaniu stojącemu przed (powiedzmy) graczem E, korzystając z aparatu teorii decyzji i maksymalizacji użyteczności, z którego korzystaliśmy w innych miejscach książki? Aby zobaczyć, dlaczego potrzebne jest coś innego, załóżmy, że E próbuje znaleźć najlepszą akcję do wykonania. Alternatywy to jedna lub dwie. Jeśli E wybierze jeden, wypłata wyniesie +2 lub -3. Która wypłata faktycznie otrzyma E, będzie jednak zależeć od wyboru dokonanego przez O: jedyne, co E może zrobić jako gracz w rzędzie, to wymusić, aby wynik gry znajdował się w określonym rzędzie. Podobnie O wybiera tylko kolumnę. Aby optymalnie wybrać pomiędzy tymi możliwościami, E musi wziąć pod uwagę, jak O będzie działać jako racjonalny decydent. Ale O z kolei powinien wziąć pod uwagę fakt, że E jest racjonalnym decydentem. Tak więc podejmowanie decyzji w ustawieniach wieloagentowych ma zupełnie inny charakter niż podejmowanie decyzji w ustawieniach z jednym agentem, ponieważ gracze muszą brać pod uwagę tok rozumowania innych graczy. Rolą koncepcji rozwiązań w teorii gier jest próba doprecyzowania tego rodzaju rozumowania. Termin strategia jest używany w teorii gier na określenie tego, co wcześniej nazywaliśmy polityką. Czysta strategia to polityka deterministyczna; w grze z jednym ruchem czysta strategia to tylko jedno działanie. Jak zobaczymy poniżej, w wielu grach agent może lepiej radzić sobie ze strategią mieszaną, która jest losową polityką, która wybiera działania zgodnie z prawdopodobieństwem dystrybucji. Strategia mieszana, która wybiera działanie a z prawdopodobieństwem p i działanie b w przeciwnym razie jest napisana [p:a; (1-p):b]. Na przykład strategia mieszana dla Morry z dwoma palcami może mieć postać [0:5:jeden;0:5:dwa]. Profil strategii to przypisanie strategii każdemu graczowi; biorąc pod uwagę profil strategii, wynik gry jest wartością liczbową dla każdego gracza – jeśli gracze używają strategii mieszanych, musimy użyć oczekiwanej użyteczności. Jak więc agenci powinni decydować o działaniu w grach takich jak Morra? Teoria gier dostarcza szeregu koncepcji rozwiązań, które próbują zdefiniować racjonalne działanie w odniesieniu do przekonań agenta na temat przekonań drugiego agenta. Niestety nie ma jednej koncepcji idealnego rozwiązania: problematyczne jest zdefiniowanie, co oznacza „racjonalny”, gdy każdy agent wybiera tylko część profilu strategii, która determinuje wynik. Przedstawiamy naszą pierwszą koncepcję rozwiązania poprzez prawdopodobnie najsłynniejszą grę w kanonie teorii gier — dylemat więźnia. Motywem tej gry jest następująca historia: Dwóch domniemanych włamywaczy, Ali i Bo, zostaje złapanych na gorącym uczynku w pobliżu miejsca włamania i przesłuchiwanych oddzielnie. Prokurator oferuje każdemu układ: jeśli złożysz zeznania przeciwko swojemu partnerowi jako przywódcy szajki z włamaniami, wyjdziesz wolny za bycie współpracownikiem, podczas gdy twój partner będzie skazany na 10 lat więzienia. Jeśli jednak oboje zeznacie przeciwko sobie, oboje dostaniecie 5 lat. Ali i Bo wiedzą również, że jeśli oboje odmówią złożenia zeznań, każdy z nich będzie służył tylko 1 rok za mniejszy zarzut posiadania skradzionej własności. Teraz Ali i Bo stają przed tak zwanym dylematem więźnia: czy zeznawać, czy odmówić? Będąc racjonalnymi agentami, Ali i Bo chcą zmaksymalizować swoją oczekiwaną użyteczność, co oznacza zminimalizowanie liczby lat więzienia – każdy jest obojętny na dobro drugiego gracza. Dylemat więźnia ujmuje następująca macierz wypłat:
Teraz postaw się na miejscu Ali. Potrafi przeanalizować macierz wypłat w następujący sposób:
- Załóżmy, że Bo gra zeznaje. Potem dostaję 5 lat, jeśli zeznaję i 10 lat, jeśli nie, więc w takim przypadku zeznawanie jest lepsze.
- Z drugiej strony, jeśli Bo gra w odmowę, wtedy wychodzę na wolność, jeśli zeznam, i dostaję 1 rok, jeśli odmówię, więc zeznawanie jest również lepsze w tym przypadku.
- Więc bez względu na to, co Bo zdecyduje się zrobić, byłoby lepiej, gdybym zeznawał. Ali odkrył, że zeznawanie jest dominującą strategią w grze.
Mówimy, że strategia s dla gracza p silnie dominuje w strategii s0, jeśli wynik dla s jest lepszy dla p niż wynik silnej dominacji dla s’, dla każdego wyboru strategii przez drugiego gracza. Strategia s słabo dominuje nad s’, jeśli s jest lepsze niż s’ w co najmniej jednym profilu strategii i nie gorsze w żadnym innym. Strategia dominująca to strategia, która dominuje nad wszystkimi innymi. Powszechnym założeniem w teorii gier jest to, że racjonalny gracz zawsze wybiera strategię dominującą i unika zdominowanej strategii J. Będąc racjonalnym – a przynajmniej nie chcąc być uważanym za irracjonalne – Ali wybiera dominującą strategię. Nietrudno zauważyć, że rozumowanie Bo będzie identyczne: dojdzie również do wniosku, że zeznawanie jest dla niego strategią dominującą i zdecyduje się nią grać. Rozwiązaniem gry, zgodnie z dominującą analizą strategii, będzie to, że obaj gracze wybiorą zeznania, a w konsekwencji obaj będą odsiedzieć 5 lat więzienia. W sytuacji takiej jak ta, gdy wszyscy gracze wybierają strategię dominującą, rezultatem jest równowaga strategii dominującej. Jest to „równowaga”, ponieważ żaden gracz nie ma motywacji, aby odejść od swojej części: z definicji, gdyby to zrobił, nie mógłby postąpić lepiej, a może postąpić gorzej. W tym sensie dominująca równowaga strategii jest bardzo silną koncepcją rozwiązania. Wracając do dylematu więźnia, widzimy, że dylemat polega na tym, że dominujący wynik równowagi strategii, w której obaj gracze zeznają, jest gorszy dla obu graczy niż wynik, który uzyskaliby, gdyby obaj odmówili zeznań. Wynik (odmowa; odmowa) dałby obu graczom tylko jeden rok więzienia, co byłoby lepsze dla nich obu niż 5 lat, które każdy z nich odsiedział, gdyby wybrali dominującą równowagę strategiczną. Czy jest jakiś sposób, aby Ali i Bo doszli do wyniku (odmowa; odmowa)? Z pewnością oboje mogą odmówić składania zeznań, ale trudno jest wyobrazić sobie, jak racjonalni agenci mogli dokonać takiego wyboru, biorąc pod uwagę sposób, w jaki gra jest ustawiona. Pamiętaj, że jest to gra bez współpracy: nie mogą ze sobą rozmawiać, więc nie mogą zawrzeć wiążącej umowy o odmowę. Możliwe jest jednak dotarcie do rozwiązania (odrzuć; odrzuć), jeśli zmienimy grę. Moglibyśmy to zmienić w grę kooperacyjną, w której agenci mogą zawrzeć wiążące porozumienie. Albo możemy przejść na grę powtórną, w której gracze wiedzą, że spotkają się ponownie – zobaczymy, jak to działa poniżej. Alternatywnie gracze mogą mieć przekonania moralne, które zachęcają do współpracy i uczciwości. Ale to by oznaczało, że mają różne funkcje użytkowe i znowu grają w inną grę. Obecność dominującej strategii dla konkretnego gracza znacznie upraszcza proces podejmowania decyzji dla tego gracza. Kiedy Ali zda sobie sprawę, że składanie zeznań jest dominującą strategią, nie musi inwestować żadnego wysiłku, próbując dowiedzieć się, co zrobi Bo, ponieważ wie, że bez względu na to, co zrobi Bo, zeznanie będzie jej najlepszą odpowiedzią. Jednak większość gier nie ma ani dominujących strategii, ani dominującej równowagi strategii. Rzadko zdarza się, że pojedyncza strategia jest najlepszą odpowiedzią na wszystkie możliwe strategie odpowiedników. Kolejna koncepcja rozwiązania, którą rozważamy, jest słabsza niż równowaga strategii dominującej, ale ma znacznie szersze zastosowanie. Nazywa się równowagą Nasha i nosi imię Johna Forbesa Nasha, Jr. (1928-2015), który studiował ją w 1950 r. praca dyplomowa – praca, za którą otrzymał Nagrodę Nobla w 1994 roku. Profil strategii jest równowagą Nasha, jeśli żaden gracz nie mógł jednostronnie zmienić swojej strategii i w konsekwencji otrzymać wyższą wypłatę, przy założeniu, że pozostali gracze pozostali przy swoich wyborach strategicznych . Tak więc w równowadze Nasha każdy gracz gra jednocześnie w najlepszą odpowiedź na wybory swoich odpowiedników. Równowaga Nasha reprezentuje stabilny punkt w grze: stabilny w tym sensie, że żaden gracz nie ma racjonalnej motywacji do odstępstwa. Równowagi Nasha są jednak lokalnymi punktami stabilnymi: jak zobaczymy, gra może zawierać wiele równowag Nasha. Ponieważ strategia dominująca jest najlepszą odpowiedzią na wszystkie strategie odpowiadające, wynika z tego, że jakakolwiek równowaga strategii dominującej musi być również równowagą Nasha (Ćwiczenie 17.EQIB). W dylematach więźnia istnieje zatem unikalna dominująca równowaga strategii, która jest jednocześnie unikalną równowagą Nasha. Poniższa przykładowa gra pokazuje, po pierwsze, że czasami gry nie mają dominujących strategii, a po drugie, że niektóre gry mają wiele równowag Nasha.
Łatwo jest zweryfikować, czy w tej grze nie ma strategii dominujących dla żadnego z graczy, a zatem nie ma równowagi strategii dominującej. Jednak profile strategii (t; l) i (b; r) są równowagami Nasha. Oczywiście w interesie obu agentów jest dążenie do tej samej równowagi Nasha – albo (t; l) albo (b; r) – ale ponieważ jesteśmy w domenie teorii gier niekooperacyjnych, gracze muszą osiągnąć dokonywanie wyborów samodzielnie, bez wiedzy o wyborach innych i bez możliwości zawarcia z nimi porozumienia. Jest to przykład problemu z koordynacją: gracze chcą koordynować swoje działania globalnie, tak aby obaj wybierali działania prowadzące do tej samej równowagi, ale muszą to robić wyłącznie przy użyciu lokalnego procesu decyzyjnego. Zaproponowano szereg podejść do rozwiązywania problemów z koordynacją. Jednym z pomysłów są punkty centralne. Centralnym punktem w grze jest wynik, który w pewien sposób wyróżnia się dla graczy jako „oczywisty” wynik, na podstawie którego można koordynować ich wybory. Nie jest to oczywiście dokładna definicja — jej znaczenie będzie zależeć od rozgrywanej gry. Jednak w powyższym przykładzie jest jeden oczywisty punkt centralny: wynik (t; l) dałby obu graczom znacznie wyższą użyteczność niż uzyskaliby, gdyby skoordynowali się na (b; r). Z punktu widzenia teorii gier oba wyniki są równowagą Nasha — ale rzeczywiście byłby to perwersyjny gracz, który spodziewał się koordynować (b; r). Niektóre gry nie mają równowagi Nasha w czystych strategiach, co ilustruje następująca gra, zwana dopasowywaniem groszy. W tej grze Ali i Bo jednocześnie wybierają jedną stronę monety, albo orzełków: jeśli dokonają tych samych wyborów, Bo daje Ali 1 USD, natomiast jeśli dokonają innych wyborów, Ali daje Bo 1 USD:
Zachęcamy czytelnika do sprawdzenia, czy gra nie zawiera dominujących strategii i że żaden wynik nie jest równowagą Nasha w czystych strategiach: w każdym wyniku jeden gracz żałuje swojego wyboru i wolałby wybrać inaczej, biorąc pod uwagę wybór drugiego gracza . Aby znaleźć równowagę Nasha, sztuczka polega na użyciu strategii mieszanych – aby umożliwić graczom losowe dokonywanie wyborów. Nash udowodnił, że każda gra ma przynajmniej jedną równowagę Nasha w strategiach mieszanych J. To wyjaśnia, dlaczego równowaga Nasha jest tak ważną koncepcją rozwiązania: inne koncepcje rozwiązań, takie jak równowaga strategii dominującej, nie gwarantują istnienia w każdej grze, ale zawsze otrzymujemy rozwiązanie, jeśli szukamy równowagi Nasha ze strategiami mieszanymi. W przypadku dopasowywania groszy mamy równowagę Nasha w strategiach mieszanych, jeśli obaj gracze wybierają orła i reszka z równym prawdopodobieństwem. Aby zobaczyć, że ten wynik jest rzeczywiście równowagą Nasha, załóżmy, że jeden z graczy wybrał wynik z prawdopodobieństwem innym niż 0:5. Wtedy drugi gracz mógłby to wykorzystać, wkładając całą swoją wagę w konkretną strategię. Załóżmy na przykład, że Bo grał orła z prawdopodobieństwem 0:6 (a więc reszką z prawdopodobieństwem 0:4). Wtedy Ali zrobiłby wszystko, żeby grać głową z pewnością. Łatwo więc zauważyć, że Bo grający głową z prawdopodobieństwem 0:6 nie może stanowić części żadnej równowagi Nasha.