Worst-case Equilibria
Explore this paper's citation graph
Summary
In a system where noncooperative agents share a common resource, the price of anarchy is proposed, which is the ratio between the worst possible Nash equilibrium and the social optimum, as a measure of the effectiveness of the system.
- Type
- article
- Published
- 1999-03-04
- Cited by
- 2,705
- References
- 20
- OpenAlex
- https://openalex.org/W2056606651
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:841868
Keywords
Price of anarchy, Nash equilibrium, Computer science, Simple (philosophy), Measure (data warehouse)
References
- Quality of Service Provision in Noncooperative Network Environments
- Architecting noncooperative networks
- Bounds for LPT Schedules on Uniform Processors
- Algorithmic Mechanism Design
- Quality of service provision in noncooperative networks: heterogenous preferences, multi-dimensional QoS vectors, and burstiness
- Pricing in computer networks: reshaping the research agenda
- On complexity as bounded rationality (extended abstract)
- How bad is selfish routing?
- Algorithms, games, and the internet
- Recommendations on Queue Management and Congestion Avoidance in the Internet
- Making greed work in networks: a game-theoretic analysis of switch service disciplines
- On the existence of equilibria in noncooperative optimal flow control
- Optimal routing control: game theoretic approach
- Algorithms
- Bounds for List Schedules on Uniform Processors
- Algorithms for selfish agents mechanism design for distributed computation
- Algorithmic mechanism design (extended abstract)
- Randomized algorithms
- AND D
Cited by
- The price of anarchy of serial cost sharing and other methods
- The impact of cooperation on new high performance computing platforms
- The price of anarchy in mobility-driven contagion dynamics
- Des modèles et des algorithmes pour la gestion des ressources dans les grilles de plusieurs organisations
- The Impact of Stackelberg Routing in General Networks
- The Ecology of Defensive Medicine and Malpractice Litigation
- Modeling and constructing unstructured overlay networks: Algorithms, techniques and the Smart Grid case
- Practical and efficient internet routing with competing interests
- Emergence of Small World Networks Network formation through link selection by selfish nodes
- Strong mediated equilibrium
- Scaling Empirical Game-Theoretic Analysis
- Application de la théorie des jeux à l'optimisation du routage réseau - solutions algorithmiques. (Game theory applied to routing in networks - algorithmic solutions)
- When Do Potential Functions Exist in Heterogeneous Routing Games
- A New Look at Selfish Routing
- A glimpse at Christos H. Papadimitriou
- Profit Sharing with Thresholds and Non-monotone Player Utilities
- Advances in Strategic Network Formation: Preferences, Centrality, and Externalities
- Truthful Mechanism Design for Cooperative Cost Sharing and Congestion Games
- Resource allocation in hard real-time avionic systems. Scheduling and routing problems
- Constrained Pure Nash Equilibria in Graphical Games
Related papers
- Network Creation Games with Disconnected Equilibria
- Strong price of anarchy
- Price of Anarchy in Non-Cooperative Load Balancing
- Intrinsic Robustness of the Price of Anarchy: Abstract of the Kalai Prize Talk
- On the Efficiency of Nash Equilibria in Charging Games
- Nash equilibria in discrete routing games with convex latency functions
- Rate Adaptation Games in Wireless LANs: Nash Equilibrium and Price of Anarchy