Эйн-Я Гура , Майкл Машлер - Экскурс в теорию игр : нетипичные математические сюжеты

Ein-Ya Gura
and Michael Maschler

INSIGHTS INTO
GAME THEORY
An Alternative
Mathematical Experience

Эйн-Я Гура,
Майкл Машлер

ЭКСКУРС
В ТЕОРИЮ ИГР
Нетипичные математические
сюжеты
Перевод с английского С. В. Бусыгина
Под научной редакцией В. П. Бусыгина, М. И. Левина

| Издательский дом Д Е Л О |
Москва | 2017

УДК 51-8
ББК 22.18
Г 95

Г 95

Гура, Эйн-Я, Машлер, Майкл
Экскурс в теорию игр : нетипичные математические сюжеты / Эйн-Я Гура, Майкл Машлер; пер. с англ. С. В. Бусыгина;
под науч. ред. В. П. Бусыгина, М. И. Левина. — М. : Издательский
дом «Дело» РАНХиГС, 2017. — 320 с.
ISBN 978-5-7749-1198-1
Немногие разделы математики играли более важную роль
в общественных науках, чем теория игр. В последние годы она
стала основным инструментом анализа для всех общественных наук, изучающих стратегическое поведение конкурирующих индивидов, фирм, стран. Однако математическая сложность теории игр часто сильно пугает студентов, имеющих
достаточно скромное математическое образование.
Настоящая книга решает эту проблему — знакомит учащихся
с основными концепциями и идеями теории игр, не используя формальные математические обозначения. Авторы на
основе четырех разных сюжетов (прием абитуриентов, социальная справедливость и голосование по правилу простого
большинства, проблема банкротства в Талмуде) анализируют
четыре раздела теории игр. И как результат — создают увлекательное введение в мир теории игр и ее возрастающей роли
в общественных науках.

УДК 51-8
ББК 22.18
ISBN 978-5-7749-1198-1

Insights into Game Theory
© Ein-Ya Gura and Michael B. Maschler 2008
Syndicate of the Press of the University of Cambridge 2008
© ФГБОУ ВО «Российская академия народного хозяйства и государственной службы при Президенте Российской Федерации», 2017

Эта книга посвящается
памяти Майкла Машлера
(22.07.1927–20.07.2008)

Оглавление

Предисловие к русскому изданию . 11
Предисловие . 12
Введение . 13
1. Математика паросочетаний . 17
1.1. Вступление . 17
1.2. Задача о паросочетаниях . 18
1.3. Упражнения . 25
1.4. Дополнительные примеры . 28
1.5. Упражнения . 34
1.6. Процедура нахождения устойчивой
системы паросочетаний
(алгоритм Гейла — Шепли) . 35
1.7. Упражнения . 39
1.8. Устойчивая система паросочетаний
всегда существует . 40
1.9. Максимальное количество стадий
в алгоритме Гейла — Шепли . 43
1.10. Обобщение . 49
1.11. Упражнения . 58
1.12. Алгоритм Гейла — Шепли и задача
о приеме абитуриентов . 63

7

1.13. Упражнения . 67
1.14. Оптимальность . 70
1.15. Упражнения . 79
1.16. Условие существования единственной
устойчивой системы паросочетаний . 82
1.17. Упражнения . 85
1.18. Обсуждение . 87
1.19. Упражнения на повторение . 88

2. Социальная справедливость . 93
2.1. Постановка задачи . 93
2.2. Математическое описание задачи . 97
2.3. Упражнения . 100
2.4. Функция общественного выбора . 103
2.5. Аксиомы для функции общественного
выбора . 116
2.6. Упражнения . 120
2.7. Что следует из аксиом 1–4? . 122
2.8. Упражнения . 128
2.9. Теорема Эрроу . 129
2.10. Что делать? . 136
2.11. Упражнения на повторение . 138

3. Вектор Шепли в кооперативных играх . 143
3.1. Введение . 143
3.2. Кооперативные игры . 144
3.3. Важные примеры коалиционных игр . 148
3.4. Упражнения . 153
3.5. Аддитивные игры . 154
3.6. Супераддитивные игры . 154
3.7. Мажоритарные игры . 156
3.8. Упражнения . 161

8

3.9. Симметричные игроки . 162
3.10. Упражнения . 164
3.11. Болваны . 165
3.12. Упражнения . 166
3.13. Сумма игр . 167
3.14. Упражнения . 171
3.15. Вектор Шепли . 174
3.16. Упражнения . 184
3.17. Ликвидация партнерства . 185
3.18. Упражнения . 195
3.19. Вектор Шепли как средний предельный
вклад . 197
3.20. Упражнения . 201
3.21. Вектор Шепли как индекс влияния
во взвешенной мажоритарной игре . 203
3.22. Упражнения . 210
3.23. Индекс Шепли — Шубика в анализе
влияния партий в парламенте . 210
3.24. Упражнения . 214
3.25. Совет Безопасности ООН . 215
3.26. Упражнения . 217
3.27. Игры с распределением затрат . 217
3.28. Упражнения . 222
3.29. Упражнения на повторение . 224

4. Анализ задачи о банкротстве
из Талмуда . 227
4.1. Введение . 227
4.2. Спор об одежде . 230
4.3. Упражнения . 233
4.4. Физическая интерпретация спора
об одежде . 235
4.5. Упражнения . 240

9

4.6. Задача о банкротстве из Талмуда . 241
4.7. Упражнения . 245
4.8. Существование и единственность
решения . 247
4.9. Дележ по принципу спора об одежде . 252
4.10. Упражнения . 258
4.11. Совместимость . 260
4.12. Упражнения . 261
4.13. Закон деления Рифа . 262
4.14. Упражнения . 264
4.15. Пропорциональный дележ . 265
4.16. Правило дележа О’Нейла . 267
4.17. --">