3. Методи розв'язку парних стратегічних ігор

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

Алгоритм розв'язку стратегічної гри в загальному вигляді складається з таких кроків.

1. Визначення варіантів власної поведінки — стратегій гравця А.

2. Визначення варіантів поведінки свого опонента — стратегій гравця В.

3. Оцінювання наслідків для всіх варіантів комбінацій власних стратегій та стратегій конкурента — побудова платіжної матриці D.

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

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

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

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

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

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

Отже, як видно з наведеного алгоритму, є два основних методи розв'язання стратегічних ігор — у чистих і в змішаних стратегіях. При цьому кроки з 1 по 4 є спільними для обох методів, оскільки перш ніж намагатися розв'язувати гру в змішаних стратегіях, слід перевірити неможливість розв'язання в чистих стратегіях.

3.1. Розв'язок гри в чистих стратегіях

Припустимо, що гравець А має m можливих варіантів поведінки (стратегій). Позначимо їх А_І;А₂, ...,А_m. Кількість стратегій гравця А має бути не меншою 2 ( ).

Нехай за результатами аналізу також з'ясовано, що наш опонент, гравець В, має n можливих варіантів поведінки (стратегій): В₁, В₂, ..., В_n. Кількість стратегій гравця В також має бути не меншою 2 ( ).

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

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

Коли набір стратегій для кожного з гравців сформовано, можна будувати платіжну матрицю гри. Рядки цієї матриці відповідають стратегіям гравця А, і позначаються А_i, . Стовпчики цієї матриці відповідають стратегіям гравця В, і позначаються В_j, .

На перетині кожного i-го рядка матриці та j-го стовпчика розміщуються елементи d_ij, що для матриці виграшів показують фінансовий результат, який отримає гравець А від застосування стратегії А_i, тоді як його опонент обрав стратегію В_j. Якщо це число додатне, то гравець А отримує виграш в розмірі d_ij, якщо від'ємне — то програш (зазнає збитків). Відповідно нульове значення елемента платіжної матриці означатиме, що гравець А, як і гравець В, не отримає ні виграшу, ні програшу.

У схематичному вигляді платіжну матрицю наведено в табл. 8.1.

Таблиця 8.1.

Загальний вигляд платіжної матриці

A	B1	B2	...	Bn
B
A1	d11	d12	...	d1n
A2	d21	d22	...	d2n
...	...	...	...	...
Am	dm1	dm2	...	dmn

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

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

Алгоритм пошуку нижньої ціни гри.

Фіксується перший рядок і з усіх його елементів знаходять і запам'ятовують найменше значення.

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

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

Алгоритм пошуку верхньої ціни гри.

1. Фіксується перший стовпчик і з усіх його елементів знаходять і запам'ятовують найбільше значення.

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

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

Коли верхня і нижня ціна гри визначені, слід перевірити, чи наявна в матриці сідлова точка .

Проілюструємо наведений матеріал на прикладі.

Завдання. Припустимо, що ми маємо антагоністичну гру. Гравець А має три стратегії, В — чотири. Нехай змістовна частина гри проаналізована і на основі цього побудована платіжна матриця, наведена в таблиці 8.2.:

Таблиця 8.2.

A	B1	B2	B3	B4
B
A1	40	0	-25	35
A2	-30	-15	30	0
A3	15	10	20	25

Визначити можливість розв'язання гри в чистих стратегіях.

Розв'язок

Спочатку визначимо нижню ціну гри.

1. Знайдемо і зафіксуємо мінімальний елемент з першого рядка. Це елемент d₁₃ = -25.

2. Знайдемо мінімальні елементи з другого і третього рядків. Це елементи d₂₁ =-30 та d₃₂ = 10 відповідно.

3. З обраних елементів знайдемо найбільший.

Таким чином, нижня ціна гри дорівнює 10. Це означає, що в разі вибору гравцем А стратегії А₃ за будь-яких варіантів поведінки гравця В, гравець А забезпечить собі виграш не менше ніж 10.

Тепер визначимо верхню ціну гри.

1. Знайдемо і зафіксуємо максимальний елемент з першого стовпчика. Це елемент d₁₁ = 40.

2. Знайдемо максимальні елементи з другого, третього і четвертого стовпчиків. Це елементи d₃₂ = 10, d₂₃ = 30 та d₁₄ = 35 відповідно.

3. З обраних елементів знайдемо найменший.

Таким чином, верхня ціна гри теж дорівнює 10, тобто в разі вибору гравцем B стратегії В₂ за будь-яких варіантів поведінки гравця А, він В не програє більше ніж 10.

Таким чином, Це означає, що між сторонaми А і В виникає раціональний компроміс, який полягає в тому, що гравцю А слід обрати стратегію А₃, а гравцю В — стратегію В₂ відповідно. В результаті гравець А отримає виграш в 10 одиниць, а гравець В — програє в таких самих обсягах. Раціональність цього компромісу полягає в тому, що гравець, який в односторонньому порядку порушує рівновагу і відхиляється від оптимальної стратегії, гарантовано погіршить своє становище (отримає або менший виграш, або ще більші збитки). Отже, наведена гра має розв'язок у чистих стратегіях і цей розв'язок знайдено.