# reforming_an_envyfree_matching__c246b2a3.pdf

Reforming an Envy-Free Matching

Takehiro Ito1, Yuni Iwamasa2, Naonori Kakimura3, Naoyuki Kamiyama4, Yusuke Kobayashi5, Yuta Nozaki6, Yoshio Okamoto7, Kenta Ozeki8

1Graduate School of Information Sciences, Tohoku University, Japan 2Graduate School of Informatics, Kyoto University, Japan 3Faculty of Science and Technology, Keio University, Japan 4Institute of Mathematics for Industry, Kyushu University, Japan 5Research Institute for Mathematical Sciences, Kyoto University, Japan 6Graduate School of Advanced Science and Engineering, Hiroshima University, Japan 7Graduate School of Informatics and Engineering, The University of Electro-Communications, Japan 8Faculty of Environment and Information Sciences, Yokohama National University, Japan takehiro@tohoku.ac.jp, iwamasa@i.kyoto-u.ac.jp, kakimura@math.keio.ac.jp, kamiyama@imi.kyushu-u.ac.jp, yusuke@kurims.kyoto-u.ac.jp, nozakiy@hiroshima-u.ac.jp, okamotoy@uec.ac.jp, ozeki-kenta-xr@ynu.ac.jp

We consider the problem of reforming an envy-free matching when each agent is assigned a single item. Given an envy-free matching, we consider an operation to exchange the item of an agent with an unassigned item preferred by the agent that results in another envy-free matching. We repeat this operation as long as we can. We prove that the resulting envy-free matching is uniquely determined up to the choice of an initial envy-free matching, and can be found in polynomial time. We call the resulting matching a reformist envy-free matching, and then we study a shortest sequence to obtain the reformist envy-free matching from an initial envy-free matching. We prove that a shortest sequence is computationally hard to obtain even when each agent accepts at most four items and each item is accepted by at most three agents. On the other hand, we give polynomial-time algorithms when each agent accepts at most three items or each item is accepted by at most two agents. Inapproximability and fixed-parameter (in)tractability are also discussed.

1 Introduction Matching under preferences constitutes an important and well investigated subarea of economics and game theory, and its computational aspects are intensively studied in algorithmic game theory and computational social choice (see, e.g., (Klaus, Manlove, and Rossi 2016; Manlove 2013)). In a lot of situations, we are interested in allocating indivisible items, namely, items that cannot be subdivided into several parts. Examples include job allocation, college admission, school choice, kidney exchange, and junior doctor allocation to hospital posts. Especially, this paper is concerned with the situation where each agent is assigned a single item. This situation is often called the house allocation problem. A set of agents faces a set of items, and each agent has a preference over her acceptable items (i.e., her preference list can be incomplete). In this situation, there may be many possible matchings. However, some of those matchings suffer from instability.

Copyright 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Stability is often studied in terms of envy of agents in the house allocation problem. Given a matching, an agent i has a (justified) envy for another agent j if the agent i prefers the item assigned to j to the item assigned to i. If there is no agent with envy, the matching is said to be envy-free. Even with envy-freeness, there may be many possible matchings, and we want to look for a good envy-free matching. This motivates the following simple procedure that can be implemented in a decentralized way. Agents start with any envyfree matching. There are many unassigned items on the table. Then an agent i can exchange the item x assigned to her with an item y on the table if i prefers y to x and the exchange does not break the envy-freeness. This reforming process can continue until no agent has an incentive for exchange. Then every agent will be assigned an item that is at least as good as the item that was initially assigned, and the resulting matching is still envy-free. Our problem arises in the following situation. First, items are assigned to agents by an envy-free matching. The matching is given a priori, and agents are satisfied by the items assigned to them. Then the agents face the arrival of extra items. This may happen, for example, when some new items are brought into the market, or when some of the agents leave the market and release their items. Since the new items could improve agents utilities, the agents might not be satisfied with the items currently assigned to them any longer. Hence, we want to reassign items by incorporating the existence of new items. One way to redistribute items is to compute a new envy-free matching from scratch. However, this requires the agents first to release their items, which will results in the decrease of their utilities. Our proposal here is to exchange items one by one so that the intermediate matchings are all envy-free and no agent decreases her utility at any moment during the procedure. In this paper, we call a matching obtained by the process above a reformist envy-free matching. A reformist envy-free matching can depend on the choice of an initial envy-free matching and the sequence of exchanges. Our first result states that the exchange sequence does not affect the resulting reformist envy-free matching. Namely, a reformist envy-

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

