Should mixed strategies in normal form games be interpreted as measurable functions or probability vectors?

Question

I have recently been stuck trying to understand how game theorists extend a normal form game (matrix game) into a game with mixed strategies (so called mixed extension). I feel like I am missing something obvious, perhaps an implicit identification.

Take for example these notes. At the very bottom near the references section, it reads:

Let $\Sigma_i$ denote the set of probability distributions over $S_i$ ($S_i$ is the set of pure strategies of player $i$)., i.e., $\sigma_i \in \Sigma_i$ if and only if $\sigma_i$ is probability measure.

My confusion in that $\sigma_i$ elsewhere in the game literature typically refers to the mixed strategies, which are vectors $\sigma_i \in \Delta$. For example, in a normal form game with three strategies it can be $\sigma_i = [1,0,0]^T$ (which represents a pure strategy) or $\sigma_i = [1/3, 1/3, 1/3]^T$ rather than measurable function. When people refer to mixed strategies (see Simple proof of the existence of Nash equilibria for 2-person games?), they usually refer to these probability vectors. Is there an implicit identification between these measurable functions and these vectors?

Another confusion arises at the definition of the expected utility (right before the references),

With this assumption, the utility functions $u_i$ are extended from $S = \prod_{j = 1}^I S_j$ to the space of probability distributions $\Sigma = \Pi_{j = 1}^I \Sigma_j$ as follows: $$ u_i(\sigma) = \int_C u_i(s) d\sigma(s)$$ where $\sigma \in \Sigma$

Once again, elsewhere in the literature, the expected utility $u_i$ usually is defined to take from the product of the simplex $\Delta = \prod_{i = 1}^I \Delta_i$ to a real number, i.e., $u_i: \Delta \to \mathbb{R}$ rather than $u_i: \Sigma \to \mathbb{R}$ . Here, the expected utility is taking from a product of measurable spaces. Once again, is there an identification that the authors are making?

So my question is: are mixed strategies in game theory measurable functions or elements of the simplex? If the former, then the expected utility is essentially a composition of measurable functions, is that right? Or is there a common but implicit identification between these two employed in the game theory literature? Or more plainly: what is a mixed strategy? I'm new to game theory so sorry in advance if this is a well known thing.

I've dug up some paper that explicitly defines mixed strategies as measurable function (and even pure strategies as functions). But this seems to be rare.

Greatly appreciated if anyone has a good reference on the construction from normal form game to games with mixed strategies or some references on game theory from measure theory point of view.

Answer 1

This could be a comment but it might clear things up. In short, a mixed strategy is a probability measure over a set of pure strategies (also called actions). If the set of actions is finite, we can represent the probability measure as a vector of probabilities, i.e. an element of the simplex.

I don't see strategies described as measurable functions in any of your references, except Milgrom and Weber --- which is not about normal-form games, as I commented. I do see utility functions described as measurable functions, so make sure you are not confusing strategies and utilities.

Unfortunately I don't know of a measure-theoretic game theory text, but I would recommend going through a standard text (Osborne and Rubinstein is free online) to develop your intuition first, if you're not feeling confident in it.

Answer 2

This is an issue I've grappled with several times when writing both classroom notes and academic papers aimed at economists. The problem is to find a general formulation of which mixed strategies, correlated strategies and quantum strategies are all special cases.

In my experience, economists generally formalize mixed strategies as probability distributions over strategy sets. Correlated strategies then emerge as a natural generalization: A correlated equilibrium is a probability distribution over the product of the players' strategy sets, not necessarily arising from a pair of mixed strategies.

In many contexts I've found it far better to go against the grain and use random variables instead of probability distributions. This is particular so for generalizations to quantum game theory. Here are a few of the relevant considerations.

1. Correlated Equilibria. The most common intuition for correlated equilibria seems to be that some referee (or some force of nature acting as a referee) dictates a probability distribution (known to everyone) over the product of the strategy spaces. The referee randomly draws a strategy pair $(s,t)$ from this distribution. You are instructed to play $s$ and your opponent is instructed to play $t$. The distribution is a correlated equilibrium if each player is always willing to obey these instructions.

(Of course a pair of mixed strategies generates such a probability distribution, which allows us to identify mixed strategies equilibria as a special case of correlated equilibria.)

But (for reasons that will become clearer below) I prefer to think of correlated equilibria this way: There is some random variable on which I am able to condition my strategy --- for example, the presence or absence of a squirrel in my backyard. There is some random variable on which you are able to condition your strategies --- for example, the presence or absence of the same squirrel in your backyard. My random variable might be correlated with yours (as in this case, where the squirrel cannot be in two places at once). A correlated equilibrium occurs when each of us wants to choose one of these strategies, taken the other's choice as given.

This "random variable" formulation is entirely equivalent to the more standard "probability distribution" formulation but in many contexts it feels more intuitive to me. Also, unlike the "probability distribution" formulation, the "random variable" formulation lends itself to natural generalizations. For example, maybe I have a choice between conditioning on the presence of a squirrel in my yard and the presence of a rabbit. Introducing the rabbit can create new equilibria (where one of us observes the rabbit) but can also destroy old equilibria (because it gives us each additional ways to deviate from what used to be an equilibrium).

2. Quantum Equilibria. All of these considerations become more important when generalizing to quantum equilibria. I want each player to have access to an array of quantum observables on which it is possible to condition one's strategy. There are, in general, no joint probability distributions for these observables, so it's pretty awkward to write down anything that looks like a generalization of the "probability distribution" formulation for correlated and mixed strategy equilibria.

3. Classical Games of Private Information. Define a game of private information G as follows: Each of two players has a signal set ${\cal A}_i$ and a strategy set ${\cal S}_i$. There is a given known-to-all probability distribution on ${\cal A}_i\times {\cal A}_2$, from which a pair $(a,b)$ is drawn. I am shown $a$ and your shown $b$; then we choose our strategies. Payoffs are functions of $a,b$ and the strategies we choose.

(For example, we both run competing airlines. A strategy is a pricing structure. A signal is an imperfect measurement of market demand.)

There are two ways to formulate the notion of a mixed strategy equilibrium in this case:

We can define a game G$^\#$ in which a strategy for player $i$ is a map ${\cal A}_i\rightarrow {\cal S}_i$, with payoffs defined in the obvious way, and say that a Type I equilibrium in G is (by definition) a mixed strategy equilibrium in G$^\#$ (or equivalently a pure strategy in G$^\#_M$, where the sub-M means that players are allowed to choose mixed strategies).

Or, given the game of private information G, we can define a new game of private information G, in which a strategy is a map from ${\cal A}_i$ to probability distributions over ${\cal S}_i$, and say that a Type II equilibrium in G is (by definition) a pure strategy equilibrium in G$'$.

(Harold Kuhn called G$^\#_M$ and G$'$ the games of mixed strategies and behavioral strategies associated with G. )

The two notions of equilibrium are equivalent in the sense that there is a one-one correspondence between Type I and Type II equilibria, given by following your nose through the definitions.

Now we come to the reason why I much prefer to use random variables rather than probability distributions. With the "probability distribution" formulation we have, as above, a one-one correspondence between equilibria in G$^\#_M$ and equilibria in G$'$. But with the "random variable" formulation, we have something much more elegant: The games themselves are isomorphic. Indeed, let $\Omega$ be some sample space on which all the relevant random variables are defined. Then a pure strategy in G$^\#_M$ is a mixed strategy in G$^\#$. The set of such mixed strategies is $$Hom(\Omega,Hom({\cal A}_i,{\cal S}_i))$$ By contrast, the pure strategies in G$'$ form the set $$Hom({\cal A}_i,Hom(\Omega,{\cal S}_i))$$

And of course the two displayed sets are naturally equivalent by elementary abstract nonsense.

So it seems to me that although (in my experience) Kuhn's results are usually formulated in terms of probability distributions, they are far more natural and straightforward in a random-variable formulation.

4. Quantum Games of Private Information. All of this comes to a head when we consider quantum games of private information (such as the famous Cleve/Hoyer/Toner/Watrous game). Here, there is no natural analogue of Kuhn's natural equivalence between games of mixed and behavioral strategies (and in fact it is a theorem --- Theorem 7.4 here in fact --- that there is no good way to fix this; i.e. no way to tweak Kuhn's definitions to get any sort of reasonable analogue to the classical result. Moreover, it's quite clear that the "random variable" formulation (generalized to include quantum observables as well as random variables) works well and the "probability distribution" formulation, no matter how you tweak it, does not.

5. Conclusion. As far as I've been able to determine, if you want a good general context in which mixed strategies, correlated strategies and quantum strategies all fit in to one general unified framework, you've got to work with random variables (generalized to quantum observables). On the other hand (again, in my experience, which might be limited), most economists prefer to work with probability distributions. I've therefore occasionally tried to write things up that way, but it's never worked out very well.