Антагоністична гра. Вирішення матричних антагоністичних ігор Принципи вирішення матричних антагоністичних ігор
Теорія ігор - це теорія математичних моделей прийняття рішень за умов конфлікту чи невизначеності. Передбачається, що дії сторін у грі характеризуються певними стратегіями – наборами правил дій. Якщо виграш однієї сторони неминуче веде до програшу іншої сторони, то говорять про антагоністичні ігри. Якщо набір стратегій обмежений, то гра називається матричною, і рішення можна отримати дуже просто. Рішення, одержувані з допомогою теорії ігор, корисні при складанні планів за умов можливого протидії конкурентів чи невизначеності у зовнішньому середовищі.
Якщо біматрична гра є антагоністичною, то матриця виграшів гравця 2 повністю визначається матрицею виграшів гравця 1 (відповідні елементи цих двох матриць відрізняються лише знаками). Тому біматрична антагоністична гра повністю описується єдиною матрицею (матрицею виграшів гравця 1) і відповідно називається матричною.
Ця гра – антагоністична. У ній j = х2 - О, Р, а Я (О, О] = Н(Р, Р) = -I і Я (О, Р) = Я (Р, О) = 1, або в матричній формі о р
Нехай певний клас ігор Ж є "дзеркально-замкнутим", тобто. разом з кожною своєю грою містить дзеркально ізоморфну їй (оскільки всі ігри, дзеркально ізоморфні даної, ізоморфні один одному, ми, відповідно до щойно сказаного, можемо говорити про одну дзеркально ізоморфну гру). Таким класом є, наприклад, клас усіх антагоністичних ігор чи клас усіх матричних ігор.
Згадуючи визначення прийнятних ситуацій в антагоністичній грі, отримуємо, що ситуація (X, Y) у змішаному розширенні матричної гри є прийнятною для гравця 1 тоді і тільки тоді, коли за будь-якого х G х виконується нерівність
Процес переробки ігор у симетричні їм називається симетризацією. Ми опишемо тут один прийом симетризації. Інший, принципово інший варіант симетризації буде наведено у п. 26.7. Обидва ці варіанти симетризації насправді застосовні до довільних антагоністичних ігор, але будуть сформульовані та доведені лише для матричних ігор.
Таким чином, вихідні терміни та позначення теорії загальних антагоністичних ігор збігаються з відповідними термінами та позначеннями теорії матричних ігор.
Для кінцевих антагоністичних (матричних) ігор існування цих екстремумів було доведено нами в 10 гол. 1, і вся справа полягала у встановленні їхньої рівності або хоча б у знаходженні шляхів подолання їхньої нерівності.
Вже розгляд матричних ігор показує, що існують антагоністичні ігри без ситуацій рівноваги (і навіть без ситуацій е-рівно-ваги за досить малих е > 0) у спочатку заданих стратегіях гравців.
Але кожну кінцеву (матричну) гру можна доповнити до нескінченної гри, наприклад, шляхом надання в розпорядження кожного гравця будь-якого числа стратегій, що домінуються (див. 22 гл. 1). Очевидно, таке розширення безлічі стратегій гравця насправді не означатиме розширення його можливостей, і фактична його поведінка у розширеній грі не повинна відрізнятись від його поведінки у початковій грі. Тим самим ми отримали відразу достатню кількість прикладів нескінченних антагоністичних ігор, які не мають сідлових точок. Є й приклади такого роду.
Таким чином, для реалізації в нескінченній антагоністичній грі принципу максиміну необхідне, як і у випадку кінцевої гри, деяке розширення стратегічних можливостей гравців. Для 96
Як і у випадку матричних ігор (див. 17 гл. 1), для загальних антагоністичних ігор важливу роль відіграє поняття спектра змішаної стратегії, якому тут доводиться дати більш загальне визначення.
Зауважимо, нарешті, що багато всіх змішаних стратегій гравця 1 у довільній антагоністичній грі є, як і в матричній
Вже розгляд антагоністичних ігор показує, що велика кількість таких ігор, і зокрема кінцевих, матричних ігор має ситуації рівноваги над вихідних, чистих стратегіях , а лише узагальнених, змішаних стратегіях . Тому і для загальних, неантагоністичних безкоаліційних ігор, природно шукати ситуації рівноваги саме в змішаних стратегіях.
Так, наприклад (див. рис. 3.1), ми вже зазначали, що "Виконавцю" майже не доводиться стикатися з поведінковою невизначеністю. А от якщо взяти концептуальний рівень типу "Адміністратор", то тут все навпаки. Як правило, головний тип невизначеності, з яким доводиться стикатися з таким "нашим ЛПР" - це "Конфлікт". Тепер можемо уточнити, що зазвичай це не суворе суперництво. Дещо рідше "Адміністратор" приймає рішення в умовах "природної невизначеності", і ще рідше він стикається зі суворим, антагоністичним конфліктом. Крім того, зіткнення інтересів при прийнятті рішень "Адміністратором" відбувається, так би мовити, "одноразово", тобто в нашій класифікації він частіше розігрує лише одну (іноді дуже невелику кількість) партій гри. Шкали з оцінки наслідків частіше якісні, ніж кількісні. Стратегічна самостійність у "Адміністратора" досить обмежена. Зважаючи на сказане, можна стверджувати, що проблемні ситуації подібного масштабу найчастіше доводиться аналізувати за допомогою безкоаліційних неантагоністичних бі-матричних ігор, причому в чистих стратегіях.
Принципи вирішення матричних антагоністичних ігор
У результаті буде розумно очікувати, що в описаній вище грі противники дотримуватимуться обраних стратегій. Матрична антагоністична гра, для якої max min fiv = min max Aiy>
Однак далеко не всі матричні антагоністичні ігри є цілком певними, і загалом
Таким чином, у випадку для вирішення матричної антагоністичної гри розмірністю /ихл необхідно вирішити пару двоїстих завдань лінійного програмування , внаслідок чого знаходиться набір оптимальних стратегій , / і ціна гри v.
Як визначається матрична антагоністична гра двох осіб
Які є методи спрощення та вирішення матричних антагоністичних ігор
У разі гри двох осіб природно вважати їхні інтереси прямо протилежними – гра антагоністична. Таким чином, виграш одного гравця дорівнює програшу іншого (сума виграшів обох гравців дорівнює нулю, звідси і назва – гра з нульовою сумою). Розглянемо ігри, в яких кожен гравець має кінцеву кількість альтернатив. Функція виграшу для такої гри двох осіб із нульовою сумою може бути задана у матричній формі (у вигляді платіжної матриці).
Як зазначалося, кінцева антагоністична гра називається матричной.
МАТРИЧНІ ІГРИ - клас антагоністичних ігор, в яких беруть участь два гравці, причому кожен гравець має в своєму розпорядженні кінцеве число стратегій. Якщо один гравець має стратегій, а другий - п, то можна побудувати матрицю гри розмірністю тхп. М.І. можуть мати сідлову точку, але можуть і не мати її. В останньому випадку
Московський Енергетичний Інститут
(Технічний університет)
Звіт з лабораторної роботи
з теорії ігор
"Програма пошуку оптимальних стратегій для парної антагоністичної гри, заданої в матричній формі"
Виконали студенти
групи А5-01
Ашрапов Далер
Ашрапова Ольга
Основні поняття теорії ігор
Теорія ігор розроблена для вирішення конфліктних ситуацій , тобто. ситуацій, у яких зіштовхуються інтереси двох і більше сторін, які мають різні мети.
Якщо цілі сторін прямо протилежні, то говорять про антагоністичний конфлікт .
грою називається спрощена формалізована модель конфліктної ситуації.
Одноразовий розіграш гри від початку до кінця називається партією . Результатом партії є платіж (або виграш ).
Партія складається з ходів , тобто. виборів гравців з певної кількості можливих альтернатив.
Ходи можуть бути особистіі випадкові.Особистий хід , на відміну від випадкового , передбачає свідомий вибір гравцем певного варіанта.
Ігри, в яких є хоча б один особистий хід, називаються стратегічними .
Ігри, у яких всі ходи випадкові, називаються азартними .
При здійсненні особистого ходу говорять також про стратегії гравця, тобто. про правило чи сукупність правил, що визначають вибір гравця. У цьому стратегія має бути всеосяжною, тобто. вибір має бути визначений для будь-якої можливої під час партії ситуації.
Завдання теорії ігор- Знаходження оптимальних стратегій гравців, тобто. стратегій, які забезпечують їм максимальний виграш чи мінімальний програш.
Класифікація теоретико-ігрових моделей
гру nосіб прийнято позначати як, де 
- безліч стратегій i-го гравця, 
- Платіж гри.
Відповідно до даного позначення можна запропонувати таку класифікацію теоретико-ігрових моделей:
Дискретні (безліч стратегій 
дискретні)
Кінцеві
Нескінченні
Безперервні (безліч стратегій 
безперервні)
Нескінченні
nосіб ( 
)
Коаліційні (кооперативні)
Некоаліційні (некооперативні)
2-х осіб (парні)
Антагоністичні (ігри з нульовою сумою)
(інтереси сторін протилежні, тобто програш одного гравця дорівнює виграшу іншого)
Неантагоністичні
З повною інформацією (якщо гравцеві, що робить особистий хід відома вся передісторія гри, тобто всі ходи противника)
З неповною інформацією
З нульовою сумою (сумарний платіж дорівнює нулю)
З ненульовою сумою
Одноходові (лотереї)
Багатоходові
Матричне уявлення парної антагоністичної гри
У цьому посібнику будемо розглядати антагоністичні ігри двох осіб
, задані у матричній формі. Це означає, що нам відомо безліч стратегій першого гравця (гравець A){
A i },
i = 1,…,
mі безліч стратегій другого гравця (гравець B){
B j },
j = 1,...,
n, а також задана матриця A
= ||
a ij ||
виграшів першого гравця. Оскільки йдеться про антагоністичній грі, то передбачається, що виграш першого гравця дорівнює програшу другого. Вважаємо, що елемент матриці a ij- Виграш першого гравця при виборі їм стратегії A iта відповіді йому другого гравця стратегією B j. Таку гру позначатимемо як 
, де m
- кількість стратегій гравця А,n
- кількість стратегій гравця Ст.Загалом вона може бути представлена наступною таблицею:
|
B 1 |
|
B j |
|
B n |
|
|
A 1 |
|
| |||
|
|
|
|
|
|
|
|
A i |
|
| |||
|
|
|
|
|
|
|
|
A m |
|
|
Приклад 1
Як найпростіший приклад розглянемо гру, партія якої складається з двох ходів.
1-й хід: Гравець Авибирає одне із чисел (1 або 2), не повідомляючи про свій вибір супернику.
2-й хід: Гравець Увибирає одне із чисел (3 або 4).
Підсумок: Вибори гравців Аі Ускладаються. Якщо сума парна, то Увиплачує її значення гравцеві Аякщо ж непарна - навпаки, Авиплачує суму гравцеві У.
Ця гра може бути представлена у вигляді 
наступним чином:
|
|
|
|
|
| ||
|
|
(Вибір 3)
(Вибір 4)
(Вибір 1)
(Вибір 2)Неважко бачити, що дана грає антагоністичної, ще, вона є грою з неповною інформацією, т.к. гравцю В,що здійснює особистий хід, не відомо, який вибір зробив гравець А.
Як зазначалося вище, завдання теорії ігор полягає у знаходженні оптимальних стратегій гравців, тобто. стратегій, які забезпечують їм максимальний виграш чи мінімальний програш. Цей процес називається рішенням гри .
При вирішенні гри в матричній формі слід перевірити гру на наявність сідлової точки . Для цього вводяться дві величини:
– нижня оцінка ціни гри та
- Верхня оцінка ціни гри.
Перший гравець, швидше за все, вибере ту стратегію, коли він отримає максимальний виграш серед усіх можливих відповідей другого гравця, а другий - навпаки, ту, яка мінімізує його власний програш, тобто. можливий виграш першого.
Можна довести, що α ≤ V ≤ β , де V–ціна гри , тобто ймовірний виграш першого гравця.
Якщо виконується співвідношення α
=
β
=
V, то кажуть, що гра має сідлову точку
, і вирішується у чистих стратегіях
. Іншими словами, є пара стратегій 
дають гравцю АV.
Приклад 2
Повернемося до гри, розглянутої нами у прикладі 1 і перевіримо її на наявність сідлової точки.
|
|
|
|
|
|
| |||
|
| |||
|
|
(Вибір 3)
(Вибір 4)
(Вибір 1)
(Вибір 2)
Для цієї гри 
=
-5,
=
4,
Отже, вона не має сідлової точки.
Ще раз звернемо увагу на те, що ця гра є грою з неповною інформацією. В даному випадку можна лише порадити гравцю Авибрати стратегію 
, т.к. у цьому випадку він може отримати найбільший виграш, щоправда, за умови вибору гравцем Устратегії 
.
Приклад 3
Внесемо до правил гри з прикладу 1 деякі зміни. Надаємо гравцю Уінформацію про вибір гравця А.Тоді у Уз'являться дві додаткові стратегії:
- стратегія, вигідна для А.Якщо вибір А - 1,то Увибирає 3, якщо вибір А - 2,то Увибирає 4;
- стратегія, не вигідна для А.Якщо вибір А - 1,то Увибирає 4, якщо вибір А - 2,то Увибирає 3.
|
|
|
|
|
|
|
|
| |||||
|
| |||||
|
|
(Вибір 3)
(Вибір 4)
(Вибір 1)
(Вибір 2)
Ця гра – з повною інформацією.
В даному випадку 
=
-5,
=
-5,
, отже, гра має сідлову точку 
. Даній сідловій точці відповідають дві пари оптимальних стратегій: 
і 
. Ціна гри V= -5.
Очевидно, що для Атака гра невигідна.
Приклади 2 та 3 є непоганою ілюстрацією до наступної теореми, доведеної в теорії ігор:
Теорема 1
Будь-яка парна антагоністична гра з повною інформацією вирішується у чистих стратегіях.
Т.о. теорема 1 говорить про те, що будь-яка гра двох осіб з повною інформацією має сідлову точку та існує пара чистих стратегій 
дають гравцю Астійкий виграш, рівний ціні гри V.
У разі відсутності сідлової точки, як рішення використовуються т.зв. змішані стратегії
:, де p i іq j- Імовірності вибору стратегій A i
і
B jпершим та другим гравцями відповідно. Рішенням гри в цьому випадку є пара змішаних стратегій 
, що максимізують математичне очікування ціни гри.
Узагальненням теореми 1 у разі гри з неповною інформацією служить наступна теорема:
Теорема 2
Будь-яка парна антагоністична гра має хоча б одне оптимальне рішення, тобто пару в загальному випадку змішаних стратегій 
дають гравцю Астійкий виграш, рівний ціні гри V, причому α ≤
V ≤
β
.
В окремому випадку, для гри з сідловою точкою рішення в змішаних стратегіях виглядає як пара векторів, в яких один елемент дорівнює одиниці, а інші дорівнюють нулю.
Найпростішим випадком, детально розробленим теоретично ігор, є кінцева парна гра з нульовою сумою (антагоністична гра двох осіб чи двох коаліцій). Розглянемо таку гру G, в якій беруть участь два гравці Аі В,мають протилежні інтереси: виграш одного дорівнює програшу іншого. Тому що виграш гравця Адорівнює виграшу гравця У сзворотним знаком, ми можемо цікавитися лише виграшем агравця А.Звичайно, Ахоче максимізувати, а В -мінімізувати а.Для простоти ототожнимо себе подумки з одним із гравців (нехай це буде а)і будемо його називати «ми», а гравця В -«противник» (зрозуміло, ніяких реальних переваг для Аз цього не випливає). Нехай у нас є тможливих стратегій А 1 , A 2 , ..., А m, а у противника - nможливих стратегій У 1 , В 2 , ..; У n(така гра називається грою т × n). Позначимо а ijнаш виграш у разі, якщо ми користуємося стратегією A i , а противник-стратегією B j .
Таблиця 26.1
|
A i B j |
B 1 |
B 2 |
B n |
|
|
A 1 A 2 A m |
a 11 a 21 a m1 |
a 21 a m |
a 1 n a 2 n a mn |
Припустимо, що з кожної пари стратегій Л<, В,виграш (або середній виграш) a, jнам відомий. Тоді, в принципі, можна скласти прямокутну таблицю (матрицю), в якій перераховані стратегії гравців та відповідні виграші (див. таблицю 26.1).
Якщо таку таблицю складено, то кажуть, що гра Gприведена до матричної форми (саме по собі приведення гри до такої форми вже може скласти важке завдання, а іноді й практично нездійсненне, через незбагненну безліч стратегій). Зауважимо, що якщо гра приведена до матричної форми, то багатоходова гра фактично зведена до одноходової – від гравця потрібно зробити лише один хід: вибрати стратегію. Коротко позначатимемо матрицю гри ( a ij).
Розглянемо приклад гри G(4×5) у матричній формі. У нашому розпорядженні (на вибір) чотири стратегії, у супротивника – п'ять стратегій. Матриця гри дана у таблиці 26.2
Давайте поміркуємо про те, якою стратегією нам (гравцю а)скористатися? У матриці 26.2 є спокусливий виграш "10"; нас так і тягне вибрати стратегію А 3 , при якій цей «ласий шматок» нам дістанеться. Але заждіть: противник теж не дурень! Якщо ми виберемо стратегію А 3 , він, на зло нам, вибере стратегію У 3 , і ми отримаємо якийсь жалюгідний виграш «1». Ні, вибирати стратегію А 3 не можна! Як же бути? Очевидно, виходячи з принципу обережності (а він – основний принцип теорії ігор), треба вибрати
Таблиця 26.2
|
B j A i |
B 1 |
B 2 |
B 3 |
B 4 |
B 5 |
|
A 1 A 2 A 3 A 4 |
ту стратегію, за якої Наш мінімальний виграш максимальний.Це – так званий «принцип мінімаксу»: роби так, щоб при найгіршій для тебе поведінці супротивника отримати максимальний виграш.
Перепишемо таблицю 26.2 та у правому додатковому стовпці запишемо мінімальне значення виграшу у кожному рядку, (мінімум рядка); позначимо його для i-й рядки α i(Див. таблицю 26.3).
Таблиця 26.3
|
B j A i |
B 1 |
B 2 |
B 3 |
B 4 |
B 5 | |
|
A 1 A 2 A 3 A 4 | ||||||
|
β j |
З усіх значень α i(Правий стовпець) виділено найбільше (3). Йому відповідає стратегія A 4 . Вибравши цю стратегію, ми, у всякому разі, можемо бути впевнені, що (за будь-якої поведінки противника) виграємо не менше, ніж 3. Ця величина - наш гарантований виграш; ведучи себе обережно, менше цього ми одержати не можемо (я, можливо, отримаємо і більше). Цей виграш називається нижньою ціною гри (або «максиміном» – максимальний із мінімальних виграшів). Будемо позначати його а.У нашому випадку α = 3.
Тепер станемо на думку противника і поміркуємо за нього. Адже він не пішака якась, а теж розумний! Вибираючи стратегію, він хотів би віддати якомога менше, але повинен розраховувати на нашу, найгіршу для нього, поведінку. Якщо він вибере стратегію У 1 , ми йому відповімо А 3 , і він віддасть 10; якщо вибере B 2 - ми йому відповімо А 2 , і він віддасть 8 і т. д. Припишемо до таблиці 26.3 додатковий нижній рядок і в ньому запишемо максимуми стовпців β j. Очевидно, обережний противник повинен вибрати ту стратегію, коли ця величина мінімальна (відповідне значення 5 виділено у таблиці 26.3). Ця величина - це значення виграшу, більше якого свідомо не віддасть нам розумний противник. Вона називається верхньою ціною гри (або «мінімаксом» – мінімальний із максимальних виграшів). У прикладі β = 5 і досягається при стратегії противника B 3 .
Отже, виходячи з принципу обережності (перестрахувального правила «завжди розраховувай на найгірше!»), ми маємо вибрати стратегію А 4 , а противник – стратегію У 3 . Такі стратегії називаються «мінімаксними» (що випливають із принципу мінімаксу). Доки обидві сторони в нашому прикладі дотримуватимуться своїх мінімаксних стратегій, виграш дорівнюватиме а 43 = 3.
Тепер уявімо собі на хвилину, що ми дізналися про те, що супротивник дотримується стратегії У 3 . Ану, покараємо його за це і виберемо стратегію А 1 - ми отримаємо 5, а це не так уже й погано. Але противник - теж не промах; нехай він дізнався, що наша стратегія А 1 ; він теж поквапиться вибрати У 4 , звівши наш виграш до 2, і т. д. (партнери «металися за стратегіями»). Одним словом, мінімаксні стратегії у нашому прикладі нестійкі щододо інформації щодо поведінки іншої сторони;ці стратегії не мають властивості рівноваги.
Чи завжди це так? Ні не завжди. Розглянемо приклад із матрицею, даною в таблиці 26.4.
У цьому прикладі нижня Ціна гри дорівнює верхній: α = β = 6. Що з цього випливає? Мінімаксні стратегії гравців Аі Убудуть стійкими. Поки обидва гравці їх дотримуються, виграш дорівнює 6. Подивимося, що буде, якщо ми (А)дізнаємося, що противник (В)
Таблиця 26.4
|
Bj A i |
B 1 |
B 2 |
B 3 |
B 4 | |
|
A 1 A 2 A 3 | |||||
|
β j |
дотримується стратегії B 2 ? А нічого не зміниться. Тому що будь-який відступ від стратегії А 2 може лише погіршити наше становище. Так само інформація, отримана противником, не змусить його відступити від своєї стратегії У 2 . Пара стратегій А 2 , B 2 має властивість рівноваги (урівноважена пара стратегій), а виграш (у нашому випадку 6), що досягається при цій парі стратегій, називається «сідловою точкою матриці» 1). Ознака наявності сідлової точки та врівноваженої пари стратегій – це рівність нижньої та верхньої ціни гри; загальне значення α та β називається ціною гри. Ми будемо позначати його v:
α = β = v
Стратегії A i , B j(в даному випадку А 2 , В 2 ), за яких цей виграш досягається, називаються оптимальними чистими стратегіями, які сукупність - рішенням гри. Про саму гру в цьому випадку говорять, що вона вирішується у чистих стратегіях. Обом сторонам Аі Уможна вказати їх оптимальні стратегії, у яких їх становище - найкраще з можливих. А що гравець Апри цьому виграє 6, а гравець В -програє 6,- що ж, такі умови гри: вони вигідні для Аі невигідні для У
1) Термін «сідлова точка» взятий з геометрії - так називається точка на поверхні, де одночасно досягається мінімум по одній координаті та максимум по іншій.
У читача може виникнути питання: чому оптимальні стратегії називаються «чистими»? Дещо забігаючи вперед, відповімо на це питання: бувають стратегії «змішані», які полягають у тому, що гравець застосовує не одну якусь стратегію, а кілька, перемежуючи їх випадковим чином. Так от, якщо допустити крім чистих ще й змішані стратегії, будь-яка кінцева грамає рішення – точку рівноваги. Але про це йдеться ще попереду.
Наявність сідлової точки в грі – це далеко не правило, скоріше – виняток. Більшість ігор немає сідлової точки. Втім, є різновид ігор, які завжди мають сідлову точку і, отже, вирішуються у чистих стратегіях. Це – так звані «ігри з повною інформацією». Ігрою з полицею інформацією називається така гра, у якій кожен гравець при кожному особистому ході знає всю передісторію її розвитку, т. е. результати всіх попередніх ходів, як особистих, і випадкових. Прикладами ігор з повною інформацією можуть бути: шашки, шахи, «хрестики та нулики» тощо.
Теоретично ігор доводиться, що кожна гра з повною інформацією має сідлову точку,і отже, вирішується у чистих стратегіях. У кожній грі з повною інформацією існує пара оптимальних стратегій, що дає стійкий виграш, рівний ланцюгу гри v. Якщо така гра складається тільки з особистих ходів, то при застосуванні кожним гравцем своєї оптимальної стратегії вона повинна закінчуватися цілком певним чином – виграшем, що дорівнює ціні гри. А значить, якщо рішення гри відоме, сама гра втрачає сенс!
Візьмемо елементарний приклад гри з повною інформацією: два гравці поперемінно кладуть п'ятаки на круглий стіл, вибираючи довільне положення центру монети (взаємне перекриття монет не дозволяється). Виграє той, хто покладе останній п'ятак (коли місця для інших не залишиться). Легко переконатися, що результат цієї гри, по суті, вирішено наперед. Існує певна стратегія, яка забезпечує виграш тому з гравців, хто кладе монету першим. Зокрема, він повинен вперше покласти п'ятак про центр столу, та був за кожен хід противника відповідати симетричним ходом. Очевидно, хоч би як поводився супротивник, йому не уникнути програшу. Так само і з шахами і взагалі іграми з повною інформацією: будь-яка з них, записана в матричній формі, має сідлову точку, і значить, рішення в чистих стратегіях, а, отже, має сенс тільки доти, поки це рішення не знайдено. Скажімо, шахова гра або завждизакінчується виграшем білих, або завжди -виграшем чорних, або завжди -нічиєї, тільки чим саме - ми поки що не знаємо (на щастя для любителів шахів). Додамо ще: навряд чи знатимемо і в найближчому майбутньому, бо число стратегій таке величезне, що вкрай важко (якщо не неможливо) привести гру до матричної форми і знайти в ній сідлову точку.
А тепер спитаємо себе, як бути, якщо гра не має сідлової точки: α ≠ β ? Ну що ж, якщо кожен гравець змушений вибрати одну – єдину чисту стратегію, то робити нічого: треба керуватися принципом мінімаксу. Інша справа, якщо можна скопію стратегії «змішувати», чергувати випадково з якимись ймовірностями. Застосування змішаних стратегій мислиться так: гра повторюється багато разів; перед кожною партією гри, коли гравцеві надається особистий хід, він «перевіряє» свій вибір випадковості, «кидає жереб», і бере ту стратегію, яка випала (як організувати жереб, ми вже знаємо з попереднього розділу).
Змішані стратегії в теорії ігор являють собою модель мінливої, гнучкої тактики, коли жоден з гравців не знає, як поведеться супротивник у цій партії. Така тактика (щоправда, зазвичай без будь-яких математичних обгрунтувань) часто застосовується у карткових іграх. Зауважимо при цьому, що найкращий спосіб приховати від супротивника свою поведінку - це надати йому випадкового характеру і, отже, самому не знати заздалегідь, як ти зробиш.
Отже, поговоримо про змішані стратегії. Позначатимемо змішані стратегії гравців Аі Увідповідно S A = ( p 1 , р 2 , ..., p m), S B = (q 1 , q 2 , …, q n), де p 1 , p 2 , …, p m(утворюють у сумі одиницю) - ймовірність застосування гравцем Астратегій А 1 , A 2 ,… , A m ; q 1 , q 2 , …, q n-ймовірності застосування гравцем Устратегій У 1 , У 2 , ..., У n . В окремому випадку, коли всі ймовірності, крім однієї, дорівнюють нулю, а ця одна - одиниці, змішана стратегія перетворюється на чисту.
Існує основна теорема теорії ігор: будь-яка кінцева гра двох осіб з нульовою сумою має принаймні одне рішення -пару оптимальних стратегій, загалом змішаних 
та відповідну ціну v.
Пара оптимальних стратегій 
утворюють рішення гри, має наступну властивість: якщо один із гравців дотримується своєї оптимальної стратегії, то іншому не може бути вигідно відступати від своєї.Ця пара стратегій утворює у грі якесь положення рівноваги: один гравець хоче звернути виграш у максимум, інший - у мінімум, кожен тягне у свій бік і, при розумній поведінці обох, встановлюється рівновага та стійкий виграш v.Якщо v > 0, то гра вигідна для нас, якщо v<
0
-
для супротивника; при v= 0 гра «справедлива», однаково вигідна обох учасників.
Розглянемо приклад гри без сідлової точки та наведемо (без доказу) її розв'язання. Гра полягає в наступному: два гравці Аі Уодночасно і не змовляючись показують один, два чи три пальці. Виграш вирішує загальну кількість пальців: якщо воно парне, виграє Аі отримує у Усуму, рівну цьому числу; якщо непарне, то, навпаки, Аплатить Усуму, рівну цьому числу. Як чинити гравцям?
Складемо матрицю гри. В одній партії у кожного гравця три стратегії: показати один, два чи три пальці. Матриця 3×3 дана в таблиці 26.5; у додатковому правому стовпці наведено мінімуми рядків, а додатковому нижньому рядку - максимуми стовпців.
Нижня ціна гри α = - 3 та відповідає стратегії A 1 . Це означає, що при розумній, обережній поведінці ми гарантуємо, що не програємо більше, ніж 3. Слабка втіха, але все ж таки краще, ніж, скажімо, виграш - 5, що зустрічається в деяких клітинах матриці. Погано нам, гравцю А...Але втішимо:
становище противника, здається, ще гірше: нижня ціна гри β = 4, тобто при розумній поведінці він віддасть нам мінімум 4. Загалом, становище не надто хороше - ні для тієї, ні для іншої сторони. Але подивимося: чи не можна його покращити? Виявляється, можна. Якщо кожна сторона застосовуватиме не одну якусь чисту стратегію, а змішану, до якої
Таблиця 26.5
|
Bj A i |
B 1 |
B 2 |
B 3 | |
|
A 1 A 2 A 3 | ||||
|
β j |
перша і третя входять із ймовірностями 1/4, а друга - з ймовірністю 1/2, тобто.
то середній виграш буде стійко дорівнює нулю (означає, гра «справедлива» і однаково вигідна тій та іншій стороні). Стратегії 
утворюють рішення гри, а її ціна v= 0. Як ми це рішення знайшли? Це питання інше. У наступному параграфі ми покажемо, як загалом вирішуються кінцеві ігри.
Розглянемо кінцеву парну гру із нульовою сумою. Позначимо через aвиграш гравця A, а через b– виграш гравця B. Так як a = –b, то при аналізі такої гри немає необхідності розглядати обидва ці числа - достатньо розглядати виграш одного з гравців. Нехай це буде, наприклад, A. Надалі для зручності викладу сторону Aбудемо умовно називати " ми", а бік B – "противник".
Нехай у нас є mможливих стратегій A 1 , A 2 , …, A m, а у противника nможливих стратегій B 1 , B 2 , …, B n(така гра називається грою m×n). Припустимо, кожна сторона вибрала певну стратегію: ми вибрали A і, супротивник B j. Якщо гра складається лише з особистих ходів, то вибір стратегій A іі B jоднозначно визначає результат гри – наш виграш (позитивний чи негативний). Позначимо цей виграш через a ij(виграш при виборі нами стратегії A і, а противником – стратегії B j).
Якщо гра містить крім особистих випадкових ходів, то виграш при парі стратегій A і, B jє величина випадкова, що залежить від наслідків усіх випадкових ходів. У цьому випадку природною оцінкою очікуваного виграшу є математичне очікування випадкового виграшу. Для зручності будемо позначати через a ijяк сам виграш (у грі без випадкових ходів), і його математичне очікування (у грі з випадковими ходами).
Припустимо, що нам відомі значення a ijза кожної пари стратегій. Ці значення можна записати у вигляді матриці, рядки якої відповідають нашим стратегіям ( A і), а стовпці - стратегіям противника ( B j):
| B j A i | B 1 | B 2 | … | B n |
| A 1 | a 11 | a 12 | … | a 1n |
| A 2 | a 21 | a 22 | … | a 2n |
| … | … | … | … | … |
| A m | a m 1 | a m 2 | … | a mn |
Така матриця називається платіжною матрицею гриабо просто матрицею гри.
Зауважимо, що побудова платіжної матриці для ігор з великою кількістю стратегій може бути непростим завданням. Наприклад, для шахова грачисло можливих стратегій настільки велике, що побудова платіжної матриці є практично нездійсненним. Однак, в принципі, будь-яка кінцева гра може бути приведена до матричної форми.
Розглянемо приклад 1антагоністичної гри 4×5. У нашому розпорядженні є чотири стратегії, противник – п'ять стратегій. Матриця гри наступна:
| B j A i | B 1 | B 2 | B 3 | B 4 | B 5 |
| A 1 | |||||
| A 2 | |||||
| A 3 | |||||
| A 4 |
Якою стратегією нам (тобто гравцю A) скористатися? Яку б ми не вибрали стратегію, розумний супротивник відповість на неї стратегією, для якої наш виграш буде мінімальним. Наприклад, якщо ми виберемо стратегію A 3 (спокусившись виграшем 10), противник у відповідь вибере стратегію B 1 , і наш виграш буде лише 1. Очевидно, виходячи з принципу обережності (а він – основний принцип теорії ігор), треба вибирати ту стратегію, за якої наш мінімальний виграш максимальний.
Позначимо через α iмінімальне значення виграшу для стратегії A і:
і додамо до матриці гри стовпець, що містить ці значення:
| B j A i | B 1 | B 2 | B 3 | B 4 | B 5 | мінімум у рядках α i | |
| A 1 | |||||||
| A 2 | |||||||
| A 3 | |||||||
| A 4 | максимін |
Вибираючи стратегію, ми повинні віддати перевагу тій, для якої значення α iмаксимально. Позначимо це максимальне значення через α :
Величина α називається нижньою ціною гриабо максиміном(Максимум мінімального виграшу). Стратегія гравця A, що відповідає максиміну α , називається максимінною стратегією.
У цьому прикладі максимін α дорівнює 3 (відповідна клітина у таблиці виділена сірим кольором), а максимінна стратегія – A 4 . Вибравши цю стратегію, можемо бути впевнені, що за будь-якої поведінки противника виграємо не менше, ніж 3 (а може бути і більше при "нерозумній" поведінці противника"). Ця величина – наш гарантований мінімум, який ми можемо собі забезпечити, дотримуючись найбільш обережної ("перестрахувальної") стратегії.
Тепер проведемо аналогічні міркування за супротивника B B A B 2 – ми йому відповімо A .
Позначимо через β j A B) для стратегії A і:
β j β :
7.ЩО НАЗИВАЄТЬСЯ ВЕРХНІЙ ЦІННОЇ ГРИТИ Тепер проведемо аналогічні міркування за противника B. Він зацікавлений у тому, щоб звернути наш виграш у мінімум, тобто віддати нам поменше, але має розраховувати на нашу, найгіршу для нього, поведінку. Наприклад, якщо він вибере стратегію B 1, то ми відповімо йому стратегією A 3 , і він віддасть нам 10. Якщо вибере B 2 – ми йому відповімо A 2 і він віддасть 8 і т. д. Очевидно, обережний противник повинен вибрати ту стратегію, при якій наш максимальний виграш буде мінімальним.
Позначимо через β jмаксимальні значення у стовпцях платіжної матриці (максимальний виграш гравця A, або, що те саме, максимальний програш гравця B) для стратегії A і:
і додамо до матриці гри рядок, що містить ці значення:
Вибираючи стратегію, противник віддасть перевагу тій, для якої значення β jмінімально. Позначимо його через β :
Величина β називається верхньою ціною гриабо мінімаксом(Мінімум максимального виграшу). Відповідна мінімакс стратегія противника (гравця B), називається мінімаксною стратегією.
Мінімакс - це значення виграшу, більше якого свідомо не віддасть нам розумний супротивник (інакше кажучи, розумний супротивник програє не більше, ніж β ). У цьому прикладі мінімакс β дорівнює 5 (відповідна клітина в таблиці виділена сірим кольором) і досягається при стратегії противника B 3 .
Отже, виходячи з принципу обережності («завжди розраховувай на найгірше!»), ми маємо вибрати стратегію A 4 , а противник – стратегію B 3 . Принцип обережності є в теорії ігор основним і називається принципом мінімаксу.
Розглянемо приклад 2. Нехай гравці Aі Уодночасно і незалежно один від одного записують одне з трьох чисел: або "1", або "2", або "3". Якщо сума записаних чисел виявляється парною, то гравець Bплатить гравцеві Aцю суму. Якщо сума непарна, то цю суму виплачує гравець Aгравцю У.
Запишемо платіжну матрицю гри, і знайдемо нижню та верхню ціни гри (номер стратегії відповідає записаному числу):
Гравець Aповинен дотримуватись максимічної стратегії A 1 , щоб виграти не менше –3 (тобто щоб програти не більше 3). Мінімаксна стратегія гравця B– будь-яка зі стратегій B 1 та B 2 , що гарантує, що він віддасть трохи більше 4.
Той самий результат ми отримаємо, якщо будемо записувати платіжну матрицю з погляду гравця У. Фактично, ця матриця виходить шляхом транспонування матриці, побудованої з погляду гравця A, та зміни знаків елементів на протилежний (оскільки виграш гравця A– це програш гравця У):
Виходячи з цієї матриці випливає, що гравець Bповинен дотримуватися будь-якої зі стратегій B 1 та B 2 (і тоді він програє не більше 4), а гравець A– стратегії A 1 (і тоді він програє трохи більше 3). Як видно, результат точно збігається з отриманим вище, тому при аналізі не важливо, з точки зору якого гравця ми його проводимо.
8 ЩО НАЗИВАЄТЬСЯ ЦІННОВОЮ ГРАЮ.
9. У ЧОМУ СХОДИТЬ ПРИНЦЕП МІНІМАКСУ. 2. Нижня та верхня ціна гри. Принцип мінімаксу
Розглянемо матричну гру типу з платіжною матрицею
Якщо гравець Авибере стратегію А і, то всі його можливі виграші будуть елементами i-й рядка матриці З. У найгіршому для гравця Авипадку, коли гравець Узастосовує стратегію, що відповідає мінімальномуелементу цього рядка, виграш гравця Адорівнюватиме числу.
Отже, для отримання найбільшого виграшу, гравцю Апотрібно вибирати ту зі стратегій, для якої число максимально.
Завдання прийняття рішення, що розглядається в рамках системного підходу, містить три основні компоненти: у ній виділено систему, що управляє підсистемою та середовищем. Тепер ми переходимо до вивчення завдань прийняття рішення, в яких на систему впливає не одна, а кілька підсистем, що управляють, кожна з яких має свої цілі і можливості дій. Такий підхід до прийняття рішень називається теоретико-ігровим, а математичні моделі відповідних взаємодій називаються іграми. Зважаючи на відмінності цілей управляючих підсистем, а також певних обмежень на можливості обміну інформацією між ними, зазначені взаємодії мають конфліктний характер. Тому будь-яка гра є математичною моделлю конфлікту. Обмежимося нагодою, коли керуючих підсистем дві. Якщо цілі систем протилежні, конфлікт називається антагоністичним, а математична модель такого конфлікту називається антагоністичною грою..
У теоретико-ігровій термінології 1-а підсистема, що управляє, називається гравцем 1 2-а керуюча підсистема - гравцем 2, множини
їх альтернативних дій називаються множинами стратегійцих гравців. Нехай Х- безліч стратегій гравця 1, Y- безліч стратегій
гравця 2. Стан системи однозначно визначається вибором керуючих впливів підсистемами 1 та 2, тобто вибором стратегій
x∈Xі y∈Y. Нехай F(x,y)- оцінка корисності для гравця 1 того стану
системи, в яку вона переходить при виборі гравцем 1 стратегії хі
гравцем 2 стратегії у. Число F(x,y) називається виграшемгравця 1 у ситуації ( x,y), а функція F- функцією виграшу гравця 1. Виграш гравця
1 одночасно є програшем гравця 2 тобто величиною, яку перший гравець прагне збільшити, а другий - зменшити. Це і є
прояв антагоністичного характеру конфлікту: інтереси гравців повністю протилежні (те, що виграє один, програє інший).
Антагоністичну гру природно поставити системою Г=(Х, Y, F).
Зауважимо, що формально антагоністична гра задається фактично так само, як і завдання ухвалення рішення в умовах невизначеності - якщо
ототожнити керуючу підсистему 2 із середовищем. Змістовна відмінність між керуючою підсистемою та середовищем полягає в тому, що
поведінка першої носить цілеспрямований характер. Якщо при складанні математичної моделі реального конфлікту ми маємо підставу (або намір) розглядати середовище як противника, мета якого - принести
нам максимальна шкода, то таку ситуацію можна подати у вигляді антагоністичної гри. Іншими словами, антагоністичну гру можна трактувати як крайній випадок ЗПР в умовах невизначеності,
характеризується тим, що середовище сприймається як противник, має мета. При цьому ми повинні обмежити види гіпотез щодо поведінки середовища.
Найбільш обґрунтованою тут є гіпотеза крайньої обережності, коли, ухвалюючи рішення, ми розраховуємо на найгірший для нас можливий варіант дій середовища.
Визначення.Якщо Хі Yкінцеві, то антагоністична гра називається матричною. У матричній грі можна вважати, що X={1,…,n},
Y={1,…,m) і покласти aij = F(i,j). Таким чином, матрична гра повністю визначається матрицею A=(aij), i=1,…,n, j=1,…,m.
Приклад 3.1. Гра з двома пальцями.
Дві людини одночасно показують один або два пальці і називають число 1 або 2, що означає, на думку того, що говорить, кількість
пальців, показаний іншим. Після того, як пальці показані та числа названі, відбувається розподіл виграшу за такими правилами:
якщо обидва вгадали або обидва не вгадали, скільки пальців показав їхній суперник, виграш кожного дорівнює нулю; якщо вгадав тільки один, то противник платить суму грошей, що вгадала, пропорційну загальному числу показаних
Це антагоністична матрична гра. Кожен гравець має чотири стратегії: 1- показати 1 палець і назвати 1, 2- показати 1 палець і назвати 2, 3-
показати 2 пальці та назвати 1, 4 - показати 2 пальці та назвати 2. Тоді матриця виграшів A = (aij), i = 1,…, 4j = 1,…, 4 визначається наступним чином:
a12= 2, a21 = - 2, a13=a42=–3, a24=a31= 3, a34 = - 4, a43= 4,aij= 0 в інших випадках.
Приклад 3.2. Дискретна гра типу дуелі.
Завданнями дуельного типу описується, наприклад, боротьба двох гравців,
кожен із яких хоче вчинити якесь одноразове дію (викид ринку партії товару, заявка про купівлю на аукціоні) і вибирає при цьому час. Нехай гравці просуваються назустріч один одному на nкроків. Після кожного зробленого кроку гравець може вистрілити чи не вистрілити у супротивника. Постріл може бути у кожного лише один. Вважається, що можливість потрапити в супротивника, якщо просунутися на k n =5 має вигляд
