Дискретно выпуклый анализ и его применение к моделям экономик с неделимыми товарами тема диссертации по экономике, полный текст автореферата

Автореферат диссертации по теме "Дискретно выпуклый анализ и его применение к моделям экономик с неделимыми товарами"

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

КОШЕВОЙ Глеб Алексеевич

ДИСКРЕТНО ВЫПУКЛЫЙ АНАЛИЗ И ЕГО ПРИМЕНЕНИЕ К МОДЕЛЯМ ЭКОНОМИК С НЕДЕЛИМЫМИ ТОВАРАМИ

1

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

экономики

Автореферат диссертации

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

МОСКВА - 2003

N

Работа выполнена в Центральном экономико-математическом институте

Научный консультант - доктор физико-математических наук Данилов В.И. Официальные оппоненты:

доктор физико-математических наук Гришухин В.П.

доктор физико-математических наук Карзанов A.B.

доктор физико-математических наук, профессор Шананин A.A.

Ведущая организация - Вычислительный центр РАН

Защита состоится "_" _ 2003 г. в "_" часов на заседании

Диссертационного совета Д 002.013.02 ЦЭМИ РАН по адресу: 117418, Москва, Нахимовский проспект 47, ком. 520.

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

Автореферат разослан "_"__2003 г.

Ученый секретарь дисс. совета, кандидат физико-математических наук

РАН

Борисова С.В.

ооЗ-А

8711

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

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

Джон фон Нейман, говоря о логике, указывал, что математик, обращаясь к логике, испытывает неудобство, йотому что вся логика крутится вокруг дискретных структур, с которыми человеку трудно общаться. Ему го-•раздо легче, когда он видит перед собой что-то непрерывное. Другой пример неудобства дискретности - вопрос о существовании целочисленных решений какого-нибудь уравнения (или системы уравнений), например, знаменитая Теорема Ферма. Похожая задача о существовании акцессорных параметров, при которых все решения целые, например, уравнение Бюкерса-Цагира: (п+ 1)2и„+1 — Ап(п + 1)и„ + Впги„-1 = Аи„, где ио = 0, а А, В, А - акцессорные параметры. Пользуясь аналогией со словами о. Павла Флоренского о явлении идеи1, представляется справедливым утверждение, что трудность "дискретности" состоит в том, что для ее понимания необходимо "явление идеи".

К типу "дискретных" задач можно отнести и задачу о нахождении равновесия в экономиках с неделимыми товарами, то есть дискретными товарами, которые измеряются только целыми числами (самолеты, морские суда, дома и т.д.). Задача о нахождении конкуретного равновесия в таких экономиках похожа на задачу о нахождении акцессорных параметров (равновесных цен), для которых существует целочисленное решение уравнения равенства нулю избыточного спроса. В силу дискретности избыточного спроса, существование равновесия в моделях с дискретными товарами воспринималось как некое изумительное исключение. Пример несуществования был приведен Торнтоном еще в 1869 году. К работам-"исключениям", в которых приводились примеры экономик, в которых удавалось доказать существование конкуретного равновесия, можно отнести работы К.Анри, Т.Купманса и Бекмана, Л.Шепли и Г.Скарфа, Л.Шепли и М. Шубика, А.Рота, Д.Гейла и Л.Шепли, Д.Гейла, М. Квинзи, М.Канеко, Г.

1 "Это есть нисхождение горнего к дольнему и восхождение дольнего к горнему, соединение Неба и земли."

Спемсона (п них рассматривались булевские топярм и предполагалось, что агенты заинтересованы п потреблении не более одной единицы товара). В работе Л.Кслсо и В.Кроуфордя предложено рассмотреть агентов с »алово-заменимым спросом и при таком предположении доказано существование стабильных исходов. Позднее Ф.Гул и Э.Стакетги показали, что с валово-заменимым спросом существует и равновесие в булевской модели, при этом связь этого условия с предположением о заинтересованности не более чем в одном товаре, как в модели Квинзи, не было вскрыто. Другие примеры функций полезности для которых существуют равновесия, приведены в работах Кроуфорда и Кнорра, Бевия, Квинзи и Силвы, пан дер Лаана, Талмана и Яига, Янга. Однако фундаментальная причина существования равновесия в этих моделях осталась невыясненой. В работе |33| приведено необходимое и достаточное условие существования равновесия для случая экономик с транс<|>прабелм1мми полезностями (позднее это условие было получено Бихч&пдани и Мамером в булевской ситуации), однако оно было сформулировано в агрегированных терминах и вопрос о его расшифровке остался открытым. Другим примером дискретных экономик являются экономики информационных топароп, предложенных П.Л. Макаровым, и несколько позднее К.Эрроу. Товары в таких экономиках образуют решетку и удалось доказать существование равновесия, потребовав чтобы спрос удовлетворял условию дополнительности |35).

Оба условия - дополнительности и валовой заменимости - связаны с матро-идами и их обобщениями - полиматроидами. В многочисленных работах, среди которых отметим работы Д.Эдмонса, Л.Франка, Л.Ловаша, С.Фуджишике, М.М.Ковалева и его соавторов, Д.'Гонкиса, было показано, что ранговые функции матроидов и их обобщение - суб/сунермодулярные функции можно рассматривать как выпуклые/вогнутые функции па булевской решетке. К.Мурота показал, что функции, у которых области пффниости являются полиматроидами, также можно назвать вогнутыми. Позднее (|30|), было показано, что есть связь между функциями с валовой заменимостью и функциями с матроидпыми областями аффииости. Вопрос о существовании других вариантов "дискретной выпуклости" и построении общей теории оставался открытым.

Все вышесказанное, учитывая также недапнне появления дискретной выпуклости в исследованиях геометрии малых клеток Шуберта, комбинаторике,

разложении на неприводимые представлений СЬ{п), доказательстве гипотезы Хорна, позволяет сделать вывод об актуальности настоящей работы.

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

Методика исследования основана на клгебраических и комбинаторных методах, выпуклом анализе и теории конкурентного равновесия.

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

1. Введено понятие дискретной выпуклости, точнее классов дискретно-выпуклых множеств, их подклассов - Б-классов, замкнутых относительно сложения (по Минковскому), и 1-классов, замкнутых относительно пересечения.

2. Получена полная характеризация этих классов дискретной выпуклости.

3. По каждому классу дискретной выпуклости построен класс дискретно выпуклых/вогнутых функций на целочисленной решетке, для которого справедливы почти все центральные результаты обычного выпуклого анализа, при этом классы функций, построенных по Б-классам дискретной выпуклости, замкнуты относительно свертки, а по 1-классам - относительно суммы. Классы целозначных функций, отвечающих Э-классам и 1-классам одной и той же чистой системы, дуальны (по Фенхелю) друг другу.

4. Показано, что, заменяя обычный выпуклый анализ на дискретно-выпуклый, связанный с Б-классами дискретной выпуклости, можно строить общую теорию равновесий в моделях экономик с неделимыми товарами, а заменяя на дискретно выпуклый анализ, связанный с 1-классами, можно переносить общую теорию равновесий на модели экономик с информационными товарами.

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

Теоретическая и практическая значимость. Результаты диссертации могут

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

Апробация работы. Результаты диссертации докладывались на Международном математическом конгрессе (Берлин, Германия, 1998), 7-ом Всемирном Конгрессе Эконометрического общества (Токио, Япония, 1995), рабочем совещании "Рынки, топология и геометрия" (Филдсовский институт, Ватерлоо, Канада, 1994), 6-ом рабочем совещании "Общая теория равновесий" (Париж, Франция, 2000), Высшем исследовательском совещании "Математические теории распределения дискретных ресурсов: Равновесия, Паросочетания, Механизмы" (Истанбул, Турция, 2001), симпозиуме по исследованию операций (Бра-уншвайг, Германия, 1996), 4-ом международном собрании Общества по теории выбора и благосостоянию (Ванкувер, Канада, 1998), конференции по анализу ординальных и символьных данных (Брюссель, Бельгия, 2000), конференции по общественным экономикам (Париж, Франция, 2002), докладывались и обсуждались на семинарах ЦЭМИ РАН, ВЦ РАН, семинарах и коллоквиумах в университетах Амстердама, Маастрихта, Твенте, Тилбурга (Голландия), Билифельда, Бонна, Бремена, Гамбурга, Кельна, Саарбрюкена (Германия), Париж-1, Париж-4, Париж-б, Париж-7 (Франция), Колумбийском университете (США), Ватерлоо, Лаваль (Канада), и составляли основы миникурсов, прочитанных в университетах Тилбурга (Голландия, 2002), Париж-1, Париж-6 (Франция, 2001), Кельна (Германия, 1999).

Публикации. По теме диссертации опубликованы 17 работ (11 в соавторстве) общим объемом 14 п.л.

Структура и объем работы. Диссертация состоит из введения, четырех глав и списка литературы (содержащего 90 наименований) и изложена на 184 страницах машинописного текста.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Какие подмножества X целочисленной решетки (свободной абелевой группы) М = Z" можно было бы называть выпуклыми?

Довольно ясно, что X должно состоять из всех целых точек своей выпуклой оболочки со(Х). Такие множества с полиэдральными со(Х) мы будем называть псевдовыпуклыми и обозначать QC класс таких множеств. Однако этот класс слишком "большой": в классе QC не выполняется свойство отделения непересекающихся множеств. Без свойства отделения построить (дискретно) выпуклый анализ не удастся. Класс псевдовыпуклых множеств надо сузить, чтобы добиться выполнения отделимости непересекающихся множеств. Мы будем рассматривать обильные сужения. Класс множеств К. С QC называется обильным, если К. замкнут относительно а) сдвигов на целочисленный вектор, Ь) отражений и с) граней. В таком же смысле мы понимаем обильность классов полиэдров. Начнем со следующих эквивалентных отделимости свойств.

