Exchange of Indivisible Objects with Asymmetry

1 Introduction

Designing rules that satisfy desirable properties for the exchange of indivisible objects among agents is a fundamental research question in the fields of economics and algorithmic game theory. For cases where each agent is assumed to own exactly one indivisible object and to have a strict preference over the objects, the problem has been called the housing market [Shapley and Scarf, 1974]. The well-known toptrading-cycles (TTC) rule always returns an allocation of the objects belonging to the (strict) core for the housing market, as well as gives agents appropriate incentives to report their preferences truthfully, i.e. is strategy-proof. Furthermore, the core allocation is individually rational and Pareto efficient, both of which are quite popular properties in economic literature.

In this paper we focus on designing rules that simultaneously satisfy strategy-proofness, individual rationality, and Pareto efficiency. For the housing market, TTC is the unique rule that satisfies all of them [Ma, 1994]. On the other hand, there have been several impossibility results about such rules for more general cases. S¨onmez (1999) showed that when agents' preferences are strict and their domain is rich enough, there is no such rule. P´apai (2003), Konishi et al. (2001), and Todo et al. (2014) respectively showed that the impossibility carries over into the responsive, additive, and lexicographic preference domains. Sonoda et al. (2014) showed that no such rule exists even under a domain of preferences that contain indifferences.

Nevertheless, we continue to investigate mechanism design for the exchange of indivisible objects. One main reason is that all those impossibilities assume that the domain of agents' preferences for the objects is symmetric: for any pair of two (combinations of) objects, the existence of a preference that prefers one of them implies the existence of another preference that would rather have the other. In other words, under a symmetric preference domain, agents are allowed to report any objects as their favorites. In practice, however, the domain of the preferences may not be symmetric. For example, considering both a good and a bad apple, or a fast and a slow processor, it seems quite natural that everyone prefers the former to the latter, if all other such conditions as prices are identical. In this case, we can assume that agents are not allowed to report the latter object as their best choice, and hence the domain of preference is no longer symmetric.

Such a common component/structure among agents' preferences actually has been often discussed in various mechanism design settings. In combinatorial auctions, the assumption of single-minded bidders is very popular and admits a polynomial-time approximation scheme for the winner determination problem [Lehmann et al., 2002]. In two-sided matching, such as school choice problems, the notion of priority list [Afacan, 2014] has usually been introduced, which is a (possibly incomplete) ranking of students and shared among all the schools, although they are usually assumed neither to be rational nor willing to cheat. In voting, sometimes all voters are assumed to have single-peaked preferences over candidates, where such a situation can be also formulated as the facility location problem [Moulin, 1980]. The key feature of all these examples is that the restriction on agents' preferences greatly simplifies the problem so that we can overcome impossibility results for general cases.

In this paper we introduce the notion of common factor, which represents the asymmetry shared among all the possible preferences of agents. A common factor is defined as a set of binary relations over the set of all indivisible objects. When such a common factor exists, each agent is assumed to have a strict ordering of the objects that is consistent with it. The preference of such an agent over all the subsets of the objects is then determined from her ordering by one of the two extensions: additive or lexicographic. The additive extension determines a preference based on the summation of a valuation function over single objects that reflects the ordering of the objects, and the lexicographic extension is a special case of the additive one. In this sense, we are focusing on situations where there are no complementarities/synergies among objects. However, since we provide an impossibility result for the additive extension, our analysis still covers the cases with complementarities.

Based on the common factor, we discuss whether there exist exchange rules that simultaneously satisfy all three above properties under preference domains with asymmetry. We first show that for any possible common factor, such an exchange rule does not exist when agents' preferences are determined by the additive extension, except for trivial cases in which some positive results were already known. This also implies that in the multiple housing market problem with additive preferences [Konishi et al., 2001], no such rule exists even if we assume that the set of all submarkets are in a sequence so that each object in a prior submarket is strictly better than any object in any subsequent submarket. We then show that for a specific class of common factors, such an exchange rule exists when agents' preferences are determined by the lexicographic extension. This positive result, compared with the impossibility in Todo et al. (2014), sheds light on the structure of preference domains in the exchange of indivisible objects.

