# Reforming an Envy-Free Matching††thanks: A preliminary version will appear
in Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI
2022). This work was supported by JSPS KAKENHI Grant Numbers JP18H04091,
JP19K11814, JP20H05793, JP20H05795, JP20K11670, JP20K23323, JP18H05291,
JP19H05485, JP21H03397.

Takehiro Ito Tohoku University<EMAIL_ADDRESS>Yuni Iwamasa Kyoto
University<EMAIL_ADDRESS>Naonori Kakimura Keio University,
<EMAIL_ADDRESS>Naoyuki Kamiyama Kyushu University,
<EMAIL_ADDRESS>Yusuke Kobayashi Kyoto University,
<EMAIL_ADDRESS>Yuta Nozaki Hiroshima University,
<EMAIL_ADDRESS>Yoshio Okamoto The University of Electro-
Communications<EMAIL_ADDRESS>Kenta Ozeki Yokohama National University,
<EMAIL_ADDRESS>
###### Abstract

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., [14, 16]). 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.”

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 envy-free 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-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 matching 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 envy-free 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 $\mu$ and a positive integer $\ell$,
and we determine whether there is a reformist sequence of length at most
$\ell$ with respect to the initial envy-free matching $\mu$. 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
$\ell$ 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 $\ell-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 envy-free matching or in
the reformist envy-free matching.

#### Related Work

The concept of envy-freeness is often used in the literature of social choice
theory. For example, Gan, Suksompong, and Voudouris [8] 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. [2] 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. [19, 1, 9]), on fair
division of indivisible goods with numerical valuations (e.g. [3, 5]), and in
two-sided markets such as the hospitals/residents problem (e.g. [20, 21, 15]).

Problems of improving a given item allocation via some operations have been
considered in the study of item allocations. Gourvès, Lesca, and Wilczynski
[10] 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 [4, 11]).

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 [12]. See, e.g.,
[17] 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\in N$ is associated
with a subset $M_{i}\subseteq M$ and a strict total order $\succ_{i}$ on
$M_{i}$: $M_{i}$ represents the set of acceptable items for $i$, and
$\succ_{i}$ represents the preference of $i$ over $M_{i}$. For each agent
$i\in N$, we define $m_{i}:=|M_{i}|$. For each agent $i\in N$, if
$M_{i}=\\{x_{1},x_{2},\dots,x_{m_{i}}\\}$ and
$x_{1}\succ_{i}x_{2}\succ_{i}\dots\succ_{i}x_{m_{i}}$, then we describe
$\succ_{i}$ by $\succ_{i}\colon x_{1},x_{2},\dots,x_{m_{i}}$. For each agent
$i\in N$ and each pair $x,y\in M$ of items, we write $x\succeq_{i}y$ if
$x\succ_{i}y$ or $x=y$. Note that $\succ_{i}$ satisfies transitivity, i.e., if
$x\succ_{i}y$ and $y\succ_{i}z$, then $x\succ_{i}z$.

An injective mapping $\mu\colon N\to M$ is called a _matching_ if $\mu(i)\in
M_{i}$ for every agent $i\in N$. For each matching $\mu$, an item $x\in M$ is
_assigned_ if there exists an agent $i\in N$ such that $\mu(i)=x$; otherwise
$x$ is _unassigned_. A matching $\mu$ is _envy-free_ if there exists no pair
$i,j\in N$ of distinct agents such that $\mu(j)\succ_{i}\mu(i)$. For each
matching $\mu$, we denote the set of unassigned items for $\mu$ by
$\overline{M}_{\mu}$.

Let $\mu,\sigma$ be envy-free matchings. We write $\mu\leadsto\sigma$ if there
exists an agent $i\in N$ with the following two conditions: (i)
$\sigma(i)\succ_{i}\mu(i)$; (ii) $\mu(j)=\sigma(j)$ for every agent $j\in
N\setminus\\{i\\}$. Intuitively, if items are assigned to the agents according
to $\mu$ and $\mu\leadsto\sigma$, then $\sigma(i)\in\overline{M}_{\mu}$ and
$i$ has an incentive to exchange her item $\mu(i)$ with $\sigma(i)$ and the
resulting matching is still envy-free. This way, the operation “$\leadsto$”
unilaterally improves the current envy-free matching $\mu$ to a new envy-free
matching $\sigma$.

Let $\mu,\sigma$ be envy-free matchings. If there exist envy-free matchings
$\mu_{0},\mu_{1},\dots,\mu_{\ell}$ such that (1) $\mu_{0}=\mu$,
$\mu_{\ell}=\sigma$, (2) $\mu_{t}\leadsto\mu_{t+1}$ for every integer
$t\in\\{0,1,\dots,{\ell}-1\\}$, and (3) there exists no envy-free matching
$\mu^{\prime}$ such that $\mu_{\ell}\leadsto\mu^{\prime}$, then $\sigma$ is
called a _reformist envy-free matching_ with respect to $\mu$. Intuitively, a
reformist envy-free matching with respect to $\mu$ is an envy-free matching
that is obtained from $\mu$ as an outcome of the iterative improvement.

To illustrate envy-free matchings, we introduce a graph representation. Given
a set $N$ of agents, a set $M$ of items, $M_{i}$ and $\succ_{i}$ for all
agents $i\in N$, we create the following directed graph. The vertex set is
$M$, the set of items. For each agent $i\in N$ with
$M_{i}=\\{x_{1},x_{2},\dots,x_{k}\\}$ and $\succ_{i}\colon
x_{1},x_{2},\dots,x_{k}$, we place $k-1$ arcs
$(x_{2},x_{1}),(x_{3},x_{2}),\dots,(x_{k},x_{k-1})$: those arcs are labeled by
$i$. There can be parallel arcs from $x$ to $y$ with different labels, or they
can be identified with a single arc from $x$ to $y$ with multiple labels.

An example is given in Figure 1. There are four agents $1,2,3,4$ and seven
items $a,b,c,d,e,f,g$. The preferences are given as follows:

$\displaystyle\succ_{1}\colon$ $\displaystyle a,b,c,d,e,f,g;$
$\displaystyle\succ_{2}\colon$ $\displaystyle f,d,a,g,e;$
$\displaystyle\succ_{3}\colon$ $\displaystyle b,g,a,c;$
$\displaystyle\succ_{4}\colon$ $\displaystyle d,c,g,e,f.$

The colors are assigned for agents: black for agent $1$, blue for agent $2$,
red for agent $3$, and violet for agent $4$.

Figure 1: A graph representation of an instance.

A matching $\mu$ is identified with a labeled token placement. A token for
each agent $i$ is placed on the vertex $\mu(i)$: the token is labeled by $i$,
and for convenience we denote the token by $i$. Since $\mu$ is a matching, no
vertex holds two or more tokens. If a matching $\mu$ is envy-free, then there
exist no pair of tokens $i,j$ such that $j$ is placed on a vertex that can be
reached from the vertex holding $i$ along arcs labeled by $i$; the converse
also holds. The operation $\mu\leadsto\sigma$ corresponds to moving the token
at $\mu(i)$ to $\sigma(i)$. Labels are often identified with colors in our
figures.

In Figure 2, labeled tokens are placed on vertices. The labels of tokens are
shown by colors. The token $1$ (black) is placed at vertex $b$, the token $2$
(blue) is placed at vertex $d$, the token $3$ (red) is placed at vertex $g$,
and the token $4$ (violet) is placed at vertex $e$. In this example, agent $4$
has an envy for agent $3$ since the token $3$ is placed on the vertex $g$ that
can be reached from the vertex $e$ holding $4$ along arcs labeled by $4$
(i.e., violet arcs). Similarly, agent $3$ has an envy for agent $1$.

Figure 2: A graph representation of a matching with envy.

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

$\displaystyle\succ_{1}:p,r,q,x\quad\text{and}\quad\succ_{2}:q,p,y.$

See Figure 3. Let $\mu$ be a matching satisfying $\mu(1)=x$ and $\mu(2)=y$.
Then it is confirmed to be envy-free. However, in the matching $\mu$, 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 $\mu$ to
$\mu_{1}$, where $(\mu_{1}(1),\mu_{1}(2))=(r,y)$, which we denote by
$\mu\leadsto\mu_{1}$. Similarly, we have
$\mu_{1}\leadsto\mu_{2}\leadsto\mu_{3}$, where $(\mu_{2}(1),\mu_{2}(2))=(r,q)$
and $(\mu_{3}(1),\mu_{3}(2))=(p,q)$. Since $p$ and $q$ are the most preferred
items for the agents, $\mu_{3}$ is the reformist envy-free matching.

Figure 3: A small example.

##  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|\cdot|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 $\mu$ be an envy-free matching. Then a reformist envy-free matching with
respect to $\mu$ 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
$\sigma$ and $\tau$ with respect to $\mu$ such that $\sigma\neq\tau$. Without
loss of generality, we can assume that there exists an agent $i\in N$ such
that $\sigma(i)\succ_{i}\tau(i)$. Suppose that for envy-free matchings
$\sigma_{0},\sigma_{1},\dots,\sigma_{\ell}$, we have
$\mu=\sigma_{0}\leadsto\sigma_{1}\leadsto\dots\leadsto\sigma_{\ell}=\sigma$.
Since $\tau$ is a reformist envy-free matching with respect to $\mu$,
$\tau(j)\succeq_{j}\sigma_{0}(j)$ holds for every agent $j\in N$. Let $t$ be
the minimum integer in $\\{1,2,\dots,\ell\\}$ such that
$\sigma_{t}(i)\succ_{i}\tau(i)$ for some agent $i\in N$. Then
$\tau(j)\succeq_{j}\sigma_{t}(j)$ holds for every agent $j\in
N\setminus\\{i\\}$.

