![]()
Chapter 1
Preliminary definitions, results and motivation
1.1 Introduction
1.1.1 Remit of this book
1.1.1.1 Matching under preferences
This book is about computational problems that involve matching agents to one another, subject to various criteria. Here, the term agent is used loosely to mean any participant in a matching process, and could include commodities in addition to human subjects. In many cases the agents form two disjoint sets, and we seek to assign the agents in one set to those in the other. Examples include assigning junior doctors to hospitals, pupils to schools, kidney patients to donors, and so on.
We primarily focus on the case that a subset of the agents have ordinal preferences over a subset of the others. That is, there is a notion of first choice, second choice, third choice, etc. For example a school-leaver who is applying for admission to university might rank in order of preference a small subset (say 5) of all available universities. Likewise, the universities might form a ranking of their applicants according to academic merit, and possibly other criteria. We will not always insist that the preference lists be strictly ordered: for example a school-leaver might have two universities that are jointly ranked as first choice in her preference list.
Typically there are other constraints in addition to the preference lists: for example, it is reasonable to assume that a school-leaver should not be assigned to more than one university, and likewise a university might have a capacity, indicating the maximum number of students that it could admit in a particular academic session.
1.1.1.2 Free-for-all markets
Applications of matching problems involving ordinal preferences (henceforth the term ordinal preferences will be shortened to preferences) can be very large in practice. For example in 2011, 140,953 students applied for admission to higher education in Hungary [90]. Economists have identified several problems that arise in free-for-all markets, in which the agents are able to negotiate with one another directly in order to arrange assignments [518, 467].
These problems include unravelling in which agents form assignments with one another earlier and earlier in advance of the deadline by which all assignments must be fixed. For example, hospitals wishing to recruit the best applicants might compete with one another by advancing the date when they make their offers. To avoid this issue, agents might be prevented from entering into premature assignments before a certain date.
This can then lead to the problem of congestion, in which agents do not have sufficient time to negotiate with one another over potential assignments prior to the deadline. For example a hospital h offering 20 places to applicants might have to make substantially more than 20 offers, to allow for applicants who will turn down h’s offer.
In an effort to avoid congestion, a new problem might emerge, namely exploding offers. In such a case, agents are given only a short time period to decide whether they are able to form a given assignment, otherwise the potential for making that assignment is removed. For example hospital h might force an applicant r to make a decision swiftly by setting r a deadline, beyond which the offer expires. Unravelling, congestion and exploding offers lead to a situation in which agents might be forced into forming an assignment with one another before they have knowledge of the whole range of potential assignments that may potentially be available to them.
Prior to 1952, the assignment of junior doctors to hospitals in the USA was carried out by a free-for-all market. A detailed description of the problems that this led to (which included unravelling, congestion and exploding offers as described above), with reference to this particular application, has been given in several references in the literature [261, 514, 518, 467].
1.1.1.3 Centralised matching schemes
Centralised matching schemes (referred to as (centralised) clearinghouses by economists) can avoid some of the problems that are inherent in free-for-all markets. These work along the following lines: the input data involving the agents and their preferences over one another are collected by a given deadline by a trusted central authority. This third party then compu...
