Object Allocation via Swaps along a Social Network

1 Introduction

Allocating indivisible resources to agents is a fundamental problem in AI [Chevaleyre et al., 2006], which lies at the interface of computer science and economics. When the set of solutions is restricted to the allocations where each agent receives a single resource, this problem corresponds to a specific type of matching under preferences [Manlove, 2013; Klaus et al., 2016], called onesided matching. The specificity of the one-sided matching lies on the fact that the resources have no preferences over the possible allocations, on the contrary of two-sided matching. One-sided matchings have been widely studied under different names: assignment problem [Gardenfors, 1973], house allocation [Abdulkadiroˇglu and S¨onmez, 1998]. When each agent is initially endowed with a resource, the problem is known in the literature as the housing market problem [Shapley and Scarf, 1974]. Starting from the initial endowment and performing a sequence of exchanges among the agents is a standard approach to reallocate the resources. The top-trading cycle algorithm and its variants [Shapley and Scarf, 1974; Abdulkadiroˇglu and S¨onmez, 1999; Aziz and De Keijzer,

2012] exploit this idea in order to compute a better allocation. Another way to grasp the problem is by letting the agents perform the exchanges by themselves. A rich literature has been developed on this approach, formalizing conditions for realistic trades and analyzing the quality of the possible outcomes [Sandholm, 1998; Dunne et al., 2005; Chevaleyre et al., 2005; Endriss et al., 2006; Chevaleyre et al., 2007; Dunne and Chevaleyre, 2008; Chevaleyre et al., 2008; Aziz et al., 2016]. Most part of this literature is devoted to general resource allocations where agents typically receive bundles of resources, but only a few articles specifically address the housing market problem [Damamme et al., 2015].

In the housing market setting, it is implicitly assumed that all the agents have the capacity to perform direct deals. This assumption is unlikely in large scale instances, where some agents are unable to communicate. Restricting the set of direct exchanges to the ones which are actually possible seems more realistic and relevant in large scale instances. The ability of agents to exchange resources can be modeled as a social network [Jackson, 2008; Easley and Kleinberg, 2010]. Recent works on matching have investigated the use of a social network in order to capture other types of social behavior such as altruism [Anshelevich et al., 2013], social contact [Arcaute and Vassilvitskii, 2009], peer effects [Bodine-Baron et al., 2011] or collaboration [Hoefer, 2013]. Most of these works focus on two-sided matchings and, up to our knowledge, only a few articles are devoted to resource allocation. In this line, the notion of negotiation topology graph [Chevaleyre et al., 2007], where the exchanges are restricted to agents belonging to the same clique of the social network, is noteworthy.

This article deals with a variant of housing market, where the agents are embedded in a social network which determines their ability to exchange their objects. Each participant is initially endowed with a single object, and she has strict ordinal preferences over objects. The agents may exchange their items under two conditions: they find it mutually profitable, and they are socially tied. Though sophisticated exchanges involving multiple agents have been analyzed [Sandholm, 1998; Dunne and Chevaleyre, 2008; Damamme et al., 2015], we focus on simple trades between pairs of neighbors.

The exchanges are made without payments or monetary compensations. Our main question is, starting from the initial endowment, which allocation of the objects can emerge? Indeed, some solutions are ruled out because of the agents' preferences over the objects (e.g. no one is interested in exchanging her current object with something that she considers as worse). In addition, the network limits the access of certain participants to each other. Therefore, it is particularly challenging to understand how the combination of these two natural ingredients influence the outcome of a dynamics in which connected agents agree on mutually profitable swaps of objects. Moreover, it appears interesting to consider the quality of a resulting allocation by sequence of profitable exchanges. In the context of ordinal preferences, Paretoefficiency appears as the minimal requirement for an allocation to be socially acceptable. Pareto-efficiency has been widely studied in the context of house allocation [Abraham et al., 2005] and housing market [Aziz et al., 2016]. As far as we know, the computation of Paretoefficient allocations has not been investigated when the possible allocations are constrained by a social network.

The paper is organized as follows. The model of object allocation along a social network is defined in Section 2, as well as the problems under consideration. Then, in Section 3, we address the problem of reachability for an object and in Section 4 the reachability of a given full allocation. Before concluding, the search of Paretoefficient allocations is investigated in Section 5.

2 Model

2.1 Notations