If there is an agent $j\in N\setminus\\{i\\}$ such that
$\tau(j)=\sigma_{t}(i)$, then $\tau(j)\succ_{i}\tau(i)$, which contradicts the
assumption that $\tau$ is envy-free. This implies that
$\tau(j)\neq\sigma_{t}(i)$ holds for every agent $j\in N\setminus\\{i\\}$,
which means $\sigma_{t}(i)\in\overline{M}_{\tau}$. Hence, under the matching
$\tau$, the agent $i$ can exchange $\tau(i)$ with $\sigma_{t}(i)$ to obtain
another matching $\tau^{\prime}$. Since $\tau$ is a reformist envy-free
matching, the resulting matching $\tau^{\prime}$ is not envy-free. That is,
there is an agent $j\in N\setminus\\{i\\}$ such that
$\tau^{\prime}(i)\succ_{j}\tau^{\prime}(j)=\tau(j)$. For such an agent $j\in
N\setminus\\{i\\}$, we have
$\sigma_{t}(i)=\tau^{\prime}(i)\succ_{j}\tau(j)\succeq_{j}\sigma_{t}(j)$.
However, this means that the agent $j$ has envy for $i$ on $\sigma_{t}$, which
contradicts the fact that $\sigma_{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 $\mu$ and $\tau$, and asked to
determine whether $\tau$ is obtained from $\mu$ by the iterative improvement.

######  Corollary 1.

For two envy-free matchings $\mu,\tau$, we can determine whether there exists
a sequence of envy-free matchings $\mu=\mu_{0},\mu_{1},\dots,\mu_{\ell}=\tau$
such that $\mu_{t}\leadsto\mu_{t+1}$ for every integer
$t\in\\{0,1,\dots,{\ell}-1\\}$.

###### Proof.

If there is an agent $i$ such that $\mu(i)\succ_{i}\tau(i)$, then the answer
is No. Therefore, assume that $\tau(i)\succeq_{i}\mu(i)$ for every agent $i$.

The algorithm first removes each item $x$ from the instance if
$x\succ_{i}\tau(i)$ for some agent $i\in N$. Then it computes the reformist
envy-free matching $\sigma$ with respect to $\mu$. If $\sigma=\tau$, then we
know $\tau$ is reached from $\mu$ and the answer is Yes. Otherwise (i.e.,
$\sigma\neq\tau$), there exists an agent $i$ such that
$\tau(i)\succ_{i}\sigma(i)$ since all the items $x$ with $x\succ_{i}\tau(i)$
were already removed from the instance. Since the reformist envy-free matching
with respect to $\mu$ is unique (Theorem 1), $\tau$ cannot be reached from
$\mu$, and the answer must be No. ∎

##  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.

######  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.

###### Proof.

We construct a desired instance as follows. Let $N=\\{1,2,3\\}$ and

$M=\\{a_{\ell},b_{\ell}\mid\ell=1,2,\dots,p\\}\cup\\{r,s,z\\}.$

We define the preferences of the $3$ agents as follows.

$\displaystyle\succ_{1}$ $\displaystyle\colon
a_{p},b_{p},a_{p-1},b_{p-1},\dots,a_{2},b_{2},a_{1},$ $\displaystyle\succ_{2}$
$\displaystyle\colon
b_{p},z,b_{p-1},a_{p},b_{p-2},a_{p-1},\dots,b_{2},a_{3},b_{1},$
$\displaystyle\succ_{3}$ $\displaystyle\colon r,z,s.$

We define the initial matching $\mu$ to be $\mu(1)=a_{1}$, $\mu(2)=b_{1}$, and
$\mu(3)=s$. Then the reformist matching $\sigma$ with respect to $\mu$ is
$\sigma(1)=a_{p}$, $\sigma(2)=b_{p}$, and $\sigma(3)=r$. See Figure 4.

We observe that we can reach $\sigma$ in four steps as follows: the agent $3$
exchanges $s$ with $r$, the agent $2$ exchanges $b_{1}$ with $z$, the agent
$1$ exchanges $a_{1}$ with $a_{p}$, and then the agent $2$ exchanges $z$ with
$b_{p}$. See Figure 5.

On the other hand, if the agent $3$ is nominated after the agents $1$ and $2$,
the number of steps to reach $\sigma$ is $2p-1$ (see Figure 6). In the
beginning, only the agent $1$ can be nominated to exchange $a_{1}$ with
$a_{2}$. Since $b_{2}$ receives no envy from the agent $1$ after the exchange,
the agent $2$ can exchange $b_{1}$ with $b_{2}$. Then, $a_{3}$ has no envy
from the agent $2$, implying that the agent $1$ can exchange $a_{2}$ with
$a_{3}$. In such a way, for an integer $i\in\\{1,2,\dots,p-1\\}$, the
$(2i-1)$-st step exchanges $a_{i}$ with $a_{i+1}$ for the agent $1$, and the
$2i$-th step exchanges $b_{i}$ with $b_{i+1}$ for the agent $2$. In the end,
the two agents reach $a_{p}$ and $b_{p}$. This transformation is unique, and
the number of necessary steps is $2p-2$. Finally, the agent $3$ exchanges $s$
with $r$. Thus the total number of steps is $2p-1$. ∎

Figure 4: Instance in the proof of Theorem 2 with $p=4$. Colors represent
labels, and colored vertices correspond to the items assigned to agents in the
initial matching $\mu$.

Figure 5: Shortest sequence for the instance in the proof of Theorem 2.

Figure 6: A long sequence for the instance in the proof of Theorem 2.

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 $m_{i}\leq 4$ for every agent $i\in N$ and $|\\{i\in N\mid x\in
M_{i}\\}|\leq 3$ for every item $x\in 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|\cdot|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\subseteq V$
such that $|S|\leq k$ and every edge $e\in E$ has one of its endvertices in
$S$ (i.e., $S\cap e\neq\emptyset$). Such a vertex subset $S$ is called a
vertex cover. It is known [13] 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 (see Figure 7). For each edge $e\in E$, we prepare
four agents $e^{1},e^{2},e^{3},e^{4}$, and for each vertex $v\in V$, we
prepare eight agents $v^{1},v^{2},\dots,v^{8}$. Thus, there are $4|E|+8|V|$
agents:

$N:=\\{e^{\ell}\mid e\in E,\,\ell\in\\{1,2,3,4\\}\\}\cup\\{v^{\ell}\mid v\in
V,\,\ell\in\\{1,2,\dots,8\\}\\}.$

We set

$M:=\\{r_{i},s_{i}\mid i\in N\\}\cup\\{t_{v}\mid v\in
V\\}\cup\\{y_{e,u},y_{e,v}\mid e=\\{u,v\\}\in E\\}\cup\\{x_{v,e}\mid v\in
V,e\in\delta(v)\\},$

where $\delta(v)$ denotes the set of edges incident to $v$. Note that
$|\delta(v)|=3$ for every vertex $v\in V$ since $G$ is $3$-regular.

Figure 7: Reduction in the NP-completeness proof (Theorem 3). The vertices
with the same labels should be identified.

For each edge $e=\\{u,v\\}\in E$, the agents $e^{1},e^{2},e^{3},e^{4}$ have
the following preferences:

$\displaystyle\succ_{e^{1}}$ $\displaystyle\colon
r_{e^{1}},y_{e,v},r_{e^{2}},s_{e^{1}},$ $\displaystyle\succ_{e^{2}}$
$\displaystyle\colon r_{e^{2}},r_{e^{3}},x_{v,e},s_{e^{2}},$
$\displaystyle\succ_{e^{3}}$ $\displaystyle\colon
r_{e^{3}},y_{e,u},r_{e^{4}},s_{e^{3}},$ $\displaystyle\succ_{e^{4}}$
$\displaystyle\colon r_{e^{4}},r_{e^{1}},x_{u,e},s_{e^{4}}.$

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

$\displaystyle\succ_{v^{1}}$ $\displaystyle\colon
r_{v^{1}},t_{v},r_{v^{2}},s_{v^{1}},\ \ \ \ \succ_{v^{2}}\colon
r_{v^{2}},r_{v^{3}},r_{v^{4}},s_{v^{2}},$ $\displaystyle\succ_{v^{3}}$
$\displaystyle\colon r_{v^{3}},y_{e,v},y_{f,v},s_{v^{3}},\ \ \ \
\succ_{v^{4}}\colon r_{v^{4}},y_{g,v},s_{v^{4}},$ $\displaystyle\succ_{v^{5}}$
$\displaystyle\colon r_{v^{5}},r_{v^{1}},s_{v^{5}},$
$\displaystyle\succ_{v^{6}}$ $\displaystyle\colon
r_{v^{6}},r_{v^{1}},s_{v^{6}},\quad\text{where\ }r_{v^{6}}=x_{v,e},$
$\displaystyle\succ_{v^{7}}$ $\displaystyle\colon
r_{v^{7}},r_{v^{5}},s_{v^{7}},\quad\text{where\ }r_{v^{7}}=x_{v,f},$
$\displaystyle\succ_{v^{8}}$ $\displaystyle\colon
r_{v^{8}},r_{v^{5}},s_{v^{8}},\quad\text{where\ }r_{v^{8}}=x_{v,g}.$

The initial matching $\mu$ is defined to be $\mu(i)=s_{i}$ for each agent
$i\in N$. Then by Claim 1 below, a reformist envy-free matching $\sigma$ with
respect to $\mu$ is $\sigma(i)=r_{i}$ for each agent $i\in N$. We observe that
each agent $i\in N$ has a set $M_{i}$ of size at most four, and each item
appears in $M_{i}$ for at most three agents $i\in 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. 1.

For each vertex $v\in S$, the agents $v^{1},v^{2},v^{3},v^{4}$ are nominated
one by one as follows. The agent $v^{1}$ exchanges $s_{v^{1}}$ with $t_{v}$.
Then $v^{2}$ exchanges $s_{v^{2}}$ with $r_{v^{2}}$, and $v^{3}$ and $v^{4}$
exchange $s_{v^{3}}$ and $s_{v^{4}}$ with $r_{v^{3}}$ and $r_{v^{4}}$,
respectively. This takes $4$ steps for each vertex $v\in S$.

  2. 2.

For each edge $e=\\{u,v\\}\in E$, the agents $e^{1},e^{2},e^{3},e^{4}$ are
nominated one by one. Since $S$ is a vertex cover, $u$ or $v$ belongs to $S$.
By symmetry, suppose that $v\in S$. The agent $e^{1}$ exchanges $s_{e^{1}}$
with $y_{e,v}$, which can be done because $y_{e,v}$ has no envy from $v^{3}$
or $v^{4}$ due to Step 1. Then the agent $e^{\ell}$ exchanges $s_{e^{\ell}}$
with $r_{e^{\ell}}$ in the order of $\ell=2,3,4$. Finally, the agent $e^{1}$
exchanges $y_{e,v}$ with $r_{e^{1}}$. This takes $5$ steps for each edge $e\in
E$.

  3. 3.

For each vertex $v\in V$ and each integer $\ell\in\\{6,7,8\\}$, $v^{\ell}$
exchanges $s_{v^{\ell}}$ with $r_{v^{\ell}}$, and then $v^{5}$ exchanges
$s_{v^{5}}$ with $r_{v^{5}}$. This can be done since $r_{v^{\ell}}$ has no
envy from the other agents for each integer $\ell\in\\{6,7,8\\}$ due to Step
2. This takes $4$ steps for each vertex $v\in V$.

  4. 4.

For each vertex $v\in S$, $v^{1}$ exchanges $t_{v}$ with $r_{v^{1}}$. This
takes $1$ step for each vertex $v\in S$.

  5. 5.

For each vertex $v\in V\setminus S$, the four agents $v^{\ell}$ exchange
$s_{v^{\ell}}$ with $r_{v^{\ell}}$ in the order of $\ell=1,2,3,4$. This takes
$4$ steps for each vertex $v\in V\setminus 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\in V$, the agents $v^{2},\dots,v^{8}$ exchange
$s_{v^{\ell}}$ with $r_{v^{\ell}}$ 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 $v^{1}$
may use $t_{v}$. Thus, for each vertex $v\in V$, we spend eight or nine steps.

  * •

For each edge $e=\\{u,v\\}\in E$, the agent $e^{2}$ ($e^{4}$, resp.,)
exchanges $s_{e^{2}}$ with $r_{e^{2}}$ ($s_{e^{4}}$ with $r_{e^{4}}$, resp.,)
in the sequence. Moreover, only one of $y_{e,u}$ or $y_{e,v}$ must be used in
the sequence. Thus, for each edge $e\in E$, we spend exactly $5$ steps.

Define $S$ as the set of $v\in V$ such that the agent $v^{1}$ possesses
$t_{v}$ 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|\leq 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\\}\in E$ such that $u\not\in S$ and $v\not\in S$. That is, neither
$t_{u}$ nor $t_{v}$ is used in the sequence. This means that, in the sequence,
$y_{e,u}$ and $y_{e,v}$ always have envy from one of $u^{\ell}$’s and
$v^{\ell}$’s, respectively, and hence neither the agents $e^{1}$ nor $e^{3}$
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 $\mu$ is an initial envy-free matching. Then, as
mentioned in Section 3, the reformist matching with respect to $\mu$ can be
found in polynomial time, which is denoted by $\sigma$. If $\mu(i)\succ_{i}x$
for some $i\in N$ and $x\in M_{i}$, then we can remove $x$ from $M_{i}$
because $i$ never envies an agent having $x$. If $x\succ_{i}\sigma(i)$ for
some $i\in N$ and $x\in M_{i}$, then we can remove $x$ from the instance
because $i$ always envies an agent having $x$. Hence, we may assume that
$\sigma(i)\succeq_{i}x\succeq_{i}\mu(i)$ for every item $x\in M_{i}$. We may
also assume that $\sigma(i)\succ_{i}\mu(i)$ for every agent $i\in N$, as we
can simply remove agents $i$ with $\sigma(i)=\mu(i)$. This implies that the
length of every reformist sequence must be at least $n$.

