2023/10/06 by Jasper Verbree, Verbree, Jasper, Ashish Cherukuri +1
Decision Sciences · Economics, Econometrics and Finance · #90B06 #90B20 #90C33 #91A14 #91A43 #Computer Science and Game Theory (cs.GT) #Economic theories and models #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2310.04256
openalex publication_date 2023/10/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This work explores the relationship between the set of Wardrop equilibria~(WE) of a routing game, the total demand of that game, and the occurrence of Braess's paradox~(BP). The BP formalizes the counter-intuitive fact that for some networks, removing a path from the network decreases congestion at WE. For a single origin-destination routing games with affine cost functions, the first part of this work provides tools for analyzing the evolution of the WE as the demand varies. It characterizes the piece-wise affine nature of this dependence by showing that the set of directions in which the WE can vary in each piece is the solution of a variational inequality problem. In the process we establish various properties of changes in the set of used and minimal-cost paths as demand varies. As a consequence of these characterizations, we derive a procedure to obtain the WE for all demands above a certain threshold. The second part of the paper deals with detecting the presence of BP in a network. We supply a number of sufficient conditions that reveal the presence of BP and that are computationally tractable. We also discuss a different perspective on BP, where we establish that a path causing BP at a particular demand must be strictly beneficial to the network at a lower demand. Several examples throughout this work illustrate and elaborate our findings.