Коаліційні ігри
Коаліційні ігри моделюють ситуації , коли гравці мають кооперуватись для досягнення своєї мети .
Вважається , що гравці можуть формувати коаліції , які створюють непорушну угоду ( яка гарантується зовнішніми чинниками ) між гравцями та генерують певну величину прибутку .
Максимальна величина прибутку , яку генерує коаліція , називається її вартістю .
Головна проблема , яка виникає : яку коаліцію створять раціональні гравці і як вони мають
поділити її вартість між собою .
Розглядатимемо ігри , у яких вартість виражається в універсальних одиницях ( доларах ) , які мають однакову цінність для всіх учасників , і вони можуть ( при визначенні розподілу вартості ) передавати її один одному .
Таки ігри називаються іграми з трансферабельною корисністю .
Розгляньмо спочатку кілька прикладів , як коаліційні ігри виникають у різних ситуаціях .
Ігри прибутку
У цих іграх коаліції створюються для отримання прибутку від кооперації .
Наступний приклад наведений у книзі ( 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 .
