2 Gale-Shapley Algorithm

The chapter introduces the Gale-Shapley algorithm as a classic stable matching method for pairing two equal-sized groups according to their preferences, such as students with universities or users in dating platforms. Its central goal is to produce a matching with no unstable pair—meaning no unmatched pair would both prefer each other over their assigned matches. The explanation emphasizes that the algorithm always finds a stable outcome when the groups are of equal size, and that its “deferred acceptance” style works by letting one side propose while the other side temporarily holds the best offer seen so far.

Through step-by-step examples, the chapter shows how proposals, acceptances, and rejections unfold until everyone is matched. In the simple case, each proposer gets their first choice immediately, while in the more realistic case, conflicts force participants to move down their preference lists and try again until a stable arrangement emerges. The process is illustrated as iterative and deterministic: once a proposal is rejected, that pairing is not revisited, and the algorithm eventually terminates with a complete stable matching.

The chapter also highlights an important asymmetry: the side that proposes has an advantage and tends to receive the best possible stable outcome for itself, while the receiving side may settle for less preferred matches. This proposer bias is a key property of the algorithm and matters in real applications such as medical residency matching, ride-sharing, online dating, and resource allocation problems. Finally, it notes that the algorithm runs in quadratic time in the worst case, making it efficient enough for many practical systems while still guaranteeing stability and predictable behavior.

shows universities proposing their first preferences. X proposes to Alice, Y to Bob, and Z to Carol.

The receiver's preference list is checked, where Alice prefers X, Bob prefers Y, and Carol prefers Z. Final matching is completed once all students accept the proposal.

Round 1 where students are proposers. Alice, Bob, and Carol propose to their first choices from the list. A conflict is seen between Bob and Carol, where both students opt for university X. X prefers Bob over Carol and rejects Carol.

In Round 2, Carol proposes to her second choice while Alice and Bob keep their previous choices only. A conflict is seen again between Alice and Carol with university Y. Y prefers Alice over Carol, and Carol is politely rejected again.

In Round 3, Carol is left with one choice, university Z. Z is not matched with anyone and prefers Carol too. Z accepts Carol, and matching is complete without conflict.

Proposers and receivers are interchanged. The matching completes in one pass itself. Universities get their first preference matched, but students do not control the match.

Students accept the proposals, as there are not better offers to choose from. In the final matching, students are matched to their second and third choices compared to when students were proposers.

• The Gale-Shapley algorithm performs steps to pair participants such that the matching is based on preferences and no pair wants someone other than their existing match.
• This algorithm is also called the Deferred Acceptance or Propose-and-Reject Algorithm.
• Each set of participants, like students and universities, has a ranked list of preferences in decreasing order. There are proposers and receivers who propose and accept/reject the proposals.
• Stable matching in this algorithm is defined as every participant in the matching cannot switch to a new participant based on their preference order.
• The algorithm favors the proposers who are matched with their best preference, while the receivers are matched with the preference they do not have control to change. This is by design and works best where the proposing side has to be favored in the result.
• The output guarantees termination, and every participant is matched at the end of the algorithm. The time complexity in worst case is O(N^2)
• Everyone always gets matched, and all matches are stable. Until finalized, matches are temporary and decided later, making it deterministic.
• Online dating, ride sharing, delivery platforms, and college admissions are a few real applications where the Gale-Shapley algorithm is used fundamentally.

FAQ