Zur Seitenansicht
 

Titelaufnahme

Titel
Existenz und Eigenschaften von reinen Nash Gleichgewichten in Budgetspielen
AutorDrees, Maximilian
BeteiligteSkopalik, Alexander In der Gemeinsamen Normdatei der DNB nachschlagen ; Meyer auf der Heide, Friedhelm In der Gemeinsamen Normdatei der DNB nachschlagen
ErschienenPaderborn, 2016
Ausgabe
Elektronische Ressource
Umfang1 Online-Ressource (x, 110 Seiten) : Diagramme
HochschulschriftUniversität Paderborn, Univ., Dissertation, 2016
Anmerkung
Tag der Verteidigung: 27.06.2016
Verteidigung2016-06-27
SpracheEnglisch ; Deutsch
DokumenttypDissertation
URNurn:nbn:de:hbz:466:2-24915 Persistent Identifier (URN)
Dateien
Existence and properties of pure nash equilibria in budget games [0.83 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Wir definieren das spieltheoretische Modell von Budgetspielen und analysieren die Existenz von reinen Nash Gleichgewichten (NG). In einem Budgetspiel konkurieren die Spieler um Ressourcen mit begrenztem Budget. Als Strategie wählen sie zwischen einer endlichen Anzahl von Anforderungsvektoren, welche nicht-negative Anforderung an die Ressourcen enthalten. Falls die Anforderungen aller Spieler an eine einzige Ressource nicht ihr Budget überschreiten, so entspricht der Gewinn eines Spieler durch diese Ressource seiner Anforderung. Andernfalls wird das Budget im Verhältnis zu den Anforderungen aufgeteilt. Für jede Kombination von Spieler und Ressourcen hängt die entsprechende Anforderung direkt von der Strategie des Spielers ab und kann sich während der best-response Dynamik ändern. Wir zeigen, dass im Allgemeinen keine NG in Budgetspielen existieren. Anschließend betrachten wir alternative Konzepte. (1) Geordnete Budgetspiele sind eine Variante, welche die Reihenfolge betonen in welcher die Spieler ihre Strategien wählen. Sie sind exakte Potenzialspiele, für die sogar die Existenz von superstarken NG garantiert werden kann und starke NG effizient berechnet werden können. (2) In einem Alpha-approximierten NG kann kein Spieler seinen Gewinn durch einen einseitigen Strategiewechsel um mehr als einen konstanten Faktor Alpha erhöhen. Wir geben obere und untere Schranken für Alpha an, so dass approxmierte NG in Budgetspiele garantiert sind. Darüber hinaus betrachten wir eine approximierte Version der best-response Dynamik, die schnell konvergiert und dazu verwendet werden kann, ein Strategieprofil zu berechnen welches den maximalen sozialen Wohlstand approximiert. (3) Durch Einschränken der Struktur der Strategieräume stellen wir die Existenz von NG wieder her. Dabei konzentrieren wir uns auf Singleton und Matroid Budgetspiele.

Zusammenfassung (Englisch)

We introduce the game-theoretical model of budget games and analyze the existence of pure Nash equilibria. In a budget game, players compete over resources with a limited budget. As his strategy, each player decides between a finite number of demand vectors. Each demand vector contains one non-negative demand for every resource. Provided the total demand by all players on a single resource does not exceed its budget, the utility each player receives from that resource equals his demand. Otherwise, the budget is split proportionally to the demands. For any combination of player and resource, the corresponding demand is directly tied to the players strategy and can change during the best-response dynamic. After showing that pure Nash equilibria generally do not exist in budget games, we consider several alternative concepts. (1) Ordered budget games are a variation which emphasizes the order in which the players choose their strategies. They are exact potential games for which even the existence of super-strong pure Nash equilibria can be guaranteed and strong pure Nash equilibria can be computed efficiently. (2) In an alpha-approximate pure Nash equilibrium, no unilateral strategy change increases the utility of the corresponding player by more than some constant factor alpha. We give upper and lower bound on alpha such that approximate pure Nash equilibria are guaranteed. In addition, we look at an approximate version of the best-response dynamic which converges quickly and can also be used to compute a strategy profile which approximates the maximal social welfare. (3) By restricting the structure of the strategy spaces, we restore pure Nash equilibria to budget games. We focus on singleton and matroid budget games. We also argue that computing the socially optimal solution is equivalent for both budget games and ordered budget games and NP-hard in both cases.