Campus Event Calendar

Event Entry

What and Who

Equilibria of Collusive Flow Games are not Unique

Chien-Chung Huang
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS  
AG Audience

Date, Time and Location

Wednesday, 22 October 2008
30 Minutes
E1 4


In routing games with infinitesimal (nonatomic) players, it follows

from well-known convexity arguments that equilibria exist and are unique (up
to induced delays, and under weak assumptions on delay functions). In
routing games
with atomic players --- players that
control large amounts of flow --- uniqueness has been demonstrated
only in limited cases: in 2-terminal, nearly-parallel graphs;
when all players control exactly the same amount of flow;
when latency functions are polynomials of degree at most three.

In this work, we answer the open question posed by Cominetti, Correa,
and Stier-Moses (ICALP 2006) and show that there may be multiple
equilibria in atomic player routing games.
We demonstrate the multiplicity via two specific examples.
In addition, we show our examples are topologically minimal
by giving a complete characterization of the class of
network topologies for which unique equilibria exist. Our
proofs and examples are based on a novel characterization of
these topologies in terms of sets of circulations.


This is joint work with Umang Bhaskar, Lisa Fleischer and Darrel Hoy


Khaled Elbassioni
--email hidden
passcode not visible
logged in users only

Khaled Elbassioni, 10/14/2008 01:25 PM -- Created document.