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

k 11 p 1 + k 21 p 2 = v (1)

де: k ij – елементи платіжної матриці.

З іншого боку, якщо припустити, що гравець "В" користуватиметься чистою стратегією B 2 , то середній виграш становитиме:

k 12 p 1 + k 22 p 2 = v (2)

Прирівнявши ліві частини рівнянь (1) та (2) отримаємо:

k 11 p 1 + k 21 p 2 = k 12 p 1 + k 22 p 2

А з урахуванням того, що p 1 + p 2 = 1 маємо:

k 11 p 1 + k 21 (1 - p 1 ) = k 12 p 1 + k 22 (1 - p 1 )

У цій задачі:

З теорії ігор відомо, що якщо гравець "B" використовує свою оптимальну стратегію, а гравець "A" залишається в рамках своїх активних стратегій, то середній виграш залишається незмінним та рівним ціні гри vнезалежно від того, як гравець "А" використовує свої активні стратегії. Тому якщо припустити, що гравець "A" користуватиметься чистою стратегією A1, то середній виграш vскладе:

k 11 q 1 + k 12 q 2 = v (4)

У цій задачі:

Відповідь:

Геометрична інтерпретація (графічне рішення):

Малюнок 1.
Графік залежності виграшу k від частоти р 2 , при використанні противником стратегії B 1.

Припустимо тепер, що гравець "B" користуватиметься стратегією B 2 у чистому вигляді. Тоді, якщо ми (гравець "A") використовуватимемо чисту стратегію A 1 , то наш виграш становитиме 5. Якщо ж ми будемо використовувати чисту стратегію A 2 , то наш виграш становитиме 3/2 (див. рис. 2). Аналогічно, якщо ми змішуватимемо в різних пропорціях стратегії A 1 і A 2 , наш виграш буде змінюватися по прямій через точки з координатами (0 , 5) і (1 , 3/2), назвемо її лінією стратегії B 2 . Як і в попередньому випадку, абсцис будь-якої точки на цій прямій дорівнює ймовірності, з якою ми застосовуємо стратегію A 2 , а ордината - виграшу, що отримується при цьому, але тільки для стратегії B 2 (див. Рис. 2).

Малюнок 2.
v та оптимальної частоти р 2 для гравця "А".

У реальній грі, коли розумний гравець "В" користується всіма своїми стратегіями, наш виграш буде змінюватися по ламаній лінії, показаній на мал.2 червоним кольором. Ця лінія визначає так звану нижній кордон виграшу. Очевидно, що найвища точка цієї ламаної відповідає нашій оптимальній стратегії. В даному випадку це точка перетину ліній стратегій B 1 і B 2 . Зверніть увагу, що якщо вибрати частоту p 2 рівної її абсцисі, то наш виграш залишатиметься незмінним і рівним v при будь-якій стратегії гравця "B", крім того він буде максимальним, який ми можемо собі гарантувати. Частота (імовірність) p 2 У цьому випадку є відповідна частота нашої оптимальної змішаної стратегії. До речі з малюнка 2 видно і частоту p 1 , нашої оптимальної змішаної стратегії, це довжина відрізка [ p 2 ; 1] на осі абсцис. (Це тому, що p 1 + p 2 = 1 )

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

Малюнок 3.
Графічне визначення ціни гри v та оптимальної частоти q 2 для гравця "В".

Тільки для нього слід збудувати так звану верхню межу програшу(червона ламана лінія) і шукати у ньому найнижчу точку, т.к. для гравця "В" ціль, це мінімізація програшу. Аналогічно значення частоти q 1 , Це довжина відрізка [ q 2 ; 1] на осі абсцис.

Розділ "Теорія ігор" представлений трьома онлайн-калькуляторами:

1. Оптимальні стратегії гравців. У таких завданнях задана платіжна матриця. Потрібно знайти чисті чи змішані стратегії гравців та, ціну гри. Для вирішення необхідно вказати розмірність матриці та метод рішення. У сервісі реалізовано такі методи вирішення гри двох гравців:
   1. Мінімакс. Якщо потрібно знайти чисту стратегію гравців або відповісти на питання про сідлову точку гри, виберіть цей метод рішення.
   2. Симплекс-метод. Використовується на вирішення гри у змішаних стратегіях методами лінійного програмування.
   3. Графічний метод. Використовується для вирішення гри у змішаних стратегіях. Якщо є сідлова точка, рішення припиняється. Приклад: За заданою платіжною матрицею знайти оптимальні змішані стратегії гравців та ціну гри за допомогою графічного методу вирішення гри.
   4. Ітераційний метод Брауна-Робінсона. Ітеративний метод застосовується тоді, коли не застосовний графічний метод і коли практично не застосовуються алгебраїчний та матричний методи. Цей метод дає наближене значення ціни гри, причому справжнє значення можна отримати з будь-яким потрібним ступенем точності. Цей метод недостатній для знаходження оптимальних стратегій, але дозволяє відслідковувати динаміку покрокової гри і визначити ціну гри для кожного з гравців на кожному кроці.
   Наприклад, завдання може звучати як "зазначити оптимальні стратегії гравців для гри, заданої платіжною матрицею".
   У всіх методах застосовується перевірка на домінуючі рядки та стовпці.
