Рефетека.ру / Математика

Статья: Решение одного класса игр на матроидах

В.П. Ильев, И.Б. Парфенова, Омский государственный университет, кафедра прикладной и вычислительной математики

1. Коалиционные игры

Игра есть математическая модель конфликта.Нас будут интересовать только такие конфликты, в которых допускается неограниченная кооперация его участников, вплоть до образования коалиций - устойчивых союзов для согласования действий в процессе выбора окончательного решения (исхода конфликта). Типичными примерами конфликтов являются выборы и законодательные процедуры.

Дж.фон Нейман и О.Моргенштерн [1] предложили следующую модель, наиболее адекватно отражающую кооперативную сущность подобных конфликтов.

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

Решение одного класса игр на матроидах

(1)

 

Подмножества Решение одного класса игр на матроидахназываются коалициями.

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

Игрой в (0,1)-редуцированной форме (или в (0,1)-форме) называется игра, для которой v(N)=1 и Решение одного класса игр на матроидах. Игра в (0,1)-форме называется простой, если Решение одного класса игр на матроидахлибо v(S)=0, либо v(S)=1. Простая игра характерна тем, что в ней любая коалиция является либо проигрывающей (если v(S)=0), либо выигрывающей (если v(S)=1).

Примером простой игры является введенная Р.Боттом [2] и исследованная Д.Джиллисом [3] мажоритарная игра, названная ими (n,k)-игрой. Она определяется условием

Решение одного класса игр на матроидах

(2)

 

где k - фиксированное целое число, Решение одного класса игр на матроидах.

В форме таких игр достаточно адекватно представляются различные модели голосования. Например, правилу простого большинства соответствует случай k=n/2, а правилу "двух третей" - квалифицированного большинства - случай k=2n/3.

Дележом в игре n лиц с характеристической функцией v называется вектор Решение одного класса игр на матроидах, удовлетворяющий условиям:  Решение одного класса игр на матроидах Множество всех дележей в игре v обозначим I.

Для простой игры n лиц множество дележей определяется условиями:

Решение одного класса игр на матроидахНа множестве всех дележей введем отношение предпочтения.

Дележ x доминирует дележ Решение одного класса игр на матроидах, если найдется такая коалиция Решение одного класса игр на матроидах, что  Решение одного класса игр на матроидах

Легко видеть, что в простых играх доминирование возможно только по выигрывающим коалициям.

Дадим определение решения коалиционной игры n лиц по фон Нейману - Моргенштерну.

Множество дележей L называется внутренне устойчивым, если никакие два дележа из L не доминируют друг друга. Множество Решение одного класса игр на матроидахназывается внешне устойчивым, если Решение одного класса игр на матроидах. Множество дележей L называется NM-решением, если оно внутренне и внешне устойчиво.

В общем случае (для произвольной игры) задача нахождения NM-решения, а тем более всех NM-решений является очень трудной. К настоящему времени NM-решения найдены только для некоторых отдельных классов игр (подробнее см. обзор [4]).

Даже сравнительно простые игры могут иметь очень много NM-решений. Например, Р.Ботт [2] описал все симметричные решения (n,k)-игр, а Д.Джиллис [3] нашел огромное число разнообразных несимметричных решений таких игр.

Далее мы покажем, что любая (n,k)-игра может быть рассмотрена, как игра на матроиде специального вида. Рассмотрим другой класс игр на матроидах, являющийся обобщением (n,k)-игр, и опишем NM-решения игр этого класса.

2. Решения игр на матроидах разбиений

Пусть Решение одного класса игр на матроидах- конечное множество, Решение одного класса игр на матроидах- семейство его подмножеств, обладающее следующими свойствами:  Решение одного класса игр на матроидах Решение одного класса игр на матроидах Тогда пара Решение одного класса игр на матроидахназывается матроидом. Множества семейства Решение одного класса игр на матроидахназываются независимыми множествами матроида M. Матроид называется дискретным, если Решение одного класса игр на матроидах.

Важным классом матроидов являются так называемые матроиды разбиений. Рассмотрим какое-либо разбиение множества N, то есть Решение одного класса игр на матроидахдля Решение одного класса игр на матроидахЗаданы целые числа Решение одного класса игр на матроидахЛегко видеть, что тогда семейство

Решение одного класса игр на матроидах является семейством независимых множеств некоторого матроида. Этот матроид называется матроидом разбиения. Частным случаем матроида разбиения является (k-1)-однородный матроид (при p=1), семейство независимых множеств которого определяется как

Решение одного класса игр на матроидах где k - целое, Решение одного класса игр на матроидах

С любым матроидом Решение одного класса игр на матроидах, отличным от дискретного, мы можем связать простую коалиционную игру n лиц, определив ее характеристическую функцию следующим образом:

Решение одного класса игр на матроидах

(3)

 

Такую игру будем называть игрой на матроиде.

Характеристическая функция игры на матроиде разбиения имеет вид:

Решение одного класса игр на матроидах

(4)

 

Эту игру можно рассматривать как обобщение мажоритарной (n,k)-игры. Сама же (n,k)-игра является игрой на (k-1)-однородном матроиде.

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

NM-решение игры на матроиде разбиения будем строить, исходя из NM-решений (уже изученных Боттом и Джиллисом) игр на соответствующих (k-1)-однородных матроидах.

Пусть Решение одного класса игр на матроидах- матроид разбиения, Решение одного класса игр на матроидах.

Рассмотрим коалиционную игру (4) на матроиде разбиения M, а также для всех j рассмотрим мажоритарные (nj,kj)-игры

Решение одного класса игр на матроидах

(5)

 

Фиксируем вектор Решение одного класса игр на матроидахтакой, что

