Approximating the Set of Nash Equilibria for Convex Games

Computing Nash Equilibria as Pareto Points Recent work by Feinstein and Rudloff (“Characterizing and Computing the Set of Nash Equilibria via Vector Optimization”) proved that it is possible to characterize the set of all Nash equilibria as the set of all Pareto optimal solutions of a certain vector optimization problem. “Approximating the Set of Nash Equilibria for Convex Games” by Feinstein, Hey, and Rudloff expands on this result to demonstrate that a comparable relation holds between the set of all approximate Nash equilibria and approximate Pareto solutions of a specific vector optimization problem. This characterization holds for all noncooperative games but opens a new way of computing Nash equilibria using techniques and algorithms from convex vector optimization. A sandwich property is proven in which the computed set of approximate Pareto solutions is bounded between the set of true Nash equilibria and the set of all approximate Nash equilibria with controlled error.