Принцип мінімаксу в парній грі з нульовою сумою

Допускаємо, що гравці, які беруть участь в грі однаково розумні і кожен з них робить все для того, щоби максимізувати свій виграш. Якщо гравець А вибирає стратегію А_і, то розраховує на те, що гравець В вибере ту із стратегій, яка мінімізує виграш гравця А. Тому в кожній стрічці платіжної матриці гравець А знаходить свій мінімальний виграш

(4.1)

Знаючи свої мінімальні виграші при використанні стратегії А_і,, гравець повинен зупинитися на тій із них, для якої є максимальним:

(4.2)

Оскільки гравець А розглядав найбільш несприятливі для себе варіанти, то встановлена ним величина називається нижньою ціною гри. Стратегія, яка забезпечує нижню ціну гри називається максимінною.

Гравець В зацікавлений мінімізувати свій програш, або виграш гравця А. Тому він буде вибирати ту із стратегій, яка забезпечить мінімальний виграш гравця А серед його максимальних виграшів, тобто використає критерій мінімаксу.

(4.3)

де (4.4)

- максимальний виграш гравця А при виборі стратегії В_j. Значення визначає верхню ціну гри, яка дає верхню оцінку програшу гравця В. Можна довести, що між нижньою та верхньою ціною гри завжди виконується співвідношення:

(4.5)

Існують ігри для яких нижня та верня ціни гри співпадають

(4.6)

Вони називаються іграми з сідловою точкою. Значення в цих іграх визначає ціну гри, а стратегії, які її забезпечують будуть оптимальними. При відході одного гравця від своєї оптимальної стратегії та її дотриманні іншим гравцем, порушник отримує гірший результат ніж встановлена ціна гри.

Приклад 2. Проаналізуємо задачу, наведену в прикладі 1.

	B1=1	B2=2	B3=3		=0
A1=1		-1	-2	-2
A2=2			-1	-1
A3=3
=0

 

Як видно з аналізу оптимальними стратегіями гравців є стратегії А₃, В₃.

 

Гра 2Х2 без сідлових точок

 

Нехай гравець А має m а гравець В – n стратегій. Враховуючи, що при відсутності сідлових точок нижня та верхня ціни гри не співпадають (), природнім є бажання гравця А збільшити свій виграш а гравця В – зменшити програш. Пошук компромісу приводить до використання складної стратегії, яка називається мішаною. Мішані стратегії гравців будемо позначати відповідно та , де p_i, q_j – імовірності використання чистих стратегій А_і та В_j., причому

(4.7)

Стратегії гравців для яких імовірності використання в оптимальних мішаних стратегіях більші нуля, називаються активними.

В основній теоремі теорії ігор доводиться, що всяка скінченна парна гра з нульовою сумою має хоча б один розв’язок в мішаних стратегіях. В найпростіших випадках цей розв’язок нескладно знайти аналітично з використанням простого графічного аналізу. Розглянемо найпростіший випадок – гру 2х2 без сідлової точки. Оскільки сідлової точки не існує, то всі стратегії гравців будуть активними. При використанні оптимальної мішаної стратегії гравцем А ціна результат гри буде рівний її ціні при виборі довільної стратегії гравцем В:

(4.8)

(4.9)

Крім того слід врахувати, що

(4.10)

покладаючи отримуємо

(4.11)

(4.12)

(4.13)

Прирівнюючи (4.11) та (4.12), отримаємо рівняння відносно р₁:

 

(4.14)

яке при конкретних значеннях коефіцієнтів платіжної матриці розв'язується елементарно.

До рівняння (4.14) можна прийти також шляхом простого геометричного аналізу (див.рисунок). Для цього через кінці одиничного відрізка осі абсцис проведемо перпендикуляри, на яких будемо відкладати виграш гравця А при використанні чистих стратегій. Нехай лівому відрізку відповідає стратегія А₁, а правому – А₂. Відповідно на лівому перпендикулярі будуємо відрізки а₁₁ та а₁₂, а на правому – відрізки а₂₁ та а₂₂. Для побудови відрізка прямої, що відповідатиме результату гри при використанні другим гравцем стратегії В₁, проведемо аналіз співвідношень (4.11), (4.13). Рівняння (4.11) визначає пряму, аргументом якої служить p₁, а умова (4.13) зводить її до відрізка.

 

Побудуємо цей відрізок прямої за його крайніми точками. Зокрема в точці А₁ p₁=1 i . В точці А₂ р1=0 і . Оскільки пряма однозначно визначається двома точками, то сполучивши точки (0,а₁₁) і (1,а₂₁), отримаємо графік залежності результату гри при стратегії В₁ від імовірності р₁. Величина р₁ будується на відрізку [0,1] як віддаль поточної точки до точки А₂ (віддаль до одиниці). Аналогічно будується пряма для стратегії В₂, що сполучає точки (0,а₂₁) і (1,а₂₂).

Для знаходження оптимального значення побудуємо нижню границю виграшу гравця І, тобто ломану B₂NB₁. Із цієї нижньої межі виграшів гравець І прагне вибрати максимальне значення, якому відповідає точка N. Ордината цієї точки рівна ціні гри а абсциса дозволяє знайти параметри оптимальної мішаної стратегії гравця І:

(4.15)

Щоб знайти точне числове значення величини , потрібно розв'язати рівняння (4.14).

.

Оптимальна мішана стратегія гравця В знаходиться аналогічно. Однак відрізки, які будуть відкладатися на вертикалях В1 та В2 повинні відповідати вже результатам гри при цих стратегіях.Гравець В передбачає найбільш несприятливі для себе дії гравця A отримуючи верхню межу програшу – ламану A₁NA₂, ціну гри та параметри своєї оптимальної мішаної стратегії.

Слід відзначити, що розв'язок гри не завжди визначається точкою перетину ліній, що визначають результати гри для певних стратегій. На наступному малюнку показано, коли нижня границя виграшу гравця А співпадає з лінією В₂В₂.

Стратегія В₁ для гравця В явно невигідна, тому гравець А аналізує лише його стратегію В₂, вибираючи єдину оптимальну для себе стратегію А₂. Отже дана гра має сідлову точку А₂В₂.Наступний малюнок представляє також випадок наявності сідлової точки, хоча точка перетину оціночних прямих існує. Тут оптимальною є стратегії А₁В₂

Спрощення ігор

 

Якщо платіжна матриця гри не містить сідлової точки, то складність розв'язання задачі можна значно знизити, якщо зменшити розмірність платіжної матриці шляхом викреслювання дублюючих та заздалегідь невигідних стратегій.

Дублюючим стратегіям відповідають рівні стрічки (стовпчики) платіжної матриці. Якщо всі елементи i-ої стрічки (стовпчика) платіжної матриці не більші відповідних елементів стрічки (стовпчика) j, то стратегія А_і (В_j) називається заздалегідь невигідною.