The Burden of Risk Aversion in Selfish Routing
Traffic congestion aggravates the daily life of millions of people around the globe and congestion games from game theory provide a suitable tool to understand its effects and offer insights on how to alleviate it. Classic congestion games assume deterministic edge delays, while in reality delays are uncertain and risk-averse drivers might prefer longer but safer routes, further exacerbating the problem of increased travel times and emissions.
Considering congestion games with uncertain delays, WNCG faculty Evdokia Nikolova and collaborator Nicolas Stier-Moses compute the inefficiency introduced in network routing by risk-averse users. At equilibrium, users may select paths that do not minimize the expected delay so as to obtain lower variability. A social planner, who is likely to be more risk neutral than agents because it operates at a longer time-scale, quantifies social cost with the total expected delay along routes. From that perspective, users may make suboptimal decisions that degrade long-term quality.
Nikolova and Stier-Moses define the price of risk aversion as a way to quantify the price users pay in terms of extra travel time due to their risk-averse routing choices. Formally, it is the worst-case ratio of the social cost at a risk-averse equilibrium to that where users are risk-neutral. For networks with general delay functions and a single origin-destination pair for all users, they show that the price of risk-aversion depends linearly on the users' risk tolerance and on the degree of variability present in the network. They obtain this result via a combinatorial proof that employs alternating paths that are reminiscent of those used in max-flow algorithms. For series-parallel graphs, the price of risk-aversion becomes independent of the network topology and its size. As a result of independent interest, they also prove that for series-parallel networks with deterministic edge delays, the equilibrium maximizes the shortest-path objective among all feasible flows.
This work also paves the ground for examining ways in which risk-aversion can help reduce rather than worsen congestion, where risk-aversion may be leveraged to spread traffic in the place of tolls.
The Burden of Risk Aversion in Mean-Risk Selfish Routing
Evdokia Nikolova, Nicolas E. Stier Moses.
November, 2014.