Two-Sided Matching over Social Networks

1 Introduction

Mechanism design for two-sided matching, also known as the stable marriage or the school choice [Abdulkadiro˘glu and S¨onmez, 2003], has been a fundamental research over the last few decades in both theoretical economics and multiagent systems. In particular, designing strategy-proof mechanisms for two-sided matching, which incentivize one side of the agents, say students, to truthfully report their preferences on the other side, say colleges, has attracted much attention. There are two prominent strategy-proof mechanisms: Deferred-Acceptance (DA) by Gale and Shapley (1962), and Top-Trading-Cycles (TTC) by Shapley and Scarf (1974).

In practice, a mechanism designer, which we also call a moderator, struggles to completely observe the set of students who are willing to participate in the matching program and advertise it to them directly a priori. Instead, students will usually get the information about a matching program from their peers/friends, through their shared social networks. From this perspective, it is important to incentivize students to diffuse such information as much as possible to their colleagues. Such a new paradigm of mechanism design is called mechanism design over social networks, initiated by Li et al. (2017) in the field of artificial intelligence. However, in the literature of two-sided matching, virtually no work has focused on mechanism design over social networks.

One motivating example of two-sided matching over social network is a food bank, i.e., matching between people in need and food companies, restaurants, grocery stores, etc. The goal is reducing food loss and helping people in need. People in need are often information poor. Thus, advertising the service of the food bank via websites and social media is not sufficient. To diffuse information to people in need, utilizing the social network (in the real world) among them would be useful. However, we need to give them incentives to diffuse information; otherwise people would not intend to decrease their share by inviting others.

As the first step of mechanism design over social networks for two-sided matching, this paper investigates the existence of mechanisms that satisfy several desiderata. We take into account 13 properties, which are classified into four criteria: incentives, efficiency, stability, and fairness. Their relationship is summarized in Fig. 1. Based on the revelation principle, we can focus on direct revelation mechanisms that satisfy strategy-proofness (SP) without loss of generality, as long as we are interested in mechanisms with dominant-strategy equilibria. Also, from the perspective of achieving some sort of stability, we believe that a property called the mutuallybest for direct-children (MB-D), which just requires that a student who is directly connected to the moderator must be matched to her most preferred college as long as they most like each other, is a minimal requirement that desirable mechanisms should satisfy.

In this paper we propose three mechanisms: the one-shot college-offering (OSCO) mechanism, the sequential DA (SeqDA) mechanism, and the sequential TTC (SeqTTC) mechanism. Although all three mechanisms satisfy SP, each mechanism also satisfies a different combination of other properties; Table 1 summarizes the satisfied properties. We further show that no mechanism dominates these mechanisms, i.e., given four criteria and 13 properties, our mechanisms are in the Pareto frontier. More specifically, for each proposed mechanism and each satisfied property, a one-level stronger property is not achievable by any mechanism when we require the other properties.

Let us briefly explain each mechanism in a bit more detail. While both the sequential DA and the sequential TTC are defined based on the well-known DA and TTC, the one-shot CO

is defined from scratch. In the one-shot CO, each college first sends invitations to as many students as possible based on a certain rule, and then each student, if she receives at least one invitation, chooses the most preferred college to enter. From the students' perspective, the one-shot CO has the "take-itor-leave-it" feature; just choosing the most preferred college among those who sent her invitations is the best option. Also, for each student, whether she receives an invitation from a college does not depend on her own preference as long as she assumes the college acceptable. Furthermore, having fewer neighbors never increases the invitations she receives. As a result, the one-shot CO is SP.

2 Literature Review

Li et al. (2017) considered mechanism design over social networks for single-item auctions and proposed a strategy-proof mechanism based on the idea of diffusion critical trees. Several works in artificial intelligence and multi-agent systems then investigated strategy-proof resource allocation mechanisms with monetary compensations, e.g., multi-unit auctions and redistributions [Zhao et al., 2018; Kawasaki et al., 2020; Li et al., 2020; Zhang et al., 2020]. On the other hand, there is limited research on resource allocation without money from the perspective of mechanism design over social networks. Recently, Kawasaki et al. (2021) and You et al. (2022) considered mechanism design over social networks for house allocation problems, which do not allow monetary compensations. However, neither papers addressed fairness or stability in resource allocations.

