Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a pretty large two-player zero-sum game in which each agent must choose between many actions. I am seeking an algorithm to approximate a mixed strategy for each player. Algorithmic simplicity and speed are more important than worse-case performance.

I realize this question is a bit vague. Thus, any algorithm not obviously dominated by another (i.e. the other performs better and is faster) is a good answer. Obviously, I'm not looking for the extremes of picking random strategies or finding the exact perfect strategies.

share|improve this question
Have you checked the Poisson approximation of large games suggested by Myerson? –  Cristian Oct 12 '12 at 15:54

1 Answer 1

You might be interested in the paper Simple Strategies for Large Zero-Sum Games with Applications to Complexity Theory, which gives a simple probabilistic proof that, for any 2-player zero-sum game with payoffs in $[0,1]$, each player has an $\epsilon$-optimal mixed strategy that plays uniformly at random from a multiset of $O(\log(n)/\epsilon^2)$ pure strategies (where $n$ is the number of pure strategies available to the other player). Here $\epsilon$-optimal means that the strategy guarantees an expected payoff within an additive $\epsilon$ of the value of the game.

If you want to compute such a strategy, you can do so by solving the game (via linear programming) and then randomly sampling from the optimal mixed strategy. Or you can compute the sparse strategy directly using a Lagrangian-relaxation algorithm; see e.g. Beating Simplex for Packing and Covering Linear Programs and references therein, particularly by Grigoriadis and Khachiyan.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.