• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Алгоритмические аспекты задач справедливого распределения

Приоритетные направления развития: математика
2016

Цель работы:

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

Используемые методы:

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

Эмпирическая база исследования:

Исследование носит теоретический характер.

Результаты работы:

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

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

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

Исследованы задачи распределения общей прибыли при различии вкладов участников. Определено и новое решение кооперативных игр – SD пред k-ядро, которое содержит одноточечное решение SD пред n-ядро, исследованное в 2015 году. Определен класс вполне релевантных игр  и показано, что на этом классе игр оба эти решения совпадают. Класс вполне релевантных игр включает в себя выпуклые игры и, соответственно,  класс игр банкротства. Для этого класса игр доказано, что SD пред k-ядро совпадает с известным правилом минимального перекрывания.

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

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

Публикации по проекту:


Bogomolnaia A., Moulin H., Sandomirskiy F., Yanovskaya E. B. Dividing goods or bads under additive utilities / Cornell university, arXiv.org. Series arXiv:1608.01540 "Computer Science". 2016.
Moulin H. Entropy, desegregation, and proportional rationing // Journal of Economic Theory . 2016. Vol. 162. P. 1-20. doi
Ivashchenko S. Estimation and Filtering of Nonlinear Ms-Dsge Models / NRU Higher School of Economics. Series WP BRP "Economics/EC". 2016. No. WP BRP 136/EC/2016 .
Kreps V. L., Domansky V. Bidding Games with Several Risky Assets // Automation and Remote Control. 2016. Vol. 72. No. 8. P. 346-357.
Arin J., Katsev I. The SD-prekernel for TU games / University of the Basque Country. Series IL. 96/16 "Ikerlanak". 2016.
Bogomolnaia A., Moulin H., Sandomirskiy F., Yanovskaya E. B. Dividing goods and bads under additive utilities / Cornell university, arXiv.org. Series arXiv:1610.03745 [cs.GT] "Computer Science". 2016.
Ivashchenko S., Gupta R. Near-Rational Expectations: How Far are Surveys from Rationality? / University of Pretoria, Department of Economics. Series University of Pretoria, Department of Economics "University of Pretoria, Department of Economics". 2016. No. 201655.
Moulin H., Caragiannis I., Kurokawa D., Procaccia A. D., Shah N., Wang J. The Unreasonable Fairness of Maximum Nash Welfare, in: Proceeding of the 17th ACM Conference on Economics and Computation. , 2016. doi
Elena Yanovskaya. The Bounded Core for Games with Restricted Cooperation / Пер. с рус. // Automation and Remote Control. 2016. Vol. 77. No. 9. P. 1699- 1710. doi
Kreps V. L. On Maximal Vector Spaces of Finite Non-Cooperative Games / NRU Higher School of Economics. Series WP BRP "Economics/EC". 2016. No. WP BRP 150/EC/2016 .
Маричева А. В. Отсутствие зависти в задачах распределения большого числа неделимых благ // В кн.: Научно-техническая конференция студентов, аспирантов и молодых специалистов НИУ ВШЭ им. Е.В. Арменского. Материалы конференции. / Под общ. ред.: А. Н. Тихонов, С. А. Аксенов, У. В. Аристова, Л. Н. Кечиев, В. П. Кулагин, Ю. Л. Леохин, А. Б. Лось, И. С. Смирнов, Н. С. Титкова. М. : МИЭМ НИУ ВШЭ, 2016. С. 36-37.
Ivashchenko S., Gupta R. Forecasting using a Nonlinear DSGE Model / University of Pretoria, Department of Economics . Series University of Pretoria, Department of Economics "University of Pretoria, Department of Economics ". 2016. No. 201659.
Gavrilovich M., Kreps V. L. On a class of optimization problems with no "effectively computable'' solution / Пер. с рус. // Journal of Mathematical Sciences. 2016. Vol. 215. No. 6. P. 706-715. doi
Bogomolnaia A., Moulin H., Sandomirskiy F., Yanovskaya E. B. Dividing Goods and Bads Under Additive Utilities / NRU Higher School of Economics. Series EC "Economics". 2016. No. 153.
Sandomirskiy F. On repeated zero-sum games with incomplete information and asymptotically bounded values / NRU Higher School of Economics. Series EC "Economics". 2016. No. 148.
Bogomolnaia A., Moulin H., Sandomirskiy F., Yanovskaya E. B. Dividing Goods or Bads Under Additive Utilities / NRU Higher School of Economics. Series EC "Economics". 2016. No. 147.