Gale and Shapley (1962) initiated the research of two-sided matching and proposed the seminal Deferred-Acceptance algorithm. Crawford (1991) studied the effect of having more students/colleges in the two-sided matching. While in their model the set of students may increase as a result of exogenous events, in our model it is due to the strategic actions of students. Toda (2006) proposed the concept of mutually-best as a relaxation of stability. Takagi and Serizawa (2010) called the same property pairwise unanimity. Two-sided matching has recently gained momentum in both artificial intelligence and theoretical computer science, where many papers have studied various kinds of two-sided matching problems, including school choice with diversity constraints [Aziz and Sun, 2021; Hamada et al., 2017; Kurata et al., 2017], matchings with budget constraints [Aziz et al., 2020; Ismaili et al., 2019], matchings with various distributional constraints [Fragiadakis et al., 2016; Goto et al., 2016; Kojima et al., 2018; Goto et al., 2017], uncertain preferences [Rastegari et al., 2013; Todo et al., 2021], and the efficient computation of stable matchings with similar agents [Meeks and Rastegari, 2020].

Todo and Conitzer (2013) also studied the variable populations in two-sided matching literature. In their model, a student may invite more students (or add fake accounts) to improve her own assignment, and the authors studied falsename-proof mechanisms, in which no student has an incentive to invite more students. This concept is totally opposite to our objective: strategy-proofness in our model (and in the literature on mechanism design over social network [Li et al., 2017]) requires that each agent has an incentive to invite as many followers as possible.

3 Model

In our model of two-sided matching over social networks, there are two sets of agents, students and colleges. Let C = {c1, c2, . . . , c|C|} be the set of colleges, and let S = {s1, s2, . . . , s|S|} be the set of students. We usually use c ∈ C and s ∈ S to represent a college and a student without specifying identifiers. The symbol ∅ denotes an "unmatched" status (for students) and "keep the seat empty" status (for colleges). Furthermore, special agent o, called moderator, corresponds to a mechanism itself or a trusted third party.

Each college c has a priority ≻c, given as a strict ordering over S ∪{∅}, which specifies the result of a one-to-one comparison over students. In this paper we do not specify how colleges compare two subsets of students. Let ≻C= (≻c)c∈C represent a profile of the priorities of colleges C. Each college c has its maximum quota qc ∈ Z>0, indicating the number of students that college c can accept. Let qC := (qc)c∈C.

Each student s has a preference ≻s, given as a strict ordering over C ∪ {∅}. Notation c ≻s c′ indicates that student s strictly prefers being assigned to college c instead of college c′ . Analogously, c ≻s ∅ indicates that student s strictly prefers being assigned to college c to being unmatched. Symbol ≿s indicates the "weak preference" associated with ≻s; since we focus on strict preferences in this paper, c ≿s c′ indicates that either c ≻s c′ or c = c′ . Let ≻S= (≻s)s∈S represent a preference profile of students S.

Students are distributed over a social network. Let ro ⊆ S be the set of the neighbors of o, which are also called the direct children of o. For each s, let rs ⊆ S \ {s} denote s's neighbors. The neighborhood relation is asymmetric, i.e., s′ ∈ rs does not imply s ∈ rs′ . Given rS := (rs)s∈S and ro, all the neighborhood relations are defined, specifying social network G(rS, ro) among students and the moderator.

Matching m specifies to which college each student is assigned. Given matching m, let m(s) ∈ C ∪ {∅} denote the college (if any) to which student s is assigned, and m(c) ⊆ S indicates the set of students (if any) with which college c is matched. We abuse ≻s and write m ≻s m′ (or m ≿s m′ ) instead of m(s) ≻s m′ (s) (or m(s) ≿s m′ (s)).

Next we give some additional notations to formalize our model as a mechanism design problem. Let θs = (≻s, rs) denote the true type of student s, and let θ = (θs)s∈S denote a profile of the students' true types. Let θ-s denote a profile of the types owned by the students except s. Analogously, given subset (also called as a coalition) T ⊆ S, let θT denote a profile of the types owned by T, and letθ-T denote a profile of the types owned by the students except T. Let R(θs) = {θ′s = (≻′s , r′s ) | r′s ⊆ rs} denote the set of reportable types by s with true type θs, assuming that each s cannot pretend to be connected to any student to whom s is not really connected. When s reports r′s as her neighbors, we say s diffuses the information toward r′s , or s invites r′s . Let θ′ = (θ′s )s∈S ∈ ×s∈SR(θs) = R(θ) denote a reportable type profile. Analogously, given subset T ⊆ S, let θ′T denote a profile of the types reported by T, and θ′-T a profile of the types reported by the students except T .

