Matching problems

Many problems in the real world involve the matching up of people, resources or items. For example in many countries, centralised matching schemes perform allocations of children to schools taking into account preference information. On the one hand, children (or more likely, their parents) have ordinal preferences over local schools (i.e., first choice, second choice, etc.), whilst on the other hand, schools have preferences over children that are expressed in the form of priorities (e.g., based on catchment area and whether there is already a sibling at the school). These centralised matching schemes involve executing a matching algorithm that takes into account this preference and priority data and the number of seats at each school. Examples of regions that involve centralised matching schemes for school choice include New York and Boston. In these applications, typically the numbers of children and schools may be very large, so it is of paramount importance that the algorithms are as efficient as possible (i.e., run in seconds or minutes rather than hours or days).

In an allocation of children to schools, a blocking pair is a child c and a school s such that child c would prefer to attend school s over their currently allocated school, and school s would prefer to include child c over either having an empty position, or some other child who has been allocated to school s. The presence of such blocking pairs makes an allocation, or matching, unstable, and for obvious reasons it is desirable to have a stable matching instead.

We develop algorithms and models that can find stable matchings of children to such schools efficiently. Of course, our work is not restricted to the school choice problem, we also consider applications such as Kidney Paired Donations and Junior Doctor Allocation.