Введение
Обзор литературы
Глава 1. Кооперативная игра
1.1. Основные понятия и определения
1.2. C-ядро
1.3. Пред-N-ядро
1.4. α-N-ядро
1.5. Коалиционная устойчивость множества α-N-ядер . . . . . . . . 16
1.6. Некоторые классы игр с коалиционно устойчивыми решениями 21
Глава 2. Программная реализация
2.1. Описание вспомогательных функций
2.2. Проверка игры на выпуклость
2.3. Нахождение вершин C-ядра
2.4. Алгоритм поиска пред-N-ядра
2.5. Нахождение α-N-ядер
2.6. Проверка решений на коалиционную устойчивость
2.7. Множество α-N-ядер для игры трех лиц
Заключение
Список литературы
Приложение
Кооперативные игры — класс игр, в которых игрокам позволено
заключать союзы для увеличения потенциальных выигрышей. В играх с
трансферабельными полезностями данные выигрыши должны оцениваться в единицах, общих для всех игроков, и могут быть произвольно поделены между игроками. Способы распределения между всеми участниками игры общего выигрыша, полученного в результате кооперации, многочисленны и поэтому являются основным предметом изучения кооперативной теории. Эти способы распределения общего выигрыша называются решениями кооперативной игры. Наиболее изученными концепциями решения в кооперативной теории игр являются C-ядро (Scarf, [11]),
N-ядро (Schmeidler, [12]) и вектор Шепли (Shapley, [13]). Сравнительно недавно введены новые концепции решения, такие как SM-ядро
(Tarashnina, [15]) и множество α-N-ядер (Smirnova, Tarashnina, [5]).
Такая многочисленность решений объясняется различными наборами
свойств решений, благодаря которым каждое из решений более предпочтительно в некоторых аспектах в сравнении с другими.
В качестве меры предпочтения в данной работе исследуется принадлежность решения C-ядру, как множеству недоминируемых дележей.
Этот подход обусловлен устойчивостью решения в том смысле, что игрокам, целью которых является максимизация собственного выигрыша,
невыгодно отказываться от такого распределения из-за возможности получить меньше предложенного.
В общем случае C-ядро может содержать бесконечно много решений, а значит выбор наиболее приемлемого из них становится дополнительной проблемой. Такое решение игры как вектор Шепли позволяет построить наиболее справедливый дележ, учитывающий все возможные
вклады игроков в общую прибыль коалиций. Однако в общем случае он
может не обладать свойством коалиционной устойчивости.
На классе выпуклых игр C-ядро всегда непусто, и в таком случае
появляется возможность изучения известных решений на принадлежность C-ядру. Целью настоящей работы является исследование на коалиционную устойчивость множества α-N-ядер N (v) и разработка программных средств для нахождения данного решения. Рассматриваемое
решение учитывает как конструктивную, так и блокирующую силу коалиций. Также интересен тот факт, что при α = 1 оно совпадает с пред-Nядром, при α = 0;5 — с SM-ядром, а при α = 0 — с анти-пред-N-ядром.
В связи с этим возникает ряд задач:
• проанализировать различные концепции решения кооперативной ТП-игры;
• изучить свойство коалиционной устойчивости решений выпуклых кооперативных игр;
• разработать программный продукт для нахождения α-N-ядер в игре n лиц и их проверки на коалиционную устойчивость;
• разработать программный продукт для нахождения множества α-
N-ядер игры трех лиц с учетом его геометрической структуры.
В ходе исследования получены результаты, позволяющие определять коалиционную устойчивость точечных решений. Также рассмотрены примеры выпуклых кооперативных игр, иллюстрирующие полученные выводы.
В главе 1 даются основные понятия и определения, касающиеся
кооперативной теории игр и ее решений, сформулированы и доказаны
теоремы и определены классы игр с коалиционно устойчивыми решениями. В главе 2 приведены описания функций программной реализации
алгоритмов поиска решений и проверки выполнения условий выпуклости и коалиционной устойчивости.
В данной работе исследовано свойство коалиционной устойчивости
множества α-N-ядер в классе выпуклых кооперативных ТП-игр с конечным числом игроков. В ходе исследования изучены основные концепции
решения кооперативных игр и их взаимное расположение в пространстве
для класса выпуклых игр. На основе изученной информации были сформулированы и доказаны теоремы о пересечении множества α-N-ядер с
C-ядром не менее чем в одной точке. Результаты теорем проиллюстрированы на нескольких примерах.
В рамках данного исследования были разработаны программы на
языке программирования MATLAB, позволяющие проверять свойства
выпуклости кооперативной игры и коалиционной устойчивости ее решений, находить α-N-ядра игры для любого заданного значения α 2 R1,
анализировать коалиционную устойчивость α-N-ядер с заданным интервалом и шагом для α, создавать сводную таблицу результатов проверки.
Также был программно реализован результат теоремы, определяющий
множество α-N-ядер произвольной кооперативной игры трех лиц.
При дальнейшем исследовании коалиционной устойчивости решений кооперативной игры планируется расширить класс рассматриваемых
игр и доработать программу до нахождения всего множества α-N-ядер
игры (N; v) для всех α 2 R1 с учетом последовательной смены сбалансированных наборов на разных интервалах значения α.
