A Caltech Library Service

Achieving target equilibria in network routing games without knowing the latency functions

Bhaskar, Umang and Ligett, Katrina and Schulman, Leonard J. and Swamy, Chaitanya (2019) Achieving target equilibria in network routing games without knowing the latency functions. Games and Economic Behavior, 118 . pp. 533-569. ISSN 0899-8256. doi:10.1016/j.geb.2018.02.009.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


The analysis of network routing games typically assumes precise, detailed information about the latency functions. Such information may, however, be unavailable or difficult to obtain. Moreover, one is often primarily interested in enforcing a desired target flow as an equilibrium. We ask whether one can achieve target flows as equilibria without knowing the underlying latency functions. We give a crisp positive answer to this question. We show that one can efficiently compute edge tolls that induce a given target multicommodity flow in a nonatomic routing game using a polynomial number of queries to an oracle that takes tolls as input and outputs the resulting equilibrium flow. This result is obtained via a novel application of the ellipsoid method, and extends to various other settings. We obtain improved query-complexity bounds for series-parallel networks, and single-commodity routing games with linear latency functions. Our techniques provide new insights into network routing games.

Item Type:Article
Related URLs:
URLURL TypeDescription Related ItemProc. 55th FOCS Paper
Ligett, Katrina0000-0003-2780-6656
Schulman, Leonard J.0000-0001-9901-2797
Additional Information:© 2018 Elsevier Inc. Received 4 November 2016, Available online 19 March 2018. An extended abstract of this work appeared in Proc. 55th FOCS (Bhaskar et al., 2014b). Work performed in part while at the Department of Computing and Mathematical Sciences, California Institute of Technology, and at the Department of Combinatorics and Optimization, University of Waterloo. Work supported in part by a Linde/SISL postdoctoral fellowship, NSF grants CNS-0846025, CCF-1101470 and EPAS-1307794, and a Ramanujan Fellowship. Work supported in part by NSF grants 1254169 and 1518941, United States-Israel Binational Science Foundation Grant 2012348, the Charles Lee Powell Foundation, a grant from the HUJI Cyber Security Research Center in conjunction with the Israel National Cyber Directorate (INCD) in the Prime Minister's Office, a startup grant from Hebrew University's School of Computer Science, and a Microsoft Faculty Fellowship. This material is based upon work supported by the United States Air Force and DARPA under Contract No. FA8750-16-C-0022. Work supported in part by NSF grants 1038578, 1319745 and 1618795. Work performed in part at the Simons Institute for the Theory of Computing at UC Berkeley. Supported in part by NSERC grant 32760-06, an NSERC Discovery Accelerator Supplement Award, and an Ontario Early Researcher Award. We thank Éva Tardos and Jim Geelen for useful discussions.
Funding AgencyGrant Number
Linde Institute of Economic and Management ScienceUNSPECIFIED
Ramanujan FellowshipUNSPECIFIED
Binational Science Foundation (USA-Israel)2012348
Charles Lee Powell FoundationUNSPECIFIED
HUJI Cyber Security Research CenterUNSPECIFIED
Israel National Cyber Directorate (INCD)UNSPECIFIED
Hebrew UniversityUNSPECIFIED
Microsoft Faculty FellowshipUNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA8750-16-C-0022
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Natural Sciences and Engineering Research Council of Canada (NSERC)32760-06
Ontario Early Researcher AwardUNSPECIFIED
Caltech Social and Information Sciences LaboratoryUNSPECIFIED
Subject Keywords:Routing games; Network flows; Tolls; Stackelberg routing; Query complexity; Ellipsoid algorithm
Classification Code:JEL: C72
Record Number:CaltechAUTHORS:20180622-082816994
Persistent URL:
Official Citation:Umang Bhaskar, Katrina Ligett, Leonard J. Schulman, Chaitanya Swamy, Achieving target equilibria in network routing games without knowing the latency functions, Games and Economic Behavior, Volume 118, 2019, Pages 533-569, ISSN 0899-8256, (
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:87309
Deposited By: Tony Diaz
Deposited On:22 Jun 2018 23:22
Last Modified:15 Nov 2021 20:47

Repository Staff Only: item control page