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

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

	S1b	S2b	Відповідно до теореми про активні стратегії, сторона А, дотримуючись оптимальної стратегії S*A забезпечить собі виграш γ навіть, якщо В буде використовувати не оптимальну стратегію S*B, а окремі S1b, S2b.
S1a	а11	а12
S2a	а21	а22

Тоді а₁₁× 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	…	Snb
S1a	а11	а12	…	а1n
S2a	а21	а22	…	а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)P1b+аi2, i=1,2,3,4, мал. 8. γ1=(а11-а12)P1b+а12=(3-1) ×P1b+1= 2×P1b+1, γ2=(а21-а22)P1b+а22= -5P1b+3, γ3=(а31-а32)P1b+а32=8P1b-3, γ4=(а41-а42)P1b+а42= -1,5P1b+2.		S1b	S2b
S1a
S2a	-2
S3a		-3
S4a	0,5

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

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

3) -2 одержуємо гру 2´2; 4) знаходимо по формулах

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

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

½

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