Equilibria of atomic flow games are not unique

ABSTRACT

In routing games with infinitesimal players, it follows from well-known convexity arguments that equilibria exist and are unique (up to induced delays, and under weak assumptions on delay functions). In routing games with players that control large amounts of flow, uniqueness has been demonstrated only in limited cases: in 2-terminal, nearly-parallel graphs; when all players control exactly the same amount of flow; when latency functions are polynomials of degree at most three.

In this work, we answer an open question posed by Cominetti, Correa, and Stier-Moses (ICALP 2006) and show that there may be multiple equilibria in atomic player routing games. We demonstrate this 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.

REFERENCES

• 1: Eitan Altman, Tamer Basar, Tania Jimenez, and Nahum Shimkin. Competitive routing in networks with polynomial costs. IEEE Transactions on Automatic Control, 47(1):92--96, January 2002.
• 2: Stefano Catoni and Stefano Pallottino. Traffic equilibrium paradoxes. Transportation Science, 25(3):240--244, August 1991.
• 3: Roberto Cominetti, Jose R. Correa, and N. E. Stier-Moses. The impact of oligopolistic competition in networks. Operation Research, 2008. to appear, extended abstract entitled "Network games with atomic players" appeared in ICALP 06.
• 4: P. Harker. Multiple equilibrium behaviors on networks. Transportation Science, 22(1):39--46, 1988.
• 5: Ara Hayrapetyan , Éva Tardos , Tom Wexler, The effect of collusion in congestion games, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132529]
• 6: N. M. Korneyenko, Combinatorial algorithms on a class of graphs, Discrete Applied Mathematics, v.54 n.2-3, p.215-217, Oct. 17, 1994 [doi>10.1016/0166-218X(94)90022-1]
• 7: Igal Milchtaich, Topological Conditions for Uniqueness of Equilibrium in Networks, Mathematics of Operations Research, v.30 n.1, p.225-244, February 2005 [doi>10.1287/moor.1040.0122]
• 8: T. Nishizeki and N. Chiba. Planar Graphs: Theory and Algorithms. North-Holland, 1988.
• 9: J. Nocedal and S. T. Wright. Numerical Optimization. Springer, 2006.
• 10: Ariel Orda , Raphael Rom , Nahum Shimkin, Competitive routing in multiuser communication networks, IEEE/ACM Transactions on Networking (TON), v.1 n.5, p.510-521, Oct. 1993 [doi>10.1109/90.251910]
• 11: Oran Richman , Nahum Shimkin, Topological Uniqueness of the Nash Equilibrium for Selfish Routing with Atomic Users, Mathematics of Operations Research, v.32 n.1, p.215-232, February 2007 [doi>10.1287/moor.1060.0229]
• 12: Tim Roughgarden, Stackelberg Scheduling Strategies, SIAM Journal on Computing, v.33 n.2, p.332-350, 2004 [doi>10.1137/S0097539701397059]
• 13: Tim Roughgarden, Selfish routing with atomic players, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 14: Tim Roughgarden, Selfish Routing and the Price of Anarchy, The MIT Press, 2005
• 15: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 16: Chaitanya Swamy, The effectiveness of Stackelberg strategies and tolls for network congestion games, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1133-1142, January 07-09, 2007, New Orleans, Louisiana
• 17: H. R. von Stackelberg. Marktform und Gleichgewicht. Springer-Verlag, 1934. English translation entitled as Market Structure and Equilibrium, published in 1952 by Oxford University Press.
• 18: J. G. Wardrop. Some theoretical aspects of road traffic research. In Proc. Institute of Civil Engineers, Pt. II, volume 1, pages 325--378, 1952.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Games