Equilibrium modeling and solution approaches inspired by nonconvex bilevel programming

Stuart Harwood (), Francisco Trespalacios, Dimitri Papageorgiou and Kevin Furman
Additional contact information
Stuart Harwood: ExxonMobil Corporate Strategic Research
Francisco Trespalacios: ExxonMobil Upstream Research Company
Dimitri Papageorgiou: ExxonMobil Corporate Strategic Research
Kevin Furman: ExxonMobil Upstream Research Company

Computational Optimization and Applications, 2024, vol. 87, issue 2, No 11, 676 pages

Abstract: Abstract Methods for finding pure Nash equilibria 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 Nash equilibrium using theory and methods for the global optimization of nonconvex bilevel programs. Through this perspective, we draw precise connections between 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 an 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. Our computational examples include practical applications like unit commitment in electricity markets.

Keywords: Nash equilibrium; Nonconvex games; Bilevel programming; Semi-infinite programming; Global optimization; Unit commitment; Spatial price equilibrium (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-023-00524-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:coopap:v:87:y:2024:i:2:d:10.1007_s10589-023-00524-w

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-023-00524-w

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().