Кооперативні ігри

Кооперативные игры

Кооперативные гри виходять у його випадках, коли, у грі 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 називається простий, якщо вона бере лише 2 значення: 0 і одну. Якщо характеристична функція 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) .

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

Распределение виграшів (делёж) гравців має задовольняти наступним природним умовам: якщо позначити через xi виграш i-го гравця, то, по-перше, має задовольнятися умова індивідуальної рациональности.

xi ³ u (і), для і ÎN .

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

= u (N) .

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

Таким чином, вектор x = (x1, …, xn), задовольняє умовам індивідуальної приватизації та колективної раціональності, називається дележём за умов характеристичною функції u.

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

Из цих визначень безпосередньо випливає следующая Теорема. Щоб вектор x = (x1, …, xn) був дележём у «класичній кооперативної грі {N, u},.

необходимо і, чтобы.

xi = u (і) + ai, (iÎN).

причём.

ai ³ 0 (iÎN).

= u (N) — .

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

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

u (K) + u (L) < u (KÈL),.

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

u (K) + u (L) = u (KÈL),.

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

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

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

= u (N).

2) в несуттєвою грі є лише один делёж.

{u (1), u (2), …, u (n) };

3) у значній грі з більш як одним гравцем безліч поділів бесконечно.

(u (1) + a1, u (2) + a2, …, u (n) +an).

где.

ai ³ 0 (і Î N), u (N) —> 0.

Кооперативная гра з безліччю гравців N і характеристичної функцією u називається стратегічно еквівалентній грою з тим самим безліччю гравців і характеристичною функцією u1, якщо знайдуться до > 0 і довільні речові Ci (iÎN), що з будь-який коаліції До Ì N має місце равенство:

u1(K) = k u (K) + .

Смысл визначення стратегічної еквівалентності кооперативних ігор (с.э.к.и.) у тому що характеристичні функції с.э.к.и. відрізняються лише масштабом виміру виграшів k і початковим капіталом Ci. Стратегічна еквівалентність кооперативних ігор з характеристичними функціями u і u1 позначається так u~u1. Часто замість стратегічної еквівалентності кооперативних ігор говорять про стратегічної еквівалентності їх характеристичних функцій .

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

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

2. Симетрія, тобто. якщо u~u1, то u1~u.

3. Транзитивность, тобто. якщо u~u1 і u1~u2, то u~u2.

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

Отношение стратегічної еквівалентності ігор й їх характеристичних функцій переноситься деякі дележи :

пусть u~u1, тобто. виконується (5), і x = (x1, …, xn) — дележи за умов характеристической функції u; розглянемо вектор x1 = (, …, ), де = k xi+Ci; йому виконується.

= k xi + Ci ³ k u (і) + Сi = u1(і);

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

== k+= k u (N) += u1(N).

т.е. виконується умова колективної раціональності. Тому вектор є поділом в умовах u1. Кажуть, що делёж x1 відповідає поділу x при стратегічної еквівалентності u~u1.

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

Всякая несуттєва гра стратегічно еквівалентна нульової .

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

u (і) = 0 (і Î N),.

u (N) = 1.

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

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

В гру (0,1)-редуцированной формі дележём є будь-який вектор x = (x1, …, xn), для которого.

xi ³ 0 (і Î N) = 1.

Перечисление характеристичних функцій малим числом игроков.

Как було зазначено раніше, кожному за безлічі гравців N існує єдиний клас стратегічно еквівалентних несуттєвих ігор з безліччю гравців N. Отже, залишається розглянути класи істотних кооперативних игр.

Рассмотрим спочатку класи ігор (0,1)-редуцированной формі для випадку ігор з травня нульової суммой.

1. Ігри 2-х гравців. Будь-яка кооперативна гра двох гравців з травня нульової сумою є несущественной.

Доказательство. Припустимо, що є істотна кооперативна гра двох гравців з характеристичної функцією u, Тоді вона мусить бути стратегічно еквівалентна деякою гру (0,1)-редуцированной формі з характеристичної функцією u1, що означає таке :

u1(1) = 0, u1(2) = 0, u1(1,2) = 1 .

По властивості додатковості должно.

