Convergence and approximation in potential games

DOI10.1016/J.TCS.2012.02.033MaRDI QIDQ441854zbMATH OpenOpenAlexFDO

Authors George Christodoulou, Anastasios Sidiropoulos, 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

nonlinear dimensionality reductionhigh dimensional datadiffusion mapsgeometry 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)

Recommendations

• Convergence and Approximation in Potential Games
• The speed of convergence in congestion games under best-response dynamics
• The Speed of Convergence in Congestion Games under Best-Response Dynamics
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• On the performance of mildly greedy players in cut games

Cites work

• scientific article; zbMATH DE number 5485547 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 2038734 (Why is no real title available?)
• A class of games possessing pure-strategy Nash equilibria
• Algorithms – ESA 2005
• Algorithms, games, and the internet
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Automata, Languages and Programming
• Convergence and Approximation in Potential Games
• Convergence to approximate Nash equilibria in congestion games
• Correlation clustering
• How bad is selfish routing?
• How easy is local search?
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Integer Linear Programs and Local Search for Max-Cut
• Performances of One-Round Walks in Linear Congestion Games
• Potential games
• 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
• The price of routing unsplittable flow
• Tight approximation algorithms for maximum general assignment problems

Cited in

(29)

• On the performance of mildly greedy players in cut games
• A note on the convergence of transfer sequences in \(n\)-person games
• Efficient equilibria in polymatrix coordination games
• Some anomalies of farsighted strategic behavior
• Circumventing the price of anarchy: leading dynamics to good behavior
• On the impact of singleton strategies in congestion games
• Computation and efficiency of potential function minimizers of combinatorial congestion games
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games
• Potential functions and the inefficiency of equilibria
• Tight bounds for online vector scheduling
• A contraction principle for finite global games
• Variational convergence: approximation and existence of equilibria in discontinuous games
• The convergence of equilibrium strategies of approximating signaling games
• Convergence and Approximation in Potential Games
• When ``better is better than ``best
• Best-response dynamics in combinatorial auctions with item bidding
• Minimum stable cut and treewidth
• Pure Nash equilibria and best-response dynamics in random games
• Complexity and optimality of the best response algorithm in random potential games
• Inefficiency of games with social context
• Congestion games with priority-based scheduling
• On the performance of mildly greedy players in cut games
• Computing better approximate pure Nash equilibria in cut games via semidefinite programming
• Convergence and approximation results for non-cooperative Bayesian games: Learning theorems
• scientific article; zbMATH DE number 1054809 (Why is no real title available?)
• Potential games and well-posedness properties
• Best-response dynamics, playing sequences, and convergence to equilibrium in random games
• The price of anarchy of affine congestion games with similar strategies

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q441854)