Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Approximate Nash equilibrium:
TR14-092 | 22nd July 2014
Mark Braverman, Young Kun Ko, Omri Weinstein

Approximating the best Nash Equilibrium in $n^{o(\log n)}$-time breaks the Exponential Time Hypothesis

The celebrated PPAD hardness result for finding an exact Nash equilibrium in a two-player game
initiated a quest for finding \emph{approximate} Nash equilibria efficiently, and is one of the major open questions in algorithmic game theory.

We study the computational complexity of finding an $\eps$-approximate Nash equilibrium with good social ... more >>>

TR16-055 | 11th April 2016
Tim Roughgarden, Omri Weinstein

On the Communication Complexity of Approximate Fixed Points

We study the two-party communication complexity of finding an approximate Brouwer fixed point of a composition
of two Lipschitz functions $g\circ f : [0,1]^n \to [0,1]^n$, where Alice holds $f$ and Bob holds $g$. We prove an
exponential (in $n$) lower bound on the deterministic ... more >>>

ISSN 1433-8092 | Imprint