Videos

Epic Math Battles: Nash vs. Pareto

Presenter
May 11, 2022
Abstract
We will start this talk with a short recap of the dynamic programming principle for dynamic games established in Feinstein, Rudloff, Zhang (2022). It is shown that the set value of the game, i.e. the set of values over all equilibria, is recursing backwards in time. This motivates us to study the question on how to compute the set of all Nash equilibria of a game (and thus obtain the set value of the game). To do so, we will focus now on one-period games and establish a strong connection between Nash equilibria and Pareto solutions. Nash equilibria and Pareto optimization are two distinct concepts in multi-criteria decision making. It is well known that the two concepts do not coincide. However, in this work we show that it is possible to characterize the set of all Nash equilibria for any non-cooperative game as the set of all Pareto optimal solutions of a certain vector optimization problem. To accomplish this task, we enlarge the objective function and formulate a non-convex ordering cone under which Nash equilibria are Pareto efficient. We demonstrate these results, first, for shared constraint games in which a joint constraint is applied to all players in a non-cooperative game. This result is then extended to generalized Nash games, where we deduce two vector optimization problems providing necessary and sufficient conditions, respectively, for generalized Nash equilibria. Finally, we show that all prior results hold for vector-valued games as well. This characterization opens a new way of computing Nash equilibria. It allows to use algorithms from vector optimization enabling us to compute the set of all Nash equilibria, which is in contrast to the classical fixed point iterations that find just a single Nash equilibrium. Multiple numerical examples are given. This is joint work with Zach Feinstein.