🔣 👩‍🎓 🌜 Nullsummenspiele und Karush-Kun-Takker-Bedingungen ☸️ 👩🏿‍🎨 😄

In diesem Artikel beschäftige ich mich mit dem Problem, ausgewogene gemischte Strategien am Beispiel antagonistischer Spiele zu finden.

Es sollen zwei Spieler sein, A und B, die wiederholt ein bestimmtes Spiel spielen. Jeder Spieler in jeder Auslosung hält sich an eine von mehreren Strategien - der Einfachheit halber nehmen wir an, dass die Anzahl der Strategien für beide Spieler übereinstimmt und gleich ist $n$ . Bei der Wahl $i$ Strategie erster Spieler und $j$ Strategie des zweiten Spielers, der erste Spieler erhält einen Gewinn $a_{ij}$ und der zweite Spieler wird den gleichen Verlust bekommen - so sind die antagonistischen Spiele angeordnet. Diese Gewinne können als quadratische Matrix geschrieben werden $A$ ::

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

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

Die Spieler spielen das Spiel wiederholt und können bei verschiedenen Gewinnspielen unterschiedliche Strategien anwenden. Eine gemischte Strategie ist ein Vektor von Wahrscheinlichkeiten, die mit jeder der reinen Strategien des Spielers verbunden sind. Jeder Spieler wählt eine der Strategien in der nächsten Ziehung entsprechend der Wahrscheinlichkeit, die für ihn durch seine gemischte Strategie definiert ist. Wenn mit bezeichnet $p$ und $q$ gemischte Strategien der Spieler, dann wird die mathematische Erwartung, den ersten Spieler zu gewinnen, sein

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

Ein Paar gemischter Strategien wird als Gleichgewicht bezeichnet, wenn kein Spieler seinen Gewinn durch Ändern seiner Strategie erhöhen kann. Mit anderen Worten, für jedes andere Strategiepaar $p'$ , $q'$ durchgeführt:

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

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

Hier suchen wir jetzt nach solchen Gleichgewichten.

1. Gleichgewicht

Ein Paar gemischter Strategien bildet also ein Gleichgewicht, wenn eine Änderung der gemischten Strategie für den ersten Spieler seinen Gewinn nicht erhöhen kann und eine Änderung der gemischten Strategie für den zweiten Spieler seinen Verlust nicht verringern kann.

Betrachten Sie beispielsweise eine solche Auszahlungsmatrix:

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

Es kann mehr als ein Gleichgewicht in einem Spiel geben, außerdem kann es unendlich viele davon geben. In jedem Fall müssen Sie darauf vorbereitet sein, dass der Algorithmus mehr als eine Lösung ausgibt (und der gesamte Satz von Lösungen eine lineare Hülle über den abgeleiteten Lösungen darstellt). Daher wird bei der Signatur der Funktion davon ausgegangen, dass das Ergebnis ein Vektor von Strategien und nicht eine Strategie ist. Dementsprechend werden im Wesentlichen alle diese Vektoren angezeigt .

Beispiele für Eingabematrizen für das Programm befinden sich in input.txt , und die Ergebnisse der Ausführung des Programms für diese Beispiele befinden sich in der Datei output.txt .

Nullsummenspiele und Karush-Kun-Takker-Bedingungen

1. Gleichgewicht

2. --

3.

5.

6.

More articles: