A Simple, Fast, and Safe Mediator for Congestion Management

2020-06-02

Proceedings of the AAAI Conference on Artificial Intelligence, 34

Volume

Vol. 34 No. 02: AAAI-20 Technical Tracks 2

AAAI Technical Track: Game Theory and Economic Paradigms

Congestion is a severe problem in cities. A large population with little information about each other's preferences hardly reaches equilibrium and causes unexpected congestion. Controlling such congestion requires us to collect information dispersed in the market and to coordinate actions among agents. We aim to design a mediator that a) induces a game with high social welfare in equilibrium, b) computes an equilibrium efficiently, c) works without common prior, and d) performs well even when only some of the agents in the market use the mediator. We propose a mediator based on a version of best response dynamics (BRD). We prove that, in a simple setting with two resources, “good behavior” (reporting truthfully and following the recommendation) forms an (approximate) ex-post Nash equilibrium in the mediated game; in the equilibrium, the welfare is close to the first-best when preferences diverge enough. Furthermore, under a certain behavioral assumption, those who are not using the mediator can always enjoy non-negative payoff gain by joining it even without the full participation of others. Additionally, our experimental results suggest that such results remain valid for more general settings.

10.1609/aaai.v34i02.5575