Головна |
« Попередня | Наступна » | |
Доповнення. Існування і єдиність вектора Шеплі |
||
Ми доведемо тут без особливих подробиць існування і єдиність значення Шеплі (більш докладно див, наприклад, Воробйов, 1995). Знайдемо спочатку вектор Шеплі для характеристичної функції виду CVR, де з > 0, a VR - найпростіша характеристична функція, тобто функція виду VR (S) = | 1, якщо SDR, О, в іншому випадку Легко бачити, що число різних найпростіших характеристичних функцій на I одно 2п - 1, тобто числу непорожніх коаліцій. Наступні дві пропозиції ми наведемо без доказів. Пропозиція 6.5.1. Всі 2п - 1 найпростіших характеристичних функцій на I лінійно незалежні. Пропозиція 6.5.2. Для будь характеристичної функції v має місце єдине подання Rcl ScR де Іншими словами , це пропозиція стверджує, що кожну характеристическую функцію на J можна уявити, і притому єдиним чином, у вигляді лінійної комбінації найпростіших характеристичних функцій. Теорема 6.5.1. Якщо vr - найпростіша характеристична функція, то {шт якщо г? R,, = {W. '5.1 (0, якщо г f R. Доказ. Безліч R є для cvr носієм. Тому по аксіомі ефективності: ^ Ф, - (сг; д) = сг; д (Д) = с. (5.2) ieR Ясно також, що перестановка будь-яких двох гравців з R не змінює значення характеристичної функції CVR | Тому по аксіомі симетрії зліва в (5.2) всі складові рівні ОДИН ОДНОМУ) і ми отримуємо верхній рядок (5.1). Нарешті, всі гравці, що не входять в R, є в CVR бовдурами, і це дає нам нижній рядок (5.1). Слідство 6.5.1. Для найпростішої характеристичної функції vr і з > 0 Ф (сид) = СФ (ід). Доказ випливає безпосередньо з (5.1). З аксіоми лінійності і останнього слідства випливає, що за будь-яких сд ^ 0 повинно бути Ф (^ СДГ; д) = ^ Ф (СДГ; д) = СДФ (ід). (5.3) Поширимо цю формулу на випадок коефіцієнтів сд з довільними знаками. Лемма 6.5.1. Якщо v 'і v "- характеристичні функції, а їх різниця v' - v" також є характеристичною функцією, то $ (v'-v ") = Ф (г /)-Ф (і "). (5.4) Доказ. За умовою ми маємо тотожне v '= v "+ (г / - v"). Праворуч тут стоїть сума двох характеристичних функцій, і по аксіомі лінійності ми маємо ф (і ') = Ф (і ") + Ф (і'-і"), звідки і слід (5.4). Слідство 6.5.2. Формула (5.3) залишається справедливою, якщо знаки коефіцієнтів cr довільні, а сума ^ 2rCrvr є характеристичною функцією. Доказ. Маємо v = cRvR = ^ 2 CRVR ~ X] (~ CR) VR- RRR CR> ° СД < ° Тут у другій сумі всі числа - cr є позитивними, так що віднімається сума виявляється характеристичної функцією. Тому по лемі 6.5.1 Ф (і) = Ф (^ 2 CRVR) ~ ф ((~ cR) vR) = RR cR> 0 cR <0 = Y CR ® (VR) - ("ся) фи = ^ СДФ (г ;). RRR cR> 0 cR <0 Теорема 6.5.2. Кожна характеристична функція має не більше одного вектора Шеплі. Доказ . Те, що кожна найпростіша характеристична функція має не більше одного вектора Шеплі, випливає з теореми 6.5.1. Але в силу пропозиції 6.5.2 довільна характеристична функція подана в вигляді лінійної комбінації найпростіших єдиним способом. Тому із доведеного вище випливає, що кожна характеристична функція має не більше одного вектора Шеплі. Нам залишається довести існування вектора Шеплі для будь характеристичної функції. Теорема 6.5.3. Для будь характеристичної функції v на I = {1, ..., га} компоненти вектора Шеплі визначаються формулою ieR'ci Доказ. Перевіримо спочатку, що вектор Ф (і) з компонентами з (5.5) задовольняє всім аксіомам Шеплі. Доведемо ефективність вектора Ф (і). Для цього розглянемо iei iei ieR'ci У всій подвійний сумі вираз v (K) зустрічається в ролі зменшуваного \ К \ раз (по числу входять до До елементів) і тим самим набуває коефіцієнт . Ап-\ К \) 1 (\ К \ - 1)! (п- \ К \) - \ К \ \ \ к \ j = j> га! га! який при \ К \ = га, тобто при К = I, очевидно, дорівнює одиниці. В ролі ж від'ємника воно зустрінеться га - \ К \ раз (по числу не входять в До елементів) і тим самим набуває коефіцієнт , ST-YM-1 ^ 1 - (га - \ К \) 1 \ К \ 1 - (п-\ К) -!-Ц --- L = - Ц1 ^-L, якщо пф \ к \, га! га! і коефіцієнт 0, якщо п = \ К \. Таким чином, права частина (5.6) дорівнює v (I): J2Mv) = V (I) 1 (5.7) iei і вектор Ф (і) виявляється ефективним. Перевірка аксіоми бовдура тривіальна. Нехай у грі v гравець i є бовдуром. Тоді для будь-якої коаліції К С I v (K) - v (K \ i) = О, а отже, кожний доданок в (5.5) для цього i дорівнює 0. Тому = 0. Перевіримо тепер аксіому симетричності. Нехай тг - перестановка I така, що V (TTK) = v (K) для будь-якої коаліції К. Тоді разом з К коаліція тг К також пробігає всі підмножини I, і ми можемо (5.5) переписати як ж ^ V-(п ~ КК |)! (| ТГК | - 1)! ... ФТГ .-І = ^ Т - (v (ttR) - V (TTK \ 7ГГ)). З іншого боку, оскільки v (irK) = v (K) і \ ТГК \ = \ К \, то 7гг і 7ГК під знаком підсумовування можна назад перейменувати відповідно в г і К. Остаточно ми маємо Фт-(") =? i * - \ mm-i) iiviK) _ v {KV)) = ф. (і) _ Kcl Аксіома лінійності випливає з того, що компоненти вектора Ф (і) залежать від значень характеристичної функції v лінійно . Таким чином, вектор Ф (і) дійсно є для характеристичної функції v вектором Шеплі, існування якого тим самим доведено. |
||
« Попередня | Наступна » | |
|
||
|
||
Інформація, релевантна" Доповнення. Існування і єдиність вектора Шеплі " |
||
|