capbtabboxtable[][]

# Shapley-Scarf Housing Markets: Respecting Improvement, Integer Programming,
and Kidney Exchange111This work is financed by COST Action CA15210 ENCKEP,
supported by COST (European Cooperation in Science and Technology) –
http://www.cost.eu/.

Péter Biró Centre for Economic and Regional Studies, and Corvinus University
of Budapest, 1097 Budapest, Tóth Kálmán utca 17, Hungary. P. Biró is supported
by the Hungarian Scientific Research Fund – OTKA (no. K129086). Flip Klijn
Institute for Economic Analysis (CSIC) and Barcelona GSE, Campus UAB, 08193
Bellaterra (Barcelona), Spain; e-mail<EMAIL_ADDRESS>F. Klijn
gratefully acknowledges financial support from AGAUR–Generalitat de Catalunya
(2017-SGR-1359) and the Spanish Ministry of Science and Innovation through
grant ECO2017-88130-P AEI/FEDER, UE and the Severo Ochoa Programme for Centres
of Excellence in R&D (CEX2019-000915-S). Xenia Klimentova INESC TEC, Porto,
Portugal. Ana Viana INESC TEC and ISEP – School of Engineering, Polytechnic of
Porto, Porto, Portugal.

(August 28, 2024)

###### Abstract

In a housing market of Shapley and Scarf [41], each agent is endowed with one
indivisible object and has preferences over all objects. An allocation of the
objects is in the (strong) core if there exists no (weakly) blocking
coalition. In this paper we show that in the case of strict preferences the
unique strong core allocation (or competitive allocation) “respects
improvement”: if an agent’s object becomes more attractive for some other
agents, then the agent’s allotment in the unique strong core allocation weakly
improves. We obtain a general result in case of ties in the preferences and
provide new integer programming formulations for computing (strong) core and
competitive allocations. Finally, we conduct computer simulations to compare
the game-theoretical solutions with maximum size and maximum weight exchanges
for markets that resemble the pools of kidney exchange programmes.

Keywords: housing market, respecting improvement, core, competitive
allocations, integer programming, kidney exchange programmes.

##  1 Introduction

Shapley and Scarf [41] introduced so-called “housing markets” to model trading
in commodities that are inherently indivisible. Specifically, in a housing
market each agent is endowed with an object (e.g., a house or a kidney donor)
and has ordinal preferences over all objects, including her own. The aim is to
find plausible or desirable allocations where each agent is assigned one
object. A standard approach in the literature is to discard allocations that
can be blocked by a coalition of agents. Specifically, a coalition of agents
blocks an allocation if they can trade their endowments so that each of the
agents in the coalition obtains a strictly preferred allotment. Similarly, a
coalition of agents weakly blocks an allocation if they can trade their
endowments so that each of the agents in the coalition obtains a weakly
preferred allotment and at least one of them obtains a strictly preferred
allotment. Thus, an allocation is in the (strong) core if it is not (weakly)
blocked. A distinct but also well-studied solution concept is obtained from
competitive equilibria, each of which consists of a vector of prices for the
objects and a (competitive) allocation such that each agent’s allotment is one
of her most preferred objects among those that she can afford. Interestingly,
the three solution concepts are entwined: the strong core is contained in the
set of competitive allocations, and each competitive allocation pertains to
the core.

In a separate line of research, Balinski and Sönmez [6] studied the classical
two-sided college admissions model of Gale and Shapley [20] and proved that
the student-optimal stable matching mechanism (SOSM) respects improvement of
student’s quality. This means that under SOSM, an improvement of a student’s
rank at a college will, ceteris paribus, lead to a weakly preferred match for
the student. The natural transposition of this property to (one-sided) housing
markets requires that an agent obtains a weakly preferred allotment whenever
her object becomes more desirable for other agents. We study the following
question: Do the most prominent solution concepts for Shapley and Scarf’s [41]
housing market “respect improvement”? We obtain several positive answers to
this question, which we describe in more detail in the next subsection.

The respecting improvement property is important in many applications where
centralised clearinghouses use mechanisms to implement barter exchanges. A
leading example are kidney exchange programmes (KEPs), where end-stage renal
patients exchange their willing but immunologically incompatible donors (Roth
et al. [37]). In the context of KEPs, the respecting improvement property
means that whenever a patient brings a “better” donor (e.g., younger or with
universal blood type 0 instead of A, B, or AB) or registers an additional
donor, the KEP should assign her the same or a better exchange donor. However,
in current KEPs, the typical objective is to maximise the number of
transplants and their overall qualities (see, e.g., [11]) which can lead to
violations of the respecting improvement property. As an illustration,
consider the maximisation of the number of transplants in Figure 1, where each
node represents a patient-donor pair. Directed edges represent compatibility
between the donor in one pair and the patient in another, and patients may
have different levels of preference over their set of compatible donors.

$1$$2$$3$$4$ Figure 1: The maximisation of the number of transplants does not
respect improvement.

Initially there are only continuous edges, where a thick (thin) edge points to
the most (least) preferred donor. For example, patient 3 has two compatible
donors: donors 1 and 4, and donor 1 is preferred to donor 4. Obviously, the
unique way to maximise the number of (compatible) transplants is obtained by
picking the three-cycle (1,2,3). Suppose that patient 4 receives antigen
desensitisation treatment so that donor 3 becomes compatible for her, or
patient 3 succeeds in bringing a second donor to the KEP and this donor turns
out to be compatible for patient 4. Then, the discontinuous edge is included
and patient-donor pair 3 “improves.” But now the unique way to maximise the
number of (compatible) transplants is obtained by picking the 2 two-cycles
(1,2) and (3,4), which means that patient 3 receives a kidney that is strictly
worse than the kidney she would have received initially.

Similarly, the allocations induced by the standard objectives of KEPs need not
be in the (strong) core. We refer to Example 1 for an illustration of this for
the case of the maximisation of the number of transplants. As a consequence,
blocking coalitions may exist. This is an undesirable feature because patient
groups could make a potentially justified claim that the matching procedure is
not in their best interest. A particular instance could occur in the
organisation of international kidney exchanges if a group of patient-donor
pairs, all citizens of the same country, learn that an internal (i.e.,
national) matching would all of them give a more preferred kidney.

We conduct simulations to determine to what extent the typical KEP objectives
lead to the violation of the respecting improvement property and the existence
of blocking coalitions. The simulations also include the three standard game-
theoretical solution concepts (as they also do not “completely” satisfy the
respecting improvement property), for which we first develop novel integer
programming formulations to speed up the computations.

Next, we describe our contributions in more detail and review the related
literature.

###  1.1 Contributions

Section 3 contains our theoretical results on the respecting improvement
property. First, we show that for strict preferences the unique strong core
allocation (which coincides with the unique competitive allocation) respects
improvement (Theorem 1). In the case of preferences with ties, since the
strong core can be empty, we focus on the set of competitive allocations.
Since typically multiple competitive allocations exist, we have to make
setwise comparisons. We obtain a natural extension of our first result:
focusing on the agent’s allotments obtained at competitive allocations, we
establish that her most preferred allotment in the new market is weakly
preferred to her most preferred allotment in the initial market; and
similarly, her least preferred allotment in the new market is weakly preferred
to her least preferred allotment in the initial market (Proposition 1).
Finally, we also prove that when preferences have ties the strong core
respects improvement conditional on the strong core being non-empty. More
precisely, under the assumption that strong core allocations exist in both the
initial and new markets, we show that the agent under consideration weakly
prefers each allotment in the new strong core to each allotment in the initial
strong core (Theorem 2).

Then we tackle an important assumption in the housing market of Shapley and
Scarf, namely that allocations can contain exchange cycles of any length,
i.e., cycles are unbounded. As a consequence, some allocations obtained from
the theory of housing markets might be difficult to implement in the case of
KEPs. The reason is that all transplants in a cycle are usually carried out
simultaneously to avoid reneging. So, if the number of surgical teams and
operation rooms is small, some of the transplants have to be conducted
necessarily in a non-simultaneous way. In many countries, this “risky”
solution is not allowed [8]. The definition of core, set of competitive
allocations, and strong core can be adjusted to the requirement that the
length of exchange cycles does not exceed an exogenously given maximum.
However, in this case the core (and hence also the set of competitive
allocations and the strong core) can be empty.222The corresponding decision
problem is NP-hard [10, 23] even for tripartite graphs (also known as the
cyclic 3D stable matching problem [34]). Conditional on the existence of a
core, competitive, or strong core allocation, we show that even if preferences
are strict, when the length of exchange cycles is limited (upper bound 3 or
higher), the core, the set of competitive allocations, and the strong core do
not respect improvement in terms of the most preferred allotment (Proposition
2).

In view of practical applications such as KEPs, we provide as a second main
contribution, in Section 4, novel integer programming (IP) formulations for
finding core, competitive, and strong core allocations. Our simple sets of
constraints for the three solution concepts clearly show the hierarchy between
them by pinpointing the additional requirements needed when moving from one
solution concept to a stronger one. Our formulations are concise and useful
for practical computations.

Section 5 contains our third main contribution, which complements our
theoretical analysis and consists of computer simulations comparing
core/competitive/strong core with maximum number of transplants and maximum
total weight allocations for both bounded length and unbounded length
exchanges. The total weight of an exchange is the sum of the weights
associated to the arcs involved in the exchange. In the simulations we use the
IP models developed in [25] for bounded length exchanges. For unbounded length
exchanges we use our novel IP formulations. To carry out our simulations we
draw markets from pools similar to those observed in KEPs. We analyse the
impact in the objective functions of the stability requirements associated
with core, competitive, and strong core allocations. For unbounded length we
also study the price of fairness: the decrease in the number of transplants of
maximum weight, core, competitive and strong core allocations, when compared
with the maximum size solution. The analysis proceeds with an indirect
assessment of how far other solutions would be from the strong core. Such
indicator provides some insight in/into the number of patients in a pool that
could get a strictly better match. The section concludes with a computational
analysis of the frequency of violations of the respecting improvement
property. It was observed that even though there exist cases of violation of
the property for (Wako-, strong) core, their quantity is dramatically lower
that those for the maximum size and maximum size solutions.

###  1.2 Literature review

##### Housing markets

The non-emptiness of the core was proved in [41] by showing the balancedness
of the corresponding NTU-game, and also in a constructive way, by showing that
David Gale’s famous Top Trading Cycles algorithm (TTC) always yields
competitive allocations. Roth and Postlewaite [36] later showed that for
strict preferences the TTC results in the unique strong core allocation, which
coincides with the unique competitive allocation in this case. However, if
preferences are not strict (i.e., ties are present), the strong core can be
empty or contain more than one allocation, but the TTC still produces all
competitive allocations. Wako [43] showed that the strong core is always a
subset of the set of competitive allocations. Quint and Wako [35] provided an
efficient algorithm for finding a strong core allocation whenever there exists
one. Their work was further generalised and simplified by Cechlárová and
Fleiner [14] who used graph models. Wako [45] showed that the set of
competitive allocations coincides with a core defined by antisymmetric weak
domination. This equivalence is key for our extension of the definition of
competitive allocations to the case of bounded exchange cycles.

##### Respecting improvement

For Gale and Shapley’s [20] college admissions model, Balinski and Sönmez [6]
proved that the student-optimal stable matching mechanism (SOSM) respects
improvement of student’s quality. Kominers [28] generalised this result to
more general settings. Balinski and Son̈mez [6] also showed that SOSM is the
unique stable mechanism that respects improvement of student quality.
Abdulkadiroglu and Son̈mez [1] proposed and discussed the use of TTC in a
model of school choice, which is closely related to the college admissions
model. Klijn [24] proved that TTC respects improvement of student quality.

Focusing on the other side of the market, Hatfield et al. [22] studied the
existence of mechanisms that respect improvement of a college’s quality. The
fact that colleges can match with multiple students leads to a strong
impossibility result: Hatfield et al. [22] proved that there is no stable nor
Pareto-efficient mechanism that respects improvement of a college’s quality.
In particular, the (Pareto-efficient) TTC mechanism does not respect
improvement of a college’s quality.

In the context of KEPs with pairwise exchanges, the incentives for bringing an
additional donor to the exchange pool was first studied by Roth et al. [38].
In the model of housing markets their donor-monotonicity property boils down
to the respecting improvement property. Roth et al. [38] showed that so-called
priority mechanisms are donor-monotonic if each agent’s preferences are
dichotomous, i.e., she is indifferent between all acceptable donors. However,
if agents have non-dichotomous preferences, then any mechanism that maximises
the number of pairwise exchanges (so, in particular any priority mechanism)
does not respect improvement. This can be easily seen by means of Example 5 in
Section 3.

##### IP formulations for matching

Quint and Wako [35] already gave IP formulations for finding core and strong
core allocations, but the number of constraints in their paper is highly
exponential, as their formulations contain a no-blocking condition for each
set of agents and any possible exchanges among these agents. Other studies
provided IP formulations for other matching problems. In particular, for Gale
and Shapley’s [20] college admissions model, Baïou and Balinski [5] already
described the stable admissions polytope, which can be used as a basic IP
formulation. Further recent papers in this line of research focused on college
admissions with special features [3], stable project allocation under
distributional constraints [4], the hospital–resident problem with couples
[9], and ties [30, 17].

##### Kidney exchange programmes

Starting from the seminal work by Saidman et al. [39], initial research on
KEPs focused on integer programming (IP) models for selecting pairs for
transplantation in such a way that maximum (social) welfare, generally
measured by the number of patients transplanted, is achieved. Authors in [15,
18, 31] proposed new, compact formulations that, besides extending the models
in [39] to accommodate for non-directed donors and patients with multiple
donors, also aimed to efficiently solve problems of larger size. Later studies
[26, 19, 12, 32] modelled the possibility of pair dropout or cancellation of
transplants (if e.g. new incompatibilities are revealed). While [26] and [19]
aimed to find a solution that maximises expected welfare, [12] proposed robust
optimisation models that search for a solution that, in the event of a
cancellation, can be replaced by an alternative (recourse) solution that in
terms of selected patients is as “close” as possible to the initial solution.
McElfresh et al. [32] also addressed the robustness of solutions, but they did
not consider the possibility of recourse.

In a different line of research, [13, 27, 33] studied KEPs where agents (e.g.
hospitals, regional and national programmes) can collaborate. Allowing agents
to control their internal exchanges, Carvalho et al. [13] studied strategic
interaction using non-cooperative game theory. Specifically, for the two-agent
case, they designed a game such that some Nash equilibrium maximises the
overall social welfare. Considering multiple matching periods, Klimentova et
al. [27] assumed agents to be non-strategic. Taking into account that at each
period there can be multiple optimal solutions, each of which can benefit
different agents, the authors proposed an integer programming model to achieve
an overall fair allocation. Finally, Mincu et al. [33] proposed integer
programming formulations for the case where optimisation goals and constraints
can be distinct for different agents.

