Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published 2014 | public
Book Section - Chapter

Network Improvement for Equilibrium Routing


In routing games, agents pick routes through a network to minimize their own delay. A primary concern for the network designer in routing games is the average agent delay at equilibrium. A number of methods to control this average delay have received substantial attention, including network tolls, Stackelberg routing, and edge removal. A related approach with arguably greater practical relevance is that of making investments in improvements to the edges of the network, so that, for a given investment budget, the average delay at equilibrium in the improved network is minimized. This problem has received considerable attention in the literature on transportation research. We study a model for this problem introduced in transportation research literature, and present both hardness results and algorithms that obtain tight performance guarantees. – In general graphs, we show that a simple algorithm obtains a 4/3-approximation for affine delay functions and an O(p/ log p)- approximation for polynomial delay functions of degree p. For affine delays, we show that it is NP-hard to improve upon the 4/3 approximation. – Motivated by the practical relevance of the problem, we consider restricted topologies to obtain better bounds. In series-parallel graphs, we show that the problem is still NP-hard. However, we show that there is an FPTAS in this case. – Finally, for graphs consisting of parallel paths, we show that an optimal allocation can be obtained in polynomial time.

Additional Information

© 2014 Springer International Publishing Switzerland. Supported in part by NSF Awards 1038578 and 1319745, an NSF CAREER Award (1254169), the Charles Lee Powell Foundation, and a Microsoft Research Faculty Fellowship.

Additional details

August 19, 2023
January 13, 2024