Предложение 1 Пусть класс К, С QC обилен. Тогда следующие свойства эквивалентны:

(Add) для любых множеств X,Y G К. множества X ± У псевдовыпуклы; (Sep) если множества X uY из 1С не пересекаются, тогда существует (целый) линейный функционал р : V —» R такой что р(х) > р(у) для любых xeX,yeY;

(Int) если множества X uY из К не пересекаются, тогда подиэдры со(Х) и co(Y) также не пересекаются;

(Edm) для любых X, У £ К полиэдр со{Х) Л со(У) целый.

Определение 1 Обильный класс К, С QC называется классом дискретной выпуклости (DC-класс), если в нем справедливо какое-нибудь свойство из Предложения 1.

В терминах целых полиэдров определение дискретной выпуклости формулируется следующим образом. Класс V целых полиэдров является полиэдральным классом дискретной выпуклости, если он обилен и выполняется следующий вариант условия Эдмондса:

(Edm') Пересечение любых двух полиэдров из класса V является целым полиэдром (хотя это пересечение может не быть в V).

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

Определение 2 Обильный класс 1С из псевдовыпуклых множеств называется S-классом, если X + У С АС вместе с любыми X, У € К..

В таких классах мы имеем автоматически X - У е QC для любых X, У 6 К, и, следовательно, всякий S-класс является DC-классом. На полиэдральном уровне, мы говорим, что класс является полиэдральным 5-классом, если он замкнут относительно сложения и выполняется свойство (Edm'). Отметим, что пересечение двух полиэдров из полиэдрального ,9-класса является целым полиэдром, однако, этот полиэдр может и не принадлежать этому 5-классу.

Определение 3 Обильный класс V целых подиэдров называется полиэдральным /-классом, если Р П Q € V с любыми P,Q 6 Р.

Ясно, что всякий /-класс является DC-классом, поскольку свойство (Edm') выполняется автоматически.

Для полного описания и построения DC-классов мы вводим специальные классы чистых подгрупп М (подгруппа S С М называется чистой, если фактор-группа M/S без кручения). Множество чистых подгрупп М не замкнуто относительно сложения, тем не менее оно содержит много нетривиальных подмножеств, замкнутых относительно сложения. Оказывается, что такие подмножества находятся в биективном соответствии с S-классами дискретной выпуклости. Итак,

Определение 4 Множество К, состоящее из чистых подгрупп М, называется чистой системой, если И замкнуто относительно сложения, то есть Б + 5' € и вместе с любыми 3,3' € Ы. Подгруппы в € Ы (или, если это ясно из контекста, соответствующие векторные подпространства К(5) С V) мы называем флэтами чистой системы 1Л.

С любым набором К псевдовыпуклых множеств, гомогенизацией К, мы называем следующий набор подгрупп М ,

и(К) = {г0рО,х е К},

где Хо(X) := г(Х — X) подгруппа М, порожденная элементами вида х — у с х, у 6 X, X С М.

Предложение 2 Пусть К, является Б-классом псевдовыпуклых подмножеств М. Тогда и (К.) является чистой системой.

Итак, чистые системы получаются посредством гомогенизации 5-классов. Теперь, обратно мы определим максимальный ¿'-класс "Рк(и, г) целых полиэдров по данной чистой системе и.

Определение 5 Пусть Ы некоторая чистая система. Полиэдр Р называется ¿/-выпуклым (или ¿/-полиэдром,/, если для любой грани .Р полиэдра Р линейное подпространство Щ(Р) := — Р) является флэтом Ъ1, или, что эквивалентно, П М е и.

Множество всех ¿/-полиэдров мы будем обозначать ~Рк(и) и подмножество целых ¿/-полиэдров будем обозначать ТК{и, Ъ). Из конструкции видно, что множество замкнуто относительно целых сдвигов, отражений и взятия граней. Поскольку сумма флэтов является флэтом, этот класс замкнут относительно сложения. Гомогенизация Т>к{и, Ъ) приводит нас опять к и. Ясно, что если гомогенизация обильного класса V содержится в 1А, то выполняется РсИ (Ы,г).

Теорема 1 Пусть Ы - чистая система. Тогда Т>к{и, г) является Б-классом целых полиэдров.

Обобщением теоремы Эдмондса о пересечении полиматроидов является следующее

Следствие 1 Пусть и - чистая система. Тогда пересечение любых двух целых И-полиэдров является целым полиэдром.

Построения /-классов во многом сходно с конструкцией построения 5-классов. Гомогенизация /-классов образует систему чистых подгрупп, ортогональную некоторой чистой системе. Это является характеризацией /-классов.

Определение 6 Множество V чистых подгрупп М называется чистой *-системой, если V замкнуто относительно пересечений и подгруппа Б + Б' -чиста для любых 5,5' € V.

Пусть С является некоторым /-кластом в М. Его гомогенизация - это набор

и(С) = [г,,^)^ е с}

подгрупп в М. Пусть £ - /-класс такой что А + А € С вместе с любым А € С. Тогда 14 (С) является чистой »-системой. Для набора И подгрупп М мы обозначаем 141 = {.9^, 5 € 14} набор ортогональных подгрупп в М', где 51 := (;» € М',р[я) = О V я € 5} обозначет ортогональную к 5 подгруппу в М\

Предложение 3 Пусть и некоторая чистая система в М и V - некоторая чистая *-система в М'. Тогда Ы' является *-системой о М', а Vх является чистой системой в М.

Пусть Б сТ пара флэтов из И1 таких что 5 имеет коразмерность 1 в Т. Тогда 5 разбивает Т на два полупространства, которые граничат по 5. Обозначим (5 : Т)* эти подпространства Т. Образуем следующее множество Ршп(1/). Оно сосгоиг из флэтов//1 и всех"полупроспрансгв" пида (Я : Т)*. Теперь мы строим полиэдры в V', беря конечные пересечения сдвигов элементов Рпт(//).

Определение 7 Пусть II - набор чистых подгрупп М. Полиэдр ф в V' называется »//-выпуклым (или »//-полиэдром^, если <2 получается как пересечение некоторых сдвигов некоторых элементов РНт(14).

Обозначим 'РНЧи) класс таких полиэдров и обозначим Тк'(Ы, г) подкласс полиэдров, которые получаются из целых сдвигов элементов Рпт(Ы). Класс "Рк'{и,Х) обилен и замкнут относительно пересечений. Однако, он может содержать не целые полиэдры. Если же Ы чиста, то этого не случается.

Теорема 2 Класс "РЛ* {14,1) состоит из целых полиэдров тогда и только тогда, когда Ы чистая система.

Когда мы рассмариваем полиэдры г), которые задаются пересечением

сдвигов элементов Рпт(1/) специального вида - полупространств в М", то есть вида (5 : Т)* с Т = М', мы, как частный случай Теоремы 2, получаем теорему Хоффмана-Краскала.

Итак, мы показали ключевую роль чистых систем в описании и построении классов дискретной выпуклости. Особый интерес представляют чистые системы, которые содержат много одномерных флэтов. В терминах 5-классов это означает, что соответствующие классы содержат много политопов. В терминах /-классов это означает, что соответствующие классы содержат много полномерных политопов. Точнее, мы интересуемся теми чистыми системами Ы, которые как полугруппы порождаются одномерными флэтами. Для таких систем нет надобности вводить флэты всех размерностей, достаточно рассматривать одномерные флэты. Эти флэты М имеют вид Ъг, где г - примитивный вектор М.

Определение 8 Множество И С М называется унимодулярным, если для любого подмножества В СИ подгруппа ЪВ С М является чистой. Унимоду-лярная система это пара (М, 72), где И. - унимодулярное множество в М.

Мы будем называть 72-флэтами (или просто флэтами, если не возникает путаница) подгруппы вида г(В), где В а И. Эти флэты образуют чистую систему, которую мы обозначим и{К). Унимодулярные системы это бескоординатное представление вполне унимодулярных матриц.

Важные примеры унимодулярных систем. Пример 1. Одномерные флэты г(е, - е}), е Ы, порождают чистая систему, обозначамую А(АГ). Множество векторов е, — е3, г,] € является унимодулярным множеством в (ж")*. Обозначим эту унимодулярную систему так же

а(ЛГ). Отметим, что эта система не полной размерности, она порождает только подпространство {т.,х(Ы) = 0}, ортогональное вектору 1/у € л". Если мы спроектируем множество а(/У и {0})) вдоль оси Не0 на пространство (кл')\ мы получим полномерную унимодулярную систему, состоящую из векторов ±е< и г,] € Ы, 1п (2")*. Симметричные подсистемы "Л С А/у называются графическими упимодулярпыми системами. На самом деле, с каждой такой системой мы можем связать неориентированный граф <7 = (/V, Е) с множеством вершин N и множеством ребер Е = {{г,-е^ € 7?.}. И наоборот, всякий граф (/V, Е) задает подсистему И с а(Аг), состоящую из векторов е; - е^-, {г,7} 6 Е.

Пример 2. С каждым графом б можно связать еще одну унимодулярную систему, кпррлфическую унимодулярную систему О(С). Она находится в группе когомологий графа Я1 (в, ъ) и состоит из классов когомологий ±[е], соответствующих ориентированным ребрам графа О.

Пример 3. В размерности 5 есть исключительная унимодулярная система, которая не является ни графической ни кографической. Эта система Е5 состоит из следующих 21 векторов: 0, ±е„ г = 1,...,5, ±(с| — <?г + ез). ±(^2 — ез + е4), ±(е3 -е4 + е5), ±(е< - е5 + е,), ±(е5 - е, + е2)}.

Согласно знаменитой теореме Сеймура |7| всякая унимодулярная система может быть построена из графических систем, кографических систем и исключительной системы Е5.

