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

Как известно, имеется три основных формы представления игры. Это 1) расширенная форма (дерево игры), 2) нормальная форма (стратегические матрицы) и 3) форма характеристической функции, которая и применяется в теории кооперативных игр. Теория кооперативных игр - это теория коалиций. Она изучает игровые ситуации, в которых допустимы совместные действия игроков и побочные платежи (перераспределение выигрыша). Для возможности беспрепятственного перераспределения выигрыша принимается допущение о том, что любые выигрыши, как индивидуальные, так и коллективные, приводимы к единой шкале (например к денежному эквиваленту) и неограниченно делимы. Смысл этой идеи заключается в том, что выигрыш коалиции всегда можно разделить между ее участниками в нужной пропорции. Одной из основных проблем теории кооперативных игр является как раз проблема (справедливого) дележа.

Новым элементом игры являются побочные платежи. Что нового они дают? Проиллюстрируем это на простом примере. Пусть имеется игра типа «семейного спора», но с перераспределяемыми (трансферабельными) выигрышами, заданная матрицей:

Пусть игроки применяют совместную смешанную стратегию (х, 1-х), где х – вероятность выбора точки (4,2), а (1-х) – точки (2,6). Оптимальным по Парето множеством в этой игре является отрезок прямой, соединяющий указанные точки. В зависимости от выбранной стратегии х суммарный выигрыш обоих игроков будет равен:

(4.1)

Максимум (4.1), равный 8, достигается при х=0, то есть при выборе обоими игроками своих вторых чистых стратегий. Пусть игроки выбрали какую-то совместную смешанную стратегию, в которой х отличен от нуля. Тогда, согласно (4.1), их суммарный выигрыш меньше 8. Рассмотрим следующую альтернативу. Игроки договариваются о том, что будут неизменно выбирать точку (2,6) с суммарным выигрышем 8, но второй игрок будет регулярно передавать часть своего выигрыша первому игроку с таким расчетом, чтобы выигрыши обоих игроков были больше, чем при применении стратегии х. Это всегда можно сделать, так как разница в суммарных выигрышах составляет 2х. Надо лишь как-то разделить ее между игроками, например, пополам. Тогда первый игрок получит , а второй - . То есть оба получат больше, чем при применении даже совместной смешанной стратегии. Таким образом, побочные платежи могут обеспечить игрокам большие возможности, нежели совместные смешанные стратегии.

Отметим лишь, что для осуществления идеи побочных платежей игра должна удовлетворять определенным требованиям. Выигрыши должны быть трансферабельными. Например, в классической постановке игры «семейный спор» жена не может передать часть своего удовольствия от посещения театра мужу. Выигрыши здесь не трансферабельны, и побочные платежи невозможны. Кроме того, выигрыши коалиций игроков должны быть устроены таким образом, чтобы побочные платежи были реализуемы. (Коалиция должна иметь «лишние деньги»).

В рамках теории кооперативных игр обычно принимаются следующие обозначения. Любое непустое множество игроков SÎN называется коалицией. Например, множество {1, 2} называется коалицией игроков 1 и 2. Характеристической функцией игры n лиц, отождествляемой обычно с игрой, называется вещественная функция v(S), определенная на множестве всех коалиций SÎN, и удовлетворяющая условиям:

v(Т) + v(S) £ v(TÈ S) (при TÇS=Æ) и v(Æ)=0.

Говоря простым языком, характеристическая функция - это функция выигрыша коалиции, которая каждой коалиции ставит в соответствие число - ее выигрыш в универсальных перераспределяемых единицах. Это число v(S), характеризует возможности коалиции и является мерой того, чего могут достигнуть участники S, формируя свою коалицию независимо от других игроков. В частности v({i}) есть то, чего может достигнуть отдельный игрок i своими собственными силами: его индивидуальный выигрыш (максимин). Первое из вышеприведенных условий называется свойством супераддитивности и означает, что расширение состава коалиции не может приводить к уменьшению ее возможностей. Второе условие есть просто доопределение функции на пустом множестве: пустая коалиция не имеет никакого выигрыша. Кооперативная игра считается заданной, если заданы множество игроков, коалиции и характеристическая функция, то есть, если указаны выигрыши каждой коалиции.

Для коалиции из двух и более игроков не имеет значения, как она формируется, каким путем игроки пришли к соглашению или насколько вероятно, что они вообще сформируют какую-либо коалицию. Ключевым моментом является только то, что v(S) реализуется только в результате соглашения и сотрудничества всех членов S. Выигрыш v(S) коалиции S является агрегированной величиной, то есть единственным числом, а не вектором, определяющим для каждого члена коалиции его индивидуальный выигрыш.

