Учебная работа № 1174. Решение одного класса игр на матроидах
В.П. Ильев, И.Б. Парфенова, Омский государственный университет, кафедра прикладной и вычислительной математики
1. Коалиционные игры
Игра есть математическая модель конфликта.Нас будут интересовать только такие конфликты, в которых допускается неограниченная кооперация его участников, вплоть до образования коалиций устойчивых союзов для согласования действий в процессе выбора окончательного решения (исхода конфликта). Типичными примерами конфликтов являются выборы и законодательные процедуры.
Дж.фон Нейман и О.Моргенштерн [1] предложили следующую модель, наиболее адекватно отражающую кооперативную сущность подобных конфликтов.
Пусть конечное множество, элементы которого называются игроками. Характеристической функцией (или коалиционной игрой) называется функция
(1) |
Подмножества называются коалициями.
Действительное число v(S) можно интерпретировать как потенциальную силу коалиции S, то есть тот суммарный выигрыш, который гарантированно могут получить игроки из S, если объединятся в коалицию и будут действовать совместно.
Игрой в (0,1)редуцированной форме (или в (0,1)форме) называется игра, для которой v(N)=1 и
Примером простой игры является введенная Р.Боттом [2] и исследованная Д.Джиллисом [3] мажоритарная игра, названная ими (n,k)игрой. Она определяется условием
(2) |
где k фиксированное целое число,
В форме таких игр достаточно адекватно представляются различные модели голосования. Например, правилу простого большинства соответствует случай k=n/2, а правилу «двух третей» квалифицированного большинства случай k=2n/3.
Дележом в игре n лиц с характеристической функцией v называется вектор
Для простой игры n лиц множество дележей определяется условиями:
Дележ x доминирует дележ
Легко видеть, что в простых играх доминирование возможно только по выигрывающим коалициям.
Дадим определение решения коалиционной игры n лиц по фон Нейману Моргенштерну.
Множество дележей L называется внутренне устойчивым, если никакие два дележа из L не доминируют друг друга. Множество
В общем случае (для произвольной игры) задача нахождения NMрешения, а тем более всех NMрешений является очень трудной. К настоящему времени NMрешения найдены только для некоторых отдельных классов игр (подробнее см. обзор [4]).
Даже сравнительно простые игры могут иметь очень много NMрешений. Например, Р.Ботт [2] описал все симметричные решения (n,k)игр, а Д.Джиллис [3] нашел огромное число разнообразных несимметричных решений таких игр.
Далее мы покажем, что любая (n,k)игра может быть рассмотрена, как игра на матроиде специального вида. Рассмотрим другой класс игр на матроидах, являющийся обобщением (n,k)игр, и опишем NMрешения игр этого класса.
2. Решения игр на матроидах разбиений
Пусть
Важным классом матроидов являются так называемые матроиды разбиений. Рассмотрим какоелибо разбиение множества N, то есть
С любым матроидом
(3) |
Такую игру будем называть игрой на матроиде.
Характеристическая функция игры на матроиде разбиения имеет вид:
(4) |
Эту игру можно рассматривать как обобщение мажоритарной (n,k)игры. Сама же (n,k)игра является игрой на (k1)однородном матроиде.
Игру на матроиде разбиения (4) можно интерпретировать как игру с голосованием, когда голосование проводится по непересекающимся округам и выигрывающей считается коалиция, набравшая хотя бы в одном округе заданное число голосов.
NMрешение игры на матроиде разбиения будем строить, исходя из NMрешений (уже изученных Боттом и Джиллисом) игр на соответствующих (k1)однородных матроидах.
Пусть
Рассмотрим коалиционную игру (4) на матроиде разбиения M, а также для всех j рассмотрим мажоритарные (nj,kj)игры
(5) |
Фиксируем вектор
(6) |
Теорема. Пусть
(7) |
является NMрешением коалиционной игры (4) на матроиде разбиения M.
Очевидно, что векторы вида
Доказательство
1.Внутренняя устойчивость. Предположим, что в L найдутся такие дележи
2. Внешняя устойчивость. Рассмотрим произвольный делeж
Случай 1.
Если при этом окажется, что
Случай 2.
Если при этом окажется, что
Пример. Голосование в Совете Безопасности ООН. Совет безопасности (СБ) состоит из 11 членов, из которых 5 «Большая пятерка» имеют право вето. Для проведения решения за него должно быть подано 7 голосов при отсутствии вето.
Рассмотрим процедуру принятия решения в СБ как коалиционную игру, игроками которой являются странычлены СБ. Множество N всех игроков естественным образом разделяется на два непересекающихся подмножества: N1″Большая пятерка» и
Будем считать успехом отклонение рассматриваемого проекта решения (т.е. отрицательное решение вопроса). Для простоты будем считать, что члены «Большой пятерки» не воздерживаются при голосовании. Тогда коалиция S противников проекта (в число которых мы включаем и воздержавшихся при голосовании) будет выигрывающей, если
Таким образом, мы имеем игру на матроиде разбиения
Коэффициенты
Например, Шепли и Шубик [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.319323.
Gilles D.B. Discriminatory and bargaining solutions to a class of symmetric nperson games // Там же. P.325342.
Соболев А.И. Кооперативные игры // Проблемы кибернетики. М.: Наука, 1982. Вып.39. С.201222.
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.787792.