Пусть 72 - некоторая унимодулярная система. Элементы г из 71 мы называем корнями этой системы. Корни можно отождествить с морфизмами А1 в 11. Морфизмы же 71 п Л) мы называем кокорнямн. Другими «юлами, кокорень - это гомомор<|>иэм групп ф : М -» % такой что ф(г) € {-1,0,1} для любого корня геИ.. Множество кокорней мм обозначаем IV.

Полиэдр называется И-полиэЭром, если каждая его грань параллельна некоторому 7?-флэту.

Обозначим "Р1г(71) и V 11(11,1) класс 71-нолиэдров и его подкласс целых полиэдров. Псевдовыпуклое множество X в М называется И-выпуклым множеством, если со(Л') является 71-полиэдром.

Например, сумма некоторого набора линейных сегментов, каждый из которых параллелен некоторому корню г 6 И, является 72-политопом. Такие политопы являются зонотопами. Класс Т^Е;) состоит только из зонотопов. Это не

верно для других классов унимодулярных систем.

Полиэдр (в двойственном пространстве V*) является *И-выпуклым если и только если он задается пересечением полупространств вида

Яг+(а) = {р€У,р(г)<а},

где г е Я, а е ни {+оо}. Если все о являются целыми, то такой полиэдр является целым *72.-полиэром; мы обозначаем Тк*(Т1) класс *7£-полиэдров и Тк"{Т1,г) класс целых *7£-полиэдров (напомним, что это /-класс).

Множества целых точек *71-псшиэдров образуют класс *71-выпуклых множеств.

Аранжмент А(71) - это набор гиперплоскостей (зеркал) Яг(0) := г1, то есть ядер ненулевых корней г € И. Зеркала делят V' на конечное число конусов, которые образуют веер Е(7£).

Пусть V, - некоторая полномерная унимодулярная система в М. Тогда одномерные камеры (или лучи) веера £(7£) соответствуют флэтам коразмерности 1 И. Кроссинги - это примитивные вектора группы М*, порожденные такими камерами (лучами). Обозначим IV множество кроссингов. Выполняется IV С IV.

