On the Uniqueness of Equilibrium in Atomic Splittable Routing Games

• 成果类型: Article
• 署名作者: Bhaskar, Umang; Fleischer, Lisa; Hoy, Darrell; Huang, Chien-Chung
• 署名单位: California Institute of Technology; Dartmouth College; Northwestern University; Chalmers University of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2014.0688
• 发表日期: 2015
• 页码: 634-654
• 关键词: NETWORKS; algorithms

摘要

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.