Задача многомерного размещения и ее приложения: теоретико-игровой подход тема диссертации по экономике, полный текст автореферата

Ученая степень
доктора физико-математических наук
Автор
Савватеев, Алексей Владимирович
Место защиты
Москва
Год
2013
Шифр ВАК РФ
08.00.13

Автореферат диссертации по теме "Задача многомерного размещения и ее приложения: теоретико-игровой подход"

На правах рукописи

005533231

Савватеев Алексей Владимирович

ЗАДАЧА МНОГОМЕРНОГО РАЗМЕЩЕНИЯ И ЕЁ ПРИЛОЖЕНИЯ: ТЕОРЕТИКО-ИГРОВОЙ ПОДХОД

Специальность 08.00.13 - Математические и инструментальные методы экономики

Автореферат

диссертации на соискание учёной степени доктора физико-математических наук

Москва - 2013

1 9 СЕН 2013

005533231

Работа выполнена в Лаборатории математической экономики Федерального государственного бюджетного учреждения науки Центральный экономико-математический институт Российской академии наук

Научные консультанты:

д.ф-м.н., академик РАН Валерий Леонидович Макаров Ph.D., профессор Шломо Вебер

Официальные оппоненты:

Поспелов Игорь Гермогенович д.ф-м.н., профессор, член-корреспондент РАН заведующий отделом математического моделирования экономических систем Вычислительного центра им. A.A. Дородницына РАН Новиков Дмитрий Александрович д.т.п., профессор, член-корреспондент РАН, заместитель директора ИПУ РАН Райгородский Андрей Михайлович д.ф-м.н., профессор кафедры математической статистики и случайных процессов механико-математического факультета МГУ имени М.В. Ломоносова

Ведущая организация:

Институт динамики систем и теории управления Иркутского Научного Центра Сибирского Отделения Российской академии наук

Защита состоится 14 октября 2013 года в 10 часов на заседании диссертационного совета Д 002.013.02 в Федеральном государственном бюджетном учреждении науки Центральный экономико-математический институт Российской академии наук, расположенном по адресу: 117418, Москва, Нахимовский проспект, 47, ауд. 520.

С диссертацией можно ознакомиться в библиотеке ЦЭМИ РАН.

Автореферат разослан 6 сентября 2013 года

Ученый секретарь

диссертационного совета г • к.ф-м.н. Борисова Светлана Валерьевна

Общая характеристика работы

Актуальность темы исследования. Работа посвящена теоретико-игровому анализу следующей задачи, называемой задачей о многомерном размещении (ЗМР в дальнейшем):

Задан распределённый в d-мерном координатном нормированном пространстве II • II) спрос со стороны множества индивидов на доступ к определённому виду общественного блага. Благо поставляется в отдельных пунктах, мощностях, которые нужно поддерживать в определённом количестве, расположив их в тех или иных местах в R . Стоимость поддержания мощности равна g и не зависит от её адреса.

Мощности эти имеют вид чистого общественного блага, то есть любая из них способна полностью удовлетворять спрос всех людей. В то же время, существуют затраты прикрепления каждого индивида к любой из мощностей, равные измеренному в заданной норме расстоянию от адреса предъявления спроса со стороны индивида до мощности, в которой спрос индивида будет удовлетворяться.

Требуется выбрать места для открытия мощностей, а также прикрепить к ним пользователей, минимальным по суммарной стоимости образом.

Идейное наполнение математических пререквизитов задачи — как самого пространства

. так и заданной на нём нормы || ■ || — зависит от рассматриваемого приложения ЗМР (которых имеется достаточно большое количество), и может меняться от географического конфликта и издержек перемещения в реальном пространстве до конфликта индивидуальных преференций относительно того, в какой из мощностей спрос может быть удовлетворён более качественно, с точки зрения данного потребителя.

Приведём примеры ЗМР: задача оптимального размещения сети центров обслуживания; задача оптимальной композиции парламента (то есть выбора количества партий и их политических программ); задача о формировании юрисдикции и городских округов.

Синонимом для ЗМР является задача формирования групп, если для каждой открытой мощности выделить группу её пользователей.

В западной литературе по теории исследования операций ЗМР известна (в несколько более общей постановке, нежели приведённая выше) как UFLP — Uncapacitated Facility Location Problem1.

Другая интеллектуальная традиция, соприкасающаяся с задачами, решаемыми в диссертации, это классическая теория пространственного размещения, пионерами которой можно считать А.Вебера, В.Кристаллера, А.Лёша, затем позже Н.Стерн, Б.Боллобаш, Ф.Морган, Р.Болтон, М.Хаймович, Т.Л.Маиьянти. В статье двух последних авторов2 показано, что решением задачи оптимального размещения пунктов обслуживания на равномерно населённой плоскости служит сетка шестиугольников определённого

1CornuejoIs, G. Nemhauser, G.L. and L.A. Wolsey (1990), The uncapacitated facility location problem, in Discrete Location Theory, P. Mirchandani and R. Francis, eds., John Wiley and Sons, NYC, New York, 119-171.

Haimovich, 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.

(оптимального) размера. Однако специалистов по теории размещения интересует лишь нахождение оптимума, а не теоретико-игровые аспекты, которые очень важны.

Западные политэкономисты по духу подошли ближе к содержанию работы. В основополагающей статье соответствующего направления3 в рамках простейшего варианта ЗМР (равномерное расселение на отрезке) впервые поставлен ряд требований к устойчивости оптимального и иных решений — требований, носящих теоретико-игровой характер.

Конкретно, рассматривается несколько видов угроз коалиционной природы: устойчивость по отношению к расколу, к объединению и к отделению региона (регионом называется произвольное интервальное подмножество отрезка-мира). Их реализация в предположении о равномерном расселении математически тривиальна, и устойчивое разбиение на "страны" всегда существует.

В настоящей работе требования теоретико-игрового характера, такие как коалиционная и миграционная устойчивость, анализируются на основе далеко идущих обобщений модели А.Алесины и Э.Сполаоре.

Приведём здесь (нестрогие) определения двух основных для нашей работы угроз устойчивости, носящих теоретико-игровую природу.

Согласно первой из них, разбиение на группы должно быть устойчиво по отношению к угрозе образования новых групп из частей старых; это понятие устойчивости близко к ядру, и введено Робертом Ауманом и Жаком Дрезом4 под названием Core of a coalition partition form, что может быть переведено как ядро в форме разбиения на группы.

Второе, как правило мепее жёсткое, требование к устойчивости заключается в том, что ни один участник ни одной группы не хочет стать членом другой группы (что происходит тогда, когда его суммарные издержки в новой группе снизятся по сравнению с исходной его группой). Данное понятие устойчивости является частным случаем равновесия по Нэшу в игре, где люда выбирают себе группы (и в равновесии каждый выберет "свою" группу).

Для придания строгости приведённым выше определениям устойчивости необходимо сделать определённые предположения о функционировании данной группы из разбиения. Важными' для настоящего исследования вопросами являются следующие два: (а) как происходит улаживание конфликта внутри сформированной группы (например, когда конфликт носит пространственный характер, то вопрос состоит в том, где имепно нужно построить центр обслуживания для данной группы пользователей), и (б) какие схемы перераспределения издержек, "внутригрупповой компенсации за удалённость", доступны участникам конфликта.

В работе принимается, что пункт (а) всегда разрешается по принципу минимизации

3Alesina, A. and Е. Spolaore (1997), On the number and size of nations, Quarterly Journal of Economics, 113, 1027-1056.

4Aumann, R.J. and J. Drèze (1974), Cooperative games with coalition structure, International Journal of Game Theory 3, 217-237.

суммарных транспортных издержек, то есть в точке Штеймера (в политических приложениях — по принципу медианного избирателя), а в пункте (б) есть три различных договорённости о делении издержек, которые естественным образом выделены, они и изучаются: принцип равнодолевого участия, принцип выравнивания общих издержек и принцип произвольного выбора схем компенсации (в последнем случае считаются доступными любые схемы перераспределения издержек).

В работах таких российских и зарубежных учёных, как Р.Болтон, С.Вартанов, А.Васин, Ш.Вебер, Ж.Дрез, А.Касселла, Х.Кониши, М.Ле Бретон, И.Ортуно-Ортин, Э.Рапопорт, Ж.Ролан, Ю.Сосина, Д.Степанов, Г.Хэрингер и других рассмотрены различные модификации ЗМР. Настоящее исследование продолжает и обобщает данное направление, а также собирает все полученные результаты воедино, в рамках одного и того же методологического подхода.

Цель работы и основные задачи. Цель исследования, во-первых, состоит в том, чтобы классифицировать теоретико-игровые подходы к анализу процесса формирования ГРУ™1 в задачах, сводящихся к ЗМР; во-вторых, чтобы получить ряд новых результатов касательно возможности противостоять тем или иным угрозам устойчивости в ЗМР.

Соответственло, ставились и решались такие задачи, как:

1. Классификация постановок и формализация угроз устойчивости решений ЗМР. Выделены 3 основные постановки ЗМР, в соответствии с предположением о множестве участников/игроков: дискретная, непрерывная с плотностью, и континуальная с конечным числом типов. Первая служит теоретической базой для выявления основных препятствий к устойчивости, вторая хорошо моделирует задачи размещения в городах, в то время как третья, наоборот, моделирует региональное взаимодействие, когда города можно приближённо считать точками;

