Convergence to approximate Nash equilibria in congestion games

No abstract is available for this paper.

• Publication year

  2007

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2007-01-07

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.geb.2009.05.004
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Fast convergence to nearly optimal solutions in potential games

  2008cited by this paper
• Concurrent imitation dynamics in congestion games

  2008cited by this paper
• Inapproximability of pure nash equilibria

  2008cited by this paper
• Routing without regret: on convergence to nash equilibria of regret-minimizing algorithms in routing games

  2006influential reference
• The complexity of computing a Nash equilibrium

  2006cited by this paper
• Computing Nash Equilibria: Approximation and Smoothed Complexity

  2006cited by this paper
• Fast convergence to Wardrop equilibria by adaptive sampling methods

  2006influential reference
• On the Impact of Combinatorial Structure on Congestion Games

  2006cited by this paper
• Settling the Complexity of Two-Player Nash Equilibrium

  2006cited by this paper
• The Price of Routing Unsplittable Flow

  2005cited by this paper
• Fast convergence of selfish rerouting

  2005cited by this paper
• Distributed selfish load balancing

  2005cited by this paper
• The price of anarchy of finite congestion games

  2005cited by this paper
• Selfish routing and the price of anarchy

  2005cited by this paper
• Sink equilibria and convergence

  2005cited by this paper
• Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game

  2004cited by this paper
• Convergence Issues in Competitive Games

  2004cited by this paper
• Approximate local search in combinatorial optimization

  2004cited by this paper
• The complexity of pure Nash equilibria

  2004cited by this paper
• Bounding the inefficiency of equilibria in nonatomic congestion games

  2004cited by this paper
• Playing large games using simple strategies

  2003cited by this paper
• Convergence Time to Nash Equilibria

  2003cited by this paper
• Efficient Nash Computation in Large Population Games with Bounded Influence

  2002cited by this paper
• Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions

  2002cited by this paper
• Algorithms, games, and the internet

  2001cited by this paper
• Congestion Games with Player-Specific Payoff Functions

  1996cited by this paper
• Potential Games

  1994cited by this paper
• Simple Local Search Problems That are Hard to Solve

  1991cited by this paper
• How Easy is Local Search?

  1985cited by this paper
• A class of games possessing pure-strategy Nash equilibria

  1973influential reference
• Studies in the Economics of Transportation.

  1956cited by this paper
• Equilibrium Points in N-Person Games.

  1950cited by this paper
• Convergence to Approximate Nash Equilibria in Congestion Games †

  year unknowncited by this paper

• On the Performance of Mildly Greedy Players in k-Coloring Games

  2025cites this paper
• Efficiently Computing Equilibria in Budget-Aggregation Games

  2025cites this paper
• Computing approximate pure Nash equilibria for weighted congestion games

  2025cites this paper
• Grouped Satisficing Paths in Pure Strategy Games: a Topological Perspective

  2025cites this paper
• Online Multi-player Resource-Sharing Games with Bandit Feedback

  2025cites this paper
• Gamekeeper: Online Learning for Admission Control of Networked Open Multiagent Systems

  2024cites this paper
• Estimating Markov Chain Mixing Times: Convergence Rate Towards Equilibrium of a Stochastic Process Traffic Assignment Model

  2024cites this paper
• Minimizing Rosenthal's Potential in Monotone Congestion Games

  2024cites this paper
• Cooperative Caching in Satellite-Terrestrial Integrated Networks: A Region Features Aware Approach

  2024cites this paper
• Finite-time convergence to an $\epsilon$-efficient Nash equilibrium in potential games

  2024cites this paper
• Paths to Equilibrium in Games

  2024cites this paper
• Potentials in Social Environments

  2024cites this paper
• Exponential Lower Bounds on the Double Oracle Algorithm in Zero-Sum Games

  2024cites this paper
• Alternation makes the adversary weaker in two-player games

  2023cites this paper
