Files in this item

FilesDescriptionFormat

application/pdf

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

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
Advisor(s):Langbort, Cedric
Department / Program:Aerospace Engineering
Discipline:Aerospace Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
Subject(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.
Issue Date:2019-07-22
Type:Text
URI:http://hdl.handle.net/2142/106130
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