Алгоритмы и программный комплекс решения задач теории кооперативных игр. Ядерные решения дискретных кооперативных игр

• Автор: Оганян, Лев Сергеевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Ростов-на-Дону
• Количество страниц: 149 с. : ил.

ОГЛАВЛЕНИЕ
Введение.

Глава 1. Сбалансированные игры с транеферабельными полезностями.

1.1 Основные понятия кооперативной теории игр.

1.2 Сядро и условия его существования .

1.3 Значения кооперативных игр. Цена Шепли и Ыядро .

1.4 Минимальные сбалансированные покрытия

1.5 Использование специальных графов для нахождения минимальных сбалансированных покрытий.
1.6 Использование метода свертки систем линейных неравенств для нахождения минимальных сбалансированных
покрытий.
1.7 Описание методов получения некоторых классов минимальных сбалансированных покрытий.
1.8 Основные результаты, полученные в первой главе.
Глава 2. Дискретные кооперативные игры
2.1. Применение стандартного отношения доминирования для определения сбалансированности дискретных игр.
2.2. Сядро, Иядро, ССядро и соотношения между
2.3. Основные результаты, полученные во второй главе.
Глава 3. Программный комплекс решения задач кооперативной
теории
3.1. Описание работы комплекса в режиме администрирования
3.2. Описание работы комплекса в режиме тестирования и обучения
3.3. Описание работы комплекса в режиме решения задач кооперативной теории.
3.4. Выводы по третьей главе
Заключение
Библиографический список использованной литературы
Приложение 1 .
Приложение 2 .
Введение
Актуальность


Кооперативные (коалиционные) игры являются предметом исследования современного направления теории игр [],[],[]. Они моделируют такие социально-экономические явления, в которых интересы участников не являются ни строго антагонистическими, ни полностью совпадающими: рыночные отношения, управление производством, международные переговоры, работа законодательных органов и т. Например, продавец и покупатель понимают, что в их общих интересах договориться о продаже, конечно, при условии, что сделка выгодна им обоим. Однако они энергично тор! Основная идея теории кооперативных игр состоит в том, чтобы, не рассматривая переговорный процесс как таковой, анализировать возможные его исходы и делать выводы о реализуемости того или иного результата переговоров. Кооперативные игры относятся к классу непозиционных (нестратегических) игр [],[]. Кооперативной игрой в форме характеристической функции называется пара Г=, где 7У={ 1,. V - функция, ставящая в соответствие каждому подмножеству множества N вещественное число (характеристическая функция) [8],[],[]. Игра часто отождествляется с се характеристической функцией. Непустое подмножество 5* множества N называется коалицией. Коалиция N. Собственной коалицией называется коалиция, отличная от максимальной коалиции. Значение у(5) интерпретируется как максимальный выигрыш (доход) коалиции 5, который она может получить независимо от поведения других игроков. Игра Г называется также классической кооперативной игрой или игрой с побочными платежами (предполагается, что выигрыш у(8) любой коалиции 8 можно произвольно поделить между ее членами, т. И1ры с побочными платежами называются также играми с трансферабельными полезностями или ТП-играми [],[],[],[],[]. Без ограничения общности будем считать характеристическую функцию V неотрицательной, т. Игра , удовлетворяющая условию у(5)> 0, 5сЫ; у(г) = 0, /сN. Условие (1. Т после объединения получают не меньший доход, чем действуя самостоятельно. Большинство игр, возникающих в экономике, супераддитивны [],[],[]. В таких играх максимальный выигрыш у(Л0 получает коалиция всех игроков. Задача заключается в "справедливом" его распределении между участниками игры. ЕКу). Дележ можно содержательно понимать как договор между игроками о распределении получаемой ими совместно (в коалиции) суммы v(N). Условие (1. В кооперативной игре мы рассматриваем не только допустимое множество полезностей максимальной коалиции состоящей из N троков, но и множество полезностей для каждой коалиции 5с N,(5 непустое подмножество) включая коалиции, состоящие из одного игрока. Если игроки договорятся, то они могут реализовать любое распределение полезностей из этого множества. При этом игровая модель не описывает действия игроков, которые они должны произвести для достижения заданного распределения полезностей. Эти действия должны быть ясны из конкретной модели, порождающей кооперативную игру. Для кооперативной игры, при всеобщей кооперации возникает проблема выбора исхода из допустимого множества максимальной коалиции N. Понятие ядра предполагает, что коалиционные множества полезностей, рассматриваются как возможные затраты от кооперации с остальными троками. Ядро предполагает защиту прав одновременно всех игроков, это происходит за счет того, что ни одна коалиция игроков не имеет такого допустимого вектора полезностей, который был бы для нее предпочтительнее результата от всеобщей кооперации игроков. Участники супераддитивной кооперативной игры, руководствуясь некоторым принципом справедливости, должны договориться о том, каким образом лучше поделить общий доход v(Лг) (например, акционеры договариваются о дележе прибыли компании пропорционально количеству акций имеющихся у каждого игрока). Принципов справедливости много, всякое общество пытается обосновать справедливость своей системы распределения. С другой стороны, принципу оптимальности может удовлетворять множество дележей. Такая "множественность" не является недостатком теории, а необходимым свойством кооперативной шры т.