  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.
