Rationality of Learning Algorithms in Repeated Normal-Form Games

Shivam Bajaj, Pranoy Das, Yevgeniy Vorobeychik, Vijay Gupta

Abstract

In multi-agent reinforcement learning (MARL), standard algorithms like Fictitious Play (FP) and Regret Matching (RM) are designed to converge to a Nash Equilibrium in self-play. However, these algorithms often ignore individual incentives, making them highly exploitable by self-interested agents. This paper introduces the "rationality ratio" to quantify this vulnerability and proposes two new algorithms—Rational Generalized Fictitious Play (R-GFP) and Rational Regret Matching (R-RM)—that are provably non-exploitable (1-rational) under perfect monitoring. We demonstrate that while classic algorithms can have unbounded exploitability, our proposed "detect and punish" framework effectively neutralizes the incentive to deviate.

Introduction

The design of learning algorithms for multi-agent systems typically focuses on convergence properties. If all agents follow a prescribed algorithm, the system reaches a stable state such as a Nash Equilibrium. However, in real-world scenarios, agents are often self-interested and may realize that deviating from the prescribed algorithm can yield significantly higher payoffs. This paper addresses the gap between convergence and individual rationality in repeated normal-form games.

The Rationality Ratio and Exploitability

To quantify how much an agent can gain by "cheating," the authors introduce the rationality ratio. This is defined as the ratio of the maximum payoff an agent can achieve by deviating to the payoff they would receive by following the algorithm. A perfectly rational algorithm has a ratio of 1, indicating zero incentive to deviate.

The paper's most striking theoretical finding is that classic algorithms like Fictitious Play and Regret Matching are not $c$-rational for any constant $c$. In certain games, an adversary can gain infinitely more utility than a loyal agent, creating an unbounded incentive to exploit the system.

Figure 1: A $2 \times 2$ payoff matrix illustrating the type of game-theoretic structures where standard learning algorithms can be exploited by self-interested agents.

Methods: The Detect and Punish Framework

The authors propose a three-phase framework to transform standard learning algorithms into rational ones (R-GFP and R-RM):

  1. Exploration Sub-Phase: Agents initially play a sequence of actions to reveal the game's payoff matrix. This is necessary because agents do not typically know the payoffs of their opponents at the start.
  2. Exploitation Sub-Phase: Agents follow the target algorithm (e.g., FP or RM) while monitoring the opponent. If the opponent's actions deviate from the algorithm's predictions, a punishment is triggered.
  3. Punishment Phase: Upon detecting a deviation, the agent switches to a minimax strategy. This strategy minimizes the maximum possible payoff the deviating adversary can receive, neutralizing any potential gains from cheating.
Figure 5: Illustration of the exploration phase at times $t=2$ and $t=3$, showing how specific actions are used to reveal the payoff structure (represented by $\mu$) to the agents.

For stochastic algorithms like Regret Matching, the framework uses a statistical approach, comparing empirical Cumulative Distribution Functions to detect if an opponent is deviating from the expected probability distribution of moves.

Key Results and Theoretical Insights

The paper provides formal proofs (Theorems 4.4 and 4.5) showing that R-GFP and R-RM are perfectly rational (ratio = 1) under the assumption of perfect monitoring—where agents can observe both the actions and payoffs of others.

Conversely, the authors prove a significant "negative result" for imperfect monitoring: if agents cannot observe their opponent's payoffs, there are some games where no $c$-rational algorithm can exist. This highlights that monitoring is the linchpin of rationality in these systems. Numerical simulations further validate these findings, showing that while an adversary's payoff spikes when exploiting standard FP, it is suppressed to the minimax level when facing R-GFP.

Conclusion and Future Work

While R-GFP and R-RM provide strong guarantees in two-agent repeated games, several challenges remain. The current proofs rely on perfect monitoring, which is often unavailable in complex real-world environments like high-frequency trading. Furthermore, extending these guarantees to $n$-agent games involves addressing the complexity of collusion, and moving from repeated normal-form games to stochastic games (where the state changes) remains a significant open challenge for the field.

Summary updated

Abstract

Many learning algorithms are known to converge to an equilibrium for specific classes of games if the same learning algorithm is adopted by all agents. However, when the agents are self-interested, a natural question is whether the agents have an incentive to unilaterally shift to an alternative learning algorithm. We capture such incentives as an algorithm’s rationality ratio, which is the ratio of the highest payoff an agent can obtain by unilaterally deviating from a learning algorithm to its payoff from following it. We define a learning algorithm to be c-rational if its rationality ratio is at most c irrespective of the game. We show that popular learning algorithms such as fictitious play and regret-matching are not c-rational for any constant ${\mathrm { c}}\geq 1$ . We also show that if an agent can only observe the actions of the other agents but not their payoffs, then there are games for which c-rational algorithms do not exist. We then propose a framework that can build upon any existing learning algorithm and establish, under mild assumptions, that our proposed algorithm is (i) c-rational for a given ${\mathrm { c}}\geq 1$ and (ii) the strategies of the agents converge to an equilibrium, with high probability, if all agents follow it.
BibTeX
@inproceedings{bajaj2024rationality,
  author = {Shivam Bajaj and Pranoy Das and Yevgeniy Vorobeychik and Vijay Gupta},
  title = {{Rationality of Learning Algorithms in Repeated Normal-Form Games}},
  booktitle = {IEEE Control. Syst. Lett},
  year = {2024},
  url = {https://openreview.net/forum?id=PNoMsayL3z},
}

Loading related content...

Figure