For those suffering from end-stage kidney disease, the ideal outcome is kidney transplantation from a living donor. Finding such a donor is not easy, however, as there is both the requirement for someone willing to give up a kidney, as well as someone who is medically compatible. If a patient has a willing but incompatible donor, and there is a second donor-patient pair, also medically incompatible, it may be possible for the two patients to "exchange" donors in order to obtain a compatible kidney.
To make finding such swaps easier, large groups of donor-patient pairs are formed into pools. In the UK, such a pool is managed by the National Health Service Blood and Transplant (NHSBT) as part of the UK Living Kidney Sharing Scheme. Periodically, the pool is searched for exchanges — groups of donor-patient pairs where every donor donates a kidney to one compatible patient. The simplest exchange is the one we mentioned, between two donor-patient pairs. This is called a 2-way exchange. NHSBT also allows 3-way exchanges, between three donor-patient pairs.
Matching these pairs can be complicated. Many different parameters must be considered, and certain matchings can be considered better matchings than others (based on medical information about the donors and patients). We design algorithms to model pools of kidney donors and kidney patients, including all relevant information), and then find an optimal matching based on externally-set criteria.
To receive a full medical license, junior doctors must complete a residency programme. These programmes are offered by hospitals, and a given programme can often accept multiple junior doctors while each junior doctor can only attend one programme. Additionally, certain hospitals are more desirable than others. Thus these junior doctors can express preferences over programmes, and at the same time the programmes can express preferences over the junior doctors. In many cases, the preferences of the programmes are determined either in part or in whole by exam results of the junior doctors.
The desired outcome is an allocation of junior doctors to programmes that avoids blocking pairs. A blocking pair is a junior doctor and programme where the junior doctor would prefer to be allocated to the hospital programme, and the programme would prefer to include the junior doctor as part of their allocation. A matching with no blocking pairs called stable, and the goal is to find a stable matching that allocates as many junior doctors to programmes as possible.
Finding stable matchings alone is difficult, but this problem has a number of added challenges. Some doctors are part of couples, i.e. in a relationship. Such doctors would prefer to be working in a similar geograph area, so where one doctor gets assigned could potentially make other choices unavailable for their partner.