CaltechAUTHORS
  A Caltech Library Service

On the Uniqueness of Equilibrium in Atomic Splittable Routing Games

Bhaskar, Umang and Fleischer, Lisa and Hoy, Darrell and Huang, Chien-Chung (2015) On the Uniqueness of Equilibrium in Atomic Splittable Routing Games. Mathematics of Operations Research, 40 (3). pp. 634-654. ISSN 0364-765X. https://resolver.caltech.edu/CaltechAUTHORS:20151001-111103219

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20151001-111103219

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1287/moor.2014.0688DOIArticle
http://pubsonline.informs.org/doi/10.1287/moor.2014.0688PublisherArticle
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.
Funders:
Funding AgencyGrant Number
NSFCCF-0515127
NSFCCF-0728869
NSFCCF-1016778
Subject Keywords:routing game; atomic players; network flows; multiple equilibria
Issue or Number:3
Classification Code:MSC2000 subject classification: Primary: 90B10; secondary: 91A10
Record Number:CaltechAUTHORS:20151001-111103219
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20151001-111103219
Official Citation:On the Uniqueness of Equilibrium in Atomic Splittable Routing Games Umang Bhaskar, Lisa Fleischer, Darrell Hoy, and Chien-Chung Huang Mathematics of Operations Research 201540:3 , 634-654
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:60690
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:01 Oct 2015 18:29
Last Modified:03 Oct 2019 08:59

Repository Staff Only: item control page