# Prisoners dilemma - exercises

1. Give the general definition for a Prisoners dilemma.

   Bookwork: https://vknight.org/gt/chapters/09/#Prisoners-Dilemma

2. Justify if the following games are Prisoners dilemmas or not:
   1. $
   A =
   \begin{pmatrix}
   3 & 0\\
   5 & 1
   \end{pmatrix}
   \qquad
   B =
   \begin{pmatrix}
   3 & 5\\
   0 & 1
   \end{pmatrix}
   $ 
   
      This is a Prisoners Dilemma: $(R, S, T, P) = (3, 1, 5, 0)$.
   
   2. $
   A =
   \begin{pmatrix}
   1 & -1\\
   2 & 0
   \end{pmatrix}
   \qquad
   B =
   \begin{pmatrix}
   1 & 2\\
   -1 & 0
   \end{pmatrix}
   $ 
   
      This is a Prisoners Dilemma: $(R, S, T, P) = (1, -1, 2, 0)$: $2>1>0>-1$ and $2\times 1 > 2 - 1$.
    
   3. $
   A =
   \begin{pmatrix}
   1 & -1\\
   2 & 0
   \end{pmatrix}
   \qquad
   B =
   \begin{pmatrix}
   3 & 5\\
   0 & 1
   \end{pmatrix}
   $ 
   
      This is not a Prisoner's Dilemma $A \ne B ^ T$
   
   4. $
   A =
   \begin{pmatrix}
   6 & 0\\
   12 & 1
   \end{pmatrix}
   \qquad
   B =
   \begin{pmatrix}
   6 & 12\\
   0 & 0
   \end{pmatrix}
   $ 
   
      This is not a Prisoner's Dilemma $A \ne B ^ T$
   
3. Obtain the Markov chain representation for a match between reactive strategies with the following vectors:

   Bookwork: this is a substitution exercise using https://vknight.org/gt/chapters/09/#Markov-chain-representation-of-a-Match-between-two-reactive-strategies 

   1. $p=(1/2, 1/2)\qquad q=(1/2, 1/2)$
   
      $$M = \begin{pmatrix}
      1/4&1/4&1/4&1/4\\
      1/4&1/4&1/4&1/4\\
      1/4&1/4&1/4&1/4\\
      1/4&1/4&1/4&1/4
      \end{pmatrix}$$
   2. $p=(1/4, 1/2)\qquad q=(1/2, 1/4)$
   
      $$M = \begin{pmatrix}
      1/8&1/8&3/8&3/8\\
      1/4&1/4&1/4&1/4\\
      1/16&3/16&3/16&9/16\\
      1/8&3/8&1/8&3/8
      \end{pmatrix}$$   
   
   3. $p=(1/3, 1/3)\qquad q=(2/3, 1/4)$
   
      $$M = \begin{pmatrix}
      2/9 & 1/9 & 4/9 & 2/9\\
      2/9 & 1/9 & 4/9 & 2/9\\
      1/12 & 1/4 & 1/6 & 1/2\\
      1/12 & 1/4 & 1/6 & 1/2
      \end{pmatrix}$$   
   
4. Obtain the utilities for both players for the vectors of question 3.

   Bookwork: this is a substitution exercise using https://vknight.org/gt/chapters/09/#Theorem:-steady-state-probabilities-for-match-between-reactive-players
   
   1. $p=(1/2, 1/2)\qquad q=(1/2, 1/2)$ gives utilities: $(9/4, 9/4)$
   2. $p=(1/4, 1/2)\qquad q=(1/2, 1/4)$ gives utilities: $(536/289, 621/289)$
   3. $p=(1/3, 1/3)\qquad q=(2/3, 1/4)$ gives utilities: $(113/54, 49/27)$
   
Here is some python code that also carries out these calculations:


```python
import numpy as np
import itertools

def make_matrix(p, q):
    """
    Code to obtain Markov chain representation of match between two reactive players.
    """
    M = [[ele[0] * ele[1] for ele in itertools.product([player, 1 - player], 
                                                       [opponent, 1 - opponent])]
         for opponent in q for player in p]
    return np.array(M)

def theoretic_steady_state(p, q):
    r_1 = p[0] - p[1]
    r_2 = q[0] - q[1]
    s_1 = (q[1] * r_1 + p[1]) / (1 - r_1 * r_2)
    s_2 = (p[1] * r_2 + q[1]) / (1 - r_1 * r_2)
    return np.array([s_1 * s_2, s_1 * (1 - s_2), (1 - s_1) * s_2, (1 - s_1) * (1 - s_2)])

def theoretic_utility(p, q, rstp=np.array([3, 0, 5, 1])):
    pi = theoretic_steady_state(p, q)
    return np.dot(pi, rstp)
```