Let N = {1, . . . n} be a set of agents and X = {x1, . . . , xn} be a set of objects such that |N| = |X| = n. An allocation is a bijection σ : N → X, where σ(i) denotes the object assigned to agent i in σ. We may write σ as an n-tuple σ = (σ(1), . . . , σ(n)). Each agent is initially endowed with an object; σ0 denotes this initial allocation. We assume w.l.o.g. that σ0(i) = xi for every agent i. Each agent i ∈ N has strict preferences over the objects, represented by a strict linear order ≻i over X. The agents' preference profile is denoted by ≻.

Let G = (N, E) be an undirected graph representing a social network over the agents, where the edges capture the possibility of communication and trade between two agents. An instance is a tuple (N,X,≻,G, σ0).

2.2 Swap Dynamics

In this article we focus on rational trades between pairs of agents. A trade between two agents is rational if both agents benefit by exchanging their objects. An allocation σ′ results from a rational trade from σ for agents i and j if σ′ (i) = σ(j), σ′ (j) = σ(i), σ′ (i) ≻i σ(i) and σ′ (j) ≻j σ(j), and for any agent k /∈ {i, j}, σ′ (k) = σ(k).

We assume that every trade is necessarily performed between two neighbors in the network. Rational trades defined according to G are called swaps. An assignment σ′ results from a swap from σ w.r.t. G = (N,E) if there exist two agents i and j such that (i, j) ∈ E and σ′ is a rational trade from σ for i and j.

A sequence of swaps is a sequence of assignments (σ0, σ1, σ2, . . . , σt) such that for any k ∈ {1, . . . , t}, σk results from a swap from σk-1. An allocation σ is stable if no swap can be performed from σ.

From σ0, represented by squares within the preferences, agents 1 and 2 can perform a swap: they are linked and they both prefer the object of the other. The same holds for agents 2 and 3. If agents 1 and 2 exchange their objects (bold arrow in the figure), we obtain allocation σ1. From σ1, only agents 2 and 3 can perform a swap, leading to allocation σ2. In σ2, agents 1 and 4 prefer the object of the other but they are not connected in G, thus this exchange is not feasible. No swap is possible in σ2, hence σ2 is stable.

An assignment σ′ is reachable if there exists a sequence of swaps (σ0, . . . , σt) such that σt = σ′ . Let us denote by RA the set of all reachable assignments. By extension, an object x ∈ X is reachable for an agent i ∈ N if there is a sequence of swaps (σ0, . . . , σt) such that σt(i) = x.

Swap dynamics is a distributed process where, starting from σ0, the agents exchange their objects without any external intervention, until a stable allocation is reached.

2.3 Issues

In order to analyze the distributed process of swap dynamics, we are interested in all the allocations obtained from σ0 by sequences of swaps. The following two decision problems naturally arise from our model.

The swaps dynamics always converges to a stable allocation. However, the following example shows that we can reach a rather bad assignment if the agents exchange their objects in an uncoordinated way.

Example 2 Consider an instance with n agents. The network and the preferences are described below.

Consider allocation σ1 resulting from the swap between agents n-1 and n. The center agent n obtains her most preferred object, thus no further swap is possible and σ1 is stable. However, if we consider the sequence of swaps performed by the pairs of agents (n,1),(n,2),. . . ,(n,n-2), (n,n-1), then we reach an allocation σ′ where every agent obtains her most preferred object.

An allocation σ is Pareto-efficient if there is no assignment σ′ such that for all i ∈ N, σ′ (i) ⪰i σ(i) and there exists j ∈ N such that σ′ (j) ≻j σ(j). We restrict the definition of Pareto-efficiency within the set RA of reachable allocations, otherwise a Pareto-efficient allocation in the standard meaning may not be reachable.

As informally noticed in Example 2, swap dynamics can reach an allocation that is Pareto dominated. This observation also leads us to consider the swap dynamics under a centralized perspective. The swaps, though constrained by the social network and the mutual benefit for the two involved agents, are guided by a coordinator, in order to reach a Pareto-efficient allocation among all reachable allocations. Consequently, we also study the following optimization problem.

3 Reachable Object

In this section we focus on Reachable Object. We prove that the problem is NP-complete even when the network is a tree. However, for some further restrictions on the graph, the problem becomes polynomial.

First observe that in any network, an object cannot pass twice by the same agent. This is derived from the definition of a swap where both agents are better off.

Observation 1 If for a reachable assignment σ and an agent i, σ(i) ̸= σ0(i) then in any assignment σ′ reachable from σ, σ′ (i) ̸= σ0(i).