• A Two-Player Resource-Sharing Game with Asymmetric Information

  2023cites this paper
• Subproject A3: The Market for Services: Incentives, Algorithms, Implementation

  2023cites this paper
• Proportional Fairness in Obnoxious Facility Location

  2023cites this paper
• Semi Bandit Dynamics in Congestion Games: Convergence to Nash Equilibrium and No-Regret Guarantees

  2023cites this paper
• To Lie or Not to Lie in Non-Cooperative User-Centric Networks: Is Lying Worth It?

  2023cites this paper
• Graphon Games with Multiple Equilibria: Analysis and Computation

  2023cites this paper
• Credit-Based Congestion Pricing: Equilibrium Properties and Optimal Scheme Design

  2022cites this paper
• Are we heading towards a BBR-dominant internet?

  2022cites this paper
• Independent Learning with Local Information in Mean-Field Games

  2022cites this paper
• Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming

  2022cites this paper
• Resource Allocation in Edge Computing: A Game-Theoretic Perspective

  2022influential citation
• $\frac{\rho}{1-\epsilon}$-approximate pure Nash equilibria algorithms for weighted congestion games and their runtimes

  2022influential citation
• Harmony or Involution: Game Inspiring Age-of-Information Optimization for Edge Data Gathering in Internet of Things

  2022influential citation
• Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularization

  2022cites this paper
• Blockchain Nash Dynamics and the Pursuit of Compliance

  2022cites this paper
• Modelling reservation-based shared autonomous vehicle services: A dynamic user equilibrium approach

  2022cites this paper
• Using Game Theory to Assign Groundwater Pumping Schedules

  2022cites this paper
• Satisficing Paths and Independent Multiagent Reinforcement Learning in Stochastic Games

  2021cites this paper
• ScholarlyCommons ScholarlyCommons

  2021cites this paper
• Sampling from the Gibbs Distribution in Congestion Games

  2021cites this paper
• Node-Max-Cut and the Complexity of Equilibrium in Linear Weighted Congestion Games

  2020cites this paper
• Tatonnement beyond gross substitutes? Gradient descent to the rescue

  2020cites this paper
• Dynamic Reserve Prices for Repeated Auctions: Learning from Bids - Working Paper

  2020cites this paper
• Communication complexity of Nash equilibrium in potential games (extended abstract)

  2020cites this paper
• On Sharding Open Blockchains with Smart Contracts

  2020cites this paper
• Computation and efficiency of potential function minimizers of combinatorial congestion games

  2020cites this paper
• Survive and Thrive: A Stochastic Game for DDoS Attacks in Bitcoin Mining Pools

  2020cites this paper
• Selfish Caching Games on Directed Graphs

  2020cites this paper
• When Nash met Markov: Novel results for pure Nash equilibria and the switch Markov chain

  2019cites this paper
• Node Max-Cut and Computing Equilibria in Linear Weighted Congestion Games

  2019cites this paper
• Introduction

  2019cites this paper
• Uniqueness and computation of equilibria in resource allocation games

  2019cites this paper
• Approximate pure nash equilibria in congestion, opinion formation and facility location games

  2019cites this paper
• On approximate pure Nash equilibria in weighted congestion games with polynomial latencies

  2019cites this paper
• Dynamics of manipulation in voting, veto and plurality

  2019cites this paper
• Metastability of the Logit Dynamics for Asymptotically Well-Behaved Potential Games

  2019cites this paper
• How Bad is Selfish Caching?

  2019influential citation
• Competitive Cloud Pricing for Long-Term Revenue Maximization

  2019cites this paper
• An Improved Algorithm for Computing Approximate Equilibria in Weighted Congestion Games

  2018cites this paper
• Multi-Agent Online Learning with Imperfect Information

  2018cites this paper
• Security from the Adversary's Inertia-Controlling Convergence Speed When Playing Mixed Strategy Equilibria

  2018cites this paper
