\setcopyright

ifaamas \acmConference[AAMAS ’25]Proc. of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025)May 19 – 23, 2025 Detroit, Michigan, USAA. El Fallah Seghrouchni, Y. Vorobeychik, S. Das, A. Nowe (eds.) \copyrightyear2025 \acmYear2025 \acmDOI \acmPrice \acmISBN \affiliation \institutionKey Laboratory of Intelligent Perception and Human-Machine Collaboration, ShanghaiTech University \cityShanghai \countryChina \affiliation \institutionKey Laboratory of Intelligent Perception and Human-Machine Collaboration, ShanghaiTech University \cityShanghai \countryChina \affiliation \institutionKey Laboratory of Intelligent Perception and Human-Machine Collaboration, ShanghaiTech University \cityShanghai \countryChina

Housing Market on Networks

Xinwei Song [email protected] , Tianyi Yang [email protected] and Dengji Zhao [email protected]

Abstract.

Incentivizing the existing participants to invite new participants to join an auction, matching or cooperative game have been extensively studied recently. One common challenge to design such incentive in these games is that the invitees and inviters are competitors. To have such an incentive, we normally have to sacrifice some of the traditional properties. Especially, in a housing market (one kind of one-sided matching), we cannot maintain the traditional stability and optimality. The previous studies proposed some new matching mechanisms to have the invitation incentive (part of the incentive compatibility), but did not have any guarantee on stability and optimality.

In this paper, we propose new notions of stability and optimality which are achievable with incentive compatibility. We weaken stability and optimality on a special structure (complete components) on networks. We first prove that the weakened notions are the best we can achieve with incentive compatibility. Then, we propose three mechanisms (Swap With Neighbors, Leave and Share, and Connected Trading Cycles) to satisfy the desirable properties. Connected Trading Cycles is the first mechanism to satisfy the best stability and optimality compatible with incentive compatibility.

Key words and phrases:

Mechanism Design, Housing Market, Incentive Compatible

1. Introduction

Housing market on networks studies an endowment exchange problem with special consideration of the participants’ social connections Kawasaki et al. (2021). In this model, participants’ social connections are private information and only a small group initiates the matching. Those who are already in the game can decide whether or not to invite their neighbors. Expanding the market via invitation can be beneficial because more participants will provide more matching options, which opens the possibility of a more satisfactory matching. Several real-world applications, like online housing markets¹¹1https://www.homeexchange.com and second-hand goods exchange platforms²²2https://www.freecycle.org, have utilized social networks to promote their markets. On these platforms, existing participants are encouraged to share the matching information on their social media and invite their friends to form larger markets. But sometimes participants may hesitate to invite because their friends will compete with them and take away their favorite items in the matching game. For this reason, the main obstacle is ensuring that the inviters’ match is not getting worse after inviting others.

To solve the above problem, one way is to constrain participants’ selection space to remove potential competition caused by invitation. For example, Kawasaki et al. (2021) restricted the social network between agents as trees and proposed Modified TTC which only allows participants to choose from their parents and descendants. In this paper, we aim to design mechanisms for general social networks structures and design mechanisms to incentivize invitations. Our first mechanism, Swap With Neighbors (SWN) restricts participants to choosing from their neighbors’ items. Under this restriction, invitations can only bring matching opportunities not competitions, thus naturally satisfying IC. The drawback of SWN is that there is a very low probability that a participant can benefit from the enlarged market, which contradicts the purpose of enlarging the market for better matching. To improve the matching, we observed that if a group of participants trade and leave the market, they do not care about what happens next in the matching. Inspired by this observation, our second mechanism, called Leave and Share (LS), uses SWN as a base protocol but dynamically connects the remaining participants when some participants are leaving the market (the sharing process). Due to the sharing process, LS gives a more satisfying outcome.

All the above-mentioned mechanisms focused on the IC property, but to properly evaluate a matching mechanism, optimality and stability are the two key properties. The former characterizes how efficient a matching is, i.e., whether participants can improve their matching without making others’ matching worse, and the latter depicts the robustness of a matching, i.e., whether participants have incentives to deviate from the matching and exchange within a smaller group. The Top Trading Cycles (TTC) presented by Shapley and Scarf (1974) is the only Pareto optimal and stable mechanism for housing market problem Ma (1994). However, Kumar et al. (2022) show that more than half of the participants prefer their matching given by TTC in a smaller market than in a large integrated market. Hence, in the network setting where participants can control the market size through strategic invitations, TTC fails to be incentive compatible (IC). Due to the uniqueness of TTC, stability and Pareto optimality are not compatible with IC in housing market on networks.

To maintain invitation incentives, we weaken stability and optimality notions with complete components (cc), called stable-cc and optimal-cc, respectively. Stable-cc weakens stability in the sense that only participants in a complete component can deviate from the matching and exchange within the component. Optimal-cc weakens optimality in the sense that a matching can only be improved if all the participants whose allocation is improved have to form a complete component. We then prove that both stable-cc and optimal-cc are the tightest notions compatible with IC. Besides IC, individual rationality (IR) is also a commonly considered property that ensures participating in the game is not harmful, serving as a base incentive for people to join the game. Finally, combining all the properties together, we construct the theoretical boundaries for housing market on networks.

The best properties we can achieve together for our setting are stable-cc, optimal-cc, IC, and IR. The previously mentioned SWN and LS detect all the cycles formed by neighbors, so they naturally satisfy stable-cc. However, they both add restrictions to the selection space and fail to satisfy optimal-cc. Hence, we further propose the third mechanism, called Connected Trading Cycles (CTC), which does not add restrictions on the participant’s selection space to satisfy all the properties. Similar to TTC, CTC detects the top trading cycles (to ensure optimality). The key difference is that CTC makes sure the trading cycles have to satisfy certain connectedness on networks (to ensure invitation incentives). Intuitively, the connectedness guarantees that a group of participants can stay together regardless of the others’ strategic invitations. Thus, in the network setting, the trading cycles should build on a group of connected participants.

To sum up, our contributions are threefold:

•

We define the stability and optimality notions compatible with IC for housing market on networks.
•

We prove the best achievable stability and optimality in the network setting.
•

We propose three mechanisms: Swap With Neighbors, Leave and Share, and Connected Trading Cycles to meet the desirable properties (Table 1 gives a quick overview of the theoretical performance of each mechanism).

Table 1. Comparison on housing market mechanisms on social networks. We propose SWN, LS and CTC in this paper.

Mechanism	Stable-cc	Optimal-cc	IC	IR
TTC Shapley and Scarf (1974)	✓	✓	✕	✓
Modified TTC Kawasaki et al. (2021)	✓(Trees)	✕	✓(Trees)	✓
SWN	✓	✕	✓	✓
LS	✓	✕	✓	✓
CTC	✓	✓	✓	✓

2. Related Work

Li et al. (2017) initiate the line of research on mechanism design on social networks. They utilize social networks to incentivize participants to invite their friends to form a larger market so that participants can receive better outcomes Zhao (2021). However, the participants are competitors and may not want to invite all their friends without proper incentives. Many classic solutions fail to provide such incentives, so we cannot directly apply them for this purpose. To combat this, in auctions, we can pay the harmed inviters some rewards Li et al. (2022). In cooperative games, we can let the inviters share their invitees’ contributions Zhang and Zhao (2022). However, in matching, we face a greater challenge since the mechanism cannot compensate participants for the loss caused by invitation through payments.

Existing solutions for matching on networks restricts participants’ selection space and the social network structures. Kawasaki et al. (2021) and You et al. (2022) model the social network as a directed graph where neighborhood relationships can be asymmetric (i.e., A is B’s neighbor does not necessarily mean B is A’s neighbor). They focus on trees and modify the classic mechanisms to incentivize invitations for housing market as well as its variant Abdulkadiroğlu and Sönmez (1999). Specifically, they add limits on the selection space of the participants in a tree to prevent an invitee competing with her inviters. For two-sided matching, Cho et al. (2022) model the school choice problem into the network setting and design invitation incentives for the student side only. Another thread of work also takes into account the social network and its influence, but they differ from our setting Gourvès et al. (2017); Hoefer (2013). In their setting, the social network is priorly known and it constrains possible allocations.

Optimality and stability are two an well-concerned property for matching mechanisms Abdulkadiroglu and Sönmez (2013). The celebrated TTC is the only Pareto optimal and stable solution in the traditional housing market problem Ma (1994). Abraham et al. (2005) study various ways to evaluate the optimality of a house allocation mechanism and illustrate why TTC gives the Pareto optimal allocation. Fleischer and Wang (2008) point out the transitions between different optimal allocations in the house allocation problem. Brandt and Wilczynski (2019) analyze whether different types of dynamic pairwise swaps converge to Pareto optimal allocations for matching markets. In the network setting, no previous work has investigated the theoretical boundaries. We propose tight stability and optimality notions for this new setting and design mechanisms to reach them.

3. The Model

We consider a housing market problem on a social network denoted by an undirected graph $G=(N,E)$ , which contains $n$ agents $N=\{1,\dots,n\}$ . Each agent $i\in N$ is endowed with an indivisible item $h_{i}$ , usually referred to as a house. Let $H=\{h_{1},\dots,h_{n}\}$ be the set of all agents’ items. Considering the nature of the exchange economy, we formulate agents’ social relationships as symmetric in this model, i.e., $i$ has connections with $j$ in the social network indicates $j$ has connections with $i$ . We define agent $i$ as $j$ ’s neighbor if there is an edge $e\in E$ between agent $i$ and $j$ , let $r_{i}\subseteq N$ be $i$ ’s neighbor set.

Despite social relationship, each agent $i\in N$ has a strict preference $\succ_{i}$ over $H$ . $h\succ_{i}h^{\prime}$ means $i$ prefers $h$ to $h^{\prime}$ and we use $\succeq_{i}$ to represent the weak preference. Thus, we denote agent $i$ ’s private type as $\theta_{i}=(\succ_{i},r_{i})$ and $\theta=(\theta_{1},\cdots,\theta_{n})$ as the type profile of all agents. Let $\theta_{-i}$ be the type profile of all agents except for agent $i$ , then $\theta$ can be written as $(\theta_{i},\theta_{-i})$ . Let $\Theta$ be the type profile space of all agents. Similarly, we have $\Theta=(\Theta_{i},\Theta_{-i})$ .

