# Can mixed strategies outperform pure strategies?

Let $G$ denote a game with a finite number $n$ of players in which each player $i$ can choose a mixed strategy $\sigma_i$ over a finite set of pure strategies $\Sigma$. Pure strategies can be seen as a special case of mixed strategies with all $\sigma_i$ being further restricted to 100% localize on a single $s \in \Sigma$.

It is folklore that there exists at least one mixed NE (Nash-Equilibrium), but there might exist many different NE. They differ particularly in the support of the $\sigma_i$'s, which can be pure, partially mixed, or fully mixed.

I am interested in globally optimal NE, or at least as good as possible. I have three related question on mixed versus pure NE:

• Can it be (in this generality of games) the case that the best non-pure mixed NE is by far better than the best pure NE?

• For which types of $n$-player games is it known that for every mixed NE there exists a pure NE that is at least as good?

• Is it, from an algorithmic point of view, more efficient to find a mixed NE than a pure NE? (This might be the case since it is somehow related to an inner point method instead of being restricted to the corners of the solution space).

Can it be (in this generality of games) the case that the best non-pure mixed NE is by far better than the best pure NE?

Yes. Here's a simple construction with 2 players and 3 strategies each. It has the form of a matching pennies game with a unique mixed equilibrium and an additional row and column that together give a pure equilibrium with arbitrarily bad payoff. There is an additional mixed equilibrium given by "mixing" the two already described equilibria. In the following example, the matching pennies equilibrium has payoff 0.5 and the pure equilibrium has payoff 0 for both players, but hopefully it is clear that the pure one can be made to have an arbitrarily bad payoff. The game $(A,B)$ is as follows:

 A=
0   1  -1
1   0  -1
-1  -1   0

B=
1   0  -1
0   1  -1
-1  -1   0


If you want to check out the equilibria, you can use, e.g., http://banach.lse.ac.uk.

For which types of n-player games is it known that for every mixed NE there exists a pure NE that is at least as good?

Potential games - see

Monderer, Dov, and Lloyd S. Shapley. "Potential games." Games and economic behavior 14.1 (1996): 124-143.

Is it, from an algorithmic point of view, more efficient to find a mixed NE than a pure NE? (This might be the case since it is somehow related to an inner point method instead of being restricted to the corners of the solution space).

In some cases, it is easy to check if a pure equilibrium exists and return one if it does but it is hard (under suitable complexity-theoretic assumptions) to find a mixed equilibrium. For example, take 2-player games in strategic form, say $k \times k$ games for simplicity:

• One can check and return a pure equilibrium if one exists in time $O(k^2)$.
• It is $\mathtt{PPAD}$-hard to find a mixed equilibrium, and a subexponential (in $k$) algorithm for this problem would be a major breakthrough, and it is widely believed that no polynomial-time algorithm exists.

In some potential games, e.g. asymmetric network congestion games, on the other hand, it is $\mathtt{PLS}$-hard to find a pure equilibrium (which is guaranteed to exist), but it may actually be easier to find a mixed equilibrium, since then the computational problem lies in both $\mathtt{PPAD}$ and $\mathtt{PLS}$. See

Daskalakis, Constantinos, and Christos Papadimitriou. "Continuous local search." Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 2011.