Data-driven regret minimization in routing games under uncertainty

Jonathan DIetrich, Ashish R. Hota, Ashish Cherukuri

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
60 Downloads (Pure)


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.

Original languageEnglish
Title of host publication2019 18th European Control Conference, ECC 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9783907144008
Publication statusPublished - 1-Jun-2019
Event18th European Control Conference, ECC 2019 - Naples, Italy
Duration: 25-Jun-201928-Jun-2019

Publication series

Name2019 18th European Control Conference, ECC 2019


Conference18th European Control Conference, ECC 2019

Cite this