Given type profile θ′ , let ˆ S(θ′ ) ⊆ S denote the set of connected students to whom a path exists from o in G(r′S , ro). Given θ′ , let M(θ′ ) denote a set of feasible matchings m satisfying the followings: (i) consistency; for any s ∈ ˆ S(θ′ ) and any c ∈ C, m(s) = c if and only if s ∈ m(c), (ii) maximum quota constraint; |m(c)| ≤ qc for any c ∈ C, and (iii) connectivity; s ̸∈ ˆ S(θ′ ) implies m(s) = ∅ for any s ∈ S. Given true type profile θ (which is not observable), mechanism µ maps each reported profile θ′ ∈ R(θ) into feasible matching m ∈ M(θ′ ), while µ can use ≻C, qC, and ro as parameters.

We further define some terms related to social networks, as well as a useful concept called the diffusion critical tree (DCT). Given θ′ and s ∈ ˆ S(θ′ ), let ds(θ′ ) ∈ Z be the distance (the number of edges in the shortest path) from o to s in G(r′S , ro). For any s ̸∈ ˆ S(θ′ ), let ds(θ′ ) = ∞. Given θ′ , let τ(θ′ ) be the diffusion critical tree (DCT), defined in the following procedure. Given θ′ , student t ∈ ˆ S(θ′ ) is a critical parent of student s ∈ ˆ S(θ′ ) if s becomes disconnected when t does not forward the information at all. If s remains connected regardless of any other student's action, we assume o is the only critical parent of s. When t is a critical parent of s, we call s a critical child of t. When multiple critical parents of s exist, we call the critical parent closest to s her least critical parent. Then, a diffusion critical tree τ(θ′ ) is constructed such that o is the root, and for each student, her least critical parent becomes her (direct) parent. Let πs(θ′ ) denote the set of critical parents of s, and let γs(θ′ ) denote the set of critical children of s. Let δo(θ′ ) be the set of directly-connected critical children of o in τ(θ′ ). By definition, ro ⊆ δo(θ′ ).

We then define 13 desirable properties, classified into four criteria. Sometimes we interchangeably use the properties of matchings and mechanisms. Mechanism µ is said to satisfy a certain property if, for any input θ′ , its output µ(θ′ ) satisfies the same property under θ′ .

Definition 1 (Incentive Properties). Given mechanism µ, any coalition T ⊆ S with true types θT , any θ′-T ∈ R(θ-T ), and any joint deviation θ′T ∈ R(θT ), let m = µ(θT , θ′-T ) and m′ = µ(θ′T , θ′-T ). Mechanism µ is (i) weakly manipulable by coalition T ⊆ S if m ≿s m′ for any s ∈ T and m ≻t m′ for some t ∈ T, (ii) strongly manipulable by T if m ≻s m′ for any s ∈ T, and (iii) manipulable by a singleton if it is strongly manipulable by T s.t. |T| = 1. Mechanism µ satisfies strong group-strategy-proofness (S-GSP), weak groupstrategy-proofness (W-GSP), or strategy-proofness (SP) if it is not weakly manipulable by any coalition, not strongly manipulable by any coalition, or not manipulable by any singleton, respectively.

Clearly, S-GSP implies W-GSP, and W-GSP implies SP.

Proposition 1. Mechanism µ satisfies SP if and only if both m ≿s m′ and m ≿s m′′ hold, where, for arbitrarily given s, θ-s, θ′-s ∈ R(θ-s), θs = (≻s, rs), ≻′s , and r′s ⊆ rs, let m = µ(θs, θ′-s ), m′ = µ((≻′s , rs), θ′-s ), and m′′ = µ((≻s, r′s ), θ′-s ).

In other words, to show that mechanism µ satisfies SP, it suffices to separately show that each student cannot benefit from (i) misreporting her preference and (ii) not inviting any subset of her neighbors. Since the proof directly follows Thm. 4.1 of Kawasaki et al. (2021), it is omitted due to space limitations.

Definition 2 (Fairness Properties). For student s and college c, assume c ≻s m(s). Then, s has (i) justified envy with respect to priority toward student s′ ∈ m(c) if s ≻c s′ holds, (ii) justified envy with respect to network toward s′ ∈ m(c) if both s ≻c s′ and s′ ̸∈ πs(θ′ ) hold, and (iii) justified envy with respect to distance toward s′ ∈ m(c) if both s ≻c s′ and ds′ (θ′ ) ≥ ds(θ′ ) hold. Matching m is fair (FR), fair with respect to network (FRN), or fair with respect to distance (FRD) for given θ′ if, there exists no student with justified envy with respect to priority, justified envy with respect to network, or justified envy with respect to distance, respectively.

