chapter two

2 Gale-Shapley Algorithm

 

This chapter covers

  • Explaining what problem the algorithm solves, and why stability matters
  • Demonstrating with an example how proposals are made and rejected until stability
  • Analyzing the correctness, termination, optimality and proposer bias
  • Applying the algorithm in real-world scenarios like college admissions

In the previous chapter, we looked at the core fundamentals of computer science and the components that drive today’s technology. We looked at data structures like hash maps, linked lists, stacks, and queues and how they perform by understanding the space and time complexities.

The Gale-Shapley algorithm was published in 1962 by David Gale and Lloyd Shapley. It is a stable matching algorithm that pairs equal numbers of participants to their preferences, like matching students to universities or online dating. It is also called the Deferred Acceptance Algorithm (DA) or the Propose-and-Reject Algorithm. This algorithm addresses one of the most elegant problems in combinatorial optimization, i.e., how to pair two equal-sized sets of participants based on their preferences in a way that no two individuals would rather be with each other than with their assigned preferences.

2.1 The Stable Matching Problem

2.1.1 One-Pass Matching

2.1.2 When preferences collide, rejections and rematching

2.1.3 Understanding the bias and complexity analysis

2.2 Real-World applications

2.2.1 Online dating and matchmaking

2.2.2 Ride Sharing and Delivery Matching

2.2.3 Kolkata Paise Restaurant Problem (KPR Model)

2.2.4 National Resident Matching Program (NRMP)

2.3 Key Insights

2.3.1 Everyone gets matched

2.3.2 Stability over optimality

2.3.3 Deferred acceptance principle

2.3.4 Weighted and dynamic matching

2.4 Summary