✍🏼 🤜🏾 🌴 Zero-sum games and Karush-Kun-Takker conditions 💴 🥩 👰🏽

In this article, I deal with the problem of finding balanced mixed strategies using antagonistic games as an example.

Let there be two players, A and B, who repeatedly play a certain game. Each player in each draw adheres to one of several strategies - for simplicity, we assume that the number of strategies for both players coincides and equals $n$ . When choosing $i$ strategy first player and $j$ strategy of the second player, the first player will receive a win $a_{ij}$ and the second player will get the same loss - this is how the antagonistic games are arranged. These wins can be written as a square matrix $A$ :

A = ‖ a_{i j} ‖, 1 \leq i, j \leq n

$A = \|a_{ij}\|, 1 \leq i, j \leq n$

Players play the game repeatedly and can use different strategies in different sweepstakes. A mixed strategy is a vector of probabilities associated with each of the player ’s pure strategies. Each player chooses one of the strategies in the next draw in accordance with the probability defined for her by his mixed strategy. If denoted by $p$ and $q$ mixed strategies of players, then the mathematical expectation of winning the first player will be

f (p, q) = (A p, q) = \sum_{i = 1}^{n} \sum_{j = 1}^{n} p_{i} q_{j} a_{i j}

$f(p,q) = (Ap, q) = \sum_{i=1}^{n}{\sum_{j=1}^{n}{p_i q_j a_{ij}}}$

A pair of mixed strategies is called equilibrium if no player can increase their winnings by changing their strategy. In other words, for any other pair of strategies $p'$ , $q'$ performed:

(A p^{'}, q) \leq (A p, q) \leq (A p, q^{'})

$(Ap', q) \leq (Ap, q) \leq (Ap, q')$

Here we are now looking for such equilibria.

1. Equilibrium

So, a pair of mixed strategies forms an equilibrium if changing a mixed strategy for the first player cannot increase his winnings, and changing a mixed strategy for the second player cannot reduce his loss.

For example, consider such a payoff matrix:

A = (\begin{matrix} 2 & 3 \\ 4 & 1 \end{matrix})

$A = \begin{pmatrix} 2& 3 \\ 4& 1 \end{pmatrix}$

. , , . : (2 3). , , : (4 1). , , : (1 4). , . , , .

. , $(1/2, 1/2)$ , $(1/2, 1/2)$ . 2.5.

, , , . , .

$p$ $q$ , :

p = \arg max_{p^{'}} (A p^{'}, q), q = \arg min_{q^{'}} (A p, q^{'})

$p = \arg \max_{p'}{(Ap', q)}, q = \arg \min_{q'}{(Ap, q')}$

p_{i} \geq 0, q_{j} \geq 0, 1 \leq i, j \leq n

$p_i \geq 0, q_j \geq 0, 1 \leq i,j \leq n$

\sum_{i = 1}^{n} p_{i} = \sum_{j = 1}^{n} q_{j} = 1

$\sum_{i=1}^{n}{p_i} = \sum_{j=1}^{n}{q_j} = 1$

, . - : , .

, , :

A = (\begin{matrix} 3 & 1 & 2 \\ - 2 & 3 & 1 \\ - 2 & - 2 & 3 \end{matrix})

$A = \begin{pmatrix} 3& 1& 2 \\ -2& 3& 1 \\ -2& -2& 3 \end{pmatrix}$

, ,

\sum_{i = 1}^{n} p_{i} = \sum_{j = 1}^{n} q_{j} = 1

$\sum_{i=1}^{n}{p_i}=\sum_{j=1}^{n}{q_j}=1$

p = (0.74, 0, 29, - 0.03)

$p=(0.74, 0,29, -0.03)$

- , . - --.

2. --

-, , 1951- , , 1939- .

m i n_{x \in R} f (x)

$min_{x \in \mathbb{R}}f(x)$

, :

h_{i} (x) \leq 0, 1 \leq i \leq m

$h_i(x) \leq 0, 1 \leq i \leq m$

