Optimal Mechanisms for Robust Coordination in Congestion Games

Abstract

Uninfluenced social systems often exhibit suboptimal performance; specially designed taxes can influence agent choices and thereby bring aggregate social behavior closer to optimal. A perfect system characterization may enable a planner to apply simple taxes to incentivize desirable behavior, but system uncertainties may necessitate highly sophisticated taxation methodologies. Using a model of network routing, we study the effect of system uncertainty on a designer's ability to influence behavior with financial incentives. We show that, in principle, it is possible to design taxes that guarantee that selfish network flows are arbitrarily close to optimal flows, despite the fact that agents' tax sensitivities and the network topology are unknown to the designer. In general, these taxes may be large; accordingly, for affine-cost parallel-network routing games, we explicitly derive the optimal bounded tolls and the best-possible performance guarantee as a function of a toll upper bound. Finally, we restrict attention to simple fixed tolls and show that they fail to provide strong performance guarantees if the designer lacks accurate information about the network topology or user sensitivities.