शून्य-राशि का खेल और करुश-कुन-टकर की स्थिति

इस लेख में, मैं एक उदाहरण के रूप में विरोधी खेलों का उपयोग करके संतुलित मिश्रित रणनीतियों को खोजने की समस्या से निपटता हूं।

दो खिलाड़ी ए और बी हों, जो बार-बार एक निश्चित खेल खेलते हैं। प्रत्येक ड्रॉ में प्रत्येक खिलाड़ी कई रणनीतियों में से एक का पालन करता है - सादगी के लिए, हम मानते हैं कि दोनों खिलाड़ियों के लिए रणनीतियों की संख्या मेल खाती है और बराबर होती है$$$n$ । चुनते समय$$$i$ पहले खिलाड़ी द्वारा वें रणनीति और$$$j$ वें खिलाड़ी द्वारा दूसरी रणनीति, पहले खिलाड़ी को एक जीत मिलेगी$$$a_{ij}$ , और दूसरा खिलाड़ी एक ही नुकसान हो जाएगा - यह कैसे विरोधी खेल व्यवस्थित कर रहे हैं है। इन जीत को एक वर्ग मैट्रिक्स के रूप में लिखा जा सकता है$$$A$ :

$$

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

खिलाड़ी बार-बार खेल खेलते हैं और विभिन्न स्वीपस्टेक में विभिन्न रणनीतियों का उपयोग कर सकते हैं। एक मिश्रित रणनीति खिलाड़ी की शुद्ध रणनीतियों में से प्रत्येक से जुड़ी संभावनाओं का एक सदिश है । प्रत्येक खिलाड़ी अपनी मिश्रित रणनीति द्वारा उसके लिए परिभाषित संभावना के अनुसार अगले ड्रा में एक रणनीति चुनता है। यदि द्वारा निरूपित किया जाता है$$$p$ तथा $$$q$खिलाड़ियों की मिश्रित रणनीति, फिर पहले खिलाड़ी के जीतने की गणितीय उम्मीद होगी

$$

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

मिश्रित रणनीतियों की एक जोड़ी को संतुलन कहा जाता है यदि कोई खिलाड़ी अपनी रणनीति को बदलकर अपनी जीत को बढ़ा नहीं सकता है। दूसरे शब्दों में, रणनीतियों की किसी भी अन्य जोड़ी के लिए$$$p'$, $$$q'$प्रदर्शन किया:

$$

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

यहां अब हम ऐसे संतुलन की तलाश कर रहे हैं।

1. संतुलन

इसलिए, मिश्रित रणनीति की एक जोड़ी एक संतुलन बनाती है यदि पहले खिलाड़ी के लिए मिश्रित रणनीति बदलने से उसकी जीत नहीं बढ़ सकती है, और दूसरे खिलाड़ी के लिए मिश्रित रणनीति बदलने से उसका नुकसान कम नहीं हो सकता है।

उदाहरण के लिए, इस तरह के अदायगी मैट्रिक्स पर विचार करें:

$$

$$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'}{(Ap', q)}, q = \arg \min_{q'}{(Ap, q')}$$

:

$$

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

, . - : , .

, , :

$$

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

$$

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

- , . - --.

2. --

-, , 1951- , , 1939- .

:

$$

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

, :

$$

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

$$

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

, , , --:

$$

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

$$

$$\lambda_i \cdot h_i(x) = 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$$

$$

$$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) = -(Ap, q) + \sum_{i=1}^{n}{\alpha_i p_i} - \beta \Big(\sum_{i=1}^{n}p_i - 1\Big)$$

$$

$$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_{ij}q_j} + \alpha_i - \beta$$

$$

$$\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_{ij}q_j} - \alpha_i + \beta = 0, 1 \le i \le 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$$

$$$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$( ).

, --:

$$

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

.

, . $$$i$:

$$

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

, $$$\alpha_i$,

$$

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

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

$$

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

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

$$

$$\sum_{j=1}^{n}{a_{ij}q_j} + \beta = 0, 1 \le i \le 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$$

:

$$

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

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

5.

: , . . , $$$p$, $$$q$, $$$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}: (Ap_i, q) \leq (Ap, q) \leq (Ap, q_i)$$

6.

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

matrix.h : , , . . , .

kkt.cpp. . , callback'.

एक खेल में एक से अधिक संतुलन हो सकते हैं, इसके अलावा, उनमें से कई असीम रूप से हो सकते हैं। किसी भी मामले में, आपको इस तथ्य के लिए तैयार रहने की आवश्यकता है कि एल्गोरिथ्म एक से अधिक समाधान का उत्पादन करेगा (और समाधान का पूरा सेट व्युत्पन्न समाधानों पर कुछ रैखिक शेल होगा)। इसलिए, फ़ंक्शन का हस्ताक्षर मानता है कि परिणाम रणनीतियों का एक वेक्टर है, और एक रणनीति नहीं है। और मुख्य रूप से, तदनुसार, इन सभी वैक्टर को प्रदर्शित किया जाता है ।

प्रोग्राम के लिए इनपुट मैट्रिसेस के उदाहरण input.txt में हैं , और इन उदाहरणों पर प्रोग्राम को चलाने के परिणाम file.txt में हैं ।