How e dey work, well well
Everybody start with endowment: dia current assignment, desk or slot. So di number of people and goods must be equal.
Everybody point di good wey dem prefer. If you follow di arrows, dem must form at least one cycle — sometimes self-loop, when person already get wetin dem prefer.
Dem run di cycles: everybody collect wetin dem point. Di people wey dem serve comot with dia good, then dem start again with di rest, until nobody remain.
Three proven properties: di outcome dey Pareto-efficient, individually rational (nobody comot with something worse than dia endowment), and di mechanism dey strategy-proof.
Example wey get figures
Three people, each holding one slot, each wanting anoda one.
| Person | Current slot | Slot wey dem want | E collect |
|---|---|---|---|
| Chloé | Monday | Tuesday | Tuesday |
| Ali | Tuesday | Monday | Monday |
| Bruno | Wednesday | Wednesday | Wednesday |
- Chloé point Ali slot, Ali point Chloé own: na cycle of length 2.
- Di cycle run: di two swap and comot satisfied.
- Bruno point im own slot: self-loop, so e keep am.
Two swaps, nobody lose. Na di central guarantee of di method: you no fit ever comot worse than how you enter.
Where e come from
Lloyd Shapley and Herbert Scarf publish di founding paper on di « housing market » for di Journal of Mathematical Economics for 1974. Dem credit di top trading cycles algorithm to David Gale and prove say e dey always produce allocation inside di core of di market.
Atila Abdulkadiroğlu and Tayfun Sönmez extend am for 1999 to mixed situations, where some occupants already dey inside and others dey come — di real case of American student housing.
Im biggest application na medical: kidney exchange programmes between donor-recipient pairs wey no match, wey Roth, Sönmez and Ünver formalise for early 2000s, dey stand on dis cycle mechanism. Alvin Roth and Lloyd Shapley collect di 2012 Nobel for Economics for all dis work.
Where dem dey use am
- To swap on-call slots, duty shifts or leave days.
- To reassign desks, equipment or parking space wey people already dey use.
- To rotate assignments or client portfolios inside team.
- Kidney exchange between pairs wey no match — di application wey win Nobel.
Limits and wahala
- Nobody go end up worse pass di start
- Sincere ranking na always di best
- Every win-win trade go happen
- Everybody need starting property
- Exactly as many things as people
- Di result depend well well on di starting property
Questions wey people dey ask
I fit end up worse than my current position?
No, never, and dem don prove am: individual rationality na proven property of di algorithm. If no swap suit you, you keep your endowment — na di self-loop.
Make I report wrong preference order?
No. Di mechanism dey strategy-proof: to lie no fit improve your result, and e fit make you miss cycle wey suit you.
Wetin happen if nobody want swap?
Everybody point dia own good, every cycle na self-loop, and nothing move. Dat result valid: e dey talk say di current arrangement already optimal.