u1(2) = u1(1,2) — u1(1) = 1 — 0 =1,.

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

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

2. Ігри 3-х гравців. Нехай u — характеристична функція істотною гри акторів-професіоналів у (0,1)-редуцированной формі, тогда.

u (1) = u (2) = u (3) = 0, u (1,2,3) = 1.

По властивості додатковості маємо :

u (1,2) = u (1,2,3) — u (3) = 1- 0 =1,.

u (1,3) = u (1,2,3) — u (2) = 1- 0 =1,.

u (2,3) = u (1,2,3) — u (1) = 1- 0 =1,.

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

3. Ігри 4-х гравців. Розглянемо все класи стратегічної еквівалентності таких игр.

Прежде всього є клас несуттєвих ігор (0,1)-редуцированной формі визначимо характеристическую функцію u такий гри.

u (1) = u (2) = u (3) = u (4) = 0.

u (1,2,3,4) = 1.

Исходя з властивості додатковості, отримуємо.

u (1,2,3) = u (1,2,3,4) — u (4) = 1- 0 =1;

u (1,2,4) = u (1,2,3,4) — u (3) = 1- 0 =1;

u (1,3,4) = u (1,2,3,4) — u (2) = 1- 0 =1;

u (2,3,4) = u (1,2,3,4) — u (1) = 1- 0 =1.

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

(1,2), (1,3), (1,4), (2,3), (2,4), (3,4).

Характеристическая функція цих коаліції відповідно до властивості додатковості задовольняє лише наступним співвідношенням :

u (1,4) = 1- u (2,3),.

u (1,3) = 1- u (2,4),.

u (1,2) = 1- u (3,4).

Так як значень невідомих шість, а співвідношень лише три, то значення з 6 може бути обрано довільно. Розкажемо про ці довільні значення через x1, x2, x3, т. е.

u (1,4) = x1, u (2,4) = x2, u (3,4) = x3 ,.

Тогда.

u (2,3) = 1- x1, u (1,3) = 1- x2, u (1,2) = 1- x3 .

Кроме того має бути.

0 £ x1, x2, x3 £ 1 ,.

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

Итак, безліч класів стратегічної еквівалентності істотних ігор чотирьох гравців нескінченно і від трьох довільних параметров.

4. Ігри, які з більш як 4-х гравців, мають більшу різноманітність класів стратегічної еквівалентності істотних игр.

Так, розмірність безлічі класів ігор n гравців дорівнює , тобто. є довільних параметров.

Рассмотрим тепер кооперативні гри без умови сталості суммы.

1. Для ігор 2-х гравців безліч N={1,2}, умови редуцированности дают.

u (Æ) = u (1) = u (2) = u (1,2) = 1.

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

2. Для ігор 3-х гравців безліч N={1,2,3}, умови редуцированности дают.

u (Æ) = u (1) = u (2) = u (3) = 0; u (1,2,3) = 1.

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

u (1,2) = C3, u (1,3) = C2, u (2,3) = C1,.

но задовольняють условию.

0 £ C1, C2, C3 £ 1.

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

Для ігор більш 3-х гравців з ненульовий сумою розгляду аналогичны.

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

Определение. Нехай є два поділу x = (x1, …, xn) і y = (y1, …, yn) в кооперативної грі G = {N, u}, і KÌ N — деяка коаліція. Тоді делёж x домінує y за коаліцією K, если.

1) £ u (K) (властивість ефективності домінуючого платежа).

2) xi > yi всім iÎK (властивість предпочтительности) Свойство ефективності означає, що порівнюваний коаліцією делёж x може бути, реализуемым цієї коаліцією: сума виграшів кожного з п’яти членів коаліції має перевершувати впевнено одержуване нею кількість. У іншому разі коаліція, ознайомившись із дележём, що дає їй стільки, скільки вона самостійно неспроможна домогтися, повинна погодитися нею і його порівнянням з якими або іншими дележами.

Условие перевагу відбиває необхідність «одностайності» в перевагу із боку коаліції: якщо хоча одне з нерівностей xi > yi порушено, тобто. якщо хоча для постраждалого учасника коаліції K виграш за умов поділу y буде меншою, ніж у умовах поділу x, можна говоритиме про перевагу поділу x поділу y не всієї коаліцією K, лише тими її членами, котрим відповідне нерівність xi > yi соблюдается.

