Best Responses in Repeated Games with Conditional Strategies

Abstract

Wiederholte Spiele bilden in der Spieltheorie einen grundlegenden Rahmen um zu modellieren, wie sich strategische Interaktionen mit der Zeit entwickeln, wenn Spieler_innen ihre Entscheidungen auf Grundlage vergangener Ereignisse treffen. Zwei besonders interessante Klassen sind reaktive-n-Strategien, bei denen die Wahl der Aktion von den letzten n Aktionen des Gegners abhängt, und selbst-reaktive-n-Strategien, die ausschließlich die eigene Handlungshistorie berücksichtigen. Diese Arbeit behandelt eine zentrale Frage: Welche Informationen benötigt eine Spielerin, Alice, um ihre Auszahlung gegen ihren Gegner, Bob, zu maximieren, wenn dieser eine reaktive-n-Strategie spielt? Die Studie von [Glynatsi, Akin, Nowak, Hilbe: PNAS, 2024] zeigte, dass Alice in Zwei-Aktionen-Spielen nicht mehr Informationen benötigt als Bob. Zudem kann Alice die für sie maximal mögliche Auszahlung erreichen wenn sie eine pure selbst-reaktive-n-Strategie verwendet. Das erste Ziel dieser Arbeit ist es, dieses Ergebnis auf alle Spiele mit endlich vielen Aktionen zu erweitern. Als unmittelbare Konsequenz ergibt sich, dass das Problem, ob eine reaktive-n-Strategie ein symmetrisches Nash-Gleichgewicht darstellt, entscheidbar ist. Im zweiten Teil der Arbeit wird gezeigt, dass sich die Interaktion zwischen reaktiven und selbst-reaktiven Strategien als Zyklen auf de-Bruijn-Graphen darstellen lässt. Dieser neue Ansatz reduziert die Komplexität der Entscheidung, ob eine reaktive-n-Strategie ein Nash-Gleichgewicht bildet, erheblich. Zuletzt betrachten wir eine spezielle Klasse wiederholter Spiele, sogenannte additive Spiele. Unter Verwendung der de-Bruijn-Darstellung zeigen wir, dass Alice in additiven Spielen ihre maximale Auszahlung gegen ihren reaktiven-n-Gegner Bob mit einer puren selbst-reaktiven-(n-1)-Strategie erreichen kann. Alice trägt also keinen Schaden, wenn sie sich an ein Ereignis weniger erinnert als Bob. Neben seiner konzeptionellen Bedeutung vereinfacht dieses Ergebnis zusätzlich die Identifikation symmetrischer Nash-Gleichgewichte unter reaktiven-n-Strategien.

Repeated games are a foundational framework in game theory, modeling how strategic interactions unfold over time as players make decisions based on prior outcomes. Two classes of interest are reactive-n strategies, which respond to the co-player’s last $n$ actions, and self-reactive-n strategies, which consider only the player’s own history. This thesis addresses a key question: What information does one player, Alice, need to maximize her payoff against her opponent, Bob, if he plays a reactive-n strategy? Previous work by [Glynatsi, Akin, Nowak, Hilbe: PNAS, 2024] established for two action games, that Alice requires no more information than is available to Bob. Moreover, Alice can receive the highest possible payoff when she uses a pure self-reactive-n strategy. The first goal of this thesis is to extend this result to all finite action games. As an immediate consequence, the problem of determining whether a reactive-n strategy is a symmetric Nash equilibrium is decidable. In the second part of the thesis, we observe that the interaction between these two classes of strategies, reactive and self-reactive, can be described as cycles on de Bruijn graphs. This new approach drastically reduces the complexity of deciding if a reactive-n strategy is a Nash equilibrium. Finally, the thesis focuses on a specific class of repeated games called additive games. Employing the de Bruijn graph representation, we prove that in additive games, Alice can receive her highest possible payoff against her reactive-n opponent Bob by playing a pure self-reactive-(n-1) strategy. Thus, Alice is allowed to remember less than Bob without sacrificing payoff. Apart from being noteworthy on a conceptual level, this result simplifies the task of identifying symmetric Nash equilibria among reactive-n strategies even further.