In the housing market problem, the goal is to construct a matching following the principle that each agent will exchange their endowments to get better allocations. Assume there is a trusted center to enforce the execution of 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 $\theta^{\prime}_{i}=(\succ^{\prime}_{i},r^{\prime}_{i})$ , where $\succ^{\prime}_{i}$ is the reported preference and $r^{\prime}_{i}\subseteq r_{i}$ is the reported neighbor set. Let $\theta^{\prime}=(\theta^{\prime}_{1},\cdots,\theta^{\prime}_{n})$ be the reported type profile of all agents.

Definition \thetheorem.

In a housing market problem, a matching mechanism is defined by an allocation policy $\pi=(\pi_{i})_{i\in N}$ , where $\pi_{i}:\Theta\to H$ satisfies for all $\theta\in\Theta$ , $\pi_{i}(\theta)\in H$ , and $\pi_{i}(\theta)\neq\pi_{j\neq i}(\theta)$ .

In the networked setting, we assume only a subset of the agents are initially in the game and the matching mechanism can incentivize agents to diffuse the information thus enlarging the matching. Without loss of generality, suppose an agent set $N_{0}\subseteq N$ contains the initial participants in the market. The others need the existing participants’ invitation to join the game. Since the invitation is modeled as reporting neighbors, we define the qualified participants by their reported types.

For a given reported type profile $\theta^{\prime}$ , we generate a directed graph $G(\theta^{\prime})=(N(\theta^{\prime}),E(\theta^{\prime}))$ , where edge $\langle i,j\rangle\in E(\theta^{\prime})$ if and only if $j\in r_{i}^{\prime}$ . Under $\theta^{\prime}$ , we say agent $i$ is qualified if and only if there is a path from any agent in $N_{0}$ to $i$ in $G(\theta^{\prime})$ . That is, $i$ can connect to the agent set $N_{0}$ by an invitation chain. Let $Q(\theta^{\prime})$ be the set of all qualified agents under $\theta^{\prime}$ . In the networked housing market problem, diffusion matching mechanisms can only use $Q(\theta^{\prime})$ .

Definition \thetheorem.

In a networked housing market problem, a diffusion matching mechanism is a matching mechanism $\pi=(\pi_{i})_{i\in N}$ , such that for all reported type profile $\theta^{\prime}$ , it satisfies:

(1)

for all unqualified agents $i\notin Q(\theta^{\prime})$ , $\pi_{i}(\theta^{\prime})=h_{i}$ .
(2)

for all qualified agents $i\in Q(\theta^{\prime})$ , $\pi_{i}(\theta^{\prime})$ is independent of the reports of all unqualified agents.

The difference between a diffusion matching and the matching defined in Definition 3.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 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. For incentive compatibility, it means reporting type truthfully is a dominant strategy for each agent.

Definition \thetheorem (Individual Rationality (IR)).

A mechanism $\pi$ is individually rational if for all $i\in N$ , all $\theta_{i}\in\Theta_{i}$ , and all $\theta^{\prime}_{-i}\in\Theta_{-i}$ , we have $\pi_{i}(\theta_{i},\theta_{-i}^{\prime})\succeq_{i}h_{i}$ .

Definition \thetheorem (Incentive Compatibility (IC)).

A mechanism $\pi$ is incentive compatible if for all $i\in N$ , all $\theta^{\prime}_{-i}\in\Theta_{-i}$ and all $\theta_{i},\theta^{\prime}_{i}\in\Theta_{i}$ , we have $\pi_{i}(\theta_{i},\theta^{\prime}_{-i})\succeq_{i}\pi_{i}(\theta^{\prime}_{i},\theta^{\prime}_{-i})$ .

To evaluate the performance of a matching mechanism, an important metric is called Pareto optimality. A matching is Pareto optimal if no agent can improve her matching without others’ allocation getting worse.

Definition \thetheorem (Pareto Optimality (PO)).

A mechanism $\pi$ is Pareto optimal if for all type profile $\theta$ , there is no other allocation $\pi^{\prime}(\theta)$ such that for each qualified agent $i\in Q(\theta)$ , $\pi^{\prime}_{i}(\theta)\succeq_{i}\pi_{i}(\theta)$ , and there exists at least one qualified agent $j\in Q(\theta)$ , $\pi^{\prime}_{j}(\theta)\succ_{j}\pi_{j}(\theta)$ .

Another metric is stability. It requires no group of agents can deviate from the matching and match among themselves to make no one in the group worse off and at least one better off.

Definition \thetheorem (Stability).

A mechanism $\pi$ is stable if for all type profile $\theta$ , there is no other allocation $\pi^{\prime}(\theta)$ such that there exists a group $S\subseteq Q(\theta)$ that satisfies $\forall i\in S,\pi^{\prime}_{i}(\theta)\in H_{S}$ , and $\forall i\in S,\pi^{\prime}_{i}\succeq_{i}\pi_{i}(\theta)$ with at least one $j\in S,\pi^{\prime}_{j}(\theta)\succ_{j}\pi_{j}(\theta)$ .

In summary, our model is a practical variant of the networked housing market model proposed in Kawasaki et al. (2021). In their paper, the authors designed matching on an asymmetric social network and proved the impossibility results of the compatibility of IC, PO and stability. In the next section, we will prove the impossibilities in our model and further construct the theoretical boundaries.

4. The Boundaries

In this section, we first prove that a diffusion matching mechanism cannot achieve Pareto optimality or stability together with IC. Next, we define the best optimality and stability notion compatible with IC and then construct the theoretical boundaries.

Table 2. Desirable properties for diffusion matching mechanisms. IC, IR, stable-cc and optimal-cc are the boundaries.The implications between properties are proved in Section 4.3.

IR	IC	Stability	Optimality
IR	IC	Stable	PO
		$\downarrow$	$\downarrow$
		Stable-wcc	Optimal-wcc
		$\downarrow$	$\downarrow$
		Stable-cc	Optimal-cc

4.1. Impossibility Results

{theorem}

[Impossibility for PO, IC and IR] No diffusion matching mechanism is PO, IC and IR.

Proof.

In the example shown in Figure 1, suppose $N_{0}=\{1,2\}$ , the Pareto optimal and IR allocations are $\pi_{1}=(h_{3},h_{2},h_{1})$ and $\pi_{2}=(h_{2},h_{1},h_{3})$ . If a mechanism allocates $\pi_{1}$ , agent 2 can misreport her neighbor set as $r^{\prime}_{2}=\{1\}$ . Under agent 2’s misreport, agent 3 cannot join the game and the only PO and IR allocation will be $\pi_{2}=(h_{2},h_{1},h_{3})$ , and 2 gets a better allocation compared to that in $\pi_{1}$ . However, if the mechanism allocates $\pi_{2}$ , agent 1 can misreport her preference as $h_{3}\succ^{\prime}_{1}h_{1}\succ^{\prime}_{1}h_{2}$ . In this way, the only PO and IR allocation is $\pi_{1}=(h_{3},h_{2},h_{1})$ , and agent 1 reaches a better allocation. Hence, no diffusion matching mechanism is PO, IC and IR. ∎

Figure 1. A social network example. Preferences are

h_{3}\succ_{1}h_{2}\succ_{1}h_{1},\ \ \ h_{1}\succ_{2}h_{2}\succ_{2}h_{3},\ \ \ h_{1}\succ_{3}h_{3}\succ_{3}h_{2}

\Description

Example for Theorem 4.1 and Theorem 4.2.

{theorem}

[Impossibility for stability and IC] No diffusion matching mechanism is stable and IC.

Proof.

Consider the example in Figure 1, suppose $N_{0}=\{1\}$ , the only stable allocations is $\pi_{1}=(h_{3},h_{2},h_{1})$ . However, agent 2 can misreport her neighbor set as $r^{\prime}_{2}=\{1\}$ , so agent 3 cannot join the game. In this way, the only stable allocation is $\pi_{2}=(h_{2},h_{1},h_{3})$ . This means agent 2 can misreport to improve her matching result, so stability is incompatible with IC. ∎

To seek achievable optimality and stability notions for IC diffusion matching mechanisms, we focus on a special graph structure: complete components, i.e., the agents are neighbors of each other. For Pareto optimality, we restrict that only fully connected agents can improve their matching. For stability, we constrain the agents who can deviate from the matching and swap among themselves to be fully connected.

Definition \thetheorem (Complete Component).

A connected directed graph $G=(V,E)$ is a complete component if for any two nodes $i,j\in V$ , we have $\langle i,j\rangle\in E$ .

The idea of the limitation comes from the reality that only a group of people who know each other have a higher possibility to communicate and negotiate for a better matching/trade. Besides, in the traditional housing market problem, since there are no constraints on social connections, agents can be viewed as fully connected. Then, any group of agents is a fully connected component.

Following this idea, we define optimality and stability under complete components: optimal-cc and stable-cc.

Definition \thetheorem (Optimality under Complete Components (Optimal-cc)).

A diffusion matching mechanism $\pi$ is optimal under complete components if for all type profiles $\theta$ and the allocation $\pi(\theta)$ , there is no other allocation $\pi^{\prime}(\theta)$ such that $\forall i\in N,\pi^{\prime}_{i}(\theta)\succeq_{i}\pi_{i}(\theta)$ and $\exists j\in N,\pi^{\prime}_{j}(\theta)\succ_{j}\pi_{j}(\theta)$ and agents $\{i\in N|\pi_{i}(\theta)\neq\pi^{\prime}_{i}(\theta)\}$ forms a complete component in $G(\theta)$ .

Definition \thetheorem (Stability under Complete Components (Stable-cc)).

A diffusion matching mechanism $\pi$ is stable under complete components if for all type profiles $\theta$ and the allocation $\pi(\theta)$ , there is no agent set $S\subseteq N$ (with item set $H_{S}\subseteq H$ ) that forms a complete component in $G(\theta)$ , and another allocation $\pi^{\prime}(\theta)$ with $\forall i\in S,\pi^{\prime}_{i}(\theta)\in H_{S}$ such that $\forall i\in S,\pi^{\prime}_{i}(\theta)\succeq_{i}\pi_{i}(\theta)$ and $\exists j\in S,\pi^{\prime}_{j}(\theta)\succ_{j}\pi_{j}(\theta)$ .

4.2. Stable-cc and Optimal-cc are the Boundaries

