Equilibrium modeling and solution approaches inspired by nonconvex bilevel programming
From MaRDI portal
Publication:6155058
DOI10.1007/S10589-023-00524-WarXiv2107.01286OpenAlexW3181261771MaRDI QIDQ6155058FDOQ6155058
Authors: Stuart M. Harwood, Francisco Trespalacios, Dimitri J. Papageorgiou, Kevin C. Furman 
Publication date: 16 February 2024
Published in: Computational Optimization and Applications (Search for Journal in Brave)
Abstract: Solution methods for generalized Nash equilibrium have been dominated by variational inequalities and complementarity problems. Since these approaches fundamentally rely on the sufficiency of first-order optimality conditions for the players' decision problems, they only apply as heuristic methods when the players are modeled by nonconvex optimization problems. In contrast, this work approaches generalized Nash equilibrium using theory and methods for the global optimization of nonconvex bilevel programs. Through this perspective, we draw precise connections between generalized Nash equilibria, feasibility for bilevel programming, the Nikaido-Isoda function, and classic arguments involving Lagrangian duality and spatial price equilibrium. Significantly, this is all in a general setting without the assumption of convexity. Along the way, we introduce the idea of minimum disequilibrium as a solution concept that reduces to traditional equilibrium when equilibrium exists. The connections with bilevel programming and related semi-infinite programming permit us to adapt global optimization methods for those classes of problems, such as constraint generation or cutting plane methods, to the problem of finding a minimum disequilibrium solution. We propose a specific algorithm and show that this method can find a pure Nash equilibrium even when the players are modeled by mixed-integer programs.
Full work available at URL: https://arxiv.org/abs/2107.01286
global optimizationbilevel programmingNash equilibriumsemi-infinite programmingunit commitmentspatial price equilibriumnonconvex games
Cites Work
- Equilibrium points in n -person games
- On relaxation algorithms in computation of noncooperative equilibria
- Generalized Nash equilibrium problems
- An overview of bilevel optimization
- Title not available (Why is that?)
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- Global solution of bilevel programs with a nonconvex inner program
- Infinitely constrained optimization problems
- A polyhedral branch-and-cut approach to global optimization
- Potential games
- On generalized semi-infinite optimization and bilevel optimization
- Global solution of nonlinear mixed-integer bilevel programs
- On the copositive representation of binary and continuous nonconvex quadratic programs
- Nash equilibria: the variational approach
- A global optimization algorithm for generalized semi-infinite, continuous minimax with coupled constraints and bi-level problems
- A Shapley value representation of potential games
- Note on noncooperative convex games
- Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions
- Approximations of Nash equilibria
- A note on solving discretely-constrained Nash-Cournot games via complementarity
- Solving discretely-constrained Nash-Cournot games with an application to power markets
- Complementarity modeling in energy markets
- Solving discretely constrained, mixed linear complementarity problems with applications in energy
- How to solve a semi-infinite optimization problem
- Solving Semi-Infinite Optimization Problems with Interior Point Techniques
- On differentiability properties of player convex generalized Nash equilibrium problems
- Generalized semi-infinite programming: a tutorial
- Nonconvex games with side constraints
- Global optimization of semi-infinite programs via restriction of the right-hand side
- An Algorithm for Solving the General Bilevel Programming Problem
- Global optimization of generalized semi-infinite programs via restriction of the right hand side
- Nash equilibria in the two-player kidney exchange game
- On generalized Nash equilibrium problems with linear coupling constraints and mixed-integer variables
- Global optimization of generalized semi-infinite programs using disjunctive programming
- Computing all solutions of Nash equilibrium problems with discrete strategy sets
- Recent advances in nonconvex semi-infinite programming: applications and algorithms
- Alternative models for markets with nonconvexities
- A bridge between bilevel programs and Nash games
- A hybrid discretization algorithm with guaranteed feasibility for the global solution of semi-infinite programs
- Lower level duality and the global solution of generalized semi-infinite programs
- A branch-and-prune algorithm for discrete Nash equilibrium problems
This page was built for publication: Equilibrium modeling and solution approaches inspired by nonconvex bilevel programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6155058)
