This is rather an open-ended question, but I'm posting here since I was not able to find a good resource elsewhere.
Say there's a two player zero sum game with payoff matrix $A$ that's $N \times H$. Call the value of this game $\lambda_N^*$. If $N$ is very large, we would be interested in finding $n\ll N$ somehow that might not do as well, but reasonably approximates $\lambda_N^*$. Let the value of the game of this subpayoff matrix be $\lambda_n^*$.
Here are my questions:
- Has there been any research on how to wisely select $n$, so that $\lambda_n^*$ best approximates $\lambda_N^*$?
- If so, can you provide a reference, and the main result, e.g. the approximation ratio, any assumptions necessary for the payoff matrix?
Small support strategy profiles that achieve additively approximate Nash equilibria have been studied in both zero-sum games:
Lipton RJ, Young NE. Simple strategies for large zero-sum games with applications to complexity theory. InProceedings of the twenty-sixth annual ACM symposium on Theory of computing 1994 May 23 (pp. 734-740). ACM.
Althöfer I. On sparse approximations to randomized strategies and convex combinations. Linear Algebra and its Applications. 1994 Mar 1;199:339-55.
And, more recently, in general games:
Lipton RJ, Markakis E, Mehta A. Playing large games using simple strategies. InProceedings of the 4th ACM conference on Electronic commerce 2003 Jun 9 (pp. 36-41). ACM.
For an $n \times n$ game and a given $\epsilon$, one can find by brute force search over strategies that are uniform on multisets of pure strategies of size $\log n$ an approximate Nash equilibrium where no player can gain more than $\epsilon$ by deviating in time $n^{\frac{\log n}{\epsilon^2}}$.