Введение к работе
Актуальность темы
Актуальность изучения кооперативных игр обусловлена их универсальностью и простотой, а также возможностью широкого применения для анализа неантагонистических конфликтных ситуаций, возникающих в экономике, социологии, политике и других областях.
Большой вклад в развитие теории кооперативных игр внесли Фон Нейман Дж., Моргенштерн О., Нэш Дж., Шепли Л.С., Воробьев Н.Н., Бондарева О.Н., Мулен Э., Петросян Л.А., Яновская Е.Б. и др.
В кооперативной игре предполагается возможность перераспределения между игроками выигрыша, полученного в результате действий образованной ими коалиции. Такие игры называются играми с побочными платежами или играми с трансферабельной полезностью (ТП-играми). Выплаты выигрышей осуществляются в количествах бесконечно-делимого и свободно перераспределяемого товара (деньги, золото и т.п.).
Основным понятием теории кооперативных игр является С-ядро. Это множество таких дележей, против которых не будут возражать игроки коалиций, требуя более выгодного для себя распределения общего дохода. Для получения максимального выигрыша требуется единодушное согласие всех игроков. С-ядро может состоять из одной точки – это идеальный случай, тогда любая коалиция не имеет ни возможности, ни желания возражать против такого дележа, может совпадать с множеством всех дележей, а может и не существовать вовсе, т.е. быть пустым.
Если игра имеет непустое С-ядро, то она называется сбалансированной. Для получения явного вида условий сбалансированности при заданном количестве игроков необходимо знать все вершины соответствующего многогранника, алгоритм нахождения которого описан в работе.
Актуальной задачей является получение условий сбалансированности игр малой размерности и исключение зависимых неравенств из условий сбалансированности. Для компактного описания вершин многогранника, определяющего условия сбалансированности, используются минимальные сбалансированные покрытия и векторы их коэффициентов, что позволяет создать эффективный алгоритм расчета, реализованный в комплексе проблемно-ориентированных программ. В литературе приведены все минимальные сбалансированные покрытия для игр трех и четырех лиц. Для игры четырех лиц наборы минимальных сбалансированных покрытий, приведенные в работах Бондаревой О.Н. и Мулена Э., не совпадают. Общего описания минимальных сбалансированных покрытий игры n лиц в литературе пока нет.
Классические кооперативные игры не охватывают конфликты, в которых разыгрываются неделимые виды ресурсов, в связи с чем актуально изучение дискретных кооперативных игр. В диссертационной работе разработаны и исследованы новые свойства и взаимосвязи между множествами, характеризующими дискретные игры (С-ядром, D-ядром, СС-ядром и множеством Вебера), получены достаточные условия непустоты С-ядра дискретной игры.
Актуальной также является задача создания программного комплекса, ориентированного на решение задач кооперативной теории игр, с помощью которого можно вычислять минимальные сбалансированные покрытия, существенные минимальные сбалансированные покрытия, проверять супераддитивность, сбалансированность, двойственную сбалансированность игр, вычислять вектор Шепли, N-ядро, обобщенное N-ядро, вершины С-ядра и двойственного С-ядра и другие множества, связанные с кооперативной игрой. Комплекс должен включать блоки администрирования, тестирования и обучения студентов, изучающих теорию кооперативных игр, позволять студентам самостоятельно изучать теоретические материалы и готовиться к тестированию, а также позволять преподавателю создавать и редактировать тестовые задания контрольных работ для студентов.
Цель работы состоит в получении условий сбалансированности игр малой размерности; в определении новых свойств множества дележей, множества двойственных дележей, множества Вебера и СС-ядра дискретных кооперативных игр, а также соотношений между ними, выводе достаточных условий непустоты С-ядра дискретной игры; создании на основе проведенных теоретических исследований программного комплекса, позволяющего не только решать задачи кооперативной теории игр, но и обучать студентов и тестировать степень усвоения изученного материала.
Для достижения этих целей в работе решены следующие задачи:
1. Получены существенные минимальные сбалансированные покрытия для игр малой размерности и их коэффициенты. Выведены условия, позволяющие получать некоторые классы минимальных сбалансированных покрытий и их коэффициенты для игр n лиц.
2. Доказана неприемлемость непосредственного применения стандартного отношения доминирования для определения сбалансированности дискретных игр.
3. Разработаны и исследованы дополнительные свойства таких математических объектов как: множество дележей, множество двойственных дележей, множество Вебера и СС-ядро целочисленной игры, которые используются при моделировании социально-экономических и других процессов. Получены необходимые и достаточные условия непустоты множества дележей, множества двойственных дележей, множества Вебера и СС-ядра дискретной игры, а также соотношения между этими множествами.
4. Выведены достаточные условия непустоты С-ядра дискретной игры.
5. Разработанные алгоритмы реализованы в виде блоков комплекса проблемно-ориентированных программ, позволяющих вычислять минимальные сбалансированные покрытия, существенные минимальные сбалансированные покрытия, проверять супераддитивность, сбалансированность, двойственную сбалансированность игр, вычислять вектор Шепли, N-ядро, обобщенное N-ядро, вершины С-ядра и двойственного С-ядра и другие множества, связанные с кооперативной игрой.
6. Создано три интерфейса программного комплекса, позволяющих преподавателю, студенту или иному пользователю, получать доступ к необходимым материалам в понятном и удобном виде.
Методы диссертационного исследования основываются на применении аппаратов теории игр и исследования операций, теории многогранников, теории графов.
Научная новизна работы состоит в следующих результатах:
1. Получены все существенные минимальные сбалансированные покрытия для игр трех, четырех и пяти лиц, а также их коэффициенты. Доказаны утверждения, позволяющие получать некоторые классы минимальных сбалансированных покрытий и их коэффициенты для игр n лиц.
2. Выведены необходимые и достаточные условия непустоты множества дележей, множества двойственных дележей, множества Вебера и СС-ядра дискретной игры, а также исследованы соотношения между этими множествами.
3. Разработаны и исследованы дополнительные свойства таких математических объектов как множество дележей, множество двойственных дележей, множество Вебера и СС-ядро целочисленной игры.
4. Получены достаточные условия непустоты С-ядра дискретной игры.
5. Разработан программный комплекс, позволяющий решать основные задачи теории кооперативных игр.
Практическая ценность работы состоит в том, что полученные результаты можно использовать для генерирования данных при вычислительном тестировании, проверке научных гипотез, составлении практически неограниченного количества различных учебных заданий, что актуально при дистанционном обучении студентов и контроле их знаний, а также для вывода достаточных условий сбалансированности кооперативной игры, вычисления N-ядра игр малой размерности, формирования характеристических функций игр с пустым и непустым С-ядром и других целей. Результаты, связанные со сбалансированными покрытиями, могут быть использованы при доказательстве некоторых утверждений и теорем кооперативной теории игр. Доказанные положения позволяют решать задачи, связанные с конфликтными ситуациями, в которых распределяется полезность неделимого типа: дискретные варианты игр банкротства, игр большого босса (в частности, холдинговых игр), клановых кооперативных игр, игр двухстороннего рынка, игр, связанных с телекоммуникационными потоками, и т.д., что служит развитию методов анализа игровых моделей задач исследования операций.
Большая часть полученных теоретических результатов, была использована при разработке программного комплекса для решения задач кооперативной теории игр, который уже используется в учебном процессе факультета математики механики и компьютерных наук Южного федерального университета.
Апробация работы. Основные положения диссертации докладывались на второй международной конференции «Математическое моделирование социальной и экономической динамики» (г. Москва, 2007 г.); на всероссийском симпозиуме «Математические модели и информационные технологии в экономике» (г. Кисловодск, 2007 г.); на конференции «Современные информационные технологии в образовании: Южный Федеральный Округ» (г. Ростов-на-Дону, 2007 г.); на XVI международной конференции «Математика. Экономика. Образование» (г. Ростов-на-Дону, 2008 г.); на всероссийской конференции «Современные проблемы прикладной математики и математического моделирования» (г. Воронеж, 2007 г.),; на всероссийской научно-практической конференции «Современная математика и проблемы математического образования» (г. Орел, 2009 г.); на третьей международной конференции «Теория игр и менеджмент» (г. Санкт-Петербург, 2009 г.); на Х всероссийском симпозиуме по прикладной и промышленной математике (г.Сочи, 2009 г.).
Публикации. По материалам диссертации опубликовано 11 печатных работ общим объемом 2.5 п.л., из них 3 – в изданиях, рекомендованных ВАК.
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, двух приложений и списка литературы. Объем диссертационной работы 146 страниц. Библиографический список содержит 99 наименований.
