ECCC-Report TR12-025https://eccc.weizmann.ac.il/report/2012/025Comments and Revisions published for TR12-025en-usMon, 26 Mar 2012 22:16:52 +0200
Paper TR12-025
| Approximating the minmax value of 3-player games within a constant is as hard as detecting planted cliques |
Kord Eickmeyer,
Kristoffer Arnsfelt Hansen,
Elad Verbin
https://eccc.weizmann.ac.il/report/2012/025We consider the problem of approximating the minmax value of a multiplayer game in strategic form. We argue that in 3-player games with 0-1 payoffs, approximating the minmax value within an additive constant smaller than $\xi/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 randomized many-one reduction and a deterministic Turing reduction. The latter, which may be seen as a derandomization 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 derandomization is general enough to also apply to related work about $\epsilon$-Nash equilibria.Mon, 26 Mar 2012 22:16:52 +0200https://eccc.weizmann.ac.il/report/2012/025