For the latter case where such an exchange rule exists, we also provide another exchange rule that satisfies all the three properties but does not always select an allocation in the core. This result indicates that the characterization by S¨onmez (1999), which pointed out the equivalence between the single-valuedness of allocations in the core and the existence of such exchange rules, does not apply to our model, mainly because of the asymmetry in preferences. Therefore, from the perspective of a mechanism designer, we generally need to take account of the allocations that are not in the core, even when we are just interested in designing exchange rules that satisfy all those three properties.

2 Preliminaries

We first introduce the exchange problem considered in this paper. There is a set of n agents N = {1, . . . , n}. Each agent i ∈ N is initially endowed with a set of indivisible objects ωi(̸= ∅). Let ω = (ωi)i∈N indicate the initial endowment distribution. We assume that ωi ∩ ωj = ∅ for any i, j ∈ N and let G be the union of the endowments of all the agents, i.e., G := ⋃i∈N ωi. An allocation a = (ai)i∈N is a distribution of G to N such that ai ⊆ G for any i ∈ N, ⋃i∈N ai = G, and ai ∩ aj = ∅ for any pair i, j ∈ N. For a given allocation a and an agent i ∈ N, ai is called an assignment to the agent i under the allocation a. Let A denote the set of all such allocations, which obviously contains ω inside 1

Each agent i ∈ N has a linear ordering Ri, known as a preference, of the set of all possible bundles S, T ⊆ G. Let R denote a preference domain that consists of all admissible preferences of each agent i ∈ N. Given a preference Ri ∈ R of an agent i and a pair S, T ⊆ G, let SRiT denote the fact that S appears earlier than T in the ordering Ri, which means that S is weakly preferred to T by the agent i with the preference Ri. We assume preferences are strict, meaning that for any pair S, T (̸= S) ⊆ G, either SPiT or TPiS holds, where Pi indicates the strict component of Ri. Therefore, SRiT and ¬SPiT implies S = T. Let R = (Ri)i∈N ∈ Rn denote a preference profile of the agents N and R-i = (Rj)j̸=i ∈ Rn-1 denote a preference profile of N \ {i}.

Here we introduce the concept of blocking, which will be frequently used in the rest of the paper. We say a set (or a coalition) of agents M ⊆ N blocks an allocation a ∈ A under preference profile R ∈ Rn via another allocation b ∈ A if (i) ∀i ∈ M, bi ⊆ ⋃k∈M ωk holds, (ii) ∀i ∈ M, biRiai holds, and (iii) ∃j ∈M, bjPjaj holds.

An exchange problem E = (N, ω, A , R) consists of a set of agents N, an initial endowment distribution ω, the set of possible allocations A , and the preference domain R for the agents. For a given exchange problem E, an exchange rule ϕ is formally defined as a mapping from R ∈ Rn to A . More precisely, an exchange rule ϕ maps each profile of the preferences that is reported by the agents N into a possible allocation to N. Here let ϕ(R) ∈ A indicate the allocation when agents report R, and let ϕ(Ri,R-i) indicate the allocation when agent i reports Ri while the other agents report R-i. Furthermore, for a given ϕ and any input R, let ϕi(R) indicate the assignment to i under ϕ(R).

We now define the three desirable properties considered in this paper. Individual rationality requires that for each agent, participation by reporting her true preference is weakly better than not participating. Formally, for a given exchange problem E = (N, ω, A , R), an exchange rule ϕ is said to be individually rational if ∀R ∈ Rn , ∀i ∈ N, ϕi(R)Riωi. Strategyproofness, which is an incentive constraint for agents, requires that for each agent, reporting her true preference is weakly better than misreporting her preference. Formally, for a given exchange problem E = (N, ω,A ,R), an exchange rule ϕ is said to be strategy-proof if ∀i ∈ N, ∀R-i ∈ Rn-1 , ∀Ri ∈ R, ∀R′i ∈ R, ϕi(Ri,R-i)Riϕi(R′i ,R-i). Finally, Pareto efficiency is one of the most popular efficiency criteria for evaluating the performance of an exchange rule. An allocation b ∈ A is said to Pareto dominate another allocation a ∈ A under a preference profile R if the set N of all agents blocks a under R via b. For a given exchange problem E = (N, ω,A ,R), an exchange rule ϕ is Pareto efficient if

