Selfish Routing with Incomplete Information
Martin Gairing, Burkhard Monien, Karsten Tiemann
Faculty of CS, EE and Math,
University of Paderborn
In his seminal work
Harsanyi [Har67] introduced an elegant approach to study
non-cooperative games with incomplete information
where the players are uncertain about some parameters.
To model such games he introduced the Harsanyi transformation,
which converts a game with incomplete information to a strategic
game where players may have different types.
In the resulting
Bayesian game players' uncertainty about each others types
is described by a probability distribution
over all possible type profiles.
In this work, we introduce a particular selfish routing game
with incomplete information that we call
Bayesian routing game. Here, n selfish
users wish to assign their traffic to one of
m links. Users do not know each others traffic.
Following Harsanyi's approach, we introduce for each user
a set of possible types.
This paper presents a
comprehensive collection of results
for the Bayesian routing game.
- We prove, with help of a potential function, that every Bayesian
routing game possesses a pure Bayesian Nash equilibrium.
For the model of identical links and independent type distribution
we give a polynomial time algorithm to compute a pure Bayesian Nash
equilibrium.
- We study structural properties of fully mixed Bayesian Nash equilibria
for the model of identical links
and show that they maximize individual cost.
In general there exists more than one fully mixed Bayesian Nash
equilibrium. We characterize the class of fully mixed Bayesian
Nash equilibria in the case of independent type distribution.
- We conclude with results on coordination ratio for the model of
identical links for three social cost
measures, that is, social cost as maximum expected congestion,
sum of individual costs and maximum individual cost. For the latter two
we are able to give (asymptotic) tight bounds using our results
on fully mixed Bayesian Nash equilibria.
To the best of our knowledge this is the first time that
mixed Bayesian Nash equilibria have been studied in conjunction
with social cost.