A Strategy-proof Mechanism For Networked Housing Markets

Market design has been greatly influenced by the theory of house allocation mechanisms that allow agents to express preferences over houses and trade them without monetary compensation. Such a mechanism can be applied to various areas such as kidney exchange Roth et al. (2004); Sönmez et al. (2020), house allocation Shapley and Scarf (1974); Abdulkadiroğlu and Sönmez (1999), and so on. Therefore, it has attracted researchers from various fields, including economics, mathematics, and computer science.

In the groundbreaking paper, Shapley and Scarf (1974) first formulated the house allocation problem as a mechanism design problem and developed a well-known matching mechanism, Top Trading Cycle, which is strategy-proof (truthful reporting preference is a dominant strategy) and Pareto efficient (resources are allocated to the maximum level of efficiency). However, they considered the case in which all agents in the housing market are only invited by the organizer. With the significant improvement in communication tools, people are interacting with others more frequently and easily than ever before. It is natural to develop such a mechanism over social networks. Indeed, agents might be interested in inviting their friends to the housing markets in order to enrich their options.

The work of mechanism design over social networks has been initiated by Li et al. (2017). They revealed that increasing the number of participants can improve the revenue of an auction, which is consistent with the result of Bulow et al. (1996). Taking social networks into consideration in the mechanism design problem is promising and has been developed in various fields such as resource allocation Li et al. (2017), task collaboration Golle et al. (2001), matching Kawasaki et al. (2021).

An important open question in matching over a networked housing market is how to develop a mechanism that ensures agents report their information truthfully. For example, an agent might not invite his friends because they would compete for a house he prefers, which reduces other agents’ options. Such an issue was first discovered by Kawasaki et al. (2021). They restricted the preference domain and found that TTC simultaneously satisfies strategy-proof and Pareto efficient under such settings; otherwise, it fails to achieve a set of properties. However, restricting the preference domains contradicts the purpose of matching mechanisms over a networked housing market, which is to enrich agents’ options in order to obtain a better allocation.

This paper proposes a novel matching mechanism that ensures strategy-proof without sacrificing all agents’ preference domains. Indeed, we reveal the possible competition between inviters and invitees, which leads agents to benefit from misreporting. Inspired by the success of Top Trading Cycle Shapley and Scarf (1974) in traditional housing markets, we develop a matching mechanism based on TTC for networked housing markets, called Top Trading Cycle with Diffusion (TTCD). Aside from being strategy-proof, the allocation of TTCD is also stable, such that agents cannot improve from coalitions with their ancestors and descendants. We further show that TTCD has a promising number of swaps, which is preferable for organizers who charge for a swap.

The remainder of the paper is organized as follows. Section 2 reviews the relevant literature. Section 3 describes the model and a set of desirable properties. In Section 4, we briefly review the existing mechanisms and discuss the impossibilities. Section 5 proposes a novel matching mechanism and analyzes its properties. Section 6 provides the performance of TTCD by simulations. Finally, we conclude with some closing remarks and discuss possible future research in Section 7.

The seminal work Shapley and Scarf (1974) introduced house allocation as a mechanism design problem and proposed the Top Trading Cycle (TTC) mechanism as a solution with several desirable properties. Since then, the design of house allocation mechanisms and TTC have received much attention from both researchers and practitioners. Roth (1982) proved that TTC is strategy-proof, individually rational, and Pareto efficient. Furthermore, Ma (1994) verified the result of Roth (1982) and showed that TTC is the only mechanism that satisfies all those properties.

Several variations of TTC have been studied in the literature. For instance, Alcalde-Unzu and Molis (2011) generalized the TTC algorithm to the case in which agents are allowed to report indifference in preference. Morrill (2015) characterized the TTC in terms of justness, which allows students with higher priority to veto an objection. Hakimov and Kesten (2018) proposed an Equitable TTC in order to eliminate avoidable justified envy situations.

Mechanism design over social networks has been well studied in various fields such as marketing and auction. For example, Emek et al. (2011) proposed a geometrical reward mechanism for marketing in which agents are rewarded for successfully referring others to purchase a product. Li et al. (2017) introduced an auction over social networks that satisfies several important properties. For more details, readers can refer to the work of Zhao (2021) and the references therein. These studies demonstrate the potential of mechanism design with social networks as a valuable direction of research.

The study of mechanism design in networked housing markets was pioneered by Kawasaki et al. (2021). They revealed that it is impossible for a mechanism to be strategy-proof and Pareto efficient over a networked housing market. As a response, they proposed a modified TTC, which restricts the preference domain of all agents. Gourvès et al. (2017); Zheng et al. (2020) studied the networked housing market where agents are only allowed to trade with their neighbors. You et al. (2022) modified the algorithm of Abdulkadiroğlu and Sönmez (1999) for a house allocation problem with existing tenants and social networks. Later on, Yang et al. (2022) extended the work of Kawasaki et al. (2021) into a graph network and enlarged the preference domain of agents who fail to invite others.

Consider a house allocation problem in a social network that consists of an organizer $o$ and a set of $n$ agents $N=\{1,2,...,n\}$. For each agent $i\in N$, he is endowed with a house $h_{i}$, and the set of all houses is denoted as $H=\{h_{1},h_{2},...,h_{n}\}$. Note that the organizer $o$ is not endowed with any house.

For each agent $i\in N$, he has a set of children $r_{i}\subseteq N$. Each agent $i\in N$, he has a strict preference $\succ_{i}$ over houses $H$, where $h_{j}\succ_{i}h_{i}$ represents that agent $i$ prefers house $j$ over house $i$. Therefore, we denote $\theta_{i}=(\succ_{i},r_{i})$ as the type of agent $i$.

Agents are asked to report their types as part of the mechanism. We denote $\theta^{\prime}_{i}=(\succ^{\prime}_{i},r^{\prime}_{i})$ as the report type of agent $i$ under the mechanism. Specifically, it is impossible to spread the information of the barter market to a non-existing child. Hence, $r^{\prime}_{i}\subseteq r_{i}$. Let $\theta^{\prime}=(\theta^{\prime}_{1},\theta^{\prime}_{2},...,\theta^{\prime}_{n})=(\theta^{\prime}_{i},\theta^{\prime}_{-i})$ be the reported types of all agents, and $\theta^{\prime}_{-i}$ is the reported types of all agents excluding agent $i$. We denote $\Theta=(\Pi\times r)$ be the reported type space of all agents, where $\Pi$ is the preference list and $r$ action spaces on reporting children.

For a given report profile $\theta^{\prime}$, we generate a directed graph $G(\theta^{\prime})=(V(\theta^{\prime}),E(\theta^{\prime}))$, where $V(\theta^{\prime})\subseteq N\cup\{o\}$, and edge $e(i,j)\in E(\theta^{\prime})$ means that agent $i$ invites agent $j$ to join the barter market ($j\in r^{\prime}_{i}$). In particular, an agent can only join the market if all his ancestors are in the market and decide to invite their children. Without loss of generality, we assume that the organizer $o$ invites all his children $r_{o}$.

The organizer $o$ aims to design a mechanism with a matching policy that incentivizes agents to invite their children to join the barter market in order to provide a broader range of options for the exchange. A matching policy $x=(x_{i})_{i\in N}$ is a redistribution of houses to the agents, where $x_{i}(\theta^{\prime})\in H$ is the house allocated to agent $i$ under matching $x$. Let $X$ be the set of all possible allocations.

Given the above settings, the networked housing market is a tuple $(N,\Pi,r)$, and the formal definition of a matching mechanism under a networked market is defined as

So far, we have defined the set of desirable properties that a matching mechanism should satisfy. In this section, we briefly review the existing matching mechanisms over networked housing markets.

Moreover, we demonstrate that it is not possible for a matching mechanism over a networked housing market to simultaneously achieve IR, SP, and PE without restrictions on agents’ preferences. Additionally, we also characterize the competition between inviters and invitees, leading to a mechanism that fails to satisfy SP.

Before introducing the matching mechanisms in detail, the following are some fundamental definitions and notations:

• •

  A directed edge points from a parent node to a child node. (e.g., $a$ is the parent of $c$, and $c$ is the child of $a$ in Figure 1.)

• •

  An ancestor (descendant) node of a node is either the parent (child) of the node or the parent (child) of some ancestor (descendant) of the node. (e.g., $a$ is the ancestor of $e$, and $e$ is the descendant of $a$.)

