Tractable Equilibrium Computation in Markov Games through Risk Aversion

Eric Mazumdar, Kishan Panaganti, Laixi Shi

TL;DR

Computing Nash equilibria in multi-agent systems is notoriously difficult (PPAD-hard), often making principled reinforcement learning impractical. This paper demonstrates that by imbuing agents with human-like traits—specifically risk aversion and bounded rationality—a new solution concept called Risk-averse Quantal Response Equilibrium (RQE) becomes computationally tractable in polynomial time for any $n$-player matrix or finite-horizon Markov game.

What Problem Does This Paper Address?

In game theory, the Nash Equilibrium (NE) is the gold standard for stable outcomes where no player has an incentive to deviate. However, finding a NE is computationally intractable for most general-sum games. While relaxations like Coarse Correlated Equilibria (CCE) are easier to compute, they often fail to predict how real humans actually play; humans are rarely perfect optimizers and frequently exhibit risk-averse behavior.

The authors tackle two major gaps:

  1. The Computational Gap: The inherent hardness of computing standard equilibrium concepts in multi-agent reinforcement learning (MARL).
  2. The Behavioral Gap: The failure of classical equilibrium concepts to capture empirical patterns of human play observed in experimental economics.

Methods

The authors introduce Risk-averse Quantal Response Equilibrium (RQE), which combines two concepts from behavioral economics:

  • Risk Aversion: Agents don't just maximize expected utility; they minimize a convex risk measure (like Entropic Risk or Value-at-Risk). The authors use the Dual Representation Theorem to transform these risk-averse objectives into a form where agents play against an "imaginary adversary" that tries to worsen their outcome within a bounded set.
  • Bounded Rationality: Instead of perfectly maximizing, agents use a Quantal Response, which is modeled by adding a convex regularizer (like entropy or a log-barrier) to their loss function. This makes their strategies smoother and less prone to extreme "all-or-nothing" shifts.

To prove tractability, the authors reduce the original $n$-player game to a specific $2n$-player auxiliary game. They show that if the agents' degrees of risk aversion and bounded rationality satisfy certain conditions, the equilibria of this larger game "collapse" into the RQE of the original game. This allows RQE to be computed efficiently using standard no-regret learning algorithms (like gradient play or mirror descent).

Common risk measures and their corresponding penalty functions used in this dual formulation are summarized in the paper:

Table 1: Widely-used convex risk-measures and their penalty functions.

Datasets

The authors validated their model using:

  • Experimental Economics Data: 13 different 2-player matrix games (including "Matching Pennies" variants) from classic studies by Selten & Chmura (2008) and Goeree et al. (2003).
  • Cliff Walk Benchmark: A custom $6 \times 6$ grid-world MARL environment designed to test how agents balance reaching a goal versus the risk of falling off a cliff, especially when their paths might collide with other agents.

Key Insights and Ideas

  • Tractability is Decoupled from Game Structure: Traditionally, games must be "zero-sum" or "monotone" to be solvable. Here, tractability depends solely on the agents' internal parameters (how risk-averse and "irrational" they are), regardless of whether the underlying game is competitive or cooperative.
  • The "Human" Sweet Spot: The authors identify a specific regime of parameters where RQE is both easy to compute and highly predictive of human behavior. As shown in Figure 1, the parameters needed to fit real-world human data fall squarely within the mathematically tractable region.
Figure 1: The shaded blue region shows the regime where RQE is computationally tractable. The markers represent parameters that best fit human play data in various games.
  • Equilibrium Collapse: The most surprising theoretical result is that the complex interaction of risk-averse agents can be simplified into a structure where Coarse Correlated Equilibria (CCE) coincide with Nash Equilibria, a property usually reserved for much simpler game classes.

Key Results

  • Polynomial Time Computation: The paper provides the first proof that RQE can be computed in polynomial time for all $n$-player matrix and finite-horizon Markov games.
  • Sample Complexity: For Markov games where the environment is unknown, the authors provide a model-based algorithm with a finite-sample guarantee. They show that an approximate RQE can be learned with a sample complexity of roughly $\tilde{O}(S^2 A H^2 L^2 / \delta^2)$, where $S$ is the state space and $A$ is the action space.
  • Behavioral Alignment: In the Cliff Walk experiments, risk-averse RQE agents naturally learned to avoid each other and take safer, albeit longer, paths to avoid the cliff, mirroring cautious human navigation.
Figure 2: Cliff Walk results showing how different levels of risk aversion ($\tau$) and bounded rationality ($\epsilon$) lead to safer (left) vs. riskier (right) pathfinding.

Limitations and Future Work

  • Uniqueness: While RQE is tractable to find, the paper does not guarantee that the equilibrium is unique. Multiple stable outcomes might still exist.
  • Decentralization: While the authors mention no-regret learning can be used, fully decentralized computation for certain complex risk measures remains an open challenge.
  • Static vs. Dynamic Risk: The current work focuses on aggregate risk. Future research could explore more granular, action-dependent risk models in deeper sequential settings.

Summary updated

Abstract

A significant roadblock to the development of principled multi-agent reinforcement learning is the fact that desired solution concepts like Nash equilibria may be intractable to compute. To overcome this obstacle, we take inspiration from behavioral economics and show that -- by imbuing agents with important features of human decision-making like risk aversion and bounded rationality -- a class of risk-averse quantal response equilibria (RQE) become tractable to compute in all $n$-player matrix and finite-horizon Markov games. In particular, we show that they emerge as the endpoint of no-regret learning in suitably adjusted versions of the games. Crucially, the class of computationally tractable RQE is independent of the underlying game structure and only depends on agents' degree of risk-aversion and bounded rationality. To validate the richness of this class of solution concepts we show that it captures peoples' patterns of play in a number of 2-player matrix games previously studied in experimental economics. Furthermore, we give a first analysis of the sample complexity of computing these equilibria in finite-horizon Markov games when one has access to a generative model and validate our findings on a simple multi-agent reinforcement learning benchmark.
BibTeX
@inproceedings{mazumdar2024tractable,
  author = {Eric Mazumdar and Kishan Panaganti and Laixi Shi},
  title = {{Tractable Equilibrium Computation in Markov Games through Risk Aversion}},
  booktitle = {Behavioral ML @ NeurIPS},
  year = {2024},
  url = {https://openreview.net/forum?id=SKWfQtfR3v},
}
Figure