# object_reachability_via_swaps_along_a_line__3910bdbb.pdf

The Thirty-Third AAAI Conference on Artiﬁcial Intelligence (AAAI-19)

Object Reachability via Swaps along a Line

Sen Huang, Mingyu Xiao

School of Computer Science and Engineering University of Electronic Science and Technology of China {huangsen47, myxiao}@gmail.com

The HOUSING MARKET problem is a widely studied resources allocation problem. In this problem, each agent can only receive a single object and has preferences over all objects. Starting from an initial endowment, we want to reach a certain assignment via a sequence of rational trades. We consider the problem whether an object is reachable for a given agent under a social network, where a trade between two agents is allowed if they are neighbors in the network and no participant has a deﬁcit from the trade. Assume that the preferences of the agents are strict (no tie is allowed). This problem is polynomially solvable in a star-network and NPcomplete in a tree-network. It is left as a challenging open problem whether the problem is polynomially solvable when the network is a path. We answer this open problem positively by giving a polynomial-time algorithm. Furthermore, we show that the problem on a path will become NP-hard when the preferences of the agents are weak (ties are allowed).

Introduction Allocating indivisible objects to agents is an important problem in both computer science and economics. A widely studied setting is that each agent can only receive one single object and each agent has preferences over objects. This problem was previously called ASSIGNMENT problem (Gardenfors 1973; Wilson 1977) and now we prefer to call it HOUSE ALLOCATION problem (Abdulkadiro glu and S onmez 1998; Manlove 2013). When each agent is initially endowed with an object and we want to reallocate objects under some conditions without any monetary transfers, the problem is known as HOUSING MARKET problem (Shapley and Scarf 1974). HOUSING MARKET has several real-life applications such as allocation of housings (Abdulkadiro glu and S onmez 1999), organ exchange (Roth, S onmez, and Unver 2004) and so on. There are two different preference sets for agents. One is strict, which is a full ordinal list of all objects, and the other one is weak, where agents

The corresponding author and supported by the National Natural Science Foundation of China, under grants 61772115 and 61370071. Copyright c 2019, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

are allowed to be indifferent between objects. Both preference sets have been widely studied. Under strict preferences, the celebrated Top Trading Cycle rule (Shapley and Scarf 1974) has several key desirable properties. Some modiﬁcations of Top Trading Cycle rule, called Top Trading Absorbing Sets rule and Top Cycles rule, were introduced for weak preferences (Alcalde-Unzu and Molis 2011; Jaramillo and Manjunath 2012), which also hold some good properties. More studies of HOUSING MARKET under the two preference sets from different aspects can be found in the literature (Jaramillo and Manjunath 2012; Aziz and De Keijzer 2012; Saban and Sethuraman 2013; Ehlers 2014; Sonoda et al. 2014; Ahmad 2017). Some rules allow a single exchange involving many agents. It is natural and fundamental to consider exchanges being bilateral deals (swaps), i.e., each exchange of objects happens only between two agents. A swap between two agents is allowed when they are mutually beneﬁcial from the exchange. This natural rule for HOUSING MARKET has been studied in the literature (Damamme et al. 2015; Gourv es, Lesca, and Wilczynski 2017). In some models, it is implicitly assumed that all agents have a tie with others. However, some agents often do not know each other and do not have the capacity to exchange even they can mutually get beneﬁts. So Gourv es, Lesca, and Wilczynski (2017) studied HOUSING MARKET where the agents are embedded in a social network to denote the ability to exchange objects between them. In fact, recently it is a hot topic to study resources allocation problems over social networks and analyze the inﬂuences of networks. Abebe, Kleinberg, and Parkes (2017) and Bei, Qiao, and Zhang (2017) introduced social network of agents into the FAIR DIVISION problem of cake cutting. Bredereck, Kaczmarczyk, and Niedermeier (2018) and Beynier et al. (2018) also considered network-based FAIR DIVISION in allocating indivisible resources. In this paper, we study HOUSING MARKET in a social network with simple trades between pairs of neighbors in the network. In this model, there are the same number of agents and objects and each agent is initially endowed with a single object. Each agent has preferences over all objects. The agents are embedded in a social network which determines

their ability to exchange their objects. Two agents may swap their items under two conditions: they are neighbors in the social network, and they ﬁnd it mutually proﬁtable (or no one will become worse under weak preferences). We focus on OBJECT REACHABILITY under this model: to determine whether an object is reachable for a given agent from the initial endowment via swaps. Damamme et al. (2015) ﬁrstly proved that the problem is NP-hard even to decide whether any one of a subset of objects is reachable for each agent. Gourv es, Lesca, and Wilczynski (2017) further showed that OBJECT REACHABILITY is polynomially solvable under star-structures and NP-complete under tree-structures. For the network being a path, they solved the special case where the given agent is an endpoint (a leaf) in the path and left it unsolved for the general case. All the above results are under strict preferences. In this paper, we will answer this open problem positively by giving a polynomial-time algorithm for OBJECT REACHABILITY in a path under strict preferences, and also prove that OBJECT REACHABILITY in a path under weak preferences is NP-hard. Although paths are rather simple graph structures, OBJECT REACHABILITY in a path is not easy at all, as mentioned in (Gourv es, Lesca, and Wilczynski 2017) that Despite its apparent simplicity, REACHABLE OBJECT (OBJECT REACHABILITY) 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. Our algorithm involves several techniques and needs to call solvers for the 2-SAT problem, but it is still interesting. The following part of the paper is organized as follows. Section 2 provides some backgrounds. Section 3 tackles the reachability of an object for an agent in a path-network under strict preferences. Section 4 shows the NP-hardness of OBJECT REACHABILITY in a path under weak preferences. The proofs of the lemmas and theorems marked with are omitted due to the limitation of space, which can be found in the full version of this paper.