Stable-cc and optimal-cc pose strict constraints on the agents who can improve by exchanging internally. Hence, it is worth investigating whether we can relax this limitation to get stronger notions. For instance, can we allow any connected group (no need to be a complete component) to improve their matching? Following this idea, we define stronger notions based on weakly complete components, but they are not compatible with IC.

Definition \thetheorem (Weakly Complete Component).

A connected directed graph $G=(V,E)$ is a weakly complete component if there exists at most one pair of nodes $i,j\in V$ such that $\langle i,j\rangle\notin E$ .

Definition \thetheorem (Optimality under Weakly Complete Components (Optimal-wcc)).

A diffusion matching mechanism $\pi$ is optimal under weakly complete components if for all type profiles $\theta$ and the allocation $\pi(\theta)$ , there is no other $\pi^{\prime}(\theta)$ such that $\forall i\in N,\pi^{\prime}_{i}(\theta)\succeq_{i}\pi_{i}(\theta)$ and $\exists j\in N,\pi^{\prime}_{j}(\theta)\succ_{j}\pi_{j}(\theta)$ and agents $\{i\in N|\pi_{i}(\theta)\neq\pi^{\prime}_{i}(\theta)\}$ forms a weakly complete component in $G(\theta)$ .

Next, we prove that no IC and IR diffusion mechanisms can be optimal-wcc.

Example	Optimal-wcc Allocation
(a)	$\pi_{a}=(h_{4},h_{2},h_{3},h_{1})$ , $\pi_{b}=(h_{2},h_{3},h_{1},h_{4})$
(b)	$\pi_{c}=(h_{2},h_{3},h_{1},h_{4})$
(c)	$\pi_{d}=(h_{4},h_{2},h_{3},h_{1})$

Figure 2. A counterexample for the coexistence of optimal-wcc, IR, and IC. Preferences are

h_{4}\succ_{1}h_{2}\succ_{1}h_{1},\ \ \ h_{3}\succ_{2}h_{2},\ \ \ h_{1}\succ_{3}h_{3},\ \ \ h_{1}\succ_{4}h_{4}

. Agents 1,2 are initial players in the matching. The red solid arrows represent favorite pointing. The red dashed arrows represent the second favorite pointing. The dashed agents are unqualified, so they are allocated their endowments.

\Description

A counterexample for the coexistence of optimal-wcc, IR, and IC.

{theorem}

No IC and IR diffusion one-sided matching mechanism is optimal-wcc.

Proof.

Let’s consider the example given in Figure 2. In figure (a), IR and optimal-wcc solutions are $\pi_{a},\pi_{b}$ . If we choose $\pi_{a}$ , agent 2 cannot get $h_{3}$ . So, agent 2 has the incentive to misreport and not invite agent 4. In this way, figure (a) transforms to figure (b) where the only IR and optimal-wcc solution is $\pi_{c}$ . Then, agent 2 can get her favorite item $h_{3}$ . To ensure IC, we should allocate $h_{3}$ to agent 2 when she truthfully reports (i.e., allocate $\pi_{b}$ in figure (a)). Next, we consider agent 1’s incentive to misreport when we choose $\pi_{b}$ in figure (a). If agent 1 does not invite agent 3, figure (a) transforms to figure (c) where the only IR and optimal-wcc solution is $\pi_{d}$ . Here, agent 1 can get her favorite item $h_{4}$ . To ensure IC in figure (a), we should allocate $h_{4}$ to agent 1 when she truthfully reports (i.e., allocate $\pi_{a}$ in figure (a)). This is a contradiction, so optimal-wcc is not compatible with IC. Hence, the tightest optimality notion compatible with IC is optimal-cc. ∎

Similarly, for stability, we define a stronger notion called stable-wcc and prove that stable-wcc is not compatible with IC and IR.

Definition \thetheorem (Stability under Complete Components (Stable-wcc)).

A diffusion matching mechanism $\pi$ is stable under weakly complete components if for all type profiles $\theta$ and the allocation $\pi(\theta)$ , there is no agent set $S\subseteq N$ (with item set $H_{S}\subseteq H$ ) that forms a weakly complete component in $G(\theta)$ , and another allocation $\pi^{\prime}(\theta)$ with $\forall i\in S,\pi^{\prime}_{i}(\theta)\in H_{S}$ such that $\forall i\in S,\pi^{\prime}_{i}(\theta)\succeq_{i}\pi_{i}(\theta)$ and $\exists j\in S,\pi^{\prime}_{j}(\theta)\succ_{j}\pi_{j}(\theta)$ .

{theorem}

No IC and IR diffusion one-sided matching mechanism is stable-wcc.

Proof.

Consider the example in Figure 1, suppose $N_{0}=\{1\}$ , the only stable-wcc allocations is $\pi_{1}=(h_{3},h_{2},h_{1})$ . However, agent 2 can misreport her neighbor set as $r^{\prime}_{2}=\{1\}$ , so that agent 3 cannot join the game. In this way, the only stable-wcc allocation is $\pi_{2}=(h_{2},h_{1},h_{3})$ . This means agent 2 can misreport to improve her matching result, so it can be concluded that stable-wcc is incompatible with IC. ∎

Combining Theorem 2 and Theorem 2, we conclude that the best stability and optimality we can aim for an IC and IR diffusion matching mechanism are stable-cc and optimal-cc respectively.

4.3. Implications between Properties

In this section, we study the relationships between different stability and optimality notions. By definition, Pareto optimality implies optimal-wcc and further implies optimal-cc. Stability implies stable-wcc and further implies stable-cc. In the traditional setting, a stable matching mechanism naturally satisfies Pareto optimal.

{theorem}

A mechanism $\pi$ is stable implies that $\pi$ is PO.

Proof.

For all type profiles $\theta$ , if a stable mechanism $\pi$ is not Pareto optimal, there exists a $\pi^{\prime}$ such that $\forall i\in N$ , $\pi^{\prime}_{i}(\theta)\succeq_{i}\pi_{i}(\theta)$ and $\exists j\in N$ , $\pi^{\prime}_{j}(\theta)\succ_{j}\pi_{j}(\theta)$ . In this case, we can construct a group of agents $S$ starting from $\{j\in N|\pi^{\prime}_{j}(\theta)\succ_{j}\pi_{j}(\theta)\}$ and consecutively add other agents so that $\forall i\in S$ , $\pi^{\prime}_{i}(\theta)\in H_{S}$ . So, $S$ can deviate from the matching together which violates stability. Thus, $\pi$ is stable implies that $\pi$ is Pareto optimal. ∎

Thus, when designing mechanisms, we can only focus on stability, and the optimality condition will be satisfied at the same time. However, in the networked setting, a similar implication relationship does not exist between the redefined notions.

{theorem}

A mechanism $\pi$ is stable-cc does not imply that $\pi$ is optimal-cc.

Proof.

See the example in Figure 3, allocation $\pi=(h_{2},h_{1},h_{4},h_{3})$ is stable under complete components. However, there exists another allocation $\pi^{\prime}=(h_{2},h_{4},h_{1},h_{3})$ where $\{2,3\}$ is a strictly better off group. Thus, $\pi$ is stable-cc does not imply that $\pi$ is optimal-cc.∎

Figure 3. Preferences are

h_{3}\succ_{1}h_{2}\succ_{1}h_{1},\ \ \ h_{4}\succ_{2}h_{1}\succ_{2}h_{2},\ \ \ h_{1}\succ_{3}h_{4}\succ_{3}h_{3},\ \ \ h_{2}\succ_{4}h_{3}\succ_{4}h_{4}

\Description

Example for stable-cc cannot imply optimal-cc.

This vanish of implication also poses a greater challenge in designing a mechanism that reaches the new boundaries.

5. The Mechanisms

In this section, we introduce three IC mechanisms, Swap With Neighbors (SWN), Leave and Share (LS) and Connected Trading Cycles (CTC). By different techniques, they all eliminate competitions caused by invitation. That is to say, they guarantee that inviting more agents to join in only potentially improves one’s matching. Formal proofs and complexity analysis are in Appendix B.

Figure 4. The properties of our three mechanisms. LS and SWN are stable-cc, IC and IR. CTC reaches the boundaries.

\Description

A figure that shows the properties of our three mechanisms.

5.1. Swap With Neighbors

First, we present SWN which is an intuitive extension of Top Trading Cycles. SWN only allows agents to choose favorite items from neighbors to achieve invitation incentives.

Definition \thetheorem (Swap With Neighbors).

For a given $G(\theta^{\prime})$ , 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.

In SWN, agents’ allocation is determined by trading cycles, which makes it strategy-proof for the preference report. Also, each agent can only get allocated a house from her neighbors, which means misreporting on one’s neighbor set is not beneficial, so SWN satisfies IC. Besides, a trading cycle within neighbors can always be allocated by SWN, so SWN satisfies stable-cc.

However, SWN achieves IC and stable-cc at the cost of efficiency, as it limits the matching options for agents. To improve the matching, we should provide more matching opportunities. But this also brings agents’ strategic report aiming for a better match. Thus, we need a strategy-proof order to help with the mechanism design and ensure that truthfully reporting one’s type is a dominant strategy for every agent. Our order is based on the shortest path length from the initial agent set to each agent. The reason is that non-initial agents require other agents’ permission to join the matching, the layer structure of the social network should be kept properly for incentive compatibility. This order is applied in both LS and CTC.

Definition \thetheorem.

An ordering of agents is a one-to-one function $\mathcal{O}:\mathbb{N}^{+}\to N$ , where agent $\mathcal{O}(t)$ is the $t^{th}$ agent in the ordering. For simplicity, we denote agent $i$ ’s order as $\mathcal{O}^{-1}(i)$ . Agents in $\mathcal{O}$ are sorted in ascending order by the length of the shortest path from agent set $N_{0}$ to them. Especially, for any agent $i\in N_{0}$ , its shortest path length from agent set $N_{0}$ is $0$ . When multiple agents have the same length of the shortest path, we use a random tie-breaking.

5.2. 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. The mechanism consists of two steps: first, agents are matched and left by rounds in a protocol that resembles SWN under a strategy-proof order. This guarantees that inviters are not worse off. Second, 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 and other agents cannot prevent this sharing.

Figure 5. Preferences are

h_{4}\succ_{1}h_{1}\succ_{1}\cdots,\ \ \ h_{3}\succ_{2}h_{2}\succ_{2}\cdots,\ \ \ h_{2}\succ_{3}h_{3}\succ_{3}\cdots,\ \ \ h_{1}\succ_{4}h_{4}\succ_{4}\cdots

