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

Взаимодействие аксиоматического и алгоритмического подходов в теории игр

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

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

Используемые методы: Наши исследования основаны на комбинации методов современной теории игр (аксиоматической, алгоритмической и стратегической), методов теории вероятностей, теоретической информатики, исследования операций, теории оптимального стохастического управления, стохастической геометрии, комбинаторики.

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

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

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

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

Построено свойство согласованности, которому удовлетворяет решение SD-prenucleolus и построена аксиоматическая характеризация SD-prenucleolus с помощью трех свойств - согласованности, анонимности и ковариантности.

Найден класс кооперативных игр,  для. которого ранее построенное решение, названное SD-решением, является монотонным. Ранее этот результат был получен для более узкого класса выпуклых игр. Таким образом, на настоящий момент  SD–решение является единственным из известных решением, для которого свойства устойчивости и монотонности выполняются на максимальном классе кооперативных игр.

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

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

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

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


Bogomolnaia A. Random assignment: redefining the Serial rule // Journal of Economic Theory . 2015. No. 158. P. 308-318.
Bogomolnaia A. Size versus fairness in the assignment problem // Games and Economic Behavior. 2015. P. 119-127.
Bogomolnaia A. The Most Ordinally-Efficient of Random Voting Rules / NRU Higher School of Economics. Series WP BRP "Economics/EC". 2015.
Sandomirskiy F. Repeated games of incomplete information with large sets of states // International Journal of Game Theory. 2014. Vol. 43. No. 4. P. 767-789. doi
Gavrilovich M., Kreps V. L. On a Class of Optimization Problems with No 'Effectively Computable' Solution / NRU Higher School of Economics. Series WP BRP "Economics/EC". 2015. No. WP BRP 112/EC/2015 .
Ivashchenko S. Estimating Nonlinear DSGE Models with Moments Based Methods // Frontiers of Economics in China. 2015. Vol. 10. No. 1. P. 38-55.
Gavrilovich M., Hasson A. Exercises de style: A homotopy theory for set theory // Israel Journal of Mathematics. 2015. Vol. 209 doi
Sandomirskiy F. On repeated zero-sum games with incomplete information and asymptotically bounded values / Cornell university, arXiv.org. Series arXiv:1509.01727 "Computer Science". 2015.