В этой же главе приводится внешнее и внутренее описание 7£-выпуклых и *7?.-выпуклых множеств. Используя внешнее описание, показано, что класс обобщенных полиматроидов в (ш")* совпадает с классом Адг-полиэдров. Мы показываем, что множество X является ^-выпуклым тогда и только тогда, когда касательный конус к .V в каждой точке х € X порождается некоторым подмножеством корней, и для всякого корня г, являющегося касательным в х, точка х + г принадлежит X. Дуально подмножество У С М' является *71-выпуклым тогда и только тогда, когда касательные конуса порождены "согласованными" подмножествами кроссингов, и для всякого касательного кроссинга £ е ТУ в точке у € У выполняется ¡/ + {6 У.

Во второй главе развивается теория дискретно-вогнутых/выпуклых функций на решетке 2".

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

Определение 9 Вогнутая функция / называется полиэдральной, если ее подграфик зир(/) является полиэдром в пространстве V х К.

Заметим, что полиэдральная функция автоматически замкнута. Область определения такой функции - тоже полиэдр. Полиэдрами являются также и любые области аффинности д'}(р) (д'/{р) = Агдтах(} — р)) в V. Мы называем множество такого вида "областью аффинности" функции /, поскольку на этом множество функция / совпадает с аффинной функцией р — /*(р), где /*(р) = Мах(/ — р).)

Полиэдральность влечет также то, что для любой точки х из области определения / существует супердифференциал. Так что области аффинности покрывают Лтп(/). Видно также, что имеется только конечное число различных областей аффинности, так как они представляют проекции (на V) граней полиэдра я«'»(/). Наконец, области аффинное!и "правильно" примыкают друг к другу. Это проявляется в том, что, во-первых, любая грань области аффинности снова являетгя областью аффинности, и, во-вторых, области аффинности пересекаются по обтцей грани. Такие структуры, состоящие из полиэдров, правильно примыкающих друг к другу, объединение которых замкнуто и выпукло и пересечение с любым компактом непусто только для конечного их подмножества, будем называть паркетами (а составляющие паркет полиэдры - ячейками паркета). Будем называть функцию локально полиэдральной, если ее области аффиности образуют паркет.

Зафиксируем некоторый класс V шшмэдроп к V, замкнутый относительно тятя |рангй.

Определение 10 Вогнутая локально полиэдральная функция } на V называется V-вогнутой, если любая ячейка д'} принадлежит классу V. Множество всех V-вогнутых функций на V обозначим как II).

Если функция / 'Р-погнута, то это же верно для функции а/, где а > 0. Если класс V замкнут относительно сдвигов (на векторы из V), то сдвиг аргумента в функции сохраняет 'Р-вогнутость. Аналогично с отражениями. Пусть теперь у нас есть две функции / и д. Мы доказываем, что если класс "Р замкнут относительно пересечений, то множество ТТ{У, Н) замкнуто относительно сумМ; если класс V замкнут относительно сумм, то ТТ{у, И) замкнуто относительно сверток.

Напомним, что ~Рк(1А) и VII'{Ы) обозначают классы полиэдров, касательные пространства к граням которых являются флэтами систем и и Ы1 соответ-

ственно. Эти классы полиэдров замкнуты относительно сумм и пересечений соответственно.

Теорема 3 Класс функций TVh{U){y,R) замкнут относительно сверток; класс функций TVh*(U){V,V) замкнут относительно сумм, и эти классы функций дуальны друг другу в том смысле, что сопряженная функция к функции из одного класса лежит в другом.

Перейдем теперь к рассмотрению функций, заданных на решетке М (или двойственной решетке М* = Hom(M,Z) в V*). Чтобы не путаться, такие функции мы будем обозначать буквами F, G и т.д. Итак, пусть F : М —t R U {—оо} -функция на М. Ее подграфик sub(F) С М х R определяется очевидным образом, sub(F) = {(m, а) 6 М х R : а < F(m)}. Аналогично, заменяя произвольные вектора на целые, определяются множества аффинности d'F(p) = Argmax{F — р\М) и супердифференциал dF(x) := {р S V : F(x) — F(m) > р(х) — р(т) V т е М} для точек х € dom(F). Легко понять, что замыкание выпуклой оболочки co(sub(F)) является подграфиком некоторой (замкнутой) вогнутой функции на V, которая обозначается как co(F) и называется конка-витизацией F, co(sub(F)) = sub(co(F)). Из определения следует F < co(F)\M. С другой стороны, если / - замкнутая вогнутая функция на V, то со(/|М) < /, так что /|М = co(f\M)\M.

Определение 11 Функция F на М называется псевдовогнутой, если co(F) полиэдральна и ее ограничение на М дает F, co(F)\M = F.

Справедливо dom(co(F)) = co(dom(F)), и dF(m) = dco(F)(m), в силу полиэдральное™ co{F) dco(F)(m) непусто, откуда следует что всякая псевдовыпуклая функция супердифференцируема.

Предложение 4 Пусть F - псевдовогнутая функция на М, up & V*. Тогда

a) co(d^F(p)) = d*(co(F))(p) и является полиэдром;

b)d-z(F)(p) = co(d*(F))(p)nM.

Таким образом, множества аффинности и область определения псевдовогнутой функции F являются псевдовыпуклыми множествами, а их выпуклые оболочки - ячейки паркета функции co(F) - являются целыми полиэдрами. Это мотивирует следующее

Определение 12 Функция f на V называется целой, если epi(f) = co(epi(f\M)) и является полиэдром.

Ясно, что псевдовогнутые функции на М и целые функции на V находятся в естественном взаимнооднозначном соответствии: для псевдовогнутой F функция co(F) целая и для целой / функция /|М псевдовогнута. Более того, co(F)\Kl = F, a co(f\M) = /. Так что мы имеем два параллельных языка, один больше ориентирован на М, а другой - на V.

Предложение 5 Полиэдральная функция f целая тогда и только тогда, когда все ячейки паркета / - целые полиэдры.

Как и в случае нсевдовогнутых множеств, многие соотношения и свойства, к которым мы привыкли в классическом Выпуклом Анализе, не верны для общих псевдовогнутых функций. Например, свертка псевдовогнутых функций может оказаться не нсевдовогнутой. Свертка здесь определяется той же формулой как и в выпуклом анализе, только участвующие в ней переменные должны быть целыми, то есть принадлежать М; чтобы избежать путаницы, будем обозначать ее ♦з;. Сумма псевдовогнутых функций определяется обычным способом и конечно пггндопогну га, но co[F + С) может отличаться от ro(F) + со(С7). Иначе говоря, сумма целых функций может оказаться нецелой. Наконец, может нарушаться теорема об отделении, или о сэндвиче. Поэтому для получения "хорошей" теории нужно наложить дополнительные требования "дискретной выпуклости", сузить класс псевдопогнутых или целых функций.

Пусть V - полиэдральный класс дискретной выпуклости. Псевдовогпутая функция F называется V-вогнутой, если соответствующая целая функция co(F) является 'Р-вогнутой.

Теорема 4 Пусть V - полиэдральный класс дискретной выпуклости, F и G -две V-вогнутые функции на М. Тогда выполнены следующие утверждения: Add') свертка F и G псевдовогнута, Edm') co(F) + co(G) = co(F + G),

Sep') (сэндвич): если —G > F, то существует аффинная функция А, такая что -G > А> F.

Утверждению Sep') можно придать форму теоремы двойственности типа Фенхеля. А именно, пусть V - полиэдральный класс дискретной выпуклости, a F

и в - две "Р-вогнутые функции. Предположим, что ^ + (3 ограничена сверху. Пусть т* € М - произвольная точка, в которой .Г+С? принимает максимальное значение; в силу полиэдральности такая точка существует. Тогда в этой точке максимальна и функция со(Р + С) = со(Р) 4- со{С). Значит

О € + (?))(т') = д(со(Г))(т') + д(со(в)){т*) = ЭР(т*) + <Э(?(т*).

То есть существует р* , который принадлежит и дР(т*) и —дО(т*).

Отметим, что свертка Р*гй и сумма .Р+б Р-вогнутых функций в общем случае уже не являются Р-вогнутыми. Для того, чтобы свертка была 'Р-вогнутой, нужно потребовать замкнутость класса V относительно сумм, то есть V должен быть ^-классом; аналогично, чтобы сумма оставалась 'Р-вогнутой, нужна замкнутость класса V относительно пересечений, то есть является /-классом.

Обозначим класс псевдовогнутых функций Р таких что

со(Р) 6 3-РН(и)(У, К) и назовем их дискретными и-вогнутыми функциями.

Имеет место "целочисленная двойственность". Для этого рассмотрим псевдовогнутые функции, принимающие целые значения, то есть функции вида F : М —» г и {—оо}. Рассмотрим целочисленный вариант оператора д мы изучили выше). А именно, положим для функции .Р на М и целых ш € Л/ и р€М*

ЭгР(т) = {р € М* | Р(т') - Р(т) < р(т') - р(т) V т' 6 М}.

Справедливо дгР(т) = д{со(Р))(тп) П М*. Обозначим через Р" ограничение сопряженной функции Р" на решетку целых А/*. Функция .Р" целозначная и псевдовогнутая. Если сопряженная функция Р* не целая, то может оказаться, что (/г1)11 ф- Справедлива

Теорема 5 Пусть Ы есть такой набор чистых подгрупп что 5 + Т чистая подгруппа для любых 5, Т € К. Пусть F - целозначная К-вогнутая функция. Тогда Р1' •- целозначная и^-вогнутая функция, и (Р')® = Р. При этом

д7Г(гп) = д^'(т) и д;Р(р) = д-^^р)

для т 6 ¿отР и р 6 Лот,0.

Таким образом, мы имеем действенность между классами целозначными U-вогнутых функций и целозначными ¿/-^-вогнутых функций. Справедлива так жо следующая целочисленная теорема двойственности типа Фенхеля.

Следствие 1 Пусть F и G две целозначные U-вогнутые функции на М, и

т' € М - точка, где достигает максимум F + G. Тогда существует целый >

функционал р' € М', такой что р' € dzF(m') и -р' € dzG(rn').

Наиболее интересные для приложений - это классы дискретных £/(7£)-вогнутых ,

функций и (U(1l))•'•-вогнутых функций, где И - унимодулярная система. Для краткости, мы будем обозначать их 71-вогнутые и *7£-вогнутые функции соответственно.

Из внутреннего описания Я-выпуклых множеств (*71-выпуклых множеств) получается следующий критерий глобальной максимизации функций из ftF(M,R) и *HF(M',K).

Предложение 6 а) Пусть функция F G 71F(M, R) « точка х G domF. Тогда F(x) > F(y) для любого у € М (то есть х является глобальным максимумом) тогда и только тогда, когда для любого г £ 71 справедливо ' •

F(x) > F(x + г). (1)

Ь) Пусть G 6 *UF(M',R) up € domG. Тогда G(p) > G(q) для любого q 6 М' тогда и только тогда, когда для любого справедливо

G(p)>G(p + Q. (2)

Теорема 6 Пусть функция G : М' -i RU {-оо} принадлежит *TZF(M',R). Тогда для любых р, q € М' любого кроссинга £ 6 a(q — р) ПIV выполняется

G(p) + G(q)<G(p + 0 + G(q-Q. (3)

Обращение этой теоремы справедливо для унимодулярных систем с симплици-альным веером. Справедливо также следующее

Предложение 7 Пусть функция G : М* -» RU {-оо} и конволюции G * G, G *G *G,... псевдовогнуты и удовлетворяют (3). Тогда G 6 *HF{M',R).

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

Напомним, что корни А„ это вектора вида е, — е), 1,] = 0,... ,п, где е0 = О, е,, г € / := {1, -. -, п}, - стандартые единичные орты в Полиэдр Р в пространстве и' будем называть полиматроидом2, если касательные пространства к граням полиэдра порождаются некоторыми подмножествами корней. Множество целых точек целого полиматроида будем называть ПМ-множеством.

Определение 13 Вогнутая полиэдральная функция / называется полима-тридной (ПМ-функцией), если клетки ее паркета 9* / являются полиматро-идами. Псевдо-вогнутая функция Р называется (дискретной) ПМ-функцией, если ее области аффинности являются ПМ-множествами, или, что эквивалентно, ее конкавификация co(F) является ПМ-функцией.

Класс ПМ-функций замкнут относительно конволюций. Выполняется и такое свойство: ограничение ПМ-функции на произвольный "ящик" ("ящиком"мы называем множество заданное неравенствами а, < х1 < Ь„ » е I, а0 < ж, < 60). Эти свойства позволяют строить новые ПМ-функции из уже имеющихся.

Простейшей ПМ-функцией является произвольная функция Т71, определенная на множестве {0} и {е,},6/, то есть dom(F) С {0} и {е,},е/. Области аффинности у этой со(Г) являются гранями единичного симплекса. Единичный симплекс со({0}и{е,},е/) и его грани являются простейшими полиматроидами.

Положительный ортант - другой простейший полиматроид, а его индикаторная функция является ПМ-функцией. Соответственно, индикаторная функция ортанта ъ\ (С?(:г) = 0 при х € и в{х) = — оо иначе) является дискретной ПМ-функцией. Конволюция произвольной (дискретной) ПМ-функции с индикаторной функцией ортанта является ПМ-функцией и называется монотонным продолжением исходной функции. Например, монотонное продолжение любой функции,.заданной на множестве {0} и {е,},6/, является ПМ-функцией.

Поскольку класс полиматроидов не замкнут относительно сложения, сумма ПМ-функций уже может не быть ПМ-функцией. Однако, сумма ПМ-функции с

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

вогнутой функцией от одного переменного х„ г € /, или Xq := — xt является ПМ-функцией. Действительно, клетки такой суммы являются пересечением полиматроидов с полосами вида а, < х, < ft,, i 6 {0}и/ и являются полиматро-идами (смотри, например |2]). По индукции получаем

Предложение 8 Пусть F - псевдовогнутая ПМ-функция, G, : Z RU{—оо}, i € {0} U I, псевдовогнутые функции одной переменной. Тогда

F+ y1 <?•(*•)

•€{о)и;

является ПМ-функцией.

Эту конструкцию можно обобщить, чтобы получить ПМ-функции, используя ламинарные семейства подмножеств I (смотри |29]). Пусть А и В - два непересекающихся подмножества /, и пусть РЛ и Fu - ПМ-функции переменных из множеств А н В соответственно. Пусть ф - некоторая псевдопогнутая функция на Ъ. Тогда

F(x) = Fa(xa) + FB(xB) + ф{х(А U В))

является ПМ-функцией, где хА обозначает ограничение х на ZA, и х(С) = Х^ес-ri- "ч этого следует, что для ламинарного семейства Т функция

F(*) = £G„(r(A)),

лет

где Ол : Z -» RU {—оо}, А € Т, псевдо-вогнутые функции одной переменной, является (дискретной) ПМ-функцией. Функции такого вида описывают все известные нам функции полезности нз моделей экономик с неделимыми товарами, п которых было доказано сущггл ппппнио равновесий.

Пусть F - дискретная функция на Z1 и х и у - две целые точки Z'. Введем следующие обозначения [х > у] := {» € Г\х, > у,} и \х < у] := {» 6 /'|х, < у,}.

Определение 14 Мы говорим, что F обладает свойством обмена в точках х tt у, если для любого г 6 [х > ?/] существует j € [т < у] так что выполняется:

F(x) + F(y) < F(x - е, + е}) + F(y + е,- е}). (4)

Определение 15 Функция Р удовлетворяет глобальному свойству обмена, если она обладает им для любой пары точек х, у 6 2'.

Это свойство глобального обмена напоминает в некотором смысле вогнутость Я в стандартном понимании для функций / на Я',

Я*)+Дз/)< 2/(^1). (5)

В случае целых х и у, их середина может оказаться не целой и поэтому напрямую (5) не работает. Если же функция удовлетворяет свойству глобального обмена, то мы можем сдвигать, увеличивая агрегированное значение на каждом шаге, (х,у) к паре (ж',у'), ближайшей возможной к точке при этом х' + у' = х + у и /(х') + /(у1) > }(х) + /{у).

Оказывается, что свойство глобального обмена эквивалентно полиматроид-ности.

Предложение 9 Пусть псевдовогнутая функция Г удовлетворяет глобальному свойству обмена, тогда К - ПМ-функция.

Будем называть касательные пространства к полиматроидным октаэдрам Т3-флэтами.

Теорема 7 Псевдовогнутая функция К является ПМ-функцией тогда и только тогда, когда ее ограничения на любой целый сдвиг всякого Тз-флэта является ПМ-функцией.

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

Итак посмотрим на дискретные функции как функции полезности экономического агента на пространстве неделимых продуктов Ж'. Потребуем для этого дополнительно монотонность. Тогда область аффинности (Э^Г'р) := А^тах(Р — р) интерпретируется как потребительский спрос при ценах р.

Следуя определению Келсо и Кроуфрда в булевской обстановке, мы дадим следующее

Определение 16 При ценах р, выделенном товаре г и е > 0, говорится, что имеет место валовая заменимость в ситуации (р, г, с), если для любого х € дуР{р) существует у 6 д^Р(р + е 1,) такое, что выполняется у> х_,, где

Определение 17 Функция Р называется ВЗ-функцией, если валовая заменимость имеет место в каждой ситуации (р, г, е).

Определение 18 Функция / называется ящичной ВЗ-функцией (6ВЗ-функция для краткости), если ограничение /\[а,ь] функции на любой ящик [а, 6] является ВЗ-функцией.

ВЗ-функции являются бВЗ-функциями. Областью определения 6ВЗ-функций может быть все пространство К7.

Теорема 8 Дискретная ПМ-функция является бВЗ-функцией.

Обращение этой теоремы не верно в общем случае. Однако, если мы будем рассматривать дискретные ВЗ-функции, определенные только на булевском кубе {0,1}', то эти функции будут ПМ-функциями.

Следствие 2 Свойства валовой заменимости и полиматроидности эквивалентны для дискретных функций на булевском кубе.

Чтобы выделить ПМ-функции в классе ВЗ-функций мы усилим свойство валовой заменимости.

Пусть Р : Т) —> К и {—оо} - дискретная функция (полезности).

Определение 19 Функция Р удовлетворяет свойству ПВЗ (пошаговой валовой заменимости) если для любого р 6 К7, для любого х 6 гЭ^Р(р), и для любого г £ I выполняется одно из следующих двух условий:

a. для любого £ > 0, х € с£Р(р + е !>)>

b. существует е > 0 и у е + £ 1,) так, что выполняется у, = х, — 1 « У-« > £->•

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

Предложение 10 Пусть Р - псевдовогнутая функция на решетке целых т). Тогда следующие свойства эквивалентны:

1. .Г является ПМ-функцией;

2. .Р удовлетворяет пошаговой валовой заменимости.

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

Рассматривается вариант стандартной модели Эрроу-Дебре с конечным числом потребителей и производителей, конечным числом неделимых товаров и одним делимым продуктом (деньгами).

Неделимые товары это только часть экономики и остальные товары представлены агрегирований через делимый товар - деньги. Итак, пространство товаров в модели является произведением решетки целых и прямой, Тк х к, где К обозначает конечное множество видов дискретных товаров. Обозначим через Ь - конечное множество производителей. Производитель I 6 Ь характеризуется свой функцией издержек С| : -* К и {+оо}, с((0) = 0, и с( является монотонной. Такой вид функции издержек означает, что производитель использует "обычные" товары как сырье в производственном процессе и не использует неделимые продукты в качестве сырья (это не упрощает модель, но и не загромождает ее). Затратив по меньшей мере с^), 2 € денег, производитель I может произвести вектор дискретных продуктов X. о(2) = +оо означает, что производитель / не может произвести 2.

Множество потребителей обозначается Я. Потребитель Л € Я имеет предпочтение ¿1, на множестве х К, то есть полное замкнутое и транзитивное бинарное отношение. Мы предполагаем, что предпочтения возрастают по неделимым товарам и строго возрастают по деньгам. Начальным запасом потребителя Л € Я является некоторый вектор (И-'л, и;/,) 6 х Ш+ и доли в прибыли производства: вц, > 0, является долей потребителя Л в прибыли производителя /, I 6 Выполняется £А€Я вл = 1 для любого I € Ь.

Итак, мы задаем дискретную экономику € с производством и деньгами следующим набором

£ = {(А,(ИЪ,«»*),№»).' 6 Ь), Л е Я; (с,), / 6 Ц.

Мы будем предполагать совершенную конкуренцию на рынках и в производстве. Цены нормализуются так, чтобы цена денег равнялась 1. Таким образом,

цены дискретных товаров являются неотрицательным линейным функционалом на Хк,~ыт просто неотрицательным вектором р € К+, р(Х) = Х^сЛ" РкХк, где р = (рк)кеК, Рк 6*+Д = (Х%ек, Хк € Ъ.

Все агенты ориентируются на цены при решении своих задач: при цене р, каждый производитель I € Ь решает следующую задачу максимизации:

тах(р(У)-с,(К)). (6)

Обозначим прибыль через тг|(р) = тахУик(р(У) — с;(К)).

Каждый потребитель Л 6 Я выбирает наилучший элемент (Л"л,тл), руководствуясь своим предпочтением в своем бюджетном множестве

Вн(р) = {{Х,т) е х ] р(ЛГ) + т < /3Л(р)},

где доход у9/,(р) определяется по правилу

Мр) = + + £

Определение 20 Набор ((Х^, т^^ен', (Удш,', р) называется конкурентным равновесием в экономике £ если:

a) VI является решением задачи (6), I 6 Ь;

b) для каждого /г € Н, (Хь, т^) является наилучшим элементом в бюджетном множестве по отношению к предпочтению ;</,;

c) рынки по всем продуктам сбалансированы:

= со

лея лея ¡€Ь

+ = (8) Лея !е£ лея

В силу строгой монотонности предпочтений по деньгам, сбалансированность по неделимым товарам влечет сбалансированность по деньгам.

Ясно, что равновесие может не существовать. Вопрос о существовании разбивается на две части. Одна относится к обычной выпуклости, другая - к дискретной выпуклости. А именно, наличие делимого товара (денег) позволяет овыпуклить дискретную экономику £, то есть построить новую экономику со(£)

с делимыми товарами, так что при любых ценах спросы и предложения овы-пукленной экономики являются выпуклыми оболочками спросов и предложений дискретной экономики. Ясно, что дискретная экономика должна быть такой чтобы существовало равновесие в овыпукленной экономике (такого сорта требования связаны с обычным выпуклым анализом). Фундаментальное требование, позволяющее перейти от равновесия в овыпукленной экономике к равновесию в изначальной дискретной экономике, состоит в требовании того, что спросы всех потребителей и предложения всех производителей из одного и того же S-класса дискретной выпуклости.

Теорема 9 Пусть £ - дискретная экономика. Предположим, что: 1) Существует равновесие в овыпукленной экономике со(£). 2) Существует S-класс дискретной выпуклости V такой, что спросы и предложения в дискретной экономике при равновесных ценах р' (в со(£)) принадлежат классу Т>. Тогда р* является равновесной ценой в дискретной экономике £.

В этой главе приводится один из вариантов условий, которые гарантируют существование равновесия в'овыпукленной экономике.

Все известные нам модели существования ([15, 12, 18, 21, 33, 9, 10, 20, 14| ) укладываются в эту теорему с одним и тем же S-классом дискретной выпуклости - классом полиматроидных множеств (А|/с|-выпуклость).

В следующем разделе этой главы рассмотрено применение дискретно выпуклого анализа к анализу двусторонних рынков с множественным партнерством. Есть два конечных множества участников: продавцы, обозначаемые 5, и покупатели - В3'. Каждый участник может образовывать сделки с произвольным количеством участников из дополнительного множества.

Определение 21 Паросочетанием называем произвольное подмножество ц С S х В. Обозначим ц{Ь) = {s, (s, 6) € /i] и /x(s) = {Ь, (s,6) € /1}.

Примитивная сделка состоит в передаче одной единицы некоторого товара (s, Ь) от продавца s к покупателю Ь4'. При покупке множестпа S С S поле зноен.

Такому разделению можно сопоставлять и другие контексты, например "фирмы и рабочие" (как в [16] или |19|), или "университеты и студенты" (как в |13|), и так далее

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

покупателя b возрастает на величину u(S,b). Аналогично, когда продавец s заключает сделки с множеством покупателей В С В, он теряет величину c(.s, В) - производственные издержки. Мы полагаем c(s, 0) = 0 и u(0,b) = 0. Теперь определим выигрыш в полезности при паросочетании р. как сумму выигрышей полезностей покупателей минус сумма издержек продавцов:

= Л иМь)<ь) - c(s>

ь &

Ядро и равновесие определяются стандартным образом. Равновесные распределения дают стабильные исходы из ядра.

Предположим, что продавцы разделены на две группы Ssut и Scom' Мы накладываем следующие три условия на полезности и функции издержек: Принцип Совместимости

(Ssub) функции —c(s, •) являются ПМ-вогнутыми для S 6 Ssub',

(Scom) функции -c(s, •) супермодулярны при S е Scom\

(В) функция полезности и(-,6) каждого покупателя b является суммой ПМ-вогнутой функции u,„i,(-,6) от переменных из множества Ssu(, и супермодулярной функции истп(-,Ь) от переменных из Sccm.

Теорема 10 Если Принцип Совместимости выполняется, тогда на двустороннем рынке существует равновесие.

Напомним, что на булевской решетке классы дискретных ПМ-функций и дискретных ВЗ-функций совпадают (Следствие 2). Тогда один из вариантов Принципа Совместимости, когда функции полезности и производственные функции являются ПМ-вогнутыми, допускает следующую форму. Валовая Заменимосить

Функция полезности и(-,Ь) каждого покупателя b € В является ВЗ-функцией и функция —c(s, •) каждого продавца s g S является ВЗ-функцией. Из Теоремы 10 и Следствия 2, мы получаем

Теорема 11 Если Валовая Заменимость выполняется, тогда существует равновесие на двустороннем рынке. А так же выполняется

a) множество М равновесных паросочетаний является промежуточно-выпуклым подмножеством" в 2п;

b) множество Р равновесных цен является подрешеткой в Rn.

Например, когда все продавцы одного типа и валовая заменимость выполнена на стороне продавцов (так обстоит дело с рабочими в модели из |16|) и полезности покупателей удовлетворяют валовой заменимости, то Принцип Совместимости выполнен и существует равновесие. Таким образом |16] слоду<ч m Теоремы 10.

Другой пример когда покупатели заинтересованы в покупке не более одного товара. Такие функции полезности являются ПМ-вогнутыми. Следовательно Принцип Совместимости будет выполняться, если валовая заменимость будет выполняться на стороне производителей. Простейший пример - аддитивные функции стоимости. Такая модель рассматривалась в (5).

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

Если производственные функции являются сепарабельными функциями с ограничением на объем, то условие валовой заменимости выполнено на стороне производителей, поскольку такие функции являются ПМ-функциями. В [11] доказывается существование равновесия с такими функциями издержек и покупателями, заинтересованными в покупке не более одно! о продукта Ясно, что такой результат простое следствие Теоремы 11.

Рассмотрим теперь другой крайний случай Теоремы 10, в котором все продукты взаимно дополняющие. Принцип дополнительности

Функции полезности u(-, 6) - супермодулярны, Ь € В, а функции издержек с(а, •) - субмодулярны, 5 € S.

Теорема 12 Предположим Принцип дополнительности выполнен на двустороннем рынке. Тогда

5Множество М С 2П называется промежуточно выпуклым множеством, если для любых двух его элементов /1* и /1" таких, что выполняется С i¡", оно содержит и все /«, то есть такие что р' С ¡i С ц".

1. Существует равновесие.

2. Множество М равновестных паросочетаний является подрешеткой в 2П.

3. Множество Р равновесных цен является промежуточно выпуклым подмножеством Rn.

Из этой теоремы следует существование равновесия в модели информационных товаров с расщепляющимся производством ([35]).

В 1991 году Макаров (|24]) первым предложил модель экономик с информационными продуктами, в которой проявлялись многие черты, отличающие такие продукты от обыкновенных. Развитие эта модель получила в работах [34, 35, 36, 37, 38).

Обозначим через D - множество информационных продуктов, X, У,... - элементы D. Информационные продукты отличаются от обычных идемпотентностью сложения (обозначим ее v), то есть d является полурешеткой. На d можно ввести порядок - лучшие или худшие товары. Обычные продукты представлены агрегированно через делимый продукт - деньги. Итак, пространство товаров это произведение Ю х 1.

Множество фирм, производящих информационные продукты, обозначим J. Предполагается, что каждая фирма, произведя какой-нибудь товар, обладает копиями этого товара уже бесплатно. В экономической теории это соответствует производству с фиксированными начальными издержками. Фирма-производитель j описывается функцией издержек а3 : В —> EU {+оо}. То есть фирма можег произвести продукт X £ D, затратив денег не меньше а,{Х). Будем считать, что а,(0) = 0 и а}(Х) > а3(Х') при X > X' (т.е. X УХ' = X). а3(Х) = +оо означает невозможность производства товара X фирмой j. Произведя товар X, фирма j, j £ J, продает копии этого товара потребителям.

Множество потребителей обозначается через I. Потребитель г € / описывается своей функцией полезности U, : D х R —> R. Для простоты изложения предполагаем, что полезность трансферабельна и, поэтому задаем потребителя его полезностью на пространстве информационных продуктов u, : D —> R. и, предполагается не убывающей и и,(0) = 0.

Состояние экономики задается набором ((Х,)^;, (У})3^), где (Х,),е; - планы потребеления и (У))^ - планы производства, все X, и из О. Сопояние (У^)^бу) называется допустимым если Ч&У] > У,6|Х„ то егть предложение не меньше спроса.

Ценой называем монотонную модулярную функцию на решетке, равную нулю в нулевом элементе. Напомним, что функция р : 1) -» И модулярпп, гели р{Х) + р{У) = р(Х V У) + р(Х Л У) при любых X, У 6 О. Мы предполагаем совершенную защиту авторских прав, то есть потребитель может купить товар только у производителя и не может перепродавать его копии. В силу этого мы имеем индивидуальные цены для потребителей. Итак, чтобы купить продукт X, потребитель г должен заплатить р,(Х). Ценой р для производителей будет сумма индивидуальных потребительских цен, то есть р = р,. Другими словами, фирма создавая информационный продукт X, ожидает продать его копии всем потребителям и получить денег р{Х) = Р.(-¥). Итак, при ценах (р,),6/ на рынке, фирма производитель ], j 6 решает задачу максимизации прибыли

т«(5>(У)-«,(У)). О)

*

Потребитель г максимизирует свою чистую полезность, ориентируясь на свои персональные цены:

шаг(«.(Х)-р,(Х)). (10)

Набор (р,Ьег) называется равновесием, если каждый У1 дает

решение задачи (9), } 6 каждый Х{ дает решение (10), i € /; состояние (№)!€/■ (КЛы) является допустимым и выполняется баланс по деньгам

£рМ) < £?.(*.)• (и)

)£] I€/

Приведем теорему существования.

Теорема 13 Пусть а) В является конечной дистрибутивной ре теткой; Ь) функции полезности и,, г € I, являются с.упермодулярными неубывающими функциями и «,(0) = 0; с) функции издержек а} неубывающие а7(0) = 0, ] 6 J, и агрегированная функция издержек А равная конволюции, А = явля-

ется субмодулярной. Тогда существует равновесие.

Нам приходится требовать субмодулярность (дискретную выпуклость) агрегированного производства, а не индивидуальных, поскольку класс субмодулярных функций замкнут относительно суммы, но не замкнут относительно конволю-ции. В некоторых случаях можно получить и условие в индивидуальных требованиях. Скажем, что производственный сектор ламинарен, если для каждого ] 6 3 функция а, - дихотомична (принимает только два значения) и есть минимальное множество Т} такое, что 0 < а}(Т) = а_,(Т;) < +оо, если ТЭТ, и а3(Т) = 0 иначе, и семейство множеств {Т3}]£,/ образует ламинарное семейство. (Напомним, что семейство Т называется ламинарным, если Т П 5 € {0,5, Т} при любых 5, Т € Т.) Легко проверить, что агрегированная функция издержек ламинарного производственного сектора является субмодулярной. Поэтому получаем

Следствие 3 Если в экономике информационных товаров выполняются Предположения 1 и 2, и производственный сектор является ламинарным, тогда существует равновесие.

Другим случаем когда агрегированная функция издержек субмодулярна является производственный сектор с расщепляющимся производствам, то есть когда носители (области эффективности) функций а;, € ./, попарно не пересекаются (Теорема 12).

Отметим, что когда В является булевской решеткой имеются еще две возможности для существования равновесия. Во-первых, равновесие существует, если функции полезности и издержек являются дискретно-вогнутыми (выпуклыми) относительно класса дискретной выпуклости, порожденного унимоду-лярной системой, изоморфной прямой сумме копий А2. Во-вторых, если функции издержек а}, ] 6 7, являются ПМ-выпуклыми функциями, а агрегированная функция полезности £/ является ПМ-выпуклой, тогда существует равновесие в экономике с информационными товарами.

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

Обозначим через Р множество альтернатив или вариантов выбора. Функция выбора / : 2Р —¥ 2Р сопоставляет непустое подмножество /(А) каждому множеству А из 2Р \ 0 и /(0) = 0.

Аксиома Плотта или, эквивалентно, концепция "независимости от пути" функции выбора была предложена в (|26|) как ослабление бинарной рацнонали-зуемости с сохранением ключевого свойства рационализуемости п том смысле, что выбор не должен зависеть от того, как делить множество альтернатив для выбора, то есть для любых А, В 6 2Р \ 0 выполняется

ДЛиВ) = /(/(Л)иДЯ)). По функции выбора / : 2Р -4 2Р, /(0) = 0, определим оператор

К/(Л) = и {Д<:/М')=/М)И'. О2)

Отображение а : 2Р —> 2Р, ст(0) = 0, называется оператором замыкания, если выполняются следующие свойства: А С о (А), о(о(А)) = а(А) и /1 С В => £г(/4) С о (В). Обозначим К(Р,о) - множество замкнутых относительно а подмножеств Р, то есть подмножества Р вида о (А), А С. Р. Базисом А называется минималмше (по включению) подмножество 5 С Л такое что я(5) » о(Л). Априори может быть несколько базисов у множества (эго так для матроидов, то есть операторов замыкания со свойством обмена). Точка я 6 А называется крайней точкой А, если а ^ о(А \ а). Множество крайних точек А обозначим ех с(А). Множество ех „(А) (возможно пустое) содержится в каждом базисе А.

Множество К(Р, а) называется абстрактной выпуклой геометрией (или а удовлетворяет свойству антиобмена), если для любого замкнутою множеств А, и двух разных точек р и д € Р, не из А, условие д 6 К {А и р) влечет р & К(А и <7). Это свойство является комбинаторной абстракцией выпуклого замыкания в обычном линейном пространстве. Действительно, если мы возьмем две точки р и д вне выпуклой оболочки множества А, и точка д оказывается в выпуклой оболочке А и р, тогда р лежит вне выпуклой оболочки А и д.

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

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

Теорема 14 Пусть функция выбора / удовлетворяет свойству независимости от пути. Тогда множество замкнутых множеств относительно оператора К{, определенного в (18), является абстрактной выпуклой геометрией и выполняется / = ехК/.

Всякая абстрактная выпуклая геометрия посредством взятия крайних точек индуцирует функцию выбора }(А) := ех (Л), которая удовлетворяет НП-свойству.

Теорема 15 Пусть а : 2Р -4 2Р - оператор замыкания, удовлетворяющий свойству антиобмена. Тогда для любых А, В С Р выполняется

ех<7(АиВ) = ех„(еха(А)иех17(В)). (13)

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ.

1. Полностью решена задача о существовании конкуретного равновесия в моделях экономик с неделимыми товарами.

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

3. Для экономических приложений важными являются классы функций отвечающих Б-классам дискретной выпуклости (замкнутым относительно сложения) и 1-классам (замкнутым относительно пересечения). Показано, что, заменяя обычный выпуклый анализ на дискретно-выпуклый, связанный с Э-классами дискретной выпуклости, можно строить общую теорию равновесий в

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

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

Список литературы

[1| Edmonds J. Submodular functions, matroids, and certain polyhedra. -Combinatorial Structures and Their Applications/ Eds. Guy H. Hanai N. Sauer and J. Schonsheim - Gordon к Breach, Sci. Publishers, NY, 1970.-p. 69-87

[2] Frank A and E. TardOs. Generalized polymatroids and submodular flows // Mathematical Programming - 42 (1988), 489-563

[3| Fujishige S. Submodular Functions and Optimization- North-Holland, Amsterdam, 1991

[4] Ковалев M.M. и Э. Гирлих. Дискретная оптимизация - Изд. БГУ, Минск, 1977

[5] Kaneko М. The central assignment game and the assignment markets // Journal of Mathematical Economics -10 (1982), 1483-1504.

|6) Murota K. Discrete convex analysis // Mathematical Programming - 83 (1998), 313-371.

[7] Seymour, P.D. Decomposition of regular matroids // J. Combinatorial Theory (Ser. B) - 28 (1980), 305-359

[8] Topkis D.M. Minimizing a Submodular Function on a Lattice // Operations Research - 26 (1978), 305-321

33

рос. национальная j библиотека i С.Петер6ург i « 09 300 акт *

1i I "-T1

[9] Bevia, C., M. Quinzii and J.Silva. Buying Several Indivisible Goods // Mathematical Social Sciences - 37 (1999), 1-23.

10] Bikhchandani S. and J. W. Mamer. Competitive equilibrium in an exchange economy with indivisibilities // Journal of Economic Theory - 74 (1997), 385413.

11] Crawford V.P. and L.C. Knoer. Job matching with heterogeneous firms and workers // Econometrica - 49 (1981), 437-450

12] Gale D. Equilibrium in a discrete exchange economy with money // International Journal of Game Theory - 13 (1984), 61-64.

13] Gale, D. and L. Shapley. College admissions and the stability of marriage // American Mathematical Monthly - 69 (1962), 9-15.

14] Gui F. and E. Stacchetti. Walrasian Equilibrium with Gross Substitutes // Journal of Economic Theory - 87 (1999), 95-124

15] Henry C. Indivisibilités dans une économie d'échangés // Econometrica - 38 (1970) , 542-558.

16] Kelso A.S. and V.P. Crawford. Job matching, coalition formation, and gross substitutes // Econometrica - 50 (1982), 1483-1504

17] Koopmans T. and M. J. Beckmann. Assignment problems and the location of economic activities // Econometrica - 25 (1957), 53-76.

18] Quinzii M. Core and equilibria with indivisibilities // International Journal of Game Theory - 13 (1984), 41-61.

19] Roth A. Stability and polarization of interests in job matching// Econometrica - 52 (1984), 47-57.

20] van der Laan, G., D. Talman and Z. Yang. Existence of an equilibrium in a competitive economy with indivisibilities and money// Journal of Mathematical Economics - 28(1997), 101-109.

[21] Svensson L.-G. Competitive equilibria with indivisible goods// Journal of Economics - 44 (1984), 373-386.

[22] Shapley, L. S. and M. Shubik. The assignment game I: the core// International Journal of Game Theory - 1 (1972), 111-130.

[23] Arrow K.J. Information and the organization of industry. / Markets, Information and Uncertanty, Essays in Economic Theory in Honnor of K.J.Arrow /Ed. G. Chichilnisky - Cambridge University Press, Cambridge, 1999 - p. 19-25

[24| Makarov V.L. About economies of intellectual goods and its modeling, Report at Sixth Congress of the European Economic Association - Cambridge, UK, 1991

|25] Korte, В., L. Lovász and R. Schrader. Greedoids - Springer-Vcrlag, В 1991

[26] Plott C.R. Path independence, rationality and social choice// Economotrica -41 (1971), 1075-1091.

[27] van de Vel M. Theory of Convex Structures. • North Holland, Amsterdam, 1993.

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

[28] Danilov V, Koshevoy G and K.Mtirota. Equilibria in economies with indivisible goods and money/ Preprint RIMS-1024 - Research Institute Mathematical Sciences, Kyoto University, 1998 - 29p.

[29| Danilov V, Koshevoy G and K.Murota. Discrete convexity and equilibria in economies with indivisible goods and money// Mathematical Social Sciences - 41 (2001), 251-273

|30| Danilov' V. I., G. A. Koshevoy, and C. Lang. Substitutes, complements and equilibrium in two-sided maiket/ Advances in Economic Design / Eds. M.R. Seitel and S.Koray - Spinger-Verlag, Berlin, 2003- p.105-123

[31] Danilov V. and G.Koshevoy, Discrete convexity and unimodularity. I // Advances in Mathematics (принята к печати), препринт http : //arXiv.org/math.CO/Qm29l

[32] Danilov, V. I., G. A. Koshevoy, and C. Lang. Gross substitution, discrete convexity and submodnlarity// Discrete and Applied Mathematics. - 129(2003), 20p.

[33] Danilov, V.I., G.A. Koshevoy and A.I. Sotskov. Equilibrium in exchange economies with indivisibilities / Book of abstracts of Symposium of Operations Research, Braunschweig (Germany) 1996, p. 134.

[34] Данилов В.И., Кошевой Г.А. и А.И. Сотсков. Равновесие в экономике с интеллектуальными товарами// Экономика и Математические Методы - 29 (1993), 607-616

[35] Danilov V.I., G.A.Koshevoy and A.I.Sotskov. Equilibrium in a market of intellectual goods// Mathematical Social Sciences - 27 (1994), 133-144

[36] Danilov V.I., G.A.Koshevoy and A.I.Sotskov. Equilibrium analysis of economies with novelties// Journal of Mathematical Economics - 27 (1997), 195-228

[37] Danilov V.I., G.A.Koshevoy and A.I.Sotskov. Equilibrium in an economy with information goods / Markets, Information and Uncertanty, Essays in Economic Theory in Honnor of K.J.Arrow / Ed. G. Chichilnisky - Cambridge University Press, Cambridge, 1999 - p 26-44

[38] Danilov V.I., G.A.Koshevoy and A.I Sotskov. A model of economic equilibrium in the market for information goods/ Contemporary Economic Issues/ Ed. M.Sertel - Macmillan Press and St.Martin's Press, NY, 1999 - p.161- 184

[39] Koshevoy G.A. Discrete convexity and unimodularity.// Abstracts of the International Congress of Mathematicians, Berlin, Germany, 1998 - http : //www.mathemaUk.uni — bielefeld de/zcm9&/ps/late_ps.html

[40] Koshevoy G.A. Choice functions and abstract convex geometries // Mathematical Social Sciences - 38 (1999), 35-44

[41] Koshevoy G.A. Path-independence and closure operators with the anti-exchange property // Discrete and Applied Mathematics (принята к печати) 18 p.

[42] Koshevoy G.A. Choice functions and abstract convexity/ Book of Abstracts of Forth International Meeting of the Society for Social Choice and Welfare -Vancouver, Canada, 1998 - p. 54

[43| Koshevoy G.A. Path-independence and closure operators with the anti-exchange property / Book of Abstracts of Ordinal and Symbolic Data Analysis Confrienre -Brussels University, Belgium, 2000 - p.29

|44] Кошевой Г.А. Функции выбора Плотта и выпуклые i сомгтрни // Экономика и Математические Методы - 39/3 (2003), 16 р.

Заказ .У, <Г*__Объем Х- п.л. Тнраж

" ЦЭМИ РАН ~ —

/

$ . 8 7 1 1i

Диссертация: содержание автор диссертационного исследования: доктора физико-математических наук, Кошевой, Глеб Алексеевич

Введение

1 ГЛАВА 1. Дискретная Выпуклость

1.1 Дискретная выпуклость: основания.

1.2 Гомогенизация S-классов: чистые системы.

1.3 Конструкция 5-классов.

1.4 Конструкция I-классов.

1.5 Классы дискретной выпуклости с удвоением.

1.6 Унимодулярные системы

1.7 Внешнее описание 7£-полиэдров и *7£-полиэдров

1.7.1 Полезные факты.

1.7.2 Опорные функции к 7^-политопам.

1.7.3 Базовые полиэдры и обобщенные полиматроиды

1.7.4 *7£-полиэдры.

1.8 Внутреннее описание дискретно выпуклых множеств

1.8.1 Касательные конуса.

1.8.2 7^-выпуклые множества.

1.8.3 Связь касательных (кокасательных) конусов И,-выпуклых множеств с опорными функциями

1.8.4 7^-выпуклые оболочки.

1.8.5 Касательные конуса *7£-выпуклых множеств

2 ГЛАВА 2. Дискретно Выпуклый Анализ

2.1 Вогнутые функции.

2.1.1 Полиэдральные функции и их паркеты.

2.2 "Р-вогнутые функции.

2.3 Псевдовогнутые и целые функции.

2.4 Дискретно-вогнутые функции.:

2.5 Целочисленная двойственность.

2.6 Примеры 7^-вогнутых и *7£-вогнутых функций.

2.6.1 Внутренне описание функций из 7ZF(M,r)

7IF(M*,R).

2.7 Полиматроидные функции

2.8 Свойство глобального обмена.

2.9 Локальное свойство обмена.

2.10 Полиматроидность и валовая заменимость.

2.11 Паркеты вогнутых ВЗ-функций и супермодулярность . 101 2.11.1 Пошаговая валовая заменимость.

3 ГЛАВА 3. Экономики с неделимыми товарами

3.1 Модель

3.2 Дискретная выпуклость и существование равновесия

3.3 Непрерывная часть проблемы существования

3.3.1 Случай трансферабельных предпочтений

3.3.2 Доказательство Предложения 36.

3.4 Двусторонний рынок.

3.5 Модель двустороннего рынка.

3.6 Теорема существования и структура равновесий

3.6.1 Рынки с валовой заменимостью.

3.6.2 Рынки с взаимно дополняющими продуктами

3.7 Экономики с информационными товарами.

3.8 Модель и определения.

3.9 Свойства равновесий.

3.9.1 Оптимальность.

3.9.2 Существование равновесий.

4 ГЛАВА 4. Функции выбора и выпуклые геометрии

4.1 Функции выбора и рационализируемость.

4.2 Аксиома Плотта и абстрактная выпуклость

4.3 Функции выбора и операторы.

4.4 Транзитивность, решетки выбора и чешуйчатость . . . 168 Список литературы

Диссертация: введение по экономике, на тему "Дискретно выпуклый анализ и его применение к моделям экономик с неделимыми товарами"

Выпуклость важна во многих областях математики и её приложений и до настоящего момента не теряет своей актуальности в оптимизации и математической экономике. Когда мы сталкиваемся с целочисленными задачами в оптимизации или с неделимыми объектами (товарами) в экономике, дискретно выпуклый анализ был бы очень уместен. Однако дискретность целочисленной решетки zn не позволяет ввести выпуклость в привычном виде: если подразумевать выпуклым подмножество, которое с любыми двумя точками а и Ь содержит и весь сегмент, соединяющий а и Ъ.

Мы можем овыпуклить любое подмножнство X С zn и получить выпуклое подмножество со(Х) в к". Если множество X таково что все целые точки полиэдра со(Х) и есть X, то это первое приближение к дискретной выпуклости, и мы будем называть такие множества псевдовыпуклыми . С этим классом множеств не удается построить интересной теории дискретной выпуклости. Дело в том, что в размерности большей 1, в этом классе непересекающиеся множества могут быть неотделимы линейными функционалами. На уровне целых полиэдров это свойство неотделимости эквивалентно тому, что пересечение целых полиэдров может быть уже не целым. Поэтому приходится сужать класс псевдовыпуклых множеств чтобы получать дискретно выпуклые. Отметим сразу отличие нашей дискретной теории от классической (непрерывной): нет единого понятия дискретно выпуклого множества, есть понятие класса дискретно выпуклых множеств. Непересекающиеся множества из одного и того же класса разделяются (строго) некоторым линейным функционалом. С каждым классом дискретно-выпуклых множеств связан класс функций, так что выпуклая и вогнутая функции разделяются аффинной, если первая функция (поточечно) больше или равна второй. Подробно эти вопросы и Дискретно выпуклый анализ изложены в первых двух

главах диссетрации.

Мы создавали нашу теорию не на пустом месте. Одним из первых примеров возможности существования выпуклого анализа в дискретной обстановке является теорема Франка [15] о разделении супермодулярной и субмодулярной функций на булевской решетке. Этот результат (усиленный для функций на дистрибутивных решетках) дал основу построения теории равновесия в экономиках с информационными товарами [37, 38, 40]. Разработанную технику мы применили к моделям экономик с неделимыми товарами и получили необходимое и достаточное условие существования равновесия в агрегированных терминах [39]. Для случая экономик с двумя потребителями мы предложили класс функций полезности - целые супермодулярные функции (в терминологии диссертации), для которых наше агрегированное условие существования выполнялось (отметим, что в [25] такие функции названы дискретно выпуклыми). В это же время появилась статья Муроты [29], в которой рассматривались полиматроидные функции и для этого класса функций строилась теория параллельная обычному выпуклому анализу. Оказалось, что класс полиматроидных функций дает еще один из примеров классов функций полезности, удовлетворяющих нашему необходимому и достаточному условию существования равновесия в моделях экономик с неделимыми товарами и деньгами ([8]).

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

Это свойство отделимости непересекающихся множеств мы взяли для основы построения теории дискретной выпуклости и назвали классом дискретной выпуклости любой подкласс псевдовыпуклых множеств, в котором непересекающиеся множества разделяются. На полиэдральном уровне (языке) это эквивалентно тому, что пересечение любых двух целых полиэдров класса является целым полиэдром, хотя это пересечение может быть полиэдром не из этого класса. При этом в таких классах хотелось бы иметь и еще несколько полезных свойств: замкнутость относительно целочисленных сдвигов, центральную симметрию, и что с каждым множеством из класса и все его грани являются множествами класса. Взяв прямое произведение одномерных псевдовыпуклых множеств, мы видим, что такие классы существуют. Но конечно этот пример далек от максимальности. Мы полностью охарактеризовали такие классы. Глава 1 посвящена описанию и конструированию этих классов. Основные результаты этой главы публикуются в [6] (частично в [8]). Мы показали, что классы дискретной выпуклости находятся в биективном соответствии с чистыми системами (полугруппы, образованные чистыми подгруппами). Чистые системы, порождаемые одномерными образующими, взаимнооднозначно соответствуют унимодулярным системам. Унимоду-лярные системы (или, что эквивалентно, регулярные матроиды, или вполне унимодулярные матрицы) хорошо известны в комбинаторной оптимизации и теории целочисленного программирования. По унимо-дулярной системе мы строим два класса. Один - S-класс, замкнутый относительно сложения (по Минковскому), получается в форме целых точек полиэдров, ребра которых параллельны векторам унимодуляр-ной системы; другой - I-класс, замкнутый относительно пересечений и получается в форме целых точек полиэдров, грани максимальной размерности которых имеют нормали параллельные векторам уни-модулярной системы. Классы, замкнутые относительно пересечения и суммы, соответствуют очень простым унимодулярным системам, раскладывающимся в прямую сумму копий двумерных унимодулярных систем. Класс полиматроидов образует S-класс дискретной выпуклости, связанный с графической системой Ап, образованной векторами е; — ej, ±ej, i,j € N, где ег- - стандартный единичный г-ый базисный вектор в к". Класс целых супермодулярных (кополиматро-идных) функций связан с этой же унимодулярной системой и образован множествами целых точек целых полиэдров, нормальные вектора к граням максимальной размерности которых имеют вид е* — ej, ±ег-, г, j 6 N. В этой же главе мы приводим внутреннее и внешнее описание множеств для унимодулярных классов дискретной выпуклости.

В Главе 2 мы развиваем дискретно выпуклый анализ. А именно, поскольку мы знаем как устроены классы выпуклых (дискретно) множеств в целочисленной решетке, мы можем рассматривать функции, паркеты которых состоят из элементов какого-нибудь класса дискретной выпуклости. (Паркет функции - разбиение ее области эффективности на клетки, являющиеся областями аффинности функции. Паркет - важное понятие для полиэдральных функций и ранее не исследовался в Выпуклом анализе.) Зафиксировав класс дискретной выпуклости, мы получаем класс функций. При этом S-классы множеств дают классы функций замкнутых относительно сложения, а 1-классы - замкнутых относительно свертки,-Мы показываем, что в этих классах выполняются теорема отделимости и двойственность Фенхеля. S-и I-классы целозначных функций с одной и той же чистой системой двойственны. Подробно исследуются классы функций, относящиеся к унимодулярной системе Ап. Соответствующий S-класс функций связан с важным экономическим свойством валовой заменимости и состоит из функций с паркетами, образованными целыми полиматро-идами; I-класс связан со свойством дополнительности и состоит из целых супермодулярных (субмодулярных) функций. Результаты этой главы опубликованы в [7, 43, 44, 8].

В Главе 3 приводятся применения дискретно выпуклого анализа к экономикам с неделимыми товарами. Коротко можно сказать так: заменяя Выпуклый анализ на Дискретно выпуклый можно параллельно получить почти все результаты из обычной равновесной теории моделей типа Эрроу-Дебре в моделях с неделимыми товарами. В начале мы приводим общую теорему существования в моделях с неделимыми товарами и деньгами и показываем, что все известные нам результаты о существовании равновесий в таких моделях получаются как следствия этой теоремы, связанные только с одним полима-троидным случаем. Затем мы применяем наш дискретно выпуклый анализ к моделям паросочетаний с множественным партнерством и показываем что известные нам результаты существования стабильных исходов в таких моделях являются частными случаями нашей общей теоремы и соответствуют Принципу Совместимости в крайней форме - Принципу валовой заменимости. Другой частный случай -Принцип полной дополнительности - ближе к экономикам с информационными (интеллектуальными) товарами. Такие модели с информационными товарами мы более подробно рассматриваем в заключении этой Главы. Основные результаты этой главы опубликованы в . [44, 8, 39, 37, 38, 40, 41, 42].

В литературе есть еще один подход к переносу понятия выпуклости в дискретную обстановку, связанный с исследованием свойств оператора замыкания. Хорошими обзорами такого рода работ является книги [90] и [75]. В главе 4 мы рассмотрим операторы замыкания с антиобменным свойством, известные также как абстрактные выпуклые геометрии. Мы показываем, что такие геометрии находятся в биективном соответствии с важным классом функций выбора, удовлетворяющих Аксиоме Плотта независимости от пути. Эта биекция следует из новой характеризации таких геометрии через свойства крайних точек [76]. Можно показать, что абстрактная выпуклость порождается одноточечными областями аффиности полиматроидных функций. Подход к исследованию функций полезности через абстрактные выпуклые геометрии не только позволяет получить новые характе-ризации ординальной рационализируемое™ и независимости от пути и усилить существующие, но и предлагает новый подход к анализу рационализируемое™. Это также оказалось полезным для исследования абстрактных выпуклых геометрий. Основные результаты этой главы опубликованы в [76, 77, 80].

Итак основными результатами диссертации являются:

1) построение новой теории "Дискретно выпуклый анализ";

2) применение этой теории к проблеме существования равновесий в моделях экономик с неделимыми товарами;

3) новый подход к анализу рационализуемости выбора.