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

Interplay of Axiomatic and Algorithmic Game Theory

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

Goal of research: The main goal is to bring together the expertise of the Laboratory and that of its foreign members to develop new connections between the algorithmic and asymptotic approaches that are so far     focused on non cooperative models, and the normative theory of cooperative and fair solution concepts, that has so far ignored the potetial complexity of its implementation.

Methodology: Our research is based on a combination of methods applied in the contemporary game theory: axiomatic, algorithmic  and strategical, on  methods of probability theory such as stochastic geometry, random matrix theory and concentration of measure tools. We apply also  stochastic optimization methods and combinatorics.

Empirical base of research: The research has a theoretical  character.

Results of research:

For the class of divisible fair allocation problems some previous results of computer modelling have being obtained. An algorithm finding the Nash maxproduct solution was realized.  With its help several hypothesis on its properties for an enough general case, when  there are big number of objects to be allocated, and individual utilities are independent idential distributed random values with continuous density, were proposed. One of the hypothesis is an assumption then the solution allocations are envy free with a great probability.

For matrix games of big size with random  Gauss distributed entries the hypothesis of Johansson that the supports of optimal strategies for such matrices approximately equal one half of the number of all strategies have been checked.

For the optimal strategies we obtained the joint distribution of its support sizes and weights.

A new consistency property has been defined. The SD-prenucleolus satisfies this property. Also, an axiomatic characterization of the SD-prenucleolus has been defined. This characterization uses three properties: consistency, anonymity and covariance.

With the help of a new invariance axiom - self-covariance  - that is weaker than the popular covariance axiom, the class of cost sharing methods for two agents (Moulin 2000) has been extended to the solutions    for the whole class of two-person cooperative games. In particular, the solution for superadditive games gives the extension of Moulin's methods to the class of two-person surplus sharing problems.

For a class of big optimization problems  the absence of  "efficiently calculable"   strategies has been proved. It was shown that when the size of a big problem tends to infinity, the equiprobable mixed strategy approximates the optimal one. The absence of efficiently calculable strategy giving a result for every optimization problem has been proved as well.

The nonlinear models with two main types of sticky prices are estimated for set of the countries. The first type of price rigidity is Calvo pricing (that suggests heterogeneous agents). The second one is Rotemberg pricing (that suggests homogenous firms). The Calvo pricing produces significant better performance for large share of countries in the sample. However, the opposite is true for some countries. Thus, we generate the list of countries which are the more favorable for models with heterogeneous agents.

Publications:


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.