The Stable Marriage Algorithm: Extending to Real-World Preferences

Abstract

This paper extends the classical Stable Marriage Problem (SMP) by incorporating the concept of preference ties, where participants can equally rank multiple options. Building upon the foundational works of Gale and Shapley, the paper presents a modified algorithm that allows proposers to simultaneously approach multiple equally preferred choices, with a subsequent selection process when multiple proposals are accepted. Using concrete examples with a 5x5 preference matrix, the paper demonstrates how the proposed extension incorporates preference ambiguities while preserving termination and stability. The analysis reveals important implications for the algorithm’s optimality properties and complexity. This extended algorithm has significant applications in college admissions, medical residency matching, and other allocation problems, offering a more practical and adaptable framework for modern matching systems where strict preference orderings are unrealistic.