Соотношение домінування x над y за коаліцією K позначається через.

.

Определение. Делёж x домінує y, якщо є така коаліція K, на яку делёж x домінує y. Це домінування позначається так:

x > y.

Наличие домінування x > y означає, що у безлічі гравців N знайдеться коаліція, на яку x краще y. Ставлення домінування не має повністю властивостями рефлексивности, симетрії, транзитивності, можливе тільки часткова симетрія і транзитивность. Співвідношення домінування можливо за будь-якої коаліції. Так, неможливо домінування за коаліцією, що з одного гравця, або із усіх игроков.

Справедлива наступна теорема.

Теорема. Якщо u і u1 — дві стратегічно еквівалентні характеристичні функції, причому дележам x і y відповідають дележи і , те з x > y слід >.

Очевидно, все явища, описувані в термінах домінування поділів, ставляться до класам стратегічної еквівалентності, тому досить вивчати ці класи (а чи не самі гри) для істотних ігор з їхньої (0,1)-редуцированной формі, а несуттєвих ігор — по нульовим играм.

В будь-який несуттєвою грі є лише один делёж, тому ніяких доминирований у ній нет.

Рассмотрим домінування поділів в істотною грі ось на чому примере.

Пример. Нехай є (0,1)-редуцированная форма істотною гри трьох гравців із постійною сумою (рівної 1). Оскільки домінування неможливо за однією з одноэлементных коаліцій 1,2,3, і навіть за коаліцією, що з всіх трьох гравців, то домінування можна тільки за однією з двухэлементных коаліцій {1,2}, {1,3}, {2,3}.

Для наочності домінування поділів введём поняття бароцентрических координат. Осями координат служать три осі x1, x2, x3, складові між собою однакові кути 60 градусів, вісь x3 перебуває в відстані одиниці від точки перетину осей x1 і x2 (мал.1), координати точки x = (x1, x2, x3) — відповідно відстані від цього точки до осей x1, x2, x3, взяті зі такими знаками, як на мал.1. (Наприклад, для точки x на мал.1. x1 < 0, x2 > 0, x3 > 0).

.

В барицентрической системі координат завжди виконується равенство.

x1 + x2 + x3 = 1. .

В площині завжди є точка з координатами x1, x2, x3, задовольняючими рівності (6). У цій бароцентрическая система координат автоматично задовольняє одного з умов, визначальних результат гри трьох гравців. З іншого боку, оскільки гра в (0, 1)-редуцированной формі, то точка x повинна перебувати у заштрихованном трикутнику (див. рис. 2). Дележи x1, x2, x3 повинні задовольняти неравенствам.

x1 + x2 £ u (1, 2), x1 + x3 £ u (1, 3), x2 + x3 £ u (2, 3).

Очевидно, з умови додатковості, что.

x1 + x2 = 1 — x3 £ 1 = u (1, 2), x1 + x3 £ 1, x2 + x3 £ 1.

Делёж x = (x1, x2, x3) домінує розподіл y = (y1, y2, y3).

по коаліції {1, 2}, якщо x1 > y1, x2 > y2;

по коаліції {1, 3}, якщо x1 > y1, x3 > y3;

по коаліції {2, 3}, якщо x2 > y2, x3 > y3,.

т.е. якщо делёж y перебуває у одному з заштрихованных паралелограмів (крім трьох граничних прямих, що пропливали точку x) на рис. 3, то делёж x домінує делёж y, а всяка точка яка перебуває у не заштрихованных трикутниках, є краще результату x.

x3 = - 1×2 = - 1.

x = (x1, x2, x3).

x3 = 1 — C3.

x1 = 0.

x1 = 1 — C1 x2 = 1 — C2.

Рис. 3 Рис. 4.

Таким чином, якщо x і y — два результату і жоден їх не краще іншого, це були відповідні точки лежать на прямий, паралельної одній з координатних осей.

Пример. Нехай є (0, 1)-редуцированная гра трьох гравців з ненульовий суммой.

