Глава 2. Елементи матричних ігор | Вступ | Приклади. | Лінійного програмування. | C. Графоаналитический спосіб вирішення завдань лінійного програмування | D. Симплекс-метод | Алгоритм симплекс-методу | Метод штучного базису (М-метод) | Елементи теорії подвійності | Основна теорема подвійності |

загрузка...
загрузка...
На головну

Методи вирішення матричних ігор.

  1. C. Графоаналитический спосіб вирішення завдань лінійного програмування
  2. I. Неекспериментальні методи
  3. II. Арени. Методи отримання.
  4. II. Основні методи збору соціологічної інформації, їх коротка характеристика.
  5. II. рішення завдання
  6. II. експериментальні методи
  7. II. Метод ДЕРЖАВНОГО УПРАВЛІННЯ.

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

Відразу зауважимо, що першим етапом пошуку вирішення будь-якої матричної гри є аналіз гри на наявність сідлової точки (див. П.2.1). Тільки при відсутності такої переходять до більш тонким методам знаходження рішення. Серед таких методів є як універсальні, які застосовні до будь-якої матричної грі, так і приватні, які використовуються для окремих класів ігор

3) Гра 2х2.

Нехай гра задана матрицею

.

Припустимо, що сідлова точка відсутня. Однак, відповідно до теореми Неймана, оптимальне рішення гри існує і визначається парою змішаних стратегій SA * = (p1 *,p2 *), SB * = (q1 *,q2 *). Використовуючи властивість 3 рішення ігр та елементарні алгебраїчні перетворення (докладний висновок ми опускаємо), приходимо до наступних формулах:

р1= (а22-а21) / (а11+а22-а12-а21), р2= 1р1,

q1= (a22-a12) / (a11+a22-a12-a21), q2= 1q1, (2.7)

vS= (a22·a11-a12·a21) / (a11+a22-a12-a21).

При цьому відсутність сідлової точки в грі гарантує незверненими в 0 знаменників в наведених формулах.

приклад 2.4. Знайдемо рішення в змішаних стратегіях гри, розглянутої в прикладі 2.1 про двох гравців з двома монетами. Платіжна матриця цієї гри має вигляд:

Нижня і верхня ціни цієї гри a= -3 І b= 2. Отже, сідлова точка відсутня.

Знайдемо оптимальні стратегії гравців і ціну гри, застосовуючи формули (4.1.). маємо:

р1= (4 - (- 3)) / (2 + 4 - (- 3) - (- 3)) = 7/12, р2= 1-7 / 12 = 5/12,

q1= (4 - (- 3)) / (2 + 4 - (- 3) - (- 3)) = 7/12, q2= 5/12,

vS= (4 ? 2 - (- 3) ? (-3)) / (2 + 4 - (- 3) - (- 3)) = - 1/12.

Отже, рішенням гри є пара змішаних стратегій SA * = (7 / 12,5 / 12), SB * = (7 / 12,5 / 12), ціна гри vS= -1 / 12. Це означає, що оптимальна стратегія кожного гравця полягає в тому, щоб чергувати свої чисті стратегії випадковим чином, вибираючи 1-ю стратегію (покласти 1 руб.) З ймовірністю 7/12, а 2-ю стратегію (покласти 2 руб.) - З ймовірністю 5/12.

Негативна ціна гри vS= -1 / 12 показує, що при використанні гравцями своїх оптимальних стратегій, перший гравець програє другому в кожній партії «в середньому» 1/12 рубля. Тим самим можна говорити про початкової несправедливості умов гри.

4) Спрощення ігор за допомогою відкидання

домінованих стратегій.

стратегія Аi гравця А називається домінуючою над стратегією Аk (А стратегія Аk домінованих стратегією Аi), Якщо всі елементи iго рядка платіжної матриці не менше відповідних елементів kго рядка, т. е. аi1?ak1, ai2?ak2, ..., aim?akm (В тому ж сенсі можна говорити і про домінуванні рядків).

стратегія Вj гравця В називається домінуючою над стратегією Вl (А стратегія Вl - домінованих стратегією Вj), Якщо всі елементи j-го стовпця платіжної матриці не більше відповідних елементів l-го стовпчика, т. е. a1j?a1l, a2j?a2l, ..., amj?aml (Тут також можна говорити і про домінуванні стовпців платіжної матриці).

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

Приклад 2.5. Знайдемо оптимальне рішення гри, заданої платіжною матрицею

Результати процесу відкидання домінованих стратегій відобразимо в таблиці:

В1 В2 В3 В4
А1  -2  -1
А2
А3  -1
А4

