TU Darmstadt / ULB / TUbiblio

Equilibrium Problems with Complementarity Constraints in Banach Spaces: Stationarity Concepts, Applications and Algorithms

Becker, Jan (2021)
Equilibrium Problems with Complementarity Constraints in Banach Spaces: Stationarity Concepts, Applications and Algorithms.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00019858
Ph.D. Thesis, Primary publication, Publisher's Version

Abstract

In mathematics, the field of non-cooperative game theory models the competition between several parties, which are called players. Therein, each player tries to reach an individual goal, which is described by an optimization problem. However and in contrast to classical nonlinear programming, there exists a dependency between the players, i.e. the choice of a suitable strategy influences the behavior and the reward of the player’s opponents and vice versa. For this reason, a popular solution concept is given by Nash equilibria, which were introduced by John Forbes Nash in his Ph.D. thesis in 1950. In order to prove the existence of a Nash equilibrium, the convexity of the underlying optimization problem is a central requirement. However, this assumption does not hold in general. This thesis is devoted to special equilibrium problems in Banach spaces, which can be described by equilibrium problems with equilibrium/complementarity constraints (EPEC/EPCC). Due to the structure of the underlying feasible set, those games are nonconvex. Motivated by known results with respect to mathematical programs with complementarity constraints, we focus on weaker Nash equilibrium concepts, which can at least be seen as necessary conditions for a Nash equilibrium under suitable assumptions. In the first part of this work, we concentrate on multi-leader multi-follower games, where the participating players are divided hierarchically into leaders and followers, which compete on their particular level with each other. Under suitable assumptions, the solution of the lower level is described by its necessary and sufficient first-order optimality system and can be written as an EPCC. In this context, we first analyze the latter problem in abstract Banach spaces and afterwards, consider the special case of a multi-leader single-follower game (MLFG), where the lower level is given by a quadratic problem in a Hilbert space. For the latter one, we show on the basis of two known penalization techniques that there exist sequences of auxiliary equilibrium problems, which approximate the corresponding EPCC. In the following application that extends known contributions on an optimal control framework of the obstacle problem, we use these auxiliary games and show that both generate sequences, which converge at least to an ϵ-almost C-stationary Nash equilibrium of the original MLFG. The results are analyzed numerically on the basis of a Gauß-Seideltype algorithm and are tested with respect to two examples. The second part is motivated by the work [14] ”A generalized Nash equilibrium approach for optimal control problems of autonomous cars” by Axel Dreves and Matthias Gerdts, where a traffic scenario between several intelligent cars is modeled by a dynamic equilibrium problem. Due to the collision avoidance constraint, this game is non-convex. However, we show that it can be written as a generalized Nash equilibrium problem with mixed-integer variables (MINEP), which again is equivalent to an EPCC. In contrast to the first application, we now concentrate on problems in Lebesgue spaces. In the following, we compare known results from abstract Banach spaces and the corresponding ones in Lebesgue spaces. In particular, we show that for general MINEPs all weak Nash equilibrium concepts coincide. Based on these observations, we apply the results to the traffic scenario. In this context, we again use a penalization technique and deduce by the generated sequence of Nash equilibrium problems that we find a sequence of equilibrium points, which converge to an S-stationary Nash equilibrium of MINEP. We end up with a numerical analysis and test the results with two hypothetical traffic scenarios.

Item Type: Ph.D. Thesis
Erschienen: 2021
Creators: Becker, Jan
Type of entry: Primary publication
Title: Equilibrium Problems with Complementarity Constraints in Banach Spaces: Stationarity Concepts, Applications and Algorithms
Language: English
Referees: Schwartz, Prof. Dr. Alexandra ; Surowiec, Prof. Dr. Thomas M.
Date: 2021
Place of Publication: Darmstadt
Collation: xviii, 159 Seiten
Refereed: 16 March 2021
DOI: 10.26083/tuprints-00019858
URL / URN: https://tuprints.ulb.tu-darmstadt.de/19858
Abstract:

