{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Normal Form Games\n",
"\n",
"Game theory is the study of interactive decision making. Consider the following situation:\n",
"\n",
"> Two friends must decide what movie to watch at the cinema. Alice would like to watch a sport movie and Bob would like to watch a comedy. Importantly they would both rather spend their evening together then apart.\n",
"\n",
"To represent this mathematically we will associate **utilities** to the 4 possible outcomes:\n",
"\n",
"1. Alice watches a sport movie, Bob watches a comedy: Alice receives a utility of $1$ and Bob a utility of $1$.\n",
"2. Alice watches a comedy, Bob watches a sport movice: Alice receives a utility of $0$ and Bob a utility of $0$.\n",
"3. Alice and Bob both watch a sport movie: Alice receives a utility of $3$ and Bob a utility of $2$.\n",
"4. Alice and Bob both watch a comedy: Alice receives a utility of $2$ and Bob a utility of $3$.\n",
"\n",
"This is referred to as the \"battle of the sexes\" and we will represent it using two matrices, $A$ will represent the utilities of Alice:\n",
"\n",
"$$\n",
"A = \n",
"\\begin{pmatrix}\n",
"3 & 1\\\\\n",
"0 & 2\n",
"\\end{pmatrix}\n",
"$$\n",
"\n",
"and matrix $B$ will represent the utilities of Bob:\n",
"\n",
"$$\n",
"B = \n",
"\\begin{pmatrix}\n",
"2 & 1\\\\\n",
"0 & 3\n",
"\\end{pmatrix}\n",
"$$\n",
"\n",
"We refer to **Alice as the row player** and **Bob as the column player**: \n",
"\n",
"- The row player chooses which row of the matrices the players will gain their utilities;\n",
"- The column player chooses which column of the matrices the player will gain their utilities.\n",
"\n",
"Thus if the row player (Alice) chooses the first row (this corresponds to a sport movie) and the column player (Bob) chooses the second column (this corresponds to a comedy):\n",
"\n",
"- The row player receives a utility of $A_{12}=1$\n",
"- The column player receives a utility of $B_{12}=1$\n",
"\n",
"This representation of the stategic interaction between Alice and Bob is called a **Normal Form Game**.\n",
"\n",
"---\n",
"\n",
"## Definition of Normal Form Game\n",
"\n",
"An \\\\(N\\\\) player normal form game consists of:\n",
"\n",
"- A finite set of $N$ players\n",
"- Strategy spaces for the players: $\\{S_1,S_2,S_3,\\dots,S_N\\}$;\n",
"- Payoff functions for the players: $u_i:S_1\\times S_2\\dots\\times S_N\\to\\mathbb{R}$\n",
"\n",
"---\n",
"\n",
"**In this course we will only consider the case of $N=2$.**\n",
"\n",
"For the battle of the sexes:\n",
"\n",
"- We have \\\\(N=2\\\\) players (Alice and Bob)\n",
"- The strategy spaces: $S_1=S_2=\\{\\text{comedy}, \\text{sport movie}\\}$ or equivalently $S_1=S_2=\\{1, 2\\}$\n",
"- The payoff functions mapping an element of $\\tilde s \\in S_1\\times S_2=\\{(1, 1), (1, 2), (2, 1), (2, 2)\\}$ to $\\mathbb{R}$:\n",
"\n",
" $$u_1(\\tilde s)=A_{\\tilde s},$$\n",
" \n",
" $$u_2(\\tilde s)=B_{\\tilde s}.$$\n",
" \n",
"---\n",
"\n",
"We can use Python to represent these games, we will use the `nashpy` library to do so and we start by building our two matrices:"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"import nash\n",
"A = [[3, 1], [0, 2]]\n",
"B = [[2, 1], [0, 3]]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We then create a `nash.Game` instance:"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Bi matrix game with payoff matrices:\n",
"\n",
"Row player:\n",
"[[3 1]\n",
" [0 2]]\n",
"\n",
"Column player:\n",
"[[2 1]\n",
" [0 3]]"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"battle_of_the_sexes = nash.Game(A, B)\n",
"battle_of_the_sexes"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In the next chapter we will start to see how to use that for further calculations.\n",
"\n",
"# Examples of other common games\n",
"\n",
"## Prisoners Dilemma\n",
"\n",
"> Assume two thieves have been caught by the police and separated for questioning. If both thieves cooperate and donâ€™t divulge any information they will each get a short sentence. If one defects he/she is offered a deal while the other thief will get a long sentence. If they both defect they both get a medium length sentence.\n",
"\n",
"This corresponds to:\n",
"\n",
"$$\n",
"A =\n",
"\\begin{pmatrix}\n",
" 3 & 0\\\\\n",
" 5 & 1\n",
"\\end{pmatrix}\\qquad\n",
"B =\n",
"\\begin{pmatrix}\n",
" 3 & 5\\\\\n",
" 0 & 1\n",
"\\end{pmatrix}\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Bi matrix game with payoff matrices:\n",
"\n",
"Row player:\n",
"[[3 0]\n",
" [5 1]]\n",
"\n",
"Column player:\n",
"[[3 5]\n",
" [0 1]]"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A = [[3, 0], [5, 1]]\n",
"B = [[3, 5], [0, 1]]\n",
"prisoners_dilemma = nash.Game(A, B)\n",
"prisoners_dilemma"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Hawk Dove game\n",
"\n",
"> Suppose two birds of prey must share a limited resource. The birds can act like a hawk or a dove. Hawks always fight over the resource to the point of exterminating a fellow hawk and/or take a majority of the resource from a dove. Two doves can share the resource.\n",
"\n",
"\n",
"\n",
"This corresponds to:\n",
"\n",
"$$\n",
"A =\n",
"\\begin{pmatrix}\n",
" 0 & 3\\\\\n",
" 1 & 2\n",
"\\end{pmatrix}\\qquad\n",
"B =\n",
"\\begin{pmatrix}\n",
" 0 & 1\\\\\n",
" 3 & 2\n",
"\\end{pmatrix}\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Bi matrix game with payoff matrices:\n",
"\n",
"Row player:\n",
"[[0 3]\n",
" [1 2]]\n",
"\n",
"Column player:\n",
"[[0 1]\n",
" [3 2]]"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A = [[0, 3], [1, 2]]\n",
"B = [[0, 1], [3, 2]]\n",
"hawk_dove = nash.Game(A, B)\n",
"hawk_dove"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Pigs\n",
"\n",
"> Consider two pigs. One dominant pig and one subservient pig. These pigs share a pen. There is a lever in the pen that delivers food but if either pig pushes the lever it will take them a little while to get to the food. If the dominant pig pushes the lever, the subservient pig has some time to eat most of the food before being pushed out of the way. If the subservient pig push the lever, the dominant pig will eat all the food. Finally if both pigs go to push the lever the subservient pig will be able to eat a third of the food.\n",
"\n",
"This corresponds to:\n",
"\n",
"$$\n",
"A =\n",
"\\begin{pmatrix}\n",
" 4 & 2\\\\\n",
" 6 & 0\n",
"\\end{pmatrix}\\qquad\n",
"B =\n",
"\\begin{pmatrix}\n",
" 2 & 3\\\\\n",
" -1 & 0\n",
"\\end{pmatrix}\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Bi matrix game with payoff matrices:\n",
"\n",
"Row player:\n",
"[[4 2]\n",
" [6 0]]\n",
"\n",
"Column player:\n",
"[[ 2 3]\n",
" [-1 0]]"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A = [[4, 2], [6, 0]]\n",
"B = [[2, 3], [-1, 0]]\n",
"pigs = nash.Game(A, B)\n",
"pigs"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Matching pennies\n",
"\n",
">Consider two players who can choose to display a coin either Heads facing up or Tails facing up. If both players show the same face then player 1 wins, if not then player 2 wins.\n",
"\n",
"This corresponds to:\n",
"\n",
"$$\n",
"A =\n",
"\\begin{pmatrix}\n",
" 1 & -1\\\\\n",
" -1 & 1\n",
"\\end{pmatrix}\\qquad\n",
"B =\n",
"\\begin{pmatrix}\n",
" -1 & 1\\\\\n",
" 1 & -1\n",
"\\end{pmatrix}\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Zero sum game with payoff matrices:\n",
"\n",
"Row player:\n",
"[[ 1 -1]\n",
" [-1 1]]\n",
"\n",
"Column player:\n",
"[[-1 1]\n",
" [ 1 -1]]"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A = [[1, -1], [-1, 1]]\n",
"B = [[-1, 1], [1, -1]]\n",
"matching_pennies = nash.Game(A, B)\n",
"matching_pennies"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As indicated by `nashpy`, this is a `Zero sum game`: \n",
"\n",
"$$\n",
"A + B = 0\n",
"$$\n",
"\n",
"---\n",
"\n",
"## Definition of a zero sum game\n",
"\n",
"A two player normal form game with payoff matrices $A, B$ is called **zero sum** iff:\n",
"\n",
"$$\n",
"A = -B\n",
"$$\n",
"\n",
"---\n",
"\n",
"To define a zero sum game using `nashpy` we can pass a single payoff matrix (it infers what the other will be):"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Zero sum game with payoff matrices:\n",
"\n",
"Row player:\n",
"[[ 1 -1]\n",
" [-1 1]]\n",
"\n",
"Column player:\n",
"[[-1 1]\n",
" [ 1 -1]]"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A = [[1, -1], [-1, 1]]\n",
"matching_pennies = nash.Game(A)\n",
"matching_pennies"
]
}
],
"metadata": {
"anaconda-cloud": {},
"kernelspec": {
"display_name": "Python [conda env:gt]",
"language": "python",
"name": "conda-env-gt-py"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.1"
}
},
"nbformat": 4,
"nbformat_minor": 2
}