РІШЕННЯ ІГОР 2´2, 2´N, M´2. ГРАФОАНАЛІТИЧНИЙ МЕТОД

Припустимо, що гра 2´2, задана матрицею А не має сідлової точки і потрібно знайти її рішення S^*_A={P^*_1a,P^*_2a}; S^*_B={P^*_1b,P^*_2b}.

	S_1b	S_2b	Відповідно до теореми про активні стратегії, сторона А, дотримуючись оптимальної стратегії S_A забезпечить собі виграш навіть, якщо В буде використовувати не оптимальну стратегію S_B, а окремі S_1b,S_2b.
S_1a	а₁₁	а₁₂
S_2a	а₂₁	а₂₂

Тоді а₁₁× P^*_1a+ а₂₁× P^*_2a= (в B - стратегія S_1b)

і а₁₂× P^*_1a+ а₂₂×P^*_2a= (в B - стратегія S_2b) (А)

Аналогічно для оптимальної стратегії B - S^*_B

а₁₁× P^*_1b+ а₂₁× P^*_2b= (в А - стратегія S_1а)

і а₁₂× P^*_1b+ а₂₂× P^*_2b= (в А - стратегія S_2а) (В)

Невідомими в цих формулах є P^*_1a, P^*_2a, P^*_1b, P^*_2bта , що обчислюються по формулах (рішення системи трьох рівнянь з трьома невідомими).

Для системи (А)

; ; (4.2)

Для системи (В)

; ; (4.3)

Для (2 - 3) або тоді та . (4.4)

Виконання (2.4) означає відсутність сідлової точки у матриці А (немає елемента мінімального в рядку і максимального в стовпчику).

Звернемося до геометричної інтерпретації результатів. Нехай S_A={P_1a,P_2a} - довільна змішана стратегія А проти чистої S_1b - В і середньоочікуваний виграш ₁=а₁₁×P_1b+а₂₁×P_2b=(а₁₁-а₂₁)P_1а+а₂₁. Те ж саме відноситься до чистої стратегії В - S_2b: ₂=а₁₂×P_1а+а₂₂×P_2b=(а₁₂-а₂₂)P_1а+а₂₂.

Але ні S_1b, ні S_2b не оптимальні для В. Сторона А повинна розраховувати на виграш .

При заданих а_ij ₁ і ₁ - функції від P_1а, отже й і її значення збігаються або з ₁ (₁<₂), або з ₂ (₁>₂).

Отже, можна побудувати графік і знайти S_A, . Для А у залежності від (2.4) буде мати місце або мал.2, або мал.3.

або

Мал.2. Мал.3.

Сторону А цікавить те P_1a, при якому - максимальне. Прямі будуються по точках (0,а₂₁); (1,а₁₁); (0,а₂₂); (1,а₁₂). P^*_1a одержуємо, прирівнюючи ₁ і ₂ Þ (а₁₁-а₂₁)P_1а+а₂₁=(а₁₂-а₂₂)P_1а+а₂₂, відкіля й одержуємо формулу (2) для P^*_1a: .

Величини P^*_1b і P^*_2b визначаються в залежності від (4) аналогічно, мал.4, мал.5, але в побудовах беруть участь точка (0,а₁₂) і (1,а₁₁) для ₁ і (0,а₂₂) і (1,а₂₁) для ₁₁ і замість розглядається , де ₁=а₁₁×P_1b+а₁₂×P_2b, ₁₁=а₂₁×P_1а+а₂₂×P_2b і відшукується .

або

Мал.4. Мал.5.

Приклад 5. Дана гра

	-1
-3

Знайти оптимальні стратегії сторін. а₁₁=2; а₂₁=-3; а₁₂=-1; а₂₂=4

Переконаємося, що немає сідлових точок.

Обчислимо =max{-1;-3}=-1, =min{2;4}=2, ¹ . По точках (0; -3) і (1;2) будуємо пряму , мал.6, по (0;4) і (1;-1) - пряму , мал.6. По точках (0;-1) і (1;2) будуємо пряму , мал.7, по (0;4) і (1;-3) - пряму , мал.7.

