Average Unfairness in Routing Games

We propose average unfairness as a new measure of fairness in routing games, defined as the ratio between the average latency and the minimum latency experienced by users. This measure is a natural complement to two existing unfairness notions: loaded unfairness, which compares maximum and minimum latencies of routes with positive flow, and user equilibrium (UE) unfairness, which compares maximum latency with the latency of a Nash equilibrium. We show that the worst-case values of all three unfairness measures coincide and are characterized by a steepness parameter intrinsic to the latency function class. We show that average unfairness is always no greater than loaded unfairness, and the two measures are equal only when the flow is fully fair. Besides that, we offer a complete comparison of the three unfairness measures, which, to the best of our knowledge, is the first theoretical analysis in this direction. Finally, we study the constrained system optimum (CSO) problem, where one seeks to minimize total latency subject to an upper bound on unfairness. We prove that, for the same tolerance level, the optimal flow under an average unfairness constraint achieves lower total latency than any flow satisfying a loaded unfairness constraint. We show that such improvement is always strict in parallel-link networks and establish sufficient conditions for general networks. We further illustrate the latter with numerical examples. Our results provide theoretical guarantees and valuable insights for evaluating fairness-efficiency tradeoffs in network routing.

Key highlights of our findings:

• We introduce average unfairness as an intuitive and interpretable measure of unfairness and derive its exact bound under general network topologies and latency function classes.
• We provide a comprehensive theoretical comparison between average unfairness and two commonly used measures in the literature (loaded and user equilibrium (UE) unfairness). To the best of our knowledge, this is the first theoretical comparison since the numerical study in previous work.
• We analyze the constrained system optimum (CSO) problem under all three unfairness measures. We establish the structure of its solutions in parallel-link networks, extending the result in previous work. Moreover, we show that the CSO solution under average unfairness can strictly outperform that under loaded unfairness, and establish conditions under which this improvement is guaranteed. We further validate these results through simulations.