Efficient Computation of Approximate Pure Nash Equilibria in Congestion Games

DOI10.1109/FOCS.2011.50zbMath1292.91012OpenAlexW2089015050MaRDI QIDQ5495031

Angelo Fanelli, Alexander Skopalik, Ioannis Caragiannis, N. V. Gravin

Publication date: 30 July 2014

Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2011.50

Mathematics Subject Classification ID

Noncooperative games (91A10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (24)

Congestion Games with Complementarities ⋮ Tight Inefficiency Bounds for Perception-Parameterized Affine Congestion Games ⋮ Congestion games with mixed objectives ⋮ On Existence and Properties of Approximate Pure Nash Equilibria in Bandwidth Allocation Games ⋮ Equilibrium computation in resource allocation games ⋮ Computing Approximate Nash Equilibria in Network Congestion Games with Polynomially Decreasing Cost Functions ⋮ 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 ⋮ On Lookahead Equilibria in Congestion Games ⋮ Congestion Games with Mixed Objectives ⋮ Efficiency and inefficiency of Nash equilibrium for scheduling games on batching-machines with activation cost ⋮ A Metaheuristic Approach to Compute Pure Nash Equilibria ⋮ The efficiency of Nash equilibria in the load balancing game with a randomizing scheduler ⋮ On lookahead equilibria in congestion games ⋮ On approximate pure Nash equilibria in weighted congestion games with polynomial latencies ⋮ Resource buying games ⋮ Short sequences of improvement moves lead to approximate equilibria in constraint satisfaction games ⋮ Approximate Nash equilibria in anonymous 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 ⋮ Pareto-optimal Algorithms for Scheduling Games on Parallel-batching Machines with Activation Cost ⋮ Pure Nash equilibria in restricted budget games

This page was built for publication: Efficient Computation of Approximate Pure Nash Equilibria in Congestion Games