Background Model. There are a set N = {1, ..., n} of n agents and a set O = {o1, ..., on} of n objects. An assignment σ is a mapping from N to O, where σ(i) is the object held by agent i in σ. We also use σT (oi) to denote the agent who holds object oi in σ. Each agent holds exactly one object at all time. Initially, the agents are endowed with objects, and the initial endowment is denoted by σ0. We assume w.l.o.g that σ0(i) = oi for every agent i. Each agent has preferences regarding objects. A strict preference is expressed as a full linear order of all objects. Agent i s preference is denoted by i, and oa i ob indicates the fact that agent i prefers object oa than object ob. The whole strict preference proﬁle for all agents is represented by . For weak preferences, agents are allowed to be indifferent between objects. For two disjoint subsets of objects S1 and S2, we use S1 i S2 to indicate that all objects in S1 (resp., S2) are indifferent for agent i and agent i prefer any object in S1 than any object in S2. We use oa i ob to denote that agent i likes oa at least as same as ob. Two relations oa i ob and ob i oa together imply that oa and

ob are indifferent for agent i. We may use to denote the whole weak preference proﬁle for all agents. Let G = (N, E) be an undirected graph as the social network among agents, where the edges capture the capability of communication and exchange between two agents. An instance of HOUSING MARKET is a tuple (N, O, , G, σ0) or (N, O, , G, σ0) according to the preferences being strict or weak.

Dynamics. The approach we take in this paper is dynamic, and we focus on individually rational trades between two agents. A trade is individual rational if each participant receives an object at least as good as the one currently held, i.e., for two agents i and j and an assignment σ, the trade between i and j on σ is individual rational if σ(j) i σ(i) and σ(i) j σ(j). We require that every trade is performed between neighbors in the social network G. Individual rational trades deﬁned according to G are called swaps. A swap is an exchange, where two participants have the capability to communicate. A sequence of swaps can be represented as a sequence of assignments (σ0, σ1, σ2, ..., σt) such that for any i {1, ..., t}, σi results from a swap from σi 1. An assignment σ is reachable if there exists a sequence of swaps (σ0, σ1, σ2, ..., σt) such that σt = σ . An object o O is reachable for an agent i N if there is a sequence of swaps (σ0, σ1, σ2, ..., σt) such that σt(i) = o.

Problems. We consider the problem of checking whether an object is reachable for an agent from the initial endowment via swaps.

OBJECT REACHABILITY Instance: (N, O, , G, σ0), an agent k N, and an object ol O. Question: Whether is object ol reachable for agent k?

When the preferences are strict, we call the problem STRICT OBJECT REACHABILITY. When the preferences are weak, we call the problem WEAK OBJECT REACHABILITY. When the social network is a path P, we call the problem OBJECT REACHABILITY in a path. For OBJECT REACHABILITY in a path, an instance will be denoted by I = (N, O, , P, σ0, k N, ol O), where we assume w.l.o.g that l < k. For path structures, we always assume w.l.o.g that the agents are listed as 1, 2, . . . , n on a line from left to right with an edge between any two consecutive agents. Below is an example for OBJECT REACHABILITY in a path. Example 1. There are four agents. The path structure, preference proﬁle and a sequence of swaps are given below.

P : 1 2 3 4 1 : o2 o1 o3 o4 σ0 : o1 o2 o3 o4 2 : o4 o3 o1 o2 σ1 : o2 o1 o3 o4 3 : o1 o4 o3 o2 σ2 : o2 o3 o1 o4 4 : o3 o1 o2 o4

The initial endowments for agents are denoted by squares

within the preferences. After a swap between agents 1 and 2 from σ0 we get σ1 and after a swap between agents 2 and 3 from σ1 we get σ2. The object o1 is reachable for agent 3.

