Bhaskar, Umang ;
Lolakapuri, Phani Raj
Equilibrium Computation in Atomic Splittable Routing Games
Abstract
We present polynomialtime 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 trafficdependent 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 polynomialtime 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 NPhard 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:158:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9521},
URN = {urn:nbn:de:0030drops95211},
doi = {10.4230/LIPIcs.ESA.2018.58},
annote = {Keywords: Routing Games, Equilibrium Computation, Convex costs, Splittable flows}
}
2018
Keywords: 

Routing Games, Equilibrium Computation, Convex costs, Splittable flows 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018)

Issue date: 

2018 
Date of publication: 

2018 