12.4. Пошук оптимальних рішень за допомогою чистих стратегій

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

Нехай гравець А розташовує m чистими стратегіями А\,

Гравець Б розташовує n чистими стратегіями B\, В2- •.., Bn.

Гравець А може обрати будь-яку стратегію A{, у відповідь на яку гравець Б може обрати будь-яку стратегію В/. Поєднання цих стратегій приведе до певного числового результату — платежу (а,у), що називають виграшем гравця А і відповідно програшем гравця Б.

Програш становитиме (-a,y).

Матриця П = |a;y|, розміром m • n, платіжна матриця чи матри­ця гри наведена в табл. 12.1.

Нехай гравець A вибирає якусь стратегію A,-; тоді в найгіршо­му випадку (наприклад, якщо вибір стане відомим гравцю Б) він одержить виграш, який дорівнюватиме min а/.

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


Для цього знайдемо спочатку для гравця А в кожному рядку число aj = minj atj, що вказує на мінімально гарантований ви­граш для гравця А, що застосовує стратегію A ,-.

Далі знайдемо в кожнім стовпці число ß j = max і a tj, що вказує

на максимально гарантований програш для Б, що застосовує стратегію Bj.

Величина a = max;(minj atj) — гарантований виграш гравця А (варіант «кращий з гірших»).

Величина а називається нижньою ціною гри, чи макси-мінним виграшем, або максимінною стратегією гравця А.

Гравець Б, вибираючи стратегію, виходить з такого принципу; при виборі певної стратегії Bj його програш не повинен переви­щити максимального зі значень елементів j-го стовпця матриці, тобто повинен бути менший чи дорівнювати max ац.

Розглядаючи згодом цю множину max ay для різних значень j, гравець Б, природно, вибере таке значення j, при якому його мак­симальний програш ß мінімізується.

Величина ß = min-s(max,8^) називається верхньою ціною

гри чи мінімаксним програшем або мінімаксною стратегією гравця Б.

Тобто гравець Б вибирає стратегію «кращу із гірших». Завжди a < ß. Принцип, відповідно до якого вибирають ці стратегії, на­зивається принципом максиміна для А і принципом мінімакса для Б. Тоді при будь-якій стратегії, вибраній гравцем Б, гравцю А забезпечується виграш не менше а, а для Б при виборі ним міні-максної стратегії забезпечується програш не більше р.

Якщо а = Р, то гра називається грою із сідловою то­чкою, а загальне значення а = Р = V називається ціною

гри. Елемент а,ф у матриці такої гри є одночасно мініма­льним у рядку іо, максимальним у стовпці \о і називається сідловою точкою.

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

Тоді оптимальним рішенням для обох гравців є вибір максимінної для А і мінімаксної для Б стратегії.

Будь-яке відхилення не буде вигідним.

Розглянемо алгоритм чистих стратегій на прикладах.

Приклад 1

Визначити нижню і верхню ціни для гри, заданої платіжною матрицею (див. табл. 12.2).


Таблиця 12.2

Знайдемо мінімальні елементи в стовпцях. Тоді а = тах(3,4,2) = 4 — нижня ціна гри. Знайдемо максимальні елементи в рядках. Тоді Р = тіп(6,7,4) = 4 — верхня ціна гри. Оскільки а = Р = 4, то це гра із сідловою точкою. Величина V = 4 — ціна гри.

Рішення полягає в тому, що гравець А повинен вибрати стра­тегію А3, при цьому його виграш не менше 4. Гравець Б повинен вибрати стратегію В3, при цьому його програш не більше 4.

Легко помітити, що відхилення одного із гравців від оптима­льної стратегії приводить до зменшення виграшу (для гравця А) і збільшенню програшу (для гравця Б).

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

Приклад 2

Є платіжна матриця. Знайти сідлову точку.

Розв'язання:

а(тіп)і


 

Дтах) і


0,3       0,6       0,8

0,9       0,4       0,2

0,7       0,5       0,4

0,9       0,6       0,8


0,3 0,2 0,4


а = 0,4 Р = 0,6 а ф Р

сідлової точки немає, оптимального рішення немає.

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