数学建模

 

模型知识点

优化模型-博弈论-计算策略的效用(en)

 

Wang Haihua

🚅 🚋😜 🚑 🚔

Calculating utilities of strategies

Player strategies

---

Definition of mixed strategies

Video

A mixed strategy for a player with strategy set $S$ is denoted by $\sigma \in [0,1]_{\mathbb{R}}^{|S|}$ and corresponds to a probability distribution over the pure strategies of player $i$. So:

$$ \sum_{i=1}^{|S|}\sigma_i = 1 $$

---

The expected score of a player can then be calculated as a measure over the probability distributions.

---

Calculating utilities

Considering a game $(A, B)\in\mathbb{{R^{m \times n}}^2}$, if $\sigma_r$ and $\sigma_c$ are the mixed strategies for the row/column player (respectively). The utility to the row player is:

$$ u_r(\sigma_r, \sigma_c) = \sum_{i=1}^m\sum_{j=1}^nA_{ij}{\sigma_r}_i{\sigma_c}_j $$

and the utility to the column player is:

$$ u_c(\sigma_r, \sigma_c) = \sum_{i=1}^m\sum_{j=1}^nB_{ij}{\sigma_r}_i{\sigma_c}_j $$

This comes from:

• The probability of being in a given cell of $A$ or $B$: ${\sigma_r}_i{\sigma_c}_j$
• The value of the particular cell: $A_{ij}$ or $B_{ij}$

---

As an example consider the matching pennies game:

$$ A = \begin{pmatrix} 1 & -1\\ -1 & 1 \end{pmatrix}\qquad B = \begin{pmatrix} -1 & 1\\ 1 & -1 \end{pmatrix} $$

with the following mixed strategies:

$$ \sigma_r = (.2, .8) \qquad \sigma_c = (.6, .4) $$

We have:

$$ u_r(\sigma_r, \sigma_c) = 0.2 \times 0.6 \times 1 + 0.2 \times 0.4 \times (-1) + 0.8 \times 0.6 \times (-1) + 0.8 \times 0.4 \times 1=-0.12, $$$$ u_c(\sigma_r, \sigma_c) = 0.2 \times 0.6 \times (-1) + 0.2 \times 0.4 \times 1 + 0.8 \times 0.6 \times 1 + 0.8 \times 0.4 \times (-1)=0.12. $$

---

Linear algebraic calculation

Video

Note that we can rearrange the expressions for the utilities:

$$ u_r(\sigma_r, \sigma_c) = \sum_{i=1}^m{\sigma_r}_i\sum_{j=1}^nA_{ij}{\sigma_c}_j $$$$ u_c(\sigma_r, \sigma_c) = \sum_{i=1}^m{\sigma_r}_i\sum_{j=1}^nB_{ij}{\sigma_c}_j $$

in turn this corresponds to the matrix vector product:

$$ u_r(\sigma_r, \sigma_c) = {\sigma_r}A\sigma_c^T $$$$ u_c(\sigma_r, \sigma_c) = {\sigma_r}B\sigma_c^T $$

We can use numpy to verify this calculation:

import numpy as np
A = np.array([[1, -1], [-1, 1]])
B = np.array([[-1, 1], [1, -1]])
sigma_r = np.array([.2, .8])
sigma_c = np.array([.6, .4])
np.dot(sigma_r, np.dot(A, sigma_c)), np.dot(sigma_r, np.dot(B, sigma_c))

(-0.11999999999999998, 0.11999999999999998)

Finally we can also directly calculate this using a nashpy game:

import nashpy as nash
matching_pennies = nash.Game(A, B)
matching_pennies[sigma_r, sigma_c]

array([-0.12,  0.12])