Содержание к диссертации
Введение 1
1 ГЛАВА 1. Дискретная Выпуклость 11
1.1 Дискретная выпуклость: основания 14
1.2 Гомогенизация S-классов: чистые системы 21
1.3 Конструкция 5-классов 26
1.4 Конструкция /-классов 28
1.5 Классы дискретной выпуклости с удвоением 33
1.6 Унимодулярные системы 34
1.7 Внешнее описание 7-полиэдров и *7-полиэдров . 44
1.7.1 Полезные факты 44
1.7.2 Опорные функции к 7^-политопам 46
1.7.3 Базовые полиэдры и обобщенные полиматроиды 50
1.7.4 *7-полиэдры 52
1.8 Внутреннее описание дискретно выпуклых множеств . 53
1.8.1 Касательные конуса 55
1.8.2 7^-выпуклые множества 56
1.8.3 Связь касательных (кокасательных) конусов 71-выпуклых множеств с опорными функциями . 58
1.8.4 7^-выпуклые оболочки 59
1.8.5 Касательные конуса *7-выпуклых множеств . 61
2 ГЛАВА 2. Дискретно Выпуклый Анализ 67
2.1 Вогнутые функции 67
2.1.1 Полиэдральные функции и их паркеты 69
2.2 "Р-вогнутые функции 74
2.3 Псевдовогнутые и целые функции 75
2.4 Дискретно-вогнутые функции : . 79
2.5 Целочисленная двойственность 80
2.6 Примеры 7^-вогнутых и *7-вогнутых функций 84
2.6.1 Внутренне описание функций из 1ZF(M,r) hj *тг^(м*,ж) 86
2.7 Полиматроидные функции 88
2.8 Свойство глобального обмена 91
2.9 Локальное свойство обмена 93
2.10 Полиматроидность и валовая заменимость 98
2.11 Паркеты вогнутых ВЗ-функций и супермодулярность . 101
2.11.1 Пошаговая валовая заменимость 106
ГЛАВА 3. Экономики с неделимыми товарами 109
3.1 Модель ПО
3.2 Дискретная выпуклость и существование равновесия . 113
3.3 Непрерывная часть проблемы существования 115
3.3.1 Случай трансферабельных предпочтений . 118
3.3.2 Доказательство Предложения 36 122
3.4 Двусторонний рынок 127
3.5 Модель двустороннего рынка 130
3.6 Теорема существования и структура равновесий . 134
3.6.1 Рынки с валовой заменимостью 139
3.6.2 Рынки с взаимно дополняющими продуктами . 140
3.7 Экономики с информационными товарами 141
3.8 Модель и определения 144
3.9 Свойства равновесий 147
3.9.1 Оптимальность 147
3.9.2 Существование равновесий 148
ГЛАВА 4. Функции выбора и выпуклые геометрии 154
4.1 Функции выбора и рационализируемость 155
4.2 Аксиома Плотта и абстрактная выпуклость 158
4.3 Функции выбора и операторы 165
4.4 Транзитивность, решетки выбора и чешуйчатость 168
Список литературы 175
Введение к работе
Выпуклость важна во многих областях математики и её приложений и до настоящего момента не теряет своей актуальности в оптимизации и математической экономике. Когда мы сталкиваемся с целочисленными задачами в оптимизации или с неделимыми объектами (товарами) в экономике, дискретно выпуклый анализ был бы очень уместен. Однако дискретность целочисленной решетки zn не позволяет ввести выпуклость в привычном виде: если подразумевать выпуклым подмножество, которое с любыми двумя точками а и Ь содержит и весь сегмент, соединяющий а и 6.
Мы можем овыпуклить любое подмножнство ІС2пи получить выпуклое подмножество со(Х) в к". Если множество X таково что все целые точки полиэдра со(Х) и есть X, то это первое приближение к дискретной выпуклости, и мы будем называть такие множества псевдовыпуклыми . С этим классом множеств не удается построить интересной теории дискретной выпуклости. Дело в том, что в размерности большей 1, в этом классе непересекающиеся множества могут быть неотделимы линейными функционалами. На уровне целых полиэдров это свойство неотделимости эквивалентно тому, что пересечение целых полиэдров может быть уже не целым. Поэтому приходится сужать класс псевдовыпуклых множеств чтобы получать дискретно выпуклые. Отметим сразу отличие нашей дискретной теории от классической (непрерывной): нет единого понятия дискретно выпуклого множества, есть понятие класса дискретно выпуклых множеств. Непересекающиеся множества из одного и того же класса разделяются (строго) некоторым линейным функционалом. С каждым классом дискретно-выпуклых множеств связан класс функций, так что выпуклая и вогнутая функции разделяются аффинной, если первая функция (поточечно) больше или равна второй. Подробно эти вопросы и Дискретно выпуклый анализ изложены в первых двух главах диссетрации.
Мы создавали нашу теорию не на пустом месте. Одним из первых примеров возможности существования выпуклого анализа в дискретной обстановке является теорема Франка [15] о разделении супермодулярной и субмодулярной функций на булевской решетке. Этот результат (усиленный для функций на дистрибутивных решетках) дал основу построения теории равновесия в экономиках с информационными товарами [37, 38, 40]. Разработанную технику мы применили к моделям экономик с неделимыми товарами и получили необходимое и достаточное условие существования равновесия в агрегированных терминах [39]. Для случая экономик с двумя потребителями мы предложили класс функций полезности - целые супермодулярные функции (в терминологии диссертации), для которых наше агрегированное условие существования выполнялось (отметим, что в [25] такие функции названы дискретно выпуклыми). В это же время появилась статья Муроты [29], в которой рассматривались полиматроидные функции и для этого класса функций строилась теория параллельная обычному выпуклому анализу. Оказалось, что класс полиматроидных функций дает еще один из примеров классов функций полезности, удовлетворяющих нашему необходимому и достаточному условию существования равновесия в моделях экономик с неделимыми товарами и деньгами ([8]).
В классах полиматроидных и целых супермодулярных функций возможность построения теории аналогичной выпуклому анализу основывалась на том, что области аффиности функций этих классов образовывали два подкласса псевдовыпуклых множеств - полиматроидных и кополиматридных, в которых любая пара непересекающихся множеств разделяются гиперплоскостью.
Это свойство отделимости непересекающихся множеств мы взяли для основы построения теории дискретной выпуклости и назва ли классом дискретной выпуклости любой подкласс псевдовыпуклых множеств, в котором непересекающиеся множества разделяются. На полиэдральном уровне (языке) это эквивалентно тому, что пересечение любых двух целых полиэдров класса является целым полиэдром, хотя это пересечение может быть полиэдром не из этого класса. При этом в таких классах хотелось бы иметь и еще несколько полезных свойств: замкнутость относительно целочисленных сдвигов, центральную симметрию, и что с каждым множеством из класса и все его грани являются множествами класса. Взяв прямое произведение одномерных псевдовыпуклых множеств, мы видим, что такие классы существуют. Но конечно этот пример далек от максимальности. Мы полностью охарактеризовали такие классы. Глава 1 посвящена описанию и конструированию этих классов. Основные результаты этой главы публикуются в [6] (частично в [8]). Мы показали, что классы дискретной выпуклости находятся в биективном соответствии с чистыми системами (полугруппы, образованные чистыми подгруппами). Чистые системы, порождаемые одномерными образующими, взаимнооднозначно соответствуют унимодулярным системам. Унимоду-лярные системы (или, что эквивалентно, регулярные матроиды, или вполне унимодулярные матрицы) хорошо известны в комбинаторной оптимизации и теории целочисленного программирования. По унимо-дулярной системе мы строим два класса. Один - S-класс, замкнутый относительно сложения (по Минковскому), получается в форме целых точек полиэдров, ребра которых параллельны векторам унимодуляр-ной системы; другой - 1-класс, замкнутый относительно пересечений и получается в форме целых точек полиэдров, грани максимальной размерности которых имеют нормали параллельные векторам уни-модулярной системы. Классы, замкнутые относительно пересечения и суммы, соответствуют очень простым унимодулярным системам, раскладывающимся в прямую сумму копий двумерных унимодуляр ных систем. Класс полиматроидов образует S-класс дискретной выпуклости, связанный с графической системой Ап, образованной векторами е{ — ej, ±ЄІ, i,j Є N, где Є{ - стандартный единичный г-ый базисный вектор в жп. Класс целых супермодулярных (кополиматро-идных) функций связан с этой же унимодулярной системой и образован множествами целых точек целых полиэдров, нормальные вектора к граням максимальной размерности которых имеют вид е — ej, ±ег-, i,j Є N. В этой же главе мы приводим внутреннее и внешнее описание множеств для унимодулярных классов дискретной выпуклости.
В Главе 2 мы развиваем дискретно выпуклый анализ. А именно, поскольку мы знаем как устроены классы выпуклых (дискретно) множеств в целочисленной решетке, мы можем рассматривать функции, паркеты которых состоят из элементов какого-нибудь класса дискретной выпуклости. (Паркет функции - разбиение ее области эффективности на клетки, являющиеся областями аффинности функции. Паркет - важное понятие для полиэдральных функций и ранее не исследовался в Выпуклом анализе.) Зафиксировав класс дискретной выпуклости, мы получаем класс функций. При этом S-классы множеств дают классы функций замкнутых относительно сложения, а 1-классы - замкнутых относительно свертки,-Мы показываем, что в этих классах выполняются теорема отделимости и двойственность Фенхеля. S-и 1-классы целозначных функций с одной и той же чистой системой двойственны. Подробно исследуются классы функций, относящиеся к унимодулярной системе Ап. Соответствующий S-класс функций связан с важным экономическим свойством валовой заменимости и состоит из функций с паркетами, образованными целыми полиматро-идами; 1-класс связан со свойством дополнительности и состоит из целых супермодулярных (субмодулярных) функций. Результаты этой главы опубликованы в [7, 43, 44, 8].
В Главе 3 приводятся применения дискретно выпуклого анализа к экономикам с неделимыми товарами. Коротко можно сказать так: заменяя Выпуклый анализ на Дискретно выпуклый можно параллельно получить почти все результаты из обычной равновесной теории моделей типа Эрроу-Дебре в моделях с неделимыми товарами. В начале мы приводим общую теорему существования в моделях с неделимыми товарами и деньгами и показываем, что все известные нам результаты о существовании равновесий в таких моделях получаются как следствия этой теоремы, связанные только с одним полима-троидным случаем. Затем мы применяем наш дискретно выпуклый анализ к моделям паросочетаний с множественным партнерством и показываем что известные нам результаты существования стабильных исходов в таких моделях являются частными случаями нашей общей теоремы и соответствуют Принципу Совместимости в крайней форме - Принципу валовой заменимости. Другой частный случай -Принцип полной дополнительности - ближе к экономикам с информационными (интеллектуальными) товарами. Такие модели с информационными товарами мы более подробно рассматриваем в заключении этой Главы. Основные результаты этой главы опубликованы в . [44, 8, 39, 37, 38, 40, 41, 42].
В литературе есть еще один подход к переносу понятия выпуклости в дискретную обстановку, связанный с исследованием свойств оператора замыкания. Хорошими обзорами такого рода работ является книги [90] и [75]. В главе 4 мы рассмотрим операторы замыкания с антиобменным свойством, известные также как абстрактные выпуклые геометрии. Мы показываем, что такие геометрии находятся в биективном соответствии с важным классом функций выбора, удовлетворяющих Аксиоме Плотта независимости от пути. Эта биекция следует из новой характеризации таких геометрии через свойства крайних точек [76]. Можно показать, что абстрактная выпуклость порождается одноточечными областями аффиности полиматроидных функ ций. Подход к исследованию функций полезности через абстрактные выпуклые геометрии не только позволяет получить новые характе-ризации ординальной рационализируемое™ и независимости от пути и усилить существующие, но и предлагает новый подход к анализу рационализируемое™. Это также оказалось полезным для исследования абстрактных выпуклых геометрий. Основные результаты этой главы опубликованы в [76, 77, 80].
Итак основными результатами диссертации являются:
1) построение новой теории "Дискретно выпуклый анализ";
2) применение этой теории к проблеме существования равновесий в моделях экономик с неделимыми товарами;
3) новый подход к анализу рационализуемости выбора.