free matching uniquely exists up to the choice of an initial envy-free matching (Theorem 1). The definition of a reformist envy-free matching was motivated by a decentralized algorithm. However, the number of steps in this process is not discussed yet. With a decentralized algorithm, we may end up with an extremely long sequence of envy-free matchings until we obtain a reformist envy-free matching. On the other hand, if there is coordination among the agents, they may quickly obtain a reformist envy-free matching. Coordination is modeled as a centralized algorithm in which a central authority declares who should exchange an item next, and agents obey the declarations of the central authority. Since a reformist envyfree matching is unique (Theorem 1), there is no reason for agents to deviate from the orders of the central authority. To formalize the discussion, we consider the following type of algorithms. Until a reformist envy-free matching is obtained, an agent is nominated at each step. Let i be the nominated agent. Then i exchanges the currently assigned item with an unassigned item on the table that is most preferred by i such that the matching after the exchange is still envy-free. The choice of nominated agents can change the number of steps. In the decentralized setting the choice will be done arbitrarily while in the centralized setting the choice is supposed to be done cleverly to minimize the number of steps. Thus, we examine the minimum number of steps to obtain a reformist envy-free matching with respect to a given initial envy-free matching. In what follows, we call a sequence of exchanges to obtain the reformist envy-free matching a reformist sequence, and we call the problem of finding a shortest reformist sequence the shortest reformist sequence problem. We define the decision version of the shortest reformist sequence problem as the problem where we are given an envy-free matching µ and a positive integer ℓ, and we determine whether there is a reformist sequence of length at most ℓwith respect to the initial envy-free matching µ. To justify the study of the shortest reformist sequence problem, we first show that coordination sometimes makes sense by giving an example in which the maximum number of steps can be arbitrarily larger than the minimum number of steps (Theorem 2). Then, we prove that the decision version of the shortest reformist sequence problem is NP-complete even if each agent accepts at most four items (i.e., the preference list of each agent contains at most four items) and each item appears in the preference lists of at most three agents (Theorem 3). On the other hand, the shortest reformist sequence problem can be solved in polynomial time if each agent accepts at most three items (Theorem 4) or each item appears in the preference lists of at most two agents (Theorem 5). With the NP-completeness result, we consider two established approaches to cope with NP-completeness, namely approximation and fixed-parameter tractability. For approximation, we indeed prove that the shortest reformist sequence problem is hard to approximate within the factor of c ln n for some constant c, where n is the number of agents (Theorem 7). For fixed-parameter tractability, we have several choices of parameters. When the length ℓof a reformist sequence is chosen as a parameter, (the decision version of)

the shortest reformist sequence problem is fixed-parameter tractable (Theorem 8). On the other hand, When ℓ n is chosen as a parameter, the problem is W[1]-hard (Theorem 9), where n is the number of agents. The choice of the parameter comes from the property that the length of a reformist sequence is at least n after preprocessing and thus the parameter is considered the number of redundant steps in the reformist sequence. On the other hand, when the number of intermediate items is chosen as a parameter, the problem is fixed-parameter tractable (Theorem 10). Here, intermediate items are items that are not assigned in the initial envyfree matching or in the reformist envy-free matching.

1.1 Related Work

The concept of envy-freeness is often used in the literature of social choice theory. For example, Gan, Suksompong, and Voudouris (Gan, Suksompong, and Voudouris 2019) considered the problem of checking the existence of an envy-free item matching in the situation where any agent accepts all the items and the preferences may contain ties. They proved that we can determine whether there is an envy-free item matching in polynomial time. Beynier et al. (Beynier et al. 2019) considered envy-freeness on an envy relationship network. Envy-freeness is also studied in the literature on fair division of divisible goods such as cake cutting (e.g. (Procaccia 2016; Aziz and Mackenzie 2020; Goldberg, Hollender, and Suksompong 2020)), on fair division of indivisible goods with numerical valuations (e.g. (Bouveret, Chevaleyre, and Maudet 2016; Chaudhury, Garg, and Mehlhorn 2020)), and in two-sided markets such as the hospitals/residents problem (e.g. (Wu and Roth 2018; Yokoi 2020; Krishnaa et al. 2020)). Problems of improving a given item allocation via some operations have been considered in the study of item allocations. Gourv es, Lesca, and Wilczynski (Gourv es, Lesca, and Wilczynski 2017) considered the problem of determining whether a target item allocation can be reached via rational swaps on a social network. Furthermore, they considered that the problem of determining whether some specified agent can get a target item via rational swaps (see also (Brandt and Wilczynski 2019; Huang and Xiao 2020)). Our problems are closely related to the study of combinatorial reconfiguration. In combinatorial reconfiguration, we consider problems where we are given an initial configuration and a target configuration of some combinatorial objects, and the goal is to check the reachability between these two configurations via some specified operations. The study of algorithmic aspects of combinatorial reconfiguration was initiated in (Ito et al. 2011). See, e.g., (Nishimura 2018) for a survey of combinatorial reconfiguration.

2 Preliminaries

Throughout this paper, a finite set of n agents is denoted by N, and a finite set of m items is denoted by M. Each agent i N is associated with a subset Mi M and a strict total order i on Mi: Mi represents the set of acceptable items for i, and i represents the preference of i over Mi. For each agent i N, we define mi := |Mi|. For each agent i N,

