Дискретно выпуклый анализ и его применение к моделям экономик с неделимыми товарами тема диссертации и автореферата по ВАК РФ 08.00.13, доктор физико-математических наук Кошевой, Глеб Алексеевич

• Кошевой, Глеб Алексеевич
• доктор физико-математических наук
• 2003

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

Введение

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) новый подход к анализу рационализуемости выбора.

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

1. N. Bourbaki, "Groupes et algebres de Ыё\ Chapter V, Hermann, Paris, 1968.

2. Bolker, E.D., 1969, A class of convex bodies. Trans. Amer. Math. Soc., 145, 323-346

3. G. Choquet, Theory of capacities. Annales de ITnstitut Fourier 5 (1953/1954), 131-295.

4. V. Danilov and V. Grishukhin, Maximal unimodular systems of vectors, European Journal of Combinatorics, 20 (1999), 507-526a) AC В A\f(A)CB\f(B), (4) /(В) С А С В /(Л) = f(B).84)85)но (смотри, например, 86.).)Q.E.D.

5. Danilov V. and G.Koshevoy, Cores of cooperative games, superdifferentials of functions and Minkowski difference of sets, J. of Math. Analysis and Appl., 247 (2000), 1-14

6. Danilov V.I. and G. A. Koshevoy, Discrete convexity and unimodularity I, Advances in Mathematics (принята к печати)

7. Danilov V.I. and G.A. Koshevoy, Discrete convexity and unimodularity II, (подготовлена к печати)

8. 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

9. Данилов В.И. и К. Ланг, Кусочно-линейные функции полезности, удовлетворяющие условию валовой заменимости. Экономика и Мат. Методы 37/4 (2002), 50-63

10. Dress A.M.W. and W. Wenzel, Valuated Matroids, Advances in Mathematics, 91 (1992), 158-208

11. Erdahl, R.M. and S.S.Ryshkov, On lattice dicing, Europ. J. Combinatorics, 15 (1994), 459-481

12. Edmonds J., 1970, Submodular functions, matroids, and certain polyhedra, in: R. Guy, H. Hanai, N. Sauer and J. Schonsheim, eds., Combinatorial Structures and Their Applications, Gordon & Breach, Sci. Publishers, New York, 69-87

13. A.J. Hoffman and J.B. Kruskal, Integral boundary points of convex polyhedra, in "Linear Inequalities and Related systems" (H.W.Kuhn and A.W. Tucker, Eds.), pp. 223-246, Princeton University Press, Princeton, 1956.

14. B. GriinbaumConvex poly top ed\ Wiley-Interscience, London, 1967.

15. L. Lov&sz, Submodular functions and convexity, in 11 Mathematical Programming: The State of the Arf (Bachem A., M.Gretschel and B.Korte, Eds.) pp. 235-257, Springer-Verlag, Berlin, New York, 1983.

16. R.T. Rockafellar, "Convex analysis, Princeton, Princeton Univ. Press, 1970.

17. A. Schrijver," Theory of Linear and Integer Programming, Wiley & Sons, Chichester, 1986.

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

19. D.J.A. Welsh, ilMatroid Theortf\ Academic Press, London-New York, 1976

20. Frank, A and E. Tardos, Generalized polymatroids and submodular flows. Mathematical Programming, 42 (1988), 489-563

21. Fujishige S., A note on Frank's generalized polymatroids, Discrete Applied Mathematics, 7 (1984), 105-109

22. Fujishige S., K. Makino, and T. Takabatake, Polybasic Polyhedra: Structure of Polyhedra with Edge Vectors of Support size at most 2, Research report No. 00-13 (August 2000), Division of System Science, Osaka University

23. Fujishige S. and Z. Yang, Indivisibilities, Money, and Equilibrium, Research report No. 00-08 (May 2000) Division of System Science, Osaka University

24. Gul F. and E. Stacchetti, Walrasian Equilibrium with Gross Substitutes, Journal of Economic Theory, 87 (1999), 95-124

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

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

27. Klee V. Asymptotes and projections of convex sets. Math.Scand. 8 (1960), 356-362

28. Данилов В.И. и Г.А. Кошевой (1999). О разделении замкнутых множеств, (рукопись) (см. Danilov V, G.Koshevoy, F. Page and M. Wooders, Sums of closed sets and equilibria in markets with short sales, Warwick University Working papers, 2003-04)

29. Murota K., Convexity and Steinitz's exchange property, Advances in Mathematics, 124 (1996), 272-311.

30. Murota K. and A, Shioura, M-convex functions on generalized polymatroids, Mathematics of operations research, 24 (1999), 95-105

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

32. Arrow K.J. (1994), Information and the organization of industry, in Markets, Information and Uncertanty, Essays in Economic Theory in Honnor of K.J.Arrow (ed. G. Chichilnisky), Cambridge University Press, Cambridge, 19-25

33. Arrow, K. and F. Hahn, 1971, General competitive analysis. North-Holland, Amsterdam.

34. Bevia, С., M. Quinzii and J.Silva, 1999, Buying Several Indivisible Goods, Mathematical Social Sciences 37, 1-23.

35. Bikhchandani, S. and J. W. Mamer, 1997, Competitive equilibrium in an exchange economy with indivisibilities, Journal of Economic Theory 74, 385-413.

36. Crawford, V. P. and E. Knoer (1981). Job matching with heterogeneous firms and workers. Econometrica 49, 437-450.

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