Clearly, FR implies FRN, and FRN implies FRD. Intuitively, FR requires that all students must be treated equally, i.e., if two students compete for a seat of college c, its resolution must be solely based on c's priority ≻c. However, FR is too demanding, since in our model, a critical parent has absolute power over her critical children. FRN allows a mechanism to override ≻c among critical parents/children. FRD further compromises that a mechanism can favor students closer to the moderator in the original network.

Definition 3 (Efficiency Properties). Given θ′ , matching m is Pareto efficient (PE) if, for any other feasible matching m′ , the existence of s ∈ ˆ S(θ′ ) s.t. m′ ≻s m implies the existence of another t ∈ ˆ S(θ′ ) s.t. m ≻t m′ . Student s claims an empty seat of college c if both c ≻s m(s) and |m(c)| < qc hold, and strongly claims an empty seat of c if both c ≻s m(s) = ∅ and |m(c)| = 0 hold. A matching is non-wasteful (NW) or weakly non-wasteful (WNW) for given θ′ if, for any college c, no student claims an empty seat or no student strongly claims an empty seat, respectively.

Clearly, PE implies NW, and NW implies WNW. WNW means that a student can (strongly) claim an empty seat of college c only when she is not assigned to any college and no student is assigned to c. This property can be considered as a minimum requirement for efficiency, although our some impossibility theorems show it can be incompatible with other properties.

Definition 4 (Stability Properties). We say matching m is stable for given θ′ if it is fair and non-wasteful. Given θ′ , we say a pair of student s and college c is a mutually-best pair (MBpair) if c ≻s c′ for any c′ ̸= c and s ≻c s′ for any s′ ∈ ˆ S(θ′ ). Matching m is mutually-best (MB), mutually-best for critical children (MB-C), or mutually-best for direct children (MBD) if any MB-pair (s, c) is matched as long as s ∈ ˆ S(θ′ ), s ∈ δo(θ′ ), or s ∈ ro, respectively.

Clearly, stability implies MB, MB implies MB-C, and MBC implies MB-D. MB means that a MB-pair is guaranteed to be matched. In our model, a directly-connected critical child of the moderator is robust against the manipulation by another student; she cannot be disconnected by any manipulation of a singleton. Also, a direct neighbor of the moderator in the original network is robust against any group manipulation; she cannot be disconnected by any joint deviation. MB-C and MB-D mean that a MB-pair is guaranteed to be matched only for such students, who are less susceptible to manipulations.

4 Impossibility Results

This section presents seven impossibility results, each of which shows the incompatibility of different combinations of the properties in our model.

Theorem 1. There is no mechanism that simultaneously satisfies PE and FRD.

Proof. Assume there are three students, s1, s2, s3, and three colleges, c1, c2, c3, where the preferences/priorities are given:

c1 : s3 ≻ s1 ≻ s2 s1 : c1 ≻ c2 ≻ c3 c2 : s3 ≻ s1 ≻ s2 s2 : c1 ≻ c3 ≻ c2 c3 : s2 ≻ s3 ≻ s1 s3 : c3 ≻ c1 ≻ c2.

We also assume that ro = {s1, s2, s3} and qc1 = qc2 = qc3 = 1, i.e., all students are directly connected to the moderator and each college accepts at most one student.

PE implies NW. Since all students prefer all colleges over ∅, all students must be assigned to some college. Then the only fair and NW matching m is such that m(s1) = c2, m(s2) = c3, and m(s3) = c1. However, this matching is Pareto-dominated by another matching m′ such that m′ (s1) = c2, m′ (s2) = c1, and m′ (s3) = c3.

Theorem 2. There is no mechanism that simultaneously satisfies SP and MB.

Proof. Consider the social network shown in Fig. 2a, with two students, s1 and s2, both of whom have preference c ≻ ∅. There is college c with priority s2 ≻ s1 ≻ ∅. From MB, s2 must be assigned to c. However, s1 is assigned to c by not inviting s2 (which is guaranteed by MB for the case without s2). This violates SP.

Theorem 3. There is no mechanism that simultaneously satisfies SP, FR, and MB-D.

Proof. Consider again the social network shown in Fig. 2a. There are two students, s1 and s2, and college c, where s2 ≻c s1 ≻c ∅, qc = 1, and c ≻s ∅ for both students s. From SP, s1 must be matched to c; otherwise, s1 has an incentive not to invite s2, which guarantees the assignment of s1 to c from MB-D. However, s2 has justified envy with respect to priority toward s1, which violates FR.

Theorem 4. There is no mechanism that simultaneously satisfies SP, FRN, and WNW.

Proof. Assume three students, s1, s2, and s3, and two colleges, c1 and c2, where qc1 = qc2 = 1, the social network is given in Fig. 2b, s3 ≻ s1 ≻ s2 for any college, and c1 ≻ c2 for any student. FromWNW, two students must be matched to some colleges. Thus, only three cases are possible: (i) s1 is unmatched, (ii) s2 is unmatched, and (iii) s3 is unmatched.

In case (i), s1 has justified envy with respect to network toward s2, violating FRN. In case (ii), s2 has an incentive not to invite s3, violating SP. In case (iii), s3 has justified envy with respect to network toward s1, violating FRN.

Theorem 5. There is no mechanism that simultaneously satisfies W-GSP, FRN, and MB-D.

Proof. Consider the network given in Fig. 2c. There are four students, s1, s2, s3, and s4, and two colleges, c1 and c2, where qc1 = qc2 = 1 and preferences/priorities are given:

Assume that a mechanism satisfies W-GSP, FRN, and MB-D. When s1 and s2 jointly manipulate and remove both s3 and s4, s1 is matched to c2 and s2 is matched to c1 fromMB-D. To guarantee W-GSP, the same assignment must hold for at least one of s1 and s2, when both s3 and s4 are connected. WLOG, assume that s1 is matched with c2 when both s3 and s4 are connected. Then student s4 has justified envy with respect to network toward s1, violating FRN.

Theorem 6. There is no mechanism that simultaneously satisfies S-GSP, MB-D, and WNW.

Proof. Consider the network given in Fig. 2d. There are three students, s1, s2, and s3, and two colleges, c1 and c2, where qc1 = qc2 = 1 and preferences/priorities are given:

FromMB-D, s1 is matched to c1. FromWNW, either s2 or s3 must be matched to c2. Assume s2 is matched to c2. Then, if s1 removes s2, then s3 is matched to c2, while the assignment of s1 does not change, violating S-GSP. The same argument holds if s3 is matched to c2; then s1 and s2 can collude.

Theorem 7. There is no mechanism that simultaneously satisfies W-GSP and MB-C.

Proof. There are four students, s1, s2, s3, and s4, and two colleges, c1 and c2, where qc1 = qc2 = 1, the network given in Fig. 2e, and the preferences/priorities are given:

When both s1 and s2 act truthfully, it holds that δo(θ′ ) = S. Then, from MB-C, s3 is matched to c1, and s4 is matched to c2. If neither s1 nor s2 invite both s3 and s4, they are disconnected. Then, from MB-C, s1 is matched to c1, and s2 is matched to c2, under which their assignments strictly improve, violating W-GSP.

These impossibility results illustrate a sharp trade-off between efficiency and fairness. Assuming that both SP and MB-D are required, FR is not achievable (Thm. 3). Also, FRN is incompatible with the weakest efficiency property WNW (Thm. 4) under the assumption of SP. Furthermore, PE is incompatible with the weakest fairness property FRD (Thm. 1), even without any incentive constraint.

Note that all the impossibility results are tight, according to the 13 properties. That is, by weakening one property with identically keeping the others, we can find a mechanism that satisfies all of them. For Thm 1, SeqTTC achieves PE, and SeqDA achieves NW and FRD. For Thm 2, OSCO achieves SP and MB-C, and the original TTC achieves MB (but not SP). For Thm 3, the no-assignment mechanism achieves SP (and even S-GSP) and FR, OSCO achieves SP (and even W-GSP), FRN, and MB-D (and even MB-C), and the original DA achieves FR and MB-D (and even MB). For Thm 4, OSCO achieves SP and FRN, SeqDA achieves SP (and even W-GSP), FRD, and WNW (and even NW), and the original DA achieves FRN (and even FR) and WNW (and even NW). For Thm 5, the no-assignment mechanism achieves W-GSP (and even S-GSP) and FRN (and even FR), SeqDA achieves W-GSP, FRD, and MB-D, and OSCO achieves SP, FRN, and MB-D (and even MB-C). For Thm 6, the original TTC that is only applied for ro achieves S-GSP and MB-D, the distancebased serial dictatorship satisfies S-GSP and WNW (and even PE), and SeqDA achieves MB-D and WNW (and even NW). Finally, for Thm 7, SeqDA achieves W-GSP and MB-D, and OSCO achieves SP and MB-C.

