An Efficient Optimal-Equilibrium Algorithm for Two-player Game Trees

Michael L. Littman, Nishkam Ravi, Arjun Talwar, Martin Zinkevich

Abstract

Finding an arbitrary Nash equilibrium in two-player game trees is computationally simple, but identifying the optimal equilibrium—such as one maximizing social welfare—is significantly more complex. This paper presents a polynomial-time algorithm, bestNash, which utilizes Utility Profile Sets (UPS) to find optimal equilibria in general-sum game trees. The research demonstrates that even in deterministic games, players may require stochastic strategies to achieve globally optimal outcomes.

Introduction

In game theory, a Nash equilibrium represents a state where no player can improve their payoff by unilaterally changing their strategy. For two-player zero-sum games, algorithms like Minimax are standard. However, most real-world interactions are general-sum, where players might win or lose together.

In these scenarios, standard bottom-up approaches (e.g., anyNash) find subgame perfect equilibria quickly but arbitrarily. In games with ties, one equilibrium might result in a payoff of [2, 100] while another yields [1000, 4]. A greedy approach fails because a choice that appears locally indifferent to one player can drastically alter the options available to the other player earlier in the game.

The bestNash Algorithm and Utility Profile Sets

The authors propose bestNash, an algorithm that maintains a Utility Profile Set (UPS) at each node. Instead of a single payoff vector, a UPS contains all possible equilibrium payoff vectors for the subtree.

As the algorithm moves up the tree, it performs a Merge Operation:

  • Deterministic Merge: If a player strictly prefers one child's payoff, they select it.
  • Stochastic Merge: If a player is indifferent between children, they can employ a probabilistic mixture. This "filling in" creates new possible payoff vectors for the opponent, effectively allowing one player to "promise" a distribution to incentivize the other.
Visual representation of merging Utility Profile Sets (UPS), showing how points and lines form complex equilibrium regions.

To maintain tractability, the authors prove these sets can be represented as unions of points, horizontal/vertical lines, and axis-aligned rectangles. This geometric representation allows the algorithm to run in $O(n^3)$ time.

Complexity Boundaries

The paper maps the computational complexity of finding optimal equilibria across various game types. While the problem is solvable in polynomial time (P) for two-player complete information trees, it quickly becomes NP-hard or PPAD-hard when adding more players, stochastic nodes (random events), or hidden information.

The complexity landscape for finding optimal equilibria, highlighting the transition from P to NP-hard as game complexity increases.

Evaluation and Key Results

The algorithm was evaluated using Open-Handed Oh Hell! (OHOH), a trick-taking card game with complex general-sum incentives. Testing on 1,000 randomly generated hands revealed:

  • Suboptimality: Standard anyNash failed to find the social optimum in 41.5% of 5-card games.
  • Probabilistic Necessity: In 7-12% of cases, the social optimum required players to use stochastic strategies; deterministic play would have led to lower total welfare.
  • Performance: For a tree with ~400,000 nodes, bestNash reached a solution in approximately 11 seconds, demonstrating its practicality.

Conclusion

The bestNash algorithm proves that finding the "best" win-win scenario in two-player games is computationally feasible. By leveraging the power of indifference and stochastic strategies, players can achieve outcomes that greedy, deterministic algorithms miss. Future work remains to address the NP-hard challenges of stochastic nodes and multi-player environments.

Summary updated

BibTeX
@inproceedings{littman2006efficient,
  author = {Michael L. Littman and Nishkam Ravi and Arjun Talwar and Martin Zinkevich},
  title = {{An Efficient Optimal-Equilibrium Algorithm for Two-player Game Trees}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2006},
}
Figure