Рассмотрим спочатку умови домінування поділу x = (x1, x2, x3) над дележём y = (y1, y2, y3) за коаліцією {1, 2}. І тут маємо :

.

Поскольку то, можливо, що C3 < 1, то перше з умов (7) не можна відкинути, як і робиться в іграх із постійною сумою. Це означає що, x мусить бути не нижче прямой.

x1 + x2 = C3.

Или, враховуючи (6), останнє рівняння приймає вид.

x3 = 1 + C3 .

Таким чином, якщо делёж x такий, что.

x1 ³ 1 — C1, x2 ³ 1 — C2, x3 ³ 1 — C3, .

то є три паралелограма, заштрихованных на рис. 4, перебувають у яких, точки x домінують y.

Если в (8) одна з нерівностей, наприклад, третє немає місця, тобто лише 2 параллелограмма, заштрихованных на рис. 5, перебувають у деяких точках x домінує y.

x1 = 1 — C1 x2 = 1 — C2 x2 = 1 — C2 x1 = 1 — C1.

x3 = 1 — C3.

x.

Рис. 5 Рис. 6.

Из розглянутої прикладу видно, що можливо багато варіантів, які виникають щодо питань, що з домінуванням поділів в кооперативних іграх. Зі збільшенням кількості гравців надзвичайно швидко росте кількість таких варіантів. У зв’язку з цим виникає необхідність виділення цілком стійких поділів, тобто. таких поділів, які не доминируются ніякими іншими дележами. Безліч цілком стійких поділів в кооперативної грі називається с-ядром цієї игры.

Теорема. Щоб делёж x належав с-ядру кооперативної ігри робилися із характеристичної функцією u, необхідне й досить, щоб для будь-який коаліції K виконувалося неравенство.

.

Поскольку нерівності (9) линейны щодо x, те з останньої теореми слід, що с-ядро у будь-якій кооперативної грі є опуклим многогранником.

К особливостям кооперативних ігор щодо існування с-ядра ставляться :

1) в несуттєвою грі с-ядро існує і складається з єдиного поділу цієї игры;

2) у будь-якій істотною грі з постійної сумою с-ядро пусто.

Для загальної гри трьох гравців в (0; 1)-редуцированной формі маємо таке (рис. 7).

Её характеристична функція має вигляд :

u (Æ) = u (1) = u (2) = u (3) = 0;

u (1, 2, 3) = 1,.

u (1, 2) = С3; u (1, 3) = С2; u (2, 3) = С1,.

где 0 £ С1, С2, С3 £ 1.

На підставі останньої теореми для приналежності поділу x с-ядру необхідне й досить виконання неравенств.

x1 + x2 ³ C3, x1 + x3 ³ C2, x2 + x3 ³ C1.

или, використовуючи рівність x1 + x2 + x3 = 1, получим.

x3 £ 1 — C3, x2 £ 1 — C2, x3 £ 1 — C1. .

1 2.

.

Рис. 7.

Это означає, що вищу точку x має лежати ближчі один до i-го вершині основного трикутника (див. рис. 7), ніж пряма.

xi = 1 — Сi (і = 1,2,3) .

Из нерівності (10) шляхом підсумовування получим.

x1 + x2 + x3 £ 3 — (С1 + С2 + С3).

или, враховуючи, що x1 + x2 + x3 = 1, получим.

С1 + С2 + С3 £ 2. .

Неравенство (12) є необхідною умовою існування непорожнього с-ядра. З іншого боку, якщо (12) виконується, можна взяти такі неотрицательные e1, e2, e3, чтобы.

,.

и положить.

xi = 1 — Ci — ei (і = ).

Такие значення xi і задовольняють неравенствам (10), тобто. такий делёж x = (x1, x2, x3) принадлежить с-ядру.

Геометрически непорожнє с-ядро є заштрихованным трикутником (рис. 7), зі сторонами, вираженими рівняннями (11).

3 3.

.

1 2 1 2.

.

Рис. 8 Рис. 9.

при умови, що виконується соотношение.

x1 + x2 + x3 = 1,.

и рішення суду будь-якої пари рівнянь (11) є неотрицательными. Приміром, рассмотрим систему.

