[ЗАСТАВКА] В 1954 году Шепли и Шубик впервые предложили использовать вектор Шепли для анализа голосований. Теперь вектор Шепли, использующийся применительно к простым играм, обычно называют индексом влияния Шепли–Шубика. Соответствующие компоненты вектора Шепли — индексом влияния того или иного игрока. Можно предложить другую интерпретацию для индекса Шепли–Шубика. Соответствующая компонента этого вектора соответствует доле последовательностей, в которых игрок i оказывается ключевым при принятии решения голосованием большинством. Определение: игрок называется ключевым, если после его присоединения к коалиции, коалиция из проигрывающей становится выигрывающей. То есть без i-того игрока платеж коалиции был равен нулю, а с i-тым игроком платеж коалиции стал равным единице. Вот если это так, то игрок называется ключевым. Тогда в случае простых игр формулу для вектора Шепли можно переписать в более простом виде. Давайте заметим, что разность, характеризующая платеж, который приносит i-тый игрок в коалицию K без i-того игрока, то есть разность (v(K) − v(K) \ {i})) всегда равен либо нулю, либо единице. Он равен единице только в тех случаях, когда игрок i оказывается ключевым. То есть без него коалиция была проигрывающей, а с ним коалиция является выигрывающей. Во всех остальных случаях эта разность равна нулю. Поэтому все нулевые слагаемые в векторе Шепли можно отбросить и тогда формулу для вектора Шепли можно переписать так: i-тая компонента вектора Шепли равна сумме по всем коалициям K, в которые входит i-тый игрок, причем коалиция K является выигрывающей, а i-тый игрок — ключевым. И вот в эту сумму входят слагаемые, которые равны (k − 1)! * (n − k)! / n!, где k — это размер коалиции K, а n — общее количество игроков. Еще один пример игр с голосованиями — это голосование с квотой. Давайте представим, что у нас есть несколько игроков и у каждого из игроков есть определенное количество голосов, которые можно отдать в пользу... которыми можно высказаться «за» или «против». Тогда выигрыш коалиции K равен 1, если сумма голосов игроков, входящих в эту коалицию, позволяет преодолеть квоту Q. То есть преодолеть тот барьер, начиная с которого решение считается принятым. Во всех остальных случаях выигрыш коалиции равен нулю. Давайте рассмотрим такой пример: пусть у нас есть четыре игрока. У первого игрока 4 голоса, у второго игрока 2 голоса, у третьего игрока 1 голос и у четвертого игрока 1 голос. Квота равна 5. То есть это означает, что для принятия решения нам нужно набрать по крайней мере 5 голосов. То есть, выигрыш коалиции равен 1, если сумма набранных голосов хотя бы 5, и ноль во всех остальных случаях. Рассматриваем выигрывающие коалиции, выпишем их. Их оказывается 7 штук, они представлены на ваших экранах. И теперь найдем, какие игроки в каждой из этих коалиций являются ключевыми. Давайте по горизонтали выпишем все выигрывающие коалиции. По вертикали выпишем имена игроков, и на пересечении строчки и столбца будем ставить единичку в том случае, если игрок, который указан по вертикали, является ключевым для коалиции, которая указана по горизонтали. То есть, если без этого игрока коалиция, указанная по горизонтали, будет получать ноль, а с ним — 1. Теперь мы можем легко посчитать соответствующие компоненты индекса Шепли-Шубика. Первый игрок является ключевым для трех коалиций размера 2, для трех коалиций размера 3 и для одной коалиции размера 4. Поэтому соответствующая компонента индекса Шепли-Шубика равна 3/4. Расчет приведен на экранах. Для второго игрока индекс Шепли-Шубика равен 1/12. Для второго, третьего и четвертого игроков индекс Шепли-Шубика равен 1/12. Таким образом, индекс Шепли-Шубика равен 3/4 для первого игрока, и 1/12 для всех остальных игроков. Первый игрок, у которого 4 голоса, оказывает существенно большее влияние на исход голосования, чем все остальные игроки. Кроме того, первый игрок является вето-игроком. То есть, если бы мы искали ядро, то этот игрок получил бы 1, а все остальные игроки получили бы 0. Наконец, заметим, что компоненты для индекса Шепли-Шубика второго, третьего и четвертого игрока равны, хотя веса, которые есть у второго, третьего и четвертого игроков различаются: у второго игрока есть 2 голоса, у третьего и четвертого игроков — всего по 1 голосу. Тем не менее, оказывается, что несмотря на это переговорная сила второго, третьего и четвертого игроков абсолютно одинакова. И, наконец, рассмотрим реальный пример. Давайте оценим влияние различных партий, представленных в парламенте Исландии. Выборы состоялись в 2013 году. Всего в альтинге (так называется парламент Исландии) 63 места. Простое большинство составляет 32 голоса. Всего в парламент входит шесть партий, их веса представлены на экранах. Формально опишем эту игру: есть 6 игроков, выигрыш коалиции равен 1, если этой коалиции удается преодолеть квоту, которая в этой игре равна 32. В противном случае, коалиция получает платеж, равный 0. Найдем индекс Шепли-Шубика для каждой партии. Сначала проанализируем Партию независимости. Выпишем все выигрывающие коалиции, в которых Партия независимости является ключевой. Все эти выигрывающие коалиции представлены на ваших экранах — их 16. Соответственно, компонента индекса Шепли-Шубика для Партии независимости будет равна 0,3. Расчеты представлены на ваших экранах. Теперь проанализируем Прогрессивную партию. У Прогрессивной партии те же самые 19 мест в парламенте, что и у Партии независимости. Поэтому компонента индекса Шепли-Шубика для Прогрессивной партии тоже равна 0,3. У Социал-демократического альянса компонента индекса Шепли-Шубика равна 2/15, то есть примерно 0,13, точно также компонента индекса Шепли-Шубика равна 0,13 и для Лево-зеленого движения. Наконец, у Светлого будущего компонента индекса Шепли-Шубика также равна 0,13. А у Пиратской партии она равна 0, потому что она не является ключевой ни в одной из выигрывающих коалиций. Распределение влияния партий в парламенте может быть представлено в следующем виде: У Партии независимости и Прогрессивной партии этот индекс влияния равен 0,3. У Социал-демократического альянса, Лево-зеленого движения и Светлого будущего — 0,13. А у Пиратской партии он равен 0. Индекс влияния характеризует переговорную силу, каждой из этих партий. [ЗАСТАВКА]