5 ProposedMechanisms

This section presents our three mechanisms, as well as their properties and the reasons why they are in the Pareto frontier. Combined with the impossibility results, the existence of these mechanisms comprehensively shows what can/cannot be achieved in two-sided matching over social networks.

5.1 One-Shot College-OfferingMechanism

This subsection presents our first positive result: the compatibility among SP, MB-C, and FRN. The proposed mechanism, called one-shot college-offering (OSCO), was developed from scratch, i.e., not based on DA or TTC. Instead, OSCO has a well-known "take-it-or-leave-it" feature; colleges first send offers to a certain set of students, and then each student accepts the best offer she receives. By carefully designing the rule for colleges to send the offers, we guarantee SP.

We begin with some additional concepts and key properties on them, which helps the analysis of OSCO.

Definition 5 (Interested/attacking/safe student). Given θ′ and college c with priority ≻c, we say student s is interested in c if c ≻s ∅ holds. We say student s who is interested in c attacks student s′ ̸= s regarding c if the followings hold:

1. s ≻c s′ , and
2. s and s′ are in different branches in DCT τ(θ′ ), i.e., there is no critical parent/child relation between them. Formally, s′ ̸∈ πs(θ′ ) ∪ γs(θ′ ).

We say s is safe regarding c if s is interested in c and no student attacks s regarding c.

Proposition 2. If multiple safe students exist regarding college c, they lie on a single path from moderator o in τ(θ′ ).

Proof. By way of contradiction, assume there exists two safe students, s and s′ , in different branches in DCT. However, since priority ≻c is strict, either s attacks s′ or s′ attacks s. This contradicts our assumption that both are safe.

Proposition 3. If student s does not invite her neighbor s′ , the possible effect of this manipulation (if any) toward another student ˆ s (possibly different from s′ ) is one of the following cases. Here, τ denotes the original DCT, and τ ′ denotes the DCT after the manipulation.

Case (i): In τ, ˆ s is a critical child of s. In τ ′ , ˆ s becomes disconnected; see the case given in Fig. 3a.

Case (ii): In τ, ˆ s is a critical child of s. In τ ′ , the least critical parent of ˆ s changes, but ˆ s remains a critical child of s; see Fig. 3b.

Case (iii): In τ, ˆ s is a critical child of s∗ (possibly s∗ = o), where s∗ is the closest common critical parent of ˆ s and s. In τ ′ , the least critical parent of ˆ s changes, but ˆ s remains a critical child of s∗ and in a branch that is different from the path from s∗ to s; see Fig. 3c.

Proof. Since student ˆ s is affected by the manipulation of s, there must be an acyclic path from moderator o to ˆ s, which goes through s and s′ in the original graph.

We first show that ˆ s cannot be a critical parent of s in τ . By way of contradiction, assume ˆ s is a critical parent of s in τ. Then, all paths from o to s go through ˆ s in the original graph. Then, no acyclic path exists from o to ˆ s, which goes through s and s′ . This is a contradiction.

Then, in τ, ˆ s can be either (1) her critical child, or (2) a student in a different branch.

For (1), if all paths from o to ˆ s go through s′ in the original social network (Fig. 3a), ˆ s will be disconnected, corresponding to case (i). If there exists a path from o to ˆ s that does not go through s′ (Fig. 3b), ˆ s is still connected and remains a critical child of s, corresponding to case (ii).

For (2), let A′ denote the students between s∗ and s on the path from s∗ to s in τ. By the manipulation, any path that goes through s and s′ in the original social network is removed. As a result, some student can become a new critical parent of ˆ s. We show that a new critical parent cannot be in A′ . By way of contradiction, assume s′′ ∈ A′ is a new critical parent of ˆ s. Then, all paths from o to ˆ s after the manipulation must go through s′′ . Also, all the removed paths go through s′′ in the original social network. Thus, s′′ must be a critical parent of ˆ s before the manipulation. This contradicts our assumption that s′′ is a new critical parent. Thus, ˆ s remains a critical child of s∗ and in a branch different from the path from s∗ to s in τ ′ , corresponding to case (iii).

