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

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

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 складатиметься тільки з другого гравця, і таке інше.

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

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

Деякі визначення гри

Кількісна оцінка результатів гри називається платежем.

Парна гра (Дві особи) називається грою з нульовою сумою, якщо сума платежів дорівнює нулю, тобто. якщо програш одного гравця дорівнює виграшу іншого.

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

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

Гра, що визначається матрицею А, що має mрядків та nстовпців, називається кінцевою парною грою розмірності m* n;

де i=
- стратегія першого гравця, що має стратегій; j=- стратегія другого гравця, що має стратегій; ij- Виграш першого гравця по i-ї стратегії при використанні другим j-ї стратегії (або, що те саме, програш другого за своєю j-ї стратегії, при використанні першим i-й);

А =   ij - платіжна матриця гри.

1.1 Гра із чистими стратегіями

Нижня ціна гри (для першого гравця)

 = max (min ij). (1.2)

i j

Верхня ціна гри (для другого гравця):

= min (max ij) . (1.3)

J i

Якщо  =  гра називається з сідловою точкою (1.4), або гра з чистими стратегіями. При цьому V =  =  називають цінної гри ( V- Ціна гри).

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

(1.4)

max 10 9 12 6

i

min 6

j

- Стратегія першого гравця (рядки).

Стратегія другого гравця (стовпці).

- Ціна гри.

Таким чином, гра має сідлову точку. Стратегія j = 4 – оптимальна для другого гравця, стратегія i=2 – для першого. Маємо гру із чистими стратегіями.

1.2 Ігри зі змішаними стратегіями

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

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

Х= (х 1 …х i …х m) - Змішана стратегія першого гравця.

У= (у 1 …у j …у n) - Змішана стратегія другого гравця.

xi , у j- Відносні частоти (ймовірності) використання гравцями своїх стратегій.

Умови використання змішаних стратегій

. (1.5)

Якщо Х* = (х 1 * ….х i * … х m*) – оптимальна стратегія, обрана першим гравцем; Y* = (у 1 * …у j * … у n*) – оптимальна стратегія, обрана другим гравцем, число є ціною гри.

(1.6)

Для того, щоб число Vбуло ціною гри, а х* і у* - оптимальними стратегіями, необхідно і достатньо виконання нерівностей

(1.7)

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

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

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

А = (1.8)

y 1 y 2 y 3

Рішення:

Складемо подвійну пару завдань лінійного програмування.

Для першого гравця

(1.9)

у 1 +у 2 +у 3 = 1 (1.10)

Звільняючись від змінної V(ціна гри), розділимо ліву та праву частину виразів (1.9), (1.10) на V. Прийнявши у j /Vза нову змінну z i, отримаємо нову системуобмежень (1.11) та цільову функцію (1.12)

(1.11)

. (1.12)

Аналогічно отримаємо модель гри для другого гравця:

(1.13)

х 1 +х 2 +х 3 = 1 . (1.14)

Привівши модель (1.13), (1.14) до форми без змінної V, отримаємо

(1.15)

, (1.16)

де
.

Якщо необхідно визначити стратегію поведінки першого гравця, тобто. відносну частоту використання його стратегій ( х 1 ….х i …х m), ми використовуватимемо модель другого гравця, т.к. ці змінні перебувають у його моделі виграшу (1.13), (1.14).

Наведемо (1.15), (1.16) до канонічної форми

(1.17)

Зміст 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. Теорія ігор - це математична теорія конфліктних ситуацій, тобто. таких ситуацій, у яких стикаються інтереси двох або більше сторін, які мають різні цілі. Гра - це конфліктна ситуація, регламентована певними правилами, в яких мають бути зазначені: можливі варіанти дій учасників кількісний результат гри або платіж (виграш, програш), до якого приводить дана сукупність ходів обсяг інформації кожної сторони про поведінку іншої. Парна гра - гра в якій беруть участь лише дві сторони (два гравці).одного з передбачених правилами гри дій + здійснення цього вибору Випадковий хід - Випадковим ходом називається вибір із ряду можливостей, що здійснюється не рішенням гравця, а будь-яким механізмом випадкового вибору. Нижче розглядаються парні ігри з нульовою сумою, що містять лише особисті ходи. Кожна сторона не має інформації про поведінку іншої. 3 1.3. Стратегії Стратегія гравця - сукупність правил, що визначають вибір дій при кожному особистому ході цього гравця в залежності від ситуації, що склалася в процесі гри. Залежно від кількості можливих стратегій гри діляться на кінцеві та нескінченні.Нескінченна гра - Гра, в якій хоча б один з гравців має нескінченну кількість стратегій.Кінцева гра - гра, у якій кожен гравець має лише кінцеве число- стратегій. Число послідовних ходів у будь-якого з гравців визначає підрозділ ігор на одноходові та багатоходові, або позиційні. + В одноходовій грі кожен гравець робить лише один вибір із можливих варіантів і після цього встановлює результат гри.+ Багатоходова, або позиційна, гра розвивається в часі, являючи собою ряд послідовних етапів, кожен з яких настає після перебігу одного з гравців та відповідної зміни обстановки. В одноходовій грі кожен гравець робить тільки один вибір з можливих варіантів з 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, що програє, тобто гравця, який прагне мінімізації критерію ефективності. Кожна кінцева гра має принаймні одне рішення, можливо, у сфері змішаних стратегій. і після цього встановлює результат гри. Оптимальна стратегія гравця - стратегія, яка за багаторазового повторення гри забезпечує даному гравцеві максимально можливий середній виграш (або, що те саме, мінімально можливий середній програш). α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. Рішення гри у змішаних стратегіях При α = β. у випадку, коли при виборі своїх стратегій обидва гравці не мають інформації про вибір іншого, гра має рішення у змішаних стратегіях. Тоді при застосуванні гравцем 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 - відстані до лівого кінця. таку, за якої мінімальний виграш гравця A (за найгіршої для нього поведінки гравця B) звертався б у максимум. І тому будуватися нижня межа виграшу гравця A при стратегіях B1 , B2 , тобто. ламана B1 N B2′;. На цьому кордоні лежатиме мінімальний виграш гравця A за будь-якої його змішаної стратегії, точка N , в якій цей виграш досягає максимуму та визначає рішення та ціну гри. Теоретично ігор всі рекомендації виробляються з припущення про розумному поведінці гравців. Прорахунки та помилки гравців, неминучі в кожній конфліктній ситуації, а також елементи азарту та ризику в теорії ігор не враховуються.гравця є чиста стратегія 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) визначається нижня межа виграшу;

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

1. Дилема ув'язненого

Берто і Роберт заарештували за пограбування банку, не зумівши правильно використовувати для втечі викрадений автомобіль. Поліція не може довести, що саме вони пограбували банк, але спіймала їх на місці злочину в вкраденому автомобілі. Їх розвели по різних кімнатах і кожному запропонували угоду: здати спільника та відправити його за ґрати на 10 років, а самому вийти на волю. Але якщо вони обидва здадуть один одного, то кожен отримає по 7 років. Якщо ж ніхто нічого не скаже, то обидва сядуть на 2 роки тільки за викрадення автомобіля.

Виходить, що коли Берто мовчить, але Роберт здає його, Берто сідає у в'язницю на 10 років, а Роберт виходить на волю.

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

Практичне застосування: Виявлення соціопатів

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

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

Найгірше те, що всі учасники дилеми ув'язненого діють так, ніби ніколи не чули її.

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

2. Домінуюча стратегія

Це ситуація, коли ваші дії дають найбільший виграш, незалежно від дій опонента.Що б не відбувалося – ви все зробили правильно. Ось чому багато людей при «дилемі ув'язненого» вважають: зрада призводить до «найкращого» результату незалежно від того, що робить інша людина, а ігнорування дійсності, властиве цьому методу, змушує виглядати супер-просто.

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

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

3. Битва статей

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

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

- просто бути з іншою людиною, і нуль – бути на самоті. спрощена теорія ігор добре виявляє дурнів.

Практичне застосування: Уникайте гострих кутів

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

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

4. Рівновага Неша

Рівновага Неша - це набір ходів, де ніхто не хоче зробити щось по-іншому після доконаного факту.І якщо ми зможемо змусити це працювати, теорія ігор замінить всю філософську, релігійну та фінансову систему на планеті, тому що «бажання не прогоріти» стало для людства потужнішою рушійною силою, ніж вогонь.

Давайте швидко поділимо 100 $. Ви і я вирішуємо, скільки з сотні ми вимагаємо та одночасно озвучуємо суми. Якщо наша загальна сума менша за сто, кожен отримує те, що хотів. Якщо загальна кількість більше ста, той, хто попросив найменшу кількість, отримує бажану суму, а жадібніша людина отримує те, що залишилося. Якщо ми просимо однакову суму, кожен отримує 50$. Скільки ви попросите? Як ви поділите гроші? Існує єдиний виграшний перебіг.

Вимога 51$ дасть вам максимальну суму незалежно від того, що вибере ваш супротивник. Якщо він попросить більше, ви отримаєте 51$. Якщо він попросить 50$ або 51$, ви отримаєте 50$. І якщо він попросить менше 50$, ви отримаєте 51$. У будь-якому випадку немає жодного іншого варіанту, який принесе вам більше грошей, ніж цей. Рівновага Неша - ситуація, в якій ми обидва вибираємо 51$.

Практичне застосування: спочатку думайте

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

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

5. Гра в орлянку

В орлянці беруть участь Гравець 1 та Гравець 2. Кожен гравець одночасно вибирає орла чи решку. Якщо вони вгадують, Гравець 1 отримує пенс Гравця 2. Якщо ж ні – Гравець 2 отримує монету Гравця 1.

Виграшна матриця проста…

…оптимальна стратегія: грайте повністю навмання.Це складніше, ніж ви думаєте, тому що вибір має бути абсолютно випадковим. Якщо у вас є переваги орла або решки, противник може використовувати його, щоб забрати гроші.

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

Практичне застосування: Пенальті

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

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

Отже, який наш висновок відповідно до теорії ігор? Ігри з м'ячем повинні закінчуватися способом «мультим'ячу», де кожну хвилину гравцям віч-на-віч виводиться додатковий м'яч/шайба, до отримання однієї зі сторін певного результату, який був показником справжньої майстерності гравців, а не ефектним випадковим збігом.

Зрештою, теорія ігор повинна використовуватися для того, щоб зробити гру розумнішою. Отже краще.