Теорія ігор

Матеріал з Вікіпедії — вільної енциклопедії.

Теорія ігор — теорія математичних моделей прийняття оптимальних рішень в умовах конфлікту.

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

Зміст

1 Поняття теорії ігор
2 Класифікація ігор
3 Математичний апарат
- 3.1 Оптимальність та розв'язки
4 Історія
5 Джерела інформації
6 Дивіться також

[ред.] Поняття теорії ігор

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

Конфлікт,
Прийняття рішення в конфлікті,
Оптимальність прийнятого рішення.

Ці поняття розглядаються в теорії ігор у найширшому сенсі. Їх формалізації відповідають змістовним уявленням про відповідні об'єкти.

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

Якщо назвати учасників конфлікту коаліціями дії (позначивши їхню множину як ℜ_D, можливі дії кожної із коаліції дії — її стратегіями (множина всіх стратегій коаліції дії K позначається як S), результати конфлікту — ситуаціями (множина всіх ситуацій позначається як S; вважається, що кожна ситуація складається внаслідок вибору кожної із коаліцій дії деякої своєї стратегії, так, що $S \subset \prod_{K \in \Re} S_K$ ), зацікавлені сторони — коаліціями інтересів (їх множина — ℜ_I) і, нарешті, говорити про можливі переваги для кожної коаліції інтересів K однієї ситуації s′ перед іншою s″ (цей факт позначається як $s^\prime \mathop{\prec}_{K} s^{\prime\prime}$ ), то конфлікт в цілому може бути описаний як система

$\Gamma = \langle \Re_D,\, \{S_K\}_{K\in\Re_D},\, S,\, \Re_I,\, \{\mathop{\prec}_{K}\}_{K\in\Re_I} \rangle$ .

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

[ред.] Класифікація ігор

Якщо в грі є лише одна коаліція дії K, можна вважати, що множина ситуацій S співпадає з множиною стратегій S_K. Такі ігри називаються нестратегічними. До них відносяться ігри без побічних платежів і класичні кооперативні ігри, разом з їхніми різновидами. Якщо в грі множини коаліцій дії та коаліцій інтересів співпадають (ℜ_D = ℜ_I = I; в цьому випадку і ті, і інші коаліції називаються гравцями), $S = \prod_{i\in I}S_i$ , а відношення переваги називаються функціями виграшу, то отримуємо безкоаліційні ігри.

Окремими класами безкоаліційних ігор є

антагоністичні ігри, у тому числі матричні ігри та ігри на одиничному квадраті.
динамічні ігри, у тому числі диференційні ігри,
рекурсивні ігри,
ігри на виживання

й інші, також належать до безкоаліційних ігор.

[ред.] Математичний апарат

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

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

[ред.] Оптимальність та розв'язки

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

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

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

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

[ред.] Історія

Як математична дисципліна, теорія ігор зародилась одночасно з теорією ймовірностей в 17 столітті, але протягом майже 300 років майже не розвивалась. Першою істотною роботою по теорії ігор слід вважати статтю Дж. фон Ноймана «До теорії стратегічних ігор» (1928), а з виходом в світ монографії американських математиків Дж. фон Ноймана та О. Моргенштерна «Теорія ігор і економічна поведінка» (1944), теорія ігор сформувалась як самостійна математична дисципліна. На відміну від інших галузей математики, які мають переважно фізичне, або фізико-технологічне походження, теорія ігор із самого початку свого розвитку була направлена на розв'язання задач, які виникають в економіці (а саме в конкурентній економіці).

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

[ред.] Джерела інформації

Енциклопедія кібернетики, Воробйов Н. Н., т. 1, ст. 333-334.

[ред.] Дивіться також

	Статті теорії ігор
Типи ігор	антагоністичні · диференціальні · матричні · на виживання · рефлексивні · азартні · без побічних платежів · безкоаліційні · біматричні · вироджені · динамічні · з вибором моменту часу · кооперативні · на графі · на одиничному квадраті · опуклі · позиційні · прості · рекурсивні · стохастичні
Ситуації	Безвиграшна ситуація · Парадокс Бертрана (економіка) · Ситуація рівноваги
Стратегія	змішана · оптимальна · поведінки · чиста
Теореми	Максіміна принцип · Мінімаксу теорема
Ігри	Дилема в'язня