• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Algorithmic aspects of fair division problems

Priority areas of development: mathematics
2016
The project has been carried out as part of the HSE Program of Fundamental Studies.

Goal of research:

To carry out normative analysis of fair resource allocation mechanisms; to construct efficient algorithms for computation of their output; to use methods of algorithmic game theory for modeling strategic behavior of agents with bounded rationality and incomplete information; application of dynamic models of strategic behavior of bounded rational agents for description of macroeconomic dynamics.

Methodology:

Strategic and cooperative game theory (strategic analysis, axiomatic approach, bargaining theory methods, methods of social choice and mechanism design), general equilibrium theory, theory of computational complexity, optimization theory, functional analysis and topology, convex geometry, random processes and stochastic geometry.

Empirical base of research:

Research is of theoretical nature.

Results of research:

Microeconomic problems of fair allocation of resources arise in a variety of situations: division of family heirlooms, dividing job shifts between substitutable workers, partnership dissolution, assignment of students to dormitories or to overdemanded courses, assigning scientific papers to referees, dividing the noxious facilities between different countries, etc.

Various types of such problems were considered. For fair division of divisible goods or bads (i.e., job shifts or loans) between agents with additive utilities an axiomatic characterization of the Competitive rule was obtained. The Competitive rule is an especially appealing efficient and envy-free division of private goods when utilities are additive: it maximizes the Nash product of utilities and is single-valued and continuous. It is shown that Competitive rule to divide bads captures similarly the critical points of the Nash product in the efficient frontier. But it is far from resolute, allowing routinely many divisions with sharply different welfare consequences. Even the much more permissive No Envy property is profoundly ambiguous in the division of bads: the set of efficient and envy-free allocations can have many connected components, and has no single-valued selection continuous in the marginal rates. The Competitive rule to divide goods is Resource Monotonic (RM): everyone (weakly) benefits when the manna increases. But when we divide bads efficiently, RM is incompatible with Fair Share Guarantee, a much weaker property than No Envy. An axiomatic characterization of Competitive rule is obtained.

Problems of allocating N indivisible objects among N agents according to their preferences where each agent needs exactly one object are the famous assignment problems. Tradeoff between efficiency and fairness in the class of strategy-proof mechanisms was examined. Three impossibility results showing mutual incompatibility of fairness and efficiency are obtained. Two new axiomatic characterizations of celebrated random serial dictatorship mechanism are provided. For fair division problems with indivisible goods when the number of agents is fixed and the number of goods tends to infinity existence of envy-free allocations with high probability is shown.

Problems of distributing the common surplus between several agents according to their contributions are modeled by cooperative games. A new solution concept for cooperative TU games, The Surplus Distributor Prekernel, was introduced. Like the prekermel, the new solution is based on an alternative motion of complaint of one player against other with respect to an allocation. The SD-prekernel contains the SD-prenucleolus and they coincide in the class of convex games. This result allows proving that in bankruptcy problems the SD-prekernel and the Minimal Overlapping rule select the same allocation.

In strategic social and economic interactions information plays an important role. Often the information is asymmetric between agents, e.g., seller knows more about the quality of a certain item, but does not know exactly the preferences of the buyer. It is shown that information asymmetry may arise from bounded computation power of agents, i.e., from bounded rationality. For zero-sum games the impact of bounded computational abilities on the information structure is described. It is provided that the difference in computational power may lead to information asymmetry in a game, where initially both players have symmetric incomplete information.

Dynamic models of strategic behavior of agents with bounded rationality are used to describe macroeconomic dynamics. For a class of such models, Markov-switching dynamic stochastic general equilibrium models (MS-DSGE), a new fast deterministic filter is developed. MS-DSGE is a generalization of DSGE models that has become popular in the last few years. DSGE models are key instruments of macroeconomic analysis which are widely used by central banks and other organizations across the world. The new methods of nonlinear approximations allow taking into account risks and information asymmetry. 

Publications:


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.