# The Search-and-Mix Paradigm in Approximate Nash Equilibrium Algorithms

arXiv: https://arxiv.org/abs/2310.08066 · HTML: https://mlsanity.com/paper/2310.08066/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 45 references that are in the map.
- First posted on arXiv 12 Oct 2023.

## Builds on (most cited first, 7 of 7)

- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [HyperTree Proof Search for Neural Theorem Proving](https://mlsanity.com/paper/2205.11491/) (2022)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Settling the complexity of computing approximate two-player Nash equilibria](https://mlsanity.com/paper/1606.04550/) (2016)
- [A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games](https://mlsanity.com/paper/2204.11525/) (2022)
- [Distributed Methods for Computing Approximate Equilibria](https://mlsanity.com/paper/1512.03315/) (2015)
- [On Tightness of Tsaknakis-Spirakis Descent Methods for Approximate Nash Equilibria](https://mlsanity.com/paper/2107.01471/) (2021)

## Abstract (arXiv)

AI in Math deals with mathematics in a constructive manner so that reasoning becomes automated, less laborious, and less error-prone. For algorithms, the question becomes how to automate analyses for specific problems. For the first time, this work provides an automatic method for approximation analysis on a well-studied problem in theoretical computer science: computing approximate Nash equilibria in two-player games. We observe that such algorithms can be reformulated into a search-and-mix paradigm, which involves a search phase followed by a mixing phase. By doing so, we are able to fully automate the procedure of designing and analyzing the mixing phase. For example, we illustrate how to perform our method with a program to analyze the approximation bounds of all the algorithms in the literature. Same approximation bounds are computed without any hand-written proof. Our automatic method heavily relies on the LP-relaxation structure in approximate Nash equilibria. Since many approximation algorithms and online algorithms adopt the LP relaxation, our approach may be extended to automate the analysis of other algorithms.