Коментарі:

1) Рядок А2 домінує над рядком А1 (4?3, 0?-2, 6?5, 1?-1); отже, рядок А1 відкидаємо (викреслюємо).

2) У частині матриці стовпець В2 домінує над стовпцями В3 и В4 (0 ? 6, -1 ? 3, 3 ? 7 і 0 ? 1, -1 ? 2, 3 ? 4); отже, викреслюємо стовпці В3 и В4.

3) Нарешті, в отриманій матриці рядок А2 домінує над рядком А3 (4?2, 2?-1); викреслюємо рядок А3.

Частина, що залишилася матриця

не має домінованих стратегій і відноситься до класу ігор 2х2.

Використовуючи формули (2.7), знайдемо оптимальні змішані стратегії гравців в отриманої грі, а також її ціну:

 = (3-1) / (4 + 3-1-0) = 2/6 = 1/3,  = 1-1 / 3 = 2/3,  = (3-0) / (4 + 3-1-0) = 1/2,

 = 1-1 / 2 = 1/2,  = (4 ? 3-0 ? 1) / (4 + 3-1-0) = 2.

Отже,  = (1 / 3,2 / 3),  = (1 / 2,1 / 2) - оптимальне рішення гри, заданої матрицею  . З огляду на викреслені домінованих стратегії гравців, запишемо оптимальне рішення вихідної гри: SA * = (0,1 / 3,0,2 / 3), SB * = (1 / 2,1 / 2,0,0). Ціна гри - та ж v * = 2.

3. Графічний метод рішення ігр 2хn і mх2.

Розглянемо детально випадок 2хn- Ігор. Нехай гравець А має в своєму розпорядженні дві чистих стратегії, а гравець В - n чистих стратегій. Матриця виграшів гравця А має вигляд:

.

Змішана стратегія гравця А задається вектором SА= (р1, р2), Де р1+р2= 1, р1?0, р2?0. покладемо р1=р, тоді р2= 1р, де рI [0, 1]. Тому SА= (р, 1р), Т. Е. Змішана стратегія гравця А однозначно визначається екоторие числом рI [0, 1].

Якщо гравець В застосує свою чисту стратегію Вj (j= 1, ...,n), То середній виграш гравця А в одній партії при використанні стратегії SA= (p,1p) Визначається виразом H(SA,Bj) =a1j?p+a2j? (1p) =zj(p) при всіх j= 1, ...,n ..

функції zj(p) - Лінійні функції на відрізку рI [0,1]. Зобразимо їх графіки на малюнку.

Кожній чистої стратегії Вj гравця В відповідає своя пряма Н=zj(p). Гравець В прагне до зменшення свого програшу. Отже, при фіксованій стратегії SA= (p, 1p) Його супротивника гравець В вибирає ту стратегію Вj, Для якої графік функції Н=zj(p) При даному р розташований нижче інших.

Таким чином, найменшим виграшами гравця А при несприятливих для нього діях гравця В відповідає нижня огинає всіх прямих Н=zj(p) на малюнку.

 
 


З іншого боку, метою гравця А є досягнення найбільшого гарантованого виграшу при будь-яких діях партнера. Значить, він буде вибирати ту стратегію SA * = (p *, 1p *), Яка визначається точкою р *, Відповідної максимуму нижньої огинаючої. Саме ця стратегія і є оптимальною для гравця А, а саме значення максимуму обвідної визначає ціну гри.

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

Випадок 1. Нижня огинає має рівно одну максимальну точку (р *, Н *). При цьому зауважимо, що якщо у вихідній матриці відсутні домінованих стратегії, то точка максимуму р * Є внутрішньою точкою відрізка [0, 1].

Отже, нехай р * I (0, 1). Тоді в піковій точці нижньої огинаючої перетинається не менше двох прямих, з яких одна має позитивний нахил, а інша - негативний.

Виділимо будь-яку пару таких прямих, наприклад, z=zk(p) і z= zl(p), Яким відповідають чисті стратегії Вk и Вl. Неважко показати, що для мінімізації власного програшу гравцеві В досить використовувати тільки ці стратегії, а від застосування інших чистих стратегій утриматися. Тим самим отримаємо допоміжну гру з платіжною матрицею:

(матриця  виходить з Н викреслюванням усіх стовпців, крім k-го і l-го). оптимальна стратегія SB= (q1, q2) Гравця В і ціна гри  в вийшла грі 2х2 можуть бути знайдені за допомогою формул (2.7). Тоді оптимальною стратегією гравця В в первісної задачі є стратегія SB * , в якій k-й і l-й компоненти дорівнюють відповідно q1 и q2, А інші компоненти дорівнюють нулю. Ціна  допоміжної гри збігається з ціною vS вихідної гри. Аналогічно можуть бути розглянуті і інші пари прямих, що проходять через пікову точку і мають разнознаковие нахили.

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

Випадок 2. Нижня огинає містить горизонтальну ділянку, відповідний відрізку [p1 *,p2 *] На осі абсцис.

 
 


 Тоді будь-яка стратегія виду SA * = (p, 1-p), де рI [p1 *,p2 *], Є оптимальною для гравця А. Гравець В володіє єдиною чистою стратегією, якої відповідає пряма, яка містить даний горизонтальну ділянку.

Приклад 2.6. Вирішимо гру з платіжною матрицею:

Спочатку спростимо матрицю за допомогою відкидання домінованих стратегій. стратегія В6 домінує над стратегіями В4, В5 и В7. Отже, викреслюємо 4-й, 5-й і 7-й стовпці. стратегія В2 домінує над стратегією В3. Тому 3-й стовпець матриці також можна відкинути.

Частина, що залишилася матриця

домінованих стратегій не має. Вирішимо гру, задану матрицею  , Використовуючи графічний метод.

Змішана стратегія А має вигляд SA= (p, 1-p). Складемо функції середніх виграшів гравця А за умови, що гравець В вибирає свої чисті стратегії , ,  грі з матрицею :

Н1= 0 ?p+ 13 ? (1p) = 13-13 ?p, Н2= 5 ?p+ 4 ? (1p) = 4 +p, Н3= 10 ?p+ 1 ? (1-p) = 1 + 9 ? p.

Побудуємо графіки цих функцій на відрізку рI [0, 1].

 
 


Виділяємо нижню огибающую цих графіків. Знаходимо найвищу точку цієї обвідної. Ця точка - результат перетину прямих Н= 13-13р и Н= 4 +р. Знайдемо її координати аналітично. Для цього вирішимо рівняння  13-13 ?р= 4 +р. Отримаємо 14 ?р= 9, звідки р * = 9/14 »0.642, 1р * = 5/14 »0.358. Отже, оптимальна змішана стратегія гравця А має вигляд SA * = (9 / 14,5 / 14).

підставляючи значення р * = 9/14 в будь-яку з функцій Н= 13-13р або Н= 4 +р, Знаходимо ціну гри vS = 13-13 ? 9/14 = 65/14 »4.642.

Знаходження оптимальної стратегії гравця В відповідає випадку 1. Розглянемо гру 2х2 з матрицею  , Стовпці якої відповідають прямим, що створює пік нижньої огинаючої. Знайдемо компоненти оптимальної стратегії  , Скориставшись формулами (2.7):

q1= (4-5) / (4 + 0-13-5) = 1/14 »0.074, q2= 1-1/14 = 13/14 »0.926.

Ціна гри  = (0 ? 4 + 13 ? 5) / (4 + 0-13-5) = 65/14 »4.642 збігається з раніше знайденою ціною vS. З огляду на викреслені стратегії гравця В, остаточно запишемо оптимальні стратегії гравців для вихідної гри SA * = (9 / 14,5 / 14), SB * = (1 / 14,13 / 14,0,0,0,0,0); ціна гри vS= 65/14.

рішення гри mх2 проводиться аналогічно. Перерахуємо лише основні етапи рішення. Нехай вихідна гра задається матрицею

.

Будемо шукати змішану стратегію гравця В в вигляді SВ= (q, 1q)

Для кожної стратегії Аi гравця А знаходимо середні виграші

H(Ai,SB) =ai1q+ai2(1q) (i= 1,2, ...,m).

Будуємо графіки цих виграшів на координатної площині.

виділяємо верхню огибающую побудованих графіків, відповідну найменш сприятливим для гравця В ситуацій.

відзначаємо точку мінімуму цієї обвідної q *, Яка визначає оптимальну стратегію гравця В; при цьому сам мінімум задає ціну гри v.

У матриці Н залишаємо два рядки, відповідні прямим, які брали участі в освіті мінімуму нижньої огинаючої.

Для отриманої гри 2х2 знаходимо оптимальну стратегію гравця А, застосовуючи формули (2.7).

Записуємо оптимальну стратегію гравця А, враховуючи викреслені рядки.

 Метод відомості матричної гри

до задачі лінійного програмування.

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

Нехай є гра mхn без сідлової точки і без домінованих стратегій, задана матрицею

.

