# MA3662 Lecture 2

While the extensive form is a useful way to visualise the steps in a game, we will find it more convenient to work with the normal form instead. For this we will need some additional definitions.

### Definition 1.2

A **strategy** is a complete contingent plan for a player in a game. That is, a plan describing what
move the player should make in each of their possible information sets.

The set of possible strategies for a given player is called the **strategy set** for that player.

Given a player \(i\) we will let \(S_i\) denote the strategy set for that player, and \(s_i\in S_i\) will denote a particular strategy. A **strategy profile** is a vector of strategies, one for each player of the game, ie a vector
\[\underline{s}=(s_1,\ldots,s_n)\]
where \(s_i\in S_i\) for \(1\leq i\leq n\).

We will let \(S\) denote the set of all strategy profiles, so \[S=S_1\times S_2\times\cdots \times S_n.\]

For each player \(i\) we can define a function \(u_i:S\longrightarrow \mathbb R\) so that for each strategy profile \(\underline{s}\in S\) the value of \(u_i(\underline{s})\) represents the payoff to player \(i\) in that game. The function \(u_i\) is called the player’s **payoff function**.

### Definition 1.3

A game in **normal form** consists of a set \(\{1,\ldots,n\}\) of players, corresponding strategy sets \(S_1,S_2,\ldots,S_n\), and payoff functions \(u_1,u_2\ldots,u_n\).

If we just have two players then we may suppose that player \(1\) has \(p\) strategies which we can number from \(1\) to \(p\) and player \(2\) has \(q\) strategies which we can number from \(1\) to \(q\).

Then a strategy profile is just a pair \((x,y)\), and we can write the payoff function for each player as a matrix where the \((x,y)\)-entry is the value of the function for the given player for the strategy profile \((x,y)\).

Because each game can be described using a pair of matrices, such games are often called **bimatrix games**.

Here is an example of such a bimatrix game, where the payoff matrix for player 1 is \(A\) and for player 2 is \(B\).

Player 2 | |||||
---|---|---|---|---|---|

Strategy 1 | Strategy 2 | \(\cdots\) | Strategy \(q\) | ||

Strategy 1 | \((a_{11},b_{11})\) | \((a_{12},b_{12})\) | \(\cdots\) | \((a_{1q},b_{1q})\) | |

Player 2 |
Strategy 2 | \((a_{21},b_{21})\) | \((a_{22},b_{22})\) | \(\cdots\) | \((a_{2q},b_{2q})\) |

\(\vdots\) | |||||

Strategy \(p\) | \((a_{p1},b_{p1})\) | \((a_{p2},b_{p2})\) | \(\cdots\) | \((a_{pq},b_{pq})\) |

### Example 1.4

Construct the normal form for the game in Example 1.1.

Example completed by hand in the lecture

The normal form can be regarded as a model for situations where the players **simultaneously** and **independently** select strategies for an extensive form game. Such games are called **one-shot** or **static** games.

### Example 1.5: The Prisoners’ Dilemma

Example completed by hand in the lecture

### Example 1.6: Matching Pennies

Example completed by hand in the lecture

### Example 1.7: The Game of Chicken

Example completed by hand in the lecture

In some games you do not want to always pick the same strategy — for example in the rock, paper, scissors game. In such circumstance we will allow players to choose their strategies probabilistically.

### Definition 1.8

A **mixed** strategy for player \(i\) is a vector \(\underline{x}=(x_1,\ldots,x_{r_i})\) where \(r_i=|S_i|\) and \(x_j\geq 0\) for all \(1\leq j\leq r_i\) and
\[\sum_{j=1}^{r_i}x_j=1.\]

Here \(x_j\) represents the probability that player i chooses strategy \(j\).

The set \(\Delta S_i\) of mixed strategies for player \(i\) is defined by \[\Delta S_i=\{(x_1,\ldots,x_{r_i}): \ x_j\geq 0\ \text{for all $j$ and}\ \sum_{j=1}^{r_i}x_j=1\}.\] Thus a mixed strategy for player \(1\) is an element of \(\Delta S_1\) and a mixed strategy for player \(2\) is an element of \(\Delta S_2\).

If all of the \(x_j\) except for one are equal to \(0\) then we call this a **pure** strategy. These were the kinds of strategies we first considered.

If players use mixed strategies then we can only calculate the **expected** payoff from a game — ie the average payoff which they would receive if the game was repeated many times.

Suppose that player 1 has payoff matrix \(A\) and uses the mixed strategy \(\underline{x}\in\Delta S_1\), and player 2 has payoff matrix \(B\), and uses \(\underline{y}\in\Delta S_2\). We would like a formula for the expected payoff for each player.

The **expected payoff for player 1** is given by
\[ \begin{array}{rl}
\mathbb E_1(\underline{x},\underline{y})=&\sum_{i=1}^{p}\sum_{j=1}^{q}a_{ij}\mathbb P(\text{1 uses strategy $i$ and 2 uses strategy $j$})\\
=&\sum_{i=1}^{p}\sum_{j=1}^{q}a_{ij}\mathbb P(\text{1 uses strategy $i$})\mathbb P(\text{2 uses strategy $j$})\\
=&\sum_{i=1}^{p}\sum_{j=1}^{q}x_ia_{ij}y_j\\
=&\underline{x}A\underline{y}^T.
\end{array}\]
(Here we use the assumption that the players choose independently for the first step.)

Similarly player 2 has expected payoff \[\mathbb E_2(\underline{x},\underline{y})=\underline{x}B\underline{y}^T.\]

### Example 1.9

Suppose that in the prisoners’ dilemma the probability of player 1 confessing is 0.2 and of player 2 confessing is 0.4. Calculate the expected value for each player of the game.

Example completed by hand in the lecture