Full Record

New Search | Similar Records

Title On the role of signaling in mitigation of road-traffic congestion: The price of anarchy of signaling-based strategies in stochastic networks
Publication Date
Date Accessioned
Degree MS
Discipline/Department Aerospace Engineering
Degree Level thesis
University/Publisher University of Illinois – Urbana-Champaign
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.
Subjects/Keywords Road-traffic; congestion; signaling games; signal; information design; game theory; price of anarchy; Wardrop equilibrium; Bayesian game
Contributors Langbort, Cedric (advisor)
Language en
Rights © 2019 by Olivier Massicot. All rights reserved.
Country of Publication us
Record ID handle:2142/106130
Repository uiuc
Date Retrieved
Date Indexed 2020-04-23
Grantor University of Illinois at Urbana-Champaign
Issued Date 2019-07-22 00:00:00

Sample Search Hits | Sample Images

…Chapter 2 Selfish routing 2.1 Routing as a congestion game In this first section, the reader will find how a road network is canonically modeled as a congestion game and the general properties of its equilibria. The first subsection is dedicated…

…to the very definition of selfish routing and introduces a potential which captures equilibria as its minima, in the same vein as the work on potential games of Monderer and Shapley [30]. The model we will use throughout has become a key…

…a congestion game, so we should expect it to be a potential game. It is indeed the case, we owe this discovery to Beckman, McGuire and Winsten [4]. The proof presented in appendix, see section A.1, shows first that the potential, Φ is…

…continuous population of drivers. We refer the reader to a recent and general work, [39], available in the game theory literature on best-response dynamics of potential games, although we only focus on a very particular problem here. If a flow f is…

…The second aspect is Braess’s paradox which in essence states that closing sections might improve traffic. 10 2.2.1 Price of anarchy If the early work of Beckmann et al. pioneered the study of selfish routing as a congestion game, Roughgarden’s…

…that day, but surprisingly, the network saw a decrease in congestion. However, the section was only closed for a day, which might not have let enough time to reach a Wardrop equilibrium, and there might have been less demand due to anticipatedly…

…measures to reduce congestion by acting on the network itself. This setting assumes a fixed demand and state of the roads, but in a more practical scenario, roads are prone e1 1 1 λω 1 2 1 2 f2 e2 (a) A simple two-route network (b)…

…As earlier, Ω encompasses all possible states of the road network, for example Ω = [0, 1] could accurately describe the congestion level of one road. In this example, which we take back from [28, 26], we set Ω = {0, 1} as…