A recent line of research acknowledges the importance of considering patients’
preferences (associated with e.g. graft quality) over matches. Biró and
Cechlárová [7] considered a model for unbounded length kidney exchanges, where
patients most care about the graft they receive, but as a secondary factor
(whenever there is a tie) they prefer to be involved in an exchange cycle that
is as short as possible. The authors showed that although core allocations can
still be found by the TTC algorithm, finding a core allocation with maximum
number of transplants is a computationally hard problem (inapproximable,
unless $P=NP$). Recently, Klimentova et al. [25] provided integer programming
formulations when each patient has preferences over the organs that she can
receive. The authors focused on allocations that among all (strong) core
allocations have maximum cardinality. Moving away from the (strong) core, they
also analysed the trade-off between maximum cardinality and the number of
blocking cycles. Finally, the reader is referred to [11] for a recent review
of KEPs.

##  2 Preliminaries

We consider housing markets as introduced by Shapley and Scarf [41]. Let
$N=\\{1,\ldots,n\\}$, $n\geq 2$, be the set of agents. Each agent $i\in N$ is
endowed with one object denoted by $e_{i}=i$. Thus, $N$ also denotes the set
of objects. Each agent $i\in N$ has complete and transitive (weak) preferences
$R_{i}$ over objects. We denote the strict part of $R_{i}$ by $P_{i}$, i.e.,
for all $j,k\in N$, $jP_{i}k$ if and only if $jR_{i}k$ and not $kR_{i}j$.
Similarly, we denote the indifference part of $R_{i}$ by $I_{i}$, i.e., for
all $j,k\in N$, $jI_{i}k$ if and only if $jR_{i}k$ and $kR_{i}j$. Let
$R\equiv{(R_{i})}_{i\in N}$. A (housing) market is a pair $(N,R)$. Object
$j\in N$ is acceptable to agent $i\in N$ if $jR_{i}i$. Agent $i$’s preferences
are called strict if they do not exhibit ties between acceptable objects,
i.e., for all acceptable $j,k\in N$ with $j\neq k$ we have $jP_{i}k$ or
$kP_{i}j$. A housing market has strict preferences if each agent has strict
preferences. A housing market where agents do not necessarily have strict
preferences is referred to as a housing market with weak preferences.

Given a housing market $M=(N,R)$ and a set $S\subseteq N$, the submarket
$M_{S}$ is the housing market where $S$ is the set of agents/objects and where
the preferences ${(R_{i})}_{i\in S}$ are restricted to the objects in $S$.

The acceptability graph of a housing market $M=(N,R)$ is the directed graph
$G_{M}=(N,E)$, or $G$ for short, where the set of nodes is $N$ and where
$(i,j)$ is a directed edge in $E$ if $j$ is an acceptable object for $i$,
i.e., $jR_{i}i$. In particular, all self-loops $(i,i)$ are in the graph (but
for convenience they are omitted in all figures). Let $\tilde{N}\subseteq N$
and $\tilde{E}\subseteq E\cap(\tilde{N}\times\tilde{N})$. For each
$i\in\tilde{N}$, the set of agent $i$’s most preferred edges in graph
$\tilde{G}\equiv(\tilde{N},\tilde{E})$ or simply $\tilde{E}$ is the set
$\tilde{E}^{T,i}\equiv\\{(i,j):(i,j)\in\tilde{E}\mbox{ and for each
}(i,k)\in\tilde{E},jR_{i}k\\}$. The most preferred edges in graph $\tilde{G}$
is the set $\cup_{i\in\tilde{N}}\tilde{E}^{T,i}$.

Let $M=(N,R)$ be a housing market. An allocation is a redistribution of the
objects such that each agent receives exactly one object. Formally, an
allocation is a vector $x=\left(x_{i}\right)_{i\in N}\in N^{N}$ such that:

for each $i\in N$, $x_{i}\in N$ denotes agent $i$’s allotment, i.e., the
object that she receives, and

no object is assigned to more than one agent, i.e., $\cup_{i\in
N}\\{x_{i}\\}=N.$ We will focus on individually rational allocations, i.e.,
allocations where each agent receives an acceptable object. Then, an
allocation $x$ can equivalently be described by its corresponding cycle cover
$g^{x}$ of the acceptability graph $G$. Formally, $g^{x}=(N,E^{x})$ is the
subgraph of $G$ where $(i,j)\in E^{x}$ if and only if $x_{i}=j$. Thus, the
graph $g^{x}$ consists of disconnected trading cycles or exchange cycles that
cover $G$. We will often write an (individually rational) allocation in cycle-
notation, i.e., as a set of exchange cycles (where we sometimes omit self-
cycles). We refer to Example 1 for an illustration.

An allocation $x$ Pareto-dominates an allocation $z$ if for each $i\in N$,
$x_{i}R_{i}z_{i}$, and for some $j\in N$, $x_{j}P_{j}z_{j}$. An allocation is
Pareto-efficient if it is not Pareto-dominated by any allocation. Two
allocations $x,z$ are welfare-equivalent if for each $i\in N$,
$x_{i}I_{i}z_{i}$.

Next, we recall the definition of solution concepts that have been studied in
the literature. A non-empty coalition $S\subseteq N$ blocks an allocation $x$
if there is an allocation $z$ such that (1) $\\{z_{i}:i\in S\\}=S$ and (2) for
each $i\in S$, $z_{i}P_{i}x_{i}$. An allocation $x$ is in the core333In the
literature the core is sometimes called the weak core or “regular” core. of
the market if there is no coalition that blocks $x$.

A non-empty coalition $S\subseteq N$ weakly blocks an allocation $x$ if there
is an allocation $z$ such that (1) $\\{z_{i}:i\in S\\}=S$, (2) for each $i\in
S$, $z_{i}R_{i}x_{i}$, and (3) for some $j\in S$, $z_{j}P_{j}x_{j}$. An
allocation $x$ is in the strong core444In the literature the strong core is
sometimes called the strict core. of the market if there is no coalition that
weakly blocks $x$.

A price-vector is a vector $p={(p_{i})}_{i\in N}\in\mathbb{R}^{N}$ where
$p_{i}$ denotes the price of object $i$. A competitive equilibrium is a pair
$(x,p)$ where $x$ is an allocation and $p$ is a price-vector such that:

for each agent $i\in N$, object $x_{i}$ is affordable, i.e., $p_{x_{i}}\leq
p_{i}$ and

for each agent $i\in N$, each object she prefers to $x_{i}$ is not affordable,
i.e., $jP_{i}x_{i}$ implies $p_{j}>p_{i}$. An allocation is a competitive
allocation if it is part of some competitive equilibrium. Since there are $n$
objects, we can assume, without loss of generality, that prices are integers
in the set $\\{1,2,\ldots,n\\}$.

######  Remark 1.

If $(x,p)$ is such that

for each $i\in N$, $p_{x_{i}}\leq p_{i}$, or

for each $i\in N$, $p_{i}\leq p_{x_{i}}$, then for each $i\in N$,
$p_{x_{i}}=p_{i}$. This follows immediately by looking at each exchange cycle
separately (see, e.g., the proof of Lemma 1 in [14]). Hence, at each
competitive equilibrium $(x,p)$, for each $i\in N$, $p_{x_{i}}=p_{i}$.

Wako [45] proved that the set of competitive allocations can be defined
equivalently as a different type of core. Formally, a non-empty coalition
$S\subseteq N$ antisymmetrically weakly blocks an allocation $x$ if there is
an allocation $z$ such that (1) $\\{z_{i}:i\in S\\}=S$, (2) for each $i\in S$,
$z_{i}R_{i}x_{i}$, (3) for some $j\in S$, $z_{j}P_{j}x_{j}$, and (4) for each
$i\in S$, if $z_{i}I_{i}x_{i}$ then $z_{i}=x_{i}$. Requirements (1–3) say that
coalition $S$ weakly blocks $x$. The additional requirement (4) is that if an
agent in $S$ is indifferent between her allotments at $x$ and $z$ then she
must get the very same object, i.e., $z_{i}=x_{i}$. An allocation $x$ is in
the core defined by antisymmetric weak domination if there is no coalition
that antisymmetrically weakly blocks $x$. Wako [45] proved that the set of
competitive allocations coincides with the core defined by antisymmetric weak
domination. Henceforth, we will often refer to the set of competitive
allocations as the Wako-core.

######  Lemma 1.

The strong core, the set of competitive allocations (i.e., the Wako-core), and
the core consist of individually rational allocations. Moreover, the cores are
equivalently characterised by the absence of blocking cycles in the
acceptability graph $G=(N,E)$. In other words, in the definition of each of
the three cores, it is sufficient to require no-blocking by coalitions $S$,
say $S=\\{i_{1},\ldots,i_{k}\\}$, such that for each $l=1,\ldots,k$ (mod $k$),
$z_{i_{l}}=i_{l+1}$ and $(i_{l},i_{l+1})\in E$.

###### Proof.

Individual rationality is immediate. To prove the statement for the strong
core, let $x$ be an individually rational allocation. Suppose there is a non-
empty coalition $T$ that weakly blocks $x$ through some allocation $w$. Let
$j\in T$ be such that $w_{j}P_{j}x_{j}$. Let $S\subseteq T$ be the agents that
constitute the exchange cycle, say $(i_{1},\ldots,i_{k})$, in $w$ that
involves agent $j$, i.e., without loss of generality, $j=i_{1}$. Since $w$ is
individually rational, $S=\\{i_{1},\ldots,i_{k}\\}$ weakly blocks $x$ through
the allocation $z$ defined by

$z_{i}\equiv\left\\{\begin{array}[]{ll}w_{i}&\mbox{if $i\in S$;}\\\
x_{i}&\mbox{if $i\not\in S$}\end{array}\right.$

and for each $l=1,\ldots,k$ (mod $k$), $z_{i_{l}}=i_{l+1}$ and
$(i_{l},i_{l+1})\in E$. This proves the statement for the strong core. The
statements for the core and the Wako-core follow similarly. ∎

An individually rational allocation $x$ is a maximum size allocation if for
each individually rational allocation $z$, $|\\{i\in N:x_{i}\neq
i\\}|\geq|\\{i\in N:z_{i}\neq i\\}|$. Below we provide an example to
illustrate the three cores and maximum size allocation.

######  Example 1.

Let $N=\\{1,\ldots,6\\}$ and let preferences be given by Table 4, where each
agent’s own object and all her unacceptable objects are not displayed. For
instance, agent 1 is indifferent between objects 2 and 3, and strictly prefers
both objects to object 5.

1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---
2,3 | 1 | 2 | 3 | 2 | 1
5 | 3 | 4 | 2 | 6 |

Figure 2: Preferences

$1$$2$$3$$4$$5$$6$

Figure 3: Acceptability graph

$x^{a}=\\{(1,3,2)\\}$
---
$x^{b}=\\{(1,2),(3,4)\\}$
$x^{c}=\\{(1,5,2),(3,4)\\}$
$x^{d}=\\{(1,3,4,2)\\}$
$x^{e}=\\{(1,5,6),(2,3,4)\\}$

Figure 4: Allocations

Figure 4 displays the induced acceptability graph.555Throughout the paper,
self-loops are omitted from the acceptability graphs in the examples. Here, a
thick edge denotes the most preferred object(s) and a thin edge denotes the
second most preferred object (if any).

Consider the allocations defined in Table 4. For instance, $x^{d}$ (in cycle-
notation, but without self-cycles) is the allocation
$x^{d}=(x^{d}_{1},x^{d}_{2},x^{d}_{3},x^{d}_{4},x^{d}_{5},x^{d}_{6})=(3,1,4,2,5,6)$.
It can be verified that $x^{a}$ is the unique strong core allocation, $x^{a}$
and $x^{b}$ are the competitive allocations, while $x^{a}$, $x^{b}$, $x^{c}$,
and $x^{d}$ form the core. Hence, the strong core is a singleton and a proper
subset of the set of competitive allocations, while the latter set is also a
proper subset of the core. Finally, $x^{e}$ is the unique maximum size
allocation and does not pertain to the core. $\diamond$

Shapley and Scarf [41] (see also page 135, Roth and Postlewaite [36]) showed
that the set of competitive allocations is non-empty and coincides with the
set of allocations that are obtained through David Gale’s Top Trading Cycles
algorithm, which is discussed in the next subsection.666If preferences are not
strict, then the Top Trading Cycles algorithm is applied to the preference
profiles that can be obtained by breaking ties in all possible ways. Roth and
Postlewaite [36] showed that if preferences are strict, then there is a unique
strong core allocation which coincides with the unique competitive allocation.
In general, when preferences are not strict, the strong core can be empty
(see, e.g., Footnote 8) or contain more than one allocation (see, e.g.,
Example 1). However, Wako [43] showed that the strong core is always a subset
of the set of competitive allocations.777Wako [44] showed that the strong core
coincides with the set of competitive allocations if and only if any two
competitive allocations are welfare-equivalent. Hence, whenever the set of
competitive allocations is a singleton it coincides with the strong core.
Furthermore, it is easy to see that the set of competitive allocations is
always a subset of the core (Shapley and Scarf [41]).

If preferences are strict, the unique competitive allocation is Pareto-
efficient (because it is in the strong core) and Pareto-dominates any other
allocation (Lemma 1, Roth and Postlewaite [36]); in particular, any other core
allocation is Pareto-inefficient. If preferences are not strict, it is
possible that each competitive allocation is Pareto-dominated by some
allocation that is not competitive.888Example 1 in Sotomayor [42], which is
attributed to Jun Wako, is illustrative: $N=\\{1,2,3\\}$ with $2P_{1}3P_{1}1$,
$1I_{2}3P_{2}2$, $2P_{3}1P_{3}3$. The set of competitive allocations consists
of $x=\\{(1,2),(3)\\}$ and $x^{\prime}=\\{(1),(2,3)\\}$, which are Pareto-
dominated by core allocations $\\{(1,2,3)\\}$ and $\\{(1,3,2)\\}$,
respectively. Moreover, $x_{1}P_{1}x_{1}^{\prime}$ and
$x_{3}^{\prime}P_{3}x_{3}$. The strong core is empty.

Finally, competitive allocations need not be welfare-equivalent: in fact,
different agents can strictly prefer distinct competitive allocations (see,
e.g., Footnote 8). However, Wako [44] showed that all strong core allocations
are welfare-equivalent. The latter result also immediately follows from Quint
and Wako’s [35] algorithm, which is discussed in the next subsection.

### Definitions for bounded length exchanges

Motivated by kidney exchange programmes, here we consider housing markets
where the length of allowed exchange cycles in allocations is limited.
Assuming that blocking coalitions are subject to the same limitation, the core
and strong core can be adjusted straightforwardly (see also [10]). In view of
Wako’s [45] result we similarly adjust the set of competitive allocations by
using the (equivalent) Wako-core.

For a housing market $M=(N,R)$, let $k$ be an integer that indicates the
maximal allowed length of exchange cycles. An allocation is a $k$-allocation
if each exchange cycle has length at most $k$. Formally, an allocation $x$ is
a $k$-allocation if there exists a partition of $N=S_{1}\cup
S_{2}\cup\dots\cup S_{q}$ such that for each $p\in\\{1,\dots,q\\}$,
$|S_{p}|\leq k$ and $\\{x_{i}:i\in S_{p}\\}=S_{p}$. The definition of the
three cores can be adjusted accordingly as well. Specifically, the $k$-core
consists of the $k$-allocations for which there is no blocking coalition of
size at most $k$; the strong $k$-core consists of the $k$-allocations for
which there is no weakly blocking coalition of size at most $k$; the
Wako-$k$-core consists of the $k$-allocations that are not antisymmetrically
weakly dominated through a coalition of size at most $k$. Due to the
“nestedness” of the three blocking notions, it follows that the strong
$k$-core is a subset of the Wako $k$-core, and that the Wako $k$-core is a
subset of the $k$-core. It is also easy to verify that, similarly to the
unbounded case, for strict preferences the strong $k$-core coincides with the
Wako-$k$-core.

To keep notation as simple as possible, whenever the context is clear, we will
omit “$k$” from $k$-allocation, $k$-core, etc. and instead refer to
$k$-housing markets to invoke the above restriction on exchange cycles,
blocking coalitions, allocations, and cores.

The absence of blocking coalitions is also called stability in the literature,
that is widely used especially for bounded length exchanges. In the case of
pairwise exchanges (i.e., for $k=2$), the problem is equivalent to the so-
called stable roommates problem, and stable marriage problem if the graph is
bipartite, as introduced in [20]. For strict preferences the core, Wako-core,
and strong core are all equivalent and they correspond to the set of stable
matchings. For weak preferences the core and Wako-core are the same, and
correspond to weakly stable matchings, whilst the strong core corresponds to
strongly stable matchings. See more about these concepts in [16].

###  2.1 Algorithms to find all strong core allocations

In this section we describe the TTC algorithm and its extension by Quint and
Wako [35] for finding strong core allocations. Our concise and standardised
descriptions provide an easy summary of the current state of the art.
Moreover, the graphs defined in the algorithms are crucial tools in Section 3
where we prove that the strong core “respects improvement.” We consider
housing markets with strict preferences and weak preferences separately. In
the first case the strong core is always a singleton (which consists of the
unique competitive allocation), while in the second case it can be empty.

#### Strict preferences

Let $M=(N,R)$ be a housing market with strict preferences. We will construct a
subgraph $G^{CP}$ of $G$ by using the Top Trading Cycles (TTC) algorithm of
David Gale [41]. The node set of $G^{CP}$ is $N$ and its directed edges
$E^{CP}=E^{C}\cup E^{P}$ are partitioned into two sets $E^{C}$ and $E^{P}$,
where $E^{C}$ will denote the edges in the TTC cycles and $E^{P}$ will denote
a particular subset of edges pointing to more preferred objects.

TTC algorithm, construction of $G^{CP}$
Set $E^{C}\equiv\emptyset$, $E^{P}\equiv\emptyset$, and $M_{1}\equiv M$. Let
$G_{1}=(N_{1},E_{1})\equiv(N,E)$ denote the acceptability graph of $M_{1}$. We
iteratively construct “shrinking” submarkets $M_{t}$ ($t=2,3,\ldots$) whose
acceptability graph will be denoted by $G_{t}=(N_{t},E_{t})$. Set $t\equiv 1$.

  1. 1.

Let $E^{T}_{t}$ be the set of most preferred edges in $G_{t}$.

  2. 2.

Let $c_{t}$ be a (top trading) cycle in $(N_{t},E^{T}_{t})$. Let $C_{t}$ and
$E_{t}$ denote the node set and edge set of $c_{t}$, respectively.

  3. 3.

Add the edges of $c_{t}$ to $E^{C}$, i.e., $E^{C}\equiv E^{C}\cup E_{t}$.

  4. 4.

Let $E^{T}_{t}(\vec{C_{t}})$ denote the subset of edges of $E^{T}_{t}$
pointing to $C_{t}$ from outside $C_{t}$. Formally,
$E^{T}_{t}(\vec{C_{t}})\equiv\\{(i,j)\in E^{T}_{t}:i\in N_{t}\setminus
C_{t}\mbox{ and }j\in C_{t}\\}$. Add $E^{T}_{t}(\vec{C_{t}})$ to $E^{P}$,
i.e., $E^{P}\equiv E^{P}\cup E^{T}_{t}(\vec{C_{t}})$.

  5. 5.

If $N_{t}=C_{t}$, stop. Otherwise, let $N_{t+1}\equiv N_{t}\setminus C_{t}$,
denote the submarket $M_{N_{t+1}}$ by $M_{t+1}$, and go to step 1.

When the algorithm terminates the set of cycles in $E^{C}$ is the unique
competitive allocation and hence the unique strong core allocation.

We classify the relation between any two agents through graph $G^{CP}$ as
follows. Let $i,j\in N$ with $i\neq j$. Then, exactly one of the following
situations holds:

  * •

$i$ and $j$ are independent: there is no directed path from $i$ to $j$ or from
$j$ to $i$;

  * •

$i$ and $j$ are cycle-members: there is a path from $i$ to $j$ that entirely
consists of edges in $E^{C}$, i.e., $i$ and $j$ are in the same top trading
cycle;999Obviously, in this case there is also a path from $j$ to $i$ that
consists of edges in $E^{C}$.

  * •

$i$ is a predecessor of $j$ (and $j$ is a successor of $i$): there is a path
from $i$ to $j$ in $G^{CP}$ using at least one edge from $E^{P}$;101010Note
that in this case $j$ was removed from the market before $i$. Hence, there is
no path from $i$ to $j$ using only edges in $E^{C}$ and $j$ is not a
predecessor of $i$. or

  * •

$j$ is a predecessor of $i$ (and $i$ is a successor of $j$): there is a path
from $j$ to $i$ in $G^{CP}$ using at least one edge from $E^{P}$.

In case $i$ is a predecessor of $j$, we define the best path from $i$ to $j$
to be the path from $i$ to $j$ in $G^{CP}$ where at each node $k\neq j$ on the
path, the path follows agent $k$’s (unique) most preferred edge in

$\\{(k,l)\in E^{CP}:\mbox{ there is a path from $l$ to $j$ using edges in
$E^{CP}$}\\}.$

Let $p^{b}(i,j)$ denote the unique best path from $i$ to $j$ in $G^{CP}$. For
each node $k\neq j$ on $p^{b}(i,j)$, if there are multiple paths from $k$ to
$j$, then $p^{b}(i,j)$ follows the edge that points to the object that is part
of the earliest top trading cycle.

#### Weak preferences

Let $M=(N,R)$ be a housing with weak preferences. We will now describe the
efficient algorithm of Quint and Wako [35] for finding a strong core
allocation whenever there exists one. We use the simplified interpretation of
Cechlárová and Fleiner [14] and construct a subgraph $G^{SP}$ of $G$ with node
set $N$ and edge set $E^{SP}\equiv E^{S}\cup E^{P}$, which will be useful for
our later analysis.

We first recall two definitions. A strongly connected component of a directed
graph is a subgraph where there is a directed path from each node to every
other node. An absorbing set is a strongly connected component with no
outgoing edge. Note that each directed graph has at least one absorbing set.

Quint-Wako algorithm, construction of $G^{SP}$
Set $E^{S}\equiv\emptyset$, $E^{P}\equiv\emptyset$, and $M_{1}=M$. Let
$G_{1}=(N_{1},E_{1})\equiv(N,E)$ denote the acceptability graph of $M_{1}$. We
iteratively construct “shrinking” submarkets $M_{t}$ ($t=2,3,\ldots$) whose
acceptability graph will be denoted by $G_{t}=(N_{t},E_{t})$. Set $t\equiv 1$.

  1. 1.

Let $E^{T}_{t}$ be the set of most preferred edges in $G_{t}$.

  2. 2.

Let $S_{t}$ be an absorbing set in $(N_{t},E^{T}_{t})$. Let $N_{t}(S_{t})$ and
$E^{T}_{t}(S_{t})$ denote the node set and edge set of $S_{t}$.

  3. 3.

Add the edges of $S_{t}$ to $E^{S}$, i.e., $E^{S}\equiv E^{S}\cup
E^{T}_{t}(S_{t})$.

  4. 4.

Let $E^{T}_{t}(\vec{S_{t}})$ denote the subset of edges of $E^{T}_{t}$
pointing to $N_{t}(S_{t})$ from outside $N_{t}(S_{t})$. Formally,
$E^{T}_{t}(\vec{S_{t}})\equiv\\{(i,j)\in E^{T}_{t}:i\in N_{t}\setminus
N_{t}(S_{t})\mbox{ and }j\in N_{t}(S_{t})\\}$. Add $E^{T}_{t}(\vec{S_{t}})$ to
$E^{P}$, i.e., $E^{P}\equiv E^{P}\cup E^{T}_{t}(\vec{S_{t}})$.

  5. 5.

If $N_{t}=N_{t}(S_{t})$, stop. Otherwise, let $N_{t+1}\equiv N_{t}\setminus
N_{t}(S_{t})$, denote the submarket $M_{N_{t+1}}$ by $M_{t+1}$, and go to step
1.

Quint and Wako [35] proved that there is a strong core allocation for $M$ if
and only if for each absorbing set $S_{t}$ defined in the above algorithm
there exists a cycle cover, i.e., a set of cycles covering all the nodes of
$S_{t}$. Finding a cycle cover, if one exists, can be done with the classical
Hungarian method [29] for finding a perfect matching for the corresponding
bipartite graph where the objects are on one side, the agents are on the other
side, and there is an undirected arc between an object-agent pair if the
object is among the agent’s most preferred objects (which might include her
own object). We refer to [2], [35], and [14] for further details on this
reduction.

######  Remark 2.

If for each absorbing set $S_{t}$ defined in the above algorithm there exists
a cycle cover, then the set of cycle covers (one cycle cover for each
absorbing set) constitutes a strong core allocation. Conversely, as shown in
the proof of Theorem 5.5 in Quint and Wako [35], each strong core allocation
can be written as a set of cycle covers (one for each absorbing set $S_{t}$).
Hence, if the strong core is non-empty, all its allocations can be obtained by
selecting all possible cycle covers in the algorithm. $\diamond$

######  Remark 3.

In the Quint-Wako algorithm, each agent obtains the same welfare at any two
cycle covers in which she is involved (because the agent is indifferent
between any two of her outgoing edges in an absorbing set). Together with
Remark 2, this immediately proves Theorem 2(2) in Wako [44], which states that
all strong core allocations are welfare-equivalent. $\diamond$

We classify the relation between any two agents through graph $G^{SP}$ as
follows. Let $i,j\in N$ with $i\neq j$. Then, exactly one of the following
situations holds:

  * •

$i$ and $j$ are independent: there is no directed path from $i$ to $j$ or from
$j$ to $i$;

  * •

$i$ and $j$ are absorbing set members: there is a path from $i$ to $j$ that
entirely consists of edges in $E^{S}$, i.e., $i$ and $j$ are in the same
absorbing set;111111Obviously, in this case there is also a path from $j$ to
$i$ that consists of edges in $E^{S}$.

  * •

$i$ is a predecessor of $j$ (and $j$ is a successor of $i$): there is a path
from $i$ to $j$ in $G^{SP}$ using at least one edge from $E^{P}$;121212Note
that in this case $j$ was removed from the market before $i$. Hence, there is
no path from $i$ to $j$ using only edges in $E^{S}$ and $j$ is not a
predecessor of $i$. or

  * •

$j$ is a predecessor of $i$ (and $i$ is a successor of $j$): there is a path
from $j$ to $i$ in $G^{SP}$ using at least one edge from $E^{P}$.

In case $i$ is a predecessor of $j$, a path from $i$ to $j$ in $G^{SP}$ is
said to be a best path from $i$ to $j$ if at each node $k\neq j$ on the path,
the path follows one of agent $k$’s most preferred edges in

$\\{(k,l)\in E^{SP}:\mbox{ there is a path from $l$ to $j$ using edges in
$E^{SP}$}\\}.$

Let $P^{b}(i,j)$ denote the set of best paths from $i$ to $j$ in $G^{SP}$.

##  3 Respecting Improvement

Let $R,\tilde{R}$ be two preference profiles over objects $N$. Let $i\in N$.
We say that $\tilde{R}$ is an improvement for $i$ with respect to $R$ if

$\tilde{R}_{i}\,=\,R_{i}$;

for all $j\neq i$ and all $k$ with $k\,R_{j}\,j$, $i\,I_{j}\,k\Longrightarrow
i\,\tilde{R}_{j}\,k$ and $i\,P_{j}\,k\Longrightarrow i\,\tilde{P}_{j}\,k$;
and

for all $j\neq i$ and all $k,l\neq i$ with $k,l\,R_{j}\,j$,
$k\,R_{j}\,l\Longleftrightarrow k\,\tilde{R}_{j}\,l$. In other words, (1) only
agents different from $i$ have possibly different preferences at $\tilde{R}$
and ${R}$, (2) for each agent $j\neq i$, object $i$ can become more preferred
than some acceptable objects, and (3) for each agent $j\neq i$ and for each
pair of acceptable objects different from $i$, preferences remain unchanged.

As a simple example with $N=\\{1,2,3,4,5\\}$, let $R$ be any preference
profile such that $4\,P_{5}\,1\,I_{5}\,2\,I_{5}\,3\,P_{5}5$. Let $\tilde{R}$
be the preference profile where agents $1,2,3$, and $4$ have the same
preferences as at $R$ and let $\tilde{R}_{5}$ be defined by
$1\,I_{5}4\,P_{5}\,2\,I_{5}\,3\,P_{5}5$. Then, $\tilde{R}$ is an improvement
for agent $1$ with respect to $R$.

###  3.1 Strict preferences

For each profile of strict preferences $R$, let $\tau(R)$ denote the unique
competitive allocation (or strong core allocation). We show that $\tau$
respects improvement on the domain of strict preferences:

######  Theorem 1.

For each $i\in N$ and each pair of profiles of strict preferences
$R,\tilde{R}$ such that $\tilde{R}$ is an improvement for $i$ with respect to
$R$, $\tau_{i}(\tilde{R})\,R_{i}\,\tau_{i}(R)$.

###### Proof.

Let $x=\tau(R)$ and $\tilde{x}=\tau(\tilde{R})$. We can assume that there is a
unique agent $j\neq i$ with $\tilde{R}_{j}\neq R_{j}$ and prove that
$\tilde{x}_{i}R_{i}x_{i}$. (If there is more than one such agent, we
repeatedly apply the one-agent result to obtain the result.) We can also
assume that $i\tilde{R}_{j}x_{j}$. (Otherwise $x_{j}\tilde{P}_{j}i$ and hence,
from the TTC algorithm, $\tilde{x}=x$.)

We distinguish among three cases, depending on the relation between agents $i$
and $j$ in the graph $G^{CP}$ for the market $(N,R)$, i.e., the graph that is
obtained in the TTC algorithm for $x$.

$j$$i$$F(i)$ |  $p(i,j)$$i$$\dots$$j$$F^{*}(N(i,j))$ |  $i$$l$$\dots$$j$$k$$p^{b}(i,j)$$F(k)$
---|---|---
Case I | Case II | Case III
Figure 5: Graph $G^{CP}$ (simplified) in the proof of Theorem 1. Each ellipse
represents a top trading cycle.

Case I: $i$ and $j$ are independent or $j$ is a predecessor of $i$. Let $F(i)$
be the set of followers131313We avoid the use of the usually equivalent
nomenclature “successor” as the latter term has already a particular (and
different) meaning. of $i$ in the graph $G^{CP}$, where we use the convention
$i\in F(i)$. Then, $j\not\in F(i)$. In the TTC algorithm for $R$, the agents
in $F(i)$ form, among themselves, trading cycles. Since for each agent $k\in
F(i)$, $\tilde{R}_{k}=R_{k}$, it follows that the trading cycles formed by
$F(i)$ in the TTC algorithm for $R$ are also formed in the TTC algorithm for
$\tilde{R}$. Hence, $\tilde{x}_{i}=x_{i}$.

Case II: $i$ and $j$ are cycle-members. Let $C$ be the cycle in the graph
$G^{CP}$ that contains $i$ and $j$. Let $p(i,j)$ be the unique path from $i$
to $j$ in the graph $G^{CP}$. Obviously, $p(i,j)$ is part of $C$. Let $N(i,j)$
be the nodes on $p(i,j)$. (So, $i,j\in N(i,j)$.) Let $F^{*}(N(i,j))$ be the
followers outside of $N(i,j)$ that can be reached by some path in $G^{CP}$
that (1) starts from a node in $N(i,j)$ and (2) does not contain edges in $C$.
Then, the nodes in $F^{*}(N(i,j))$ constitute trading cycles at $x$. Moreover,
the nodes in $F^{*}(N(i,j))$ are neither predecessors of $j$ nor cycle-members
with $j$. Hence, by the same arguments as in Case I, at $\tilde{x}$ the nodes
in $F^{*}(N(i,j))$ constitute the same trading cycles as at $x$. Since
$i\tilde{R}_{j}x_{j}$, the trading cycle of agent $i$ at $\tilde{x}$ is the
cycle that consists of the path $p(i,j)$ and the edge $(j,i)$. Since $p(i,j)$
is part of $C$, it follows that $\tilde{x}_{i}=x_{i}$.

Case III: $i$ is a predecessor of $j$. Since for each $k\neq j$,
$\tilde{R}_{k}=R_{k}$, $i\tilde{R}_{j}x_{j}$, and $\tilde{R}_{j}$ is obtained
from $R_{j}$ by shifting $i$ up, it follows that at some step in the TTC
algorithm for $\tilde{R}$, agent $j$ will start pointing to agent $i$ and will
keep doing so if and as long as agent $i$ is present. Next, consider the
predecessor of $j$ on the path $p^{b}(i,j)$ (in $G^{CP}$ for the market
$(N,R)$), say agent $l$. Let $k\in N$ with $kP_{l}j$. By definition of
$p^{b}(i,j)$, $k$ and $j$ are not cycle-members nor is $k$ a predecessor of
$j$. From the same arguments as in Case I, the nodes in $F(k)$ (the followers
of $k$, where $k\in F(k)$) form among themselves the same trading cycles at
$x$ and $\tilde{x}$. Hence, at some step in the TTC algorithm for $\tilde{R}$,
agent $l$ will start pointing to agent $j$ and will keep doing so if and as
long as agent $j$ is present. We can repeat the same arguments until we
conclude that each node in the cycle formed by $p^{b}(i,j)$ and the edge
$(j,i)$ will, at some step, start pointing to its follower and will keep doing
so if and as long as the follower is present. Thus, the cycle is a trading
cycle at $\tilde{x}$. Let $i^{\prime}$ be the follower of $i$ in this cycle.
Note that in the graph $G^{CP}$, $(i,i^{\prime})\in E^{C}$ or
$(i,i^{\prime})\in E^{P}$. If $(i,i^{\prime})\in E^{C}$, then
$i^{\prime}=x_{i}$, in which case $\tilde{x}_{i}=i^{\prime}=x_{i}$. If
$(i,i^{\prime})\in E^{P}$, then by definition of $E^{P}$,
$\tilde{x}_{i}=i^{\prime}P_{i}x_{i}$. ∎

###  3.2 Weak preferences

For each profile of preferences $R$, let $\mathcal{T}(R)$ denote the set of
competitive allocations.

######  Proposition 1.

For each $i\in N$ and each pair of profiles of preferences $R,\tilde{R}$ such
that $\tilde{R}$ is an improvement for $i$ with respect to $R$,

there is $\tilde{x}\in\mathcal{T}(\tilde{R})$ such that for each
$x\in\mathcal{T}(R)$, $\tilde{x}_{i}R_{i}x_{i}$; and

there is $x\in\mathcal{T}(R)$ such that for each
$\tilde{x}\in\mathcal{T}(\tilde{R})$, $\tilde{x}_{i}R_{i}x_{i}$.

In other words, if agent $i$ compares her best allotment at the allocations in
$\mathcal{T}(R)$ with her best allotment at the allocations in
$\mathcal{T}(\tilde{R})$, then she prefers the latter. Similarly, if agent $i$
compares her worst allotment at the allocations in $\mathcal{T}(R)$ with her
worst allotment at the allocations in $\mathcal{T}(\tilde{R})$, then she
prefers again the latter. Note that in general there is no competitive
allocation where each agent receives her most preferred allotment (among those
that are obtained at competitive allocations), i.e., agents do not unanimously
agree on the “best” competitive allocation (see, e.g., agents 3 and 4 and
competitive allocations $x^{a}$ and $x^{b}$ in Example 1). Nonetheless,
Proposition 1 shows that any individual agent that is systematically
optimistic or pessimistic about the specific competitive allocation that is
chosen subscribes to the thesis that “the competitive mechanism” would respect
any of her potential improvements.

###### Proof.

Let $R^{1},R^{2},\ldots,R^{m}$ be the profiles of strict preferences that are
obtained from $R$ by breaking ties between acceptable objects in each possible
way. Similarly, let $\tilde{R}^{1},\tilde{R}^{2},\ldots,\tilde{R}^{p}$ be the
profiles of strict preferences that are obtained from $\tilde{R}$ by breaking
ties between acceptable objects in each possible way, where possibly $p\neq
m$. Then, from Shapley and Scarf [41] (see also page 306 in Wako [44]),
$\mathcal{T}(R)=\\{\tau(R^{1}),\tau(R^{2}),\ldots,\tau(R^{m})\\}$ and
$\mathcal{T}(\tilde{R})=\\{\tau(\tilde{R}^{1}),\tau(\tilde{R}^{2}),\ldots,\tau(\tilde{R}^{p})\\}$.
It is not difficult to see that for each $R^{k}$, there is some
$\tilde{R}^{l}$ such that $\tilde{R}^{l}$ is an improvement for $i$ with
respect to $R^{k}$. Similarly, for each $\tilde{R}^{l}$, there is some $R^{k}$
such that $\tilde{R}^{l}$ is an improvement for $i$ with respect to $R^{k}$.

We can assume, without loss of generality, that for each $k=1,\ldots,m$,
$\tau_{i}(R^{1})R_{i}\tau_{i}(R^{k})$. Let $\tilde{R}^{l}$ be an improvement
for $i$ with respect to $R^{1}$. Then, from Theorem 1,
$\tau_{i}(\tilde{R}^{l})R^{1}_{i}\tau_{i}({R}^{1})$. Since $R^{1}_{i}=R_{i}$,
$\tau_{i}(\tilde{R}^{l})R_{i}\tau_{i}({R}^{1})$. This proves the first
statement.

We can also assume, without loss of generality, that for each $l=1,\ldots,p$,
$\tau_{i}(\tilde{R}^{l})R_{i}\tau_{i}(\tilde{R}^{p})$. Let $R^{k}$ be such
that $\tilde{R}^{p}$ is an improvement for $i$ with respect to $R^{k}$. Then,
from Theorem 1, $\tau_{i}(\tilde{R}^{p})R^{k}_{i}\tau_{i}({R}^{k})$. Since
$R^{k}_{i}=R_{i}$, $\tau_{i}(\tilde{R}^{p})R_{i}\tau_{i}({R}^{k})$. This
proves the second statement. ∎

The following example illustrates Proposition 1.

######  Example 2.

Let $N=\\{1,2,3,4,5\\}$ and let preferences $R$ and $\tilde{R}$ be given by
Tables 8 and 8, where only acceptable objects are displayed. Note that
$\tilde{R}$ is an improvement for agent $3$ with respect to $R$.

1 | 2 | 3 | 4 | 5
---|---|---|---|---
4 | 1 | 4 | 1 | 2
2 | 3,5 | 2 | 4 | 5
1 | 2 | 3 |  |

Figure 6: $R$

1 | 2 | 3 | 4 | 5
---|---|---|---|---
4 | 3 | 4 | 1,3 | 2
2 | 1 | 2 | 4 | 5
1 | 5 | 3 |  |
| 2 |  |  |

Figure 7: $\tilde{R}$

$x^{a}=\\{(1,4),(2,5)\\}$
---
$x^{b}=\\{(1,4),(2,3)\\}$
$x^{c}=\\{(1,2),(3,4)\\}$

Figure 8: Competitive allocations

By applying the TTC algorithm to the strict preferences obtained by breaking
all ties in all possible ways, we compute the competitive allocations (Table
8). In the case of $R$, the two competitive allocations are $x^{a}$ and
$x^{b}$, and in the case of $\tilde{R}$, the two competitive allocations are
$x^{b}$ and $x^{c}$. Hence, both of agent 3’s best and worst competitive
allotment strictly improve, and at both $R$ and $\tilde{R}$ her best allotment
is different from her worst allotment. $\diamond$

In Example 2, for the “improving agent” (agent 3), each competitive allotment
in the new market is weakly preferred to each competitive allotment in the
initial market. However, it is easy to construct housing markets without this
feature.

Next, we turn to the strong core, which in the case of weak preferences is a
(possibly proper) subset of the set of competitive allocations. Formally, for
a profile of preferences $R$, let $\mathcal{SC}(R)$ denote the (possibly
empty) strong core of $R$. Since strong core allocations are welfare-
equivalent (Remark 3), we can show that the correspondence $\mathcal{SC}$
conditionally respects improvement:

######  Theorem 2.

Let $i\in N$. Let $R,\tilde{R}$ be a pair of profiles of preferences such that
$\tilde{R}$ is an improvement for $i$ with respect to $R$. If
$\mathcal{SC}(R),\mathcal{SC}(\tilde{R})\neq\emptyset$, then for each
$\tilde{x}\in\mathcal{SC}(\tilde{R})$ and for each $x\in\mathcal{SC}(R)$,
$\tilde{x}_{i}R_{i}x_{i}$.

###### Proof.

Let $x\in\mathcal{SC}(R)$. From Remark 3 it follows that it is sufficient to
show that there exists $\tilde{x}\in\mathcal{SC}(\tilde{R})$ with
$\tilde{x}_{i}R_{i}x_{i}$. We can assume that there is a unique agent $j\neq
i$ with $\tilde{R}_{j}\neq R_{j}$. (If there is more than one such agent, we
repeatedly apply the one-agent result to obtain the result.) We can also
assume that $i\tilde{R}_{j}x_{j}$. (Otherwise $x_{j}\tilde{P}_{j}i$ and hence,
from the Quint-Wako algorithm, $x\in\mathcal{SC}(R)=\mathcal{SC}(\tilde{R})$.)

We distinguish among three cases, depending on the relation between agents $i$
and $j$ in the graph $G^{SP}$ for the market $(N,R)$, i.e., the graph that is
generated in the Quint-Wako algorithm to obtain $x$.

Case I: $i$ and $j$ are independent or $j$ is a predecessor of $i$. Let $F(i)$
be the followers of $i$ in the graph $G^{SP}$, where we use the convention
$i\in F(i)$. Then, $j\not\in F(i)$. In the Quint-Wako algorithm for $R$, the
nodes in $F(i)$ are exactly the nodes of a collection of absorbing sets. Since
for each agent $k\in F(i)$, $\tilde{R}_{k}=R_{k}$, it follows that in the
Quint-Wako algorithm for $\tilde{R}$ the nodes in $F(i)$ are exactly the nodes
of the same collection of absorbing sets. Since
$\mathcal{SC}(\tilde{R})\neq\emptyset$, it follows from Remark 2 that there
exists $\tilde{x}\in\mathcal{SC}(\tilde{R})$ such that for each agent $k\in
F(i)$, $\tilde{x}_{k}=x_{k}$. In particular, $\tilde{x}_{i}=x_{i}$.

Case II: $i$ and $j$ are absorbing set members. Let $S_{t}$ be the absorbing
set that contains $i$ and $j$ in the Quint-Wako algorithm for $R$. Let $(i,l)$
be an edge in $S_{t}$, where possibly $l=i$. Let $F^{*}(N_{t}(S_{t}))$ be the
followers outside of $N_{t}(S_{t})$ that can be reached by some path in
$G^{SP}$ that starts from a node in $N_{t}(S_{t})$. Then, the nodes in
$F^{*}(N_{t}(S_{t}))$ are exactly the nodes of a collection of absorbing sets
in the Quint-Wako algorithm for $R$. Moreover, the nodes in
$F^{*}(N_{t}(S_{t}))$ are neither predecessors of $j$ nor absorbing set
members with $j$. Hence, by the same arguments as in Case I, in the Quint-Wako
algorithm for $\tilde{R}$ the nodes in $F^{*}(N_{t}(S_{t}))$ are again the
nodes of the same collection of absorbing sets. Therefore, when the Quint-Wako
algorithm is applied to $\tilde{R}$, the absorbing set that contains $i$ will
again contain $l$. Since $\mathcal{SC}(\tilde{R})\neq\emptyset$, at each
$\tilde{x}\in\mathcal{SC}(\tilde{R})$, agent $i$ will receive an object
$\tilde{x}_{i}$ such that $\tilde{x}_{i}\,I_{i}l$. Since also
${x}_{i}\,I_{i}l$, we obtain $\tilde{x}_{i}\,I_{i}{x}_{i}$.

Case III: $i$ is a predecessor of $j$. Since for each $k\neq j$,
$\tilde{R}_{k}=R_{k}$, $i\tilde{R}_{j}x_{j}$, and $\tilde{R}_{j}$ is obtained
from $R_{j}$ by shifting $i$ up, it follows that at some step in the Quint-
Wako algorithm for $\tilde{R}$, agent $j$ will start pointing to agent $i$ and
will keep doing so if and as long as agent $i$ is present. Next, consider the
predecessor of $j$ on a best path $p^{b}(i,j)\in P^{b}(i,j)$ (in $G^{SP}$ for
the market $(N,R)$), say agent $l$. Let $k\in N$ with $kP_{l}j$. By definition
of $p^{b}(i,j)$, $k$ and $j$ are not absorbing set members nor is $k$ a
predecessor of $j$. From the same arguments as in Case I, the nodes in $F(k)$
(the followers of $k$, where $k\in F(k)$) form among themselves the same
absorbing sets in the Quint-Wako algorithm for both $R$ and $\tilde{R}$.
Hence, during the Quint-Wako algorithm for $\tilde{R}$, at some step agent $l$
will start pointing to agent $j$ and will keep doing so if and as long as
agent $j$ is present. We can repeat the same arguments until we conclude that
each node in the cycle formed by $p^{b}(i,j)$ and the edge $(j,i)$ will, at
some step, start pointing to its follower and will keep doing so if and as
long as the follower is present. Hence, at some step of the algorithm the
cycle formed by $p^{b}(i,j)$ and the edge $(j,i)$ is part of an absorbing set.
Let $i^{b}$ denote the follower of agent $i$ in path $p^{b}(i,j)$. Since
$\mathcal{SC}(\tilde{R})\neq\emptyset$, at each
$\tilde{x}\in\mathcal{SC}(\tilde{R})$, agent $i$ will receive an object
$\tilde{x}_{i}$ such that $\tilde{x}_{i}\,I_{i}i^{b}$. Note that in the graph
$G^{SP}$, $(i,i^{b})\in E^{S}$ or $(i,i^{b})\in E^{P}$. If $(i,i^{b})\in
E^{S}$, then $i^{b}I_{i}x_{i}$, in which case $\tilde{x}_{i}I_{i}x_{i}$. If
$(i,i^{b})\in E^{P}$, then by definition of $E^{P}$, $i^{b}R_{i}x_{i}$, in
which case $\tilde{x}_{i}R_{i}x_{i}$. ∎

######  Corollary 1.

For each $i\in N$ and each pair of profiles of strict preferences
$R,\tilde{R}$ such that $\mathcal{SC}(R),\mathcal{SC}(\tilde{R})\neq\emptyset$
and $\tilde{R}$ is an improvement for $i$ with respect to $R$,

there is $\tilde{x}\in\mathcal{SC}(\tilde{R})$ such that for each
$x\in\mathcal{SC}(R)$, $\tilde{x}_{i}R_{i}x_{i}$; and

there is $x\in\mathcal{SC}(R)$ such that for each
$\tilde{x}\in\mathcal{SC}(\tilde{R})$, $\tilde{x}_{i}R_{i}x_{i}$.

###  3.3 Bounded length exchanges

In this subsection we provide several examples to demonstrate the possible
violations of the respecting improvement property (or variants/extensions of
the property) in the setting of bounded length exchanges.

#### Pairwise exchanges

As mentioned in Section 1, the maximisation of the number of pairwise
exchanges does not respect improvement. Example 5 below proves this formally.
A consequence is that the priority mechanisms studied by Roth et al. [38] need
not be donor-monotonic if agents’ preferences can be non-dichotomous.

######  Example 3.

Let $N=\\{1,\ldots,4\\}$ and let preferences $R$ be given by Table 11 and the
new preferences $\tilde{R}$ by Table 11, where the only improvement is that
agent 1 becomes acceptable for agent 3.

1 | 2 | 3 | 4
---|---|---|---
2 | 1 | 3 | 2
3 | 4 |  | 4
1 | 2 |  |

Figure 9: $R$

1 | 2 | 3 | 4
---|---|---|---
2 | 1 | 1 | 2
3 | 4 | 3 | 4
1 | 2 |  |

Figure 10: $\tilde{R}$

$1$$2$$3$$4$

Figure 11: Acceptability graph

Initially, at $R$, there are two ways to maximise the number of pairwise
exchanges, namely by picking either of the two-cycles $(1,2)$ and $(2,4)$.
Assume, without loss of generality, that $(1,2)$ is selected. (In case $(2,4)$
is selected, similar arguments can be employed.) Suppose the discontinuous
edge (in Figure 11) is included so that agent 1 “improves” and we obtain
$\tilde{R}$. Then, the unique way to maximise the number of pairwise exchanges
is obtained by picking the 2 two-cycles (1,3) and (2,4), which means that
agent 1 is strictly worse off than in the initial situation. $\diamond$

We illustrate that the respecting improvement property can be violated in a
weak sense , namely the best allotment remains the same, but a worse allotment
is created for the improving agent.

######  Example 4.

Let $N=\\{1,\ldots,4\\}$ and let preferences $R$ be given by Table 14 and the
new preferences $\tilde{R}$ by Table 14, where the only improvement is that
agent 1 becomes acceptable for agent 3.

1 | 2 | 3 | 4
---|---|---|---
2 | 4 | 4 | 3
3 | 1 | 3 | 2
1 | 2 |  | 4

Figure 12: $R$

1 | 2 | 3 | 4
---|---|---|---
2 | 4 | 1 | 3
3 | 1 | 4 | 2
1 | 2 | 3 | 4

Figure 13: $\tilde{R}$

$1$$2$$3$$4$

Figure 14: Acceptability graph

Initially, at $R$, the unique (strong) core allocation is
$x^{a}=\\{(1,2),(3,4)\\}$. Suppose the discontinuous edge (in Figure 14) is
included so that agent 1 “improves” and we obtain $\tilde{R}$. Then, another
(strong) core solution is created, $x^{b}=\\{(1,3),(2,4)\\}$, which is
strictly worse for 1. $\diamond$

The following example illustrates violation of best-Ri property for pairwise
exchanges with ties for core and Wako-core.

######  Example 5.

Let $N=\\{1,\ldots,4\\}$ and let preferences $R$ be given by Table 17. In the
new preferences $\tilde{R}$, Table 17, agent 4 makes an improvement and
becomes acceptable for agent 1.

1 | 2 | 3 | 4
---|---|---|---
3 | 4 | 1,4 | 1
|  |  | 3
|  |  | 4

Figure 15: $R$

1 | 2 | 3 | 4
---|---|---|---
3 | 4 | 1,4 | 1
4 |  |  | 3
|  |  | 4

Figure 16: $\tilde{R}$

$1$$2$$3$$4$

Figure 17: Acceptability graph

For original preferences $R$ there exists two (Wako-) core allocations
$x^{a}=\\{(3,4)\\}$ and $x^{b}=\\{(1,3),(2,4)\\}$, i.e.,
$\mathcal{C}(R)=\mathcal{WC}(R)=\\{x^{a},x^{b}\\}$. The best allotment for
agent 4 agent 3, i.e. allocation $x^{a}$ is to be chosen.

For preferences $\tilde{R}$, newly formed cycle $(1,4)$ is blocking for
allocation $x^{a}$, while $(1,3)$ is blocking for allocation $(1,4)$. Then
$\mathcal{C}(\tilde{R})=\mathcal{WC}(\tilde{R})=\\{x^{b}\\}$, hence the
improvement is not respected.

#### Three-way exchanges

The following example exhibits three housing markets where for each housing
market the three cores coincide (and are non-empty). Subsequently, we will use
the example to show that the three cores do not respect improvement when the
maximal allowed length of exchange cycles is 3.

For a housing market $(N,R)$, let, with a slight abuse of notation,
$\mathcal{SC}(R)$, $\mathcal{WC}(R)$, and $\mathcal{C}(R)$ denote the
(possibly empty) strong core, Wako-core, and core of $R$, respectively.

######  Example 6.

Throughout the example we focus on the core. However, since all blocking
arguments can be replaced by weak blocking arguments, all statements also hold
for the strong core, and hence also for the Wako-core. Let
$N=\\{1,\ldots,10\\}$ be the set of agents. We consider three different
housing markets that only differ in preferences. First, consider the housing
market $(N,R)$, or simply $R$ for short, with the following “cyclic” strict
preferences (where unacceptable objects are not displayed):

preferences $R$ 1 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 1 10 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10

Since only directly neighbouring objects (and one’s own object) are
acceptable, it follows that the only exchange cycles where each agent is
assigned an acceptable object are the 10 self-cycles and the 10 two-cycles
$(i,i+1)$ (mod 10) where agents $i$ and $i+1$ swap their objects.141414So, the
core coincides with the set of stable matchings of the corresponding “roommate
problem” (Gale and Shapley, 1962). The core $\mathcal{C}(R)=\\{x^{a},x^{b}\\}$
consists of the following two allocations:

$\displaystyle x^{a}$ $\displaystyle=$
$\displaystyle\\{(1,2),(3,4),(5,6),(7,8),(9,10)\\}\mbox{ and}$ $\displaystyle
x^{b}$ $\displaystyle=$ $\displaystyle\\{(10,1),(2,3),(4,5),(6,7),(8,9)\\}.$

Next, we create an extended housing markets $R^{b}$ by inserting one three-
cycle in $R$.

Preferences $R^{b}$ are provided in Table 19, where the changes with respect
to $R$ are bold-faced and depicted in Figure 19.

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---
4 | 3 | 4 | 5 | 6 | 7 | 8 | 1 | 10 | 1
2 | 1 | 2 | 8 | 4 | 5 | 6 | 9 | 8 | 9
10 | 2 | 3 | 3 | 5 | 6 | 7 | 7 | 9 | 10
1 |  |  | 4 |  |  |  | 8 |  |

Figure 18: Preferences $R^{b}$

$2$$3$$5$$6$$7$$9$$10$$1$$4$$8$

Figure 19: Acceptability graph for $R^{b}$

Apart from the earlier mentioned self-cycles and two-cycles, the only
additional exchange cycle with only acceptable objects in $R^{b}$ is
$c^{b}=(1,4,8)$. Allocation $x^{b}$ is in the core of $R^{b}$ because $c^{b}$
does not block $x^{b}$: agent $4$ obtains object $8$ in $c^{b}$, which is
strictly less preferred to her assigned object at $x^{b}$. In fact, $x^{b}$ is
the unique core allocation of $R^{b}$. To see this, note first that $x^{a}$ is
not in the core of $R^{b}$ as $c^{b}$ blocks it. And second, the only new
exchange cycle created in $R^{b}$, i.e., $c^{b}$, cannot be part of a core
allocation, because if it were, then to avoid blocking cycle $(4,5)$, the next
two-cycle $(5,6)$ would have to be part of the allocation, in which case $7$
would remain unmatched (i.e., be a self-cycle) and cycle $(6,7)$ would block
the allocation. Therefore, $x^{b}$ is the unique core allocation of $R^{b}$,
i.e., $\mathcal{C}(R^{b})=\\{x^{b}\\}$. $\diamond$

Using the above example we can easily prove the following result. For $i\in
N$, preferences $R_{i}$, and a set of allocations $X$, agent $i$’s most
preferred allotment in $X$ is her most preferred allotment among those that
she receives at the allocations in $X$.

######  Proposition 2.

Suppose the maximum allowed length of exchange cycles is 3. Then, there are
3-housing markets with strict preferences $(N,R)$ and $(N,\tilde{R})$ with

$X(R)\equiv\mathcal{SC}(R)=\mathcal{WC}(R)=\mathcal{C}(R)\neq\emptyset$ and

$X(\tilde{R})\equiv\mathcal{SC}(\tilde{R})=\mathcal{WC}(\tilde{R})=\mathcal{C}(\tilde{R})\neq\emptyset$
such that for some $i\in N$, $\tilde{R}$ is an improvement for $i$ with
respect to $R$ but

$X(\tilde{R})\subseteq X(R)$,

for the unique $x\in X(R)\backslash X(\tilde{R})$ and for each $\tilde{x}\in
X(\tilde{R})\backslash X(R)$, $x_{i}\,P_{i}\tilde{x}_{i}$.

###### Proof.

Let $(N,\tilde{R})$ be the 3-housing market with $N=\\{1,\ldots,10\\}$ and
$\tilde{R}=R^{b}$ from Example 6. Let $(N,R)$ be the 3-housing market that is
obtained from $(N,\tilde{R})$ by making object 1 unacceptable for agent 8.
Obviously, $\tilde{R}$ is an improvement for agent 1 with respect to $R$. As
shown in Example 6,
$\mathcal{SC}(\tilde{R})=\mathcal{WC}(\tilde{R})=\mathcal{C}(\tilde{R})=\\{x^{b}\\}\neq\emptyset$.
One also easily verifies that
$\mathcal{SC}(R)=\mathcal{WC}(R)=\mathcal{C}(R)=\\{x^{a},x^{b}\\}\neq\emptyset$.
Finally, agent 1’s most preferred allotment in
$\mathcal{SC}(R)=\mathcal{WC}(R)=\mathcal{C}(R)$ is object 2, while agent 1’s
unique (hence, most preferred) allotment in
$\mathcal{SC}(\tilde{R})=\mathcal{WC}(\tilde{R})=\mathcal{C}(\tilde{R})$ is
object 10. Since agent 1 strictly prefers object 2 to object 10, the result
follows. ∎

##  4 Integer Programming Formulations

In this section we propose novel integer programming (IP) formulations for the
core, the set of competitive allocations (the Wako-core), and the strong core.
First, we propose models for the unbounded case, for the three solution
concepts. Second, we propose alternative cycle formulations for the Wako-Quint
formulations for core and strong core. Finally, we propose a new formulation
for the competitive allocations.

###  4.1 Novel edge-formulations

Let $(N,R)$ be a housing market and $G\equiv G(N,R)=(N,E)$ its acceptability
graph. Since all three cores only contain individually rational allocations,
we can restrict attention to the edges of the acceptability graph.
Specifically, with each edge $(i,j)\in E$ we associate a variable $y_{ij}$ as
follows:

$y_{ij}=\left\\{\begin{array}[]{ll}1&\mbox{if agent $i$ receives object
$j$;}\\\ 0&\mbox{otherwise.}\end{array}\right.$

Then, the base model reads as follows:

$\displaystyle\sum_{j:(i,j)\in E}y_{ij}=1$ $\displaystyle\forall i\in N$ (1)
$\displaystyle\sum_{j:(j,i)\in E}y_{ji}=1$ $\displaystyle\forall i\in N$ (2)
$\displaystyle y_{ij}\in\\{0,1\\}$ $\displaystyle\forall(i,j)\in E$ (3)

Constraints (1) guarantee that agent $i$ receives exactly one (acceptable)
object (possibly her own). Constraints (2) guarantee that object $i$ is given
to exactly one agent. Each vector ${(y_{ij})}_{(i,j)\in E}$ that satisfies
(1), (2), and (3) yields an allocation $x$ defined by $x_{i}=j$ if and only if
$y_{ij}=1$. Moreover, each allocation can be obtained in this way. So, there
is a one-to-one correspondence between allocations and vectors that satisfy
(1), (2), and (3).

We introduce for each $i\in N$ an additional integer variable $p_{i}$ that
represents the price of object $i$.

$\displaystyle p_{i}\in\\{1,\dots,n\\}$ $\displaystyle\forall i\in N$ (4)

In what follows we give our IP formulations for the general case of weak
preferences and explain how they can be simplified for strict preferences. We
tackle the core, the set of competitive allocations, and the strong core (in
this order), by subsequently adding constraints. Given an allocation $x$, we
say that $x$ dominates an edge $(i,j)$ in the acceptability graph $G$ if agent
$i$ weakly prefers her allotment $x_{i}$ to object $j$, i.e.,
$x_{i}\,R_{i}\,j$.

#### IP for the core

It follows from Lemma 1 that an allocation $x$ is in the core if and only if
each cycle in $G$ contains an edge that is dominated by $x$. Or equivalently,
there exists no cycle in $G$ that consists of undominated edges. Note that the
undominated edges form a cycle-free subgraph if and only if there is a
topological order of the objects. The existence of this topological order is
equivalent to the existence of prices of the objects such that for each
undominated edge $(i,j)$, $p_{i}<p_{j}$. Therefore, an allocation $x$ is in
the core if and only if there exist prices ${(p_{i})}_{i\in N}$ such that

$(i,j)\in E\mbox{ is not dominated by }x\,\,\Longrightarrow\,\,p_{i}<p_{j}.$
(*)

Thus, core allocations are characterised by constraints (1)–(4) together with
(5) below:

$\displaystyle p_{i}+1\leq p_{j}+n\cdot\sum_{k:kR_{i}j}y_{ik}$
$\displaystyle\forall(i,j)\in E$ (5)

######  Proposition 3.

Let $x$ be an allocation. Let $y$ be the corresponding vector that satisfies
(1), (2), and (3). Allocation $x$ is in the core if and only if there are
prices ${(p_{i})}_{i\in N}$ such that (4) and (5) hold.

###### Proof.

First observe that for each $(i,j)\in E$,

$(i,j)$ is dominated by $x$
$\displaystyle\Longleftrightarrow\,\,x_{i}\,R_{i}\,j$
$\displaystyle\Longleftrightarrow\,\,\mbox{there is }k\in N\mbox{ with
}k\,R_{i}\,j\mbox{ and }y_{ik}=1$
$\displaystyle\Longleftrightarrow\,\,\sum_{k:kR_{i}j}y_{ik}=1.$ (**)

Suppose $x$ is in the core. Then, there exist prices ${(p_{i})}_{i\in N}$ that
satisfy (4) and (* ‣ 4.1). We verify that (5) holds. Let $(i,j)\in E$. If
$(i,j)$ is not dominated by $x$, then (5) follows immediately from (* ‣ 4.1).
Suppose $(i,j)$ is dominated by $x$. From (** ‣ 4.1),
$\sum_{k:kR_{i}j}y_{ik}=1$. Hence,

$p_{i}+1\leq n+1\leq p_{j}+n=p_{j}+n\cdot\sum_{k:kR_{i}j}y_{ik}.$

Suppose that there exist prices ${(p_{i})}_{i\in N}$ such that (4) and (5)
hold. We verify that (* ‣ 4.1) holds. Let $(i,j)\in E$ and suppose it is not
dominated by $x$. From (** ‣ 4.1), $\sum_{k:kR_{i}j}y_{ik}=0$. Hence, from
(5), $p_{i}+1\leq p_{j}+n\cdot 0$, i.e., $p_{i}<p_{j}$. ∎

#### IP for the set of competitive allocations, i.e., the Wako-core

The set of competitive allocations is characterised by constraints (1)–(5)
together with (6) below:

$\displaystyle p_{i}\leq p_{j}+n\cdot(1-y_{ij})$ $\displaystyle\forall(i,j)\in
E$ (6)

######  Proposition 4.

Let $x$ be an allocation. Let $y$ be the corresponding vector that satisfies
(1), (2), and (3). Allocation $x$ is competitive if and only if there exist
prices ${(p_{i})}_{i\in N}$ such that (4), (5), and (6) hold. Moreover, if
such prices exist, then together with $x$ they constitute a competitive
equilibrium.

###### Proof.

Suppose $x$ is competitive. Let ${(p_{i})}_{i\in N}$ be prices such that
$(x,p)$ is a competitive equilibrium. Then, (4) and (* ‣ 4.1) hold. From the
first part of the proof of Proposition 3 it follows that (5) holds. We now
prove that (6) holds as well. Let $(i,j)\in E$. If $y_{ij}=0$, then
immediately $p_{i}\leq p_{j}+n=p_{j}+n\cdot(1-y_{ij})$. If $y_{ij}=1$, then
$x_{i}=j$, and since $(x,p)$ is a competitive equilibrium it follows from
Remark 1 that $p_{i}=p_{x_{i}}=p_{j}$.

Suppose that there exist prices ${(p_{i})}_{i\in N}$ such that (4), (5), and
(6) hold. We verify that $(x,p)$ is a competitive equilibrium. First, it
follows from (6) that for each $i\in N$, taking $j=x_{i}$ yields $p_{i}\leq
p_{x_{i}}+n\cdot(1-1)=p_{x_{i}}$, i.e., $p_{i}\leq p_{x_{i}}$. Hence, from
Remark 1, for each $i\in N$, $p_{i}=p_{x_{i}}$. Second, let $j\in N$ be an
object such that $j\,P_{i}\,x_{i}$. Then, $(i,j)\in E$ is not dominated by
$x$. From the second part of the proof of Proposition 3 it follows that (* ‣
4.1) holds. Hence, we obtain $p_{i}<p_{j}$. ∎

#### IP for the strong core

The strong core is characterised by constraints (1)–(6) together with (7)
below:

$\displaystyle p_{i}\leq p_{j}+n\cdot\left(\sum_{k:kP_{i}j}y_{ik}\right)$
$\displaystyle\forall(i,j)\in E$ (7)

######  Proposition 5.

Let $x$ be an allocation. Let $y$ be the corresponding vector that satisfies
(1), (2), and (3). Allocation $x$ is in the strong core if and only if there
exist prices ${(p_{i})}_{i\in N}$ such that (4), (5), (6), and (7) hold.
Moreover, if such prices exist, then together with $x$ they constitute a
competitive equilibrium.

###### Proof.

Suppose $x$ is in the strong core. By Remark 2, $x$ can be obtained in the
Quint-Wako algorithm by choosing for each absorbing set in the algorithm a
particular cycle cover. Hence, there exist price ${(p_{i})}_{i\in N}$ such
that (i) constraints (4) are satisfied, (ii) all objects in the same absorbing
set have the same price, and (iii) an absorbing set that is processed earlier
by the algorithm has a strictly higher associated price (of its objects). It
is easy to verify that $(x,p)$ is a competitive allocation. Hence, from the
first part of the proof of Proposition 4 it follows that (5) and (6) hold.
Finally, to see that (7) holds note that from the definition of the prices it
follows that (i) if $jR_{i}x_{i}$ then $p_{i}\leq p_{j}$ and (ii) if
$x_{i}P_{i}j$ then $p_{i}\leq n=n(\sum_{k:kP_{i}j}y_{ik})$.

Suppose that there exist prices ${(p_{i})}_{i\in N}$ such that (4), (5), (6),
and (7) hold. It follows from Proposition 4 that $(x,p)$ is a competitive
equilibrium. We prove that $x$ is a strong core allocation. Suppose there is a
coalition $S$ that weakly blocks $x$ through an allocation $z$. From Lemma 1
it follows that we can assume, without loss of generality, that
$S=\\{1,\ldots,r\\}$ and that for each $i=1,\ldots,r-1$, $z_{i}=i+1$,
$z_{r}=1$, and $z_{1}P_{1}x_{1}$. Since $x$ is individually rational, $r>1$.
Since $(x,p)$ is a competitive equilibrium, $p_{1}<p_{2}$. Since
$3=z_{2}\,R_{2}\,x_{2}$, we have $\sum_{k:kP_{2}3}y_{2k}=0$. Hence, from (7),

$p_{2}\leq p_{3}+n\cdot\left(\sum_{k:kP_{2}3}y_{2k}\right)=p_{3}.$

So, $p_{2}\leq p_{3}$. By repeatedly applying the same arguments we find
$p_{2}\leq p_{3}\leq\cdots\leq p_{r}\leq p_{1}$. Since $p_{1}<p_{2}$, we
obtain a contradiction. Therefore, there is no coalition that weakly blocks
$x$. Hence, $x$ is a strong core allocation. ∎

######  Remark 4.

We note that in the case of strict preferences, constraints (7) are satisfied
by any competitive equilibrium $(x,p)$. To see this note that if $y_{ij}=1$
then (6) implies (7), since $1-y_{ij}=0$, and hence

$p_{i}\leq p_{j}+n\cdot(1-y_{ij})=p_{j}\leq
p_{j}+n\cdot\left(\sum_{k:kP_{i}j}y_{ik}\right).$

Otherwise, if $y_{ij}=0$ then (5) implies (7), since for strict preferences
$\sum_{k:kP_{i}j}y_{ik}=\sum_{k:kP_{i}j}y_{ik}+y_{ij}=\sum_{k:kR_{i}j}y_{ik}$,
and hence

$p_{i}<p_{i}+1\leq
p_{j}+n\cdot\left(\sum_{k:kR_{i}j}y_{ik}\right)=p_{j}+n\cdot\left(\sum_{k:kP_{i}j}y_{ik}\right).$

Therefore, in either case, constraints (7) are satisfied. This reflects the
fact that for strict preferences the strong core is a singleton that consists
of the unique competitive allocation. $\diamond$

###  4.2 Quint and Wako’s IP formulations

To compare our IP formulations with the IP formulations for the core and the
strong core given by Quint and Wako [35], we describe the latter IP
formulations using our notation.

First, for both the core and the strong core, Quint and Wako [35] used the
“basic” constraints (1), (2), and (3). We refer to their formulas (9.2),
(9.3), (9.4), as well as (8.2), (8.3), (8.4), together with an integrality
condition.

Next, to obtain the core Quint and Wako [35] imposed the following additional
no-blocking condition (see (9.1) in [35]):

$\displaystyle\sum_{i\in S}\left(\sum_{j:jR_{i}\pi_{i}}y_{ij}\right)\geq 1$
$\displaystyle\forall S\subseteq N,\pi\in\Pi_{S}$ (8)

Finally, to obtain the strong core Quint and Wako [35] imposed the following
additional no-blocking condition (see (8.1) in [35]):

$\displaystyle\sum_{i\in
S}\left(\sum_{j:jP_{i}\pi_{i}}y_{ij}+\frac{1}{|S|}\sum_{j:jI_{i}\pi_{i}}y_{ij}\right)\geq
1$ $\displaystyle\forall S\subseteq N,\pi\in\Pi_{S},$ (9)

where $\Pi_{S}$ is the set of allocations in the submarket $M_{S}$ (so that
$\pi$ is an allocation in $M_{S}$).

Constraints (8) and (9) directly describe that no coalition $S$ can block /
weakly block through an allocation $\pi$, respectively. Both sets of
constraints are highly exponential (in the number of agents), since they are
required not only for all subsets $S$ of $N$, but also for all possible
redistributions within each $S$.

Alternative cycle-formulations

In view of Lemma 1, it is sufficient to impose constraints (8) and (9) for the
cycles of the acceptability graph $G$. Based on this observation and results
in [25], we will describe alternative cycle-formulations for the core and the
strong core. Furthermore, we will provide a new proposition and IP formulation
for the Wako-core.

Let $M=(N,R)$ be a housing market. Let $\mathcal{C}$ denote the set of
exchange cycles in $G(N,R)$. For a cycle $c\in\mathcal{C}$, let $N(c)$ and
$A(c)$ denote the set of nodes and edges in $c$, respectively, and let $|c|$
denote the size/length of $c$. We write $c_{i}=j$ if agent $i$ receives object
$j$ in the exchange cycle $c$, i.e., $(i,j)\in A(c)$.

######  Proposition 6 ([25]).

An allocation $x$ is in the core if and only if for each cycle
$c\in\mathcal{C}$, for some agent $i\in N(c)$, $x_{i}R_{i}c_{i}$.

The corresponding IP constraints, which reduce the constraints (8) to cycles,
are as follows:

$\displaystyle\sum_{(i,j)\in A(c)}\sum_{k:kR_{i}j}y_{ik}\geq 1$
$\displaystyle\forall c\in\mathcal{C}$ (10)

Next, we describe the alternative cycle-formulation for the strong core. First
we focus on the special case of strict preferences.

######  Proposition 7 ([25]).

Suppose preferences are strict. Then, an allocation $x$ is in the strong core
if and only if for each cycle $c\in\mathcal{C}$, $c$ is an exchange cycle in
$x$ or for some agent $i\in N(c)$, $x_{i}P_{i}c_{i}$.

Proposition 7 leads to the following constraints:

$\displaystyle\sum_{(i,j)\in A(c)}y_{ij}+|c|\cdot\left[\sum_{(i,j)\in
A(c)}\,\,\sum_{k:kP_{i}j}y_{ik}\right]\geq|c|$ $\displaystyle\forall
c\in\mathcal{C}$ (11)

The alternative cycle-formulation for the strong core in the general case
(where preferences can have ties) is as follows.

######  Proposition 8 ([25]).

An allocation $x$ is in the strong core if and only if for each cycle
$c\in\mathcal{C}$,
(i) $c$ is an exchange cycle in $x$, or
(ii) for some agent $i\in N(c)$, $x_{i}P_{i}c_{i}$, or
(iii) for each agent $i\in N(c)$, $c_{i}I_{i}x_{i}$.

The corresponding IP constraints, which reduce the constraints (9) to cycles,
are as follows:

$\displaystyle\sum_{(i,j)\in
A(c)}\sum_{k:kI_{i}j}y_{ik}+|c|\cdot\left[\sum_{(i,j)\in
A(c)}\,\,\sum_{k:kP_{i}j}y_{ik}\right]\geq|c|$ $\displaystyle\forall
c\in\mathcal{C}$ (12)

Finally, similarly to the core and strong core, we provide a new alternative
characterisation for the Wako-core.

######  Proposition 9.

An allocation $x$ is in the Wako-core if and only if for each cycle
$c\in\mathcal{C}$,
(i) $c$ is an exchange cycle in $x$, or
(ii) for some agent $i\in N(c)$, $x_{i}P_{i}c_{i}$, or
(iii) for some agent $i\in N(c)$, $c_{i}I_{i}x_{i}$ and $c_{i}\neq x_{i}$.

The proof of Proposition 9 is omitted as it is very similar to that of
Proposition 8 (see [25]). Proposition 9 leads to the following constraints,
which can be used to find competitive allocations (i.e., allocations in the
Wako-core):

$\displaystyle\sum_{(i,j)\in A(c)}y_{ij}+|c|\cdot\left[\sum_{(i,j)\in
A(c)}\,\,\sum_{k:kR_{i}j,k\neq j}y_{ik}\right]\geq|c|$ $\displaystyle\forall
c\in\mathcal{C}$ (13)

To see the correctness of this new formulation, observe that the first term of
(13) is equal to $|c|$ if condition (i) of Proposition 9 is satisfied and less
than $|c|$ otherwise; and the second term has value at least $|c|$ if
condition (ii) or (iii) of Proposition 9 is satisfied and 0 otherwise.
Therefore, constraint (13) is satisfied if and only if at least one of the
three conditions of Proposition 9 holds.

###  4.3 Bounded length exchanges

Note that the above cycle-formulations are not very practical due to the
exponentially large number of cycles. In fact, this justified the novel IP
formulations proposed in Section 4.1. However, the cycle-formulations are
practical for the case of bounded length exchanges.

One easily verifies that Lemma 1 can be extended to bounded length exchanges
in a natural way: the strong core, Wako-core, and core of a $k$-housing market
can be defined equivalently by the absence of corresponding blocking cycles of
size at most $k$. In fact, Klimentova et al. [25] proposed associated IP
formulations by adapting constraints (10) and (12) to bounded exchange cycles.
One can similarly adapt constraints (13) to obtain an IP formulation for the
Wako-core of a $k$-housing market. In our simulations we used the most
efficient cycle-edge formulations by Klimentova et al. (see the detailed
description in section 3.3 of [25]).

##  5 Computational Experiments

In this section we perform a computational analysis of the models proposed in
Section 4 and compare them with the models for bounded length exchange cycles,
proposed in [25]. Furthermore, we estimate the frequency of violations of the
respecting improvement property for all models by computational simulations.
The models are run for both strict and weak preferences and considering two
objective functions: maximisation of the size of the exchange (corresponding
to the maximisation of the number of transplants in the context of KEPs),
denoted by Maxt, and maximisation of total weight (where weights can mean the
scores given to the corresponding transplants in a KEP, reflecting the
qualities of the transplants), denoted by Maxw. For bounded length exchanges,
the maximum length considered are $k=2$ and $k=3$.

In Section 5.1, we compare the size/weight of the maximum size/weight
allocation to the core, competitive and strong core allocations under the same
objective. For the unbounded case, we further analyse the price of fairness:
the difference in percentage in the number of transplants of the maximum total
weight solution, and the core, competitive and strong core allocations for
both objectives, when compared to the maximum size solution.

In Section 5.2 we calculate the average number of weakly blocking cycles for
allocations provided by each formulation. By doing so, we give a rough
indication of how far each solution is from the strong core. We complement
that analysis with the quantification of the average number of vertices of an
instance that may obtain a strictly better allotment in at least one weakly
blocking cycle.

Average CPU times required to solve an instance of a given size for each of
the formulations in Section 4 are presented in subsection 5.3.

Finally, in subsection 5.4 we provide results on the frequency of violations
of the respecting improvement property for all of our models.

All programs were implemented using Python programming language and tested
using Gurobi as optimisation solver [21]. Tests were executed on a MacMini 8
running macOS version 10.14.3 in a Intel Core i7 CPU with 6 cores at 3.2 GHz
with 8GB of RAM.

Test instances were generated with the generator proposed in [40, 27] and are
available from http: TBA. The number of pairs of an instance ranges from 20 to
150; 50 instances of each size were generated. The weights associated to the
arcs of the graph were generated randomly within the interval $(0,1)$, and
preferences were assigned in accordance with those weights: the higher is the
weight of an outgoing arc for a given vertex, the more preferred is the
corresponding good. For weak preferences, outgoing arcs with weights within
each interval of length $\frac{1}{|V|}$ were considered equally preferable.

###  5.1 Impact of stability on the number of transplants

Figure 20 presents average results for the maximum size and maximum weight
objectives for weak preferences under different settings: no stability
requirements (Max), core, competitive and strong core allocations. We refrain
ourselves from presenting the results for the case of strict preferences as
all curves are similar, except that for strict preferences the competitive and
strong core allocations are the same.

As expected, both the number of transplants and total weight decrease by
increasing the number of constraints from Max to Core, then to Competitive,
and then to Strong Core allocations. The strong core curve is non-monotonic,
which is explained by the absence of feasible solutions for several instances.
Next to the curve we present the number of instances out of the total 50 where
a feasible solution existed.

Figure 20: Number of transplants (left) and total weight of transplants
(right) for unbounded length and weak preferences. The numbers in the chart
reflect the number of instances where a feasible solution existed.

Figure 21 makes a similar analysis for the bounded case, when $k=2$ and $k=3$.
Maxk=∞ refers to the unbounded exchange problem, whilst Maxk=2 and Maxk=3
correspond to the bounded problem for $k=2$ and $k=3$, respectively. The same
reasoning is used for the notation associated to the Wako-core 151515As
mentioned before, for the unbounded case competitive allocations are
equivalent to Wako-core, and for bounded case we only have Wako-core.
(W.-Core) and strong core (S.Core). For easiness of comparison between the
bounded and the unbounded cases, we again plot the two curves from Figure 20
associated with maximum utility (Max) which, in both cases, represent an upper
bound for our solutions. Naturally, the curves associated with $k=2$ are
dominated by those associated with $k=3$. We can observe that the maximum
number of transplants for $k=3$ and for unbounded $k$ are very similar (see
Figure 21 (left)). Notice also that even though some curves overlap and seem
identical, there are minor differences among them, except for the case of core
and Wako-core allocations for $k=2$, that coincide. Again, we only present
results for weak preferences, as this is the more general case. For strict
preferences, for $k=3$ the curves are similar, for $k=2$, core, competitive
and strong core allocations coincide, and the latter two are also the same for
unbounded exchanges.

Figure 21: Comparison of the number of transplants (left) and the total weight
of transplants (right) for bounded length exchanges ($k=2,3$) and weak
preferences. A solid line is used for the unbounded case, dotted lines are
used for $k=2$ and dashed lines for $k=3$.

From a practical point of view an interesting question is to study the impact
of stability requirements on the number of transplants achievable. Although
KEPs have many other key performance indicators, this is unarguably the most
relevant one, as this criterion is optimised as a first objective in all the
European KEPs [11]. Figure 22 presents the price of fairness, that is
difference in percentage in the number of transplants for Maxw allocation, and
for Core, Competitive and Strong Core allocations under both objectives, when
compared to the maximum number of transplants achievable (Maxt). Subscripts
$t$ and $w$ identify the objective functions used for each allocation. As
shown, the price of fairness for competitive and strong core allocations is
extremely high, when compared to the core. It decreases with problem size for
both objective functions and for all allocation models, being slightly higher
for the core for the total weight objective (see curve Corew). For the
maximisation of the number of transplants (curve Coret), for instances with
more than 50 nodes the reduction is of less than 3%, decreasing to 1% for the
largest instance. Such result is of major practical relevance as it indicates
that with increasing size of the programs one can consider pairs’ preferences
in the matching with no significant reduction in the number of pairs
transplanted.

Figure 22: Price of fairness with respect to maximum number of transplants for
core, competitive and strong core allocations, with maximum number of
transplants and maximum total weight, and solution with maximum total weight;
for strict (left) and weak (right) preferences.

###  5.2 Assessing the distance of different solutions from the strong core

Figure 23 (left) presents the average number of weakly blocking cycles of size
2 in Max, Core, and Competitive (Wako-core) allocations. We denote the maximum
length of the blocking cycles considered by $l$. For the bounded case,
following the same reasoning as in [25], the figure also reports the minimum
average number of weakly blocking cycles for the cases where the strong core
does not exist, i.e., for the maximum number of transplants/total weight
solution with minimum number of weakly blocking cycles. Interestingly, when
the objective function is the number of transplants, the “unstability” of the
solutions barely depends on the size of exchanges allowed. The same does not
hold for the core, where the number of blocking cycles is considerably smaller
for $k=2$. For this and all the remaining cases, the average number of weakly
blocking cycles is very low, in most cases below 1. It is worth to note that
the average number of blocking cycles tends to be smaller when the objective
is to maximise the total weight (Figure 23 (right)). A plausible justification
for this is that the weights reflect patients preferences and therefore a
solution obtained by considering that objective will be closer to a stable
solution.

Figure 23: Number of weakly blocking cycles of size ${l=2}$ for solutions with
maximum number of transplants (left) and maximum total weight of transplants
(right), for unbounded exchanges and exchanges of size up to $k=2$ and $k=3$
for weak preferences. A solid line is used for the unbounded case, dotted
lines are used for $k=2$ and dashed lines for $k=3$.

Figure 24 presents the same analysis, now considering weakly blocking cycles
of size up to 3. Naturally, the solutions for $k=2$ are excluded from this
analysis, as they are fully reflected in Figure 23. The conclusions drawn for
$l=2$ remain valid for this case.

Figure 24: Number of weakly blocking cycles of size ${l=3}$ for solutions with
maximum number of transplants (left) and maximum total weight of transplants
(right), for unbounded exchanges and exchanges of size up to $k=3$ for weak
preferences.

For the unbounded case, the number of blocking cycles is larger, since one
must consider also the cases when $l>3$. Figure 25 provides information on the
number of weakly blocking cycles of size up to 4 and up to 5. We do not
present results for $l>5$ as searching for those blocking cycles would exceed
our CPU time.

Figure 25: Number of weakly blocking cycles of size ${l=4}$ and $l=5$ for
solutions with maximum number of transplants (left) and maximum total weight
of transplants (right), for unbounded exchanges and weak preferences.

Although the information above is already insightful, to complement our
analysis we provide in Figure 26 information on the average number of vertices
of an instance that strictly prefer their allotments in at least one weakly
blocking cycle (i.e., on the number of patients that could receive a strictly
better kidney in a deviating allocation). An important conclusion can be drawn
from the results in the figure: the maximisation of total weight decreases the
number of agents that can get a better allotment in a blocking cycle when
compared to the maximum size solutions (compare curves Max in Figure 26 (left)
and (right)). It also allows, by comparison with Figure 22, to analyse the
trade-off that would be necessary to make in terms of reduction of the total
number of transplants to meet a certain level of patients preferences.

Figure 26: Average number of agents for an instance for those there exists at
least one weakly blocking cycles, where this agent receives a strictly better
allotment for weak preferences. The grey line is a reference line showing the
number of vertices in an instance.

###  5.3 CPU time for unbounded models

In Table 1 we present the average CPU time for solving an instance of a given
size with one of the tree newly proposed IP models for unbounded case.

| Max # transplants | Max total weight | Max # transplants | Max total weight
---|---|---|---|---
$|V|$ | Core | Compet. | S.Core | Core | Compet. | S.Core | Core | Compet. | S.Core | Core | Compet. | S.Core
| Strict preferences | Weak preferences
20 | 0.00 | 0.03 | 0.01 | 0.00 | 0.02 | 0.01 | 0.00 | 0.04 | 0.01 | 0.00 | 0.03 | 0.01
30 | 0.03 | 0.13 | 0.04 | 0.02 | 0.11 | 0.03 | 0.02 | 0.28 | 0.04 | 0.02 | 0.17 | 0.03
40 | 0.08 | 0.48 | 0.12 | 0.06 | 0.25 | 0.11 | 0.09 | 0.63 | 0.10 | 0.06 | 0.44 | 0.08
50 | 0.24 | 1.74 | 0.38 | 0.16 | 0.58 | 0.34 | 0.20 | 2.15 | 0.25 | 0.17 | 1.06 | 0.21
60 | 0.47 | 2.39 | 0.87 | 0.28 | 0.91 | 0.79 | 0.52 | 6.03 | 0.44 | 0.26 | 2.87 | 0.39
70 | 1.06 | 3.91 | 1.94 | 0.66 | 2.29 | 1.50 | 0.84 | 16.99 | 1.09 | 0.53 | 7.35 | 0.77
80 | 1.62 | 6.54 | 3.26 | 0.82 | 3.39 | 2.32 | 1.41 | 32.21 | 1.63 | 0.76 | 17.47 | 1.01
90 | 3.14 | 36.34 | 5.31 | 3.27 | 5.38 | 3.59 | 3.29 | 167.15 | 2.36 | 1.82 | 80.88 | 1.49
100 | 3.53 | 16.19 | 19.26 | 2.43 | 6.15 | 9.81 | 4.51 | 188.35 | 8.87 | 3.08 | 95.39 | 4.62
110 | 8.73 | 21.42 | 28.26 | 4.97 | 9.01 | 13.79 | 6.68 | 331.64 | 16.40 | 5.92 | 159.12 | 7.24
120 | 17.84 | 72.87 | 57.36 | 6.81 | 15.36 | 24.32 | 20.14 | 392.88 | 19.60 | 6.79 | 218.58 | 10.87
130 | 14.34 | 46.92 | 84.49 | 14.24 | 22.68 | 34.11 | 14.78 | 586.27 | 21.75 | 12.32 | 438.23 | 10.42
140 | 29.50 | 61.99 | 110.82 | 21.51 | 34.33 | 46.67 | 41.59 | 708.92 | 40.97 | 16.43 | 539.56 | 14.89
150 | 41.99 | 161.10 | 214.32 | 30.66 | 52.61 | 70.77 | 57.13 | 786.43 | 61.79 | 27.82 | 682.99 | 23.91
Table 1: Average CPU time (in seconds) for solving an instance of a given size
with the proposed formulation.

The instances with the weak preferences are more complicated, for core and, in
particular, for the competitive allocation model. However, it was faster to
find the strong core for weak, rather than for strict preferences. Moreover,
surprisingly, finding the strong core is the most time consuming task for
strict preferences, while it is least time consuming for weak preferences.
Finally, we can notice that models for finding core and strong core
allocations are performing within the same ranges of magnitude with respect to
the CPU time if compared with the corresponding models for the bounded case,
analysed in [25].

###  5.4 Violation of respecting improvement property

In this section we will make a computational analysis on how often the
respecting improvement (RI) property is violated for different models, for
both unbounded and bounded cases. To do so, for each model and for instances
with 20 and 30 vertices we run the following procedure, presented in Algorithm
1. For the unbounded case we considered the Max and Core models under both
objectives.

Let $r^{i}_{k}$, $r\in\\{1,\dots,|V|\\}$ be the rank of good $k$ for agent
$i$, that will reflect preferences of $i$, i.e. if
$r^{i}_{k}\leq(<,=)r^{i}_{j}$, then $kR_{i}(P_{i},I_{i})j$.

Result: $N$ number of violations of RI property

$N\leftarrow 0$;

for $i\in V$, $j\in V$, $i\neq j$ do

Let $R$ be the current preferences of agents;

Find allocation with the best allotment for $i$ with respect to $R$, denote
the solution by $\bar{y}$;

For $\bar{y}_{il}=1$ denote $\bar{r}\leftarrow r^{i}_{l}$;

while $\exists kP_{j}i$ do

Let $k$ be the first strictly preferred agent for $j$ that precedes $i$ in
$R$;

if Strict preferences then

Swap $i$ with $k$ in the list of preferences of $j$;

end if

if Weak preferences then

Let $i$ become equally preferred for $j$ as $k$ (i.e. $r^{j}_{i}=r^{j}_{k}$);

end if

Denote modified preferences by $\tilde{R}$;

Find allocation with the best allotment for $i$ with respect to $\tilde{R}$,
denote solution by $\tilde{y}$;

For $\tilde{y}_{it}=1$, denote $\tilde{r}=r^{i}_{t}$;

if $\bar{r}<\tilde{r}$ then

The respecting improvement property is violated: $N\leftarrow N+1$;

end if

$\bar{r}\leftarrow\tilde{r}$; $R\leftarrow\tilde{R}$;

end while

end for

Algorithm 1 Procedure for Checking RI property

For each pair of agents $i$ and $j$, agent $i$ is consecutively making
improvements, moving up in the preference list of agent $j$ until its top. In
each step (see while loop in the algorithm) for the case of strict
preferences, $i$ is swapped with $k$, who is the first strictly preferred
agent by $j$ to $i$. For the case of ties, agent $i$ first becomes equally
preferred for $j$ as $k$. After the improvements, the best allocations for the
original ($R$) and improved ($\tilde{R}$) preferences are compared for $i$. It
is considered that there is a violation of the RI property if $i$ obtains a
strictly worse allotment in allocation for $\tilde{R}$.

Figures 27 and 28 present box plots for the number of violations of the RI
property for instances of a given size for strict and weak preferences,
respectively, for those models where the RI property is violated at least
once. Models whose results are the same, independently of the objective
considered, are plotted together. That is the case, for example, of Coret and
Corew, for $k=3$ and strict preferences (see figure 27), or of Wako-core and
Core, weak preferences and $k=2$ and $k=3$ (see figure 28).

Figure 27: Number of violations of the respecting improvement property for all
instances in total of a given size, $|V|=20,30$, for strict preferences.
Figure 28: Number of violations of the respecting improvement property for all
instances in total of a given size, $|V|=20,30$, for weak preferences.

For (Wako-, Strong) Core models there were few cases of violations of the RI
property, as reflected in the figure. To give an indication, the total number
of violations for all instances with 30 vertices for the weak preferences and
$k=3$ was 4549 for Maxt, 3145 for Maxw, 10 for Coret,w, 20 for W.-Coret,w, and
2 for S.Coret,w. For maximum size and maximum weight solutions (Maxt and Maxw,
respectively), both for the unbounded and the bounded cases, one can observe a
significant number of violations. Those numbers increase with instance size.
Interestingly, for the unbounded case the number of violations for Maxt was
lower than that for Maxw. This can be explained by the fact that the former
problem has a larger number of alternative best allocations, while for the
weighted objective problem the solution is usually unique. On the contrary,
for the bounded case maximum weighted solutions violated the property less
times, compared to maximum size solutions.

##  6 Conclusion

This paper advances current state of the art in several lines of research. We
first prove that in case of strict preferences the unique competitive
allocation respects improvement; an extension of that result is provided for
the case of ties.

We also advance the work in the housing market of Shapley and Scarf presented
in [35] by providing Integer Programming models that do not require
exponential number of constraints for the weak core, strong core, and the set
of competitive allocations. These models assume that there is no limit on the
maximum size of an exchange cycle. However, since there are problems where
such assumption may be difficult to hold (e.g. Kidney Exchange Programmes) we
further propose alternative IP models for bounded cycles. This contribution is
inspired by the definition of competitive equilibrium allocations provided in
[45].

We proceed with computational experiments that provide insights on the trade-
off between stability requirements and maximum number of transplants. Results
show that with increasing size of the instances, such trade-off decreases: for
instances with more than 50 nodes core allocations impact on the reduction of
transplants is less than 3%, decreasing to 1% for the largest instance.

Furthermore, results show that when the objective is to maximise the number of
transplants, the “unstability” of the solutions, measured by the number of
weakly blocking cycles barely depends on the length of the exchanges.
Additionally, the maximisation of total weight instead of the number of
transplants, leads to solutions where patients’ preferences matter more.

As the main open question we left open whether the respecting improvement
property with regard to the best allotment holds for a) the core for unbounded
exchanges b) for stable matchings in the roommates problem with strict
preferences. It would also be interesting to study whether the respecting
improvement property can be used to characterise the TTC mechanism for the
classical housing markets with strict preferences.

