{'fraction_non_alphanumeric': 0.039248511904761904, 'fraction_numerical': 0.007347470238095238, 'mean_word_length': 4.013521914827479, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 17, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
One-Sided Matching with Permission

Classic one-sided matching assumes participants are independent and known in advance, each with an initial endowment to exchange with others. In this paper, we consider the participants are connected to form a network, which is often the case in reality. Some participants from the network initiate the matching game and the others need the existing participants' invitation/permission to join the game. The challenge is that participants may compete with each other if we apply the classic solution Top Trading Cycle (TTC), so they would not invite each other. Although we can add constraints on TTC to incentivize participants to invite each other, it only works on very limited networks. To combat this, we propose a new matching mechanism called Leave and Share to work on all networks. We prove that our solution is the most stable matching in all networks. In terms of optimality, as it is impossible to achieve it in any network, we conduct simulations to compare it with the extensions of TTC.


Introduction
Incentivizing agents to invite new agents via their social connections is a new trend in mechanism design. Different from traditional static settings, the agents' connections are specifically considered, and we can utilize their connections to enlarge the market by incentivizing them to invite their neighbors (Zhao 2021). In most games, a larger market contributes to a more desirable outcome. Particularly, for onesided matching, the motivation for agents' invitation is to get a better match instead of swapping within a small group. In fact, there exist online house swapping and second-hand goods exchanging platforms, where people can propagate them to social networks to form a larger and credible market.
To design the invitation incentives in a one-sided matching, we should guarantee that the inviters' match is not getting worse after inviting others. Till now, no mechanism can incentivize invitation in social network settings without restrictions. The classic Top Trading Cycle (TTC) matching mechanism gives the unique optimal and stable solution in the static one-sided matching (Shapley and Scarf 1974;Ma 1994). However, TTC cannot incentivize the participants to invite others, because an invitee might compete with her inviters for the match. Therefore, we have seen solutions to extend TTC by adding limitations on the selection range of participants or the network structure (e.g., restrict the network to trees (Kawasaki et al. 2021)).
The restrictions on TTC strictly narrow the participants' matching choices and thus result in a poor allocation. Though the restrictions do prevent an invitee from competing with her inviters, not all invitees will harm their inviters. The challenge is that we cannot clarify whether an invitee will bring harm to her inviters without a certain matching mechanism. So a straightforward way is to disable all possible competition between an invitee and her inviters, which is what the restriction on TTC does.
We move this effort forward by proposing a new mechanism that can be applied in all settings, and it clearly improves the outcome compared to the TTC extensions. We propose a mechanism called Leave and Share (LS). LS does not allow invitees to compete with their inviters before their inviters are matched. However, once the inviters are matched, their invitees cannot bring harm to them anymore, so they are allowed to match with more people to improve the invitees' match (which is the share part). The sharing process does not hurt the participants left but benefits the participants remaining significantly. This is the key of our mechanism, and it makes a clear outperformance without restricting the network structure of the participants. Our contributions advance the state of the art in the following ways: • We first prove the impossibility of incentivizing invitation under the condition of optimality or stability. For stability, we extend the definition and prove what we can and cannot achieve with invitation incentives under the new setting. • We then propose the Leave and Share (LS) mechanism to achieve both invitation incentive and the extended stability. LS performs as good as TTC if the network is a complete graph. • Due to the lack of a theoretical analysis of optimality, we conduct simulations to compare LS with TTC extensions. The results indicate that LS offers a more satisfiable matching in expectation in all settings under consideration.

Related Work
Mechanism design over social networks is a hot research topic, where agents' social connections and interactions are considered by the mechanism. One popular way to utilize the connections is to attract new participants, which has made a significant progress in auctions and cooperative games (Li et al. , 2017Zhang and Zhao 2022). In auctions, the main technique proposed to design the invitation incentives is to allow buyers to gain the social welfare increase due to their invitation. In cooperative games, invitees need to share their contributions with their inviters to get invited. Their methods rely on transferable utilities, which is not possible in matching. Specifically, for one-sided matching over social networks, traditional solutions like TTC cannot be directly applied to incentivize participants' invitation. To make TTC work in the network setting, Kawasaki et al. (2021) presented a modified TTC under tree networks only. Their modification restricted each participant's choices to her parent and her subtree. Their extension incentivized invitation by disabling more satisfiable matchings. Gourvès, Lesca, and Wilczynski (2017) also studied one-sided matching in social networks, but they focused on static social connections and ignored agents' strategic behaviors. To evaluate the efficiency of a matching mechanism, some cardinal methods are wellstudied in the traditional setting (Abebe et al. 2020;Abraham et al. 2005). Motivated by these work, we also apply a cardinal method to evaluate our mechanism.
Besides standard one-sided matching, You et al. (2022) also studied a variant of house allocation problem (Abdulkadiroglu and Sönmez 1999) under the tree-structured networks. Moreover, Cho, Todo, and Yokoo (2022) investigated two-sided matching over social networks, where they presented a series of impossibilities to show the hardness of the problem, and designed mechanisms under the assumption that one side is known. The goal of these papers is to extend the traditional solutions to get the invitation incentives required in the corresponding network settings.

The Model
We consider a one-sided matching problem in a social network denoted by an undirected graph G = (N, E), which contains n agents N = {1, . . . , n}. Each agent i ∈ N is endowed with an indivisible item h i and H = {h 1 , . . . , h n } is the set of all agents' items. We define agent i as j's neighbor if there is an edge e ∈ E between agent i and j, and let r i ⊆ N be i's neighbor set.
Each agent i ∈ N has a strict preference i over H. h i h means i prefers h to h and we use i to represent the weak preference. Denote agent i's private type as θ i = ( i , r i ) and θ = (θ 1 , · · · , θ n ) as the type profile of all agents. Let θ −i be the type profile of all agents except for agent i, then θ can be written as (θ i , θ −i ). Let Θ be the type profile space of all agents. Similarly, we have Θ = (Θ i , Θ −i ).
In a matching mechanism, each agent is required to report her type (reporting neighbor set is treated as inviting neighbors in practice). We denote agent i's reported type as θ i = ( i , r i ), where i is the reported preference and r i ⊆ r i is the reported neighbor set. Let θ = (θ 1 , · · · , θ n ) be the reported type profile of all agents.
Different from traditional settings, we assume only a subset of the agents are initially in the game (e.g., one agent initiated a matching with her neighbors). Without loss of generality, suppose an agent set N 0 ⊆ N contains the initial participants in the matching. The others need the existing participants' invitation to join the game. As the invitation process is modeled by reporting their neighbors, we define the qualified participants by their reported types.
For a given report profile θ , we generate a directed graph G(θ ) = (N (θ ), E(θ )), where edge i, j ∈ E(θ ) if and only if j ∈ r i . Under θ , we say agent i is qualified if and only if there is a path from any agent in N 0 to i in G(θ ). That is, i can be properly invited by the invitation chain from agent set N 0 . Let Q(θ ) be the set of all qualified agents under θ . Then the matching mechanism can only use Q(θ ).
Definition 2. A diffusion one-sided matching mechanism in social networks is a one-sided matching mechanism, π = (π i ) i∈N , such that for all reported type profile θ , it satisfies: 1. for all unqualified agents i / ∈ Q(θ ), π i (θ ) = h i . 2. for all qualified agents i ∈ Q(θ ), π i (θ ) is independent of the reports of all unqualified agents.
The difference between a diffusion one-sided matching and the matching defined in Definition 1 is that the participants can affect the qualification of other participants. If a participant changes her reported neighbor set, the qualified agent set may change. This is the challenge of this setting.
Next, we define two desirable properties for diffusion onesided matching mechanisms: individual rationality and incentive compatibility. Intuitively, individual rationality requires that for each agent, reporting her type truthfully guarantees that she gets an item no worse than her own.
Definition 3 (Individual Rationality (IR)). A diffusion onesided matching mechanism π is individually rational if for For incentive compatibility, it means reporting type truthfully is a dominant strategy for each agent.
Definition 4 (Incentive Compatibility (IC)). A diffusion one-sided matching mechanism π is incentive compatible if To evaluate the performance of a matching mechanism, an important metric is called Pareto optimality.
Definition 5 (Pareto Optimal (PO)). A mechanism π is Pareto optimal if for all type profile θ, there is no other allocation π (θ) such that for each agent i, π i (θ) i π i (θ), and there exists at least one agent j, π j (θ) j π j (θ).
Another metric is stability. A matching is stable if there does not exist any subset of agents who can deviate from the matching and match among the subset to make no one worse off, but at least one better off (this is called a blocking coalition). In the setting without networks, any subset of players can form a blocking coalition. However, in the network setting, they should know each other before they can form a coalition. Therefore, we assume that the blocking coalition in our setting is at least connected.
In the traditional setting, since there are no constraints on social connections, the agents can be viewed as fully connected. Then, any blocking coalition is at least a connected component. Hence, in the traditional setting, our redefined stability is the same as the standard stability. Definition 6 (Blocking Coalition). Given an allocation π(θ), we say a set of agents S ⊆ N (with item set H S ⊆ H) is a blocking coalition for π(θ) if S forms a connected component in G(θ) and there exists an allocation z(θ) such that for all i ∈ S, z i (θ) ∈ H S and z i (θ) i π i (θ) with at least one j ∈ S such that z j (θ) j π j (θ).
Definition 7 (Stability). We say a mechanism π is stable if for all type profiles θ, there is no blocking coalition for π(θ).

Impossibility Results
In this section, we discuss the impossibility results in the network setting presented in Table 1. Theorem 1 (Impossibility for PO, IC and IR). Given a social network with no less than three agents, no diffusion matching mechanism satisfies PO, IC and IR simultaneously. Proof. In the example shown in Figure 1, the only PO and IR allocations are a 3 and a 6 . For the former, agent 1 can misreport her preference as h 3 1 h 1 1 h 2 . Under agent 1's misreport, the only PO and IR allocation will be a 6 , and 1 reaches a better allocation under a 6 thus violating IC. For the latter, agent 2 can misreport her neighbor set as {1} and disqualify agent 3. In this way, the only PO and IR allocation is a 3 , 2 reaches a better allocation which also violates IC. Hence, there does not exist a mechanism under the social network setting with no less than 3 agents, which satisfies PO, IC and IR at the same time. A similar result also holds even if the neighbor relationship is asymmetric (Kawasaki et al. 2021). Theorem 2 (Impossibility for stability and IC). Given a social network with no less than three agents, no diffusion matching mechanism satisfies stability and IC simultaneously.

PO+IR Stable Stable-WCC Stable-CC IC
Proof. Consider the example given in Figure 1, the stable allocations are identical to the PO and IR ones (under the two type profile in Table 2). With the same strategic misreport, it can be concluded that stability is incompatible with IC.   Figure 1 and whether an allocation satisfies specific properties. If agent 1 misreports, the allocation satisfies Stable-CC (SCC) will be a 1 and a 6 , instead of a 6 only as under stable or Stable-WCC (SWCC).
To seek for an achievable stability in social networks, we further restrict the blocking coalitions from connected components to complete components. Definition 8 (Blocking Coalition under Complete Components). Given an allocation π(θ), we say a set of agents S ⊆ N (with item set H S ⊆ H) is a blocking coalition under complete components for π(θ) if S forms a complete component in G(θ) and there exists an allocation z(θ) such that for all i ∈ S, z i (θ) ∈ H S and z i (θ) i π i (θ) with at least one j ∈ S, z j (θ) j π j (θ). Definition 9 (Stability under Complete Components (Stable-CC)). We say a mechanism π is stable under complete components if for all type profiles θ, there is no blocking coalition under complete components for π(θ).
In this paper, we will design a matching mechanism that satisfies IC, IR and Stable-CC. This extended stability looks rather restricted, is it possible to make a slight relaxation on the complete component? In fact, it is not achievable even if we just remove a single edge from a complete component. Definition 10 (Nearly Complete Component). We call a connected graph The gap between a complete component and a nearly complete component is only one edge. We define a new stability under nearly complete components and prove that it is impossible to coexist with IC. Definition 11 (Blocking Coalition under Weakly Complete Components). Given an allocation π(θ), we say a set of agents S ⊆ N (with item set H S ⊆ H) is a blocking coalition under weakly complete components for π(θ) if S forms a nearly complete component or a complete component in G(θ) and there exists an allocation z(θ) such that for all i ∈ S, z i (θ) ∈ H S and z i (θ) i π i (θ) with at least one j ∈ S, z j (θ) j π j (θ). Definition 12 (Stability under Weakly Complete Components (Stable-WCC)). We say a mechanism π is stable under weakly complete components if for all type profiles θ, there is no blocking coalition under weakly complete components for π(θ).
Theorem 3 (Impossibility for Stable-WCC and IC). Given a social network with no less than three agents, no diffusion matching mechanism satisfies Stable-WCC and IC simultaneously.
Proof. Recall the example given in Figure 1, the possible blocking coalitions and allocations under Stable-WCC is identical to the example used in the proof of Theorem 2. Therefore, the same reasoning applies here.

The Mechanism
Before we introduce our mechanism, we first define the Top Trading Cycle and its extensions, which will be used as benchmarks to evaluate our mechanism.
Definition 13 (Top Trading Cycle). For a given G(θ ), construct a directed graph by letting each agent point to the agent who has her favorite item remaining in the matching. There is at least one cycle. For each cycle, allocate the item to the agent who points to it and remove the cycle. Repeat the process until there is no agent left.
TTC cannot ensure IC in the new setting, one trivial extension is called Swap With Neighbors (SWN), which only allows agents to swap with their neighbors. This completely removes all competition between inviters and invitees.
Definition 14 (Swap With Neighbors). For a given G(θ ), construct a directed graph by letting each agent point to her favorite item among herself and her neighbors remaining in the matching. There is at least one cycle. For each cycle, allocate the item to the agent who points to it and remove the cycle. Repeat the process until there is no agent left.
Another attempt is to restrict the network to trees and allow each agent to swap with her neighbors and subtree (Kawasaki et al. 2021). Let's call this extension Swap With Children (SWC).
Definition 15 (Swap With Children). For a given G(θ ), construct a directed graph by letting each agent points to her favorite item among herself, her neighbors, and her descendants remaining in the matching. There is at least one cycle. For each cycle, allocate the item to the agent who points to it and remove the cycle. Repeat the process until there is no agent left.
Both SWN and SWC avoid competition by restricting matching choices, which is not our goal to enlarge the market. We propose a new mechanism called Leave and Share (LS) which satisfies IC, IR and Stable-CC in all networks. Table 3 shows the difference of these mechanisms.
Mechanism Stable-CC IC Trees All Networks TTC SWN SWC (Trees) LS Table 3: Comparison on one-sided matching mechanisms over social networks.

Leave and Share
Leave and Share uses SWN as a base and adds a natural sharing process to enlarge agents' selection space, trying to provide a better allocation. Firstly, agents are matched by rounds in a protocol that resembles SWN under a strategyproof order. This guarantees that inviters are not worse off. Then, we share the neighbors of the left agents in this round by connecting their neighbors to each other, thus their neighbors can have new neighbors in the next round. This dynamic neighbor set update comes naturally because a matched cycle does not care how the remaining neighbors will be matched. Also, their remaining neighbors cannot prevent this sharing, and neither can the other remaining agents. : Preferences are h 6 1 h 1 1 · · · , h 5 2 h 2 2 · · · , h 4 3 h 3 3 · · · , h 3 4 h 4 4 · · · , h 2 5 h 5 5 · · · , h 1 6 h 6 6 · · · . One allocation for the agents 1 to 6 is (h 6 , h 5 , h 4 , h 3 , h 2 , h 1 ).
To see the value of our mechanism, consider the example given in Figure 2, where only agents 3 and 4 can exchange with each other in both SWN and SWC. The rest of the agents will end up with their own items. However, agents 3 and 4 will not block the exchange for agents 2 and 5 once they get their preferred items. After agents 3 and 4 are matched and Leave, we Share their remaining neighbors then agents 2 and 5 can swap. Similarly, after agents 2 and 5 leave, agents 1 and 6 can be matched as well. The process of Leave and Share is the name and core of our mechanism.
Before formalizing our mechanism, we introduce two notations to simplify the description.
Definition 16. Given a set A ⊆ N , we define a favorite agent function for agent i as f i (A) = j ∈ A such that ∀k ∈ A, h j i h k . We say f i (A) is i's favorite agent in A.
Definition 17. An ordering of agents is a one-to-one function P : N + → N , where agent P(i) is the i th agent in the ordering. Agents in P are sorted in ascending order by the length of the shortest path from agent set N 0 to them. Especially, for any agent i ∈ N 0 , its shortest path length is 0. When multiple agents have the same length of the shortest path, we use a random tie-breaking.

Leave and Share (LS)
1. Initialize N out = ∅ and an empty stack S. Define the top and bottom of S as S top and S bottom respectively, and let R i = r i ∪ {S bottom , i}. 2. While N out = N : (a) Find the minimum t such that P(t) / ∈ N out . Push P(t) into S. (b) While S is not empty: i who already formed a trading cycle C following their favorite agents. Allocate each agent i ∈ C the item h fi(Ri) . Add C to N t out . iii. Update the neighbor set of C's remaining neighbors by removing C, i.e., for all j ∈ i∈C r i \ N t out , set r j = r j \ C. (c) Add N t out to N out . Let all remaining neighbors of N t out connect with each other, i.e., they become neighbors of each other. That is, let X = i∈N t out r i \ N t out and for all j ∈ X, set r j = r j ∪ X.
In LS, we first define an order P which depends on each agent's shortest distance to the initial agent set. Under this order, the first while loop (step 2) guarantees that the agent pushed into the stack is the remaining agent with the smallest order, and all agents are matched (including self-match) in the end. A new round begins each time the stack empties.
In the Leave stage, each agent that is pushed into the stack pushes her (current) favorite neighbor into the stack (step (a)). If her favorite agent is already in the stack, we pop all the agents between herself and her favorite agent to form a trading cycle. Specially, we allow the agent to choose the agent at the bottom of the stack as her favorite, which leads to the pop of all the agents in the stack (step (b)).
Once the stack is empty, the mechanism enters the Share stage and updates the neighbor set of the remaining agents (step (c)). All the neighbors of the left agents become new neighbors to each other. In the next Leave stage, they can choose their favorite neighbors in a larger neighbor set.
We illustrate how LS executes by an example. Consider the social network in Figure 3(a). The ordering is given as P = (1,2,3,4,5,6,7,9,8), N 0 = 1. The type profile θ is given in Table 4. The changes of N t out and r i in each turn are shown in Table 5. Figure 3(b) to Figure 3(d) show the process of Leave and Share, which runs as follows.

Properties of Leave and Share
In this section, we prove that LS is IR, IC and Stable-CC. Theorem 4. For any ordering P, LS satisfies IR.
Proof. In LS, agent i leaves only when she gets an item h j . Agent i can always choose herself as her favorite agent, then LS will allocate h i to i. Thus, LS satisfies IR.  Table 5: Updates of neighbor set for each agent. The allocation is shown in the rightmost column.
Theorem 5. For any ordering P, LS satisfies IC.
Proof. Since each agent i's type consists of two parts, her preference i and her neighbor set r i , we will prove misreporting neither i nor r i can improve her allocation. Misreport on : For agent i, we fix her reported neighbor set as r i . Her real preference is i and reported preference is Since P is based on the minimum distance, which is irrelevant to agents' preferences, we only need to prove that h j i h j for all agents for a given order.
Before i is pushed into the stack, all trading cycles are irrelevant to i ( i has not been preferred by the agents in the stack before, so i is not used at all). Thus we only consider the situation when agent i is pushed into the stack and then i can decide which agent after i is pushed into the stack. When i is on the top of the stack, the next pushed agent f i (R i ) is determined by i . Agent i can be allocated with h j only when there is a trading cycle with i. Assume that h j i h j , i.e., misreporting i gives i a better item. We will show this leads to a contradiction. If i reported i truthfully, then i would first choose j before j (j is pushed into the stack first), since i did not get h j , which means j formed a cycle C j without i. If reporting i , i is matched with j , then it must be the case that there exists another trading cycle B which breaks the cycle C j . Otherwise, whenever i points to j , j will form the original cycle C j as it is independent of i's preference. The only possibility for i to achieve this is by pointing her favorite agent under the false preference i . By doing so, i can force other agents to leave earlier with different cycles including B. Next, we will show that it is impossible for B to break C j .
If B can actually break C j , there must be an overlap between B and C j . Assume that x is the node where B joins C j and y is the node where B leaves C j (x and y can be the same node). For node y, her match in B and C j cannot be the same (the model assumes strict preference), and no matter when y is pushed into the stack, both items in B and C j are still there. Assume the matching in C j is her favorite, then cycle B will never be formed. This is a contradiction, thus we cannot have h j i h j , i.e., reporting i truthfully is a dominant strategy. Misreport on r: As the above showed for any reported neighbor set r i , reporting i truthfully is a dominant strategy. Next, we further show that under truthful preference report, reporting r i is a dominant strategy. That is, for the allocation π i (( i , r i ), θ −i ) = h j and π i (( i , r i ), θ −i ) = h j , we will show h j i h j .
Firstly, we show that the tradings before i being pushed into the stack are irrelevant to i's neighbor set report r i . For all the agents ranked before i in P, their shortest distance is smaller than or equal to i's shortest distance to agent 1, which means that their shortest paths do not contain i and therefore r i cannot change them. Thus, r i cannot change the order of all agents ordered before i in P. In addition, agent i could be a cut point to disconnect certain agents D i from agent 1, so r i can impact D i 's distances and qualification. However, D i can only be involved in the matching after i is in the stack, as others cannot reach D i without i. Hence, before i is pushed into the stack, the tradings only depend on those ordered before i and the agents excluding D i , which are independent of i. In fact, the order of the agents pushed into the stack before i is the same no matter what r i is. That is, when i is pushed into the stack, the agents, except for D i , remaining in the game is independent of i.
Then when i misreports r i , she will only reduce her own options in the favorite agent selection. Whether r i disconnects D i or not, reporting r i here is equivalent to modifying i by disliking neighbors in r i \ r i . As we have showed, this is not beneficial for the agent. Therefore, reporting r i truthfully is a dominant strategy, i.e., h j i h j .
Put the above two steps together, we have proved that LS is incentive compatible.
Theorem 6. For any ordering P, LS satisfies Stable-CC.
Proof. For every S ⊆ N and their item set H S . Let the allocation given by LS be π(θ). If there exists a blocking coalition S, where S ⊆ N is the node set of a complete component in G(θ).
Since S is the node set of a complete component, we have ∀i ∈ S, S ⊆ r i . A blocking coalition S suggests there exists a z(θ) such that for all i ∈ S, z i (θ) ∈ H S , z i (θ) i π i (θ) with at least one j ∈ S we have z j (θ) j π j (θ). Therefore, for all j ∈ S, the blocking coalition guarantees the owner of z j (θ) and j are in one trading cycle. This indicates if a trading cycle contains any agent in the coalition, all the agents in the trading cycle are in the coalition. Based on LS, z j (θ) π j (θ) means the owner of z j (θ) will be pushed into the stack before the owner of π j (θ). Thus, the trading cycle which contains the owner of z j (θ) and j can trade by the cycle (i.e.,∀i ∈ S, z i (θ) = π i (θ)). This contradicts the assumption of existing at least one j ∈ S ⊆ r j , z j (θ) j π j (θ). Hence, LS satisfies Stable-CC.

Optimality Analysis
In this section, we compare our mechanism with Top Trading Cycle (TTC), Swap With Neighbors (SWN) and Swap With Children (SWC). Since Pareto Optimality fails to be compatible with IC, IR in the network setting, we define a cardinal index D to measure the performance and run experiments in various graphs to show the eminence of our mechanism. Although TTC cannot be directly applied in the social network setting, it provides a performance upper bound for the comparison. The performance lower bound is given by SWN since agents should be able to swap with their neighbors. We define i (j) as the j th favorite item of i. Assuming that h i is i (j) and π i (θ) is i (k), where j ≥ k for IR property, we define the ascension of i as d i = j − k. The average ascension of agents is defined as D = i∈N di n .
We use D to measure the average improvement of agents' satisfaction in a one-sided matching mechanism.
Figure 4: 100 graphs generated for each p to see how D changes accordingly. The minimum scale for p is 0.02.
To generate random networks, we define the probability of an edge between any two nodes as p. A higher p leads to a denser connected graph. Especially, when p = 1, the graph is complete. To generate a tree, we use ub to represent the maximum number of child nodes for a tree, and for each node, we uniformly select an integer i from [1, ub] as the number of the node's child nodes. Beginning at the root node, we create i child nodes for each node by a breadth-first order until the tree reaches size n. Agents' preferences are generated randomly from all permutations of the items. Figure 4 shows the performances of three mechanisms. SWN only allows swap in neighbors, while TTC allows swap without limit and LS considers invitations and sharing. In this figure, we generate 100 graphs of 50 nodes with fixed but randomly generated preferences and adjust p to see how D changes. When p is close to 1, the performances of LS and SWN are close, and they are the same as TTC when p = 1. Due to the sharing process, LS converges to TTC faster than SWN. In the other extreme case, when p goes to 0, both LS and SWN have a poorer performance, because there are fewer neighbors to swap or share.
Next, we compare LS with SWC, the other extension of TTC only on trees, in two dimensions including (a) different tree sizes; (b) same tree size, but different tree structures.
In terms of tree size, we generate 100 different trees for each tree size. As Figure 5 shows, LS outperforms the other two mechanisms significantly as the tree size is increasing. Also, the results showed that SWC and SWN are not so different, because the probability of forming a cycle with more than two agents is quite small when applying SWC. It requires all agents except for one in a cycle to prefer their parents' item rather than their whole subtrees'. The larger the cycle is, the smaller the probability is. Thus, by comparison to SWN, the improvement of SWC is very limited, while LS Figure 5: The tree is generated by a uniform distribution [1, n − 1] for each node's child node number, n is the size of the tree. For LS, n and D are positively correlated. takes a big advantage from sharing.
As for tree structures, we fix the tree size and use the number of leaf nodes to indicate the difference between trees. For a certain tree with n nodes, the lower bound and upper bound of n leaf are 1 and n − 1 respectively. We do the same simulation to show the relation between D and n leaf .
In Figure 6, we generate 100 different trees for each ub from 1 to 49 and count the number of each tree's leaf nodes. Then we simulate three mechanisms on each tree. When n leaf is small, SWC and LS are close, because there are few neighbors to share and form a big cycle. With the increase of n leaf , LS performs better, because sharing can match nodes in different branches, even for leaf nodes. If allocated by SWC, those leaf nodes can only get their own items.

Conclusion
In this paper, we proposed a novel one-sided matching protocol in social networks called Leave and Share to incentivize invitation. Then we redefined stability in social networks and showed its tightness by proving several impossibilities. Based on that, we not only proved LS is IC, IR and Stable-CC, but also evaluated its performance and compared it with TTC-like mechanisms. Our mechanism works in all network settings and significantly outperformed the benchmark mechanisms in the experiments. One possible future work is to find proper and attainable optimality with IC and design new mechanisms to achieve it.