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.
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.
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
anyNashfailed 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,
bestNashreached 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