Online Constraint Satisfaction via Tolls in MDP Congestion Games.

We consider the toll design problem that arise for a game designer of a congested stochastic network when the decision makers are myopically updating their strategies based on current system state. If both the designer and the decision makers are adaptively searching for an optimal strategy, it is not clear how and if both parties can attain their optimal strategies. We formulate the toll synthesis problem of inducing an equilibrium distribution that satisfies a given set of design specifications as a bilevel optimization problem, in which the lower level consists of decision makers playing a Markov decision process (MDP) congestion game. In addition to showing the existence of an optimal tolling threshold, we formulate learning algorithms that can be employed by both the game designer and the players to jointly determine the optimal toll and induced equilibrium, respectively, and analyze its convergence properties.