Коаліційні ігри
Коаліційні ігри моделюють ситуації, коли гравці мають кооперуватись для досягнення своєї мети.
Вважається, що гравці можуть формувати коаліції, які створюють непорушну угоду (яка гарантується зовнішніми чинниками) між гравцями та генерують певну величину прибутку.
Максимальна величина прибутку, яку генерує коаліція, називається її вартістю.
Головна проблема, яка виникає: яку коаліцію створять раціональні гравці і як вони мають
поділити її вартість між собою.
Розглядатимемо ігри, у яких вартість виражається в універсальних одиницях (доларах), які мають однакову цінність для всіх учасників, і вони можуть (при визначенні розподілу вартості) передавати її один одному.
Таки ігри називаються іграми з трансферабельною корисністю.
Розгляньмо спочатку кілька прикладів, як коаліційні ігри виникають у різних ситуаціях.
Ігри прибутку
У цих іграх коаліції створюються для отримання прибутку від кооперації.
Наступний приклад наведений у книзі (Game Theory by Michael Maschler, Eilon Solan, Shmuel Zamir ).
Уявімо трьох підприємців: Орві, Рона та Вілбура.
У Орві є ідеї щодо нових патентів і винаходів, і він оцінює прибуток від цих винаходів у $170,000 щорічно.
Рон — спеціаліст із бізнес-консалтингу і  хоче створити фірму, яка, за оцінками, дасть $150,000 щорічно.
Вілбур, супер сейлз і він планує увійти на новий ринок із доходом $180,000 щорічно.
Ці троє зустрічаються і розуміють, що їхні ідеї та плани націлені на одну область.
Працюючи разом, вони можуть створити додатковий прибуток.
Рон може консультувати Орві, які патенти наразі є найбільш затребуваними ринком, тому разом вони отримають $350,000.
Вілбур може продавати патенти та ідеї Орві, і разом вони генерують $380,000.
Рон і Вілбур разом можуть створити об’єднану фірму, яка принесе $360,000.
Якщо ж усі вони об’єднають свої зусилля, то оцінка прибутку дорівнює $560,000 щорічно.
Підприємці розуміють усі переваги сумісної роботи, але зовсім незрозуміло, як їм поділити прибутки.
Внесок кожного відрізняється, навіть внесок пари відрізняється.
Якщо вони не домовляться про принцип поділу, то досить швидко виникне ризик того, що вони просто пересваряться і розвалять потенційно успішний бізнес.
Така ситуація формалізується у вигляді коаліційної гри (з виграшами у доларах).
Далі задаються цінності коаліцій:
v(∅) = 0 — порожня коаліція має нульову цінність,
v(Вілбур) = 180,000,
v(Орві) = 170,000,
v(Рон) = 150,000,
v(Орві, Вілбур) = 380,000,
v(Рон, Вілбур) = 360,000,
v(Орві, Рон) = 350,000,
v(Орві, Вілбур, Рон) = 560,000.
Питання: яку коаліцію вони мають утворити та як розподілити прибутки для максимізації виграшів?
Дещо інший тип проблем, який однак призводить до аналогічної структури, виникає у іграх витрат.
На відміну від попередньої ситуації гравці об’єднуються в коаліції для того, щоб отримати певний цінний ресурс (послугу, товар).
Цінність коаліції — це сума, яку вони повинні заплатити за отримання ресурсу.
Наприклад, нехай Швеція, Норвегія і Фінляндія планують побудувати гідроелектростанцію, яка генеруватиме 3 гігавати електроенергії і для її побудови необхідна згода всіх трьох учасників.
Кожна з країн отримає третину від спільної генерації (1 гВт — це саме те, що їм зараз потрібно).
Вартість побудови $180 мільйонів.
Питання в тому, як поділити ці витрати.
Якщо країни повністю однакові, то логічно поділити витрати порівну.
Але припустимо, що умови, у яких ці країни перебувають, відрізняються.
Наприклад, може статись, що у Швеції є інша річка, що підходить для побудови меншої електростанції, яка генеруватиме 2 гігавата і її побудова коштує $100 мільйонів.
На переговорах Швеція може аргументувати наявність у неї кращої альтернативи (в цьому разі вона отримує 1 гВт за $50 мільйонів) порівняно з ситуацією рівного розподілу, коли вона отримує той самий гВт за $60 мільйонів.
Але Фінляндія і Норвегія також можуть побудувати меншу електростанцію, яка даватиме 2 гВт за $130 мільйонів.
Будь-яка країна, якане зможе вступити у коаліцію з іншими, має будувати 1 гВт електростанцію (звичайну) сама.
Вартість такої споруди буде
$80 мільйонів для Швеції, $90 мільйонів для Норвегії і $70 мільйонів для Фінляндії.
Знаючи все це, як повинні країни поділити вартість?
Тут c(S) описує вартість, яку коаліція має заплатити за надання електроенергії кожному членові коаліції.
c(∅) = 0,
c(Фінляндія) = 70,
c(Швеція) = 80,
c(Норвегія) = 90,
c(Швеція, Фінляндія) = 100,
c(Швеція, Норвегія) = 100,
c(Норвегія, Фінляндія) = 130,
c(Швеція, Норвегія, Фінляндія) = 180.
Коаліційні ігри і приклад обчислення вектора Шеплі
Коаліційні ігри є частиною кооперативних ігор — великого класу стратегічних ситуацій, які досліджуються у теорії ігор.
Розгляньмо конкретну і практичну ситуацію:
Троє гравців вирішують замовити таксі.
У цьому прикладі ми розглянемо випадок, коли їм потрібно потрапити у точки вздовж прямої лінії.
Отже, гравець А має заплатити за свою подорож 20 грн, Б — 80 грн і В — 120 грн.
Якщо А і Б утворять коаліцію, то їхні спільні витрати дорівнюватимуть 80, тому економія від такої коаліції дорівнює 20 грн.
Окремо вони  витратили б 100 грн, разом можуть доїхати за 80 грн.
Тобто 20 грн — це бонус, який виникає з їхньої співпраці і для того, щоб вони могли успішно створити коаліцію, потрібно визначити, яким чином розподілити ці гроші між собою.
Позначимо формулою v(АБ) = 20 — “ціну” цієї коаліції.
Відповідно, ціна інших коаліцій дорівнюють v(БВ) = 80, v(АВ) = 20, v(АБВ) = 100.
Коаліція всіх трьох учасників має найвищу додану вартість, тому розгляньмо, які тут можливі поділи.
Зазвичай люди, які не знають про теорію ігор, пропонують два варіанти: поділити порівну або пропорційно.
Очевидно, що якщо поділити 100 порівну між усіма трьома учасниками, то виявиться, що Б і В мають доплатити 13.33 першому гравцю.
Це нереалістично — навіщо Б і В така коаліція?
Рівний поділ дискримінує великих гравців.
Інший варіант — поділити пропорційно до кілометражу.
Тоді А отримає 100/11, Б — 400/11 В — 600/11.
Але в цьому разі уже відбувається дискримінація маленьких гравців — А отримує одну одинадцяту від спільного.
Наведені способи поділу “погані”, тому що не дають ані справедливого, ані навіть прийнятного поділу, і гравці можуть сперечатись до нескінченності.
Один із можливих розв’язків, який отримав назву вектор Шеплі, запропонував Лойд Шеплі.
За відкриття властивостей цього алгоритму поділу (крім іншого) він отримав Нобелівську премію з економіки.
Вектор Шеплі
Алгоритм простий, але гарантує єдиний (і часто справедливий) розподіл для задач такого типу: потрібно утворити різні комбінації гравців (порядок має значення) та уявити, що вони послідовно додають суму, потрібну для подорожі до своєї точки.
Наприклад, перший рядок розшифровується так:
А платить 20, потім Б додає 60, щоб отримати свою вартість, потім В додає до результату 40, щоб отримати свою вартість.
АБВ: 20 60 40
АВБ: 20 0 100
БАВ: 0 80 40
БВА: 0 80 40
ВАБ: 0 0 120
ВБА: 0 0 120
–----------------------------
6.66 36.66 76.66
Результат:
А має заплатити 6.66, Б  — 36.66 і С — 76.66.
