Stackelberg Strategies and Cost-Balancing Tolls for Atomic Congestion Games

Stackelberg Strategies and Cost-Balancing Tolls for Atomic Congestion Games

Abstract

In this talk, we discuss two natural approaches to reducing the inefficiency of (pure Nash) equilibria when self-interested atomic players route unsplittable traffic through a congested network. The first approach is to let a fraction of the players be coordinated by a Stackelberg strategy, which selects their paths so as to minimize the inefficiency of the worst equilibrium reached by the selfish players. We investigate the efficiency of three natural Stackelberg strategies for two orthogonal classes of congestion games, namely games with affine latency functions and parallel-link games. The second approach is to introduce edge tolls that influence the players' selfish choices and hopefully induce an optimal configuration. We focus on a natural toll mechanism called cost-balancing tolls. For symmetric network congestion games, we show how to compute in linear time a moderate set of cost-balancing tolls that induce the optimal configuration as an equilibrium of the modified game. For series-parallel networks with increasing latency functions, we prove that the optimal configuration is induced as the unique equilibrium of the game with the corresponding cost-balancing tolls.