On Intrinsic Complexity of Nash Equilibrium Problems and Bilevel Optimization

D. Dorsch (), H. T. Jongen and V. Shikhman
Additional contact information
D. Dorsch: RWTH Aachen University
H. T. Jongen: RWTH Aachen University
V. Shikhman: Catholic University of Louvain (UCL)

Journal of Optimization Theory and Applications, 2013, vol. 159, issue 3, No 5, 606-634

Abstract: Abstract In this article we study generalized Nash equilibrium problems (GNEP) and bilevel optimization side by side. This perspective comes from the crucial fact that both problems heavily depend on parametric issues. Observing the intrinsic complexity of GNEP and bilevel optimization, we emphasize that it originates from unavoidable degeneracies occurring in parametric optimization. Under intrinsic complexity, we understand the involved geometrical complexity of Nash equilibria and bilevel feasible sets, such as the appearance of kinks and boundary points, non-closedness, discontinuity and bifurcation effects. The main goal is to illustrate the complexity of those problems originating from parametric optimization and singularity theory. By taking the study of singularities in parametric optimization into account, the structural analysis of Nash equilibria and bilevel feasible sets is performed. For GNEPs, the number of players’ common constraints becomes crucial. In fact, for GNEPs without common constraints and for classical NEPs we show that—generically—all Nash equilibria are jointly nondegenerate Karush–Kuhn–Tucker points. Consequently, they are isolated. However, in presence of common constraints Nash equilibria will constitute a higher dimensional set. In bilevel optimization, we describe the global structure of the bilevel feasible set in case of a one-dimensional leader’s variable. We point out that the typical discontinuities of the leader’s objective function will be caused by follower’s singularities. The latter phenomenon occurs independently of the viewpoint of the optimistic or pessimistic approach. In case of higher dimensions, optimistic and pessimistic approaches are discussed with respect to possible bifurcation of the follower’s solutions.

Keywords: Generalized Nash equilibrium problem; Bilevel optimization; Parametric optimization; Singularities; Bilevel feasible set (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-012-0210-7 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:joptap:v:159:y:2013:i:3:d:10.1007_s10957-012-0210-7

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-012-0210-7

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

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