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

Mechanism Design: internet-markets

Priority areas of development: economics, management, mathematics
2019
Head: Moulin, Hervé, Nesterov, Alexander S.

Goal of the research project

To answer a variety of modern research questions in the field of mechanism design and game theory using multiple theoretic and empirical approaches.

Methodology

The methodology is a combination of cutting-edge approaches for solving numerous tasks. It includes methods of experimental economics, competitive analysis from the theory of online algorithms and the interplay between convexity and probability, in particular, the splitting lemma that links convexification of a function and expectation over martingales, theory of approximation, game-theoretic methods and basic methods of set theory and graph theory, methods of machine learning, probability theory, in particular the theory of stopping time processes, algebraic methods and methods of matrix game theory, non-standard expected utility theories, statistical inference, and studies in prediction markets, deep learning,

Empirical base of research

The absolute majority of our research projects are theoretical and experimental (based on synthetic data and computer simulations). Data for the research project on auctions was extracted from the official ftp server of procurement auctions website: ftp://ftp.zakupki.gov.ru/

Results of research

We studied the mechanism of decision making in the presence of a possible conflict of interests and incompleteness of information in case of a doctor-patient relationship. We conducted a pilot experiment with a binary version of the dictator game where we added medical framing with medical and non-medical students. We didn’t find a difference in the behavior of these two subject groups.

We found a family of prior-independent fair rules such that any other fair prior-independent rule collects strictly less welfare ex-post for some input. For two agents, there exists only one such dominating rule, while for more than two agents undominated rules form a one-parametric family.

We showed that when studying the phenomenon of cheating among students, data on the level of students' training and motivation and teachers' ability to fight against cheating cannot be excluded. The proposed theoretic-game model of cheating on the written exam has several equilibria when the student always cheats and the teacher never interferes with him/her, there is an equilibrium in mixed strategies, and there is no equilibrium where the teacher would always try to catch cheaters - the latter situation is unstable. The difference between the model and the available literature is that the student has a type which depends on the level of expertise; the higher the level of expertise, the less the need for cheating arises.

We introduced a modification of Beauty-contest game to model situation in which agents benefit from being different from other agents. We provided a full description of Nash equilibria in pure strategies and show that there is no symmetric equilibrium in pure strategies. Also, we have presented some findings on symmetric Nash equilibria in mixed strategies for 3 players received by using numerical methods.

We proposed a new notion to compare non-strategy-proof mechanisms called strategic accessibility. A mechanism is less strategically accessible than another if each school can be accessed by fewer students via manipulation (and thus each student can access fewer schools by manipulation). We have shown that in each of the observed reforms the mechanism became less strategically accessible.

We provided the first proof of concept that machine learning methods are highly suitable for building crop meta-models for spatio-temporal downscaling and indicate the potential for further developments towards scalable crop model emulators.

We built models based on the two well-known stopping problems: the secretary problem and a model in auction theory. We have shown that in our models the optimal threshold strategy yields a significantly lower probability of winning. We started developing software to search for optimal strategies in the models we build.

We proposed a computationally simple criterion to check the value positivity for matrix game

For a proposition and a population of relevant experts, we introduced the notion of the collective probability of the proposition and proposed an operational method for its elicitation based on self-resolving prediction markets.

Simulations results showed that the characteristics of the preferences such as correlation and intercorrelation influence the efficiency of the considered Decentralized, Deferred Acceptance, Boston and Random mechanisms but do not affect dramatically the choice of the most efficient mechanism by both musicians and orchestras. Overall, musicians gain more from centralized mechanisms and orchestras gain more from decentralized mechanisms. The results also indicated that we can split markets for different types of musicians into three groups: with conflicting interests (harp, horn, trumpet, piano, drums and violin musicians), with common interests in centralization (viola and flute musicians) and with nearly common interests in centralization (cello, oboe, bassoon, clarinet, trombone, tuba and double bass musicians).

We proposed a novel machine-learning-based approach to detect corruptive bid leakage in first-price sealed-bid auctions. We have extracted and analyzed the data on more than 1.4 million Russian procurement auctions between 2014 and 2018. As bid leakage in each particular auction is tacit, the direct classification is impossible. Instead, we reduced the problem of bid leakage detection to positive-unlabeled classification. The key idea is to regard the losing participants as fair and the winners as possibly corrupted. This allowed us to estimate the prior probability of bid leakage in the sample – 16%, as well as the posterior probability of bid leakage for each specific auction.

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

The results can be used in designing less manipulable matching mechanisms, and, more generally, other mechanisms: auctions, voting, etc.

Publications:


Aziz H., Moulin H., Sandomirskiy F. A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation / Cornell university. Series Computer Science and Game Theory (cs.GT), arXiv:1909.00740. "arXiv". 2019. 
Осипов Н. Н. Функция Беллмана для параметрического семейства экстремальных задач в пространстве BMO // Записки научных семинаров ПОМИ РАН. 2018. Т. 467. C. 128-142. 
Bogomolnaia A., Moulin H., Sandomirskiy F. A simple Online Fair Division problem // Working papers by Cornell University. Series CS "arxiv.org" (США). 2019. P. 1-29. 
Dietzenbacher B., Borm P., Hendrickx R. A procedural egalitarian solution for NTU-games // Discrete Applied Mathematics. 2019. P. 1-25. doi
Branzei S., Sandomirskiy F. Algorithms for Competitive Division of Chores / Cornell university. Series Computer Science and Game Theory (cs.GT), arXiv:1907.01766. "arxiv". 2019. 
Shchepashchenko D., See Linda, Lesiv M., Baklanov A., Fritz S. Recent Advances in Forest Observation with Visual Interpretation of Very High-Resolution Imagery // Surveys in Geophysics. 2019. Vol. 40. No. 4. P. 839-862. doi
Folberth C., Baklanov A., Balkovič J., Skalský R., Khabarov N., Obersteiner M. Spatio-temporal downscaling of gridded crop model yield estimates based on machine learning // Agricultural and Forest Meteorology. 2019. Vol. 264. P. 1-15. doi
Bogomolnaia A., Moulin H., Sandomirskiy F., Yanovskaya E. B. Dividing bads under additive utilities // Social Choice and Welfare. 2019. Vol. 52. No. 3. P. 395-417. doi
Gavrilovich M. Standard conjectures in model theory, and categoricity of comparison isomorphisms // Communications in Algebra. 2019. 
Zseleva A., Ifrach B., Maglaras C., Scarsini M. Bayesian social learning from consumer reviews // Operations Research. 2019. Vol. 67. No. 5. P. 1209-1221. doi
V.L. Kreps Bidding Models and Repeated Games with Incomplete Information: A Survey // Автоматика и телемеханика. 2019. Vol. 80. No. 2. P. 362-379. doi
Ivanov D. DEDPUL: Difference-of-Estimated-Densities-based Positive-Unlabeled Learning / Cornell University. Series Computer Science "arxiv.org". 2019. 
Ianovski E. Electing a committee with dominance constraints / Cornell University. Series arxive "math". 2019. 
Shkolnikov M., Kalinin N. Tropical formulae for summation over a part of SL(2,Z) // European Journal of Mathematics. 2019. Vol. 5. No. 3. P. 909-928. doi
Moulin H. Fair Division in the Internet Age // Annual Review of Economics. 2019. Vol. 11. P. 407-441. doi
Sandomirskiy F., Segal-Halevi E. Fair Division with Minimal Sharing / Cornell university. Series Computer Science and Game Theory (cs.GT), arXiv:1908.01669. "arXiv". 2019. 
Zseleva A., Flesch J., Vermeulen D. On the equivalence of mixed and behavior strategies in finitely additive decision problems // Journal of Applied Probability. 2019. Vol. 56. No. 3. P. 810-829. doi
Крепс В. Л., Гаврилович М. Р. Расшифровка сигналов с помощью конечных автоматов: применение к играм с неполной информацией // Математическая теория игр и ее приложения. 2019. Т. 11. № 1. C. 21-38. 
Moulin H., Caragiannis I., Kurokawa D., Procaccia A., Shah N., Wang J. The Unreasonable Fairness of Maximum Nash Welfare // ACM Transactions on Economics and Computation. 2019. Vol. 7. No. 3. P. 1-32. doi
Malinnikova E., Nikolay N. O. Two Types of Rubio de Francia Operators on Triebel–Lizorkin and Besov Spaces // Journal of Fourier Analysis and Applications. 2019. Vol. 25. No. 3. P. 804-818. doi
Ianovski E., Wilson M. C. Manipulability of consular election rules // Social Choice and Welfare. 2019. Vol. 2. No. 52. P. 363-393. doi
Moulin H., Bogomolnaia A., Aziz H. Fair Mixing: the case of dichotomous preferences, in: Proceeding of the ACM Conference EC19.: Association for Computing Machinery (ACM), 2019. С. 753-781. 
Gavrilovich M. Formulating basic notions of finite group theory via the lifting property / Cornell University. Series math "arxiv.org". 2020. 
Dietzenbacher B., Borm P., Arantza E. NTU-bankruptcy problems: consistency and the relative adjustment principle // Review of Economic Design. 2019. P. 1-22. doi
Moulin H., Seth A., Taub B. Self-enforcing cooperation via strategic investment // Economic Theory Bulletin. 2019. P. 1-11. doi
Baklanov A., Khachay M., Pasynkov M. Fully Convolutional Neural Networks for Mapping Oil Palm Plantations in Kalimantan, in: 12th International Conference, LION 12, Kalamata, Greece, June 10–15, 2018, Revised Selected Papers.: Springer, 2019. С. 427-432. 
Kuchkarov I., Petrosian O. On Class of Linear Quadratic Non-cooperative Differential Games with Continuous Updating, in: Mathematical Optimization Theory and Operations Research, 18th International Conference, MOTOR 2019 Ekaterinburg, Russia, July 8–12, 2019.: Springer, 2019. С. 635-650. 
Mironov V., Kondratev A., Mironova A. Growth of Sphagnum is strongly rhythmic: contribution of the seasonal, circalunar and third components // Physiologia Plantarum. 2020. Vol. 168. No. 4. P. 765-776. doi
Kondratev A., Ianovski E., Nesterov A. S. How should we score athletes and candidates: geometric scoring rules / Cornell University. Series Computer Science "arxiv.org". 2019. 
Ivanov D., Nesterov A. S. Identifying Bid Leakage In Procurement Auctions: Machine Learning Approach / Cornell University. Series arxiv.org. "Economics". 2019. 
Kondratev A., Nesterov A. S. Minimal Envy and Popular Matchings / Cornell University. Series Computer Science "arxiv.org". 2019. 
Ben-Porat O., Sandomirskiy F., Tennenholtz M. Protecting the Protected Group: Circumventing Harmful Fairness / Cornell University. Series Computer Science "arxiv.org". 2019. 
Gavrilovich M. Simplicial sets with a notion of smallness / Cornell University. Series math "arxiv.org". 2019. 
Gavrilovich M. Standard conjectures in model theory, and categoricity of comparison isomorphisms. A model theory perspective / IHES. Series Les Publications mathématiques de l’IHES. "IHES/M/19/03". 2019. 
Aleksandra L. G. Stochastic n-person prisoner's dilemma: the time-consistency of core and Shapley value, in: Contributions to Game Theory and Management Volume XII.: Издательство СПбГУ, 2019. С. 151-158. 
Гриних А. Л. Об одном коалиционно-устойчивом решении в конечношаговой игре "дилеммы заключённого", in: Процессы управления и устойчивость Том 6 (22). Санкт-Петербург : Издательский дом Федоровой Г.В., 2019. С. 409-413. 
Kondratev A., Mazalov V. V. Tournament solutions based on cooperative game theory // International Journal of Game Theory. 2020. Vol. 49. No. 1. P. 119-145. doi