Introduction
In traditional game theory, the rules and payoffs of a game are typically treated as fixed and known. However, in many practical scenarios—ranging from ad auctions to strategic policy-making—a game designer may have limited control over certain payoff entries or may face uncertainty regarding specific outcomes. This paper explores the computational complexity of "incompletely specified games," where a designer can strategically "fill in the blanks" to influence the resulting equilibrium.
We specifically address two fundamental questions regarding a target action $a$:
- Possible Equilibrium Action: Does there exist a valid specification of the missing payoffs such that $a$ is played with positive probability in at least one Nash equilibrium?
- Necessary Equilibrium Action: Is $a$ played in every Nash equilibrium, regardless of how the missing payoffs are set within their allowed bounds?
Problem Formulation
An incompletely specified game is defined by a payoff matrix where some entries are sets of possible values rather than single scalars. The designer's goal is to select values from these sets to achieve a desired equilibrium property.
This framework is particularly relevant for symmetric zero-sum games, which are common in social choice theory. We focus on two specific solution concepts: the Essential Set (ES) and the Bipartisan Set (BP), which identify "desirable" actions based on their presence in equilibrium supports.
Computational Complexity
A major contribution of this work is establishing the hardness of these problems. We prove that determining if an action is a possible equilibrium action is NP-complete, while determining if it is a necessary action is coNP-complete.
Surprisingly, these hardness results persist even in highly restricted settings, such as tournament games (symmetric zero-sum games with payoffs in $\{-1, 0, 1\}$ and no ties). This settles a long-standing open question regarding the complexity of the "possible winner" problem for the Bipartisan Set. The proofs utilize novel "alternating game" gadgets to reduce problems like SAT and SetCover to equilibrium selection.
Algorithmic Approach: Mixed-Integer Programming
Despite the theoretical hardness, practical instances can often be solved efficiently. We developed a Mixed-Integer Programming (MIP) formulation to identify possible equilibrium actions. By leveraging modern solvers like CPLEX, this approach avoids the exponential cost of brute-force search over all possible payoff combinations.
In experimental evaluations using randomly generated weak tournament games, the MIP formulation demonstrated significant scalability. While brute-force methods failed as the number of actions grew, the MIP approach successfully handled games with up to 60 actions in under 10 seconds.
Conclusion
This research highlights the extreme sensitivity of Nash equilibria to even minor changes in payoff structures. A single unspecified entry can fundamentally alter the set of viable strategies. While the general problem is computationally difficult, our MIP results suggest that strategic game-tweaking is feasible for many real-world applications. Future work will extend these findings to general-sum games and explore continuous payoff intervals.
Summary updated