Dissertation
Selfish Routing with Incomplete Information
Karsten Tiemann
Schriftliche Arbeit zur Erlangung des Grades
Doktor der Naturwissenschaften
Universit¨at Paderborn,
Fakult¨at f¨ur Elektrotechnik, Informatik und Mathematik
Paderborn, 14. Juni 2007
ii
Abstract
To study selfish routing scenarios in networks we use and extend in this thesis
two well-known classes of games modeling such routing scenarios: network
congestion games and Wardrop games. In both games, we are given a network
with edge latency functions. In a network congestion game, each player selects
as its strategy one path from its origin to its destination node and experiences as
its private cost the sum of edge latencies on this path. In a Nash equilibrium,
no player can decrease its private cost by unilaterally deviating to another
path. In a Wardrop game, amounts of traffic are associated with pairs of
network nodes. The traffic from an origin to a destination node is modeled as
a splittable network flow and the cost on an origin-destination path is again
given by the sum of edge latencies on this path. In a Wardrop equilibrium, no
fraction of the traffic assigned to some path, however small, can decrease its
cost by unilaterally switching to another path.
This thesis is primarily concerned with network routing scenarios where the
players have incomplete information. One possibility to model such scenarios
is to assume that a player who does not know some relevant parameter of
the game is at least aware of a probability distribution over the possible out-
comes of this parameter. In such a setting, it is reasonable to assume that the
decisions of a player are based on the expected values of the unknown para-
meters. We apply this approach for network routing games where the players
have incomplete information about the edge latency functions. Since each
player obtains for each edge his own expected latency function we get games
with player-specific latency functions. For both network congestion games
and Wardrop games with player-specific latency functions, we show positive
and negative results concerning the convergence to equilibria, the existence
and polynomial-time computability of equilibria. We also prove bounds on
the so-called price of anarchy that measures the worst-possible inefficiency of
equilibria with respect to a social welfare measure.
iii
We use an incomplete information model different from the aforementioned
one for games where, in contrast to congestion games, the players do not
know each other’s weight. Based on Harsanyi’s incomplete information concept
of Bayesian games, each player in our Bayesian routing games has a set of
possible types and each type of a player corresponds to some weight. The
players’ uncertainty about each other’s weight is described by one probability
distribution over all possible type profiles that is known to all players. In this
setting, we focus on the price of anarchy, the existence and the computational
complexity of equilibria.
We also study in this thesis, as a complete information setting, bottleneck
games with splittable traffic where the latency on a path is given by the max-
imum latency of an edge on this path. We characterize for which games the
social welfare of equilibria is unique and we give results on the price of stability
that measures the worst-possible inefficiency of the best equilibrium.
iv
Acknowledgments
My acknowledgments go to all persons who supported my research during
the past three years. First and foremost, I would like to thank my advisor,
Burkhard Monien, whose scientific expertise and constant guidance gave me
an excellent support in the process of my scientific work. Moreover, I would
like to express my thanks to Yvonne Bleischwitz, Martin Gairing, and Flo-
rian Schoppmann for the great collaboration on game theory topics. I am
indebted to Martin Gairing, Florian Schoppmann, and Ulf-Peter Schroeder for
the careful reading of parts of this dissertation and for numerous suggestions
for improvements. I would also like to thank all members of the research group
Monien for the very good cooperation and the excellent working atmosphere.
Thanks go to Marios Mavronicolas and Igal Milchtaich for inspiring my
work with many good ideas and to Michael Dellnitz and Friedhelm Meyer
auf der Heide for being my Ph.D. co-advisors. Furthermore, I would like to
thank the International Graduate School of Dynamic Intelligent Systems at
the University of Paderborn for establishing a stimulating environment for
research and for providing financial support in the form of a scholarship.
Last but not least, I am very grateful to my family and friends whose con-
tinuous support greatly helped me to finish this thesis.
Paderborn, June 2007 Karsten Tiemann
v
Loading more pages...