1 There exist some works that restrict the set A of such possible allocations, which investigate the model reffered to as multiple housing market, including Konishi et al. (2001) and Miyagawa (2002) .

∀R ∈ Rn , any allocation b ∈ A does not Pareto dominate ϕ(R).

For our perspective of designing exchange rules that satisfy all the three properties, we consider an exchange problem successful if it guarantees the existence of such rules.

Definition 1 (Successful Problem). An exchange problem E is said to be successful if for the exchange problem E, there exists an exchange rule ϕ that is individually rational, strategy-proof, and Pareto efficient.

Using the concept of a successful problem, we can review several known results in the literature. The first positive result follows from several papers [Ma, 1994; Aziz and de Keijzer, 2012; Saban and Sethuraman, 2013].

Proposition 1. Any exchange problem E = (N, ω,A ,R) is successful for any R (even including indifferent preferences) if |ωi| = 1 for all i ∈ N.

Actually the top-trading-cycles (TTC) rule [Shapley and Scarf, 1974] satisfies all the properties for cases with strict preferences. We briefly describe the procedure since it is used in another exchange rule we will propose in Sections 5 and 6.

Definition 2 (Top-Trading-Cycles). For an exchange problem E = (N, ω,A ,R) s.t. |ωi| = 1 for all i ∈ N, this algorithm works as follows:

Step 1 Construct a directed graph with two types of nodes (agents and objects) and edges (from agents to objects or from objects to agents). Each agent points to her most favorite object and each object points to its owner. Obviously there is at least one cycle. Assign to each agent in each cycle the object to which she points and remove all such objects and agents from the graph. Then go to Step 2.

Step t(≥ 2) If no agent remains in the market, then the procedure terminates; otherwise, each agent points to her most favorite object among the remaining ones and each object points to its owner. Assign to each agent in each cycle the object to which she points and remove all such objects and agents from the graph. Go to Step t + 1.

On the other hand, S¨onmez (1999) showed that an exchange problem is not successful in general if each agent can initially have more than one object.

Proposition 2. An exchange problem E = (N, ω,A ,R) is not successful if R contains all possible strict preferences and |ωi| ≥ 2 for some i ∈ N.

3 Preference Domains with Common Factor

In this section we define a notation that enables us to represent common structures among preferences of agents. Let ▷ be a set of partial binary relations, which we refer as a common factor, over G. For a given common factor ▷ and two objects x, y ∈ G, let x ▷ y represent (x, y) ∈ ▷. Note that ▷ is strict and transitive, but need not be complete. Therefore ▷ = ∅ is possible. Let F be the set of all possible common factors over G. This definition is actually identical with the conditional importance network of [Bouveret et al., 2009].

Now we define the concept of the orderings of all single objects G, which induce agents' preferences. For a given common factor ▷ ∈ F, let S▷ be the set of all possible strict orderings of G that keeps all the relations in ▷. That is, for a given ▷ and two objects x, y ∈ G, x ▷ y implies that x appears before y in every ordering in the set S▷. Furthermore, given a common factor ▷ ∈ F, we assume that each agent i has an ordering ≻i∈ S▷, which means that for two given objects x, y ∈ G, an appearance of x before y in ≻i implies that she prefers x to y. Each agent i's preference Ri is then derived from the ordering ≻i by one of the two following extension rules:

Additive extension first defines a value function vi : G → R≥0 s.t. x ≻i y implies vi(x) > vi(y) for any x, y ∈ G. Then, for given S, T ⊆ G, SRiT if and only if ∑x∈S vi(x) ≥ ∑x∈T vi(x).

Lexicographic extension is a special case of the additive extension s.t. for any x ∈ G, vi satisfies vi(x) > ∑y;x≻iy vi(y).

For a given common factor ▷ ∈ F, let R ADD ▷ and R LEX ▷ indicate the set of all possible preferences that are derived from strict orderings in S▷ by the additive and lexicographic extensions.

For instance, consider the following example with a common factor ▷ = {(g1, g2)} over G = {g1, g2, g3}.

Example 1. There are two agents N = {1, 2}, whose initial endowments are given as ω = (ω1, ω2) = ({g1, g2}, {g3}). The common factor is given as ▷ = {(g1, g2)}. Agent 1 has the ordering ≻1∈ S▷ s.t. g1 ≻1 g3 ≻1 g2, and agent 2 has ≻2∈ S▷ s.t. g3 ≻2 g1 ≻2 g2. Furthermore, agent 1's preference R1 is derived from the lexicographic extension:

Note that the lexicographic extension is uniquely determined for a given ordering over G. On the other hand, agent 2's preference R2 is derived from an additive extension:

In contrast to the lexicographic extension, the additive extension is not unique for a given ordering.

This example reflects a situation where g1 is obviously better than g2, say the good and bad apples mentioned in Section 1, for any agent in the market.

Using the concept of the common factor as well as the successfulness of exchange problems, we can represent two impossibilities provided by Konishi et al. (2001) and Todo et al. (2014) as follows:

Proposition 3 (Konishi et al., 2001). An exchange problem E = (N, ω, A , R ADD ▷ ) is not successful for ▷ = ∅.

Proposition 4 (Todo et al., 2014). An exchange problem E = (N, ω, A , R LEX ▷ ) is not successful for ▷ = ∅.

4 Impossibility for Additive Extension

In this section we first focus on the additive extension and show that for any possible common factor, we cannot find an exchange rule that is individually rational, strategy-proof, and Pareto efficient, except for very trivial cases that have already been investigated in the literature.

Theorem 1. An exchange problem E = (N, ω, A , R ADD ▷ ) is not successful for any common factor ▷ ∈ F if |N| ≥ 2 and |ωi| ≥ 2 for all i ∈ N.

Proof. Let us consider the following exchange problem: N = {1, 2}, ω = (ω1, ω2) = ({g1, g2}, {g3, g4}), and ▷ is given as g3 ▷ g1 ▷ g2 ▷ g4. The agents' preferences are defined by the following valuation functions v1 and v2:

Under this profile of preferences (or equivalently valuation functions), there are only two allocations a and b satisfying individual rationality and Pareto efficiency.

Now we are going to show that both of them cannot be chosen by any strategy-proof exchange rule for the profile. If a is chosen, then agent 2 would better off by reporting another valuation function v′2 s.t. v′2 (g2) = 2.5 and all the others are the same with v2, which makes b the only allocation that satisfies individual rationality and Pareto efficiency. Similarly, if b is chosen, then agent 1 would better off by reporting another valuation function v′1 s.t. v′1 (g3) = 8 and all the others are the same with v1, which makes a the only allocation that satisfies individual rationality and Pareto efficiency. So there is no exchange rule that simultaneously satisfies individual rationality, strategy-proofness and Pareto efficiency. The statement still holds for any number of agents greater than three and any other common factor, since we can construct the same situation with this example for such cases.

When | ⋃i∈N ωi| = n, the problem coincides with the traditional housing market, in which the TTC rule satisfies all the requirements. On the other hand, if | ⋃i∈N ωi| = n + 1, there may be a chance that the problem E = (N, ω, A , R ADD ▷ ) is successful for a specified common factor where all the agents share the same ordering over every single object.

Konishi et al. (2001) also showed that there exists no exchange rule that satisfies all the three properties for general additive preferences when objects are separated into several types, each agent initially owns at most one object for each type, and only trading the objects of the same type is allowed, Theorem 1 has a stronger implication on this problem: no such exchange rule exists even if we introduce any common factor into the multiple housing market problem.

5 Possibility for Lexicographic Extension

In light of the negative results presented in the previous section, we restrict ourselves to the lexicographic extension and seek some positive results with respect to common factors. As mentioned in Example 1, the lexicographic extension is unique for a given ordering. Therefore, it is trivially true that an exchange problem E = (N, ω, A , R LEX ▷ ) is successful for any complete ▷ ∈ F, because reporting a false preference is not allowed for any agent in this case. On the other hand, Todo 2014 showed that an exchange problem is not successful when agents are allowed to initially have more than one object and preferences are lexicographic, which coincides with the case of setting ▷ = ∅. The following theorem explains the existence of a non-trivial class of successful exchange problems with a common factor that is between the above two observations.

Theorem 2. An exchange problem E = (N, ω,A ,R LEX ▷ ) is successful if the common factor ▷ satisfies the following conditions:

1. There exists anm-partition (H1, . . . ,Hm) of G s.t. ∀i ∈ N, ∀k ∈ {1, . . . ,m}, |ωi ∩Hk| ≤ 1 holds, and
2. ∀k ∈ {1, . . . ,m}, ∀x ∈ Hk, ∀l > k, ∀y ∈ Hl, x ▷ y holds.

These conditions reflect a situation where the set of objects establishes a certain format of hierarchy s.t. each agent owns at most one object from each level/submarket Hk in it (guaranteed from condition 1), and there is a common priority between submarkets so that having an object in a higher submarket is strictly better than having any object in any lower submarket (guaranteed from condition 2). Actually, the multiple housing market mentioned in the previous section satisfies condition 1, although its original definition based on additive valuation functions violates condition 2.

We prove this theorem by showing the existence of an exchange rule that is individually rational, strategy-proof, and Pareto efficient for any such problem. Indeed, a very simple rule that applies the TTC procedure for each submarket Hk of the hierarchy works, since each level can be considered a traditional housing market in which each agent owns exactly one object and has a strict preference over all the objects. Note that this exchange rule is also known as the coordinate-wise core (CWC) mechanism [Wako, 2005].

Observation 1. For any exchange problem satisfying the conditions described in Theorem 2, applying the TTC procedure for each submarket is strategy-proof and always selects the core allocation in each submarket.

We next find the following observation about the condition when an agent improves that for each agent the number of objects she receives does not change in each submarket.

Observation 2. Under the conditions described in Theorem 2, let ak indicate the allocation in the k-th submarket Hk when a represents the allocation that the number of each agent's object does not change in each submarket, i.e. ∀i ∈ N, ∀k ∈ {1, . . . ,m}, |ωi∩Hk| = |ai∩Hk|. Then ∀a, b ∈ A , ∀i ∈ N, bPia holds if and only if ∃q ∈ {1, . . . , m} s.t. bqi Piaqi and ∀p ∈ {1, . . . , q - 1}, bpi = api .

Finally we show that the allocation by the exchange rule that selects the core in each submarket is also in the core of the original problem, which implies individual rationality and Pareto efficiency of the rule.

Lemma 1. For any exchange problem satisfying the conditions described in Theorem 2, the allocation that selects the core in each submarket is also in the core of the problem.

Proof. For the sake of contradiction, we assume that there exists a profile R of the preferences and a coalition M ⊆ N

of agents that blocks the allocation a chosen by the exchange rule under R via another allocation b ∈ A . By the definition of blocking, (i) bi ⊆ ⋃k∈M ωk for all i ∈ M, (ii) biRiai holds for all i ∈M and (iii) bjPjaj holds for some j ∈M.

First we can easily observe that for such M and b, |bi ∩ Hk| = |ωi ∩ Hk| holds for any i ∈ M and any k ∈ {1, . . . ,m}. Otherwise, from condition (i) of blocking and the preferences based on the lexicographic extension, at least one agent in M will get worse. We then construct a modified allocation ˆb that satisfies |ˆbi ∩Hk| = |ωi ∩Hk| for any agent in N and any k ∈ {1, . . . , m}, as well as conditions (i), (ii), and (iii) for blocking. Thus, without a loss of generality we consider ˆb a combination of the reallocations for each submarket Hk.

Let M ′ ⊆ M be the set of agents j ′ in the coalition M, each of whom strictly gets better, i.e. ˆbj ′Pj ′aj ′ . Then, from Observation 1, for each such j ′ ∈ M ′ , there exists an index q ∈ {1, . . . ,m} such that ˆbqj ′Pj ′aqj ′ and ∀p ∈ {1, . . . , q - 1},ˆbpj ′ = apj ′ . Let qj ′ be the index for each j ′ ∈ M ′ , and let q∗ = minj ′∈M′ qj ′ . From the assumption that if such a blocking coalition exists, then it must be the case that q∗ ∈ {1, . . . ,m} and we show that such q∗ does not exist by induction on the cardinality of q∗ .

Let us consider q∗ = 1. Since we already observed that ˆb is a combination of the reallocations for each submarket and M blocks a via ˆb, it must hold that ∃j ′ ∈ M ′ , ˆb1j ′Pj ′a1j ′ . This obviously violates the fact that TTC chooses the unique core in the submarket H1. Thus q∗ can not be 1.

