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

| Категория реферата: Рефераты по математике
| Теги реферата: шпаргалки по государству и праву, скачать бесплатно шпоры
| Добавил(а) на сайт: Янишпольский.

Предыдущая страница реферата | 1 2 3 4 | Следующая страница реферата

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

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

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

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

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

где k - целое,

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

(3)

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

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

Claw.ru | Рефераты по математике | Решение одного класса игр на матроидах

(4)

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

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

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

Пусть - матроид разбиения, .