1
$\begingroup$

What is the worst case for the stable marriage problem?

I know the worst case is $n^2 - 2n + 2$ but I would like to know how to prove it.

That is: why is the maximal number of iterations required by the Gale–Shapley algorithm given by $n^2 - 2n + 2$?

$\endgroup$
  • $\begingroup$ It would help to state the theorem, or at the least link to it. $\endgroup$ – Thomas Andrews Aug 27 '15 at 0:09
  • 3
    $\begingroup$ It is not clear what you mean by "the worst case". Perhaps you mean the maximal number of iterations required by the Gale–Shapley algorithm to solve an instance of the stable marriage problem? $\endgroup$ – joriki Aug 28 '15 at 5:52
  • 1
    $\begingroup$ Yes joriki that is it $\endgroup$ – dirtysocks45 Aug 28 '15 at 17:25
4
$\begingroup$

Claim: $n(n-1) + 1$

Proof: While it is true that there are $n$ lists with $n$ entries in them, it is also true that no man can be eliminated $n$ times. For if he was, he would run out of choices in women and be out of the game. We know this can't happen because the stable marriage algorithm is guaranteed to terminate in a stable pairing as proved in lecture. i.e. it isn't possible to have a man with no one to propose to. So in the worst case scenario, with exactly one man being rejected every day until the algorithm terminates, there are $n$ men with at most $(n-1)$ rejections each.

That means there is at maximum $n(n-1)$ days where a man gets rejected by a woman. Now suppose that on the $n(n-1)$th day man $x$ gets rejected for the $(n-1)$th time; he still needs one more day to propose to the $n$th woman on his list. i.e. Since the stable marriage algorithm terminates, there must be exactly 1 day where no man makes a proposal.

Therefore the worst case scenario for the stable marriage algorithm is: the sum of the worst case number of days where a man gets rejected and the one day where no man gets rejected. Or in mathematical notation $n(n-1) + 1$.

$\endgroup$
1
$\begingroup$

First, consider how many proposals may be made in total. Certainly no woman receives more than $n$ proposals. However, as soon as every woman has received at least one proposal, all women are engaged and the process stops. So the last woman to receive a proposal gets exactly $1$, and the others at most $n$ each, so at most $n(n-1)+1$ proposals are made.

Now note that $n$ proposals are made on the first day, and at least $1$ every day thereafter until the process finishes, so $n(n-1)+1$ proposals will take at most $1+(n(n-1)+1-n)=n^2-2n+2$ days.

Finally, we need a construction to show that this bound can be attained. I'll illustrate this for $n=5$; it should be easy to see how it generalises (and trying to write it out in generality would only make it more obscure).

  • M1 has preference order W1 W2 W3 W4 W5;
  • M2 has order W2 W3 W4 W1 W5;
  • M3 has order W3 W4 W1 W2 W5;
  • M4 has order W4 W1 W2 W3 W5; and
  • M5 has order W4 W1 W2 W3 W5.
  • W1 prefers M2, but puts M1 second;
  • W2 prefers M3, but puts M2 second;
  • W3 prefers M4, but puts M3 second; and
  • W4 prefers M1, but puts M4 second.

The other details of the women's preferences do not matter. In the first round, woman $i$ gets engaged to man $i$ for $i<5$, and M5 is rejected by W4. He then tries W1, then W2, and is accepted by W3. Now M3 is unengaged, and tries W4, then W1, then W2, who accepts him. Now M2 tries W3, W4 and then W1. Now M1 tries W2, W3, W4. Finally M4 is unengaged and tries the other women in turn, ending with W5.

Each woman apart from the last is proposed to by all the men, and after the first day exactly one proposal per day is made, so this takes $n^2-2n+2$ days.

$\endgroup$
1
$\begingroup$

My assumption about the stable marriage algorithm is from the following MIT notes.

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_chap05.pdf

Example of a worst-case scenario: taking 5 males and 5 females. n=5

Males are A, B,C,D,E

Females are 1,2,3,4,5

Preferences of Males : $$ \begin{matrix} A - & 2& 3 & 4 & 5 & 1 \\ B - & 2 & 4 & 5 & 3 & 1\\ C-& 3 & 4 & 5 & 2 & 1 \\ D -& 4 & 5 & 2 & 3 & 1 \\ E - & 5 & 2 & 3 & 4 & 1 \end{matrix} $$

Preferences of Females: $$ \begin{matrix} 1 - & D& x & x & x & x \\ 2 - & C & D & E & B & A\\ 3-& B & D & E & A & C \\ 4 -& E & A & B & C & D \\ 5 - & A & B & C & D & E \end{matrix} $$

Worst case scenario - Finding no. of days and no. of proposals, the algorithm will take:

Logic: we chose the input in such a way that every day only one male gets rejected. n men will be proposing n-1 times. And then at last one of the males will do his nth proposal and then for every female there will be only one male, hence there will be a stable marriage. $$ \text{No. of proposals} = n(n-1) + 1 = n^2 - n + 1$$

Now, on the first day, n proposals are made, and thereafter each day only one male is getting rejected so, one proposal per day.

$$ \text{No. of days} = \text{No. of proposals} - n + 1 = n(n-1) + 1 - n +1 = n^2 -2n + 2$$


Proof: By Induction

P(n) : For n males and females, the max number of proposals made by males are $n^2-n+1$

Base Case: For n=1, 1 male and 1 female, no. of the proposal made will be 1 = 1-1+1.

Inductive Case: We must prove P(n) => P(n+1)

Assume P(n) is true.

In the group of n male and females, max n-1 proposals were made by n-1 males and 1 male made n proposal.

Now for n+1 males and females, we have one more male and one more female than the set of n, those n-1 male need to propose one more female (to make total n proposals for n males), and the new male added to the set will be making n+1 proposal (1 male proposal n+1 females).

\begin{align} \text{No. of proposals for n+1 set} & = \text{No. of proposals made for n set} + (n-1) + (n+1) \\ & = n^2 - n + 1 + n - 1 + n + 1\\ & = n^2 + n + 1 \\ & = (n+1)^2 - (n+1) + 1\\ & = (n+1)(n) + 1 \\ \end{align}

$$q.e.d.$$


Proof : By Induction

P(n) : For n males and females, the max no. of days (no. of iterations) this algorithm will take is $n^2-2n+2$

Base Case: For n=1, 1 male and 1 female, no. of days will be 1 = 1-2+2.

Inductive Case: We must prove P(n) => P(n+1)

Assume P(n) is true.

Now after the first day, no. of proposal per day is 1. And the extra number of proposals going from n to n+1 set is (n-1) + (n+1). and also we need to subtract one for the new male member, whose first proposal will happen on day1 \begin{align} \text{No. of days for n+1 set} & = \text{No. of days made for n set} + (n-1) + (n+1) - 1\\ & = n^2 - 2n + 2 + n - 1 + n + 1 - 1\\ & = n^2 + 1 \\ & = (n+1)^2 - 2(n+1) + 2\\ \end{align} $$q.e.d.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.