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

Mechanism Design: modern approaches

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

Goal of research

To apply a variety of modern theoretic and empirical approaches to solve a wide range of game-theoretic, economic and mechanism design problems (such as fair allocation of bads, problem of self-organized criticality, voting theory, corruption in auctions).

Methodology

The methodology is a combination of cutting-edge approaches for solving numerous tasks. It includes methods of probability theory, theory of finite-state machines, theory of approximation; methods of convex analysis, methods of discrete harmonic analysis; unified Bellman function method; methods of social choice theory; methods of semi-supervised machine learning, deep learning, classification and statistics; methods of behavioral economics.

For the Efficient algorithms for enumerating competitive allocations of bads, methods are based on a combination of three ideas: all consumption graphs of efficient allocations can be listed in polynomial time; for a given consumption graph a {candidate for a competitive allocation} can be constructed via explicit formula; a given allocation can be checked for being competitive using a MaxFlow computation.

Empirical base of research

Data for the research was extracted from the official ftp server of procurement auctions website: ftp://ftp.zakupki.gov.ru/

Results of research

We have shown that all the outcomes of CR for bads can be computed in polynomial time if either the number of agents or the number of bads are fixed.

We continue considering zero-sum games of players with incomplete information
on both sides, random public signal on the state of game and  limited computational capacity.
Players are computationally bounded by finite automata of different sizes:  m for Player 1 and nfor Player 2 where m>>n. We obtain a lower bound for m and an upper bound for  n which may turn the original game with incomplete information for both players into
a game with incomplete information for Player 2.

We have proved the finiteness of individual utilities in competitive equilibria for divisible assignment problems.

We have discovered, that information avoidance is sensitive to the order of making a decision on information disclosure and is insensitive to the probability of conflict. Both results show, that when making a decision whether to avoid the information, experimental subjects act not strategic, but rather short-sighted.

We have built a continuous model of self-organising criticality and have proven corresponding theorems about tropical sequences and tropical analytical curves.

We have constructed a social choice rule satisfying the criteria of first order positional dominance, mutual majority, and Condorcet loser. We showed that the rule satisfies other desirable properties, such as positive responsiveness, idempotency, and reversal symmetry.

We have solved the problem of optimal information disclosure for the case of no private information of participants.

First estimates of spread of corruption are obtained - about 10\%; a prototype of automated bid leakage detection algorithm is built; initial analysis of economically relevant effects of corruption presence is conducted

We have described how the Bellman function for the functional varies when f runs over a certain parametric family of functions.

We have described a new class of differential games with continuous refreshment of information. We have described a method of building cooperative strategies and positional Nash equilibrium for the model of dynamic information refreshment.

We have formally defined optimal behaviour of players in bargaining model of Ariel Rubinstein with respect to dynamic nature of the estimation of discounting coefficient that players receive as parts of their profits.

We have studied a strategic behavior on the carpooling market. Such behavior thinners the market on both sides, which is consistent with reality. By introducing a simple time lag between the submission and announcement the market designer can improve the outcome.

We have introduced the model of school choice that matches Russian reality. We have conducted equilibrium analysis of mechanism, which is currently used by many schools of Russia in Saint-Petersburg, Moscow and other cities. It was shown, that current mechanism has both advantages and disadvantages and requires more detailed research.

We have considered the game of search on undirected graph, where strategies of search with various features of players are built, for instance, connected and monotonous. Also, we find upper estimates of minimal number of players, which ensures successful search.

Level of implementation,  recommendations on implementation or outcomes of the implementation of the results

Developed algorithms can be used for real-world implementation of mechanisms for fair and efficient distribution of tasks between workers.

Strong evidence of corruption presence suggest, that system of procurement should be changed. For instance, if first-price auctions are replaced with second-price auctions, bid leakage would be useless. Suggested algorithm of automated bid leakage detection in requests for quotation might be useful for regulation, as manual detection of bid leakage is a complex and usually intractable issue.

The constructed rule can be used in the systems of automatic decision making, where a selected alternative should dominate each other alternative by positions and by majority of decisive parameters. 

Studies of the Bellman function method in harmonic analysis are theoretical. But it is worth noting that apart from the fact that this method allows to obtain sharp constants in various harmonic analysis inequalities, it shows deep connections between harmonic analysis, differential geometry, and stochastic processes.

The results on strategic behavior on the carpooling market can be implemented in Blablacar carsharing platform in order to prevent drivers from strategic behaviour and increase the quality of trips performed through the platform.

Publications:


Bogomolnaia A., Moulin H., Sandomirskiy F. A simple Online Fair Division problem // Working papers by Cornell University. Series CS "arxiv.org" (США). 2019
Kalinin N. LEGENDRIAN CURVES IN CP^3: CUBICS AND CURVES ON A QUADRIC SURFACE // Journal of Mathematical Sciences. 2018. Vol. 476. P. 92-110.
Yanovskaya E. B. Self-Covariant and Consistent Solutions of Transferable Utility Cooperative Games // Automation and Remote Control. 2018. Vol. 79. No. 12. P. 2237-2258. doi
Moulin H., Caragiannis I., Kurokawa D., Procaccia A. D., Shah N., Wang J. The Unreasonable Fairness of Maximum Nash Welfare // ACM Transactions on Economics and Computation. 2018
Hougaard J., Moulin H. Sharing the cost of risky projects // Economic Theory. 2018. Vol. 65. No. 3. P. 663-679. doi
Kreps V. L., Gavrilovich M. Games with symmetric incomplete information and asymmetric computational resources // International Game Theory Review. 2018. Vol. 20. No. 2. P. 1-16. doi
Gordon J., Panina G., Teplitskaya Y. Polygons with prescribed edge slopes: configuration space and extremal points of perimeter // Beitrage zur Algebra und Geometrie. 2018. P. 1-15. doi
Kalinin N., Guzmán-Sáenz A., Prieto Y., Shkolnikov M., Kalinina V., Lupercio E. Self-organized criticality and pattern emergence through the lens of tropical geometry // Proceedings of the National Academy of Sciences of the United States of America. 2018. Vol. 115. No. 35. P. E8135-E8142. doi
A. Yu. Kondratev. Positional Voting Methods Satisfying the Criteria of Weak Mutual Majority and Condorcet Loser // Automation and Remote Control. 2018. Vol. 79. No. 8. P. 1489-1514. doi
Gavrilovich M. Expressing the statement of the Feit-Thompson theorem with diagrams in the category of finite groups // Archive for Mathematical Logic. 2018
Gavrilovich M. Standard conjectures in model theory, and categoricity of comparison isomorphisms // Advances in Mathematics. 2018
Kalinin N., Shkolnikov M. Introduction to tropical series and wave dynamic on them // Discrete and Continuous Dynamical Systems. 2018. Vol. 38. No. 6. P. 2827-2849. doi
Zseleva A., Flesch J., Vermeulen D. Catch Games - The impact of modeling decisions // International Journal of Game Theory. 2018
Zseleva A., Ifrach B., Maglaras C., Scarsini M. Bayesian Social Learning from Consumer Reviews // Operations Research. 2018
Gavrilovich M. A diagram chasing formalisation of elementary topological properties // Bulletin of Symbolic Logic. 2018