\Description

Driving example that shows the value of Leave and Share.

To see the value of our mechanism, consider the example given in Figure 5, where only agents 2 and 3 can exchange with each other in SWN. The rest of the agents will end up with their own items. However, agents 2 and 3 will not block the exchange for agents 1 and 4 once they get their preferred items. After agents 2 and 3 are matched and Leave, we Share their remaining neighbors then agents 1 and 4 can swap. The process of Leave and Share is the name and core of our mechanism.

Before formalizing our mechanism, we introduce two notations to simplify our description.

Definition \thetheorem.

Given a set $A\subseteq N$ , we say $f_{i}(A)=j\in A$ is $i$ ’s favorite agent in $A$ if for any agent $k\in A,h_{j}\succeq^{\prime}_{i}h_{k}$ .

Leave and Share (LS)

(1)

Initialize $N_{out}=\emptyset$ 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}^{\prime}\cup\{S_{bottom},i\}$ .
(2)
While $N_{out}\neq N$ :
1. (a)
  
  Find the minimum $t$ such that $\mathcal{O}(t)\notin N_{out}$ . Push $\mathcal{O}(t)$ into $S$ .
2. (b)
  While $S$ is not empty:
  1. (i)
    
    While $f_{S_{top}}(R_{S_{top}})\notin S$ , push $f_{S_{top}}(R_{S_{top}})$ into $S$ .
  2. (ii)
    
    Pop off all agents from $S_{top}$ to $f_{S_{top}}(R_{S_{top}})$ , who already formed a trading cycle $C$ following their favorite agents. Allocate each agent $i\in C$ the item $h_{f_{i}(R_{i})}$ . Add $C$ to $N_{out}^{t}$ .
  3. (iii)
    
    Update the neighbor set of $C$ ’s remaining neighbors by removing $C$ , i.e., for all $j\in\bigcup_{i\in C}r_{i}^{\prime}\setminus N_{out}^{t}$ , set $r_{j}^{\prime}=r_{j}^{\prime}\setminus C$ .
3. (c)
  
  Add $N_{out}^{t}$ to $N_{out}$ . Let all remaining neighbors of $N_{out}^{t}$ connect with each other, i.e., they become neighbors of each other. That is, let $X=\bigcup_{i\in N_{out}^{t}}r_{i}^{\prime}\setminus N_{out}^{t}$ and for all $j\in X$ , set $r_{j}^{\prime}=r_{j}^{\prime}\cup X$ .

In LS, we first define an order $\mathcal{O}$ 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 is already in the stack, we pop all the agents between herself and her favorite to form a trading cycle. Specially, we allow agents to choose the agent at the bottom of the stack as favorite, which leads to popping off 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 neighbors of the left agents become new neighbors to each other. In the next Leave stage, they can choose in a larger neighbor set.

5.3. Connected Trading Cycles

In this section, we present our mechanism called Connected Trading Cycles (CTC) which takes both the trading cycles and agents’ connections into consideration. CTC is IR, IC, optimal-cc, and stable-cc, which is the best we can get in the network setting. To begin with, we give a few definitions to serve the description of our mechanism.

Definition \thetheorem.

Given a reported type profile $\theta^{\prime}$ , we generate a directed graph $F(\theta^{\prime})$ , in which each qualified agent has exactly one outgoing edge pointing to a qualified agent in $G(\theta^{\prime})$ . An edge $\langle i,j\rangle$ in $F(\theta^{\prime})$ means agent $i$ likes agent $j$ ’s item the most among all the qualified agents’ items ( $i,j$ can be the same agent). We name $F(\theta^{\prime})$ as the favorite pointing graph for $\theta^{\prime}$ .

There is at least one cycle in $F(\theta^{\prime})$ , and we formalize the definition of a cycle as below.

Definition \thetheorem.

A cycle in $F(\theta^{\prime})$ is an agent sequence $C_{m}=\{c_{1},\dots,c_{m}\}$ such that $\forall i\in\{1,\dots,m-1\}$ , $c_{i}$ points to $c_{i+1}$ , and $c_{m}$ points to $c_{1}$ in the favorite pointing graph $F(\theta^{\prime})$ .

Since the optimality and stability boundaries are constructed on complete components, it is natural to let cycles build on complete components to trade. However, if we only allow cycles formed by complete components to get traded, the performance is not better than SWN or LS (it meets stable-cc, but far from optimal-cc). Thus, we also consider cycles formed by connected components. Given that optimal-c is not compatible with IC, it is clear that not all such cycles can get traded. Therefore, we should further distinguish these cycles and identify the ones compatible with IC. This detection also makes our CTC description complex.

Figure 6. Preferences are

h_{5}\succ_{1}h_{2}\succ_{1}h_{1},\ \ \ h_{3}\succ_{2}h_{2},\ \ \ h_{4}\succ_{3}h_{1}\succ_{3}h_{3},\ \ \ h_{1}\succ_{4}h_{4},\ \ \ h_{3}\succ_{5}h_{5}

. The solid arrows represent favorite pointing. The dashed arrows represent second favorite pointing. The dashed agents are unqualified agents .

\Description

A motivated example for connected cycles.

Here comes a motivated example. The social network is shown in Figure 6 and agent 1 is the initial agent. If agent 1 does not invite agent 2, the connected component $\{1,3,5\}$ will form the blue cycle ( $C_{3}=\{1,5,3\}$ ). On the other hand, if agent 3 does not invite agent 5, the connected component $\{4,2,1,3\}$ will form the red cycle ( $C_{4}=\{1,2,3,4\}$ ). If both cycles are allowed, IC cannot hold since both agent 1 and agent 3 have the incentive to not invite a neighbor and form the cycle in favor of herself. Thus, an IC mechanism can only allow at most one of these two cycles to get traded. To distinguish the two cycles, we pay attention to each agent’s pointing. In the blue cycle, each agent has an exclusive path to reach her pointing: $\textbf{1}\to 3,\textbf{3}\to 5,\textbf{5}\to 3\to 1$ . However, in the red cycle, $\textbf{2}\to 1\to 3$ and $\textbf{4}\to 2\to 1$ have a shared edge $2\to 1$ . Similarly, $\textbf{1}\to 2$ and $\textbf{3}\to 1\to 2\to 4$ have a shared edge $1\to 2$ . Recall that in the cycle formed by a complete component (which is always allowed to get traded), each agent has an exclusive path to her pointing. Intuitively, the exclusive path can be regarded as an insurance for invitation incentives (no agent wants to influence other’s pointing by not inviting a neighbor). Following this idea, we design an algorithm to detect cycles in which each agent has an exclusive path to her pointing.

We also needs a strategy-proof order of the agents to determine who can be matched first.

Path Detection

Input: a cycle $C_{m}$ , a reported type profile $\theta^{\prime}$ , a favorite pointing graph $F(\theta^{\prime})$ and social network $G(\theta^{\prime})$ .

a.

Find a minimum connected component $T$ in $G(\theta^{\prime})$ where $C_{m}\subseteq T$ and $\forall i\in T$ , let $j$ be $i$ ’s pointing in $F(\theta^{\prime})$ , we have $j\in T$ . Note that if the cycle $C_{m}$ form a connected component in $G(\theta^{\prime})$ , then $T=C_{m}$ . If there is no such $T$ let $T=\emptyset$ .
b.

Construct a subgraph $G_{T}$ with the reported type profile of all agents in $T$ .
c.

If agent $i\in T$ points to herself in $F(\theta^{\prime})$ , add a mark $i$ on all the outgoing edges of $i$ in $G_{T}$ .
d.
Construct a shortest path set $SP=\{sp_{i}|i\in T\}$ in $G_{T}$ , where $sp_{i}$ is the shortest path from agent $i\in T$ to her pointing in $F(\theta^{\prime})$ . While $SP\neq\emptyset$ , execute the following,
1. i.
  
  Sort $SP$ by the ascending order of path length. If $sp_{i}$ and $sp_{j}$ have the same length, sort them by the agents ascending order $\mathcal{O}^{-1}(i)$ and $\mathcal{O}^{-1}(j)$ .
2. ii.
  
  Remove the first $sp_{i}$ in $SP$ . Add a mark $i$ on every edge on path $sp_{i}$ in $G_{T}$ . If $sp_{i}$ contains marks other than $i$ , and $i$ has another path to her pointing, add the next shortest path $sp^{\prime}_{i}$ for $i$ to $SP$ .

Output: an agent set $T$ and the marked subgraph $G_{T}$ .

Figure 7. Path Detection process for cycle

C_{5}=\{1,5\}

. The double arrows represent agents’ connections. The red arrow is agents’ pointing in the favorite pointing graph. The dashed box shows the minimum connected component

T

\Description

A mini-example for Path Detection process.

We use a brief example to show how path detection works. As shown in Figure 7, agents’ social connections (edges in $G(\theta^{\prime})$ ) are denoted by double arrows, and the red arrows represent edges in the favorite pointing graph $F(\theta^{\prime})$ . Take cycle $C_{5}=\{1,5\}$ as an example, the minimum connected component for $C_{5}$ is $T=\{1,2,4,5\}$ . Agent 4 is involved to help agent 1 and 5 connect to each other, and since $\langle 4,2\rangle\in F(\theta^{\prime})$ , agent 2 should also be involved in $T$ (as in Path Detection step a). Then we detect the shortest path set $SP$ for subgraph $G_{T}$ , the sorted path set is shown in Figure 7(c). Finally, follow the instruction in Path Detection step d.ii, we mark the subgraph $G_{T}$ to represents which directed edge by which agent.

In cycles like $C_{4}=\{1,2,3,4\}$ or $C_{5}=\{1,5\}$ , not all agents have an exclusive path to their pointing, so some have to switch their pointing in $F(\theta^{\prime})$ to a less preferred one. We define a next favorite function to adjust $F(\theta^{\prime})$ based on agents’ preferences.

Definition \thetheorem.

Given a reported type profile $\theta^{\prime}$ , the qualified agent set is $Q(\theta^{\prime})$ . Suppose agent $i$ points to agent $j$ in the favorite pointing graph $F(\theta^{\prime})$ , we have $\succ_{i}^{next}(F(\theta^{\prime}))=j^{\prime}$ if $j^{\prime}$ owns $i$ ’s favorite item in $Q(\theta^{\prime})\setminus\{k\in Q(\theta^{\prime})|k\succeq_{i}j\}$ .