STRICT OBJECT REACHABILITY in a Path STRICT OBJECT REACHABILITY is known to be NPcomplete when the network is a tree and polynomially solvable when the network is a star (Gourv es, Lesca, and Wilczynski 2017). It is left unsolved whether the problem with the network being a path is NP-hard or not. We reveal some properties of STRICT OBJECT REACHABILITY under the path structure and design a polynomial time algorithm for it. In the remaining part of this section, we assume that the preferences are strict and the network is a path. Recall that the problem is to check whether an object ol is reachable for an agent k with l < k. The main idea of our algorithm is as follows. First, we show that the instance is equivalent to the instance after deleting all agents (and the corresponding endowed objects) on the left of agent l. Thus, we can assume the problem is to check whether object o1 is reachable for an agent k. Second, we prove that if o1 is reachable for agent k then there is an object on with n k that should be moved to agent k 1 in the ﬁnal assignment and we can ignore all agents and objects on the right of agent n . We guess n by letting it be each possible value between k and n and get at most n candidate instances. These instances are called neat (o1, on , k)-CONSTRAINED instances. A neat (o1, on , k)-CONSTRAINED instance contains only n agents and it is to check whether there is a reachable assignment σ , called compatible assignment, such that σ (k) = o1 and σ (k 1) = on . Third, we are going to ﬁnd compatible assignments. In a neat (o1, on , k)- CONSTRAINED instance, in every compatible assignment each object oi will be moved to either the left or the right of its original position in the path. We prove that for each direction, there is at most one possible position il (or ir for the right direction) for each object oi. We can compute il and ir directly in polynomial time. Since there are still two possible ﬁnal positions for each object, we do not get a feasible assignment yet. Fourth, we reduce the subproblem to 2-SAT and determine which of il and ir should be chose for each agent i by solving a 2-SAT instance. We show that each feasible assignment obtained in this step is corresponding to a reachable assignment for the neat (o1, on , k)- CONSTRAINED instance. Finally, we can solve the original problem in polynomial time, because the original instance is a yes-instance if and only if at least one of the candidate neat (o1, on , k)-CONSTRAINED instances is a yes-instance. In fact, when the preferences are strict, we have the following observations and lemmas. Observation 1. Given a sequence of swaps (σ0, σ1, . . . , σt) and an agent j N. For any i {0, 1, . . . , t 1}, it holds either σi+1(j) = σi(j) or σi+1(j) j σi(j). It implies the following lemma. Lemma 1. Given a sequence of swaps (σ0, σ1, . . . , σt). For any two integers i < j in {0, 1, . . . , t} and any agent q N, if σi(q) = σj(q), then σd(q) = σi(q) for any integer i d j.

Lemma 1 also says that an object will not visit an agent twice. This property is widely used in similar allocation problems under strict preferences. Next, we analyze properties under the constraint that the social network is a path. In a swap, the moving of an object is on the right direction if it is moved from agent i to agent i + 1, and the moving of an object is on the left direction if it is moved from agent i to agent i 1. In each swap, one object is moved on the right direction and one object is moved on the left direction. We study the tracks of the objects in a feasible assignment sequence.

Lemma 2. For a sequence of swaps (σ0, σ1, . . . , σt), if σT t (oi) = j for an object oi, then there are exactly |j i| swaps includes oi. Furthermore, all the |j i| movings of oi are on the right direction if i < j, and all the |j i| movings of oi are on the left direction if i > j.

Lemma 3. Let (σ0, σ1, . . . , σt) be a sequence of swaps, and oa and ob be two objects with a < b. Let a = σT t (oa) and b = σT t (ob). If a a or b b, then a < b .

Lemma 1 shows that any object can only move on one direction. Lemma 3 shows that when an object moves on the right direction, all objects initially allocated on the left of it can not move to the right of it at any time; when an object moves on the left direction, all objects initially allocated on the right of it can not move to the left of it at any time. In fact, if we want to move an object ol to an agent k with k > l, we may not need to move any object on the left of ol, i.e., objects ol with l < l. Equipped with Lemma 3, we can prove

Lemma 4. If object ol is reachable for agent k, then there is a feasible assignment sequence (σ0, σ1, . . . , σt) such that σT t (ol) = k, and σt(i) = σ0(i) for all i < l if l k and for all i > l if l k.

For an instance I = (N, O, , P, σ0, k, ol) of STRICT OBJECT REACHABILITY in a path with l < k, let I = (N , O , , P , σ 0, k, ol) denote the instance obtained from I by deleting agents {1, 2, . . . , l 1} and objects {o1, o2, . . . , ol 1}. In other words, we let N = {l, l + 1, . . . , n}, O = {ol, ol+1, . . . , on}, and , P and σ 0 be the corresponding subsets of , P and σ0.

Lemma 5. Object ol is reachable for agent k in the instance I if and only if object ol is reachable for agent k in the instance I .

By Lemma 5, we can always assume that the instance of STRICT OBJECT REACHABILITY in a path is to check whether the object o1 is reachable for an agent k. Assume that object o1 is reachable for agent k. For a sequence of swaps (σ0, σ1, . . . , σt) such that σt(o1) = k, there are exactly k 1 swaps including o1 which are moving o1 on the right direction according to Lemma 2. The last swap including o1 will be happened between agent k 1 and agent k. Let on denote the other object included in the last swap. In other words, after the last swap, agent k 1 will get the object on and agent k will get the object o1. Note that the moving of on in this swap is in the left direction. By Lemma 2, we know that all movings of on in the sequence of swaps

are in the left direction. Therefore, we have the following observation.

Observation 2. It holds that n k.

Our idea is to transform our problem to the following constrained problem: to determine whether there is a reachable assignment σ such that σ(k 1) = on and σ(k) = o1, where n k. We do not know the exact value of n . So we search by letting n be each value in {k, k + 1, . . . , n}. This will only increase the running time bound by a factor of n. We denote the above constrained problem by (o1, on , k)- CONSTRAINED problem.

Lemma 6. An instance I = (N, O, , P, σ0, k, o1) is yes if and only if at least one of the (o1, on , k)-CONSTRAINED instances for n {k, k + 1, . . . , n} is yes.

