Gale–Shapley algorithm
E612744
algorithm
algorithm in computer science
algorithm in mathematics
matching algorithm
stable matching algorithm
The Gale–Shapley algorithm is a foundational procedure in mathematics and computer science that computes stable matchings between two equally sized sets, such as students and schools or men and women in the stable marriage problem.
All labels observed (1)
| Label | Occurrences |
|---|---|
| Gale–Shapley algorithm canonical | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T6710762 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Gale–Shapley algorithm Context triple: [David Gale, notableWork, Gale–Shapley algorithm]
-
A.
Matchmakers
Matchmakers is a popular Ukrainian comedy television series produced by Kvartal 95 Studio that follows the humorous clashes and relationships between two very different families.
-
B.
Sperner's lemma
Sperner's lemma is a fundamental result in combinatorial topology that guarantees the existence of a fully labeled simplex in certain labeled triangulations, and is widely used to prove fixed-point and equilibrium theorems.
-
C.
Happy Ending problem
The Happy Ending problem is a famous combinatorial geometry question that investigates the minimum number of points in general position in the plane needed to guarantee the existence of a convex polygon with a given number of vertices.
-
D.
Erdős–Gallai theorem
The Erdős–Gallai theorem is a fundamental result in graph theory that characterizes which sequences of nonnegative integers can occur as the degree sequences of simple graphs.
-
E.
Eppstein
Eppstein is a small historic town in the German state of Hesse, known for its medieval castle and scenic location in the Taunus mountains.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Gale–Shapley algorithm Target entity description: The Gale–Shapley algorithm is a foundational procedure in mathematics and computer science that computes stable matchings between two equally sized sets, such as students and schools or men and women in the stable marriage problem.
-
A.
Matchmakers
Matchmakers is a popular Ukrainian comedy television series produced by Kvartal 95 Studio that follows the humorous clashes and relationships between two very different families.
-
B.
Sperner's lemma
Sperner's lemma is a fundamental result in combinatorial topology that guarantees the existence of a fully labeled simplex in certain labeled triangulations, and is widely used to prove fixed-point and equilibrium theorems.
-
C.
Happy Ending problem
The Happy Ending problem is a famous combinatorial geometry question that investigates the minimum number of points in general position in the plane needed to guarantee the existence of a convex polygon with a given number of vertices.
-
D.
Erdős–Gallai theorem
The Erdős–Gallai theorem is a fundamental result in graph theory that characterizes which sequences of nonnegative integers can occur as the degree sequences of simple graphs.
-
E.
Eppstein
Eppstein is a small historic town in the German state of Hesse, known for its medieval castle and scenic location in the Taunus mountains.
- F. None of above. chosen
Statements (49)
| Predicate | Object |
|---|---|
| instanceOf |
algorithm
ⓘ
algorithm in computer science ⓘ algorithm in mathematics ⓘ matching algorithm ⓘ stable matching algorithm ⓘ |
| alsoKnownAs | deferred acceptance algorithm NERFINISHED ⓘ |
| appliedTo |
college admissions
ⓘ
kidney exchange matching ⓘ matching medical residents to hospitals ⓘ matching men and women in marriage markets ⓘ matching students to schools ⓘ school choice mechanisms ⓘ |
| coreIdea |
iterative proposals from one side to the other
ⓘ
tentative acceptance and possible later rejection of proposals ⓘ |
| field |
algorithmic game theory
ⓘ
computer science ⓘ game theory ⓘ market design ⓘ mathematics ⓘ |
| guarantees |
existence of a stable matching for any complete strict preferences
ⓘ
no blocking pairs in the resulting matching ⓘ proposer-optimal stable matching ⓘ receiver-pessimal stable matching ⓘ termination in finite time ⓘ |
| input |
strict preference lists of agents over the opposite set
ⓘ
two equally sized sets of agents ⓘ |
| inspired |
design of many school choice systems worldwide
ⓘ
design of the National Resident Matching Program mechanisms ⓘ |
| namedAfter |
David Gale
NERFINISHED
ⓘ
Lloyd Shapley NERFINISHED ⓘ |
| output | stable matching ⓘ |
| property |
lattice structure of stable matchings underlies its optimality
ⓘ
not strategy-proof for the receiving side ⓘ produces a matching in the core of the associated marriage market ⓘ strategy-proof for the proposing side under strict preferences ⓘ |
| publishedIn | American Mathematical Monthly NERFINISHED ⓘ |
| relatedConcept |
blocking pair
ⓘ
core of a matching market ⓘ deferred acceptance mechanism ⓘ lattice of stable matchings ⓘ stable matching ⓘ |
| solvesProblem |
stable marriage problem
ⓘ
stable matching problem ⓘ |
| spaceComplexity | O(n^2) ⓘ |
| terminationCondition | no unmatched proposer has someone left to propose to ⓘ |
| timeComplexity | O(n^2) ⓘ |
| usedIn |
matching theory
ⓘ
mechanism design ⓘ |
| yearProposed | 1962 ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Gale–Shapley algorithm Description of subject: The Gale–Shapley algorithm is a foundational procedure in mathematics and computer science that computes stable matchings between two equally sized sets, such as students and schools or men and women in the stable marriage problem.
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.