Тема: Модели формирования коалиций

Теория игр - это математическая дисциплина, в которой изучаются ситуации столкно­вения интересов, их свойства и особенности, и разрабатываются методы оптимального в том или ином смысле поведения игроков в таких ситуациях. Кооперативной называется игра, в которой группы игроков - коалиции - могут объединять свои усилия.
Люди часто объединяются в группы из соображений личной выгоды. Например, когда они организуют фирму с целью производства каких-то товаров, или клуб по ин­тересам. В таких ситуациях каждый индивид имеет личные предпочтения относитель­но того, какой группе он хочет принадлежать. Обычно его интересует размер группы, другие входящие в нее индивиды и то чем группа занимается. Подобные ситуации неод­нократно анализировались в рамках теории кооперативных игр.
В 1962 году Дэвид Гейл и Ллойд Шепли сформулировали задачу распределения сту­дентов по колледжам [8]. Она заключается в том, чтобы каждого студента из заданного множества определить в один из нескольких колледжей, если известны предпочтения студентов среди колледжей и колледжей среди студентов с учетом того, что каждый колледж может принять ограниченное число абитуриентов и каждый абитуриент мо­жет попасть только в один колледж. При рассмотрении этой задачи Гейл и Шепли ввели понятия устойчивого и неустойчивого разбиения, а также рассмотрели задачу «об устойчивом браке».
Игры, в которых задача каждого игрока - попасть в наиболее приятную для себя коалицию, называются гедонистическими [7]. Они были определены в самостоятельный класс игр Жаком Дзеном и Джозефом Гринбергом в 1980 году. Такое название было вы­брано не случайно. Гедонизм(греч. hedone-наслаждение) - это этико-психологическое учение, возникшее в античности, утверждающее, что наслаждение является высшим благом, целью личности, критерием истинности и целесообразности, основным моти­вом ее поведения [20].
За последние 30 лет гедонистические игры стали объектом изучения многих уче­ных. Наиболее практически-значимые результаты были получены в работах Элвина Рота, сумевшего связать задачу о поиске устойчивого паросочетания с теорией коали­ционных игр. В США при его участии были изменены многие общественные механизмы распределения, в том числе механизмы распределения интернов по больницам, систе­ма распределения учащихся по школам округов Нью-Йорк и Бостон. Помимо этого, Э.Рот совместно с Тайфуном Сомезом построили научный фундамент системы обмена донорскими органами. В 2012 году Ллойд Шепли и Элвин Рот были удостоены Нобелев­ской премии по экономике «за теорию устойчивого распределения и практики дизайна рынка».
Целью данной работы является изучение принципов устойчивости для коалиционных структур в гедонистических играх с использованием практических примеров. На сегодняшний день, не существует материалов на русском языке по теории гедонисти­ческих игр. В качестве основы для исследования была взята обзорная работа [2].
В первой главе приведены основные понятия, связанные с гедонистическими играми, и разобраны поясняющие примеры.
Вторая глава посвящена задаче «об устойчивом браке» [8], поставленной Гейлом и Шепли в 1962 году - приведена ее формулировка, а также алгоритм решения и прак­тические примеры реализации этого алгоритма.
Далее рассмотрены игры с различными принципами формирования предпочтений.
В третьей главе рассказывается о гедонистических играх с аддитивно-сепарабельными предпочтениями. Для симметричной аддитивно-сепарабельной игры объясняется спо­соб нахождения устойчивого по Нэшу решения, приведенный в работе Анны Богомоль­ной и Мэттью Джексона [4], приводятся примеры нахождения таких решений.
В четвертой главе разобран алгоритм нахождения решения из ядра, для игр с общим порядком предпочтений, созданный Варутом Саксомпонгом [14].
Пятая глава рассказывает о B, W и TOP -играх. Помимо основных определений, взятых из [2], в ней выводится взаимосвязь между этими видами игр. Приводится ал­горитм «Тор covering», который находит разбиения из ядра для TOP-игр [1], а также доказательство его корректности [5].
Алгоритм «Тор covering» был реализован на языке C#. Текст программы приведен в приложении.
Купить

В работе были изучены принципы устойчивости для коалиционных структур в гедони­стических играх, предъявлены и продемонстрированы с помощью примеров некоторые модели игр, для которых есть алгоритм нахождения устойчивого решения.
Изучив уже опубликованные исследования в области теории гедонистических игр, приходится сделать вывод, что она разработана не достаточно широко. Обзорная ста­тья, послужившая основой для данной работы, ссылается на более чем пятьдесят ис­точников, но большинство из них являются пересказом друг друга. Известно очень мало моделей игр, для которых существует разбиение, обладающее достаточно силь­ной устойчивостью. Хочется верить, что новые исследования в этой области принесут практически-важные результаты.
Купить