# linear time nash equilibirum aproximations for two player zero sum games

I'm working on an AI for a game where I'd like the game where each player has hundreds of moves to select from and so the game matrix has 10s of thousands of entries. The game is however zero sum. Given that I have 10s of thousands of entries I can't apply even an $$O(n^2)$$ algorithm or the result will take too long so I need a linear time algorithm. I've found this note which details an exceedingly simple $$\frac{1}{2}$$-approximation algorithm that works for any game, not just a zero sum game. It also does so by only looking at $$O(\sqrt{N})$$ entries in the table which is even faster than what I need.

Zero sum games can have their exact equilibrium computed in polynomial time via linear programming but this is too slow.

What I'm looking for is something in between; Something that uses more computational resources than the simple 1/2-aproximation algorithm but gives a better approximation; Something that uses fewer computational resources than linear programming but only gives an approximate answer. Does a linear time approximation algorithm exist for 2-player zero-sum games that is better than $$\frac{1}{2}$$-approximation?