Now we are ready to introduce our mechanism.

Connected Trading Cycles (CTC)

Given a reported type profile $\theta^{\prime}$ , construct the reported social network $G(\theta^{\prime})$ and favorite pointing graph $F(\theta^{\prime})$ . Initiate a settled agent set $V=\emptyset$ . Execute the following steps until $V=N$ .

a.

Find the agent $p_{1}\in N\setminus V$ with the minimum order $\mathcal{O}^{-1}(p_{1})$ . Start from agent $p_{1}$ , detect a node sequence $P_{m}=\{p_{1},\dots,p_{l},\dots,p_{m}\}$ in $F(\theta^{\prime})$ such that $\forall i\in\{1,\dots,m-1\}$ , $p_{i}$ points to $p_{i+1}$ , and $\{p_{l},\dots,p_{m}\}$ is a cycle $C_{m}$ .
b.

Run Path Detection algorithm with input $C_{m}$ , $\theta^{\prime}$ , $G(\theta^{\prime})$ and $F(\theta^{\prime})$ . Get an agent set $T$ and marked subgraph $G_{T}$ as output.
c.
Find every agent $i\in T$ such that no path in $G_{T}$ from $i$ to her pointing is exclusively marked by $i$ , and $i$ ’s outgoing edges are marked only by $i$ . Denote the set of such agents as $S\subset T$ .
1. i.
  
  If $T=\emptyset$ , find the last agent $i$ on $C_{m}$ who cannot connect to her pointing in $G(\theta^{\prime})$ , let $i$ switch her pointing to $\succ_{i}^{next}(F(\theta^{\prime}))$ .
2. ii.
  
  If $S=\emptyset$ and $C_{m}=T$ , add all agents in $T$ into the settled agent set $V$ . While an agent $i\in N\setminus V$ points to an agent in $V$ , let $i$ point to $\succ_{i}^{next}(F(\theta^{\prime}))$ .
3. iii.
  
  If $S=\emptyset$ and $C_{m}\subset T$ , find the agent $j\in T\setminus C_{m}$ with minimum order $\mathcal{O}^{-1}(j)$ . Start from agent $j$ ’s pointing, find the last agent $i\in C_{m}$ such that $i$ ’s path to its pointing passes at least one agent in $T\setminus C_{m}$ . If no such $i$ , start from agent $j$ ’s pointing, find the last agent $i\in(T\setminus C_{m})$ such that $i$ ’s path to its pointing passes at least one agent in $C_{m}$ . Let $i$ point to $\succ_{i}^{next}(F(\theta^{\prime}))$ .
4. iv.
  
  If $(T\setminus C_{m})\cap S\neq\emptyset$ , find the agent $i\in(T\setminus C_{m})\cap S$ with minimum order $\mathcal{O}^{-1}(i)$ . Let $i$ point to $\succ_{i}^{next}(F(\theta^{\prime}))$ .
5. v.
  
  If $(T\setminus C_{m})\cap S=\emptyset$ , find the agent $i\in S$ with the minimum order $\mathcal{O}^{-1}(i)$ such that $i$ ’s path to its pointing covers another agent’s path to her pointing. If no such $i$ , find agent $i\in S$ with the minimum order $\mathcal{O}^{-1}(i)$ . Let $i$ point to $\succ_{i}^{next}(F(\theta^{\prime}))$ .

Our mechanism first detects cycles in the favorite pointing graph because these cycles can ensure optimality. Thus, agents will not misreport their preferences to get a better allocation (also why TTC is IC in the traditional setting). However, in the network setting, trading cycles formed by agents who cannot connect to each other are fragile. The reason is that others can misreport neighbor set to break the cycle (for instance, disqualify some agents on the cycle). Hence, we construct a minimum connected component $T$ for each cycle where they can stay connected.

Recall the example in Figure 6, we can see that if every agent on the cycle has an exclusive path to her pointing (e.g. 1-3-5), the cycle can get traded. For cycles that do not meet this condition, we identify a special agent set $S$ . each agent in $S$ does not have an exclusive path to her pointing, and her outgoing edges are only marked by herself. These agents cannot misreport to avoid path overlap because the overlap lies outside their outgoing edges (which is irrelevant to their report). Hence, we let agents in $S$ switch their pointing to a less preferred one.

For cases where $S=\emptyset$ , if $T$ consists of only agents on the cycle, they can get traded (CTC step c-ii). Otherwise, we start from an agent $i\in T$ who is not on the cycle and find the last agent on the cycle who does not have a path to her pointing only by connections on the cycle (CTC step c-iii). This is because every agent in $T$ now has an exclusive path to her pointing, and the cycle has to rely on agents not on the cycle to stay connected. Thus, agents on the cycle have to switch preferences first, and we start from the last agent to maintain the completeness of the cycle to the greatest extent.

For cases where $S\neq\emptyset$ , if $S$ contains an agent not on the cycle, let her switch pointing to a less preferred one first (CTC step c-iv). This is because such agents do not provide any connection for the cycle and agents on the cycle have incentives to disqualify them to eliminate path overlaps. If $S$ consists only of agents on the cycle, we find the agent $i$ whose path covers another agent $j$ ’s path to her pointing and let $i$ switch her preference (CTC step c-v). This is because, to ensure everyone has an exclusive path to her pointing, $i$ and $j$ can never hold their pointing together. Agent $i$ should switch preference first because her path contains $j$ ’s outgoing edges ( $j$ ’s report has impacts on $i$ ).

Figure 8. The double arrows represent agents’ connections. The red arrow is agents’ pointing in the favorite pointing graph. The dashed red arrow means the agent switch her pointing to a less favorite one. The dashed box shows the minimum connected component

T

\Description

A mini-example for Connected Trading Cycles, see the full version in Appendix A.

We present an example to illustrate the execution of CTC in Figure 8. In (a), everyone points to her favorite item. Since agent 1 has the minimum order, we start from agent 1 and detect cycle $C_{5}=\{1,5\}$ . Then, we construct the minimum connected component $T=\{1,2,4,5\}$ in (b). By the Path Detection algorithm, we can see that both agent 2 and agent 5 do not have an exclusive path to their pointing, so $S=\{2,5\}$ . By CTC step c-iv, we let agent 2 switch her pointing to a less favorite one. In (c), we also start from agent 1 and detect the same cycle $C_{5}$ , and the same $T$ . Now, only agent 5 does not have an exclusive path to her pointing, so $S=\{5\}$ . By CTC step c-v, we let agent 5 switch her pointing. In (d), we detect cycle $C_{3}=\{1,5,3\}$ and construct $T=\{1,2,3,4,5\}$ . Everyone has an exclusive path to reach her pointing, so $S=\emptyset$ . By CTC step c-iii, we start from agent 2’s pointing and find that agent 5 is the last agent whose path to her pointing passes at least one agent in $T\setminus C_{3}$ . So, we let agent 5 switch her pointing. Finally in (e), $C_{2}=\{1,5,4,2\}$ is a connected cycle and $S=\emptyset$ . By CTC step c-ii, $C_{2}$ can get traded and agent 3 will switch her pointing to her next favorite one as shown in (f). We leave the detailed execution in Appendix A.

To our best knowledge, the Connected Trading Cycles is the first mechanism that satisfies optimal-cc.

{theorem}

For any order $\mathcal{O}$ , CTC is optimal-cc.

Proof.

For any given type profile $\theta$ , if the allocation $\pi(\theta)$ given by CTC violates optimal-cc, there exists another allocation $\pi^{\prime}(\theta)$ such that every agent in a complete component $B$ in $G(\theta)$ is strictly better, while others receive the same allocation. Let $i,j$ be two agents in $B$ , and $\pi^{\prime}_{i}(\theta)=\pi_{j}(\theta)=h_{k}$ . Because $B$ is a complete component in $G(\theta)$ , $i$ can reach $j$ by her outgoing edge, which means $i\to j$ is an exclusive path for $i$ . Since $\pi(\theta)$ is given by CTC, $j$ has an exclusive path to agent $k$ , the owner of her allocation $\pi_{j}(\theta)$ (as in CTC step c.ii). Combining the two paths together, agent $i$ can reach $k$ , the owner of $\pi^{\prime}_{i}(\theta)$ , by $i\to j\to k$ . Hence, if $i$ points to $k$ , CTC will not make agent $i$ switch her pointing to a less preferred agents. Therefore, there exists an exclusive path for every agent $i\in B$ to reach the owner of $\pi^{\prime}_{i}(\theta)$ , and CTC will allocate $\pi^{\prime}(\theta)$ . This means $\pi(\theta)=\pi^{\prime}(\theta)$ , which contradicts our assumption. ∎

6. Conclusion

In this paper, we redefine optimality and stability notions in social networks and show their tightness by proving impossibilities. We propose two novel matching protocols called Swap With Neighbors and Leave and Share respectively that satisfy IC, IR and stable-cc. We also prove the theoretical boundaries and propose a mechanism called Connected Trading Cycles to reach them. One future work is to study network settings with practical limits to find better optimality and stability notions. Another direction is to design the distributed execution for centralized matching mechanisms to make them more applicable.

{acks}

We thanks the reviewers for their valuable comments on the original submission. This work was supported in part by Science and Technology Commission of Shanghai Municipality (No.22ZR1442200 and No.23010503000), and Shanghai Frontiers Science Center of Human-centered Artificial Intelligence (ShangHAI).

References

