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 (2014) Achieving Target Equilibria in Network Routing Games without Knowing the Latency Functions. In: IEEE 55th Annual Symposium on Foundations of Computer Science. IEEE , Piscataway, NJ, pp. 31-40. ISBN 978-1-4799-6517-5. https://resolver.caltech.edu/CaltechAUTHORS:20160105-073143688

[img] PDF - Submitted Version
See Usage Policy.

371Kb

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

Abstract

The analysis of network routing games typically assumes, right at the onset, precise and 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 desirable target flow as the equilibrium by suitably influencing player behavior in the routing game. We ask whether one can achieve target flows as equilibria without knowing the underlying latency functions. Our main result gives a crisp positive answer to this question. We show that, under fairly general settings, 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 candidate tolls as input and returns the resulting equilibrium flow. This result is obtained via a novel application of the ellipsoid method, and applies to arbitrary multicommodity settings and non-linear latency functions. Our algorithm extends easily to many other settings, such as (i) when certain edges cannot be tolled or there is an upper bound on the total toll paid by a user, and (ii) general nonatomic congestion games. We obtain tighter bounds on the query complexity for series-parallel networks, and single-commodity routing games with linear latency functions, and complement these with a query-complexity lower bound applicable even to single-commodity routing games on parallel-link graphs with linear latency functions. We also explore the use of Stackelberg routing to achieve target equilibria and obtain strong positive results for series-parallel graphs. Our results build upon various new techniques that we develop pertaining to the computation of, and connections between, different notions of approximate equilibrium, properties of multicommodity flows and tolls in series-parallel graphs, and sensitivity of equilibrium flow with respect to tolls. Our results demonstrate that one can indeed circumvent the potentially-onerous task of modeling latency functions, and yet obtain meaningful results for the underlying routing game.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/FOCS.2014.12DOIArticle
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6978987PublisherArticle
http://arxiv.org/abs/1408.1429arXivDiscussion Paper
ORCID:
AuthorORCID
Ligett, Katrina0000-0003-2780-6656
Additional Information:© 2014 IEEE. We thank Éva Tardos for useful discussions. UB was supported by a Linde/SISL postdoctoral fellowship and NSF grants CNS-0846025, CCF-1101470 and EPAS-1307794. KL was supported by the Charles Lee Powell Foundation and a Microsoft Faculty Fellowship. LJS was supported by NSF grants 1038578 and 1319745, and was partly at the Simons Institute at UC Berkeley. CS was supported by NSERC grant 32760-06, an NSERC Discovery Accelerator Supplement Award, and an Ontario Early Researcher Award.
Funders:
Funding AgencyGrant Number
Linde/SISL postdoctoral fellowshipUNSPECIFIED
NSFCNS-0846025
NSFCCF-1101470
NSFEPAS-1307794
Charles Lee Powell FoundationUNSPECIFIED
Microsoft Research Faculty FellowshipUNSPECIFIED
NSF1038578
NSF1319745
UC Berkeley Simons InstituteUNSPECIFIED
Natural Sciences and Engineering Research Council of Canada (NSERC)32760-06
Ontario Early Researcher AwardUNSPECIFIED
Subject Keywords:Network routing; tolls; ellipsoid method; approximate equilibria; multicommodity flows; Stackelberg routing
Record Number:CaltechAUTHORS:20160105-073143688
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20160105-073143688
Official Citation:Bhaskar, U.; Ligett, K.; Schulman, L.J.; Swamy, C., "Achieving Target Equilibria in Network Routing Games without Knowing the Latency Functions," in Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on , vol., no., pp.31-40, 18-21 Oct. 2014 doi: 10.1109/FOCS.2014.12
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:63366
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:05 Jan 2016 16:53
Last Modified:03 Oct 2019 09:27

Repository Staff Only: item control page