• Computing Nash equilibria for integer programming games

  2018cites this paper
• Potential games, path independence and Poisson’s binomial distribution

  2018cites this paper
• The Complexity of Sequential Routing Games

  2018cites this paper
• Resource Allocation Game on Social Networks: Best Response Dynamics and Convergence

  2018cites this paper
• Convergence of Iterative Voting Under Restrictive Dynamics for Plurality Rule: A Review

  2018cites this paper
• Electric vehicle charging station placement and management

  2018cites this paper
• Concept Design of Medium Access Control for Spectrum Access Systems in 3.5 GHz

  2018cites this paper
• Pure Nash equilibria in restricted budget games

  2018cites this paper
• Dynamic Pricing for Reusable Resources in Competitive Market With Stochastic Demand

  2018cites this paper
• Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses

  2018cites this paper
• G T ] 8 A ug 2 01 8 Equilibrium Computation in Resource Allocation Games

  2018cites this paper
• Analysing the impact of travel information for minimising the regret of route choice

  2018cites this paper
• Potential Function Minimizers of Combinatorial Congestion Games: Efficiency and Computation

  2017cites this paper
• Computing Approximate Pure Nash Equilibria in Shapley Value Weighted Congestion Games

  2017cites this paper
• A better-response strategy for self-interested planning agents

  2017cites this paper
• Fast Convergence of Best-Reply Dynamics in Aggregative Games

  2017cites this paper
• The Efficiency of Best-Response Dynamics

  2017cites this paper
• Walrasian Dynamics in Multi-unit Markets

  2017cites this paper
• Pure Nash equilibria in restricted budget games

  2017cites this paper
• Robustness in Discrete Preference Games

  2017cites this paper
• Congestion Games with Complementarities

  2017cites this paper
• Non-Cooperative Games for Self-Interested Planning Agents

  2017cites this paper
• Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos

  2017cites this paper
• Learning to Minimise Regret in Route Choice

  2017cites this paper
• Shapley Facility Location Games

  2017cites this paper
• A congestion avoidance game for information exchange on intersections in heterogeneous vehicular networks

  2017cites this paper
• Convergence analysis and control of evolutionary matrix-game dynamics

  2017cites this paper
• Approximate Best-Response Dynamics in Random Interference Games

  2017cites this paper
• Reconciling Selfish Routing with Social Good

  2017cites this paper
• Convergence of Incentive-Driven Dynamics in Fisher Markets

  2017cites this paper
• Twenty Lectures on Algorithmic Game Theory

  2016influential citation
• Joint Resource Block and Power Allocation for Interference Management in Device to Device Underlay Cellular Networks: A Game Theoretic Approach

  2016cites this paper
• Equilibrium Computation in Atomic Splittable Singleton Congestion Games

  2016cites this paper
• Networks of conforming or nonconforming individuals tend to reach satisfactory decisions

  2016cites this paper
• Market Dynamics of Best-Response with Lookahead

  2016cites this paper
• FogMQ: A Message Broker System for Enabling Distributed, Internet-Scale IoT Applications over Heterogeneous Cloud Platforms

  2016cites this paper
• Flocking virtual machines in quest for responsive IoT cloud services

  2016cites this paper
• Algorithmic, Game Theoretic and Learning Theoretic Aspects of Distributed Optimization

  2016cites this paper
• Independent lazy better-response dynamics on network games

  2016cites this paper
• Resource Allocation in Operator-owned Content Delivery Systems

  2016cites this paper
• Evolutionary Markov chains, potential games and optimization under the lens of dynamical systems

  2016cites this paper
• Generalized mirror descents in congestion games

  2016cites this paper
• Congestion games with mixed objectives

  2016cites this paper
• Convergence of approximate best-response dynamics in interference games

  2016cites this paper
• Equilibrium computation in resource allocation games

  2016cites this paper