if Mi = {x1, x2, . . . , xmi} and x1 i x2 i i xmi, then we describe i by i : x1, x2, . . . , xmi. For each agent i N and each pair x, y M of items, we write x i y if x i y or x = y. Note that i satisfies transitivity, i.e., if x i y and y i z, then x i z. An injective mapping µ: N M is called a matching if µ(i) Mi for every agent i N. For each matching µ, an item x M is assigned if there exists an agent i N such that µ(i) = x; otherwise x is unassigned. A matching µ is envy-free if there exists no pair i, j N of distinct agents such that µ(j) i µ(i). For each matching µ, we denote the set of unassigned items for µ by M µ. Let µ, σ be envy-free matchings. We write µ ; σ if there exists an agent i N with the following two conditions: (i) σ(i) i µ(i); (ii) µ(j) = σ(j) for every agent j N \ {i}. Intuitively, if items are assigned to the agents according to µ and µ ; σ, then σ(i) M µ and i has an incentive to exchange her item µ(i) with σ(i) and the resulting matching is still envy-free. This way, the operation ; unilaterally improves the current envy-free matching µ to a new envyfree matching σ. Let µ, σ be envy-free matchings. If there exist envy-free matchings µ0, µ1, . . . , µℓsuch that (1) µ0 = µ, µℓ= σ, (2) µt ; µt+1 for every integer t {0, 1, . . . , ℓ 1}, and (3) there exists no envy-free matching µ such that µℓ; µ , then σ is called a reformist envy-free matching with respect to µ. Intuitively, a reformist envy-free matching with respect to µ is an envy-free matching that is obtained from µ as an outcome of the iterative improvement. We conclude this section with a small example.

Example Consider 2 agents N = {1, 2} and 5 items M = {x, y, p, q, r} with preferences

1: p, r, q, x and 2: q, p, y.

Let µ be a matching satisfying µ(1) = x and µ(2) = y. Then it is confirmed to be envy-free. However, in the matching µ, agent 1 has an incentive to exchange her current item x with r, and such exchange does not arouse envy in agent 2. Thus we can improve µ to µ1, where (µ1(1), µ1(2)) = (r, y), which we denote by µ ; µ1. Similarly, we have µ1 ; µ2 ; µ3, where (µ2(1), µ2(2)) = (r, q) and (µ3(1), µ3(2)) = (p, q). Since p and q are the most preferred items for the agents, µ3 is a reformist envy-free matching.

3 Uniqueness We first observe that a reformist envy-free matching with respect to an envy-free matching can be obtained in polynomial time. In fact, since one exchange strictly improves the current matching, the number of exchanges to obtain a reformist envy-free matching is at most |M| |N|. We prove that the obtained reformist envy-free matching is unique up to the choice of an initial envy-free matching. Theorem 1. Let µ be an envy-free matching. Then a reformist envy-free matching with respect to µ uniquely exists.

Proof. The existence is immediate from the definition. We prove the uniqueness. Suppose to the contrary that there exist reformist envy-free matchings σ and τ with respect to µ

such that σ = τ. Without loss of generality, we can assume that there exists an agent i N such that σ(i) i τ(i). Suppose that for envy-free matchings σ0, σ1, . . . , σℓ, we have µ = σ0 ; σ1 ; ; σℓ= σ. Since τ is a reformist envy-free matching with respect to µ, τ(j) j σ0(j) holds for every agent j N. Let t be the minimum integer in {1, 2, . . . , ℓ} such that σt(i) i τ(i) for some agent i N. Then τ(j) j σt(j) holds for every agent j N \ {i}. If there is an agent j N \ {i} such that τ(j) = σt(i), then τ(j) i τ(i), which contradicts the assumption that τ is envy-free. This implies that τ(j) = σt(i) holds for every agent j N \ {i}, which means σt(i) M τ. Hence, under the matching τ, the agent i can exchange τ(i) with σt(i) to obtain another matching τ . Since τ is a reformist envyfree matching, the resulting matching τ is not envy-free. That is, there is an agent j N \ {i} such that τ (i) j τ (j) = τ(j). For such an agent j N \ {i}, we have σt(i) = τ (i) j τ(j) j σt(j). However, this means that the agent j has envy for i on σt, which contradicts the fact that σt is envy-free. This completes the proof.

Theorem 1 has a consequence for the following reconfiguration question. Namely, we are given two envy-free matchings µ and τ, and asked to determine whether τ is obtained from µ by the iterative improvement. The proof is omitted.

Corollary 1. For two envy-free matchings µ, τ, we can determine in polynomial time whether there exists a sequence of envy-free matchings µ = µ0, µ1, . . . , µℓ= τ such that µt ; µt+1 for every integer t {0, 1, . . . , ℓ 1}.

4 Shortest Reformist Sequence: Hardness To justify the study of the shortest reformist sequence problem, we first give an example in which the maximum length of a reformist sequence can be arbitrarily larger than the minimum length. The proof is omitted.

Theorem 2. For any positive integer p, there is an instance of the shortest reformist sequence problem with three agents and 2p + 3 items such that there is a reformist sequence of length 2p 1 while the shortest reformist sequence has length at most four.

As it turns out, (the decision version of) the shortest reformist sequence problem is NP-complete.

Theorem 3. The decision version of the shortest reformist sequence problem is NP-complete even when mi 4 for every agent i N and |{i N | x Mi}| 3 for every item x M.

Proof. We first observe that the problem is in NP. This is because one exchange strictly improves the current matching, and hence the maximum number of exchanges in the reformist sequence is at most |M| |N|. We reduce the vertex cover problem in 3-regular graphs to the decision version of the shortest reformist sequence problem. In the vertex cover problem, we are given an undirected graph G = (V, E) and a positive integer k, and we are asked to determine whether G has a subset S V such that |S| k and every edge e E has one of its endvertices in S (i.e., S e = ). Such a vertex subset S is called a vertex

