Введение 3
Постановка задачи 5
Обзор литературы 6
Глава 1. Кооперативные игры 7
1.1. Классическая кооперативная игра 7
1.2. Решения кооперативных игр 9
1.3. Свойства N-ядра и SM-ядра 11
Глава 2. Интервальные игры 13
2.1. Основные понятия интервальных игр 13
2.2. Интервальное N-ядро 15
2.3. SM-ядро для интервальных игр 17
2.4. Свойства интервальных N-ядра и SM-ядра 18
Глава 3. Программная реализация нахождения N-ядра и SM-ядра . 20
3.1. Минимальные сбалансированные коалиции 20
3.2. Усовершенствованный метод перебора 23
3.3. Метод минимизации лексикографической разницы 25
Глава 4. Примеры 28
4.1. Нахождение N-ядра 28
4.2. Нахождение SM-ядра 30
Заключение 34
Список литературы 35
Приложение 1 38
Приложение 2 42
Приложение 3 48
Современную теорию игр можно разделить на два раздела - на теорию некооперативных (бесколиционных) игр и на теорию кооперативных (коалиционных) игр. В некооперативных играх основной упор ставится на изучение стратегий, способов достижения желаемого игроками равновесного состояния. Игроки в таких играх играют каждый сам за себя.
В отличие от бесколиционных игр в кооперативных играх в первую очередь рассматриваются проблемы групп игроков. В данных играх у игроков есть возможность объединяться в коалиции для достижения большей выгоды. При этом предполагается, что если игроки создали коалицию, то коалиции известно, что необходимо сделать, чтобы гарантированно получить свой выигрыш.
Кооперативные игры также разделяются на два основных раздела - на игры с трансферабельной полезностью (ТП игры) и на игры с нетрансферабельной полезностью. Под кооперативными ТП играми, то есть играми с побочными платежами, понимаются игры, в которых полезность измеряется в универсальных, общепринятых для всех участников игры единицах и передается от игрока к игроку без потерь и трансформаций. Иные игры называются играми с нетрансферабельной полезностью.
В данной работе рассматриваются кооперативные интервальные игры с трансферабельной полезностью и их решения, основанные на эксцессах коалиций. Такие игры подходят для описания ситуаций, в которых люди или компании, рассматривающие возможность сотрудничества, не могут определить достижимые выигрыши коалиции, зная с уверенностью только их нижнюю и верхнюю границы. Кооперативные интервальные игры были введены в статьях (Branzei, Dimitrov and Tijs, 2003)[1] и в
(Branzei, Dimitrov, Pickl and Tijs, 2004)[2] в контексте ситуаций банкротства и подробнее изучены (Alparslan GOk, Branzei and Tijs, 2008, Branzei, Tijsand Alparslan GOk, 2008)[3]. Каждая интервальная игра определяется двумя классическими кооперативными играми - нижней и верхней - чьи значения характеристических функций являются границами выигрыша коалиции. Решения для интервальных игр определяются также в интервальной форме. Значение ТП игры дает значение интервала для соответствующего класса интервальных игр, если значение верхней игры преобладает над значением нижней игры.
В данной работе рассматривается новое решение кооперативных интервальных игр - SM-ядро. Впервые SM-ядро для кооперативных игр было введено в статье «The simplified modified nucleolus of a cooperative TU-games» (2011) Тарашниной С.И. [4]. Данное решение интересно тем, что учитывает конструктивную и блокирующую силы коалиции. Подробнее об этом написано в статье «Constructive and Blocking Powers in Some Applications» Тарашниной С. И., Смирновой Н. В.[6]. По этой причине данный подход рассмотрен и для интервальных кооперативных игр.
Постановка задачи
Целью данной работы является рассмотрение понятия интервальных игр, изучение алгоритма построения N-ядра и SM-ядра для кооперативных игр, интервального N-ядра для интервальных игр и построения интервального SM-ядра для интервальных игр. Для выполнения поставленных целей необходимо решить ряд задач:
1. Рассмотреть понятие интервальных игр.
2. Рассмотреть понятие интервального N-ядра и его свойства.
3. Построить интервальное SM-ядро и изучить его свойства.
4. Рассмотреть примеры нахождения N-ядра и SM-ядра для игр трех и четырех лиц.
5. Реализовать компьютерную программу для нахождения интервальных N-ядра и SM-ядра.
В данной работе были выполнены все поставленные задачи. Были изучены основные понятия и определения интервальных кооперативных игр, а так же рассмотрена теория для расширения SM-ядра на множество интервальных игр и его построение на нескольких примерах. Были изучены свойства N-ядра и SM-ядра, и некоторые из них были распространены на интервальные игры. Было также реализовано несколько методов программного нахождения N-ядра и SM-ядра на языке программирования Python.
В дальнейшем планируется изучение свойств N-ядра и SM-ядра на множестве интервальных игр, улучшение программных методов нахождения этих решений, путем переноса на другой более быстрый язык программирования и усовершенствования их алгоритмов работы.
