назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [ 85 ] [86] [87] [88] [89] [90]


85

Аксиома эффективности. Пусть в условиях v игрок / является болваном. Тогда при любой коалиции К С/

v(K)-v(KM) = v(i),(21.9)

и точно так же, как от неравенства (21.5) мы переходили к неравенству (21.6), мы можем от равенства (21.9) перейти к равенству

Фiiv) = v(i).(21.10)

Возьмем теперь произвольного носителя Аигры v. Так как все игроки вне N - болваны, мы можем просуммировать равенство (21.10) по / G

EI\N:

X Ф,(1;)= X v(i). I е i\Ni е i\N

Почленное вычисление этого равенства из (21.8) приводит к

X Фi{v) = v{I)- X v(il

и ссылка на формулу (6.10) дает нам требуемое.

Аксиома симметрии. Пусть тг - автоморфизм v. Тогда вместе с К коалиция ттК пробегает все подмножества /, и мы можем (21.5) переписать как

(/2- 7Г/)1 !(7Г/:1- 1)!

.iiv)= X--- (v(nK)-v(7riK\i))).

с другой стороны, из автоморфности тг следует, что v (тгК) = v (К), и \7гК \ = \К \ , г iri и пК под знаком суммирования можно обратно переименовать соответственно в / я К. Окончательно мы имеем

(/2-А)!(1А"1-1)!

.i(v)= 2 -~-- (v(K)-viK\l)) = Фt(v).

KCIп\

Аксиома агрегации соблюдается в силу того, что компоненты вектора Ф(1;) зависят от значений характеристической функции i; линейно.

Таким образом, вектор Ф(1;) действительно является для характеристической функции V вектором Шепли, существование которого тем самым доказано. □

21.7.Вектор Шепли как дележ обладает естественным свойством инвариантности.

Теорема. Если я - изоморфизм характеристической функции v на характеристическую функцию v, то Фг/ (v ) = Ф/ (v).

Доказательство отличается лишь несущественными деталями от проверки аксиомы симметрии в доказательстве теоремы предьщущего пункта. □

21.8.Теорема. Если имеется преобразование аффинной эквивалентности характеристической функции v в v\ то вектор Шепли Ф{v) будет как дележ соответствовать вектору Шепли Ф{у).

Доказательство вытекает непосредственно из линейности выражения компонент вектора Шепли через значения характеристической функции. □



§ 22. ЭВРИСТИЧЕСКИЕ ВЫВОДЫ ФОРМУЛЫ ДЛЯ ВЕКТОРА ШЕПЛИ

22.1."Справедливо считать", что каждый игрок /Е/, создавая вместе с какими-либо другими игроками некоторую коалицию АС/, должен получить тот прирост уверенного выигрыша, т.е. значения характеристической функции

v(lO-v(K\il(22.1)

который он вносит в коалицию К.

Так, как, однако, при этом может быть сформирована любая содержащая игрока i коалиция А, справедливой долей игрока / следует считать не значение разности (22.1) для какой-либо конкретной коалиции А, а некоторое усреднение значений этой разности по всем коалициям, содержащим игрока /.

В случае вектора Шепли разность (22.1) входит в его i-ю компоненту с коэффициентом ("весом", "вероятностью")

<"-"> <"-" .(22.2)

и уместен вопрос о непосредственном обосновании этих коэффициентов как вероятностей появления коалиции А, при условии, что в нее заведомо войдет игрок /.

22.2.Наиболее простым будет представление числа (22.2) в виде

) • При таком представлении его можно понимать как вероятность совмещения двух независимых событий: равновероятного назначения размеров I К I коалиции К, т.е. равновероятного выбора одного из чисел 1, 2, . . . ,« с последующим равновероятным выбором из п - I возможных партнеров, состоящего из I А - 1 игроков набора, составляющего вместе с i коалицию IА .

22.3.Несколько "игрушечный", хотя и достаточно наглядный вид имеют следующие рассздения.

Предположим, что игроки в слзайном порядке по очереди приходят в некоторое место, причем каждый пришедший пол)ает ту сумму, на которую он увеличивает своим приходом значение характеристической функции для уже собравшейся коалиции. Покажем, что математическое ожидание этой суммы и есть компонента вектора Шепли игрока.

Рассмотрим для этого произвольную перестановку тг множества игроков. Обозначим через А(7г) множество игроков, предшествующих данному игроку i в перестановке тт. Разность

v(Ki(7r) и О - v(Ki(7r)) = A(v, и тг)(22.3)

есть тот прирост значения характеристической функции и, который игрок / осуществляет в перестановке тг.

Теорема. Если все перестановки тг равновероятны, то

MA(i;, /, тг) = - 2 А (и, /, тг) = Ф,.(1;).(22.4)



Доказательство. Число перестановок, в которых игроку / предшествуют игроки т К и только они, очевидно, равно (п-1-\К\)1, а вероятность появления такой перестановки равна

\К\1 (п-1-\К\)\.

Следовательно, по (22.3) 1

М A(i;, /, тг) = S - \К\\ {п-\-\К\)! {v{K U /) - i;(A)),

или, переобозначая под знаком суммы К U / через К,

М A(i;, /, тг) = Z 4- (11 - 1) U« - 11)! iPiK) - i(AO) = i(p\

2l это И требовалось. □

22.4. В сущности, приведенные в п.п. 22.2 и 22.3 выводы формул для компонент вектора Шепли можно считать "как бы аксиоматическими". Только применяемые при этом аксиомы (равновероятность числа партнеров в коалиции с данным игроком в равновероятность самих коалиций с заданным числом партнеров в первом случае или равновероятность всевозможных перестановок игроков во втором) представляются несколько нарочитыми и потому малоубедительными.

§ 23 *. ВЫВОД ФОРМУЛЫ для ВЕКТОРА ШЕПЛИ ИЗ АКСИОМ

23.1.Выведем формулу (21.4) для компонент вектора Шепли непосредственно из положенных в его основу аксиом эффективности, симметрии агрегации. Говоря точнее, мы воспользуемся формулой (21.1) для компонент вектора Шепли простейшей характеристической функции и явным представлением (4.3)-(4.4) произвольной характеристической функции через простейшие и преобразуем полученное выражение к виду (21.5).

23.2.Согласно пп. 21.3, 21.4 из i; = 2 XrVr, следует

Фi(v) - Z ХФ,(1;).

Подставим в правую часть этой формулы вместо коэффициента \r его выражение из формулы (4.4), а вместо Фi(vR) - его выражение из формулы (21.2). Мы получим

Ф,-(и) =2(2 (-1)11-11и(/0)- =

iR KCR\R\

= 5;( Б (-iy-ii-i-)u(r).

K\KUiCR\R\/

Нам остается преобразовать стоящее справа выражение.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [ 85 ] [86] [87] [88] [89] [90]