2. Классификация коалициошшх и миграционных угроз устойчивости, носящих теоретико-игровую природу; адаптация строгих определений к каждому из трёх вариантов постановок задачи. Ниже при ссылке на тот или иной вариант постановки используются следующие обозначения: F,D,T — дискретный, непрерывный, конечно-типовой вариант задачи; М,С — означает, что миграционные, коалиционные угрозы принимаются в расчёт; S,R,E — рассматривается принцип распределения издержек с побочными платежами, принцип выравнивания, принцип равнодолевого участия. Таким образом, например, аббревиатура DEC означает задачу поиска коалиционно устойчивых разбиений для случая непрерывного расселения с плотностью при принципе равнодолевого участия; аналигично расшифровываются и все остальные 17 аббревиатур.

3. Формулировка нового принципа устойчивости, усиленного миграционного равновесия — принципа, который относится к непрерывным постановкам и характеризуется

устойчивостью против скоординированного перемещения малых масс жителей между группами;

4. Построение контрпримеров как к существованию коалиционно устойчивых, так и мигралионно устойчивых решений; построение примеров расселений, устойчивые конфигурации в которых обладают нетривиальными свойствами (неинтервальность

и др.);

5. Получение теорем существования устойчивых решений в некоторых случаях и при специальных предположениях на функции распределения;

6. Полное решение задачи поиска устойчивых разбиений в следующих трёх случаях: (a) DEC, равномерное расселение на отрезке; (б) DEM, равномерное расселение на отрезке; ТЕС, случай двух типов игроков (в последнем случае полная характеризация решений получена при любых параметрах расселения).

Методы исследования. Методы, использованные в работе, включают: теорию неподвижных точек, анализ параметрических экстремальных задач, функционально-аналитические методы, структурный анализ пространства разбиений, теоретико-игровой анализ и теорию меры.

Научная новизна. Результаты диссертации являются новыми. Более того, новыми являются не только сами результаты, но и многие методы их обоснования. Научная новизна состоит в следующем:

1. Сформулирована модель оптимального размещения, относящаяся к классу "нескольких городов" и заключающаяся в том, что в стандартной постановке ЗМР вместо конечного числа точек спроса имеется конечное число типов потребителей (при этом внутри каждого типа — континуум потребителей).

2. В общей непрерывной модели формирования групп (которая в работе строго формализована) введено повое, усиленное требование миграционной устойчивости, которое было названо локально устойчивым миграционным равновесием.

3. В стандартной модели Алесины и Сполаоре обнаружены эндогенные неоднородные групповые структуры, в том числе и среди локально устойчивых миграционных равновесий; получены достаточные условия на коалиционную устойчивость, выделяющие целый класс (бесконечномерный!) устойчивых разбиений, а не только разбиений "на равные по размеру страны-интервалы" (как было в работе Алесины и Сполаоре).

4. Доказана теорема существования миграционно-устойчивого разбиения для произвольного расселения участников на отрезке; получены точные условия совпадения

оптимума и равновесия, они имеют несколько параметров вырождения. Тем самым закрыто сразу два вопроса, до этого неизученных.

5. Для равномерного расселения на плоскости в условиях трансферабельной полезности получена полная характеризация эпсилон-ядра и показано, что единственной схемой распределения издержек, лежащей в минимальном ядре, является схема выравнивания общих издержек.

6. Получен критерий существования коалиционно устойчивых разбиений для произвольного биполярного мира, то есть расселения ровно по двум городам. Выявлены зоны отсутствия устойчивых решений, а также необходимой дробности устойчивого разбиения.

7. Построена конфигурация точек спроса, являющаяся контрпримером к гипотезе существования коалиционно устойчивой групповой структуры для дискретного размещения на прямой. Конфигурация эта (включающая 13 игроков) обладает тем свойством, что не допускает устойчивого разбиения на группы даже при наиболее жёстких требованиях по отношению к выбору медианных мест открытия мощностей в группах, представляющих угрозу устойчивости. Этот контрпример обобщает и подытоживает предыдущие контрпримеры, которые были найдены на ранних стадиях диссертационного исследования.

Теоретическая и практическая значимость. Работа носит теоретический характер. Однако методы, разработашше в ней, могут быть полезными при дальнейшем исследовании задач многомерного размещения и близких к ним из политической науки, в которых принимаются в расчёт теоретико-игровые угрозы. Принципы устойчивости могут быть приняты к сведению и учтены при решении практических задач обеспечения города клубными благами и размещения сетей мест общего пользования в больших городах. Наглядность результатов позволяет внедрять их в учебный процесс — в рамках специальных курсов и специальных семинаров (что уже сделано в ряде прочитанных спецкурсов, как автором диссертации, так и его учениками и коллегами в ведущих ВУЗах страны, таких как МГУ, МФТИ, РЭШ, ВШЭ, ИГУ, ИрГТУ, УрФУ, НГУ и других).

Основные приложения ЗМР лежат либо в сфере политического конфликта (образование политических партий, объединений, клубов по интересам или даже стран), либо в сфере чисто географического конфликта (образование юрисдикции). В диссертации приведены примеры реализации как тех, так и других конфликтов.

Автору видится, что в случае конфликтов в сфере вкусов/взглядов более содержательной угрозой устойчивости является угроза коалиционная (образование новых групп), в то время как в случае географического конфликта важно уметь учесть и, по возможности, парировать угрозы миграционные. В работе изучаются и те, и другие угрозы в рамках общей математической модели.

Апробация работы. Результаты диссертации докладывались на международных конференциях и семинарах, а также на конференциях, летних школах и семинарах в России.

Перечислим конференции за рубежом: Coalition Theory Network (Париж 2005, Лювен-ля-нёв 2007, Венеция 2008); Heterogeneity in Social Organizations (Лювен-Ля-Нёв 2005, Брюссель 2006); Public Goods, Public Projects and Externalities (Марсель 2007); The Equi-libriura Manifold (Лунд 2006).

В России автор докладывал результаты диссертационного исследования на Международной конференции ВШЭ (Москва 2006 - 2011, 2013); Международной научно-практической конференции УрГУ (Екатеринбург 2006 - 2013); Шаталинской Школе-Семинаре (Воронеж 2008, Вологда 2009, Звенигород 2010, Калининград 2011, Кострома 2012); Ежегодной конференции ЕУ СПб (Санкт-Петербург 2008-2011); конференции СПбЭМИ РАН (Санкт-Петербург 2008, 2010, 2012); Байкальских Чтениях (Иркутск 20082013); Школе-семинаре "Методы оптимизации и их приложения" (Северобайкальск 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, ФИНЭК СПб, ИГУ, ИСЭМ СО РАН, ИДСТУ СО РАН и в ряде других институтов и ВУЗов России.

Публикации. Результаты диссертации опубликованы в 40 работах общим объёмом 42,8 печатных листов (личный вклад автора - 15,75 печатных листов). Из них 13 работ общим объёмом 13,5 печатных листов входят в список журналов, включённых ВАК Министерства образования и науки России в перечень ведущих журналов и изданий, рекомендованных для публикации основных результатов диссертационных исследований на соискание учёных степеней кандидата и доктора наук (личный вклад автора - 6,4 печатных листа).

Структура диссертации. Диссертация состоит из введения, четырёх глав и

заключения, списка литературы из 120 наименований, двух таблиц и 15-ти иллюстраций. Полный объем работы составляет 256 страниц, из которых 13 страниц занимает список использованных источников.

Содержание работы

Во Введении формулируется в общем виде решаемая в диссертации задача, даётся её мотивировка, рассказывается о том, что исследование находится на стыке нескольких научных направлений, приводится характеристика этих направлений, и обсуждаются знаковые научные достижения в них. Затем на описательном уровне вводятся в рассмотрение угрозы устойчивости, носящие теоретико-игровой характер и служащие предметом исследования в работе, а также приводится обзор литературы, содержащий описание результатов, примыкающих к полученным в диссертации.

Первая глава посвящена формализации дискретного (конечного) варианта рассматриваемой задачи, и соответствующих ей модификаций, связанных с поиском миграционио устойчивых решений.

Сначала определяется стандартная конечная постановка задачи многомерного размещения, в которой множество N = {1, ...,п} людей, проживающих в точках XI, ...,хп (Е нормированного координатного пространства, должно быть приписано к пунктам удовлетворения спроса, которых можно открыть сколько угодно.

Каждого человека обязательно прикрепить (ровно) к одному из пунктов. Стоимость открытия любого пункта фиксирована и равна д. Дополнительная стоимость прикрепления человека с адресом х{ к пункту, открытому в точке т, равна - т|| — расстоянию, измеренному в заданной на И11 порме.

Сперва ставится задача оптимального размещения пунктов (иногда говорят: "мощностей"). Наиболее удобная форма постановки этой задачи, в свете изучения устойчивости получаемых решений относительно коалиционных и индивидуальных ("миграционных") угроз — это форма двуступенчатая. Сначала вводится следующей важнейшая для всего исследования, мета-задача, которая восходит к Штейнеру, сформулировавшему её.на плоскости в начале XIX века:

Эта задача состоит в следующем: предположив, что состав одной из групп будет совпадать с подмножеством £, мы минимизируем затраты на приписку путём выбора места т £ Н.1* самого выгодного (по суммарным издержкам) расположения пункта.

Любое решение этой задачи в дальнейшем будет называться медианой подмножества троков 5 (иногда мы будем также использовать термин точка Штейнера).

с[5] = МттеКа

д + ЕкПК'-гаН _ 9 + Е.ея II- т\\

(1)

1«1

Теперь задача о размещении мощностей ставится следующим образом:1

,.5

Min^U ІЗДЗ]}, {к; ж = ,..., Sk} : N = 5, U S2 U... U Sk}.

