In game theory, there is a sharp computational divide between two-player zero-sum games and general-sum games. Two-player zero-sum games are computationally well-behaved: they satisfy Von Neumann’s minimax theorem, meaning a unique equilibrium value always exists, and they can be solved efficiently using linear programming or scalable iterative algorithms like Counterfactual Regret Minimization (CFR).
General-sum and multi-player games, by contrast, are notoriously difficult. Finding a Nash equilibrium in these settings is PPAD-complete, and finding the optimal equilibrium (one that maximizes social welfare or revenue) is often NP-hard. Without a zero-sum structure, learning algorithms frequently suffer from cyclic dynamics or fail to converge entirely.
To bypass these computational hurdles, a powerful research direction has emerged: transforming or reducing complex, general-sum, and multi-player games into strategically equivalent or approximate zero-sum formulations. By cleverly restructuring payoffs, introducing virtual players, or decomposing interactions sequentially, researchers can deploy the highly optimized toolkit of zero-sum optimization to solve problems that would otherwise be computationally intractable.
Restoring Symmetry via Virtual Cost Transfers
One common way a game loses its zero-sum property is through individual overheads, such as computational costs, transaction fees, or resource deployment expenses. Even if the underlying conflict is purely competitive, these asymmetric costs turn the interaction into a general-sum game.
The core intuition for resolving this is simple: if individual costs can be modeled as transfers between players or to a virtual entity, the zero-sum structure can be restored without changing the strategic incentives.
[General-Sum Game with Costs]
│
▼ (Treat costs as virtual transfers)
[Strategically Equivalent Zero-Sum Game] ──► Solvable via Minimax / LP
Ben-Sasson et al. demonstrate this mechanism in their foundational work on bounded rationality, An Approach to Bounded Rationality. They show that when players face strategy-specific computational costs, the game can be mapped to a strategically equivalent constant-sum game by treating those costs as transfers between the players. This preserve the existence of stable equilibria and allows the direct application of minimax principles.
A similar intuition applies to resource allocation. In Equilibria of the Colonel Blotto Games with Costs, Kazmierowski tackles a variant of the classic Colonel Blotto game where players incur costs for acquiring and deploying resources. By introducing a single "dummy" battlefield that absorbs the value of unspent resources, the author mathematically reduces this non-zero-sum game into a standard zero-sum formulation, enabling polynomial-time equilibrium computation.
The Mediator-Deviator Saddle Point
When a platform designer or policymaker wants to find the optimal equilibrium in a general-sum extensive-form game, they face a daunting optimization landscape. They cannot simply run standard zero-sum solvers because players' incentives are not diametrically opposed.
The breakthrough insight here is to reframe the search for an optimal equilibrium as a zero-sum game between two meta-players: a Mediator and a Deviator.
┌────────────────────────────────────────────────────────┐
▼ │
[Mediator] Proposes a welfare-maximizing joint strategy │ (Zero-Sum Loop)
│ │
▼ │
[Deviator] Attempts to find a profitable deviation ─────────┘
This reduction relies on Lagrangian relaxation. As detailed by Zhang et al. in Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games, the Mediator's goal is to maximize the target objective (e.g., social welfare) while minimizing the players' incentive to deviate. The Deviator's goal is strictly the opposite: to find the most profitable deviation from the mediator's proposed recommendations.
Because the Mediator and Deviator are in a state of pure competition, their interaction forms a two-player zero-sum saddle-point problem. Consequently, highly optimized zero-sum algorithms like CFR can be used to find the optimal correlated or coarse correlated equilibrium of the original general-sum game. Zhang et al. and Tuomas Sandholm previously leveraged a related structural transformation in Polynomial-Time Optimal Equilibria with a Mediator in Extensive-Form Games to prove that introducing a trusted mediator allows the optimal equilibrium to be found in polynomial time via linear programming.
Sequential Zero-Sum Decomposition
Some games are not strictly zero-sum but possess a low-rank structure or sit "near" a zero-sum game. For instance, a market with a minor transaction fee is almost zero-sum, but standard gradient descent algorithms still struggle with its non-zero-sum components.
Instead of trying to solve the complex game directly, the strategy here is to decompose the game into a sequence of parameterized zero-sum subproblems.
[Near-Zero-Sum Game] ──► [Isolate Non-Zero-Sum Component (Scalar λ)] ──► [Sequence of Zero-Sum Subproblems]
In Learning Nash Equilibria in Rank-1 Games, Patris et al. apply this to rank-1 games (games where the payoff matrix can be decomposed into a zero-sum matrix plus a rank-1 outer product). By introducing a scalar variable that tracks the non-zero-sum component, the authors isolate the asymmetry and solve the game as a sequence of zero-sum optimization steps, bypassing traditional convergence hurdles.
Similarly, Luo et al. introduce the Iterative Coupling Linearization (ICL) algorithm in Monotone Near-Zero-Sum Games: A Generalization of Convex-Concave Minimax. By exploiting a game's proximity to a zero-sum baseline, they reduce the gradient complexity from linear to square-root scaling relative to the condition number. This allows problems with small non-zero-sum components to be solved with nearly the same efficiency as pure minimax problems.
Folding Teams into Coordinated Entities
Multi-player games involving teams (such as a team of colluding players playing against a casino or an adversary) are notoriously hard to solve due to the exponential explosion of joint action spaces and the need for coordination without communication.
The reduction strategy here is to collapse the multi-player team into a single, coordinated meta-player, transforming the interaction into a standard two-player zero-sum game.
[Team Player 1] ┐
[Team Player 2] ┼─► [Information Pre-Branching (PIPB)] ─► [Single Coordinated Team Entity] vs [Adversary]
[Team Player 3] ┘
In Enhanced Equilibria-Solving via Private Information Pre-Branch Structure in Adversarial Team Games, Qiu et al. achieve this by replacing complex action-based coordination with a Private Information Pre-Branch (PIPB) structure. This structure folds the team's decision-making process into a single coordinated entity. By reducing the multi-player team game to an equivalent two-player zero-sum game, the authors drastically lower memory overhead and achieve up to a 694x speedup using standard iterative zero-sum solvers.
Best-Response Equivalence in Security and Control
In real-world security scenarios—such as protecting infrastructure or deploying adversarial classification defenses—the game appears general-sum because the defender's cost to secure a target does not perfectly equal the attacker's utility from destroying it.
However, many of these settings exhibit best-response equivalence, meaning that the optimal strategies under the general-sum payoffs are identical to the optimal strategies of a simplified zero-sum game.
- Adversarial Classification: Dritsoula et al. demonstrate in A Game-Theoretic Analysis of Adversarial Classification that adversarial machine learning interactions can be mapped directly to zero-sum games. This allows defenders to compute robust classification thresholds using standard linear programming.
- Interdependent Targets: In Non-Additive Security Games, Wang et al. analyze security games where targets are interconnected (e.g., power grids where failing one node cascades to others). They prove that despite the highly non-additive, general-sum nature of the payoffs, the game maintains a strategic zero-sum equivalence, allowing operators to safely use zero-sum linear programs to find optimal defense allocations.
- Concept Interchangeability: Korzhyk et al. exploit this equivalence in Stackelberg vs. Nash in Security Games: An Extended Investigation of Interchangeability, Equivalence, and Uniqueness. By mapping security games to corresponding zero-sum games, the authors prove that strategies designed for observant attackers (Stackelberg) remain optimal even when the attacker lacks surveillance capabilities (Nash), unifying different solution concepts under a single minimax umbrella.
By identifying these hidden zero-sum structures, researchers across algorithmic game theory, machine learning, and security can bypass the inherent intractability of general-sum interactions, turning fragile multi-agent coordination problems into robust, solvable optimization tasks.
Key Foundational Work
Team-optimal closed-loop Stackelberg strategies in hierarchical control problems (1980) — contributed 1 concept elements to this direction.
A note on strategy elimination in bimatrix games (1988) — contributed 1 concept elements to this direction.