x1 = 1 — С1, x2 = 1 — С2.

Поскольку 0 £ С1 £ 1, 0 £ С2 £ 1, то x1, x2 ³ 0. Звідси получаем.

x3 = 1 — x1 — x2 = 1 — (1 — С1) — (1 — С2) = С1 + С2 — 1.

Для здобуття права було x3 ³ 0, необхідно чтобы С1 + С2 — 1 ³ 0.

или С1 + С2 ³ 1.

В цьому випадку с-ядро представлене див. мал.7 як заштрихованого трикутника всередині основного трикутника. Аналогічно розглядаються інші можливі варіанти сочетаний нерівностей. Наприклад, якщо С1 + С2 < 1, то с-ядро має вигляд заштрихованого чотирьохкосинця всередині основного трикутника (див. мал.8). Взагалі багатогранник, що становить с-ядро, утвориться як мінімум опуклий багатогранник перетином прямих (11) і рядків основного трикутника. Якщо, наприклад, виконуються неравенства С1 + С2 < 1; С2 + С3 < 1; С1 + С3 < 1,.

то с-ядро представляється як шестигранника, заштрихованого на рис. 9.

Очевидно, у виконання кооперативної гри має входити дележи, кращі з визначеноіншої погляду. Так, дележи, що входять до с-ядро, є стійкими на кілька пасивном сенсі, тобто. за обставин немає підстав відхилятися від такої поділу. Однадо, знайти делёж, який би не доминировался б певними іншими дележами, але сам домінував усякий інший делёж, не вдається. Тому вирішення відшукують по дорозі розширення класу поділів. І це розширення у тому, що рішенням гри може бути чимало делёж, а певну їх множество.

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

Определение. Рішенням по Нейману-Моргенштерну (Н-М-решением) кооперативної гри називається безліч R поділів у ньому, що має такими властивостями :

1) внутрішня стійкість: ніякі два поділу з R не домінують друг друга;

2) зовнішня стійкість: який був делёж P. S не приналежний R, знайдеться делёж r, приналежний R, який домінував б S.

Содержательная інтерпретація Н-М-решения у тому, будь-які дві норми поведения, відповідні Н-М-решению, не може бути протипоставлено одна одній; яке було відхилення від допустимих поводжень, знайдеться така коаліція, яка йти до відновленню нормы.

Теорема. Якщо кооперативної грі існує с-ядро З і Н-М-решение R, то CÌ R.

Свойства Н-М-решений.

Н-М-решение кооперативної гри неспроможна перебувати тільки з поділу, т.к. у разі характеристичне функція гри несущественная.

Недостатки Н-М-решения.

1. Відомі приклади кооперативних ігор, які мають Н-М-решений. Понад те, нині невідомо будь-яких критеріїв, дозволяють будувати висновки про у кооперативних ігор Н-М-решений. Тим самим було закладений Н-М-решении принцип оптимальності не є універсально реализуемым, і науковотехнологічна галузь його можливості бути реалізованим поки що залишається неопределённой.

2. Кооперативні гри, а то й мають Н-М-решения, те, як правило, більше. Тому принцип оптимальності, що призводить до Н-М-решению, перестав бути повним: він, власне кажучи, неспроможна вказати гравцям єдиною системи норм розподілу выигрыша.

3. Рішення істотних кооперативних ігор перебуває понад, ніж із одного поділу. Отже, навіть вибір будь-якого конкретного Н-М-решения не визначає виграшу кожного з игроков.

4. Поняття Н-М-решения відбиває лише у дуже малій мірі риси справедливости.

Перечисленные недоліки відбивають стан справ у дійсності: більшість економічних та соціальних проблем допускає множинні рішення, і рішення який завжди піддаються безпосередньому порівнянню з їхньої предпочтительности.

Перечисленные недоліки Н-М-решения коаліційних ігор сприяють пошукам нових підходів. Однією з таких підходів є підхід Шепли, суті якого у цьому, що він будуватися виходячи з аксіом, що відбивають справедливість дележей.

Определение. Носієм ігри робилися із характеристичної функцією u називається така коали-ция T, что.

u (S) = u (S Ç T).

для будь-який коаліції S.

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

