Aarhus University Seal / Aarhus Universitets segl

Approximating the minmax value of Three-player games within a constant is as hard as detecting planted cliques

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

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 ξ=3−5 √ 2 ≈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
Original languageEnglish
Book seriesLecture Notes in Computer Science
Volume7615
Pages (from-to)96-107
Number of pages12
ISSN0302-9743
DOIs
Publication statusPublished - 2012
EventSymposium on Algorithmic Game Theory - Barcelona, United States
Duration: 22 Oct 201223 Oct 2012
Conference number: 5

Conference

ConferenceSymposium on Algorithmic Game Theory
Number5
CountryUnited States
CityBarcelona
Period22/10/201223/10/2012

Bibliographical note

Title of the vol.: Algorithmic Game Theory : 5th International Symposium, SAGT 2012, Barcelona, Spain, October 22-23, 2012. Proceedings / ed. by Maria Serna.
ISBN: 978-3-642-33995-0, 978-3-642-33996-7

See relations at Aarhus University Citationformats

ID: 51836658