Апріорно допустимо, що ціна цієї гри позитивна. Це значення заздалегідь невідомо, але, відповідно до властивості 2 з п.2.2, vS?a, де a - Нижня ціна гри. Так що при a> 0 умова vS> 0 виконано. Якщо ж a? 0, то виконання такого умови можна гарантувати, додавши, наприклад, до всіх елементів матриці Н число с> -a і отримавши матрицю Н ? нової гри. Відповідно до властивості 1 з п. 2.2, нова гра має те ж саме рішення, що і вихідна гра, а її ціна vS'=vS+c.

Отже, нехай vS> 0. Ми хочемо знайти дві оптимальні змішані стратегії SA * = (р1, ...,рm) і SB * = (р1, ...,рn), Що дають кожному гравцеві максимально можливі для нього середні виграші. знайдемо SA *. Уже відомо, що, якщо гравець А застосовує свою оптимальну стратегію, то гравець В не може поліпшити своє становище, відступаючи від своєї оптимальної стратегії: H(SA *,SB) ?H(SA *,SB *) =vS для всіх SB (Програш В буде не менше, ніж vS). Зокрема, якщо гравець В користується будь-якої чистої стратегією Вj, то:

H(SA *,Bj) =a1j?p1+ ... +amj? pm?vS при всіх j= 1, ...,n.

Отримаємо наступну систему нерівностей:

 (2.8)

Так як vS> 0, то при почленного розподілі лівих і правих частин нерівностей (2.8) на vS знаки нерівностей не зміняться. Вводячи, крім того, позначення xj=pj/ vS, Перепишемо систему (2.8) у вигляді:

 (2.9)

Умова р1+р2+ ... +рm= 1 рівносильно умові x1+x2+ ... +xm= 1 /vS.

але vS - Гарантований виграш гравця А. Метою гравця А в грі є максимізація цього значення і, отже, мінімізація вираження 1 /vS. Отримали наступну задачу лінійного програмування:

Знайти невід'ємні значення x1, x2, ..., xm, Які задовольняють лінійним обмеженням - нерівностям (2.9) і звертають в мінімум цільову функцію L=x1+x2+ ... +xm.

Отримана задача може бути вирішена, наприклад, симплекс-методом. нехай (x1 *,x2 *, ...,xm *) - Деяке рішення цього завдання, L * - Мінімальне значення цільової функції L . Тоді ціна гри vS= 1 /L *, А компоненти оптимальної стратегії гравця А рівні: pj * =xj * /L * (j= 1, ...,m).

Оптимальна стратегія гравця В знаходиться аналогічно. В результаті приходимо до задачі лінійного програмування, двоїстої до першої:

y1+y2+ ... +yn ® max

 (2.10)

Рішення (y1 *,y2 *, ...,yn *) Цього завдання і компоненти q1 *,q2 *, ...,qn * Оптимальної стратегії гравця В зв'язані співвідношеннями: qi * =yi * /L *, Де L * - Максимальне значення цільової функції завдання (2.10), що збігається з мінімальним значенням попереднього завдання.

Приклад 2.7. Знайти рішення гри, заданої матрицею

.

По-перше, зауважимо, що дана гра не має домінованих стратегій, так що скорочення розмірності матриці неможливо. Далі перевіримо, чи не має матриця седловую точку. Знайдемо нижню і верхню ціни гри:

,  . Так як a<b, То сідлова точка відсутня. Приступаємо до пошуку рішення гри в змішаних стратегіях, використовуючи метод відомості гри до задачі лінійного програмування.

Додамо до всіх елементів матриці Н модуль її найменшого негативного елементу, т. е. 2. Отримаємо матрицю

,

яка задає гру зі свідомо позитивної ціною vS?. Для знаходження оптимальної змішаної стратегії гравця А складемо наступну задачу лінійного програмування:

L =x1+x2+x3 ® min

 (2.11)

Для знаходження оптимальної стратегії гравця В складемо двоїсту задачу:

L1=y1+y2+y3 ® max

 (2.12)

