Содержание к диссертации
Введение
1. Индексы влияния: основные понятия и обзор литературы 16
1. Простые игры и голосования с квотой 16
1.1. Простые игры 16
1.2. Голосования с квотой 24
2. Индексы влияния 30
2.1. Предыстория: решение кооперативной игры и вектор Шепли 30
2.2. Индексы влияния: общие соображения 35
2.3. Классические индексы влияния 37
2.3.1. Индекс Шепли—Шубика 37
2.3.2. Индексы влияния Банцафа и Пенроуза 37
2.3.3. Вероятностная интерпретация и сравнение индексов Банцафа (Пенроуза) и Шепли—Шубика . 40
2.4. Другие индексы влияния 42
2.4.1. Индекс Джонстона 43
2.4.2. Индекс Холера—Пакела 43
2.4.3. Индекс Дигена — Пакела 44
2.4.4. Индекс Коулмена 46
2.5. Свойства влияния: аксиомы и парадоксы 47
3. Игры и индексы влияния, зависящие от предпочтений участников 54
3.1. Общая конструкция: симметричные и несимметричные игры 58
3.2. Индексы влияния 60
2. Аксиоматическое описание индексов влияния 63
1. Избранные аксиоматики для классических индексов влияния 63
1.1. Аксиоматика Дуби для индекса Шепли—Шубика и аксиоматика Дуби—Шепли для общего индекса Банцафа 64
1.2. Аксиоматики Ларуелль—Валенсиано 66
2. Аксиоматики для индексов влияния, зависящих от предпочтений участников 69
2.1. Теорема классификации 70
2.2. Аксиоматики для «-индекса 75
2.2.1. Следствие из теоремы классификации 76
2.2.2. Аналог аксиоматики Ларуелль—Валенсиано 76
2.3. Применение к индексам Банцафа и Шепли—Шубика 81
3. Аксиоматики для индексов влияния в случае голосования с квотой 82
3.1. Аксиоматики для индексов Банцафа и Шепли—Шубика 86
3.2. Аксиоматика для «-индекса в случае голосований с квотой 90
4. Проективные аксиоматики для индексов влияния 92
4.1. Проективные индексы влияния: определения 93
4.2. Аксиомы 95
4.3. Основная теорема 97
4.4. Аксиоматики для нормированного «-индекса и нормированного индекса Банцафа 101
4.4.1. Следствие: аксиоматика для нормированного ин
декса Банцафа 103
5. Обзор и сравнение аксиом 104
5.1. Сравнение аксиом Дуби—Шепли, Ларуелль-Валенсиано и следствий из аксиоматик для «-индекса 106
5.2. Аксиоматики для нормированных индексов влияния 107
3. Оценки и алгоритмы для расчета индексов влияния 109
1. Теорема о среднем для индексов влияния 109
2. Алгоритмы вычисления индексов влияния 115
2.1. "Прямое" вычисление. Оценка сложности 116
2.2. Метод производящих функций 117
2.3. Приближенные методы вычисления индексов влияния 122
3. Алгоритмы расчета индексов влияния, зависящих от предпочтений участников с помощью производящих функций 125
3.1. Аналог индекса Банцафа 126
3.2. Аналог индекса Шепли—Шубика 126
3.3. Основная теорема 127
4. Примеры и применение 129
4.1. О правиле принятия решения в Совете министров Европейского Союза 129
4.2. Комплекс программ для вычисления индексов влияния, зависящих от предпочтений участников 135
4.2.1. Основная программа 136
4.2.2. Вспомогательные программы 136
Заключение 138
Литература 140
Приложения 150
- Вероятностная интерпретация и сравнение индексов Банцафа (Пенроуза) и Шепли—Шубика
- Аксиоматики для индексов влияния, зависящих от предпочтений участников
- Сравнение аксиом Дуби—Шепли, Ларуелль-Валенсиано и следствий из аксиоматик для «-индекса
- О правиле принятия решения в Совете министров Европейского Союза
Введение к работе
Коллективное принятие решений является одним из основных способов управления сложными социальными и экономическими системами.
Если речь идет о принятии каких-то решений, например, в парламентах, законодательных собраниях и т.п., обычно считается, что влияние партии на принятие этих решений прямо зависит от числа мест, которыми она располагает в парламенте. Однако, известно много примеров, которые противоречат этому, казалось бы естественному мнению. Аналогично, влияние акционера не всегда зависит от доли акций, которыми он владеет.
Использование в указанной задаче кооперативной теории игр привело к созданию такой концепции решения игры, как вектор Шепли и, как его развитие, многочисленным индексам влияния.
Индекс влияния — это способ оценить влияние участника (или партии) в выборном органе, т.е. приписать каждой партии неотрицательное число, пропорциональное ее влиянию на принятие решений. Среди индексов влияния наиболее известен индекс Банцафа.
Актуальность темы
Развитие теории индексов влияния включает два направления:
аксиоматическое, позволяющее понять различие и определить границы применимости индексов.
вычислительное, в котором строятся алгоритмы, вычисляющие индексы влияния при большом количестве игроков.
Первое систематическое изложение теории игр (и, в частности, кооперативной теории игр) было дано Д. фон Нейманом и О. Моргенштерном в 1944 г.
Формальная постановка задачи оценки влияния была предложена JI. Пенро- узом в 1946 г.
Фундаментальные работы в этой области были выполнены JI. Шепли, М.
Шубиком, Дж. Банцафом и др.
В настоящее время множество работ, как в России, так и за рубежом посвящено изучению теории индексов влияния и прикладным вопросам распределения влияния в различных организациях, например, Европейском Союзе, МВФ и др.
Но классические индексы влияния учитывают только коалиционные возможности участников процесса принятия коллективных решений и не учитывают взаимоотношения между ними. В реальности некоторые коалиции образуются часто, некоторые реже, некоторые, возможно, не образуются вообще.
Недавно Ф.Т. Алескеровым были введены в рассмотрение индексы влияния, учитывающие предпочтения участников по вступлению в коалиции.
Поэтому развитие теории индексов влияния, учитывающих предпочтения участников по созданию коалиций, представляется актуальным.
Цель работы
Разработка аксиоматик, методов и алгоритмов оценки влияния участников в задаче принятия коллективных решений, учитывающих ограничения на формирование коалиций.
Основные задачи
-
-
Построение аксиоматик для индексов влияния, зависящих от предпочтений участников и, как следствие, новых аксиоматик для классических индексов влияния, как в классическом случае (простые кооперативные игры), так и для голосований с квотой.
-
Обоснование и развитие подхода к индексам влияния, как к элементам проективного пространства.
-
Построение эффективных алгоритмов для вычисления индексов влияния, зависящих от предпочтений участников и создание соответствующего программного комплекса.
4) Проверка "гипотезы о среднем", предполагающей, что "в среднем по квоте" влияние участника голосования пропорционально числу его голосов.
Методы исследования
Используются модели простых игр, комбинаторного анализа, теории множеств, элементы проективной геометрии, техника производящих функций.
Научная новизна работы
-
-
-
Впервые развит подход к индексам влияния, как к элементам проективного пространства;
-
Впервые построены аксиоматики для индексов влияния, зависящих от предпочтений участников а) в случае простых игр; б) в случае голосования с квотой; в) как элементов проективного пространства;
-
Впервые предложен алгоритм вычисления индексов влияния, зависящих от предпочтений участников, использующий производящие функции;
-
Впервые осуществлена проверка "гипотезы о среднем", предполагающей, что "в среднем по квоте" влияние участника голосования пропорционально числу его голосов и доказан аналог этого утверждения для индексов влияния, зависящих от предпочтений участников.
Применение
Модели индексов влияния, учитывающих предпочтения участников, включены в курсы лекций "Дискретные математические модели" и "Модели согласования интересов", которые читаются на факультетах экономики и бизнес- информатики НИУ ВШЭ.
Апробация работы
Результаты работы докладывались на
общемосковском семинаре "Экспертные оценки и анализ данных" в ИПУ РАН в 2009 и 2010 гг.;
конференции "Экономическое развитие в современном мире: Россия и Азия в условиях глобальной экономической нестабильности (УРГУ, Екатеринбург, 2009);
Научном семинаре Международной лаборатории анализа и выбора решений (НИУ ВШЭ, 2009);
10-й Международной конференции Общества по исследованию социального выбора и благосостояния (10-th International Meeting of the Society for Social Choice and Welfare, НИУ ВШЭ, Москва, 2010);
VI-й Московской международной конференции по исследованию операций (ВМК МГУ, 2010);
XIII и XIV Апрельских международных научных конференциях по проблемам развития экономики и общества (Москва, НИУ ВШЭ, 2012, 2013);
научном семинаре Лаборатории теории игр и принятия решений Санкт- Петербургского экономико-математического института РАН (научный руководитель д.ф.-м.н. Е.Б. Яновская, 2013);
Школе-конференции "Байкальские чтения" (ИМЭИ ИГУ, Иркутск, 2013);
Результаты исследования опубликованы в 6 работах, список которых приводится в конце автореферата.
Структура и объем диссертации.
Вероятностная интерпретация и сравнение индексов Банцафа (Пенроуза) и Шепли—Шубика
Классические индексы влияния имеют существенный недостаток — все они не учитывают взаимоотношения между игроками (или, по другому, предпочтения игроков по созданию коалиций), в то время как некоторые коалиции могут образовываться часто, некоторые редко, некоторые, возможно, не образовываться вообще.
Кажется естественным учитывать предпочтения игроков при подсчете влияния. На самом деле этот подход далеко не бесспорен и вызвал оживленную дискуссию [36, 37, 76] — чего стоят только названия статей: "The impossibility of a preference-based power index" vs "The possibility of a preference-based power index".
Основной аргумент за "impossibility" [36] — учет предпочтений противоречит самой концепции влияния, поскольку влияние это возможность влиять на исход голосования, и не должно зависеть от действий игрока.
Кроме того, если же игрок своими действиями может увеличить влияние (и, весьма вероятно, стремится это сделать), то речь идет уже о теоретико-игровой (причем не коалиционной) модели.
С другой стороны ([76]), возможности "стратегического поведения" игрока ограничены, поскольку странно ради мифического увеличения влияния голосовать за те решения, с которыми он категорически не согласен.
Подробнее с аргументами сторон можно познакомиться (кроме оригинальных статей) в обзоре [16].
Хотя многое, сказанное в этой дискуссии, актуально для любых индексов влияния, зависящих от предпочтений участников, реально в ней обсуждался первый из них, индекс Шепли—Оуэна [82], в котором предпочтения участников относительно исхода голосования зависели от их идеологической позиции, интерпретируемой, как точка в -мерном пространстве.
Однако, попытки применить индекс Шепли—Оуэна к реальным данным ([33, 89], в обеих статьях обсуждалось распределение влияния в Евросоюзе) показали его серьезные недостатки.
Альтернативная модель первоначально была основана на "бинарной логике" — коалиции либо возможны, либо нет.
Утрируя, представим себе, что коалиция {А, В} выигрывающая, но партии А и В придерживаются противоположных точек зрения по ключевым вопросам, т.е. коалиция {А, В} при реальных голосованиях не образуется.
Существует два способа ввести ограничения на создание коалиций:
1) Считать, что если партии А и В не вступают в коалицию, то невозможна только коалиция {А, В} (т.е. она объявляется проигрывающей) и только она. А, например, коалиция {Л, В, С}, возможна (т.е. остается выигрывающей).
2) в той же ситуации считать, что невозможна никакая коалиция, содержащая одновременно А и. В. Формально говоря, это предположение не вписывается в концепцию простой игры, поскольку нарушается условие монотонности (например, тотальная коалиция будет проигрывающей всегда). Вычисление индекса влияния Банцафа в этой ситуации возможно, но может привести к делению на 0.
Впервые эта модель была рассмотрена в [4], поскольку при исследовании распределения влияния в Государственной Думе РФ выяснилось, что индекс Банцафа не описывает реальную ситуацию. Какие коалиции могут образовы ваться, какие нет, определялось, исходя из введенного в этой работе индекса согласованности партий, основанного на результатах предыдущих голосований.
Обе рассмотренные выше модели применялись к анализу реальных выборных органов [4, 5, 95, 96] и давали результаты часто совершенно отличные от "чистых" индексов влияния. Так, в ГД РФ 3-го созыва КПРФ была самой многочисленной партий, но в некоторые периоды времени влияние КПРФ, вычисленное с учетом ограничений на образование коалиций было равно 0 [4, 5].
Пример 22 ([7]). Рассмотрим голосование с квотой (51; 50,49,1) и обозначим игроков А, В и. С. Выигрывающими коалициями будут {А, ?}, {А, С} и {А, В, С}. Игрок А ключевой во всех коалициях, В и. С — только в одной. Поэтому индекс влияния Банцафа равен Bz(A) = 5 Bz(B) = і Bz(C) = \. 5 5 5 1) Предположим теперь, что по каким-либо причинам игроки А и В в коа лицию не вступают, но коалиция {А, В, С} возможна. Выигрывающими коали циями теперь будут только {А, С} и {Л, В, С}. Вычислим индекс Банцафа: Bz(A) = Bz(B) = 0, Bz(C) = і 2) Если же В и С не вступают в коалицию, даже если в нее входят другие игроки, то выигрывающими останутся только коалиции {А, В} и {А, С}. Игрок А ключевой в двух коалициях, В и. С — в одной. Поэтому индекс влияния Банцафа равен: т.е. нежелание двух игроков вступать в коалицию друг с другом может (вопреки интуиции) привести к увеличению влияния обоих. Это явление называется "парадокс вражды" и было подробно изучено в работах [38, 62]. Более общая конструкция такого типа — игры с ограниченной кооперацией, впервые рассмотренные в [75]. Игрой с ограниченной кооперацией называется тройка (N,v,G), где (N,v) — обычная кооперативная игра, a G — неориентированный граф, вершины ко торого — игроки, а ребра означают, что кооперация между соответсвующими игроками возможна. Для простых игр естественно считать коалицию S выигрывающей, если она выигрывающая в исходной игре и граф Gs связен [42]. Или можно предполагать, что S выигрывающая, если среди связных компонент графа Gs есть выигрывающая коалиция. Например, ситуация, когда в коалицию не вступают только партии А и. В, соответствует графу, содержащему все возможные дуги, кроме (Л, В). Другой (более общий) способ определить игру с ограниченной кооперацией — задать выигрыши только допустимых коалиций (см., например, [61]). В этом случае игрой с ограниченной кооперацией называется тройка множество игроков, Q, С 2 — множество допустимых коалиций, характеристическая функция.
Аксиоматики для индексов влияния, зависящих от предпочтений участников
Поскольку игрок і ключевой в коалиции 5, если и только если коалиция 5\{г} набирает от q — ггц до q — 1 голосов, то число коалиций, в которых г ключевой, т.е. общий индекс Банцафа равен т.е. равно сумме коэффициентов производящей функции S(x, у) при s-й степени у и степенях х от q — Wi до q — 1-й, что позволяет вычислить индекс Шепли— Шубика.
При вычислении коэффициентов производящих функций Gi естественно после раскрытия очередных скобок сразу же приводить подобные слагаемые. Именно благодаря этому одновременно обрабатываются многие коалиции с одинаковой суммой голосов при вычислении индекса Банцафа и с одним и тем же числом участников и суммой голосов для индекса Шепли—Шубика. Особенно такая схема вычислений эффективна, если многие участники голосования имеют равное число голосов. В этом случае соответствующие им скобки можно раскрывать с помощью формулы бинома Ньютона.
При последовательном перемножении можно исключать члены, степень которых по х не меньше квоты, поскольку в дальнейшем эта степень не может уменьшиться и не будет учтена при подсчете выигрывающих коалиций. Аналогично, можно не учитывать члены, степень которых при домножении не может достигнуть q — Wi.
Пример 4. Вычислим с помощью производящих функций индекс Банцафа для голосования с квотой (5;3,2,1,1,1).
Для вычисления индекса Банцафа методом производящих функций требуется 0(C(v) п), где C(v) — число различных значений, которые может принимать вес коалиции в игре v [34]. Оценка для индекса Шепли—Шубика хуже — 0(C(v) п2). Отметим, что С не превосходит суммарное число голосов. Более того, используя соображения из предыдущего абзаца, оценку можно улучшить до q п (q п2). Пример 5. [95] Политические группы в Европейском парламенте и неприсоединившиеся депутаты образуют игру из 36 игроков: 7 партий с голосами 266, 201, 89, 42, 41, 35, 27 и 29 неприсоединившихся депутатов. Игра имеет вид: (367; 266, 201, 89,42,41, 35, 27,1,..., 1). Производящая функция для 1-го игрока содержит 464 ненулевых коэффициента. При полном переборе придется рассмотреть 235 « 3, 43 1010 коалиций. Но в плохом случае (веса всех коалиций различны) C(v) = 2п и число операций ровно то же, что и при "прямом" вычислении. Производящие функции были использованы для вычисления индексов влияний практически сразу после их (индексов) появления. Впервые — в [73] в 1962 г. для вычисления индекса Шепли—Шубика. Метод был адаптирован для вычисления индекса Банцафа в [39] и применялся, в частности, для оценки влияния в Коллегии выборщиков США [64] и совете министров Евросоюза [35, 96]. В [27, 96] метод производящих функций был адаптирован для индексов влияния, учитывающих ограничения на создание коалиций. Если число игроков (и число их голосов) слишком велико, чтобы применить прямые методы вычислений индексов влияния, необходимо использовать приближенные методы. Насколько известно автору, приближенные вычисления индексов влияния проводились только для индексов Банцафа и Шепли—Шубика, используя их вероятностную интерпретацию. Иначе говоря, раз влияние — вероятность некоторого события, то его можно оценить, используя математическую статистику. Основной недостаток перечисленных ниже методов — невозможность хорошо оценить точность вычислений. Скорее всего он неустраним, поскольку индексы влияния "не непрерывны" — очень маленькие изменения числа голосов могут привести к существенному перераспределению влияния.
Достоинство, как и полагается приближенным методам, — малое время работы, точнее можно потратить все имеющееся машинное время, сколько бы его не было — чем больше "итераций", тем выше точность.
Впервые ([72], 1960г.) индексы влияния были приближенно вычислены методом Монте-Карло. Способ зависит от вероятностной интерпретации. Так, для вычисления индекса Шепли—Шубика можно выбирать случайный порядок игроков и считать, в какой доле случаев при добавлении игрока і образовалась выигрывающая коалиция. Для индекса Пенроуза (Банцафа) необходимо выбирать случайную коалицию и считать вероятность того, что игрок в ней будет ключевым. В [79, 80] Оуэн предложил метод, основанный на том, что коэффициент в формуле для индекса Шепли—Шубика представляет собой бета-функцию:
Сравнение аксиом Дуби—Шепли, Ларуелль-Валенсиано и следствий из аксиоматик для «-индекса
Как будет показано ниже, сложность вычисления индексов влияния, кроме самого индекса, может быть оценена исходя из числа игроков и (если речь идет о голосовании с квотой) суммарного числа голосов. Следующие примеры показывают, о каких цифрах идет речь.
Сразу отметим, что нормировка индекса влияния (т.е переход от ненормированного к нормированному индексу) требует 0(п) операций, что много меньше, чем требуется на остальные вычисления. Поэтому дальше будет говориться только о ненормированных индексах.
Бесхитростный (т.е. основанный на определении или предложении 4) алгоритм вычисления любого индекса влияния требует перебора всех 2п коалиций, причем для каждой из них нужно проверить, какие игроки будут ключевыми, т.е. даже если вычисление f(S) требует 0(1) операций1, то вычисление ненормированного индекса влияния требует 0(п 2п) ([69]) операций.
Если число игроков порядка 200 (как в приведенных выше примерах), число операций оценивается, как 200 2200 1062, что неприемлемо для реальных вычислений.
Если простая игра задана таблицей значений характеристической функции, то задача сокращения времени вычислений не актуальна, поскольку сама таблица значений занимает 0(2п) ячеек памяти и 0(2П) операций потребуется только для чтения таблицы. Кроме того, так задаются только игры с малым (как правило не более 10) числом игроков, и в этом случае нет нужды в сокращении перебора.
Большинство практических вычислений производится, когда простая игра может быть записана, как голосование с квотой. Далее будем рассматривать только этот случай.
Сократить перебор можно, если не рассматривать заведомо не подходящие коалиции, т.е. коалиции, в которых не может быть ключевых игроков, т.е. перебирать только такие коалиции 5, что q w(S) q + wmax, где w max число :Что неверно уже для индекса Шепли—Шубина голосов "самого сильного" игрока: wmax = maxггц. Но возникают две проблемы. ieN
1) Непонятно, как эффективно выделить такие коалиции. В [74] показано, что уже NP-трудной будет даже проверка, существует ли коалиция с данным числом голосов.
2) В любом случае, радикально сократить перебор не удастся. Даже в близком к "идеальному" случае, когда все игроки имеют по одному голосу, а квота равна "половине голосов плюс один" (пусть для определенности п четно), выигрывающими коалициями с ключевыми игроками будут все коалиции из п + 1 игроков, которых
К сожалению, если считать, что веса игроков и квота — произвольные целые числа, то полиномиального алгоритма, позволяющего вычислять индексы влияния, не существует. В единственной известной автору работе на эту тему [74] показано, что задачи вычисления индексов Банцафа и Шепли—Шубика NP-полные даже в случае, если квота равна половине числа голосов +1 голос.
Если же веса игроков невелики, возможны более оптимистичные оценки.
Задачу вычисления индексов влияния можно рассматривать и как комбинаторную задачу. Прямое вычисление (как правило использующее биноминальные коэффициенты) возможно только для индекса Банцафа и только в редких случаях (см. пример 2 или, например, [7]).
Лучшие результаты дает использование другой классической комбинаторной техники — производящих функций.
Определение 1 ([13]). Пусть {сц) — некоторая (не важно, конечная или бесконечная) последовательность. Производящей функцией этой последовательности называется (формальная) сумма: CLQ + а\х + а,2Х2 + ... + щхг + ...
Производящие функции определены и для последовательностей с несколькими индексами. В этом случае производящие функции зависят от нескольких переменных. Так, производящей функцией для последовательности (fl j) будет
Пример 3. Функция будет производящей функцией для последовательности биноминальных коэффициентов: Вычислять индексы Банцафа и Шепли—Шубика помогает следующая лемма. Пусть (q; w\:..., wn) — голосование с квотой, 6&(г) — число коалиций с суммарным числом голосов к, не включающим игрока г, а &&)П(г) — число коалиций из п игроков с суммарным числом голосов к, не включающим игрока г. Лемма 1. [68] Производящая функция для последовательности Ъ {г) равна а для последовательности &й;П(г) — Поскольку игрок і ключевой в коалиции 5, если и только если коалиция 5\{г} набирает от q — ггц до q — 1 голосов, то число коалиций, в которых г ключевой, т.е. общий индекс Банцафа равен
О правиле принятия решения в Совете министров Европейского Союза
Если число игроков (и число их голосов) слишком велико, чтобы применить прямые методы вычислений индексов влияния, необходимо использовать приближенные методы.
Насколько известно автору, приближенные вычисления индексов влияния проводились только для индексов Банцафа и Шепли—Шубика, используя их вероятностную интерпретацию. Иначе говоря, раз влияние — вероятность некоторого события, то его можно оценить, используя математическую статистику.
Основной недостаток перечисленных ниже методов — невозможность хорошо оценить точность вычислений. Скорее всего он неустраним, поскольку индексы влияния "не непрерывны" — очень маленькие изменения числа голосов могут привести к существенному перераспределению влияния.
Достоинство, как и полагается приближенным методам, — малое время работы, точнее можно потратить все имеющееся машинное время, сколько бы его не было — чем больше "итераций", тем выше точность.
Впервые ([72], 1960г.) индексы влияния были приближенно вычислены методом Монте-Карло. Способ зависит от вероятностной интерпретации. Так, для вычисления индекса Шепли—Шубика можно выбирать случайный порядок игроков и считать, в какой доле случаев при добавлении игрока і образовалась выигрывающая коалиция. Для индекса Пенроуза (Банцафа) необходимо выбирать случайную коалицию и считать вероятность того, что игрок в ней будет ключевым.
В [79, 80] Оуэн предложил метод, основанный на том, что коэффициент в формуле для индекса Шепли—Шубика представляет собой бета-функцию:
Если считать, что игроки принимают решения независимо и х — вероятность того, что игрок голосует за, подынтегральная функция равна вероятности того, что коалиция S голосует за решение, а N \ (5 U {і} — против, т.е. вероятности того, что голос игрока і окажется решающим. Вероятность же того, что игрок і будет ключевым в образовавшейся коалиции, будет равна Чтобы получить индекс Шепли—Шубика, нужно проинтегрировать р(х) от 0 до 1, а чтобы получить индекс Банцафа — подставить х = 1/2.
Поэтому для приближенного вычисления индексов Банцафа и Шепли—Шубика достаточно оценить р(х). Для этого рассматривается случайная величина Wi(x), равная сумме голосов всех игроков, входящих в коалицию с і. Игрок і ключевой в получившейся коалиции, если q — W{ Wi(x) g, т.е.
Эта вероятность приближенно вычисляется в предположении, что Wi(x) распределено нормально.
Предположение о нормальном распределении Wi{x) допустимо, если игроков много и все они обладают примерно одинаковым числом голосов. Если это не aтак, то ошибки вычисления могут быть велики [69, 94].
В работах Д. Лича [68, 69] предлагается комбинированный метод, сочетающий в себе "прямой" алгоритм и метод Оуэна. Типична ситуация, в которой несколько игроков обладают относительно большим числом голосов (мажоритарные акционеры в акционерных обществах), а остальные — малым. Пусть М — множество игроков с большим числом голосов. Функцию fi (х) можно вычислить, как где p(S,x) = xs(l — x)m s l — вероятность того, что все игроки коалиции S проголосуют за решение, а М \ (S U {і}) — против, a gi(S,x) — вероятность того, что игрок г будет ключевым в сложившейся ситуации.
Для каждого S функция р(5, х) вычисляется точно, a gi(S,x) приближенно, тем же методом, что и fi(x) в методе Оуэна.
Число "больших" игроков выбирается либо исходя из специфики игры, либо из имеющегося машинного времени — чем больше "больших" игроков, тем больше времени займет вычисление, но тем оно будет точнее.
Скорее всего, метод Лича дает хорошие результаты (хотя автору не известно, использовался ли он где-нибудь, кроме оригинальных работ), но получить оценку его точности затруднительно.
3. Алгоритмы расчета индексов влияния, зависящих от предпочтений участников с помощью производящих функций
"Прямой" алгоритм вычисления индексов влияния работает для а-индекса столь же хорошо, как и для классических индексов влияния. Алгоритм состоит в переборе коалиций и в этом случае не важно, что суммировать по всем элементам Wi(v) — константы, как в индексе Банцафа, или какие-то другие числа.
Но, "прямой" алгоритм не позволяет вычислять индексы влияния за разумное время уже при п 60. Поэтому встает вопрос, как применить к «-индексу метод производящих функций.
В этом разделе предполагается, что функции f(i,S) зависят только от матрицы предпочтений Р ([28], см. также пример 23, глава 1). Для того, чтобы подчеркнуть этот факт, вместо f(i,S) будем писать /(г, 5, Р).
Похожие диссертации на Индексы влияния, зависящие от предпочтений участников - аксиоматическое построение и методы вычисления
-
-
-
