Strategic Aspects of Stable Matching Markets: A Survey

1 Introduction

Two-sided matching markets describe a large class of problems wherein agents from one side of the market must be matched to the agents in the other side according to their preferences. These markets are present in a wide range of applications in economics, computer science, and artificial intelligence such as school choice [Abdulkadiro˘glu et al., 2005a; Abdulkadiro˘glu et al., 2005b], medical residency [Roth and Peranson, 1999], refugee placement [Aziz et al., 2018; Ahani et al., 2021], ridesharing platforms [Banerjee and Johari, 2019], electric vehicle charging [Gerding et al., 2013], and recommendation systems [Eskandanian and Mobasher, 2020]. The primary objective is to find a stable matching between the two disjoint sets (colloquially men and women) such that no pair of agents prefer each other to their matched partners.

The celebrated Deferred Acceptance (DA) algorithm [Gale and Shapley, 1962] is an elegant mechanism that guarantees a stable solution. Under this algorithm, agents from one side (say men) make proposals to the agents on the other side (say women). Each woman tentatively accepts her favorite proposal and rejects the rest. 1

1 The use of gender-based pronouns to distinguish two disjoint sets of agents (men/women) is merely for the ease of exposition and for consistency with a plethora of work in matching markets.

The DA algorithm is only strategyproof for one side of the market, i.e. the proposing side (men), enabling the agents on the receiving side (women) to behave strategically. In fact, it is well-known that any stable matching algorithm is susceptible to strategic misreporting of preferences by agents [Roth, 1982]. These strategic behaviors may negatively influence the stability of the resulting outcome. Due to the practical appeal of the DA algorithm, various models of strategic behavior have been investigated, both from computational and axiomatic perspectives. The majority of these works focus on "one-sided" manipulation strategies wherein the misreporting agent and the beneficiary are on the same side [Roth and Rothblum, 1999; Teo et al., 2001; Vaish and Garg, 2017; Dubins and Freedman, 1981; Huang, 2006]. However, strategic behavior may not always be confined to the agents from the same side, i.e. the manipulation may be "two-sided" with a coalition of agents from different sides. For example, in school choice problems, there is evidence that schools could influence the preferences of students through indirect strategies such as fee hikes [Hatfield et al., 2016]. Moreover, the set of misreporting agents and the beneficiaries may not necessarily overlap: an agent may misreport not to benefit itself, rather to improve the outcome for other agents.

This paper is an excursion into strategic behavior of agents in stable matching markets. We explore strategic behavior of agents or coalitions of agents along the dimensions of onesided, two-sided, and manipulations with externalities. We discuss strategic misreporting by permutation of the preference list, truncation of the list, or strategies involving dropping agents from the preference list. Through these distinctions, we identify several classes of strategic behavior beyond traditional studies, and along the way, highlight a series of open research questions.

2 Preliminaries

Problem setup. An instance of the stable matching problem is given by a tuple ⟨M,W, ≻⟩, where M is a set of men, W is a set of women, and ≻ is a preference profile which specifies the preference lists of all the agents. The preference list of an agent i, denoted by ≻i, is a strict total order over the agents on the other side. We write w1 ≻m w2 to denote that m prefers w1 to w2 and w1 ⪰m w2 to denote "either w1 ≻m w2 or w1 = w2". Moreover, for a set X ⊆ M ∪W, we write ≻-X to denote a preference profile without the preferences of individual agents in set X; thus, ≻= {≻-X, ≻X}. In this paper, we primarily consider one-to-one matchings where |M| = |W| = n.

Stable matching. A matching is a function µ : M ∪W → M ∪ W such that µ(m) ∈ W for all m ∈ M, µ(w) ∈ M for all w ∈ W, and µ(m) = w if and only if µ(w) = m. Given a matching µ, a blocking pair with respect to the preference profile ≻ is a pair (m, w) who prefer each other over their assigned partners, i.e., w ≻m µ(m) and m ≻w µ(w). A matching is said to be stable if it does not have any blocking pair. We write S≻ to denote the set of all stable matchings with respect to ≻. The set of stable matchings, S≻, forms a distributive lattice, and its size can be exponential in n [Knuth, 1997]. For any pair of matchings µ, µ′ , we write µ ⪰X µ′ if all agents in X weakly prefer µ over µ′ , i.e., µ(i) ⪰i µ′ (i) for all i ∈ X. Note that if X = M, then µ is weakly better-off for all men (analogously for women if X = W).