cover. It is known (Karp 1972) that the vertex cover problem is NP-complete even when a given graph is 3-regular. Let G = (V, E) be a 3-regular graph as an instance of the vertex cover problem. We construct an instance of the decision version of the shortest reformist sequence problem as follows. For each edge e E, we prepare four agents e1, e2, e3, e4, and for each vertex v V , we prepare eight agents v1, v2, . . . , v8. Thus, there are 4|E| + 8|V | agents:

N := {eℓ| e E, ℓ {1, 2, 3, 4}}

{vℓ| v V, ℓ {1, 2, . . . , 8}}.

We set M := {ri, si | i N} {ye,u, ye,v | e = {u, v} E} {tv | v V } {xv,e | v V, e δ(v)},

where δ(v) denotes the set of edges incident to v. Note that |δ(v)| = 3 for every vertex v V since G is 3-regular. For each edge e = {u, v} E, the agents e1, e2, e3, e4 have the following preferences:

e1 : re1, ye,v, re2, se1, e2 : re2, re3, xv,e, se2, e3 : re3, ye,u, re4, se3, e4 : re4, re1, xu,e, se4.

For each vertex v V with δ(v) = {e, f, g}, we define the preferences of the associated 8 agents as follows:

v1 : rv1, tv, rv2, sv1, v2 : rv2, rv3, rv4, sv2, v3 : rv3, ye,v, yf,v, sv3, v4 : rv4, yg,v, sv4, v5 : rv5, rv1, sv5, v6 : rv6, rv1, sv6, where rv6 = xv,e, v7 : rv7, rv5, sv7, where rv7 = xv,f, v8 : rv8, rv5, sv8, where rv8 = xv,g.

The initial matching µ is defined to be µ(i) = si for each agent i N. Then by Claim 1 below, a reformist envy-free matching σ with respect to µ is σ(i) = ri for each agent i N. We observe that each agent i N has a set Mi of size at most four, and each item appears in Mi for at most three agents i N.

Claim 1. If G has a vertex cover of size k, then there exists a reformist sequence of length |N| + |E| + k.

Proof. Let S be a vertex cover of size k in G. Consider the following reformist sequence.

1. For each vertex v S, the agents v1, v2, v3, v4 are nominated one by one as follows. The agent v1 exchanges sv1 with tv. Then v2 exchanges sv2 with rv2, and v3 and v4 exchange sv3 and sv4 with rv3 and rv4, respectively. This takes 4 steps for each vertex v S. 2. For each edge e = {u, v} E, the agents e1, e2, e3, e4 are nominated one by one. Since S is a vertex cover, u or v belongs to S. By symmetry, suppose that v S. The agent e1 exchanges se1 with ye,v, which can be done because ye,v has no envy from v3 or v4 due to Step 1. Then the agent eℓexchanges seℓwith reℓin the order of ℓ= 2, 3, 4. Finally, the agent e1 exchanges ye,v with re1. This takes 5 steps for each edge e E.

3. For each vertex v V and each integer ℓ {6, 7, 8}, vℓexchanges svℓwith rvℓ, and then v5 exchanges sv5 with rv5. This can be done since rvℓhas no envy from the other agents for each integer ℓ {6, 7, 8} due to Step 2. This takes 4 steps for each vertex v V . 4. For each vertex v S, v1 exchanges tv with rv1. This takes 1 step for each vertex v S. 5. For each vertex v V \ S, the four agents vℓexchange svℓwith rvℓin the order of ℓ= 1, 2, 3, 4. This takes 4 steps for each vertex v V \ S.

The total number of steps in the reformist sequence is 4k + 5|E| + 4|V | + k + 4(|V | k) = 8|V | + 5|E| + k. Since |N| = 8|V | + 4|E|, this is equal to |N| + |E| + k.

Claim 2. If there exists a reformist sequence of length |N|+ |E| + k, then G has a vertex cover of size k.

Proof. Consider a reformist sequence with minimum length. We first observe the following because of the minimality.

For each vertex v V , the agents v2, . . . , v8 exchange svℓwith rvℓin the reformist sequence, since moving to an intermediate item is redundant, i.e., moving to an intermediate item does not improve the situation of the other agents. We note that the agent v1 may use tv. Thus, for each vertex v V , we spend eight or nine steps. For each edge e = {u, v} E, the agent e2 (e4, resp.,) exchanges se2 with re2 (se4 with re4, resp.,) in the sequence. Moreover, only one of ye,u or ye,v must be used in the sequence. Thus, for each edge e E, we spend exactly 5 steps.

Define S as the set of v V such that the agent v1 possesses tv at some point. Then the number of steps is 8|V | + |S| + 5|E|. By the assumption with |N| = 8|V | + 4|E|, it follows that |S| k. We will claim that S is a vertex cover of G. Indeed, suppose to the contrary that S is not a vertex cover. Then there is some edge e = {u, v} E such that u S and v S. That is, neither tu nor tv is used in the sequence. This means that, in the sequence, ye,u and ye,v always have envy from one of uℓ s and vℓ s, respectively, and hence neither the agents e1 nor e3 can exchange items, which is a contradiction.

By Claims 1 and 2, the vertex cover problem in 3-regular graphs is reduced to the decision version of the shortest reformist sequence problem, which completes the proof.

