
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.
Non-cooperative networks, Technology, Computation theory, congestion games, #P-completeness, Wardrop, Quadratic programming, Computer systems, worst-case Nash equilibrium, Nash equilibrium, Parallel links, Applications of game theory, New model, Lecture Notes, coordination ratio, Game theory, Road traffic, Civil engineers, Telecommunication networks, Chlorine compounds, Traffic problems in operations research, Coordination ratio, Model assumptions, Hybrid model, Computer Science(all), Tight bounds, Polynomial approximation, Lower and upper bounds, Nash equilibria, Theoretical Computer Science, Computer programming languages, quadratic social cost, Social cost, Computing systems, Platinum, Polynomial-time, Computers, Weighted-sum, Computer science, Costs, Mixed strategy, Mixed strategies, Communication networks in operations research, Selfish routing, Positive probability, Noncooperative networks
Non-cooperative networks, Technology, Computation theory, congestion games, #P-completeness, Wardrop, Quadratic programming, Computer systems, worst-case Nash equilibrium, Nash equilibrium, Parallel links, Applications of game theory, New model, Lecture Notes, coordination ratio, Game theory, Road traffic, Civil engineers, Telecommunication networks, Chlorine compounds, Traffic problems in operations research, Coordination ratio, Model assumptions, Hybrid model, Computer Science(all), Tight bounds, Polynomial approximation, Lower and upper bounds, Nash equilibria, Theoretical Computer Science, Computer programming languages, quadratic social cost, Social cost, Computing systems, Platinum, Polynomial-time, Computers, Weighted-sum, Computer science, Costs, Mixed strategy, Mixed strategies, Communication networks in operations research, Selfish routing, Positive probability, Noncooperative networks
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 63 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
