Кооперативна гра (теорія ігор)

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

Основи теорії кооперативних ігор розробили американські вчені Дж. фон Нейман та Моргенштерн Оскар. Спочатку, конструювання кооперативних ігор робилось на основі безкоаліційних ігор. А саме, в грі з множиною гравців I, для кожної коаліції K ⊂ I розглядали антагоністичну гру K проти додаткової до неї коаліції I\K. Значення цієї гри, яке позначається як ν(K), є функцією від K, яка називається характеристичною функцією. Деякі кооперативні ігри можуть бути задані безпосередньо своїми характеристичними функціями. Прикладами таких ігор є схеми голосування, а також моделі ринків.

Формальне визначення

Кооперативну гру визначають формально як пару <I, ν>, де I = {1, 2, …, n} — множина гравців, а ν — характеристична функція, визначена на підмножинах I. Вектор виграшів гравців є розподілом гри. Як множину всіх розподілів, як правило, беруть

A=\left\{x=(x_{1},...,x_{n})\in E^{n}:\;x_{i}\geq \nu (i),\;\sum _{i=1}^{n}x_{i}=\nu (I)\right\}

На цій множині визначають відношення домінування: розподіл x=(x₁, …, x_n) домінує (домінує над) розподіл y=(y₁, …, y_n) (позначення $x\succ y$ ), якщо знайдеться така коаліція K, що

\sum _{i\in K}x_{i}\leq \nu (K)

та x_i>y_i для всіх i∈ K.

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

Множина елементів, максимальних відносно домінування, називається c-ядром. Для відношення домінування розподілів, важливу роль грає розв'язок по Нейману-Моргенштерну. Однак, нормативна сутність розв'язку має ряд недоліків: розв'язок може складатись більш ніж із одного розподілу; він може бути не єдиним; відомий приклад гри (десяти осіб), яка не має розв'язку.

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

Джерела інформації

Енциклопедія кібернетики, Бондарева О. Н., т. 1, с. 337.

Див. також

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.