Definition 6 (One-shot College-Offering (OSCO)). In Step 1, each college c chooses at most qc safe students regarding c (if more than qc safe students exist, the students closer to the moderator are chosen), and makes an offer to them. In Step 2, each student accepts her most preferred offer among those she received (if she receives no offer, she is unmatched).

Theorem 8. OSCO satisfies SP, FRN, and MB-C.

Proof. For FRN, if student s receives an offer from college c, then, regardless of whether she accepts/rejects, she never has envy regarding c. Thus, the only possibility that s has envy toward another student s′ regarding c is when s does not get an offer while s′ receives an offered from c. In such a case, at least one of the followings holds (because s′ is safe): (a) s′ is a critical parent of s, (b) s′ ≻c s, or (c) s is not interested in c. Thus, no student has justified envy with respect to network.

For SP, it is clear that no student s has an incentive to misreport her preference. In Step 1, her preference is used only to exclude her from the procedure that determines which students receive an offer from college c, in which she is not interested. In Step 2, she can choose her most preferred offer.

Thus, we examine that student s never has an incentive not to invite her neighbor s′ . By way of contradiction, assume s has an incentive to manipulate, i.e., s does not receive an offer from college c (s.t. she is interested) before the manipulation, while she does get an offer after the manipulation. First, assume s is safe but not chosen before the manipulation. However, as Prop. 3 shows, a student cannot affect her critical parents. Thus, she cannot get an offer after the manipulation. Second, assume s is not safe before the manipulation, while she becomes safe after the manipulation. From the fact that s is not safe, there exists another student ˆ s who is attacking s before the manipulation. Since s becomes safe after the manipulation, either ˆ s becomes disconnected or changes her position such that she cannot attack s. However, by Prop. 3, if ˆ s becomes disconnected (case (i)), she is a critical child of s. Thus, she cannot attack s before the manipulation. Also, if ˆ s changes her position, either case (ii) or case (iii) in Prop. 3 holds. In case (ii), ˆ s is a critical child of s; she cannot attack s before the manipulation. In case (iii), ˆ s is a critical child of s∗ , and she is in a branch that is different from the path from s∗ to s before/after the manipulation. Thus, she still attacks s after the manipulation. These situations contradict our assumption that s is not safe before the manipulation while she becomes safe after the manipulation.

For MB-C, assume MB-pair (s, c) exists s.t. s ∈ δo(θ′ ). Clearly s is interested in c. Also, since s ≻c s′ for any s′ ∈ ˆ S(θ′ ) \ {s}, s is not attacked by any student. Thus, s is safe and gets an offer from c since she is closest to o in τ(θ′ ). Moreover, s will accepts it. Thus, (s, c) will be matched.

Let us show that the OSCO is in the Pareto frontier. Given FRN and MB-C, an incentive property cannot be improved from SP to W-GSP due to Thm. 7. Given SP and MB-C, a fairness property cannot be improved from FRN to FR due to Thm. 3. Given SP and FRN, a stability property cannot be improved from MB-C to MB due to Thm. 2. Finally, given SP, FRN, and MB-C, WNW cannot be achieved as an efficiency property due to Thm. 4.

5.2 Sequential DA and Sequential TTC

Sequential DA (SeqDA) applies the standard DA sequentially, where DA repeats the following procedure. Each student applies to her most preferred college from which she has not been rejected. Each college deferred-accepts applicants up to its maximum quota, and the rest are rejected. Then, the rejected students apply to their second-best college, and so on.

Definition 7 (Sequential DA (SeqDA)). Given θ′ , the Sequential DA runs in the following steps. In Step 1, apply DA to all the colleges and students s such that ds(θ′ ) = 1, and update maximum quotas. In Step k (≥ 2), apply DA to the remaining colleges and students s such that ds(θ′ ) = k, and update the maximum quotas. The sequential DA terminates when all the students joined a DA market.

Theorem 9. SeqDA satisfies W-GSP, FRD, NW, and MB-D.

Proof. It is clear that a student cannot help any student in the previous steps. Thus, no profitable coalition exists that consists of students joining in different steps. Also, since DA satisfies W-GSP in the standard model, no joint deviation exists for students in the same step. Thus, W-GSP holds.

For FRD, from the FR of DA, no justified envy exists in each step. Assume student s is rejected from college c. Then, c has already reached its maximum quota qc in the step that s joined. Thus, no student can be assigned to c in any later steps; s never envies students who joined in later steps.