Мал.6. Мал.7.

Max досягається при P^*_1а=0,7 і дорівнює 0,5; - при P^*_1b=0,5 і дорівнює 0,5. Слушність можна перевірити по формулах (2 і 3).

Тоді S^*_A=(0,7;0,3); S^*_B=(0,5;0,5).

Нехай задана гра 2´n, що не має сідлових точок. Знайдемо її рішення: S^*_A={P^*_1a,P^*_2a}; S^*_B={P^*_1b,P^*_2b,…,P^*_nb}... Застосовуючи проти кожної із окремих стратегій S_jb S^*_A, одержимо =а₁₁×P^*_1a+а₂₁×P^*_2a;…;= =а_1n×P^*_1a+а_2n×P^*_2a. Точно також, застосовуючи проти кожної S_ia S^*_B, одержимо =а₁₁×P^*_1b+а₁₂×P^*_2b+…+ а_1n×P^*_1a; =а₂₁×P^*_1b+а₂₂×P^*_2b+…+ а_2n×P^*_nb; .

Аналітичне рішення цих систем більш складне, чим 2´2. Тому вирішимо графічно.		S1b	S2b	…	S_nb
S_1a	а₁₁	а₁₂	…	а_1n
S_2a	а₂₁	а₂₂	…	а_2n

Загальна схема пошуку S^*_A, S^*_B:

1) за даними матриці будуємо n прямих ₁=(а₁₁-а₂₁)P_1а+а₂₁, ₂=(а₁₂-а₂₂)P_1а+а₂₂,…,_n=(а_1n-а_2n)P_1а+а_2n, і креслимо графік , на ньому знаходиться екстремальна точка (P^*_1a;);

2) вибираються дві будь-які прямі з протилежним нахилом із тих, що перетинаються у цій точці;

3) прямим стратегії, що відповідають цим S_rb S_kb включаються в гру 2´2 проти S_1а S_2а.

4) отримана гра 2´2 вирішується аналітично за допомогою формул або графічно.

Аналогічно для рішення гри m´2. Єдина відмінність буде полягати в тому, що будують прямі _i=(а_i1-а_i2)P_1b+а_i2, i=1,2,…,m і знаходимо , мінімум досягається в P^*_1b і точка (P^*_1b,) використовується для переходу до гри 2´2.

Приклад 6. Дана гра 4´2. Вона не має сідлових точок =1< =3. 1) Будуємо прямі _i=(а_i1-а_i2)P_1b+а_i2, i=1,2,3,4, мал. 8. ₁=(а₁₁-а₁₂)P_1b+а₁₂=(3-1) ×P_1b+1= 2×P_1b+1, ₂=(а₂₁-а₂₂)P_1b+а₂₂= -5P_1b+3, ₃=(а₃₁-а₃₂)P_1b+а₃₂=8P_1b-3, ₄=(а₄₁-а₄₂)P_1b+а₄₂= -1,5P_1b+2.		S_1b	S_2b
S_1a
S_2a	-2
S_3a		-3
S_4a	0,5

Знаходимо P^*_1b=0,29, =1,56. Через цю точку проходять прямі ₁, ₂, _4. Тому сторона А має три активні стратегії S_1a, S_2a,S_4a.

2) вибираємо з цих трьох прямих дві з протилежними нахилами, наприклад, ₁та _2.


-2

одержуємо гру 2´2;

4) знаходимо по формулах

Одержали те ж саме, що і графічно. У такий спосіб S^*_A=(²/₇,⁵/₇,0,0), S^*_B=(²/₇,⁵/₇), =¹¹/₇.

Якщо вибрати ₁та ₄, то одержимо гру


½

та її рішення S^*_A=(³/₇,0,0,⁴/₇), S^*_B=(²/7,⁵/₇), =¹¹/₇.