Matching mechanisms. A matching mechanism ϕ returns a matching µ corresponding to an instance ⟨M,W,≻⟩, i.e. µ := ϕ(≻). The most seminal mechanism-proposed by Gale and Shapley [1962]-is the deferred acceptance (DA) algorithm that, given a preference profile, proceeds by a series of proposals and rejections. In the initial proposal phase, each of the unmatched men propose to their favourite woman who has not rejected them yet. In the subsequent rejection phase, each woman tentatively accepts her favourite proposal, rejecting the others. The algorithm terminates when no further proposals can be made. Gale and Shapley [1962] showed that given any preference profile ≻, the matching computed by the DA algorithm, denoted by DA(≻), is stable, and menoptimal as each man receives his favorite partner among all stable matchings in S≻. Furthermore, the same matching is simultaneously women-pessimal [McVitie and Wilson, 1971]. In other words, given a matching µ := DA(≻), every man m ∈ M (weakly) prefers his matched partner in µ to their partners in any other stable matching, and every woman w ∈ W (weakly) prefers her match in any other stable matching than the one in µ.

Manipulation. The set of strategic agents X ⊆ M ∪ W contains a subset of manipulating agents A ⊆ X who misreport their preferences to (weakly) improve the matching outcome for a fixed subset of beneficiary agents B ⊆ X. Formally, given a preference profile ≻ and a set of beneficiary agents B ⊆ M ∪W, we say that a set of manipulating agents A ⊆ M ∪ W can strategically manipulate a mechanism ϕ if there exists a misreport ≻′A such that ϕ(≻-A, ≻′A) ⪰B ϕ(≻), with a strict inequality for at least one agent i ∈ B. The strategy ≻′ is said to be optimal when no other strategy results in a matching which Pareto dominates ϕ(≻-A,≻′A) for agents in B; otherwise, it is called a suboptimal strategy.

The relation between the strategic agents, i.e. manipulating agents A and beneficiaries B, gives rise to a variety of intriguing strategic behavior. For instance, A = B implies self-manipulation by a coalition of agents, as in coalitional manipulation by men (when A ⊆ M) [Dubins and Freedman, 1981] or women (when A ⊆ W) [Shen et al., 2021]. On the other hand, A ̸= B implies manipulation to improve the outcome possibly for other agents as in accomplice manipulation [Hosseini et al., 2021]. We say a manipulation strategy is one-sided if all manipulating and beneficiary agents are from the same side (either men or women), i.e., A,B ⊆ M or A,B ⊆ W; otherwise, it is a two-sided manipulation strategy, i.e. there exist at least one man m ∈ M and one woman w ∈ W in A ∪ B. With this lens, we say that a strategy is a single-agent manipulation when A = B and |A| = 1 (in other words, |A ∪ B| = 1), e.g. settings studied by Teo et al.; Vaish and Garg [2001; 2017]. Whenever |A∪B| > 1, the manipulation is said to be coalitional.

Manipulation strategy. An agent's manipulation strategy is often through misreporting its preference: either by declaring members in the tail of their preference as unacceptable (truncation manipulation), or by changing the priority ordering of different members in its preference list (permutation manipulation). A permutation manipulation is said to be inconspicuous if each manipulator only changes the position of a single agent in its preference list. A manipulation strategy is said to be with no-regret when the resulting matching is not worse-off for any manipulator; otherwise, it is a with-regret manipulation strategy.

3 Types of Manipulations

This section explores the various types of manipulations of the DA algorithm. The first two subsections (Sections 3.1 and 3.2) explore different types of manipulations that result from the relation between the manipulators A and the beneficiaries B. Table 1 summarizes the current known results in strategic manipulation and the open problems in this setting. In the final subsection, we discuss manipulations which are performed by external agents in scenarios that include bribery or side-payments.

3.1 One-SidedManipulation

We study four types of one-sided manipulations based on the manipulation strategy employed and whether it is a singleagent or coalitional manipulation.

Single-agent truncation manipulation. In the menproposing DA algorithm, no single man can benefit by truncating his own preference list [Roth, 1982].

