Кооперативні ігри
Кооперативні ігри виходять в тих випадках, коли, в грі n гравців дозволяється утворювати певні коаліції. Позначимо через N безліч всіх гравців, N = {1,2, ..., n}, а через K - будь-яке його підмножина. Нехай гравці з K домовляються між собою про спільні діях і, таким чином, утворюють одну коаліцію. Очевидно, що число таких коаліцій, що складаються з r гравців, дорівнює числу сполучень з n по r, тобто, а число всіляких коаліцій одно
= 2n - 1.
З цієї формули видно, що число всіляких коаліцій значно зростає в залежності від числа всіх гравців у даній грі. Для дослідження цих ігор необхідно враховувати всі можливі коаліції, і тому труднощі досліджень зростають із зростанням n. Утворивши коаліцію, безліч гравців K діє як один гравець проти решти гравців, і виграш цієї коаліції залежить від застосовуваних стратегій кожним з n гравців.
Функція u, що ставить у відповідність кожній коаліції K найбільший, впевнено одержуваний його виграш u (K), називається характеристичною функцією гри. Так, наприклад, для безкоаліційній ігри n гравців u (K) може вийти, коли гравці з безлічі K оптимально діють як один гравець проти решти NK гравців, що утворюють іншу коаліцію (другий гравець).
Характеристична функція u називається простий, якщо вона приймає тільки два значення: 0 і 1. Якщо характеристична функція u проста, то коаліції K, для яких u (K) = 1, називаються виграють, а коаліції K, для яких u (K) = 0, - програють.
Якщо в простій характеристичної функції u виграють є ті і тільки ті коаліції, які містять фіксовану непорожню коаліцію R, то характеристична функція u, що позначається в цьому випадку через uR, називається найпростішої.
Змістовно прості характеристичні функції виникають, наприклад, в умовах голосування, коли коаліція є виграє, якщо вона збирає більше половини голосів (проста більшість) або не менше двох третин голосів (кваліфікована більшість).
Більш складним є приклад оцінки результатів голосування в Раді безпеки ООН, де виграють коаліціями є всі коаліції, що складаються з усіх п'яти постійних членів Ради плюс ще хоча б один непостійний член, і тільки вони.
Найпростіша характеристична функція з'являється, коли в голосі колективі є деяка "ядро", голосуюча з дотриманням правила "вето", а голоси інших учасників виявляються несуттєвими.
Позначимо через uG характеристичну функцію безкоаліційній гри. Ця функція має такі властивості:
персональность
uG (Г†) = 0,
тобто коаліція, яка не містить жодного гравця, нічого не виграє;
супераддітівность
uG (KГ€L) Ві uG (K) + uG (L), якщо K, L ГЊ N, KГ‡L В№ Г†,
тобто загальний виграш коаліції не менше сумарного виграшу всіх учасників коаліції;
додатковість
uG (K) + u (NK) = u (N)
тобто для безкоаліційній ігри з постійною сумою сума виграшів коаліції і решти гравців повинна дорівнювати загальній сумі виграшів ус...