Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Решение одного класса игр на матроидах
Раздел: Рефераты по математике
Тип: статья Добавлен 19:33:08 24 марта 2007 Похожие работы
Просмотров: 112 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

В.П. Ильев, И.Б. Парфенова, Омский государственный университет, кафедра прикладной и вычислительной математики

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

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

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

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

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

где k - целое,

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

(3)

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

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

(4)

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

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

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

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

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

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений21:58:48 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
14:55:29 24 ноября 2015

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

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(151281)
Комментарии (1843)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru