Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Theoretical Computer...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Theoretical Computer Science
Article
License: Elsevier Non-Commercial
Data sources: UnpayWall
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
http://www2.cs.ucy.ac.cy/~mavr...
Part of book or chapter of book
Data sources: UnpayWall
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Theoretical Computer Science
Article . 2008
License: Elsevier Non-Commercial
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Theoretical Computer Science
Article . 2008 . Peer-reviewed
License: Elsevier Non-Commercial
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 2008
Data sources: zbMATH Open
https://doi.org/10.1007/978-3-...
Part of book or chapter of book . 2004 . Peer-reviewed
Data sources: Crossref
DBLP
Article . 2008
Data sources: DBLP
DBLP
Conference object
Data sources: DBLP
versions View all 9 versions
addClaim

A new model for selfish routing

Authors: Lücking, T.; Mavronicolas, Marios; Monien, Burkhard; Rode, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard; +1 Authors

A new model for selfish routing

Abstract

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.

Country
Cyprus
Related Organizations
Keywords

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

  • BIP!
    Impact byBIP!
    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%
Powered by OpenAIRE graph
Found an issue? Give us feedback
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).
BIP!Citations provided by BIP!
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.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
63
Top 10%
Top 10%
Top 10%
hybrid