Links

Nash Fixed Point Networks

tl;dr - Implicit networks can be used to estimate equilibria from context, even when cost functions are unknown.

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 only game equilibria are observed, while the players' true cost functions are unknown. This work introduces Nash Fixed Point Networks (N-FPNs), a class of implicit neural networks that learn to predict the equilibria given only the context. The N-FPN design fuses data-driven modeling with provided constraints on the actions available to agents. N-FPNs are compatible with the recently introduced Jacobian-Free Backpropagation technique for training implicit networks, making them significantly faster to train than prior models. N-FPNs can exploit novel constraint decoupling to avoid costly projections. Provided numerical examples show the efficacy of N-FPNs on atomic and non-atomic games (e.g. traffic routing).

Citation

@article{heaton2021learn,
title={{Learn to Predict Equilibria via Fixed Point Networks}},
author={Heaton, Howard and McKenzie, Daniel and Li, Qiuwei and Fung, Samy Wu and Osher, Stanley and Yin, Wotao},
journal={arXiv preprint arXiv:2106.00906},
year={2021}
}