Matching theory: the assignment of doctors to hospitals

Abstract

[en] The main goal of this work is to study two-sided matching markets where money is not involved. Matching theory is a branch of discrete mathematics that belongs to game theory. This theory considers markets with two disjoint sets, such as men and women, firms and workers or colleges and students. Each agent in a side has preferences over the agents on the opposite side. Then, a matching is a set of pairs formed by agents of different side. The first chapter of this project introduces the college admission problem, which is the model for a many-to-one two-sided market, where agents on one side (students) can only be matched to one partner while the agents on the opposite side (colleges) may have several partners. Chapter 2 is divided into two parts. The first one provides the theoretical basis to develop two-sided matching theory, since the notions of stability and optimality for matchings are studied in depth for the simplest case, that is, one-to-one matchings. The existence of stable matchings, their properties and the structure of the set of stable matchings is analyzed. The second part is focused on many-to-one matching problems, say the college admission problem, to analyse which results of the one-to-one matching carry over to the many-to-one matching. For many-to-one matching problems, Chapter 3 shows us a different notion of stability and the way it is related to the pairwise stability studied in Chapter 2. Chapter 4 is a real-life application of the theory of matchings: students who graduate from medical schools in US are typically employed as residents (interns) at hospitals, where they comprise a significant part of the labor force. Here we are going to present the first algorithm established by NIMP (National Intern Matching Program), which was the first centralized clearinghouse introduced. To finish, Chapter 5 introduces a new complication to the labor markets: the presence of couples. Here the model is introduced and for the first time we we are going to see that couples can cause the hospital-intern market not to have any stable matching. We are going to see also that under some restrictions in the preferences we can solve that problem.