Симплекс-методом зручніше вирішувати задачу (2.12). Опускаючи процес розрахунків цим методом, запишемо лише результат: у1 * = 1/4, у2 * = 5/4, у3 * = 0 - рішення задачі (2.12), максимальне значення цільової функції L1 * = 3/2. Звідси знаходимо компоненти оптимальної змішаної стратегії гравця В: q1 * = (1/4): (3/2) = 1/6, q2 * = (5/4): (3/2) = 5/6, q3 * = 0; ціна гри vS? = 1 /L1 *. При вирішенні задачі лінійного програмування симплекс-методом в підсумковій симплекс-таблиці міститься також і рішення двоїстої завдання, в нашому випадку - завдання (2.11): х1 * = 0, х2 * = 1/2, х3 * = 1. Враховуючи що L * =L1 *, Звідси отримаємо: p1 * = 0: (3/2) = 0, p2 * = (1/2): (3/2) = 1/3, p3 * = 1: (3/2) = 2/3. Відповідно до властивості 1 рішення матричних ігор (п.2.3), оптимальні змішані стратегії початкової гри збігаються зі знайденими оптимальними стратегіями: SA * = (0,1 / 3,2 / 3), SB * = (1 / 6,5 / 6,0). Ціна vS вихідної гри і знайдена ціна vS? допоміжної гри пов'язані співвідношенням vS? =vS+2. Тому vS= 2 / 3-2 = -4 / 3.

4.5. Ітераційний метод Брауна - Робінсон.

Основна ідея методу полягає в наступному.

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

Розглянемо реалізацію цього методу на прикладі.

Приклад 2.8. Знайти наближений розв'язок гри, заданої матрицею

.

Гра не має домінованих стратегій і тому не може бути зведена до гри меншої розмірності. Нижня ціна гри a= 4, А3 - Відповідна Максиміна стратегія гравця А; верхня ціна гри b= 6, В2 - Відповідна мінімаксна стратегія гравця В. Оформимо розрахунки методом Брауна у вигляді таблиці.

k Ai B1 B2 B3 Bj A1 A2 A3 v * v * vS
1 2 3 4 5 6 7 8 9  10  11  12
A3 4 * B3 8 *  4.00  8.00  6.00
A1  10 * B1  11 *  5.00  5.50  5.25
A1  13 * B1  20 *  4.33  6.67  5.55
A2  21 * B2  24 *  5.25  6.00  5.63
A2  24 * B3  28 *  4.80  5.60  5.20
A1  31 * B2  34 *  5.17  5.67  5.32
A1  37 * B1  39 *  5.29  5.86  5.58
A2  41 * B2  44 *  5.13  5.50  5.31
A3  46 * B2  49 *  5.11  5.37  5.24
A1  52 * B2  55 *  5.20  5.50  5.35
 ...  ...  ...  ...  ...  ...  ...  ...  ...  ...  ...  ...

тут:

· k - Номер партії (пари виборів гравцями своїх стратегій);

· Аi - Стратегія, обрана гравцем А в цій партії;

· В наступних трьох шпальтах - «накопичений виграш» за перші k партій при тих стратегіях, які застосовували гравці в попередніх партіях і при стратегіях В1, В2, В3 в даній партії (виходить додатком елементів відповідного рядка до того, що було рядком вище);

· З цих накопичених виграшів виділяється мінімальний (якщо їх декілька, то - будь-який з них), виділене число визначає відповідний вибір гравця В в даній партії - він вибирає ту стратегію, яка відповідає виділеному числу; таким чином, визначається оптимальна в даній партії стратегія Вj гравця В;

· В наступних трьох шпальтах дається накопичений виграш за k партій відповідно при стратегіях А1, А2, А3 гравця А (виходить додатком стовпчика Вj до того, що було рядком вище); з цих значень виділяється максимальна; воно визначає вибір стратегії гравця А в наступній партії;

· v *  - Нижня оцінка ціни, що дорівнює мінімальній накопиченому виграшу, поділеній на k;

· v *  - Верхня оцінка ціни гри, рівна максимальному накопиченому виграшу, поділеній на k;

· vS - середнє арифметичне v * и v * .

Розглянемо докладно кілька кроків методом Брауна в даній грі. В 1-й партії гравець А може вибрати будь-яку зі своїх чистих стратегій, але краще, якщо це буде Максиміна стратегія А3 (Вносимо цей вислів на 2-й стовпець). Цієї стратегії відповідає 3-й рядок матриці виграшів (7 5 4), відповідних стратегій В1, В2, В3 гравця В (заносимо їх в 3-й, 4-й і 5-й стовпці). Серед цих чисел виділяємо значком " * "Мінімальне. Воно відповідає найбільш вигідною для гравця В стратегії В3 в цій партії. Цієї стратегії відповідає 3-й стовпець платіжної матриці (8 2 4)Т. Заносимо ці значення в 7-й, 8-й і 9-й стовпці, виділяючи серед них значком *  максимальне, відповідне найбільшому виграшу гравця А. Тому на початку 2-й партії гравець А вибирає стратегію А1, Якій відповідає 1-й рядок (3 6 8) матриці Н. «Накопичений виграш» при цій та попередній стратегіях дорівнює (3 6 8) + (7 5 4) = (10 11 12). Саме ці значення і заносимо в 3-й, 4-й і 5-й стовпці. Мінімального з них значенням відповідає стратегія В1, Т. Е. 1-й стовпець (3 9 7)Т. З урахуванням передісторії «накопичений виграш» гравця А дорівнює (3 9 7)Т + (8 2 4)Т = (11 11 11)Т. Заповнюємо цими значеннями 7-й, 8-й і 9-й стовпці таблиці і т. Д.

