Lipton; Mehta (2-player Nash Equilibria)

Time Complexity

$O(n^{(O(log n)$)} (previously $O(n^{2} logn)$????)

Space Complexity

(see sheet {2}) words

()

Approximate?

Approximate

Approximation Factor:

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

2003

Reference

https://dl.acm.org/doi/10.1145/779928.779933