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

• Автор: Савватеев, Алексей Владимирович
• Шифр специальности: 08.00.13
• Научная степень: Докторская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 268 с.

Оглавление
0 Введение
0.1 Описание изучаемой проблемы
0.1.1 Постановка задачи: формальная модель
0.1.2 На стыке дисциплин
0.1.3 Фундаментальный конфликт, изучаемый в работе, и его
конкретные воплощения
0.1.4 Союз постулата Тьебу и принципа медианного избирателя
0.2 Формализация конфликта: иГЬР и ЗМР
0.2.1 Постановка задачи РГРЬР и переход к ЗМР
0.2.2 Конкретная реализация ЗМР: география, вкусы, взгляды
0.2.3 Подробнее о поставке клубных благ
0.2.4 Две трактовки задачи: дробная и неделимая
0.2.5 Странообразование (модель Алеснны и Сполаоре)
0.3 Обзор полученных в работе результатов
0.3.1 Краткое содержание следующих глав работы
0.3.2 Основные результаты диссертационного исследования
0.4 Обзор литературы по смежным направлениям
0.4.1 Вокруг ОРЬР: дробная релаксация и зазор устойчивости 39 0.4.2 Обзор других родственных теорий и областей науки ... 42 0.4.3 Результаты, непосредственно примыкающие к полученным
в диссертационном исследовании
1 Случай Р1: дискретная (конечная) задача многомерного
размещения

1.1 Постановка задачи в конечном случае
1.1.1 Пояснения, термины и обозначения
1.1.2 Переформулировка задачи
1.1.3 Лемма о медиане
1.2 Теоретико-игровые угрозы миграционной природы в задаче
ЗМР (постановка Р)
1.2.1 Об угрозах: вступление
1.2.2 Три механизма распределения издержек: Р, Р, Р
1.2.3 Случай Р при с1 = 1: интервальные разбиения
1.2.4 Концепция миграционной устойчивости решения
1.3 Миграционные угрозы в задаче ЗМР (постановка Р): устойчивых
решений может не существовать
1.3.1 Контрпример, случай РДМ
1.3.2 Теорема об интервалыюсти, случай РРМ
1.3.3 Контрпример, случай РРРМ (центральная медиана)
1.4 Миграционные угрозы в задаче ЗМР на прямой: две теоремы
существования
1.4.1 Случай РРРМ, равномерное расселение
1.4.2 Случай ЕЕММ (принцип минимального насилия)
2 Случай Р, продолжение: коалиционные угрозы
2.1 Теоретико-игровые угрозы коалиционной природы
2.1.1 Исторический экскурс: в погоне за устойчивостью на прямой
2.1.2 Ядро в форме разбиения на коалиции
2.2 Результаты для постановок ЕНС и ЕЭС
2.2.1 Случай РЛС: универсальная теорема существования
2.2.2 Случай РРС: основные определения и пояснения
2.2.3 Случай РРС: малые размерности (с/ = 1,2)
2.3 Постановка РРС, подслучаи РРРС и ЕЕМС
2.3.1 Анализ случая ЕЕМС для с1
2.3.2 Контрпример для ЕЕ ЕС (“центральная медиана”)

2.3.3 Обзор мелких результатов для постановок FEFC и
FEMC
2.4 Постановка FEAC, или универсальный контрпример
2.4.1 Случай FEAC: “самая общая теорема” пустоты ядра
2.4.2 Доказательство теоремы FEAC: начало
2.4.3 Доказательство теоремы FEAC: продолжение
2.4.4 Окончание доказательства теоремы FEAC
3 Случай D: непрерывные расселения
3.1 Задача многомерного размещения для непрерывных расселений
и принципы распределения издержек
3.1.1 Пререквизиты для ЗМР в случае D
3.1.2 Формализация ЗМР для постановки D
3.1.3 Принципы распределения издержек для постановки D
3.2 Теорема DEM о существовании устойчивого разбиения для произвольного расселения на отрезке
3.2.1 Определения для случаев DRM и DEM
3.2.2 Постановка задачи на отрезке: ЗМР с фиксированным
числом групп
3.2.3 Миграционная устойчивость па отрезке
3.2.4 Доказательство основной теоремы
3.2.5 Сравнение равновесного и оптимального решений
3.3 DSC -устойчивость при d
3.3.1 Коалиционная устойчивость в сюжете D
3.3.2 Шестиугольные мозаики
3.3.3 Круг как фигура, оптимальная для размещения
3.3.4 0.0018-устойчивость
3.3.5 Начало доказательства: применение теоремы Фубини
3.3.6 Окончание доказательства: “торжество справедливости”
3.4 U[0,1]: анализ устойчивости в постановке DE
3.4.1 Равномерный линейный мир: обзор проблематики

Миграционных аспектов в этой главе я не касаюсь (случай TRM уже упоминался как решённый, а случай ТЕМ пока что, на сегодня, остаётся практически неизученным — хотя там и удалось, по аналогии с конечным случаем, построить потенциал, но последний пока “плохо себя ведёт”).
Коалиционная устойчивость в случае ТRC уже упоминалась как общий результат, а анализ случая TS = TSC по смыслу особо не отличается от анализа постановки FSC, о которой речь пойдёт ниже во введении.
Таким образом, остаётся лишь случай ТЕС, причём он, по аналогии с постановкой F ЕС, дробится далее на подслучаи. Только одна из его модификаций изучалась до сих пор. Конкретно, на сегодня проведён исчерпывающий анализ одного из подслучаев ТЕС для расселений с (не более, чем) двумя типами игроков.19 Результаты анализа этого подслучая, тем не менее, включают в себя доказательство длиной более 30 страниц, и завершают основную часть диссертационной работы. Там обнаруживаются весьма удивительные вещи (не буду говорить, какие — когда до конца дочитаете, тогда и узнаете!).
Заключительная глава 5 суммирует основные результаты, а также повествует о тех достижениях и планах, которые выходят за пределы логического “кубика Рубика” диссертационных постановок.
0.3.2 Основные результаты диссертационного исследования
Только что был упомянут некий таинственный “кубик Рубика”.
Этот кубик строится следующим образом: сперва класс расселений, один из трёх F,D,T, декартово домножается на идеологию, тоже одну из трёх — оптимизация (без буквы), миграционная устойчивость М, коалиционная устойчивость С. Затем все блоки, за исключением оптимизационных, ещё раз домножаются на один из трёх принципов распределения издержек S,R,E. Не все 27 ячеек кубика-рубнка различны (ибо оптимизационные блоки так и остаются без дробления), зато некоторые из ячеек с буквой
19В этом случае совершенно неважно, чему равно d и какая задана на Rd норма: всё рассмотрение фактически происходит вдоль прямой, соединяющей наши “два города”, а на прямой все нормы одинаковы и пропорциональны обычному модулю.