A Generalized Strategy Eliminability Criterion and Computational Methods for Applying It

Vincent Conitzer, Tuomas SandholmAAAI 2005 · OpenReview

Abstract

We define a generalized strategy eliminability criterion for bimatrix games that considers whether a given strategy is eliminable relative to given dominator & eliminee subsets of the players' strategies. We show that this definition spans a spectrum of eliminability criteria from strict dominance (when the sets are as small as possible) to Nash equilibrium (when the sets are as large as possible). We show that checking whether a strategy is eliminable according to this criterion is coNP-complete. We then give an alternative definition of the eliminability criterion and show that it is equivalent using the Minimax Theorem. We show how this alternative definition can be translated into a mixed integer program of polynomial size with a number of (binary) integer variables equal to the sum of the sizes of the eliminee sets. Finally, we study using the criterion for iterated elimination of strategies.

Introduction

In game theory, simplifying a game by removing "bad" strategies is a standard preprocessing step. Traditionally, this is done using strict dominance, where one strategy is always worse than another regardless of the opponent's actions. However, dominance is often too restrictive and fails to eliminate many strategies that would never actually be played in a rational outcome. On the other end of the spectrum is the Nash equilibrium, which identifies viable strategies but is computationally hard to find (PPAD-complete).

A simple 2x2 bimatrix game used to illustrate basic dominance and equilibrium concepts.

This paper addresses the need for an intermediate tool: a criterion that is stronger than dominance but easier to compute than a Nash equilibrium, allowing for "semi-local" reasoning to prune the search space of complex games.

The Generalized Eliminability Criterion

The authors propose a criterion where a strategy is considered "eliminable" relative to specific subsets of strategies called dominator and eliminee sets. By varying the size of these sets, the criterion spans from strict dominance (minimal sets) to Nash equilibrium (maximal sets).

A 4x4 game matrix with partial payoffs, used to demonstrate the generalized eliminability criterion and properties like path dependence.

A major insight is the distinction between locality and globality. Dominance is "local" (comparing two strategies), while Nash is "global" (considering the whole game). This criterion allows for "semi-local" reasoning, where one only looks at a small neighborhood of strategies to prove one is useless.

Computational Methods and Complexity

Using the Minimax Theorem, the authors derive an alternative definition of their criterion that is easier to translate into a computational model. They provide a Mixed Integer Programming (MIP) formulation to check for eliminability. Crucially, the number of binary integer variables in this program is determined only by the size of the eliminee sets, not the total number of strategies in the game.

The paper proves that deciding eliminability is coNP-complete in the general case, even in symmetric games and when dominator sets are limited to a size of 1. However, the MIP approach allows for polynomial-time elimination as long as the eliminee sets are small, making it a practical tool for pruning.

Key Results and Iterated Elimination

The research successfully places dominance and Nash equilibrium on the same mathematical spectrum. The authors also explore iterated elimination, applying the criterion repeatedly to remove strategies. They show that iterated elimination under a size restriction can eliminate strategies that a single-round check would miss.

One critical finding is path dependence: unlike strict dominance, the order in which strategies are eliminated using this new criterion matters. Removing one strategy might actually make it harder to eliminate another later. Despite this, the criterion is "safe"---it will never eliminate a strategy that could be part of a Nash equilibrium.

Conclusion and Future Work

The current computational tools, specifically the MIP, are designed for two-player games. Generalizing these to $N$-player games is not straightforward and likely significantly more complex. Additionally, because the order of elimination matters, finding the "optimal" path of elimination remains an open challenge. Future work should involve empirical validation on random games to see how much this approach speeds up state-of-the-art Nash equilibrium solvers in practice.

Summary updated

Abstract

We define a generalized strategy eliminability criterion for bimatrix games that considers whether a given strategy is eliminable relative to given dominator & eliminee subsets of the players' strategies. We show that this definition spans a spectrum of eliminability criteria from strict dominance (when the sets are as small as possible) to Nash equilibrium (when the sets are as large as possible). We show that checking whether a strategy is eliminable according to this criterion is coNP-complete (both when all the sets are as large as possible and when the dominator sets each have size 1). We then give an alternative definition of the eliminability criterion and show that it is equivalent using the Minimax Theorem. We show how this alternative definition can be translated into a mixed integer program of polynomial size with a number of (binary) integer variables equal to the sum of the sizes of the eliminee sets, implying that checking whether a strategy is eliminable according to the criterion can be done in polynomial time, given that the eliminee sets are small. Finally, we study using the criterion for iterated elimination of strategies.
BibTeX
@inproceedings{conitzer2005generalized,
  author = {Vincent Conitzer and Tuomas Sandholm},
  title = {{A Generalized Strategy Eliminability Criterion and Computational Methods for Applying It}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2005},
  url = {https://openreview.net/forum?id=S1b9RReuZB},
}
Figure