2. Біматрична гра. Зазвичай у такій грі задають дві матриці однакового розміру виграшів першого та другого гравців. Рядки цих матриць відповідають стратегіям першого гравця, а стовпці матриць – стратегіям другого гравця. При цьому у першій матриці представлені виграші першого гравця, а у другій матриці – виграші другого.
3. Ігри з природою. Використовується, коли необхідно вибрати управлінське рішення за критеріями Максимакса, Байєса, Лапласа, Вальда, Севіджа, Гурвіца.
   Для критерію Байєса необхідно також запровадити ймовірність настання подій. Якщо вони не задані, залиште значення за промовчанням (будуть рівнозначні події).
   Для критерію Гурвіца вкажіть рівень оптимізму λ. Якщо в умовах цього параметра не заданий можна використовувати значення 0, 0.5 і 1 .

Багато завданнях потрібно шукати рішення засобами ЕОМ. Одним з інструментів є вищенаведені послуги та функції

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

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

З історії теорії ігор

Історія теорії ігор як самостійної дисципліни починається у 1944 році, коли Джон фон Нейман та Оскар Моргенштерн опублікували книгу "Теорія ігор та економічна поведінка" ("Theory of Games and Economic Behavior"). Хоча приклади теорії ігор зустрічалися й раніше: трактат Вавилонського Талмуду про поділ майна померлого чоловіка між його дружинами, карткові ігри в 18-му столітті, розвиток теорії шахової гри на початку 20-го століття, доказ теореми про мінімакс того ж Джона фон Неймана в 1928 року, без якої не було б жодної теорії ігор.

У 50-х роках 20-го століття Мелвін Дрешер і Меріл Флод з Rand Corporationпершими експериментально застосували дилему ув'язненого, Джон Неш у роботах про стан рівноваги в іграх двох осіб розвинув поняття рівноваги Неша.

Рейнхард Селтен в 1965 опублікував книгу "Обробка олігополії в теорії ігор на вимогу" ("Spieltheoretische Behandlung eines Oligomodells mit Nachfrageträgheit"), з якою застосування теорії ігор в економіці отримало нову рушійну силу. Кроком вперед у еволюції теорії ігор пов'язані з роботою Джона Мейнарда Сміта " Еволюційно стабільна стратегія " ( " Evolutionary Stable Strategy " , 1974). Дилема ув'язненого була популяризована у книзі Роберта Аксельрода "Еволюція кооперації" ("The Evolution of Cooperation"), опублікованій 1984 року. У 1994 році саме за внесок у теорію ігор Нобелівської премії були удостоєні Джон Неш, Джон Харсаньї та Рейнхард Селтен.

Теорія ігор у житті та бізнесі

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

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

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

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

Одна з найпростіших конфліктних ситуацій, яка може бути записана і вирішена в теорії ігор - дуель, що є конфліктом двох гравців 1 і 2, які мають відповідно pі qпостріли. Для кожного гравця існує функція, що вказує на ймовірність того, що постріл гравця iу момент часу tдасть влучення, яке виявиться смертельним.

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

Математична модель у теорії ігор та формалізація завдань

Як ми вже зазначали, гра є математичною моделлю конфліктної ситуації і вимагає наявності наступних компонентів:

1. зацікавлених сторін;
2. можливі дії з кожної сторони;
3. інтересів сторін.

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

Реальна конфліктна ситуація не завжди, а гра (в понятті теорії ігор) – завжди – протікає по певним правилам , які точно визначають:

1. варіанти дій гравців;
2. обсяг інформації кожного гравця про поведінку партнера;
3. виграш, якого призводить кожна сукупність дій.

Прикладами формалізованих ігор можуть бути футбол, карткова гра, шахи.

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

Для гри характерна невизначеність результату . Причини невизначеності можна розподілити за такими групами:

1. комбінаторні (як у шахах);
2. вплив випадкових факторів (як у грі "орел чи решка", кістки, карткові ігри);
3. стратегічні (гравець не знає, яку дію вдасться противник).

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

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

Класифікація ігор

1. Класифікація за кількістю гравців (Гра двох і більше осіб). Ігри двох осіб посідають центральне місце у всій теорії ігор. p align="justify"> Основним поняттям теорії ігор для гри двох осіб є узагальнення дуже істотної ідеї рівноваги, яка природно з'являється в іграх двох осіб. Що ж до ігор nосіб, одна частина теорії ігор присвячена іграм, у яких співробітництво між гравцями заборонено. В іншій частині теорії ігор nосіб передбачається, що гравці можуть співпрацювати для взаємної користі (див. далі у цьому параграфі про некооперативні та кооперативні ігри).
2. Класифікація за кількістю гравців та їх стратегіями (кількість стратегій не менше двох, може бути нескінченністю).
3. Класифікація за кількістю інформації щодо минулих ходів: ігри з повною інформацією та неповною інформацією. Нехай є гравець 1 – покупець і гравець 2 – продавець. Якщо гравець 1 не має повної інформації про дії гравця 2, то гравець 1 може і не розрізнити дві альтернативи, між якими йому належить зробити вибір. Наприклад, вибираючи між двома видами деякого товару та не знаючи про те, що за деякими ознаками товар Aгірше за товар B, гравець 1 може не бачити різницю між альтернативами.
4. Класифікація за принципами поділу виграшу : кооперативні, коаліційні з одного боку та некооперативні, безкоаліційні з іншого боку. У некооперативної гри , або інакше - безкоаліційної гри гравці вибирають стратегії одночасно, не знаючи, яку стратегію вибере другий гравець. Комунікація між гравцями неможлива. У кооперативної гри , або інакше - коаліційної гри , гравці можуть об'єднуватися в коаліції та робити колективні дії, щоб збільшити свої виграші.
5. Кінцева гра двох осіб із нульовою сумою або антогоністична гра – це стратегічна гра з повною інформацією, в якій беруть участь сторони із протилежними інтересами. Анатагоністичними іграми є матричні ігри.

Класичний приклад з теорії ігор – дилема ув'язненого

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

Якщо це стратегічне завдання сформулювати у термінах ув'язнення, то воно зводиться до наступного:

Таким чином, якщо обидва ув'язнені не визнаються, вони отримають по 1 році кожен. Якщо обидва зізнаються, кожен отримає по 8 років. А якщо один зізнається, інший не визнається, то той, який зізнався, відбудеться трьома місяцями ув'язнення, а той, який не визнається, отримає 10 років. Наведена вище матриця правильно відбиває дилему ув'язненого: перед кожним стоїть питання - зізнатися чи зізнатися. Гра, яку окружний прокурор пропонує ув'язненим, є некооперативну гру чи інакше - безкоаліційну гру . Якби обидва в'язні мали можливість співпрацювати (тобто гра була б кооперативною чи інакше коаліційною грою ), то обидва не зізналися б і отримали за роком в'язниці кожен.

Приклади використання математичних засобів теорії ігор

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

Приклад формалізації некооперативної (безкоаліційної) гри двох осіб

У попередньому параграфі ми вже розглянули приклад некооперативної (безкоаліційної) гри (дилема ув'язненого). Давайте закріпимо наші навички. Для цього підійде класичний сюжет, навіяний "Пригодами Шерлока Холмса" Артура Конан Дойля. Можна, звичайно, заперечити: приклад не з життя, а з літератури, але Конан Дойль не зарекомендував себе як письменник-фантаст! Класичний ще й тому, що завдання виконане Оскаром Моргенштерном, як ми вже встановили, - одним із засновників теорії ігор.

приклад 1.Буде наведено скорочений виклад фрагмента однієї з "Пригод Шерлока Холмса". Відповідно до відомих понять теорії ігор скласти модель конфліктної ситуації та формально записати гру.

Шерлок Холмс має намір вирушити з Лондона в Дувр з подальшою метою потрапити на континент (європейський), щоб врятуватися від професора Моріарті, який переслідує його. Сівши в поїзд, він побачив на вокзальній платформі професора Моріарті. Шерлок Холмс припускає, що Моріарті може вибрати особливий поїзд і обігнати його. Шерлок Холмс має дві альтернативи: продовжувати поїздку до Дувру або зійти на станції Кентерберрі, яка є єдиною проміжною станцією на його маршруті. Ми приймаємо, що його противник досить розумний, щоб визначити можливості Холмса, тому перед ним ті самі дві альтернативи. Обидва противники повинні вибрати станцію, щоб зійти на ній з поїзда, не знаючи, яке рішення ухвалить кожен із них. Якщо в результаті ухвалення рішення обидва виявляться на одній і тій же станції, то можна однозначно вважати, що Шерлок Холмс буде вбитий професором Моріарті. Якщо ж Шерлок Холмс добереться до Дувру, то він буде врятований.

Рішення. Героїв Конан Дойля можемо розглядати як учасників гри, тобто гравців. У розпорядженні кожного гравця i (i=1,2) дві чисті стратегії:

• зійти в Дуврі (стратегія si1 ( i=1,2) );
• зійти на проміжній станції (стратегія si2 ( i=1,2) )

Залежно від того, яку з двох стратегій вибере кожен із двох гравців, буде створено особливу комбінацію стратегій як пару s = (s1 , s 2 ) .

Кожній комбінації можна поставити у відповідність подію - результат спроби вбивства Шерлока Холмса професором Моріарті. Складаємо матрицю цієї гри з можливими подіями.

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

Приклад формалізації та рішення кооперативної (коаліційної) гри nосіб

У цьому пункті практична частина, тобто хід розв'язання прикладу завдання, буде передована теоретичною частиною, в якій знайомитимемося з поняттями теорії ігор для вирішення кооперативних (безкоаліційних) ігор. Для цього завдання теорія ігор пропонує:

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

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

Для формалізації гри нам потрібно запровадити формальні позначення вищезгаданих понять.

Для гри nпозначимо безліч її гравців як N= (1,2,...,n) Будь-яке непусте підмножина множини Nпозначимо як Т(включаючи саме Nі всі підмножини, що складаються з одного елемента). На сайті є заняття Множини та операції над множинами", яке при переході за посиланням відкривається у новому вікні.

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

Для двох непустих коаліцій із підмножин T1 і T2 адитивність характеристичної функції кооперативної (коаліційної) гри записується так:

А суперадитивність так:

приклад 2.Троє студентів музичної школи підробляють у різних клубах, свою виручку вони одержують від відвідувачів клубів. Встановити, чи вигідно їм поєднувати свої сили (якщо так, то з якими умовами), використовуючи поняття теорії ігор для вирішення кооперативних ігор nосіб, за таких вихідних даних.

В середньому їх виручка за один вечір складала:

• у скрипаля 600 одиниць;
• у гітариста 700 одиниць;
• у співачки 900 одиниць.

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

• скрипаль + гітарист заробляли 1500 одиниць;
• скрипаль + співачка заробляли 1800 одиниць;
• гітарист + співачка заробляли 1900 одиниць;
• скрипаль + гітарист + співачка заробляли 3000 одиниць.

Рішення. У цьому прикладі кількість учасників гри n= 3 , отже, область визначення характеристичної функції гри складається з 2³ = 8 можливих підмножин безлічі всіх гравців. Перерахуємо всі можливі коаліції T:

• коаліції з одного елемента, кожна з яких складається з одного гравця – музиканта: T{1} , T{2} , T{3} ;
• коаліції із двох елементів: T{1,2} , T{1,3} , T{2,3} ;
• коаліція із трьох елементів: T{1,2,3} .

Кожному з гравців надамо порядковий номер:

• скрипаль – 1-й гравець;
• гітарист – 2-й гравець;
• співачка – 3-й гравець.

За даними завдання визначимо характеристичну функцію гри v:

v(T(1)) = 600; v(T(2)) = 700; v(T(3)) = 900; ці значення характеристичної функції визначені виходячи з виграшів відповідно першого, другого та третього гравців, коли вони не поєднуються в коаліції;

v(T(1,2)) = 1500; v(T(1,3)) = 1800; v(T(2,3)) = 1900; ці значення характеристичної функції визначені за виручкою кожної пари гравців, котрі об'єдналися у коаліції;

v(T(1,2,3)) = 3000; це значення характеристичної функції визначено за середнім виторгом у разі, коли гравці об'єднувалися в трійки.

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

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

1 Загальні відомості 2 1.1 Ігри. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Ходи. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Стратегії. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Матрична гра. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Слідова точка. Чисті стратегії 7 2.1 Приклади. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Приклад 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Приклад 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Змішані стратегії 9 3.1 Гра 2×2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.1 Приклади. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Приклад 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Приклад 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1.2 Геометрична інтерпретація. . . . . . . . . . . . . . . . . . . . 12 3.2 Ігри 2×n та m×2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Приклад 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1 1. Загальні відомості з теорії ігор 1.1. Теорія ігор - це математична теорія конфліктних ситуацій, тобто. таких ситуацій, у яких стикаються інтереси двох або більше сторін, що мають різні цілі. Гра - це конфліктна ситуація, регламентована певними правилами, в яких мають бути зазначені: можливі варіанти дій учасників кількісний результат гри або платіж (виграш, програш), до якого приводить дана сукупність ходів обсяг інформації кожної сторони про поведінку іншої. Парна гра - гра в якій беруть участь лише дві сторони (два гравці). Парна гра з нульової сумою - парна гра, у якій сума платежів дорівнює нулю, тобто. програш одного гравця дорівнює виграшу другого. Залежно від ставлення кожного з гравців до значення функції виграшу парні ігри поділяються: Парна гра з нульовою сумою (антагоністична) - парна гра, у якій сума платежів дорівнює нулю, тобто. програш одного гравця дорівнює виграшу другого. Неантагоністична гра - парна гра, в якій гравці мають різні, але не прямо протилежні цілі. 2 1.2. Ходи Хід - вибір одного з передбачених правил гри дій здійснення цього вибору Ходи бувають двох типів: Особистий хід - + свідомий вибір одного з передбачених правил гри дій + здійснення цього вибору Випадковий хід - Випадковим ходом називається вибір з ряду можливостей, що здійснюється не рішенням гравця, а якимось механізмом випадкового вибору. Нижче розглядаються парні ігри з нульовою сумою, що містять лише особисті ходи. Кожна сторона не має інформації про поведінку іншої. 3 1.3. Стратегії Стратегія гравця - сукупність правил, що визначають вибір дій при кожному особистому ході цього гравця в залежності від ситуації, що склалася в процесі гри. Залежно від кількості можливих стратегій гри діляться на кінцеві та нескінченні. Нескінченна гра - гра, в якій хоча б один з гравців має нескінченну кількість стратегій. Кінцева гра - гра, у якій кожен гравець має лише кінцеве число- стратегій. Число послідовних ходів у будь-якого з гравців визначає підрозділ ігор на одноходові та багатоходові, або позиційні. + В одноходовій грі кожен гравець робить лише один вибір із можливих варіантів і після цього встановлює результат гри. + Багатоходова, або позиційна, гра розвивається в часі, являючи собою ряд послідовних етапів, кожен з яких настає після перебігу одного з гравців та відповідної зміни обстановки. В одноходовій грі кожен гравець робить лише один вибір із можливих варіантів і після цього встановлює результат гри. Оптимальна стратегія гравця - стратегія, яка за багаторазового повторення гри забезпечує даному гравцеві максимально можливий середній виграш (або, що те саме, мінімально можливий середній програш). Теоретично ігор всі рекомендації виробляються з припущення про розумному поведінці гравців. Прорахунки та помилки гравців, неминучі в кожній конфліктній ситуації, а також елементи азарту та ризику в теорії ігор не враховуються. 4 1.4. Матрична гра Матрична гра - одноходова кінцева гра з нульовою сумою. Матрична гра є теоретико-ігровою моделлю конфліктної ситуації, в якій противники для досягнення діаметрально протилежних цілей роблять за одним вибором (ходом) з кінцевого числа можливих способів дій. Відповідно до обраних способів дій (стратегіями) визначається результат, що досягається. Розглянемо з прикладу. Нехай є два гравці A і B, один з яких може вибрати i-ю стратегію з m своїх можливих стратегій A1, A2, ... Am, а другий вибирає j-ю стратегію зі своїх можливих стратегій B1, B2,. . Bm. В результаті перший гравець виграє величину aij, а другий програє цю величину. З чисел aij , складемо матрицю   a11 a11 ··· a1n  a21 a22 ··· a2n    A = (aij) =  .. .. .. ..   . . . .  am1 am2 · · · amn Матриця A = (aij), i = 1, m, j = 1, n називається платіжною матрицею або матрицею гри m × n. У цій матриці рядки завжди для стратегій гравця, що виграє (максимізує), тобто гравця, який прагне максимізації свого виграшу. Стовпці відводяться для стратегій гравця B, що програє, тобто гравця, який прагне мінімізації критерію ефективності. Нагадаємо, що позиційна багатоходова гра є теоретико-ігровою моделлю конфліктної ситуації, в якій противники для досягнення своїх цілей послідовно роблять за одним вибором (ходом) з кінцевого числа можливих способів дій на кожному етапі розвитку цієї ситуації. Рішення гри - знаходження оптимальних стратегій обох гравців та визначення ціни гри Ціна гри - очікуваний виграш (програш) гравців. Рішення гри може бути знайдено або в чистих стратегіях - коли гравець повинен дотримуватися однієї єдиної стратегії, або в змішаних, коли гравець повинен з певними ймовірностями застосовувати дві чисті стратегії або більше. Останні у разі називаються активними. 5 Змішана стратегія одного гравця - вектор, кожен з компонентів якого показує частоту використання гравцем відповідної чистої стратегії. Максимін або нижня ціна гри - число α = max min aij i j Максиминна стратегія (рядок) - стратегія, яку вибрав гравець, щоб максимізувати свій мінімальний виграш. Очевидно, що при виборі найбільш обережної максимінної стратегії гравець A забезпечує собі (незалежно від поведінки супротивника) гарантований виграш не менше ніж α. Максимін або верхня ціна гри - число β = min max aij j i Мінімаксна стратегія (стовпець) - стратегія, яку вибрав гравець, щоб мінімізувати свій максимальний програш. Очевидно, що при виборі найбільш обережної мінімаксної стратегії гравець B не дає можливості за жодних обставин гравцеві A виграти більше, ніж β. Нижня ціна гри завжди не перевищує верхню ціну гри α = max min aij 6 min max aij = β i j j i Теорема 1 (основна теорема теорії матричних ігор). Кожна кінцева гра має принаймні одне рішення, можливо, у сфері змішаних стратегій. 6 2. Ігри з сідловою точкою. Розв'язання в чистих стратегіях Гра з сідловою точкою - гра, для якої α = max min aij = min max aij = β i j j i Для ігор з сідловою точкою знаходження рішення полягає у виборі максимінної та міні-макcної стратегій, які є оптимальними. , Чиста ціна гри – загальне значення нижньої та верхньої ціни гри α=β=ν 2.1. Приклади Приклад 1 Знайти рішення у чистих стратегіях гри, заданої матрицею   8 4 7 A= 6 5 9  7 7 8 Рішення: визначимо верхню та нижню ціну гри. Для цього знайдемо мінімальне з чисел aij у i-му рядку αi = min aij j і максимальне з чисел aij у j-му стовпці βj = max aij i Числа αi (мінімуми рядків) випишемо поряд із платіжною матрицею праворуч у вигляді додаткового стовпця . Числа βi (максимуми стовпців) випишемо під матрицею у вигляді додаткового рядка: αi 8 4 7 4 6 5 9 5 7 7 8 7 βj 8 7 9 7 Знаходимо максимальне з чисел αi α = max αi = 7 i та мінімальне з чи βj β = min βj = 7 j α = β - гра має сідлову точку. Оптимальною стратегією для гравця є стратегія A3 , а для гравця B - стратегія B2 , чиста ціна гри ν = 7 Приклад 2 Задано платіжну матрицю:   2 2 1 1 2  0 1 1 1 1  A=  1 1 2   1 2 1 1 2 Знайти рішення гри у чистих стратегіях. Рішення: 2 2 1 1 2 1 0 1 1 1 1 0 1 1 1 1 2 1 1 2 1 1 2 1 βj 2 2 1 1 2 α = β = 1. Гра має шість сідлових точок. Оптимальними стратегіями будуть: A1 і B3 або B4 A3 і B3 або B4 A4 і B3 або B4 8 3. Рішення гри у змішаних стратегіях При α = β. у випадку, коли при виборі своїх стратегій обидва гравці не мають інформації про вибір іншого, гра має рішення у змішаних стратегіях. SA = (p1, p2, ..., pm) - змішана стратегія гравця A, в якій стратегії A1, A2, ..., Am застосовуються про ймовірності ∑ m p1, p2, ..., pm, pi = 1, pi > 0, i = 1, mi = 1 SB = (q1 , q2 , ..., qn) - змішана стратегія гравця B , в якій стратегії B1 , B2 , ..., Bm застосовуються про ймовірності ∑ n q1 , q2 , ..., qm , qi = 1, qi > 0, i = 1, n i=1 Якщо: SA∗ - оптимальна стратегія гравця A , SB∗ - - оптимальна стратегія гравця B , то ціна гри - ∑ n ∑ m ν = aij · p∗i · qi∗ j=1 i=1 Наступна теорема дає відповідь на питання, як знайти рішення для ігор 2×2, 2×n, m×2 Теоремма 2 (як знайти рішення для ігор 2×2, 2×n, m×2). Якщо один із гравців застосовує оптимальну змішану стратегію, то його виграш дорівнює ціні гри ν незалежно від того, з якими ймовірностями буде застосовувати другий гравець стратегії, що увійшли до оптимальної (в тому числі й чистої стратегії). 9 3.1. Гра 2×2 Розглянемо гру 2×2 про матрицю: () a11 a21 a21 a22 Нехай гра не має рішення у чистих стратегіях. Знайдемо оптимальні стратегії SA∗ та SB∗. Спочатку визначимо стратегію SA∗ = (p∗1, p∗2). Відповідно до теореми, якщо сторона A дотримуватиметься стратегії ν, то незалежно від способу дій сторони B виграш залишатиметься рівним ціні гри ν. Отже, якщо сторона A дотримується оптимальної стратегії SA∗ = (p∗1 , p∗2), то сторона B може, не змінюючи виграшу, застосовувати будь-яку зі своїх стратегій. Тоді при застосуванні гравцем B чистої стратегії B1 або B2 гравці отримає середній виграш рівний ціні гри: a11 p∗1 + a21 p∗2 = ν ← при стратегії B1 a12 p∗1 + a22 p∗2 = ν ← при стратегії B2 Приймаючи у увага, що p∗1 + p∗2 = 1: p∗1 = a2 2−a2 1 a11 +a22 −a12 −a21 p∗2 = a1 1−a1 2 a11 +a22 −a12 −a21 Ціна гри: a22 a11 − a12 a21 ν= a11 + a22 − a12 − a21 Аналогічно знаходиться оптимальна стратегія гравця B: SB∗ = (q1∗ , q2∗). Зважаючи на те, що q1∗ + q2∗ = 1: q1∗ = a2 2−a1 2 a11 +a22 −a12 −a21 q2∗ = a1 1−a2 1 a11 +a22 −a12 −a21 3.1.1. Приклади Приклад 3 Знайти рішення гри з матрицею () −1 1 A= 1 −1 10 Рішення: гра не має сідлової точки, оскільки α= -1, β = 1, α ̸= β. Шукаємо рішення у змішаних стратегіях. За формулами для p∗ та q ∗ отримуємо p∗1 = p∗2 = 0.5 і q1∗ = q2∗ = 0.5, ν = 0 Таким чином, SA∗ = (0.5, 0.5) SB∗ = (0.5, 0.5) Приклад 4 Знайти рішення гри з матрицею () 2 5 A= 6 4 Рішення: гра не має сідлової точки, оскільки α= 4, β = 5, α ̸= β. Шукаємо рішення у змішаних стратегіях. За формулами для p∗ та q ∗ отримуємо p∗1 = 0.4, p∗2 = 0.6 та q1∗ = 0.2 q2∗ = 0.8, ν = 4.4 Таким чином, SA∗ = (0.4, 0.6) SB∗ = (0.2, 0.8) 11 3.1.2. Геометрична інтерпретація Ігри 2×2 можна дати просту геометричну інтерпретацію. Візьмемо одиничну ділянку осі абсцис, кожній точці якого поставимо у відповідність деяку змішану стратегію S = (p1 , p2) = (p1 , 1 − p1) причому ймовірність p1 стратегії A1 дорівнюватиме відстані від точки SA до правого кінця ділянки, а ймовірність p2, стратегії A2 - відстані до лівого кінця. .y .I .I I .B1′ .N .B1 .a21 .a11 .I I .I .∗ .x .P2 .SA∗ .P1∗ Зокрема, лівий кінець ділянки (крапка з абсцисою = 0) відповідає стратегії A1 , правий кінець ділянки (x = 1) - стратегії A2 На кінцях ділянки відновлюються два перпендикуляри до осі абсцис: вісь I - I - відкладається виграш при стратегії A1 вісь II - II - відкладається виграш за стратегії A2 Нехай гравець B застосовує стратегію B1; вона дає на осях I - I і II - II відповідно точки з ординатами a11 і a21. Проводимо через ці точки пряму B1−B1′. За будь-якої змішаної стратегії SA = (p1 , p2) виграш гравця визначається точкою N на прямій B1 −B1′ , що відповідає точці SA на осі абсцис, що ділить відрізок щодо p2: p1 . Очевидно, таким же способом може бути побудована і пряма B2 − B2′ , що визначає виграш при стратегії B2 . 12 .y .I .I I .B2 .N .a21 .B2′ a . 22 .I I .I .∗ .x .P2 .SA∗ .P1∗ Необхідно знайти оптимальну стратегію SA∗ , тобто. таку, за якої мінімальний виграш гравця A (за найгіршої для нього поведінки гравця B) звертався б у максимум. І тому будуватися нижня межа виграшу гравця A при стратегіях B1 , B2 , тобто. ламана B1 N B2′;. На цьому кордоні лежатиме мінімальний виграш гравця A за будь-якої його змішаної стратегії, точка N , в якій цей виграш досягає максимуму та визначає рішення та ціну гри. .y .I .I I .B2 .B1′ .N .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S . 1∗ P Ордината точки N є нічим іншим, як ціна гри ν, її абсцис дорівнює ∗2 , а відстань до правого кінця відрізка дорівнює ∗1 , тобто. відстань від точки SA∗ до кінців відрізка дорівнюють ймовірностям ∗2 і ∗1 стратегій A2 та A1 оптимальної змішаної стратегії гравця A. в даному випадку рішення гри визначалося точкою перетину стратегій B1 та B2. Нижче наведено випадок, коли оптимальною стратегією гравця є чиста стратегія A2 . Тут стратегія A2 (при будь-якій стратегії противника) вигідніша за стратегію A1 , 13 .y .y .I .I I .I I. I .B2′ . 1′ B .B1′ B . 2 .B2′ B . 2 .B1 .ν = a21 .B1 .ν = a21 I. I I. I.I. .x .I. .x. 2∗ P . A∗ S = A2. 2∗ P . A∗ S = A2 Правіше показаний випадок, коли явно невигідна стратегія є у гравця B. Геометрична інтерпретація дає можливість наочно зобразити також нижню ціну гри α і верхню β .y .I .I .I I .B2 .B1′ .N .B1 . B2′ .β = a21 .α = a22 .I I .I .∗ .x .P2 . A∗ S . 1∗ P На тому ж графіку можна дати і геометричну інтерпретацію оптимальних стратегій гравця B . Неважко переконатися, що частка q1∗ стратегії B1 оптимальної змішаної стратегії SB∗ = (q1∗ , q2∗) дорівнює відношенню довжини, відрізка KB2 до суми довжин відрізків KB1 і KB2 на осі I - I: .y .I .I . B1′ .N .K .L .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S . 1∗ P 14 KB2 q1∗ = KB2 + KB1 або LB2′ q1∗ = LB2′ + LB1′ Оптимальну стратегію SB∗ = (q1∗ , q2∗) можна знайти й іншим способом, якщо поміняти місцями гравців B та B, а замість максимуму нижньої межі виграшу розглянути мінімум верхньої межі. .y .I .I I .A2 .A′1 .N .A1 .A′2 .I I .I . .x .q2∗ . B∗ S .q1∗ 15 3.2. Ігри 2×n та m×2 Розв'язання ігор 2×n та m×2 ґрунтується на наступній теоремі. Теоремма 3. Будь-яка кінцева гра m × n має рішення, в якому число активних стратегій кожної сторони не перевищує найменшого з чисел m і n. Відповідно до цієї теореми у гри 2 × n завжди є рішення, в якому кожен гравець має не більше двох активних стратегій. Варто тільки знайти ці стратегії, і гра 2×n перетворюється на гру 2×2, яка вирішується елементарно. Знаходження активних стратегій може виконуватись графічним способом: 1) будується графічна інтерпретація; 2) визначається нижня межа виграшу; 3) виділяються на нижній межі виграшу дві стратегії другого гравця, яким відповідають дві прямі, що перетинаються в точці з максимальною ординатою (якщо в ній перетинаються більше двох прямих, береться будь-яка пара) - ці стратегії є активними стратегіями гравця B. Таким чином , гра 2 × n зведена до гри 2 × 2. Також може бути вирішена гра m × 2 з тією різницею, що будується не нижня, а верхня межа виграшу і на ній шукається не максимум, а мінімум. Приклад 5 Знайти рішення гри () 7 9 8 A= 10 6 9 Рішення: використовуючи геометричний метод, виділяємо активні стратегії. Прямі B1 − B1′, B2 − B2′ та B3 − B3′ відповідають стратегіям B1, B2, B3. Ламана B1 N B2 – нижня межа виграшу гравця. Гра має рішення S∗A = (23, 31); S∗B = (0.5; 0.5; 0); v = 8. 16 .y .I .I I . 1′ B B . 2 .B3′ .N .B3 .B1 .B2′ .I I .I . .x. 2∗ P . A∗ S . 1∗ P 17 Предметний покажчик гра, 2 хід, 3 2 × 2, 10 особистий, 3 2 × 2, 9 випадковий, 3 геометрія, 12 чиста ціна гри, 7 приклади, 10 2 × n, 9, 16 m × 2, 9, 16 нескінченна, 4 у нормальній формі, 5 кінцева, 4 багатоходова, 4 одноходова, 4 матрична, 5 парна, 2 c нульовою сумою, 2 антагоністична, 2 неантагоністична, 2 рішення, 5 у змішаних стратегіях, 5, 9 у чистих стратегіях , 5 з сідловою точкою, 7 ціна, 5 верхня, 6 нижня, 6 чиста, 7 максимін, 6 матриця гри, 5 платіжна, 5 мінімакс, 6 нормалізація гри, 5 стратегія, 4 максимінна, 6 мінімаксна, 6 оптимальна, 4 змішана 5 теорія ігор, 2 18