Asymptotically Tight Bounds for Inefficiency in Risk-Averse Selfish Routing / 338
Thanasis Lianeas, Evdokia Nikolova, Nicolas E. Stier-Moses

We consider a nonatomic selfish routing model with independent stochastic travel times for each edge, represented by mean and variance latency functions that depend on arc flows. This model can apply to traffic in the Internet or in a road network. Variability negatively impacts packets or drivers, by introducing jitter in transmission delays which lowers quality of streaming audio or video, or by making it more difficult to predict the arrival time at destination. The price of risk aversion (PRA) has been defined as the worst-case ratio of the cost of an equilibrium with risk-averse players who seek risk-minimizing paths, and that of an equilibrium with risk-neutral users who minimize the mean travel time of a path [Nikolova and Stier-Moses, 2015]. This inefficiency metric captures the degradation of system performance caused by variability and risk aversion. In this paper, we provide the first lower bounds on the PRA. First, we show a family of structural lower bounds, which grow linearly with the size of the graph and players' risk-aversion. They are tight for graph sizes that are powers of two. We also provide asymptotically tight functional bounds that depend on the allowed latency functions but not on the topology. The functional bounds match the price-of-anarchy bounds for congestion games multiplied by an extra factor that accounts for risk aversion. Finally, we provide a closed-form formula of the PRA for a family of graphs that generalize series-parallel graphs and the Braess graph. This formula also applies to the mean-standard deviation user objective a much more complex model of risk-aversion due to the cost of a path being non-additive over edge costs.

PDF