91-XX GAME THEORY, ECONOMICS, SOCIAL AND BEHAVIORAL SCIENCES
Refine
Document Type
- Doctoral Thesis (1)
- ZIB-Report (1)
Language
- English (2)
Has Fulltext
- yes (2)
Is part of the Bibliography
- no (2)
Keywords
Institute
In this thesis, we study multicommodity routing problems in networks, in which commodities have to be routed from source to destination nodes. Such problems model for instance the traffic flows in street networks, data flows in the Internet, or production flows in factories. In most of these applications, the quality of a flow depends on load dependent cost functions on the edges of the given network. The total cost of a flow is usually defined as the sum of the arc cost of the network. An optimal flow minimizes this cost. A main focus of this thesis is to investigate online multicommodity routing problems in networks, in which commodities have to be routed sequentially. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes (fractionally) each commodity by minimizing a convex cost function that depends on the previously routed flow. We present a competitive analysis of this algorithm and prove upper bounds of (d+1)^(d+1) for polynomial price functions with nonnegative coefficients and maximum degree d. For networks with two nodes and parallel arcs, we show that this algorithm returns an optimal solution. Without restrictions on the price functions and network, no algorithm is competitive. We also investigate a variant in which the demands have to be routed unsplittably. In this case, it is NP-hard to compute the offline optimum. Furthermore, we study selfish routing problems (network games). In a network game, players route demand in a network with minimum cost. In this setting, we study the quality of Nash equilibria compared to the the system optimum (price of anarchy) in network games with nonatomic and atomic players and spittable flow. As a main result, we prove upper bounds on the price of anarchy for polynomial latency functions with nonnegative coefficients and maximum degree d, which improve upon the previous best ones.
In this paper, we study the efficiency of Nash equilibria for a sequence of nonatomic routing games. We assume that the games are played consecutively in time in an online fashion: by the time of playing game $i$, future games $i+1,\dots,n$ are not known, and, once players of game $i$ are in equilibrium, their corresponding strategies and costs remain fixed. Given a sequence of games, the cost for the sequence of Nash equilibria is defined as the sum of the cost of each game. We analyze the efficiency of a sequence of Nash equilibria in terms of competitive analysis arising in the online optimization field. Our main result states that the online algorithm $\sl {SeqNash}$ consisting of the sequence of Nash equilibria is $\frac{4n}{2+n}$-competitive for affine linear latency functions. For $n=1$, this result contains the bound on the price of anarchy of $\frac{4}{3}$ for affine linear latency functions of Roughgarden and Tardos [2002] as a special case. Furthermore, we analyze a problem variant with a modified cost function that reflects the total congestion cost, when all games have been played. In this case, we prove an upper bound of $\frac{4n}{2+n}$ on the competitive ratio of $\sl {SeqNash}$. We further prove a lower bound of $\frac{3n-2}{n}$ of $\sl {SeqNash}$ showing that for $n=2$ our upper bound is tight.