(1)
Abdulkadiroğlu and Sönmez (1999) Atila Abdulkadiroğlu and Tayfun Sönmez. 1999. House allocation with existing tenants. Journal of Economic Theory 88, 2 (1999), 233–260.
Abdulkadiroglu and Sönmez (2013) Atila Abdulkadiroglu and Tayfun Sönmez. 2013. Matching markets: Theory and practice. Advances in Economics and Econometrics 1 (2013), 3–47.
Abraham et al. (2005) David J. Abraham, Katarína Cechlárová, David F. Manlove, and Kurt Mehlhorn. 2005. Pareto Optimality in House Allocation Problems. In Algorithms and Computation, Rudolf Fleischer and Gerhard Trippen (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 3–15.
Brandt and Wilczynski (2019) Felix Brandt and Anaëlle Wilczynski. 2019. On the Convergence of Swap Dynamics to Pareto-Optimal Matchings. In Web and Internet Economics, Ioannis Caragiannis, Vahab Mirrokni, and Evdokia Nikolova (Eds.). Springer International Publishing, Cham, 100–113.
Cho et al. (2022) Sung-Ho Cho, Taiki Todo, and Makoto Yokoo. 2022. Two-Sided Matching over Social Networks. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, Lud De Raedt (Ed.). International Joint Conferences on Artificial Intelligence Organization, 186–193. https://doi.org/10.24963/ijcai.2022/27 Main Track.
Fleischer and Wang (2008) Rudolf Fleischer and Yihui Wang. 2008. Dynamic Pareto Optimal Matching. In Proceedings of the 2008 International Symposium on Information Science and Engieering - Volume 02 (ISISE ’08). IEEE Computer Society, USA, 797–802. https://doi.org/10.1109/ISISE.2008.237
Gourvès et al. (2017) Laurent Gourvès, Julien Lesca, and Anaëlle Wilczynski. 2017. Object Allocation via Swaps along a Social Network. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (Melbourne, Australia) (IJCAI’17). AAAI Press, 213–219.
Hoefer (2013) Martin Hoefer. 2013. Local matching dynamics in social networks. Information and Computation 222 (2013), 20–35. https://doi.org/10.1016/j.ic.2012.10.005 38th International Colloquium on Automata, Languages and Programming (ICALP 2011).
Kawasaki et al. (2021) Takehiro Kawasaki, Ryoji Wada, Taiki Todo, and Makoto Yokoo. 2021. Mechanism Design for Housing Markets over Social Networks. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems (Virtual Event, United Kingdom) (AAMAS ’21). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 692–700.
Kumar et al. (2022) Rajnish Kumar, Kriti Manocha, and Josué Ortega. 2022. On the integration of Shapley–Scarf markets. Journal of Mathematical Economics 100 (2022), 102637.
Li et al. (2022) Bin Li, Dong Hao, Hui Gao, and Dengji Zhao. 2022. Diffusion auction design. Artificial Intelligence 303 (2022), 103631.
Li et al. (2017) Bin Li, Dong Hao, Dengji Zhao, and Tao Zhou. 2017. Mechanism Design in Social Networks. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (San Francisco, California, USA) (AAAI’17). AAAI Press, 586–592.
Ma (1994) Jinpeng Ma. 1994. Strategy-proofness and the strict core in a market with indivisibilities. International Journal of Game Theory 23, 1 (1994), 75–83.
Shapley and Scarf (1974) Lloyd Shapley and Herbert Scarf. 1974. On cores and indivisibility. Journal of mathematical economics 1, 1 (1974), 23–37.
You et al. (2022) Bo You, Ludwig Dierks, Taiki Todo, Minming Li, and Makoto Yokoo. 2022. Strategy-Proof House Allocation with Existing Tenants over Social Networks. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (Virtual Event, New Zealand) (AAMAS ’22). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 1446–1454.
Zhang and Zhao (2022) Yao Zhang and Dengji Zhao. 2022. Incentives to Invite Others to Form Larger Coalitions. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (Virtual Event, New Zealand) (AAMAS ’22). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 1509–1517.
Zhao (2021) Dengji Zhao. 2021. Mechanism Design Powered by Social Interactions. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems (Virtual Event, United Kingdom) (AAMAS ’21). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 63–67.

Appendix A A Detailed Example for CTC

i	$\succ_{i}$	$r_{i}$	$\pi_{i}$
1	$h_{5}\succ h_{1}\succ\cdots$	2,3,4	$h_{5}$
2	$h_{4}\succ h_{1}\succ h_{2}\succ\cdots$	1	$h_{1}$
3	$h_{1}\succ h_{6}\succ h_{3}\succ\cdots$	1	$h_{3}$
4	$h_{2}\succ h_{4}\succ\cdots$	1,3,5,6	$h_{2}$
5	$h_{1}\succ h_{3}\succ h_{4}\succ h_{5}\succ\cdots$	4	$h_{4}$
6	$h_{3}\succ h_{6}\succ\cdots$	4	$h_{6}$

Figure 9. Figure (a) represents the

G(\theta^{\prime})

. Figure (b) is the favorite pointing graph

F(\theta^{\prime})

. Table (c) presents the preference, neighbor set, and the allocation given by CTC for each agent.

\Description

A detailed example for Connected Trading Cycles, graph and profile table.

Figure 10. An running example of CTC. The double arrows represent agents’ connections. The red arrow is agents’ pointing in the favorite pointing graph. The dashed red arrow means the agent switch her pointing to a less favorite agent. We use a dashed box to indicate agents in the minimum connected component

T

, and the matched agents are in grey.

\Description

Execution of Connected Trading Cycles on Figure 9.

In this section, We run a detailed example to illustrate our mechanism. The initial agent set is $N_{0}=\{1\}$ . The order is $\mathcal{O}=(1,2,3,4,5,6)$ . The social network, type profiles, and allocation are presented in Figure 9. The following steps match the sub-figures in Figure 10. Since edges in both $G(\theta^{\prime})$ and $F(\theta^{\prime})$ are directed, which may cause ambiguity, we adopt $i\to j$ to represent the directed edge $\langle i,j\rangle$ in $G(\theta^{\prime})$ and use $\langle i,j\rangle$ for directed edge between $i,j$ in $F(\theta^{\prime})$ . For simplicity, we denote a path $(\langle i,j\rangle,\langle j,k\rangle)$ in $G(\theta^{\prime})$ as $(i\to j\to k)$ .

(a)

In the beginning, agent 1 has the minimum order in $N\setminus V=\{1,2,3,4,5,6\}$ . We detect $P_{5}=C_{5}=\{1,5\}$ . In the path detection process, the minimum connected component that contains $C_{5}$ is $T=\{1,2,4,5\}$ . We then compute the shortest path set $SP=\{(\textbf{1}\to 4\to 5),(\textbf{2}\to 1\to 4),(\textbf{4}\to 1\to 2),(\textbf{5}\to 4\to 1)\}$ . Both agent 2 and agent 5 do not have a path to their pointing only marked by themselves, and their outgoing edges are not marked by others, so $S=\{2,5\}$ . Since $(T\setminus C_{5})\cap S=\{2\}$ , and agent 2 has the minimum order in $S$ , we change $\langle 2,4\rangle$ to $\langle 2,\succ_{2}^{next}(F(\theta^{\prime}))=3\rangle$ (CTC step c-iv).
(b)

Agent 1 has the minimum order in $N\setminus V=\{1,2,3,4,5,6\}$ . We detect $P_{5}=C_{5}=\{1,5\}$ . In the path detection process, the minimum connected component that contains $C_{5}$ is $T=\{1,2,4,5\}$ . The shortest path set is $SP=\{(\textbf{2}\to 1),(\textbf{1}\to 4\to 5),(\textbf{4}\to 1\to 2),(\textbf{5}\to 4\to 1)$ . Agent 5 is the only agent who does not have a path to her pointing only marked by herself, and her outgoing edge is not marked by others, so $S=\{5\}$ . Since $(T\setminus C_{m})\cap S=\emptyset$ and $S=\{5\}$ , we change $\langle 5,1\rangle$ to $\langle 5,\succ_{5}^{next}(F(\theta^{\prime}))=3\rangle$ (CTC step c-v).
(c)

Agent 1 has the minimum order in $N\setminus V=\{1,2,3,4,5,6\}$ . We detect $P_{3}=C_{3}=\{1,5,3\}$ . In the path detection process, the minimum connected component that contains $C_{3}$ is $T=\{1,2,3,4,5\}$ . The shortest path set $SP=\{(\textbf{2}\to 1),(\textbf{3}\to 1),(\textbf{1}\to 4\to 5),(\textbf{4}\to 1\to 2),(\textbf{5}\to 4\to 3)\}$ . All agents in $T$ have a path to their pointing only marked by themselves, so $S=\emptyset$ and $C_{3}\subset T$ . Agent 2 has the minimum order in $T\setminus C_{3}=\{2,4\}$ , we start from agent 2’s pointing, and agent 5 is the last agent on $C_{3}$ whose path to her pointing contains at least one agent (i.e., agent 4) in $T\setminus C_{3}$ . We change $\langle 5,3\rangle$ to $\langle 5,\succ_{5}^{next}(F(\theta^{\prime}))=4\rangle$ (CTC step c-iii).
(d)

Agent 1 has the minimum order in $N\setminus V=\{1,2,3,4,5,6\}$ . We detect $P_{2}=C_{2}=\{1,5,4,2\}$ . In the path detection process, the minimum connected component that contains $C_{2}$ is $T=\{1,2,4,5\}$ . We then compute the shortest path set $SP=\{(\textbf{2}\to 1),(\textbf{5}\to 4),(\textbf{1}\to 4\to 5),(\textbf{4}\to 1\to 2)$ . All agents in $T$ have a path to their pointing only marked by themselves, so $S=\emptyset$ and $C_{2}=T$ . We add $\{1,2,4,5\}$ to $V$ . Since agent 3 belongs to $N\setminus V$ but she points to agent 1 who is added to $V$ , we change $\langle 3,1\rangle$ to $\langle 3,\succ_{3}^{next}(F(\theta^{\prime}))=6\rangle$ (CTC step c-ii).
(e)

Agent 3 has the minimum order in $N\setminus V=\{3,6\}$ . We detect $P_{6}=C_{6}=\{3,6\}$ . In the path detection process, we cannot find a connected component $T$ that contains $C_{6}$ . Agent 6 is the last agent on $C_{6}$ who cannot connect to her pointing, we change $\langle 6,3\rangle$ to $\langle 6,\succ_{6}^{next}(F(\theta^{\prime}))=6\rangle$ (CTC step c-i).
(f)

Agent 3 has the minimum order in $N\setminus V=\{3,6\}$ . We detect $P_{6}=\{3,6\}$ and $C_{6}=\{6\}$ . In the path detection process, the minimum connected component that contains $C_{6}$ is $T=C_{6}=\{6\}$ . The shortest path set $SP=\{(\textbf{6}\to 6)\}$ . Agent 6 is the only agent in $T$ , and she has a path to herself that is not marked by others. We have $S=\emptyset$ . So, we add $\{6\}$ to $V$ (CTC step c-ii). Since agent 3 belongs to $N\setminus V$ but she points to agent 6 who is added to $V$ , we change $\langle 3,6\rangle$ to $\langle 3,\succ_{3}^{next}(F(\theta^{\prime}))=3\rangle$ (CTC step c-ii).
(g)

Agent 3 has the minimum order in $N\setminus V=\{3\}$ . We detect $P_{3}=C_{3}=\{3\}$ . The shortest path set $SP=\{(\textbf{3}\to 3)\}$ . Agent 3 is the only agent in $T$ , and she has a path to herself that is not marked by others. We have $S=\emptyset$ . So, we add $\{3\}$ to $V$ (CTC step c-ii).
(h)

Now $V=N$ , the algorithm terminates. The allocation given by CTC is $\pi=(h_{5},h_{1},h_{3},h_{2},h_{4},h_{6})$ .

Appendix B Formal Proofs for Mechanisms

B.1. Swap With Neighbors

In this section, we prove that SWN is IR, IC and stable-cc.

{theorem}

SWN is IR.

Proof.

In SWN, agent $i$ can always choose herself as her favorite agent, and then SWN will allocate $h_{i}$ to $i$ . Thus, SWN is IR. ∎

{theorem}

SWN is IC.

Proof.

Since each agent $i$ ’s type consists of two parts, her preference $\succ_{i}$ and her neighbor set $r_{i}$ , we will prove misreporting neither $\succ_{i}$ nor $r_{i}$ can improve her allocation.

Misreport on $\succ$ : For agent $i$ , we fix her reported neighbor set as $r_{i}^{\prime}$ . Her real preference is $\succ_{i}$ and her reported preference is $\succ_{i}^{\prime}$ . Suppose her allocation $\pi_{i}((\succ_{i}^{\prime},r_{i}^{\prime}),\theta^{\prime}_{-i})=h_{j^{\prime}}\succ_{i}\pi_{i}((\succ_{i},r_{i}^{\prime}),\theta^{\prime}_{-i})=h_{j}$ .

In SWN, when $i$ truthfully reports her preference, agent $i$ is allocated $h_{j}$ instead of $h_{j^{\prime}}$ , we know that $h_{j^{\prime}}$ is in a trading cycle without $i$ . Let the cycle containing $j^{\prime}$ be $C_{j^{\prime}}$ . When we fix the others preference and $i$ misreports as $(\succ^{\prime}_{i},r_{i}^{\prime})$ , since the trading cycle $C_{j^{\prime}}$ is only determined by agents’ preference in $C_{j^{\prime}}$ , which excludes agent $i$ , $C_{j^{\prime}}$ still forms. By SWN, agent $i$ cannot be allocated $h_{j^{\prime}}$ , which contradicts our assumption.

Misreport on $r$ : For agent $i$ , we fix her reported preference as $\succ_{i}^{\prime}$ . Her real neighbor set is $r_{i}$ and her reported neighbor set is $r_{i}^{\prime}$ . Now we suppose her allocation $\pi_{i}((\succ_{i}^{\prime},r_{i}^{\prime}),\theta^{\prime}_{-i})=h_{j^{\prime}}\succ_{i}^{\prime}\pi_{i}((\succ_{i}^{\prime},r_{i}),\theta^{\prime}_{-i})=h_{j}$ .

In SWN, each agent can only be allocated the item from her reported neighbor set $r_{i}^{\prime}$ . Therefore, we have $j\in r_{i}$ , $j^{\prime}\in r_{i}$ and $j^{\prime}\in r_{i}^{\prime}$ . Since with true neighbor set $r_{i}$ , agent $i$ is allocated $h_{j}$ instead of $h_{j^{\prime}}$ , we know that $h_{j^{\prime}}$ is in a trading cycle without $i$ . Let the cycle containing $j^{\prime}$ be $C_{j^{\prime}}$ . According to SWN, each agent in $C_{j^{\prime}}$ is pointing to her neighbor, which means their neighbor set is irrelevant to $r_{i}$ as well as any $r_{i}^{\prime}$ . Therefore, the trading cycle $C_{j^{\prime}}$ still remains and excludes agent $i$ when agent $i$ misreports $r_{i}^{\prime}$ . By SWN, agent $i$ cannot be allocated $h_{j^{\prime}}$ , which contradicts our assumption.

Put the above two steps together, we prove that SWN is IC. ∎

{theorem}

SWN is stable-cc.

Proof.

For every $S\subseteq N$ and their item set $H_{S}$ . Let the allocation given by SWN be $\pi(\theta)$ . If there exists a blocking coalition $S$ , where $S\subseteq N$ is the node set of a complete component in $G(\theta)$ .

Since $S$ is the node set of a complete component, we have $\forall i\in S,S\subseteq r_{i}$ . A blocking coalition $S$ suggests there exists a $z(\theta)$ such that for all $i\in S$ , $z_{i}(\theta)\in H_{S}$ , $z_{i}(\theta)\succeq_{i}\pi_{i}(\theta)$ with at least one $j\in S$ we have $z_{j}(\theta)\succ_{j}\pi_{j}(\theta)$ . Therefore, for all $j\in S$ , the blocking coalition guarantees the owner of $z_{j}(\theta)$ and $j$ are neighbors. Based on SWN, $z_{j}(\theta)\succ_{j}\pi_{j}(\theta)$ means $j$ can always point to and get allocated $z_{j}(\theta)$ instead of $\pi_{j}(\theta)$ . Thus, the trading cycle which contains the owner of $z_{j}(\theta)$ and $j$ can trade by the cycle (i.e., $\forall i\in S,z_{i}(\theta)$ = $\pi_{i}(\theta)$ ). This contradicts the assumption of existing at least one $j\in S\subseteq r_{j},z_{j}(\theta)\succ_{j}\pi_{j}(\theta)$ . Hence, SWN is stable-cc. ∎

B.2. Leave and Share

In this section, we prove that LS is IR, IC and stable-cc.

{theorem}

For any order $\mathcal{O}$ , LS is 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, and then LS will allocate $h_{i}$ to $i$ . Thus, LS is IR. ∎

{theorem}

For any order $\mathcal{O}$ , LS is IC.

Proof.

Since each agent $i$ ’s type consists of two parts, her preference $\succ_{i}$ and her neighbor set $r_{i}$ , we will prove misreporting neither $\succ_{i}$ nor $r_{i}$ can improve her allocation.

Misreport on $\succ$ : For agent $i$ , we fix her reported neighbor set as $r_{i}^{\prime}$ . Her real preference is $\succ_{i}$ and her reported preference is $\succ_{i}^{\prime}$ . Now we compare her allocation $\pi_{i}((\succ_{i},r_{i}^{\prime}),\theta_{-i})=h_{j}$ with $\pi_{i}((\succ_{i}^{\prime},r_{i}^{\prime}),\theta_{-i})=h_{j^{\prime}}$ .

Since $\mathcal{O}$ is based on the minimum distance, which is irrelevant to agents’ preferences, we only need to prove that $h_{j}\succeq_{i}h_{j^{\prime}}$ for all agents for a given order.

Before $i$ is pushed into the stack, all trading cycles are irrelevant to $\succ_{i}^{\prime}$ ( $i$ has not been preferred by the agents in the stack before, so $\succ_{i}^{\prime}$ is not used at all). Thus we only consider the situation when agent $i$ is pushed into the stack and then $\succ_{i}^{\prime}$ 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 $\succ_{i}^{\prime}$ . Agent $i$ can be allocated with $h_{j^{\prime}}$ only when there is a trading cycle with $i$ . Assume that $h_{j^{\prime}}\succ_{i}h_{j}$ , i.e., misreporting $\succ_{i}$ gives $i$ a better item. We will show this leads to a contradiction. If $i$ reported $\succ_{i}$ truthfully, then $i$ would first choose $j^{\prime}$ before $j$ ( $j^{\prime}$ is pushed into the stack first), since $i$ did not get $h_{j^{\prime}}$ , which means $j^{\prime}$ formed a cycle $C_{j^{\prime}}$ without $i$ . If reporting $\succ_{i}^{\prime}$ , $i$ is matched with $j^{\prime}$ , then it must be the case that there exists another trading cycle $B$ which breaks the cycle $C_{j^{\prime}}$ . Otherwise, whenever $i$ points to $j^{\prime}$ , $j^{\prime}$ will form the original cycle $C_{j^{\prime}}$ 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 $\succ_{i}^{\prime}$ . 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^{\prime}}$ .

If $B$ can actually break $C_{j^{\prime}}$ , there must be an overlap between $B$ and $C_{j^{\prime}}$ . Assume that $x$ is the node where $B$ joins $C_{j^{\prime}}$ and $y$ is the node where $B$ leaves $C_{j^{\prime}}$ ( $x$ and $y$ can be the same node). For node $y$ , her match in $B$ and $C_{j^{\prime}}$ 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^{\prime}}$ are still there. Assuming the matching in $C_{j^{\prime}}$ is her favorite, then cycle $B$ will never be formed. This contradicts to $h_{j^{\prime}}\succ_{i}h_{j}$ , so reporting $\succ_{i}$ truthfully is a dominant strategy.

Misreport on $r$ : As the above showed for any reported neighbor set $r_{i}^{\prime}$ , reporting $\succ_{i}$ truthfully is a dominant strategy. Next, we further show that under truthful preference reports, reporting $r_{i}$ is a dominant strategy. That is, for the allocation $\pi_{i}((\succ_{i},r_{i}),\theta_{-i})=h_{j}$ and $\pi_{i}((\succ_{i},r_{i}^{\prime}),\theta_{-i})=h_{j^{\prime}}$ , we will show $h_{j}\succeq_{i}h_{j^{\prime}}$ .

Firstly, we show that the tradings before $i$ being pushed into the stack are irrelevant to $i$ ’s neighbor set report $r_{i}^{\prime}$ . For all the agents ranked before $i$ in $\mathcal{O}$ , 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}^{\prime}$ cannot change them. Thus, $r_{i}^{\prime}$ cannot change the order of all agents ordered before $i$ in $\mathcal{O}$ . In addition, agent $i$ could be a cut point to disconnect certain agents $D_{i}$ from agent $1$ , so $r_{i}^{\prime}$ 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}^{\prime}$ is. That is, when $i$ is pushed into the stack, the agents, except for $D_{i}$ , remaining in the game are independent of $i$ .