For an (o1, on , k)-CONSTRAINED instance I, we use I n to denote the instance obtained from I by deleting agents {n + 1, n + 2, . . . , n} and objects {on +1, on +2, . . . , on}.

Lemma 7. An (o1, on , k)-CONSTRAINED instance I is yes if and only if the instance I n is yes.

By Lemma 7, we can ignore all agents on the right of n in an (o1, on , k)-CONSTRAINED instance. An (o1, on , k)- CONSTRAINED instance is called neat if n is the last agent. We may simply consider neat (o1, on , k)-CONSTRAINED instances only. For any two integers a and b, we use [a, b] to denote the set of integers between a and b (including a and b).

Lemma 8. Let (σ0, σ1, . . . , σt) be a sequence of swaps, and oa and ob be two objects with a < b. Let a = σT t (oa), b = σT t (ob) and Q = [a, a ] [b, b ]. Assume that Q = . (a) If a > a and b > b, it holds that oa q ob for all q Q. (b) If a < a and b < b, it holds that ob q oa for all q Q.

See Figure 1 for an illustration for Lemma 8(a).

1 . . . a . . . b . . . q . . . a . . . b . . . n

Figure 1: An illustration for Lemma 8(a)

Lemma 9. Let (σ0, σ1, . . . , σt) be a sequence of swaps for a neat (o1, on , k)-CONSTRAINED instance such that σT t (o1) = k and σT t (on ) = k 1, and oa and ob be two objects with a < b. Let a = σT t (oa) and b = σT t (ob). Assume that a > a, b < b and Q = [a, a ] [b, b ] = . Let Q = [a + 1, a ] [b, b ]. (a) There is a swap including oa and ob which happens between agent c 1 and c, where c = a + b k + 1 Q . (b) It holds that ob q oa for all max(a, b ) q < c, and oa q ob for all c q min(a , b).

See Figure 2 for an illustration for Lemma 9.

1 . . . a . . . b . . . c 1 c . . . a . . . b . . . n q ob q oa

Figure 2: An illustration for Lemma 9

Given a neat (o1, on , k)-CONSTRAINED instance and an assignment σt such that σT t (o1) = k and σT t (on ) = k 1. We show some conditions for σt to be a feasible assignment. For any two objects oa and ob, we let a = σT t (oa) and b = σT t (ob). We say oa and ob are intersected if Q = [a, a ] [b, b ] is not an empty set. There are three kinds of intersections, which are corresponding to Lemma 8(a), Lemma 8(b) and Lemma 9. We say a pair of objects oa and ob (a < b) are compatible in assignment σt if there are either not intersected or intersected and satisfying one of the follows: 1. when a > a and b > b, it holds that a < b (corresponding to Lemma 3) and oa q ob for all agents q Q (corresponding to Lemma 8(a)); 2. when a < a and b < b, it holds that a < b (corresponding to Lemma 3) and ob q oa for all agents q Q (corresponding to Lemma 8(b)); 3. when a > a and b < b, it holds that c = a +b k+1 Q = Q \ {a}, ob q oa for all max(a, b ) q < c, and oa q ob for all c q min(a , b) (corresponding to Lemma 9). An assignment σ is compatible if it holds σ(i) = oi for any agent i and any pair of objects in it are compatible. Lemma 3, Lemma 8 and Lemma 9 directly imply that Lemma 10. If σt is a reachable assignment for a neat (o1, on , k)-CONSTRAINED instance such that σT t (o1) = k and σT t (on ) = k 1, then σt is compatible. Lemma 11. Let σt be a compatible assignment for a neat (o1, on , k)-CONSTRAINED instance such that σT t (o1) = k and σT t (on ) = k 1. For any two objects ox 1 and ox, if σT t (ox 1) > x 1 and σT t (ox) < x, then the swap between agents x 1 and x in σ0 is feasible. Let σ1 denote the assignment after the swap between x 1 and x in σ0. Then σt is still compatible by taking σ1 as the initial endowment.1

Based on Lemma 11 we will prove the following lemma. Lemma 12. Let σt be an assignment for a neat (o1, on , k)-CONSTRAINED instance such that σT t (o1) = k and σT t (on ) = k 1. If σt is compatible, then σt is a reachable assignment. By Lemma 12, to solve a neat (o1, on , k)-CONSTRAINED instance, we only need to ﬁnd a compatible assignment.

1If the swap is happened between agents 1 and 2, then object o1 will be moved to agent 2 in σ1 and we will may not be able to get an (o1, on , k)-CONSTRAINED instance by letting σ1 be the initial endowment. For this case, we will delete agent 1 and object σ1(1) to keep object o1 in the ﬁrst agent. More details will be given in the full version.