Этой задаче было посвящено много усилий учёных.9 В диссертационном исследовании акцент переносится с поиска оптимума (или разработки алгоритмов поиска оптимума) на анализ угроз устойчивости, имеющих теоретико-игровую природу и возникающих при реализации решения (как оптимального, так и любого допустимого). Угрозы устойчивости, подвергнутые анализу в диссертационном исследовании, делятся на два класса: "миграционные" (синоним: "индивидуальные"), с одной стороны, и коалиционные (синоним: "ядерные", из-за связи соответствующего понятия устойчивости разбиения на группы с концепцией ядра кооперативной игры в характеристической форме), с другой.

Для анализа устойчивости групповых структур требуется указать, какой принцип распределения издержек внутри сформированных групп принимается за основу. В диссертации изучается три разных принципа. Согласно одному из них, издержки внутри каждой группы S могут быть поделены любым способом. Согласно другому принципу, издержки g на открытие и поддержание мощности делятся поровну между членами группы S, а издержки — ш|| прикрепления члена г G 5 группы S к пункту, открытому в точке m, каждый член сформированной группы несёт самостоятельно.

Третий принцип состоит в том, что общие издержки группы (1) делятся поровну между её участниками (полная компенсация различий в издержках прикрепления за счёт внутригрупповых трансфертов).

Первый принцип будет называться принципом трансферабелъной полезности или иначе принципом побочных платежей, второй — принципом равнодолевого участия, а третий — принципом Ролса, по имени известного исследователя такого подхода в экономических и социальных проблемах.

Коалиционные угрозы устойчивости можно сформулировать для всех трёх (на самом деле, вообще любых) принципов распределения издержек, а миграционные угрозы — только для таких принципов, в которых список участников группы однозначно определяет предписанные каждому из её членов платежи (для "однозначных" принципов распределения издержек, в англоязычной литературе это называется "hedonic environment").

Формально, в первой главе диссертации вводятся понятия схемы распределения издержек и принципа распределения издержек:

Определение Р. Принципом распределения издержек мы будем называть сопоставление каждой коалиции S набора векторов:

P[S] С Rs;

5Всюду в работе знак и будет обозначать несвязное объединение коалиций. 6 См. уже упоминавшуюся в сноске 1 обзорную статью.

каждый из векторов и] = {и;*}^ 6 Р[5] предписывает каждому члену i € в коалиции 3 нести суммарные издержки в размере w^. Вектора предполагаются неотрицательными и сбалансированными:

5> = с[5]. (4)

«ей

Векторы из Р[5] также будем называть допустимыми относительно принципа распределения издержек Р.

