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

Рассмотрим коалиционную игру (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.