Решение одного класса игр на матроидах В.П. Ильев, И.Б. Парфенова, Омский государственный университет, кафедра прикладной и вычислительной математики 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)-игра может быть рассмотрена, как игра на матроиде специального вида. ............