38. Danilov V.I., G.A.Koshevoy and A.I.Sotskov (1994), Equilibrium in a market of intellectual goods, Mathematical Social Sciences, 27,133144

39. Danilov, V.I., G.A. Koshevoy and A.I. Sotskov, 1995, Equilibrium in exchange economies with indivisibilities, mimeo (Book of abstracts of Symposium of Operations Research, Braunschweig (Germany) 1996, c. 134).

40. Danilov V.I., G.A.Koshevoy and A.I.Sotskov (1997), Equilibrium analysis of economies with novelties, J. of Mathematical Economics, 27, 195^2.2<?

41. Danilov V.I., G.A.Koshevoy and A.I.Sotskov (1999), A model of economic equilibrium in the market for information goods, in Contemporary Economic Issues, ed. M.Sertel, Macmillan Press and St. Martin's Press, New York, 161- 184

42. Danilov, V. I., G. A. Koshevoy, and C. Lang (2002). Gross substitution, discrete convexity and submodularity. Discrete and Applied Mathematics, (в печати)

43. Lov^sz L. (1983), Submodular functions and convexity, in A. Bachem, M.Gretschel and B.Korte, eds., Mathematical Programming: The State of the Art (Springer-Verlag, Berlin, New York) 235-257

44. Makarov V.L. (1991), About economies of intellectual goods and its modeling, Report at Sixth Congress of the European Economic Association, Cambridge, UK

45. McMullen, P., 1975, Space tiling zonotopes, Mathematika, 22, 202211

46. Murota, K., 1998, Discrete convex analysis, Mathematical Programming 83, 313-371.

47. Kaneko, M. (1982). The central assignment game and the assignment markets. Journal of Mathematical Economics 10, 1483-1504.

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

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

50. Quinzii, M., 1984, Core and equilibria with indivisibilities, International Journal of Game Theory 13, 41-61.

51. Shapley L.S., 1971, Cores of convex games, Intern. J. Game Theory, 1: 11-26

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

53. Arrow K. J. (1963). Social Choice and Individual Values, 2nd ed., Wiley, New York

54. M.A. Aizerman, New problems in the general choice theory, Social Choice and Welfare, 2 (1985), 235-282

55. K.Ando, Extreme point operator of convex geometries, Discrete mathematics (to appear)

56. C. Blair, The lattice structure of the set of stable matchings with multiple partners, Mathematics of Operations Research, 13 (1988), 619-628

57. P.H. Edelman and R. Jamison, The theory of convex geometries, Geom. Dedicata 19 (1985), 247-270.

58. Johnson, M.R. and Dean Richard A. (1996). An algebraic characterization fo path independent choice functions. Paper presented at Third International Meeting of the Society for Social Choice and Welfare, Maastricht, The Netherlands

59. K.Kashiwabara and Y.Okamoto, A greedy algorithm for convex geometries. Discrete and Applied Mathematics, (to appear).

60. Korte, В., L. Lov&sz and R. Schrader, (1991), Greedoids, Springer-Verlag, Berlin

61. Koshevoy G.A., (1999), "Choice functions and abstract convex geometries", Mathematical Social Sciences, 38, 35-44

62. Koshevoy G.A., Path-independence and closure operators with the anti-exchange property, Discrete and Applied Mathematics (принята к печати)

63. Koshevoy G.A. (1998). Choice functions and abstract convexity. Book of Abstracts of Forth International Meeting of the Society for Social Choice and Welfare, Vancouver, Canada, p. 54

64. Koshevoy G.A. (2000) Path-independence and closure operators with the anti-exchange property. Book of Abstracts of Ordinal and Symbolic Data Analysis Conference, Brussels University (Belgium) p.29

65. Кошевой Г.A. (2003). Функции выбора Плотта и выпуклые геометрии. Экономика и матем. Методы, т.38 (1)

66. Koshevoy G.A. and D. Talman, (2002). Competitive equilibria in economies with multiply divisible and multiple indivisible goods. Working Paper 2002-72, CentER (Tilburg University)

67. Malishevski A.V. (1994), Path independence in serial-parallel data processing, Mathematical Social Sciences, 27, 335-367

68. Малишевский А.В. (1998). Качественные модели в теории сложных систем. Наука. Физматлит. Москва

69. В. Monjardet (1990), The Consequences of Dilworth's Work on Lattices with Unique Irreducible Decompositions, in The Dilworth theorems. Selected works of Robert P. Dilworth, eds. K. Bogard, R. Freese, J. Kung, Birkhauser, Boston, 192-201

70. В. Monjardet and R. Raderanirina, The duality between the semi-lattice of anti-exchange closure operators and path-independent choice operators. Mathematical Social Sciences, 41 (2001), 131-150

71. H. Moulin, Choice functions over a finite set: a summary, Social Choice and Welfare, 2 (1985), 147-160

72. Nehring, K., (1997). Rational Choice and Revealed Preference without Binariness, Social Choice and Welfare, 14, 403-425

73. Plott C.R., (1973). Path independence, rationality and social choice, Econometrica, 41, 1075-1091

74. Sen A.K., (1986). Social Choice Theory, in Handbook in Economics, Volume III, (eds. K. Arrow and M. Intriligator), North-Holland, Amsterdam

75. Van de Vel, M. (1993). Theory of Convex Structures. North Holland, Amsterdam.