Two-sided matching theory

Abstract

The purpose of this degree project is to study two-sided matchings where money is not involved.

Matching theory is a branch of discrete mathematics belonging 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 on one sector has preferences (a complete and transitive binary relation) over the set of agents on the opposite side. Then, a matching is a set of pairs formed by agents of different side, in such a way that one agent can take part in at most one pair.

We can situate its origin in the article of Gale and Shapley (1962) "College admissions and the stability of marriage" followed by the book of Knuth (1976), which first edition in French had the title of "Mariages stables".

The first chapter of this monograph focuses on the theory of one-to-one matching, that is known as the marriage problem. This chapter provides the theoretical basis to develop two-sided matching theory, since the notions of stability and optimality for matchings are studied in depth. Chapter 2 is devoted to many-to-one matching problems, say the college admission problem, to analyse until which extent the results obtained for one-to-one markets still hold. In these two chapters the existence of stable matchings, their properties and the structure of the set of stable matchings are studied.

Chapter 3 is a real-life application of the theory of matchings: the school choice problem. Here, we are going to analyse which algorithms have been used to fairly assign children to schools. This problem is currently under study, approached from the fields of mathematics, economics, operations research or computer science.