Seminar Friday March 24
Great Tolls: How to induce optimal flows under strategic link owners
Cristóbal Guzmán (PUC-Chile and CWI-Amsterdam)
Network pricing games provide a framework for modeling real-world settings with two types of strategic
agents: users of the network and owners of the network. Owners of the network post a price for usage of
the link they own; users of the network select routes based on price and level of use by other users. The
challenge in these games is that there are two levels of competition: one, among the owners to attract
users to their link so as to maximize profit; and second, among users of the network to select routes that
are cheap yet not too congested. Interestingly, we observe that: (i) an equilibrium may not exist; (ii) it
might not be unique; and (iii) the network performance at equilibrium can be arbitrarily inefficient.
Our main result is to observe that a slight regulation on the network owners market solves all three issues
above. Specifically, if the authority could set appropriate caps (upper bounds) on the tolls (prices) operators
can charge then: the game among the link operators has a unique strong Nash equilibrium and the users’
game results in a Wardrop equilibrium that achieves the optimal total delay. We call any price vector with
these properties a great set of tolls. We then ask, can we compute great tolls that minimize total users’
payments? We show that this optimization problem reduces to a linear program in the case of single-commodity
series-parallel networks. Starting from the same linear program, we obtain multiplicative approximation results
for arbitrary networks with polynomial latencies of bounded degree, while in the single-commodity case we
obtain a surprising bound, which only depends on the topology of the network.
This is joint work with José Correa, Thanasis Lianeas, Evdokia Nikolova and Marc Schröder.