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

Мішаною стратегією S_А гравця А називається застосування чистих стратегій А₁, А₂,…, А_m з ймовірностями p₁, p₂,…, p_m. При цьому очевидно, що .

Мішані стратегії гравця А записують у вигляді матриці

або .

Аналогічно, мішані стратегії гравця В позначаються так:

або .

Чисті стратегії можна вважати окремим випадком мішаних у випадку, коли чистій стратегії відповідає ймовірність 1, а ймовірність інших стратегій дорівнює 0.

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

a ≤ v ≤ b.

Введемо в розгляд функцію виграшу

Гравець А орієнтується на найгірше, тобто на втрати, що дорівнюють мінімуму функції виграшу F(S_A,S_B) по всім стратегіям гравця В, тобто грає роль a_i.

Тоді найкращою стратегією для гравця А є та, на якій буде досягнуто – це грає роль a.

Аналогічно для гравця В найкращою стратегією буде та, на якій буде досягнуто – це грає роль b.

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

На це питання дає відповідь основна теорема теорії ігор – теорема Неймана.

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

З цієї теореми випливають наступні висновки:

Теорема 1 Стратегії оптимальні тоді і тільки тоді, коли виконується умова

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

Перш ніж сформулювати другу теорему, що випливає з основної теореми, дамо наступне означення.

Стратегії, які входять до складу оптимальних мішаних стратегій з ненульовими ймовірностями, називаються активними стратегіями.

Теорема 2 Якщо гравець В застосовує оптимальну мішану стратегію , а гравець А застосовує активну стратегію А_і, то . Аналогічно,

Ігри 2x2

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

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

Нехай платіжна матриця має вигляд

Для того, щоб знайти оптимальні мішані стратегії , скористуємося теоремою 2.

Ми одержали систему рівнянь для визначення p^* і v. Аналогічним чином шукаємо стратегію :

Звідси вже можна знайти q^* і шукати вже не потрібно.

Приклад. Розв’язати гру «вірю – не вірю».

Правила цієї гри розглянуті в 6.1 і там же знайдена платіжна матриця цієї гри

Розв’язання. Оптимальні мішані стратегії гравця А – , гравця В – , a=0, b=1. Тоді

Розв’язуючи цю систему рівнянь, знаходимо

Тоді

Таким чином, оптимальні мішані стратегії гравців А і В такі:

Ціна гри дорівнює 0,2. Це означає, що гравець А в шести випадах з 10 має казати «правду», а в решті 4 – «неправду». Гравець В у восьми випадках з 10 має «вірити», а в решті – не вірити. Середній виграш в цій грі дорівнює

0,2 грн.

5.4 Геометрична інтерпретація гри

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

Мішані стратегії гравців

За теоремою 2 маємо:

З точки зору геометрії маємо рівняння двох прямих в системі координат (p,v):

v = a₁₁p + a₂₁(1–p),

v = a₁₂p + a₂₂(1–p).

Побудуємо графіки цих прямих.

Гравець А розраховує на min(F(S_A,B₁), F(S_A,B₁)) – жирно виділена ламана на графіку. Він гарантовано одержує виграш на цій ламаній і, очевидно, вибирає на ній найвищу точку. Координати цієї точки (p^*,v) задають ціну гри v і оптимальну мішану стратегію гравця А:

Для гравця В за теоремою 2 маємо:

Так само в системі координат (q,v) побудуємо прямі

v = a₁₁q + a₁₂(1– q)

v = a₂₁q + a₂₂(1– q)

Гравець В розраховує на max(F(A₁,S_B), F(A₂,S_B)) – жирно виділена ламана на графіку. Він гарантовано одержує програш на цій ламаній і, очевидно, вибирає на ній найнижчу точку. Координати цієї точки (q^*,v) задають ціну гри v і оптимальну мішану стратегію гравця B:

Приклад. Розв’язати геометрично гру з платіжною матрицею

Будуємо відповідні прямі

Знайдемо координати точки перетину прямих

2p–3(1–p) = –p+4(1–p),

10p = 7, p^*=0,7,

v = 2·0,7–3·0,3=0,5.

– оптимальна мішана стратегія гравця А.

Для гравця В

3q=1,5, q^*=0,5.

– оптимальна мішана стратегія гравця B.

Ціна гри v=0,5.

5.5 Розв’язання ігор та

Такі ігри мають наступні платіжні матриці:

Ці ігри краще за все розв’язувати геометрично.

Для визначеності розглянемо гру і застосуємо теорему 2, враховуючи, що мішана стратегія гравця А має вигляд

Тоді

… ,

Далі будуємо графіки всіх прямих і обираємо нижню ламану, тобто ламану min(F(S_A,B₁), F(S_A,B₁),…, F(S_A,B_n)), а потім найвищу точку цієї ламаної. Її координати (p^*,v) задають ціну гри v і оптимальну мішану стратегію гравця А. Відрізки цієї ламаної відокремлюють також і активні стратегії гравця В. Решта стратегій не грають ніякої ролі. На активних стратегіях гравця В шукаємо, знаючи ціну гри v, оптимальну мішану стратегію .

Аналогічно розв’язується і гра , але в ній обирають верхню ламану max(F(A₁,S_B), F(A₂,S_B),…, F(A_m,S_B)), а в ній найнижчу точку та її координати.

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

Розв’язання. Перш за все зауважимо, що стратегія А₂ є більш вдалою, ніж А₁ і А₄. Тобто зрозуміло, що А₁ і А₄ – неактивні стратегії, і платіжна матриця стає такою:

, .

Застосуємо теорему 2.

Будуємо відповідні прямі

Нижня точка виділеної ламаної знаходиться на перетині ліній і , тобто стратегії А₂ і А₃ є активними. Розв’яжемо систему відповідних рівнянь

2q+1=-5q+3, 7q=2,

Таким чином, оптимальна мішана стратегія гравця В має вигляд

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

Тоді

, , .

Таким чином, оптимальна мішана стратегія гравця А

Ціна гри .

5.6 Розв’язання ігор

Ігри можуть бути розв’язані трьома методами:

1) розв’язанням відповідних систем лінійних рівнянь;

2) методами лінійного програмування;

3) наближеними методами.

Розглянемо кожен з методів окремо.

І Метод розв’язання системи лінійних рівнянь.

Розглянемо приклад – гру «монетка під пару». Правила гри. Кожний з двох гравців має монети 5, 10, 25 коп. За командою обидва гравці показують свої монети. Якщо монети однакові, тоді вони переходять гравцю А, якщо різні – гравцю В. Розв’язати гру.

Розв’язання. Складемо матрицю платежів цієї гри. Кожен гравець має три стратегії: А₁ – 5 к., А₂ – 10 к., А₃ – 25 к., теж саме для гравця В. Тоді

Мішана стратегія гравця А

Складаємо систему рівнянь

Розв’язуючи цю систему рівнянь, одержимо

Таким чином, оптимальна стратегія гравця А така:

Перейдемо до гравця В.

Складаємо систему рівнянь

Розв’язуючи цю систему рівнянь, одержимо

і , ціна гри .

ІІ Зведення матричної гри до задачі лінійного програмування.

Якщо в матриці платежів є від’ємні елементи, то потрібно додати до кожного елемента матриці таке число, щоб всі елементи стали додатними. Розв’язувати гру методом лінійного програмування потрібно за новою матрицею, а потім від ціни гри відняти те число, яке додавали до елементів матриці.

Гравець А застосовує стратегію , а гравець В відповідає стратегією В_j.

Тут v>0 – ціна гри за новою матрицею.

Розділимо обидві частини нерівностей на v і введемо позначки

де x_i ≥ 0, i=0,1,…,m.

Гравець А намагається збільшити ціну гри v. Тоді одержуємо таку задачу лінійного програмування:

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

де .

ІІІ Наближений метод розв’язання ігор .

Розглянемо наближений метод, що має назву метод Брауна–Дж.Робінсон. Він складається з наступного. Проводиться багато партій гри, причому на кожному n–му кроці сторона В вибирає таку свою чисту стратегію, яка найкращим чином протидіє накопиченому виграшу сторони А при перших (n–1) ходах. Аналогічним чином діє і сторона А при виборі своєї стратегії.

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

Літерою «с» позначимо виграш. Якщо зустрінуться однакові числа «с», то будемо вибирати стратегію з меншим номером (за нижчеподаною таблицею).

N партії к	Вибір А_і	Сумарний виграш гравця А при стратегіях В_j		Вибір B_j	Сумарний виграш гравця B при стратегіях A_i
B₁	B₂	B₃	A₁	A₂	A₃
	A₃					B₁					4,5
	A₁	1+8	7+2	3+4		B₃		4+6	1+3
	A₁	9+8	9+2	7+4		B₂	12+2		4+7
	A₂		16			B₂					4,5
	A₂		21		4,2	B₂					4,6
	A₂		26			B₂
	A₃	30				B₁
	A₂	34				B₁					4,5
	A₂	38				B₁
	A₁		45		4,5	B₂				4,7	4,6

Зроблено 10 кроків задачі. Послідовність чисел в останньому стовпці збігається до ціни гри.

За 10 кроків стратегія А₁ зустрілась 3 рази, А₂ – 5 разів, А₃ – 2 рази, В₁ – 4 рази, В₂ – 5 разів, В₃ – 1 раз. Тоді емпіричні оптимальні мішані стратегії на 10 кроках такі:

, .

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

Питання для самоперевірки

1 Що таке матрична гра?

2 Шо таке платіжна матриця?

3 Що таке нижня та верхня ціна гри, зв'язок між ними?

4 Що таке функція виграшу?

5 Що називається ціною гри?

6 Наведіть основну теорему теорії гри.

7 Що таке мішана стратегія?

8 Що таке чиста стратегія?

9 Що таке активна стратегія?

10 Сформулюйте основну теорему теорії гри.

11 Як розв’язується гра 2x2?

12 Дати геометричну інтерпретацію гри 2x2.

13 Як застосовується геометрична інтерпретація для розв’язання ігор 2xn і mx2?

14 Які існують методи розв’язання ігор mxn?

Задачі для самостійної роботи

1 Побудувати платіжну матрицю для гри за наступним правилом.

Кожний з двох гравців має 3 монети номіналом 5; 10; 25 копійок. Обидва гравця одночасно показують по одній монеті. Якщо монети однакові, то вони переходять до першого гравця, якщо різні − до другого.

2 Гра полковника Блотто.

Полковник має 5 полків і захищає дві рівноцінні позиції. Його противник має 4 полки і атакує ці позиції. Кожний з противників може виділити цілу кількість полків. Полковник виграє 1 грошову одиницю, якщо на кожній з позицій зосередить не менше полків, ніж його противник. У всіх інших випадках він програє 1 грош. одиницю. Скласти матрицю гри.

3 Розв’язати гру при заданій платіжній матриці.

Варіант 1 Варіант 2

. .