Linde Institute/Social and Information Sciences Laboratory (SISL) Seminar

The analysis of network routing games typically assumes precise, detailed information about the underlying latency functions. Such information may however be unavailable and difficult to obtain. Moreover, one is often primarily interested in enforcing a desirable target flow as the equilibrium by suitably influencing players' behavior, e.g., via tolls on the roads. Can one 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 polynomial number of queries to an oracle that takes candidate tolls as input and returns the resulting equilibrium flow. Our algorithm extends easily to a variety of other settings, including atomic splittable routing games and 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. We show that on a series-parallel graph with m edges, a Stackelberg routing inducing the given target flow as an equilibrium can be computed in polytime and with at most m queries. For a stronger problem that roughly corresponds to determining the delay functions, we obtain strong query- and computational-complexity lower bounds. 

This is joint work with Katrina Ligett, Leonard J. Schulman and Chaitanya Swamy.