A new model for selfish routing

DOI10.1016/J.TCS.2008.06.045MaRDI QIDQ952441zbMATH OpenOpenAlexFDO

Authors Thomas Lücking, Marios Mavronicolas, Burkhard Monien, Manuel Rode

Publication date 12 November 2008

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2008.06.045

congestion games coordination ratio quadratic social cost worst-case Nash equilibrium

Communication networks in operations research (90B18) Traffic problems in operations research (90B20) Applications of game theory (91A80)

Review text

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.

Recommendations

Cites work

Cited in

(32)

This page was built for publication: A new model for selfish routing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q952441)