Convergence to approximate Nash equilibria in congestion games

DOI10.1016/j.geb.2009.05.004zbMath1209.91020OpenAlexW1990873282MaRDI QIDQ632952

Steve Chien, Alistair Sinclair

Publication date: 28 March 2011

Published in: Games and Economic Behavior (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.geb.2009.05.004

zbMATH Keywords

convergence to equilibriumcongestion gamespolynomial timebest-response dynamicsapproximate Nash equilibriaPLS-completenesssymmetric congestion games

Mathematics Subject Classification ID

Noncooperative games (91A10) (n)-person games, (n>2) (91A06)

Related Items (23)

Potential games, path independence and Poisson's binomial distribution ⋮ Congestion Games with Complementarities ⋮ Concurrent imitation dynamics in congestion games ⋮ Security from the adversary's inertia-controlling convergence speed when playing mixed strategy equilibria ⋮ Congestion games with mixed objectives ⋮ On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games ⋮ Decentralized dynamics for finite opinion games ⋮ Equilibrium computation in resource allocation games ⋮ Convergence of incentive-driven dynamics in Fisher markets ⋮ On the performance of mildly greedy players in cut games ⋮ Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses ⋮ Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions ⋮ Computing pure Nash and strong equilibria in bottleneck congestion games ⋮ Congestion Games with Mixed Objectives ⋮ On lookahead equilibria in congestion games ⋮ On approximate pure Nash equilibria in weighted congestion games with polynomial latencies ⋮ Short sequences of improvement moves lead to approximate equilibria in constraint satisfaction games ⋮ Approximate Nash equilibria in anonymous games ⋮ Competitive routing over time ⋮ Decentralized utilitarian mechanisms for scheduling games ⋮ Fast Convergence of Best-Reply Dynamics in Aggregative Games ⋮ On Approximate Pure Nash Equilibria in Weighted Congestion Games with Polynomial Latencies ⋮ Pure Nash equilibria in restricted budget games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• How easy is local search?
• 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
• Fast convergence to Wardrop equilibria by adaptive sampling methods
• Simple Local Search Problems that are Hard to Solve
• On the impact of combinatorial structure on congestion games
• Distributed Selfish Load Balancing
• The complexity of pure Nash equilibria
• The price of anarchy of finite congestion games
• Algorithms, games, and the internet
• Routing without regret
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game
• Equilibrium points in n -person games
• The Price of Routing Unsplittable Flow

This page was built for publication: Convergence to approximate Nash equilibria in congestion games