Name
Abstract | ||
|---|---|---|
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 logn , 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 + *** ) logn 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)) logn with high probability. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-03685-9_50 | APPROX-RANDOM |
Keywords | Field | DocType |
approximate nash equilibrium,size c logn,two-player game,high probability,g n,approximate nash equilibria,polynomial time,small clique detection,approximate equilibrium,nash equilibria,nash equilibrium | Graph,Discrete mathematics,Combinatorics,Random graph,Clique,Nash equilibrium,Time complexity,Polynomial-time approximation scheme,Mathematics | Conference |
Volume | ISSN | Citations |
5687 | 0302-9743 | 13 |
PageRank | References | Authors |
0.67 | 13 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lorenz Minder | 1 | 92 | 5.53 |
| Dan Vilenchik | 2 | 143 | 13.36 |