12.4. Розв'язування матричних ігор розміру 2x2 : Обгрунтування господарських рішень та оцінювання ризиків : B-ko.com : Книги для студентів

12.4. Розв'язування матричних ігор розміру 2x2

Розглянемо матричну парну гру розміру 2*2.

Таблиця 12.9

Матрична парна гра розміру 2x2

 

B1

B2

4

an

a12

4

a21

a22

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

А p

Р2

so —

sb —

Якщо матрична гра не має сідлової точки, то основною теоремою теорії ігор вона має хоча б одне оптимальне рішення, яке

SA —

визначається парою змішаних стратегій B1 B2

q0 q°2

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

А А~,

o12

дотримується своєї оптимальної стратегії SA — о о , то його

V pi p2 У

середній виграш буде дорівнювати ціні гри v , яку б активну стратегію не використовував б гравець В. Для гри розміру 2*2 будь- яка чиста стратегія є активною, якщо сідлова точка відсутня. Виграш гравця А (програш гравця В) представляє собою випадкову величину, математичне очікування якої дорівнює ціні гри. Тому середній виграш гравця А (оптимальна стратегія) буде дорівнювати v для першої і другої стратегій гравця В.

Той же самий виграш отримає гравець А, якщо гравець В буде використовувати чисту стратегію B2, тобто a12p0° + a22p20 — v .

(12.10)

(12.11)

(12.13)

гравця Б, отримаємо, що при

Оскільки рО + рО = 1, то отримаємо систему рівнянь для знаходження оптимальної стратегії SA і ціни гри v :

й11 Pl + й21 Р° = V, й12 Pl + й22 Р2 = v, Pl + р = 1.

Розв'язуючи систему (2.3.1), отримаємо значення шуканих ймовірностей

р1 =

йп І й22 й12 й21

р2 =

йи І й22 й12 й21

і ціни гри

— /

v = йц І й22 й12 й21

Використовуючи теорему про активні стратегії при знаходженні

^B1 B24

оптимальної стратегії SB =

q2 У

(12.14)

використанні будь-якої чистої стратегії гравця А середній програш гравця Б дорівнює ціні гри v , тобто

anq1° + a^ = v, a21ql + a22ql = v, ql + q°2 = 1.

Звідки отримаємо значення шуканих ймовірностей     329

-»о

4і       _ _

і і a^^ aa л a^ і

11 22 12 21          (12.15)

qo _   a11 _ a21   

an і $22 $12 $21

Приклад 12.4. Знайти рішення матричної гри, платіжну матрицю якої побудовано в прикладі 12.1. Розв

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

у додатковий стовпчик min a у.

j i

Таблиця 12.10 Платіжна матриця гри про вибір сторони монети

 

B1

B2

min ay

у 1

A\

1

-1

-1

A,

-1

1

-1

max ay

i 1

1

1

 

З найдених чисел виберемо найбільше за формулою (12.5) а_ maxa _ max{_1,_1}__1, що визначає нижню ціну гри або максимін, тобто максимальний виграш, який гравець А може собі гарантувати в грі, що розглядається. Цей виграш відповідає стратегіям A1, A2. Тобто кожна стратегія фірми А є максимінною.

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

З найдених чисел виберемо найменше за формулою (12.6) в_ minву _ min {1,1}_ 1, що визначить верхню ціну гри або мі- німакЬ, тобто мінімальний програш, який гравець В може собі дозволити в грі, що розглядається, який відповідає стратегіям B1 , B2 . Ці стратегії є мінімаксними.

Верхня і нижня ціни гри не співпадають: vnH Ф ущ , тому цю гру можна розв'язати в змішаних стратегіях.

Для гравця А середній виграш дорівнює ціни гри v і система

o А    А-2

(12.10) для знаходження його оптимальної стратегії SA = 0 0

V po  Роj

(12.16)

має вигляд:

-о-p + о-p = v,

0-РоО -0-РО = v,

рО + рО = о.

Для гравця В середній програш дорівнює ціні гри v і система

qO q°2

(12.17)

B0 B2

(12.14) для знаходження його оптимальної стратегії S°B = має вигляд:

-0-qO + 0-q°2 = v, 0-qO -0-q°2 = v, q0 + q°2 = 0.

Розв'язавши системи (12.16) і (12.17), отримаємо pl = pO = ql = q2 = 0 , v = 0 , тобто оптимальні змішані стратегії

 

f А

А і

 

f B0

B2 і

гравців такі SAo =

0

0

і SB =

0

0

 

V 2

2.

 

V 2

2.

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

1

ймовірностями — , при цьому середній виграш дорівнює нулю.

'1       4        3        0        10л

3        6        7        1        9

4        3        0        10

3        6        5        4

Розв  Скоротимо розмірність платіжної матриці. Стра

тегії А1 і А3 гравця А співпадають, тому виключимо стратегію А3:

'1 4 3 0 10Л

3 6 7 1 9 2 3 6 5 4

Стратегії В5, В3 і В2 гравця В домінують стратегію В1, тому їх можна виключити з платіжної матриці:

' 1 0Л

3 1

.2 5,

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

' 3 1л 2 5

За алгоритмом знаходження максиміну (мінімаксу) знаходимо нижню та верхню ціни гри.

За формулою (12.5) маємо vm _ max{1, 2} _ 2. За формулою

(12.6) маємо v _ min{3, 5} _ 3 . Верхня і нижня ціни гри не

j

Приклад 12.5. Розв'язати матричну гру

співпадають vHH Ф ve4, тому цю гру можна розв'язати в змішаних стратегіях.

3 - 5 - 0-2 03

За формулою (12.13) знайдемо ціну гри v = -—-—-—— = — = 2,6.

За формулами (12.11) знайдемо ймовірності чистих стратегій гравця А:5 - 2

2

= - = 0,6 , p4 =   = - = 0,4

3 - 0

Р2 =

3 + 5 - 0 - 2 5      4 3 + 5 - 0 - 2 5тому оптимальна стратегія гравця А така

'4 А2 А3 А4 Л

0 0,6 0 0,4у

За формулами (12.15) знайдемо ймовірності чистих стратегій гравця В:

5-0 4 ЛО     3 - 2 0 _

q0 = . _ ,—- = - = 0,8 , q4 = -—:—:—- = - = 0,2.

3 + 5 - 0 - 2 5      3 + 5 - 0 - 2 5

So = sb =

тому оптимальна стратегія гравця В така

ґ B0 В2 B3 B4 В5 Л v0,8 0 0 0,2 0