The price of anarchy for polynomial social cost

DOI10.1016/j.tcs.2006.07.055zbMath1142.91376OpenAlexW2037822626MaRDI QIDQ861255

Martin Gairing, Marios Mavronicolas, Thomas Lücking, Burkhard Monien

Publication date: 9 January 2007

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

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2005/200/

zbMATH Keywords

price of anarchyselfish routingpolynomial price of anarchy

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Combinatorics in computer science (68R05) Games involving graphs (91A43)

Related Items (10)

The structure and complexity of Nash equilibria for a selfish routing game ⋮ Atomic routing games on maximum congestion ⋮ Price of anarchy for parallel link networks with generalized mean objective ⋮ Tight bounds for selfish and greedy load balancing ⋮ Stability vs. optimality in selfish ring routing ⋮ Distributed backup placement in networks ⋮ A new model for selfish routing ⋮ Nash equilibria in discrete routing games with convex latency functions ⋮ Facets of the Fully Mixed Nash Equilibrium Conjecture ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Subjectivity and correlation in randomized strategies
• Approximate equilibria and ball fusion
• Exponential polynomials
• A class of games possessing pure-strategy Nash equilibria
• Structure and complexity of extreme Nash equilibria
• Non-cooperative games
• How bad is selfish routing?
• Selfish traffic allocation for server farms
• The price of anarchy of finite congestion games
• The price of selfish routing
• Algorithms, games, and the internet
• Competitive routing in networks with polynomial costs
• STACS 2004
• Mathematical Foundations of Computer Science 2003
• Exact Price of Anarchy for Polynomial Congestion Games
• Automata, Languages and Programming
• Algorithms – ESA 2005
• Equilibrium points in n -person games
• Theoretical Computer Science
• The Price of Routing Unsplittable Flow

This page was built for publication: The price of anarchy for polynomial social cost