In mathematics, the field of non-cooperative game theory models the competition between several parties, which are called players. Therein, each player tries to reach an individual goal, which is described by an optimization problem. However and in contrast to classical nonlinear programming, there exists a dependency between the players, i.e. the choice of a suitable strategy influences the behavior and the reward of the player’s opponents and vice versa. For this reason, a popular solution concept is given by Nash equilibria, which were introduced by John Forbes Nash in his Ph.D. thesis in 1950. In order to prove the existence of a Nash equilibrium, the convexity of the underlying optimization problem is a central requirement. However, this assumption does not hold in general. This thesis is devoted to special equilibrium problems in Banach spaces, which can be described by equilibrium problems with equilibrium/complementarity constraints (EPEC/EPCC). Due to the structure of the underlying feasible set, those games are nonconvex. Motivated by known results with respect to mathematical programs with complementarity constraints, we focus on weaker Nash equilibrium concepts, which can at least be seen as necessary conditions for a Nash equilibrium under suitable assumptions. In the first part of this work, we concentrate on multi-leader multi-follower games, where the participating players are divided hierarchically into leaders and followers, which compete on their particular level with each other. Under suitable assumptions, the solution of the lower level is described by its necessary and sufficient first-order optimality system and can be written as an EPCC. In this context, we first analyze the latter problem in abstract Banach spaces and afterwards, consider the special case of a multi-leader single-follower game (MLFG), where the lower level is given by a quadratic problem in a Hilbert space. For the latter one, we show on the basis of two known penalization techniques that there exist sequences of auxiliary equilibrium problems, which approximate the corresponding EPCC. In the following application that extends known contributions on an optimal control framework of the obstacle problem, we use these auxiliary games and show that both generate sequences, which converge at least to an ϵ-almost C-stationary Nash equilibrium of the original MLFG. The results are analyzed numerically on the basis of a Gauß-Seideltype algorithm and are tested with respect to two examples. The second part is motivated by the work [14] ”A generalized Nash equilibrium approach for optimal control problems of autonomous cars” by Axel Dreves and Matthias Gerdts, where a traffic scenario between several intelligent cars is modeled by a dynamic equilibrium problem. Due to the collision avoidance constraint, this game is non-convex. However, we show that it can be written as a generalized Nash equilibrium problem with mixed-integer variables (MINEP), which again is equivalent to an EPCC. In contrast to the first application, we now concentrate on problems in Lebesgue spaces. In the following, we compare known results from abstract Banach spaces and the corresponding ones in Lebesgue spaces. In particular, we show that for general MINEPs all weak Nash equilibrium concepts coincide. Based on these observations, we apply the results to the traffic scenario. In this context, we again use a penalization technique and deduce by the generated sequence of Nash equilibrium problems that we find a sequence of equilibrium points, which converge to an S-stationary Nash equilibrium of MINEP. We end up with a numerical analysis and test the results with two hypothetical traffic scenarios.

Alternative Abstract:
Alternative abstract Language

