How e dey work, well well
Two separate groups dey rank each other. Side 1 dey propose, side 2 dey dispose — and each entry for side 2 fit get capacity of several places.
Each proposer apply to dia first choice. Each receiver dey provisionally hold di best candidates up to im capacity and dey turn di rest away. Nothing dey final: na di whole meaning of DEFERRED acceptance.
Candidates wey dem turn away go apply to dia next choice, wey fit push out candidate wey dem dey hold provisionally, and dat person go apply again. E dey stop when nobody get proposal to make again.
Di result dey stable: no candidate-programme pair go prefer each other pass dia assignment. E dey also OPTIMAL for di proposing side — among all stable matchings, each proposer collect di best one possible.
Example wey get figures
Three candidates, three programmes with one place each, cross rankings.
| Candidate | Wishes | Programme | Ranking |
|---|---|---|---|
| Chloé | A, B, C | A | Ali, Chloé, Bruno |
| Ali | A, C, B | B | Chloé, Bruno, Ali |
| Bruno | B, A, C | C | Bruno, Chloé, Ali |
- Round 1: Chloé and Ali apply to A, Bruno to B. A prefer Ali and drop Chloé; B hold Bruno.
- Round 2: Chloé apply to B. B prefer Chloé pass Bruno and swap — dem push Bruno comot.
- Round 3: Bruno apply to A, wey keep Ali; then to C, wey accept am. End: Ali→A, Chloé→B, Bruno→C.
Dem hold Bruno then push am comot: na di deferred mechanism, and na why Parcoursup results dey move for weeks. Di final outcome dey stable.
Where e come from
David Gale and Lloyd Shapley publish « College Admissions and the Stability of Marriage » for di American Mathematical Monthly for 1962. Dem prove say stable matching between two groups dey ALWAYS exist, and dem give simple algorithm to build am: deferred acceptance.
Historical surprise: di National Resident Matching Program, wey don dey assign American medical residents to hospitals since 1952, don already dey use equivalent algorithm — dem find am by practice, ten years before anybody theorise am. Alvin Roth prove dis for 1984 and lead di 1998 redesign to handle couples.
Roth and Shapley collect di 2012 Nobel for Economics for di theory of stable allocations and market design. For France, Parcoursup don apply dis principle since 2018, in place of APB, with automatic responder wey dey play di role of deferred acceptance.
Where dem dey use am
- Parcoursup and French post-secondary admissions.
- American medical residency match (NRMP) since 1952.
- School assignment for New York and Boston, wey Roth and colleagues redesign.
- Mentoring programmes, internships and project allocation between two separate populations.
Limits and wahala
- Always stable matching
- E handle capacities (plenty spots per side-2 entry)
- Sincere ranking na optimal for side 1
- E dey favour di side wey propose
- Side 2 fit rank tactical
- Some people go remain unmatched if spots finish
Questions wey people dey ask
Why my assignment dey change as we dey go?
Because di acceptance dey deferred: dem hold place for you provisionally, and candidate wey rank better fit push you comot — same way you fit push anoda person comot for anoda place. Di process dey settle only for di end, and na dat dey guarantee stable result.
Make I rank my wishes tactically?
If you dey di proposing side — di candidates, for Parcoursup — no: to rank sincerely na provably di best. To put « realistic » wish before di one wey you really want fit only harm you.
Wetin « stable » mean?
Say no candidate-programme pair go both prefer each other pass wetin dem collect. Without dat property, side deals go start outside di system — exactly wetin dey happen for United States before 1952.
Wetin be di difference from serial dictatorship?
Serial dictatorship get only one side wey dey rank: di options no get opinion. Here di two sides dey rank, and di assignment must satisfy both — na why stability dey, wey no get meaning inside serial dictatorship.