1 Search Results for "Lolakapuri, Phani Raj"

Document
DOI: 10.4230/LIPIcs.ESA.2018.58
Equilibrium Computation in Atomic Splittable Routing Games

Authors: Umang Bhaskar and Phani Raj Lolakapuri

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

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.
Cite as

Umang Bhaskar and Phani Raj Lolakapuri. Equilibrium Computation in Atomic Splittable Routing Games. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bhaskar_et_al:LIPIcs.ESA.2018.58,
  author =	{Bhaskar, Umang and Lolakapuri, Phani Raj},
  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 =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.58},
  URN =		{urn:nbn:de:0030-drops-95211},
  doi =		{10.4230/LIPIcs.ESA.2018.58},
  annote =	{Keywords: Routing Games, Equilibrium Computation, Convex costs, Splittable flows}
}
  • Refine by Author
  • 1 Bhaskar, Umang
  • 1 Lolakapuri, Phani Raj

  • Refine by Classification
  • 1 Theory of computation → Network games

  • Refine by Keyword
  • 1 Convex costs
  • 1 Equilibrium Computation
  • 1 Routing Games
  • 1 Splittable flows

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact