welcome: please sign in

Please enter your password of your account at the remote wiki below.
/!\ You should trust both wikis because the password could be read by the particular administrators.

Clear message
location: ProblemsDescription / StableMarriageProblem

Stable Marriage Problem

Problem Description

Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are "stable".

The stable marriage problem (SMP) is the problem of finding a stable matching mapping men to women. Stability in a matching requires that whenever there is no element A of the first matched set that prefers an element B (that it's not matched to) of the second matched set, and at the same time B also prefers A over the one B is matched with.

SMP has several practical applications, as well as several variants. The variant proposed here is known to be polynomially solvable.

Input format

Output format

Example

Author(s)

References