Computing Compatible Assignments In a compatible assignment, object o1 will be assigned to agent k and object on will be assigned to agent k 1. We consider other objects oi for i {2, 3, . . . , n 1}. In a compatible assignment, object oi will not be assigned to agent i since each agent will attend in at least one swap including object o1 or on . There are two possible cases: oi is assigned to agent i such that i < i; oi is assigned to agent i such that i > i. We say that oi is moved to the left side for the former case and moved to the right side for the latter case. We will show that for each direction, there is only one possible position for each object oi in a compatible assignment. First, we consider i {2, 3, . . . , k 1}. Assume that object oi is moved to the left side in a compatible assignment. Thus, o1 and oi are intersected and the intersection is of the case in Lemma 9. We ﬁnd the index i such that i i, oi i 1 o1 and o1 j oi for each j {i , i + 1, . . . , i}. We can see that i is the only possible agent for object oi to make o1 and oi are compatible if oi is moved to the left side. We use il to denote this agent if it exists for i. Assume that object oi is moved to the right side in a compatible assignment. Since o1 will be moved to agent k and oi will be moved to the right side, by Lemma 3 we know that oi will be moved to the right of o1, i.e., an agent i with i > k. Thus, oi and on are intersected and the intersection is of the case in Lemma 9. We ﬁnd the index i such that i > k, oi i on and on j oi for each j {k 1, k, . . . , i 1}. We can see that i is the only possible agent for object oi to make on and oi are compatible if oi is moved to the right side. We use ir to denote this agent if it exists for i. Second, we consider i {k, k + 1, . . . , n 1}. In fact, the structure of neat (o1, on , k)-CONSTRAINED instances is symmetrical. We can rename the agents on the path from left to right as {n , n 1, . . . , 1} instead of {1, 2, . . . , n } and then this case becomes the above case. We can compute il and ir for each i {k, k + 1, . . . , n 1} in a similar way. Therefore, we can compute il and ir for all i {2, 3, . . . , n 1} if they exist. If none of il and ir exists for some i, then this instance is a no-instance. If only one of il and ir exists, then object oi must be assigned to this agent in any compatible assignment. The hardest case is that both of il and ir exist, where we may not know which agent the object will be assigned to in the compatible assignment. For this case, we will rely on algorithms for 2-SAT to ﬁnd possible solutions. For each agent j, we will use Rj to store all possible objects that may be assigned to agent j in a compatible assignment. We use the following procedure to maintain Rj. Initially, we let Rk 1 = {on }, Rk = {o1}, and Ri = for all other agent i. Then for each i {2, 3, . . . , n 1}, we compute il and ir and add oi into Ril and Rir. After this, we can do the following to make the size of each Rj at most 2. While there is a set Rj0 becoming an empty set, stop and report the instance is a no-instance; while there is a set Rj0 containing only one object oi0 and the object oi0 appears in two sets Rj0 and Rj 0, delete oi0 from Rj 0. The correctness of the third step is based on the fact that agent j0 should get one object. If there is only one candidate object oi0 for agent j0, then oi0 can only be assigned to agent

j0, no possible to agent j 0. We also analyze the running time of the above procedure to compute Rj. For each object oi, we can compute il and ir in O(n). Therefore, we use O(n2) time to set the values for all sets Rj in the ﬁrst two steps. To update Ri, we may execute at most n iterations in the third step and each iteration can be executed in O(n). Therefore, the procedure running times in O(n2) time.

Lemma 13. After the above procedure, either the instance is a no-instance or it holds that 1 |Rj| 2 for each j {1, 2, . . . , n }.

For a set Rj containing only one object oi, we know that the object oi should be assigned to agent j in any compatible assignment. For sets Rj containing two objects, we still need to design which object is assigned to this agent such that we can get a compatible assignment. We will reduce the remaining problem to 2-SAT. The instance contains n variables {x1, x2, . . . , xn } corresponding to the n objects. When xi = 1, it means that the object oi moves on the right direction, i.e, we will assign it to the agent ir in the compatible assignment. When xi = 0, it means that the object oi moves on the left direction and we will assign it to the agent il in the compatible assignment. We have two kinds of clauses, called agent clauses and compatible clauses. For each set Rj, we associate |Rj| literals with it. If there is an object oi such that il = j, we associate literal xi with Rj; if there is an object oi such that ir = j, we associate literal xi with Rj. For each set Rj of size 1 (let the associated literal be ℓj), we construct one clause containing only one literal cj : ℓj. For each set Rj of size 2 (let the associated literals be ℓ1 j and ℓ2 j), we construct two clauses cj1 : ℓ1 j ℓ1 j and cj2 : ℓ1 j ℓ2 j. These clauses are called agent clauses. The agent clauses are to guarantee that exactly one object is assigned to each agent. For each pair of sets Rj and Ri, we construct several clauses according to the deﬁnition of compatibility. For any two objects oj Rj (the corresponding literal associated to Rj is ℓj) and oi Ri (the corresponding literal associated to Ri is ℓi), we say that ℓj and ℓi are compatible if oj and oi are compatible when oj is assigned to agent j and oi is assigned to agent i in the assignment. If ℓj and ℓi are not compatible, then either oj cannot be assigned to agent j or oi cannot be assigned to agent i in any compatible assignment. So we construct one compatible clause: ℓj ℓi for each pair of incompatible pair ℓj and ℓi. Since each set contains at most two objects, for each pair of sets Rj and Ri, we will create at most 2 2 = 4 clauses. In fact, when there are four clauses for a pair, the instance will become a no-instance, since no matter what objects assigned to agents j and i, there is no compatible assignment. In the following example, we will illustrate the construct of agent clauses and compatible clauses. We can see that each clause contains at most two literals and then the instance is a 2-SAT instance. The construction of 2-SAT instances implies that

Lemma 14. The 2-SAT instance has a feasible assign-

ment if and only if the corresponding neat (o1, on , k)- CONSTRAINED instance has a compatible assignment.

