liveBook · Manning

Chapter 2: Gale-Shapley Algorithm

What you will learn in chapter 2 of Algorithms Every Programmer Should Know

The introduction frames Gale-Shapley as a way to match two equal-sized groups by preference without leaving a mutually preferred unmatched pair, and introduces deferred acceptance and proposer bias.

After this chapter you will be able to

What it builds on

Section by section

Introduction

The introduction frames Gale-Shapley as a way to match two equal-sized groups by preference without leaving a mutually preferred unmatched pair, and introduces deferred acceptance and proposer bias.

Key terms: stable matching, preferences, proposer, recipient, proposers, recipients, deferred acceptance, offers, rejections, optimal for the proposer

2.1 The Stable Matching Problem

Introduces a forthcoming student–university example of stable matching without explaining the matching process.

2.1.1 One-Pass Matching

This section defines a stable student–university match and walks through an ideal example completed in one round of proposals.

Key terms: stable match, preference, universities (proposers), students (receivers), proposals, one pass

2.1.2 When preferences collide, rejections and rematching

This section walks through rejection and rematching in Gale–Shapley, checks the resulting matchings for stability, and shows how changing the proposing side changes the outcome.

Key terms: proposers, receivers, preference order, rejected, stable, preference, matching, first choice, second choice

2.1.3 Understanding the bias and complexity analysis

This section explains how the proposing side benefits in Gale–Shapley matching and what its worst-case quadratic runtime means in practice.

Key terms: proposers, stable matching, structurally biased, worst case, O(N^2), N, time complexity

2.2 Real-World applications

This section contrasts the earlier conflict-and-rematching implementation with real-world uses that must account for the needs of each use case.

Key terms: use case, conflicts and rematching

2.2.1 Online dating and matchmaking

This section maps online dating to stable matching while noting how modern platforms extend the original model.

Key terms: stable matching, ranked order lists, proposer, receivers, unstable pairs, explicitly express their preferences, implicit, swiping, profile views

2.2.2 Ride Sharing and Delivery Matching

The section applies stable matching to ride-sharing and delivery, showing how platform preferences can be modeled and why avoiding unstable assignments matters.

Key terms: two sets of participants, preferences, ranked ordered lists, constraints, stability, unstable matches, rematching, reassigning, cancellations

2.2.3 Kolkata Paise Restaurant Problem (KPR Model)

This section uses customers and restaurants to explain decentralized resource allocation in KPR and contrasts its outcome-based adaptation with Gale-Shapley matching.

Key terms: decentralized resource allocation, customers, restaurants, preferences, proposals and acceptances, repeated interaction, payoff values, customer switching, stability, payoff

2.2.4 National Resident Matching Program (NRMP)

The section explains how the NRMP uses ranked preferences and an applicant-proposing variation of Gale–Shapley to match applicants with clinical training programs.

Key terms: NRMP, ordered lists, ranked lists, stable outcome, applicant-proposing Gale–Shapley algorithm, stable matching, optimal for applicants, strategic disadvantage

2.3 Key Insights

2.3.1 Everyone gets matched

2.3.2 Stability over optimality

This section explains that stable matches need not be optimal for everyone and that the proposing side tends to fare better.

Key terms: stable, optimal match, proposing side, receiving universities

2.3.3 Deferred acceptance principle

2.3.4 Weighted and dynamic matching

The section explains how adding weights and costs to preferences can make stable matching more adaptive to real-world priorities.

Key terms: weights, costs, preferences, preference list ordering, dynamic

2.4 Summary

Concepts explained in this chapter

← Chapter 1: The Language of Algorithms Chapter 3: Hungarian Algorithm →

These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.