Project number: K143858
In this proposed project we would like to focus on matching and exchange markets, where central coordination mechanisms have been established for many application areas in the past decades. The seminal paper of Gale and Shapley on college admissions appeared in 1962, their solution concept of stable matchings and the deferred-acceptance algorithm have been used in many real applications, starting with the US resident allocation scheme (NRMP) in 1952, and implemented also for the Hungarian secondary school and university admissions. The basic exchange market model by Shapley and Scarf with the TTC algorithm by David Gale was published in 1974, and this model was proposed for organising kidney exchange programmes in and also used as a school choice mechanism in the US. The impactful work on this research line has also been recognised with the 2012 Nobel Memorial Award in Economic Sciences given to Roth and Shapley.
Our plan is to study new research questions in the above topic from a computational and game theoretical point of view. Our expected findings are mostly theoretical concerning the computational complexity of various solution concepts, such as the core of cooperative games. However, identifying these complexities can be important from a practical point of view as well,
as the designer of the mechanism can conclude whether an optimal solution can be computed efficiently, or some sort of heuristic methods needs to be used. These algorithms can be potentially applied as centrally coordinated matching mechanisms in the corresponding applications, such as university admissions, assignment of workers to jobs, kidney
exchange programmes, or financial clearing.