У таблиці наведено перші 10 кроків методом Брауна-Робінсон. В результаті гравець А застосовував 5 разів стратегію А1, 3 рази - стратегію А2, 2 рази - стратегію А3; гравець В - 3 рази стратегію В1, 5 разів - стратегію В2, 2 - рази стратегію В3. Тому оптимальні стратегії гравців, наближено обчислені по відносним частотах використання своїх чистих стратегій, мають вигляд: SAp= (0.5, 0.3,0.2), SBp= (0.3,0.5,0.2).

Нижня і верхня оцінки ціни гри рівні відповідно v * = 5.2 і v * = 5.5 (обчислюються діленням відповідно мінімального та максимального накопичених виграшів (52 і 55) на кількість зіграних партій (10)). Наближена ціна гри vSp= (5.2 + 5.5) /2=5.35.

Після 20-ти кроків методом Брауна аналогічні результати виглядають наступним чином: наближені оптимальні стратегії SAp= (0.4,0.1,0.5), SBp= (0.25,0.6,0.15), наближена ціна гри vSp= 5.275. При цьому точне рішення гри, яке може бути отримано методом відомості гри до задачі лінійного програмування, має вигляд: SA * = (0.4,0,0.6), SB * = (0.2,0.8,0), vS= 5.4.

Виходячи з розглянутого прикладу і деяких теоретичних викладок, які ми опускаємо, можна зробити два висновки:

1) Метод Брауна дозволяє порівняно просто знаходити наближені рішення матричних ігор, причому трудомісткість методу зі збільшенням розмірності гри зростає незначно (на відміну від методу зведення гри до задачі лінійного програмування).

2) Відповідність наближених рішень, розрахованих методом Брауна, до точного розв'язання відбувається досить повільно.

2.5. Ігри з природою.

До сих пір розглядалися моделі таких конфліктних ситуацій, в яких противники були рівноправні і, прагнучи до протилежних цілей, однаково дотримувалися обережного принципу минимакса. Однак в реальній дійсності досить часто виникають якісно інші ситуації конфлікту двох сторін. Вони як і раніше формально описуються матрицею виграшу Н= ||аij||i= 1, ...,m,j= 1, ...,n одного з гравців (А), який, як завжди, вибирає свої стратегії свідомо, прагнучи до збільшення свого виграшу. Але другий гравець (В) особливий. Про нього відомо, що:

- Або він дотримується фіксованого змішаної стратегії SB= (q1, ...,qn) (Випадок стохастичною визначеності),

- Або про те, чим саме керується гравець В, взагалі нічого не відомо (випадок невизначеності).

Такі ситуації називаються «Іграми з природою», Гравець В ( «природа») найчастіше є не конкретна особа, а об'єктивну реальність. його стратегіями Вj служать стану «природи» (тип погодних умов, попит на певну продукцію і. т. п.). Метою дослідження такої гри є пошук розумних правил вибору гравцем А будь-кого зі своїх можливих стратегій.

Розглянемо деякі способи такого вибору в залежності від специфіки тієї чи іншої ситуації.

Випадок 1. Нехай змішана стратегія SB= (q1, ...,qn) «Природи» відома, т. Е. Відомі ймовірності їх станів В1, ...,Вn (Наприклад, на підставі статистичних даних).

Обчислимо середні виграші (математичні очікування) гравця А при застосуванні їм кожної з його чистих стратегій:

при А1 маємо Н(A1,SB) = a11?q1+ ... +a1n?qn = v1,

.................................................. .

при Аm маємо Н(Аm,SB) = am1?q1+ ... +amn?qn = vm.

Залишається порівняти отримані значення і вибрати серед них найбільше v * = Max (v1, ...,vm). Чистий стратегія Аi * , Що відповідає цьому значенню, є оптимальною для гравця А. При цьому неважко показати, що застосування будь-яких змішаних стратегій гравцеві А не вигідно, так як це може призвести тільки до зменшення середнього виграшу v *.

