On the complexity of equilibria in games with succinct representation

Skopalik, Alexander; Vöcking, Berthold

doi:999910016153

On the complexity of equilibria in games with succinct representation = Die Komplexität von Gleichgewichten in Spielen mit kompakter Darstellung

Skopalik, Alexander (Author)

2010

Verantwortlichkeitsangabevorgelegt von Alexander Skopalik

ImpressumAachen : Publikationsserver der RWTH Aachen University 2010

UmfangVIII, 106 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2010

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Vöcking, Berthold (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2010-08-31

Online
URN: urn:nbn:de:hbz:82-opus-33359
URL: https://publications.rwth-aachen.de/record/63207/files/3335.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Gleichgewichtspunkt <Spieltheorie> (Genormte SW) ; Berechnungskomplexität (Genormte SW) ; Informatik (frei) ; complexity (frei) ; game theory (frei) ; equilibrium (frei)

Thematische Einordnung (Klassifikation)
DDC: 004
ccs: F.2 ANALYS

Kurzfassung
Die algorithmische Spieltheorie beschäftigt sich mit algorithmischen Fragestellungen, die sich aus strategischem Verhalten von Spielern ergeben. In den letzten Jahrzehnten sind Aspekte bezüglich der Berechnungskomplexität in den Fokus der wissenschaftlichen Diskussion gerückt. Ein Grund hierfür ist sicherlich das Aufkommen großer Kommunikationssysteme. Der technische Fortschritt ermöglicht selbst in großen Systeme das Verhalten untereinander interagierender Agenten zu beobachten, auszuwerten und zu beeinflussen. Hier sind viele (zukünftige) Anwendungen denkbar, wie etwa die Verteilung von Gütern und Dienstleistung, die Aufteilung von Ressourcen, die Weiterleitung von Datenpaketen und die Regulierung von Straßenverkehr. Einer der wichtigsten Beiträge der Spieltheorie ist die Fähigkeit Vorhersagen zu treffen, wie solche Spiele gespielt werden. Das häufig genutzte Lösungsmodell sind Gleichgewichtskonzepte, die beschreiben, welche Strategien von den einzelnen Spielern genutzt werden. Eine der wesentlichen Herausforderungen der algorithmischen Spieltheorie ist es die Berechnungskomplexität solcher Gleichgewichte zu charakterisieren. Ergebnisse in dieser Richtung geben wichtige Hinweise darauf, ob spieltheoretische Lösungskonzepte plausibel das Ergebnis in einer kompetitiven Umgebung beschreiben können. Weiterhin, ist die Komplexität natürlich von praktischer Relevanz, wenn man den Ausgang einer strategischen Situation in einer großen Umgebung vorhersagen oder beeinflussen möchte. In der vorliegenden Arbeit beantworten wir fundamentale komplexitätstheoretische Fragen über verschiedene Gleichgewichtskonzepte. Wir untersuchen die Komplexität von Problemen bezüglich der Existenz, dem Erkennen und der Berechnung von Nash Gleichgewichten, starken Gleichgewichten und Senke Gleichgewichten. Das wahrscheinlich bekannteste Lösungskonzept der (nicht kooperativen) Spieltheorie ist das Nash Gleichgewicht – ein Strategieprofil, von dem kein Spieler sich verbessern kann, wenn er unilateral abweicht. Eine Verallgemeinerung des Nash Gleichgewichts ist das Konzept des starken Gleichgewichts – ein Strategieprofil, von dem keine Koalition von Spielern profitabel abweichen kann. Wir betrachten auch die Dynamik die entsteht, wenn Spieler iterativ ihre beste Antwort spielen. Das heiß, in jedem Schritt wählt einer der Spieler die für ihn optimale Strategie wobei die Strategien der anderen Spieler fix sind. Wir identifizieren diejenigen Spiele, in denen dieser Prozess zu einen Gleichgewicht konvergiert und betrachten die Dauer dieses Prozesse. Für Spiele, in denen dieser Prozess nicht konvergiert, wurde das Konzept des Senke Gleichgewichts vorgeschlagen. Anschaulich besteht das Senke Gleichgewicht aus der Menge der Strategieprofile, in die die oben genannte Dynamik letztendlich gelangt ohne sie wieder zu verlassen. Ein solches Senke Gleichgewicht existiert in jedem endlichen Spiel. Wir untersuchen die Komplexität zweier grundlegenden Fragen bezüglich Senke Gleichgewichten – ob ein gegebenes Strategieprofil zu einen Senke Gleichgesicht gehört und ob ein Spiel ein Senke Gleichgewicht besitzt, das aus mehr als einem Strategieprofil besteht. Wir untersuchen diese Gleichgewichtskonzepte in Spielen die eine kompakte Darstellung haben. Im Gegensatz zu Spielen in Normalform, in der Nutzen bzw. die Profite für die Spieler explizit für jedes mögliche Strategieprofil angegeben sind, betrachten wir hier Spiele, denen eine gewisse kombinatorische Struktur zu Grunde liegt, die es erlaubt das Spiel kompakt zu beschreiben. Eine intensiv untersuchte Klasse solcher kompakten Spiele sind Auslastungsspiele. Sie sind ein elegantes Modell um die Effekte von gemeinsamer Ressourcennutzung und steigender Auslastung in Szenarien mit strategisch handelnden Agenten zu beschreiben. Häufig werden sie auch genutzt um Netzwerk Routing in kompetitiven Szenarien zu modellieren. Wir betrachten auch zwei Generalisierungen der Klasse der Auslastungsspiele, nämlich gewichtete und Spieler-spezifische Auslastungsspiele sowie einer weiter Variante in Form der Bottleneck Auslastungsspiele. Weiterhin, untersuchen wir die Klasse der Anonymen Spiele mit einer konstanten Aktionsanzahl. Hier ist der Nutzen eines Spielers unabhängig von der Identität der anderen Spieler, so dass eine Beschreibung des Spiele mit polynoniellen Platzbedarf möglich ist. Schließlich hinterfragen wir die Annahme, dass Spieler egoistisch sind und betrachten ein Szenario in dem Spieler teilweise altruistisch sind. Wir untersuchen die Existenz und die Komplexität von Gleichgewichten und Auslastungsspielen mit solchen Spielern. Einige Ergebnisse lassen sich auf eine Klasse von allgemeinen Potentialspielen und sozialen Kostenfunktion verallgemeinern. Zusätzlich zu diesen Ergebnissen über Unkoordinierte Dynamiken, betrachten wir ein Szenario mit einer zentralen, altruistischen Instanz, die für die einzelnen Spieler Anreizes setzen kann ein bevorzugtest Verhalten zu zeigen.

Algorithmic game theory studies computational and algorithmic questions arising from the behavior of players in strategic situations. The computational aspects of game theory became subject to closer scrutiny in the last two decades. One reason for this is certainly the advent of large scale communication networks – most prominently the Internet. Modern technology allows to monitor, evaluate, and influence the behavior of interacting agents in large systems. One may think of many (future) applications including distribution of goods and services in auctions, allocation of resources, routing of data packages, or regulation of vehicle traffic. One of the main contributions of game theory is the ability to predict how these games will be played. The most commonly used solution concepts are equilibrium concepts that describe which strategies will be adopted by players. One of the central challenges in algorithmic game theory is to characterize the computational complexity of such equilibria. Results in this direction yield important indicators if game-theoretic solution concepts are plausible outcomes of competitive environments in practice. Furthermore, computational complexity is of practical importance if one desires to predict or influence the outcome of a strategic situation in a large-scale environment. In this work, we answer fundamental complexity theoretic questions about several equilibrium concepts. We investigate the complexity of problems regarding the existence, recognition, and computation of Nash equilibria, strong equilibria, and sink equilibria. Probably the most prominent solution concept in (non-cooperative) game theory is the Nash equilibrium – a strategy profile, from which no player can profitably unilaterally deviate. A refinement of Nash equilibria is the concept of strong equilibrium – a strategy profile, from which no coalition wants to jointly deviate. We also study the dynamics that emerge when players iteratively play best responses. That is, in each time step one of the players chooses his optimal strategy given that strategies of the other players are fixed. We identify games in which this process converges to an equilibrium and study the duration of this process. For games in which the best response dynamics does not converge, the concept of sink equilibrium was proposed. Intuitively, a sink equilibrium is the set of strategy profiles on which the aforementioned best response dynamics eventually ends up without leaving this set again. a strongly connected component without outgoing arcs of the A sink equilibrium is guaranteed to exist in every finite game. We study the complexity of two basic questions related to sink equilibria – whether a given strategy profile belongs to a sink equilibrium and whether a game has a sink equilibrium that consists of more than one strategy profile. We study these equilibrium concepts in games that have a succinct representation. Unlike games in normal form, in which the utilities or payoffs for the players are given explicitly for every possible strategy profile of the game, we consider games that have a certain underlying combinatorial structure which allows for a compact description of the game: That is, the description size of the game grows only polynomial with natural parameters such as the number of players or the number of strategies. A well studied class of succinct games are congestion games. They are an elegant model to adress the effects of resource usage and congestion with strategic agents and have been used frequently to model competitive network routing scenarios. We also consider two generalizations of the class of congestion games, namely weighted and player-specific congestion games, and a variation in form of bottleneck congestion games. In addition, we study the class of anonymous games with a constant number of actions. Here, a player's payoff does not depend on the identities of others players, which allows to represent the game in polynomial space. Finally, we question the assumption of selfish players and consider a scenario in which players are partly altruistic. We study the existence and the complexity of equilibria in congestion games with such players. Some of our results can be extended to a class of general potential games and social cost functions, and we study a number of prominent examples. In addition to these results for uncoordinated dynamics, we consider a scenario with a central altruistic institution that can set incentives for the agents to adopt favorable behavior.

Fulltext:
PDF