Friday, 21 February 2014

Best responses to mixed strategies in class

On Monday my Game Theory class and I took a look the connection between extensive form games and normal form games (leading to subgame perfection) which correspond to these two chapters of my course: C7 and C8 but before starting that we took another look at best responses to mixed strategies (this Chapter of my course).

We have been using this game quite a bit in class:

\[\begin{pmatrix}
(2,-2) & (-2,2)\\
(-1,1) & (1,-1)
\end{pmatrix}\]

We played it before and I blogged about it here. This is a slight modification of the matching pennies game where the 1st strategy corresponds to playing Heads (\(H\)) and the second to playing Tails (\(T\))

If player 1 (the row player) is playing a mixed strategy \(\sigma_1=(x, 1-x)\) then the utility to player 2 when playing player 2 plays $H$ (the first column) can be written as:

\[
u_2(\sigma_1,H)=-2x+1-x=1-3x
\]

and when player 2 plays $T$:

\[
u_2(\sigma_1,T)=2x-1+x=3x-1
\]

We can plot these two utilities here (using +Sage Mathematical Software System):

It is immediate to note that when \(x < 1/3\) player 2 should play $T$. In fact we can write down player 2's best response \(s_2^*\) to any \(\sigma_1\):

\[
s_2^*=\begin{cases}
H,&x < 1/3\\
T,&x > 1/3\\
\text{indifferent},&
\end{cases}
\]

Using all this I played the following game in class:


  • I handed out sheets asking students to play against 3 separate mixed strategies \(\sigma_1\in\{(.2,.8),(.9,.1),(1/3,2/3)\}\). I will refer to these 3 rounds as R1, R2 and R3;
  • Students (acting as player 2) filled in their strategies;
  • I then used the following interact to sample mixed strategies according to \(\sigma_1\):

I changed the value of \(x\) as required.

Here are the three row strategies that were sampled:


  • R1: TTTTTH 
  • R2: HHHTHH 
  • R3: TTHTTT 


This is obviously not giving the exact proportions dictated by the mixed strategy \(\sigma_1\) but that's also kind of the point. By round, here are the results.

R1

Here's a plot of the mixed strategy that was played by the entire class during round 1:


This corresponds to \(\sigma_2=(.70,.30)\), so most students seemed willing to 'trust the theory' that one should play $H$ against this mixed strategy.

4 students scored the highest score (\(7\)) and here's the strategy they all played: \(HHHHHT\), in essence they got lucky and maxed out what they could have had. If they had played the theoretical best response (to only play $H$) they would have scored: 3.

The expected value of playing the theoretical best response (always pick \(H\) against this mixed strategy is: \(6(1-3\times.2)=2.4\) (recall that \(\sigma_1=(.2,.8)\) for this round).

The mean score for this round was 1.4 and here's a distribution of the scores:



47 students who 'won' ie scored a positive score (this is a zero zum game) played \(\sigma_2=(.83,.17)\). 18 'lost' (scored a negative score) playing \(.37,.63\).

It's nice to see that there was a large amount of students who did in fact score 3.

R2

Here's a plot of the mixed strategy that was played by the entire class during round 2:


This corresponds to \(\sigma_2=(.12,.88)\), which is again pretty close to the theoretical best response.

2 students scored the highest score: 11. They once again lucked out and played the perfect response: \(TTTHTT\). If they had played the theoretical best response they would have scored 9.

The expected value of playing the theoretical best response (always pick \(T\) against this mixed strategy is: \(6(3\times.9-1)=10.2\) (recall that \(\sigma_1=(.9,.1)\) for this round).

The mean score for this round was  6.9 and here's a distribution of the scores:


60 students 'won' ie scored a positive score (this is a zero zum game) playing \(\sigma_2=(.07,.93)\). 5 'lost' (scored a negative score) playing \(.77,.23\).

R3

The third round had the students playing against a mixed strategy for which they should have been indifferent. Here's how they played:


This corresponded to \(\sigma_2=(0.62,.38)\).

There were 10 winners for this game and they scored 10 (quite a few strategy profile gave this score so I won't list them but they mainly took advantage of the fact that mostly $T$ was sampled). (The theoretical utility is in fact 0 as you can see with one of the plots above).

The mean score for this round was was .4 (which is quite close to the theoretical value of 0). Here's the distribution of the scores:




28 scored positively playing \(\sigma_2=(.64,.36)\) and 37 scored negatively playing \(\sigma_2=(.77,.23)\).

What's nice to see here is that this 3rd round is a bit more random, with an almost (stretching the definition of the word almost) equal distribution between the number of students who won and lost.

Here's a distribution of the overall scores:

The overall winner of the game (who scored the most over the 3 rounds) was Becky who played:

  • R1: \(TTHHHH\)
  • R2: \(TTTTTT\)
  • R3: \(HHTHTH\)

For a cumulative score of: 21

This was good fun to analyse and was hopefully useful to my students to see what is meant by best responses to mixed strategies. It was particularly cool to see an 'indifferent' (again stretching the definition of the word indifferent) response to the third round.

(Like with everything for this course you can find the data, analysis scripts and everything else at this github repo)