Online Constraint Satisfaction for MDP Congestion Games

Under the Markov decision process (MDP) congestion game framework, we study the problem of enforcing global constraints using tolls on a population of players with stochastic dynamics and coupled congestion costs. Existing work demonstrates that by enforcing identical tolls on every player, the optimal joint strategy for the playing population can be shifted to satisfy global design constraints. However, computing the minimum tolling value for constraint satisfaction requires explicit modelling of the congestion cost as a function of the playing population. In this paper, we assume that both the playing population and the constraint-enforcing authority, the game designer, lack such a model. Instead, the game designer can enforce tolls on a gaming instance that responds by approximating the optimal joint strategy under any toll. Under these assumptions, we develop a myopic algorithm that enables the game designer to compute the minimum tolling value, and prove that, up to the approximation error made by the gaming instance, our algorithm not only converges to the correct toll, but will guarantee average constraint satisfaction during the iterative process. Finally, we demonstrate how our model and algorithm can be applied to the profit-seeking ride-share driver population of Manhattan, New York City to optimally reduce traffic congestion using tolls.