11institutetext:  Centre for Economic and Regional Studies, Budapest, Hungary,
11email<EMAIL_ADDRESS>22institutetext:
Budapest University of Technology and Economics, Budapest, Hungary
33institutetext: Corvinus University of Budapest, Budapest, Hungary

#  The core of housing markets from an agent’s perspective: Is it worth
sprucing up your home?

Ildikó Schlotter 1122 Péter Biró 1133 Tamás Fleiner 1122

###### Abstract

We study housing markets as introduced by Shapley and Scarf (1974). We
investigate the computational complexity of various questions regarding the
situation of an agent $a$ in a housing market $H$: we show that it is
$\mathsf{NP}$-hard to find an allocation in the core of $H$ where (i) $a$
receives a certain house, (ii) $a$ does not receive a certain house, or (iii)
$a$ receives a house other than her own. We prove that the core of housing
markets _respects improvement_ in the following sense: given an allocation in
the core of $H$ where agent $a$ receives a house $h$, if the value of the
house owned by $a$ increases, then the resulting housing market admits an
allocation in its core in which $a$ receives either $h$ or a house that $a$
prefers to $h$; moreover, such an allocation can be found efficiently. We
further show an analogous result in the Stable Roommates setting by proving
that stable matchings in a one-sided market also respect improvement.

##  1 Introduction

Housing markets are a classic model in economics where agents are initially
endowed with one unit of an indivisible good, called a _house_ , and agents
may trade their houses according to their preferences without using monetary
transfers. In such markets, trading results in a reallocation of houses in a
way that each agent ends up with exactly one house. Motivation for studying
housing markets comes from applications such as kidney exchange [36, 8, 12]
and on-campus housing [1].

In their seminal work Shapley and Scarf [39] examined housing markets where
agents’ preferences are weak orders. They proved that such markets always
admit a _core_ allocation, that is, an allocation where no coalition of agents
can strictly improve their situation by trading only among themselves. They
also described the Top Trading Cycles (TTC) algorithm, proposed by David Gale,
and proved that the set of allocations that can be obtained through the TTC
algorithm coincides with the set of competitive allocations; hence the TTC
always produces an allocation in the core. When preferences are strict, the
TTC produces the unique allocation in the _strict core_ , that is, an
allocation where no coalition of agents can weakly improve their situation by
trading among themselves [35].

Although the core of housing markets has been the subject of considerable
research, there are still many challenges which have not been addressed.
Consider the following question: given an agent $a$ and a house $h$, does
there exist an allocation in the core where $a$ obtains $h$? Or one where $a$
does not obtain $h$? Can we determine whether $a$ may receive a house better
than her own in some core allocation? Similar questions have been extensively
studied in the context of the Stable Marriage and the Stable Roommates
problems [31, 23, 21, 22, 20], but have not yet been considered in relation to
housing markets.

Even less is known about the core of housing markets in cases where the market
is not static. Although some researchers have addressed certain dynamic
models, most of these either focus on the possibility of repeated allocation
[35, 28, 29], or consider a situation where agents may enter and leave the
market at different times [43, 13, 32]. Recently, Biró et al. [9] have
investigated how a change in the preferences of agents affects the housing
market. Namely, they considered how an improvement of the house belonging to
agent $a$ affects the situation of $a$. Following their lead, we aim to answer
the following question: if the value of the house belonging to agent $a$
increases, how does this affect the core of the market from the viewpoint of
$a$? Is such a change bound to be beneficial for $a$, as one would expect?
This question is of crucial importance in the context of kidney exchange: if
procuring a new donor with better properties (e.g., a younger or healthier
donor) does not necessarily benefit the patient, then this could undermine the
incentive for the patient to find a donor with good characteristics, damaging
the overall welfare.

###  1.1 Our contribution

We consider the computational complexity of deciding whether the core of a
housing market contains an allocation where a given agent $a$ obtains a
certain house. In Theorem 3.1 we prove that this problem is
$\mathsf{NP}$-complete, as is the problem of finding a core allocation where
$a$ does _not_ receive a certain house. Even worse, it is already
$\mathsf{NP}$-complete to decide whether a core allocation can assign _any_
house to $a$ other than her own. Various generalizations of these questions
can be answered efficiently in both the Stable Marriage and Stable Roommates
settings [31, 23, 21, 22, 20], so we find these intractability results
surprising.

Instead of asking for a core allocation where a given agent can trade her
house, one can also look at the optimization problem which asks for an
allocation in the core with the maximum number of agents involved in trading.
This problem is known to be $\mathsf{NP}$-complete [18]. We show in Theorem
3.2 that for any $\varepsilon>0$, approximating this problem with ratio
$|N|^{1-\varepsilon}$ for a set $N$ of agents is $\mathsf{NP}$-hard. We
complement this strong inapproximability result in Proposition 1 by pointing
out that a trivial approach yields an approximation algorithm with ratio
$|N|$.

Turning our attention to the question of how an increase in the value of a
house affects its owner, we show the following result in Theorem 4.1. If the
core of a housing market contains an allocation where $a$ receives a house
$h$, and the market changes in a way that some agents perceive an increased
value for the house owned by $a$ (and nothing else changes in the market),
then the resulting housing market admits an allocation in its core where $a$
receives either $h$ or a house that $a$ prefers to $h$. We prove this by
presenting an algorithm that finds such an allocation. This settles an open
question by Biró et al. [9] who ask whether the core _respects improvement_ in
the sense that the best allocation achievable for an agent $a$ in a core
allocation can only (weakly) improve for $a$ as a result of an increase in the
value of $a$’s house.

It is clear that an increase in the value of $a$’s house may not always yield
a _strict_ improvement for $a$ (as a trivial example, some core allocation may
assign $a$ her top choice even before the change), but one may wonder if we
can efficiently determine when a strict improvement for $a$ becomes possible.
This problem turns out to be closely related to the question whether $a$ can
obtain a given house in a core allocation; in fact, we were motivated to study
the latter problem by our interest in determining the possibilities for a
strict improvement. Although one can formulate several variants of the problem
depending on what exactly one considers to be a strict improvement, by Theorem
4.2 each of them leads to computational intractability ($\mathsf{NP}$-hardness
or $\mathsf{coNP}$-hardness).

Finally, we also answer a question raised by Biró et al. [9] regarding the
property of respecting improvements in the context of the Stable Roommates
problem. An instance of Stable Roommates contains a set of agents, each having
preferences over the other agents; the usual task is to find a matching
between the agents that is _stable_ , i.e., no two agents prefer each other to
their partners in the matching. It is known that a stable matching need not
always exist, but if it does, then Irving’s algorithm [26] finds one
efficiently. In Theorem 5.1 we show that if some stable matching assigns agent
$a$ to agent $b$ in a Stable Roommates instance, and the valuation of $a$
increases (that is, if $a$ moves upward in other agents’ preferences, with
everything else remaining constant), then the resulting instance admits a
stable matching where $a$ is matched either to $b$ or to an agent preferred by
$a$ to $b$. This result is a direct analog of the one stated in Theorem 4.1
for the core of housing markets; however, the algorithm we propose in order to
prove it uses different techniques. In Proposition 5 we also provide an
observation about strongly stable matchings in the Stable Marriage model,
showing that if agents have weakly ordered preferences, then strongly stable
matchings do not satisfy the property of respecting improvements.

We remark that we use a model with partially ordered preferences (a
generalization of weak orders), and provide a linear-time implementation of
the TTC algorithm in such a model.

###  1.2 Related work

Most works relating to the core of housing markets aim for finding core
allocations with some additional property that benefits global welfare, most
prominently Pareto optimality [27, 4, 5, 34, 38]. Another line of research
comes from kidney exchange where the length of trading cycles is of great
importance and often plays a role in agents’ preferences [19, 16, 15, 7, 17]
or is bounded by some constant [2, 10, 11, 25, 18]. None of these papers deal
with problems where a core allocation is required to fulfill some constraint
regarding a given agent or set of agents—that they be trading, or that they
obtain (or not obtain) a certain house. Nevertheless, some of them focus on
finding a core allocation where the number of agents involved in trading is as
large as possible. Cechlárová and Repiský [18] proved that this problem is
$\mathsf{NP}$-hard in the classical housing market model, while Biró and
Cechlárová [7] considered a special model where agents care first about the
house they receive and after that about the length of their trading cycle
(shorter being better); they prove that for any $\varepsilon>0$, it is
$\mathsf{NP}$-hard to approximate the number of agents trading in a core
allocation with a ratio $|N|^{1-\varepsilon}$ (where $N$ is the set of
agents).

The property of respecting improvement has first been studied in a paper by
Balinski and Sönmez [6] on college admission. They proved that the student-
optimal stable matching algorithm respects the improvement of students, so a
better test score for a student always results in an outcome weakly preferred
by the student (assuming other students’ scores remain the same). Hatfield et
al. [24] contrasted their findings by showing that no stable mechanism
respects the improvement of school quality. Sönmez and Switzer [40] applied
the model of matching with contracts to the problem of cadet assignment in the
United States Military Academy, and have proved that the cadet-optimal stable
mechanism respects improvement of cadets. Recently, Klaus and Klijn [30] have
obtained results of a similar flavor in a school-choice model with minimal-
access rights.

Roth et al. [37] deal with the property of respecting improvement in
connection with kidney exchange: they show that in a setting with dichotomous
preferences and pairwise exchanges priority mechanisms are donor monotone,
meaning that a patient can only benefit from bringing an additional donor on
board. Biró et al. [9] focus on the classical Shapley-Scarf model and
investigate how different solution concepts behave when the value of an
agent’s house increases. They prove that both the strict core and the set of
competitive allocations satisfy the property of respecting improvements,
however, this is no longer true when the lengths of trading cycles are bounded
by some constant.

##  2 Preliminaries

Here we describe our model, and provide all the necessary notation.
Information about the organization of this paper can be found at the end of
this section.

###  2.1 Preferences as partial orders

In the majority of the existing literature, preferences of agents are usually
considered to be either strict or, if the model allows for indifference, weak
linear orders. Weak orders can be described as lists containing _ties_ , a set
of alternatives considered equally good for the agent. Partial orders are a
generalization of weak orders that allow for two alternatives to be
_incomparable_ for an agent. Incomparability may not be transitive, as opposed
to indifference in weak orders. Formally, an (irreflexive)111Throughout the
paper we will use the term _partial ordering_ in the sense of an irreflexive
(or strict) partial ordering. _partial ordering_ $\prec$ on a set of
alternatives is an irreflexive, antisymmetric and transitive relation.

Partially ordered preferences arise by many natural reasons; we give two
examples motivated by kidney exchanges. For example, agents may be indifferent
between goods that differ only slightly in quality. Indeed, recipients might
be indifferent between two organs if their expected graft survival times
differ by less than one year. However, small differences may add up to a
significant contrast: an agent may be indifferent between $a$ and $b$, and
also between $b$ and $c$, but strictly prefer $a$ to $c$. Partial preferences
also emerge in multiple-criteria decision making. The two most important
factors for estimating the quality of a kidney transplant are the HLA-matching
between donor and recipient, and the age of the donor.222In fact, these are
the two factors for which patients in the UK program can set acceptability
thresholds [8]. An organ is considered better than another if it is better
with respect to both of these factors, leading to partial orders.

###  2.2 Housing markets

Let $H=(N,\\{\prec_{a}\\}_{a\in N})$ be a _housing market_ with agent set $N$
and with the preferences of each agent $a\in N$ represented by a partial
ordering $\prec_{a}$ of the agents. For agents $a$, $b$, and $c$, we will
write $a\preceq_{c}b$ as equivalent to $b\not\prec_{c}a$, and we write
$a\sim_{c}b$ if $a\not\prec_{c}b$ and $b\not\prec_{c}a$. We interpret
$a\prec_{c}b$ (or $a\preceq_{c}b$) as agent $c$ _preferring_ (or _weakly
preferring_ , respectively) the house owned by agent $b$ to the house of agent
$a$. We say that agent $a$ finds the house of $b$ _acceptable_ , if
$a\preceq_{a}b$, and we denote by $A(a)=\\{b\in N:a\preceq_{a}b\\}$ the set of
agents whose house is acceptable for $a$. We define the _acceptability graph_
of the housing market $H$ as the directed graph $G^{H}=(N,E)$ with
$E=\\{(a,b)\mid b\in A(a)\\}$; we let $|G^{H}|=|N|+|E|$. Note that $(a,a)\in
E$ for each $a\in N$. The _submarket_ of $H$ on a set $W\subseteq N$ of agents
is the housing market $H_{W}=(W,\\{\prec_{a}^{|_{W}}\\}_{a\in W})$ where
$\prec_{a}^{|_{W}}$ is the partial order $\prec_{a}$ restricted to $W$; the
acceptability graph of $H_{W}$ is the subgraph of $G^{H}$ induced by $W$,
denoted by $G^{H}[W]$. For a set $W$ of agents, let $H-W$ be the submarket
$H_{N\setminus W}$ obtained by _deleting_ $W$ from $H$; for $W=\\{a\\}$ we may
write simply $H-a$.

For a set $X\subseteq E$ of arcs in $G^{H}$ and an agent $a\in N$ we let
$X(a)$ denote the set of agents $b$ such that $(a,b)\in X$; whenever $X(a)$ is
a singleton $\\{b\\}$ we will abuse notation by writing $X(a)=b$. We also
define $\delta^{-}_{X}(a)$ and $\delta^{+}_{X}(a)$ as the number of in-going
and out-going arcs of $a$ in $X$, respectively. For a set $W\subseteq N$ of
agents, we let $X[W]$ denote the set of arcs in $X$ that run between agents of
$W$.

