Convergence and approximation in potential games

DOI10.1016/j.tcs.2012.02.033zbMath1251.91008OpenAlexW2016663842MaRDI QIDQ441854

Anastasios Sidiropoulos, George Christodoulou, Vahab S. Mirrokni

Publication date: 8 August 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.02.033

zbMATH Keywords

high dimensional datadiffusion mapsnonlinear dimensionality reductiongeometry of dataHessian locally linear embeddingIsomapsLaplacian eigenmapslocal tangent space alignmentlocally linear embeddingmanifold embedding techniquemaximum variance unfolding

Mathematics Subject Classification ID

Noncooperative games (91A10) Game theory (91Axx)

Related Items (15)

Best-response dynamics in combinatorial auctions with item bidding ⋮ On the performance of mildly greedy players in cut games ⋮ When ``better is better than ``best ⋮ Efficient Equilibria in Polymatrix Coordination Games ⋮ Best-response dynamics, playing sequences, and convergence to equilibrium in random games ⋮ Inefficiency of games with social context ⋮ Tight Bounds for Online Vector Scheduling ⋮ Computation and efficiency of potential function minimizers of combinatorial congestion games ⋮ Short sequences of improvement moves lead to approximate equilibria in constraint satisfaction games ⋮ Congestion games with priority-based scheduling ⋮ 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 ⋮ Some anomalies of farsighted strategic behavior ⋮ Pure Nash Equilibria and Best-Response Dynamics in Random Games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Correlation clustering
• How easy is local search?
• Potential games
• A class of games possessing pure-strategy Nash equilibria
• How bad is selfish routing?
• Simple Local Search Problems that are Hard to Solve
• The Speed of Convergence in Congestion Games under Best-Response Dynamics
• The complexity of pure Nash equilibria
• The price of anarchy of finite congestion games
• Tight approximation algorithms for maximum general assignment problems
• Performances of One-Round Walks in Linear Congestion Games
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Integer Linear Programs and Local Search for Max-Cut
• Algorithms, games, and the internet
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Convergence and Approximation in Potential Games
• Automata, Languages and Programming
• Algorithms – ESA 2005
• The Price of Routing Unsplittable Flow

This page was built for publication: Convergence and approximation in potential games