8.4. Матрична гра двох гравців з нульовою сумою


Повернутися на початок книги
1 2 3 4 5 6 7 8 9 10 11 12 13 14 
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 
60 61 62 63 64 65 66 67 

Загрузка...

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

Гра, що розглядається, може повністю визначатися матрицею:

 

п

A

 

 

п

\п

а\і

\   '•.   ;   '•.   :

аі)

 

ат

\   '•.   ;   '•.   :

 

 

 

ml

 

 

 

щі

 

 

 

де стратеш першого гравця позначені номерами відповідних ря-дків: 1, 2,..., т; стратегії другого гравця— номерами стовпчиків 1, 2,..., п. Якщо кожний з гравців вибирає з імовірністю 1 деяку стратегію, то говорять, що він користується чистою стратегі-єю. Через atj позначено виграш першого гравця, якщо він обере

свою чисту /-ту стратегію, а його супротивник — свою чисту j -ту стратегію. Виграш другого гравця за цієї умови складе вели-чину, яка протилежна до виграшу першого гравця, тобто виграш другого гравця дорівнюватиме у цій ситуації (- atj).

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

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

 

^

 

і=1,т

 

ДЄ

 

а =тш

ШІац \,   і = \,т.

Значення а = а;* називається нижньою ціною гри:

a = max mm

w

a  стратегія  /* —   максимінною стратегією  першого граеця. Нижня ціна гри — гарантоеаний еиграш першого граеця при

будь-якій стратегії другого.

Якщо виконати аналогічні міркування з позицій другого грав-ця, дійдемо до еерхньоїціни гри р :

P=minmax{a },

j        і

а також до мінімаксної стратегії j* другого граеця, яка від-повідає умовам:

Р=Ру.=пш(ру},

ДЄ

Р - = maxW-},    j = \,п .

Верхня ціна гри— гарантоеаний програш другого граеця

при будь-якій стратегії першого.

У випадку, коли нижня ціна гри збігається з верхньою:

а = р,

відповідні чисті стратегії /'* та j* вважаються оптимальними стратегіями гравців, а про гру кажуть, що вона має сідлоеу то-оскільки елемент аіу„ матриці А задовольняє умову:

тіп{аг<7} = a^j, = тах{ау„}.

У випадку, коли нижня ціна гри менша від верхньої ціни гри:

а<р,

тоді гравці застосовують змішану стратегію.

Якщо перший гравець вибирає одну з стратегій \А\. Г— ВІДПО-

відно до розподілу ймовірностей Р = {РІ) , деpi — імовірність ви-бору стратегії АІ то говорять, що він застосовує змішану страте-гЬо.   Аналогічно   g ■ - -  імовірність  того,   що   другий  гравець

вибирає стратегію В-. P = {pj) і Q = [gj} називаютьсязмішаними

стратегіями I і II граеціе, а очікувании виграш першого гравця визначається співвідношенням:

— —\       т    п

M{P,Q) називається платіжною функцією.

Сформулюємо осноену теорему теорії матричних ігор.

Кожна матрична гра з нульовою сумою має розв'язок в чистих

або змішаних стратегіях, тобто існують такі PQ , Q0, що M[P,Q0J< M\Po,Q0J< M\Po,QJ, тобто \Po,Q0J є сідловою точкою платіжної функції М\Р, QJ.

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

Змішану стратегію першого гравця позначимо вектором х = (х1,.,.,хт), компоненти якого означають імовірності, з якими перший гравець визначатиме свою чисту стратегію. За аналогі-єю  змішану  стратегію  другого  гравця  позначимо  вектором

у = (уї,-..,у„) = іуі,---, уп), компонентиякого означають імовірно-сті вибору ним своєї чистої стратегії.

Оптимальна стратегія першого гравця х* визначається розв'язуванням задачі лінійного програмування виду:

v —> max,

aljxl+--- + amjxm>v,    j = \,n,

х1 ч     \- хт =1,

х. > 0,   г= 1,т.

Оптимізаційна задача для визначення оптимальної стратегії у* другого гравця має вигляд:

w —> min,

аі\У\ Л V аіпУп — W>   І = 1' т>

У\ л—v Уп = і> У І - 0,    j = 1, п.

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

а їх спільне значення називається ціною гри.

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

Приклад 8.2. Матриця гри двох осіб задана табл. 8.5. Визна-чити оптимальну стратегію гри та її ціну.

Таблиця 8.5

 

 Bj       В\        Ві         Вг        І>4      Оі

А\        1          2          3          4          1

А2       5          ш         7          3          3

А3       4          2          3          1          1

аі         5          3          7          4         

 

a,- max a. = 3

г=1,3

 

mma. =

/=1,4

 

3

 

mina =maxa =3.

7=1,4

 

Оптимальна стратегія А2-В2, сідлова точка а22, ціна гри до-рівнює 3.

Припустимо, що перший гравець не вибрав стратегію А2, а ви-брав Аз, яка обіцяє йому виграш 4, але тоді другий може вибрати стратегію В^, і перший одержить виграш, рівний 1. Аналогічно припустимо, що другий не вибирає стратегію В2, при якій він програє 3, а надає перевагу стратегії В\, при якій його програш може бути рівним 1. Але в такому випадку перший може вибрати стратегію А2, при якій другий програє 5. Таким чином, відмова від стратегії сідлової точки тільки зменшує виграш першого гра-вця і збільшує програш другого гравця.