5 Shortest Reformist Sequence: Algorithms 5.1 Preprocessing Here we present some basic observations for the shortest reformist sequence problem. Suppose that µ is an initial envy-free matching. Then, as mentioned in Section 3, the reformist matching σ with respect to µ can be found in polynomial time. If µ(i) i x for some i N and x Mi, then we can remove x from Mi because i never envies an agent having x. If x i σ(i) for some i N and x Mi, then we can remove x from the instance because i always envies an agent having x. Hence, we may assume that σ(i) i x i µ(i) for

every item x Mi. We may also assume that σ(i) i µ(i) for every agent i N, as we can simply remove agents i with σ(i) = µ(i). This implies that the length of every reformist sequence must be at least n. We denote S = {µ(i) | i N} and R = {σ(i) | i N}. Then S R = holds. In fact, suppose that there exist two agents i, j such that µ(i) = σ(j). Then, µ(i) j µ(j) since σ(j) j µ(j) and µ(i) = µ(j). However, this contradicts the envy-freeness of µ. Those assumptions can be ensured in polynomial time, and thus in the following we assume that given instances satisfy those properties.

5.2 Preferences of Length Three While Theorem 3 says the shortest reformist sequence problem is NP-hard when each agent has at most four acceptable items, we show that, if each agent has at most three acceptable items, then the shortest reformist sequence problem is polynomial-time solvable.

Theorem 4. If mi 3 for every agent i N, then a shortest reformist sequence can be found in polynomial time.

Proof. We prove that there is a reformist sequence of length n = |N|, and such a sequence can be found in polynomial time. Since n is a lower bound on the length of a reformist sequence (see Section 5.1), the obtained sequence is optimal. Let µ and σ be an initial envy-free matching and the reformist envy-free matching with respect to µ, respectively. As mentioned in Section 5.1, we may assume that {σ(i) | i N} and {µ(i) | i N} are disjoint. Thus, we may assume that each agent i N has preferences σ(i) i b(i) i µ(i) by appending a dummy item b(i) if mi < 3. We claim that there exists an agent i N such that i can exchange µ(i) with σ(i) keeping envy-freeness. If this claim is true, by repeatedly finding such an agent and removing her, we can find a reformist sequence of length n, which completes the proof. To find such an agent, we construct an auxiliary directed graph D = (N, A) where, for each pair i, j N, an arc (i, j) A exists if and only if σ(i) = b(j). The existence of the arc (i, j) means that i cannot exchange to σ(i) before j gets σ(j). Since σ is a reformist envy-free matching with respect to µ, there does not exist a directed cycle in D, that is, D is acyclic. Hence D has a sink i N. Since σ(i) = b(j) for every agent j N, the agent i can exchange µ(i) with σ(i). Thus the claim follows.

5.3 Items Are Acceptable to at Most Two Agents By Theorem 3, the shortest reformist sequence problem is NP-hard when each item is acceptable to at most three agents. Here, we show that, if every item is acceptable to at most two agents, then the shortest reformist sequence problem is polynomial-time solvable.

Theorem 5. If |{i N | x Mi}| 2 for every item x M, then we can obtain a shortest reformist sequence in polynomial time.

To this end, we introduce a slightly generalized version of the original problem. Let µ be an initial envy-free matching

and σ the reformist envy-free matching with respect to µ. For each agent i N, we are given an item xi Mi, and define Li := {x Mi | x i xi} as the target set of i. Note that Li consists of the best |Li| items with respect to i. Denote L := {Li | i N}. In addition, we are given a partition N := {N1, N2, . . . , Nk} of N. We generalize the concept of envy according to the target sets L and the partition N as follows. Suppose that an agent i is in Na and an agent j is in Nb. For a matching µ , we say that i has (L, N)-envy for j on µ if µ (j) i µ (i) if a = b, µ (j) i µ (i) and µ (i ) / Li ( i Na) if a = b.

The definition says that an agent i has envy for j if the agent i prefers µ (j) to µ (i), except in the case when i and j are in different groups and some agent i in the same group as i has an item in Li. In other words, if some agent i is assigned an item in her target set Li , then agents in the same group as i have no envy for agents in the other groups. A matching µ is said to be (L, N)-envy-free if every agent i N has no (L, N)-envy for any agent j N \ {i} on µ . An (L, N)-envy-free matching µ is said to be satisfactory if, for each index a {1, 2, . . . , k}, there is an agent i Na such that µ (i) Li. Since an envy-free matching is (L, N)-envy-free and the reformist envy-free matching is satisfactory, there always exists a sequence µ ; ; σ of (L, N)-envy-free matchings from µ to some satisfactory matching σ . In what follows, we consider the problem of finding such a sequence with minimum length. The following theorem shows that the problem defined above can be solved in polynomial time if every item is acceptable by at most two agents. Theorem 6. If |{i N | x Mi}| 2 for every item x M, then a shortest sequence of (L, N)-envy-free matchings to some satisfactory matching can be found in polynomial time. We remark that, if |Na| = 1 for every a {1, 2, . . . , k} and |Li| = 1 for every agent i N, the above problem is equivalent to the shortest reformist sequence problem. Thus, Theorem 5 immediately follows from Theorem 6.

Proof of Theorem 6. We denote by ℓ(L, N) the length of a shortest sequence from an initial matching µ to some satisfactory matching. If the value P i N |Mi \ Li| is zero, then µ is satisfactory, which implies ℓ(L, N) = 0. We assume P i N |Mi \ Li| > 0. In the following, we construct in polynomial time a new instance (L , N ) with the set N of agents, where N is a partition of N and L := {L i | i N } is the set of the target sets L i , satisfying the following two conditions.

C1. P i N |Mi \ L i | + |N | < P i N |Mi \ Li| + |N|. C2. ℓ(L , N ) = ℓ(L, N) c, where the value c can be computed in polynomial time from the original instance (L, N).

If such an instance can be constructed, then we can obtain ℓ(L, N) in polynomial time by recursive computation: the condition C1 implies that the number of recursive calls is

bounded by P i N |Mi|+|N|; the condition C2 verifies that each recursive call can be preformed in polynomial time and that we can compute ℓ(L, N) from ℓ(L , N ). We first consider a simple case where there exist an index a {1, 2, . . . , k} and an agent i Na such that µ(i) Li. Then we define N := N \ Na, N := N \ {Na}, and L i := Li for each agent i N . Moreover, we set an initial envy-free matching as the restriction of µ to N . Then the new instance satisfies the conditions C1 and C2 since |N | < |N| and ℓ(L , N ) = ℓ(L, N). A similar argument can be applied to the case when there exist an index a {1, 2, . . . , k} and an agent i Na such that µ(i) / Li but a matching µ obtained from µ by exchanging µ(i) with some x Li is (L, N)-envy-free. In this case, we define N := N \ Na, N := N \ {Na}, and L i := Li for each agent i N . We set an initial envy-free matching as the restriction of µ to N . Then the new instance satisfies the conditions C1 and C2 since |N | < |N| and ℓ(L , N ) = ℓ(L, N) 1. Therefore, we may assume the following. ( ) For any agent i, µ(i) Li and any item x Li receives (L, N)-envy from some agent on µ(i). Since each item is acceptable to at most two agents, there exists exactly one agent that has (L, N)-envy for an item x Li. We construct a new instance (L , N ) as follows. Let N := N. We define the directed graph D = (V, A) by

V := {1, 2, . . . , k}, A := {(a, b) V V | a = b, i Na, j Nb, Mi Lj = }.

Roughly, Mi Lj = means that j cannot receive some item in Lj because of (L, N)-envy from i. We decompose D into strongly connected components. Let S V be a source component of the decomposition (i.e., no arc in A enters S). We define the partition N of N by merging {Na | a S} into one part, i.e., N := N \ {Na | a S} {NS}, where we define NS := S a S Na. Let X := S i NS Li. For each agent i NS, we denote by x i be the item in X Mi that is minimum with respect to i. We define L = {L i | i N } by

L i := {x Mi | x i x i } if i NS, Li if i N \ NS.

We set µ as the initial matching in the resulting instance. Note that µ is an (L , N )-envy-free matching. Claims 3 and 4 below show that the resulting instance satisfies the conditions C1 and C2, respectively.

i N |Mi \ L i | < P

i N |Mi \ Li|.

Proof. By definition, L i Li holds for every agent i NS. Hence, it suffices to show L i Li for some agent i NS. Suppose, to the contrary, that L i = Li for every agent i NS. Take an arbitrary sequence of (L, N)-envy-free matchings from µ to some satisfactory matching. Let µ denote the first (L, N)-envy-free matching in the sequence with µ (i) Li for some agent i NS. Recall here that µ (i) belongs to the sets of acceptable items of two agents;

one is i and the other is denoted by j. Since S is a source component of D, the group Nb having j belongs to NS. Since µ (i) X, we see that µ (i) L j. Since L j = Lj by assumption, µ (i) particularly belongs to Lj, which implies that j has (L, N)-envy for i. This is a contradiction to the (L, N)-envy-freeness of µ .

Claim 4. ℓ(L , N ) = ℓ(L, N) |S|.

