# Sparse strategies for zero-sum matrix games

Here is a derivation of a Lagrangian-relaxation algorithm for computing approximately optimal mixed strategies for two-player zero-sum matrix games. It illustrates the basic idea of deriving Lagrangian-relaxation algorithms.

The algorithm and the derivation are from . The approximation guarantee is comparable to those for the packing algorithms of Plotkin, Shmoys, and Tardos . The mixed strategies also happen to be sparse. The existence proof for sparse mixed strategies is from .

Problem statement.

Fix a payoff matrix for a two-player zero sum game, so that is the payoff from MIN to MAX if MAX plays pure strategy and MIN plays pure strategy .

A mixed strategy for MIN is a probability distribution on . The value of is (the maximum expected payoff that MAX can force if MIN plays a pure strategy randomly from ).

We say a mixed strategy is -sparse if it chooses uniformly from a multiset of pure strategies. Equivalently, each probability is an integer multiple of .

The goal is to compute some -sparse mixed strategy for MIN whose value is at most times the minimum possible.

(Although we will not use them in this note, of course symmetrical definitions hold for MAX. A mixed strategy for MAX is a probability distribution on ; it has value . If denotes an optimal (minimum value) mixed strategy for MAX, then Von Neumann’s min-max theorem states that, for any payoff matrix , the value of equals the value of .)

# Computing an approximately optimal k-sparse mixed strategy

We will derive the following algorithm and performance guarantee:

 1 Initialize to the empty sequence. 2 For : 3 Choose a pure strategy for MIN minimizing , where is the total payoff so far if MAX played every time. 4 Add to the end of . 5 Return , where equals times the number of times occurs in .

Let be the number of pure strategies available to MAX.

Theorem.

For any such that , given the instance, , and , if each payoff is in , then the algorithm returns a -sparse strategy of value at most , where is the minimum value of any mixed strategy for MIN.

To prove the theorem, we apply the method of conditional probabilities to the following rounding scheme. Fix any integer and let be any mixed strategy for MIN.

Randomly sample pure strategies independently from the distribution on .
Return the mixed strategy such that, for each pure strategy , the probability equals the number of times was sampled.

First we analyze the rounding scheme. Let be the value of the mixed strategy .

Lemma ().

Assume each payoff is in . For any , if , then, with positive probability, the rounding scheme returns a -sparse mixed strategy of value at most .

Now we prove the theorem by showing that applying the method of conditional probabilities to the lemma yields the algorithm.

## Running time

The algorithm takes iterations. Each iteration requires selecting the best response for MIN for a given mixed strategy for MAX.

If the goal is to find an approximately optimal mixed strategy (independent of ), then one can just take . If is unknown, then one can simply run the algorithm until the resulting mixed strategy for MIN has value at most times the mixed strategy for MAX defined by . (Note that the main loop of the algorithm is independent of .) This will take iterations.

In many cases of interest, is exponentially small, so the number of iterations can be exponentially large. In this case, Garg and Könemann’s technique of non-uniform increments can be used to modify the algorithm to have iterations.