Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 2015 | public
Journal Article

On the Uniqueness of Equilibrium in Atomic Splittable Routing Games

Abstract

In routing games with infinitesimal players, it follows from well-known convexity arguments that equilibria exist and are unique. In routing games with atomic players with splittable flow, equilibria exist, but uniqueness of equilibria has been demonstrated only in limited cases: in two-terminal nearly parallel graphs, when all players control the same amount of flow, and when latency functions are polynomials of degree at most three. There are no known examples of multiple equilibria in these games. In this work, we show that in contrast to routing games with infinitesimal players, atomic splittable routing games admit multiple equilibria. We demonstrate this multiplicity via two specific examples. In addition, we show that our examples are topologically minimal by giving a complete characterization of the class of network topologies for which multiple equilibria exist. Our proofs and examples are based on a novel characterization of these topologies in terms of sets of circulations.

Additional Information

© 2015 INFORMS. Received September 9, 2012; revised September 16, 2013, and July 9, 2014. Published online in Articles in Advance November 5, 2014. The authors thank Shahar Dobzinski and Zoya Svitkina for helpful conversations. The authors also thank the referees of this paper for their valuable feedback. This paper was supported in part by National Science Foundation [Grants CCF-0515127, CCF-0728869, and CCF-1016778]. A preliminary version of this paper appeared in the Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009. Most of this work was done while the first, third, and fourth authors were students at Dartmouth College.

Additional details

Created:
August 22, 2023
Modified:
October 24, 2023