Theorem 1 Reachable Object is NP-complete even when the network is a tree.

Sketch of proof: One can easily verify that the problem is in NP. We use a reduction from the NP-complete problem 2P1N-SAT [Yoshinaka, 2005]. In 2P1N-SAT, we are given a set V = {v1, . . . , vn} of variables, and a collection C = {C1, . . . ,Cm} of clauses over V such that each positive (resp., negative) literal occurs exactly 2 (resp., 1) times in C. Is C satisfiable?

Let vik (resp., vik ) denote the positive (resp., negative) literal vk if present in Ci. Index pkj (resp., nk ) refers to the clause containing the j th occurrence (j ∈ {1, 2}) of vk (resp., the occurrence of vk).

We construct an instance (N,X,≻,G, σ0) of Reachable Object as follows. Each literal vik (resp., vik ) is associated with an agent Xik (resp., Xik ) which is initially endowed with object xik (resp., xik ). Every clause Ci is associated with an agent Ci initially endowed with object ci. We add an agent T initially endowed with object t, leading to |N| = |X| =m+3n+1. The graph G = (N,E) is as follows.

The preference profile ≻ is defined below. We only represent the objects that each agent prefers to her initial one, and {ℓi} denotes the set of the objects associated with the literals of clause Ci, which are ranked in arbitrary order.

Now, we have an instance of Reachable Object and we claim that C is satisfiable iff t is reachable for Cm. The details of the equivalence are omitted.

Observe, on one hand, that in the dipath τ from T to Cm, every agent prefers t to her initial object, and only accepts to exchange t with an object of her successor in τ, corresponding to a literal that satisfies the clause associated with the successor. Therefore, the only way to move t from T to Cm is to give to each agent Ci an object associated with a literal that satisfies the clause Ci. Thus, for i = 1 to m, an object of {ℓi} moves to Ci.

On the other hand, we ensure in each branch corresponding to a variable vk, that if an object xik (resp., xjk ) moves out of the branch, then an object xi′ k (resp., xj ′ k ) cannot move out thereafter. Indeed, if xnk k is the first object to move out of the branch, then agent Xpk1 k obtains her most preferred object and no other object in this branch can move out. Otherwise, if xpk1 k or xpk2 k moves first, then agent Xpk1 k has received an object that she prefers to xnk k , so xnk k is blocked. ■

The network in the previous proof is a tree where all the subtrees derived from a common root are paths (called generalized star thereafter). Nevertheless, Reachable Object is solvable in polynomial time when the network is a star.

Proposition 1 When G is a star, there exists a polynomial algorithm for Reachable Object.

Proof: The problem asks whether agent i can get object x. The network consists of a center denoted by n, and n1 leaves denoted by 1, . . . , n-1. A swap always involves the center and a leaf. Once a leaf has exchanged her initial object, she is not involved in a subsequent swap (Observation 1). Thus, any sequence of swaps reduces to an ordered list (without repetition) of leaves, indicating with which agents the center exchanges her object.

Let us first focus on the case where agent i is the center. The problem reduces to the search of a path in a digraph GD = (N,E′ ) where (a, b) ∈ E′ with a ∈ N and b ∈ N \ {n} iff the center and leaf b can rationally trade when the center owns the initial object of a while b owns her initial object. There is a path from n to b in the digraph iff the center can get the initial object of agent b. A linear algorithm solves this path problem and the construction of the digraph is polynomial.

In case i is a leaf, the problem reduces to the previous one: the center gets x and then, i and n swap their objects. Return "yes" if these two steps are feasible. ■

Now we suppose that the network is a path. Each time G is a path, we assume that E = {(j, j + 1) : 1 ≤ j < n}. Observation 1 implies that when G is a path, once an object "moves" in a given direction, then it cannot "move" in the opposite direction.

Let us define as canonical sequence of exchanges κ(j, k) the sequence of exchanges which assigns object xj to agent k by directly moving it along the dipath from j to k. This is the sequence of exchanges between the following pairs of agents if j < k: (j, j+1), (j+1, j+ 2), . . . , (k -1, k). It transforms σ0 into an assignment σ where σ(ℓ) = xℓ if ℓ < j, σ(ℓ) = xℓ+1 if j ≤ ℓ < k and σ(k) = xj. This sequence is said to be a sequence of swaps if all its exchanges are rational.

Proposition 2 When G is a path, if object xj is reachable for agent n, then κ(j, n) is a sequence of swaps.