We denote $S=\\{\mu(i)\mid i\in N\\}$ and $R=\\{\sigma(i)\mid i\in N\\}$. Then
$S\cap R=\emptyset$ holds. In fact, suppose that there exist two agents $i,j$
such that $\mu(i)=\sigma(j)$. Then, $\mu(i)\succ_{j}\mu(j)$ since
$\sigma(j)\succeq_{j}\mu(j)$ and $\mu(i)\neq\mu(j)$. However, this contradicts
the envy-freeness of $\mu$.

Those assumptions can be ensured in polynomial time, and thus in the sequel 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 $m_{i}\leq 3$ for every agent $i\in 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 $\mu$ and $\sigma$ be an initial envy-free matching and the
reformist envy-free matching with respect to $\mu$, respectively.

As mentioned in Section 5.1, we may assume that $\\{\sigma(i)\mid i\in N\\}$
and $\\{\mu(i)\mid i\in N\\}$ are disjoint. Thus, we may assume that each
agent $i\in N$ has preferences $\sigma(i)\succ_{i}b(i)\succ_{i}\mu(i)$ by
appending a dummy item $b(i)$ if $m_{i}<3$.

We claim that there exists an agent $i\in N$ such that $i$ can exchange
$\mu(i)$ with $\sigma(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\in N$, an arc $(i,j)\in A$ exists if and only if
$\sigma(i)=b(j)$ (see Figure 8). The existence of the arc $(i,j)$ means that
$i$ cannot exchange to $\sigma(i)$ before $j$ gets $\sigma(j)$. Since $\sigma$
is a reformist envy-free matching with respect to $\mu$, there does not exist
a directed cycle in $D$, that is, $D$ is acyclic. Hence $D$ has a sink $i\in
N$. Since $\sigma(i)\neq b(j)$ for every agent $j\in N$, the agent $i$ can
exchange $\mu(i)$ with $\sigma(i)$ (see Figure 9). Thus the claim follows. ∎

Figure 8: Algorithm for Theorem 4. (Left) An instance. (Right) The
construction of the directed graph $D$.

Figure 9: Algorithm for Theorem 4. A shortest reformist sequence following the
order $5,4,3,2,1$.

###  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\in N\mid x\in M_{i}\\}|\leq 2$ for every item $x\in 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 $\mu$ be an initial envy-free matching and $\sigma$ the reformist
envy-free matching with respect to $\mu$. For each agent $i\in N$, we are
given an item $x_{i}\in M_{i}$, and define $L_{i}:=\\{x\in M_{i}\mid
x\succeq_{i}x_{i}\\}$ as the target set of $i$. Note that $L_{i}$ consists of
the best $|L_{i}|$ items with respect to $\succ_{i}$. Denote
$\mathcal{L}:=\\{L_{i}\mid i\in N\\}$. In addition, we are given a partition
$\mathcal{N}:=\\{N_{1},N_{2},\dots,N_{k}\\}$ of $N$.

We generalize the concept of envy according to the target sets $\mathcal{L}$
and the partition $\mathcal{N}$ as follows. Suppose that an agent $i$ is in
$N_{a}$ and an agent $j$ is in $N_{b}$. For a matching $\mu^{\prime}$, we say
that $i$ has _$(\mathcal{L},\mathcal{N})$ -envy_ for $j$ on $\mu^{\prime}$ if

$\begin{cases}\mu^{\prime}(j)\succ_{i}\mu^{\prime}(i)&\mbox{if $a=b$},\\\
\mu^{\prime}(j)\succ_{i}\mu^{\prime}(i)\mbox{ and
}\mbox{$\mu^{\prime}(i^{\prime})\notin L_{i^{\prime}}$ ($\forall i^{\prime}\in
N_{a}$)}&\mbox{if $a\neq b$}.\end{cases}$

The definition says that an agent $i$ has envy for $j$ if the agent $i$
prefers $\mu^{\prime}(j)$ to $\mu^{\prime}(i)$, except in the case when $i$
and $j$ are in different groups and some agent $i^{\prime}$ in the same group
as $i$ has an item in $L_{i}$. In other words, if some agent $i^{\prime}$ is
assigned an item in her target set $L_{i^{\prime}}$, then agents in the same
group as $i^{\prime}$ have no envy for agents in the other groups. A matching
$\mu^{\prime}$ is said to be _$(\mathcal{L},\mathcal{N})$ -envy-free_ if every
agent $i\in N$ has no $(\mathcal{L},\mathcal{N})$-envy for any agent $j\in
N\setminus\\{i\\}$ on $\mu^{\prime}$. An $(\mathcal{L},\mathcal{N})$-envy-free
matching $\mu^{\prime}$ is said to be _satisfactory_ if, for each index
$a\in\\{1,2,\dots,k\\}$, there is an agent $i\in N_{a}$ such that
$\mu^{\prime}(i)\in L_{i}$. Since an envy-free matching is
$(\mathcal{L},\mathcal{N})$-envy-free and the reformist envy-free matching is
satisfactory, there always exists a sequence
$\mu\leadsto\dots\leadsto\sigma^{\prime}$ of $(\mathcal{L},\mathcal{N})$-envy-
free matchings from $\mu$ to some satisfactory matching $\sigma^{\prime}$. 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\in N\mid x\in M_{i}\\}|\leq 2$ for every item $x\in M$, then a
shortest sequence of $(\mathcal{L},\mathcal{N})$-envy-free matchings to some
satisfactory matching can be found in polynomial time.