Визначення. Нехай u — характеристичний функція кооперативної гри n гравців, p — будь-яка перестановка безлічі N гравців. Через pu позначимо характеристическую функцію і тадідька лисого гри, що з коаліції P. S = {i1, i2, …, iS} будет.

u ({p (i1), p (i2), …, p (iS)}) = u (S).

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

Аксиомы Шепли.

1о. Аксіома ефективності. Якщо P. S — будь-який носій ігри робилися із характеристичною функцією u, то.

= u (S).

Иными словами, «справедливість вимагає», що з поділі загального виграшу носія гри щось виділяти частку сторонніх, котрі належать до цьому носію, як і щось стягувати з них.

2о. Аксіома симетрії. Для будь-який перестановки p і iÎN має выполняться.

(pu) = ji (u),.

т.е. гравці, однаково що входять до гру, повинні «по справедливості» отримувати однакові выигрыши.

3о. Аксіома агрегації. Якщо є дві ігри робилися із характеристичними функціями u¢ і u¢¢, то.

j і (u¢ + u¢¢) = j і (u¢) + j і (u¢¢),.

т.е. заради «справедливості» треба вважати, що з участі гравців у двох іграх їх виграші в окремих іграх повинні складываться.

Определение. Вектором цін (вектором Шепли) ігри робилися із характеристичної функцією u називається n-мерный вектор

j (u) = (j1(u), j2(u), …, jn (u)),.

удовлетворяющий аксіомам Шепли.

Существование вектора Шепли випливає з наступній теоремы Теорема. Існує єдина функція j, певна всім ігор й яка задовольнить аксіомам Шепли.

Определение. Характеристична функція wS (T), певна для будь-який коаліції P. S, називається найпростішої, если.

wS (T) = .

Содержательно найпростіша характеристична функція описує таке стан справ, у якому безліч гравців P. S виграє одиницю тоді й тільки тоді, як його містить деяку основну мінімальну выигрывающую коаліцію S.

Можно довести, що компоненти вектора Шепли вочевидь запишуться наступним образом.

.

где t — число елементів в T.

Вектор Шепли змістовно можна інтерпретувати так: гранична величина, яку вносить i-го гравець у коаліцію T, виражається как.

u (T) — u (T {i}).

и вважається виграшем i-го гравця; gi (T) — це можливість, що i-го гравець вступить у коаліцію T {і}; ji (u) — середній виграш i-го гравці таку схему інтерпретації. У тому випадку, коли u — простейшая,.

.

Следовательно.

,.

где підсумовування по T поширюється попри всі такі які виграють коаліції T, що коаліція T {i}не є выигрывающей.

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

a1 = 10, a2 = 20, a3 = 30, a4 = 40.

Любое рішення стверджується акціонерами, мають у сумі більшість акцій. Таке рішення вважається виграшем, рівним 1. Тому викладена ситуація може розглядатися як проста гра чотирьох гравців, у якій выигрывающими коаліціями є следующие:

{2; 4}, {3; 4},.

{1; 2; 3}, {1; 2; 4}, {2; 3; 4}, {1; 3; 4},.

{1; 2; 3; 4}.

Найдём вектор Шепли з цією игры.

При перебування j1 необхідно враховувати, що є лише одна коаліція T={1;2;3}, котра виграє, а коаліція T {1} = {2; 3} не виграє. У коаліції T є t = 3 гравця, поэтому.

.

Далее, визначаємо все які виграють коаліції, але з які виграють без 2-го гравця: {2; 4}, {1; 2; 3}, {2; 3; 4}. Поэтому.

.

Аналогично отримуємо, що , .

В результаті отримуємо, що вектор Шепли дорівнює . У цьому, якщо вважати, вага голоси акціонера пропорційний кількості наявних проблем нього акцій, одержимо наступний вектор голосования.

,.

который, очевидно, відрізняється від вектора Шепли.

Анализ гри показує, що компоненти 2-го і 3-го гравців рівні, хоча третій гравець має більше акцій. Це виходить через те, можливості освіти коаліцій у 2-го і 3-го гравця однакові. Для 1-го і 4-го гравця ситуація природна, відповідальна силі їх капитала.