The main steps of the whole algorithm to solve STRICT OBJECT REACHABILITY in a path are listed in Algorithm 1. The correctness of the algorithm follows from Lemma 5, Lemma 6, Lemma 7 and Lemma 14. Next, we analyze the running time bound of it. The dominating part of the running time is taken by the computation for neat (o1, on , k)- CONSTRAINED instances. Next, we consider the running time used for solving each neat (o1, on , k)-CONSTRAINED instance. By the above analysis, we use O(n2) time to compute the ﬁnal values for all sets Rj. To construct 2-SAT instance, we construct at most 2n agent clauses in O(n) time and construct at most 4 n 2 compatible clauses, each of which will take O(n) time to check the compatibility. So the 2-SAT instance can be constructed in O(n3) time. We use the O(n+m)-time algorithm for 2-SAT (Aspvall, Plass, and Tarjan 1979) to solve our instance, where m = O(n2). There are at most n neat (o1, on , k)-CONSTRAINED instances. In total, we use O(n4) time.

Theorem 1. STRICT OBJECT REACHABILITY in a path can be solved in O(n4) time.

Algorithm 1: Main steps to solve STRICT OBJECT REACHABILITY in a path

Input: An instance (N, O, , P, σ, k N, o1 O) Output: To determine whether o1 is reachable for k

1 for k n n do

2 Construct the neat (o1, on , k)-CONSTRAINED instance by deleting agent i and object oi for all n < i n;

3 Compute ir and il for all 1 i n if it exist according to Lemma 9;

4 Construct the set Rj of all possible objects that may be assigned to each agent j according to the result in the above step, where Rk 1 = {on } and Rk = {o1};

5 Iteratively update Rj according to the procedure before Lemma 13;

6 Construct a 2-SAT instance as follows: construct a variable for each object, construct agent clauses according to Rj, and construct compatible clauses for all incompatible pairs;

7 Determine whether the 2-SAT instance is satisﬁable;

8 if the 2-SAT instance is yes then

9 return yes;

10 return no.

We give an example to show the steps to compute a compatible assignment for a neat (o1, on , k)-CONSTRAINED instance.

Example 2. Consider a neat (o1, on , k)-CONSTRAINED instance with n = 8 and k = 5 as the top right ﬁgure. We compute ir and il for all 1 i n by the above pro-

1 : o2 o8 o7 o1 2 : o5 o3 o4 o1 o8 o2 3 : o6 o4 o1 o8 o5 o3 4 : o8 o1 o6 o3 o2 o7 o5 o4 5 : o1 o8 o3 o7 o6 o4 o2 o5 6 : o3 o2 o5 o8 o4 o6 7 : o4 o6 o2 o8 o1 o3 o7 8 : o7 o3 o5 o4 o1 o8

cedure, the values of which are listed in the top right table.

agent i 1 2 3 4 5 6 7 8 il - 1 2 3 2 3 - 4 ir 5 6 6 7 6 7 8 -

We construct Rj for each agent j according to this table, and then update them as doing in the procedure. After the update, it holds that 1 |Rj| 2 for all 1 j n . We reduce the remaining problem to 2-SAT. The agent clauses for each set Rj are given in the last column of the table.

Set Initial Updated Agent clauses R1 {o2} {o2} x2 R2 {o3, o5} {o3, o5} x3 x5, x3 x5 R3 {o4, o6} {o4, o6} x4 x6, x4 x6 R4 {o8} {o8} x8 R5 {o1} {o1} x1 R6 {o2, o3, o5} {o3, o5} x3 x5, x3 x5 R7 {o4, o6} {o4, o6} x4 x6, x4 x6 R8 {o7} {o7} x7

Next, we construct compatible clauses for all incompatible pairs. We check all pairs of objects and ﬁnd that there are only two incompatible cases: o4 and o5 are incompatible if o4 and o5 are moved to agent 3 and agent 2, respectively; o4 and o5 are incompatible if o4 and o5 are moved to agent 7 and agent 6, respectively. The compatible clauses are

x4 x5 and x4 x5.

By using the O(n + m) time algorithm for 2-SAT (Aspvall, Plass, and Tarjan 1979), we get a feasible variables assignment (1, 0, 0, 0, 1, 1, 1, 0) for the 2-SAT instance. The corresponding swap sequence constructed via variables assignment above is given below. Remark: Although Step 4 of our algorithm will compute possible values il and ir for each i, it does not mean that object oi must be reachable for il or ir. In the above example, object o2 is not reachable for agent 2r = 6 since agent 3 prefers its initial object o3 to o2 and then o2 cannot go to the right direction. In our algorithm, the compatible clauses can avoid assigning an object to an unreachable value il or ir. In the above example, if object o2 goes to agent 6, then some object oi with i > 2 will go to agent 1 or 2 and we will get an incompatible pair o2 and oi.

σ0 : o1 o2 o3 o4 o5 o6 o7 o8 σ1 : o2 o1 o3 o4 o5 o6 o7 o8 σ2 : o2 o3 o1 o4 o5 o6 o7 o8 σ3 : o2 o3 o4 o1 o5 o6 o7 o8 σ4 : o2 o3 o4 o1 o5 o6 o8 o7 σ5 : o2 o3 o4 o1 o5 o8 o6 o7 σ6 : o2 o3 o4 o1 o8 o5 o6 o7 σ7 : o2 o3 o4 o8 o1 o5 o6 o7