```python
import sympy as sym
for p, q in [([sym.S(1) / 2, sym.S(1) / 2], [sym.S(1) / 2, sym.S(1) / 2]),
             ([sym.S(1) / 4, sym.S(1) / 2], [sym.S(1) / 2, sym.S(1) / 4]),
             ([sym.S(1) / 3, sym.S(1) / 3], [sym.S(2) / 3, sym.S(1) / 4])]:
    print("=====")
    print(p, q)
    print("gives:")
    print(make_matrix(p, q))
    print("With utility:", theoretic_utility(p, q), theoretic_utility(q, p))
```

    =====
    [1/2, 1/2] [1/2, 1/2]
    gives:
    [[1/4 1/4 1/4 1/4]
     [1/4 1/4 1/4 1/4]
     [1/4 1/4 1/4 1/4]
     [1/4 1/4 1/4 1/4]]
    With utility: 9/4 9/4
    =====
    [1/4, 1/2] [1/2, 1/4]
    gives:
    [[1/8 1/8 3/8 3/8]
     [1/4 1/4 1/4 1/4]
     [1/16 3/16 3/16 9/16]
     [1/8 3/8 1/8 3/8]]
    With utility: 536/289 621/289
    =====
    [1/3, 1/3] [2/3, 1/4]
    gives:
    [[2/9 1/9 4/9 2/9]
     [2/9 1/9 4/9 2/9]
     [1/12 1/4 1/6 1/2]
     [1/12 1/4 1/6 1/2]]
    With utility: 113/54 49/27


`5`. Assuming $p=(x, 1/2)$, find the optimal $x$ against the following players:

   A part of this question involves bookwork: this is a substitution exercise using https://vknight.org/gt/chapters/09/#Theorem:-steady-state-probabilities-for-match-between-reactive-players. This is a substitution exercise to obtain a formula for the utility of $p$ as a function of $x$.

   1. $q=(1, 0)$
   
      $$u(x)=\frac{(-10x + 4(x - 1)^2 + 13)}{(2x - 3)^2}$$
      
      The derivative of this function is given by:
      
      $$
      \frac{2(6x - 7)}{(2x - 3)^3}
      $$
      
      This derivative has zero for $x=7/6$ which is $>1$. Thus the utility is monotic increasing over the interval $[0, 1]$. We have (by substitution):
      
      $$u(0)=17/9\qquad u(1)=3$$
      
      Thus $u(x)$ is an increasing function so the optimal value of $x$ is $1$.
      
      Against a player that is unforgiving (reacts to defection with defection), given that our player will play randomly against a defection it is better to always cooperate.
      
   2. $q=(1/2, 1/2)$
   
      $$u(x)=-3x/4+21/8$$
      
      This is a decreasing function so the optimal value of $x$ is $0$.
      
      Against a random player (who takes no notice of what we do) it is better to defect.
      
Below is some code to verify this calculations.


```python
x = sym.Symbol("x")
for q in [(sym.S(1), sym.S(0)), (sym.S(1) / 2, sym.S(1) / 2)]:
    utility = theoretic_utility((x, sym.S(1) / 2), q)
    print(utility.simplify(), utility.subs({x: 0}), utility.subs({x: 1}), sym.diff(utility, x).simplify(), sym.solveset(sym.diff(utility, x), x))
```

    (-10*x + 4*(x - 1)**2 + 13)/(2*x - 3)**2 17/9 3 2*(6*x - 7)/(2*x - 3)**3 {7/6}
    -3*x/4 + 21/8 21/8 15/8 -3/4 EmptySet()


3be9f23f7eaec409dff16ae3c7c2a6e7d4763e88
ipynb
Jupyter Notebook
nbs/solutions/09-Prisoners-dilemma.ipynb
prokolyvakis/gt
e679e5d54d9a98583ad4981411ce505cea31f028
MIT
2017-05-25T08:10:40.000Z
2021-12-07T21:01:51.000Z
nbs/solutions/09-Prisoners-dilemma.ipynb
prokolyvakis/gt
e679e5d54d9a98583ad4981411ce505cea31f028
MIT
2017-05-23T16:12:03.000Z
2022-03-30T13:42:25.000Z
nbs/solutions/09-Prisoners-dilemma.ipynb
prokolyvakis/gt
e679e5d54d9a98583ad4981411ce505cea31f028
MIT
2017-06-19T11:04:06.000Z
2020-08-30T11:28:00.000Z
Qwen/Qwen-72B
1. YES
2. YES