For NW, if c ≻s m(s) holds, s must apply to c and be rejected. Student s is only rejected by college c when the total number of already assigned students in previous steps and the currently applying students exceeds qc. Thus, |m(c)| = qc.

For MB-D, consider direct child s of o, who joins in the first step. If (s, c) is an MB-pair, she applies to c and is never rejected since s is in the top of ≻c. So (s, c) is matched.

SeqDA is in the Pareto frontier. Given FRD, NW and MBD, an incentive property cannot be improved fromW-GSP to S-GSP due to Thm. 6. Given W-GSP, NW, and MB-D, a fairness property cannot be improved from FRD to FRN due to Thm. 5. Given W-GSP, NW, and FRD, a stability property cannot be improved from MB-D to MB-C due to Thm. 7. Finally, given W-GSP, FRD, and MB-D, an efficiency property cannot be improved from NW to PE due to Thm. 1.

Sequential TTC (SeqTTC) applies the standard TTC sequentially, where TTC repeats the following procedure. Each student points to her most preferred (remaining) college, and each college points to the (remaining) student with the highest priority. At least one cycle always exists. Each student in a cycle is matched to the college to which she points and leaves the market.

Definition 8 (Sequential TTC (SeqTTC)). Given θ′ , the Sequential TTC runs in the following steps. In Step 1, apply TTC to all the colleges and students s such that ds(θ′ ) = 1, and update the maximum quotas. In Step k (≥ 2), apply TTC to the remaining colleges and students s such that ds(θ′ ) = k, and update the maximum quotas. The sequential TTC terminates when all the students joined a TTC market.

Theorem 10. SeqTTC satisfies W-GSP, PE, and MB-D.

Proof. Clearly, a student cannot help others in the previous steps. Thus, no profitable coalition consists of students in different steps. Also, from the S-GSP of TTC, each step is not weakly manipulable by coalitions. W-GSP thus holds.

For PE, all the students assigned at the first round of TTC in Step 1 are assigned to their first-best colleges. All the students who were assigned at the second round in Step 1, if any, are assigned to their most-preferred colleges among the remaining ones. The same argument holds for later rounds of TTC and later steps, suggesting that, to improve a student's assignment, another previously-assigned student must get worse, which coincides with the definition of PE.

Finally, MB-D only cares about the students who are directly connected to o, all of whom are assigned in Step 1 of SeqTTC. In each step, the standard TTC runs, which matches any MB-pair if any. So MB-D holds.

SeqTTC is also in the Pareto frontier. Given PE and MBD, an incentive property cannot be improved fromW-GSP to S-GSP due to Thm. 6. Given W-GSP, PE, and MB-D, even the weakest fairness property FRD cannot be achieved due to Thm. 1. Given W-GSP and PE, a stability property cannot be improved from MB-D to MB-C due to Thm. 7. Finally, the efficiency property cannot be improved anymore since the best efficiency property PE is already achieved.

Both SeqDA and SeqTTC exploit the distance in the original social network and sequentially apply the known SP mechanisms. We strongly believe that this is the only way to achieve SP based on those mechanisms in our model. Obviously, applying them directly to all the participating students violates SP. In the case given in Fig. 2a, s1 would make s2 disconnected if colleges preferred s2 to s1. Using the distance in DCT τ does not work either. In Fig. 2e, s1 would remove s3 and/or s4 from Step 1; while they remain connected through s2, they join in Step 2.

6 Conclusions

In this paper we investigated the existence of desirable mechanisms for two-sided matching over social networks. To the best of our knowledge, this is the first work to study two-sided matching from the perspective of mechanism design over social networks. Future works will include further discussions on the Pareto frontier. Even though all our proposed mechanisms are in the Pareto frontier according to the 13 properties, those mechanisms (or even different ones) may also satisfy a slightly stronger property that is defined between two adjacent properties, e.g., a new fairness property between FRN and FRD. It would also be interesting to discuss more general formulations of two-sided matching over social networks, e.g., cases where both students and colleges are distributed over networks.

Acknowledgments

This work is partially supported by JSPS KAKENHI Grant Numbers JP20H00587, JP20H00609, and JP21H04979, and Grant-in-Aid for "2019 Initiative for Realizing Diversity in the Research Environment" through the "Diversity and Super Global Training Program for Female and Young Faculty (SENTAN-Q)," Kyushu University from MEXT.