Yosi Richter Talk

Title: Tradeoffs in worst-case equilibria
 
Absract:
We investigate the problem of routing traffic through a congested
network in an environment of non-cooperative users. We use the
worst-case coordination ratio suggested by Koutsoupias and
Papadimitriou to measure the performance degradation due to the
lack of a centralized traffic regulating authority. I intend to begin 
with a survey of the known results and then provide a
full characterization of the worst-case coordination ratio in the
restricted assignment and unrelated parallel links model. In
particular, we quantify the tradeoff between the ``negligibility''
of the traffic controlled by each user and the worst-case
coordination ratio. We analyze both pure and mixed strategies
systems and identify the range where their performance is similar.
 
Joint work with Baruch Awerbuch, Yossi Azar and Dekel Tsur