What is the Stable Matching Problem? (A Simple Analogy)

Imagine you're a matchmaker for two groups of people, say, five doctors and five hospitals. Each doctor has a ranked list of the hospitals they'd love to work at, and each hospital has a ranked list of the doctors they'd love to hire. Your job is to create five perfect pairs. But what does "perfect" mean? In this puzzle, it means creating a **stable** set of matches. A matching is "unstable" if there's a doctor and a hospital who are *not* matched together, but who would both rather be with each other than their current assignments. For example, if Dr. Smith is matched with City General but secretly prefers County Hospital, and County Hospital is matched with Dr. Jones but secretly prefers Dr. Smith, that's an unstable pair just waiting to cause trouble! A **stable matching** is a set of pairs where no such unstable "rogue couples" exist.

This fascinating problem isn't just a thought experiment; it's used in the real world for incredibly important tasks, most famously for the National Resident Matching Program, which matches thousands of medical school graduates to hospitals across the country every year. This interactive tool brings the Nobel Prize-winning **Gale-Shapley algorithm** to life, letting you see exactly how it solves this puzzle. It's designed to be a visual playground that takes an abstract computer science concept and makes it tangible and easy to understand. You can set up the preferences, run the simulation, and watch the step-by-step "drama" of proposals and rejections unfold in the log, leading to a guaranteed stable and optimal result.

How to Use This Visualizer

This tool is designed to be an interactive playground for understanding this powerful algorithm:

1. Set the Scene: Use the "Number of Participants" input to decide how many are in each group. You can also click on any name to edit it (e.g., "Student A", "Company X").
2. Rank Preferences: This is the fun part! For each person or entity, drag and drop the colored tags in their preference list to rank them from their first choice (left) to their last choice (right). For a quick start, just hit the "Randomize Preferences" button!
3. Generate the Matching: Once your preferences are set, click the big "Generate Stable Matching" button.
4. Watch the Algorithm Work: The final, stable pairs will appear at the top. But the real magic is in the log below, which gives you a play-by-play of the entire process. You'll see who proposes to whom, who gets tentatively "engaged," and who gets rejected for a better offer, showing you exactly how the algorithm arrives at its perfect solution.

Tips for Exploring

• Who Has the Power?: The Gale-Shapley algorithm is famously known to produce a result that is optimal for the "proposing" group (in this case, Group 1). This means every member of Group 1 gets the best possible partner they can hope for in any stable matching. Try running a simulation, then swap the names of the two groups and run it again. Do you get the same pairs? Who seems happier with the result?
• Try to Break It: After you get a result, look at the final pairs and try to find an unstable "rogue couple." You'll find that it's impossible! For any two people who aren't matched, at least one of them is happier with the partner the algorithm gave them.
• Model the Real World: Don't just use people! You can model anything. Try matching 3 programmers to 3 projects, where the programmers rank the projects by interest, and the "projects" rank the programmers by skill. Or match 4 friends to 4 board games. The possibilities are endless!