Paper deep dive
Privacy Attacks on Stable Marriage
Stephan A. Fahrenkrog-Petersen, Aleksander Figiel, Darya Melnyk, Tijana Milentijević, Stefan Schmid
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 7/18/2026, 10:38:25 AM
Summary
This paper investigates privacy attacks on stable marriage algorithms, demonstrating that malicious agents (e.g., hospitals) can infer the private preference lists of honest agents (e.g., residents) by repeatedly interacting with the matching algorithm. The study shows that the Gale-Shapley algorithm is vulnerable when the malicious side proposes, allowing full preference revelation, whereas it may preserve privacy if the honest side proposes under specific distribution conditions. The authors extend these findings to decentralized settings and validate their theoretical results with experiments on synthetic and real-world data.
Entities (8)
Relation Signals (6)
Gale-Shapley Matching Algorithm → isvulnerableto → Privacy Attack
confidence 95% · We show that the widely applied Gale-Shapley Matching Algorithm, where the proposers' side is malicious, is vulnerable to privacy attacks
Hospitals → caninfer → Residents' Preferences
confidence 93% · we demonstrate how such interactions can reveal private preferences of the non-malicious side (e.g., the residents).
National Resident Matching Program → uses → Gale-Shapley Matching Algorithm
confidence 90% · The algorithm used in the program is based on the traditional Gale-Shapley algorithm
Centralized Model → supports → Privacy Attack
confidence 88% · In the centralized case, this can be done by repeatedly executing a matching algorithm with the identical preference matrix
Decentralized Model → supports → Privacy Attack
confidence 88% · We extend our results to the decentralized setting and show that the attacker's side can infer all preference orderings.
Gale-Shapley Matching Algorithm → canpreserveprivacyif → Honest Side Proposes
confidence 85% · show that the Gale-Shapley Matching Algorithm where the honest side proposes can preserve privacy in non-susceptible preference distributions.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2607.13015v1
- Canonical: https://arxiv.org/abs/2607.13015v1
PDF not stored locally. Use the link above to view on the source site.
Full Text
55,653 characters extracted from source content.
Expand or collapse full text
Privacy Attacks on Stable Marriage Stephan A. Fahrenkrog-Petersen University of LiechtensteinVaduzLiechtenstein stephan.fahrenkrog@uni.li , Aleksander Figiel TU BerlinBerlinGermany a.figiel@tu-berlin.de , Darya Melnyk TU BerlinBerlinGermany melnyk@tu-berlin.de , Tijana Milentijević TU BerlinBerlinGermany tijana.milentijevic@tu-berlin.de and Stefan Schmid TU Berlin and Weizenbaum InstituteBerlinGermany stefan.schmid@tu-berlin.de 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. †copyright: none © 2026 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. This research was supported by the German Research Foundation (DFG), Priority Programme SPP 2378 (ReNO-2), 2025–2029. 1. Introduction In many real-world applications, such as college admissions, donor-patient pairing, job markets, or residency assignment, it is required to compute a stable marriage, also referred to as the stable matching, that reflects the preferences of the participants. These preferences are typically expressed as ranked lists that contain sensitive information and should be kept private. A simple everyday example is assigning students to project topics: students rank the projects they would like to work on, while supervisors rank the students they would like to supervise. A matching is stable if there is no student and supervisor who would both rather work with each other than with their assigned partner. In order to compute a stable marriage, algorithms like the renowned Gale-Shapley algorithm let participants on one side propose to their top-ranked preference. If rejected, they iteratively propose to the next best alternative in their ranking. A particularly relevant and sensitive use case is the US National Resident Matching Program (NRMP), where medical graduates are matched to hospital residency programs. In this setting, applicants (graduates) are the more vulnerable side, while hospitals may have incentives to prefer candidates who rank them highly. For example, a clinic may avoid selecting applicants who list it as a second or third choice, fearing those candidates will leave after training. If such programs could infer or access parts of the applicants’ preferences, they might manipulate the process to their advantage. This undermines both fairness and stability, and highlights the need for matching protocols that maintain not only correctness, but also the confidentiality of individual preferences. Our Contribution We initiate the study of how much information one colluding side of the participants (the hospitals in the example) can infer about the preferences of the other side of the participants (the residents in the example). Note that we assume a strong collaboration on the colluding side, with full information exchange. The challenge lies in choosing preferences for the dishonest (colluding) side in such a way that useful information about the preferences of the honest side can be extracted from each stable matching. Given a single stable matching, an attacker may infer some preference information such as one participant ranking another above someone else. However, in practice, many matching systems repeat the matching process over multiple rounds, allowing the change of one’s preferences between the rounds. We show that this poses a great risk to the confidentiality of preference information. We analyze both the centralized and the decentralized settings. In the centralized case, a trusted third party aggregates all preferences and publicly announces a stable matching. In the decentralized setting, participants send each other matching proposals in a peer-to-peer fashion and thus determine their matching partner. In this work, we assume that each side has n participants. We show that: • it is possible to infer the top preference of all honest participants within n matching rounds, independent of the chosen algorithm, • it is possible to learn the full preference ordering of participants if all participants have the identical preferences, • there are algorithms that, under certain input preferences can prevent the attacker from revealing too much information, such as the Gale-Shapley matching algorithm where the honest side proposes, • the Gale-Shapley matching algorithm where the dishonest side proposes, as well as the decentralized Gale-Shapley matching algorithms, are vulnerable to revealing the full preference ordering. We further design multiple strategies for the centralized and decentralized setting that aim to maximize what can be learned about the preferences and evaluate them empirically on synthetic and real-world data. Example Consider the problem of pairing medical graduates with residency programs. In the US, the pairing is done using the National Resident Matching Program (NRMP), also known as The Match. The algorithm used in the program is based on the traditional Gale-Shapley algorithm where applicants propose, delivering an applicant-optimal solution. Both applicants and clinics submit their preferences to the R3 system, which performs the pairing centrally. Now hospitals might prefer candidates who rank them highly, fearing that applicants who ranked them lower would leave after training. Therefore, residency programs may have an incentive to learn applicants’ preferences and exploit this information to their advantage. As we demonstrate, by using different preference orderings and repeating the matching, the clinics are able to find out applicants’ preferences. Once the preferences are learned, the clinics can adjust their own preferences strategically to get a match in their favor. For a toy example on how the learning process for an attacker works see Figure 1. 1≻a _a2 \\ 2≻b _b1 1:ab 2:a\\ (15.0,15.0)[]2: blue!20 (15.0,15.0)[]ab 1:ba 2:b\\ (15.0,15.0)[]2: red!20 (15.0,15.0)[]ba Figure 1. A small example of how one can attack the preferences of agents a and b. The agents 1 and 2 are ranked highest by a and b, respectively (see top figure). If both attackers 1 and 2 lie about their preferences and set a as their top preference, as visualized in the bottom left figure, then, in any stable matching, a has to be matched to its first preference. Once we observe the matching for these preferences, and see that a and 11 are matched, we conclude 11 was the first preference of a. Likewise, the attackers can both set b as their first preference, as visualized in the bottom right figure, and learn that 22 is the first preference of b. Since this example is so small, once we know the first preference, we also know the last. In two matching iterations, the attackers were able to learn all preferences. 2. Related Work The stable marriage problem was formally introduced by Gale and Shapley in (Gale and Shapley, 1962) and is today often referred to as the stable matching problem. Later variants of this problem, such as allowing partial preferences or having ties in the preference list, have been considered in (Gusfield and Irving, 1989). Adversarial behavior in matching problems in form of strategic manipulation and misreporting of preferences has been studied extensively in the literature (Roth, 1982; Gusfield and Irving, 1989). (Roth, 1982) showed that the stable marriage is not always truthful, as agents could lie about their preferences in order to get a better matching partner. Nevertheless, (Gale and Shapley, 1962) have shown the proposing side cannot gain anything by misreporting their preferences in the Gale-Shapley algorithm. A similar setting was considered in (Teo et al., 2001), where it is required that all agents submit complete (not partial) preference lists. They showed that an optimal manipulation strategy for women, under the man-optimal Gale–Shapley outcome, can be computed in polynomial time. Additionally, cases where agents from the proposing side can work jointly to obtain better partners (Huang, 2006) and construct stable matching pairs even with errors in the input (Mai and Vazirani, 2018) were studied in the past. Also robustness measures, with respect to small changes in preferences, related to stable matchings were examined in (Boehmer and Boehmer, 2024; Chen et al., 2021; Drummond and Boutilier, 2013; Aziz et al., 2017, 2020). The aforementioned lying strategies assume the knowledge of preference orderings based on which a better pair for an agent can be obtained. (Constantinescu et al., 2025) recently introduced the notion of Byzantine stable matching. The authors study the solvability of the stable matching problem in the presence of malicious parties on both sides, examining how different communication models impose varying conditions for solvability. In contrast to the previous adversarial studies, our work focuses on inferring preference lists based on the pairs matched by an algorithm rather than manipulating the matching. Privacy aspects of stable marriage have also been considered in the literature. A stable matching algorithm is considered private if it computes a stable match while revealing no additional information to the adversary, beyond what can be inferred from the final matching itself and the preferences of the participants under the adversary’s control (Golle, 2006). (Golle, 2006) proposed an algorithm where privacy is guaranteed if the majority of matching authorities are honest. Further work regarding private matchings using secret sharing schemes (Franklin et al., 2007) and homomorphic encryption (Teruya and Sakuma, 2015) have been studied. Practically implemented private stable matchings with thousands of agents include (Doerner et al., 2016; Teruya and Sakuma, 2015; Keller and Scholl, 2014; Blanton et al., 2013; Zahur et al., 2016; Riazi et al., 2017). Research on multi-agent systems provides an additional perspective on private matching problems, particularly through work on strong collaboration among agents (Wooldridge, 2009; Sioutis and Tweedale, 2006; Zhang et al., 2025; Lashkari et al., 1997), where agents can collaborate to reach their own goals. In this context, matchmaking in multi-agent systems refers to mechanisms that assign agents to other agents or clusters based on their interests and preferences (Foner, 1997; Zhang and Zhang, 2002; Kuokka et al., 1995). Unlike our work, these scenarios are typically benign and assume all agents are honest and behave correctly. Note that in our work, benign agents do not collaborate, but we do assume strong collaboration among dishonest agents. The privacy attack considered in this paper was first introduced in the context of scheduling problems (Fahrenkrog-Petersen et al., 2023), where the original scheduling instance is solved and the privacy loss resulting from the publication of the final schedule is analyzed. To our best knowledge, we are the first to consider privacy attacks in stable marriage where only the final matching is revealed and the protocol itself does not expose intermediate state. 3. Privacy Attacks 3.1. Model Stable marriage/matching We consider a two-sided matching system with 2n2n participating agents, where every agent has to be matched to exactly one agent from the other side. The agents are divided into two groups, H=h1,…,hnH=\h_1,…,h_n\ representing honest agents, and D=d1,…,dnD=\d_1,…,d_n\ denoting dishonest agents, such that |H|=|D|=n|H|=|D|=n. We assume that the dishonest agents share all information with each other and coordinate on how to set their preferences. For simplicity one may assume a single entity controls the dishonest agents. We assume that each agent in a∈Ha∈ H (resp. D) maintains a strict, linear preference ordering πa _a over the agents in D (resp. H). In particular, for any pair of agents b,c∈Db,c∈ D, a∈Ha∈ H either strictly prefers agent b over c, denoted b≻acb _ac, or it strictly prefers agent c over b, denoted c≻abc _ab. We represent the ordering of agent a as a list πa=[1a,2a,…,na] _a=[1^a,2^a,…,n^a], where 1a1^a is the agent that a ranks the highest, and nan^a is the agent a ranks the lowest. We use ΠH ^H (resp. ΠD ^D) to denote the matrix containing the preferences of all agents a∈Ha∈ H (resp. D), specifically ΠD[d,i]=h ^D[d,i]=h is the honest agent h∈Hh∈ H that is ithi^th in the ranking of d∈Dd∈ D The goal is to find a stable matching M between H and D: a stable matching is a matching that does not contain any blocking matching pairs. A pair of agents (h,d)∈H×D(h,d)∈ H× D is called blocking, if both h and d prefer to be matched to each other over their current matching partner. In the following we define two models in which we consider the stable matching problem. Centralized model In the centralized setting, we assume that there is a trusted central server to which the agents submit their preference rankings. Upon receiving the preferences ΠH ^H and ΠD ^D, a matching algorithm is executed on the server to compute a stable matching M. Afterward, the agents receive their matching partners from the server. In this work, we will assume that the applied algorithm to compute a stable matching is public, and thus known to all agents. Decentralized model In the decentralized setting, we assume that the agents can communicate to each other in a peer-to-peer manner. The communication is assumed to be synchronous, i.e. all agents start executing a stable matching algorithms at the same time and proceed in rounds. We assume that all agents know the executed algorithm. Adversarial model In this work, we differentiate between two types of agents. The set H denotes a set of honest agents who always share their true preference lists with the central server in the centralized case. In the decentralized case, we assume that the honest agents do not change their preference lists during different algorithm runs, and that they always correctly follow the algorithm. The set D denotes the set of dishonest (or malicious) agents. These agents are not bound to sharing their true preferences with the central server or with other agents. Additionally, in the decentralized case, malicious agents may not follow the distributed algorithm correctly. Centralized privacy attack We assume that the goal of an attacker (who represents the malicious agents) is to violate the privacy of the honest agents. This means that the goal of the dishonest agents is to (at least partially) reveal the preference lists of the honest agents. In the centralized case, this can be done by repeatedly executing a matching algorithm with the identical preference matrix ΠH ^H, and adaptively changing dishonest preferences ΠD ^D. To compare different malicious attacks, we assume that one run of the matching algorithm by the server is atomic. An attack that finds out the preferences of the honest agents with fewer matching computations is thus favorable. Decentralized privacy attack While the goal of a malicious adversary is the same as in the centralized case, we change the way to estimate the efficiency of an attack. In the decentralized case, we count the number of rounds needed to reveal the preferences of the honest agents. If multiple algorithm executions are needed, we sum the number of rounds used in each execution. 4. Theoretical Results 4.1. Gale-Shapley Matching Algorithms In this section, we will describe different variants of the classical Propose&\&Reject (Gale and Shapley, 1962) algorithm that will be analyzed in the following sections. Propose&\&Reject - centralized The algorithm is executed by a central authority that collects complete preference lists from all agents and outputs a stable matching. In particular, one side (noted as the proposers) iteratively proposes to agents on the other side according to the preference ordering, while each receiver tentatively accepts the most preferred proposal so far and rejects the rest. The process continues until no further proposals are made and the central authority outputs a stable matching. Propose&\&Reject - decentralized This algorithm is a generalization of the centralized algorithm, and it is executed in synchronous rounds. In the first round, the proposing side proposes to agents on the other side according to the preference ordering. Next, each receiver tentatively accepts the most preferred proposal so far and rejects the rest. The process proceeds in rounds and terminates when no new proposals are made, resulting in a stable matching. 4.2. Algorithm-Independent Leakage In this section, we show privacy attacks that generalize to all matching algorithms. We start by proving that, independent of the choice of the preference matrix ΠH ^H, there exists an adversarial strategy that reveals the top preference of each honest agent. Lemma 0. Consider the centralized stable matching setting. Independent of the stable matching algorithm, it is always possible for the malicious side to learn the top preference of each agent in H within n iterations. Proof. Assume an adversarial strategy where, in the first iteration, every agent d∈Dd∈ D sets the first agent h1h_1 of H as the top choice for every candidate. This way, any stable matching algorithm has to match h1h_1 with its top choice. If this was not the case, h1h_1 and its top preference would form a blocking pair. Similarly in iteration i, the malicious agents place the ithi^th agent in H as their top alternative. After n rounds the adversary knows the top preferences in of every h∈Hh∈ H. ∎ Next, we consider the case where all good agents have the identical preferences in ΠH ^H. Lemma 0. If every row of ΠH ^H is the same, i.e., all good agents have the identical preferences, then there exists no stable matching algorithm that can hide ΠH ^H. Proof. By (Gusfield and Irving, 1989; Clark, 2006), there exists a unique stable matching if agents of at least one side all have the identical preference list. Since the matching is unique, we choose a stable matching algorithm and prove that this algorithm cannot hide ΠH ^H. Consider therefore the Propose&\&Reject algorithm where the attacker proposes. The attacker can learn the whole preference matrix in n iterations using the following strategy: Assume that there are n honest agents with IDs h1,h2,…,hnh_1,h_2,…,h_n and all of them have the identical preference orderings. Let the n malicious agents set their preferences in a Round-Robin manner for the next n iterations, where each agent has the identical preference list. For example, they set h1≻h2≻h3≻⋯≻hnh_1 h_2 h_3 … h_n in the first iteration; h2≻h3≻…hn≻h1h_2 h_3 … h_n h_1 in the second iteration; hn≻h1≻⋯≻hn−1h_n h_1 … h_n-1 in the last iteration. We refer to the corresponding attack as the Round-Robin attack. With this strategy, in each iteration, every honest agent will be paired with a different malicious agent that it has not been paired with in an earlier iteration. This happens, since all honest agents have the identical preference list and, in each execution of a matching algorithm, they will be proposed to by all malicious agents. For example, in iteration 33, malicious agents have the preference list h3≻h4≻⋯≻hn≻h1≻h2h_3 h_4 … h_n h_1 h_2. In this case, the agent h3h_3 will be proposed to first by all malicious agents and will pair with its highest preference. Similarly, agent h4h_4 would pair with its second hightest preference and so on. Note that the matching is different in every execution of a matching algorithm, because every honest agent has the identical preference list. Consider iteration k of the presented attack strategy. Assume agents hih_i and djd_j are matched. We know that djd_j ranks hih_i at position x=(i+k−1)modn+1x=(i+k-1) n+1 in this iteration. From the stability of the matching we can conclude that djd_j is in 1hi,…,xhi\1^h_i,…,x^h_i\. Now after n iterations of the attack strategy, for every honest agent hih_i, we have obtained the following information: for every y∈[n]y∈[n], hih_i was matched with some djyd_j_y in some iteration and it was determined that djyd_j_y is in 1hi,…,yhi\1^h_i,…,y^h_i\. However, since hih_i was matched to a different agent in each iteration we deduce that djyd_j_y in fact corresponds to yhiy^h_i of hih_i. Consequently, this attack strategy learns all preferences. Note that the attack strategy does not assume beforehand that all honest agents’ preferences are identical, however, if they are, then it succeeds in learning them. ∎ Observation 1. The Round-Robin attack also learns the top preference of each agent. 4.3. Analysis of centralized algorithms In this section, we analyze the privacy properties of the centralized stable marriage algorithms. We start by showing that there are special cases of ΠH ^H, where an algorithm can prevent an adversary from revealing too many preferences. Lemma 0. Assume that the top choice for each agent in H is different. Then, there exists a stable matching algorithm, such that no adversarial strategy can learn anything beyond the first preference. Proof. If the top choices of agents in H are different, a matching M that maps the agents in H with their top choices is always stable. Independent of the preferences in D and the bottom n−1n-1 preferences of agents in H, an algorithm can always output the matching M. This way, the malicious side cannot learn any more preferences beyond the top choices. ∎ Note that in Lemma 1 we showed that the top choices can always be learned independent of the algorithm. We now show that the above matrix ΠH ^H can be generalized: Corollary 0. Partition D into disjoint sets D1,…,DkD_1,...,D_k, further partition H into disjoint sets H1,…,HkH_1,...,H_k, such that |Di|=|Hi||D_i|=|H_i|. Define ΠH ^H such that all agents in HiH_i have DiD_i as their top preferences (the ordering of the preferences in DiD_i can vary among the agents in HiH_i). Then, there exists a stable matching algorithm, such that no adversarial strategy can learn anything beyond the clusters, that is learn how agents in HiH_i order D∖DiD D_i. Next, we show that the Propose&\&Reject algorithm, where the dishonest side proposes, is vulnerable to privacy attacks. Theorem 5. Assume that the Propose&\&Reject algorithm, where the dishonest side proposes, is used as the matching algorithm. Then, there exists a privacy attack that learns everything in n2n^2 matching iterations. Proof. By Lemma 1, it is possible to learn the first preference of each agent in n rounds. We use induction to show that the attacker can learn all preferences in ΠH ^H. The top preferences that can be learned with Lemma 1 form the induction base. The induction step is performed for each honest agent h separately. We assume that the attacker has learned the first i,i≥1i,i≥ 1 preferences of h. To learn the preference (i+1)h(i+1)^h, the attacker can use the following preference matrix: put h in the last place of its first i preferences 1h,…,(i)h\1^h,…,(i)^h\, and place h as the top choice for all other malicious agents. To prove that (h,(i+1)h)(h,(i+1)^h) will be matched, we need to show that no agent in 1h,…,(i)h\1^h,…,(i)^h\ will propose to h in the matching algorithm. Observe first that (i+1)h(i+1)^h will form a matching pair with h in the first round, since it is the highest ranked agent to propose to h in this round. After this round, h can only reject (i+1)h(i+1)^h if it receives a proposal from an agent in 1h,…,(i)h\1^h,…,(i)^h\. Moreover, none of the agents in D∖1h,…,(i)hD \1^h,…,(i)^h\ will propose to h anymore. We will now show that, in the following rounds, all other agents will form a stable matching among themselves and therefore no agent in 1h,…,(i)h\1^h,…,(i)^h\ will propose to h. Assume by means of contraposition that an agent d∈1h,…,(i)hd∈\1^h,…,(i)^h\ proposes to their last preference h. This means that the previous n−1n-1 proposals of this agent have been rejected. A proposal can only be rejected by an agent hi≠h_i≠ h if it accepts a proposal from another agent. That is, hih_i is matched to one of the remaining n−2n-2 agents in D (all agents excluding (i+1)h(i+1)^h and d). Observe that there are only n−2n-2 agents in D that can make agents H∖hH h reject proposals (or previously established matchings) from d. Thus, there must exist at least one agent in H∖hH h that accepts a proposal from d without rejecting it later. This is a contradiction to our previous assumption. This shows that h will not receive any proposals after the first matching round. Therefore (h,(i+1)h)(h,(i+1)^h) must form a pair in the output stable matching and thus be revealed to the attacker. ∎ We now turn our focus to centralized Propose&\&Reject algorithm where the honest side proposes and show that this algorithm can in fact preserve privacy in the previously discussed cases. Theorem 6. Assume that the Propose&\&Reject algorithm where the honest side proposes is used as the matching algorithm. This algorithm is privacy preserving with respect to Lemma 3 and Corollary 4. Proof. Consider the matrix in Lemma 3 first. In the first round of the Propose&\&Reject algorithm, all honest agents propose to their first preference in the list. By assumption, the first preference is different for every honest agent. Thus, every malicious node will receive exactly one proposal which it will accept in this round. Since every honest node has a matching partner, the algorithm terminates with a matching after one round. Next, consider ΠH ^H from Corollary 4. Observe that the agents in HiH_i will propose to agents in DiD_i first, and the Propose&\& Reject algorithm will establish a stable matching between these subsets. Thereafter, the agents in HiH_i will not propose anymore. This holds for every i∈[k]i∈[k]. The matching is stable, because none of the agents in HiH_i will prefer any of the agents in D∖DiD D_i. ∎ 4.4. Analysis of decentralized algorithms In this section, we show that the decentralized versions of both Propose&\&Reject algorithms are vulnerable to privacy attacks. For the analysis in the decentralized setting, we consider communication rounds within one iteration of the Propose&\&Reject algorithm used for sending proposals and rejecting them. Lemma 0. There is a malicious privacy attack that learns all preferences in the Propose&\&Reject algorithm, where the honest side initiates proposals. This attack takes 1 algorithm iteration with 2n2n communication rounds. Proof. If the honest agents are the proposers, malicious agents can strategically reject all incoming proposals. By observing the sequence of proposals they receive over n proposal rounds, the attacker can fully reconstruct the preference orderings of all honest agents. Moreover, the attacker can prevent honest agents from obtaining a matching. ∎ Lemma 0. There is a malicious attack that learns all preferences in the Propose&\&Reject algorithm, where the malicious side initiates proposals. This attack takes n(n−1)n(n-1) algorithm iterations with at least two communication rounds in each iteration. Proof. Using the round-robin proposal scheme, by Lemma 1, each honest agent’s top choice is revealed within the first n iterations. Over the next n(n−2)n(n-2) iterations, the attacker can uncover all remaining preferences, revealing one per round. To reveal agent h’s ithi^th preference ihi^h, the malicious agents manipulate their rankings as follows: The agents in positions 1h1^h through (i−1)h(i-1)^h of h place h at the bottom of their preference lists. All other malicious agents rank h as their top choice and propose. As shown in the proof of Theorem 5, h will accept the proposal from ihi^h. This allows the attacker to learn h’s ithi^th choice. This process is repeated for each agent and each preference position, enabling complete recovery of all preferences within n(n−1)n(n-1) iterations. ∎ 5. Simulations To complement our theoretical results we additionally performed simulations on both real-world as well as synthetically generated preferences. Our main focus here will be the central Propose&\&Reject algorithm in which the honest side initiates the proposals. From Theorem 6 we know that if all first preferences of the honest agents are different, then we can not learn anything beyond the first preferences. However, by Lemma 2 we know if all preferences are identical, then a Round-Robin attack learns all preferences in n iterations. We aim to investigate experimentally the structural gap between the two results, and answer how much we can learn in the cases in-between, specifically also in the case of structured real-world preference data. We note that we have also simulated the case in which the dishonest agents initiate proposals to see if our algorithms learn faster in practice than what is guaranteed by Theorem 5, which unfortunately was not the case. In general, we learn only one preference per iteration and not significantly more information, unless in specific cases such as when all honest agents’ preferences are identical. For completeness, we describe what information we learn from a matching, as well as the strategies we utilize in more detail. Finally, we briefly evaluate different strategies for the decentralized setting. As Lemma 7 shows, by simply rejecting all incoming proposals all preferences can be learned. However,this will also result in an empty matching. We evaluate different strategies that try to learn the preferences while also computing a matching. 5.1. Learning rules We initialize for every honest agent h and a position x in its preference with a set of possible dishonest agents that could occupy that position. Initially all these sets are D. During the execution of our algorithms we remove agents from these sets if we learn any information. The goal is to reduce the size of each possibility set down to one agent, if possible. We say a preference of some honest agent at some position has been learned, if the corresponding possibility set contains only a single element. It may happen that at the end of our algorithms we still have more than one possibility per honest agent and position. To measure the gained information about the preferences we introduce an uncertainty metric which we define as follows: ∑h∈H,x∈[n](possibilities for preference x of agent h)−n2n3−n2 _h∈ H,x∈[n](possibilities for preference x of agent h)-n^2n^3-n^2 Consequently, the uncertainty ranges from 0, if all preferences were learned, to 1, in the case that no information on the preferences was obtained. We use the below learning rules to shrink the size of the possibility sets: 5.1.1. General learning rule Let ΠH ^H and ΠD ^D be preferences of the honest and dishonest agents, respectively, and M a stable matching under these preferences. Let h be any honest agent and let d∈Dd∈ D be the dishonest agent it was matched to in M. Further, let P be the set of dishonest agents (excluding d) that would prefer h over their current partner in M. From the stability property we infer that d≻hpd _hp for all p∈Pp∈ P. This implies that d cannot be in the bottom |P||P| preferences of h. We thus remove d from h’s bottom most |P||P| possibility sets. 5.1.2. Information propagation Once we know there is only one possible position of agent d∈Dd∈ D in the preferences of agent h∈Hh∈ H then we fix that preference, by assigning the possibility set d\d\ at that position. Note that more involved propagation techniques are possible, e.g. based on similar combinatorial arguments. However, for simplicity we only use this one propagation rule for its simplicity and the ability to efficiently implement it. 5.1.3. Attack strategies For our experiments we utilized the following strategies for the dishonest agents: Random Here we simply try n2n^2 random preference matrices for the attackers as a baseline to compare our strategies against. We report on average values obtained from 10 different runs. Round-Robin This is the strategy utilized in Lemma 2. That is, all dishonest agents initially set their preferences to h1≻⋯≻hnh_1 … h_n. This preference order is then cycled in round-robin fashion in subsequent iterations. Recall that this strategy is guaranteed to always learn at least the first preferences of the honest agents. Brute-Force Here the attackers simply try all possible preferences for the attack. This takes (n!)n(n!)^n many iterations, which we have found to be only computationally viable for n at most 4. Targeted-Propose This strategy is based on the strategy described in Theorem 5, which is guaranteed to work if the dishonest agents propose. We now consider the setting where the honest agents propose. We adapt the strategy in the following ways: we try to first learn the first preferences of every agent, then the second preference of every agent and so on. In each iteration when we are trying to learn the ithi^th preference of honest agent h, as before, we try to prevent the dishonest agents 1h,…,(i−1)h1^h,…,(i-1)^h from matching with h by assigning h as their last preference, and the remaining ones assign h as their first preference. If we have not determined the preferences 1h,…,(i−1)h1^h,…,(i-1)^h we then stop trying to learn more preferences for h. Unfortunately, as the honest agents propose, we can not ensure that the agents 1h,…,(i−1)h1^h,…,(i-1)^h will not be matched to h. We try to mitigate this by assigning their top preferences to honest agents that also rank them highly. Specifically, we iterate over preference positions x starting with 1 and ending at n and for every honest agent h′≠h ≠ h, if we have determined the preference xh′x^h we assign h′h at the highest available free position in xhx^h’s preferences. Recall, that agents that have each other as their first preference have to be matched in any stable matching. For completeness we give the pseudocode in Algorithm 1. Learn first preferences using Round-Robin for h∈Hh∈ H do for i←1,…,ni← 1,…,n do if 1h,…,(i−1)h1^h,…,(i-1)^h are not determined then break end if F←1h,…,(i−1)hF←\1^h,…,(i-1)^h\ // Try to learn the i’th preference of h ΠD[d,k]←⊥∀d∈D,k∈[n] ^D[d,k]← ∀ d∈ D,k∈[n] for f∈Ff∈ F do ΠD[f]←[] ^D[f]←[\,] // Empty list end for for i′←1,…,ni ← 1,…,n do for h′∈Hh ∈ H with h′≠h ≠ h do f←(i′)h′f←(i )^h if f is determined and in F then append h′h to ΠD[f] ^D[f] end if end for end for for f∈Ff∈ F do while |ΠD[f]|<n| ^D[f]|<n do append ⊥ to ΠD[f] ^D[f] end while end for for d∈D∖Fd∈ D F do ΠD[d,1]←h ^D[d,1]← h end for Replace ⊥ ’s in ΠD ^D randomly to obtain a valid preference ordering for every agent Submit preferences and apply learning rules to the resulting matching end for end for Algorithm 1 Targeted-Propose 5.2. Brute-force attacks for n=4n=4 Firstly, we investigate how the different strategies perform by considering all possible 4×44× 4 preference matrices of the honest agents. To reduce the number of possible instances we only consider non-isomorphic instances. For example, we can assume any permutation of the honest and dishonest agents without changing the problem. Therefore we only consider 4×44× 4 preferences matrices for the honest agents where the entries in the first row are sorted, and the rows of the matrix are sorted lexicographically. This reduces the number of instances from 331,776 to 2,600. Note that within the Brute-Force strategy the same trick can not be performed and we still have to try all 331,776 preference matrices for the dishonest agents. Unfortunately, these were the largest instances we still could apply the Brute-Force strategy to in reasonable time. We summarize these results in Figure 2. It can be observed that the Random strategy with n2n^2 iterations appears to perform similar to the Round-Robin strategy that only needs n rounds. Even Brute-Force is not able to learn many preferences, however Targeted-Propose is not much worse despite using only at most n2n^2 iterations. Lastly, the Round-Robin approach with n iterations learns significantly less than Targeted-Propose. Figure 2. Results for brute-forcing all possible preferences for the honest agents using all possible preferences for the dishonest agents. 5.3. Synthetic data - entropy dissimilarity We define a new measure of similarities among the preferences of the honest agents, namely the entropy dissimilarity as follows: ∑ientropy in column inlogn _ientropy in column in n This way if all preferences are identical then dissimilarity is 0, and if they are all different, then dissimilarity is 1. We sample matrices with a desired dissimilarity, by first sampling a random matrix and then doing random ranking swaps that change dissimilarity in the right direction. This way we are able to interpolate smoothly between matrices where all preferences are different and ones where they are all identical. This allows us to investigate the structural gap between Theorem 6 and Lemma 2. We measured the uncertainty after an attack with our learning strategies in Figure 3. The Random strategy with n2n^2 iterations appears to have high uncertainty for all dissimilarity values, especially for dissimilarity 1 where it has the highest uncertainty among the different strategies, meaning it was not always able to learn the first preferences. The Round-Robin strategy efficiently learns preferences only when dissimilarity is low, whereas the uncertainty of preferences after an attack with Targeted-Propose appears to correlate well with the dissimilarity. However, note that the dissimilarity is not a perfect indicator; the first preferences could be all different, and the remaining preferences mostly identical, leading to low dissimilarity, but high uncertainty. Figure 3. Uncertainty for 64×6464× 64 preference matrices with varying dissimilarity. The error bars show the minimum and maximum among 50 samples. 5.4. Synthetic data - Mapel We utilized the Mapel dataset from (Boehmer et al., 2023). This dataset contains 503 stable matching instances grouped into 15 categories, based on the statistical cultures they originate from. All instances have the same number of agents, that is n=100n=100. We take both preference matrices from each instance to obtain 1006 privacy attack instances. See Figure 4 for a visualization of the learned preferences using our Targeted-Propose approach. The following can be deduced from the data: for most instances there exists an agent whose top-75% or more preferences we can learn fully, and in at least half of the instances we learn at least the top-25% preferences of half of the agents. The results are therefore heavily skewed: a fraction of agents have preferences that are easier to learn compared to the majority, and a further fraction has preferences that are difficult to learn much further beyond the first preference. Figure 4. Learned preference information for mapel datasets. The y-axes denote the agents, and the x-axis denotes the preferences. The colors indicate the size of the possible preference sets at the positions in the preference matrices after applying the Targeted-Propose strategy. Three subgroups of data from the dataset have been selected for which we computed the element-wise median of the set sizes in the matrices, and additionally the median over all 1006 instances in the dataset was taken (bottom right). Before the aggregation with the median, the agents are sorted according to how much was learned for them. 5.5. Real-world data - student/project allocation The availability of real-world matching data is unfortunately very limited. The PrefLib preference library (Mattei and Walsh, 2013) contains a single real-world dataset for a matching problem with preferences, which contains data from a student/project allocation problem at a university (Kwanashie et al., 2015). For 8 different academic years, around 31–51 students each year submitted a linear ordering over their top-5 rated projects, out of 56–155 available projects. In this case, we assume the attackers are the project supervisors, wishing to learn the project preferences of the students. To fit this to our setting we set the remaining project preferences of the students randomly. Furthermore, as the number of students is smaller than the number of available projects, we considered different strategies for ensuring the number of participants on each side is the same: duplicating one student many times, or duplicating all students roughly the same number of times, or, finally, adding new dummy students with random preferences. However, there was no large difference in the results in any of these approaches, thus we report on the case where we duplicated one student many times. Using our Targeted-Propose strategy we can determine the top 5 preferences for most students. For a visualization of the learned preferences see Figure 5. Therein we depict the four project years where we learned the fewest preferences. For the last three project years we learn all top-5 preferences, and for another 3 years we only do not learn 1–4 preferences. As we are only interested in the top-5 preferences it is also sufficient to use 5n5n attack iterations. Our Round-Robin approach was only able to learn the top-1 preferences and in a few cases also the second preference, but not much more. Figure 5. Learned student preferences for the academic years 2007 to 2010 (left to right) using Targeted-Propose. The students are on the y-axis and the preferences are on the x-axis, starting with top preferences on the left side. The colors indicate the size of the preference possibility sets. 5.6. Decentralized Setting Figure 6. Simulation results for 64×6464× 64 preference matrices with varying dissimilarity in the decentralized setting. The error bars show the minimum and maximum among 50 samples. Matched refers to the number of matched agents after applying a strategy, whereas the learned fraction is the fraction of revealed honest agents’ preferences. We simulate a decentralized setting in which the honest agents send proposals to the dishonest agents. We assume the agents send proposals as in the Propose&\&Reject algorithm, that is, in order of their preferences. The dishonest agents therefore learn from each incoming proposal one preference from an honest agents ranking. Furthermore, we assume the proposals are sent in synchronous rounds, where in one round all honest agents that are unmatched each send one proposal to an dishonest agent, then the dishonest agents decide which proposals to accept. The goal for the dishonest agents is therefore to behave strategically in a way that maximizes the number of proposals sent by the honest agents. As shown in Lemma 7, if the dishonest agents simply reject all incoming proposals, then they learn all preferences. However, this also results in an empty matching, which means that the honest agents can realize, that the dishonest agents did not follow the Propose&Reject algorithm. We empirically evaluate different strategies for the dishonest agents to accept or reject the incoming proposals in an attempt to learn as much information as possible while also matching as many agents as possible. We consider the following strategies: One-Accept in any given round an arbitrarily chosen proposal is taken and the two agents, the one being proposed to and the one proposing, are matched. If the agent that was proposed to was already matched, then it rejects its previous matched partner. One-Free-Accept: here in any round we choose arbitrarily one proposal to an unmatched dishonest agent and match it with the proposing honest agent. All-Accept all proposals are accepted by the dishonest agents. Note that if an agent gets two or more proposals in one round, then it will accept all of them, but also immediately reject all but one of them. Accept-Last-Round the dishonest agents reject all proposals in the first n−1n-1 rounds, and in the final round accept all proposals. This is similar to the strategy used in Lemma 7, but tries to find a matching in the last round. Accept-Last-Proposal here the dishonest agents keep track of which proposals were already sent by the honest agents. An unmatched dishonest agent accepts a proposal only if all other unmatched honest agents proposed to it, that is, this is the last proposal the agent may still receive, so it accepts it. The results for these strategies are presented in Figure 6. The only strategy among these that always resulted in a complete matching was All-Accept, unfortunately this was also the strategy that generally learned the least. The One-Accept and One-Free-Accept appear to match at least half of the agents, but learn only around half of the preferences. Accepting in the last round learns all preferences similar to the strategy in Lemma 7, but does the number of matched agents varies greatly — all agents are matched only if the last preferences are all different. Accepting the last proposal appears to generally learn many preferences, however a small fraction of unmatched agents remains. 6. Conclusion In this work, we introduced the notion of privacy attacks for the stable marriage problem. We showed that stable marriage algorithms from the literature are vulnerable to these attacks. Our practical evaluation demonstrated that also on real-world datasets we can often learn top-20% of the preferences, even in the theoretically challenging settings. Our work shows that there is a need for new privacy-preserving stable marriage algorithms to make sure that the private preferences of the participants are protected. It will be interesting in future work to contribute to devising such algorithms, also answering the question: given a preference matrix of the honest participants, how much information would the best-possible matching algorithm have to reveal in this case? Another interesting direction for future work is to focus on attacks in which different subsets of agents participate across repeated executions. In many real-world markets, such as job markets, school choice or organ exchange, participants may enter and leave over time. Understanding how dynamic participation affects privacy leakage is an important next step. Finally, while existing privacy-preserving techniques can in principle protect preferences, their computational cost and practical feasibility for large matching markets require further investigation. References H. Aziz, P. Biró, T. Fleiner, S. Gaspers, R. de Haan, N. Mattei, and B. Rastegari (2017) Stable matching with uncertain pairwise preferences. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’17, Richland, SC, p. 344–352. Cited by: §2. H. Aziz, P. Biró, S. Gaspers, R. de Haan, N. Mattei, and B. Rastegari (2020) Stable matching with uncertain linear preferences. Algorithmica 82 (5), p. 1410–1433. Cited by: §2. M. Blanton, A. Steele, and M. Alisagari (2013) Data-oblivious graph algorithms for secure computation and outsourcing. In Proceedings of the 8th ACM SIGSAC symposium on Information, computer and communications security, p. 207–218. Cited by: §2. K. Boehmer and N. Boehmer (2024) Worst-and average-case robustness of stable matchings:(counting) complexity and experiments. In ECAI 2024, p. 3469–3476. Cited by: §2. N. Boehmer, K. Heeger, and S. Szufa (2023) A map of diverse synthetic stable roommates instances. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’23, Richland, SC, p. 1003–1011. External Links: ISBN 9781450394321 Cited by: §5.4. J. Chen, P. Skowron, and M. Sorge (2021) Matchings under preferences: strength of stability and tradeoffs. ACM Trans. Econ. Comput. 9 (4). External Links: ISSN 2167-8375, Link, Document Cited by: §2. S. Clark (2006) The uniqueness of stable matchings. Contributions in Theoretical Economics 6 (1). Cited by: §4.2. A. Constantinescu, M. Dufay, D. Ghinea, and R. Wattenhofer (2025) Byzantine stable matching. External Links: 2502.05889, Link Cited by: §2. J. Doerner, D. Evans, and a. shelat (2016) Secure stable matching at scale. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS ’16, New York, NY, USA, p. 1602–1613. External Links: ISBN 9781450341394, Link, Document Cited by: §2. J. Drummond and C. Boutilier (2013) Elicitation and approximately stable matching with partial preferences.. In IJCAI, p. 97–105. Cited by: §2. S. A. Fahrenkrog-Petersen, A. Senderovich, A. Tichauer, A. K. Tutak, J. C. Beck, and M. Weidlich (2023) Privacy attacks on schedule-driven data. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 37, p. 11972–11979. Cited by: §2. L. N. Foner (1997) Yenta: a multi-agent, referral-based matchmaking system. In Proceedings of the first international conference on Autonomous agents, p. 301–307. Cited by: §2. M. Franklin, M. Gondree, and P. Mohassel (2007) Improved efficiency for private stable matching. In Cryptographers’ Track at the RSA Conference, p. 163–177. Cited by: §2. D. Gale and L. S. Shapley (1962) College admissions and the stability of marriage. The American mathematical monthly 69 (1), p. 9–15. Cited by: §2, §2, §4.1. P. Golle (2006) A private stable matching algorithm. In Financial Cryptography and Data Security, G. Di Crescenzo and A. Rubin (Eds.), Berlin, Heidelberg, p. 65–80. External Links: ISBN 978-3-540-46256-9 Cited by: §2. D. Gusfield and R. W. Irving (1989) The stable marriage problem: structure and algorithms. MIT Press, Cambridge, MA, USA. External Links: ISBN 0262071185 Cited by: §2, §2, §4.2. C. Huang (2006) Cheating by men in the gale-shapley stable matching algorithm. In European Symposium on Algorithms, p. 418–431. Cited by: §2. M. Keller and P. Scholl (2014) Efficient, oblivious data structures for mpc. In International Conference on the Theory and Application of Cryptology and Information Security, p. 506–525. Cited by: §2. D. Kuokka, L. Harada, et al. (1995) Matchmaking for information agents. In IJCAI (1), p. 672–678. Cited by: §2. A. Kwanashie, R. W. Irving, D. F. Manlove, and C. T. S. Sng (2015) Profile-based optimal matchings in the student/project allocation problem. In Combinatorial Algorithms, Cham, p. 213–225. Cited by: §5.5. Y. Lashkari, M. Metral, and P. Maes (1997) Collaborative interface agents. Readings in agents, p. 111–116. Cited by: §2. T. Mai and V. V. Vazirani (2018) Finding Stable Matchings That Are Robust to Errors in the Input. In 26th Annual European Symposium on Algorithms (ESA 2018), Y. Azar, H. Bast, and G. Herman (Eds.), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 112, Dagstuhl, Germany, p. 60:1–60:11. Note: Keywords: Stable Matching, Robust External Links: ISBN 978-3-95977-081-1, ISSN 1868-8969, Document Cited by: §2. N. Mattei and T. Walsh (2013) PrefLib: a library of preference data http://preflib.org. In Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT 2013), Lecture Notes in Artificial Intelligence. Cited by: §5.5. M. S. Riazi, E. M. Songhori, A. Sadeghi, T. Schneider, and F. Koushanfar (2017) Toward practical secure stable matching. Proceedings on Privacy Enhancing Technologies. Cited by: §2. A. E. Roth (1982) The economics of matching: stability and incentives. Mathematics of operations research 7 (4), p. 617–628. Cited by: §2. C. Sioutis and J. Tweedale (2006) Agent cooperation and collaboration. In International Conference on Knowledge-Based and Intelligent Information and Engineering Systems, p. 464–471. Cited by: §2. C. Teo, J. Sethuraman, and W. Tan (2001) Gale-shapley stable marriage problem revisited: strategic issues and applications. Management Science 47 (9), p. 1252–1267. Cited by: §2. T. Teruya and J. Sakuma (2015) Round-efficient private stable matching from additive homomorphic encryption. In Information Security: 16th International Conference, ISC 2013, Dallas, Texas, November 13-15, 2013, Proceedings, p. 69–86. Cited by: §2. M. Wooldridge (2009) An introduction to multiagent systems. John wiley & sons. Cited by: §2. S. Zahur, X. Wang, M. Raykova, A. Gascón, J. Doerner, D. Evans, and J. Katz (2016) Revisiting square-root oram: efficient random access in multi-party computation. In 2016 IEEE Symposium on Security and Privacy (SP), p. 218–234. Cited by: §2. X. Zhang, X. Dong, Y. Wang, D. Zhang, and F. Cao (2025) A survey of multi-ai agent collaboration: theories, technologies and applications. In Proceedings of the 2nd Guangdong-Hong Kong-Macao Greater Bay Area International Conference on Digital Economy and Artificial Intelligence, DEAI ’25, New York, NY, USA, p. 1875–1881. External Links: ISBN 9798400712791, Link, Document Cited by: §2. Z. Zhang and C. Zhang (2002) An improvement to matchmaking algorithms for middle agents. In Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems: Part 3, AAMAS ’02, New York, NY, USA, p. 1340–1347. External Links: ISBN 1581134800, Link, Document Cited by: §2.