hide
Free keywords:
-
Abstract:
In STOC 2006, Hayrapetyan, Tardos and Wexler introduced the problem
of studying collusion in network routing games. In this
work, we show that collusion adds significant
complexity to the structure of equilibria in nonatomic routing games,
answering an open question posed by
Cominetti, Correa, and Stier-Moses (ICALP 2006):
Without collusion, it follows from well-known convexity arguments
that equilibria exist and are unique (up to induced delays, and under
weak assumptions on delay functions). The question
is, does this uniqueness continue to hold in the presence of collusion?
We answer no: we show that if collusion is allowed in nonatomic routing games,
there may be multiple equilibria.
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.
