Advertisement
Published in:
2009 | OriginalPaper | Chapter
Small Clique Detection and Approximate Nash Equilibria
Authors : Lorenz Minder, Dan Vilenchik
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Recently, Hazan and Krauthgamer showed [12] that if, for a fixed small
ε
, an
ε
-best
ε
-approximate Nash equilibrium can be found in polynomial time in two-player games, then it is also possible to find a planted clique in
G
n
, 1/2
of size
C
log
n
, where
C
is a large fixed constant independent of
ε
. In this paper, we extend their result to show that if an
ε
-best
ε
-approximate equilibrium can be efficiently found for arbitrarily small
ε
> 0, then one can detect the presence of a planted clique of size (2 +
δ
) log
n
in
G
n
, 1/2
in polynomial time for arbitrarily small
δ
> 0. Our result is optimal in the sense that graphs in
G
n
, 1/2
have cliques of size (2 −
o
(1)) log
n
with high probability.