#⃣ ⚱️ 🧖🏾 Game zero-sum dan kondisi Karush-Kun-Takker 🏇🏽 👩🏾 👩🏽‍🌾

Pada artikel ini, saya membahas masalah menemukan strategi campuran seimbang menggunakan game antagonis sebagai contoh.

Biarkan ada dua pemain, A dan B, yang berulang kali memainkan game tertentu. Setiap pemain di setiap undian mengikuti salah satu dari beberapa strategi - untuk kesederhanaan, kami menganggap bahwa jumlah strategi untuk kedua pemain bertepatan dan setara. $n$ . Saat memilih $i$ pemain strategi pertama dan $j$ strategi pemain kedua, pemain pertama akan menerima kemenangan $a_{ij}$ dan pemain kedua akan mendapatkan kerugian yang sama - ini adalah bagaimana permainan antagonis diatur. Kemenangan ini dapat ditulis sebagai matriks persegi $A$ :

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

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

Pemain memainkan game berulang kali dan dapat menggunakan strategi yang berbeda dalam undian yang berbeda. Strategi campuran adalah vektor probabilitas yang terkait dengan masing-masing strategi murni pemain. Setiap pemain memilih salah satu strategi dalam undian berikutnya sesuai dengan probabilitas yang ditentukan untuknya oleh strategi campurannya. Jika dilambangkan dengan $p$ dan $q$ strategi campuran pemain, maka harapan matematis untuk memenangkan pemain pertama adalah

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

Sepasang strategi campuran disebut keseimbangan jika tidak ada pemain yang dapat meningkatkan kemenangan mereka dengan mengubah strategi mereka. Dengan kata lain, untuk setiap pasangan strategi lainnya $p'$ , $q'$ dilakukan:

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

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

Di sini kita sekarang mencari keseimbangan semacam itu.

1. Ekuilibrium

Jadi, sepasang strategi campuran membentuk keseimbangan jika perubahan dalam strategi campuran untuk pemain pertama tidak dapat meningkatkan keuntungannya, dan perubahan dalam strategi campuran untuk pemain kedua tidak dapat mengurangi kerugiannya.

Sebagai contoh, pertimbangkan matriks hasil seperti itu:

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

Mungkin ada lebih dari satu keseimbangan dalam permainan, apalagi, bisa ada banyak dari mereka. Dalam kasus apa pun, Anda harus siap dengan fakta bahwa algoritma akan menghasilkan lebih dari satu solusi (dan seluruh rangkaian solusi akan menjadi beberapa shell linier dari solusi yang diturunkan). Oleh karena itu, tanda tangan fungsi menganggap bahwa hasilnya adalah vektor strategi, dan bukan satu strategi. Dan pada intinya, dengan demikian, semua vektor ini ditampilkan .

Contoh-contoh matriks masukan untuk program ada di input.txt , dan hasil menjalankan program pada contoh-contoh ini ada di file output.txt .

Game zero-sum dan kondisi Karush-Kun-Takker

1. Ekuilibrium

2. --

3.

5.

6.

More articles: