On the role of signaling in mitigation of road-traffic congestion: The price of anarchy of signaling-based strategies in stochastic networks
We study the influence of information design on routing in the presence of vagaries, following the canonical congestion game approach. We allow a central controller to observe nature's state and make exploit the information gap between her and the drivers, to cater information to drivers in a most social manner. In addition to the extreme cases of full and no information, she can also use randomized public signaling and personal recommendations. We revisit these programs and raise algorithmic concerns, but most importantly, we revisit Roughgarden's celebrated Price of Anarchy (PoA) in uncertain networks. Unexpectedly, no upper bound on the PoA holds if drivers are kept uninformed in the presence of vagaries, while fully informed drivers perform regularly. On the other hand, uninformed drivers might outperform informed drivers by a factor equal to the price of anarchy. Comparing pairwise all information provisions, we establish a table of competitive ratios, which turn out to only take vales one, the PoA, and infinity.
Road-traffic, congestion, signaling games, signal, information design, game theory, price of anarchy, Wardrop equilibrium, Bayesian game
University of Illinois - Urbana-Champaign
Networked Digital Library of Theses and Dissertations
University of Illinois at Urbana-Champaign