A new model for selfish routing (Q952441)

The authors study a new model for selfish routing over non-cooperative networks, as an hybridization of the two prevailing such models, namely the KP model [\textit{E. Koutsoupias} and \textit{C. Papadimitriou}, ``Worst-case equilibria'', Lect. Notes Comput. Sci. 1563, 404--413 (1999; Zbl 1099.91501)] and the W model [Wardrop (1952)]. In this model, each of \(n\) users is using a mixed strategy to ship its unsplittable traffic over a network consisting of \(m\) parallel links. In a Nash equilibrium, no user can unilaterally improve its Expected Individual Cost. To evaluate Nash equilibria, they introduce Quadratic Social Cost as the sum of the expectations of the latencies, incurred by the squares of the accumulated traffic. The Quadratic Coordination Ratio is the worst case ratio of the Quadratic Social Cost of a Nash equilibrium divided by the Quadratic Optimum. The main results are: \(\bullet \) Quadratic Social Cost can be computed in polynomial time. \(\bullet \) For the case of identical users and identical links, the fully mixed Nash equilibrium maximizes Quadratic Social Cost. \(\bullet \) In several cases, lower and upper bounds on the Quadratic Coordination Ratio are given.