## Acknowledgements

We thank Antonio Nicoló for his contribution to an earlier version of this
paper, and Tayfun Sönmez, and Utku Ünver for valuable comments.

## References

  * [1] Atila Abdulkadiroğlu and Tayfun Sönmez.  School choice: A mechanism design approach.  American Economic Review, 93(3):729–747, 2003.
  * [2] David J. Abraham, Avrim Blum, and Tuomas Sandholm.  Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges.  In Proceedings of the 8th ACM Conference on Electronic Commerce, EC-07, pages 295–304, New York, NY, USA, 2007. ACM.
  * [3] Kolos Csaba Ágoston, Péter Biró, and Iain McBride.  Integer programming methods for special college admissions problems.  Journal of Combinatorial Optimization, 32(4):1371–1399, 2016.
  * [4] Kolos Csaba Ágoston, Péter Biró, and Richárd Szántó.  Stable project allocation under distributional constraints.  Operations Research Perspectives, 5:59–68, 2018.
  * [5] Mourad Baïou and Michel Balinski.  The stable admissions polytope.  Mathematical Programming, 87(3):427–439, 2000.
  * [6] Michel Balinski and Tayfun Sönmez.  A tale of two mechanisms: Student placement.  Journal of Economic Theory, 84(1):73–94, 1999.
  * [7] Péter Biró and Katarína Cechlárová.  Inapproximability of the kidney exchange problem.  Information Processing Letters, 101(5):199–202, 2007.
  * [8] Péter Biró, Bernadette Haase-Kromwijk, Joris van de Klundert, and et al.  Building kidney exchange programmes in Europe – an overview of exchange practice and activities.  Transplantation, 103(7):1514–1522, 2019.
  * [9] Péter Biró, David F. Manlove, and Iain McBride.  The hospitals/residents problem with couples: Complexity and integer programming models.  In International Symposium on Experimental Algorithms, pages 10–21. Springer, 2014.
  * [10] Péter Biró and Eric McDermid.  Three-sided stable matchings with cyclic preferences.  Algorithmica, 58(1):5–18, 2010.
  * [11] Péter Biró, Joris van de Klundert, David F. Manlove, and et al.  Modelling and optimisation in European Kidney Exchange Programmes.  European Journal of Operational Research, 2019.
  * [12] Margarida Carvalho, Xenia Klimentova, Kristiaan Glorie, Ana Viana, and Miguel Constantino.  Robust models for kidney exchange programs.  Accepted for publication in INFORMS Journal on Computing, 2020.
  * [13] Margarida Carvalho, Andrea Lodi, João P. Pedroso, and Ana Viana.  Nash equilibria in the two-player kidney exchange game.  Mathematical Programming, 161(1-2):389–417, 2017.
  * [14] Katarína Cechlárová and Tamás Fleiner.  Housing markets through graphs.  Algorithmica, 58(1):19–33, 2010.
  * [15] Miguel Constantino, Xenia Klimentova, Ana Viana, and Abdur Rais.  New insights on integer-programming models for the kidney exchange problem.  European Journal of Operational Research, 231(1):57–68, 2013.
  * [16] Manlove David.  Algorithmics of matching under preferences, volume 2.  World Scientific, 2013.
  * [17] Maxence Delorme, Sergio García, Jacek Gondzio, Jörg Kalcsics, David F. Manlove, and William Pettersson.  Mathematical models for stable matching problems with ties and incomplete lists.  European Journal of Operational Research, 277(2):426–441, 2019\.
  * [18] John P. Dickerson, David F. Manlove, Benjamin Plaut, Tuomas Sandholm, and James Trimble.  Position-indexed formulations for kidney exchange.  CoRR, abs/1606.01623, 2016.
  * [19] John P. Dickerson, Ariel D. Procaccia, and Tuomas Sandholm.  Failure-aware kidney exchange (extended version of the EC-13 paper).  2014\.
  * [20] David Gale and Lloyd S. Shapley.  College admissions and the stability of marriage.  American Mathematical Monthly, 69(1):9–15, 1962.
  * [21] LLC Gurobi Optimization.  Gurobi optimizer reference manual, 2018.
  * [22] John William Hatfield, Fuhito Kojima, and Yusuke Narita.  Improving schools through school choice: A market design approach.  Journal of Economic Theory, 166:186–211, 2016.
  * [23] Chien-Chung Huang.  Circular stable matching and 3-way kidney transplant.  Algorithmica, 58(1):137–150, 2010.
  * [24] Flip Klijn.  The top trading cycles algorithm respects improvement of student quality in school choice.  Mimeo, 2019.
  * [25] Xenia Klimentova, Péter Biró, Virginia Costa, João P. Pedroso, and Ana Viana.  Novel IP formulations for the stable kidney exchange problem.  Working paper available at https://arxiv.org/abs/2012.04918, 2020\.
  * [26] Xenia Klimentova, João P. Pedroso, and Ana Viana.  Maximising expectation of the number of transplants in kidney exchange programmes.  Computers & OR, 73:1–11, 2016.
  * [27] Xenia Klimentova, Ana Viana, João P. Pedroso, and Nicolau Santos.  Fairness models for multi-agent kidney exchange programs.  Accepted for publication in Omega, 2019.
  * [28] Scott D. Kominers.  Respect for improvements and comparative statics in matching markets.  Working paper, 2019.
  * [29] Harold W. Kuhn.  The Hungarian method for the assignment problem.  Naval Research Logistics Quarterly, 2(1-2):83–97, 1955.
  * [30] Augustine Kwanashie and David F. Manlove.  An integer programming approach to the hospitals/residents problem with ties.  In Operations Research Proceedings 2013, pages 263–269. Springer, 2014.
  * [31] Vicky Mak-Hau.  On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approaches.  Journal of Combinatorial Optimization, 33(1):35–59, 2017.
  * [32] Duncan C. McElfresh, Hoda Bidkhori, and John P. Dickerson.  Scalable robust kidney exchange.  CoRR, Presented at AAAI 19, abs/1811.03532, 2018.
  * [33] Radu-Stefan Mincu, Péter Biró, Márton Gyetvai, Alexandru Popa, and Utkarsh Verma.  Ip solutions for international kidney exchange programmes.  Accepted for publication in Central European Journal of Operations Research, 2020.
  * [34] Cheng Ng and Daniel S. Hirschberg.  Three-dimensional stable matching problems.  SIAM Journal on Discrete Mathematics, 4(2):245–252, 1991.
  * [35] Thomas Quint and Jun Wako.  On houseswapping, the strict core, segmentation, and linear programming.  Mathematics of Operations Research, 29(4):861–877, 2004.
  * [36] Alvin E. Roth and Andrew Postlewaite.  Weak versus strong domination in a market with indivisible goods.  Journal of Mathematical Economics, 4(2):131–137, 1977.
  * [37] Alvin E. Roth, Tayfun Sönmez, and M Utku Ünver.  Kidney exchange.  Quarterly Journal of Economics, 119(2):457–488, 2004.
  * [38] Alvin E. Roth, Tayfun Sönmez, and M Utku Ünver.  Pairwise kidney exchange.  Journal of Economic Theory, 125(2):151–188, 2005.
  * [39] Susan L. Saidman, Alvin E. Roth, Tayfun Sönmez, M. Utku Ünver, and Francis L. Delmonico.  Increasing the opportunity of live kidney donation by matching for two and three way exchanges.  Transplantation, pages 773–782, 2006.
  * [40] Nicolau Santos, Paolo Tubertini, Ana Viana, and João P. Pedroso.  Kidney exchange simulation and optimization.  Journal of the Operational Research Society, 68(12):1521––1532, 12 2017.
  * [41] Lloyd S. Shapley and Herbert Scarf.  On cores and indivisibility.  Journal of Mathematical Economics, 1(1):23–37, 1974.
  * [42] Marilda Sotomayor.  An elementary non-constructive proof of the non-emptiness of the core of the housing market of Shapley and Scarf.  Mathematical Social Sciences, 50(3):298–303, 2005.
  * [43] Jun Wako.  A note on the strong core of a market with indivisible goods.  Journal of Mathematical Economics, 13(2):189–194, 1984.
  * [44] Jun Wako.  Some properties of weak domination in an exchange market with indivisible goods.  Economics Studies Quarterly, 42(4):303–314, 1991.
  * [45] Jun Wako.  Coalition-proofness of the competitive allocations in an indivisible goods market.  Fields Institute Communications, 23:277–283, 1999.