12.2. Принцип мінімаксу (максиміну).

магниевый скраб beletage

Розв'язок матричної гри в чистих стратегіях

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

Алгоритм знаходження максиміну (мінімаксу)

В рядку платіжної матриці, що відповідає стратегії A , знайти мінімальне з чисел а„: а = min а„, У = 1,n .

у 1     і U ? J 7

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

Серед всіх чисел а вибрати найбільше число а, яке визначається за формулою

а = maxa = maxminау, j = 1,n,i = 1,m , (12.5)

i i j '

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

4. Серед всіх чисел fij вибрати найбільше число в, яке визначається за формулою

в= mmfi. = minmaxaij, j = l,n,i = 1,m , (12.6)

j j j i [1]

і називається верхньою ціною гри або мінімаксом v .

Мінімакс - це мінімальний програш, який гравець В може собі дозволити в грі проти розумного противника.

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

Стратегія, яка відповідає мінімаксу називається мінімаксною.

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

Приклад 12.3. Проаналізувати платіжну матрицю, яку побудовано у прикладі 12.2. Визначити верхню і нижню ціну гри.

Платіжна матриця гри

Розв' язання. Запишемо платіжну матрицю у вигляді таблиці 12.3.

Таблиця 12.3

 

А

B2

B3

B4

Bs

A

2,5

1

2

3

4

A

4

2

1

2

3

A3

3

3

1,5

1

2

A4

2

2

2

1

1

As

1

1

1

1

0,5

Платіжна матриця гри без стратегії B1

Проаналізуємо гру з боку фірми В, яка контролює стовпці платіжної матриці. Перший стовпець, що відповідає стратегії B1 , є гіршим ніж інші, оскільки фірмі В він несе найбільший програш. Фірмі В стратегію B1 не зручно застосовувати (говорять, що це домінуюча стратегія), тому її можна виключити з платіжної матриці:

Таблиця 12.4

 

B2

B3

B4

B5

A

1

2

3

4

A

2

1

2

3

A3

3

1,5

1

2

A4

2

2

1

1

A

1

1

1

0,5

Проаналізуємо гру з боку фірми А, яка контролює рядки платіжної матриці. Останній рядок, що відповідає стратегії A5 є гіршим ніж інші, оскільки фірмі А він несе найменший виграш. Фірмі А стратегію A не зручно застосовувати, тому її можна виключити з платіжної матриці:

Таблиця 12.5 Платіжна матриця гри без стратегій B1, A5

 

B2

B3

B4

B5

A1

1

2

3

4

A2

2

1

2

3

A3

3

1,5

1

2

A4

2

2

1

1

Фірма В не буде застосовувати стратегію B5, оскільки вона домінується стратегією B4, при виборі якої програш цієї фірми менше. Тому стратегію B5 можна виключити з платіжної матриці:

Таблиця 12.6

Платіжна матриця гри без стратегій Bl, A5, B5

 

B2

B3

B4

4

1

2

3

a2

2

1

2

A3

3

1,5

1

A4

2

2

1

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

j j

Таблиця 12.7 Платіжна матриця гри без стратегій Bl, A5 , B5

 

B2

B3

B4

min a „

j j

4

1

2

3

1

4

2

1

2

1

A3

3

1,5

1

1

 

2

2

1

1

max a j

j

3

2

3

 

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

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

З найдених чисел виберемо найменше за формулою (12.6) в= \>вц = min в у = min {3, 2, 3} = 2 , що визначить верхню ціну гри або мінімаїкс, тобто мінімальний програш, який фірма В може собі дозволити в грі, що розглядається, який відповідає стратегії B3 . Ця стратегія є мінімаксною.

Таким чином, скоротити розмірність платіжної матриці можна: виключенням однакових рядків чи стовпців; виключенням більших стовпців виключенням менших рядків.

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

Якщо верхня і нижня ціни гри співпадають, то загальне значення v = v = v називається чистою ціною гри або ціною гри, а така гра називається визначеною грою в чистих стратегіях або грою з сідловою точкою.

Чистою стратегією A гравця А називається можливий хід, який гравець А обрав з ймовірністю 1.

Ціна гри v дорівнює елементу платіжної матриці (а у). Елемент (а,-у) є одночасно мінімальним в рядку i0 платіжної матриці, максимальним в стовпці у0 платіжної матриці і називається сідловою точкою. Сідловій точці відповідають оптимальні стратегії, сукупність яких є оптимальним рішенням або рішенням матричної гри.

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

Приклад 12.4. Визначити верхню і нижню ціни гри, яку задано

ґ3 2 5 7Л 5 4 6 5 2 3 16

Розв  Запишемо платіжну матрицю у вигляді таблиці

12.8.

Таблиця 12.8

Платіжна матриця гри

 

A

B2

B3

B4

min a„

j i

Ai

3

2

5

7

2

A2

5

4

6

5

(4)

A3

2

3

1

6

1

max a j

i j

5

(4)

6

7

 

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

minйу. З найдених чисел виберемо найбільше за формулою (12.5)

j '

vm = а = max а = max {2, 4,1} = 4 , що визначить нижню ціну гри

або максимін. Цей виграш відповідає стратегії A2, яка є макси- мінною.

матрицею

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

З найдених чисел виберемо найменше за формулою (12.6)

vm = в = minву = min {5, 4, 6, 7} = 4 , що визначить верхню ціну гри або мінімакс, який відповідає стратегії B2 . Ця стратегія є міні- максною.

Верхня і нижня ціни гри співпадають, тобто vm = v = 4 . Досягається це на одній і тій же парі стратегій (A2, B2) = 4 . Значить гра має сідлову точку (A2, B2) і ціна гри дорівнює v = 4 .