Approximating the Minmax Value of Three-Player Games within a Constant is as Hard as Detecting Planted Cliques

We consider the problem of approximating the minmax value of a multi-player game in strategic form. We argue that in three-player games with 0-1 payoffs, approximating the minmax value within an additive constant smaller than

ξ

/2, where

$\xi = \frac{3-\sqrt5}{2} \approx 0.382$

, is not possible by a polynomial time algorithm. This is based on assuming hardness of a version of the so-called planted clique problem in Erdős-Rényi random graphs, namely that of

detecting

a planted clique. Our results are stated as reductions from a promise graph problem to the problem of approximating the minmax value, and we use the detection problem for planted cliques to argue for its hardness. We present two reductions: a randomised many-one reduction and a deterministic Turing reduction. The latter, which may be seen as a derandomisation of the former, may be used to argue for hardness of approximating the minmax value based on a hardness assumption about

deterministic

algorithms. Our technique for derandomisation is general enough to also apply to related work about

ε

-Nash equilibria.