
Решение одного класса игр на матроидах
Категория реферата: Рефераты по математике
Теги реферата: шпаргалки по государству и праву, скачать бесплатно шпоры
Добавил(а) на сайт: Янишпольский.
1 2 3 4 | Следующая страница реферата
Решение одного класса игр на матроидах
В.П. Ильев, И.Б. Парфенова, Омский государственный университет, кафедра прикладной и вычислительной математики
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] нашел огромное число разнообразных несимметричных решений таких игр.
Рекомендуем скачать другие рефераты по теме: предмет культурологии, цель курсовой работы.
1 2 3 4 | Следующая страница реферата