Ітеративні методи розв’язання ігор

Зведення матричних ігор до задач лінійного програмування. Припустимо, що ціна гри додатна (u > 0). Якщо це не так, то відповідно властивості 2.6 завжди можна підібрати таке число с, додаток якого до всіх елементів матриці виграшів дає матрицю з додатними елементами, і отже, з додатними значеннями ціни гри. При цьому оптимальні змішані стратегії обох гравців не змінюються.

Отже, нехай дана матрична гра з матрицею А порядку m ´ n. Відповідно властивості 8.7 оптимальні змішані стратегії х = (х₁,..., х_m), y = (y₁,..., y_n) щодо гравців 1 і 2 і ціна гри u повинні задовольняти співвідношення.

(8.7)

(8.8)

Розділимо всі рівняння і нерівності в (8.7) і (8.8) на u (це можна зробити, оскільки за припущенням u > 0) і введемо позначення:

, ,

Тоді (8.7) і (8.8) перепишеться у вигляді:

, , , ,

, , , .

Оскільки перший гравець прагне знайти такі значення х_i і, отже, p_i, щоб ціна гри u була максимальною, розв’язок першої задачі зводиться до пошуку таких додатних значень p_i , для яких

, . (8.9)

Оскільки другий гравець прагне знайти такі значення y_j і, отже, q_j, щоб ціна гри u була найменшою, розв’язок другої задачі зводиться до пошуку таких додатних значень q_j, , для яких

, . (8.10)

Формули (8.9) і (8.10) описують двоїсті одна до одної задачі лінійного програмування (ЛП). Розв’язуючи ці задачі, отримаємо значення p_i , q_j і u. Тоді змішані стратегії отримуються за виразами:

. (8.11)

Приклад 8.9. Знайти розв’язок гри, що описується матрицею

Розв’язання. Під час розв’язання цієї гри до кожного елемента матриці А додамо 1 і отримаємо таку матрицю

Складемо тепер пару взаємодвоїстих задач:

Розв’яжемо другу з них:

Б.п.	q1	q2	Q3	q4	q5	q6	Розв’язок	å	Відношення
	-1	-1	-1					-3
q4									—
q5			1
q6									—

Б.п.	q1	Q2	q3	q4	q5	q6	Розв’язок	å	Відношення
		-1
q4		2
q3									—
q6

Б.п.	q1	q2	q3	q4	q5	q6	Розв’язок	å	Відношення
			0
q2
q3
q6

З оптимальної симплекс-таблиці випливає, що

(q₁, q₂, q₃) = (0; ; 1),

а із співвідношень подвійності випливає, що (p₁, p₂, p₃) = (; 1; 0).

Отже, ціна гри з платіжною матрицею А₁ дорівнює

= ,

а гри з платіжною матрицею А: .

При цьому оптимальні стратегії гравців мають вигляд:

Х = (х₁, х₂, х₃) = (uр₁; uр₂; uр₃) = = ,

Y = (y₁, y₂, y₃) = (uq₁; uq₂; uq₃) = = .