However, in cases where ⟨M,W,≻⟩ admits at least two stable matchings, there always exists a woman who benefits from truncating her preference [Gale and Sotomayor, 1985]. Her optimal strategy is to truncate preferences at her womanoptimal matching partner, i.e., if a woman w receives the man m in the women-proposing DA algorithm, then her optimal strategy in the men-proposing DA algorithm is to report all men below m in her true preference list as unacceptable. This strategy requires less information, making truncation manipulation robust and easy to perform [Roth and Rothblum, 1999]. In large markets, women may significantly alter their preferences by truncating a substantial portion (nearly all) of their list in the optimal manipulation; the size of truncation increases with reduced risk aversion and decreased correlation across agents' preferences [Coles and Shorrer, 2014].

Truncation manipulation by a single agent is also 'exhaustive', meaning any manipulation achievable by any singleagent manipulation strategy can be replicated or improved upon by some truncation strategy [Jaramillo et al., 2014].

Table 1: Summary: Types of Permutation Manipulations. Here ✗, denotes that DA is not manipulable by the corresponding manipulator and beneficiary sets, whereas ✓, denotes that it is manipulable. 'Weak' represents that no beneficiary gets worse-off, but not all of them become strictly better-off. Problems which have not been studied are marked with a question mark (?). Whenever these manipulations preserve stability, we mark them in green, and when they do not, we mark them in red. 1 denotes a result by Dubins and Freedman [1981], 2 Huang [2006], 3 indicates results by Hosseini et al. [2021], 4 by Hosseini et al. [2022], 5 by Teo et al. [2001], 6 by Vaish and Garg [2017], 7 by Shen et al. [2021], and 8 by Demange et al. [1987].

Open Problem 1. Is truncation manipulation exhaustive against coalitional manipulations?

With respect to one-sided coalitions, truncation manipulation strategies are not exhaustive. However, a generalization of truncation strategies called dropping strategies, where any subset of agents can be deemed unacceptable in the preference list (not just all agents starting from a certain point), are known to be exhaustive against one-sided coalitional manipulations [Jaramillo et al., 2014]. The question of the exhaustiveness of truncation manipulation (and its dropping strategy generalization) against two-sided manipulations remains unexplored.

Single-agent permutation manipulation. Similar to truncation manipulation, a man cannot obtain a better partner by permuting his own preference in the men-proposing DA algorithm [Dubins and Freedman, 1981; Huang, 2006]. 2 However, women can manipulate the DA algorithm [Roth, 1982].

Example 1 (Permutation manipulation by a woman). Consider a matching instance with four men and four women having the following preference profile. The DA outcome is underlined.

For A = B = {w1}, when she misreports her preference as ≻′w1 := m3 ≻ m1 ≻ m2 ≻ m4 while others continue to truthfully report their preferences, the resulting matching on the execution of DA is marked by ∗ ; woman w1 prefers the latter since she is matched to her most preferred man, m3.

In the men-proposing DA, the optimal single-agent permutation manipulation strategy can be computed by a woman in polynomial time [Teo et al., 2001]. Moreover, the optimal manipulation can be achieved in an inconspicuous way, i.e., the manipulator only needs to change the position of a single agent in its list [Vaish and Garg, 2017]. While under the optimal manipulation, the resulting matching remains stable with respect to the truthful profile (aka it is stability-preserving), a suboptimal manipulation may no longer preserve stability.

2 However, DA does not satisfy a refinement of strategyproofness, called obvious strategy-proofness [Li, 2017], for the proposing side [Ashlagi and Gonczarowski, 2018].

After learning that a woman can benefit by permuting her own preference, the next natural question that arises is: to what extent can a woman benefit from a permutation manipulation? Unlike truncation manipulation in which a woman can always obtain her woman-optimal matching partner, there are instances in which it is impossible for a woman to obtain her women-optimal matching partner by permutation manipulations alone [Teo et al., 2001].

Open Problem 2. Are there necessary and sufficient conditions for achieving the women-optimal match through singleagent permutation manipulation? And how likely is it for DA to result in the women-optimal partner for a single manipulator who performs an optimal permutation manipulation?

When multiple women independently manipulate their preferences, in the optimal scenario, ( 12 + o(1))log(n) number of women are required to manipulate their preferences to reach the women-optimal solution. However, nearly every woman may need to manipulate if the set of (independent) manipulators are randomly chosen [Ndiaye et al., 2021].

Coalitional truncation manipulation. If all women perform their optimal truncation manipulation, then the matching produced by the men-proposing DA algorithm is the women-optimal matching. Not only this strategy ensures that the women-optimal matching can be achieved by coalitional truncation manipulation, but also it guarantees that it is the unique stable matching in the manipulated instance. In fact, this strategy is a strong Nash equilibrium in the associated game when all women are strategic [Shen et al., 2018].

This result can be extended to coerce any M-rational matching 3 as the unique stable matching through a coalitional dropping strategies by women [Gonczarowski, 2014].

Coalitional permutationmanipulation. While aman cannot perform a single-agent manipulation in the DA algorithm, a coalition of men can collectively misreport their preferences to weakly benefit [Dubins and Freedman, 1981;

3 An M-rational matching is a matching where every man prefers to be matched to their partners rather than remaining single.

Huang, 2006]. However, there always exists at least one man in the coalition who continues to be matched to the same partner; thus, the coalition cannot strictly improve through any manipulation. To address this impossibility, Huang [2006] studies whether men can collude to be strictly better-off in expectation when random stable matchings are chosen.

On a structural note, the optimal coalition strategy for a coalition of men while helping a (possibly distinct) set of men-beneficiaries is characterized by 'push-down' operations by every manipulator, i.e., pushing down some highly preferred women in the manipulating man's preference list by declaring them as less desirable [Huang, 2006]. Since this manipulation makes the beneficiary men better-off than their men-optimal matching, such a manipulation necessarily results in an unstable matching.

Shen et al. [2021] consider the optimal self-coalitional manipulation by a subset of women (i.e., A = B ⊆ W) and provide an efficient algorithm to compute the manipulated strategy profile. This strategy profile is stability preserving, inconspicuous (in every manipulating woman's true preference list), and is Pareto optimal for the women across all stable matchings. Interestingly, they show that this constructed strategy is also a Nash equilibrium of the manipulation game (see Section 4). While this paper studies what happens when the manipulators are the beneficiaries themselves, one may ask what happens when they are distinct.

Open Problem 3. What is the optimal coalitional strategy for the manipulating women A ⊆ W, when the set of beneficiaries B ⊆ W need not necessarily be exactly the same as the manipulators (A ̸= B)?

Towards this, the works of Kobayashi and Matsui; Kobayashi and Matsui [2009; 2010] becomes relevant. They ask: given the preference list of all men ≻M and a matching µ, can we determine whether there exists a preference profile ≻W reported by women for which we obtain µ on running the men-proposing DA algorithm on (≻M,≻W)? Based on a simple condition on the relation between the men's preferences and the desired matching µ, such a preference profile of the women can be efficiently computed, whenever it exists.

3.2 Two-SidedManipulation

The majority of work in stable matching considers one-sided manipulation strategies. Yet, agents from both side of the market may form strategic coalitions to improve their outcome. Demange et al. [1987] showed that a coalition of manipulators consisting of both, men and women, cannot strictly benefit from their own misreport. These results extend the impossibility of manipulations by a coalition consisting of only men in the men-proposing DA algorithm [Dubins and Freedman, 1981].

In a broader sense, a two-sided coalition of agents may form new strategic behavior, particularly when the manipulators are not necessarily also the beneficiaries. In this line, Bendlin and Hosseini [2019] proposed a manipulation strategy through an accomplice.

Accomplice Manipulation. An accomplice man (A = {m}) has the ability to misreport his preferences to improve a woman's (B = {w}) matching outcome while maintaining his own match. This type of manipulation is particularly significant when it enables a woman to achieve better outcomes compared to what she could achieve through selfmanipulation alone.

Example 2 (Accomplice manipulation; adopted from Example 1 in [Hosseini et al., 2021]). Consider a matching instance with four men and four women having the following preference profile; the DA matching in underlined in the instance.

m1: w∗ 3 w2 w1 w4 w1: m4 m∗3 m1 m2 m2:w1 w∗ 4 w2 w3 w2: m∗4 m3 m2 m1 m3:w2 w4 w∗ 1 w3 w3: m3 m∗1 m2 m4 m4: w∗ 2 w1 w3 w4 w4: m∗2 m1 m3 m4

Notice that woman w1 cannot benefit from lying about her own preferences since she only receives a proposal fromm2 in the execution of DA. However, if m1 misreports his preferences as ≻′m1 := w1 ≻ w3 ≻ w2 ≻ w4, then in the resulting matching (marked by ∗ ), w1's match improves from m2 to m3. Since m1 continues to be matched to w3, he incurs no regret through this manipulation.

Like one-sided manipulations by women, any beneficial accomplice manipulation can be equivalently performed via an inconspicuous strategy; thus, an optimal accomplice manipulation can also be found in polynomial time. Moreover, as long as the manipulator man incurs no regret during this manipulation, accomplice manipulation also preserves stability [Hosseini et al., 2021].

Note that a man may expand his strategy space to further improve a woman's matching if he is willing to incur some regret during the manipulation [Hosseini et al., 2021]. Such considerations becomes relevant in situations of bribery and side-payments; we will discuss this further in Section 3.3.

One-for-All Manipulation. Consider the matching instance in Example 2. Notice that m1's misreport not only benefits w1 but also w4, i.e., the resulting matching from the manipulation Pareto dominates the original matching for all women. Thus, extending accomplice manipulations, it is possible for an accomplice man to misreport in order to help all the women; such a manipulation is referred to as one-for-all manipulation [Hosseini et al., 2022]. Specifically, a one-forall manipulation is characterized by A = {m} and B = W.

Unlike single-agent manipulation by a woman and accomplice manipulation, the optimal one-for-all manipulation need not be inconspicuous, i.e., there exist matching instances for which an accomplice man needs to push-up more than one woman in his preference list in the optimal strategy. 4 Despite this, Hosseini et al. [2022] provide a polynomial time algorithm for computing the optimal one-for-all manipulation strategy. Moreover, as before, the optimal strategy is stability preserving.

The next natural question that arises is whether a group of men can collectively improve the preference of some woman, more than they can do so individually.

4 In a push-up operation, a manipulator moves-up a set of less desired agents higher than its DA partner in its preference ordering.

Open Problem 4. Do there exist instances in which a coalition of men manipulate for a single beneficiary woman (i.e., A ⊆ M, B = {w}), even when none of them can individually help her? Are these manipulations stability preserving, inconspicuous, and efficiently computable?

The technical simplification in two-sided manipulation so far arose from the fact that it was sufficient to focus on inconspicuous strategies or push-up operations. However, the case of a group of men helping a single women is complicated by the plausible requirement of a combination of push-up and push-down operations.

Two-for-One Manipulation. Interestingly, a woman can benefit more from a collective misreport from a man and herself, as compared to self-manipulation by herself or through an accomplice manipulation with the help of the man (A = {m,w} and B = {w}). Such strategic coalitions are called two-for-one manipulations [Hosseini et al., 2022].

Example 3 (Two-for-one manipulation; adopted from Example 1 in [Hosseini et al., 2022]). Consider an instance with five men and five women having the following preference profile.

The DA outcome on this (truthful) profile is underlined. One can check that woman w1 cannot benefit through either a self-manipulation or an accomplice manipulation by any man. However, if ≻′m1 := w1 ≻ w5 ≻ w3 ≻ w4 ≻ w2 and ≻′w1 := m3 ≻ m5 ≻ m1 ≻ m4 ≻ m2, then the resulting matching is as shown by ∗ ; here, w1 is matched with her most preferred man m3 while the accomplice man m1 continues to be matched to w3, thus incurring no regret.

As seen in the example, two-for-one manipulation is not merely the 'sum-of-its-parts'; more precisely, a woman can benefit more when both she and an accomplice man misreport, as compared to the case in which either only she or the accomplice man misreports. However, such manipulations do not share the stability preserving properties like accomplice and one-for-all manipulations. Moreover, it is unclear if there always exists an inconspicuous equivalent of an optimal two-for-one manipulation strategy. Nonetheless, Hosseini et al. [2022] provide a polynomial time algorithm for computing the optimal two-for-one manipulation strategy.

Open Problem 5. Do all optimal (or sub-optimal) two-sided manipulation strategies (e.g. two-for-one manipulation) have inconspicuous counterparts? And under what conditions are these two-sided strategies stability preserving?

Here, a manipulation is said to have an inconspicuous equivalent when each manipulator only changes the position of a single agent in its list.

3.3 ManipulationWith Externalities

One type of strategic manipulation may involve externalities wherein a (possibly external) agent wishes to manipulate the outcome by bribing agents or by controlling the matching instance.

When such an external agent is involved, one can explicitly define the manipulative actions and manipulation objectives. For instance, through a bribe, an external agent could ask an active agent to swap two adjacent preferences, or completely reorder the preferences. Towards control, the external agent could add or remove agents from participating in the market. These manipulative actions may be geared towards different objectives such as improving the matched partners of as many agents as possible, or ensuring that a desired pair of agents is always (or, never) matched. While some of these problems have polynomial-time algorithmic solutions, many of them are computationally intractable [Boehmer et al., 2021].

The bribery setting entails swapping and reordering preferences of active agents. On a technical level, it can be seen as a type of with-regret manipulations by active players [Hosseini et al., 2021]. The underlying assumption in Sections 3.1 and 3.2 was that a single or a coalition of manipulators never receive a matching that is worse than those under their truthful report. That is, the manipulation is a no-regret strategy. In contrast, a with-regret manipulation enables manipulators to receive side payments (aka bribery).

This formulation of bribery gives rise to several novel questions about both one-sided and two-sided manipulation, by allowing manipulators to incur regret.

Open Problem 6. What are the optimal with-regret manipulation strategies for different considerations of manipulators (A) and beneficiaries (B)? When are these manipulations stability preserving?

Allowing for regret increases the space of manipulation strategies; thus, raising new computational questions in computing optimal (or suboptimal) strategies. With-regret manipulations have been studied for the case of accomplice manipulation (A = {m}, B = {w}); here, the optimal strategies are shown to be inconspicuous but not stability preserving [Hosseini et al., 2021]. However, other combinations of manipulators A and beneficiaries B (i.e., men and women coalitions) remain unexplored.

Moreover, given a fixed budget-measured by external monetary compensation or the regret (e.g. drops in the matched partners)-one may investigate computational complexity of computing an optimal manipulation strategy. It turns out that every manipulation considered by Boehmer et al. [2021] is computationally intractable in the budgeted setting [Gupta and Jain, 2022].

4 Effect of Manipulations

Thus far, we argued that strategic manipulations may have a negative impact on the stability of outcomes in two-sided matching markets. In this section, we discuss additional effects of strategic behavior on i) fairness among the two sides and ii) incentivizing deviation from truthful reporting.

4.1 Manipulation for Good

Strategic manipulation of DA may result in improved matchings for women as beneficiary [Roth and Rothblum, 1999; Teo et al., 2001; Vaish and Garg, 2017; Shen et al., 2018;

Shen et al., 2021; Hosseini et al., 2021; Hosseini et al., 2022]. Recall that the DA algorithm always return a stable matching that is men-optimal and women-pessimal. This rather unfair treatment of the two sides may result in a significant welfare gap between men and women. One of the most prominent fairness notion is proposed by Gusfield and Irving [1989] that aims at finding a stable matching with the minimum welfare gap (aka sex-equality cost) among all stable solutions. Other fairness measures aim at minimizing the worst-off agent (aka regret-minimizing stable matchings) [Gusfield, 1987].

A careful review of Example 2 illustrates that the manipulation (marked by ∗ ) results in a matching that is superior compared to the truthful outcome with respect to fairness measures such as sex equality, regret, and total welfare. This raises the question of whether and how strategic manipulation can be used to improve fairness in matching markets.

Open Problem 7. Can strategic manipulation be used for social good, specifically, towards achieving fairness across the two sets of agents?

In this vein, strategic behavior can be formulated as manipulation with externalities with goals such as increasing fairness, by agents (either active participants or external agents) to obtain socially desirable outcomes while maintaining stability.

4.2 Manipulation Games

In strategic reporting, conflicts may arise among manipulators in the case of single-agent permutation manipulation. That is, while a woman benefits from manipulating her own preferences individually, uncoordinated simultaneous manipulation by multiple women can result in worse-off outcomes for all manipulators compared to the truth-telling outcome. 5

Example 4 (Conflict among manipulators; adopted from Table 1 in [Shen et al., 2021]). Consider the instance in Example 1. Both, women w1 and w2, can individually benefit by misreporting their own preferences. Specifically, if w1 misreports her preference as ≻′w1 := m3 ≻ m1 ≻ m2 ≻ m4, while the others truthfully report their preferences, she gets matched to m3 who is her most preferred man. Similarly, if w2 misreports her preferences as ≻′′w2 := m1 ≻ m3 ≻ m4 ≻ m2 while others (including w1) tell the truth, she is matched to her most preferred man m1 in the execution of DA. However, if both w1 and w2 simultaneously misreport their preferences, i.e., ≻′′′ := (≻′w1 ,≻′′w2 ,≻-{w1,w2}), then the resulting matching is {(m1, w1), (m2, w3), (m3, w2), (m4, w4)}. Here, both w1 and w2 end up worse-off compared to the truthful solution.

Given this example, the preference revelation problem of agents can be modeled as a non-cooperative game where the manipulators A are the players and their action space consists of all possible preference profiles they can submit.

Manipulation games have been extensively studied in the past in the context of one-sided manipulation (both, singleagent as well as coalitional). For the single-agent permutation manipulation game by women, not only does every Nash equilibrium result in a stable matching [Roth, 1984], but every Nash equilibrium profile can be characterized in the following way: for every stable matching which is supported by some preference profile, it is also attainable by a Nash equilibrium preference profile [Zhou, 1991]. This settles the question of the existence of a Nash equilibrium for this gamethe men-optimal stable matching is supported by the truthful preference profile. In the case where the manipulators are a subset of women, a strong Nash equilibrium always exists and the resulting matching is unique [Shen et al., 2018].

5 Under the manipulation by truncation strategy, all women can independently and simultaneously truncate their preferences without affecting other women.

Considering two-sided manipulations, understanding the existence of Nash equilibria, their characterization, and the properties of the resulting matching result in the following open questions.

Open Problem 8. For what sets of manipulators A and beneficiary B, does the preference revelation game have a Nash equilibrium? Do all Nash equilibria (when they exist) result in a stable matching?

Previous works have examined the manipulation game for the special case of self-manipulation (A = B), by individuals as well as coalitions [Alcalde, 1996; Ma, 1995; S¨onmez, 1997; Kalai et al., 1979]. However, manipulation games for two-sided strategies remain unexplored. In the special case when A,B contains every coalition of agents, the existence of a Nash equilibrium guarantees a strategy profile in which no manipulation by any individual or group of individuals is possible.

When the Nash equilibrium strategy profiles for these games do not result in stable outcomes, the relationship between stability loss and different Nash equilibria can be measured through the price of anarchy or the price of stability [Koutsoupias and Papadimitriou, 1999; Roughgarden and Tardos, 2007].

5 OvercomingManipulation

This section discusses the different efforts aimed at overcoming manipulability in two-sided stable matching problems.

5.1 MeasuringManipulability

Since all stable matching mechanisms are manipulable [Roth, 1982], one can measure the extent to which a mechanism is manipulable to compare the 'manipulability' of different matching mechanisms. For instance, a mechanism ϕ is said to be less manipulable than mechanism δ if the set of manipulating agents in δ Pareto dominates the set of manipulating individuals in ϕ [Pathak and S¨onmez, 2013; Chen et al., 2016]. Or, in a weaker version, one can say that ϕ is less manipulable than δ if it contains fewer number of manipulating agents [Bonkoungou and Nesterov, 2023].

However, neither the Pareto dominance condition, nor the weaker variant based on a comparison of the number of manipulating agents, consider the 'degree' by which a manipulation alters the resulting matching. Thus, we ask:

Open Problem 9. How can we compare the manipulability of different mechanisms based on the extent of change in the resulting matching outcome? Can we identify and characterize the set of least manipulable mechanisms?

Understanding the compatibility of the different comparison metrics, and the set of least manipulable mechanisms therein, is also an interesting avenue for future work.

5.2 Domain Restrictions

Inspired by the voting literature where it is well-known that strategy-proof voting rules exist when agents' preferences are single-peaked [Moulin, 1980], we ask:

Open Problem 10. Are there any preference domains under which the DA algorithm (or any other mechanism) is stable and strategyproof?

Instances consisting of (appropriate two-dimensional extensions of) single-peaked and single-crossing preferences have been shown to be strategyproof in the stable matchings setting [Salonen and Salonen, 2018]. Moreover, under the large market assumption, every individual has nearly the same utility across all stable matchings; thus, do not benefit much from manipulations [Kojima and Pathak, 2009; Roth and Peranson, 1999; Immorlica and Mahdian, 2005; Lee, 2016]. However, these classes of instances are clearly not exhaustive.

5.3 Computational Intractability

While manipulation strategies of the DA mechanism can be found in polynomial time (see Sections 3.1 and 3.2), are there other stable matching mechanisms which are computationally difficult to manipulate? Using Single Transferable Votes (STV) mechanisms from the voting literature (which is known to be NP-hard to manipulate [Bartholdi III and Orlin, 1991]), one can engineer stable matching mechanisms in which it is NP-complete to determine whether an agent can manipulate its preference for its own benefit [Pini et al., 2009]. This mechanism also possesses a fairness property called gender-neutrality 6 , echoing our discussion in Section 4.1. At the same time, some preference profiles are 'universally manipulable', i.e., for these matching instances, all stable matching mechanisms (not just DA) are computationally easy to manipulate by a a single agent [Pini et al., 2009].

While NP-hardness is a worst-case guarantee, (i.e., if P ̸= NP, every manipulation algorithm has some families of instances on which it does not scale polynomially), the universal manipulability of certain instances tells us that there does not exist a mechanism which is universally difficult to manipulate. However, the average-case computational guarantee of stable matching mechanisms remains unexplored.

Open Problem 11. Can we construct stable matching mechanisms which are difficult to manipulate on average?

5.4 Approximations

While it might not be possible to exactly satisfy stability and strategy-proofness simultaneously, one can ask:

Open Problem 12. What are the best approximations of stability and strategy-proofness which can be simultaneously satisfied?

6 A property of the mechanism wherein swapping the roles of the men and women results in the same outcome matching.

Toward this, one may want exact stability along with some relaxation of strategy-proofness such as non-obvious manipulations [Troyan and Morrill, 2020], Bayesian incentive compatibility [Aziz, 2019; Hartline et al., 2011], or strategyproofness in the large markets [Azevedo and Budish, 2019].

On the other hand, other approximations of stability, such as X-stability [Hosseini et al., 2021], could allow for a set of X agents to be part of a blocking pair. The objective is then to find matching mechanisms that guarantee strategy-proofness, similar to the well-studied random serial dictatorship mechanism [Abdulkadiro˘glu and S¨onmez, 1998] while simultaneously providing approximate stability guarantees.

Such an analysis of approximate versions of stability and strategy-proofness would help our understanding of the tradeoffs and the frontiers of stability and strategy-proofness. For example, a recent study showed that a random matching mechanism derived from a deep learning model outperforms the baseline formed by convex combinations of the DA algorithm (which is stable, but not strategy-proof), the TopTrading Cycle mechanism [Shapley and Scarf, 1974] (which is neither stable, nor strategy proof), and the random serial dictatorship mechanism (which is strategy-proof, but not stable) [Ravindranath et al., 2021].

5.5 Experimental Evidence

Despite the theoretical incompatibility of strategy-proofness and stability [Roth, 1984], it has been observed through simulations that only 5.1% of women improve their match by misreporting preferences [Teo et al., 2001], and that, in reality, individuals primarily report their preferences truthfully [Guillen and Veszteg, 2021]. For truncation manipulations, it was conjectured (and later theoretically proven [Immorlica and Mahdian, 2005]) that the premise of this experimental observation lay in the large size of the market [Roth and Peranson, 1999]. For a detailed survey on the experimental evidence of manipulation strategies in matching markets, please refer to Hakimov and K¨ubler [2019].

6 Conclusion

In this paper, we review the literature on the strategic aspects of stable matching markets. After discussing the different types of manipulations and their effects on the outcome, we mention ways in which we can overcome such manipulative behavior. In the process, we highlight a series of plausible future directions. This survey (and the literature on manipulation in stable matchings so far) primarily focuses on the DA algorithm. 7 Thus, an important future direction is understanding the different types and effects of strategic behavior in other matching algorithms.

Acknowledgments

The authors acknowledge support from NSF IIS grants #2144413 (CAREER) and #2107173. We thank the anonymous reviewers for their helpful comments.

7 Notable exceptions include Roth and Vate; Roth and Vate [1990; 1991].