Решение одного класса игр на матроидах

(6)

 

Теорема. Пусть Решение одного класса игр на матроидах- какие-то NM-решения (nj,kj)-игр Решение одного класса игр на матроидах. Тогда для любого Решение одного класса игр на матроидах, удовлетворяющего (6), множество

Решение одного класса игр на матроидах

(7)

 

является NM-решением коалиционной игры (4) на матроиде разбиения M.

Очевидно, что векторы вида Решение одного класса игр на матроидах, где Решение одного класса игр на матроидах, являются дележами в игре (4).

Доказательство

1.Внутренняя устойчивость. Предположим, что в L найдутся такие дележи

Решение одного класса игр на матроидах, что Решение одного класса игр на матроидахпо некоторой выигрывающей коалиции Решение одного класса игр на матроидах. Тогда Решение одного класса игр на матроидах- выигрывающая коалиция в игре vj и Решение одного класса игр на матроидахпо коалиции Решение одного класса игр на матроидах. Это противоречит внутренней устойчивости множества Lj.

2. Внешняя устойчивость. Рассмотрим произвольный делeж Решение одного класса игр на матроидахДокажем, что найдется такой делeж Решение одного класса игр на матроидах, что Решение одного класса игр на матроидахЗаметим, что если бы Решение одного класса игр на матроидахто Решение одного класса игр на матроидах, и y не был бы дележом. Поэтому Решение одного класса игр на матроидахБез ограничения общности можно считать, что Решение одного класса игр на матроидахВозможны 2 случая:

Случай 1. Решение одного класса игр на матроидахРассмотрим вектор yj с компонентами вида Решение одного класса игр на матроидах. Тогда Решение одного класса игр на матроидахто есть yj - дележ в игре vj.

Если при этом окажется, что Решение одного класса игр на матроидахто сменим j (то есть рассмотрим другой номер j, для которого Решение одного класса игр на матроидах. Такой обязательно существует, так как в противном случае Решение одного класса игр на матроидах. Не может быть также, чтобы Решение одного класса игр на матроидахи Решение одного класса игр на матроидах, так как это означает, что Решение одного класса игр на матроидах). Поэтому далее будем считать,что Решение одного класса игр на матроидахТогда Решение одного класса игр на матроидахпо некоторой выигрывающей коалиции Решение одного класса игр на матроидахЗначит Решение одного класса игр на матроидахпо коалиции Sj, где Решение одного класса игр на матроидах.

Случай 2. Решение одного класса игр на матроидахРассмотрим вектор yj с компонентами вида Решение одного класса игр на матроидахЗаметим, что yj - не дележ в игре vj, так как Решение одного класса игр на матроидахРассмотрим вектор zj с компонентами Решение одного класса игр на матроидахгде Решение одного класса игр на матроидахТогда Решение одного класса игр на матроидахто есть zj - дележ в игре vj.

Если при этом окажется, что Решение одного класса игр на матроидахто Решение одного класса игр на матроидах, где xr - произвольный дележ из Решение одного класса игр на матроидахи Решение одного класса игр на матроидахпо любой выигрывающей коалиции Решение одного класса игр на матроидах. Если же Решение одного класса игр на матроидах, то Решение одного класса игр на матроидахпо некоторой выигрывающей коалиции Решение одного класса игр на матроидахНо тогда Решение одного класса игр на матроидахпо коалиции Sj, где  Решение одного класса игр на матроидах

Пример. Голосование в Совете Безопасности ООН. Совет безопасности (СБ) состоит из 11 членов, из которых 5 - "Большая пятерка" имеют право вето. Для проведения решения за него должно быть подано 7 голосов при отсутствии вето.

Рассмотрим процедуру принятия решения в СБ как коалиционную игру, игроками которой являются страны-члены СБ. Множество N всех игроков естественным образом разделяется на два непересекающихся подмножества: N1-"Большая пятерка" и Решение одного класса игр на матроидах.

Будем считать успехом отклонение рассматриваемого проекта решения (т.е. отрицательное решение вопроса). Для простоты будем считать, что члены "Большой пятерки" не воздерживаются при голосовании. Тогда коалиция S противников проекта (в число которых мы включаем и воздержавшихся при голосовании) будет выигрывающей, если Решение одного класса игр на матроидахили Решение одного класса игр на матроидах. Характеристическая функция этой игры имеет вид:

Решение одного класса игр на матроидах

Таким образом, мы имеем игру на матроиде разбиения Решение одного класса игр на матроидах, где

Решение одного класса игр на матроидах

Коэффициенты Решение одного класса игр на матроидахотносительной важности элементов разбиения Nj могут быть получены на основании экспертных оценок либо априорных оценок игры (см. вектор Шепли [4]).

Например, Шепли и Шубик [5] утверждают, что 98,7 % силы обладает "Большая пятерка", а остальным шести членам СБ вместе взятым остается лишь 1,3 %. Если согласиться с этими оценками, то в NM-решении игры на матроиде, являющейся моделью системы голосования в СБ, следует принять Решение одного класса игр на матроидах.

Список литературы

Нейман Дж. фон, Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970.

Bott R. Symmetric solutions to majority games // Annals of Mathematical Studies. Princeton: Princeton Univ. Press, 1953. Vol.28. P.319-323.

Gilles D.B. Discriminatory and bargaining solutions to a class of symmetric n-person games // Там же. P.325-342.

Соболев А.И. Кооперативные игры // Проблемы кибернетики. М.: Наука, 1982. Вып.39. С.201-222.

Shapley L.S., Shubik M. A method for evaluiting the distribution of power in a commitee system // American Political Science Review. 1954. Vol.48. P.787-792.

Рефетека ру refoteka@gmail.com