Принцип Р называется однозначным, если для каждого 5 подмножество Р[Й] является одноточечным, то есть состоит из одого допустимого вектора 6 Я5. В противном случае мы называем принцип многозначным. Однозначные принципы иногда назваются схемами распределения издержек; схемы часто обозначаются просто ОДНОЙ буквой Ь = {г®}5<;(2~)\{0} , где = {ifl.es

Принцип побочных платежей является многозначным, принцип Ролса — однозначным. Принцип равнодолевого участия будет однозначным тогда и только тогда, когда для любого подмножества Я С N множество медиан М[5] одноточечно, то есть когда медиана т[5] каждого подмножества определена однозначно.

В одном специальном случае многозначности множества М[£>], а именно в случае ЗМР, заданной на обычной прямой, в работе предпринят более детальный анализ угроз устойчивости, как коалиционной, так и миграционной, при разных дополнительных требованиях на выбор медиан в формирующихся группах. Для этого специального, но весьма важного частного случая также введено понятие интереальности групп и разбиений, и в первых двух главах приведён целый ряд результатов, связанных с этой концепцией.

Для однозначных принципов (схем) распределения издержек формулируется понятие миграционно устойчивого разбиения:

Определение -РМ. Разбиение 7Г = {5'ь..., б*} , заданное непересекающимся набором подмножеств 5( С ЛГ, где ЛГ = 5х и ... и Бк, называется миграционно устойчивым, Нэшевским или индивидуально устойчивым (эти термины взаимозаменяемы) при схеме распределения издержек t = }5САГ?е5 > если для любого номера I — 1 ,..,,к группы разбиения, любого игрока г 6 , а также любого подмножества С N либо пустого (IV = 0), либо совпадающего с Я/, при некотором номере группы к = 1,..., к, имеет место следующее неравенство:

(5)

Иными словами, если какой-либо из участников конфликта самовольно покинет свою группу и присоединится к другой (или просто останется в одиночестве), то его издержки от такого шага могут лишь возрасти.

В оставшихся разделах главы рассмотрения проводятся для случая в. = 1. В этом случае постановка РЕМ ещё дальше дробится на два варианта: РЕСМ, когда медиана, если их целый отрезок, должна быть взята в центральной точке последнего — "случай (схема) центральной медианы", и РЕММ, когда при смене группы игрок влияет на местоположение медианы минимально возможным образом — "требование минимального насилия при миграции". Строго говоря, последнее требование не укладывается ни в понятие схемы, ни в понятие принципа распределения издержек.

Для обоих постановок верна теорема об интервальное™ любого устойчивого разбиения. А вот само существование такого разбиения критическим образом зависит от конкретных предположений о выборе медианы. В работе приведён пример расселения ("Контрпример для случая РЕРМ"), при котором не существует миграционно устойчивых разбиений при требовании выбора центральной медианы, а также доказана теорема ('Теорема существования для случая РЕММ"), утверждающая существование миграционно устойчивого разбиения для любых расселений на прямой, если исходить из принципа минимального насилия при миграции. При доказательстве теоремы используется техника потенциальных игр.

Кроме того, в главе приведён пример ("Контрпример для случая РПМ ") расселения на прямой, при котором не существует миграционно устойчивого разбиения для принципа выравнивания издержек внутри групп, а также доказывается теорема существования миграционно устойчивых разбиений для расселений с равноотстоящими друг от друга локациями.

В главе 2 исследуются коалиционно устойчивые разбиения в дискретной постановке (в принятой классификации обозначаемой за'РС —анализ случаев РИС, РвС и РЕС).

Сперва даётся исторический экскурс по задаче в постановке РС, ибо именно с такой постановки (даже точнее, с анализа случая РЕС) и начиналось 10 лет назад становление того раздела теории игр, который лёг в основу диссертационного исследования.

Затем проводятся параллели с кооперативной теорией игр, конкретно с концепцией ядра в форме разбиения на коалиции (из упоминавшейся выше статьи Р.Аумаппа и Ж.Дреза, процитированной в ссылке 4). Для любого принципа распределения издержек Р даётся следующее определение:

Определение РС. Разбиение 7Г = {й^ ... ,5*} , заданное непересекающимся набором подмножеств 5| С где N = ^ и ... и Бк, называется коалиционно-устойчивым или ядерным для принципа распределения издержек Р, если существует вектор и= («!,... ,ип), для которого выполнены следующие требования:

(¡) Для каждой группы разбиения в! € тг проекция вектора и на группу , то есть вектор {«¡}£ея, , является допустимым относительно принципа Р для группы , то есть принадлежит множеству Р[5|];

(и) для любой потенциальной коалиции 5 и любого её допустимого вектора ^ 6

Р[5] существует такой участник коалиции 5, скажем г б 5, что для него верно следующее неравенство:

tf > Щ. (6)

Иными словами, в рамках разрешённых векторов внутригруппового деления издержек, невозможно найти группу и вектор для неё таким образом, чтобы всем её участникам при отделении этой группы стало строго лучше, чем при исходном разбиении. Это определение можно адаптировать под любой конкретный принцип распределения издержек.

Далее последовательно разбираются постановки FRC, FSC и FEC. Для принципа выравнивания платежей верна самая общая теорема существования устойчивого разбиения на группы; более того, она распространяется без труда и на случаи DRC, TRC, то есть анализ устойчивых структур для постановки RC является тривиальным. Интересно, впрочем, отметить, что устойчивая групповая структура в этом случае может быть неинтервальной, соответствующий пример одномерного расселения приведён в работе.

Исследованию коалиционной устойчивости в случае принципа побочных платежей (или трансферабельной полезности, FSC) были посвящены усилия многих учёных-предшественников.

В разделе, посвящённом этому случаю, даётся небольшой обзор полученных результатов. Здесь остановлюсь па главном: при d = 1, то есть для одномерных расселений, верен общий результат существования коалиционно устойчивого разбиения на группы.7

Для случая FEC, то есть без побочных платежей, при d. = 1 было доказано существование разбиения, устойчивого относительно интервальных коалиционных угроз.8 Сопоставляя оба этих достижения, авторы последней упомянутой работы высказали гипотезу о верности общей теоремы существования в постановке FEC при d = 1.

И тут следует отметить одно из знаковых достижений работы — опрвержение, причём многократное, этой гипотезы (в различных модификациях случая FEC касательно способа выбора медианы). Ниже в автореферате будет сказано про случай ТЕС, а здесь мы остановимся на формулировке теоремы "о крушении надежд на устойчивость", полностью закрывающей вопрос общей теоремы существования в дискретной постановке (для случая FEC):

Теорема о крушении надежд. Существует конечное расселение на прямой, при котором для любого разбиения п — {Si,...,SL} множества игроков N, взятого вместе с любым набором медиан {т;}1=11...£ в соответствующих группах, га; е

7Goemans, М.Х. and М. Skutella (2004), Cooperative facility location games, Journal of Algorithms 50, 192-214.

8Greenberg, J. and S. Weber (1986), Strong Tiebout Equilibrium under Restricted Preferences Domain, Journal of Economic Theory 38, 101-117.

А^ф], существует группа с однозначной медианой IV, то есть М[IV] = {т}, для любого участника i € IV которой будет выполнено следующее строгое неравенство (где I таково, что г € ^ в исходном, предлагаемом разбиении 7Г):

= щ + = Щ + (7)

Конкретно, N = {1,2,3,4,5,6,7,8,9,10,11,12,13}, на этот раз д = 120 и х\ = 12 = х3 = Х4 = хъ = 1е = = -4; х8 = 0; хя = хщ = хц = Х12 = хн = 12. (8)

Соответствующее расселение выглядит следующим образом:

9,10,11,12,13

___1_„

12

Рисунок 1. Универсальный контрпример.

Тем не менее не всё так плохо, есть и определённый позитивный задел. Существование коалиционно устойчивых решений в работе доказано для некоторых специальных классов расселений. Ниже приведён целый ряд мелких результатов диссертации, относящихся к случаю Е дискретного распределения спроса. Аббревиатура ЕЕЕ обозначает дополнение к принципу равнодолевого участия, при котором всегда выбирается центральная медиана отрезка всех медиан.

Теорема об устойчивых разбиениях для постановки ЕС. Справедливы еле-, дующие утверждения:

(¡) В случае РЕЕ всегда существует интервальное коалиционно устойчивое разбиение на группы для расселения через равноотстоящие локации х; = Н, I = 1,... ,п (в дальнейшем будем называть этот случай "равноотстоящим расселением", или просто равномерным расселением);

(п) В случае ЕЕЕ существуют неинтервалъные устойчивые разбиения даже при равномерном расселении;

(Ш) В случае F-БF указано конкретное расселение, для которого единственным коалиционно устойчивым разбиением на группы служит неинтервальное разбиение;

(¿у) В случае ЕЕЕ указано конкретное расселение, для которого существует коалиционно устойчивое, но не существует миграционно устойчивого разбиения;

(у) В случае ЕЕЕ указано конкретное расселение, для которого, наоборот, существует миграционно устойчивое, но не существует коалиционно устойчивого

1,2,3,4,5,6,7

I_I

-4 0

разбиения (как следствие, можно сделать вывод о том, что понятия миграционной и коалиционной устойчивости логически независимы друг от друга);

(у1) В случае РЕС с выбором произвольной медианы из отрезка медиан всегда существует интервальное коалиционно устойчивое разбиение на группы для равномерного расселения;

(то) В случае ГЕС с выбором произвольной медианы из отрезка медиан всегда существует интервальное коалиционно устойчивое разбиение на группы для всех расселений XI,...,х„ при п < 4.

Глава 3 посвящена формализации и анализу случая Л — непрерывной постановки с плотностью. Необходимость такой постановки диктуется теми многочисленными приложениями рассматриваемой проблемы, которые описаны во введении. Учитывая сложности, связанные с "самой общей формулировкой" непрерывной постановки, мы всюду в главе 3 под случаем В понимаем следующий:

Абсолютно непрерывная постановка. Пространство игроков N совпадает с (выпуклым) замкнутым подмножеством X С И.'' при некотором Л (как правило, с каким-то простым — отрезком, шаром, самим пространством целиком). Предполагается заданной плотность расселения / : X —> 11+, строго положительная всюду на X.

Везде, кроме раздела 4.4, N = X предполагается компактным.9 Как и раньше, д обозначает стоимость открытия мощности. Постановка ЗМР становится интегральной, формализация угроз несколько видоизменяется.

Остановимся на формализации самой ЗМР10 (видоизменение формализации угроз приведено в тексте диссертации). Мета-задача формулируется для любого измеримого подмножества 5 С X положительной меры (именно такие подмножества объявляются в непрерывных постановках коалициями), и выглядит следующим образом:

Л о, М{„ 9 + 1в\\х-уШх)0х д + Мту<=х ¡3\\х- у\\Цх)йх ^ - -Щ^х-=-мШх-•

Для основного случая евклидовой нормы, при всех в, > 1 решение этой задачи достигается в единственной точке, называемой медианой коалиции 5, и обозначается

^Сложности, связанные с некомпактным (неограниченным) X — например, в важном частном случае X = К" — являются чисто математическими. В необходимом нам сюжете X = R2 они преодолены многими предшественниками, занимавшимися классическими задачами пространственного размещения, см. например, Bollobas, В. and N. Stern (1972), The optimal structure of market areas, Journal of Economic Theory 4, 174-179.

10C точки зрения нахождения оптимального решения рассмотренная задача является частным случаем задачи о дискретном приближении непрерывной меры, см. например, Э.О. Рапопорт (2012), О дискретном приближении непрерывных мер и некоторых приложениях, Сибирский журнал индустриальной математики, том 15, номер 3 (51), 99-110.

за m[5]. Потенциальную множественность медиан при d = 1 мы игнорируем, чтобы сосредоточиться на главном.11 ■

Теперь задача о размещении мощностей формулируется для любого компактного пространства N — X 6 Rd с положительной мерой в точности так же, как и раньше:

Min{Eli(Js¡ /(®)dr)c[Si]}, (10ч

{k-,* = {S1,...,Sk}:N = S1USiU...uSt¡},

с поправкой на замену |5¡| (количестваигроков в S() массой (мерой, /S| f(x)dx) коалиции S¡ (впрочем, в диссертации мы продолжаем массу коалиции S обозначать так же за |S|).

Миграционная угроза устойчивости в непрерывных постановках В и Г дополняется трудоёмким определением усиленной миграционной устойчивости (здесь мы не будем его приводить), которая в работе подвергнута анализу в одном частном случае, а именно, для равномерного расселения на прямой (f(x) = 1).

Глава 3 содержит два важных результата, а также несколько мелких (последние мы здесь не приводим). Первый результат формулируется так:

Теорема DEM при d = 1. Рассмотрим расселение игроков на отрезке [0,1], заданное распределением F(-), допускающим непрерывную и отделённую от нуля плотноть f(x) > е > 0. Тогда при любом п > 2 существует интервальное разбиение 7г = {5'],..., .?„} ровно на п невырожденных групп, являющееся миграционно устойчивым.

Доказательство этого результата использует лемму Никайдо-ГейлагДебрэ.

Второй из важных результатов получен в случае DSC для равномерного расселения на всей плоскости.

Существование коалиционно устойчивого разбиения на группы для любого дискретного расселения на прямой доказано предшественниками (об этом было сказано выше). Совершая предельный переход, можно то же самое утверждать для постановок DSC и TSC на прямой. Однако интересна и сама характеризация устойчивых решений — какие векторы (функции для континуальной постановки) распределения издержек лежат в ядре?

В общем случае это сделано с привлечением методов двойственности в линейном программировании.12 Но имеются и конкретные вычисления для наиболее важных примеров расселений. В случае равномерного расселения на прямой имеется такой результат:13 единственной коалиционно устойчивой функцией распределения издержек

"Договорившись о том, что в случае целого отрезка медиан в качестве решения задачи всегда берётся середина последнего.

12См., например, наш обзор Le Bretón М., Moreno-Ternero J. D., Savvateev A., and S. Weber (2013), Stability and Fairness in Modela with a Múltiple Membership, International Journal of Game Theory 42 (3), 673-694.

"Dreze, J., Le Bretón, M. and S. Weber (2007), Rawlsian Pricing of Access to Public Facilities: a Unidimensional Illustration, Journal of Economic Theory 136, 759-766.

является правило Ролса — "Всё собрать и поделить". (Заметим, что выше, при определении принципа Ролса мы потребовали, чтобы в каждой группе общие издержки делились поровну, а здесь то же самое достигается при наложении требования коалиционной устойчивости!)

Следуя общей логике последней процитированной статьи, в диссертации представлен анализ равномерного расселения на плоскости.

Решение соответствующей задачи о многомерном размещении хорошо известно:14 плоскость дробится на правильные одинаковые шестиугольники, размер которых определяется величиной д (для транспортных издержек, совпадающих с евклидовым расстоянием). А вот с коалиционно устойчивыми схемами распределения платежа возникает следующий эффект:

Теорема DSC на евклидовой плоскости. Множество векторов распределения издержек, коалиционно устойчивых для равномерного расселения на плоскости — пустое.

Иными словами, уже при расселении на плоскости парировать коалиционные угрозы не удаётся даже для простейшего случая равномерного расселения.

Так как мы живём, в первом приближении, на плоскости, и многие города с определённой долей правдоподобия можно считать заселёнными равномерно и "очень большими", то данный результат может потенциально настораживать. Однако следующие два соображения надо иметь в виду.

Во-первых, метрика (то есть способ измерения расстояний) в любом городе далёка от евклидовой. В городе, устроенном по принципу пересечения параллельного пучка улиц типа "север - юг" и пучка улиц типа "запад - восток", более правдоподобна "манхэттэнская" метрика, названная так из-за описанного выше расположения улиц в Манхэттэнском районе города Ныо-Йорка.15 В этой метрике, как явствует из результатов, полученных недавно и поэтому не вошедших в текст диссертации, множество ядерных распределений непусто.

Во-вторых, и в евклидовой ситуации "зазор" между оптимальностью разбиения на группы и его коалиционной устойчивостью невелик. Остановимся подробнее на последнем наблюдении.

Представим себе, что часть издержек несёт в случае подчинения "шестиугольному порядку" государство, а при образовании отклоняющейся группы людей эта часть издержек не возмещается. Возникает вопрос: насколько большой процент издержек нужно компенсировать, чтобы никакая группа не представила коалиционной угрозы устойчивости оптимального шестиугольного разбиения?

"Например, Morgan, F. and R. Bolton (2002), Hexagonal economic regions solve the location problem, The American Mathematical Monthly 109 (2), 165-72, а также уже процитировалпую статью Bollobas, В. and N. Stern (1972).

15B России такую метрику можно было бы назвать "Екатеринбургской".

Для ответа на поставленный вопрос введём новое понятие.

Определение DSC - R Регулярной функцией (правилом) распределения издержек называется произвольное отображение tu : R2 —» R, инвариантное относительно любых сдвигов шестиугольной сетки. Правило называется 6-ядерным, если для любой коалиции S S R2 (имеющей конечную меру |S|) выполнено следующее неравенство:

(1 - S) [ w(x)dx < c[S], (11)

JS

где c[S], напомним, является решением метагзадачи (9) в абсолютно непрерывной постановке.

Для формулировки второй основной теоремы главы 3 надо ввести ешё одно обозначение. А именно, за с* мы будем обозначать средние издержки функционирования плоскости, разбитой на оптимальные шестиугольники. Иными словами с* = с[Н*], где Я* обозначает типичный шестиугольник сетки. Тогда имеет место следующая теорема:

Теорема о приближённой устойчивости. Обозначим за S' точную нижнюю грань тех 5, при которых существуют 6 -ядерные способы распределения издержек. Справедливы следующие утверждения:

(i) 6* = 1- , где В* — круг на плоскости с минимальным значением с[В\ среди всех кругов % (то есть круг оптимального радиуса);

(ii) á* и 0.0018 то есть пренебрежимо мало — можно считать, что на плоскости ядро приближённо непусто.

(ш) С точностью до меры ноль существует единственный способ г(-) распределения издержек, являющийся 5*-ядерным. Этот способ является Ролсовским, то есть правилом выравнивания издержек: Vx 6 R2 r(i) н с*.

Доказательство первого пункта теоремы базируется на теореме Фубини о перестановочности операторов интегрирования; второй пункт — простое вычисление, а вот доказательство последнего утверждения весьма нетривиально. Оно зиждится на достаточно тонких построениях из теории меры и измеримых множеств.

Четвёртая глава посвящена постановке Т с конечным числом типов игроков, или, как мы его называем, "случаю нескольких городов". Положим N = Ij,l¡.. .U/n , где каждый отрезок Ii имеет длину, или массу a¡). Каждый "город" i обладает локацией x¡ е RJ.

Так как описываемая постановка в литературе по ЗМР вводится впервые, то остановимся здесь на модификации классической постановки задачи многомерного размещения, связанной с этой постановкой. Требуется открыть конечное число пунктов

(мощностей), в точках подмножества К С Rd, и приписать к ним жителей всех городов самым экономным образом:

Min [д\К\ + £¡=i.....„ Zy€K tfllr, - j,||},

{К с Rá; MW*}. 1 }

Минимум в (12) берётся среди всех вариантов выбора центров обслуживания, а также всех способов {/i^Jie^yeif} разбивки каждого из кластеров однотипных игроков между центрами (с условием, что для любого типа г — 1 ,...,п должно быть выполнено балансовое условие /А — ai )•

Как и в остальных двух вариантах постановки задачи, нам потребуется переформулировать ЗМР в "коалиционном формате". Оказывается, что в сюжете с несколькими типами игроков целые широкие классы коалиций получаются всецело эквивалентными друг другу (как и целые классы разбиений). А именно, для исчерпывающего описания шаблона коалиции достаточно указать, сколько игроков каждого типа туда вошло. Введём соответствующую терминологию.

Определение Т: (i) Коалицией (синоним: группой) игроков называется любое измеримое подмножество S С N положительной меры. Каждой коалиции S ставится в соответствие коалиционный шаблон {ßi,...,ß„) — набор из п неотрицательных чисел ¿i¡ = A[Sfl [0, ck¿]] , представляющих собой численность (меру Лебега) представителей соответствующих типов 1,..., га в группе S. Любая группа (коалиция), приводящая к данному набору численностей, называется реализацией коалиционного шаблона (pi,..., рп) ;

(ii) Разбиение тт в сюжете Т с конечным числом типов игроков отождествляется с матрицей

K}i=l.....п; а=1.....* (13)

коалиционных шаблонов к штук групп, входящих в разбиение; при этом, конечно, требуется, чтобы

Vt = l,...,n = (14)

а—1

Теперь ЗМР, как и раньше в главах 1 и 3, может быть записана в два этапа. Сначала сформулируем задачу о поиске наиболее экопомного способа поставки общественного блага для потребителей из произвольной группы S, реализованной через коалиционный шаблон (/íj, ..., fin), то есть задачу Штейнера:

с[5] - ф] = MinxeX° + -Д + ttll* -*!l, (15)

£¿=i fr Ei=i IM

В решении задачи определяется величина c[S] — средние суммарные издержки членов группы S при оптимальном выборе блага. Множество М[£] решений этой

задачи называется, как и в предыдущих сюжетах, множеством медиан группы 5, или шаблона (ßlt... ,ß„). Множество медиан может, как и в дискретных постановках, не быть одноточечным (в работе приводится полная характеризация этого множества, в

зависимости от расположения локаций, {ii}i=i.....п и набора численностей каждого из

типов, {ai}i=li...in).

Также, по аналогии с предыдущими главами, мы будем обозначать численность (массу) коалиции S за . В сюжете нескольких типов имеем |5| = /¿,.

После этого мы можно переформулировать ЗМР для случая конечного числа типов игроков:

мы {t,LM + ■■■+Mßl • • •, /01}, .

(K}i=i..........Vt = l,...,n Ej=i/*? = <*}>

где минимум берётся по всем матрицам, каждая строка которых представляет одну коалицию, а количество строк не является фиксированным: при поиске минимума перебираются все значения к = 1,..., п (легко понять, что любое к > п неоптимально ни при каком выборе матрицы ß).

В главе далее даются определения миграционной и коалиционной устойчивости, которые практически дословно переписываются из предыдущей главы, но с учётом новых реалий. Основным результатом четвёртой главы является полная классификация расселений с двумя городами с позиции коалиционной устойчивости (постановка ТЕС; любое такое расселение называется "биполярным миром"). Конкретно:

Теорема об устойчивости для случая ТЕС с двумя типами игроков. Спраг ведливы следующие утверждения (где за а и b обозначены численности городов, а > Ь > 0):

(i) Если коалиционно устойчивое разбиение биполярного мира существует, то устойчивым будет одно из трёх конкретных разбиений: союз {(а, 6)}, федерация {(а, 0); (0,6)} или дробное разбиение {(а — Ь, 0); (Ь, Ь)}. При а = Ь устойчивое разбиение существует, и им обязательно является одно из двух конкретных разбиений: федерация {(Ь, 0); (0,6)} или союз {(6, Ь)};

(ii) При некоторых значениях параметров (а, Ь) устойчивых разбиений не существует-,

(iii) При некоторых значениях параметров (а, Ь) единственным устойчивым разбиением служит дробное разбиение {(а — Ъ, 0); (Ь, 6)} .

С учётом симметрий в постановке задачи, биполярный мир полностью характеризуется размером каждого города, при условии, что g = 1, и что б'олыпий город находится в точке 0 на обычной прямой, а меньший — в точке 1. Полная классификация изображена ниже на рисунке 2, где по осям расположены численности городов (для определённости, большой город по оси абсцисс). Зоны в фазовом пространстве (пространстве параметров)

задачи помечены буквами, указывающими на то, какое из трёх конкретных разбиений является в соответствующей зоне устойчивым (или же на то, что устойчивых разбиений в данной зоне нет).

Ь

Рисунок 2. Зоны устойчивости трёх базовых видов разбиений.

В заключении, после краткого обзора полученных в диссертации результатов, приведён целый ряд примеров постановок, не вошедших в принятую в работе классификацию, но представляющихся автору достаточно важными. В некоторых случаях в них уже имеются определённые результаты, но в большинстве своём они представляют собой темы для будущих исследований.

Основные научные публикации по теме диссертационного исследования

Публикации в журналах, включённых ВАК Министерства образования и науки России в перечень ведущих журналов и изданий, рекомендованных для публикации основных результатов диссертационных исследований на соискание учёных степеней кандидата и доктора наук:

1. Савватеев А.В. Коалиционная устойчивость "биполярного мира". // Журнал Новой Экономической Ассоциации. 2013. № 17. С. 10-44. (2,1 п.л.)

2. Савватеев А.В. Миграционно устойчивая организация одномерного мира: теорема существования решепия. // Известия Иркутского Государственного Университета, Серия "Математика". 2013, том 6 (2). С.58-69. (0,69 п.л.)

3. Савватеев А. В., Кукушкин Н. С. Ординальная сравнительная статика: непрерывный случай. // Экономика и математические методы. 2009. JV»45(1). С. 83-86. (0,19 п.л., вклад автора - 0,09 п.л.)

4. Вебер Ш., Габжевич Дж., Гинзбург В., Савватеев А. В., Филатов А. Ю. Языковое разнообразие и его влияние на экономические и политические решения. // Журнал Новой экономической ассоциации. 2009. №3-4. С. 28-53. (1,58 п.л., вклад автора - 0,32 п.л.)

5. Dreze, J., Le Breton, M., Sawateev, A. and S. Weber. Almost subsidy-free spatial pricing in a multidimensional setting. // Journal of Economic Theory. 2008. Vol. 143. P. 275-291. (1 п.л., вклад автора - 0,25 п.л.)

6. Bogomolnaia A., Le Breton M., Sawateev, A., and S. Weber. Stability of jurisdiction structures under the equal share and median rules. // Economic Theory. 2008. Vol. 3. P. 523-543. (1,25 п.л., вклад автора - 0,32 п.л.)

7. Bogomolnaia, A., Le Breton, M., Sawateev, A. and S. Weber. Heterogeneity Gap in Unidimensional Spatial Models. // Journal of Public Economic Theory. 2008. Vol. 10. P. 455-473. (1,13 п.л., вклад автора - 0,28 п.л.)

8. Bogomolnaia A., Le Breton M., Sawateev, A., and S. Weber. Stability under unanimous consent, free mobility and core. // International Journal of Game Theory. 2007. Vol. 35. P. 185-204. (1,2 п.л., вклад автора - 0,3 п.л.)

9. Polishchuk L. I., and A. V. Sawateev. Spontaneous (non)emergence of property rights. // Economics of Transition. 2004. Vol. 12, Issue 1. P. 103-127. (1,5 п.л., вклад автора -0,75 п.л.)

10. Савватеев А. В. Оптимальные стратегии подавления коррупции. // Экономика и математические методы. 2003. №39(1). С. 62-75. (0,81 п.л.)

11. Magnus J. R., Polterovich V. M., Danilov D. L., and A. V. Sawateev. Tolerance of cheating: an analysis across countries. // Journal of Economic Education. 2002. Vol. 33, issue 2. P. 125-135. (0,62 п.л., вклад автора - 0,15 п.л.)

12. Le Breton M., Moreno-Ternero J. D., Sawateev A., and S. Weber. Stability and Fairness in Models with a Multiple Membership. // International Journal of Game Theory. 2013. Vol. 42, issue 3. P. 673-694. (1,2 п.л., вклад автора - 0,3 п.л.)

13. Bogomolnaia, Л., Le Breton, M., Sawateev, A. and S. Weber. The egalitarian sharing rule in provision of public projects. // Economics Bulletin. 2005. Vol. 8 (11). P. 1-5. (0,25 п.л., вклад автора - 0,06 п.л.)

Публикации в иных научных изданиях:

14. Sawateev, A.V. Uni-dimensional models of coalition formation: non-existence of stable partitions / A.V. Sawateev. // Moscow Journal of Combinatorics and Number Theory. 2012. V. 2, Issue 4. P. 49-62. (0,75 п.л.)

15. Sawateev A. Achieving stability in heterogeneous societies: multi-jurisdictional structures and redistribution policies. // EERC Working Paper. 2003. # 04/13E, Moscow: EERC. (1,88 п.л.)

16. Le Breton M., Moreno-Ternero J.D., Sawateev A., Weber S. Stability and fairness in models with a multiple membership. // CORE Discussion Paper. 2010/79. (3 п.л., вклад автора - 0,75 п.л.)

17. Dreze, J., Le Breton, M., Sawateev, A. and S. Weber . "Almost" subsidy-free spatial pricing in a multi-dimensional setting. // CORE discussion paper. 2007/47. (1,35 п.л., вклад автора — 0,35 п.л.)

18. Bogomolnaia, A., Le Breton, M., Sawateev, A. and S. Weber. Heterogeneity Gap in Unidimensional Spatial Models. // CORE Discussion Paper. 2006/36. (1,56 п.л., вклад автора - 0,39 п.л.)

19. Bogomolnaia A., Le Breton M., Sawateev, A., S. Weber. Stability under unanimous consent, free mobility and core. // CORE Discussion Paper. 2006/7. (1,25 п.л., вклад автора - 0,32 п.л.)

20. Bogomolnaia, A., Le Breton, M., Sawateev, A. and S. Weber. Stability of Jurisdiction Structures under the Equal Share and Median Rules. // CORE Discussion Paper. 2005/32. (1,5 п.л., вклад автора - 0,38 п.л.)

21. Bogomolnaia, A., Le Breton, M., Sawateev, A. and S. Weber. The Egalitarian Sharing Rule in Provision of Public Projects. // CORE Discussion Paper. 2005/24. (0,38 п.л., вклад автора - 0,09 п.л.)

22. Le Breton M., Moreno-Ternero J. D., Sawateev A., Weber S. Stability and Fairness in Models with a Multiple Membership. // IDEI Working Paper. 2012. No. 715. (3 п.л., вклад автора - 0,75 п.л.)

23. Le Breton M., Makarov V., Sawateev A., Weber S. Multiple Membership and Federal Structures. // IDEI Working Papers. 2007. No. 491. (0.6 п.л., вклад автора - 0.15 п.л.)

24. Dreze, J., Le Breton, M., Sawateev, A. and S. Weber. "Almost" Subsidy-EYee Spatial Pricing. // IDEI Working Papers. 2006. No. 423. (1.2 п.л., вклад автора - 0.3 п.л.)

25. Bogomolnaia A., Le Breton M., Sawateev, A., S. Weber. Stability under unanimous consent, free mobility and core. // IDEI Working Papers. 2006. No. 413. (1,25 п.л., вклад автора - 0,32 п.л.)

26. Bogomolnaia, A., Le Breton, M., Sawateev, A. and S. Weber. Heterogeneity Gap in the Stable Jurisdiction Structures. // IDEI Working Papers. 2006. No. 412. (1,56 п.л., вклад автора - 0,39 п.л.)

27. Bogomolnaia, A., Le Breton, M., Sawateev, A. and S. Weber. Strong Stability in Jurisdiction Formation. // IDEI Working Papers. 2005. No. 365. (1.2 п.л., вклад автора - 0.3 п.л.)

28. Bogomolnaia, A., Le Breton, M., Sawateev, A. and S. Weber. The Egalitarian Sharing Rule in Provision of Public Projects. // IDEI Working Papers. 2005. No. 364. (0,38 п.л., вклад автора - 0,09 п.л.)

29. Bogomolnaia, A., Le Breton, M., Sawateev, A. and S. Weber. On Heterogeneous Size of Stable Jurisdictions. // IDEI Working Papers. 2005. No. 363. (1,56 п.л., вклад автора-0,39 п.л.)

30. Bogomolnaia A., Le Breton M., Sawateev, A. and S. Weber. Stability of Jurisdiction Structures under the Equal Share and Median Rules. // IDEI Working Papers. 2005. No. 362. (1,5 п.л., вклад автора - 0,38 п.л.)

31 Le Breton M., Makarov V., Sawateev A., Weber S. Multiple Membership and Federal Structures. // FEEM Working Paper. 2008. No. 41. (0.6 п.л., вклад автора - 0.15 п.л.)

32. Dreze, J., Le Breton, M., Sawateev, A. and S. Weber. "Almost" Subsidy-FVee Spatial Pricing. // Fondazione Eni Enrico Mattei Working Papers. 2007. No. 68. (1.2 п.л., вклад автора - 0.3 п.л.)

33. Bogomolnaia, A., Le Breton, M., Savvateev, A. and S. Weber. Heterogeneity gap in stable juridiction structures. // Discussion Papers (ECON - Département des Sciences Economiques).2006. No. 19. (1,56 п.л., вклад автора - 0,39 п.л.)

34. Bogomolnaia A., Le Breton M., Savvateev, A., S. Weber. The Egalitarian Sharing Rule in Provision of Public Projects. // NOTA DI LAVORO 39.2005, in: Fondazione Eni Enrico Mattei Working Paper Series. # 2005.39. (0,25 п.л., вклад автора - 0,06 п.л.)

35. Remizov I.D., and A.V Savvateev (2012) " D[Maximum] = Р[Лгдтахгтит]", Intellectual Archive, 18.08, ID#612, ISSN1929 - 1329 (0,15 п.л., вклад автора - 0,08 п.л.)

Избранные тезисы докладов на конференциях:

36. Le Breton М., Makarov V., Savvateev Л., Weber S. Multiple membership and federal structures. // Contribution to game theory and management. Collected papers presented on the International Conference Game Theory and Management. SPb.: Graduate School of Management. SPbSU. 2007. P. 286-293. (0,44 п.л., вклад автора - 0,11 п.л.)

37. Le Breton M., Makarov V., Savvateev A., Weber S. Multiple membership and federal structures. // Системное моделирование социально-экономических процессов. Труды 31-й Международной научной школы-семинара. Воронеж. 1-5 октября 2008 г. Воронеж: Издательсксьполиграфический центр Воронежского государственного университета. 2008. Т. 1. С. 112-119. (0,44 п.л., вклад автора - 0,11 п.л.)

38. Bogomolnaia, A., Le Breton, М., Savvateev, A. and S. Weber. Stability of a bi-polar world. // Равновесные модели в экономике и энергетике: труды XIII Байкальской международной летней школы-семинара «Методы оптимизации и их приложения». Иркутск: Институт систем энергетики им. Л. А. Мелентьева СО РАН. 2005. С. 138-142. (0,25 п.л., вклад автора - 0,06 п.л.)

39. Jle Бреттон М., Вебер ILL, Мусатов Д., Савватеев А. Теория социального взаимодействия. // Труды 33-й Международной научной школы-семинара, Звенигород. 1-4 октября 2010 г. Воронеж: Издательско-полиграфический центр Воронежского государственного университета. 2010. С. 281-282. (0,13 п.л., вклад автора - 0,03 п.л.)

40. Ле Бретон М., Всбер Ш., Мусатов Д., Савватеев А. Коалиционно и Миграционно устойчивые разбиения на клубы. XI международная научная конференция по проблемам развития экономики и общества: В 3 кн. / отв. ред. Е.Г.Ясин. М.: Изд. дом Высшей школы экономики. 2011. Кн. 1. С. 441-447. (0,38 п.л., вклад автора -0,09 п.л.)

Соискатель считает своим приятным долгом поблагодарить своего научного консультанта, профессора Южного Методистского Университета (Даллас, США) Шломо Вебера за плодотворную совместную работу в течение последних десяти лет над темами, так или иначе связанными с диссертационным исследованием.

Савватеев Алексей Владимирович

ЗАДАЧА МНОГОМЕРНОГО РАЗМЕЩЕНИЯ И ЕЁ ПРИЛОЖЕНИЯ: ТЕОРЕТИКО-ИГРОВОЙ ПОДХОД

Специальность 08.00.13 - Математические и инструментальные методы экономики

Автореферат

диссертации на соискание учёной степени доктора физико-математических наук

Подписано к печати 13.11.2006. Формат 60 х 84 / 16 Усл. печ. л. 1. Заказ № Тираж 150 экз.

Отпечатано полиграфическим участком ИСЭМ СО РАН 664033, Иркутск, ул. Лермонтова, 130 Подписано в печать: 28.08.2013

Диссертация: текстпо экономике, доктора физико-математических наук, Савватеев, Алексей Владимирович, Москва

РОССИЙСКАЯ АКАДЕМИЯ НАУК

ЦЕНТРАЛЬНЫЙ ЭКОНОМИКО-МАТЕМАТИЧЕСКИЙ ИНСТИТУТ

05201351448 На правах рукописи

удк 513Я

Савватеев A.B.

ЗАДАЧА МНОГОМЕРНОГО РАЗМЕЩЕНИЯ И ЕЁ ПРИЛОЖЕНИЯ: ТЕОРЕТИКО-ИГРОВОЙ ПОДХОД

08.00.13 - Математические и инструментальные методы экономики

Диссертация на соискание ученой степени доктора физико-математических наук

Научные консультанты:

академик В.Л.Макаров профессор Шломо Вебер

Москва 2013

Оглавление

0 Введение 7

0.1 Описание изучаемой проблемы......................................7

0.1.1 Постановка задачи: формальная модель....................7

0.1.2 На стыке дисциплин.....................10

0.1.3 Фундаментальный конфликт, изучаемый в работе, и его

конкретные воплощения...................11

0.1.4 Союз постулата Тьебу и принципа медианного избирателя 14

0.2 Формализация конфликта: ИРЬР и ЗМР.............18

0.2.1 Постановка задачи ОТЬР и переход к ЗМР........18

0.2.2 Конкретная реализация ЗМР: география, вкусы, взгляды 20

0.2.3 Подробнее о поставке клубных благ............22

0.2.4 Две трактовки задачи: дробная и неделимая.......23

0.2.5 Странообразование (модель Алесины и Сполаоре) .... 26

0.2.6 Первичная формализация теоретико-игровых угроз ... 28

0.3 Обзор полученных в работе результатов..............31

0.3.1 Краткое содержание следующих глав работы.......31

0.3.2 Основные результаты диссертационного исследования . . 35

0.4 Обзор литературы по смежным направлениям..........38

0.4.1 Вокруг иПР: дробная релаксация и зазор устойчивости 39

0.4.2 Обзор других родственных теорий и областей науки ... 42 0.4.3 Результаты, непосредственно примыкающие к полученным

в диссертационном исследовании..............48

1 Случай ^: дискретная (конечная) задача многомерного размещения 51

1.1 Постановка задачи в конечном случае...............52

1.1.1 Пояснения, термины и обозначения ............53

1.1.2 Переформулировка задачи .................56

1.1.3 Лемма о медиане.......................60

1.2 Теоретико-игровые угрозы миграционной природы в задаче ЗМР (постановка F).........................62

1.2.1 Об угрозах: вступление...................62

1.2.2 Три механизма распределения издержек: S,R,E .... 64

1.2.3 Случай F при d = 1: интервальные разбиения......66

1.2.4 Концепция миграционной устойчивости решения.....69

1.3 Миграционные угрозы в задаче ЗМР (постановка F): устойчивых решений может не существовать..................72

1.3.1 Контрпример, случай FRM ................72

1.3.2 Теорема об интервальности, случай FEM........77

1.3.3 Контрпример, случай FEFM (центральная медиана) . 79

1.4 Миграционные угрозы в задаче ЗМР на прямой: две теоремы существования............................81

1.4.1 Случай FEFM, равномерное расселение.........81

1.4.2 Случай FEMM (принцип минимального насилия) ... 90

2 Случай F, продолжение: коалиционные угрозы 96

2.1 Теоретико-игровые угрозы коалиционной природы........97

2.1.1 Исторический экскурс: в погоне за устойчивостью на прямой.............................97

2.1.2 Ядро в форме разбиения на коалиции...........100

2.2 Результаты для постановок FRC и FSC ............102

2.2.1 Случай FRC: универсальная теорема существования . . 103

2.2.2 Случай FSC: основные определения и пояснения .... 106

2.2.3 Случай FSC: малые размерности (с? = 1,2).......109

2.3 Постановка FEC, подслучаи FE FC и FE MC.........110

2.3.1 Анализ случая FEM С для d = 1.............112

2.3.2 Контрпример для FE FC ("центральная медиана") . . .116

2.3.3 Обзор мелких результатов для постановок FEFC и

FEMC ............................117

2.4 Постановка FEAC, или универсальный контрпример......121

2.4.1 Случай FEAC: "самая общая теорема" пустоты ядра . . 121

2.4.2 Доказательство теоремы FEAC: начало.........124

2.4.3 Доказательство теоремы FEAC: продолжение......128

2.4.4 Окончание доказательства теоремы FEAC........132

3 Случай D: непрерывные расселения 136

3.1 Задача многомерного размещения для непрерывных расселений

и принципы распределения издержек...............140

3.1.1 Пререквизиты для ЗМР в случае D............140

3.1.2 Формализация ЗМР для постановки D..........143

3.1.3 Принципы распределения издержек для постановки D . 146

3.2 Теорема DEM о существовании устойчивого разбиения для произвольного расселения на отрезке ...............150

3.2.1 Определения для случаев DRM и DEM ........150

3.2.2 Постановка задачи на отрезке: ЗМР с фиксированным числом групп.........................152

3.2.3 Миграционная устойчивость на отрезке..........153

3.2.4 Доказательство основной теоремы.............156

3.2.5 Сравнение равновесного и оптимального решений .... 159

3.3 DSC-устойчивость при d = 2 ...................159

3.3.1 Коалиционная устойчивость в сюжете D.........160

3.3.2 Шестиугольные мозаики...................163

3.3.3 Круг как фигура, оптимальная для размещения.....165

3.3.4 0.0018-устойчивость.....................168

3.3.5 Начало доказательства: применение теоремы Фубини . . 170

3.3.6 Окончание доказательства: "торжество справедливости" . 174

3.4 С/[0,1]: анализ устойчивости в постановке DE..........177

3.4.1 Равномерный линейный мир: обзор проблематики .... 177

3.4.2 Локально устойчивое миграционное равновесие и близкие

концепции...........................179

3.4.3 Устойчивые групповые структуры для U[О,1] ......183

4 Случай Т: "несколько городов" 188

4.1 Введение в Т-сценарий: терминология, ЗМР, и определения теоретико-игровой устойчивости..................190

4.1.1 Описание постановки задачи в сюжете Т.........190

4.1.2 Задача многомерного размещения: Т-случай.......191

4.1.3 Переформулировка задачи .................192

4.1.4 Принципы распределения издержек в Т-сценарии .... 197

4.1.5 Свойства устойчивости разбиений в сюжете Т......198

4.1.6 Принципы TS, TR и ТЕ распределения издержек . . . 201

4.2 Коалиционная устойчивость "биполярного мира".........205

4.2.1 Обозначения и нормализация параметров.........206

4.2.2 Подготовительная работа и решение ЗМР.........207

4.2.3 Коалиционная устойчивость: первичный анализ.....208

4.2.4 Промежуточный результат.................213

4.3 Окончание анализа и графическое представление результатов . 220

4.3.1 Устойчивые разбиения при равной численности городов . 221

4.3.2 Условия устойчивости союза и федерации при а > Ь . . 222

4.3.3 Устойчивость "дробного" разбиения............225

5 Заключение 237

5.1 Описание полученных в работе результатов............238

5.1.1 Результаты в дискретной (конечной) модели.......238

5.1.2 Результаты в континуальной модели............240

5.2 Принципы устойчивости в континуальных сюжетах.......241

5.2.1 Виды угроз устойчивости и концепций решения.....243

5.2.2 Миграционная устойчивость в неатомарных играх .... 245

5.2.3 Метрические постановки и локальная устойчивость . . . 247

5.2.4 Коалиционная и смешанная устойчивость.........249

5.3 Гербарий сюжетов, окаймляющий кубик Рубика.........250

5.3.1 Мультипликативный нуклеолус...............250

5.3.2 Метрическое X........................251

5.3.3 Принцип частичной компенсации..............251

5.3.4 Всякая всячина........................252

5.4 Благодарности............................253

Литература 255

Глава О Введение

Многие научные результаты появляются на стыке двух или нескольких дисциплин, подходов и направлений. Это происходит от того, что на предмет исследования смотрят под совершенно разными, часто дополняющими друг друга углами зрения. Происходит нечто вроде "перекрёстного опыления". Настоящее диссертационное исследование, как видится автору, представляет собой как раз такой пример синтеза идей из разных областей знания.

0.1 Описание изучаемой проблемы

Исследование посвящено теоретико-игровому анализу оптимизационной задачи, называемой задачей многомерного размещения (ЗМР всюду в дальнейшем). Так как соискатель претендует на физико-математическую степень, уместно первым делом дать строгую формулировку изучаемой проблемы, а потом уже говорить о ряде её приложений.

0.1.1 Постановка задачи: формальная модель

Задан распределённый в в, -мерном нормированном пространстве

(нЛ 11-11)

спрос со стороны множества индивидов на доступ к определённому виду общественного блага. Благо поставляется в отдельных пунктах, мощностях, количество и места расположения которых нужно выбрать. Стоимость поддержания мощности равна д и не зависит от её адреса.

Эти мощности имеют вид чистого общественного блага, то есть любая из них способна полностью удовлетворить спрос всех людей. В то же

время существуют затраты прикрепления каждого индивида к любой из мощностей, равные измеренному в заданной норме расстоянию от адреса предъявления спроса со стороны индивида до мощности, в которой спрос индивида будет удовлетворяться.

Требуется выбрать места для открытия мощностей, а также прикрепить к открытым мощностям всех пользователей, минимальным по суммарной стоимости образом.

Для каждой открытой мощности рассмотрим группу её пользователей. Если внимание фокусируется на числе и композиции полученных групп, то для ЗМР используется синоним: задача формирования групп.

Выше не сказано, как именно выглядит "распределённый спрос", и не случайно. Дело в том, что с точки зрения разумных приложений (см. ниже) существуют три принципиально разных класса распределений спроса.

Первый — простейший, назовём его Р, когда в пространстве просто задано несколько точек (случай конечного числа игроков). Второй, Ю — абсолютно непрерывный, когда некое компактное подмножество пространства (или даже всё пространство целиком!) заселено людьми с непрерывной плотностью расселения. Такая постановка характерна для решения задачи обеспечения общественным благом жителей некоторого города.

Наконец, третий случай Т является логической комбинацией первых двух и предназначен для описания задачи поставки благ на некоторой большой территории, в пределах которой люди живут в нескольких населённых пунктах. Последний случай (с конечным числом типов игроков), насколько автору известно, вводится в научной литературе, посвящённой поставке клубных благ, впервые.

Основная часть диссертации делится на главы соответственно изучаемым в них классам постановок: главы 1 и 2 посвящены конечной постановке, глава 3 — непрерывным расселениям, глава 4 — расселениям с конечным числом типов. Помимо этих глав, в диссертации присутствует введение (текущая глава!) и заключение (про которое будет сказано ниже).

Вернёмся теперь к описанию изучаемой в диссертационной работе задачи.

Проблема, если её переформулировать на содержательном языке "анализа

конфликтов", состоит в следующем. Имеется многомерное "пространство конфликта", или разногласия, и заданное распределение участников конфликта внутри этого пространства (каждый участник располагается в той точке пространства, которая насыщает его предпочтения). Удаление от оптимальной точки влечёт издержки разногласия, измеряемые с помощью заданной нормы на пространстве конфликта.

Решением задачи ("допустимым планом") называется набор из нескольких точек пространства, или "вариантов разрешения конфликта", вместе с правилом соотнесения с каждым участником одного варианта, или точки разрешения конфликта, соответствующей лично ему. Каждый "вариант" стоит фиксированных денежных затрат.

Чем больше вариантов разрешения конфликта предложено, тем ниже суммарные издержки от разногласия, и одновременно тем выше затраты на обеспечение этих вариантов. В работе исследуются способы разрешения конфликтов, устойчивые по отношению к угрозам теоретико-игрового характера.

Теоретико-игровой аспект описанной проблемы состоит в том, чтобы протестировать получаемые в решении ЗМР сети пунктов открытия мощностей (вместе со способом прикрепления индивидуумов к мощностям) на устойчивость относительно миграционных и коалиционных угроз. При первом подходе устойчивости угрожает любой потребитель блага, желающий прикрепиться к иному, нежели предписанному ему, пункту. При втором подходе принимаются во внимание целые группы потребителей, координирующиеся с целью основания собственного "клуба" и открытия пункта удовлетворения спроса только для членов такого клуба. Более того, на устойчивость будут проверяться не только оптимальные решения, но и любые допустимые: иногда свойство устойчивости решения важнее свойства его оптимальности.

В настоящей главе дается описание ряда приложений задачи многомерного размещения (формирование стран, партий и клубов, а также обеспечение потребителей доступом к конкретным видам локального общественного блага).

0.1.2 На стыке дисциплин

Исследуемая в работе проблема, а именно вопрос устойчивости в задаче многомерного размещения по отношению к теоретико-игровым угрозам, лежит на стыке теории исследования операций, как её понимают "математики", и политэкономических дисциплин (в ключе современной западной "political economics").

В исследовании операций задача, как правило, ставится абстрактно и дискретно — задаётся конечное множество предъявителей спроса и конечное множество "вариантов открытия мощностей", в которых спрос может быть удовлетворён, а также вектор стоимостей открытия мощностей и матрица издержек прикрепления людей (предъявителей спроса) к мощностям. Требуется решить задачу обеспечения всех предъявителей спроса доступом к мощностям.

Эта задача называется Uncapacitated Facility Location Problem (UFLP), и про неё ниже во введении будет рассказано более подробно.

В политико-экономическом ключе ставятся вопросы устойчивости различных политических объединений, процессов формирования партий, клубов по интересам, аспектов "отделения регионов", миграции и т.п. В последние 20 лет эта теория стала популярной из-за её перехода на рельсы теории игр. Про историю становления современной политической экономики также будет рассказано в настоящей главе с соответствующими библиографическими ссылками.

Мостом между политической экономикой и теорией исследования операций служит предположение о том, что многообразие политического конфликта может быть "оцифровано" так называемым пространством разногласия, то есть конечномерным пространством, на котором заданы "вкусы и предпочтения" жителей мира/страны — участников изучаемого конфликта. Размерность пространства разногласия совпадает с количеством параметров разногласия. Каждый участник конфликта отождествляется с точкой в пространстве разногласия, а само пространство разногласия объявляется множеством X из задачи UFLP.

Если теперь предположить, что издержки от разногласия измеряются в некоторой норме на пространстве разногласия X = 11/*, а также что стоимость формирования одной группы составляет величину д в тех же единицах измерения, в каких "измеряется" разногласие, то мы придём к формулировке задачи многомерного размещения, приведённой выше.

Политэкономические аспекты проблемы напрямую приводят нас к вопросам теоретико-игровой устойчивости решений ЗМР.

Кроме того, полученные результаты можно интерпретировать и осмыслять в духе общей теории пространственного размещения, пионерами которого можно считать таких учёных, как А.Вебер, Кристаллер, Лёш, затем позже Стерн, Боллобаш, Морган, Болтон, Хаймович, Маньянти, Тотс и другие исследователи. ЗРМ можно интерпретировать и как задачу поставки клубных благ — бассейнов, медпунктов, полицейских участков, домов быта и др. в большом городе или в данной провинции (А.Васин, Д.Степанов, С.Вартанов, Ю.Сосина) или как задачу приближения непрерывных мер дискретными (как, к примеру, это делает Э.Рапопорт [27]).

Методологией настоящего исследования является современная теория игр — как коалиционная, так и стратегическая.

0.1.3 Фундаментальный конфликт, изучаемый в работе, и его конкретные воплощения

Лейтмотивом диссертационного исследования служит конфликт, присутствующий при организации и ведении практически любой коллективной деятельности. Это — конфликт между экономией от масштаба, во имя которой и происходит любая "коллективизация", с одной стороны, и растущими при объединении людей разногласиями, с другой.

Анализом этого конфликта занимались многие учёные, и в течение всей диссертационной работы у нас будут встречаться ссылки на те или иные ранее полученные результаты. Данный конфликт прослеживается во многих сюжетах, и ниже я привожу список наиболее интересных, с моей точки зрения, его проявлений.

Сюжет 1: Странообразоваиие, имперское строительство

Никогда ещё за всю историю планеты не существовало империи размером в целый мир. При этом империи часто росли до очень внушительных размеров (Британская имиерия в 1922 году составляла более 1/5 суши, Монгольская империя много веков назад занимала приблизительно столько же, затем Российская Империя и после неё СССР со знаменитой 1/6 частью суши, да и современная Россия занимает 1/8 часть суши, что весьма внушительно на фоне общей тенденции мира к измельчеишо).

Но чем больше империи росли, тем сложнее бывало улаживать явные или неявные конфликты внутри них — конфликты самой разной природы (религиозной, национальной, культурной, географической). Начиная с определённого размера, каждая империя становилась неуправляемой и распадалась (либо теряла часть своих территорий).

Несмотря на это, во все времена нации и народы стремились к имперскому строительству (исключение составляют, возможно, лишь последние 30-40 лет воинствующего сепаратизма). Это обусловлено целым рядом факторов, обсуждение которых является предметом других наук о социуме. Мы здесь можем лишь суммировать эти факторы в виде следующего конфликта, попытка модели