Files in this item



application/pdfMASSICOT-THESIS-2019.pdf (624kB)
(no description provided)PDF


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
Advisor(s):Langbort, Cedric
Department / Program:Aerospace Engineering
Discipline:Aerospace Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
signaling games
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.
Issue Date:2019-07-22
Rights Information:© 2019 by Olivier Massicot. All rights reserved.
Date Available in IDEALS:2020-03-02
Date Deposited:2019-12

This item appears in the following Collection(s)

Item Statistics