A lengthy set of support enumeration calculations and a Python speed run
On Friday we went over the support enumeration algorithm and on Monday I gave a
Python refresher:
- A recording of Friday’s class on the support enumeration algorithm is available here.
- A recording of Monday’s class going over the basics of Python is available here.
Support enumeration algorithm
We applied the algorithm described
here
to the zero sum game defined by:
\[A = \begin{pmatrix}
0 & -1 & 1\\
1 & 0 & -1\\
-1 & 1 & 0
\end{pmatrix}\]
The basic idea behind the algorithm is as follows:
- Assume what actions are played by both players (this is called the supports
of the strategies
- Identify the strategies that ensure that indeed all actions of the chosen
supports will be played: this only happens if all actions in the support
itself have the same expected utility.
- Check that there is no better outside of the supports chosen.
We considered the supports of size 1: there are no single pairs of actions that
are pairs of best responses to each other.
We considered 2 pairs of supports of size 2:
- \(I = \{R, P\}\) (the row player only using Rock and Paper) and \(J=\{R, P\}\)
(the column player also only using Rock and Paper). This lead to a
contradiction (at step 2 of the above general idea) where there would be no
probabilities that work.
- \(I = \{R, P\}\) (the row player only using Rock and Paper) and \(J=\{P, S\}\)
(the column player only using Paper and Scissors). This lead to a contradiction (at step 3
of the above general idea) where there was a best response outside of the support chosen.
That is 2 of the 9 possible pairs of supports of size 2.
Python refresher
You can find the notebook I used here.
I worked through the how to sections of these two chapters of Python for Mathematics: