№ 19 Теорія ігор: введення з пісочниці
Відео: Стрим пісочниці 24.06.2016
Що це таке, і з чим його їдять.
теорія ігор - це розділ математичної економіки, що вивчає рішення конфліктів між гравцями і оптимальність їх стратегій. Конфлікт може ставитися до різних областей людського інтересу: найчастіше це економіка, соціологія, політологія, рідше біологія, кібернетика і навіть військова справа. Конфліктом є будь-яка ситуація, в якій порушені інтересу двох і більше учасників, які традиційно називають гравцями. Для кожного гравця існує певний набір стратегій, які він може застосувати. Перетинаючись, стратегії декількох гравців створюють певну ситуацію, в якій кожен гравець отримує певний результат, званий виграшем, позитивним або негативним. При виборі стратегії важливо враховувати не тільки отримання максимального профіту для себе, але так само можливі кроки супротивника, і їх вплив на ситуацію в цілому.
Коротка історія розвитку.
Основи теорії ігор зародилися ще в 18 столітті, з початком епохи просвящения і розвитком економічної теорії. Вперше математичні аспекти та застосування теорії були викладені в класичній книзі 1944 року Джона фон Неймана і Оскара Моргенштерна «Теорія ігор і економічна поведінка». Перші концепції теорії ігор аналізували антагоністичні гри, коли є ті, хто програв і виграли за їх рахунок гравці. Не дивлячись на те, що теорія ігор розглядала економічні моделі, аж до 50-х років 20 століття вона була всього лише математичною теорією. Після, в результаті різкого стрибка економіки США після другої світової війни, і, як наслідок, більшого фінансування науки, починаються спроби практичного застосування теорії ігор в економіці, біології, кібернетиці, техніці, антропології. Під час Другої світової війни і відразу після неї теорією ігор серйозно зацікавились військові, які побачили в ній потужний апарат для дослідження стратегічних рішень. На початку 50-х Джон Неш (на фото) розробляє методи аналізу, в яких всі учасники або виграють, або зазнають поразки. Ці ситуації отримали назви «рівновагу Неша». За його теорією, сторони повинні використовувати оптимальну стратегію, що призводить до створення стійкої рівноваги. Гравцям вигідно зберігати цю рівновагу, так як будь-яка зміна погіршить їхнє становище. Ці роботи Неша зробили серйозний внесок в розвиток теорії ігор, були переглянуті математичні інструменти економічного моделювання. Джон Неш показує, що класичний підхід до конкуренції А. Сміта, коли кожен сам за себе, неоптимальний. Більш оптимальні стратегії, коли кожен намагається зробити краще для себе, роблячи краще для інших. За останні 20 - 30 років значення теорії ігор і інтерес значно зростає, деякі напрямки сучасної економічної теорії неможливо викласти без застосування теорії ігр.Большім внеском в застосування теорії ігор стала робота Томаса Шеллінга, нобелівського лауреата з економіки 2005 року "Стратегія конфлікту».
Як це працює
Як мені здається, сенс теорії ігор найпростіше пояснити на «Проблемі ув`язненого», класична формулювання якої звучить так:
Двоє злочинців, А і Б, попалися приблизно в один і той же час на подібних злочинах. Є підстави вважати, що вони діяли за змовою, і поліція, ізолювавши їх один від одного, пропонує їм одну і ту ж операцію: якщо один свідчить проти іншого, а той мовчить, то перший звільняється за допомогу слідству, а другий отримує максимальний термін позбавлення волі (10 років). Якщо обидва мовчать, їх діяння проходить по більш легкої статті, і вони засуджуються до 6 місяців. Якщо обидва свідчать проти один одного, вони отримують мінімальний термін (по 2 роки). Кожен ув`язнений вибирає, мовчати або свідчити проти іншого. Однак жоден з них не знає точно, що зробить інший. Що станеться?Представивши гру у вигляді матриці ми отримаємо:
| злочинець Б Стратегія «мовчати» | злочинець Б Стратегія «зрадити» | |
|---|---|---|
| злочинець А Стратегія «мовчати» | Пів року кожному | 10 Років злочинцеві А Відпустити злочинця Б |
| злочинець А Стратегія «зрадити» | 10 Років злочинцеві Б Відпустити злочинця А | 2 роки кожному |
А тепер уявімо розвиток ситуації, поставивши себе на місце укладеного А. Якщо мій подільник мовчить, краще його здати і вийти на свободу. Якщо він говорить, то так само краще все розповісти, і отримати лише два роки, замість десяти. Таким чином, якщо кожен гравець вибирає, що краще для нього, обидва здадуть один одного, і отримають два роки, що не є ідеальною ситуацією для обох. Якби кожен думав про загальне благо, вони б отримали всього по пів року.
типи ігор
Кооперативна некооперативна гра
Кооперативної грою є конфлікт, в якому гравці можуть спілкуватися між собою і об`єднуватися в групи для досягнення найкращого результату. Прикладом кооперативної гри можна вважати карткову гру Брідж, де окуляри кожного гравця вважаються індивідуально, але виграє пара, яка набрала найбільшу суму. З двох типів ігор, некооперативного описують ситуації в найдрібніших деталях і видають більш точні результати. Кооперативні розглядають процес гри в цілому. Не дивлячись на те, що ці два види протилежні одна одній, цілком можливе об`єднання стратегій, яке може принести більше користі, ніж проходження будь-якої однієї.
З нульовою сумою і з ненульовою сумою
Грою з нульовою сумою називають гру, в якій виграш одного гравця дорівнює програшу іншого. Наприклад банальна суперечка: якщо ви виграли суму N, то хтось цю ж суму N програв. У грі ж з ненульовою сумою може змінюватися загальна ціна гри, таким чином приносячи вигоду одному гравцеві, що не забираю її ціну в іншого. Як приклад тут відмінно підійдуть шахи: перетворюючи пішака на ферзя гравець А збільшує загальну суму своїх фігур, при цьому не віднімаючи нічого у гравця Б. В іграх з ненульовою сумою програш одного з гравців не є обов`язковою умовою, хоча такий результат і не виключається.
Відео: Unity3d 19 Створення пісочниці
Паралельні і послідовні
Паралельної є гра, в якій гравці роблять ходи одночасно, або хід одного гравця невідомий іншому, поки не завершиться загальний цикл. У послідовній грі кожен гравець володіє інформацією про попередніх ході свого опонента до того, як зробити свій вибір. І зовсім не обов`язково інформації бути повною, що підводить на з Кльод типу.
З повною або неповною інформацією
Ці типи є підвидом послідовних ігор, і назви їх говорять самі за себе.
Відео: Алгоритми програмування і структури даних / Університет ИТМО
Метаігри
Ці ігри є «лемами» теорії ігор. Вони корисні не самі по собі, а в контексті будь-якого конфліката, розширюючи його набір правил.
У будь-якому конфлікті типи об`єднуються, визначаючи таким чином правила гри, будь це кооперативна послідовна гра з нульовою сумою, або метаігра з неповною інформацією.
Відео: Граю з сином в CRAFT the WORLD # 2
Проблеми практичного застосування
Безумовно, слід вказати і на наявність певних меж застосування аналітичного інструментарію теорії ігор. У таких випадках він може бути використаний лише за умови отримання додаткової інформації.
По-перше, це той випадок, коли у гравців склалися різні уявлення про гру, в якій вони беруть участь, або коли вони недостатньо поінформовані про можливості один одного. Наприклад, може мати місце неясна інформація про платежі конкурента (структурі витрат). Якщо неповнотою характеризується не дуже складна інформація, то можна застосовувати досвід подібних випадків з урахуванням певних відмінностей.
По-друге, теорію ігор важко застосовувати при безлічі ситуацій рівноваги. Ця проблема може виникнути навіть у ході простих ігор з одночасним вибором стратегічних рішень.
По-третє, якщо ситуація прийняття стратегічних рішень дуже складна, то гравці часто не можуть вибрати кращі для себе варіанти. Наприклад, на ринок в різні терміни можуть вступити кілька підприємств або реакція вже діючих там підприємств може виявитися складнішим, ніж бути агресивною або дружньою.
Експериментально доведено, що при розширенні гри до десяти і більше етапів гравці вже не в змозі користуватися відповідними алгоритмами і продовжувати гру з рівноважними стратегіями.
На жаль, ситуації реального світу часто дуже складні і настільки швидко змінюються, що неможливо точно спрогнозувати, як відреагують конкуренти на зміну тактики. Проте, теорія ігор корисна, коли потрібно визначити найбільш важливі і вимагають обліку чинники в ситуації прийняття рішень в умовах конкурентної боротьби. Ця інформація важлива, оскільки дозволяє врахувати додаткові змінні або фактори, які мають можливість вплинути на ситуацію, і тим самим підвищити ефективність вирішення.
висновок
На закінчення слід особливо підкреслити, що теорія ігор є дуже складною областю знання. При зверненні до неї треба дотримуватися дуже обережним і чітко знати межі застосування. Занадто прості тлумачення таять в собі приховану небезпеку. Аналіз і консультації на основі теорії ігор через їх складності рекомендуються лише для особливо важливих проблемних областей. Досвід показує, що використання відповідного інструментарію переважно при прийнятті одноразових, принципово важливих планових стратегічних рішень, в тому числі при підготовці великих коопераційних договорів.
Якщо тема виявиться цікавою для спільноти, наступних статтях я спробую докладніше розкрити типи ігор і їх стратегії.
