Approximating the Set of Nash Equilibria for Convex Games
Zachary Feinstein (),
Niklas Hey () and
Birgit Rudloff ()
Additional contact information
Zachary Feinstein: Stevens Institute of Technology, School of Business, Hoboken, New Jersey 07030
Niklas Hey: Vienna University of Economics and Business, Institute for Statistics and Mathematics, A-1020 Vienna, Austria
Birgit Rudloff: Vienna University of Economics and Business, Institute for Statistics and Mathematics, A-1020 Vienna, Austria
Operations Research, 2025, vol. 73, issue 5, 2729-2743
Abstract:
In Feinstein and Rudloff (2024) , it was shown that the set of Nash equilibria for any noncooperative N player game coincides with the set of Pareto optimal points of a certain vector optimization problem with nonconvex ordering cone. To avoid dealing with a nonconvex ordering cone, an equivalent characterization of the set of Nash equilibria as the intersection of the Pareto optimal points of N multi-objective problems (i.e., with the natural ordering cone) is proven. So far, algorithms to compute the exact set of Pareto optimal points of a multi-objective problem exist only for the class of linear problems, which reduces the possibility of finding the true set of Nash equilibria by those algorithms to linear games only. In this paper, we will consider the larger class of convex games. Because typically only approximate solutions can be computed for convex vector optimization problems, we first show, in total analogy to the result above, that the set of ϵ -approximate Nash equilibria can be characterized by the intersection of ϵ -approximate Pareto optimal points for N convex multi-objective problems. Then, we propose an algorithm based on results from vector optimization and convex projections that allows for the computation of a set that, on one hand, contains the set of all true Nash equilibria and is, on the other hand, contained in the set of ϵ -approximate Nash equilibria. In addition to the joint convexity of the cost function for each player, this algorithm works provided the players are restricted by either shared polyhedral constraints or independent convex constraints.
Keywords: Optimization; convex game; set of Nash equilibria; Pareto optimality; approximation; algorithm (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:
Downloads: (external link)
http://dx.doi.org/10.1287/opre.2023.0541 (application/pdf)
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:5:p:2729-2743
Access Statistics for this article
More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().