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

• 成果类型: Article
• 署名作者: Bhaskar, Umang; Ligett, Katrina; Schulman, Leonard J.; Swamy, Chaitanya
• 署名单位: Tata Institute of Fundamental Research (TIFR); California Institute of Technology; Hebrew University of Jerusalem; University of Waterloo; University of California System; University of California Berkeley
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2018.02.009
• 发表日期: 2019
• 页码: 533-569
• 关键词: Routing games; network flows; tolls; Stackelberg routing; Query complexity; Ellipsoid algorithm

摘要

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. (C) 2018 Elsevier Inc. All rights reserved.