We define an _allocation_ $X$ in $H$ as a subset $X\subseteq E$ of arcs in
$G^{H}$ such that $\delta^{-}_{X}(a)=\delta^{+}_{X}(a)=1$ for each $a\in N$,
that is, $X$ forms a collection of cycles in $G^{H}$ containing each agent
exactly once. Then $X(a)$ denotes the agent whose house $a$ obtains according
to allocation $X$. If $X(a)\neq a$, then $a$ is _trading_ in $X$. For
allocations $X$ and $X^{\prime}$, we say that $a$ _prefers_ $X$ to
$X^{\prime}$ if $X^{\prime}(a)\prec_{a}X(a)$.

For an allocation $X$ in $H$, an arc $(a,b)\in E$ is _$X$ -augmenting_, if
$X(a)\prec_{a}b$. We define the _envy graph_ $G^{H}_{X\prec}$ of $X$ as the
subgraph of $G^{H}$ containing all $X$-augmenting arcs. A _blocking cycle_ for
$X$ in $H$ is a cycle in $G^{H}_{X\prec}$, that is, a cycle $C$ where each
agent $a$ on $C$ prefers $C(a)$ to $X(a)$. An allocation $X$ is contained in
the _core_ of $H$, if there does not exist a blocking cycle for it, i.e., if
$G^{H}_{X\prec}$ is acyclic. A _weakly blocking cycle_ for $X$ is a cycle $C$
in $G^{H}$ where $X(a)\preceq_{a}C(a)$ for each agent $a$ on $C$ and
$X(a)\prec_{a}C(a)$ for at least one agent $a$ on $C$. The _strict core_ of
$H$ contains allocations that do not admit weakly blocking cycles.

###  2.3 Organization

Section 3 contains an adaptation of the TTC algorithm for partially ordered
preferences, followed by our results on finding core allocations with various
arc restrictions and on maximizing the number of agents involved in trading.
In Section 4 we present our results on the property of respecting improvements
in relation to the core of housing markets, including our main technical
result, Theorem 4.1. In Section 5 we study the respecting improvement property
in the context of Stable Roommates. Section 6 contains some questions for
future research.

##  3 The core of housing markets: some computational problems

We investigate a few computational problems related to the core of housing
markets. In Section 3.1 we describe our adaptation of TTC to partially ordered
preferences. In Section 3.2 we turn our attention to the problem of finding an
allocation in the core of a housing market that satisfies certain arc
restrictions, requiring that a given arc be contained or, just the opposite,
not be contained in the desired allocation. In Section 3.3 we look at the most
prominent optimization problem in connection with the core: given a housing
market, find an allocation in its core where the number of trading agents is
as large as possible.

###  3.1 Top Trading Cycles for preferences with incomparability

Here we present an adaptation of the Top Trading Cycles algorithm for the case
when agents’ preferences are represented as partial orders. We start by
recalling how TTC works for strict preferences, propose a method to deal with
partial orders, and finally discuss how the obtained algorithm can be
implemented in linear time.

#### Strict preferences.

If agents’ preferences are represented by strict orders, then the TTC
algorithm [39] produces the unique allocation in the strict core. TTC creates
a directed graph $D$ where each agent $a$ points to her top choice, that is,
to the agent owning the house most preferred by $a$. In the graph $D$ each
agent has out-degree exactly 1, since preferences are assumed to be strict.
Hence, $D$ contains at least one cycle, and moreover, the cycles in $D$ do not
intersect. TTC selects all cycles in $D$ as part of the desired allocation,
deletes from the market all agents trading along these cycles, and repeats the
whole process until there are no agents left.

#### Preferences as partial orders.

When preferences are represented by partial orders, one can modify the TTC
algorithm by letting each agent $a$ in $D$ point to her _undominated_ choices:
$b$ is undominated for $a$, if there is no agent $c$ such that $b\prec_{a}c$.
Notice that an agent’s out-degree is then _at least_ 1 in $D$. Thus, $D$
contains at least one cycle, but in case it contains more than one cycle,
these may overlap.

A simple approach is to select a set of mutually vertex-disjoint cycles in
each round, removing the agents trading along them from the market and
proceeding with the remainder in the same manner. It is not hard to see that
this approach yields an algorithm that produces an allocation in the core: by
the definition of undominated choices, any arc of a blocking cycle leaving an
agent $a$ necessarily points to an agent that was already removed from the
market at the time when a cycle containing $a$ got selected. Clearly, no cycle
may consist of such “backward” arcs only, proving that the computed allocation
is indeed in the core.

#### Implementation in linear time.

Abraham et al. [3] describe an implementation of the TTC algorithm for strict
preferences that runs in $O(|G^{H}|)$ time. We extend their ideas to the case
when preferences are partial orders as follows.

For each agent $a\in N$ we assume that $a$’s preferences are given using a
_Hasse diagram_ which is a directed acyclic graph $H_{a}$ that can be thought
of as a compact representation of $\prec_{a}$. The vertex set of $H_{a}$ is
$A(a)$, and it contains an arc $(b,c)$ if and only if $b\prec_{a}c$ and there
is no agent $c^{\prime}$ with $b\prec_{a}c^{\prime}\prec_{a}c$. Then the
description of our housing market $H$ has length $\sum_{a\in A}|H_{a}|$ which
we denote by $|H|$. If preferences are weak or strict orders, then
$|H|=O(|G^{H}|)$.

Throughout our variant of TTC, we will maintain a list $U(a)$ containing the
undominated choices of $a$ among those that still remain in the market, as
well as a subgraph $D$ of $G^{H}$ spanned by all arcs $(a,b)$ with $b\in
U(a)$. Furthermore, for each agent $a$ in the market, we will keep a list of
all occurrences of $a$ as someone’s undominated choice. Using $H_{a}$ we can
find the undominated choices of $a$ in $O(|H_{a}|)$ time, so initialization
takes $O(|H|)$ time in total.

Whenever an agent $a$ is deleted from the market, we find all agents $b$ such
that $a\in U(b)$, and we update $U(b)$ by deleting $a$ and adding those in-
neighbors of $a$ in $H_{b}$ which have no out-neighbor still present in the
market. Notice that the total time required for such deletions (and the
necessary replacements) to maintain $U(b)$ is $O(|H_{b}|)$. Hence, we can
efficiently find the undominated choices of each agent at any point during the
algorithm, and thus traverse the graph $D$ consisting of arcs $(a,b)$ with
$b\in U(a)$.

To find a cycle in $D$, we simply keep building a path using arcs of $D$,
until we find a cycle (perhaps a loop). After recording this cycle and
deleting its agents from the market (updating the lists $U(a)$ as described
above), we simply proceed with the last agent on our path. Using the data
structures described above the total running time of our variant of TTC is
$O(|N|+\sum_{a\in N}|H_{a}|)=O(|H|)$.

###  3.2 Allocations in the core with arc restrictions

We now focus on the problem of finding an allocation in the core that fulfills
certain arc constraints. The simplest such constraints arise when we require a
given arc to be included in, or conversely, be avoided by the desired
allocation.

The input of the Arc in Core problem consists of a housing market $H$ and an
arc $(a,b)$ in $G^{H}$, and its task is to decide whether there exists an
allocation in the core of $H$ that contains $(a,b)$, or in other words, where
agent $a$ obtains the house of agent $b$. Analogously, the Forbidden Arc in
Core problem asks to decide if there exists an allocation in the core of $H$
_not_ containing $(a,b)$.

By giving a reduction from Acyclic Partition [14], we show in Theorem 3.1 that
both of these problems are computationally intractable, even if each agent has
a strict ordering over the houses. In fact, we cannot even hope to decide for
a given agent $a$ in a housing market $H$ whether there exists an allocation
in the core of $H$ where $a$ is trading; we call this problem Agent Trading in
Core.

######  Theorem 3.1.

Each of the following problems is $\mathsf{NP}$-complete, even if agents’
preferences are strict orders:

  * •

Arc in Core,

  * •

Forbidden Arc in Core, and

  * •

Agent Trading in Core.

###### Proof.

It is easy to see that all of these problems are in $\mathsf{NP}$, since given
an allocation $X$ for $H$, we can check in linear time whether it admits a
blocking cycle: taking the envy graph $G_{X\prec}^{H}$ of $X$, we only have to
check that it is _acyclic_ , i.e., contains no directed cycles (this can be
decided using, e.g., some variant of the depth-first search algorithm).

To prove the $\mathsf{NP}$-hardness of Arc in Core, we present a polynomial-
time reduction from the Acyclic Partition problem: given a directed graph $D$,
decide whether it is possible to partition the vertices of $D$ into two
acyclic sets $V_{1}$ and $V_{2}$. Here, a set $W$ of vertices is _acyclic_ ,
if $D[W]$ is acyclic. This problem was proved to be $\mathsf{NP}$-complete by
Bokal et al. [14].

Given our input $D=(V,A)$, we construct a housing market $H$ as follows (see
Fig. 1 for an illustration). We denote the vertices of $D$ by
$v_{1},\dots,v_{n}$, and we define the set of agents in $H$ as

