TU Darmstadt / ULB / TUprints

Nonconvex Nash Games : Solution Concepts and Algorithms

Nowak, Daniel (2021):
Nonconvex Nash Games : Solution Concepts and Algorithms. (Publisher's Version)
Darmstadt, Technische Universität,
DOI: 10.26083/tuprints-00017637,
[Ph.D. Thesis]

[img]
Preview
Text
Dissertation_Daniel_Nowak.pdf
Available under CC-BY-NC-ND 4.0 International - Creative Commons, Attribution Non-commerical, No-derivatives.

Download (2MB) | Preview
Item Type: Ph.D. Thesis
Status: Publisher's Version
Title: Nonconvex Nash Games : Solution Concepts and Algorithms
Language: English
Abstract:

Game theory is a mathematical approach to model competition between several parties, called players. The goal of each player is to choose a strategy, which solves his optimization problem, i.e. minimizes or maximizes his objective function. Due to the competitive setting, this strategy may influence the optimization problems of other players. In the non-cooperative setting each player acts selfish, meaning he does not care about the objective of his opponents. A solution concept for this problem is a Nash equilibrium, which was introduced by John Forbes Nash in his Ph.D. thesis in 1950. Convexity of the optimization problems is a crucial assumption for the existence of Nash equilibria. This work investigates settings, where this convexity assumption fails to hold.

The first part of this thesis extends results of Jong-Shi Pang and Gesualdo Scutari from their paper "Nonconvex Games with Side Constraints'' published in 2011. In this publication, a game with possibly nonconvex objective functions and nonconvex individual and shared inequality constraints was investigated. We extend these results twofold. Firstly, we generalize the individual and shared polyhedral constraints to general convex constraints and, secondly, we introduce convex and nonconvex, individual and shared equality constraints. After a detailed comparison of solution concepts for the generalized Nash game and a related Nash game, we show that so-called quasi-Nash equilibria exist under similar assumptions than in the original work, provided some additional constraint qualification holds. Subsequently, we prove that the existence of Nash equilibria needs additional assumptions on the gradients of the equality constraints. Furthermore, a special case of a multi-leader multi-follower game is investigated. We show the convergence of epsilon-quasi-Nash equilibria to C-stationary points and prove that these are also Clarke-stationary under reasonable assumptions.

In the second part of this thesis, an application in computation offloading is investigated. We consider several mobile users that are able to offload parts of a computation task to a connected server. However, the server has limited computation capacities which leads to competition among the mobile users. If a user decides to offload a part of his computation, he needs to wait for the server to finish before he can assemble the results of his computation. This leads to a vanishing constraint in the optimization problem of the mobile users which is a nonconvex and nonsmooth condition. We show the existence of a unique Nash equilibrium for the computation offloading game and provide an efficient algorithm for its computation. Furthermore, we present two extensions to this game, which inherit similar properties and we also show the limitations of these formulations.

The third part investigates a hierarchical constrained Cournot game. In the upper level, several firms decide on capacities which act as constraints for the production variables. In the lower level the same firms engage in a Cournot competition, where they choose production variables to maximize profit. The prior chosen capacities are upper bounds on these production variables. This hierarchical setting induces nonconvexity and nonsmoothness in the upper level objective functions. After a detailed sensitivity analysis of the lower level, we give necessary optimality conditions for the upper level, i.e. for the hierarchical Cournot game. Using these conditions, we construct an algorithm which provably finds all Nash equilibria of the game, provided some assumptions are satisfied. This algorithm is numerically tested on several examples which are motivated by the gas market.

Alternative Abstract:
Alternative AbstractLanguage

In der Mathematik behandelt das Feld der nicht-kooperativen Spieltheorie den Wettbewerb zwischen mehreren Parteien, genannt Spieler. Jeder Spieler verfolgt eigene Ziele, was durch die Wahl von Strategievariablen in einem Optimierungsproblem dargestellt wird. Der Unterschied zu regulären Optimierungsproblemen ist, dass mehrere Optimierungsprobleme in der Spieltheorie gekoppelt sind. Die Spieler beeinflussen also die Probleme und somit die optimalen Strategien ihrer Gegner. Ein Lösungskonzept sind Nash-Gleichgewichte, welche von John Forbes Nash 1950/51 eingeführt wurden. Ein Nash-Gleichgewicht ist ein stabiler Punkt des Spiels, das heißt kein Spieler kann sich verbessern wenn die Variablen seiner Gegner festgehalten werden.

Eine zentrale Voraussetzung für die Existenz solcher Nash-Gleichgewichte ist die Konvexität der Optimierungsprobleme. Viele Anwendungen resultieren allerdings in nicht-konvexen oder nicht-glatten Problemen, für die die Existenz von Nash-Gleichgewichten nicht notwendigerweise gegeben ist. Diese Dissertation beschäftigt sich mit der Frage, welche Ergebnisse ohne Konvexitätsannahme an die Probleme noch erzielt werden können.

Im ersten Teil der Dissertation werden Ergebnisse von Jong-Shi Pang und Gesualdo Scutari aus der Veröffentlichung "Nonconvex Games with Side Constraints'' zu nicht-konvexen Spielen erweitert. Wir ergänzen diese Ergebnisse um konvexe und nicht-konvexe Gleichungsnebenbedingungen und verallgemeinern alle Formulierungen auf generell konvexe Nebenbedingungen, welche in der ursprünglichen Veröffentlichung als polyedrisch angenommen werden. In der Arbeit wird eine detaillierte Übersicht der Zusammenhänge von verschiedenen Lösungskonzepten bezüglich zwei Formulierungen von Spielen ausgearbeitet. Wir zeigen, dass sogenannte Quasi-Nash-Gleichgewichte unter ähnlichen Bedingungen existieren wie in der Originalarbeit, wobei jedoch zusätzlich Constraint Qualifications erfüllt sein müssen. Weiterhin wird gezeigt, dass für die Existenz von Nash-Gleichgewichten zusätzlich zu den von Pang und Scutari genannten Voraussetzungen noch weitere Bedingungen an die Gradienten der Gleichungsnebenbedingungen erfüllt sein müssen. Abschließend untersuchen wir ein spezielles hierarchisches Spiel, für das sogenannte Epsilon-Quasi-Nash-Gleichgewichte eingeführt werden. Wir zeigen, dass diese gegen C-stationäre Punkte konvergieren, welche in unserem Fall auch Clarke-stationär sind.

Der zweite Teil der Dissertation beschäftigt sich mit einer Anwendung in der Nachrichtentechnik, bei der mehrere Nutzer von mobilen Endgeräten um die Ressourcen eines Servers konkurrieren. Hierbei versuchen die Nutzer Berechnungen von ihren mobilen Endgeräten auf den Server auszulagern, welcher jedoch eine begrenzte Kapazität hat. Falls ein Nutzer einen Teil seiner Berechnung auslagert, muss er auf die Fertigstellung der Berechnungen des Servers warten. Dies resultiert in sogenannten "vanishing constraints'' im zugehörigen Optimalitätsproblem, welche nicht-glatt und nicht-konvex sind. Wir zeigen, dass dieses Spiel ein eindeutiges Nash-Gleichgewicht hat und geben einen effizienten Algorithmus an dieses zu berechnen. Es werden zwei Verallgemeinerungen des Spiels vorgestellt, wobei viele wesentliche Eigenschaften erhalten werden können.

Im dritten Teil betrachten wir ein hierarschisches, kapazitätsbeschränktes Cournot-Nash-Spiel, welches durch die Hierarchie auch nicht-konvex und nicht-glatt ist. Hierbei wählen Firmen im oberen Level Kapazitätsschranken und versuchen im unteren Level unter Wettbewerb maximalen Profit zu erwirtschaften, wobei die Kapazitätsschranken respektiert werden müssen. Nach einer detaillierten Sensitivitätsanalyse des unteren Levels leiten wir notwendige Optimalitätsbedingungen für Nash-Gleichgewichte des hierarchischen Spiels her. Ferner konstruieren wir einen Algorithmus und zeigen, dass dieser unter gewissen Voraussetzungen alle Nash Gleichgewichte des Spiels findet. Numerisch wird der Algorithmus anhand mehrerer Beispielprobleme getestet, welche hauptsächlich in der Modellierung von Gasmärkten Anwendung haben.

German
Place of Publication: Darmstadt
Collation: xi, 175 Seiten
Classification DDC: 500 Naturwissenschaften und Mathematik > 510 Mathematik
Divisions: DFG-Collaborative Research Centres (incl. Transregio) > Transregios > TRR 154 Mathematical Modelling, Simulation and Optimization using the Example of Gas Networks
Exzellenzinitiative > Graduate Schools > Graduate School of Computational Engineering (CE)
04 Department of Mathematics > Optimization > Nonlinear Optimization
TU-Projects: DFG|TRR154|TPB09SchwartzTRR154
Date Deposited: 13 Apr 2021 08:47
Last Modified: 13 Apr 2021 08:47
DOI: 10.26083/tuprints-00017637
URN: urn:nbn:de:tuda-tuprints-176371
Referees: Schwartz, Prof. Dr. Alexandra ; Schmidt, Prof. Dr. Martin
Refereed: 29 January 2021
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/17637
Export:
Actions (login required)
View Item View Item