Metraipolis › archive › dc_549141e40af5

Gale–Shapley algorithm — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-06T09:25:08.555Z
SHA-256 of the archived text
6b6f16265ea831e6e4fe8933358ec2c06d8938a632370160503e4987fae108d9
Stable URL of this page
https://metraipolis.com/documento/dc_549141e40af5

How to cite

Gale–Shapley algorithm — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_549141e40af5 (Metraipolis archive dc_549141e40af5, sha256 6b6f16265ea831e6e4fe8933358ec2c06d8938a632370160503e4987fae108d9)
BibTeX
@misc{dc549141e40af5,
  title = {Gale–Shapley algorithm — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_549141e40af5; sha256 6b6f16265ea831e6e4fe8933358ec2c06d8938a632370160503e4987fae108d9},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In mathematics, economics, and computer science, the Gale–Shapley algorithm (also known as the deferred acceptance algorithm, propose-and-reject algorithm, or Boston Pool algorithm) is an algorithm for finding a solution to the stable matching problem. It is named for David Gale and Lloyd Shapley, who published it in 1962 in The American Mathematical Monthly, although it had been used for the National Resident Matching Program since 1952 despite lacking the theoretical foundation. Shapley and Alvin E. Roth (who pointed out its prior application) won the 2012 Nobel Prize in Economics for work including this algorithm. It had been said that Gale would have been the third co-recipient of the Prize, if he were alive. The stable matching problem seeks to pair up equal numbers of participants of two types, using preferences from each participant. The pairing must be stable: no pair of matched participants should mutually prefer each other to their assigned match. In each round of the Gale–Shapley algorithm, unmatched participants of one type propose a match to the next participant on their preference list. Each proposal is accepted if its recipient prefers it to their current match. The resulting procedure is a truthful mechanism from the point of view of the proposing participants, who receive their most-preferred pairing consistent with stability. In contrast, the recipients of proposals receive their least-preferred pairing. The algorithm can be implemented to run in time quadratic in the number of participants, and linear in the size of the input to the algorithm. The stable matching problem, and the Gale–Shapley algorithm solving it, have widespread real-world applications, including matching American medical students to residencies and French university applicants to schools. For more, see Stable marriage problem § Applications.

Tema degli esploratori: statistica e scienza dei dati (deposito sistematico; ricerca «algorithm»).
Fonte: Wikipedia in inglese, voce «Gale–Shapley algorithm» — https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm
Wikidata Q65123731 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q65123731
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1377920781, consultata il 2026-10-06T08:23:29.870Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 2b8e2af8df36e728af62ca857dc6107ca7996a9ebcf2a4aceb1727e9e7fd0bcc