What is an algorithm?

• An algorithm is a clear step-by-step procedure to solve a given problem (by computers).
  • Each step must be computer-implementable.
  • Must be clear enough that anyone reading it cannot misunderstand any of the steps.
• After figuring out an algorithm for a problem, we can then implement it as a computer program.

The importance of proofs for this course

• As you will soon see, many algorithms do not make sense at first glance yet they are actually correct.
• For such algorithms, studying the proofs of their correctness is the only way to understand why they are correct.

Other benefits of studying proofs

• You will unlikely to misremember and/or misuse the algorithms.

• You will know whether the same algorithm can be used for other similar problem.

• Sometimes, just a few slight tweaks to the proofs you study can result in a modified algorithm for a new problem you encounter!

• You will be able to distinguish between proper and flawed arguments. Useful for real life.

• You will likely find proofs to be difficult to understand in the beginning as they are new and different to you.

• Unfortunately, they are crucial for this course (and only a few other courses in your curriculum, i.e., CSS321, CSS322).

About the exams in this course

• Because proofs are difficult, there will not be any proof question in the midterm exam, and there will be at most one light “kind-of proof” question in the final exam.
• That is, you can easily get A for this course even if you cannot answer the proof question (as long as you can do the other non-proof ones better than your classmates).
• Caveat: For ambitious students who want to study Master/PhD in top universities or work in top companies abroad, they do expect you to be comfortable at understanding proofs and proving new theorems.

Intro problem: Stable Matching

• There are n men and n women.
• We want to arrange marriages between them.
• n marriages. So everyone is married.
• But, suppose Somchai prefers Somsri to his wife and Somsri also prefers Somchai to her husband...
• Somchai and Somsri may both leave their respective marriages and run off together.
  • I.e., ==Somchai’s and Somsri’s marriages are unstable.==
• So we want to arrange marriages such that all marriages are stable.
• The problem also applies to matching employees to employers, subordinates to bosses, students to universities, residents to hospitals, and so on.

Stable Matching: Problem Formulation

• Let $M=\{m_1,\dotso,m_n\}$ be a set on $n$ men.
• Let $W=\{w_1,\dotso,w_n\}$ be a set on $n$ women.
• A matching S is a set of ordered pairs $(m,w)\in M\times W$ where each member of $M$ and each member of $w$ appears in at most one pair in S.
• A perfect matching S’ is a matching with the property that each member of $M$ and each member of $W$ appears in exactly one pair in S’.
  • I.e., everyone is married and no one is married to two or more people.

Preferences

• Each man $m\in M$ ranks all the women according to his preference.
• Call this ranking his “preference list”.
• $m$ prefers $w$ to $w’$ if $m$ ranks $w$ higher than $w’$. → $m$ like $w$ more than $w’$ (different gir)
• Ties in the ranking are not allowed.
• Each woman ranks all the men in the same way.

Instability

• There are two pairs $(m,w)$ and $(m’,w’)$ in S where $m$ prefers $w’$ to $w$ and $w’$ prefers $m$ to $m’$
• So $m$ and $w'$ may abandon their current partners and head off together.
• Such a pair $(m,w’)$ is said to be an instability with respect to S.

Goal

• A matching S is stable if
  • It is perfect, and → (No one is single)
  • There is no instability with respect to S.

Example 1

• Two men: $m$ = {$m$,$m'$}. Two women: $w$ = {$w$,$w'$}.
• $m$ prefers $w$ to $w'$.
• $m'$prefers $w$ to $w'$.
• $w$ prefers $m$ to $m'$.
• $w'$prefers $m$ to $m'$.
• Any stable matching in this example? If so, what is it? Is it unique?
  

Designing the Algorithm

• Initially, everyone is unmarried.

• Suppose an unmarried man $m$ chooses the woman $w$ who ranks highest on his preference list and proposes to her.

• Question: Should $w$ accept and marry $m$?

• Will $(m,w)$ be one of the pairs in a stable matching?

  • Not necessarily. We cannot be sure at this point.
  • Another man $m'$ whom $w$ prefers to $m$ may propose to her in the future. If $w$ is already married to $m$, this may lead to instability.

• On the other hand, should $w$ reject $m$ right away?

  • No, because it is possible that no other men whom $w$ prefers to $m$ will propose to her in the future.

  If that woman is free, she just accept the proposal

• So let’s have $w$ engaged to $m$.

• Let’s keep doing this.

• Suppose, at the current state, some men and women are free (not engaged).

• An arbitrary free man $m$ chooses the highest-ranked woman $w$ to whom he has not yet proposed, and he proposes to her.

• If $w$ is also free, have $m$ and $w$ engaged.

• But what if $w$ is already engaged to some other man $m'$?

• If she prefers $m'$to $m$, she keeps her current engagement to $m'$and reject $m$.

• Otherwise, $w$ then breaks off her engagement with $m'$and becomes engaged to $m$ instead.

• Repeat until no one is free.

• At this point, have every woman marry her current fiancé.

• This algorithm is known as the Gale-Shapley (G-S) algorithm.

  • Proved in 1962 by David Gale & Lloyd Shapley
  • Well recognized in 1980 from Alvin Roth’s work
  • Roth and Shapley won Nobel prize in 2012.

Analyzing the algorithm

• Some part of the step of the algorithm is called lemma.

• Proof:
  • When a woman receives her first proposal, she accepts it and becomes engaged right away (because she is free).
  • The only way for a woman to break off her engagement is to switch to be engaged to another man whom she prefers.

• Proof:
  • Because a man starts by proposing the woman highest on his list and works his way lower his preference list.

• Proof:
  • Each man proposes at most n times because he never proposes to the same woman more than once.
  • There are n men. So at most _n_2 proposals before the algorithm terminates.

• Proof:
  • Let’s prove by contradiction.
  • Suppose there comes a point where $m$ is free but has already proposed to every woman.
  • By (1.1), each of the n women is engaged at this point in time.
  • All n women are engaged means all n men are engaged.
  • This contradicts the assumption that $m$ is free.

• Proof:
  • First, the set of engaged pairs always forms a matching.
  • By (1.4), if $m$ is free, there must be at least one woman to whom he has not yet proposed.
  • Therefore, the algorithm does not leave the While loop and continues.
  • This means that when the algorithm does terminate, no men are free.
  • Since engagement is one-to-one, no women are free either (same number of men and women).
  • Therefore, the returned S is a perfect matching.

• Proof:
  • We already know from (1.5) that S is a perfect matching.
  • To prove that S is a stable matching, let’s assume there is an instability with respect to S and obtain a contradiction.
  • Assume there is an instability involves two pairs ($m$,$w$)and ($m$0_,_$w$0) in S with the property that
    • $m$ prefers $w'$ to $w$, and
    • $w'$ prefers $m$ to $m'$.
  • Since $m$ is married to $w$, it means$m$’s last proposal was to $w$.
  • Question: Did $m$ propose to $w$0at some earlier point in this execution?
  • Since m prefers _w_0to w (our assumed instability), he did (as he

proposes in order of his preference).

Since m does not end up married to _w_0,itmeansthat_w_0must have

rejected m (either right away or later on) in favor of some other man

_m_00, whom _w_0prefers to m.

_m_0is the final partner of _w_0,soeither_m_00= _m_0or _w_0prefers her final

partner _m_0to _m_00.

Either way, this contradicts our assumption that _w_0prefers m to _m_0.

It follows that S is a stable matching.

Running time of G-S

• With suitable data structure and implementation, G-S is $O(n^2)$.

• What about the running time of a straightforward brute-force search?

  • The brute-force search would try every possible perfect matching and check if each one is stable until it finds a stable one.
  • There are $n!$ perfect matchings.
  • Checking if a perfect matching is stable takes $O(n^2)$ operations (with suitable data structure).
  • So total running time is $O(n!(n^2))$ = $O(n^{n+2})$.

• Note how the G-S algorithm is unfair, favoring men...

• Ex: If the men all list di↵erent women as their first choice, then in all runs of the G-S algorithm, all men end up matched with their first choice, independent of the preferences of the women.

• Also, G-S is underspecified: when there is more than one free man, we can choose any free man to make the next proposal.

• Difference choices lead to di↵erent executions of the algorithm.

• Question: Do all executions of G-S yield the same matching?

Overall Themes of Algorithm Design

• Many problems have “easy” and straightforward but highly-inefficient algorithms for solving them.
  • Usually brute-force search.
  • High-polynomial time or exponential time for some problems.
• But by designing more sophisticated algorithms, we can solve the same problems more efficiently.
  • Exponential time → Polynomial time.
  • High-polynomial time → Low-polynomial time.
• It is usually not intuitive if/why these sophisticated algorithms are correct.
• So the proofs of their correctness are required.
• (People won’t use your algorithms unless you can show them that the algorithms are correct).