Proof: Assume by contradiction that there exists k ∈ {j +1, . . . , n} such that the exchange between k-1 and k is not rational i.e., xk ≻k xj or xj ≻k-1 xk.

Assume first that xk ≻k xj holds. Note that if there exists a sequence of swaps leading to assign xj to n, then xj must be assigned once to agent k since the path from j to n is unique. Because xk ≻k xj, agent k will never accept xj, contradiction.

Assume now that xj ≻k-1 xk holds. If there exists a sequence of swaps leading to assign xj to n, then xj must be exchanged once with xk, because xj must reach n and there is no agent after n to receive xk. This swap cannot be performed between k-1 and k since xj ≻k-1 xk, and thus occurs between some agents before k. Consequently, agents k-1 and k must have performed an earlier swap in order to make xk moving to the agents with lower indices than k. After this swap, the object currently owned by k - 1 must move to the direction of n before xj, and xj cannot overtake this object, contradiction. ■

For testing that an object is reachable for a leaf of the path, it suffices to verify that the associated canonical sequence of exchanges is a sequence of swaps.

Corollary 1 When G is a path and agent i a leaf of G, Reachable Object is solvable in polynomial time.

Other solvable cases of Reachable Object in a path can be listed. The main one is when the distance between the agent and the object is a constant. We omit the details due to the space limitation but they essentially rely on the following observations. If agent i tries to get object xj, with i < j, then we can ignore agent k and object xk, for k > j. If one can guess which set N ′ ⊂ N of agents eventually get the objects of {xk : i ≤ k < j}, then we can deduce the final allocation: for two agents a, b ∈ N ′ such that a < b, the object received by agent a must have a smaller index than the object received by agent b. It suffices to test whether the final allocation is reachable, a problem that is solved in polynomial time in the next section (Proposition 3).

Despite its apparent simplicity, Reachable Object in a path is a challenging open problem when no restriction on the agent's location is made. We believe that this case is at the frontier of tractability.

4 Reachable Assignment

In this section, we address the decision problem Reachable Assignment: does σ belong to RA? We prove that this problem is NP-complete in general but polynomial when the network is a tree.

Theorem 2 Reachable Assignment is NPcomplete.

Proof: One can easily verify that the problem is in NP. We propose a reduction from Reachable Object. Take an instance I = (N,X,G,≻, σ0). The problem asks whether an agent (called 1 w.l.o.g.) can reach a given object (called xℓ thereafter). We construct an instance of Reachable Assignment I ′ = (N ∪ N ′ ,X ∪ X′ ,G′ ,≻′ , σ′0 ) where each element of N (resp., X) has a copy in N ′ (resp., X′ ). The copies of j and xj are denoted by j ′ and x′j , respectively. The edge set of G′ is a superset of E and each j ′ ∈ N ′ has an edge with every k ∈ N ′ ∪ {j}. The initial assignment σ′0 is such that σ′0 (j) = σ0(j) when j ∈ N, and σ′0 (j) = x′j when j ∈ N ′ . For every j ∈ N, ≻′j consists of x′j on top, followed by ≻j , and the remaining objects are put on the last positions. For the agents of N ′ , the preferences ≻′ are defined as follows.

We claim that xℓ is reachable for agent 1 in I iff every agent gets her most preferred object in I ′ .

Suppose that xℓ is reachable for agent 1 in I. By construction, it is also the case in I ′ . Once xℓ has reached agent 1, every agent j ∈ N exchanges her object with her copy j ′ ∈ N ′ . Thus, each j ∈ N possesses her most preferred object x′j . The same holds for agent 1′ . Then, by starting with ℓ′ and afterwards considering every j ′ by increasing order of indices, j ′ exchanges her object with the current owner of her most preferred object. Those exchanges are swaps by construction.

Suppose that every agent can get her most preferred object in I ′ . Agent 1′ must receive xℓ after an exchange with agent 1 because no agent in N ′ \ {1′ } prefers xℓ to her initial object. For the same reason, xℓ cannot reach 1′ through the agents of N ′ \ {1′ }. The preferences and the network topology impose that no object of X′ can be involved in the move of xℓ to agent 1. ■

In the previous reduction, we have constructed a graph which contains cycles. When G is a tree, a polynomial algorithm (Algorithm 1) solves Reachable Assignment.

The global idea of the algorithm is that every object must move along a unique dipath in order to reach its owner in σ from its owner in σ0. Therefore, it suffices to verify that every dipath intersects another one of the opposite direction within a swap for the involved agents. In the pseudocode, list L stores the first arc of each dipath and pop(P) outputs the first arc of dipath P and deletes this arc from P.

Algorithm 1:

Input: (N,X,≻,G, σ0), assignment σ Output: whether σ is reachable from σ0 1 L← ∅; σ′ ← σ0; 2 for each x ∈ X do 3 Px ← the unique dipath from the owner of x in σ0 to the owner of x in σ; 4 L←L∪ {pop(Px)}; 5 while L ̸= ∅ do 6 if ∃i,j∈N,i̸=j : (i, j), (j, i) ∈ L then 7 if (σ′ (i) ≻i σ′ (j)) ∨ (σ′ (j) ≻j σ′ (i)) then 8 return false; 9 Update σ′ with exchange between i and j; 10 L ← L \ {(i, j), (j, i)}; 11 L ← L ∪ {pop(Pσ′ (i))} ∪ {pop(Pσ′ (j))}; 12 else return false; 13 return true;

Let us illustrate Algorithm 1 with an example.

At each step L stores the first arc of each Pxi . At step 1, only one exchange is possible: between agents 2 and 4. This exchange being rational, σ′ is updated by performing the swap. Arcs (2, 4) and (4, 2) are removed from L. Arcs (4, 5) and (2, 1), which are respectively the new first arcs of Px2 and Px4 , are inserted in L. The algorithm stops when L is empty, implying that σ is reached.

Proposition 3 Algorithm 1 solves Reachable Assignment in polynomial time when G is a tree.

Proof: Consider an instance with a minimum number of agents where σ is reachable but Algorithm 1 returns "false". Let s be a feasible sequence of swaps from σ0 to σ. The allocation reached by Algorithm 1 is denoted by σ′ . Since some objects have not reached their destination in σ′ , L is non empty at the end of the execution.

Case 1. L contains no pair of opposite arcs. Start from a node x such that σ(x) ̸= σ′ (x) and follow the arcs of L. Since G is acyclic, the walk is finite and ends with an arc, say (a, b). Object σ′ (a) must pass through agent b to reach it owner in σ, but object σ′ (b) has reached its destination (no arc goes out of b because σ′ (b) = σ(b)).

Because a unique path links two nodes in a tree, we know that in s, agent a exchanges σ′ (a) with an object held by agent b. Suppose this object is assigned in σ′ to agent c. It holds that σ′ (c) ̸= σ′ (b) and σ′ (c) ≻a σ′ (a).

Consider the path τ from a to c in G. Suppose b ∈ τ. By considering b as the root of G, we observe that a and c belong to two distinct subtrees. Moreover, σ′ (c) ̸= σ(c) and σ′ (a) ̸= σ(a). Therefore by removing σ′ (a) or σ′ (c), we get a smaller counterexample to Algorithm 1, contradiction. Now suppose b /∈ τ. Since σ′ (c) passes through b then a in s, a has been assigned σ′ (c) before getting σ′ (a), which implies that σ′ (a) ≻a σ′ (c), contradiction. Case 2. Two opposite arcs (a, b), (b, a) belong to L but σ′ (a) ≻a σ′ (b) . In s, agent a exchanges σ′ (a) with an object held by agent b. Suppose this object is assigned in σ′ to agent c. It holds that σ′ (c) ̸= σ′ (b) and σ′ (c) ≻a σ′ (a). Since σ′ (c) passes through (b, a) in s, if a has been assigned σ′ (c) before getting σ′ (a), then σ′ (a) ≻a σ′ (c), contradiction. If a has not been assigned σ′ (c) before getting σ′ (a), then σ′ (c), together with σ′ (a) and σ′ (b), has not reached its destination. Thus, a smaller counterexample without one of these objects exists. ■

5 Pareto-Efficient Allocations

The question of this section is how to coordinate the swaps in order to reach a Pareto-efficient allocation within RA. Note that a Pareto-efficient allocation is stable, otherwise at least two agents will benefit from a possible swap. However, the reverse does not hold, as we can see in Example 2 with allocation σ1 that is stable but Pareto dominated by another reachable allocation.

Proposition 4 Pareto is NP-hard.

Proof: The reduction is the same as in the proof of Theorem 2. I is a yes-instance iff every agent gets her most preferred object in I ′ (which must be the unique Paretoefficient assignment). Therefore, an algorithm computing a Pareto-efficient assignment can be used to recognize a yes-instance of Reachable Object. ■

