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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Aerospace Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2020

Author dc:creator

• Massicot, Olivier

Contributors dc:contributor

• Langbort, Cedric

• Road-traffic
• congestion
• signaling games
• signal
• information design
• game theory
• price of anarchy
• Wardrop equilibrium
• Bayesian game

Statement dc:rights

• © 2019 by Olivier Massicot. All rights reserved.

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/106130

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/106130