Geometry of the sets of Nash equilibria in mixed extensions of finite games

Vujić, Matija

PDF
Dissertation_Vujic.pdf - Veröffentlichte Version
Download (1MB)

URN:	urn:nbn:de:bsz:180-madoc-641559
Dokumenttyp:	Dissertation
Erscheinungsjahr:	2023
Ort der Veröffentlichung:	Mannheim
Hochschule:	Universität Mannheim
Gutachter:	Hertling, Claus
Datum der mündl. Prüfung:	23 März 2023
Sprache der Veröffentlichung:	Englisch
Einrichtung:	Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Algebraische Geometrie (Hertling 2005-)
Fachgebiet:	510 Mathematik
Freie Schlagwörter (Deutsch):	Nash-Gleichgewicht , gemischte Erweiterung eines endlichen Spiels
Freie Schlagwörter (Englisch):	Nash equilibrium , mixed extension of a finite game
Abstract:	The theory of strategic games in normal form is a part of game theory. The most important solution concept for them is the notion of a Nash equilibrium. Nash defined it and proved that the mixed extension of any finite game has Nash equilibria. Here the space in which the Nash equilibria live is a product of simplices, namely a product of spaces of probability distributions, each over a finite set of pure strategies. The existence leads to questions on the shape of the set of all Nash equilibria for a given game. In this thesis we concentrate on generic games. There it is well-known that the number of Nash equilibria is finite and odd. It is interesting to think about the maximal number of Nash equilibria in generic games with fixed number of players and fixed finite sets of pure strategies. In general, the precise number is unknown. But in the case of 2 players, there are good upper and lower bounds, which are not so far apart. In the case of m ≥ 3 players, up to now only an upper bound was known. In the case of m players each of whom has exactly two pure strategies, we present a lower bound, which is surprisingly close to the known upper bound. It is more than half of the upper bound. This result was the outcome of a mixture of conceptual and calculational steps. We present more calculational results for such games. We also study with computer a certain 2-person game where each player has six pure strategies. One chapter recalls a good part of the history of the problem. The penultimate chapter works out an old foundational result on the union of the sets of mixed Nash equilibria for all games with fixed player set and fixed finite sets of pure strategies. The second chapter presents a stronger result on generic games than can be found in the literature. The product of simplices embeds naturally into a product of real projective spaces. The equalities and inequalities for Nash equilibria make sense in this bigger space. In the case of generic games all involved hypersurfaces are smooth and maximally transversal in this bigger space.
Übersetzter Titel:	Geometrie der Mengen der Nash-Gleichgewichte in gemischten Erweiterungen endlicher Spiele (Deutsch)
Übersetzung des Abstracts:	Die Theorie der strategischen Spiele in Normalform ist ein Teil der Spieltheorie. Das wichtigste Lösungsbegriff for diese ist der Begriff des Nash-Gleichgewichts. Nash definierte es und bewies, dass die gemischte Erweiterung jedes endlichen Spiels Nash-Gleichgewichte hat. Der Raum, in welchem Nash-Gleichgewichte liegen, ist ein Produkt von Simplizes, und zwar ein Produktraum von Wahrscheinlichkeitsverteilungen. Die Existenz führt zu Fragen über die Gestalt der Menge aller Nash-Gleichgewichte für ein gegebenes Spiel. Wir konzentrieren uns in dieser Dissertation auf generische Spiele. Dort ist wohlbekannt, dass die Anzahl der Nash-Gleichgewichte endlich und ungerade ist. Es ist interessant, sich über die maximale Anzahl der Nash-Gleichgewichte bei generischen Spielen mit fester Spieleranzahl und festen endlichen reinen Strategiemengen Gedanken zu machen. Im Allgemeinen ist die genaue Anzahl unbekannt, aber im Fall von 2 Spielern gibt es gute obere und untere Schranken. Im Fall m ≥ 3 war bis jetzt nur eine obere Schranke bekannt. Im Fall mit Spielern, wobei jeder Spieler genau zwei reine Strategien hat, beweisen wir eine untere Schranke, welche überraschend nah an der bekannten oberen Schranke ist. Sie ist größer als die Hälfte der oberen Schranke. Das Resultat war die Folge einer Mischung von konzeptionellen und rechnerischen Schritten. Wie stellen mehrere rechnerische Resultate für solche Spiele dar. Außerdem betrachten wir mithilfe eines Computers ein bestimmtes 2-Personenspiel, wobei jeder Spieler sechs reine Strategien hat. Ein Kapitel betrachtet ein gutes Stück der Geschichte der Aufgabenstellung. Das vorletzte Kapitel betrachtet ein altes und grundlegendes Resultat über die Vereinigung der Mengen der gemischten Nash-Gleichgewichte für alle Spiele mit fester Spieleranzahl und festen endlichen Strategiemengen. Das zweite Kapitel präsentiert ein stärkeres Resultat über generische Spiele, als in der Literatur gefunden werden kann. Das Produkt der Simplizes bettet sich in natürlicher Weise in ein Produkt reeller projektiver Räume ein. Die Gleichungen und Ungleichungen für Nash-Gleichgewichte ergeben in diesem größeren Raum Sinn. In dem Fall von generischen Spielen sind alle beteiligten Hyperflächen glatt und maximal transversal in dem größeren Raum. (Deutsch)