Equilibrium modeling and solution approaches inspired by nonconvex bilevel programming
From MaRDI portal
Publication:6155058
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.
Recommendations
- A branch-and-bound algorithm for nonconvex Nash equilibrium problems
- Using EPECs to Model Bilevel Games in Restructured Electricity Markets with Locational Prices
- Bilevel Nash equilibrium problems: numerical approximation via direct-search methods
- A metaheuristic approach to compute pure Nash equilibria
- A mixed 0-1 linear programming approach to the computation of all pure-strategy Nash equilibria of a finite \(n\)-person game in normal form
Cites work
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- A Shapley value representation of potential games
- A branch-and-prune algorithm for discrete Nash equilibrium problems
- A bridge between bilevel programs and Nash games
- A global optimization algorithm for generalized semi-infinite, continuous minimax with coupled constraints and bi-level problems
- A hybrid discretization algorithm with guaranteed feasibility for the global solution of semi-infinite programs
- A note on solving discretely-constrained Nash-Cournot games via complementarity
- A polyhedral branch-and-cut approach to global optimization
- Alternative models for markets with nonconvexities
- An Algorithm for Solving the General Bilevel Programming Problem
- An overview of bilevel optimization
- Approximations of Nash equilibria
- Complementarity modeling in energy markets
- Computing all solutions of Nash equilibrium problems with discrete strategy sets
- Equilibrium points in n -person games
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- Generalized Nash equilibrium problems
- Generalized semi-infinite programming: a tutorial
- Global optimization of generalized semi-infinite programs using disjunctive programming
- Global optimization of generalized semi-infinite programs via restriction of the right hand side
- Global optimization of semi-infinite programs via restriction of the right-hand side
- Global solution of bilevel programs with a nonconvex inner program
- Global solution of nonlinear mixed-integer bilevel programs
- How to solve a semi-infinite optimization problem
- Infinitely constrained optimization problems
- Lower level duality and the global solution of generalized semi-infinite programs
- Nash equilibria in the two-player kidney exchange game
- Nash equilibria: the variational approach
- Nonconvex games with side constraints
- Note on noncooperative convex games
- On differentiability properties of player convex generalized Nash equilibrium problems
- On generalized Nash equilibrium problems with linear coupling constraints and mixed-integer variables
- On generalized semi-infinite optimization and bilevel optimization
- On relaxation algorithms in computation of noncooperative equilibria
- On the copositive representation of binary and continuous nonconvex quadratic programs
- Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions
- Potential games
- Recent advances in nonconvex semi-infinite programming: applications and algorithms
- Solving Semi-Infinite Optimization Problems with Interior Point Techniques
- Solving discretely constrained, mixed linear complementarity problems with applications in energy
- Solving discretely-constrained Nash-Cournot games with an application to power markets
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)
