All Games Have Equilibria
Computer Science and Game Theory
Summary
The authors studied games with infinitely many choices and players, which are usually very complicated to analyze for stable outcomes called Nash equilibria. They proposed using a new way of mixing strategies, called finitely additive mixed strategies, instead of the usual countably additive ones. With this change, they proved that every such infinite game has at least one Nash equilibrium. They also showed that these equilibria behave nicely when games are approximated by simpler finite versions. Overall, their work makes it easier to study equilibria in games that were previously considered too difficult.
Authors
M. Ali Khan, Arthur Paul Pedersen, Maxwell B. Stinchcombe
Abstract
Research on Nash equilibrium existence for infinite games has grown into a patchwork of technical preconditions and counterexamples. This paper presents a unified program in equilibrium theory by revising the predominant model of mixed strategies based on countable additivity. A game is specified by a nonempty set of players and, for each player, a nonempty action set and a bounded von Neumann-Morgenstern utility function. Every such game is shown to admit a Nash equilibrium in finitely additive mixed strategies. In addition, the equilibrium correspondence for any such game is shown to be nonempty, compact-valued, and upper hemicontinuous, and the same is true for equilibria obtained as limits of finite approximations. Techniques developed in this paper show that infinite games long treated as intractable become amenable to direct equilibrium analysis.