Proof. Let ℓ:= ℓ(L, N) and ℓ := ℓ(L , N ). We first show ℓ ℓ |S|. Consider a shortest sequence µ =: µ0 ; µ1 ; ; µℓof (L, N)-envy-free matchings from µ to some satisfactory (L, N)-envy-free matching µℓ. For each a S, we denote by pa the minimum index such that µpa(i) Li for some agent i Na. Let b S be the index that satisfies pb = min{pa | a S}, and ib Nb be the agent such that µpb(ib) Lib. Then, by assumption ( ), the item µpb(ib) is acceptable to another agent j in some group Na, meaning that either a = b or D has an arc (a, b). Since S is a source component, we see a S. By the definition of pb, we observe that µpb 1(j) j µpb(ib), which implies that µpb 1(j) L j \Lj as µpb(ib) X. Thus, in the (pb 1)-st step, the agent j NS has an item in the new target set L j. We construct a sequence of (L , N )-envy-free matchings as follows. For p with pb p ℓ, define a matching µ p to be µ p(i) = µpb 1(i) if i NS and µ p(i) = µp(i) otherwise. Then the sequence (µ0, µ1, . . . , µpb 1, µ pb, . . . , µ ℓ) forms that of (L , N )-envy-free matchings from µ to some satisfactory (L , N )-envy-free matching. Furthermore, since µ pa = µ pa 1 holds for all a S, we can remove µ pa s from the sequence. This implies that there exists a sequence of (L , N )-envy-free matchings whose length is ℓ |S|. Thus ℓ ℓ |S| holds. We next show ℓ ℓ |S|. Consider a shortest sequence µ =: µ0 ; µ1 ; ; µℓ of (L , N )-envyfree matchings from µ to some satisfactory (L , N )-envyfree matching µℓ . Let p be the minimum index such that µp(i0) L i0 for some a0 S and i0 Na0. We observe that µp(i0) particularly belongs to L i0 \ Li0. In fact, suppose that µp(i0) Li0. Then the item µp(i0) is acceptable to another agent by assumption ( ). Since S is a source component, there exist an index b S and j Nb such that µp(i0) Mj. Since µp(i0) L j and µp 1(j) j µp(i0), we have µp 1(j) L j. This contradicts the definition of p. Let x1 := x i0. Then there exist a1 S and i1 Na1 such that x1 Li1. Moreover, since µp(i0) = x1 as µp is (L , N )-envy-free, it follows that µp(i0) i0 x1. Hence, the matching σ1 obtained from µp by assigning x1 to i1 is (L, N)-envy-free. By this change, Na1 has the agent i1 with an item in her target set, and hence any agent in Na1 has no (L, N)-envy for agents in the other groups on σ1. Suppose that there exists some a2 S with (a1, a2) A. Then there exist i Na1 and i2 Na2 such that Mi Li2 contains an item, say x2. Since the agent i has no (L, N)- envy for agents in Na2 on σ1, the matching σ2 obtained from σ1 by assigning x2 to i2 is (L, N)-envy-free. This change makes Na2 have the agent i2 with an item in her target set. We repeat the above procedure; for j = 2, 3, . . . , we find

an index aj S \ {a1, . . . , aj 1} such that there exists an arc to aj from {a1, . . . , aj 1}, and obtain an (L, N)-envyfree matching by exchanging an item for some agent in Naj. Since D[S] forms a strongly connected component of D, the repetition can be performed until, for all a S, some agent in Na has an item in her target set. Thus we obtain a sequence µp ; σ1 ; σ2 ; ; σ|S| of (L, N)-envyfree matchings in which for each a S there is an agent i Na with σ|S|(i) Li. For q with p + 1 q ℓ , we define a matching µ q to be µ q(i) = σ|S|(i) if i NS and µ q(i) = µq(i) otherwise. Then µ0 ; ; µp ; σ1 ; ; σ|S| ; µ p+1 ; ; µ ℓ forms a sequence of (L, N)-envy-free matchings from µ to a satisfactory (L, N)-envy-free matching µ ℓ . This implies ℓ ℓ + |S|.

It follows from the above claims that we can recursively compute ℓ(L, N) in polynomial time. Since the above proofs are constructive, we can find a shortest sequence as well in polynomial time. This completes the proof.

6 Coping with NP-Hardness

To cope with NP-hardness of the shortest reformist sequence problem, we need to compromise either obtaining exact solutions or computing in polynomial time. All the proofs in this section are omitted. The compromise of exact solutions leads us to the possibility of approximation algorithms. A polynomial-time algorithm for the shortest reformist sequence problem approximates within a factor of α 1 if for all instances, the length of the reformist sequence that is obtained as the output of the algorithm is at most as long as α times the shortest length of a reformist sequence. The smaller value of α means a better approximation guarantee. It turns out that even an approximation is hard to obtain. The following theorem gives a precise statement of the sentence above.

Theorem 7. The shortest reformist sequence problem is inapproximable in polynomial time within a factor of c ln n for some constant c > 0, unless P = NP.

The proof reduces the set cover problem to the shortest reformist sequence problem. It is known (Dinur and Steurer 2014) that the set cover problem is inapproximable within a factor of (1 ε) ln n for every ε > 0 unless P = NP. On the other hand, the compromise of polynomial-time computability leads us to fixed-parameter tractability. In fixed-parameter tractability, we extract a certain value k from the instance as a parameter, and allow the running time of the form O(f(k)p(m, n)), where f is an arbitrary (but usually computable) function and p is a polynomial. An algorithm with such a running time is called a fixed-parameter algorithm, and the problem with a fixed-parameter algorithm is called fixed-parameter tractable. For the shortest reformist sequence problem, we have several choices of natural parameters. First, we study the shortest length ℓof a reformist sequence as a parameter. With this choice, the problem is fixed-parameter tractable.

Theorem 8. The decision version of the shortest reformist sequence problem parameterized by the length ℓof a sequence is fixed-parameter tractable. As the second choice, we study the shortest length ℓof a reformist sequence minus the number n of agents as a parameter. Since the shortest length is at least n (see Section 5.1), this parameter can be seen as the number of extra steps needed to obtain the reformist envy-free matching. The next theorem shows that it is unlikely to obtain a fixed-parameter algorithm with this parameter. Here, W[1]- hardness is a counterpart of NP-hardness in fixed-parameter tractability. The proof reduces the multi-colored clique problem, which is known to be W[1]-hard when the number of parts is a parameter (Fellows et al. 2009; Pietrzak 2003). Theorem 9. It is W[1]-hard to decide whether there exists a reformist sequence of length at most n + k when k is a parameter. Third, we study the problem parameterized by the number of intermediate items. Let K denote the set of all the intermediate items from the initial envy-free matching µ to the reformist envy-free matching σ, namely, K := M \ {µ(i), σ(i) | i N}. Note that the preprosessing in section 5.1 does not increase |K|, and |K| = m 2n holds after the preprocessing. We prove that the shortest reformist sequence problem parameterized by |K| is fixed-parameter tractable. Theorem 10. The shortest reformist sequence problem parameterized by |K| is fixed-parameter tractable. The proof designs a fixed-parameter algorithm by preprocessing and branching. The running time is O(2|K|p(m, n)) for some polynomial p.

