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. https://resolver.caltech.edu/CaltechAUTHORS:20180622-082816994
Full text is not posted in this repository. Consult Related URLs below.
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: |
| ||||||||||||||||||||||||||||||||||||||||||||
ORCID: |
| ||||||||||||||||||||||||||||||||||||||||||||
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: |
| ||||||||||||||||||||||||||||||||||||||||||||
Subject Keywords: | Routing games; Network flows; Tolls; Stackelberg routing; Query complexity; Ellipsoid algorithm | ||||||||||||||||||||||||||||||||||||||||||||
Classification Code: | JEL: C72 | ||||||||||||||||||||||||||||||||||||||||||||
DOI: | 10.1016/j.geb.2018.02.009 | ||||||||||||||||||||||||||||||||||||||||||||
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, Volume 118, 2019, Pages 533-569, 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: | 15 Nov 2021 20:47 |
Repository Staff Only: item control page