Do tej pory przyglądaliśmy się tylko grom, które trwają jeden ruch. Najprostszym rodzajem gry z wieloma ruchami jest gra powtarzana (zwana również grą iterowaną), w której gracze wielokrotnie rozgrywają rundy gry z jednym ruchem, zwanej grą etapową. Strategia w powtarzanej grze określa wybór akcji dla każdego gracza w każdym kroku czasowym dla każdej możliwej historii poprzednich wyborów graczy. Najpierw spójrzmy na przypadek, w którym gra etapowa powtarza się o ustalonej, skończonej i wzajemnie znanej liczbie rund – wszystkie te warunki są wymagane, aby poniższa analiza zadziałała. Załóżmy, że Ali i Bo grają w powtórzoną wersję dylematu więźnia i oboje wiedzą, że muszą rozegrać dokładnie 100 rund gry. W każdej rundzie zostaną zapytani, czy mają zeznawać, czy odmówić, i otrzymają zapłatę za tę rundę zgodnie z zasadami dylematu więźnia, który widzieliśmy powyżej. Na koniec 100 rund obliczamy ogólną wypłatę dla każdego gracza, sumując wypłaty tego gracza w 100 rundach. Jakie strategie powinni wybrać Ali i Bo, aby zagrać w tę grę? Rozważ następujący argument. Oboje wiedzą, że setna runda nie będzie grą powtórzoną – to znaczy, że jej wynik nie może mieć wpływu na kolejne rundy. Tak więc w 100. rundzie grają w grę z dylematem jednego więźnia.
Jak widzieliśmy powyżej, wynik 100. rundy będzie (zeznaj; zeznaj) dominującą strategią równowagi dla obu graczy. Ale po ustaleniu setnej rundy, 99. runda może nie mieć wpływu na kolejne rundy, więc ona też ustąpi (zeznawać; zeznawać). Dzięki temu indukcyjnemu argumentowi obaj gracze wybiorą zeznania w każdej rundzie, za co otrzymają łącznie 500 lat więzienia. Ten rodzaj rozumowania jest znany jako indukcja wsteczna i odgrywa fundamentalną rolę w teorii gier. Jeśli jednak odrzucimy jeden z trzech warunków – ustalony, skończony lub wzajemnie znany – wtedy argument indukcyjny nie będzie słuszny. Załóżmy, że gra powtarza się nieskończoną liczbę razy. Matematycznie strategia dla gracza w nieskończenie powtarzanej grze to funkcja, która odwzorowuje każdą możliwą skończoną historię gry na wybór w grze etapowej dla tego gracza w odpowiedniej rundzie. W ten sposób strategia analizuje to, co wydarzyło się wcześniej w grze, i decyduje, jakiego wyboru dokonać w bieżącej rundzie. Ale nie możemy przechowywać nieskończonej tabeli w skończonym komputerze. Potrzebujemy skończonego modelu strategii dla gier, które będą rozgrywane w nieskończonej liczbie rund. Z tego powodu standardem jest przedstawianie strategii dla nieskończenie powtarzanych gier jako automatów skończonych (FSM) z wyjściem. Rysunek ilustruje szereg strategii FSM dla iterowanego dylematu więźnia.
Rozważ strategię Tit-za-Tat. Każdy owal jest stanem maszyny, a wewnątrz owalu znajduje się wybór, którego dokonałaby strategia, gdyby maszyna była w tym stanie. Z każdego stanu mamy jedną krawędź wychodzącą dla każdego możliwego wyboru agenta odpowiednika: podążamy za krawędzią wychodzącą odpowiadającą wyborowi dokonanemu przez drugą, aby znaleźć następny stan maszyny. Na koniec jeden stan jest oznaczony strzałką przychodzącą, wskazując, że jest to stan początkowy. Tak więc w przypadku TIT-FOR-TAT maszyna uruchamia się w stanie odpadu; jeśli przeciwnik zagra odmowę, pozostaje w stanie odmowy, natomiast jeśli przeciwnik zagra zeznaje, przechodzi do stanu zeznania. Pozostanie w stanie zeznań tak długo, jak jego odpowiednik będzie zeznawał, ale jeśli kiedykolwiek jego odpowiednik zagra odmowę, powróci do stanu odmowy. Podsumowując, TIT-FOR-TAT rozpocznie się od wybrania odmowy, a następnie po prostu skopiuje to, co jego odpowiednik zrobił w poprzedniej rundzie. Strategie HAWK i DOVE są prostsze: HAWK po prostu gra zeznania w każdej rundzie, podczas gdy DOVE po prostu gra odmowę w każdej rundzie. Strategia GRIM jest nieco podobna do TIT-FOR-TAT, ale z jedną ważną różnicą: jeśli kiedykolwiek jej odpowiednik zeznaje, to zasadniczo zamienia się w HAWK: gra zeznawanie w nieskończoność. Podczas gdy TIT-FOR-TAT jest wyrozumiały, w tym sensie, że zareaguje na późniejszą odmowę, odwzajemniając to samo, z GRIM nie ma odwrotu. Samo zagranie zeznaj raz spowoduje karę (zagranie zeznania), która trwa wiecznie. (Czy widzisz, co robi TAT-FOR-TIT?) Następnym problemem związanym z nieskończenie powtarzanymi grami jest to, jak zmierzyć użyteczność nieskończonej sekwencji wypłat. Tutaj skupimy się na podejściu do granicy średnich — zasadniczo oznacza to branie średniej z otrzymanych użyteczności w ciągu nieskończonego ciągu. Przy takim podejściu, mając nieskończoną sekwencję wypłat (U0,U1,U2,…), definiujemy użyteczność sekwencji dla odpowiedniego gracza jako:
Nie można zagwarantować, że ta wartość będzie zbieżna dla dowolnych sekwencji użyteczności, ale jest to gwarantowane dla sekwencji użyteczności, które są generowane, jeśli używamy strategii FSM. Aby to zobaczyć, zauważ, że jeśli strategie FSM grają przeciwko sobie, to w końcu FSM ponownie wejdą w konfigurację, w której byli poprzednio, w którym to momencie zaczną się powtarzać. Dokładniej, każda sekwencja użyteczności wygenerowana przez strategie FSM będzie składać się ze skończonej (prawdopodobnie pustej) niepowtarzającej się sekwencji, po której następuje niepusta skończona sekwencja, która powtarza się nieskończenie często. Aby obliczyć średnią użyteczność otrzymaną przez gracza na tej nieskończonej sekwencji, musimy po prostu obliczyć średnią na skończonej powtarzającej się sekwencji. W dalszej części założymy, że gracze w nieskończenie powtarzanej grze po prostu wybierają maszynę skończonych stanów, aby zagrać w grę w ich imieniu. Nie nakładamy żadnych ograniczeń na te maszyny: mogą być tak duże i rozbudowane, jak chcą gracze. Gdy wszyscy gracze wybiorą maszynę skończonych stanów, aby grać w ich imieniu, możemy obliczyć wypłaty dla każdego gracza, korzystając z podejścia limitu środków, jak opisano powyżej. W ten sposób nieskończenie powtarzana gra sprowadza się do normalnej gry, aczkolwiek z nieskończenie wieloma możliwymi strategiami dla każdego gracza. Zobaczmy, co się stanie, gdy rozegramy nieskończenie powtarzający się dylemat więźnia, stosując strategie z rysunku. Po pierwsze, załóżmy, że Ali i Bo wybierają DOVE.
Nietrudno zauważyć, że ta para strategii nie tworzy równowagi Nasha: każdy z graczy zrobiłby lepiej, gdyby zmienił swój wybór na HAWK. Załóżmy więc, że Ali przełącza się na HAWK:
To najgorszy możliwy wynik dla Bo; i ta para strategii znowu nie jest równowagą Nasha. Bo zrobiłby lepiej, wybierając również HAWK:
Ta para strategii tworzy równowagę Nasha, ale niezbyt interesującą – zabiera nas mniej więcej do punktu, w którym zaczęliśmy w wersji gry z jednym strzałem, w której obaj gracze zeznają przeciwko sobie. Ilustruje kluczową właściwość nieskończenie powtarzanych gier: równowaga Nasha w grze scenicznej będzie utrzymywana jako równowaga w nieskończenie powtarzanej wersji gry. Jednak nasza historia jeszcze się nie skończyła. Załóżmy, że Bo przeszedł na GRIM:
Tutaj Bo nie robi gorzej niż gra w HAWK: w pierwszej rundzie Ali zeznaje, podczas gdy Bo gra odmawia, ale to skłania Bo do zeznawania na zawsze: utrata użyteczności w pierwszej rundzie znika w limicie. Ogólnie rzecz biorąc, obaj gracze otrzymują taką samą użyteczność, jak gdyby obaj grali w HAWK. Ale o to chodzi: te strategie nie tworzą równowagi Nasha, ponieważ tym razem Ali ma korzystne odchylenie – do GRIM. Jeśli obaj gracze wybiorą GRIM, dzieje się tak:
Wyniki i wypłaty są takie same, jak gdyby obaj gracze wybrali DOVE, ale w przeciwieństwie do tego, GRIM grający przeciwko GRIM tworzy równowagę Nasha, a Ali i Bo są w stanie racjonalnie osiągnąć wynik, który jest niemożliwy w jednorazowej wersji gra. Aby zobaczyć, że te strategie tworzą równowagę Nasha, załóżmy, ze względu na sprzeczność, że tak nie jest. Wtedy jeden gracz – załóżmy bez utraty ogólności, że to Ali – ma korzystne odchylenie, w postaci strategii FSM, która przyniosłaby wyższą wypłatę niż GRIM. Teraz w pewnym momencie ta strategia musiałaby zrobić coś innego niż GRIM – w przeciwnym razie uzyskałaby taką samą użyteczność. Więc w pewnym momencie musi grać zeznawać. Ale wtedy strategia GRIM Bo przeszłaby w tryb kary, stale zeznając w odpowiedzi. W tym momencie Ali byłaby skazana na wypłatę nie wyższą niż -5: gorszą niż -1, którą otrzymałaby wybierając GRIM. W ten sposób obaj gracze wybierający GRIM tworzą równowagę Nasha w nieskończenie powtarzającym się dylemacie więźnia, dając racjonalnie trwały wynik, który jest niemożliwy w jednorazowej wersji gry. Jest to przykład ogólnej klasy wyników zwanych ludowymi twierdzeniami Nasha, które charakteryzują wyniki, które mogą być podtrzymane przez równowagę Nasha w nieskończenie powtarzanych grach. Powiedzmy, że wartość bezpieczeństwa gracza jest najlepszą wypłatą, jaką gracz może zagwarantować. Zatem ogólna forma ludowych twierdzeń Nasha jest z grubsza taka, że każdy wynik J, w którym każdy gracz otrzymuje przynajmniej swoją wartość bezpieczeństwa, może zostać utrzymany jako równowaga Nasha w nieskończenie powtarzanej grze. Strategie GRIM są kluczem do ludowych twierdzeń: wzajemna groźba kary, jeśli jakikolwiek agent nie odegra swojej roli w pożądanym wyniku, utrzymuje graczy w ryzach. Działa to jednak jako środek odstraszający tylko wtedy, gdy drugi gracz uważa, że przyjąłeś tę strategię – a przynajmniej, że mogłeś ją przyjąć. Możemy również uzyskać różne rozwiązania, zmieniając agentów, a nie zmieniając zasady zaangażowania. Załóżmy, że agenci są skończonymi maszynami stanowymi o n stanach i grają w grę z m > n całkowitymi krokami. Agenci nie są zatem w stanie przedstawić liczby pozostałych kroków i muszą traktować ją jako nieznaną. Dlatego nie mogą dokonać indukcji wstecznej i mogą swobodnie dojść do korzystniejszej równowagi (odrzuć, odrzuć) w powtórzonym Dylemacie Więźnia. W tym przypadku ignorancja jest błogością – a raczej błogością jest przekonanie przeciwnika, że jesteś ignorantem. Twój sukces w tych powtarzających się grach w dużej mierze zależy w znacznym stopniu od tego, czy inny gracz postrzega cię jako łobuza lub prostaka, a nie od twoich rzeczywistych cech.