Assuming q∗ cannot equal any integer smaller than r, let us consider q∗ = r. From the lexicographic extension, it must be the case that ˆbrj ′Pj ′arj ′ and ∀p ∈ {1, . . . , r -1}, ˆbpj ′ = apj ′ , which again violates the fact that TTC chooses the unique core in submarket Hr. Thus q∗ cannot be r.

Proof of Theorem 2. FromObservation 1, the exchange rule, which simply applies the TTC procedure for each submarket, is strategy-proof and selects the core for each submarket. From Lemma 1, the exchange rule also selects the core for the original problem. Thus the statement is true.

Note that the exchange rule considered in the proof also coincides with the augmented top-trading-cycles rule [Fujita et al., 2015], under the conditions in Theorem 2.

6 Exchange Rule that Does Not Always Select the Core

In this section we compare our positive result presented in the previous section with a characterization of (not) successful problems by S¨onmez (1999). We first define the notion of the single-valued core. We say the core is single-valued if every agent i ∈ N is indifferent between any two core allocations a and a′ (̸= a). Since we only care about strict preferences in this paper, some agent strictly prefers one of the two distinct core allocations. Formally we have the following observation:

Observation 3. For the exchange problem E = (N, ω, A , R LEX ▷ ) with a common factor ▷ satisfying the conditions described in Theorem 2, the core is always non-empty but not always single-valued.

S¨onmez (1999) clarified under some natural assumptions, an equivalence between the single-valuedness of the core and the existence of exchange rules satisfying all the three properties in a large class of mechanism design situations including exchange problems. One critical assumption in his characterization is, however, that the domain of preferences must be rich enough so that, intuitively, any permutation of a preference ordering is possible. It is therefore not the case for our model with a common factor. Indeed, we now propose a new exchange rule, inspired from an algorithm called YRMHIGYT [Abdulkadiroˇglu and S¨onmez, 1999], and show that it satisfies all the properties but does not select the core.

Definition 3. Apply the TTC procedure for each submarket H1, . . . ,Hm-1. For the least prioritized submarket Hm, use the following procedure:

Initialization: Create a queue of the agents who initially own an object in the submarket Hm to represent their priority. Initially all the agents are in an ascending order with respect to their indices. From the top of the queue, sequentially check whether an agent has received a set of objects that is better than her initial endowments from the prior submarkets H1, . . . ,Hm-1. If so, return her to the end of the queue and make the object she initially owned in Hm not pointing to her or anyone. Otherwise do nothing. Then construct a directed graph as well as the TTC procedure.

Step t(≥ 1): If no agent remains in themarket, then the procedure terminates; otherwise, each agent points to her most favorite object among the remaining ones. Each object belonging to an agent points to her. All the other objects point to the highest priority agent in the queue. Obviously there is at least one cycle. Assign to each agent in each cycle the object to which she points and remove all such objects and agents from the graph. Also remove those agents from the queue. Then go to Step t + 1.

Proposition 5. For the exchange problem E = (N, ω, A , R LEX ▷ ) with a common factor ▷ satisfying the conditions described in Theorem 2, Mechanism 1 is individually rational, strategy-proof, and Pareto efficient and does not always select the core.

The proposition follows from Lemmas 2 and 3.

Lemma 2. The exchange rule described in Definition 3 is individually rational, strategy-proof, and Pareto efficient.

Proof Sketch. By definition, the exchange rule assigns an identical number of objects for each agent in each submarket. Each submarket except for the least prioritized one just uses the TTC procedure. Furthermore, even in the least prioritized submarket, only the agents who already received a better set of objects than their initial endowments lose their objects. Thus the exchange rule is individually rational.

For strategy-proofness, we first observe that, from the definition of TTC, no agent can improve her assignment in any submarket except for the least prioritized one. Furthermore, for an agent to have a higher priority in the least prioritized submarket, she has to give up receiving a better object in some prior submarket, which surely make her worse off from the definition of the lexicographic extension.

