Mark Braverman, Young Kun Ko, Omri Weinstein

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 >>>

Tim Roughgarden, Omri Weinstein

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 >>>