On the performance of approximate equilibria in congestion games

DOI10.1007/s00453-010-9449-2zbMath1219.91009arXiv0804.3160OpenAlexW1725578675MaRDI QIDQ634681

Paul G. Spirakis, George Christodoulou, Elias Koutsoupias

Publication date: 16 August 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0804.3160

zbMATH Keywords

congestion gamesprice of anarchyalgorithmic game theoryprice of stabilityselfish routingapproximate equilibria

Mathematics Subject Classification ID

Noncooperative games (91A10) (n)-person games, (n>2) (91A06) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Related Items (24)

Congestion Games with Complementarities ⋮ Tight Inefficiency Bounds for Perception-Parameterized Affine Congestion Games ⋮ The price of anarchy and stability in general noisy best-response dynamics ⋮ Tight inefficiency bounds for perception-parameterized affine congestion games ⋮ On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games ⋮ A Glimpse at Paul G. Spirakis ⋮ A Selective Tour Through Congestion Games ⋮ Collusion in atomic splittable routing games ⋮ On the performance of mildly greedy players in cut games ⋮ Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses ⋮ Sensitivity of wardrop equilibria: revisited ⋮ Price of anarchy for parallel link networks with generalized mean objective ⋮ On the performance of approximate equilibria in congestion games ⋮ The price of stability for undirected broadcast network design with fair cost allocation is constant ⋮ Non-atomic one-round walks in congestion games ⋮ The impact of worst-case deviations in non-atomic network routing games ⋮ A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games ⋮ The price of anarchy of affine congestion games with similar strategies ⋮ Unnamed Item ⋮ On the Robustness of the Approximate Price of Anarchy in Generalized Congestion Games ⋮ On the robustness of the approximate price of anarchy in generalized congestion games ⋮ The Price of Stability of Weighted Congestion Games ⋮ The Price of Stability of Weighted Congestion Games ⋮ A unifying approximate potential for weighted congestion games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the performance of approximate equilibria in congestion games
• A note on approximate Nash equilibria
• Potential games
• Bounding the inefficiency of equilibria in nonatomic congestion games
• Congestion games with player-specific payoff functions
• A class of games possessing pure-strategy Nash equilibria
• The complexity of computing a Nash equilibrium
• How bad is selfish routing?
• Fast, Fair, and Efficient Flows in Networks
• The Price of Stability for Network Design with Fair Cost Allocation
• An Optimization Approach for Approximate Nash Equilibria
• The complexity of pure Nash equilibria
• The price of anarchy of finite congestion games
• Tight Bounds for Selfish and Greedy Load Balancing
• On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations
• Algorithms, games, and the internet
• Algorithmic Game Theory
• Exact Price of Anarchy for Polynomial Congestion Games
• Algorithms – ESA 2005
• Traffic assignment problem for a general network
• Selfish Routing in Capacitated Networks
• The Price of Routing Unsplittable Flow

This page was built for publication: On the performance of approximate equilibria in congestion games