Optimierung und verallgemeinerte Nash-Gleichgewichte
Final Report Abstract
In diesem Projekt wurden nicht-kooperative Spiele untersucht, bei denen jeder Teilnehmer ohne Absprache mit den anderen versucht, seinen eigenen Gewinn zu maximieren. Dabei müssen von jedem Spieler gewisse Restriktionen, die von den übrigen Spielern abhängen können, eingehalten werden. Derartige Aufgabenstellungen werden als verallgemeinerte Nash-Gleichgewichtsprobleme bezeichnet. Als Lösungen solcher Probleme betrachtet man Spielsituationen, in denen kein Spieler durch einen alleinigen Strategiewechsel seinen Gewinn erhöhen kann (Nash-Lösungskonzept). Diese spieltheoredschen Probleme wurden auf verschiedene Arten als Optimierungsprobleme umformuliert. Es wurde gezeigt, dass man für diese Probleme bekannte Optimierungsverfahren anpassen kann, um somit Lösungen des ursprünglichen Problems zu berechnen. Hierdurch sind mehrere Algorithmen entstanden, die entweder möglichst viele verschiedene Lösungen, oder aber ganz bestimmte findenkönnen. Ferner solche, die lokal sehr schnell konvergieren, und auch solche, die durch sehr große Robustheit glänzen. Überraschend war vor allem, dass dem eigentlich naheliegenden Ansatz der Betrachtung der gemeinsamen Karush-Kuhn-Tucker-Bedingungen der Optimierungsprobleme der einzelnen Spieler bisher in der Literatur eher wenig Beachtung geschenkt wurde. Hier ließen sich sehr gute theoretische und numerische Resultate zeigen. Offen geblieben ist die Frage nach einem Stationaritätsresultat für die unrestringierten (oder auch für die restringierten) Optimierungsumformulierungen der GNEPs: Gibt es (nicht allzu restriktive) Bedingungen, unter denen stationäre Punkte von Vαβ auch verallgemeinerte Nash-Gleichgewichte sind?
Publications
- A globalized Newton method for the computation of normalized Nash equilibria. Journal of Global Optimization, 2011
A. Dreves, A. von Heusinger, C. Kanzow, M. Fukushima
(See online at https://doi.org/10.1007/s10898-011-9824-9) - Nonsmooth optimization reformulations characterizing all solutions of jointly convex generalized Nash equilibrium problems. Computational Optimization and Applications 50, 2011, 23-48
A. Dreves und C. Kanzow
- On the solution of the KKT conditions of generalized Nash equilibrium problems. SIAM Journal on Optimization 21,2011, 1082-1108
A. Dreves, F. Facchinei, C. Kanzow, S. Sagratella
- Globally Convergent Algorithms for the Solution of Generalized Nash Equilibrium Problems. Dissertation, Fakultät für Mathematik und Informatik, Universität Würzburg, März 2012
A. Dreves
- Nonsmooth optimization reformulations of player convex generalized Nash equilibrium problems. Journal of Global Optimization 53, 2012, 587-614
A. Dreves, C. Kanzow und O. Stein
(See online at https://doi.org/10.1007/s10898-011-9727-9)
