Strategies¶
Motivating example: Strategy for Rock Paper Scissors¶
The game of Rock Paper Scissors is a common parlour game between two players who pick 1 of 3 options simultaneously:
Rock which beats Scissors;
Paper which beats Rock;
Scissors which beats Paper
Thus, this corresponds to a Normal Form Game with:
Two players (\(N=2\)).
The action sets are: \(\mathcal{A}_1=\mathcal{A}_2=\{\text{Rock}, \text{Paper}, \text{Scissors}\}\)
The payoff functions are given by the matrices \(A, B\) where the first row or column corresponds to \(\text{Rock}\), the second to \(\text{Paper}\) and the third to \(\text{Scissors}\).
If we consider two players, assume the row player always chooses \(\text{Paper}\) and the column player randomly chooses from \(\text{Rock}\) and \(\text{Paper}\) (with equal probability) what is the expected outcome of any one game between them?
The expected score of the row player will be: \(-1 \times 1/2 + 0 \times 1/2 = -1/2\).
The expected score of the column player will be: \(1 \times 1/2 + 0 \times 1/2 = 1/2\).
In Game theoretic terms, the behaviours described above are referred to as strategies. Strategies map information to actions. In this particular case, the only available information is the game itself and the actions are \(\mathcal{A}_1=\mathcal{A}_2\).
Definition of a strategy in a normal form game¶
A strategy for a player with action set \(\mathcal{A}\) is a probability distribution over elements of \(\mathcal{A}\).
Typically a strategy is denoted by \(\sigma \in [0, 1]^{|\mathcal{A}|}_{\mathbb{R}}\) so that:
Question
For Rock Papoer Scissors:
What is the strategy \(\sigma_r\) that corresponds to the row player’s behaviour of always choosing \(\text{Paper}\)?
What is the strategy \(\sigma_c\) that corresponds to the column player’s behaviour of always randomly choosing between \(\text{Rock}\) and \(\text{Paper}\)?
Answer
\(\sigma_r = (0, 1, 0)\)
\(\sigma_c = (1 / 2, 1 / 2, 0)\)
Definition of support of a strategy¶
For a given strategy \(\sigma\), the support of \(\sigma\): \(\mathcal{S}(\sigma)\) is the set of actions \(i\in\mathcal{A}\) for which \(\sigma_i > 0\).
Question
For the following strategies \(\sigma\) obtain \(\mathcal{S}(\sigma)\):
\(\sigma = (1, 0, 0)\)
\(\sigma = (1/3, 1/3, 1/3)\)
\(\sigma = (2/5, 0, 3/5)\)
Answer
\(\mathcal{S}(\sigma) = \{1\}\)
\(\mathcal{S}(\sigma) = \{1, 2, 3\}\)
\(\mathcal{S}(\sigma) = \{1, 3\}\)
Note here that as no specific action sets are given the integers are used.
Strategy spaces for Normal form Games¶
Given a set of actions \(\mathcal{A}\) the space of all strategies \(\mathcal{S}\) is defined as:
Calculation of expected utilities¶
Considering a game \((A, B) \in \mathbb{R} ^{(m\times n) ^ 2}\), if \(\sigma_r\) and \(\sigma_c\) are the strategies for the row/column player, the expected utilities are:
For the row player: \(u_{r}(\sigma_r, \sigma_c) = \sum_{i=1}^m\sum_{j=1}^nA_{ij}\sigma_{r_i}\sigma_{c_j}\)
For the column player: \(u_{c}(\sigma_r, \sigma_c) = \sum_{i=1}^m\sum_{j=1}^nB_{ij}\sigma_{r_i}\sigma_{c_j}\)
This corresponds to taking the expectation over the probability distributions \(\sigma_r\) and \(\sigma_c\).
Question
For the Rock Papoer Scissors:
What are the expected utilities to both players if \(\sigma_r=(1/3, 0, 2/3)\) and \(\sigma_c=(1/3, 1/3, 1/3)\).
Answer
Linear algebraic calculation of expected utilities¶
Given a game \((A, B) \in \mathbb{R} ^{(m\times n) ^ 2}\), considering \(\sigma_r\) and \(\sigma_c\) as vectors in \(\mathbb{R}^m\) and \(\mathbb{R}^n\). The expected utilities can be written as the matrix vector product:
For the row player: \(u_{r}(\sigma_r, \sigma_c) = \sigma_r A \sigma_c^T\)
For the column player: \(u_{c}(\sigma_r, \sigma_c) = \sigma_r B \sigma_c^T\)
Question
For Rock Paper Scissors:
Calculate the expected utilities to both players if \(\sigma_r=(1/3, 0, 2/3)\) and \(\sigma_c=(1/3, 1/3, 1/3)\) using a linear algebraic approach.
Answer
Using Nashpy¶
See Calculate utilities for guidance of how to use Nashpy to calculate utilities.