Privacy Attacks on Stable Marriage
2026-07-14 • Data Structures and Algorithms
Data Structures and AlgorithmsDistributed, Parallel, and Cluster ComputingMultiagent Systems
AI summaryⓘ
The authors studied how the stable marriage algorithm, used to match two groups like hospitals and residents, can leak private preference information if one side tries to cheat by repeatedly interacting with it. They found that when the side making proposals is dishonest, the preferences of the honest side can be completely uncovered. However, if the honest side proposes and their preferences meet certain conditions, privacy can be maintained. Their experiments showed that real-world data is vulnerable to such privacy attacks. The authors highlight the need for new algorithms that better protect users' preference privacy.
Stable Marriage ProblemGale-Shapley AlgorithmPrivacy AttacksPreference ListsNational Resident Matching ProgramStrategic ManipulationData ProtectionDecentralized AlgorithmsMatching TheoryPrivacy Preservation
Authors
Stephan A. Fahrenkrog-Petersen, Aleksander Figiel, Darya Melnyk, Tijana Milentijević, Stefan Schmid
Abstract
The stable marriage problem appears in many privacy-sensitive domains, for example in the National Resident Matching Program in the US. In such applications, preserving the privacy of users' preference lists is essential to prevent strategic manipulation, discourage misreporting, and comply with data protection regulations. In this work, we investigate privacy attacks on stable marriage algorithms. Assuming that the attacker (e.g., the hospitals) can repeatedly interact with the stable marriage algorithm, we demonstrate how such interactions can reveal private preferences of the non-malicious side (e.g., the residents). We show that the widely applied Gale-Shapley Matching Algorithm, where the proposers' side is malicious, is vulnerable to privacy attacks and all honest agents' preferences can be revealed. We further investigate which preference distributions of the honest, non-malicious side are susceptible to privacy attacks and show that the Gale-Shapley Matching Algorithm where the honest side proposes can preserve privacy in non-susceptible preference distributions. We extend our results to the decentralized setting and show that the attacker's side can infer all preference orderings. In an experimental evaluation, we test privacy attacks on synthetic and real-world data and show that real-world data is indeed susceptible to privacy attacks. This work underlines a need for new privacy-preserving stable marriage algorithms.