Als Teilgebiet der Mathematik modelliert die nicht-kooperative Spieltheorie den Wettbewerb zwischen mehreren Parteien, genannt Spieler. Diese verfolgen darin individuelle Ziele, welche durch die Minimierung einer Zielfunktion über einer zulässigen Menge dargestellt werden. Im Unterschied zu klassischen Optimierungsproblemen, existiert jedoch eine Abhängigkeit zwischen den Spielern, d.h. die Wahl einer eigenen Strategie hat direkte Auswirkungen auf das Verhalten sowie den Ertrag der Gegner und umgekehrt. Ein mögliches Lösungskonzept ist durch Nash-Gleichgewichte gegeben, welche durch den Namensgeber, John Nash, 1950 in seiner Dissertation untersucht worden sind. Eine zentrale Voraussetzung für die Existenz von Nash-Gleichgewichten ist die Konvexität der einzelnen Optimierungsprobleme, welche jedoch in der Realität nicht immer gegeben ist. Die eingereichte Dissertation untersucht in diesem Zusammenhang spezielle Spiele in Banachräumen, welche durch Gleichgewichtsprobleme mit Gleichgewichtsbeschränkungen (engl. equilibrium problems with equilibrium constraints, EPEC) bzw. Gleichgewichtsprobleme mit Komplementaritätsrestriktionen (engl. equilibrium problems with complementarity constraints, EPCC) beschrieben werden können. Durch die namensgebenden Restriktionen an die zulässige Menge definieren diese nicht-konvexe Probleme in Funktionenräumen. Motiviert durch bekannte Resultate bezüglich mathematischer Programme mit Komplementaritätsnebenbedinungen, weichen wir deshalb auf schwächere Gleichgewichtskonzepte aus, welche unter gewissen Annahmen zumindest notwendige Bedingungen für ein Nash-Gleichgewicht liefern. Der erste Teil der Arbeit beschäftigt sich mit sogenannten Multi-Leader Multi-Follower Spielen (engl. multi-leader multi-follower games, MLMFG), in denen die beteiligten Spieler hierarchisch in Leader und Follower klassifiziert werden und auf beiden Ebenen untereinader konkurrieren. Unter geeigneten Annahmen lässt sich darin die Lösung auf der unteren Stufe durch notwendige und hinreichende Optimalitätsbedingungen erster Ordnung charakterisieren und in ein Gleichgewichtsproblem mit Komplementaritätsrestriktionen überführen. Im weiteren Verlauf untersuchen wir zunächst das daraus resultierende EPCC in abstrakten Banachräumen und betrachten im Anschluss den Spezialfall eines Multi-Leader Single-Follower Spiels, in dem der Follower ein quadratisches Optimierungsproblem in einem Hilbertraum löst. Für dieses konstruieren wir, anhand zweier Penalisierungstechniken, ixFolgen vereinfachter Gleichgewichtsprobleme und zeigen, dass diese das dazugehörige EPCC approximieren. Im daran anschließenden Anwendungsbeispiel, welches auf Arbeiten über die optimale Steuerung des Hindernisproblems in Sobolevräumen aufbaut, nutzen wir diese Hilfsprobleme als Grundlage, um Folgen von Nash-Gleichgewichten zu erzeugen. Für Letztere können wir in beiden Fällen nachweisen, dass sie unter geeigneten Annahmen mindestens gegen ein ϵ-almost C-stationäres Nash-Gleichgewicht des ursprünglichen hierarchischen Spiels konvergieren. Die dabei erhaltenen Ergebnisse analysieren wir im Anschluss numerisch und nutzen Gauß-Seidel-artige Algorithmen um diese anhand ausgewählter Beispiele zu testen. Der zweite Teil der Dissertation ist maßgeblich durch die Arbeit [14] ”A generalized Nash equilibrium approach for optimal control problems of autonomous cars” von Axel Dreves und Mathias Gerdts motiviert, in dem ein Verkehrsszenario zwischen intelligenten Fahrzeugen durch ein dynamisches Gleichgewichtsproblem modelliert wird. Durch die auftretenden Kollisionsvermeidungs-Bedingungen, ist dieses ein nicht-konvexes Spiel, welches durch die spezielle Struktur der erwähnten Restriktion als ein gemischt-ganzzahliges Gleichgewichtsproblem (engl. generalized Nash equilibrium problem with mixed-integer variables, MINEP) beschrieben werden kann. Da die geforderte Ganzzahligkeit äquivalent zu einer Komplementaritätsbedingung ist, erhalten wir auch hier ein EPCC mit dem Unterschied, dass die zugrundeliegenden Komplementaritätsrestriktionen Teil eines Lebesgueraumes sind. Im Anschluss vergleichen wir zunächst die Resultate bezüglich abstrakter Banachräume mit den bereits bekannten Ergebnissen in Lebesgueräumen. Insbesondere zeigen wir, dass in diesem Szenario alle schwachen Gleichgewichtskonzepte identisch sind. Darauf aufbauend werden die Ergebnisse auf das eingangs beschriebene Verkehrszenario übertragen. In diesem Zusammenhang erzeugen wir analog zum ersten Teil durch einen Penalisierungsansatz eine Folge von Gleichgewichtsproblemen und weisen nach, dass die dadurch konstruierte Folge von Nash-Gleichgewichten unter zusätzlichen Voraussetzungen gegen ein S-stationäres Nash-Gleichgewicht von MINEP konvergiert. Die erzielten Resultate werden abschließend numerisch analysiert, implementiert und mittels fiktiver Verkehrssituationen getestet.

German
Status: Publisher's Version
URN: urn:nbn:de:tuda-tuprints-198588
Classification DDC: 500 Science and mathematics > 510 Mathematics
Divisions: 04 Department of Mathematics
04 Department of Mathematics > Optimization
04 Department of Mathematics > Optimization > Nonlinear Optimization
Date Deposited: 16 Nov 2021 12:21
Last Modified: 22 Nov 2021 09:45
PPN:
Referees: Schwartz, Prof. Dr. Alexandra ; Surowiec, Prof. Dr. Thomas M.
Refereed / Verteidigung / mdl. Prüfung: 16 March 2021
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)
Show editorial Details Show editorial Details