Розділ 11. Кооперативні ігри

11.1 Характеристика кооперативних ігор

Кооперативні ігри виходять у тих випадках, коли, у грі n гравцям дозволяється утворювати визначені коаліції. Позначимо через N множину усіх гравців, N ={1, 2, ..., n}, а через K – будь-яку її підмножину. Нехай гравці з K домовляються між собою про спільні дії і, таким чином, утворять одну коаліцію. Очевидно, що число таких коаліцій, що складаються з r гравців, дорівнює числу сполучень з n по r , тобто , а число всіляких коаліцій дорівнює

= 2ⁿ – 1.

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

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

Характеристична функція  називається простою, якщо вона приймає тільки два значення: 0 і 1. Якщо характеристична функція  проста, то коаліції K, для яких (K)=1, називаються коаліціями, що виграють, а коаліції K, для яких (K) = 0, – що програють.

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

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

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

Найпростіша характеристична функція з'являється тоді, коли в голосуючому колективі є якесь “ядро”, що голосує з дотриманням правила “вето”, а голоси інших учасників виявляються несуттєвими.

Позначимо через _G характеристичну функцію безкоаліційної гри. Ця функція має такі властивості:

- персональність:_G() = 0,

тобто коаліція, що не містить жодного гравця, нічого не виграє;

- суперадитивність: _G(KL)  _G(K) + _G(L), якщо K, L  N, KL  ,

тобто загальний виграш коаліції не менше сумарного виграшу всіх учасників коаліції;

- додатковість: _G(K) + (N\K) = (N), (11.1)

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

Розподіл виграшів гравців повинен задовольняти таким умовам: якщо позначити через x_i виграш i-го гравця, то, по-перше, повинна задовольнятися умова індивідуальної раціональності

X_i  ( i ), для i N , (11.2)

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

= (N), (11.3)

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

Таким чином, вектор x = (x₁, ..., x_n), що задовольняє умовам індивідуальної і колективної раціональності, називається розподілом в умовах характеристичної функції .

Система {N, }, що складається з множини гравців, характеристичної функції над цією множиною і множини розподілів, що задовольняють співвідношенням (11.2) і (11.3) в умовах характеристичної функції, називається класичною кооперативною грою.

З цих визначень безпосередньо випливає така теорема.

Теорема 11.1. Для того щоб вектор x = (x₁, ..., x_n) був розподілом у класичній кооперативній грі {N, }, необхідно і достатньо, щоб

x_i = ( i ) + _i, (iN),

причому _i  0 (iN),

= (N) –. (11.4)

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

Кооперативні ігри вважаються істотними, якщо для будь-яких коаліцій K і L виконується нерівність

(K) + (L) < (KL),

тобто в умові суперадитивності виконується строга нерівність. Якщо ж в умові суперадитивності виконується рівність

(K) + (L) = (KL),

тобто виконується властивість адитивності, то такі ігри називаються несуттєвими.

Справедливі такі властивості :

- для того щоб характеристична функція була адитивною (кооперативна гра – несуттєвою), необхідно і достатня виконання наступної рівності:

= (N)

- у несуттєвій грі є тільки один розподіл

{(1) , (2) , ... , (n) };

- в істотній грі з більше ніж одним гравцем множина розподілів нескінчена

( (1) + ₁ , (2) + ₂ , ... , (n) +_n )

де

_i  0 ( i  N ) , (N) — 0

Кооперативна гра з множиною гравців N і характеристичною функцією  називається стратегічно еквівалентною грою з тією же множиною гравців і характеристичною функцією ¹ , якщо знайдуться такі к  0 і довільні дійсні C_i ( iN ), що для будь-якої коаліції К N має місце рівність:

¹(K) = k  (K) +. (11.5)

Сенс означення стратегічної еквівалентності кооперативних ігор полягає в тому що характеристичні функції стратегічної еквівалентності кооперативних ігор відрізняються тільки масштабом виміру виграшів k і початковим капіталом C_i . Стратегічна еквівалентність кооперативних ігор з характеристичними функціями  і ¹ позначається так ¹. Часто замість стратегічної еквівалентності кооперативних ігор говорять про стратегічну еквівалентність їх характеристичних функцій.

Справедливі такі властивості для стратегічних еквівалентних ігор:

1. Рефлексивність, тобто кожна характеристична функція еквівалентна собі .

2. Симетрія, тобто якщо ¹, то ¹.

3. Транзитивність, тобто якщо ¹ і ¹², то ².

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

Відношення стратегічної еквівалентності ігор і їх характеристичних функцій переноситься на окремі розподіли: нехай ¹ , тобто виконується (11.5), і x = (x₁, ..., x_n) – розподіли в умовах характеристичної функції . Розглянемо вектор x¹ = (, ...,) , де=k x_i+C_i . Для нього виконується

= k x_i + C_i  k ( i ) + С_i = ¹( i );

тобто виконується умова індивідуальної раціональності, і

==k+=k (N) +=¹(N)

тобто виконується умова колективної раціональності. Тому вектор є розподілом в умовах¹. Говорять, що розподіл x¹ відповідає розподілові x при стратегічній еквівалентності ¹.

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

Означення 11.1. Кооперативна гра з характеристичною функцією  має (0,1)-редуційну форму, якщо виконуються співвідношення:

( i ) = 0, ( i  N ), (N) = 1.

Теорема 11.2. Кожна істотна кооперативна гра стратегічно еквівалентна одній і тільки одній грі в (0,1)-редуційній формі.

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

У грі в (0,1)-редуційній формі розподілом є будь-який вектор x = (x₁, ..., x_n), для якого x_i  0, (i  N), = 1.