Is the stable marriage problem defined for $0$ people?

40 Views Asked by At

When proving properties of algorithms which are supposed to solve the stable marriage problem, I find myself unable to prove them sometimes in the case of there being $0$ things to pair with each other. Is this a problem, or is the stable marriage problem not even defined for $0$ people?

EDIT: specifically, I am trying to prove properties of the propose and reject algorithm in my homework, such as the chances for women always improve with each iteration of the algorithm. If there are $0$ people, it does not seem possible to prove this.

1

There are 1 best solutions below

0
On BEST ANSWER

You can define the 0-person stable marriage problem as a vacuous truth. The goal of the problem is satisfied if there are no two individuals who would both prefer each other over their current partners. If there are no people involved in the first place, and thus no preferences or potential matches to consider, the problem is trivially “solved” by not creating any matches.

This framing is probably meaningless by itself, but could be useful as the stopping case of a recursive algorithm that stably-matches one couple, and then excludes them from future consideration, recursing to the case of $n-1$ men and $n-1$ women.