Skip to content

6.4 Matching

  1. Setup:
    A teacher initially places the students at desks (each desk holds two students). Students may rearrange themselves under these rules:

    • Valid moves:
      Two students can swap seats, or one student can move to an empty seat.
    • Gender constraint:
      No two boys sit together, no two girls sit together.
    • Preferences:
      After any move, every student that changed the place must be at least as happy as before.
      Preferences are fixed; a student may prefer sitting alone to sitting with a classmate.

    The process stops when no further valid moves are possible.
    Questions:

    • Will the reseating process always terminate?

    No, image​ * Will it always terminate if only the boys are allowed to move?

    No, boys can all prefer only not sitting alone, then there is a loop * After termination, can a student be paired with a neighbor they like less than some other classmate?

    Yes, change places, your partner doesn't want

  2. Let \(n\) students seek admission to one of \(m\) universities. The \(i\)'th university has a quota of \(n_i\) places. All universities evaluate students solely based on a single universal exam grade (resulting a strict global ranking of students). Each student has a known preference ranking over the universities. Propose an algorithm that produces a stable distribution of students.

    image​

    Initially no boy is engaged.

    On every turn every non-engaged boy sends a proposal to the girl he likes the most, who has not refused to him yet.

    Girls study the proposals they have, choose the best one, refuse to all the others.

    Stop when all the boys are engaged.

    image we don't have unstable pair

    Modification:

    On every stop the non-engages students send their files to the Universities.

    Every University keep the \(\underline{\text{best}}\) \(\text{n}_\text{i}\) \(\underline{\text{students}}\).

  3. A girl \(g\) and a boy \(b\) are called admissible partners, if there exists a stable matching that pairs \(g\) and \(b\). Prove that Gale-Shapley algorithm produces a matching in which every boy is paired with the best possible admissible partner. Prove that every girl receives the worst admissible partner.

‍

  1. Notation.
    Let us write \(x \succ_g y\) to mean “girl \(g\) prefers boy \(x\) over boy \(y\).”

    Suppose during the GS run, boy \(b\) proposes to \(g\), and \(g\) is currently holding some boy \(b'\) with \(b' \succ_g b\). Then \(g\) rejects \(b\). From that moment on, \(g\) will only “trade up.” Hence at the end of the algorithm, the final partner \(M(g)\) satisfies:

    \(M(g) = \text{some } b^* \text{ with } b^* \succ_g b' \text{ or } b^* = b',\)so

    \[ M(g) \succ_g b' \succ_g b. \tag{*} \]

  2. Goal.
    Show that in any stable matching \(N\), \(g\) cannot be matched with a boy she ranks below \(b\).

  3. Contradiction.
    Suppose \(N(g) = x\) with \(x \preceq_g b.\)

    From \((*)\), we know \(M(g) \succ_g x\). Let \(b^* := M(g)\). In \(M\), \(b^*\) is matched to \(g\); in \(N\), \(b^*\) is matched to \(g^* \ne g\). Since \(b^*\) ended up with \(g\) in GS, he must prefer \(g\) to \(g^*\),

    so: \(g \succ_{b^*} g^*.\)Now, \((b^*, g)\) is a blocking pair in \(N\), contradicting stability.

    Thus, no stable matching can pair \(g\) with a partner worse than \(b\), completing the proof.

‍