Теорія ігор є математичною теорією оптимальної поведінки в умовах конфліктної ситуації. Предмет її вивчення – формалізована модель конфлікту чи так звана «гра».

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

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

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

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

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

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

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

У кожній грі вирішуються три основні питання:

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

Чи реалізується таке розуміння оптимальності?

Чи існують відповідні стратегії?

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

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

та рекомендації щодо вибору стратегій залежать від багатьох факторів.

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

Теоретично ігор грою називається

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

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

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

Рейнхард Селтен в 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. Матрична гра. Використання симплексного методу. Знаходимо гарантований виграш, який визначається нижньою ціною гри a = max(a i) = 2, яка вказує на максимальну чисту стратегію A 1 .
2. Приклад рішення матричної гри методом лінійного програмування. Вирішити матричну гру методом лінійного програмування.

Дайте графічну виставу, приведіть до нормальної форми і знайдіть точне рішення позиційної гри з наступною функцією виграшів:
1-й хід робить гравець А: він вибирає число x з двох чисел.
2-й хід робить гравець: не знаючи про вибір гравця А на 1-му ході, він вибирає число y з безлічі двох чисел.
3-й хід робить гравець А: він вибирає число z з двох чисел, знаючи значення y, обране гравцем В на 2-му ході, але не пам'ятаючи власного вибору x на 1-му ході.

Ігри із природою

1. Статистичні ігри
   Сільськогосподарське підприємство може реалізувати деяку продукцію:
   А1) відразу після збирання;
   А2) у зимові місяці;
   А3) у весняні місяці.
   Прибуток залежить від ціни реалізації в даний період часу, витратами на зберігання та можливих втрат. Розмір прибутку, розрахований для різних станів-співвідношень доходу та витрат (S1, S2 та S3), протягом усього періоду реалізації, представлений у вигляді матриці (млн.руб.)
2. Фірма виробляє сукні та костюми, реалізація яких залежить від стану погоди. Витрати фірми протягом квітня-травня на одиницю продукції становитимуть...
3. Розв'язання задачі про запаси сировини. За деякий період часу на підприємстві споживання вихідної сировини в залежності від її якості становить 1 , 2 , 3 і 4 .
4. Стратегії крайнього песимізму, крайнього оптимізму та оптимізму-песимізму

Біматричні ігри

Дерево розв'язків у теорії ігор (приклад розв'язання задачі).

див. також збірник рішень з теорії ігор (вирішення матричних ігор), типові завдання з ЕММ (лінійне програмування, теорія ігор).

У місті працюють три телекомпанії: АВС, СВSі NВС. Ці компанії можуть розпочинати програму вечірніх новин о 6.30 або о 7.00. 60% телеглядачів вважають за краще дивитися вечірні новини о 6.30, а 40% — о 7.00. Найбільш популярна програма вечірніх новин у компанії АВСНайменшою популярністю користуються новини, підготовлені компанією NВС. Частка телеглядачів вечірніх програм новин представлена ​​в таблиці (NBС, СВS, АВС)

Знайти оптимальні стратегії компаній за часом показу програм новин

Вказівка ​​до рішення: у грі існує домінована стратегія

Із популярного американського блогу Cracked.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дар'я Золотих 09.02.2015

Сподобався піст?
Підтримай Фактрум, натисніть:

Зміст 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. Стратегії Стратегія гравця - сукупність правил, що визначають вибір дій при кожному особистому ході цього гравця в залежності від ситуації, що склалася в процесі гри. Залежно від кількості можливих стратегій гри діляться на кінцеві та нескінченні.Нескінченна гра - Гра, в якій хоча б один з гравців має нескінченну кількість стратегій.Кінцева гра - гра, у якій кожен гравець має лише кінцеве число- стратегій. Число послідовних ходів у будь-якого з гравців визначає підрозділ ігор на одноходові та багатоходові, або позиційні. + В одноходовій грі кожен гравець робить лише один вибір із можливих варіантів і після цього встановлює результат гри. дій. Відповідно до обраних способів дій (стратегіями) визначається досягається результат. Розглянемо з прикладу. Нехай є два гравці 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, що програє, тобто гравця, який прагне мінімізації критерію ефективності. Очевидно, що при виборі найбільш обережної мінімаксної стратегії гравець B не дає можливості за жодних обставин гравцеві A виграти більше, ніж β. Нижня ціна гри завжди не перевищує верхню ціну гри α = max min aij 6 min max aij = β i j j i Теорема 1 (основна теорема теорії матричних ігор). Кожна кінцева гра має принаймні одне рішення, можливо, у сфері змішаних стратегій. + Багатоходова, або позиційна, гра розвивається в часі, являючи собою ряд послідовних етапів, кожен з яких настає після перебігу одного з гравців та відповідної зміни обстановки. В одноходовій грі кожен гравець робить тільки один вибір зα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 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. Рішення гри в змішаних стратегіях При α = β. у випадку, коли при виборі своїх стратегій обидва гравці не мають інформації про вибір іншого, гра має рішення у змішаних стратегіях. Шукаємо рішення у змішаних стратегіях. За формулами для 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 - відстані до лівого кінця. оптимальною стратегієюгравця є чиста стратегія 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) будується графічна інтерпретація;