Stable pairs

How e dey work, well well

Everybody rank ALL di other participants. Na one group only, so no asymmetry between proposers and receivers.

First phase: everybody propose to di highest-ranked person wey never reject dem; proposals wey improve things dey provisionally accepted, di worse ones dey rejected. Na so reduced table dey come out.

Second phase: dem dey find and remove rotations — chains of cyclic preferences wey dey block stability — until everybody get exactly one partner, or di table empty, wey prove say no solution dey.

Di matching wey come out dey stable: no two people wey dem no pair together dey prefer each other pass dia current partner.

Example wey get figures

Four people to pair, each one don rank di other three.

Person	1st	2nd	3rd
Chloé	Ali	Bruno	Dana
Ali	Chloé	Dana	Bruno
Bruno	Dana	Chloé	Ali
Dana	Bruno	Ali	Chloé

Chloé and Ali put each other first: dat pair settle.
Bruno and Dana do di same: second pair.
No outside pair prefer each other: di matching dey stable.

Here di preferences fit each other perfectly. Change only one ranking and di stable matching fit disappear completely — na di fragility wey dey special to dis problem.

Where e come from

David Gale and Lloyd Shapley raise di problem for 1962, for di end of dia founding paper on stable marriage: wetin go happen if, instead of two separate groups, everybody dey inside di same set? Dem note say dia algorithm no work for am, and dem leave di question open.

Dem also prove say stable matching fit simply NOT EXIST — na di main difference from stable marriage, where one dey always exist.

Robert Irving publish di first polynomial-time algorithm for 1985: e dey determine whether stable solution dey and e dey build am if e dey, for two phases, and di second one dey remove « rotations » one by one.

Where dem dey use am

To form pairs for work, review or pair programming.
To assign flatmates or roommates.
To pair training or tournament partners.
To organise peer mentoring, with no hierarchy between di two roles.

Limits and wahala

✓ GOOD SIDE

No pair wan "run away" togeda
E dey based on both sides preferences
E dey honestly detect impossible cases

✕ BAD SIDE

Stable pairing no dey always exist
E need even number
To rank everybody fit take time

E fit no get solution

Unlike stable marriage, stability no dey guaranteed. Na proven result, no be weakness of di implementation.

Number must be even

With odd number, somebody go remain alone by design.

Full ranking dey demand plenty

Everybody must rank everybody else: di cost dey climb fast with group size, and to rank your colleagues no be small social matter.

Questions wey people dey ask

Wetin happen if no stable solution dey?

Di tool go talk am plain. Na real information about di group: di preferences form cycle wey no fit break. Na you go adjust — pair by declared affinity, or accept instability wey you sabi.

Wetin be di difference from two-sided Gale-Shapley?

Gale-Shapley assume two separate sets wey dey rank each other (candidates and programmes) and e dey always guarantee solution. Here everybody dey inside di same set, so no side get advantage — but di guarantee say solution dey don comot.

Wetin « stable » really mean?

Say no two people wey dem no pair together go both prefer each other pass dia current partner. Such pair go comot from di arrangement: na exactly wetin stability dey prevent.