P : 1 2 3 4 5 6 7 8

WEAK OBJECT REACHABILITY in a Path

We have proved that STRICT OBJECT REACHABILITY in a path is polynomially solvable. Next, we show that WEAK OBJECT REACHABILITY in a path is NP-hard. One of the most important properties is that Lemma 1 will not hold for WEAK OBJECT REACHABILITY and an object may visit an agent more than one time. Our proof is a modiﬁcation of the reduction in (Gourv es, Lesca, and Wilczynski 2017) to prove the NP-hardness of STRICT OBJECT REACHABILITY in a tree.

Theorem 2. WEAK OBJECT REACHABILITY is NP-hard even when the network is a path.

We give a reduction from the known NP-complete problem 2P1N-SAT (Yoshinaka 2005). In a 2P1N-SAT instance, we are given a set V = {v1, v2, . . . , vn} of variables and a set C = {C1, C2, . . . , Cm} of clauses over V such that every variable occurs 3 times in C with 2 positive literals and 1 negative literal. The question is to check whether there is an variable assignment satisfying C. For a 2P1N-SAT instance ISAT , we construct an instance IW OR of WEAK OBJECT REACHABILITY on a path such that ISAT is a yes-instance if and only if IW OR is a yes-instance. The instance IW OR contains 6n + m + 1 agents and objects, which are constructed as follows. There is an agent named T. For each clause Ci (i {1, . . . , m}), we introduce an agent also named Ci. For each variable vi, we add six agents, named as X ni i , Xpi i , Xqi i , A3 i , A2 i and A1 i . They form a path of length 5 in the order as showed below. We call the path a block and denote it by Bi. The names of the six agents have certain meaning: X ni i means that the negative literal of vi appears in the clause Cni; Xpi i and Xqi i mean that the positive literals of vi appear in the two clauses Cpi and Cqi; A3 i , A2 i and A1 i are three auxiliary agents.

X ni i X pi i X qi i A3 i A2 i A1 i Bi

The whole path is connected in the order showed below.

Bn . . . B1 Cm . . . C1 T

In the initial assignment σ0, object t is assigned to agent T, object ci is assigned to agent Ci for i {1, 2, . . . , m}, object aj i is assigned to agent Aj i for each i {1, 2, . . . , n} and j {1, 2, 3}, and oni i (resp., opi i and oqi i ) is assigned to agent X ni i (resp., Xpi i and Xqi i ) for each i {1, 2, . . . , n}. Next, we deﬁne the preference proﬁle . We only show the objects that each agent prefers at least as its initial one and all other objects can be put behind its initial endowment in any order. The initial endowment is denoted by a square in the preference. Let Li be the set of the objects associated with the literals in clause Ci, i.e., Li is the set of objects ona a , opb b and oqc c with na = i, pb = i or qc = i. For each variable vi, we deﬁne a set of objects Wi = {c1, . . . , cm} {onj j : j > i} {opj j : j = i} {oqj j : j > i} {al j : j < i, l = 1, 2, 3}. We are ready to give the preferences for the agents. First, we consider the preferences for T and Ci. The following preferences ensure that when Ci holds an object in Li for each i {1, . . . , m}, object t is reachable for agent Cm via a sequence of m swaps between Ci and Ci 1 for i = 1, . . . , m, where C0 = T. T : L1 t ; Ci : Li+1 t Li c1 Li 1 . . . ci 1 L1 ci , for all 1 i m 1 ; Cm : t Lm c1 Lm 1 . . . cm 1 L1 cm .

Next, we consider the preferences for the agents in each block Bi. The following preferences ensure that at most one of oni i and {opi i , oqi i } can be moved to the right of the block, which will indicate the corresponding variable is either true or false. If oni i is moved to the right of the block, we will assign the corresponding variable false; if some of {opi i , oqi i } is moved to the right of the block, we will assign the corresponding variable true. We use the preference of A3 i to control this. Furthermore, we use A1 i , A2 i and A3 i to (temporarily) hold oni i (or opi i and oqi i ) if they do not need to be moved to the right of the block. X ni i : Wi {a1 i , a2 i , a3 i , opi i , oqi i } oni i ,

Xqi i : Wi {a1 i , a2 i , a3 i , oni i , opi i } oqi i ,

Xpi i : Wi {a1 i , a2 i , a3 i , oqi i , oni i } opi i ,

A1 i : Wi { a1 i , a2 i , a3 i , opi i , oqi i , oni i } ,

A2 i : Wi {a1 i , a2 i , a3 i , opi i , oqi i , oni i } ,

A3 i : Wi {a1 i , a2 i , opi i , oqi i } oni i a3 i , for all 1 i n.

The instance IW OR is to determine whether object t is reachable for agent Cm.

Lemma 15. A 2P1N-SAT instance ISAT is yes if and only if the corresponding instance IW OR of WEAK OBJECT REACHABILITY in a path is yes.

Proof Sketch. If t is reachable for cm, there are m swaps including t which happen between Ci and Ci+1 for i {0, 1, . . . , m 1}, where C0 = T. Note that the swap between Ci and Ci+1 (where Ci holds the object t) can happen if and only if Ci+1 holds an object a Li+1. We can let the