We remark that, if $|N_{a}|=1$ for every $a\in\\{1,2,\dots,k\\}$ and
$|L_{i}|=1$ for every agent $i\in 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 $\ell\left(\mathcal{L},\mathcal{N}\right)$ the length of a
shortest sequence from an initial matching $\mu$ to some satisfactory
matching. If the value $\sum_{i\in N}|M_{i}\setminus L_{i}|$ is zero, then
$\mu$ is satisfactory, which implies
$\ell\left(\mathcal{L},\mathcal{N}\right)=0$.

We assume $\sum_{i\in N}|M_{i}\setminus L_{i}|>0$. In the following, we
construct in polynomial time a new instance
$(\mathcal{L}^{\ast},\mathcal{N}^{\ast})$ with the set $N^{\ast}$ of agents,
where $\mathcal{N}^{\ast}$ is a partition of $N^{\ast}$ and
$\mathcal{L}^{\ast}:=\\{L_{i}^{\ast}\mid i\in N^{\ast}\\}$ is the set of the
target sets $L_{i}^{\ast}$, satisfying the following two conditions.

C1.

$\sum_{i\in N^{\ast}}|M_{i}\setminus L_{i}^{\ast}|+|N^{\ast}|<\sum_{i\in
N}|M_{i}\setminus L_{i}|+|N|$.

C2.

$\ell\left(\mathcal{L}^{\ast},\mathcal{N}^{\ast}\right)=\ell\left(\mathcal{L},\mathcal{N}\right)-c$,
where the value $c$ can be computed in polynomial time from the original
instance $\left(\mathcal{L},\mathcal{N}\right)$.

If such an instance can be constructed, then we can obtain
$\ell\left(\mathcal{L},\mathcal{N}\right)$ in polynomial time by recursive
computation: the condition C1 implies that the number of recursive calls is
bounded by $\sum_{i\in N}|M_{i}|+|N|$; the condition C2 verifies that each
recursive call can be preformed in polynomial time and that we can compute
$\ell\left(\mathcal{L},\mathcal{N}\right)$ from
$\ell\left(\mathcal{L}^{\ast},\mathcal{N}^{\ast}\right)$.

We first consider a simple case where there exist an index
$a\in\\{1,2,\dots,k\\}$ and an agent $i\in N_{a}$ such that $\mu(i)\in L_{i}$.
Then we define $N^{\ast}:=N\setminus N_{a}$,
$\mathcal{N}^{\ast}:=\mathcal{N}\setminus\\{N_{a}\\}$, and
$L_{i}^{\ast}:=L_{i}$ for each agent $i\in N^{\ast}$. Moreover, we set an
initial envy-free matching as the restriction of $\mu$ to $N^{\ast}$. Then the
new instance satisfies the conditions C1 and C2 since $|N^{\ast}|<|N|$ and
$\ell\left(\mathcal{L}^{\ast},\mathcal{N}^{\ast}\right)=\ell\left(\mathcal{L},\mathcal{N}\right)$.

A similar argument can be applied to the case when there exist an index
$a\in\\{1,2,\dots,k\\}$ and an agent $i\in N_{a}$ such that $\mu(i)\notin
L_{i}$ but a matching $\mu^{\prime}$ obtained from $\mu$ by exchanging
$\mu(i)$ with some $x\in L_{i}$ is $(\mathcal{L},\mathcal{N})$-envy-free. In
this case, we define $N^{\ast}:=N\setminus N_{a}$,
$\mathcal{N}^{\ast}:=\mathcal{N}\setminus\\{N_{a}\\}$, and
$L_{i}^{\ast}:=L_{i}$ for each agent $i\in N^{\ast}$. We set an initial envy-
free matching as the restriction of $\mu^{\prime}$ to $N^{\ast}$. Then the new
instance satisfies the conditions C1 and C2 since $|N^{\ast}|<|N|$ and
$\ell\left(\mathcal{L}^{\ast},\mathcal{N}^{\ast}\right)=\ell\left(\mathcal{L},\mathcal{N}\right)-1$.

Therefore, we may assume the following.

($\ast$) For any agent $i$, $\mu(i)\not\in L_{i}$ and any item $x\in L_{i}$
receives $(\mathcal{L},\mathcal{N})$-envy from some agent on $\mu(i)$. Since
each item is acceptable to at most two agents, there exists exactly one agent
that has $(\mathcal{L},\mathcal{N})$-envy for an item $x\in L_{i}$.

We construct a new instance $(\mathcal{L}^{\ast},\mathcal{N}^{\ast})$ as
follows. Let $N^{\ast}:=N$. We define the directed graph $D=(V,A)$ by

$\displaystyle\begin{split}V&:=\\{1,2,\dots,k\\},\\\ A&:=\\{(a,b)\in V\times
V\mid a\neq b,\exists i\in N_{a},\exists j\in N_{b},\ M_{i}\cap
L_{j}\neq\emptyset\\}.\end{split}$

Roughly, $M_{i}\cap L_{j}\neq\emptyset$ means that $j$ cannot receive some
item in $L_{j}$ because of $(\mathcal{L},\mathcal{N})$-envy from $i$. We
decompose $D$ into strongly connected components. Let $S\subseteq V$ be a
source component of the decomposition (i.e., no arc in $A$ enters $S$). We
define the partition $\mathcal{N}^{\ast}$ of $N^{\ast}$ by merging
$\\{N_{a}\mid a\in S\\}$ into one part, i.e.,
$\mathcal{N}^{\ast}:=\big{(}\mathcal{N}\setminus\\{N_{a}\mid a\in
S\\}\big{)}\cup\left\\{N_{S}\right\\}$, where we define $N_{S}:=\bigcup_{a\in
S}N_{a}$. Let $X:=\bigcup_{i\in N_{S}}L_{i}$. For each agent $i\in N_{S}$, we
denote by $x_{i}^{\ast}$ be the item in $X\cap M_{i}$ that is minimum with
respect to $\succ_{i}$. We define $\mathcal{L}^{\ast}=\\{L^{\ast}_{i}\mid i\in
N^{\ast}\\}$ by

$L_{i}^{\ast}:=\begin{cases}\\{x\in M_{i}\mid
x\succeq_{i}x_{i}^{\ast}\\}&\text{ if }i\in N_{S},\\\ L_{i}&\text{ if }i\in
N\setminus N_{S}.\end{cases}$

We set $\mu$ as the initial matching in the resulting instance. Note that
$\mu$ is an $(\mathcal{L}^{\ast},\mathcal{N}^{\ast})$-envy-free matching.

Claims 3 and 4 below show that the resulting instance satisfies the conditions
C1 and C2, respectively.

######  Claim 3.

$\sum_{i\in N}|M_{i}\setminus L_{i}^{\ast}|<\sum_{i\in N}|M_{i}\setminus
L_{i}|$.

###### Proof.

By definition, $L_{i}^{\ast}\supseteq L_{i}$ holds for every agent $i\in
N_{S}$. Hence, it suffices to show $L_{i}^{\ast}\supsetneq L_{i}$ for some
agent $i\in N_{S}$.

