Equilibria of Atomic Flow Games are not Unique

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