Abstract
This paper introduces a novel method to scale Stackelberg Equilibrium solvers to massive games by using neural networks to approximate "Enforceable Payoff Frontiers" (EPFs). Unlike standard AI for zero-sum games that predicts a single scalar value for a state, this approach learns the entire tradeoff curve between leader and follower payoffs. This provides the first function-approximation framework for Stackelberg settings with formal guarantees on incentive compatibility.
Introduction: Beyond Zero-Sum Games
In game theory, a Stackelberg Equilibrium involves a "leader" who commits to a strategy first and a "follower" who responds optimally. While massive success has been achieved in zero-sum games (like Chess or Go) using Function Approximation (FA)—where a neural network predicts the "value" of a state—general-sum games present a significantly higher hurdle.
The core challenge is that in general-sum games, the "value" of a state cannot be summarized by a single number. Instead, it is a complex set of possible payoff pairs for both players. Existing exact solvers rely on backward induction, which requires traversing the entire game tree—an impossible task for games with billions of states. Furthermore, simply plugging in standard neural networks often leads to "unfulfillable promises," where the leader's strategy relies on promising the follower a reward that the game's mechanics cannot actually deliver, causing the equilibrium to collapse.
Representing the Enforceable Payoff Frontier (EPF)
The authors propose representing the Enforceable Payoff Frontier (EPF) using neural networks. An EPF is a function $U_s(\mu_2)$ that tells the leader: "If I want to guarantee the follower a payoff of at least $\mu_2$, what is the maximum payoff I can get for myself?"
As shown in Figure 1, the EPF captures the boundary of achievable payoffs. Crucially, the method distinguishes between "Enforceable" and "Unenforceable" payoffs. A payoff is only enforceable if the leader can actually provide a subgame strategy that justifies the follower's choice. Without this distinction, a neural network might predict a high reward for the leader based on a "lie" to the follower.
Methods: Scaling with Neural Networks
To scale this concept, the authors developed several key technical components:
- Piecewise Linear Representation: Since exact EPFs are piecewise linear and concave, the neural network is designed to output a set of "knots" (coordinates) that define such a function.
- Fitted Value Iteration (FVI): The authors adapted the FVI algorithm from reinforcement learning. The network is trained to minimize a Bellman-like loss between the current predicted EPF and a "target" EPF calculated from the state's children.
- Architectural Constraints: To prevent unfulfillable promises, the network's output layer is constrained so that the follower's payoffs always fall between the "grim" value (the worst P1 can do to P2) and the "altruistic" value (the best P1 can do for P2).
- $L_\infty$ Loss: Instead of standard Mean Squared Error ($L_2$), the authors use a maximum-absolute-error loss ($L_\infty$). This ensures the approximation is tight across the entire frontier, which is critical for maintaining the follower's incentives.
Key Results and Insights
The researchers tested their framework on two synthetic environments: Tantrum, a game with over $10^{12}$ states designed to test long-range threats, and Resource Collection (RC), a grid-based game testing generalization.
- Scalability: The method successfully found near-optimal solutions in the Tantrum game, where exact solvers would have timed out or run out of memory.
- Generalization: In featurized versions of the games, the model learned to predict frontiers for entirely new game configurations it hadn't seen during training, rather than just memorizing paths.
- The Danger of Small Errors: A key insight is that while small errors in zero-sum games lead to slightly sub-optimal moves, in Stackelberg games, they can lead to "incentive violations." If a follower realizes a leader's promise is unfulfillable, they may choose a completely different, catastrophic branch of the game tree. By baking constraints into the architecture, the authors "disentangle" reward maximization from incentive maintenance.
Conclusion and Future Work
This work provides a robust foundation for solving large-scale Stackelberg games, but limitations remain. The current model is restricted to Perfect Information games; extending this to imperfect information (like Poker) would require EPFs to account for "beliefs" about the opponent's state. Additionally, the method assumes that the "grim" and "altruistic" bounds for the follower are known or easily approximated. Future research will likely focus on relaxing these assumptions and managing the complexity of the "knots" as games grow even more intricate.
Summary updated