OTHER NEAT FACTS

• Can be more students than hospital slots, or vice versa. Theory carries over (smaller set gets completely matched).
• The same students are matched and the same hospital positions are filled at every stable matching. (That is, any student who is unmatched at one stable matching is unmatched at every stable matching, and the hospital positions that are unfilled are the same at every stable matching.) Only the specific assignment of which matched students are in which filled hospital positions differs between different stable matchings.
• When the student-proposing algorithm is used, but not when the hospital-proposing algorithm is used, no student can possibly improve his or her match by submitting an ROL that is different from his or her true preferences.
• There is a polynomial-time egalitarian algorithm (neither student nor hospital optimal).
• The student-optimal algorithm is, in fact, hospital pessimal (even though hospitals don't directly give a ranking over groups of students).
• Couples match: The basic algorithm can be extended to permit constraints on where pairs of people end up. However, the nice mathematics is trashed.