Booth Id:
MA040
Category:
Robotics and Intelligent Machines
Year:
2014
Finalist Names:
Mirchandani, Rishi
Abstract:
This study examines the classic traffic-flow problem: how should networks be designed in order to minimize commuters’ travel time? Besides transportation, this question also has important implications for other network-based fields, including neurology, social networking, material science, and electrical engineering.
A central difficulty in traffic-flow planning is that, when commuters self-optimize, aggregate network travel time is usually not minimized. That is, there is a cost to allowing commuters to route themselves (instead of assigning system-optimal routes). This cost is particularly bothersome in the Downs-Thomson and Braess paradoxes, which demonstrate that expanding highway capacity or constructing a new road (respectively) can increase commuter travel time.
The purpose of this study is to use game-theoretical principles to model this cost, quantified by “price of anarchy” (PoA), as a function of the demand on the network. This analysis has led to three major theoretical results. The first result is that, under certain conditions, increased demand leads to decreased travel time for all commuters. Second, this investigation identifies some striking similarities, including unimodality, in the PoA functions for multifarious networks; these similarities suggest that the term “price of fairness” is a better descriptor for commuter behavior than “price of anarchy.” Third, this study proves that PoA is unbounded in networks that include a mass-transit link (e.g., a railway), yet a small change in demand is often sufficient to greatly mitigate the inefficiency. These results are significant because they highlight the importance of evaluating network performance at all possible demand levels before modifying the network.
Awards Won:
Third Award of $1,000