Three-Operator Splitting for Learning to Predict Equilibria in Convex Games
D. McKenzie, Herbert Heaton, Qiuwei Li, Samy Wu Fung, Stanley Osher, Wotao Yin · SIAM Journal on Mathematics of Data Science · 2024
Abstract. Systems of competing agents can often be modeled as games. Assuming rationality, the most likely outcomes are given by an equilibrium, e.g., a Nash equilibrium. In many practical settings, games are influenced by context, i.e., additional data beyond the control of any agent (e.g., weather for traffic and fiscal policy for market economies). Often, the exact game mechanics are unknown, yet vast amounts of historical data consisting of (context, equilibrium) pairs are available, raising the possibility of learning a solver that predicts the equilibria given only the context. We introduce Nash fixed-point networks (N-FPNs), a class of neural networks that naturally output equilibria. Crucially, N-FPNs employ a constraint decoupling scheme to handle complicated agent action sets while avoiding expensive projections. Empirically, we find that N-FPNs are compatible with the recently developed Jacobian-free backpropagation technique for training implicit networks, making them significantly faster and easier to train than prior models. Our experiments show that N-FPNs are capable of scaling to problems orders of magnitude larger than existing learned game solvers. All code is available online.