Из свойства супераддитивности следует, что для любой системы непересекающихся множеств S₁, ... , S_k

Это, в частности, означает, что не существует такого разбиения множества N на коалиции, чтобы суммарный выигрыш этих коалиций превышал выигрыш всеобщей коалиции.

Основная задача теории кооперативных игр заключается в построении реализуемых принципов оптимального распределения выигрыша всеобщей коалиции v(N) между ее участниками. Пусть a_i - сумма, которую получает игрок i при распределении выигрыша. Тогда вектор a = (a₁,..., a_n ) называется дележом, если выполнены следующие условия

(4.2)

Смысл условий весьма прозрачен. Они означает, что каждый игрок должен получить при дележе не меньше, чем он может заработать в одиночку, и, что весь выигрыш коалиции полностью и без остатка доложен быть поделен между ее участниками.

Если в (4.2) имеет место знак строгого неравенства, то игра называется существенной, в противном случае - она несущественна. В существенной игре каждый участник всеобщей коалиции может получить строго больше, чем может заработать сам. Во всякой существенной игре с более чем одним игроком множество дележей бесконечно. Такие игры анализируются с помощью отношения доминирования.

Определение. а) Дележ a доминирует дележ b по коалиции S (обозначение ), если Первое условие означает, что дележ a лучше дележа b для всех членов коалиции, а второе отражает реализуемость дележа a коалицией S.

б) Дележ a доминирует дележb, если существует коалиция S, для которой . Доминирование дележа b дележом a обозначается .

Кооперативные игры можно объединять в классы, например в классы эквивалентных игр.

Определение. Кооперативная игра называется эквивалентнойигре , если существует положительное число k и п таких произвольных вещественных чисел что для любой коалиции выполняется равенство

.

Эквивалентность игры обозначается как ~ или n~n¢. Поскольку отношение эквивалентности рефлексивно, симметрично и транзитивно, оно разбивает множество всех игр п лиц на взаимонепересекающиеся классы эквивалентных игр. Приведем без доказательства теорему: если две игры n и n¢ эквивалентны, то отображение a®a¢, где

,

устанавливает взаимно однозначное соответствие множества всех дележей игры n на множество дележей игры n¢.

При разбиении множества кооперативных игр на попарно непересекающиеся классы эквивалентности возникает задача выбора наиболее простых представителей из каждого класса.

Определение. Игра называется игрой в (0 – 1)- редуцированной форме, если для всех

.

Теорема. Каждая существенная кооперативная игра эквивалентна некоторой игре в (0 – 1)-редуцированной форме

Доказательство. Пусть

Тогда Теорема доказана.

Из теоремы следует, что свойства игр, включающие понятие доминирования, можно изучать на играх в (0 – 1)-редуцированной форме. Если n есть характеристическая функция произвольной существенной игры, то

есть (0 –1) – нормализация, соответствующая функции n.

Каковы же принципы оптимального распределения максимального суммарного выигрыша между игроками? Возможен следующий подход. Пусть игроки пришли к такому соглашению о распределении выигрыша всей коалиции (дележу a*), при котором ни один из дележей не доминирует a*. Тогда такое распределение устойчиво в том смысле, что ни одной из коалиций невыгодно отделиться от других игроков и распределить между членами коалиции выигрыш n(S).Это значит, что необходимо рассмотреть множество недоминируемых дележей.

Определение. Множество недоминируемых дележей кооперативной игры (N,n) называется ее С-ядром.

С-ядро характеризует следующая теорема: для того, чтобы дележ a принадлежал С-ядру, необходимо и достаточно выполнение для всех SÌN неравенства

.

(Доказательство можно найти в литературе). Из последнего соотношения следует, что если дележ принадлежит С-ядру, то ни одна коалиция не может гарантировать себе выигрыш, превосходящий суммарный выигрыш. Это делает нецелесообразным существование коалиций, отличных от максимальной коалиции N. Теорема дает основания для использования С-ядра как важного принципа оптимальности в кооперативной теории.

Другим принципом оптимальности в кооперативных играх является Н-М-решение, которое также является множественным принципом оптимальности в множестве всех дележей

Существуют различные способы дележа, предложенные для игр с n участниками. Один из них - значения Шепли[2]. 1953 г. Шепли ввел понятие вектора значений j[v] = (j₁,...,j_n) для кооперативной игры v(S) с множеством игроков N={1, 2, ..., n}, SÌN. Эти значения, введенные аксиоматическим путем, могут быть интерпретированы как математическое ожидание взноса игрока i в выигрыш всеобщей коалиции v(N), в предположении, что все упорядочения игроков являются равновероятными.