Випадок 2. Нехай стратегії «природи» невідомі, але вони як і раніше можуть бути змішаними, тобто. Е. Кількість партій з природою необмежено. Розглянемо два можливих підходи до вирішення цього завдання.

а) Принцип недостатнього підстави Лапласа. Якщо немає ніяких підстав вважати, що будь-яка стратегія «природи» має велику частоту, ніж будь-яка інша стратегія, то ми можемо припустити, що вірогідність всіх стратегій В1, ...,Вn однакові: q1= ... =qn= 1 /n. Тоді гіпотетичні середні виграші гравця А при використанні його чистих стратегій А1, ..., Аm визначаються відповідно рівностями:

v1L = 1 /n? (a11+ ... +a1n), ..., vmL = 1 /n? (am1+ ... + Amn).

Порівнюючи отримані значення, вибираємо серед них найбільше vL * = (v1L, ...,vmL). стратегія Аi * , Що відповідає цьому значенню, оголошується оптимальної.

б) Принцип минимакса. Інший можливий підхід пов'язаний з оцінкою «природи» як розумного, причому агресивного супротивника, який прагне зробити середній виграш гравця А як можна менше. У цьому випадку завдання пошуку оптимальної стратегії гравець А повинен вирішувати звичайними методами теорії матричних ігор, чому був присвячений попередній параграф.

Приклад 2.9. Сільськогосподарське підприємство планує посів трьох культур - А1, А2, А3. Вважаємо, що при інших рівних умовах врожаї культур залежать від погоди, а сама погода може мати 3 різних стану: В1- Посушливе літо, В2 - Нормальне літо, В3 - Дощове літо, Розрахунки прибутку с / г підприємства (в у. Е.) В залежності від станів погоди зведені в матрицю

.

Знайти оптимальну стратегію підприємства, якщо: а) ймовірності станів В1, В2, В3 погоди відомі q1= 0.2, q2= 0.3, q3= 0.5; б) дотримуватися принципу недостатнього підстави Лапласа; в) орієнтуватися на найменш сприятливу погоду.

Рішення. Відразу зауважимо, що в розглянутій платіжної матриці стратегія А1 доминируется стратегією А2 і, отже, може бути відкинута, як свідомо невигідна с / г підприємству.

а) У даному випадку змішана стратегія «природи» відома SB= (0.2,0.3,0.5). Знайдемо середні прибутку підприємства при використанні їм залишилися стратегій А2 и А3: H(A2,SB) = 8 ? 0.2 + 5 ? 0.3 + 3 ? 0.5 = 4.6, H(A3,SB) = 2 ? 0.2 + 3 ? 0.3 + 7 ? 0.5 = 4.8. Друге значення більше, тому слід вибрати стратегію А3.

б) У силу відсутності інформації про стани «природи», апріорно приймемо q1=q2=q3= 1/3. У разі використання стратегій А2 и А3 отримаємо такі оціночні «виграші»: v2L= 1/3 ? (8 + 5 + 3) = 16/3, v3L= 1/3 ? (2 + 3 + 7) = 4. Тут, навпаки, більше перше значення, і оптимальною стратегією є А2.

в) Орієнтація на найменш сприятливу погоду передбачає розгляд «природи» як розумного і рівноправного противника, прагнучого мінімізувати прибуток підприємства. Тому оптимальна стратегія підприємства може бути знайдена звичайними методами вирішення матричних ігор, наприклад, графічним методом. Опускаючи проміжні розрахунки, запишемо лише результат вирішення цієї «гри»: SA= (2 / 3,1 / 3) - оптимальна змішана стратегія підприємства, vS= 13/3 »4.33 - ціна« гри ». Інтерпретувати цей результат можна наступним чином: с / г підприємству рекомендується 2/3 всіх площ засіяти культурою А2 і 1/3 площ - культурою А3. При цьому можна гарантувати середню прибуток в 4.33 у. е.

Випадок 3. Припустимо, що, як і в випадку 2, нічого про станах природи невідомо. Однак гра з «природою» проводиться один лише раз, так що вживання змішаних стратегій ні гравцем А, ні «природою» не має сенсу. В цьому випадку при пошуку оптимального рішення найчастіше використовуються критерії Вальда, Севіджа і Гурвіца.

А) Критерій Вальда (максимина критерій).

Гравець А виходить з песимістичної оцінки ситуації і передбачає, що «природа» грає з ним в антагоністичну гру. Його мета --гарантірованний виграш або нижня ціна гри

Його оптимальна стратегія - Максиміна стратегія Аi * , При якій досягається W (Див. П.2.2).

