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