CaltechAUTHORS
  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 (2018) Achieving target equilibria in network routing games without knowing the latency functions. Games and Economic Behavior . ISSN 0899-8256. (In Press) https://resolver.caltech.edu/CaltechAUTHORS:20180622-082816994

[img] PDF - Submitted Version
See Usage Policy.

371Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20180622-082816994

Abstract

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
https://doi.org/10.1016/j.geb.2018.02.009DOIArticle
http://resolver.caltech.edu/CaltechAUTHORS:20160105-073143688 Related ItemProc. 55th FOCS
https://arxiv.org/abs/1408.1429arXivDiscussion Paper
ORCID:
AuthorORCID
Ligett, Katrina0000-0003-2780-6656
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.
Funders:
Funding AgencyGrant Number
Linde/SISL Postdoctoral FellowshipUNSPECIFIED
NSFCNS-0846025
NSFCCF-1101470
NSFEPAS-1307794
Ramanujan FellowshipUNSPECIFIED
NSF1254169
NSF1518941
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
NSF1038578
NSF1319745
NSF1618795
Natural Sciences and Engineering Research Council of Canada (NSERC)32760-06
Ontario Early Researcher AwardUNSPECIFIED
Subject Keywords:Routing games; Network flows; Tolls; Stackelberg routing; Query complexity; Ellipsoid algorithm
Classification Code:JEL: C72
Record Number:CaltechAUTHORS:20180622-082816994
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20180622-082816994
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, 2018, ISSN 0899-8256, https://doi.org/10.1016/j.geb.2018.02.009. (http://www.sciencedirect.com/science/article/pii/S0899825618300320)
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:87309
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:22 Jun 2018 23:22
Last Modified:03 Oct 2019 19:54

Repository Staff Only: item control page