# twosided_matching_over_social_networks__81612af6.pdf

Two-Sided Matching over Social Networks

Sung-Ho Cho, Taiki Todo, and Makoto Yokoo Graduate School of Information Science and Electrical Engineering, Kyushu University, Fukuoka, 819-0395 Japan {cho@agent., todo@, yokoo@}inf.kyushu-u.ac.jp

A new paradigm of mechanism design, called mechanism design over social networks, investigates agents incentives to diffuse the information of mechanisms to their followers over social networks. In this paper we consider it for two-sided matching, where the agents on one side, say students, are distributed over social networks and thus are not fully observable to the mechanism designer, while the agents on the other side, say colleges, are known a priori. The main purpose of this paper is to clarify the existence of mechanisms that satisfy several properties that are classified into four criteria: incentive constraints, efficiency constraints, stability constraints, and fairness constraints. We proposed three mechanisms and showed that no mechanism is better than these mechanisms, i.e., they are in the Pareto frontier according to the set of properties defined in this paper.

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 (Seq DA) mechanism, and the sequential TTC (Seq TTC) 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

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

Mechanism Incentive Efficiency Stability Fairness

OSCO SP MB-C FRN

Seq DA W-GSP NW MB-D FRD

Seq TTC W-GSP PE MB-D

Table 1: Three proposed mechanisms are on Pareto frontier, according to four criteria and 13 properties given in Fig. 1.

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.

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 q C := (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 r S := (rs)s S and ro, all the neighborhood relations are defined, specifying social network G(r S, 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. Analo-

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

gously, 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, q C, 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 ma-

Incentive Properties

Efficiency Properties

Stability Properties

Fairness Properties

Figure 1: Relations among 13 properties. For each arrow, its origin property implies its destination. The implication is transitive. Note that FR and NW together imply Stability.

nipulable 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

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

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. From WNW, 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:

c1 : s3 s2 s1 s4 s1, s4 : c2 c1 c2 : s4 s1 s2 s3 s2, s3 : c1 c2 .

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 from MB-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:

c1 : s1 s1 : c1 c2 : s2, s3 : c2 .

From MB-D, s1 is matched to c1. From WNW, 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.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

Figure 2: Examples of original social networks (not DCTs) used in the proofs for deriving contradictions

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: c1 : s3 s1 . . . s1, s3 : c1 c2 : s4 s2 . . . s2, s4 : c2 . 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, Seq TTC achieves PE, and Seq DA 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, Seq DA 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), Seq DA 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 Seq DA achieves MB-D and WNW (and even NW). Finally, for Thm 7, Seq DA achieves W-GSP and MB-D, and OSCO achieves SP and MB-C.

5 Proposed Mechanisms

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-Offering Mechanism 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.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

Figure 3: Social networks where three different effects occur on relation between s and ˆs when s does not invite neighbor s .

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.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

5.2 Sequential DA and Sequential TTC Sequential DA (Seq DA) 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 (Seq DA)). 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. Seq DA 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.

Seq DA is in the Pareto frontier. Given FRD, NW and MBD, an incentive property cannot be improved from W-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 (Seq TTC) 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 (Seq TTC)). 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. Seq TTC 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 Seq TTC. In each step, the standard TTC runs, which matches any MB-pair if any. So MB-D holds.

Seq TTC is also in the Pareto frontier. Given PE and MBD, an incentive property cannot be improved from W-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 Seq DA and Seq TTC 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.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