Согласно теореме Шепли значение, определенное выше, является единственной функцией, удовлетворяющей следующей системе аксиом:

S1: Симметричность. Пусть p есть перестановка игроков, такая что p(i) есть образ игрока i. Тогда значение Шепли игрока p(i) во вновь полученной игре равно значению Шепли для игрока i в исходной игре.

S2: Линейность. Пусть игра g есть сумма двух игр v и w. Тогда значения Шепли в игре v+w есть сумма значений Шепли в играх v и w.

S3: Эффективность или нормализация. Сумма значений Шепли для всех игроков равна выигрышу всеобщей коалиции v(N)

Значения Шепли - это вектор дележа, т.е. способ (справедливого) распределения суммарного выигрыша v(N) полной коалиции игроков такой, что каждый игрок i получает величину j_i (значение Шепли).

Одна из возможных интерпретаций значений Шепли состоит в следующем. Предположим, имеется произвольный порядок игроков, заданный перестановкой p на множестве N, где p(i) есть позиция игрока i (например, если n=5 и порядок игроков есть 5, 2, 4, 3, 1, то p(5)=1, p(2)=2, p(4)=3, p(3)=4, p(1)=5), и пусть игроки входят в комнату в этом порядке. В определенный момент игроки в комнате формируют коалицию S с выигрышем v(S). Каждый входящий в комнату игрок i увеличивает коалицию b(i) игроков, вошедших до него, и увеличивает ее выигрыш за счет своего участия на величину

Данная величина не является постоянной, она зависит от того, сколько и каких именно игроков вошло в комнату до i. Если рассмотреть все мыслимые перестановки из n игроков (их всего n!) с учетом вероятностей их возникновения и подсчитать взнос игрока i в каждом случае, то можно вычислить математической ожидание, то есть некий среднестатистический взнос игрока i. Это и будет его значением Шепли. Обычно все перестановки игроков принимаются равновероятными, тогда значение Шепли j_i для игрока i есть:

где суммирование производится по всем перестановкам игроков.

Более подробной формулой для значения Шепли игрока i является:

(4.3)

где n и t - числа игроков в коалициях N и T соответственно.

Простая игра есть кооперативная игра, в которой выигрыш v(S)любой коалиции S есть либо 0, либо 1. Простую игру можно представить как систему принятия решений (например, голосование в парламенте): коалиция S может быть либо достаточной для прохождения решения (тогда v(S) = 1, и в этом случае она - выигрывающая коалиция) или нет (тогда v(S) = 0, и в этом случае она - проигрывающая коалиция). Частным примером является взвешенная мажоритарная игра, где каждый игрок i (например, партия в парламенте) имеет определенный неотрицательный вес wi(например, число мест) и имеется определенная квота q[0,1] (например, q = 1/2), определяющая общее количество голосов, необходимое для прохождения решения. То есть, если общий вес w(S) коалиции S определяется как сумма весов ее членов , то S является выигрывающей коалицией (v(S) = 1 ) при условии, что она имеет требуемое большинство голосов: , в противном случае она проигрывающая коалиция (v(S) = 0).

Наверное, первой серьезной попыткой применить методы математической теории игр для оценки политического влияния в процессе принятия решений является предложенная Шепли и Шубиком (1954) методика вычисления индексов влияния.

Рассмотрим формулу (4.3) применительно к ситуации голосовательных (простых) игр, когда характеристическая функция v(S) считается принимающей лишь два значения: 1 - для выигрывающей коалиции и 0 - для проигрывающей. Выражение в квадратных скобках из (4.3) оказывается равным нулю в случаях, когда выигрыш коалиции Т не зависит от участия в ней игрока i. Разность, стоящая в квадратных скобках, не равна нулю, только если v(Т)=1, а v(Т-{i})=0. То есть, она равна единице, только если игрок i является решающим для коалиции Т: с его участием коалиция Т побеждает, без него проигрывает. Пусть W - множество выигрывающих коалиций, а L - множество проигрывающих коалиций. Тогда формулу (4.3) можно записать как

В этом случае значение Шепли трансформируется в индекс политического влияния (Шепли-Шубика), который будучи подсчитанным для игрока i, есть отношение числа упорядочений игроков, в которых голос игрока i оказывается решающим, к общему числу таких упорядочений. Индексы Шепли-Шубика могут принимать значения в интервале между 0 и 1, а их общая сумма всегда равна 1. Если индекс игрока равен 0, он не имеет никакого влияния на процесс принятия решений (нулевой игрок или “болван”), если индекс равен 1, то данный игрок полностью контролирует процесс принятия решений ( "диктатор").

