Содержание к диссертации
Введение
1 Введение 6
1.1 Описание изучаемой проблемы 6
1.1.1 Постановка задачи: формальная модель 6
1.1.2 На стыке дисциплин 9
1.1.3 Фундаментальный конфликт, изучаемый в работе, и несколько его конкретных воплощений 10
1.1.4 Постулат Тьебу и принцип медианного избирателя: плодотворный союз 13
1.2 Абстрактная реализация конфликта: UFLP и ЗМР 16
1.2.1 Постановка задачи UFLP и переход к ЗМР 17
1.2.2 Конкретная реализация ЗМР: география, вкусы и взгляды 19
1.2.3 Подробнее о поставке клубных благ 21
1.2.4 Две трактовки задачи: дробная и неделимая 22
1.2.5 Странообразование (модель Алесины и Сполаоре) . 25
1.2.6 Первичная формализация теоретико-игровых угроз . 26
1.3 Обзор полученных в работе результатов 29
1.3.1 Краткое содержание следующих глав работы 29
1.3.2 Основные результаты диссертационного исследования . 33
1.4 Обзор литературы по смежным направлениям 36
1.4.1 Вокруг UFLP: дробная релаксация и зазор устойчивости 36
1.4.2 Обзор других родственных теорий и областей науки . 40
1.4.3 Результаты, непосредственно примыкающие к полученным в диссертационном исследовании 46
2 Случай F: дискретная (конечная) задача многомерного размещения 53
2.1 Постановка задачи в конечном случае 55
2.1.1 Пояснения, термины и обозначения 55
2.1.2 Переформулировка задачи 58
2.1.3 Лемма о медиане 61
2.2 Теоретико-игровые угрозы миграционной природы в задаче ЗМР (постановка F) 62
2.2.1 Об угрозах: вступление 62
2.2.2 Три механизма распределения издержек: S,R,E . 64
2.2.3 Случай F при d = 1: интервальные разбиения 67
2.2.4 Концепция миграционной устойчивости решения 69
2.3 Миграционные угрозы в задаче ЗМР (постановка F): устойчивых решений может не существовать 72
2.3.1 Контрпример, случай FRM 73
2.3.2 Теорема об интервальности, случай FEM 77
2.3.3 Контрпример, случай FEFM (центральная медиана) . 79
2.4 Миграционные угрозы в задаче ЗМР (постановка F): две теоремы существования 81
2.4.1 Случай FEFM, равномерное расселение 81
2.4.2 Случай FEMM (принцип минимального насилия) . 89
3 Случай F, продолжение: коалиционные угрозы 95
3.1 Теоретико-игровые угрозы коалиционной природы 95
3.1.1 Исторический экскурс: в погоне за устойчивостью на
3.1.2 Ядро в форме разбиения на коалиции 98
3.1.3 Случай FRC: универсальная теорема существования . 100
3.1.4 Случай FSC: основные определения и пояснения . 103
3.1.5 Случай FSC: дробная релаксация задачи и концепция
3.2 Случай FEC: универсальный контрпример 109
3.2.1 Анализ случая FEMC для d = 1 110
3.2.2 Контрпример для FEFC (“центральная медиана”), свойства интервальности и обзор мелких фактов 112
3.2.3 Случай FEAC , или “самая общая теорема” пустоты ядра114
4 Случай D:непрерывные расселения 127
4.1 Постановка задачи многомерного размещения для случая непрерывного расселения 128
4.1.1 Пререквизиты для ЗМР в случае D 128
4.1.2 Формализация ЗМР 130
4.1.3 Принципы распределения издержек 131
4.2 Миграционная устойчивость (анализ постановки DM ) 134
4.2.1 Концепция MG, или “абстрактная миграционная устойчивость”135
4.2.2 Метрические постановки и усиленная миграционная устойчивость 138
4.2.3 Определения для случаев DRM и DEM 141
4.2.4 Анализ случая DEM для равномерного расселения на прямой 141
4.3 Миграционные равновесия на отрезке с произвольным расселением: общая теорема существования 142
4.3.1 Постановка задачи на отрезке: ЗМР с фиксированным числом групп 142
4.3.2 ЗМР: миграционная устойчивость 144
4.3.3 Доказательство основной теоремы 147
4.3.4 Сравнение равновесного и оптимального решений 150
4.4 Коалиционная устойчивость (анализ постановок DSC и DEC ) 150
4.4.1 Равномерное распределение на плоскости: 0.018-устойчивость152
5 СлучайT:“несколько городов” 158
5.1 Введение в T -сценарий: терминология, постановка ЗМР и основные определения теоретико-игровой устойчивости 160
5.1.1 Постановка задачи: напоминание 160
5.1.2 Задача многомерного размещения: T -случай 162
5.1.3 Переформулировка задачи 163
5.1.4 Коалиционная и миграционная устойчивость в T -сценарии 166
5.2 Анализ коалиционной устойчивости “биполярного мира” 170
5.2.1 Обозначения и нормализация параметров 171
5.2.2 Подготовительная работа и решение ЗМР 172
5.2.3 Коалиционная устойчивость: первичный анализ 173
5.2.4 Промежуточный результат 178
5.3 Окончание анализа и графическое представление его результатов184
5.3.1 Устойчивые разбиения при равной численности городов 185
5.3.2 Условия устойчивости союза и федерации при a > b 186
5.3.3 Устойчивость “дробного” разбиения 189
6 Заключение 200
6.0.4 Метрическое X 202
Литература 207
- Фундаментальный конфликт, изучаемый в работе, и несколько его конкретных воплощений
- Теоретико-игровые угрозы миграционной природы в задаче ЗМР (постановка F)
- Ядро в форме разбиения на коалиции
- Миграционные равновесия на отрезке с произвольным расселением: общая теорема существования
Введение к работе
Актуальность темы исследования. Работа посвящена теоретико-игровому анализу следующей задачи, называемой задачей о многомерном размещении (ЗМР в дальнейшем):
Задан распределённый в d -мерном координатном нормированном пространстве (R , || ||) спрос со стороны множества индивидов на доступ к определённому виду общественного блага. Благо поставляется в отдельных пунктах, мощностях, которые нужно поддерживать в определённом количестве, расположив их в тех или иных местах в Rd . Стоимость поддержания мощности равна g и не зависит от её адреса.
Мощности эти имеют вид чистого общественного блага, то есть любая из них способна полностью удовлетворять спрос всех людей. В то же время, существуют затраты прикрепления каждого индивида к любой из мощностей, равные измеренному в заданной норме расстоянию от адреса предъявления спроса со стороны индивида до мощности, в которой спрос индивида будет удовлетворяться.
Требуется выбрать места для открытия мощностей, а также прикрепить к ним пользователей, минимальным по суммарной стоимости образом.
Идейное наполнение математических пререквизитов задачи — как самого пространства Rd , так и заданной на нём нормы 11 11 — зависит от рассматриваемого приложения ЗМР (которых имеется достаточно большое количество), и может меняться от географического конфликта и издержек перемещения в реальном пространстве до конфликта индивидуальных преференций относительно того, в какой из мощностей спрос может быть удовлетворён более качественно, с точки зрения данного потребителя.
Приведём примеры ЗМР: задача оптимального размещения сети центров обслуживания; задача оптимальной композиции парламента (то есть выбора количества партий и их политических программ); задача о формировании юрисдикции и городских округов.
Синонимом для ЗМР является задача формирования групп, если для каждой открытой мощности выделить группу её пользователей.
В западной литературе по теории исследования операций ЗМР известна (в несколько более общей постановке, нежели приведённая выше) как UFLP — Un-capacitated Facility Location Problem1.
^ornuejols, G. Nemhauser, G.L. and L.A. Wolsey (1990), The uncapacitated facility location prob-
Другая интеллектуальная традиция, соприкасающаяся с задачами, решаемыми в диссертации, это классическая теория пространственного размещения, пионерами которой можно считать А.Вебера, В.Кристаллера, А.Лёша, затем позже Н.Стерн, Б.Боллобаш, Ф.Морган, Р.Болтон, М.Хаймович, Т.Л.Маньянти. В статье двух последних авторов2 показано, что решением задачи оптимального размещения пунктов обслуживания на равномерно населённой плоскости служит сетка шестиугольников определённого (оптимального) размера. Однако специалистов по теории размещения интересует лишь нахождение оптимума, а не теоретико-игровые аспекты, которые очень важны.
Западные политэкономисты по духу подошли ближе к содержанию работы. В основополагающей статье соответствующего направления3 в рамках простейшего варианта ЗМР (равномерное расселение на отрезке) впервые поставлен ряд требований к устойчивости оптимального и иных решений — требований, носящих теоретико-игровой характер.
Конкретно, рассматривается несколько видов угроз коалиционной природы: устойчивость по отношению к расколу, к объединению и к отделению региона (регионом называется произвольное интервальное подмножество отрезка-мира). Их реализация в предположении о равномерном расселении математически тривиальна, и устойчивое разбиение на "страны" всегда существует.
В настоящей работе требования теоретико-игрового характера, такие как коалиционная и миграционная устойчивость, анализируются на основе далеко идущих обобщений модели А.Алесины и Э.Сполаоре.
Приведём здесь (нестрогие) определения двух основных для нашей работы угроз устойчивости, носящих теоретико-игровую природу.
Согласно первой из них, разбиение на группы должно быть устойчиво по отношению к угрозе образования новых групп из частей старых; это понятие устойчивости близко к ядру, и введено Робертом Ауманом и Жаком Дрезом4 под названием Core of a coalition partition form, что может быть переведено как ядро в форме разбиения на группы.
lem, in Discrete Location Theory, P. Mirchandani and R. Francis, eds., John Wiley and Sons, NYC, New York, 119-171.
2Haimovich, M. and T. L. Magnanti (1988), Extremum properties of hexagonal partitions and the uniform distribution in Euclidean location, Siam Journal of Discrete Mathematics 1(1), 50-64.
3Alesina, A. and E. Spolaore (1997), On the number and size of nations, Quarterly Journal of Economics, 113, 1027-1056.
4Aumann, R.J. and J. Dreze (1974), Cooperative games with coalition structure, International Journal of Game Theory 3, 217-237.
Второе, как правило менее жёсткое, требование к устойчивости заключается в том, что ни один участник ни одной группы не хочет стать членом другой группы (что происходит тогда, когда его суммарные издержки в новой группе снизятся по сравнению с исходной его группой). Данное понятие устойчивости является частным случаем равновесия по Нэшу в игре, где люди выбирают себе группы (и в равновесии каждый выберет "свою" группу).
Для придания строгости приведённым выше определениям устойчивости необходимо сделать определённые предположения о функционировании данной группы из разбиения. Важными для настоящего исследования вопросами являются следующие два: (а) как происходит улаживание конфликта внутри сформированной группы (например, когда конфликт носит пространственный характер, то вопрос состоит в том, где именно нужно построить центр обслуживания для данной группы пользователей), и (б) какие схемы перераспределения издержек, "внутригрупповой компенсации за удалённость", доступны участникам конфликта.
В работе принимается, что пункт (а) всегда разрешается по принципу минимизации суммарных транспортных издержек, то есть в точке Штейнера (в политических приложениях — по принципу медианного избирателя), а в пункте (б) есть три различных договорённости о делении издержек, которые естественным образом выделены, они и изучаются: принцип равнодо левого участия, принцип выравнивания общих издержек и принцип произвольного выбора схем компенсации (в последнем случае считаются доступными любые схемы перераспределения издержек).
В работах таких российских и зарубежных учёных, как Р.Болтон, С.Вартанов, А.Васин, Ш.Вебер, Ж.Дрез, А.Касселла, Х.Кониши, М.Ле Бретон, И.Ортуно-Ортин, Ж.Ролан, Ю.Сосина, Д.Степанов, Г.Хэрингер и других рассмотрены различные модификации ЗМР. Настоящее исследование продолжает и обобщает данное направление, а также собирает все полученные результаты воедино, в рамках одного и того же методологического подхода.
Цель работы и основные задачи. Цель исследования, во-первых, состоит в том, чтобы классифицировать теоретико-игровые подходы к анализу процесса формирования групп в задачах, сводящихся к ЗМР; во-вторых, чтобы получить ряд новых результатов касательно возможности противостоять тем или иным угрозам устойчивости в ЗМР.
Соответственно, ставились и решались такие задачи, как:
1. Классификация постановок и формализация угроз устойчивости решений
ЗМР. Выделены 3 основные постановки ЗМР, в соответствии с предположением о множестве участников/игроков: дискретная, непрерывная с плотностью, и континуальная с конечным числом типов. Первая служит теоретической базой для выявления основных препятствий к устойчивости, вторая хорошо моделирует задачи размещения в городах, в то время как третья, наоборот, моделирует региональное взаимодействие, когда города можно приближённо считать точками;
-
Классификация коалиционных и миграционных угроз устойчивости, носящих теоретико-игровую природу; адаптация строгих определений к каждому из трёх вариантов постановок задачи. Ниже при ссылке на тот или иной вариант постановки используются следующие обозначения: F,D,T — дискретный, непрерывный, конечно-типовой вариант задачи; М, С — означает, что миграционные, коалиционные угрозы принимаются в расчёт; S, R, Е — рассматривается принцип распределения издержек с побочными платежами, принцип выравнивания, принцип равнодолевого участия. Таким образом, например, аббревиатура DEC означает задачу поиска коалиционно устойчивых разбиений для случая непрерывного расселения с плотностью при принципе равнодолевого участия; аналигично расшифровываются и все остальные 17 аббревиатур.
-
Формулировка нового принципа устойчивости, усиленного миграционного равновесия — принципа, который относится к непрерывным постановкам и характеризуется устойчивостью против скоординированного перемещения малых масс жителей между группами;
-
Построение контрпримеров как к существованию коалиционно устойчивых, так и миграционно устойчивых решений; построение примеров расселений, устойчивые конфигурации в которых обладают нетривиальными свойствами (неинтервальность и др.);
-
Получение теорем существования устойчивых решений в некоторых случаях и при специальных предположениях на функции распределения;
-
Полное решение задачи поиска устойчивых разбиений в следующих трёх случаях: (a) DEC , равномерное расселение на отрезке; (б) DEM , равномерное расселение на отрезке; ТЕС, случай двух типов игроков (в последнем случае полная характеризация решений получена при любых параметрах расселения).
Методы исследования. Методы, использованные в работе, включают: теорию неподвижных точек (теорема Дебрэ-Никайдо-Гейла), анализ параметрических экстремальных задач, аналитические методы, дискретные методы, структурный анализ пространства разбиений, теоретико-игровой анализ, теория меры и функциональный анализ.
Научная новизна. Результаты диссертации являются новыми. Более того, новыми являются не только сами результаты, но и многие методы их обоснования. Научная новизна состоит в следующем:
-
Сформулирована модель оптимального размещения, относящаяся к классу "нескольких городов" и заключающаяся в том, что в стандартной постановке ЗМР вместо конечного числа точек спроса имеется конечное число типов потребителей (при этом внутри каждого типа — континуум потребителей).
-
В общей непрерывной модели формирования групп (которая в работе строго формализована) введено новое, усиленное требование миграционной устойчивости, которое было названо локально устойчивым миграционным равновесием.
-
В стандартной модели Алесины и Сполаоре обнаружены эндогенные неоднородные групповые структуры, в том числе и среди локально устойчивых миграционных равновесий; получены достаточные условия на коалиционную устойчивость, выделяющие целый класс (бесконечномерный!) устойчивых разбиений, а не только разбиений "на равные по размеру страны-интервалы" (как было в работе Алесины и Сполаоре).
-
Доказана теорема существования миграционно-устойчивого разбиения для произвольно расселения участников на отрезке; получены точные условия совпадения оптимума и равновесия, они имеют несколько параметров вырождения. Тем самым закрыто сразу два вопроса, до этого неизученных.
-
Для равномерного расселения на плоскости в условиях трансферабельной полезности получена полная характеризация эпсилон-ядра и показано, что единственной схемой распределения издержек, лежащей в минимальном ядре, является схема выравнивания общих издержек.
-
Получен критерий существования коалиционно устойчивых разбиений для произвольного биполярного мира, то есть расселения ровно по двум городам.
Выявлены зоны отсутствия устойчивых решений, а также необходимой дробности устойчивого разбиения.
7. Построена конфигурация точек спроса, являющаяся контрпримером к гипотезе существования коалиционно устойчивой групповой структуры для дискретного размещения на прямой. Конфигурация эта (включающая 13 игроков) обладает тем свойством, что не допускает устойчивого разбиения на группы даже при наиболее жёстких требованиях по отношению к выбору медианных мест открытия мощностей в группах, представляющих угрозу устойчивости. Этот контрпример обобщает и подытоживает предыдущие контрпримеры, которые были найдены на ранних стадиях диссертационного исследования.
Теоретическая и практическая значимость. Работа носит теоретический характер. Однако методы, разработанные в ней, могут быть полезными при дальнейшем исследовании задач многомерного размещения и близких к ним из политической науки, в которых принимаются в расчёт теоретико-игровые угрозы. Принципы устойчивости могут быть приняты к сведению и учтены при решении практических задач обеспечения города клубными благами и размещения сетей мест общего пользования в больших городах. Наглядность результатов позволяет внедрять их в учебный процесс — в рамках специальных курсов и специальных семинаров (что уже сделано в ряде прочитанных спецкурсов, как автором диссертации, так и его учениками и коллегами в ведущих ВУЗах страны, таких как МГУ, МФТИ, РЭШ, ВШЭ, ИГУ, ИрГТУ, УрФУ, НГУ и других).
Основные приложения ЗМР лежат либо в сфере политического конфликта (образование политических партий, объединений, клубов по интересам или даже стран), либо в сфере чисто географического конфликта (образование юрисдикции). В диссертации приведены примеры реализации как тех, так и других конфликтов.
Автору видится, что в случае конфликтов в сфере вкусов/взглядов более содержательной угрозой устойчивости является угроза коалиционная (образование новых групп), в то время как в случае географического конфликта важно уметь учесть и, по возможности, парировать угрозы миграционные. В работе изучаются и те, и другие угрозы в рамках общей математической модели.
Апробация работы. Результаты диссертации докладывались на международных конференциях и семинарах, а также на конференциях, летних школах и семинарах в России.
Перечислим конференции за рубежом: Coalition Theory Network (Париж 2005, Лювен-ля-нёв 2007, Венеция 2008); Heterogeneity in Social Organizations (Лювен-Ля-Нёв 2005, Брюссель 2006); Public Goods, Public Projects and Externalities (Марсель 2007); The Equilibrium Manifold (Лунд 2006).
В России автор докладывал результаты диссертационного исследования на Международной конференции ВШЭ (Москва 2006 - 2011, 2013); Международной научно-практической конференции УрГУ (Екатеринбург 2006 - 2013); Шаталинской Школе-Семинаре (Воронеж 2008, Вологда 2009, Звенигород 2010, Калининград 2011, Кострома 2012); Ежегодной конференции ЕУ СПб (Санкт-Петербург 2008-2011); конференции СПбЭМИ РАН (Санкт-Петербург 2008, 2010, 2012); Байкальских Чтениях (Иркутск 2008-2013); Школе-семинаре "Методы оптимизации и их приложения" (Северобайкальск 2005, 2008, Омск 2009, Листвянка 2011); конференции ГУУ (Москва 2010-2011); конференции РЭШ (Москва 1998-2011); конференции СЗАГС (Санкт-Петербург 2011, 2012); на Юбилейной конференции в честь 50-летия Академгородка (Новосибирск 2007); Game theory and Management (Санкт-Петербург 2007); ORM (Москва 2008, 2010); конференции памяти Гайдара в АНХ (Москва 2011); конференции в честь 100-летия Канторовича (Санкт-Петербург 2012), а также на ряде других конференций и летних школ.
Перечислим теперь города, где автор выступал с приглашённым докладом на семинарах: Тилбург, Мадрид, Аликанте, Маастрихт, Брюссель, Варшава, Тулуза, Киев, Осло, Москва, Санкт-Петербург, Иркутск, Новосибирск, Томск, Новочеркасск, Ростов, Воронеж;, Пермь, Красноярск, Нижний Новгород, Казань, Самара и во многих других городах; из ведущих семинаров неоднократно выступал на семинаре математической экономики ЦЭМИ РАН, семинаре теоротдела ФИ АН, в МГУ, СПбЭМИ, ЕУ СПб, Computer Science Club, ПОМП, РЭШ, ВШЭ, в Финансовой Академии при Правительстве РФ, в филиалах ВШЭ в Санкт-Петербурге, Нижнем Новгороде и Перми, в СПбГУ, EERC-Kiev, ФИНЭК СПб, ИГУ, ИСЭМ СО РАН, ИДСТУ СО РАН и в ряде других институтов и ВУЗов России.
Публикации. Результаты диссертации опубликованы в тридцати девяти работах общим объёмом 41,6 печатных листов (личный вклад автора - 15,45 печатных листов). Из них 11 работ общим объёмом 12,06 печатных листов входят в список журналов, включённых ВАК Министерства образования и науки России в перечень ведущих журналов и изданий, рекомендованных для публикации основных результатов диссертационных исследований на соискание учёных степеней кандидата и доктора наук (личный вклад автора - 6, 05 печатных листов).
Структура диссертации. Диссертация состоит из введения, четырёх глав и заключения, списка литературы из 120 наименований, двух таблиц и 15-ти иллюстраций. Полный объем работы составляет 256 страниц, из которых 13 страниц занимает список использованных источников.
Фундаментальный конфликт, изучаемый в работе, и несколько его конкретных воплощений
Лейтмотивом диссертационного исследования служит конфликт, присутствующий при организации практически любой коллективной деятельности. Это — конфликт между экономией от масштаба, во имя которой и происходит любая “коллективизация”, с одной стороны, и растущими при объединении людей разногласиями, с другой.
Анализом этого конфликта занимались многие учёные, и в течение всей диссертационной работы у нас будут встречаться ссылки на те или иные ранее полученные результаты. Данный конфликт прослеживается во многих сюжетах, и ниже я привожу список наиболее интересных, с моей точки зрения, его проявлений.
Сюжет 1: Странообразование, имперское строительство Никогда ещё за всю историю планеты не существовала империя размером в целый мир. При этом империи часто росли до очень внушительных размеров (Британская империя в 1922 году составляла более 1/5 суши, Монгольская империя много веков назад приблизительно столько же, затем Российская Империя и после неё СССР со знаменитой 1/6 частью суши, да и соверменная Россия занимает 1/8 часть суши, что весьма внушительно на фоне общей тенденции мира к измельчению).
Но чем больше империи росли, тем сложнее бывало улаживать явные или неявные конфликты внутри них — конфликты самой разной природы (религиозной, национальной, культурной, географической). Начиная с какого-то размера, каждая империя становилась неуправляемой и распадалась (либо теряла часть своих территорий).
Несмотря на это, во все времена нации и народы стремились к имперскому строительству, пытаясь убегать от феодальной разрозненности как от чумы, хорошо понимая, что последняя грозит потерей независимости, и в конечном счёте ведёт к войнам или порабощению одних цивилизаций другими (исключение составляют последние 30-40 лет воинствующего сепаратизма как отката назад в векторе исторического развития).
Итак, маленькие страны слабы и не выдерживают внешнего напора, а большие страны вынуждены всё время решать проблемы разногласий и/или управляемости. Налицо реализация вышеописанного конфликта.
В интернете часто возникают некие “виртуальные сообщества” по интересам, прообразом которых прежде служили “клубы”. Такое сообщество объединяет людей, увлечённых чем-нибудь — футболом, музыкой, собачками. Эти люди объединяются и обсуждают своих любимцев; однако объединение это, как правило, “упирается” в существенные вкусовые расхождения. Футбол даже в одной Москве — это и Спартак, и ЦСКА, и Локомотив, и Динамо, а музыка — это и классика, и джаз, и русский рок, и даже, с определённой натяжкой, русская эстрада (попса и шансон).
Ясно, что вкусовые разногласия воспрепятствуют созданию единого клуба “всех любителей музыки”. Пример с футболом является более запутанным: у нас на уровне любви к сборной всё-таки объединяются вместе все! Но, например, в Великобритании действует сразу несколько сборных, и тут налицо реализация вышеупомянутого конфликта один в один: потенциальная сборная Великобритании способна победить на любом чемпионате, но её вероятный успех не смогут разделить, скажем, шотландцы: они не воспримут его как СВОЙ успех, не станут этот успех отождествлять с самими собой !
Задача в данном случае состоит в нахождении оптимальной композиции парламента (то есть в выборе количества партий и определения их политических программ). Реализация фундаментального конфликта проходит по оси “большая партия более влиятельна, но и менее консолидирована”.
Это особенно хорошо заметно на Западе, но даже и у нас всё не так прямолинейно, как это кажется на первый взгляд. В самом деле, даже если Единая Россия и имеет решающий голос по многим вопросам, этот голос не всегда может быть, так сказать, использован — внутри самой ЕР имеются конфликтующие группировки.
Однако самую непосредственную, явную роль постулированный выше конфликт между размером и разногласиями играет в задачах пространственного размещения. Приведу его очень грубую форму (ибо конфликтов пространственного размещения — великое множество).
Есть деревня, расположенная вдоль одной улицы. Нужно построить колодец (один или несколько), чтобы снабдить жителей доступом к воде. Если построить один колодец, то это дёшево (в среднем с дома), но жители на краю села (более далёком от колодца) будут носить воду очень далеко.
Вероятно, при достаточной длине деревни решено будет построить не один, а сразу несколько колодцев, в разных местах улицы, однако вряд ли каждый дом станет рыть свой собственный колодец. Общественный выбор остановится на чём-то промежуточном.
В реальной жизни воплощением ЗМР может быть задача оптимального размещения сети центров обслуживания — госпиталей, школ, бассейнов, стадионов, музеев, почтамтов, библиотек и т.п., задача о формировании юрисдикций и городских округов и многие другие проблемы. Подведём предварительный итог.
В каждом из описанных сюжетов намечается тенденция к формированию групп компромиссного размера. От чего зависит этот “компромиссный размер”? Какие групповые структуры мы признаём устойчивыми, и в каком точном смысле слова? Эти, а также многие другие близкие по духу вопросы ставятся и анализируются в настоящем исследовании.
Теоретико-игровые угрозы миграционной природы в задаче ЗМР (постановка F)
aТак или иначе формулируй задачу ЗМР, а сложностей, связанных с её решением, всё равно не избежать: она NP-трудная. Точнее, NP-трудной является задача UFLP (см. [45] и подробное обсуждение во введении), а переход к конечномерным постановкам, судя по всему, не даёт никаких специальных преимуществ при её решении.
Наука, посвящённая разработке алгоритмов решения этой задачи, относится к области исследования операций. В то же время вопросы, которым посвящена диссертационная работа, относятся к теории игр — и по духу, и по методам, и по сути решаемых проблем.
Нас не будет интересовать то, насколько сложно с алгоритмической точки зрения решить задачу многомерного размещения. Решение есть, и хорошо; нас интересуют свойства устойчивости получаемых решений, причём устойчивость здесь понимается в смысле поведенческих, теоретико-игровых угроз. Согласятся ли сами резиденты, игроки из N, с навязанным им разбиением 7Г? Если да, то как это доказать? Если нет, то что можно предложить им взамен? Каковы потенциальные угрозы предлагаемым решениям задачи со стороны участников конфликта?
Наш подход не должен выходить за рамки понятий, введённых выше — то есть, за рамки рассуждений в терминах издержек, стоимостей прикрепления, экономии и т.п. Иными словами, мы будем рассматривать только такие угрозы, которые возникают в связи с возможностью резидентов снизить суммарные индивидуальные издержки/увеличить выигрыш. Исследование остаётся в рамках экономического подхода и не принимает во внимание такие угрозы, как “Вася не хочет плавать в одном бассейне с Петей”.3
С новой формулировкой ЗМР (с той, которая имеет дело с пространством всех разбиений и минимизацией функционала на нём) удобно работать с позиций теории игр. Мы будем рассматривать угрозы по отношению к предлагаемому в решении задачи разбиению 7Г со стороны “перебежчиков” из группы в группу, а также со стороны целых “коалиций” S С N, которые могут быть как частями групп исходного разбиения 7Г, так и быть сколоченными из частей различных групп-кусков разбиения , и своим созданием саботировать (разрушать) предлагаемое решение 7Г. Конкретно:
Миграционная угроза. Что, если любой человек может самовольно “прикрепиться” к той мощности, к которой он захочет, игнорируя
3Или посещать с ним на фестивале один и тот же СП. назначенную всем функцию прикрепления h?
Коалиционная угроза. А что, если любая коалиция S С N имеет возможность сепаратистского поведения, то есть может сама решить свою задачу (2.10), игнорируя назначенное решение {(mi,... , m ); h(-)} , или, что эквивалентно, игнорируя предложенное в решении задачи разбиение 7Г Уже сходу ясно, что изучать такие угрозы можно лишь после доопределения понятия решения задачи. В самом деле, что толку резидентам в том, что решение получено оптимальное? Ведь более важный вопрос в сообществе методологических индивидуалистов — “а сколько за всё это буду платить лично я”? То есть, как именно распределены между игроками оптимизированные суммарные издержки?
Но и это ещё не всё. Даже если Центр, решив задачу, как-либо распределит суммарные издержки по людям, встаёт вопрос, на что могут рассчитывать отклоняющиеся, саботирующие группы и индивиды? Что получит Вася, самовольно прикрепившись к некой другой мощности j, внутри группы, в которую он автоматически таким образом влился? Какие перспективы у коалиции S, “организовавшей своё собственное дело”?
Мы приходим к центральному понятию теории формирования групп — к понятию принципа и схемы распределения общих издержек (cost allocation rule по-английски). От того, каковы господствующие представления в обществе относительно того, кто сколько платит и при каких обстоятельствах, критическим образом зависит устойчивость получаемых (оптимальных, но также и просто допустимых) решений относительно возникающих угроз теоретико-игровой природы.
Ядро в форме разбиения на коалиции
Перейдём к строгой формализации коалиционных угроз устойчивости, пока при произвольной размерности d пространства разногласия Hd. Начнём с наведения мостов со стандартной коалиционной теорией игр.
А именно, каждому множеству игроков N с расселением хі,...,хп Є Rd, вместе с указанным принципом распределения издержек Р (см. определение Р в главе 2), мы сопоставим кооперативную игру в характеристической форме V. А именно, множество V(S) допустимых выигрышей коалиции S С N определяется следующим образом: V(S) состоит из векторов {v = (vi)ies R }, для которых существует вектор ts = {tf} Є P[S] со свойством
Выигрыши все идут со знаком “минус”, так как у нас делятся издержки. Это игра удовлетворяет всем стандартным условиям, накладываемым на игры без побочных платежей. Таким образом, можно применить к ней стандартные приёмы для исследования кооперативных игр. (Пока мы не специфицируем конкретного принципа распределения издержек, все построения годятся для любого из исследуемых принципов.)
Определение ND. Недоминируемым распределением (вариант: вектором) выигрышей называется такой вектор v = {v = (УІ)ІЄМ} Є Rn, что VS С А индуцированный вектор выигрышей vs = {v = (vi)ies} R не принадлежит внутренности множества V(S).
Заметим, что определение, данное выше, годится для любого абстрактного вектора из Rn. Теперь, если мы хотим видеть недоминируемый вектор выигрышей в качестве решения задачи, нам нужно наложить условия на его допустимость, или иначе говоря, реализуемость через ту же игру. Начнём с определения ядра, просто напомним определение:
Определение Core. Ядром кооперативной игры, заданной в характеристической форме, называется множество всех недоминируемых распределений, реализуемых тотальной коалицией: v Є V{N).
Кооперативные игры, построенные по данным изучаемой задачи, не всегда удовлетворяют условию супераддитивности. Это означает, в частности, что образование и функционирование тотальной коалиции не обязательно является Парето-оптимальным. Поэтому определение ядра также нуждается в модификации. Требуемая модификация определения взята из статьи [26]:
Определение С — Stab. Ядром в форме разбиения на коалиции называется множество таких недоминируемых распределений v, для которых существует разбиение 7Г = {Si,... , Sk} множества игроков, а также набор схем распределения издержек {t к} со свойством V/ tSl Є P[Sj\ , что
Концепция коалиционной устойчивости решения: ядро в форме разбиения на коалиции (Core of a coalition partition form).
В диссертационном исследовании мы смещаем фокус с рассмотрения недоминируемых распределений на анализ разбиений, реализующих эти недоминируемые распределения выигрышей, или издержек (что то же самое, после смены знака).
Коалиционная устойчивость, или устойчивость против теоретико-игровых угроз коалиционной природы, может быть определена для всех принципов FT, FR, FE (а также и для любых прочих, но на этом не будем останавливаться), согласно выработанному выше единому подходу:
Определение FC. Разбиение 7г = {Si,..., Sk} , где N = Si U ... U
Sk, называется коалиционно- устойчивым или ядерным для принципа распределения издержек Р, если существует вектор u= (щ,..., ип), для которого выполнены следующие два требования: (i) Для каждой группы разбиения Si Є 7Г проекция вектора и на группу Si, то есть вектор {ui}ies,, является разрешённой схемой относительно принципа Р для группы Si, то есть принадлежит множеству P[Si]; для любой потенциальной коалиции S и любой её разрешённой относительно Р схемы ts Є P[S] существует такой член коалиции S, скажем і Є S, что для него верно следующее неравенство:
Ниже мы по очереди рассмотрим три введённых выше принципа распределения издержек, и в каждом из них проанализируем концепцию коалиционной устойчивости решений: FRC, FSC и FEC; последний случай при d = 1 также распадается на под-случаи FEFC и FEMC, кроме того, будет введён ещё один случай FEAC, подводящий итог общему рассмотрению коалиционной устойчивости для дискретных расселений.
Миграционные равновесия на отрезке с произвольным расселением: общая теорема существования
Настоящий раздел содержит весьма общий результат существования миграционно устойчивого разбиения на предписанное число групп для произвольных расселений на отрезке, обладающих плотностью, которая непрерывна и отделена от нуля. Этот раздел — второй “сюжетный”, поэтому в нём изложение как бы автономное, хотя прямо так заявить, что можно читать его без оглядки на предыдущие главы, я не могу.
Рассмотрим неатомическую игру [6], состоящую из континуума игроков общей массы 1, расселённых по отрезку [0,1] с заданной положительной и отделённой от нуля плотностью /() .2 В дальнейшем всюду будем отождествлять игрока с его адресом проживания, х Є [0,1]. Кумулятивная функция распределения для плотности /() будет обозначаться за F(-). Массу любого измеримого подмножества S С [0,1] будем обозначать за \S\ = Is f{x)dx. Если S — интервал, S = [а, Ь], то \S\ = F(b) — F(a).
Каждый житель3 отрезка должен быть приписан к определённому пункту удовлетворения фиксированного, неэластичного спроса. Всего пунктов обеспечения спроса планируется открыть п 0, фиксированное и заданное число. Более того, рассматривается только случай п 1, ибо при п = 1 невозможно поставить вопрос о миграционной устойчивости.
Стоимость открытия любого пункта не зависит от адреса и равна д.
Стандартная постановка ЗРНМ в нашем случае будет выглядеть следующим образом (помятуя о том, что число групп разбиения задано и равно n): Min \gn + JQ \X — rriux\\f{x)dx\, uflp (4.17) {{mi,...,mn};/i: [0,1] - {l,...,n}}.
Иными словами, нужно выбрать места открытия мощностей mi,... ,mn, а также способ прикрепления каждого жителя к одному из мест, оптимальным по общей стоимости образом. Будем всегда считать в дальнейшем, что ті ЇЇІ2 ... тп (легко показать, что в оптимуме никогда не будет совпадения двух или более мест открытия мощностей). В качестве матрицы стоимости прикрепления потребителей к пунктам доступа в нашем случае берётся просто матрица попарных расстояний: сху = \х — у\, если житель х приписан к можности, открытой в точке у.
Настоящий раздел диссертации — последний из трёх самостоятельных блоков-модулей. Он также имеет свою историю, пускай и не столь Постановка задачи оптимального размещения на плоскости
В 1909 году А.Вебер опубликовал работу (...) по теории размещения. Его идеи подхватили Кристаллер и Лёш (...). Тема развивалась, вполедствии ею занимались многие учёные, вплоть до живущих ныне знаменитых математиков, например, Боллобаш.
Задача об оптимальном размещении является, на самом деле, континуальной реинкарнацией всё той же ЗМ, только на плоскости. Она формулируется следующим образом. Пока “нестрого”:
Дана плоскость, равномерно заселённая народом. Требуется создать некоторое количество “деловых центров”, в которых люди будут встречаться и сообща решать различные вопросы (торговать, учиться, просто общаться по интересам и т.п.). Стоимость строительства одного такого центра равна д. Расстояние между человеком и центром, к которому он приписан, принимается за меру транспортных издержек (величина д выражена в единицах издержек, то есть в единицах расстояния между точками, но является величиной интегральной, а само расстояние — потоковой, stock and flow, только не во временной шкале, а в шкале интегрирования по мере Лебега).
На более строгом уровне, мы договоримся использовать евклидово расстояние на плоскости (хотя в заключении к этому сюжету будет сказано и
Задача состоит в том, чтобы придумать наиболее экономную сеть деловых центров, при которой суммарные издержки от строительства центров плюс интегральные издержки перемещения всех людей будут минимальными.
Иными словами, ставится задача минимизации на пространстве всех подмножеств плоскости, задача такого же вида, как и (??): с одой только поправкой: минимизируемый функционал тождественно бесконечен на всём пространстве допустимых планов задачи.
Впрочем, эту трудность можно обходить различными способами. Один из них состоит в том, чтобы рассмотреть данную постановку на конечном куске плоскости, например на большом круге, затем разделить целевой функционал на площадь круга и устремить к бесконечности, на этот раз оптимизируя предельное значение (т.е. среднее значение подушевых общих издержек от строительства центров плюс перемещения).
Более правильно, однако, исходить из другой формализации нашей бесконечной задачи, см. (...). Её желательность следует из того факта, что целевой функционал, усреднённый по большим кругам, в оптимуме нечувствителен к пертурбациями любого вида на конечном куске плоскости, с сохранением оптимальности расположения центров на остальной её части: в пределе разница уйдёт в ноль.
Поэтому нужно минимизировать бесконечный интерграл, так сказать, в смысле нестандартного анализа: искать такую сеть центров, для которой любая пертурбация приведёт к увеличению целевого интеграла на каком-нибудь конечном куске плоскости. И теперь ниже приводится точный результат, полученный на этом пути:
Теорема ( ) Единственной сетью центров, оптимизирующей задачу (4.41) в указанном выше самом строгом смысле слова, является треугольная сетка на плоскости; при этом структура групп, состоящих из пользователей одного и того же центра, окажется шестиугольным регулярным замощением плоскости. (Природа знает своё дело; нам есть чего научиться у пчёл!).
Основные ссылки на доказательство этой теоремы, хотя этот результат носит чёткую окраску “народного”: Fejes Toth (1953), Haimovich and Mag-nanti (1988), Morgan and Bolton (2002), а также Christaller (1933), Losch (1954), Bollobas and Stern (1972) и Stern (1972) в контексте географического конфликта. Размер групп- шестиугольников, образующих оптимальное замощение, убывает определённым образом с убыванием параметра д.
