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