Aspects of Wardrop equilibria

Olbrich, Lars; Vöcking, Berthold

doi:3179

Aspects of Wardrop equilibria = Aspekte von Wardrop Gleichgewichten

Olbrich, Lars (Author)

2010

Verantwortlichkeitsangabevorgelegt von Lars Olbrich

ImpressumAachen : Publikationsserver der RWTH Aachen University 2010

Umfang118 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2010

Zusammenfassung in engl. und dt. Sprache

Genehmigende Fakultät
Fak01

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

Tag der mündlichen Prüfung/Habilitation
2010-02-22

Online
URN: urn:nbn:de:hbz:82-opus-31796
URL: https://publications.rwth-aachen.de/record/50519/files/Olbrich_Lars.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Spieltheorie (Genormte SW) ; Informatik (frei) ; game theory (frei) ; selfish routing (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Weltweite Kommunikationsnetzwerke wie das Internet können nicht zentral gesteuert werden. Benutzer solcher Netzwerke handeln eigennützig, ohne die Gesamtleistung des Systems zubeachten. Solch komplexe Strukturen führten zu einem Paradigmenshift in der Informatik. Während traditionelle Konzepte für überschaubare Netzwerke konzipiert wurden, stellt die nicht-kooperative Spieltheorie die benötigten Techniken zur Analyse von Verkehr in heutigen Netzwerken zur Verfügung. Gegenstand dieser Arbeit sind Gleichgewichtszustände im von Wardrop in den 1950er Jahren eingeführten Verkehrsmodell. In Wardrops Modell wird Verkehr als Fluß zwischen Paaren von Knoten in einem Graphen modelliert. Latenzfunktionen beschreiben die flußabhängigen Latenz einer Kante. Eine weitverbreitete Interpretation des Modells ist, das unendlich viele Agenten jeweils einen infinitesimal kleinen Flußbetrag kontrollieren. Die Kosten jedes Agenten sind genau die Summe der Kantenlatenzen auf dem von ihm gewählten Pfad. Ein Wardrop Gleichgewicht ist einen Zustand, in dem jeder Agent einen latenzminimalen Pfad zwischen seinem Start- und Zielknoten gewählt hat. Es ist bekannt, dass die Netzwerklatenz in Wardrop Gleichgewichten nicht minimiert wird. Darüberhinaus zeigt das Braess Paradox, dass das Hinzufügen von Kapazität die Netzwerkleistung sogar verschlechtern kann. In dieser Arbeit analysieren wir wichtige Probleme, die zum Verständnis der Wardrop Gleichgewichte beitragen. Es ist lange bekannt, dass wenn beliebige Steuern auf jeder Kante erhoben werden können, ein bezüglich der Gesamtlatenz optimaler Gleichgewichtsfluss erreicht werden kann. Wir untersuchen den Fall, dass Steuern nur auf einigen Kanten erhoben werden können. Für beliebige Netzwerke zeigen wir dass optimale Steuern NP-schwer zu berechnen sind. Auf der anderen Seite präsentieren wir für einfache Netzwerkstrukturen einen effizienten Algorithmus. Anschließend führen wir mit dem Konzept des Hilfsflusses einen alternativen Ansatz zur Verbesserung von Gleichgewichten ein. Wir konzentrieren uns auf die Komplexität der wesentlichen damit verbundenen Optimierungsprobleme. In einem weiteren Kapitel studieren wir die Sensitivität von Wardrop Gleichgewichten bezüglich Änderungen entscheidender Netzwerkparameter und erhalten positive und negative Ergebnisse zu allen wichtigen Gleichgewichtsmerkmalen. Abschließend analysieren wir wie Agenten mit nur wenig Information ein Gleichgewicht erreichen können. Basierend auf einer existierenden rundenbasierten Imitationsdynamik entwickeln wir einen verteilten Algorithmus, der in erwarteter polynomieller Zeit zu einem approximativem Gleichgewicht konvergiert.

Global communication networks like the Internet often lack a central authority that monitors and regulates network traffic. Network users may behave selfishly according to their private interest without regard to the overall system performance. Such highly complex environments prompted a paradigm shift in computer science. Whereas traditional concepts are designed for stand-alone machines and manageable networks, a profound understanding of large-scale communication systems with strategic users requires to combine methods from theoretical computer science with game-theoretic techniques. In this thesis, we study equilibrium situations in Wardrop’s traffic model. In Wardrop’s model a rate of traffic between each pair of vertices of a network is modeled as network flow, i. e., traffic is allowed to split into arbitrary pieces. The resources are the network edges with latency functions quantifying the time needed to traverse an edge. The latency of an edge depends on the congestion. It increases the more flow traverses that edge. A common interpretation of the Wardrop model is that flow is controlled by an infinite number of agents each of which is responsible to route an infinitesimal amount of traffic between its origin and destination vertex. Each agent plays a pure strategy in choosing one path from its origin to its destination, where the agent’s disutility is the sum of edge latencies on this path. A Wardrop equilibrium denotes a strategy profile in which all used paths between a given origin-destination pair have equal and minimal latency. Wardrop equilibria are also Nash equilibria as no agent can decrease its experienced latency by unilaterally deviating to another path. Like Nash equilibria in general, Wardrop equilibria do not optimize any global objective per se. In particular, the total latency of all agents is not minimized at Wardrop equilibrium. Addressing this issue, Roughgarden and Tardos gave tight bounds on the price of anarchy measuring the worst-possible inefficiency of equilibria with respect to the incurred latency. Further, the famous Braess’s paradox states that adding edges to a network may in fact worsen the unique equilibrium. The primary goal of this thesis is to provide a deeper understanding of Wardrop equilibria. We identify several problems whose solution captures the essence of Wardrop equilibria. First, we study natural and innovative means to reduce the price of anarchy. Secondly, we analyze the stability of equilibria regarding modifications of the network environment. Finally, we propose a distributed algorithm for computing approximate equilibria. The inefficiency of equilibria motivates our first line of research. In Wardrop’s model, imposing marginal cost taxes on every edge completely eliminates the inefficiency of selfish routing. We concentrate on optimal taxes for the crucial and more realistic case in which only a given subset of the edges can be taxed. We establish NP-hardness of this optimization problem in general networks. On the positive side, we provide a polynomial time algorithm for computing optimal taxes in parallel link networks with linear latency functions. We also propose a novel approach to improve the performance of selfish flow in networks by additionally routing flow, called auxiliary flow. We focus on the computational complexity for the optimal utilization of auxiliary flow and present strong inapproximability results. In particular, the minimal amount of auxiliary flow needed to induce an optimal flow as the outcome of selfish behavior cannot be approximated by any subexponential factor. Further, we study the sensitivity of Wardrop equilibria. From both the practical and the theoretical perspective it is a natural and intriguing question, how equilibria respond to slight modifications of either the network topology or the traffic flow. We show positive and negative results on the stability of flow pattern and flow characteristics at equilibrium. As it is fundamental for the above studies that selfish behavior in network routing games yields an equilibrium, it is not clear how the set of agents can attain an equilibrium in the first place. In previous work it was shown that an infinite set of selfish agents can approach Wardrop equilibria quickly by following a simple round-based load-adaptive rerouting policy relying on very mild assumptions only. We convert this policy into an efficient, distributed algorithm for computing approximate Wardrop equilibria for a slightly different setting in which the flow is controlled by a finite number of agents only each of which aims at balancing the entire flow of one commodity. We show that an approximate equilibrium in which only a small fraction of the agents sustains latency significantly above average is reached in expected polynomial time.

Fulltext:
PDF