References [Abdulkadiro glu and S onmez, 2003] Atila Abdulkadiro glu and Tayfun S onmez. School choice: A mechanism design approach. American Economic Review, 93(3):729 747, 2003. [Aziz and Sun, 2021] Haris Aziz and Zhaohong Sun. School choice with flexible diversity goals and specialized seats. In Proc. the 30th Intl. Joint Conf. Artif. Intell. (IJCAI-21), pages 17 23, 2021. [Aziz et al., 2020] Haris Aziz, Anton Baychkov, and P eter Bir o. Summer internship matching with funding constraints. In Proc. the 19th Intl. Conf. Autonomous Agents & Multiagent Systems (AAMAS-20), pages 97 104, 2020. [Crawford, 1991] V. P. Crawford. Comparative statics in matching markets. Journal of Economic Theory, 54(2):389 400, 1991. [Fragiadakis et al., 2016] Daniel Fragiadakis, Atsushi Iwasaki, Peter Troyan, Suguru Ueda, and Makoto Yokoo. Strategyproof matching with minimum quotas. ACM Transactions on Economics and Computation, 4(1):6:1 6:40, 2016. [Gale and Shapley, 1962] David Gale and Lloyd Stowell Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9 15, 1962. [Goto et al., 2016] Masahiro Goto, Atsushi Iwasaki, Yujiro Kawasaki, Ryoji Kurata, Yosuke Yasuda, and Makoto Yokoo. Strategyproof matching with regional minimum and maximum quotas. Artif. Intell., 235:40 57, 2016. [Goto et al., 2017] Masahiro Goto, Fuhiko Kojima, Ryoji Kurata, Akihisa Tamura, and Makoto Yokoo. Designing matching mechanisms under general distributional constraints. American Economic Journal: Microeconomics, 9(2):226 62, 2017. [Hamada et al., 2017] Naoto Hamada, Chia-Ling Hsu, Ryoji Kurata, Takamasa Suzuki, Suguru Ueda, and Makoto Yokoo. Strategy-proof school choice mechanisms with minimum quotas and initial endowments. Artif. Intell., 249:47 71, 2017. [Ismaili et al., 2019] Anisse Ismaili, Naoto Hamada, Yuzhe Zhang, Takamasa Suzuki, and Makoto Yokoo. Weighted matching markets with budget constraints. J. Artif. Intell. Res., 65:393 421, 2019. [Kawasaki et al., 2020] Takehiro Kawasaki, Nathana el Barrot, Seiji Takanashi, Taiki Todo, and Makoto Yokoo. Strategy-proof and non-wasteful multi-unit auction via social network. In Proc. the 34th AAAI Conf. Artif. Intell. (AAAI-20), pages 2062 2069, 2020. [Kawasaki et al., 2021] Takehiro Kawasaki, Ryoji Wada, Taiki Todo, and Makoto Yokoo. Mechanism design for housing markets over social networks. In Proc. the 20th Intl. Conf. Autonomous Agents & Multiagent Systems (AAMAS-21), pages 692 700, 2021. [Kojima et al., 2018] Fuhito Kojima, Akihisa Tamura, and Makoto Yokoo. Designing matching mechanisms under

constraints: An approach from discrete convex analysis. Journal of Economic Theory, 176:803 833, 2018. [Kurata et al., 2017] Ryoji Kurata, Naoto Hamada, Atsushi Iwasaki, and Makoto Yokoo. Controlled school choice with soft bounds and overlapping types. J. Artif. Intell. Res., 58:153 184, 2017. [Li et al., 2017] Bin Li, Dong Hao, Dengji Zhao, and Tao Zhou. Mechanism design in social networks. In Proc. the 31st AAAI Conf. Artif. Intell. (AAAI-17), pages 586 592, 2017. [Li et al., 2020] Bin Li, Dong Hao, and Dengji Zhao. Incentive-compatible diffusion auctions. In Proc. the 29th Intl. Joint Conf. Artif. Intell. (IJCAI-20), pages 231 237, 2020. [Meeks and Rastegari, 2020] Kitty Meeks and Baharak Rastegari. Solving hard stable matching problems involving groups of similar agents. Theoretical Computer Science, 844:171 194, 2020. [Rastegari et al., 2013] Baharak Rastegari, Anne Condon, Nicole Immorlica, and Kevin Leyton-Brown. Two-sided matching with partial information. In Proc. the 14th ACM Conf. Economics & Computation (EC-13), pages 733 750, 2013. [Shapley and Scarf, 1974] L. S. Shapley and H. Scarf. On cores and indivisibility. Journal of Mathematical Economics, 1:23 28, 1974. [Takagi and Serizawa, 2010] Shohei Takagi and Shigehiro Serizawa. An impossibility theorem for matching problems. Social Choice and Welfare, 35(2):245 266, 2010. [Toda, 2006] Manabu Toda. Monotonicity and consistency in matching markets. International Journal of Game Theory, 34:13 31, 2006. [Todo and Conitzer, 2013] Taiki Todo and Vincent Conitzer. False-name-proof Matching. In Proc. the 12th Intl. Conf. Autonomous Agents & Multiagent Systems (AAMAS-13), pages 311 318, 2013. [Todo et al., 2021] Taiki Todo, Ryoji Wada, Kentaro Yahiro, and Makoto Yokoo. Lazy Gale-Shapley for Many-to-One Matching with Partial Information. In Proc. the Seventh Intl. Conf. Algorithmic Decision Theory (ADT-21), pages 390 405, 2021. [You et al., 2022] Bo You, Ludwig Dierks, Taiki Todo, Minming Li, and Makoto Yokoo. Strategy-proof house allocation with existing tenants over social networks. In Proc. the 21st Intl. Conf. Autonomous Agents & Multiagent Systems (AAMAS-22), pages 1446 1454, 2022. [Zhang et al., 2020] Wen Zhang, Dengji Zhao, and Hanyu Chen. Redistribution mechanism on networks. In Proc. the 19th Intl. Conf. Autonomous Agents & Multiagent Systems (AAMAS-20), pages 1620 1628, 2020. [Zhao et al., 2018] Dengji Zhao, Bin Li, Junping Xu, Dong Hao, and Nicholas R. Jennings. Selling multiple items via social networks. In Proc. the 17th Intl. Conf. Autonomous Agents & Multiagent Systems (AAMAS-18), pages 68 76, 2018.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)