Computing Nash Equilibria in Potential Games with Private Uncoupled Constraints
Preprint
Abstract
We consider the problem of computing Nash equilibria in potential games where each player's strategy set is subject to private uncoupled constraints. This scenario is frequently encountered in real-world applications like road network congestion games where individual drivers adhere to personal budget and fuel limitations. Despite the plethora of algorithms that efficiently compute Nash equilibria (NE) in potential games, the domain of constrained potential games remains largely unexplored. We introduce an algorithm that leverages the Lagrangian formulation of NE. The algorithm is implemented independently by each player and runs in polynomial time with respect to the approximation error, the sum of the size of the action-spaces, and the game's inherent parameters.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Augmented Lagrangian and exact penalty methods for quasi-variational inequalitiesComputational Optimization and Applications, 2017
- Algorithms for generalized potential games with mixed-integer variablesComputational Optimization and Applications, 2017
- Accelerated gradient methods for nonconvex nonlinear and stochastic programmingMathematical Programming, 2015
- Minima of Functions of Several Variables with Inequalities as Side Conditions2013
- Partial penalization for the solution of generalized Nash equilibrium problemsJournal of Global Optimization, 2010
- Restricted generalized Nash equilibria and controlled penalty algorithmComputational Management Science, 2009
- Generalized Nash equilibrium problems and Newton methodsMathematical Programming, 2007
- Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower gamesComputational Management Science, 2005
- Side Constrained Traffic Equilibrium Models—Traffic Management Through Link Tolls1998
- A class of games possessing pure-strategy Nash equilibriaInternational Journal of Game Theory, 1973