Finally we verify that the exchange rule is Pareto efficient. The exchange rule can be considered as a combination of the TTC algorithm for m housing market problems, each of which corresponds to each submarket Hk. Since the allocation by the TTC algorithm for housing market problem is guaranteed to be Pareto efficient, the allocation by the exchange rule is a combination of a Pareto efficient allocation for each submarket Hk. Now that agents' preferences are determined by the lexicographic extension, such an allocation cannot be dominated by any other allocation.

Lemma 3. The exchange rule described in Definition 3 does not always select the core.

Proof. Consider the following exchange problem E = (N, ω,A ,R ADD ▷ ) s.t. N = {1, 2, 3, 4}, ω = (ω1, ω2, ω3, ω4) = ({g1, g5}, {g2, g6}, {g3, g7}, {g4, g8}), and ▷ is given as

g1 ▷ g5, g6, g7, g8

This problem obviously satisfies the condition described in Theorem 1, since we can find a 2-partition (H1, H2) s.t. H1 = {g1, g2, g3, g4} and H2 = {g5, g6, g7, g8}.

Now let us consider a profile of preferences that are uniquely determined by the lexicographic extension from the following orderings ≻1, . . . , ≻4:

≻1: g2 > g1 > g4 > g3 > g6 > g7 > g8 > g5

The left picture in Fig. 1 shows the initial situation in the submarket H1. In the submarket, by simply applying the TTC procedure, agent 1, 2, 3 and 4 receives g2, g1, g3 and g4, respectively. At the end of the initialization in the least prioritized submarket H2, the queue orders all the four agents as 3 ≻ 4 ≻ 1 ≻ 2, because both agents 1 and 2 have already been guaranteed to get a strictly better assignment than their initial endowments. On the other hand, agents 3 and 4 just received their initial endowment in H1, which does not guarantee a better assignment for them.

The right picture in Fig. 1 shows the initial situation in the submarket H2. At step 1 in it, g5, g6, and g7 point to agent 3, while g8 points to agent 4. Then agent 3 receives g5. At step 2, all the remaining objects g6, g7 and g8 point to agent 4, who then receives g6. At step 3, all the remaining objects point to agent 1, who then receives g7. Finally agent 2 receives g8. Thus, the final allocation is ({g2, g7}, {g1, g8}, {g3, g5}, {g4, g6}), which a coalition of the two agents {1, 2} blocks under R via another allocation ({g2, g6}, {g1, g5}, {g3, g7}, {g4, g8}).

The failure of the exchange rule to select the core mainly comes from the fact that the exchange rule ignores some information about initial endowments when it confirms the existence of at least one individually rational allocation. Note that this may not be the only exchange rule that satisfies all three properties and does not always select the core.

This proposition has a slight negative implication. In contrast to the exchange problems investigated by S¨onmez (1999), we should not just focus on exchange rules that choose a core allocation in our model with asymmetry, even though we are only interested in exchange rules that satisfy individual rationality, strategy-proofness, and Pareto efficiency. Actually, for environments where the core allocation is not very appealing due to some characteristics of agents, say those who are segregated geographically or who generally cooperate with the mechanism, it may be possible to introduce some other criteria than the core to evaluate those exchange rules. For instance, considering such strong incentive property as group strategy-proofness, hiding-proofness [Atlamaz and Klaus, 2007], or split-proofness [Fujita et al., 2015] (also known as false-name-proofness [Todo and Conitzer, 2015]) is one possible direction.

7 Conclusion

We obtained a general impossibility on the additive extension and found a class of successful problems with the lexicographic extension. We further provided a counter example of the equivalence between the single-valued core and successfulness by showing an exchange rule that satisfies all three properties but does not always select the core. One possible future work is to give a necessary and sufficient condition for a given exchange problem with the lexicographic extension to be successful. We would also like to find some property, instead of the core, that evaluates exchange rules that satisfy all the properties and characterize such rules with it. Finally, we also believe that it would be interesting to introduce the concept of common factor into different mechanism design situations such as two-sided matching and combinatorial auctions.

8 Acknowledgement

This work was partially supported by JSPS KAKENHI Grant Number 24220003 and 26730005, and JSPS Program for Advancing Strategic International Networks to Accelerate the Circulation of Talented Researchers. The authors thank Etsushi Fujita, Akihisa Sonoda, and three anonymous reviewers for their helpful comments and discussions.