Then when $i$ misreports $r_{i}$ , she will only reduce her own options in the favorite agent selection. Whether $r_{i}^{\prime}$ disconnects $D_{i}$ or not, reporting $r_{i}^{\prime}$ here is equivalent to modifying $\succ_{i}$ by disliking neighbors in $r_{i}\setminus r_{i}^{\prime}$ . As we have shown, this is not beneficial for the agent. Therefore, reporting $r_{i}$ truthfully is a dominant strategy, i.e., $h_{j}\succeq_{i}h_{j^{\prime}}$ .

Put the above two steps together, we have proved that $\pi_{i}((\succ_{i},r_{i}),\theta_{-i})\succeq_{i}\pi_{i}((\succ_{i}^{\prime},r_{i}^{\prime}),\theta_{-i})$ , i.e., LS is IC. ∎

{theorem}

For any order $\mathcal{O}$ , LS is stable-cc.

Proof.

For every $S\subseteq N$ and their item set $H_{S}$ . Let the allocation given by LS be $\pi(\theta)$ . If there exists a blocking coalition $S$ , where $S\subseteq N$ is the node set of a complete component in $G(\theta)$ , we have $\forall i\in S,S\subseteq r_{i}$ . A blocking coalition $S$ suggests there exists a $z(\theta)$ such that for all $i\in S$ , $z_{i}(\theta)\in H_{S}$ , $z_{i}(\theta)\succeq_{i}\pi_{i}(\theta)$ with at least one $j\in S$ we have $z_{j}(\theta)\succ_{j}\pi_{j}(\theta)$ . Therefore, for all $j\in S$ , the blocking coalition guarantees the owner of $z_{j}(\theta)$ 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}(\theta)\succeq\pi_{j}(\theta)$ means the owner of $z_{j}(\theta)$ will be pushed into the stack before the owner of $\pi_{j}(\theta)$ . Thus, the trading cycle which contains the owner of $z_{j}(\theta)$ and $j$ can trade by the cycle (i.e., $\forall i\in S,z_{i}(\theta)$ = $\pi_{i}(\theta)$ ). This contradicts the assumption of existing $j\in S,z_{j}(\theta)\succ_{j}\pi_{j}(\theta)$ . Hence, LS is stable-cc. ∎