Б) Критерій Севіджа (критерій мінімального ризику).

ризиком rij гравця А при користуванні стратегією Аi в умовах стану «природи» Bj називається різниця між максимально можливим виграшем гравця А при даному стані природи і виграшем аij при обраної стратегії Аi , Т. Е. rij= bj-aij, де  - Максимальний елемент в j-м стовпці. Ризик - це «плата за відсутність інформації». В результаті отримуємо матрицю, складену з чисел rij, - Матрицю ризику R.

Оптимальною стратегією за критерієм Севіджа є та стратегія Аi *  , При якій величина ризику має мінімальне значення в самій несприятливій ситуації:

В) Критерій Гурвіца (критерій врахування ступеня оптимізму).

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

де tI [0,1] - суб'єктивний показник оптимізму, зазвичай близький до 0,5.

Зауважимо, що при t= 0 (крайній песимізм!) Критерій Гурвіца переходить в критерій Вальда.

Приклад 2.10. Гра з «природою» задана матрицею

.

Знайдіть оптимальні стратегії, керуючись критеріями Вальда, Севіджа і Гурвіца з t= 0.6.

Для застосування перелічених критеріїв зручніше виконати попередні розрахунки в таблиці:

  В1 В2 В3 minj aij maxj aij
A1
A2
A3
A4
bj= maxi aij    

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

Знайдений максимум досягається при i= 3, т. Е., Виходячи з критерію Вальда, слід здійснювати стратегію А3.

б) Критерій Севіджа. Спочатку складемо матрицю ризиків R . Для цього визначаємо максимальні елементи в кожному стовпці матриці Н (Нижня рядок таблиці). Потім знаходимо елементи матриці R за формулою rij=bj-aij. Отримаємо матрицю:

.

потім знаходимо

Мінімум досягається при i= 2 і i= 3. Значить, за критерієм Севіджа оптимальними є стратегії А2 и А3.

в) Критерій Гурвіца з t= 0.6. Знайдемо мінімальні і максимальні числа в кожному рядку матриці Н (Останні два стовпці таблиці). Для кожного номера i= 1, 2, 3, 4 знаходимо значення:

 при t= 0.6.

маємо: G1= 0.4 ? 15 + 0.6 ? 30 = 24, G2= 0.4 ? 20 + 0.6 ? 75 = 53,

G3= 0.4 ? 25 + 0.6 ? 80 = 58, G4= 0.4 ? 5 + 0.6 ? 85 = 53.

Знаходимо максимальне з отриманих значень. це - G3= 58. Воно відповідає стратегії А3, Яке і є оптимальною за критерієм Гурвіца.

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

Список рекомендованої літератури.

Вентцель Е. с. Елементи теорії ігор. - М .: Наука, 1961.

Вентцель Е. с. Дослідження операцій. Завдання, принципи, методологія. - М .: Наука, 1980.

Воробйов Н. н. Теорія ігор. Лекції для економістів-кібернетиків. - Л., Изд-во Ленингр. ун-ту, 1974.

Зайченко Ю. п. Дослідження операцій. - Київ: Вища школа, 1986.

Замків О. о., Толстопятенко А. в., Черемних Ю. н. Математичні методи в економіці: Підручник. - М .: МГУ ім. М. в. Ломоносова, Изд-во «ДІС», 1998.

Дослідження операцій в економіці: Навчальний посібник / За ред. Кремера Н. ш. / - М .: Банки і біржі, ЮНИТИ, 1999..

Карлін С. Математичні методи в теорії ігор, програмуванні та економіці. - М .: Світ, 1964.

Косоруков О. а., Міщенко А. в. Дослідження операцій: Підручник. - М .: Іспит, 2003.

Моделювання марковських процесів і елементи теорії масового обслуговування: Методичні вказівки / Упоряд. М. б. Єрмолаєв. - Іваново: Іван. держ. хім.-технол. ун-т, 2005.

Нейман Дж., Моргенштерн О. Теорія ігор і економічна поведінка. - М .: Наука, 1970.

Оуен Г. Теорія ігор. - М .: Наука, 1971.

Економіко-математичні методи і моделі: Навчальний посібник / В. ю. Кисельов, Іван. держ. енерг. ун-т. - Іваново, 1998..

Елементи теорії ігор: Методичні вказівки / Упоряд. М. б. Єрмолаєв. - Іваново: Іван. держ. хім.-технол. ун-т, 2001..

 



Принцип міінімакса рішення матричних ігор. | Романіка
загрузка...
© um.co.ua - учбові матеріали та реферати