This week’s Game Theory is dedicated to Mixed-Strategy Nash Equilibrium.

Mixed strategy, different from pure strategy, means that players can choose an action according to a specific probability distribution (among all possible actions). The following concepts and definitions all derives from this idea:

Strategy $s_i$
: any probability distribution over the actions $A_i$ for agent i.

Pure strategy
: only one action is played with positive probability.

Mixed strategy
: more than one action is played with positive probability.

Support (of mixed strategy)
: all the actions

We denote $s_i \in S_i$ as $S_i$ is the set of all strategies for user i. All strategies $S = S_1 \times S_2 \times \ldots \times S_n$

Expected Utility is defined as follows:
$$$$u_{i}(s) = \sum_{a \in A} u_{i}(a) P(a|s) \ P(a|s) = \prod_{j \in N} s_j(a_j)$$$$
In the equations above, a means a possible action profile from A. $a_j$ does not mean each of the action but the player j’s corresponding action in the corresponding profile.

Best response

$s_{i}^{} \in BR(s_{-i}) iff \forall s_i \in S_i u_{i}(s_{i}^{}, s_{-i}) \ge u_{i}(s_i, s_{-i})$

Nash Equilibrium

$s=\ \mbox( is a Nash Equilibrium iff }\forall i, s_i \in BR(s_{-i})$

Theorem
: Every finite game has a Nash Equilibrium. (While comparing to pure strategy games!)

It is often very hard to compute the Nash Equilibrium of a game, but in simple cases, in which we know the support, we can get the Nash Equilibrium by being acknowledged that a player will act indifferently facing a mixed strategy.

2014-10-18