On the role of signaling in mitigation of road-traffic congestion: The price of anarchy of signaling-based strategies in stochastic networks
Massicot, Olivier
Loading…
Permalink
https://hdl.handle.net/2142/106130
Description
Title
On the role of signaling in mitigation of road-traffic congestion: The price of anarchy of signaling-based strategies in stochastic networks
Author(s)
Massicot, Olivier
Issue Date
2019-07-22
Director of Research (if dissertation) or Advisor (if thesis)
Langbort, Cedric
Department of Study
Aerospace Engineering
Discipline
Aerospace Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Keyword(s)
Road-traffic
congestion
signaling games
signal
information design
game theory
price of anarchy
Wardrop equilibrium
Bayesian game
Abstract
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
