06. Принцип максиміну в антагоністичних іграх. Сідлова точка
Як зазначалося, найважливішим питанням теорії ігор (зокрема і матричних) є питання про вибір оптимальних стратегій кожного з гравців.
Оптимальною стратегієюгравця в матричній грі називається така, що забезпечує йому максимальний виграш. Якщо гра повторюється неодноразово, оптимальна стратегія повинна забезпечувати максимальний середній виграш.
При виборі цієї стратегії основою міркувань є припущення, щоПротивник є щонайменше так само розумний, як і ми самі,і робить все, щоб досягти такої ж мети.
Розрахунок на розумного супротивника - лише одна з можливих позицій у конфлікті, але в теорії ігор саме вона кладеться в основу.
При цьому для вибору оптимальної стратегії використовуютьПринцип максиміна:Вибирай ту стратегію, щоб при найгіршій для нас поведінці противника отримати максимальний виграш.Іншими словами, принцип максиміна передбачає вибір тієї стратегії, коли він наш мінімальний виграш для різних стратегій максимальний. Звідси і назва «принцип максиміну».
Як видно, принцип максиміну - це принцип вкрай обережного гравця, але він є основним принципом теорії матричних ігор.
Для пояснення принципу максиміну розглянемо приклад 1 матричної гри G (4х5) із платіжною матрицею, наведеною на рис. 2.2.
Якою стратегією гравцюАскористатися? Є спокусливий виграш 12 при застосуванні стратегіїА3. Але при цьому противник може вибрати стратегіюВ3, і гравець А отримає виграш, що дорівнює трьом.
Для визначення оптимальної стратегії відповідно до принципу максиміну, запишемо у правому додатковому стовпці платіжної матриці мінімальне значенняAIу кожному рядку (мінімум рядка). З усіх значеньAI(правий стовпець) виділимо найбільше. Йому відповідає стратегіяА4. Вибравши цю стратегію, ми у всякому разі можемо бути впевнені, що за будь-якої поведінки противника виграш буде не менше п'яти.
Ця величина – наш гарантований виграш. Він називаєтьсянижньою ціною гри(або «максиміном» - максимальний з мінімальних виграшів). Будемо позначати йогоA. У прикладі a = Aij =5.
Тепер станемо на думку гравця В і поміркуємо за нього. Вибираючи стратегію, він хотів би віддати якомога менше, але повинен розраховувати на найгіршу для нього поведінку гравця А.
Припишемо до платіжної матриці (рис.2.2) нижній рядок і в ньому запишемо найгірше для гравця У можливі результати (максимуми стовпцівBJ).
Очевидно, обережний супротивник повинен вибрати стратегію, при якій величина B J мінімальна. Ця величина називаєтьсяверхньою ціною гри(або "мінімаксом" - мінімальний з максимальних програшів). Позначатимемо їїB. У прикладі b = Aij = 7.
Отже, з принципу обережності, гравець А повинен вибрати стратегіюА4, яке противник -В3. Такі стратегії називаються максимінними або мінімаксними стратегіями (що випливають із принципу максиміну).
Доки обидві сторони в нашому прикладі дотримуватимуться своїх максимічних стратегій, виграш гравцяАі програш гравцяВдорівнюватимеА43=5.
Легко показати, що нижня ціна гри ніколи не перевищує верхню ціну гри.
Лемма 1. Нехай задана матриця виграшів
А = êêaijêêі визначені b = та a = .
Тоді.
Доказ.За визначенням максимуму та мінімуму длябудь-яких фіксованих значеньIтаJмаємо
(2.1)
Оскільки ліва частина нерівності (2.1) не залежить відI, то можемо записати
(2.2)
Оскільки права частина нерівності (2.1) залежить відJ, то
(2.3)
Об'єднуючи нерівності (2.2) і (2.3), отримуємо нерівність (2.1), що потрібно було довести. Отже, завждиB³A.
ВипадокB=Aвідповідає наявності у платіжної матриці так званоїСідлової точки.
Визначення. Точка (I*,J*) називається сідловою точкою платіжної матриціAIj, якщо для решти i і j цієї матриці виконується умова
Т. е.Аijє одночасно мінімумом свого рядка і максимумом свого стовпця.
Наведемо без підтвердження наступну теорему.
Теорема 1. Для того щоб
Необхідно і достатньо, щоб матрицяAIj мала сідлову точку. Крім того, якщо (I*,J*) - сідлова точка матриціAIj, то
(2.4)
Кажуть, що матрична гра має сідлову точку, якщо відповідна їй матриця виграшів (платіжна матриця) має сідлову точку.
Приклад 2.Знайти рішення гри G (3х3), платіжна матриця якої має такий вигляд: