Matching with Ties

When preferences can have ties (e.g., schools ranking by coarse test score bands), multiple stability concepts arise with different existence guarantees.

Stability Concept

Strong Stability: No pair where both weakly prefer the change, with at least one strictly preferring it.

Tie-Breaking Method

Algorithm Pseudocode

Strong-Stable Matching:
1. Break ties (or use extended GS)
2. Run Gale-Shapley with tie handling
3. Check stability under selected concept
4. If super-stable: verify no weak
   blocking pairs exist
   (may report "does not exist")

Preferences (with Ties)

Schools {tied} = same rank

Students

Event Log

Select a stability concept and click "Run Algorithm".

Real-World: The NHS Foundation Programme in the UK uses SMTI to match junior doctors. Ties arise because applicants are ranked by exam score bands.

Matching Result

Stability Analysis

Run the algorithm to see stability analysis.

Size Comparison

With ties, stable matchings can have different sizes. We want the maximum-size stable matching!

Run with different tie-breaking methods to compare sizes.