Пример 1. В качестве примера можно рассмотреть взвешенную мажоритарную игру трех игроков с весами (w₁, w₂, w₃) = (2, 1, 1) и квотой большинства q=2/3. Например, это может быть совет из 3 директоров, где первый директор имеет 2 голоса, а остальные - по 1. Для принятия решения необходимо собрать не менее 3 голосов. Будем считать, что значениями выигрыша коалиции будут числа 1 (если коалиция обладает 3 или более голосами) и 0 (если голосов меньше, чем 3). В этой игре первый игрок обладает правом вето: он является необходимым участником любой выигрывающей коалиции, но не в состоянии обеспечить прохождение решения сам по себе. Все возможные перестановки игроков (порядок, в котором они присоединяются к коалиции) выглядят следующим образом (звездочкой помечены игроки, привносящие решающий голос):

Всего имеется 3! = 6 перестановок игроков. Голос игрока 1 оказался решающим в четырех перестановках. Остальные имеют по одному решающему голосу. Таким образом, значения Шепли игроков 1, 2, 3 выражаются числами: 2/3, 1/6, 1/6. Из примера видно, что значения Шепли во взвешенных мажоритарных играх могут существенно отличаться от соответствующих весов (количества голосов), выражая реальное влияние игроков (фракций парламента) на принятие решений. В качестве меры влиятельности значения Шепли выглядят достаточно убедительно и широко применяются в прикладных исследованиях.

Важную роль в теории значений Шепли играет носитель игры. Носителемназывается такое множество игроков Т, что для любой коалиции С будет выполнено: v(С)=v(ТÇ С). В последнем примере единственный носитель игры совпадает со множеством игроков N. Если игрок не входит в какой-либо носитель, то он является нулевым игроком или “болваном” - его значение Шепли равно нулю. Содержательно это означает, что он не способен увеличить выигрыш никакой коалиции и может быть вообще исключен из рассмотрения.

Пусть, например, парламент состоит из трех фракций всегда голосующих солидарно. Первая имеет 70 голосов, вторая - 20, и третья - 10. Для принятия решений требуется либо простое большинство (50% голосов), либо квалифицированное большинство (2/3 голосов). Первая фракция обладает необходимым большинством голосов во всех случаях. Следовательно она является диктатором - обладает всей полнотой власти в парламенте. Носителями такой игры являются все коалиции, содержащие игрока 1. В частности, множество, состоящее из одного первого игрока, является носителем. Две других фракции не входят в этот носитель, а значит являются нулевыми игроками.Распределение значений Шепли в этом случае: (1, 0, 0).

Индекс Шепли-Шубика измеряет важность игрока в плане его участия в принятии или поддержке угодного ему решения. Можно поставить и двойственную задачу: выяснить какова влиятельность игрока в смысле блокирования неугодного ему решения. Оказывается, что решение этой задачи дает тот же самый результат: блокирующее влияние игрока тоже равно индексу Шепли-Шубика.

Другой тип индекса влияния (хотя и близкий по смыслу) был предложен юристом Банцхафом (1968). Идея его в том, что в голосовательной игре рассматривается множество всех минимальных выигрывающих коалиций. Минимальной выигрывающей коалицией является такая, которая при любом ее уменьшении превращается в проигрывающую. Любой участник минимальной выигрывающей коалиции является для нее важным или решающим: если он уйдет, коалиция сразу станет проигрывающей. Банцхаф предложил для каждого участника голосовательной игры подсчитывать число минимальных выигрывающих коалиций, в которые он входит. Это число характеризует политический вес игрока, зависимость от него других, и называется индексом Банцхафа. Чаще используют нормированный индекс Банцхафа:

где b_j - число минимальных выигрывающих коалиций, в которые входит игрок j.

Пример 2. Рассмотрим ту же игру, что и в примере 1, и подсчитаем для игроков индексы Банцхафа. Выпишем все минимальные выигрывающие коалиции: {1,2}, {1,3}. (Коалиция {1, 2, 3} – не является минимальной выигрывающей: удаление из нее игрока 2 (или 3) оставляет ее выигрывающей). Подсчитаем, сколько раз каждый из игроков оказывается членом минимальной выигрывающей коалиции: . Индексы Банцхафа игроков равны:

Задачи:

А) Оценить влиятельность игроков при помощи индекса Шепли-Шубика во взвешенных мажоритарных играх с квотой большинства 50% и весами игроков:

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

Б) Оценить влиятельность игроков при помощи индекса Шепли-Шубика во взвешенных мажоритарных играх 1-4 с квотой большинства 2/3.

В) Выполнить задания пунктов А) и Б) для индексов Банцхафа.

Позиционные игры