AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

One of the most effective means to reduce the price of anarchy in non-atomic network routing games is to impose tolls on the arcs of the network. It is a well-known fact that marginal cost tolls induce a Nash flow that corresponds to a minimum cost flow. However, despite their effectiveness, marginal cost tolls suffer from two major drawbacks, namely (i) that potentially every arc is tolled and (ii) that the imposed tolls might be arbitrarily large. In this paper, we consider the problem of computing (approximately) optimal tolls that are restricted to not exceed a predefined budget for every arc, or path. The main contribution of the paper is to prove an equivalence between the set of epsilon-Nash flows and the set of Nash flows that are inducible by tolls that do not increase the latency of any path by more than an epsilon-fraction. A consequence of our results is that the efficiency of the best Nash flow that is inducible via such tolls corresponds to the price of stability of epsilon-Nash flows.

Vincenzo Bonifaci

--email hidden

passcode not visible

logged in users only

algorithmic game theory, selfish routing, tolls