literal corresponding to the object a Li+1 to be true for all agents Ci to get a satisfying assignment for ISAT because the construction of each block Bi does not allow both oni i and one of opi i and oqi i moving to the right of the block according to the construction of the block Bi the preference of A3 i . On the other hand, if there is a satisﬁed assignment τ for ISAT , we can construct a reachable assignment for IW OR. For each variable vi, if it is true in τ, we move opi i and oqi i to agents A3 i and A2 i ; if it is false in τ, we move oni i to agent A2 i . These objects are called true objects. All these happen within each block. After this procedure, we move true objects ona a , opb b and oqc c to agent Cj with j = na, j = pb or j = qc one by one in an order where Cj with smaller j ﬁrst gets its object in Lj. During this procedure, once another true object is moved out of its position A3 i or A2 i (this may happen when the true object is on the moving path of another true object to Cj), we will simply move it back by one swap. So in each iteration only one true object is moved out of its current position A3 i or A2 i and it is moved to its ﬁnal position Cj directly.

In this paper, we mainly investigate OBJECT REACHABILITY that asks whether an object is reachable for a given agent. We show that when the network is a path, WEAK OBJECT REACHABILITY is NP-hard but STRICT OBJECT REACHABILITY is polynomially solvable. In the literature, more problems under the HOUSING MARKET model with a different objective have been investigated, such as the reachability of a whole assignment, ﬁnding Pareto efﬁcient assignments and so on (Gourv es, Lesca, and Wilczynski 2017). Some of our results can be extended to these problems with some modiﬁcations. We will give the details in the full version of this paper.

Abdulkadiro glu, A., and S onmez, T. 1998. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66(3):689 701. Abdulkadiro glu, A., and S onmez, T. 1999. House allocation with existing tenants. Journal of Economic Theory 88(2):233 260. Abebe, R.; Kleinberg, J.; and Parkes, D. C. 2017. Fair division via social comparison. In Proceedings of the 16th Conference on Autonomous Agents and Multiagent Systems, 281 289. Ahmad, G. 2017. Essays on Housing Market Problem. Ph.D. Dissertation, Texas A & M University. Alcalde-Unzu, J., and Molis, E. 2011. Exchange of indivisible goods and indifferences: The top trading absorbing sets mechanisms. Games and Economic Behavior 73(1):1 16. Aspvall, B.; Plass, M. F.; and Tarjan, R. E. 1979. A lineartime algorithm for testing the truth of certain quantiﬁed boolean formulas. Information Processing Letters 8(3):121 123.

Aziz, H., and De Keijzer, B. 2012. Housing markets with indifferences: a tale of two mechanisms. In Proceedings of the 26th AAAI Conference on Artiﬁcial Intelligence, 1249 1255. Bei, X.; Qiao, Y.; and Zhang, S. 2017. Networked fairness in cake cutting. In Proceedings of the 26th International Joint Conference on Artiﬁcial Intelligence, 3632 3638. Beynier, A.; Chevaleyre, Y.; Gourv es, L.; Lesca, J.; Maudet, N.; and Wilczynski, A. 2018. Local envy-freeness in house allocation problems. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems, 292 300. Bredereck, R.; Kaczmarczyk, A.; and Niedermeier, R. 2018. Envy-free allocations respecting social networks. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems, 283 291. Damamme, A.; Beynier, A.; Chevaleyre, Y.; and Maudet, N. 2015. The power of swap deals in distributed resource allocation. In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems, 625 633. Ehlers, L. 2014. Top trading with ﬁxed tie-breaking in markets with indivisible goods. Journal of Economic Theory 151:64 87. Gardenfors, P. 1973. Assignment problem based on ordinal preferences. Management Science 20(3):331 340. Gourv es, L.; Lesca, J.; and Wilczynski, A. 2017. Object allocation via swaps along a social network. In Proceedings of the 26th International Joint Conference on Artiﬁcial Intelligence, 213 219. Jaramillo, P., and Manjunath, V. 2012. The difference indifference makes in strategy-proof allocation of objects. Journal of Economic Theory 147(5):1913 1946. Manlove, D. F. 2013. Algorithmics of matching under preferences, volume 2. World Scientiﬁc. Roth, A. E.; S onmez, T.; and Unver, M. U. 2004. Kidney exchange. The Quarterly Journal of Economics 119(2):457 488. Saban, D., and Sethuraman, J. 2013. House allocation with indifferences: a generalization and a uniﬁed view. In Proceedings of the 14th ACM conference on Electronic commerce, 803 820. Shapley, L., and Scarf, H. 1974. On cores and indivisibility. Journal of Mathematical Economics 1(1):23 37. Sonoda, A.; Fujita, E.; Todo, T.; and Yokoo, M. 2014. Two case studies for trading multiple indivisible goods with indifferences. In Proceedings of the 28th AAAI Conference on Artiﬁcial Intelligence, 791 797. Wilson, L. B. 1977. Assignment using choice lists. Journal of the Operational Research Society 28(3):569 578. Yoshinaka, R. 2005. Higher-order matching in the linear lambda calculus in the absence of constants is np-complete. In International Conference on Rewriting Techniques and Applications, 235 249.