7 Conclusion We studied a process of iterative improvement of envy-free matchings in the house allocation problem, and defined a reformist envy-free matching as an outcome of the process. We proved that a reformist envy-free matching is unique up to the choice of an initial envy-free matching. Then, we studied the shortest reformist sequence problem and showed a contrast between NP-hardness and polynomial-time solvability with respect to the lengths of preference lists of agents and the number of occurrences of each item in the preference lists. Several questions remain unsolved. As for approximation, we proved the inapproximability of factor c ln n for some constant c. On the other hand, we do not know any approximation algorithm. As for fixed-parameter tractability, we showed an fixed-parameter algorithm when the length of a reformist sequence or the number of intermediate items is a parameter. On the other hand, we do not know this is also the case when n is a parameter. Another direction of research may look at the case where preferences may contain a tie or a pair of incomparable items.

Acknowledgments This work was supported by JSPS KAKENHI Grant Numbers JP18H04091, JP19K11814, JP20H05793, JP20H05795, JP20K11670, JP20K23323, JP18H05291, JP19H05485, and JP21H03397, Japan. We thank the reviewers and the meta-reviewers for their helpful comments.

References Aziz, H.; and Mackenzie, S. 2020. A bounded and envy-free cake cutting algorithm. Communications of the ACM, 63(4): 119 126. Beynier, A.; Chevaleyre, Y.; Gourv es, L.; Harutyunyan, A.; Lesca, J.; Maudet, N.; and Wilczynski, A. 2019. Local envyfreeness in house allocation problems. Autonomous Agents and Multi-Agent Systems, 33(5): 591 627. Bouveret, S.; Chevaleyre, Y.; and Maudet, N. 2016. Fair Allocation of Indivisible Goods. In Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D., eds., Handbook of Computational Social Choice, 284 310. Cambridge University Press. Brandt, F.; and Wilczynski, A. 2019. On the Convergence of Swap Dynamics to Pareto-Optimal Matchings. In Proceedings of the 15th Conference on Web and Internet Economics Web and Internet Economics, volume 11920 of Lecture Notes in Computer Science, 100 113. Chaudhury, B. R.; Garg, J.; and Mehlhorn, K. 2020. EFX Exists for Three Agents. In Proceedings of the 21st ACM Conference on Economics and Computation, 1 19. Dinur, I.; and Steurer, D. 2014. Analytical Approach to Parallel Repetition. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, 624 633. Fellows, M. R.; Hermelin, D.; Rosamond, F.; and Vialette, S. 2009. On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science, 410(1): 53 61. Gan, J.; Suksompong, W.; and Voudouris, A. A. 2019. Envy Freeness in House Allocation Problems. Mathematical Social Sciences, 101: 104 106. Goldberg, P.; Hollender, A.; and Suksompong, W. 2020. Contiguous Cake Cutting: Hardness Results and Approximation Algorithms. Journal of Artificial Intelligence Research, 69: 109 141. 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 Artificial Intelligence, 213 219. Huang, S.; and Xiao, M. 2020. Object reachability via swaps under strict and weak preferences. Autonomous Agents and Multi-Agent Systems, 34(2): 51. Ito, T.; Demaine, E. D.; Harvey, N. J. A.; Papadimitriou, C. H.; Sideri, M.; Uehara, R.; and Uno, Y. 2011. On the complexity of reconfiguration problems. Theoretical Computer Science, 412(12-14): 1054 1065. Karp, R. M. 1972. Reducibility among Combinatorial Problems. In Complexity of Computer Computations, The IBM Research Symposia Series, 85 103.

Klaus, B.; Manlove, D. F.; and Rossi, F. 2016. Matching under Preferences. In Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D., eds., Handbook of Computational Social Choice, 333 355. Cambridge University Press. Krishnaa, P.; Limaye, G.; Nasre, M.; and Nimbhorkar, P. 2020. Envy-Freeness and Relaxed Stability: Hardness and Approximation Algorithms. In Proceedings of the 13th Symposium on Algorithmic Game Theory, volume 12283 of Lecture Notes in Computer Science, 193 208. Manlove, D. F. 2013. Algorithmics of Matching Under Preferences. World Scientific. Nishimura, N. 2018. Introduction to Reconfiguration. Algorithms, 11(4): 52. Pietrzak, K. 2003. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. Journal of Computer and System Sciences, 67(4): 757 771. Procaccia, A. D. 2016. Cake Cutting Algorithms. In Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D., eds., Handbook of Computational Social Choice, 311 330. Cambridge University Press. Wu, Q.; and Roth, A. E. 2018. The lattice of envy-free matchings. Games and Economic Behavior, 109: 201 211. Yokoi, Y. 2020. Envy-Free Matchings with Lower Quotas. Algorithmica, 82(2): 188 211.