• •

  Nodes with the same parent are called siblings. (e.g., $c$ is the sibling of $d$.)

Given the impossibility results in Section 4.5, TTC fails to achieve IR, SP, and PE over a networked housing market. Moreover, we also explain how to restrict agents’ preferences in order to keep the matching mechanism SP. Therefore, we propose a novel algorithm based on traditional TTC, which is called Top Trading Cycle with Diffusion (TTCD), in order to overcome the aforementioned challenges.

As highlighted by Kawasaki et al. (2021), the presence of multiple paths to an agent can result in strategic behavior and incompatibility. For example, agents may strategically accept invitations from others. To simplify our analysis, we focus on the social network, which is a directed tree rooted at organizer $o$. (For graph networks, see Appendix.) Furthermore, we allow the organizer to invite multiple agents, which is not well discussed in related literature.

TTCD is easy to understand, and it works similarly to traditional TTC. For agent $i\in r_{o}$ invited by the organizer, they are free to select any house owned by their descendants and siblings. For other agents, if there are no conflicts between agents and their ancestors/descendants, they are free to select any house in the corresponding tree branch. (Recall our analysis focuses on a directed tree network rooted at the organizer $o$.)

Moreover, steps $3$, $4$, and $5$ prevent the conflicts in Theorem 2 and guarantee all agents cannot be worse off from inviting others. Compared with the mechanisms in Kawasaki et al. (2021); Yang et al. (2022), the preference restriction in our mechanism is less strict. This makes our mechanism more efficient and flexible than other existing mechanisms.

We demonstrate a running process of TTCD by using the example shown in Figure 2. The preference list is given in Table 1.

• •

  Figure 2(a) is the directed tree rooted at organizer $o$.

• •

  All agents point to their most preferred house available in the market, which is shown in Figure 2(b). Note that agent $9$ cannot point to $h_{2}$, as it is pointed by his ancestor agent $5$. (Recall steps $1$, $2$, $3$, and $4$.)

• •

  After the first iteration, agents $1$, $3$, $4$, $6$, $7$, and $9$ are removed from the market.

• •

  Agent $2$’s most preferred house in the market is now $h_{8}$.

• •

  The allocation of agents $N=\{1,2,3,4,5,6,7,8,9,10\}$ is houses $X=\{h_{7},h_{8},h_{6},h_{4},h_{2},h_{1},h_{3},h_{10},h_{9},h_{5}\}$.

In this section, we start with a random example to show the advantages of TTCD compared with other existing mechanisms (modified TTC, Leave and Share, and YRMH-IGYT). Then, we numerically compare these mechanisms by simulations.

Considering the social network in Figure 3. The following are the allocations for each mechanism.

• •

  modified TTC: $x_{1}=h_{1}$, $x_{2}=h_{3}$, $x_{3}=h_{2}$, $x_{4}=h_{5}$, and $x_{5}=h_{4}$.

• •

  Leave and Share (LaS): $x_{1}=h_{4}$, $x_{2}=h_{3}$, $x_{3}=h_{2}$, $x_{4}=h_{1}$, and $x_{5}=h_{5}$.

• •

  YRMH-IGYT: $x_{1}=h_{4}$, $x_{2}=h_{3}$, $x_{3}=h_{2}$, $x_{4}=h_{1}$, and $x_{5}=h_{5}$.

• •

  TTCD: $x_{1}=h_{5}$, $x_{2}=h_{3}$, $x_{3}=h_{2}$, $x_{4}=h_{1}$, and $x_{5}=h_{4}$.

Although TTCD does not always promise a Pareto efficient allocation, in Figure 3, the allocation of TTCD Pareto dominates the allocations of other existing mechanisms.

In this paper, we study a matching mechanism over a networked housing market and propose a novel mechanism called Top Trading Cycle with Diffusion (TTCD). In other existing matching mechanisms, they limit all agents’ preference domains in order to ensure the truthfulness of the mechanism. We characterize the possible competitions between inviters and invitees, resulting in an untruthful mechanism. Under TTCD, we update the policy based on the traditional TTC in order to avoid all those competitions. As a result, TTCD is strategy-proof which minimizes the restrictions on the preference domain. Besides other desirable properties, it maximizes the agents’ satisfaction and the number of swaps.

Promising future work includes considering an allocation problem over social networks with monetary transfers and budget.