2010/10/14 by Umang Bhaskar, Bhaskar, Umang, Lisa Fleischer +3
Decision Sciences · Economics, Econometrics and Finance · Engineering · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems #ICT Impact and Policies
paper · pdf · doi:10.48550/arxiv.1010.3034
openalex publication_date 2010/10/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Routing games are used to to understand the impact of individual users' decisions on network efficiency. Most prior work on routing games uses a simplified model of network flow where all flow exists simultaneously, and users care about either their maximum delay or their total delay. Both of these measures are surrogates for measuring how long it takes to get all of a user's traffic through the network. We attempt a more direct study of how competition affects network efficiency by examining routing games in a flow over time model. We give an efficiently computable Stackelberg strategy for this model and show that the competitive equilibrium under this strategy is no worse than a small constant times the optimal, for two natural measures of optimality.