Suppose, to the contrary, that $L_{i}^{\ast}=L_{i}$ for every agent $i\in
N_{S}$. Take an arbitrary sequence of $(\mathcal{L},\mathcal{N})$-envy-free
matchings from $\mu$ to some satisfactory matching. Let $\mu^{\prime}$ denote
the first $(\mathcal{L},\mathcal{N})$-envy-free matching in the sequence with
$\mu^{\prime}(i)\in L_{i}$ for some agent $i\in N_{S}$. Recall here that
$\mu^{\prime}(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 $N_{b}$ having $j$ belongs to $N_{S}$. Since
$\mu^{\prime}(i)\in X$, we see that $\mu^{\prime}(i)\in L_{j}^{\ast}$. Since
$L_{j}^{\ast}=L_{j}$ by assumption, $\mu^{\prime}(i)$ particularly belongs to
$L_{j}$, which implies that $j$ has $(\mathcal{L},\mathcal{N})$-envy for $i$.
This is a contradiction to the $(\mathcal{L},\mathcal{N})$-envy-freeness of
$\mu^{\prime}$. ∎

######  Claim 4.

$\ell\left(\mathcal{L}^{\ast},\mathcal{N}^{\ast}\right)=\ell\left(\mathcal{L},\mathcal{N}\right)-|S|$.

###### Proof.

Let $\ell:=\ell\left(\mathcal{L},\mathcal{N}\right)$ and
$\ell^{\ast}:=\ell\left(\mathcal{L}^{\ast},\mathcal{N}^{\ast}\right)$.

We first show $\ell^{\ast}\leq\ell-|S|$. Consider a shortest sequence
$\mu=:\mu_{0}\leadsto\mu_{1}\leadsto\dots\leadsto\mu_{\ell}$ of
$(\mathcal{L},\mathcal{N})$-envy-free matchings from $\mu$ to some
satisfactory $(\mathcal{L},\mathcal{N})$-envy-free matching $\mu_{\ell}$. For
each $a\in S$, we denote by $p_{a}$ the minimum index such that
$\mu_{p_{a}}(i)\in L_{i}$ for some agent $i\in N_{a}$. Let $b\in S$ be the
index that satisfies $p_{b}=\min\\{p_{a}\mid a\in S\\}$, and $i_{b}\in N_{b}$
be the agent such that $\mu_{p_{b}}(i_{b})\in L_{i_{b}}$. Then, by assumption
($\ast$), the item $\mu_{p_{b}}(i_{b})$ is acceptable to another agent $j$ in
some group $N_{a}$, meaning that either $a=b$ or $D$ has an arc $(a,b)$. Since
$S$ is a source component, we see $a\in S$. By the definition of $p_{b}$, we
observe that $\mu_{p_{b}-1}(j)\succ_{j}\mu_{p_{b}}(i_{b})$, which implies that
$\mu_{p_{b}-1}(j)\in L_{j}^{\ast}\setminus L_{j}$ as $\mu_{p_{b}}(i_{b})\in
X$. Thus, in the $(p_{b}-1)$-st step, the agent $j\in N_{S}$ has an item in
the new target set $L_{j}^{\ast}$.

We construct a sequence of $(\mathcal{L}^{\ast},\mathcal{N}^{\ast})$-envy-free
matchings as follows. For $p$ with $p_{b}\leq p\leq\ell$, define a matching
$\mu_{p}^{\prime}$ to be $\mu_{p}^{\prime}(i)=\mu_{p_{b}-1}(i)$ if $i\in
N_{S}$ and $\mu_{p}^{\prime}(i)=\mu_{p}(i)$ otherwise. Then the sequence
$(\mu_{0},\mu_{1},\dots,\mu_{p_{b}-1},\mu^{\prime}_{p_{b}},\dots,\mu^{\prime}_{\ell})$
forms that of $(\mathcal{L}^{\ast},\mathcal{N}^{\ast})$-envy-free matchings
from $\mu$ to some satisfactory
$(\mathcal{L}^{\ast},\mathcal{N}^{\ast})$-envy-free matching. Furthermore,
since $\mu^{\prime}_{p_{a}}=\mu^{\prime}_{p_{a}-1}$ holds for all $a\in S$, we
can remove $\mu^{\prime}_{p_{a}}$’s from the sequence. This implies that there
exists a sequence of $(\mathcal{L}^{\ast},\mathcal{N}^{\ast})$-envy-free
matchings whose length is $\ell-|S|$. Thus $\ell^{\ast}\leq\ell-|S|$ holds.

We next show $\ell^{\ast}\geq\ell-|S|$. Consider a shortest sequence
$\mu=:\mu_{0}\leadsto\mu_{1}\leadsto\dots\leadsto\mu_{\ell^{\ast}}$ of
$(\mathcal{L}^{\ast},\mathcal{N}^{\ast})$-envy-free matchings from $\mu$ to
some satisfactory $(\mathcal{L}^{\ast},\mathcal{N}^{\ast})$-envy-free matching
$\mu_{\ell^{\ast}}$. Let $p$ be the minimum index such that $\mu_{p}(i_{0})\in
L_{i_{0}}^{\ast}$ for some $a_{0}\in S$ and $i_{0}\in N_{a_{0}}$. We observe
that $\mu_{p}(i_{0})$ particularly belongs to $L_{i_{0}}^{\ast}\setminus
L_{i_{0}}$. In fact, suppose that $\mu_{p}(i_{0})\in L_{i_{0}}$. Then the item
$\mu_{p}(i_{0})$ is acceptable to another agent by assumption ($\ast$). Since
$S$ is a source component, there exist an index $b\in S$ and $j\in N_{b}$ such
that $\mu_{p}(i_{0})\in M_{j}$. Since $\mu_{p}(i_{0})\in L^{\ast}_{j}$ and
$\mu_{p-1}(j)\succ_{j}\mu_{p}(i_{0})$, we have $\mu_{p-1}(j)\in L^{\ast}_{j}$.
This contradicts the definition of $p$.

Let $x_{1}:=x^{\ast}_{i_{0}}$. Then there exist $a_{1}\in S$ and $i_{1}\in
N_{a_{1}}$ such that $x_{1}\in L_{i_{1}}$. Moreover, since $\mu_{p}(i_{0})\neq
x_{1}$ as $\mu_{p}$ is $(\mathcal{L}^{\ast},\mathcal{N}^{\ast})$-envy-free, it
follows that $\mu_{p}(i_{0})\succ_{i_{0}}x_{1}$. Hence, the matching
$\sigma_{1}$ obtained from $\mu_{p}$ by assigning $x_{1}$ to $i_{1}$ is
$(\mathcal{L},\mathcal{N})$-envy-free. By this change, $N_{a_{1}}$ has the
agent $i_{1}$ with an item in her target set, and hence any agent in
$N_{a_{1}}$ has no $(\mathcal{L},\mathcal{N})$-envy for agents in the other
groups on $\sigma_{1}$.

Suppose that there exists some $a_{2}\in S$ with $(a_{1},a_{2})\in A$. Then
there exist $i^{\prime}\in N_{a_{1}}$ and $i_{2}\in N_{a_{2}}$ such that
$M_{i^{\prime}}\cap L_{i_{2}}$ contains an item, say $x_{2}$. Since the agent
$i^{\prime}$ has no $(\mathcal{L},\mathcal{N})$-envy for agents in $N_{a_{2}}$
on $\sigma_{1}$, the matching $\sigma_{2}$ obtained from $\sigma_{1}$ by
assigning $x_{2}$ to $i_{2}$ is $(\mathcal{L},\mathcal{N})$-envy-free. This
change makes $N_{a_{2}}$ have the agent $i_{2}$ with an item in her target
set. We repeat the above procedure; for $j=2,3,\dots$, we find an index
$a_{j}\in S\setminus\\{a_{1},\dots,a_{j-1}\\}$ such that there exists an arc
to $a_{j}$ from $\\{a_{1},\dots,a_{j-1}\\}$, and obtain an
$(\mathcal{L},\mathcal{N})$-envy-free matching by exchanging an item for some
agent in $N_{a_{j}}$. Since $D[S]$ forms a strongly connected component of
$D$, the repetition can be performed until, for all $a\in S$, some agent in
$N_{a}$ has an item in her target set. Thus we obtain a sequence
$\mu_{p}\leadsto\sigma_{1}\leadsto\sigma_{2}\leadsto\dots\leadsto\sigma_{|S|}$
of $(\mathcal{L},\mathcal{N})$-envy-free matchings in which for each $a\in S$
there is an agent $i\in N_{a}$ with $\sigma_{|S|}(i)\in L_{i}$.

For $q$ with $p+1\leq q\leq\ell^{\ast}$, we define a matching
$\mu_{q}^{\prime}$ to be $\mu_{q}^{\prime}(i)=\sigma_{|S|}(i)$ if $i\in N_{S}$
and $\mu_{q}^{\prime}(i)=\mu_{q}(i)$ otherwise. Then
$\mu_{0}\leadsto\dots\leadsto\mu_{p}\leadsto\sigma_{1}\leadsto\dots\leadsto\sigma_{|S|}\leadsto\mu_{p+1}^{\prime}\leadsto\dots\leadsto\mu_{\ell^{\ast}}^{\prime}$
forms a sequence of $(\mathcal{L},\mathcal{N})$-envy-free matchings from $\mu$
to a satisfactory $(\mathcal{L},\mathcal{N})$-envy-free matching
$\mu_{\ell^{\ast}}^{\prime}$. This implies $\ell\leq\ell^{\ast}+|S|$. ∎

It follows from the above claims that we can recursively compute
$\ell(\mathcal{L},\mathcal{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.

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 $\alpha\geq 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 $\alpha$ times the shortest length of a
reformist sequence. The smaller value of $\alpha$ 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.

###### Proof.

We reduce the set cover problem to the shortest reformist sequence problem. In
the set cover problem, we are given a family of subsets
$\mathcal{S}=\\{S_{1},\dots,S_{h}\\}$ on the ground set $V$ where we assume
that $h=O({|V|}^{\beta})$. The goal is to find a subfamily
$\mathcal{S}^{\prime}\subseteq\mathcal{S}$ such that
$\bigcup_{S\in\mathcal{S}^{\prime}}S=V$ and $|\mathcal{S}^{\prime}|$ is
minimized. It is known [6] that the set cover problem is inapproximable within
a factor of $(1-\varepsilon)\ln n$ for every $\varepsilon>0$ unless P$=$NP. We
denote by $\delta(v)$ the set of subsets in $\mathcal{S}$ that contain an
element $v\in V$, i.e., $\delta(v)=\\{S\in\mathcal{S}\mid v\in S\\}$. Also, we
define $T:=\sum_{S\in\mathcal{S}}|S|$.

We construct an instance of the shortest reformist sequence problem as
follows. Let $p$ be a positive integer, which will be specified later. For
each subset $S_{j}\in\mathcal{S}$ where $d_{j}=|S_{j}|$, we define $d_{j}+3$
agents $x_{j,0},x_{j,1},\dots,x_{j,d_{j}}$, $y_{j}$, and $y^{\prime}_{j}$,
and, for each element $v\in V$, we define $f_{v}$ agents
$v^{1},v^{2},\dots,v^{f_{v}}$, where $f_{v}=|\delta(v)|$. Moreover, we
introduce one more agent $z$. Thus

$\begin{split}N&=\\{x_{j,\ell}\mid
j\in\\{1,\dots,h\\},\ell\in\\{0,1,2,\dots,d_{j}\\}\\}\cup\\{y_{j},y^{\prime}_{j}\mid
j\in\\{1,\dots,h\\}\\}\\\ &\ \ \ \ \cup\\{v^{\ell}\mid v\in
V,\ell\in\\{1,2,\dots,f_{v}\\}\\}\cup\\{z\\}.\end{split}$

We see that $n=|N|=O(h|V|)$.

Define

$M^{\prime}=\\{r_{i},s_{i}\mid i\in N\\}\cup\\{t_{j,v}\mid
S_{j}\in\mathcal{S},v\in S_{j}\\}\cup\\{u_{j}\mid S_{j}\in\mathcal{S}\\}.$

For each subset $S_{j}\in\mathcal{S}$, we prepare the set of items

$M_{j}=\\{a_{j,\ell},b_{j,\ell}\mid
S_{j}\in\mathcal{S},\ell\in\\{1,2,\dots,p\\}\\}.$

Our instance has the set of items
$M=M^{\prime}\cup\bigcup_{S_{j}\in\mathcal{S}}M_{j}$.

For each subset $S_{j}\in\mathcal{S}$, letting
$S_{j}=\\{v_{1},\dots,v_{d_{j}}\\}$ (in an arbitrary order), the agents
$x_{j,\ell}$’s have the following preferences:

$\displaystyle\succ_{x_{j,0}}$ $\displaystyle\colon
r_{x_{j,0}},u_{j},r_{x_{j,d_{j}}},r_{x_{j,d_{j}-1}},\dots,r_{x_{j,1}},s_{x_{j,0}},$
$\displaystyle\succ_{x_{j,\ell}}$ $\displaystyle\colon
r_{x_{j,\ell}},t_{j,v_{\ell}},s_{x_{j,\ell}}\quad(\ell\in\\{1,2,\dots,d_{j}\\}).$

Moreover, the agents $y_{j}$ and $y^{\prime}_{j}$ have the preferences in a
way similar to Theorem 2, that is,

$\displaystyle\succ_{y_{j}}$ $\displaystyle\colon
a_{j,p},b_{j,p},a_{j,p-1},b_{j,p-1},\dots,a_{j,2},b_{j,2},a_{j,1},$
$\displaystyle\succ_{y^{\prime}_{j}}$ $\displaystyle\colon
b_{j,p},u_{j},b_{j,p-1},a_{j,p},b_{j,p-2},a_{j,p-1},\dots,b_{j,2},a_{j,3},b_{j,1}.$

For each vertex $v\in V$, we may re-index subsets in $\delta(v)$ so that
$\delta(v)=\\{S_{1},\dots,S_{f_{v}}\\}$. Then the preferences of the
associated agents are defined to be

$\displaystyle\succ_{v^{\ell}}$ $\displaystyle\colon
r_{v^{\ell}},t_{\ell,v},r_{v^{\ell+1}},s_{v^{\ell}}\quad(\ell\in\\{1,2,\dots,f_{v}\\}),$

where we assume that $v^{\ell+1}=v^{1}$. Finally, the last agent $z$ has the
preference defined by

$\displaystyle\succ_{z}$ $\displaystyle\colon
r_{z},r_{x_{1,0}},\dots,r_{x_{h,0}},s_{z}.$

The initial matching $\mu$ is set $\mu(i)=s_{i}$ for each agent $i$. By Claim
5 below, a reformist envy-free matching $\sigma$ with respect to $\mu$ is
$\sigma(i)=r_{i}$ for each agent $i$.

######  Claim 5.

Let $k$ be a non-negative integer. If $\mathcal{S}$ has a set cover of size
$k$, then there exists a reformist sequence of length at most
$(2p-4)k+2T+4h+|V|+1$.

###### Proof.

Let $\mathcal{S}^{\ast}$ be a set cover of size $k$. Consider the following
reformist sequence.

  1. 1.

For each $S_{j}\in\mathcal{S}^{\ast}$ where
$S_{j}=\\{v_{1},\dots,v_{d_{j}}\\}$, we do the following: The agents $y_{j}$
and $y^{\prime}_{j}$ exchange items repeatedly to obtain $a_{j,p}$ and
$b_{j,p}$, respectively, which takes $2p-2$ steps (See the proof of Theorem
2). Then since an envy at $u_{j}$ from $y^{\prime}_{j}$ is removed, the agent
$x_{j,0}$ exchanges $s_{x_{j,0}}$ with $u_{j}$. For each integer
$\ell\in\\{1,2,\dots,d_{j}\\}$, $x_{j,\ell}$ exchanges $s_{x_{j,\ell}}$ with
$r_{x_{j,\ell}}$. This step takes $2p-2+d_{j}+1$ exchanges for each
$S_{j}\in\mathcal{S}^{\ast}$.

  2. 2.

For each element $v\in V$, the associated agents are nominated one by one as
follows. Since $\mathcal{S}^{\ast}$ is a set cover, there exists a subset
$S\in\mathcal{S}^{\ast}$ with $v\in S$. So we may re-index subsets in
$\delta(v)$ so that $\delta(v)=\\{S_{1},\dots,S_{f_{v}}\\}$ with
$S_{1}\in\mathcal{S}^{\ast}$. The agent $v^{1}$ exchanges $s_{v^{1}}$ with
$t_{1,v}$. This can be done since $t_{1,v}$ receives no envy from
$x_{1,\ell}$’s due to Step 1. Then the agent $v^{\ell}$ exchanges
$s_{v^{\ell}}$ with $r_{v^{\ell}}$ in the order of $\ell=2,3,\dots,f_{v}$.
Finally, the agent $v^{1}$ exchanges $t_{1,v}$ with $r_{v^{1}}$. In total,
this step takes $f_{v}+1$ exchanges for each element $v\in V$.

  3. 3.

The agent $z$ exchanges $s_{z}$ with $r_{z}$.

  4. 4.

For each subset $S_{j}\in\mathcal{S}^{\ast}$, the agent $x_{j,0}$ exchanges
$u_{j}$ with $r_{x_{j,0}}$. Furthermore, for each subset
$S_{j}\in\mathcal{S}\setminus\mathcal{S}^{\ast}$, the agent $x_{j,\ell}$
exchanges $s_{x_{j,\ell}}$ with $r_{x_{j,\ell}}$ in the order of
$\ell=0,1,\dots,d_{j}$. This can be done since $r_{x_{j,0}}$ receives no envy
from the other agents.

  5. 5.

For each subset $S_{j}\in\mathcal{S}\setminus\mathcal{S}^{\ast}$,
$y^{\prime}_{j}$ exchanges $s_{y^{\prime}_{j}}$ with $u_{j}$, $y_{j}$
exchanges $s_{y_{j}}$ with $r_{y_{j}}$, and $y^{\prime}_{j}$ exchanges $u_{j}$
with $r_{y^{\prime}_{j}}$.

In the above reformist sequence, the total number of steps is

$\displaystyle(2p-2)k+\sum_{S_{j}\in\mathcal{S}^{\ast}}(d_{j}+1)+\sum_{v\in
V}(f_{v}+1)+1+|\mathcal{S}^{\ast}|+\sum_{S_{j}\in\mathcal{S}\setminus\mathcal{S}^{\ast}}(d_{j}+1)+3|\mathcal{S}\setminus\mathcal{S}^{\ast}|$
$\displaystyle=(2p-1)k+(T+h)+\left(\sum_{v\in V}f_{v}+|V|\right)+1+3(h-k)$
$\displaystyle=(2p-4)k+2T+4h+|V|+1.$

where the last equality holds since $\sum_{v\in V}f_{v}=T$. ∎

######  Claim 6.

Let $k$ be a non-negative integer. If there exists a reformist sequence of
length $(2p-4)k+2T+4h+|V|+1$, then $\mathcal{S}$ has a set cover of size $k$.

###### Proof.

Consider a reformist sequence of length at most $(2p-4)k+2T+4h+|V|+1$. We may
assume that it has no redundant steps. Define $\mathcal{S}^{\prime}$ as the
family of $S_{j}\in\mathcal{S}$ such that $x_{j,0}$ possesses $u_{j}$ at some
point in the reformist sequence. Then, for $S_{j}\in\mathcal{S}^{\prime}$,
$x_{j,0}$ takes $2$ steps, and $x_{j,\ell}$ takes one step for each
$\ell=1,2,\dots,d_{j}$. Moreover, for such $j$, $y_{j}$ and $y^{\prime}_{j}$
have to take $2p-2$ steps in total to remove envy at $u_{j}$ before the agent
$x_{j,0}$ moves. For $S_{j}\in\mathcal{S}\setminus\mathcal{S}^{\prime}$, the
agents $x_{j,\ell}$ takes one step for each $\ell=0,1,2,\dots,d_{j}$, and
$y_{j}$ and $y^{\prime}_{j}$ take at least $3$ steps. For each element $v\in
V$, the agents $v^{\ell}$’s take at least $f_{v}+1$ steps in total. Therefore,
the total number of steps in the reformist sequence is at least

$\displaystyle(2p-2)|\mathcal{S}^{\prime}|+\sum_{S_{j}\in\mathcal{S}^{\prime}}(d_{j}+2)+\sum_{S_{j}\in\mathcal{S}\setminus\mathcal{S}^{\prime}}(d_{j}+1)+\sum_{v\in
V}(f_{v}+1)+3|\mathcal{S}\setminus\mathcal{S}^{\prime}|+1$
$\displaystyle=(2p-4)|\mathcal{S}^{\prime}|+2T+4h+|V|+1.$

Hence $|\mathcal{S}^{\prime}|\leq k$ holds by the assumption.

Moreover, we see that $\mathcal{S}^{\prime}$ is a set cover. Suppose not. Then
there exists an element $v\in V$ such that
$\delta(v)\cap\mathcal{S}^{\prime}=\emptyset$. This means that no subset
$S_{j}\in\delta(v)$ possesses $u_{j}$ at any point in the reformist sequence.
So all the agents $x_{j,0}$ for $S_{j}\in\delta(v)$ exchange $s_{j,0}$ with
$r_{j,0}$. Since $r_{j,0}$ receives an envy from the agent $z$, the agent $z$
has to exchange before that. However, to exchange items of the agent $z$, we
have to exchange items of the agents $v^{\ell}$’s, but it is impossible before
agent $x_{j,0}$ for some $S_{j}\in\delta(v)$ exchanges. This is a
contradiction. Thus $\mathcal{S}^{\prime}$ is a set cover of size $k$. ∎

Let $\mathrm{OPT}$ be the optimal value for the instance of the shortest
reformist sequence problem we construct as above. Since we may assume that
${\cal S}$ has a set cover of size at least $1$, it follows from Claim 6 that

$\mathrm{OPT}\geq 2p-4+2T+4h+|V|+1.$

Suppose that we can find in polynomial time a reformist sequence of length at
most $\alpha\mathrm{OPT}$ steps for some $\alpha\geq 1$. By Claim 6, we can
construct a set cover of size $k$ where

$k\leq\frac{1}{2p-4}\left(\alpha\mathrm{OPT}-2T-4h-|V|-1\right).$

On the other hand, Claim 5 implies that an optimal set cover has size at least

$\frac{1}{2p-4}\left(\mathrm{OPT}-2T-4h-|V|-1\right).$

Hence the approximation ratio for the set cover problem is at most

$\frac{\alpha\mathrm{OPT}-2T-4h-|V|-1}{\mathrm{OPT}-2T-4h-|V|-1}\leq\alpha\frac{2p-4+2T+4h+|V|+1}{2p-4}.$

since the maximum is attained when $\mathrm{OPT}$ is minimum, that is,

$\mathrm{OPT}=2p-4+2T+4h+|V|+1.$

Therefore, if $p$ is sufficiently large, i.e., $2p-4\geq 2T+4h+|V|+1$, then
the approximation ratio is at most $2\alpha$.

We now suppose that $\alpha=c\ln n$ for some sufficiently small constant $c$.
Since $n=O(h|V|)$ and $h\leq O({|V|}^{\beta})$ for some constant $\beta$, the
above discussion implies that the set cover problem admits
$2c(\beta+1)\ln|V|$-approximation. However, this contradicts that the set
cover problem is inapproximable within a factor of $(1-\varepsilon)\ln|V|$ for
every $\varepsilon>0$. This completes the proof. ∎

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 $\ell$ 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 $\ell$ of a sequence is fixed-parameter tractable.

###### Proof.

First, note that after preprocessing in section 5.1, if the number $n$ of
agents is larger than $\ell$, then there exists no reformist sequence of
length at most $\ell$ since no agent shares an item in the initial envy-free
matching and the reformist envy-free matching, and thus the length of every
reformist sequence must be at least $n$. Therefore, after the preprocessing,
if $n>\ell$, then the output is No.

Now, we may assume that $n\leq\ell$. Then, we consider nominating an arbitrary
agent and exchanging her current item with the best item for her on the table
while keeping the envy-freeness. We iterate nomination at most $\ell$ times.
Then, we obtain a branching algorithm with branching factor $n$ and height
$\ell$. Therefore, the size of the recursion tree is at most
$n^{\ell}\leq\ell^{\ell}$. Since each exchange can be performed in polynomial
time, the whole algorithm runs in $O(\ell^{\ell}p(n,m))$ for some polynomial
$p$. ∎

As the second choice, we study the shortest length $\ell$ 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.

######  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.

###### Proof.

In order to prove the theorem, we reduce the multi-colored clique problem to
our problem. The multi-colored clique problem is to ask whether, given a
$k$-partite graph $G=(V,E)$ with a partition $V_{1},V_{2},\dots,V_{k}$ of $V$,
there exist $k$ vertices $v_{1},v_{2},\dots,v_{k}$ such that $v_{i}\in V_{i}$
for every integer $i\in\\{1,2,\dots,k\\}$ and $v_{1},v_{2},\dots,v_{k}$ forms
a clique. It is known [7, 18] that the multi-colored clique problem is
W[1]-hard when $k$ is a parameter.

Let $G=(V,E)$ with a partition $V_{1},V_{2},\dots,V_{k}$ of $V$ be an instance
of the multi-colored clique problem. We denote
$V:=\\{v_{1},\dots,v_{n^{\prime}}\\}$, where $n^{\prime}:=|V|$.

We construct an instance of our problem as follows. For each vertex $v_{j}\in
V$, we introduce $d_{j}+1$ agents

$v_{j}^{0},v_{j}^{1},\dots,v_{j}^{d_{j}},$

where $d_{j}:=|\delta(v_{j})|$ is the degree of $v_{j}$. For each edge $e\in
E$, we prepare one agent $e$. Moreover, we define one more agent $a$. Thus,
the set $N$ of agents is

$N=\\{v_{j}^{\ell}\mid v_{j}\in V,\ \ell\in\\{0,1,\dots,d_{j}\\}\\}\cup
E\cup\\{a\\}.$

The size $|N|$ is equal to

$\sum_{v_{j}\in V}(d_{j}+1)+|E|+1=|V|+3|E|+1,$

since $\sum_{v_{j}\in V}d_{j}=2|E|$. Define the set $M$ of items to be

$M=\\{r_{i},s_{i}\mid i\in N\\}\cup\\{y_{e}\mid e\in E\\}\cup\\{z_{v_{j}}\mid
v_{j}\in V\\}.$

The preferences of the agents are defined as follows. For each vertex
$v_{j}\in V$, letting $\delta(v_{j})=\\{e_{1},e_{2},\dots,e_{\ell}\\}$ (in an
arbitrary order),

$\displaystyle\succ_{v_{j}^{\ell}}$ $\displaystyle\colon
r_{v_{j}^{\ell}},y_{e_{\ell}},s_{v_{j}^{\ell}}\quad(\ell\in\\{1,2,\dots,d_{j}\\}),$
$\displaystyle\succ_{v_{j}^{0}}$ $\displaystyle\colon
r_{v_{j}^{0}},z_{v_{j}},r_{v_{j}^{d}},r_{v_{j}^{d-1}},\dots,r_{v_{j}^{1}},s_{v_{j}^{0}}.$

For each pair of integers $i,j\in\\{1,2,\dots,k\\}$ such that $i\neq j$, we
denote by $E[V_{i},V_{j}]$ the set of edges connecting vertices of $V_{i}$ and
$V_{j}$. Note that every edge belongs to exactly one of the $E[V_{i},V_{j}]$.
For each pair of integers $i,j\in\\{1,2,\dots,k\\}$ such that $i\neq j$,
denoting $E[V_{i},V_{j}]=\\{e_{1},\dots,e_{t}\\}$ (in an arbitrary order),

$\displaystyle\succ_{e_{\ell}}$ $\displaystyle\colon
r_{e_{\ell}},y_{e_{\ell}},r_{e_{\ell+1}},r_{a},s_{e_{\ell}},\quad(\ell\in\\{1,2,\dots,t\\}),$

where we assume that $e_{t+1}=e_{1}$. The last agent $a$ has preference
defined by

$\displaystyle\succ_{a}$ $\displaystyle\colon
r_{a},r_{v_{n^{\prime}}^{0}},\dots,r_{v_{1}^{0}},s_{a}.$

The initial matching $\mu$ is defined to be $\mu(i)=s_{i}$ for each agent $i$.
By Claim 7, a reformist envy-free matching $\sigma$ with respect to $\mu$ is
$\sigma(i)=r_{i}$ for each agent $i$.

######  Claim 7.

If $G$ has a multi-colored clique, then there exists a reformist sequence of
length $n+\binom{k}{2}+k$.

###### Proof.

Let $X$ be a multi-colored clique. For simplicity, we re-index vertices so
that $X=\\{v_{1},\dots,v_{k}\\}$ and $v_{i}\in V_{i}$ for each integer
$i\in\\{1,2,\dots,k\\}$. Consider the following reformist sequence.

  1. 1.

For each vertex $v_{j}\in X$, we do the following: The agent $v_{j}^{0}$
exchanges $s_{v_{j}^{0}}$ with $z_{v_{j}}$. Then $v_{j}^{\ell}$ exchanges
$s_{v_{j}^{\ell}}$ with $r_{v_{j}^{\ell}}$ for each integer
$\ell\in\\{1,2,\dots,d_{j}\\}$. This takes $d_{j}+1$ steps for each $v_{j}\in
X$.

  2. 2.

For each pair of integers $i,j\in\\{1,2,\dots,k\\}$ such that $i\neq j$, do
the following. Let $E[V_{i},V_{j}]=\\{e_{1},\dots,e_{t_{ij}}\\}$ where
$t_{ij}:=|E[V_{i},V_{j}]|$. As $\\{v_{i},v_{j}\\}\in E[V_{i},V_{j}]$, we may
re-index edges of $E[V_{i},V_{j}]$ so that $e_{1}=\\{v_{i},v_{j}\\}$. First,
the agent $e_{1}$ exchanges $s_{e_{1}}$ with $y_{e_{1}}$. This can be done
since $y_{e_{1}}$ has no envy due to Step 1. Then in the order of
$\ell=2,3,\dots,t$, the agent $e_{\ell}$ exchanges $s_{e_{\ell}}$ with
$r_{e_{\ell}}$. Finally, the agent $e_{1}$ exchanges $y_{e_{1}}$ with
$r_{e_{1}}$. This takes $t_{ij}+1$ steps for each pair $i,j$. Hence the total
number of exchanges is $\sum_{i,j}(t_{ij}+1)=|E|+\binom{k}{2}$ as
$\sum_{i,j}t_{ij}=|E|$.

  3. 3.

The agent $a$ exchanges $s_{a}$ with $r_{a}$. This can be done because $r_{a}$
has no envy due to Step 2.

  4. 4.

For each vertex $v_{j}\in X$, the agent $v_{j}^{0}$ exchanges $z_{v_{j}^{0}}$
with $r_{v_{j}^{0}}$. This can be done since $r_{v_{j}^{0}}$ has no envy from
$a$ due to Step 3.

  5. 5.

For each vertex $v_{j}\in V\setminus X$, the agent $v_{j}^{0}$ exchanges
$s_{v_{j}^{0}}$ with $r_{v_{j}^{0}}$, and then $v_{j}^{\ell}$ exchanges
$s_{v_{j}^{\ell}}$ with $r_{v_{j}^{\ell}}$ for each integer
$\ell\in\\{1,2,\dots,d_{j}\\}$.

In the reformist sequence above, each vertex $v_{j}\in X$ needs $d_{j}+2$
exchanges in Steps 1 and 4, and each vertex $v_{j}\in V\setminus X$ requires
$d_{j}+1$ exchanges in Step 5. Therefore, since the number of exchanges in
Steps 2 and 3 is $|E|+\binom{k}{2}+1$, the total number of exchanges is

$\displaystyle\sum_{v_{j}\in X}(d_{j}+2)+\sum_{v_{j}\in V\setminus
X}(d_{j}+1)+|E|+\binom{k}{2}+1$ $\displaystyle=\sum_{v_{j}\in
V}d_{j}+k+|V|+|E|+\binom{k}{2}+1$
$\displaystyle=|V|+3|E|+\binom{k}{2}+k+1=|N|+\binom{k}{2}+k,$

where the last equation follows from $|N|=|V|+3|E|+1$. This completes the
proof. ∎

######  Claim 8.

If there exists a reformist sequence of length $|N|+\binom{k}{2}+k$, then $G$
has a multi-colored clique.

###### Proof.

Consider a reformist sequence with minimum number of steps. We first observe
that, because of the minimality, the agent $v_{j}^{\ell}$ for each vertex
$v_{j}\in V$ and each integer $\ell\in\\{1,2,\dots,d_{j}\\}$ takes only one
exchange. Moreover, for each pair of integers $i,j\in\\{1,2,\dots,k\\}$ such
that $i\neq j$, the agents in $E[V_{i},V_{j}]$ take $|E[V_{i},V_{j}]|+1$
exchanges in total, and, before that, we need to remove envy at $y_{e}$ for
some $e=\\{v_{i},v_{j}\\}\in E[V_{i},V_{j}]$ by exchanging $v_{i}^{\ell}$’s
and $v_{j}^{\ell}$’s. Also, to exchange with $r_{v_{j}^{0}}$ for a vertex
$v_{j}\in V$, we need to remove envy from the agent $a$, which implies that we
have to exchange items for the agents $e$ for all $e\in E$ before that.

Define $X$ as the set of $v_{j}\in V$ such that $v_{j}^{0}$ uses $z_{v_{j}}$
in the reformist sequence. Then the number of steps in the sequence is at
least $|N|+|X|+\binom{k}{2}$. Since it is at most $|N|+\binom{k}{2}+k$ by the
assumption, it follows that $|X|\leq k$. We observe that, for any pair of
integers $i,j\in\\{1,2,\dots,k\\}$ such that $i\neq j$, we have
$E[V_{i},V_{j}]\cap E[X]\neq\emptyset$, where $E[X]$ is the set of edges
induced by $X$. In fact, suppose not. Then, for such a pair $i,j$ and each
edge $e=\\{\hat{v}_{i},\hat{v}_{j}\\}\in E[V_{i},V_{j}]$, the item $y_{e}$
receives an envy from some of $\hat{v}_{i}^{\ell}$’s and
$\hat{v}_{j}^{\ell}$’s. Hence we cannot exchange any items on $\bigcup_{e\in
E[V_{i},V_{j}]}M_{e}$. This is a contradiction.

Therefore, since $|X|\leq k$, it follows that $X$ forms a multi-colored
clique. ∎

By Claims 7 and 8, the multi-colored clique problem reduces to the shortest
reformist sequence problem, which completes the proof. ∎

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 $\mu$ to the reformist envy-free matching $\sigma$, namely,
$K:=M\setminus\\{\mu(i),\sigma(i)\mid i\in 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.

###### Proof.

In order to prove the theorem, we design a fixed-parameter algorithm.

Step 1.

While some agent $i$ can exchange $\mu(i)$ with $\sigma(i)$, we nominate $i$
to exchange $\mu(i)$ with $\sigma(i)$ and remove $i$ from the instance.

Step 2.

Choose an item $x\in K$ such that $x\in M_{i}$ for exactly one agent $i$. We
solve recursively the following two instances with smaller parameter.

  * •

An instance with the initial matching $\mu^{\prime}$ where $\mu^{\prime}(i)=x$
and $\mu^{\prime}(j)=\mu(j)$ for the other agents $j$

  * •

An instance obtained by replacing $M_{i}$ with
$M^{\prime}_{i}=M_{i}\setminus\\{x\\}$.

We first observe that the exchanges in Step 1 can be done first before the
other exchanges without destroying the minimality of a reformist sequence.
Thus, we may assume that no agent $i$ can exchange $\mu(i)$ with $\sigma(i)$.
The next step must be for some agent $i$ to exchange $\mu(i)$ with some item
$x\in M_{i}$. Since the resulting matching is envy-free, no agent $j\neq i$
has $x$ in $M_{j}$.

We consider branching using such an item $x$. That is, we pick arbitrarily an
item $x\in K$ such that $x\in M_{i}$ for exactly one agent $i$, and consider
two cases: when the next step is to exchange $\mu(i)$ with $x$ for the agent
$i$, or when the item $x$ is never used in the reformist sequence. We note
that, if $x$ is used in the reformist sequence, then we can exchange $\mu(i)$
with $x$ now before the other agents’ exchange, as it does not worse the
situation. For the former one, we consider the instance with the initial
matching $\mu^{\prime}$ where $\mu^{\prime}(i)=x$ and $\mu^{\prime}(j)=\mu(j)$
for the other agents $j$. For the latter one, we solve the instance obtained
by replacing $M_{i}$ with $M^{\prime}_{i}=M_{i}\setminus\\{x\\}$. For each
case, the parameter $|K|$ is decreased by one. Thus the depth of recursion is
at most $|K|$. Therefore, the total time complexity 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.

## References

  * [1] Haris Aziz and Simon Mackenzie.  A bounded and envy-free cake cutting algorithm.  Communications of the ACM, 63(4):119–126, 2020.
  * [2] Aurélie Beynier, Yann Chevaleyre, Laurent Gourvès, Ararat Harutyunyan, Julien Lesca, Nicolas Maudet, and Anaëlle Wilczynski.  Local envy-freeness in house allocation problems.  Autonomous Agents and Multi-Agent Systems, 33(5):591–627, 2019\.
  * [3] Sylvain Bouveret, Yann Chevaleyre, and Nicolas Maudet.  Fair allocation of indivisible goods.  In Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors, Handbook of Computational Social Choice, pages 284–310. Cambridge University Press, Cambridge, UK, 2016.
  * [4] Felix Brandt and Anaëlle Wilczynski.  On the convergence of swap dynamics to pareto-optimal matchings.  In Ioannis Caragiannis, Vahab S. Mirrokni, and Evdokia Nikolova, editors, Proceedings of the 15th Conference on Web and Internet Economics Web and Internet Economics, volume 11920 of Lecture Notes in Computer Science, pages 100–113, Cham, Switzerland, 2019. Springer.
  * [5] Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn.  EFX exists for three agents.  In Péter Biró, Jason D. Hartline, Michael Ostrovsky, and Ariel D. Procaccia, editors, Proceedings of the 21st ACM Conference on Economics and Computation, pages 1–19, New York, NY, 2020. ACM.
  * [6] Irit Dinur and David Steurer.  Analytical approach to parallel repetition.  In David B. Shmoys, editor, Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 624–633, New York, NY, 2014. ACM.
  * [7] Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, and Stéphane Vialette.  On the parameterized complexity of multiple-interval graph problems.  Theoretical Computer Science, 410(1):53–61, 2009.
  * [8] Jiarui Gan, Warut Suksompong, and Alexandros A. Voudouris.  Envy-freeness in house allocation problems.  Mathematical Social Sciences, 101:104–106, 2019.
  * [9] Paul Goldberg, Alexandros Hollender, and Warut Suksompong.  Contiguous cake cutting: Hardness results and approximation algorithms.  Journal of Artificial Intelligence Research, 69:109–141, 2020.
  * [10] Laurent Gourvès, Julien Lesca, and Anaëlle Wilczynski.  Object allocation via swaps along a social network.  In Carles Sierra, editor, Proceedings of the 26th International Joint Conference on Artificial Intelligence, pages 213–219, Palo Alto, CA, 2017\. AAAI Press.
  * [11] Sen Huang and Mingyu Xiao.  Object reachability via swaps under strict and weak preferences.  Autonomous Agents and Multi-Agent Systems, 34(2):51, 2020.
  * [12] Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno.  On the complexity of reconfiguration problems.  Theoretical Computer Science, 412(12-14):1054–1065, 2011.
  * [13] Richard M. Karp.  Reducibility among combinatorial problems.  In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, The IBM Research Symposia Series, pages 85–103. Plenum Press, 1972.
  * [14] Bettina Klaus, David F. Manlove, and Francesca Rossi.  Matching under preferences.  In Felix Brandt, Vincent Conitzer, Ulle Endriss, Jerôme Lang, and Ariel D. Procaccia, editors, Handbook of Computational Social Choice, pages 333–355. Cambridge University Press, Cambridge, UK, 2016.
  * [15] Prem Krishnaa, Girija Limaye, Meghana Nasre, and Prajakta Nimbhorkar.  Envy-freeness and relaxed stability: Hardness and approximation algorithms.  In Tobias Harks and Max Klimm, editors, Proceedings of the 13th Symposium on Algorithmic Game Theory, volume 12283 of Lecture Notes in Computer Science, pages 193–208. Springer, 2020.
  * [16] David F. Manlove.  Algorithmics of Matching Under Preferences.  World Scientific, Singapore, 2013.
  * [17] Naomi Nishimura.  Introduction to reconfiguration.  Algorithms, 11(4):52, 2018.
  * [18] Krzysztof Pietrzak.  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, 2003.
  * [19] Ariel D. Procaccia.  Cake cutting algorithms.  In Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors, Handbook of Computational Social Choice, pages 311–330. Cambridge University Press, Cambridge, UK, 2016.
  * [20] Qingyun Wu and Alvin E. Roth.  The lattice of envy-free matchings.  Games and Economic Behavior, 109:201–211, 2018.
  * [21] Yu Yokoi.  Envy-free matchings with lower quotas.  Algorithmica, 82(2):188–211, 2020.