Abstract
dc:descriptionGlobal 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.
Degree
thesis:*- Grantor dc:publisher
- Publikationsserver der RWTH Aachen University
- Year dc:date
- 2010
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Olbrich, Lars
- Contributors dc:contributor
-
- Vöcking, Berthold
Subjects
dc:subject × 5Rights
dc:rights- Statement dc:rights
-
- info:eu-repo/semantics/openAccess
- Language dc:language
- eng