Fast Complete Algorithm for Multiplayer Nash Equilibrium

• URL: http://arxiv.org/abs/2002.04734v9
• Date: Fri, 9 Dec 2022 07:03:01 GMT
• Title: Fast Complete Algorithm for Multiplayer Nash Equilibrium
• Authors: Sam Ganzfried
• Abstract summary: We describe a new complete algorithm for computing Nash equilibrium in multiplayer general-sum games. We demonstrate that the algorithm runs significantly faster than the prior fastest complete algorithm on several game classes previously studied.
• Score: 1.7132914341329848
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We describe a new complete algorithm for computing Nash equilibrium in multiplayer general-sum games, based on a quadratically-constrained feasibility program formulation. We demonstrate that the algorithm runs significantly faster than the prior fastest complete algorithm on several game classes previously studied and that its runtimes even outperform the best incomplete algorithms.

Related papers

• The Many Faces of Optimal Weak-to-Strong Learning [10.985323882432086]
  We present a new and surprisingly simple Boosting algorithm that obtains a provably optimal sample complexity. Our pilot empirical study suggests that our new algorithm might outperform previous algorithms on large data sets.
  arXiv  Detail & Related papers  (2024-08-30T09:38:51Z)
• A Generalized Extensive-Form Fictitious Play Algorithm [0.0]
  We introduce a simple extensive-form algorithm for finding equilibria of two-player, zero-sum games. We compare its performance to that of a similar extensive-form fictitious play algorithm and a counter-factual regret minimization algorithm.
  arXiv  Detail & Related papers  (2023-10-14T20:18:49Z)
• On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
  We study the problem of best-arm identification with fixed budget in multi-armed bandits with Bernoulli rewards. For the problem with two arms, also known as the A/B testing problem, we prove that there is no algorithm that performs as well as the algorithm sampling each arm equally.
  arXiv  Detail & Related papers  (2023-08-23T08:38:53Z)
• Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer Vision [6.574107319036238]
  Hochbaum pseudoflow algorithm is fastest serial algorithm, Boykov-Kolmogorov algorithm is most memory efficient. Existing parallel min-cut/max-flow algorithms can significantly outperform serial algorithms on large problems but suffers from added overhead on small to medium problems.
  arXiv  Detail & Related papers  (2022-02-01T14:06:27Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  We study last-iterate convergence of optimistic algorithms in sequential games. We show that all of these algorithms enjoy last-iterate convergence, with some of them even converging exponentially fast.
  arXiv  Detail & Related papers  (2021-06-27T22:02:26Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  We propose unified algorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models. Our algorithms exploit a fundamental connection between gradients and expectations, which allows us to derive efficient algorithms.
  arXiv  Detail & Related papers  (2020-08-29T14:58:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.