This negative result does not prevent the existence of a polynomial algorithm for constructing a Pareto-efficient allocation in a specific class of instances. The remainder of this section is devoted to the resolution of Pareto in a path and in a star.

A classical algorithm for achieving Pareto-efficiency is Serial Dictatorship [Abdulkadiroˇglu and S¨onmez, 1998]. It ranks the agents in an arbitrary manner, and assigns them in turns their most favorite object within the set of unassigned objects, until each object is assigned. When the social network is a path, one can use this idea to compute a Pareto-efficient allocation within RA.

Algorithm 2:

Input: (N,X,≻,G, σ0), agent k Output: an assignment σ 1 if k = 1 then 2 return σ0; 3 xi ← best reachable object for k; 4 σ ← apply κ(i, k) on σ0; 5 return Algorithm 2 ((N,X,≻,G, σ), k -1);

The parameter k of Algorithm 2 designates the dictator who chooses her best reachable object, and κ(i, k) is the canonical sequence (see Proposition 2).

Proposition 5 When G is a path, Algorithm 2 with k = n solves Pareto in polynomial time.

Sketch of proof: The algorithm starts with a leaf of the path, modifies the current allocation in such a way that the leaf agent obtains her best object (Corollary 1 is used), and continues on the subpath from k-1 to 1. The proof is by induction on k: when the decision for agent k is made, the partial allocation for agents {k+1, . . . , n} is Pareto-efficient. ■

Now we study the case of a star. The network consists of a center denoted by n, and n - 1 leaves denoted by 1, . . . , n- 1 (see Example 2 for an illustration). We can suppose w.l.o.g. that ∀i < n, xi ≻n xi+1. Indeed, if xn ≻n xj for some j then the center will never exchange her object with j, so j keeps her object in any sequence of swaps. The algorithm is simple: for i = n - 1 down to 1, exchange the objects of n and i if it is rational.

Proposition 6 When G is a star, there exists a linear time algorithm for Pareto.

Proof: As already mentioned, a leaf who has exchanged her initial object is not involved in a subsequent swap. The algorithm considers the objects by increasing order of preference of the center agent. Suppose by contradiction that the allocation σ returned by the algorithm is Pareto dominated by another reachable allocation σ′ . Let us denote by s and s′ the sequences of exchanges leading respectively to σ and σ′ . The key observation is that any feasible sequence of swaps is performed by decreasing index of the leaves. In the first step for which s and s′ differ, the center swaps her object with ℓ and ℓ′ , respectively. Since ℓ < ℓ′ , ℓ and n cannot swap their object in s′ . Therefore σ(ℓ) ≻ℓ σ′ (ℓ), contradiction. ■

It appears interesting to see if Pareto is polynomial time solvable in a generalized star by a combination of the techniques used to solve the cases of paths and stars.

6 Conclusion

We have investigated some natural problems arising when a group of agents exchange their object along a social network. Our results show that, beyond the agents' preferences, the network can widely influence and constrain the possible allocations. In particular, we proved that deciding whether an agent can obtain a given object (Reachable Object) is computationally difficult, even if the network is a tree. Nevertheless, an efficient algorithm can determine if a complete allocation (Reachable Assignment) is reachable in a tree. Concerning simple graph structures like paths, we were able to decide if a leaf agent can acquire a given object. This result can be extended to the case where the distance between a non-leaf agent and the original location of the object is bounded by a constant. We left open the question whether Reachable Object can be efficiently solved in a path, without restriction on the agent's location.

In this article, the social quality of reachable allocations has also been studied through the search of Paretoefficient allocations. This problem is shown difficult in general networks. On the positive side, polynomial algorithms have been presented for paths and stars. It seems challenging to settle the complexity of computing a Pareto-efficient allocation when the network is a tree.

As future works, many additional aspects of the model deserve attention. For example, we have not investigated the impact if some agents adopt a strategic behavior. Reasoning strategically can drive an agent to refuse a profitable deal (e.g. in a lookahead search). It would also be important to study the social welfare of the feasible allocations. Beyond Pareto-efficiency, is it hard to optimize the egalitarian or the utilitarian social welfare? Like in the price of anarchy/stability, how bad a stable outcome can be, compared to an allocation that is not constrained by the social network? Another future direction is to allow more than two agents to exchange their objects along the network and see which allocations emerge. Finally, our work does not assume any restriction on the preference domain (e.g. single peakedness or single crossingness) which may fit well with our model.