B.3. Connected Trading Cycles

In this section, we prove that CTC is IR, IC, and stable-cc. The proof for optimal-cc is in Section 5, Theorem 5.7.

{theorem}

For any order $\mathcal{O}$ , CTC is IR.

Proof.

In CTC, every agent $i$ can point to her endowment $h_{i}$ , and $i$ always has an exclusive path to herself so she does not have to switch her preference. Eventually, CTC will assign $h_{i}$ to $i$ . Thus, CTC is IR. ∎

{theorem}

For any order $\mathcal{O}$ , CTC is IC.

Proof.

In CTC, the path detection and preference switching process (in CTC step c) ensures each agent choose from her best possible choice (based on the next favorite function), and only switch pointing if all paths from herself to her pointing fail to be connected by an exclusive path. In path detection, while agent $i$ ’s path to her pointing $j$ overlaps with others, we constantly find all possible paths from $i$ to $j$ with ascending order in length. This means, $i$ cannot misreport neighbor set ( $r^{\prime}_{i}\subset r_{i}$ ) to add new paths to $j$ . Further, $i$ has no incentive to misreport neighbor set to exclude her competitor $i^{\prime}$ (i.e., $i$ can misreport $r^{\prime}_{i}\subset r_{i}$ so that $i^{\prime}$ who also points to $j$ is unqualified.) because in this case, all paths from $i^{\prime}$ to $j$ pass through $i$ . So, if $i$ and $i^{\prime}$ are competing for the same item $h_{j}$ , $i^{\prime}\to j$ overlaps with $i\to j$ , so $i^{\prime}$ will switch to a less preferred agents before $i$ does.

Suppose CTC is not IC, there must exist an agent $i\in N$ , when $i$ truthfully report her type, we have $\pi_{i}((\theta_{i},\theta^{\prime}_{-i}))=h_{j}$ , and $i$ can misreport to improve her matching, $\pi_{i}((\theta^{\prime}_{i},\theta^{\prime}_{-i}))=h_{j^{\prime}}\succ_{i}h_{j}$ .

We denote the cycle involving $i\to j$ as $C_{i}$ , suppose $\pi_{k}((\theta_{i},\theta^{\prime}_{-i}))=h_{i}$ and $\pi_{i}((\theta_{i},\theta^{\prime}_{-i}))=h_{j}$ . According to CTC step c.ii, we know that cycle $C_{i}$ is a connected cycle and each agent in $C_{i}$ has an exclusive path to her pointing.

Similarly, we denote the cycle formed under $i$ ’s misreport as $C^{\prime}_{i}$ , involving $i\to j^{\prime}$ . Suppose we have $\pi_{k^{\prime}}((\theta^{\prime}_{i},\theta^{\prime}_{-i}))=h_{i}$ and $\pi_{i}((\theta^{\prime}_{i},\theta^{\prime}_{-i}))=h_{j^{\prime}}$ . According to CTC step c.ii, we know that cycle $C^{\prime}_{i}$ is also a connected cycle and each agent in $C^{\prime}_{i}$ has an exclusive path to her pointing.

Since other agents type profiles are fixed as $\theta^{\prime}_{-i}$ , $j\to\cdots\to k\to i$ in cycle $C_{i}$ and $j^{\prime}\to\cdots\to k^{\prime}\to i$ in cycle $C^{\prime}_{i}$ form irrelevant of agent $i$ ’s reported type profile. Thus, following truthful type $\theta_{i}$ , agent $i$ will point to $j^{\prime}$ first ( $h_{j^{\prime}}\succ_{i}h_{j}$ ), so $C^{\prime}_{i}$ will form and get traded in CTC.

This contradicts our assumption which means CTC is IC. ∎

{theorem}

For any order $\mathcal{O}$ , CTC is stable-cc.

Proof.

For any given type profile $\theta$ , if the allocation $\pi(\theta)$ given by CTC violates stable-cc, there exists a group of agents $B$ that forms a complete component in $G(\theta)$ , they deviate together and swap among themselves can result in a better allocation $\pi^{\prime}(\theta)$ . Since group $B$ is a complete component, each agent $i$ can point to the owner of her allocation $\pi^{\prime}_{i}(\theta)$ through her outgoing edge (i.e., $\pi^{\prime}_{i}(\theta)=h_{j}$ , agent $i$ points to $j\in B$ ).

We next demonstrate that when agent $i\in B$ points to $\pi_{i}^{\prime}(\theta)$ , $i$ will not switch her pointing to a less preferred agent in CTC. Suppose during CTC’s execution, an agent $i\in B$ points to $j\in B,\pi_{i}^{\prime}(\theta)=h_{j}$ , let the connected component involving $i\to j$ be $T$ . Since $i\to j$ is $i$ ’s outgoing edge, whether $i\to j$ is exclusively marked by $i$ or not, $i$ is not in $S$ (refer to CTC step c). If $T=\emptyset$ (CTC step c.i), CTC will not let $i$ switch her pointing because $i$ can always connect to her pointing $j$ by her outgoing edge. If $S=\emptyset$ and $C_{m}=T$ (CTC step c.ii), CTC will let $C_{m}$ trade, so $i$ still does not switch points. If $S=\emptyset$ and $C_{m}\subset T$ (CTC step c.iii), since $i$ ’s pointing path passes no other agents, $i$ does not have to switch points. Finally, if $S\neq\emptyset$ (CTC step c.iv and c.v), since $i\notin S$ , CTC will not let $i$ switch her pointing.

That is to say, any agent $i\in B$ can hold her pointing to $\pi^{\prime}_{i}(\theta)$ , and CTC will allocate $\pi^{\prime}(\theta)$ . This means $\pi(\theta)=\pi^{\prime}(\theta)$ , which contradicts our assumption. ∎

B.4. Complexity Analysis

Proposition \thetheorem

The computation complexity of SWN is $O(N^{2})$ .

Proof.

In SWN, each agent points to the neighbor with her favorite item, and then we detect cycles in the constructed directed pointing graph with the computation cost of $O(N)$ . In the worst-case scenario, all agents are self-looped, the above process will be conducted $N$ times, so the computation complexity is $O(N^{2})$ . ∎

Proposition \thetheorem

The computation complexity of LS is $O(N^{2})$ .

Proof.

In LS, we first compute the shortest path length from each agent to the initial agent set to determine the order $\mathcal{O}$ . The corresponding computation complexity is $O(N^{2})$ . Next, following the order, at each turn, we start from the agent with the smallest order to form a cycle with a computation complexity of $O(N)$ . A stack is used to record the pointed agents, if a sequence of agents forms a cycle, they will be popped out of the stack (as in LS step b). Once the stack is empty, LS merges the remaining neighbors of the matched agents with a computation complexity of $O(N)$ (as in LS step c). In the worst-case scenario, all agents are self-looped, so the above process will be conducted $N$ times, and the total computation complexity is $O(N^{2})$ . ∎

Proposition \thetheorem

The computation complexity of CTC is $O(2^{N}\cdot N^{2})$ .

Proof.

In CTC, we first compute the order for each agent with a computation complexity of $O(N^{2})$ . Then, starting from the agent with the smallest order, CTC finds a cycle sequence $C_{m}$ in the favorite pointing graph with computation complexity of $O(N)$ (as in CTC step a). During the path detection process, the construction of minimum connected component $T$ requires a combination of all agents in $N\setminus C_{m}$ and a check on the connectedness for each combination attempt with computation complexity of $O(N^{2})$ , resulting in a computation cost of $O(2^{N}\cdot N^{2})$ (as in Path Detection step a). Next, CTC applies a marking process to determine whether each agent in $T$ has an exclusive path to her pointing to further distinguish the connectedness of $C_{m}$ (as in Path Detection step c,d). This process involves determining the shortest paths for all agents in $T$ , sorting the paths, and marking on a subgraph $G_{T}$ . Together, the computation cost for the marking process is $O(N^{2}\cdot NlogN)$ . Finally, with the marked $G_{T}$ , CTC determines which agent should switch her pointing to the next favorite or let the cycle $C_{m}$ get traded in $O(N)$ as in CTC step c. Hence, the computation complexity of CTC is $O(2^{N}\cdot N^{2})$ . ∎