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.
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):
- 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.
- 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.
- 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.
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