2
$\begingroup$

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.

  • 0
    Have you checked the Poisson approximation of large games suggested by Myerson?2012-10-12

1 Answers 1

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.