License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.58
URN: urn:nbn:de:0030-drops-95211
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9521/
Go to the corresponding LIPIcs Volume Portal

Bhaskar, Umang ; Lolakapuri, Phani Raj

Equilibrium Computation in Atomic Splittable Routing Games

pdf-format:
LIPIcs-ESA-2018-58.pdf (0.5 MB)

Abstract

We present polynomial-time algorithms as well as hardness results for equilibrium computation in atomic splittable routing games, for the case of general convex cost functions. These games model traffic in freight transportation, market oligopolies, data networks, and various other applications. An atomic splittable routing game is played on a network where the edges have traffic-dependent cost functions, and player strategies correspond to flows in the network. A player can thus split its traffic arbitrarily among different paths. While many properties of equilibria in these games have been studied, efficient algorithms for equilibrium computation are known for only two cases: if cost functions are affine, or if players are symmetric. Neither of these conditions is met in most practical applications. We present two algorithms for routing games with general convex cost functions on parallel links. The first algorithm is exponential in the number of players, while the second is exponential in the number of edges; thus if either of these is small, we get a polynomial-time algorithm. These are the first algorithms for these games with convex cost functions. Lastly, we show that in general networks, given input C, it is NP-hard to decide if there exists an equilibrium where every player has cost at most C.

BibTeX - Entry

@InProceedings{bhaskar_et_al:LIPIcs:2018:9521,
  author =	{Umang Bhaskar and Phani Raj Lolakapuri},
  title =	{{Equilibrium Computation in Atomic Splittable Routing Games}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{58:1--58:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Yossi Azar and Hannah Bast and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9521},
  URN =		{urn:nbn:de:0030-drops-95211},
  doi =		{10.4230/LIPIcs.ESA.2018.58},
  annote =	{Keywords: Routing Games, Equilibrium Computation, Convex costs, Splittable flows}
}

Keywords: Routing Games, Equilibrium Computation, Convex costs, Splittable flows
Collection: 26th Annual European Symposium on Algorithms (ESA 2018)
Issue Date: 2018
Date of publication: 14.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI