🍮 🤽🏻 🍻 Jeux à somme nulle et conditions de Karush-Kun-Takker 🤳 👨🏼‍💼 👇🏿

Dans cet article, je traite du problème de trouver des stratégies mixtes équilibrées en utilisant des jeux antagonistes comme exemple.

Soit deux joueurs, A et B, qui jouent à plusieurs reprises un certain jeu. Chaque joueur dans chaque tirage adhère à l'une de plusieurs stratégies - pour simplifier, nous supposons que le nombre de stratégies pour les deux joueurs coïncide et est égal $n$ . Lors du choix $i$ stratégie premier joueur et $j$ stratégie du deuxième joueur, le premier joueur recevra une victoire $a_{ij}$ et le deuxième joueur subira la même perte - c'est ainsi que les jeux antagonistes sont organisés. Ces gains peuvent être écrits sous forme de matrice carrée $A$ :

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

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

Les joueurs jouent le jeu à plusieurs reprises et peuvent utiliser différentes stratégies dans différents tirages au sort. Une stratégie mixte est un vecteur de probabilités associé à chacune des stratégies pures du joueur. Chaque joueur choisit l'une des stratégies du prochain tirage en fonction de la probabilité définie pour elle par sa stratégie mixte. Si indiqué par $p$ et $q$ stratégies mixtes des joueurs, alors l'attente mathématique de gagner le premier joueur sera

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}}}$

Une paire de stratégies mixtes est appelée équilibre si aucun joueur ne peut augmenter ses gains en modifiant sa stratégie. En d'autres termes, pour toute autre paire de stratégies $p'$ , $q'$ effectué:

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

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

Ici, nous recherchons maintenant de tels équilibres.

1. Équilibre

Ainsi, une paire de stratégies mixtes forme un équilibre si changer une stratégie mixte pour le premier joueur ne peut pas augmenter ses gains, et changer une stratégie mixte pour le deuxième joueur ne peut pas réduire sa perte.

Par exemple, considérons une telle matrice de gains:

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'.

Il peut y avoir plus d'un équilibre dans un jeu; de plus, il peut y en avoir une infinité. Dans tous les cas, vous devez être préparé au fait que l'algorithme produira plus d'une solution (et l'ensemble des solutions sera un shell linéaire sur les solutions dérivées). Par conséquent, la signature de la fonction suppose que le résultat est un vecteur de stratégies et non une stratégie. Et en général, en conséquence, tous ces vecteurs sont affichés .

Des exemples de matrices d'entrée pour le programme se trouvent dans input.txt et les résultats de l'exécution du programme sur ces exemples se trouvent dans le fichier output.txt .

Jeux à somme nulle et conditions de Karush-Kun-Takker

1. Équilibre

2. --

3.

5.

6.

More articles: