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

Введение 2
1. Основные определения 4
1.1. Определение гедонистической игры 4
1.2. Свойства решений 5
1.3. Концепции решения основанная на групповом отклонении 6
1.4. Концепции решений основанные на одиночном отклонении игроков 7
2. Задача «об устойчивом браке» 11
3. Аддитивно-сепарабельные гедонистические игры 14
4. Игры с общим порядком предпочтений 17
5. B,W и TOP-игры 19
5.1. Определение B и W-игр 19
5.2. TOP-игры 21
5.3. Алгоритм «Top covering» 25
Заключение 30
Литература 31
Приложение 33
Купить

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