Data-driven regret minimization in routing games under uncertainty

This paper studies network routing under uncertain costs. We introduce the notion of regret and present methods to minimize it using data. Given a flow vector and a realization of the uncertainty, the regret experienced by a user on a particular path is the difference between the cost incurred on the path and the minimum cost across all paths connecting the same origin and destination. The network-wide regret is the cumulative regret experienced by all agents. We show that, for a fixed uncertainty, the total regret of all agents is a convex function provided the cost function of each path is affine and monotone. We provide two data-driven methods that minimize the expected value and a specified quantile of the total regret, respectively. Simulations compare our solutions to existing approaches of handling uncertainty in routing games.