Details

Autor(en) / Beteiligte

• Drees, Maximilian
• Skopalik, Alexander[Akademischer Betreuer]
• Meyer auf der Heide, Friedhelm[Akademischer Betreuer]

Titel

Existence and properties of pure nash equilibria in budget games : = Existenz und Eigenschaften von reinen Nash Gleichgewichten in Budgetspielen

Ort / Verlag

Paderborn

Erscheinungsjahr

2016

Link zum Volltext

• Hochschulschriften Visual Library - Scan2Web Hochschulschriften UB Paderborn (s2w-hsspadubpb)

Link zu anderen Inhalten

• Volltext

Verknüpfte Titel

Beschreibungen/Notizen

• Tag der Verteidigung: 27.06.2016
• Open Access
• ger: 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.
• eng: 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.