l_{j} (x) = 0, 1 \leq j \leq r

$l_j(x) = 0, 1 \leq j \leq r$

, , , --:

\frac{\partial}{\partial x} (f (x) - \sum_{i = 1}^{m} λ_{i} h_{i} (x) - \sum_{j = 1}^{r} μ_{j} l_{j} (x)) = 0

$\frac{\partial}{\partial{x}}\Big({f(x)} - \sum_{i=1}^{m}{\lambda_i h_i(x)} - \sum_{j=1}^{r}{\mu_j l_j(x)}\Big) = 0$

λ_{i} \cdot h_{i} (x) = 0, 1 \leq i \leq m

$\lambda_i \cdot h_i(x) = 0, 1 \leq i \leq m$

λ_{i} \geq 0, 1 \leq i \leq m

$\lambda_i \ge 0, 1 \leq i \leq m$

h_{i} (x) \leq 0, 1 \leq i \leq m

$h_i(x) \leq 0, 1 \leq i \leq m$

l_{j} (x) = 0, 1 \leq j \leq r

$l_j(x) = 0, 1 \leq j \leq r$

; .

— . :

$h_i(x) = 0$ ,
- $h_i(x) < 0$ , $\lambda_i=0$ .

, , , . , :

2 $\lambda_i$ ;
2, 1 5 ;
, 3 4;
2 ;
, .

, . .

3.

. , , « ».

$p$ :

$-(Ap, q) \rightarrow \min$
$-p_i \le 0, 1 \leq i \leq n$
$\sum_{j=1}^{n}{p_i} - 1 = 0$

$q$ :

$(Ap, q) \rightarrow \min$
$-q_j \le 0, 1 \leq j \leq n$
$\sum_{j=1}^{n}{q_j} - 1 = 0$

L_{1} (p) = - (A p, q) + \sum_{i = 1}^{n} α_{i} p_{i} - β (\sum_{i = 1}^{n} p_{i} - 1)

$L_1(p) = -(Ap, q) + \sum_{i=1}^{n}{\alpha_i p_i} - \beta \Big(\sum_{i=1}^{n}p_i - 1\Big)$

L_{2} (q) = (A p, q) + \sum_{j = 1}^{n} λ_{j} q_{j} - μ (\sum_{j = 1}^{n} q_{j} - 1)

$L_2(q) = (Ap, q) + \sum_{j=1}^{n}{\lambda_j q_j} - \mu \Big(\sum_{j=1}^{n}q_j - 1\Big)$

\frac{\partial L_{1} (p)}{p_{i}} = - \sum_{j = 1}^{n} a_{i j} q_{j} + α_{i} - β

$\frac{\partial L_1(p)}{p_i} = -\sum_{j=1}^{n}{a_{ij}q_j} + \alpha_i - \beta$

\frac{\partial L_{2} (q)}{q_{j}} = \sum_{i = 1}^{n} a_{i j} p_{i} + λ_{j} - μ

$\frac{\partial L_2(q)}{q_j} = \sum_{i=1}^{n}{a_{ij}p_i} + \lambda_j - \mu$

--, . $p$ :

$\alpha_i \cdot p_i = 0, 1 \leq i \leq n$
$\alpha_i \ge 0, 1 \leq i \leq n$
$\sum_{i=1}^{n}{p_i} = 1$
$p_i \ge 0, 1 \leq i \leq n$

$q$ :

$\lambda_j \cdot q_j = 0, 1 \leq j \leq n$
$\lambda_j \ge 0, 1 \leq j \leq n$
$\sum_{j=1}^{n}{q_j} = 1$
$q_j \ge 0, 1 \leq j \leq n$

, :

\sum_{j = 1}^{n} a_{i j} q_{j} - α_{i} + β = 0, 1 \leq i \leq n

$\sum_{j=1}^{n}{a_{ij}q_j} - \alpha_i + \beta = 0, 1 \le i \le n$

\sum_{i = 1}^{n} a_{i j} p_{i} + λ_{j} - μ = 0, 1 \leq j \leq n

$\sum_{i=1}^{n}{a_{ij}p_i} + \lambda_j - \mu = 0, 1 \le j \le n$

\sum_{i = 1}^{n} p_{i} = 1, \sum_{j = 1}^{n} q_{j} = 1

$\sum_{i=1}^{n}{p_i} = 1, \sum_{j=1}^{n}{q_j} = 1$

$4n +2$ $2n+2$ . :

$\alpha_i \cdot p_i = 0, 1 \leq i \leq n$
$\lambda_j \cdot q_j = 0, 1 \leq j \leq n$

$p_i$ , $\alpha_i$ , $q_j$ , $\lambda_j$ . , $2^{2n}$ $2n$ . $2^{2n}$ , $2n+2$ $2n+2$ ( ).

, --:

α_{i}, p_{i}, λ_{j}, q_{j} \geq 0, 1 \leq i, j \leq n

$\alpha_i, p_i, \lambda_j, q_j \ge 0, 1 \leq i, j \leq n$

, . $i$ :

\sum_{j = 1}^{n} a_{i j} q_{j} - α_{i} + β = 0

$\sum_{j=1}^{n}{a_{ij}q_j} - \alpha_i + \beta = 0$

, $\alpha_i$ ,

\sum_{j = 1}^{n} a_{i j} q_{j} + β = 0

$\sum_{j=1}^{n}{a_{ij}q_j} + \beta = 0$

$\alpha_i$ , $q$ $\beta$ :

α_{i} = \sum_{j = 1}^{n} a_{i j} q_{j} + β

$\alpha_i = \sum_{j=1}^{n}{a_{ij}q_j} + \beta$

, : $A$ . , $\alpha_i$ , $\lambda_j$ : , ; . :

\sum_{j = 1}^{n} a_{i j} q_{j} + β = 0, 1 \leq i \leq n

$\sum_{j=1}^{n}{a_{ij}q_j} + \beta = 0, 1 \le i \le n$

\sum_{i = 1}^{n} a_{i j} p_{i} - μ = 0, 1 \leq j \leq n

$\sum_{i=1}^{n}{a_{ij}p_i} - \mu = 0, 1 \le j \le n$

\sum_{i = 1}^{n} p_{i} = 1, \sum_{j = 1}^{n} q_{j} = 1

$\sum_{i=1}^{n}{p_i} = 1, \sum_{j=1}^{n}{q_j} = 1$

p_{i}, q_{j} \geq 0, 1 \leq i, j \leq n

$p_i, q_j \ge 0, 1 \leq i,j \leq n$

, $n+1$ $n+1$ . .

5.

: , . . , $p$ , $q$ , $p'$ , $q'$ :

(A p^{'}, q) \leq (A p, q) \leq (A p, q^{'})

$(Ap', q) \leq (Ap, q) \leq (Ap, q')$

, , . , . , . : $p_1, q_1; p_2, q_2; ... ; p_k, q_k$ — . $p, q$ ,

\forall i \in 1, . . ., k : (A p_{i}, q) \leq (A p, q) \leq (A p, q_{i})

$\forall i \in {1,...,k}: (Ap_i, q) \leq (Ap, q) \leq (Ap, q_i)$

6.

GitHub: https://github.com/ashagraev/zero_sum_game

matrix.h : , , . . , .

kkt.cpp. . , callback'.

There can be more than one equilibrium in a game; moreover, there can be infinitely many of them. In any case, you need to be prepared for the fact that the algorithm will output more than one solution (and the whole set of solutions will be some linear shell over the derived solutions). Therefore, the signature of the function assumes that the result is a vector of strategies, and not one strategy. And in main, accordingly, all these vectors are displayed .

Examples of input matrices for the program are in input.txt , and the results of running the program for these examples are in the file output.txt .

Zero-sum games and Karush-Kun-Takker conditions

1. Equilibrium

2. --

3.

5.

6.

More articles: