$M$ is a set of men and $W$ is a set of women.

Initially all m in M and w in W are free
While there is a man m who is free and hasn’t proposed to
every woman
    Choose such a man m
    Let w be the highest-ranked woman in m’s preference list
       to whom m has not yet proposed
    If w is free then
      (m, w) become engaged
    Else w is currently engaged to m'
      If w prefers m' to m then
         m remains free
      Else w prefers m to m'
         (m, w) become engaged
         m' becomes free
Return the set S of engaged pairs

Claim: The algorithm above terminates after at most $n^2$ iterations of While loop.

Proof: In the case of the present algorithm, each iteration consists of some man proposing (for the only time) to a woman he has never proposed to before. So if we let $P(t)$ denote the set of pairs $(m, w)$ such that $m$ has proposed to $w$ by the end of iteration $t$, we see that for all $t$, the size of $P(t + 1)$ is strictly greater than the size of $P(t)$. But there are only $n^2$ possible pairs of men and women in total, so the value of $P(\cdot)$ can increase at most $n^2$ times over the course of the algorithm. It follows that there can be at most $n^2$ iterations.

My questions:

  1. $P(t)$ contains at least $1$ and at most $n^2$ elements. Correct?

  2. $P(t)$ is the set after $t$ iterations and $P(\cdot)$ is the set after unknown number of iterations? I mean $P(t)$ is special case of more general $P(\cdot)$, correct? Else what is $P(\cdot)$?

  3. What's the point of mentioning $|P(t)| < |P(t +1)|$ for all $t$?

  1. Correct.

  2. Don't look too hard for a deep difference between "$P(t)$" and "$P(\cdot)$". In fact, I think the proof would be just as good if it said $P(t)$ even where your rendering has $P(\cdot)$.

  3. That's the crucial point of the proof -- $|P(t)|$ is always a (non-negative) integer, and if it increases in each execution of the loop, it must increase by at least $1$. So if the loop executes for more than $n^2$ iterations $|P(t)|$ will eventually become greater than it can be, which is absurd.

    But we can't conclude that unless we know that $|P(t)|$ is in fact strictly increasing.

In my opinion it would be a bit crisper to notice that $|P(t)|=t$ exactly, so a contradiction results if $t>n^2$. But there's nothing wrong with the reasoning here.


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.