Nash Equilibria of Two-Player Matrix Games Repeated Until Collision

Aniket Murhekar, Eklavya Sharma

Introduction

In classical game theory, repeated games often present a significant challenge due to the complexity of the strategy space. Because players can condition their current moves on the entire history of previous rounds, the resulting "Folk Theorems" suggest that almost any outcome can be sustained as a Nash Equilibrium (NE) through intricate punishment and reward schemes. This paper introduces and analyzes a specific class of repeated interactions termed Repeated-Until-Collision (RUC) games. These games terminate immediately when both players select the same action, providing a natural model for scenarios such as predator-prey dynamics, cybersecurity breaches, and the childhood game of hand cricket.

The RUC Game Model

An RUC game is a two-player matrix game that continues round-by-round until a "collision" occurs—defined as both players choosing the same action $i = j$. The core research question is whether these games possess stable, computable equilibria and whether players can optimize their outcomes using simple, memoryless strategies rather than complex, history-dependent ones.

The authors formalize the game by examining the expected total payoff, which is the sum of rewards or costs accumulated across all rounds until termination. A key contribution of this work is the proof that stationary strategies—fixed probability distributions that remain constant regardless of the game's history—are sufficient to achieve a Nash Equilibrium.

Theoretical Framework: Stationarity and Perron-Frobenius

The analysis of RUC games bridges game theory with classical matrix algebra. By restricting the initial analysis to Stationary RUC (SRUC) games, the authors derive an elegant expression for the expected total payoff $e(x, y)$ for a strategy pair $(x, y)$:

$$e(x, y) = \frac{x^T A y}{x^T y}$$

In this formula, $x^T y$ represents the probability of a collision in any given round. To prove the existence of an equilibrium, the authors leverage Perron-Frobenius Theory. They demonstrate that the Nash Equilibrium strategies correspond to the leading eigenvectors (Perron vectors) of the payoff matrices. This spectral interpretation provides a geometric foundation for understanding optimal play in collision-based games.

Key Insights

1. The Sufficiency of Memoryless Play

Perhaps the most significant finding is that "memory" does not provide a competitive advantage in RUC games. Even when players are permitted to use infinitely complex, history-dependent strategies, they have no incentive to deviate from the stationary distribution derived from the Perron vectors. This simplifies the strategy space from an infinite-dimensional one to a simple probability simplex.

2. Zero-Sum Uniqueness

For zero-sum RUC games, where one player's gain is the other's loss, the authors prove that the Nash Equilibrium is "unique up to equivalence." This ensures that all equilibria result in the same observable behavior and expected payoffs, providing a stable solution concept for competitive scenarios.

3. Computational Efficiency

While exact eigenvectors can be irrational and difficult to compute precisely, the paper provides an algorithm to find $\epsilon$-approximate Nash Equilibria. By utilizing the power method—an iterative technique for finding dominant eigenvectors—the authors show that an approximate NE can be computed in polynomial time relative to the size of the action set and the desired precision.

Limitations and Future Directions

The current theoretical framework relies heavily on the assumption that payoff matrices are irreducible (strongly connected). While the authors address reducible cases in their appendices, these scenarios are more complex and do not always guarantee unique equilibria.

Future research may expand the definition of a "collision." Currently, the model only triggers termination when $i=j$. Generalizing this to a "collision matrix," where different pairs of actions result in termination with varying probabilities, would broaden the model's applicability to more diverse real-world systems. Additionally, while existence is proven for general-sum RUC games, the uniqueness of those equilibria remains an open question for the field.

Summary updated

Abstract

We introduce and initiate the study of a natural class of repeated two-player matrix games, called Repeated-Until-Collision (RUC) games. In each round, both players simultaneously pick an action from a common action set {1, 2, … , n}. Depending on their chosen actions, they derive payoffs given by n × n matrices A and B, respectively. If their actions collide (i.e., they pick the same action), the game ends, otherwise, it proceeds to the next round. Both players want to maximize their total payoff until the game ends. RUC games can be interpreted as pursuit-evasion games or repeated hide-and-seek games. They also generalize hand cricket, a popular game among children in India. We show that under mild assumptions on the payoff matrices, every RUC game admits a Nash equilibrium (NE). Moreover, we show the existence of a stationary NE, where each player chooses their action according to a probability distribution over the action set that does not change across rounds. Remarkably, we show that all NE are effectively the same as the stationary NE, thus showing that RUC games admit an almost unique NE. Lastly, we also show how to compute (approximate) NE for RUC games.
BibTeX
@inproceedings{murhekar2023nash,
  author = {Aniket Murhekar and Eklavya Sharma},
  title = {{Nash Equilibria of Two-Player Matrix Games Repeated Until Collision}},
  booktitle = {FSTTCS},
  year = {2023},
  url = {https://openreview.net/forum?id=MaPrcZGxBH},
}
Figure