$N=\\{a_{i},b_{i},c_{i},d_{i}\mid
i\in\\{1,\dots,n\\}\cup\\{a^{\star},b^{\star},a_{0},b_{0}\\}.$

The preferences of the agents’ are as shown below; for each agent $a\in N$ we
only list those agents whose house $a$ finds acceptable. Here, for any set $W$
of agents we let $[W]$ denote an arbitrary fixed ordering of $W$.

$\begin{array}[]{lll}a^{\star}:&b^{\star};&\\\
b^{\star}:&a_{0},a_{1},\dots,a_{n},a^{\star};&\\\
a_{i}:&b_{i},b^{\star}&\textrm{ where $i\in\\{0,1,\dots,n\\}$};\\\
b_{i}:&c_{i+1},d_{i+1}&\textrm{ where $i\in\\{0,1,\dots,n-1\\}$};\\\
b_{n}:&a_{0};&\\\ c_{i}:&d_{i},[\\{c_{j}\mid(v_{i},v_{j})\in
A\\}],a_{i}&\textrm{ where $i\in\\{1,\dots,n\\}$};\\\
d_{i}:&c_{i},[\\{d_{j}\mid(v_{i},v_{j})\in A\\}],a_{i}&\textrm{ where
$i\in\\{1,\dots,n\\}$}.\\\ \end{array}$

Figure 1: Illustration of the housing market $H$ constructed in the
$\mathsf{NP}$-hardness proof for Arc in Core. Here and everywhere else we
depict markets through their acceptability graphs with all loops omitted.
Preferences are indicated by numbers along the arcs; the symbol $\infty$
indicates the least-preferred choice of an agent. The example assumes that
$(v_{1},v_{2})$ and $(v_{n},v_{2})$ are arcs of the directed input graph $D$,
as indicated by the dashed arcs.

We finish the construction by defining our instance of Arc in Core as the pair
$(H,(a^{\star},b^{\star}))$. We claim that there exists an allocation in the
core of $H$ containing $(a^{\star},b^{\star})$ if and only if the vertices of
$D$ can be partitioned into two acyclic sets.

“$\Rightarrow$”: Let us suppose that there exists an allocation $X$ that does
not admit any blocking cycles and contains $(a^{\star},b^{\star})$.

We first show that $X$ contains every arc $(a_{i},b_{i})$ for
$i\in\\{0,1,\dots,n\\}$. To see this, observe that the only possible cycle in
$X$ that contains $(a^{\star},b^{\star})$ is the cycle $(a^{\star},b^{\star})$
of length 2, because the arc $(b^{\star},a^{\star})$ is the only arc going
into $a^{\star}$. Hence, if for some $i\in\\{0,1,\dots,n\\}$ the arc
$(a_{i},b_{i})$ is not in $X$, then the cycle $(a_{i},b^{\star})$ is a
blocking cycle. As a consequence, exactly one of the arcs $(b_{i},c_{i+1})$
and $(b_{i},d_{i+1})$ must be contained in $X$ for any
$i\in\\{0,1,\dots,n-1\\}$, and similarly, exactly one of the arcs
$(c_{i},a_{i})$ and $(d_{i},a_{i})$ is contained in $X$ for any
$i\in\\{1,\dots,n\\}$.

Next consider the agents $c_{i}$ and $d_{i}$ for some $i\in\\{1,\dots,n\\}$.
As they are each other’s top choice, it must be the case that either
$(c_{i},d_{i})$ or $(d_{i},c_{i})$ is contained in $X$, as otherwise they both
prefer to trade with each other as opposed to their allocation according to
$X$, and the cycle $(c_{i},d_{i})$ would block $X$. Using the facts of the
previous paragraph, we obtain that for each $v_{i}\in V$ exactly one of the
following conditions holds:

  * •

$X$ contains the arcs $(b_{i-1},c_{i})$, $(c_{i},d_{i})$, and $(d_{i},a_{i})$,
in which case we put $v_{i}$ into $V_{1}$;

  * •

$X$ contains the arcs $(b_{i-1},d_{i})$, $(d_{i},c_{i})$, and $(c_{i},a_{i})$,
in which case we put $v_{i}$ into $V_{2}$.

We claim that both $V_{1}$ and $V_{2}$ are acyclic in $D$. For a
contradiction, let $C_{1}$ be a cycle within vertices of $V_{1}$ in $D$. Note
that any arc $(v_{i},v_{j})$ of $C_{1}$ corresponds to an arc $(d_{i},d_{j})$
in the acceptability graph $G=G^{H}$ for $H$. Moreover, since $v_{i}\in
V_{1}$, by definition we know that $d_{i}$ prefers $d_{j}$ to
$X(d_{i})=a_{i}$. This yields that the agents $\\{d_{i}\mid v_{i}\textrm{
appears on }C_{1}\\}$ form a blocking cycle for $H$. The same argument works
to show that any cycle $C_{2}$ within $V_{2}$ corresponds to a blocking cycle
formed by the agents $\\{c_{i}\mid v_{i}\textrm{ appears on }C_{2}\\}$,
proving the acyclicity of $V_{2}$.

“$\Leftarrow$”: Assume now that $V_{1}$ and $V_{2}$ are two acyclic subsets of
$V$ forming a partition. We define an allocation $X$ to contain the cycle
$(a^{\star},b^{\star})$, and a cycle consisting of the arcs in

$\displaystyle X_{\circ}$ $\displaystyle=$
$\displaystyle\\{(b_{n},a_{0})\\}\cup\\{(a_{i},b_{i})\mid
v\in\\{0,1,\dots,n\\}\\}$
$\displaystyle\cup\,\\{(b_{i-1},c_{i}),(c_{i},d_{i}),(d_{i},a_{i})\mid
v_{i}\in V_{1}\\}$
$\displaystyle\cup\,\\{(b_{i-1},d_{i}),(d_{i},c_{i}),(c_{i},a_{i})\mid
v_{i}\in V_{2}\\}.$

Observe that $X_{\circ}$ is indeed a cycle, and that $X$ is an allocation
containing the arc $(a^{\star},b^{\star})$. We claim that the core of $H$
contains $X$. Assume for the sake of contradiction that $X$ admits a blocking
cycle $C$. Now, since $a^{\star}$, as well as each agent $a_{i}$,
$i\in\\{0,1,\dots,n\\}$, is allocated its first choice by $X$, none of these
agents appears on $C$. This implies that neither $b^{\star}$, nor any of the
agents $b_{i}$, $i\in\\{0,1,\dots,n\\}$, appears on $C$, since these agents
have no in-neighbors that could possibly appear on $C$. Furthermore, every
agent in $\\{c_{i}\mid v_{i}\in V_{1}\\}\cup\\{d_{i}\mid v_{i}\in V_{2}\\}$ is
allocated its first choice by $X$. It follows that $C$ may contain only agents
from $D_{1}=\\{d_{i}\mid v_{i}\in V_{1}\\}$ and $C_{2}=\\{c_{i}\mid v_{i}\in
V_{2}\\}$. Observe that there is no arc in $G$ from $D_{1}$ to $C_{2}$ or vice
versa, hence $C$ is either contained in $G[D_{1}]$ or $G[C_{2}]$. Now, since
any cycle within $G[D_{1}]$ or $G[C_{2}]$ would correspond to a cycle in $D$,
the acyclicity of $V_{1}$ and $V_{2}$ ensures that $X$ admits no blocking
cycle, proving the correctness of our reduction for the Arc in Core problem.

Observe that the same reduction proves the $\mathsf{NP}$-hardness of Agent
Trading in Core, since agent $a^{\star}$ is trading in an allocation $X$ for
$H$ if and only if the arc $(a^{\star},b^{\star})$ is used in $X$.

Finally, we modify the above construction to give a reduction from Acyclic
Partition to Forbidden Arc in Core. We simply add a new agent $s^{\star}$ to
$H$, with the house of $s^{\star}$ being acceptable only for $a^{\star}$ as
its second choice (after $b^{\star}$), and with $s^{\star}$ preferring only
$a^{\star}$ to its own house. We claim that the resulting market $H^{\prime}$
together with the arc $(a^{\star},s^{\star})$ is a yes-instance of Forbidden
Arc in Core if and only if $H$ with $(a^{\star},b^{\star})$ constitutes a yes-
instance of Arc in Core. To see this, it suffices to observe that any
allocation for $H^{\prime}$ not containing $(a^{\star},s^{\star})$ is either
blocked by the cycle $(a^{\star},s^{\star})$ of length 2, or contains the arc
$(a^{\star},b^{\star})$. Hence, any allocation in the core of $H^{\prime}$
contains $(a^{\star},b^{\star})$ if and only if it does not contain
$(a^{\star},s^{\star})$, proving the theorem.

###  3.3 Maximizing the number of agents trading in a core allocation

Perhaps the most natural optimization problem related to the core of housing
markets is the following: given a housing market $H$, find an allocation in
the core of $H$ whose _size_ , defined as the number of trading agents, is
maximal among all allocations in the core of $H$; we call this the Max Core
problem. Max Core is $\mathsf{NP}$-hard by a result of Cechlárová and Repiský
[18]. In Theorem 3.2 below we show that even approximating Max Core is
$\mathsf{NP}$-hard. Our result is tight in the following sense: we prove that
for any $\varepsilon>0$, approximating Max Core with a ratio of
$|N|^{1-\varepsilon}$ is $\mathsf{NP}$-hard, where $|N|$ is the number of
agents in the market. By contrast, a very simple approach yields an
approximation with ratio $|N|$.

We note that Biró and Cechlárová [7] proved a similar inapproximability
result, but since they considered a special model where agents not only care
about the house they receive but also about the length of their exchange
cycle, their result cannot be translated to our model, and so does not imply
Theorem 3.2. Instead, our reduction relies on ideas we use to prove Theorem
3.1.

######  Theorem 3.2.

For any constant $\varepsilon>0$, the Max Core problem is $\mathsf{NP}$-hard
to approximate within a ratio of $\alpha_{\varepsilon}(N)=|N|^{1-\varepsilon}$
where $N$ is the set of agents, even if agents’ preferences are strict orders.

###### Proof.

Let $\varepsilon>0$ be a constant. Assume for the sake of contradiction that
there exists an approximation algorithm $\mathcal{A}_{\varepsilon}$ that given
an instance $H$ of Max Core with agent set $N$ computes in time polynomial in
$|N|$ an allocation in the core of $H$ having size at least
$\textup{OPT}(H)/\alpha_{\varepsilon}(N)$, where $\textup{OPT}(H)$ is the
maximum size of (i.e., number of agents trading in) any allocation in the core
of $H$. We can prove our statement by presenting a polynomial-time algorithm
for the $\mathsf{NP}$-hard Acyclic Partition problem using
$\mathcal{A}_{\varepsilon}$.

We are going to re-use the reduction presented in the proof of Theorem 3.1
from Acyclic Partition to Arc in Core. Recall that the input of this reduction
is a directed graph $D$ on $n$ vertices, and it constructs a housing market
$H$ containing a set $N$ of $4n+4$ agents and a pair $(a^{\star},b^{\star})$
of agents such that the vertices of $D$ can be partitioned into two acyclic
sets if and only if some allocation in the core of $H$ contains the arc
$(a^{\star},b^{\star})$. Moreover, such an allocation (if existent) must have
size $4n+4$, by our arguments in the proof of Theorem 3.1.

Let us now define a housing market
$H^{\prime}=(N^{\prime},\\{\prec_{a}\\}_{a\in N^{\prime}})$ that can be
obtained by subdividing the arc $(a^{\star},b^{\star})$ with $K$ newly
introduced agents $p_{1},\dots,p_{K}$ where

$K=\left\lceil(4n+4)^{1/\varepsilon}\right\rceil.$

Let $N^{\prime}=N\cup\\{p_{1},\dots,p_{K}\\}$. Formally, we define preferences
$\prec^{\prime}_{a}$ for each agent $a\in N^{\prime}$ as follows:
$\prec^{\prime}_{a}$ is identical to $\prec_{a}$ if $a\in
N\setminus\\{a^{\star}\\}$, $\prec^{\prime}_{a^{\star}}$ is obtained from
$\prec_{a^{\star}}$ by $p_{1}$ taking the role of $b^{\star}$, and each agent
$p_{i}\in N^{\prime}\setminus N$ prefers only the house of agent $p_{i+1}$ to
her own house (where we set $p_{K+1}=b^{\star}$). Clearly, the allocations in
the core of $H$ correspond to the allocations in the core of $H^{\prime}$ in a
bijective manner. Hence, it is easy to see that if there is an allocation in
the core of $H$ that contains $(a^{\star},b^{\star})$ and where every agent of
$N$ is trading, then there is an allocation in the core of $H^{\prime}$ where
each agent of $N^{\prime}$ is trading. Conversely, if there is no allocation
in the core of $H$ that contains $(a^{\star},b^{\star})$, then the agents
$p_{1},\dots,p_{K}$ cannot be trading in any allocation in the core of
$H^{\prime}$. Thus, we have that if $D$ is a yes-instance of Acyclic
Partition, then $\textup{OPT}(H^{\prime})=|N^{\prime}|=4n+4+K$; otherwise
$\textup{OPT}(H^{\prime})\leq 4n+4$.

Now, after constructing $H^{\prime}$ we apply algorithm
$\mathcal{A}_{\varepsilon}$ with $H^{\prime}$ as its input; let $X^{\prime}$
be its output. If the size of $X^{\prime}$ is greater than $4n+4$, then we
conclude that $D$ must be a yes-instance of Acyclic Partition, as implied by
the previous paragraph. Otherwise, we conclude that $D$ is a no-instance of
Acyclic Partition. To show that this is correct, it suffices to see that if
$D$ is a yes-instance, that is, if $\textup{OPT}(H^{\prime})=|N^{\prime}|$,
then the size of $X^{\prime}$ is greater than $4n+4$. And indeed, the
definition of $K$ implies

$(4n+4)^{1/\varepsilon}<4n+4+K=|N^{\prime}|$

which raised to the power of $\varepsilon$ yields

$4n+4<|N^{\prime}|^{\varepsilon}=\frac{|N^{\prime}|}{|N^{\prime}|^{1-\varepsilon}}=\frac{\textup{OPT}(H^{\prime})}{\alpha_{\varepsilon}(N^{\prime})}$

as required.

It remains to observe that the above reduction can be computed in polynomial
time, because $\varepsilon$ is a constant and so $K$ is a polynomial of $n$ of
fixed degree.

We contrast Theorem 3.2 with the observation that an algorithm that outputs
_any_ allocation in the core yields an approximation for Max Core with ratio
$|N|$.

######  Proposition 1.

Max Core can be approximated with a ratio of $|N|$ in polynomial time, where
$|N|$ is the number of agents in the input.

###### Proof.

An approximation algorithm for Max Core has ratio $|N|$, if for any housing
market $H$ with agent set $N$ it outputs an allocation with at least
$\textup{OPT}(H)/|N|$ agents trading, where $\textup{OPT}(H)$ is the maximum
number of trading agents in a core allocation of $H$. Thus, it suffices to
decide whether $\textup{OPT}(H)\geq 1$, and if so produce an allocation in
which at least one agent is trading. Observe that $\textup{OPT}(H)=0$ is only
possible if $G^{H}$ is acyclic, as any cycle in $G^{H}$ blocks the allocation
where each agent gets her own house. Hence, computing _any_ allocation in the
core of $H$ is an $|N|$-approximation for Max Core; this can be done in linear
time using the variant of the TTC algorithm described in Section 3.1.

##  4 The effect of improvements in housing markets

Let $H=(N,\\{\prec_{a}\\}_{a\in N})$ be a housing market containing agents $p$
and $q$. We consider a situation where the preferences of $q$ are modified by
“increasing the value” of $p$ for $q$ without altering the preferences of $q$
over the remaining agents. If the preferences of $q$ are given by a strict or
weak order, then this translates to _shifting_ the position of $p$ in the
preference list of $q$ towards the top. Formally, a housing market
$H^{\prime}=(N,\\{\prec^{\prime}_{a}\\}_{a\in N})$ is called a
$(p,q)$-_improvement_ of $H$, if $\prec_{a}=\prec^{\prime}_{a}$ for any $a\in
N\setminus\\{q\\}$, and $\prec^{\prime}_{q}$ is such that (i)
$a\prec^{\prime}_{q}b$ iff $a\prec_{q}b$ for any $a,b\in N\setminus\\{p\\}$,
and (ii) if $a\prec_{q}p$, then $a\prec^{\prime}_{q}p$ for any $a\in N$. We
will also say that a housing market is a _$p$ -improvement_ of $H$, if it can
be obtained by a sequence of $(p,q_{i})$-improvements for a series
$q_{1},\dots,q_{k}$ of agents for some $k\in\mathbb{N}$.

To examine how $p$-improvements affect the situation of $p$ in the market, one
may consider several solution concepts such as the core, the strict core, and
so on. We regard a solution concept as a function $\Phi$ that assigns a set of
allocations to each housing market. Based on the preferences of $p$, we can
compare allocations in $\Phi$. Let $\Phi^{+}_{p}(H)$ denote the set containing
the best houses $p$ can obtain in $\Phi(H)$:

$\Phi^{+}_{p}(H)=\\{X(p)\mid X\in\Phi(H),\forall
X^{\prime}\in\Phi(H):X^{\prime}(p)\preceq_{p}X(p)\\}.$

Similarly, let $\Phi^{-}_{p}(H)$ be the set containing the worst houses $p$
can obtain in $\Phi(H)$.

Following the notation used by Biró et al. [9], we say that $\Phi$ _respects
improvement for the best available house_ or simply _satisfies the RI-best
property_ , if for any housing markets $H$ and $H^{\prime}$ such that
$H^{\prime}$ is a $p$-improvement of $H$ for some agent $p$,
$a\preceq_{p}a^{\prime}$ for every $a\in\Phi^{+}_{p}(H)$ and
$a^{\prime}\in\Phi^{+}_{p}(H^{\prime})$. Similarly, $\Phi$ _respects
improvement for the worst available house_ or simply _satisfies the RI-worst
property_ , if for any housing markets $H$ and $H^{\prime}$ such that
$H^{\prime}$ is a $p$-improvement of $H$ for some agent $p$,
$a\preceq_{p}a^{\prime}$ for every $a\in\Phi^{-}_{p}(H)$ and
$a^{\prime}\in\Phi^{-}_{p}(H^{\prime})$.

Notice that the above definition does not take into account the possibility
that a solution concept $\Phi$ may become empty as a result of a
$p$-improvement. To exclude such a possibility, we may require the condition
that an improvement does not destroy all solutions. We say that $\Phi$
_strongly satisfies the RI-best (or RI-worst) property_ , if besides
satisfying the RI-best (or, respectively, RI-worst) property, it also
guarantees that whenever $\Phi(H)\neq\emptyset$, then
$\Phi(H^{\prime})\neq\emptyset$ also holds where $H^{\prime}$ is a
$p$-improvement of $H$ for some agent $p$.

We prove that the core of housing markets strongly satisfies the RI-best
property. In fact, Theorem 4.1 (proved in Section 4.2) states a slightly
stronger statement.

######  Theorem 4.1.

For any allocation $X$ in the core of housing market $H$ and a $p$-improvement
$H^{\prime}$ of $H$, there exists an allocation $X^{\prime}$ in the core of
$H^{\prime}$ such that either $X(p)=X^{\prime}(p)$ or $p$ prefers $X^{\prime}$
to $X$. Moreover, given $H$, $H^{\prime}$ and $X$, it is possible to find such
an allocation $X^{\prime}$ in $O(|H|)$ time.

######  Corollary 1.

The core of housing markets strongly satisfies the RI-best property.

By contrast, we show that the RI-worst property does not hold for the core.

######  Proposition 2.

The core of housing markets violates the RI-worst property.

Figure 2: The housing markets $H$ and $H^{\prime}$ in the proof of Proposition
2. For both $H$ and $H^{\prime}$, the allocation represented by bold (and
blue) arcs yields the worst possible outcome for $p$ in any core allocation of
the given market.

###### Proof.

Let $N=\\{a,b,c,p,q\\}$ be the set of agents. The preferences indicated in
Figure 2 define a housing market $H$ and a $(p,q)$-improvement $H^{\prime}$ of
$H$.

We claim that in every allocation in the core of $H$, agent $p$ obtains the
house of $a$. To see this, let $X$ be an allocation where $(p,a)\notin X$. If
agent $a$ is not trading in $X$, then $a$ and $p$ form a blocking cycle;
therefore, $(b,a)\in X$. Now, if $(c,b)\notin X$, then $c$ and $b$ form a
blocking cycle for $X$; otherwise, $q$ and $b$ form a blocking cycle for $X$.
Hence, $p$ obtains her top choice in all core allocations of $H$.

However, it is easy to verify that the core of $H^{\prime}$ contains an
allocation where $p$ obtains only her second choice ($q$’s house), as shown in
Figure 2.

We describe our algorithm for proving Theorem 4.1 in Section 4.1, and prove
its correctness in Section 4.2. In Section 4.3 we look at the problem of
deciding whether a $p$-improvement leads to a situation strictly better for
$p$.

###  4.1 Description of algorithm HM-Improve

Before describing our algorithm for Theorem 4.1, we need some notation.

#### Sub-allocations and their envy graphs.

Given two subsets $U$ and $V$ of agents of the same size (i.e., $|U|=|V|$) in
a housing market $H=(N,\\{\prec_{a}\\}_{a\in N})$, we say that a set $Y$ of
arcs in $G^{H}=(N,E)$ is a _sub-allocation_ from $U$ to $V$ in $H$, if

  * $\bullet$

$\delta^{+}_{Y}(v)=0$ for each $v\in V$, and $\delta^{+}_{Y}(a)=1$ for each
$a\in N\setminus V$;

  * $\bullet$

$\delta^{-}_{Y}(u)=0$ for each $u\in U$, and $\delta^{-}_{Y}(a)=1$ for each
$a\in N\setminus U$.

Note that $Y$ forms a collection of mutually vertex-disjoint cycles and paths
$P_{1},\dots,P_{k}$ in $G^{H}$, with each path $P_{i}$ leading from a vertex
of $U$ to a vertex of $V$. Moreover, the number of paths in this collection is
$k=|U\triangle V|$, where $\triangle$ stands for the symmetric difference
operation. We call $U$ the _source set_ of $Y$, and $V$ its _sink set_.

Given a sub-allocation $Y$ from $U$ to $V$ in $H$, an arc $(a,b)\in E$ is _$Y$
-augmenting_, if either $a\in V$ or $Y(a)\prec_{a}b$. We define the _envy
graph_ of $Y$ as $G^{H}_{Y\prec}=(N,E_{Y})$ where $E_{Y}$ is the set of
$Y$-augmenting arcs in $E$. A blocking cycle for $Y$ is a cycle in
$G^{H}_{Y\prec}$. We say that the sub-allocation $Y$ is _stable_ , if no
blocking cycle exists for $Y$, that is, if its envy graph is acyclic.

We are now ready to propose an algorithm called HM-Improve that given an
allocation $X$ in the core of $H$ outputs an allocation $X^{\prime}$ as
required by Theorem 4.1. Let $q_{1},\dots,q_{k}$ denote the agents for which
$H^{\prime}$ can be obtained from $H$ by a series of $(p,q_{i})$-improvements,
$i=1,\dots,k$. Observe that we can assume w.l.o.g. that the agents
$q_{1},\dots,q_{k}$ are all distinct.

#### Algorithm HM-Improve.

For a pseudocode description, see Algorithm 1.

First, HM-Improve checks whether $X$ belongs to the core of $H^{\prime}$, and
if so, outputs $X^{\prime}=X$. Hence, we may assume that $X$ admits a blocking
cycle in $H^{\prime}$. Let $Q$ denote that set of only those agents among
$q_{1},\dots,q_{k}$ that in $H^{\prime}$ prefer $p$’s house to the one they
obtain in allocation $X$, that is,

$Q=\left\\{q_{i}:X(q_{i})\prec^{\prime}_{q_{i}}p,1\leq i\leq k\right\\}.$

Observe that if an arc is an envy arc for $X$ in $H^{\prime}$ but not in $H$,
then it must be an arc of the form $(q,p)$ where $q\in Q$. Therefore any cycle
that blocks $X$ in $H^{\prime}$ must contain an arc from $\\{(q,p):q\in Q\\}$,
as otherwise it would block $X$ in $H$ as well.

HM-Improve proceeds by modifying the housing market: for each $q\in Q$, it
adds a new agent $\widetilde{q}$ to $H^{\prime}$, with $\widetilde{q}$ taking
the place of $p$ in the preferences of $q$; the only house that agent
$\widetilde{q}$ prefers to her own will be the house of $p$. Let
$\widetilde{H}$ be the housing market obtained. Then the acceptability graph
$\widetilde{G}$ of $\widetilde{H}$ can be obtained from the acceptability
graph of $H^{\prime}$ by subdividing the arc $(q,p)$ for each $q\in Q$ with a
new vertex corresponding to agent $\widetilde{q}$. Let
$\widetilde{Q}=\\{\widetilde{q}:q\in Q\\}$,
$\widetilde{N}=N\cup\widetilde{Q}$, and let $\widetilde{E}$ be the set of arcs
in $\widetilde{G}$.

Initialization. Let $Y=X\setminus\\{(q,X(q)):q\in
Q\\}\cup\\{(q,\widetilde{q}):q\in Q\\}$ in $\widetilde{G}$. Observe that $Y$
is a sub-allocation in $\widetilde{H}$ with source set $\\{X(q):q\in Q\\}$ and
sink set $\widetilde{Q}$. Additionally, we define a set $R$ of _irrelevant_
agents, initially empty. We may think of irrelevant agents as temporarily
deleted from the market.

Iteration. Next, algorithm HM-Improve iteratively modifies the sub-allocation
$Y$ and the set $R$ of irrelevant agents. It will maintain the property that
$Y$ is a sub-allocation in $\widetilde{H}-R$; we denote its envy graph by
$\widetilde{G}_{Y\prec}$, having vertex set $\widetilde{N}\setminus R$. While
the source set of $Y$ changes quite freely during the iteration, the sink set
always remains a subset of $\widetilde{Q}$.

At each iteration, HM-Improve performs the following steps:

  1. Step 1.

Let $U$ be the source set of $Y$, and $V$ its sink set. If $U=V$, then the
iteration stops.

  2. Step 2.

Otherwise, if there exists a $Y$-augmenting arc $(s,u)$ in
$\widetilde{G}_{Y\prec}$ entering some source vertex ${u\in U}$ (note that
$s\in\widetilde{N}\setminus R$), then proceed as follows.

     * (a)

If $s\notin V$, then let $u^{\prime}=Y(s)$. The algorithm modifies $Y$ by
deleting the arc $(s,u^{\prime})$ and adding the arc $(s,u)$ to $Y$. Note that
$Y$ thus becomes a sub-allocation from $U\setminus\\{u\\}\cup\\{u^{\prime}\\}$
to $V$ in $\widetilde{H}-R$.

     * (b)

If $s\in V$, then simply add the arc $(s,u)$ to $Y$. In this case $Y$ becomes
a sub-allocation from $U\setminus\\{u\\}$ to $V\setminus\\{s\\}$ in
$\widetilde{H}-R$.

  3. Step 3.

Otherwise, let $u$ be any vertex in $U$ (not entered by any arc in
$\widetilde{G}_{Y\prec}$), and let $u^{\prime}=Y(u)$. The algorithm adds $u$
to the set $R$ of irrelevant agents, and modifies $Y$ by deleting the arc
$(u,u^{\prime})$. Again, $Y$ becomes a sub-allocation from
$U\setminus\\{u\\}\cup\\{u^{\prime}\\}$ to $V$ in $\widetilde{H}-R$.

Figure 3: Illustration of the possible steps performed during the iteration by
HM-Improve. The edges of the current sub-allocation $Y$ are depicted using
bold, green lines, while edges of the envy graph are shown by dashed, red
lines. Source and sink vertices of $Y$ are depicted with a white black
diamond, respectively. Vertices of $R$ as well as all edges incident to them
are shown in grey.

Output. Let $Y$ be the sub-allocation at the end of the above iteration, $U=V$
its source _and_ sink set, and $R$ the set of irrelevant agents. Note that
$\widetilde{Q}\setminus R\setminus U$ may contain at most one agent. Indeed,
if $\widetilde{q}\in\widetilde{Q}\setminus R\setminus U$, then $Y$ must
contain the uniqe arc leaving $\widetilde{q}$, namely $(\widetilde{q},p)$;
therefore, by $\delta^{-}_{Y}(p)\leq 1$, at most one such agent
$\widetilde{q}$ can exist.

To construct the desired allocation $X^{\prime}$, the algorithm first applies
the variant of the TTC algorithm described in Section 3.1 to the submarket
$H^{\prime}_{R\cap N}$ of $H^{\prime}$ when restricted to the set of
irrelevant agents. Let $X_{R}$ denote the obtained allocation in the core of
$H^{\prime}_{R\cap N}$.

HM-Improve next deletes all agents in $\widetilde{Q}$. As any agent in
$\widetilde{Q}\cap U=\widetilde{Q}\cap V=V$ has zero in- and outdegree in $Y$,
there is no need to modify our sub-allocation when deleting such agents; the
same applies to agents in $\widetilde{Q}\cap R$. By conrast, if there exists
an agent $\widetilde{q}\in\widetilde{Q}\setminus R\setminus U$, then $Y$ must
contain the unique incoming and outgoing arcs of $\widetilde{q}$, and
therefore the algorithm replaces the arcs $(q,\widetilde{q})$ and
$(\widetilde{q},p)$ with the arc $(q,p)$. This way we obtain an allocation on
the submarket of $H^{\prime}$ on agents set $N\setminus R$.

Finally, HM-Improve outputs an allocation $X^{\prime}$ defined as

$X^{\prime}=\left\\{\begin{array}[]{ll}X_{R}\cup Y&\textrm{ if
$\widetilde{Q}\setminus R\setminus U=\emptyset$,}\\\ X_{R}\cup
Y\setminus\\{(q,\widetilde{q}),(\widetilde{q},p)\\}\cup\\{(q,p)\\}&\textrm{ if
$\widetilde{Q}\setminus R\setminus U=\\{\widetilde{q}\\}$.}\end{array}\right.$

Algorithm 1 Algorithm HM-Improve

Input: housing market $H=(N,\prec)$, its $p$-improvement
$H^{\prime}=(N,\prec^{\prime})$ for some
Input: agent $p$, and an allocation $X$ in the core of $H$.
Output: an allocation $X^{\prime}$ in the core of $H^{\prime}$ s.t.
$X(p)\prec_{p}X^{\prime}(p)$ or $X(p)=X^{\prime}(p)$.

1:if $X$ is in the core of $H^{\prime}$ then return $X$

2:Set $Q=\\{a\in N:\prec_{a}\not=\prec^{\prime}_{a}$ and
$X(a)\prec^{\prime}_{a}p\\}$.

3:Initialize housing market $\widetilde{H}\vcentcolon=H$.

4:for all $q\in Q$ do

5: Add new agent $\widetilde{q}$ to $\widetilde{H}$, preferring only $p$ to
her own house.

6: Replace $p$ with $\widetilde{q}$ in the preferences of $q$ in
$\widetilde{H}$.

7:Set $\widetilde{Q}=\\{\widetilde{q}:q\in Q\\}$. $\triangleright$
$\widetilde{H}$ is now defined.

8:Create sub-allocation $Y\vcentcolon=X\setminus\\{(q,X(q)):q\in
Q\\}\cup\\{(q,\widetilde{q}):q\in Q\\}$.

9:Set $U$ and $V$ as the source and sink set of $Y$, resp., and set
$R\vcentcolon=\emptyset$.

10:while $U\neq V$ do

11: if there exists an arc $(s,u)$ in the envy graph $\widetilde{G}_{Y\prec}$
with $u\in U$ then

12: if $s\notin V$ then

13: Set $u^{\prime}\vcentcolon=Y(s)$, and update $Y\leftarrow
Y\setminus\\{(s,u^{\prime})\\}\cup\\{(s,u)\\}$ and $U\leftarrow
U\setminus\\{u\\}\cup\\{u^{\prime}\\}$.

14: else$\triangleright$ Case $s\in V$.

15: Update $Y\leftarrow Y\cup\\{(s,u)\\}$, $U\leftarrow U\setminus\\{u\\}$ and
$V\leftarrow V\setminus\\{s\\}$.

16: else$\triangleright$ No arc enters $U$ in the envy graph
$\widetilde{G}_{Y\prec}$.

17: Pick any agent $u\in U$, and set $u^{\prime}\vcentcolon=Y(u)$.

18: Update $Y\leftarrow Y\setminus(u,u^{\prime})$, $U\leftarrow
U\setminus\\{u\\}\cup\\{u^{\prime}\\}$ and $R\leftarrow R\cup\\{u\\}$.

19:Compute a core allocation $X_{R}$ in the submarket $H^{\prime}_{R\cap N}$.

20:if $\widetilde{Q}\setminus R\setminus U=\emptyset$ then set
$X^{\prime}\vcentcolon=X_{R}\cup Y$.

21:else set $X^{\prime}\vcentcolon=X_{R}\cup
Y\setminus\\{(q,\widetilde{q}),(\widetilde{q},p)\\}\cup\\{(q,p)\\}$ where
$\widetilde{Q}\setminus R\setminus U=\\{\widetilde{q}\\}$.

22:return the allocation $X^{\prime}$.

###  4.2 Correctness of algorithm HM-Improve

We begin proving the correctness of algorithm HM-Improve with the following.

######  Lemma 1.

At each iteration, sub-allocation $Y$ is stable in $\widetilde{H}-R$.

###### Proof.

The proof is by induction on the number $n$ of iterations performed. For
$n=0$, suppose for the sake of contradiction that $C$ is a cycle in
$\widetilde{G}_{Y\prec}$. First note that $C$ cannot contain any agent in
$\widetilde{Q}$, since the unique arc entering $\widetilde{q}$, that is, the
arc $(q,\widetilde{q})$, is contained in $Y$ by definition. Hence, $C$ is also
a cycle in $H$. Moreover, recall that initially $Y(a)=X(a)$ for each agent
$a\in N\setminus Q$, and by the definition of $Q$, we also know
$X(q)\prec_{q}\widetilde{q}=Y(q)$ for each $q\in Q$. Therefore, any arc of $C$
is an envy arc for $X$ as well, and thus $C$ is a blocking cycle for $X$ in
$H$. This contradicts our assumption that $X$ is in the core of $H$. Hence,
$Y$ is stable in $\widetilde{H}$ at the beginning; note that $R=\emptyset$
initially.

For $n\geq 1$, assume that the algorithm has performed $n-1$ iterations so
far. Let $Y$ and $R$ be as defined at the beginning of the $n$-th iteration,
and let $Y^{\prime}$ and $R^{\prime}$ be the sub-allocation and the set of
irrelevant agents obtained after the modifications in this iteration. Let also
$U$ and $V$ ($U^{\prime}$ and $V^{\prime}$) denote the source and sink set of
$Y$ (of $Y^{\prime}$, respectively). By induction, we may assume that $Y$ is
stable in $\widetilde{H}-R$, so $\widetilde{G}_{Y\prec}$ is acyclic. In case
HM-Improve does not stop in Step 1 but modifies $Y$ and possibly $R$, we
distinguish between three cases:

  * (a)

The algorithm modifies $Y$ in Step 2(a), by using a $Y$-augmenting arc $(s,u)$
where $s\notin V$; then $R^{\prime}=R$. Note that $s\in$ prefers $Y^{\prime}$
to $Y$, and for any other agent $a\in N\setminus R^{\prime}$ we know
$Y(a)=Y^{\prime}(a)$. Hence, this modification amounts to deleting all arcs
$(s,a)$ from the envy graph $\widetilde{G}_{Y\prec}$ where
$Y(s)\prec_{s}a\preceq_{s}Y^{\prime}(s)$.

  * (b)

The algorithm modifies $Y$ in Step 2(b), by using a $Y$-augmenting arc $(s,u)$
where $s\in V$; then $R^{\prime}=R$. First observe that
$V\subseteq\widetilde{Q}$, as the only way the sink set of $Y$ can change is
when an agent ceases to be a sink of the current sub-allocation due to the
application of Step 2(b). Thus, $s\in V$ implies $s\in\widetilde{Q}$, which
means that $(s,u)$ must be the unique arc $(s,p)$ leaving $s$. Hence, adding
$(s,u)$ to $Y$ amounts to deleting the arc $(s,u)$ from the envy graph
$\widetilde{G}_{Y\prec}$.

  * (c)

The algorithm modifies $Y$ in Step 3, by adding an agent $u\in U$ to the set
of irrelevant agents, i.e., $R^{\prime}=R\cup\\{u\\}$. Then
$Y^{\prime}(a)=Y(a)$ for each agent $a\in N\setminus R^{\prime}$, so the envy
graph $\widetilde{G}_{Y^{\prime}\prec}$ is obtained from
$\widetilde{G}_{Y\prec}$ by deleting $u$.

Since deleting some arcs or a vertex from an acyclic graph results in an
acyclic graph, the stability of $Y^{\prime}$ is clear.

We proceed with the observation that an agent’s situation in $Y$ may only
improve, unless it becomes irrelevant: this is a consequence of the fact that
the algorithm only deletes arcs and agents from the envy graph
$\widetilde{G}_{Y\prec}$.

######  Proposition 3.

Let $Y_{1}$ and $Y_{2}$ be two sub-allocations computed by algorithm HM-
Improve, with $Y_{1}$ computed at an earlier step than $Y_{2}$, and let $a$ be
an agent that is not irrelevant at the end of the iteration when $Y_{2}$ is
computed. Then either $Y_{1}(a)=Y_{2}(a)$ or $a$ prefers $Y_{2}$ to $Y_{1}$.

In the next two lemmas, we prove that HM-Improve produces a core allocation.
We start by explaining why irrelevant agents may not become the cause of
instability in the housing market.

######  Lemma 2.

At the end of algorithm HM-Improve, there does not exist an arc
$(a,b)\in\widetilde{E}$ such that $a\notin R$, $b\in R$ and
$Y(a)\prec^{\prime}_{a}b$.

###### Proof.

Suppose for contradiction that $(a,b)$ is such an arc, and let $Y$ and $R$ be
as defined at the end of the last iteration. Suppose that HM-Improve adds $b$
to $R$ during the $n$-th iteration, and let $Y_{n}$ be the sub-allocation at
the beginning of the $n$-th iteration. By Proposition 3, either
$Y_{n}(a)=Y(a)$ or $Y_{n}(a)\prec^{\prime}_{a}Y(a)$. The assumption
$Y(a)\prec^{\prime}_{a}b$ yields $Y_{n}(a)\prec^{\prime}_{a}b$ by the
transitivity of $\prec^{\prime}_{a}$. Thus, $(a,b)$ is a $Y_{n}$-augmenting
arc entering $b$, contradicting our assumption that the algorithm put $b$ into
$R$ in Step 3 of the $n$-th iteration.

######  Lemma 3.

The output of HM-Improve is an allocation in the core of $H^{\prime}$.

###### Proof.

Let $Y$ and $R$ be the sub-allocation and the set of irrelevant agents,
respectively, at the end of algorithm HM-Improve, and let $U$ be the source
set of $Y$. To begin, we prove it formally that the output $X^{\prime}$ of HM-
Improve is an allocation for $H^{\prime}$.

Since HM-Improve stops only when $U=V$, the arc set $Y$ forms a collection of
mutually vertex-disjoint cycles in $\widetilde{H}-R$ that covers each agent in
$\widetilde{N}\setminus R\setminus U$; agents of $U$ have neither incoming nor
outgoing arcs in $Y$. As no agent outside $\widetilde{Q}$ can become a sink of
$Y$, we know $U=V\subseteq\widetilde{Q}$.

First, assume $\widetilde{Q}\setminus R\setminus U=\emptyset$, that is,
$\widetilde{Q}\setminus R=U=V$. In this case, $Y$ is the union of cycles
covering each agent in $N\setminus R$ exactly once. Hence, $Y$ is an
allocation in the submarket of $H^{\prime}$ restricted to agent set
$N\setminus R$, i.e., $H^{\prime}_{N\setminus R}$.

Second, assume $\widetilde{Q}\setminus R\setminus U\neq\emptyset$. In this
case, $Y$ is the union of cycles covering each agent in
$\widetilde{N}\setminus R\setminus V$ exactly once. Let $\widetilde{q}$ be an
agent in $\widetilde{Q}\setminus R\setminus V$. As $\widetilde{q}$ is not a
sink of $Y$, is not irrelevant, and has a unique outgoing arc to $p$, we know
$(\widetilde{q},p)\in Y$. As $Y$ cannot contain two arcs entering $p$, this
proves that $\widetilde{Q}\setminus R\setminus V=\widetilde{Q}\setminus
R\setminus U=\\{\widetilde{q}\\}$. Moreover, since the unique arc entering
$\widetilde{q}$ is from $q$, we get $(q,\widetilde{q})\in Y$. Therefore, the
arc set $Y\setminus\\{(q,\widetilde{q}),(\widetilde{q},p)\\}\cup\\{(q,p)\\}$
is an allocation in $H^{\prime}_{N\setminus R}$.

Consequently, as $X_{R}$ is an allocation on $H^{\prime}_{R\cap N}$, we obtain
that $X^{\prime}$ is indeed an allocation in $H^{\prime}$ in both cases.

Let us now prove that $X^{\prime}$ is in the core of $H^{\prime}$; we do this
by showing that the envy graph $G^{H^{\prime}}_{X^{\prime}\prec}$ of
$X^{\prime}$ is acyclic. First, the subgraph
$G^{H^{\prime}}_{X^{\prime}\prec}[R]$ is exactly the envy graph of $X_{R}$ in
$H^{\prime}_{R\cap N}$ and hence is acyclic.

######  Claim 1 (Claim.).

Let $a\in N\setminus R$ and let $(a,b)$ be an $X^{\prime}$-augmenting arc in
$H^{\prime}$. Then $(a,b)$ is $Y$-augmenting as well, i.e.,
$Y(a)\prec^{\prime}_{a}b$.

###### of Claim.

Suppose first that $(a,b)\notin\\{(q,p):q\in Q\\}$: then $(a,b)$ is an arc in
$G^{\widetilde{H}}$. If $a\notin Q$ or $Y(a)\notin\widetilde{Q}$, then
$Y(a)=X^{\prime}(a)$ and thus the claim follows immediately. If $a\in Q$ and
$Y(a)=\widetilde{a}\in\widetilde{Q}$, then
$X^{\prime}(a)=p\prec^{\prime}_{a}b$ implies that $a$ prefers $b$ to
$Y(a)=\widetilde{a}$ in $\widetilde{H}$ as well, that is, $(a,b)$ is
$Y$-augmenting.

Suppose now that $(a,b)=(q,p)$ for some $q\in Q$. We finish the proof of the
claim by showing that $(q,p)$ is not $X^{\prime}$-augmenting if $q\notin R$
(recall that we assumed $q=a\notin R$).

First, if $\widetilde{q}\notin U$, then necessarily
$\\{(q,\widetilde{q}),(\widetilde{q},p)\\}\subseteq Y$, and so $(q,p)\in
X^{\prime}$, which means that $(q,p)$ is not $X^{\prime}$-augmenting.

Second, if $\widetilde{q}\in U$, then consider the iteration in which
$\widetilde{q}$ became a source for our sub-allocation, and let $Y_{n}$ denote
the sub-allocation at the end of this iteration. Agent $\widetilde{q}$ can
become a source either in Step 2(a) or in Step 3, since Step 2(b) always
results in one agent being deleted from the source set without a replacement.
Recall that the only arc entering $\widetilde{q}$ is $(q,\widetilde{q})$. If
$\widetilde{q}$ became the source of $Y_{n}$ in Step 2(a), then we know
$\widetilde{q}\prec^{\prime}_{q}Y_{n}(q)$. By Proposition 3, this implies
$\widetilde{q}\prec^{\prime}_{q}Y(q)$. By the construction of $\widetilde{H}$,
we obtain that $q$ prefers $Y(q)=X^{\prime}(q)$ to $p$ in $H^{\prime}$, so
$(q,p)$ is not $X^{\prime}$-augmenting. Finally, if agent $\widetilde{q}$
became the source of $Y_{n}$ in Step 3, then this implies $q\in R$, which
contradicts our assumption $a=q\notin R$.
a $\blacksquare$

Our claim implies that $G^{H^{\prime}}_{X^{\prime}\prec}[N\setminus R]$ is a
subgraph of $\widetilde{G}_{Y\prec}$ and therefore it is acyclic by Lemma 1.
Hence, any cycle in $G^{H^{\prime}}_{X^{\prime}\prec}$ must contain agents
both in $R$ and in $N\setminus R$ (recall that
$G^{H^{\prime}}_{X^{\prime}\prec}[R]$ is acyclic as well). However,
$G^{H^{\prime}}_{X^{\prime}\prec}$ contains no arcs from $N\setminus R$ to
$R$, since such arcs cannot be $Y$-augmenting by Lemma 2. Thus
$G^{H^{\prime}}_{X^{\prime}\prec}$ is acyclic and $X^{\prime}$ is in the core
of $H^{\prime}$.

The following lemma, the last one necessary to prove Theorem 4.1, shows that
HM-Improve runs in linear time; the proof relies on the fact that in each
iteration but the last either an agent or an arc is deleted from the envy
graph, thus limiting the number of iterations by $|E|+|N|$.

######  Lemma 4.

Algorithm HM-Improve runs in $O(|H|)$ time.

###### Proof.

Observe that the initialization takes $O(|E|+|N|)=O(|E|)$ time; note that $E$
contains every loop $(a,a)$ where $a\in N$, so we have $|E|\geq|N|$. We can
maintain the envy graph $\widetilde{G}_{Y\prec}$ in a way that deleting an arc
from it when it ceases to be $Y$-augmenting can be done in $O(1)$ time, and
detecting whether a given agent is entered by a $Y$-augmenting arc also takes
$O(1)$ time. Observe that there can be at most $|E|+|N|$ iterations, since at
each step but the last, either an agent or an arc is deleted from the envy
graph. Thus, the whole iteration takes $O(|E|)$ time. Finally, the allocation
$X_{R}$ for irrelevant agents by the variant of TTC described in Section 3.1
can be computed in $O(|H|)$ time. Hence, the overall running time of our
algorithm is $O(|H|)+O(|E|)=O(|H|)$.

We are now ready to prove Theorem 4.1.

###### of Theorem 4.1.

Lemma 4 shows that algorithm HM-Improve runs in linear time, and by Lemma 3
its output is an allocation $X^{\prime}$ in the core of $H^{\prime}$. It
remains to prove that either $X^{\prime}(p)=X(p)$ or $p$ prefers $X^{\prime}$
to $X$. Observe that it suffices to show $p\notin R$, by Proposition 3.

For the sake of contradiction, assume that HM-Improve puts $p$ into the set of
irrelevant vertices at some point, during an execution of Step 3. Let $Y$
denote the sub-allocation at the beginning of this step, and let $V$ be its
sink set. Clearly, $V\not=\emptyset$ (as in that case the source and the sink
set of $Y$ would coincide). Recall also that $V\subseteq\widetilde{Q}$. Thus,
there exists some $\widetilde{q}\in V\subseteq\widetilde{Q}$. However, then
$(\widetilde{q},p)$ is an $Y$-augmenting arc by definition, entering $p$,
which contradicts our assumption that the algorithm put $p$ into the set of
irrelevant agents in Step 3 of this iteration.

###  4.3 Strict improvement

Looking at Theorem 4.1 and Corollary 1, one may wonder whether it is possible
to detect efficiently when a $p$-improvement leads to a situation that is
strictly better for $p$. For a solution concept $\Phi$ and housing markets $H$
and $H^{\prime}$ such that $H^{\prime}$ is a $p$-improvement of $H$ for some
agent $p$, one may ask the following questions:

  1. 1.

Possible Strict Improvement for Best House or PSIB:
is it true that $a\prec_{p}a^{\prime}$ for some $a\in\Phi(H)^{+}_{p}$ and
$a^{\prime}\in\Phi(H^{\prime})^{+}_{p}$?

  2. 2.

Necessary Strict Improvement for Best House or NSIB:
is it true that $a\prec_{p}a^{\prime}$ for every $a\in\Phi(H)^{+}_{p}$ and
$a^{\prime}\in\Phi(H^{\prime})^{+}_{p}$?

  3. 3.

Possible Strict Improvement for Worst House or PSIW:
is it true that $a\prec_{p}a^{\prime}$ for some $a\in\Phi(H)^{-}_{p}$ and
$a^{\prime}\in\Phi(H^{\prime})^{-}_{p}$?

  4. 4.

Necessary Strict Improvement for Worst House or NSIW:
is it true that $a\prec_{p}a^{\prime}$ for every $a\in\Phi(H)^{-}_{p}$ and
$a^{\prime}\in\Phi(H^{\prime})^{-}_{p}$?

Focusing on the core of housing markets, it turns out that all of the above
four problems are computationally intractable, even in the case of strict
preferences.

######  Theorem 4.2.

With respect to the core of housing markets, PSIB and NSIB are
$\mathsf{NP}$-hard, while PSIW and NSIW are $\mathsf{coNP}$-hard, even if
agents’ preferences are strict orders.

###### Proof.

Since agents’ preferences are strict orders, we get that PSIB and NSIB are
equivalent, and similarly, PSIW and NSIW are equivalent as well, since there
is a unique best and a unique worst house that an agent may obtain in a core
allocation. Therefore, we are going to present two reductions, one for PSIB
and NSIB, and one for PSIW and NSIW. Since both reductions will be based on
those presented in the proof of Theorem 3.1, we are going to re-use the
notation defined there.

The reduction for PSIB (and NSIB) is obtained by slightly modifying the
reduction from Acyclic Partition to Arc in Core which, given a directed graph
$D$ constructs the housing market $H$. We define a housing market
$\widehat{H}$ by simply deleting the arc $(b^{\star},a^{\star})$ from the
acceptability graph of $H$. Then $H$ is an $a^{\star}$-improvement of
$\widehat{H}$. Clearly, as the house of $a^{\star}$ is not acceptable to any
other agent in $\widehat{H}$, the best house that $a^{\star}$ can obtain in
any allocation in the core of $\widehat{H}$ is her own. Moreover, the best
house that $a^{\star}$ can obtain in any allocation in the core of $H$ is
either the house of $b^{\star}$ or her own. This immediately implies that
$(\widehat{H},H)$ is a yes-instance of PSIB (and of NSIB) with respect to the
core if and only if there exists an allocation in the core of $H$ that
contains the arc $(a^{\star},b^{\star})$. Therefore, $(\widehat{H},H)$ is a
yes-instance of PSIB and of NSIB with respect to the core if and only if $D$
is a yes-instance of Acyclic Partition, finishing our proof for PSIB (and
NSIB).

The reduction for PSIW (and NSIW) is obtained analogously, by slightly
modifying the reduction from Acyclic Partition to Forbidden Arc in Core which,
given a directed graph $D$ constructs the housing market $H^{\prime}$. We
define a housing market $\widehat{H}^{\prime}$ by deleting the arc
$(a^{\star},s^{\star})$ from the acceptability graph of $H^{\prime}$. Then
$H^{\prime}$ is an $s^{\star}$-improvement of $\widehat{H}^{\prime}$. Clearly,
as the house of $s^{\star}$ is not acceptable to any other agent in
$\widehat{H}^{\prime}$, the worst house that $s^{\star}$ can obtain in any
allocation in the core of $\widehat{H}^{\prime}$ is her own. Moreover, the
worst house that $s^{\star}$ can obtain in any allocation in the core of
$H^{\prime}$ is either the house of $a^{\star}$ or her own. Therefore,
$(\widehat{H}^{\prime},H^{\prime})$ is a no-instance of PSIW (and of NSIW)
with respect to the core if and only if there exists an allocation in the core
of $H^{\prime}$ where $s^{\star}$ is not trading, i.e., that does not contain
the arc $(a^{\star},s^{\star})$. So $(\widehat{H}^{\prime},H^{\prime})$ is a
no-instance of PSIW and of NSIW with respect to the core if and only if $D$ is
a yes-instance of Acyclic Partition, finishing our proof for PSIW (and NSIW).

##  5 The effect of improvements in Stable Roommates

In the Stable Roommates problem we are given a set $N$ of agents, and a
preference relation $\prec_{a}$ over $N$ for each agent $a\in N$; the task is
to find a stable matching $M$ between the agents. A matching is _stable_ if it
admits no _blocking pair_ , that is, a pair of agents such that each of them
is either unmatched, or prefers the other over her partner in the matching.
Notice that an input instance for Stable Roommates is in fact a housing
market. Viewed from this perspective, a stable matching in a housing market
can be thought of as an allocation that (i) contains only cycles of length at
most 2, and (ii) does not admit a blocking cycle of length at most 2.

For an instance of Stable Roommates, we assume mutual acceptability, that is,
for any two agents $a$ and $b$, we assume that $a\prec_{a}b$ holds if and only
if $b\prec_{b}a$ holds. Consequently, it will be more convenient to define the
acceptability graph $G^{H}$ of an instance $H$ of Stable Roommates as an
undirected simple graph where agents $a$ and $b$ are connected by an edge
$\\{a,b\\}$ if and only if they are acceptable to each other and $a\neq b$. A
_matching_ in $H$ is then a set of edges in $G^{H}$ such that no two of them
share an endpoint.

Biró et al. [9] have shown the following statements, illustrated in Examples 1
and 2.

######  Proposition 4 ([9]).

Stable matchings in the Stable Roommates model

  * •

violate the RI-worst property (even if agents’ preferences are strict), and

  * •

violate the RI-best property, if agents’ preferences may include ties.

######  Example 1.

Let $N=\\{a,b,c,d,e,p,q\\}$ be the set of agents. The preferences indicated in
Figure 4 define two housing markets $H$ and $H^{\prime}$ such that
$H^{\prime}$ is a $(p,q)$-improvement of $H$. Note that agent $d$ is
indifferent between her two possible partners. Looking at $H$ and $H^{\prime}$
in the context of Stable Roommates, it is easy to see that the best partner
that $p$ might obtain in a stable matching for $H$ is her second choice $b$,
while in $H^{\prime}$ the only stable matching assigns $a$ to $p$, which is
her third choice.

Figure 4: The housing markets $H$ and $H^{\prime}$ as instances of Stable
Roommates with ties, in the Example 1. For both $H$ and $H^{\prime}$, the
matching represented by bold arcs yields the best possible partner for $p$ in
any stable matching of the given market.

######  Example 2.

Let $N=\\{a,b,p,q\\}$ be the set of agents. The preferences indicated in
Figure 5 define two housing markets $H$ and $H^{\prime}$ such that
$H^{\prime}$ is a $(p,q)$-improvement of $H$. The worst partner that $p$ might
obtain in a stable matching for $H$ is her top choice $a$, while in
$H^{\prime}$ there exists a stable matching that assigns $b$ to $p$, which is
her second choice.

Figure 5: The housing markets $H$ and $H^{\prime}$ in Example 2. For both $H$
and $H^{\prime}$, the matching represented by bold arcs yields the worst
possible partner for $p$ in any stable matching of the given market.

Complementing Proposition 4, we show that a $(p,q)$-improvement can lead to an
instance where no stable matching exists at all. This may happen even if
preferences are strict orders; hence, stable matchings do not strongly satisfy
the RI-best property.

######  Proposition 5.

Stable matchings in the Stable Roommates model do not strongly satisfy the RI-
best property, even if agents’ preferences are strict.

###### Proof.

Let $N=\\{a,b,p,q\\}$ be the set of agents. The preferences indicated in
Figure 6 define housing markets $H$ and $H^{\prime}$ where $H^{\prime}$ is an
$(p,q)$-improvement of $H$. The best partner that $p$ might obtain in a stable
matching for $H$ is her second choice $a$, while $H^{\prime}$ does not admit
any stable matchings at all.

Figure 6: Housing markets $H$ and $H^{\prime}$ illustrating the proof of
Proposition 5. For $H$, the bold arcs represent a stable matching, while the
instance $H^{\prime}$, which is a $(p,q)$-improvement of $H$, does not admit
any stable matchings.

Contrasting Propositions 4 and 5, it is somewhat surprising that if agents’
preferences are strict, then the RI-best property holds for the Stable
Roommates setting. Thus, the situation of $p$ cannot deteriorate as a
consequence of a $p$-improvement unless instability arises.

######  Theorem 5.1.

Let $H=(N,\\{\prec_{a}\\}_{a\in N})$ be a housing market where agents’
preferences are strict orders. Given a stable matching $M$ in $H$ and a
$(p,q)$-improvement $H^{\prime}$ of $H$ for two agents $p,q\in N$, either
$H^{\prime}$ admits no stable matchings at all, or there exists a stable
matching $M^{\prime}$ in $H^{\prime}$ such that
$M(p)\preceq_{i}M^{\prime}(p)$. Moreover, given $H$, $H^{\prime}$ and $M$ it
is possible to find such a matching $M^{\prime}$ in polynomial time.

######  Corollary 2.

Stable matchings in the Stable Roommates model satisfy the RI-best property.

We describe our algorithm for Theorem 5.1 in Section 5.1, and prove its
correctness in Section 5.2.

###  5.1 Description of algorithm SR-Improve

To prove Theorem 5.1 we are going to rely on the concept of proposal-rejection
alternating sequences introduced by Tan and Hsueh [42], originally used as a
tool for finding a stable partition in an incremental fashion by adding agents
one-by-one to a Stable Roommates instance. We somewhat tailor their definition
to fit our current purposes.

Let $\alpha_{0}\in N$ be an agent in a housing market $H$, and let $M_{0}$ be
a stable matching in $H-\alpha_{0}$. A sequence $S$ of agents
$\alpha_{0},\beta_{1},\alpha_{1},\dots,\beta_{k},\alpha_{k}$ is a _proposal-
rejection alternating sequence_ starting from $M_{0}$, if there exists a
sequence of matchings $M_{1},\dots,M_{k}$ such that for each
$i\in\\{1,\dots,k\\}$

  * (i)

$\beta_{i}$ is the agent most preferred by $\alpha_{i-1}$ among those who
prefer $\alpha_{i-1}$ to their partner in $M_{i-1}$ or are unmatched in
$M_{i-1}$,

  * (ii)

$\alpha_{i}=M_{i-1}(\beta_{i})$, and

  * (iii)

$M_{i}=M_{i-1}\setminus\\{\\{\alpha_{i},\beta_{i}\\}\\}\cup\\{\\{\alpha_{i-1},\beta_{i}\\}\\}$
is a matching in $H-\alpha_{i}$.

We say that the sequence $S$ _starts_ from $M_{0}$, and that the matchings
$M_{1},\dots,M_{k}$ are _induced_ by $S$. We say that $S$ _stops_ at
$\alpha_{k}$, if there does not exist an agent fulfilling condition (i) in the
above definition for $i=k+1$, that is, if no agent prefers $\alpha_{k}$ to her
current partner in $M_{k}$ and no unmatched agent in $M_{k}$ finds
$\alpha_{k}$ acceptable. We will also allow a proposal-rejection alternating
sequence to take the form $\alpha_{0},\beta_{1},\alpha_{1},\dots,\beta_{k}$,
in case conditions (i), (ii), and (iii) hold for each $i\in\\{1,\dots,k-1\\}$,
and $\beta_{k}$ is an unmatched agent in $M_{k-1}$ satisfying condition (i)
for $i=k$. In this case we define the last matching induced by the sequence as
$M_{k}=M_{k-1}\cup\\{\\{\alpha_{k-1},\beta_{k}\\}\\}$, and we say that the
sequence _stops_ at agent $\beta_{k}$.

We summarize the most important properties of proposal-rejection alternating
sequences in Lemma 5 as observed and used by Tan and Hsueh.333The first claim
of Lemma 5 is implicit in the paper by Tan and Hsueh [42], we prove it for the
sake of completeness.

######  Lemma 5 ([42]).

Let $\alpha_{0},\beta_{1},\alpha_{1},\dots,\beta_{k}(,\alpha_{k})$ be a
proposal-rejection alternating sequence starting from a stable matching
$M_{0}$ and inducing the matchings $M_{1},\dots,M_{k}$ in a housing market
$H$. Then the following hold.

  1. 1.

$M_{i}$ is a stable matching in $H-\alpha_{i}$ for each
$i\in\\{1,\dots,k-1(,k)\\}$.

  2. 2.

If $\beta_{j}=\alpha_{i}$ for some $i$ and $j$, then $H$ does not admit a
stable matching; in such a case we say that sequence $S$ _has a return_.

  3. 3.

If the sequence stops at $\alpha_{k}$ or $\beta_{k}$, then $M_{k}$ is a stable
matching in $H$.

  4. 4.

For any $i\in\\{1,\dots,k-1\\}$ agent $\alpha_{i}$ prefers
$M_{i-1}(\alpha_{i})$ to $M_{i+1}(\alpha_{i})$.

  5. 5.

For any $i\in\\{1,\dots,k-1\\}$ agent $\beta_{i}$ prefers $M_{i}(\beta_{i})$
to $M_{i-1}(\beta_{i})$.

###### of the first statement of Lemma 5.

We prove the statement by induction on $i$; the case $i=0$ is clear. Assume
that $i\geq 1$ and $M_{i-1}$ is stable in $H-\alpha_{i-1}$. Since
$M_{i}\triangle
M_{i-1}=\\{\\{\alpha_{i},\beta_{i}\\},\\{\alpha_{i-1},\beta_{i}\\}\\}$ we know
that any blocking pair for $M_{i}$ in $H-\alpha_{i}$ must contain either
$\beta_{i}$ or $\alpha_{i-1}$. By our choice of $\beta_{i}$, it is clear that
$\alpha_{i-1}$ cannot be contained in a blocking pair. Moreover, since
$\beta_{i}$ prefers $\alpha_{i-1}$ to $M_{i-1}(\beta_{i})=\alpha_{i}$, any
blocking pair for $M_{i}$ would also be blocking in $M_{i-1}$, a
contradiction.

We are now ready to describe algorithm SR-Improve; see Algorithm 2 for its
pseudocode.

#### Algorithm SR-Improve.

Let $H=(N,\\{\prec_{a}\\}_{a\in N})$ be a housing market containing a stable
matching $M$, and let $H^{\prime}=(N,\\{\prec^{\prime}_{a}\\}_{a\in N})$ be a
$(p,q)$-improvement of $H$ for two agents $p$ and $q$ in $N$; recall that
$\prec^{\prime}_{a}=\prec_{a}$ unless $a=q$. We now propose algorithm SR-
Improve that computes a stable matching $M^{\prime}$ in $H^{\prime}$ with
$M(p)\preceq_{p}M^{\prime}(p)$, whenever $H^{\prime}$ admits some stable
matching.

First, SR-Improve checks whether $M$ is stable in $H^{\prime}$, and if so,
returns the matching $M^{\prime}=M$. Otherwise, $\\{p,q\\}$ must be a blocking
pair for $M$ in $H^{\prime}$.

Second, the algorithm checks whether $H^{\prime}$ admits a stable matching,
and if so, computes _any_ stable matching $M^{\star}$ in $H^{\prime}$ using
Irving’s algorithm [26]; if no stable matching exists for $H^{\prime}$,
algorithm SR-Improve stops. Now, if $M(p)\preceq^{\prime}_{p}M^{\star}(p)$,
then SR-Improve returns $M^{\prime}=M^{\star}$, otherwise proceeds as follows.

Let $\widetilde{H}$ be the housing market obtained from $H^{\prime}$ by
deleting all agents in the set $\\{a\in N:a\preceq^{\prime}_{q}p\\}$ from the
preference list of $q$ (and vice versa, deleting $q$ from the preference list
of these agents). Notice that in particular this includes the deletion of $p$
as well as of $M(q)$ from the preference list of $q$ (recall that
$M(q)\prec^{\prime}_{q}p$).

Let us define $\alpha_{0}=M(q)$ and $M_{0}=M\setminus\\{q,\alpha_{0}\\}$.
Notice that $M_{0}$ is a stable matching in $\widetilde{H}-\alpha_{0}$:
clearly, any possible blocking pair must contain $q$, but any blocking pair
$\\{q,a\\}$ that is blocking in $\widetilde{H}$ would also block $H$ by
$M(q)\prec_{q}a$. Observe also that $q$ is unmatched in $M_{0}$.

Finally, algorithm SR-Improve builds a proposal-rejection alternating sequence
$S$ of agents $\alpha_{0},\beta_{1},\alpha_{1},\dots,\beta_{k}(,\alpha_{k})$
in $\widetilde{H}$ starting from $M_{0}$, and inducing matchings
$M_{1},\dots,M_{k}$ until one of the following cases occurs:

  * (a)

$\alpha_{k}=p$: in this case SR-Improve outputs
$M^{\prime}=M_{k}\cup\\{\\{p,q\\}\\}$;

  * (b)

$S$ stops: in this case SR-Improve outputs $M^{\prime}=M_{k}$.

Algorithm 2 Algorithm SR-Improve

Input: housing market $H=(N,\prec)$, its $(p,q)$-improvement
$H^{\prime}=(N,\prec^{\prime})$ for two
Input: agents $p$ and $q$, and a stable matching $M$ in $H$.
Output: a stable matching $M^{\prime}$ in $H^{\prime}$ such that
$M(p)\preceq_{p}M^{\prime}(p)$ or $M(p)=M^{\prime}(p)$,
Output: if $H^{\prime}$ admits some stable matching.

1:if $M$ is stable in $H^{\prime}$ then return $M$

2:if $H^{\prime}$ admits a stable matching then let $M^{\star}$ be any stable
matching in $H^{\prime}$.

3:$\triangleright$ Use Irving’s algorithm [26]

4:else return “No stable matching exists for $H^{\prime}$.”

5:if $M(p)\preceq_{p}M^{\star}(p)$ then return
$M^{\prime}\vcentcolon=M^{\star}$

6:Create housing market $\widetilde{H}$ by deleting the agents $\\{a\in
N:a\preceq^{\prime}_{q}p\\}$ from $A(q)$ and vice versa.

7:Set $i\vcentcolon=0$, $\alpha_{0}\vcentcolon=M(q)$, and
$M_{0}\vcentcolon=M\setminus\\{\alpha_{0},q\\}$

8:repeat$\triangleright$ Computing a proposal-rejection sequence $S$.

9: Set $i\leftarrow i+1$.

10: Set $B_{i}\vcentcolon=\\{b:\alpha_{i-1}\in A(b),b\textrm{ is unmatched in
}M_{i-1}\textrm{ or }M_{i-1}(b)\prec_{b}\alpha_{i-1}\\}$.

11: if $B_{i}=\emptyset$ then return $M^{\prime}\vcentcolon=M_{i-1}$
$\triangleright$ $S$ stops at $i-1$.

12: Set $\beta_{i}$ as the agent most preferred by $\alpha_{i-1}$ in $B_{i}$.

13: if $\beta_{i}$ is unmatched in $M_{i-1}$ then return
$M^{\prime}\vcentcolon=M_{i-1}\cup\\{\\{\alpha_{i-1},\beta_{i}\\}\\}$

14:$\triangleright$ $S$ stops at $i$.

15: Set $\alpha_{i}\vcentcolon=M_{i-1}(\beta_{i})$ and
$M_{i}\vcentcolon=M_{i-1}\cup\\{\\{\alpha_{i-1},\beta_{i}\\}\\}\setminus\\{\\{\alpha_{i},\beta_{i}\\}\\}$.

16:until $\alpha_{i}=p$ return
$M^{\prime}\vcentcolon=M_{i}\cup\\{\\{p,q\\}\\}$

###  5.2 Correctness of algorithm SR-Improve

To show that algorithm SR-Improve is correct, we first state the following two
lemmas.

######  Lemma 6.

The sequence $S$ cannot have a return. Furthermore, if $S$ stops, then it
stops at $\beta_{k}$ with $\beta_{k}=q$.

###### Proof.

Recall that $M^{\star}$ is a stable matching in $H^{\prime}$ with
$M^{\star}(p)\prec_{p}M(p)$. Since the pair $\\{p,q\\}$ is blocking for $M$ in
$H^{\prime}$, we know $M(p)\prec_{p}q$, yielding $M^{\star}(p)\prec_{p}q$. By
the stability of $M^{\star}$, this implies that $q$ is matched in $M^{\star}$
and $p\prec^{\prime}_{q}M^{\star}(q)$. As a consequence, $M^{\star}$ is a
stable matching not only in $H^{\prime}$ but also in $\widetilde{H}$, since
deleting agents less preferred by $q$ than $M^{\star}(q)$ from $q$’s
preference list cannot compromise the stability of $M^{\star}$.

By the second claim of Lemma 5, we know that if $S$ has a return, then
$\widetilde{H}$ admits no stable matching, contradicting the existence of
$M^{\star}$. Furthermore, since $q$ is matched in $M^{\star}$, it must be
matched in every stable matching of $\widetilde{H}$, by the well-known fact
that in an instance of Stable Roommates where agents’ preferences are strict
all stable matchings contain exactly the same set of agents [23, Theorem
4.5.2]. Now, if $S$ stops with the last induced matching $M_{k}$, then by the
third statement of Lemma 5 we get that $M_{k}$ is a stable matching in
$\widetilde{H}$, and thus $q$ must be matched in $M_{k}$. Clearly, as $q$ is
unmatched in $M_{0}$, this can only occur if $\beta_{k}=q$ and $S$ stops at
$q$.

######  Lemma 7.

If SR-Improve outputs a matching $M^{\prime}$, then $M^{\prime}$ is stable in
$H^{\prime}$ and $M(p)\preceq^{\prime}_{p}M^{\prime}(p)$.

###### Proof.

First, assume that the algorithm stops when $\alpha_{k}=p$. Then by the first
statement of Lemma 5, $M_{k}$ is stable in $\widetilde{H}-p$. Note also that
$q$ must be unmatched in $M_{k}$, as $q$ can only obtain a partner in the
sequence of matchings induced by $S$ if $q=\beta_{k}$, which cannot happen
when $\alpha_{k}=p$. So $M^{\prime}=M_{k}\cup\\{\\{p,q\\}\\}$ is indeed a
matching in $H^{\prime}$.

Let us prove that $M^{\prime}$ is stable in $H^{\prime}$. Since $q$ is
unmatched in $M_{k}$, and $M_{k}$ is stable in $\widetilde{H}-p$, no agent
acceptable for $q$ prefers $q$ to her partner in $M_{k}$ or is left unmatched
in $M_{q}$. Hence, $q$ cannot be contained in a blocking pair for
$M^{\prime}$. Thus, any blocking pair for $M^{\prime}$ must contain $p$.
Suppose that $\\{p,a\\}$ blocks $M^{\prime}$ in $H^{\prime}$; then
$q\prec^{\prime}_{p}a$. Since $S$ cannot have a return by Lemma 6, we know
that $p$ is not among the agents
$\alpha_{0},\beta_{1},\alpha_{1},\dots,\beta_{k-1}$. Therefore,
$M_{k-1}(p)=M_{0}(p)=M(p)$. Recall that $M(p)\prec^{\prime}_{p}q$, which
implies $M_{k-1}(p)\prec^{\prime}_{p}q$. Since $M_{k-1}(a)=M_{k}(a)$ (because
$a\notin\\{\alpha_{k-1},\beta_{k},p\\}$), we get that $\\{p,a\\}$ must also
block $M_{k-1}$ in $\widetilde{H}-\alpha_{k-1}$, a contradiction. This shows
that $M^{\prime}$ is stable in $H^{\prime}$. By
$M(p)\prec^{\prime}_{p}q=M^{\prime}(p)$, the lemma follows in this case.

Second, assume that SR-Improve outputs $M^{\prime}=M_{k}$ after finding that
the sequence $S$ stops with $q$ being matched in $M_{k}$. By the first
statement of Lemma 5, we know that $M^{\prime}$ is stable in $\widetilde{H}$,
and by the definition of $\widetilde{H}$, we know that
$p\prec_{q}M^{\prime}(q)$. Therefore, $M^{\prime}$ is also stable in
$H^{\prime}$ (as adding agents less preferred by $q$ than $M^{\prime}(q)$ to
$q$’s preference list cannot compromise the stability of $M^{\prime}$). To
show that $M(p)\preceq^{\prime}_{p}M^{\prime}(p)$, it suffices to observe that
$p=\alpha_{i}$ is not possible for any $i\in\\{1,\dots,k\\}$ (as in this case
$q$ would be unmatched, as argued in the first paragraph of this proof), and
hence by the fifth claim of Lemma 5 the partner that $p$ receives in the
matchings $M_{0},M_{1},\dots,M_{k}$ can only get better for $p$, and thus
$M(p)=M_{0}(p)\preceq^{\prime}_{p}M_{k}(p)=M^{\prime}(p)$.

We can now piece together the proof of Theorem 5.1.

###### of Theorem 5.1.

From the description of SR-Improve and Lemma 7 it is immediate that any output
the algorithm produces is correct. It remains to show that it does not fail to
produce an output. By Lemma 6 we know that the sequence $S$ built by the
algorithm cannot have a return and can only stop at $q$, implying that SR-
Improve will eventually produce an output. Considering the fifth statement of
Lemma 5, we also know that the length of $S$ is at most $2|E|$. Thus, the
algorithm finishes in $O(|E|)$ time.

###  5.3 A note on strongly stable matchings in Stable Roommates

Given an instance of Stable Roommates where preferences are not strict, strong
stability is an alternative notion of stability based on the notion of weakly
blocking pairs. Given a matching $M$ in a housing market
$H=(N,\\{\prec_{a}\\}_{a\in N})$, an edge $\\{a,b\\}$ in the acceptability
graph $G^{H}$ is _weakly blocking_ , if (i) $a$ is either unmatched or weakly
prefers $b$ to $M(a)$, and (ii) $b$ is either unmatched or weakly prefers $a$
to $M(b)$, and (iii) if $a$ and $b$ are both matched in $M$, then $a$ prefers
$b$ to $M(a)$, or $b$ prefers $a$ to $M(b)$. If there is no weakly blocking
pair for $M$, then $M$ is _strongly stable_.

Note that a strongly stable matching for $H$ can be thought of as an
allocation that (i) contains only cycles of length at most 2, and (ii) does
not admit a _weakly blocking_ cycle of length at most 2. Recall that stable
matchings correspond to the concept of core if we restrict allocations to
pairwise exchanges; analogously, strongly stable matchings correspond to the
concept of strict core for pairwise exchanges.

In view of Corollary 2, it is natural to ask whether the set of strongly
stable matchings satisfy the RI-best property in the case when preferences may
not be strict. The following statement answers this question in the negative.
Interestingly, the result holds even in the Stable Marriage model, the special
case of Stable Roommates where the acceptability graph is bipartite.

######  Proposition 6.

Strongly stable matchings in the the Stable Marriage model do not satisfy the
RI-best property.

Figure 7: The housing markets $H$ and $H^{\prime}$ in the proof of Proposition
6. For both $H$ and $H^{\prime}$, the allocation represented by bold arcs
yields the best possible strongly stable matchings.

###### Proof.

Consider the housing markets $H$ and $H^{\prime}$ depicted in Figure 7; note
that $H^{\prime}$ is a $(p,q)$-improvement of $H$. Note that the preferences
in $H$ are strict, but in $H^{\prime}$ agent $q$ is indifferent between $p$
and $b$.

First observe that the matching $M$ shown in bold in the first part of Figure
7 is stable in $H$, so it is possible for $p$ to be matched with its second
choice, namely $a$, in a (strongly) stable matching in $H$. We claim that the
best possible partner $p$ can obtain in any strongly stable matching in
$H^{\prime}$ is its third choice. To see this, first note that any matching
containing $\\{p,q\\}$ is weakly blocked by $\\{q,b\\}$ in $H$, so $p$ cannot
be matched to its first choice, agent $q$, in any strongly stable matching in
$H^{\prime}$. Second, note that any matching $M^{\prime}$ containing
$\\{p,a\\}$ must match $q$ to its first choice (otherwise the pair $\\{p,q\\}$
weakly blocks $M^{\prime}$) and hence $M^{\prime}$ must match $b$ to its third
choice (so as not to form a blocking pair with it); however, then $\\{a,b\\}$
is a blocking pair for $M^{\prime}$. Thus, $p$ cannot be matched in any
strongly stable matching of $H^{\prime}$ to its second choice, agent $a$,
either.

By contrast, it is easy to verify that the matching shown in bold in the
second part of Figure 7, matching $p$ to its third choice, is strongly stable
in $H^{\prime}$. This proves our proposition.

##  6 Further research

Even though the property of respecting improvement is important in exchange
markets, many solution concepts have not been studied from this aspect. A
solution concept that seems interesting from this point of view is the set of
stable half-matchings (or equivalently, stable partitions) in instances of
Stable Roommates without a stable matching. Although Figure 8 contains an
example about stable half-matchings where improvement of an agents’ house
damages her situation, perhaps a more careful investigation may shed light on
some interesting monotonicity properties.

Figure 8: An example where an agent’s improvement has a detrimental effect on
the agent’s situation in a model where allocations are defined as half-
matchings (see also [41]). Given a Stable Roommates instance with underlying
graph $(V,E)$, a _half-matching_ is a function
$f:E\rightarrow\\{0,\frac{1}{2},1\\}$ that satisfies $\sum_{e=\\{u,v\\}\in
E}f(e)\leq 1$ for each agent $v\in V$. The figure contains housing market $H$
and its $(p,q)$-improvement $H^{\prime}$, and a unique stable half-matching
for each market; see [33] for the definition of stable half-matchings. We
depict half-matchings in blue, with double lines for matched edges and single
bold lines for half-matched edges. For $H$, the half-matching $f$ depicted
leaves $p$ more satisfied than the half-matching $f^{\prime}$ depicted for
$H^{\prime}$.

## Acknowledgments.

Ildikó Schlotter is supported by the Hungarian Academy of Sciences under its
Momentum Programme (LP2021-2) and the Hungarian Scientific Research Fund
through OTKA grants no. K128611 and K124171. The research reported in this
paper and carried out by Tamás Fleiner at the Budapest University of
Technology and Economics was supported by the “TKP2020, National Challenges
Program” of the National Research Development and Innovation Office (BME NC
TKP2020 and OTKA K128611 and K143858) and by the Higher Education Excellence
Program of the Ministry of Human Capacities in the frame of the Artificial
Intelligence research area of the Budapest University of Technology and
Economics (BME FIKP-MI/SC). P. Biró gratefully acknowledges financial support
from the Hungarian Scientific Research Fund, OTKA, Grant No. K143858, and the
Hungarian Academy of Sciences, Momentum Grant No. LP2021-2.

## References

  * [1] A. Abdulkadiroǧlu and T. Sönmez.  House allocation with existing tenants.  J. Econ. Theory, 88(2):233–260, 1999.
  * [2] D. J. Abraham, A. Blum, and T. Sandholm.  Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges.  In EC ’07: Proc. of the 8th ACM Conference on Electronic Commerce, pages 295–304, 2007.
  * [3] D. J. Abraham, K. Cechlárová, D. F. Manlove, and K. Mehlhorn.  Pareto optimality in house allocation problems.  In ISAAC 2004, pages 3–15, Berlin, Heidelberg, 2004.
  * [4] J. Alcalde-Unzu and E. Molis.  Exchange of indivisible goods and indifferences: The Top Trading Absorbing Sets mechanisms.  Game. Econ. Behav., 73(1):1–16, 2011.
  * [5] H. Aziz and B. de Keijzer.  Housing markets with indifferences: A tale of two mechanisms.  In AAAI ’12, pages 1249–1255, 2012.
  * [6] M. Balinski and T. Sönmez.  A tale of two mechanisms: Student placement.  J. Econ. Theory, 84(1):73–94, 1999.
  * [7] P. Biró and K. Cechlárová.  Inapproximability of the kidney exchange problem.  Inform. Process. Lett., 101(5):199–202, 2007.
  * [8] P. Biró, B. Haase-Kromwijk, T. Andersson, E. I. Ásgeirsson, T. Baltesová, I. Boletis, et al.  Building kidney exchange programmes in Europe: an overview of exchange practice and activities.  Transplantation, 103(7):1514–1522, 2019.
  * [9] P. Biró, F. Klijn, X. Klimentova, and A. Viana.  Shapley-Scarf housing markets: Respecting improvement, integer programming, and kidney exchange.  CoRR, abs/2102.00167, 2021.  arXiv:2102.00167 [econ.TH].
  * [10] P. Biró, D. Manlove, and R. Rizzi.  Maximum weight cycle packing in directed graphs, with application to kidney exchange programs.  Discrete Math. Algorithms Appl., 1(4):499–517, 2009.
  * [11] P. Biró and E. McDermid.  Three-sided stable matchings with cyclic preferences.  Algorithmica, 58(1):5–18, 2010.
  * [12] P. Biró, J. van de Klundert, D. Manlove, and et al.  Modelling and optimisation in European Kidney Exchange Programmes.  Eur. J. Oper. Res., 291(2):447–456, 2021.
  * [13] F. Bloch and D. Cantala.  Markovian assignment rules.  Soc. Choice Welfare, 40:1–25, 2003.
  * [14] D. Bokal, G. Fijavz̆, M. Juvan, P. M. Kayll, and B. Mohar.  The circular chromatic number of a digraph.  J. Graph Theor., 46(3):227–240, 2004.
  * [15] K. Cechlárová, T. Fleiner, and D. F. Manlove.  The kidney exchange game.  In SOR ’05, pages 77–83, 2005.
  * [16] K. Cechlárová and J. Hajduková.  Computational complexity of stable partitions with b-preferences.  Int. J. Game Theory, 31(3):353–364, 2003.
  * [17] K. Cechlárová and V. Lacko.  The kidney exchange problem: How hard is it to find a donor?  Ann. Oper. Res., 193:255–271, 2012.
  * [18] K. Cechlárová and M. Repiský.  On the structure of the core of housing markets.  Technical report, P. J. Šafárik University, 2011.  IM Preprint, series A, No. 1/2011.
  * [19] K. Cechlárová and A. Romero-Medina.  Stability in coalition formation games.  Int. J. Game Theory, 29(4):487–494, 2001.
  * [20] Á. Cseh and D. F. Manlove.  Stable marriage and roommates problems with restricted edges: Complexity and approximability.  Discrete Optim., 20:62–89, 2016.
  * [21] V. Dias, G. da Fonseca, C. Figueiredo, and J. Szwarcfiter.  The stable marriage problem with restricted pairs.  Theor. Comput. Sci., 306:391–405, 01 2003.
  * [22] T. Fleiner, R. W. Irving, and D. F. Manlove.  Efficient algorithms for generalized stable marriage and roommates problems.  Theor. Comput. Sci., 381(1):162–176, 2007.
  * [23] D. Gusfield and R. W. Irving.  The Stable Marriage problem: Structure and Algorithms.  MIT press, 1989.
  * [24] J. W. Hatfield, F. Kojima, and Y. Narita.  Improving schools through school choice: A market design approach.  J. Econ. Theory, 166(C):186–211, 2016.
  * [25] C.-C. Huang.  Circular stable matching and 3-way kidney transplant.  Algorithmica, 58(1):137–150, 2010.
  * [26] R. W. Irving.  An efficient algorithm for the “stable roommates” problem.  J. Algorithms, 6(4):577–595, 1985.
  * [27] P. Jaramillo and V. Manjunath.  The difference indifference makes in strategy-proof allocation of objects.  J. Econ. Theory, 147(5):1913–1946, 2012.
  * [28] Y. Kamijo and R. Kawasaki.  Dynamics, stability, and foresight in the Shapley-Scarf housing market.  J. Math. Econ., 46(2):214–222, 2010.
  * [29] R. Kawasaki.  Roth–Postlewaite stability and von Neumann–Morgenstern stability.  J. Math. Econ., 58:1–6, 2015.
  * [30] B. Klaus and F. Klijn.  Minimal-access rights in school choice and the deferred acceptance mechanism.  Cahiers de Recherches Economiques du Département d’économie 21.11, Université de Lausanne, 2021.
  * [31] D. E. Knuth.  Mariages stables et leurs relations avec d’autres problèmes combinatoires.  Les Presses de l’Université de Montréal, Montreal, Que., 1976.
  * [32] M. Kurino.  House allocation with overlapping generations.  Am. Econ. J.-Microrecon., 6(1):258–289, 2014.
  * [33] D. F. Manlove.  Algorithmics of matching under preferences, volume 2 of Series on Theoretical Computer Science.  World Scientific, Singapore, 2013.
  * [34] C. G. Plaxton.  A simple family of Top Trading Cycles mechanisms for housing markets with indifferences.  In ICGT 2013, 2013.
  * [35] A. E. Roth and A. Postlewaite.  Weak versus strong domination in a market with indivisible goods.  J. Math. Econ., 4:131–137, 1977.
  * [36] A. E. Roth, T. Sönmez, and M. U. Ünver.  Kidney exchange.  Quarterly J. of Econ., 119:457–488, 2004.
  * [37] A. E. Roth, T. Sönmez, and M. U. Ünver.  Pairwise kidney exchange.  J. Econ. Theory, 125(2):151–188, 2005.
  * [38] D. Saban and J. Sethuraman.  House allocation with indifferences: A generalization and a unified view.  In EC ’13: Proc. of the 14th ACM Conference on Electronic Commerce, pages 803–820, 2013.
  * [39] L. Shapley and H. Scarf.  On cores and indivisibility.  J. Math. Econ., 1:23–37, 1974.
  * [40] T. Sönmez and T. Switzer.  Matching with (Branch-of-Choice) contracts at the United States Military Academy.  Econometrica, 81:451–488, 2013.
  * [41] J. J. M. Tan.  Stable matchings and stable partitions.  Int. J. Comput. Math., 39(1-2):11–20, 1991.
  * [42] J. J. M. Tan and Y.-C. Hsueh.  A generalization of the stable matching problem.  Discrete Appl. Math., 59(1):87–102, 1995.
  * [43] M. U. Ünver.  Dynamic kidney exchange.  Rev. Econ. Stud., 77(1):372–414, 2010.