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

diffusion mapsgeometry of dataHessian locally linear embeddinghigh dimensional dataIsomapsLaplacian eigenmapslocal tangent space alignmentlocally linear embeddingmanifold embedding techniquemaximum variance unfoldingnonlinear dimensionality reduction

Mathematics Subject Classification ID

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

Review text

The paper addresses the field of game theory and, in particular, convergence and approximation within potential games.NEWLINENEWLINEConvergence speed to approximately optimal states is investigated within selfish routing games and cut games. The authors provide bounds in terms of the number of rounds, model the sequential interaction between players by a best-response walk in the state graph; the goal is to bound the social value of the states at the end of these walks -- by taking into account the cut and the total happiness as the social functions.

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

• 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?
• 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?)
• 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 complexity of pure Nash equilibria
• The price of anarchy of finite congestion games
• The price of routing unsplittable flow
• The Speed of Convergence in Congestion Games under Best-Response Dynamics
• Tight approximation algorithms for maximum general assignment problems

Cited in

(32)

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

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)