# Paper Rock Scissor
A = np.array([
[1,0,-1],
[0,-1,1],
[-1,1,0]
])
solution_x, solution_y = NashEquilibrium(A, -A).solve()3 Nash Equilibrium
3.1 Introduction
In game theory we consider two rational agents \(x\) and \(y\) that both want to maximize their score.
In discrete cases, \(x\) has \(m\) possible actions, \(y\) has n possible actions.
If \(x\) and \(y\) play simultaneously, we can considers the matrices \(A\) and \(B\) of dimension \((m,n)\).
\(A_{i,j}\) and \(B_{i, j}\) represents respectivily the score of \(x\) and \(y\) when \(x\) plays his \(i\)-th action and \(y\) his \(j\)-th action.
For convenience, we will also call player \(x\) as \(a\), and \(y\) as \(b\).
3.1.1 Definition Stochastic vector and Strategie
Let \(v\) a vector. If \(\sum v_i = 1\) and \(\forall i, v_i \geq 0\), \(v\) is a stochastic vector.
We call the strategy of the player \(x\) and \(y\), the stochastic vectors \(x\), \(y\) that represents the probabilty of choosing each actions. If only one coefficient of a strategy is none negative (ie. equal to one), we call it a pure strategy.
A best strategy \(\overline v\) is a strategy that maximise the gain of its player :
- \(\overline x \in \arg \max_x x A y^t\)
- \(\overline y \in \arg \max_x x B y^t\)
A best strategy is always of convex combination of pure strategies.
3.1.2 Definition Zero-sum game
Zero-sum game is defined by \(B = -A\), which means every gain for \(x\) is a loss of the same amplitude to \(y\), and the other way around.
3.1.3 Definition Nash equilibrium
A nash equilibrium is a couple \((x, y)\) of strategies, where \(x\) and \(y\) are both best strategies.
3.1.3.1 Theorem: A nash equilibrium always exists.
Remark: If we impose strategies to be pure, the theorem doesn’t hold. (eg: paper, rock, scissor)
3.2 Code
To find the nash equilibrium, create a NashEquilibrium object, and solve it.
solution_x, solution_y = NashEquilibrium(A, B).solve()3.2.1 Examples
x: [0.33333333 0.33333333 0.33333333]
y: [0.33333333 0.33333333 0.33333333]# Non-zero sum game
A = np.array([[1, 2], [3, 4]])
B = np.array([[4, 3], [2, 1]])
solution_x, solution_y = NashEquilibrium(A, B).solve()x: [0. 1.]
y: [1. 0.]A = np.array([[3, 2], [1, 4]])
B = np.array([[2, 1], [3, 2]])
solution_x, solution_y = NashEquilibrium(A, B).solve()x: [1. 0.]
y: [1. 0.]3.3 Modelization
We solve this problem using pulp with mixted linear programming (linear + discrete).
3.3.1 Variables :
| Variable | Player a | Player b | Domain |
|---|---|---|---|
| Strategies | \(x_{a1}, \dots, x_{am}\) | \(x_{b1}, \dots, x_{bn}\) | \([0,1]\) |
| Strategies supports | \(s_{a1}, \dots s_{am}\) | \(s_{b1}, \dots, s_{bn}\) | \(\{0, 1\}\) |
| Regrets | \(r_{a1}, \dots, r_{am}\) | \(r_{b1}, \dots r_{bn}\) | \([0, M]\) |
| Potential Gain | potential_gain_a | potential_gain_b | \([LG, HG]\) |
| Max Gain (scalar) | max_gain_a | max_gain_b | \([LG, HG]\) |
M represents respectively the max regret for \(a\) and \(b\).
\(M_a := \max A_{ij} - \min A_{ij}\) \(M_b := \max B_{ij} - \min B_{ij}\)
HG represents respectively the highest gain for \(a\) and \(b\).
\(HG_a := \max A_{ij}\) \(HG_b := \max B_{ij}\)
LG represents respectively the lowest gain for \(a\) and \(b\).
\(LG_a := \min A_{ij}\) \(LG_b := \min B_{ij}\)
3.3.2 Constraints
3.3.2.1 [Eq Constraint] Stochastic vectors
\(\sum x_{ai} = 1\)
\(\sum x_{bi} = 1\)
3.3.2.2 [Eq Constraint] Potential gain
potential_gain_a \(= A y^t\)
potential_gain_b \(= x B\)
3.3.2.3 [Constraint] Max gain
\(\forall i\) max_gain_a \(\geq\) potential_gain_a\(_i\)
\(\forall j\) max_gain_b \(\geq\) potential_gain_b\(_j\)
3.3.2.4 [Eq Constraint] Risk
\(\vec{r_a} =\) potential_gain_a \(-\) max_gain_a
\(\vec{r_b} =\) potential_gain_b \(-\) max_gain_b
3.3.2.5 [Constraint] Best strategy constraint
\(\forall i :\quad\) \(x_{ai} \leq s_{ai} \qquad\) \(r_{ai} \leq (1 - s_{ai}) \times M_a\)
\(\forall j :\quad\) \(x_{bj} \leq s_{bi} \qquad\) \(r_{bj} \leq (1 - s_{bj}) \times M_b\)
3.3.3 Objective function :
Minimize : \(\sum r_{ai} + \sum r_{bi}\)