University of Glasgow<EMAIL_ADDRESS>by the
Engineering and Physical Sciences Research Council [EP/V032305/1].Indian
Institute of Technology<EMAIL_ADDRESS>Indian Institute
of Technology<EMAIL_ADDRESS>John Q. Public and Joan R.
Public <ccs2012> <concept> <concept_id>10003752.10003809.10010052</concept_id>
<concept_desc>Theory of computation Parameterized complexity and exact
algorithms</concept_desc> <concept_significance>500</concept_significance>
</concept> <concept> <concept_id>10003752.10003809.10003635</concept_id>
<concept_desc>Theory of computation Graph algorithms analysis</concept_desc>
<concept_significance>500</concept_significance> </concept> <concept>
<concept_id>10003752.10003809.10011254</concept_id> <concept_desc>Theory of
computation Algorithm design techniques</concept_desc>
<concept_significance>500</concept_significance> </concept> </ccs2012>
[500]Theory of computation Parameterized complexity and exact algorithms
[500]Theory of computation Algorithm design techniques

###### Acknowledgements.

John Q. Open and Joan R. Access 2 42nd Conference on Very Important Topics
(CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016 Little Whinging, United
Kingdom 42 23

# The Cost and Complexity of Minimizing Envy
in House Allocation

Jayakrishnan Madathil  Neeldhara Misra  Aditi Sethia

###### Abstract

We study almost-envy-freeness in house allocation, where $m$ houses are to be
allocated among $n$ agents so that every agent receives exactly one house. An
envy-free allocation need not exist, and therefore we may have to settle for
relaxations of envy-freeness. But typical relaxations such as envy-free up to
one good do not make sense for house allocation, as every agent is required to
receive exactly one house. Hence we turn to different aggregate measures of
envy as markers of fairness. In particular, we define the amount of envy
experienced by an agent $a$ w.r.t. an allocation to be the number of agents
that agent $a$ envies under that allocation. We _quantify_ the envy generated
by an allocation using three different metrics: 1) the number of agents who
are envious; 2) the maximum amount of envy experienced by any agent; and 3)
the total amount of envy experienced by all agents, and look for allocations
that minimize one of the three metrics. We thus study three computational
problems corresponding to each of the three metrics and prove a host of
algorithmic and hardness results. We also suggest practical approaches for
these problems via integer linear program (ILP) formulations and report the
findings of our experimental evaluation of ILPs. Finally, we study the price
of fairness (PoF), which quantifies the loss of welfare we must suffer due to
the fairness requirements, and we prove a number of results on PoF, including
tight bounds as well as algorithms that simultaneously optimize both welfare
and fairness.

###### keywords:

house allocation, envy-freeness, egalitarian, utilitarian, kernel, expansion
lemma

###### category:

##  1 Introduction

The _house allocation problem_ consists of $n$ agents and $m$ houses, where
the agents have preferences over the houses, and we have to allocate the
houses to the agents so that each agent receives exactly one house and each
house is allocated to at most one agent.111Notice that these requirements
immediately imply that we must have $m\geq n$, and under any allocation,
exactly $n$ houses are allocated and the remaining $m-n$ houses remain
unallocated. The problem captures scenarios such as assigning clients to
servers, employees to offices, families to government housing, and so on. We
may think of the house allocation problem as a one-sided matching problem.
Several variants of house allocation have been studied in the matching-under-
preferences literature [Manlove, (2013); Hylland and Zeckhauser, (1979); Zhou,
(1990)], where the typical objectives have been economic efficiency
requirements such as Pareto-optimality [Hylland and Zeckhauser, (1979);
Abraham et al., (2004)], rank maximality [Irving et al., (2006)] or
strategyproofness [Krysta et al., (2019)]. Another useful and desirable
objective in any resource allocation setting is _fairness_ , and we may
equally well think of the house allocation problem as a special case of the
fair division of indivisible goods setting, with the additional requirement
that each agent be allocated exactly one good. Given an allocation, say
$\phi:A\rightarrow H$, an agent $a$ envies $a^{\prime}$ if she values
$\phi(a^{\prime})$ more than $\phi(a)$. Finding “envy-free” allocations, i.e.,
ones where no agent envies another, is one of the main goals in fair division.
Fairness in house allocation, in particular, has been a topic of interest in
recent years [Gan et al., (2019); Kamiyama et al., (2021); Hosseini et al.,
(2023, 2024)].

In the context of the house allocation problem, note that if $n=m$, an envy-
free allocation exists if and only if there is a perfect matching in the
following bipartite graph: introduce a vertex for every agent and every house,
and let the vertex corresponding to an agent be adjacent to all the houses
that she values no less than any other house. Since every house must be
assigned when $n=m$, when an agent is assigned anything short of her best
option, she will be envious. Therefore, the existence of an envy-free
allocation can be determined efficiently in this situation using standard
algorithms for checking if a perfect matching exists.

The question is less obvious when $n<m$, i.e., when there are more houses than
agents. Indeed, one could work with the same bipartite graph, but it is
possible for the house allocation instance to admit an envy-free allocation
even though the bipartite graph does not have a perfect matching. Consider a
situation with three houses and two agents, where both agents value one house
above all else, and the other two equally. While the graph only captures the
contention on the highly valued house, it does not lead us directly to the
envy-free allocation that can be obtained by giving both agents the houses
that they value relatively less (but equally). It turns out that the question
of whether an envy-free allocation exists can be determined in polynomial time
even when $n<m$, by an algorithm of [Gan et al., (2019)] that involves
iteratively removing subsets of contentious houses.

When an envy-free allocation does not exist at all, the natural objective is
to resort to a relaxation of the fairness objective. However, house allocation
differs from the typical fair division setting, with an additional constraint
that every agent receive exactly one item. This constraint renders the well-
studied relaxed notions of fairness like envy-freeness up to ‘some’ good
(where an agent chooses to hypothetically ignore one good from the envied
bundle) futile. Hence we resort to a different kind of relaxation of envy-
freeness: We _quantify_ the envy involved in an allocation using different
aggregate measures such as the number of envious agents, the maximum number of
agents any agent envies, and look for allocations that minimize these
“measures of envy.” We note that Nguyen and Rothe, (2013) and Shams et al.,
(2021) previously studied minimizing aggregate measures of envy in resource
allocation problems. In the context of house allocation, Kamiyama et al.,
(2021) studied the problem of minimizing the number of envious agents. They
showed that it is $\mathsf{NP}$-complete to find allocations that minimize the
number of envious agents, even for binary utilities, and this quantity is hard
to approximate for general utilities. In this paper, we explore envy
minimization in house allocation from a broader perspective and prove
algorithmic results not only for minimizing the number of envious agents but
for two other measures of envy as well—minimizing the amount of maximum envy
experienced by any agent and minimizing the amount of total envy experienced
by all the agents put together. We say that the _amount of envy_ experienced
by an agent $a$ is the number of agents she is envious of.

We remark here that minimizing the number of envious agents may lead to a sub-
optimal allocation in terms of maximum envy and vice-versa. For instance,
consider an instance with $4$ agents $a,b,c,d$ and $4$ houses
$h_{1},h_{2},h_{3},h_{4}$ with the following rankings:

$a:$ | $\mathbf{h_{1}}\succ h_{2}\succ h_{3}\succ h_{4}$
---|---
$b:$ | $h_{1}\succ h_{2}\succ h_{3}\succ\mathbf{h_{4}}$
$c:$ | $\mathbf{h_{2}}\succ h_{3}\succ h_{4}\succ h_{1}$
$d:$ | $\mathbf{h_{3}}\succ h_{4}\succ h_{1}\succ h_{2}$

Consider the highlighted allocation, denoted as $\phi$. Only agent $b$
experiences envy under $\phi$. This allocation effectively minimizes the
number of envious agents. However, the envy experienced by the sole envious
agent is substantial, as she envies all the other agents. Alternatively, the
envy of agent $b$ could have been reduced to just $1$ under the allocation
$\phi^{\prime}$, where agent $b$ receives house $h_{2}$ and agents $c$ and $d$
are allocated houses $h_{3}$ and $h_{4}$ respectively. While both $\phi$ and
$\phi^{\prime}$ are optimal in terms of minimizing overall total envy, $\phi$
falls short when it comes to addressing maximum envy, whereas $\phi^{\prime}$
is not ideal for minimizing the number of agents who experience envy. This
suggests that the three notions of envy minimization are not directly
comparable in general and, therefore demand individual scrutiny and analysis.

When our focus is on minimizing the envy, there can be a trade-off with
regards to social welfare, which is essentially the collective measure of
individual agent utilities within any allocation. The method for aggregating
these utilities can vary, including options such as the geometric mean (known
as Nash), the summation of utilities, or the minimum utility of any agent,
among others. We restrict our attention to the sum of the individual agent
utilities as our measure of social welfare for this work. For this measure,
the trade-off between welfare and envy-minimization is illustrated as follows.
Consider an instance with $2n-1$ houses such that each of the $n$ agents like
only the first $n-1$ houses. Then the only envy-free allocation is to allocate
the last $n$ houses to everyone, resulting in zero social welfare. On the
contrast, if we allow for envious agents, the above instance can achieve a
social welfare of at least $n-1$. This potential loss in welfare due to
fairness guarantees is captured by price of fairness, which is the worst-case
ratio of the maximum social welfare in any allocation to that in a fair
allocation. This notion was first proposed by Bertsimas et al., (2011),
following which there has been substantial progress towards finding the bounds
for the price for various combinations of fairness and welfare notions,
specifically in resource allocation setting [Caragiannis et al., (2012), Bei
et al., (2021), Barman et al., (2020), Sun et al., (2023), Bhaskar et al.,
(2023)]. To the best of our knowledge, this fairness-welfare trade-off has not
been looked at in the house allocation setting previously. In this work, we
give tight bounds for the price of fairness. Our investigation into PoF
inspired us to look at simultaneously minimizing all three envy-minimization
objectives while maximizing welfare. We show that we can indeed do this for
$m=n$ and binary valuations. In this setting, we establish that there is an
allocation that simultaneously maximizes welfare and minimizes the number of
envious agents, maximum envy, and total envy.

#### Our Contributions.

We propose to study the issue of “minimizing envy” from a broader perspective,
and to this end we consider three natural measures of the “amount of envy”
created by an allocation: a) the total number of agents who experience envy
(discussed above), b) the envy experienced by the _most_ envious agent, where
the amount of envy experienced by an agent is simply the number of agents that
she is envious of, and c) the total amount of envy experienced by all agents.
We refer to the questions of finding allocations that minimize these three
measures of envy the Optimal House Allocation (OHA), Egalitarian House
Allocation (EHA), and Utilitarian House Allocation (UHA) problems,
respectively. The following is a summary of our main results and how they are
obtained (c.f. Table 1).

Hardness Results. We show (parameterized) hardness of OHA and EHA even under
highly restricted input settings. We show that OHA is $\mathsf{NP}$-complete
even on instances where every agent values at most two houses. Further, it is
$\mathsf{W}[1]$-hard when parameterized by $k$, the number of agents who are
allowed to be envious (which implies that it is unlikely to admit a
$f(k)(n+m)^{O(1)}$ time algorithm). These results require two separate
reductions, where the latter result can be viewed as a reformulation of the
$\mathsf{NP}$-completeness result of Kamiyama et al., (2021). As for EHA, we
show that it is $\mathsf{NP}$-complete, even on instances where every agent
values at most two houses _and_ every house is approved by a constant number
of agents. In fact, we achieve this hardness even when the maximum allowed
envy is just _one_ , establishing that the problem is para-$\mathsf{NP}$-hard
when parameterized by $k$, the maximum envy (which implies that it is NP-hard
even for a constant value of the parameter). The (parameterized) complexity of
UHA, however, remains open.

Algorithmic and Experimental Results. Despite the hardness results even under
the restricted input settings mentioned above, we explore tractable scenarios
and prove a number of positive results. Observe that in a given instance, the
number of houses$(m)$ could be much larger than the number of agents($n$). But
we show that all three problems admit _polynomial-time pre-processing
algorithms_ that reduce the number of houses; in particular, after this pre-
processing, we will have the guarantee that $m\leq 2(n-1)$. This result, in
parameterized complexity parlance, means that all three problems admit
_polynomial kernels_ when parameterized by the number of agents. To prove
this, we use a popular tool called the _expansion lemma_. While the kernels
are interesting in their own right, we also leverage them to design
polynomial-time algorithms for all three problems on _extremal_ instances. An
instance of OHA/EHA/UHA is extremal if the houses can be ordered in such a way
that every agent values either the first few houses or the last few houses in
the ordering; that is, there is an ordering $(h_{1},h_{2},\ldots,h_{m})$ of
the houses such that for every agent $a$, there is an index $i(a)$ with $0\leq
i(a)\leq m$ such that $\mathcal{P}(a)=\\{h_{1},h_{2},\ldots,h_{i(a)}\\}$ or
$\mathcal{P}(a)=\\{h_{m},h_{m-1},\ldots,h_{m-i(a)}\\}$. We note here that
extremal instances, although restrictive, form a non-trivial subclass for
demonstrating tractability and have been studied in the literature [Elkind and
Lackner, (2015)]. In fact, despite the relatively simple structure of the
preference profile, the obvious greedy approaches do not work and the three
problems require three different lines of arguments. Finally, we show that
both OHA and EHA are fixed-parameter tractable ($\mathsf{FPT}$)222FPT w.r.t a
parameter $\ell$ means the instance can be decided in time
$f(\ell)\cdot(n+m)^{\mathcal{O}(1)}$, where $f$ is an arbitrary computable
function. when parameterized by the total number of house types or agent
types; two agents are of the same type if they both like the same set of
houses, and two houses are of the same type if they are both liked by the same
set of agents. Notice that the number of (house or agent) types could
potentially be much smaller than $m$ or $n$. The $\mathsf{FPT}$ algorithms are
obtained using ILP formulations with a bounded number of variables and
constraints (for UHA, we obtain an integer quadratic program). The ILPs may
also be of independent practical value. We implemented our ILPs for OHA and
EHA over synthetic datasets of house allocation, generated uniformly at
random. For a fixed number of houses and agents, the results show that the
number of envious agents and the maximum envy decreases as the number of agent
types (the maximum number of agents with distinct valuations) increases.
Instances with identical valuations seem to admit more envy, attributed to the
contention on the specific subset of houses. Also, when we increase the number
of houses, for a constant number of agents and agent-types, the envy
decreases, which is as expected, because of the increase in the number of
choices and the fact that some houses (the more contentious ones) remain
unallocated.

Price of Fairness. Along with different measures of envy, we also focus on the
social welfare of an allocation, as captured by the sum of the individual
agent utilities. Minimizing the measures of envy can lead to economically
inefficient allocations with poor social welfare. For example, an allocation
that only allocates the “dummy houses” (i.e., houses that no agent values) is
trivially envy-free, but has zero social welfare. Quantifying this welfare
loss, incurred as the cost of minimizing envy is, therefore, an imperative
consideration. We quantify this trade-off between welfare and envy
minimization using a metric called the _price of fairness (PoF)_ ; each
measure of envy leads to its corresponding PoF, and we defer a formal
definition of PoF to Section 8. We prove several tight bounds for PoF for
binary valuations. In particular, we show that when $m>n$, PoF can be as large
as the number of agents and that the bound is tight, for all the three envy
measures of envy. We also identify the instances where no welfare has to be
sacrificed in order to minimize envy, and hence no price has to be paid. In
particular, we show that the price of fairness is $1$ for $m=n$ and binary
valuations and also for $m>n$ and binary doubly normalized valuations. We show
in particular that when $m=n$, there is an allocation that simultaneously
minimizes the number of envious agents, the maximum and total envy while
maximizing social welfare. Moreover, we can compute such an allocation in
polynomial time.

#### Related Work.

Shapley and Scarf, (1974) studied the house allocation model with existing
tenants, which holds crucial applications in domains like kidney exchanges.
Scenarios encompassing entirely new applicants, as well as mixed scenarios
with a few existing tenants have also been studied in the literature [Hylland
and Zeckhauser, (1979), Abdulkadiroğlu and Sönmez, (1999)], and their
practical implementations span diverse areas such as public housing and
college dormitory assignments, among others.

The notion of fairness in house allocation setting was initiated by Beynier et
al., (2019) who studied a local variant for an equal number of agents and
houses, where an agent can envy only those who are connected to her in a given
social network. Gan et al., (2019) studied envy-freeness when the number of
houses can be more than that of agents and gave an efficient algorithm that
returns an envy-free solution if it exists. When such solutions do not exist,
Kamiyama et al., (2021) initiated the study of finding allocations that
minimize the number of agents who experience envy and showed that it is
$\mathsf{NP}$-complete to find allocations that minimize the number of envious
agents, even for binary utilities, and this quantity is hard to approximate
for general utilities. Further, Aigner-Horev and Segal-Halevi, (2021) study
the relaxed variant of assigning at most one house to every agent and give an
$O(m\sqrt{n})$ algorithm for finding an envy-free matching of maximum
cardinality in the setting of binary utilities. Shende and Purohit, (2020)
studied envy-freeness in conjunction with strategy-proofness. In more recent
work, Hosseini et al., (2023, 2024) have considered minimizing the sum of all
pairwise envy values over all edges in a social network. They proved
structural and computational results for various classes of underlying graphs
on agents. Choo et al., (2024) discussed house allocations in the context of
subsidies and showed that finding envy-free allocations with minimum subsidy
is hard in general but tractable if agents have identical utilities or $m$
differs from $n$ by an additive constant.

#### Organization of the paper.

We discuss the results for OHA, EHA, and UHA in Section 4, Section 5, and
Section 6 respectively. We discuss the experiments in Section 7. Finally, we
discuss the price of fairness in Section 8, which is largely independent of
all the other sections.

| Cardinal |
---|---|---
|  | Binary |
| General | General | Extremal Intervals | d = 1 | d = 2 | Rankings
OHA |  [HTML]EFEFEF NP-Complete (by implication) |  [HTML]ECCECE NP-Complete ($\dagger$) from Clique (Theorem 4.9) |  [HTML]B3E7B4 P (Theorem 4.1) |  [HTML]B3E7B4 P (Theorem 4.4) |  [HTML]ECCECE NP-Complete from Clique (Theorem 4.11) |  [HTML]ECCECE NP-Complete from Balanced Biclique (Theorem 4.13)
EHA |  [HTML]EFEFEF  | NP-Complete
---
(by implication)
[HTML]B3E7B4 P (Theorem 5.1) |  [HTML]B3E7B4 P (Theorem 5.3) |  [HTML]ECCECE NP-Complete ($\star$) from Independent Set (Theorem 5.5) |  [HTML]ECCECE NP-Complete ($\star$) from Multi-Colored Independent Set (Theorem 5.7)
UHA |  [HTML]FFFFC7 ? |  [HTML]B3E7B4 P (Theorem 6.1) |  [HTML]B3E7B4 P (Corollary 6.6) |  [HTML]FFFFC7 ?

Table 1: A partial summary of our results. Here, $d$ denotes the maximum
number of houses approved by any agent. The results marked with a $\star$
refer to reductions that imply hardness even when the standard parameter is a
constant, while the result marked with a $\dagger$ is a FPT reduction and also
implies W[1]-hardness in the standard parameter.

##  2 Preliminaries

Let $[k]$ denote the set $\\{1,2,\ldots,k\\}$ for any positive integer $k$.

An instance $\mathcal{I}$ of the House Allocation problem (HA) comprises a set
$A=$ $\left\\{a_{1},a_{2},\ldots,a_{n}\right\\}$ of agents and a set
$H=\left\\{h_{1},h_{2},\ldots,h_{m}\right\\}$ of houses. An assignment or
house allocation is an injection $\phi:A\rightarrow H$. Throughout this
section, let $\phi$ be an arbitrary but fixed allocation. While we make all
our notation explicit with respect to $\phi$, during future discussions, the
subscript $\phi$ may be dropped if the allocation is clear from the context.
There are a few different ways in which agents may express their preferences
over houses, and we focus here on both linear orders as well as cardinal
utilities.

#### Rankings

In this setting, each agent $a\in A$ has a linear order $\succ_{a}$ over the
set of houses $H$. We will typically use $\succ_{i}$ to denote333In some of
the reductions, the indices of the agents in $A$ are different from $[n]$, and
we continue to adopt the convention that $\succ_{\circ}$ is used to describe
the preferences of the agent $a_{\circ}$. the preferences of agent $a_{i}$.
The _rank_ of a house $h$ in the order $\succ_{a}$ is one plus the number of
houses $h^{\prime}$ such that $h^{\prime}\succ_{a}h$. For example, if $m=3$
and $\succ_{a}$ is given by $h_{2}\succ h_{3}\succ h_{1}$, then the houses
$h_{2}$, $h_{3}$ and $h_{1}$ have ranks $1,2,$ and $3$ respectively. We denote
the rank of a house $h$ in an order $\succ$ by $rk(h,\succ)$. A ranking is
said to have ties ($rk(h,\succeq)$) if there is an agent who ranks some pair
of houses equally.

An agent $a\in A$ _envies_ an agent $b\in A$ under the allocation $\phi$ if
$\phi(a)\prec_{a}\phi(b)$, which is to say that $a$ perceives $\phi$ to have
allocated a house to $b$ that she ranks more than the one allocated to her. We
use $\mathcal{E}_{\phi}(a)$ to denote the set of agents $b$ such that $a$
envies $b$ in the allocation $\phi$.

An agent $a$ is _envy-free_ with respect to $\phi$ if there is no agent $b$
such that $a$ envies $b$. In other words, $\mathcal{E}_{\phi}(a)=\emptyset$.
An allocation $\phi$ is said to be _envy-free_ if all agents $a$ are envy-free
with respect to $\phi$. The _amount of envy_ experienced by an agent $a$ is
the number of agents she is envious of, that is, $|\mathcal{E}_{\phi}(a)|$ and
is denoted by $\kappa_{\phi}(a)$. Note that if an agent is envy-free, then the
amount of envy experienced by her is zero.

#### Binary Preferences

Preferences are said to be _binary_ if $u_{a}(h)\in\\{0,1\\}$ for all $a\in A$
and $h\in H$. We note here that binary utilities are a crucial subclass with
simple elicitation and several works in fair division and voting literature
have paid special attention to this case [Halpern et al., (2020); Barman et
al., (2018); Lackner and Skowron, (2023)]. A house is called a _dummy_ house
if the utility of every agent for it is zero, that is, $u_{a}(h)=0$ for all
$a\in A$. The set of dummy houses is denoted by $D$.

As previously, an agent $a\in A$ _envies_ an agent $b\in A$ under the
allocation $\phi$ if $u_{a}(\phi(a))<u_{a}(\phi(b))$, which is to say that $a$
perceives $\phi$ to have allocated a house to $b$ that she values more than
the one allocated to her. That is, $u_{a}(\phi(a))=0$ but $u_{a}(\phi(b)=1$.
The definition of $\mathcal{E}_{\phi}(a)$ and the notion of _envy-freeness_ is
the same as before. The amount of envy experienced by an agent is
$|\mathcal{E}_{\phi}(a)|$. Just as with rankings, if an agent is envy-free,
then the amount of envy experienced by her is zero.

Let $\mathcal{P}$ be a profile of binary utilities of agents $A$ over houses
$H$. For an agent $a\in A$, use $\mathcal{P}(a)$ to denote the set of houses
$h$ for which $u_{a}(h)=1$. We say that these are houses that are valued by
the agent $a$. For a subset $S\subseteq A$, we use $\mathcal{P}(S)$ to denote
$\cup_{a\in S}\mathcal{P}(a)$. Similarly, for a house $h$, we use
$\mathcal{T}(h)$ to refer to the set of agents who value $h$, and for a subset
$S\subseteq H$, we use $\mathcal{T}(S)$ to denote $\cup_{h\in
S}\mathcal{T}(h)$.

Two agents $a_{p}$ and $a_{q}$ are said to be of the same type if
$\mathcal{P}(a_{p})=\mathcal{P}(a_{q})$ and two houses $h_{p}$ and $h_{q}$ are
said to be of the same type $\mathcal{T}(h_{p})=\mathcal{T}(h_{q})$. For an
instance with $n$ agents and $m$ houses, we use $n^{\star}$ and $m^{\star}$ to
denote the number of distinct types of agents and houses, respectively.

The _preference graph_ $G$ based on $\mathcal{P}$ is a bipartite graph defined
as follows: the vertex set of $G$ consists of one vertex $v_{a}$ corresponding
to every agent $a\in A$ and one vertex $v_{h}$ corresponding to every house
$h\in H$; and $(v_{a},v_{h})$ is an edge in $G$ if and only if $a$ values $h$.
We use $d(\mathcal{P})$ to denote the maximum number of houses that are valued
by any agent and $d^{\prime}(\mathcal{P})$ to denote the maximum number of
agents who value a house. In other words, $d(\mathcal{P})$ is the maximum
number of ones in any row of $U_{\mathcal{P}}$, while
$d^{\prime}(\mathcal{P})$ is the maximum number of ones in any column of
$U_{\mathcal{P}}$. We call a profile $\mathcal{P}$ _row-sparse_ if
$d(\mathcal{P})$ is bounded by a constant and _column-sparse_ if
$d^{\prime}(\mathcal{P})$ is bounded by a constant.

Extremal Interval Structure. We say that $\mathcal{P}$ has an _extremal
interval structure with respect to houses_ if there exists an ordering
$\sigma$ of the houses such that for every agent $a$, $\mathcal{P}(a)$ forms a
prefix or suffix of $\sigma$ [Elkind and Lackner, (2015)]. Further, we say
that $\mathcal{P}$ has a _left (respectively, right) extremal interval
structure with respect to houses_ if there exists an ordering $\sigma$ of the
houses such that for every agent $a$, $\mathcal{P}(a)$ forms a prefix
(respectively, suffix) of $\sigma$.
Analogously, $\mathcal{P}$ has an _extremal interval structure with respect to
agents_ if there exists an ordering $\pi$ of the agents such that for every
house $h$, the set of agents who value $h$ forms a prefix or suffix of $\pi$.
The notions of left and right extremal interval structures here are also
defined as before. In our discussions, whenever we speak of an _extremal
interval structure_ without explicit qualification, it is with respect to
houses unless mentioned otherwise.

#### Optimization Objectives

We focus on the following optimization objectives.

  1. 1.

The _number of envious agents_ in an allocation $\phi$ is the number of agents
$a\in A$ for which $\kappa_{\phi}(a)\geq 1$ and will be denoted by
$\kappa^{\\#}(\phi)$. Further, given an instance $\mathcal{I}$ of the house
allocation problem, we use $\kappa^{\\#}(\mathcal{I})$ to denote the number of
envious agents in an optimal allocation, that is,
$\kappa^{\\#}(\mathcal{I}):=\min_{\phi}(\kappa^{\\#}(\phi))$.

  2. 2.

The _maximum envy_ generated by $\phi$ is $\max_{a\in A}\kappa_{\phi}(a)$ and
is denoted by $\kappa^{\dagger}(\phi)$. As before, given an instance
$\mathcal{I}$ of the house allocation problem, we use
$\kappa^{\dagger}(\mathcal{I})$ to denote the maximum envy in an optimal
allocation, that is,
$\kappa^{\dagger}(\mathcal{I}):=\min_{\phi}(\kappa^{\dagger}(\phi))$.

  3. 3.

The _total envy_ generated by $\phi$ is $\sum_{a\in A}\kappa_{\phi}(a)$ and
will be denoted by $\kappa^{\star}(\phi)$. Again, given an instance
$\mathcal{I}$ of the house allocation problem, we use
$\kappa^{\star}(\mathcal{I})$ to denote the total envy in an optimal
allocation, that is,
$\kappa^{\star}(\mathcal{I}):=\min_{\phi}(\kappa^{\star}(\phi))$.

#### Computational Questions

We now formulate the computational problems that we would like to address.

Optimal House Allocation Input: A set $A=$
$\left\\{a_{1},a_{2},\ldots,a_{n}\right\\}$ of agents and a set
$H=\left\\{h_{1},h_{2},\ldots,h_{m}\right\\}$ of houses, a preference profile
describing the preferences of all agents over houses, and a non-negative
integer $k\in\mathbb{Z}^{+}$. Question: Determine if there is an allocation
$\phi$ that minimizes the number of envious agents, i.e,
$\kappa^{\\#}(\phi)\leq k$.

Egalitarian House Allocation Input: A set $A=$
$\left\\{a_{1},a_{2},\ldots,a_{n}\right\\}$ of agents and a set
$H=\left\\{h_{1},h_{2},\ldots,h_{m}\right\\}$ of houses, a preference profile
describing the preferences of all agents over houses, and a non-negative
integer $k\in\mathbb{Z}^{+}$. Question: Determine if there is an allocation
$\phi$ that minimizes the maximum envy, i.e, $\kappa^{\dagger}(\phi)\leq k$.

Utilitarian House Allocation Input: A set $A=$
$\left\\{a_{1},a_{2},\ldots,a_{n}\right\\}$ of agents and a set
$H=\left\\{h_{1},h_{2},\ldots,h_{m}\right\\}$ of houses, a preference profile
describing the preferences of all agents over houses, and a non-negative
integer $k\in\mathbb{Z}^{+}$. Question: Determine if there is an allocation
$\phi$ that minimizes the total envy, i.e, $\kappa^{\star}(\phi)\leq k$.

We use $[\succ]$-OHA, $[\succeq]$-OHA, and $[\nicefrac{{0}}{{1}}]$-OHA to
denote the versions of the OHA problem when the preferences are given,
respectively, by linear orders, rankings with ties, and binary utilities,
respectively. We adopt this convention for EHA and UHA as well.

We note that for all three problems, the question of finding an envy-free
allocation, i.e., one for which the optimization objective attains the value
zero, is a natural special case. This amounts to finding an allocation where
no agent has any envy for another and is therefore resolved (for both binary
valuations and rankings) by the algorithm of Gan et al., (2019) which uses an
approach based on iteratively eliminating subsets that violate Hall’s
condition in the preference graph.

We also observe here that all three problems are tractable for the special
case when $m=n$. We assume, without loss of generality, that every agent
values at least one house. Observe that since $n=m$, all valid allocations
have no unallocated houses.

######  Proposition 2.1 (folklore).

$[\nicefrac{{0}}{{1}}]$-Optimal House Allocation and $[\succ]$-Optimal House
Allocation can be solved in polynomial time if $m=n$.

######  Proof 2.2.

Let $\mathcal{I}:=(A,H,\mathcal{P};k)$ be an instance of
$[\nicefrac{{0}}{{1}}]$-OHA and let $G=(A\cup H;E)$ be the associated
preference graph. We obtain an optimal allocation in polynomial time, and we
return an appropriate output based on how the value of the optimum compares
with $k$.

Let $M$ be a maximum matching in $G$. We claim that any optimal allocation for
$\mathcal{I}$ has $|M|$ envy-free agents. To see that there exists an
allocation that has at least $|M|$ envy-free agents, consider the allocation
that gives the house $M(a)$ to every agent $a$ saturated by $M$, and allocates
the remaining houses arbitrarily among the agents not saturated by $M$. It is
easy to see that this allocation has at least $|M|$ envy-free agents, namely
the ones corresponding to those saturated by the matching $M$. On the other
hand, suppose there is an allocation $\phi$ with $k$ envy-free agents, then
the envy-free agents must have received houses that they value—indeed,
consider any agent $a$, and let $h$ be any house that $a$ values. If $a$ does
not value the house $\phi(a)$, then $a$ envies the agent who received the
house $h$. Therefore, the set:

$M:=\\{(a,\phi(a))\leavevmode\nobreak\ |\leavevmode\nobreak\ a\text{ is envy-
free with respect to }\phi\\}$

corresponds to a matching with $k$ edges in $G$, and this concludes the
argument. Notice that this argument extends to weak orders by the natural
extension of the notion of a preference graph: we have that an agent $a$ is
adjacent to all houses $h$ that she prefers over all other houses. Therefore,
we have the claim $[\succ]$-OHA as well.

######  Proposition 2.3.

$[\nicefrac{{0}}{{1}}]$-Egalitarian House Allocation and $[\succ]$-Egalitarian
House Allocation can be solved in polynomial time if $m=n$.

######  Proof 2.4.

Let $\mathcal{I}:=(A,H,\mathcal{P};k)$ be an instance of
$[\nicefrac{{0}}{{1}}]$-EHA. We show that this problem reduces to finding a
perfect matching among high-degree agents in the preference graph, based on
the following observations.

  1. 1.

Suppose $a$ is an agent who values at most $k$ houses. Then, the amount of
envy experienced by $a$ is at most $k$ in _any_ allocation.

  2. 2.

Suppose $a$ is an agent who values at least $k+1$ houses. Then, if $\phi$ is a
valid solution, then $a$ must value the house $\phi(a)$.

It follows that $\mathcal{I}$ is a Yes-instance if and only if the projection
of the preference graph $G$ on $(A^{\star}\cup H)$ admits a perfect matching,
where $A^{\star}$ is the subset of agents whose degree in $G$ is at least
$k+1$.

Now, let $\mathcal{I}:=(A,H,\mathcal{P};k)$ be an instance of $[\succ]$-EHA.
Consider the bipartite graph $G=(A\cup H;E^{\star})$, where $(a,h)$ is an edge
if and only if the rank of $h$ is at most $k+1$ in $\succ_{a}$. We claim that
$\mathcal{I}$ is a Yes-instance if and only if $G$ has a perfect matching.

Indeed, observe that the amount of envy experienced by any agent $a$ with
respect to an allocation $\phi$ is exactly one less than the rank of $\phi(a)$
in $\succ_{a}$. Therefore, if $\phi$ is an allocation whose maximum envy is
$k$, then the rank of $\phi(a)$ in $\succ_{a}$ must be at most $k+1$ for all
agents $a$. It is easy to check that such allocations are in one-to-one
correspondence with perfect matchings in the graph $G$.

######  Proposition 2.5.

$[\nicefrac{{0}}{{1}}]$Utilitarian House Allocation and $[\succ]$-Utilitarian
House Allocation can be solved in polynomial time if $m=n$.

######  Proof 2.6.

Let $\mathcal{I}:=(A,H,\mathcal{P};k)$ be an instance of
$[\nicefrac{{0}}{{1}}]$-UHA. To begin with, let $d(a)$ denote the degree of
$a$ in the preference graph $G$ of $\mathcal{I}$. Now consider a complete
bipartite graph $G^{\star}$ with bi-partition $(A\uplus H)$ and a cost
function $c$ on the edges defined as follows:

$c({\color[rgb]{.185,.31,.31}\definecolor[named]{pgfstrokecolor}{rgb}{.185,.31,.31}(a,h)})=\begin{cases}d(a)&\text{if
}a\text{ does not value }h,\\\ 0&\text{otherwise.}\end{cases}$

Let $M$ be a minimum cost perfect matching in $G$ with total cost $t$. We
claim that $\mathcal{I}$ is a Yes-instance if and only if $t\leq k$. In the
forward direction, if $\phi$ is an allocation with total envy at most
$\kappa^{\star}$, then consider the following perfect matching in $G$:

$M:=\\{(a,\phi(a))\leavevmode\nobreak\ |\leavevmode\nobreak\ a\in A\\}$

Notice that the cost of $M$ corresponds exactly to $\kappa^{\star}(\phi)$, the
total amount of envy in $\phi$. This shows that there is a perfect matching in
$G^{\star}$ with cost at most $k$.

On the other hand, let $M$ be a perfect matching in $G^{\star}$ with the cost
at most $k$, and let $M(a)$ denote the house $h$ such that $(a,h)\in M$. Then
consider the allocation $\phi$ given by $\phi(a)=M(a)$ for all agents $a$.
Notice that every zero-cost edge in $M$ corresponds to an envy-free agent with
respect to $\phi$, and every other edge $e=(a,h)$ corresponds to an agent in
$\phi$ who was allocated a house she did not value. Observe that the amount of
envy experienced by $a$ in $\phi$ is the number of houses she values, in other
words, $d(a)$; however, this is also exactly the cost of the edge $e$.
Therefore, it follows that the amount of envy in $\phi$ is exactly equal to
the cost of the matching $M$, and this concludes the proof of our claim.

Now, let $\mathcal{I}:=(A,H,\mathcal{P};k)$ be an instance of $[\succ]$-UHA.
As before, consider a complete bipartite graph $G^{\star}$ with bipartition
$(A\uplus H)$. This time, we have the cost function $c$ on the edges defined
as
$c({\color[rgb]{.185,.31,.31}\definecolor[named]{pgfstrokecolor}{rgb}{.185,.31,.31}(a,h)})=rk(h,\succ_{a})-1$.
This cost reflects the envy experienced by the agent $a$ if she were to be
allocated the house $h$. Using arguments similar to the setting of binary
valuations, it is easily checked that $\mathcal{I}$ is a Yes-instance if and
only if there is a perfect matching in $G^{\star}$ whose cost is at most $k$.

#### Parameterized Complexity

Parameterized algorithms or multi-variate analysis is a popular perspective in
the context of “coping with computational hardness”. The key idea here is to
segregate the running time of our algorithms into two parts: one that is
polynomially bounded in the size of the entire input so that it is efficient
on a quantity that is expected to be large in practice and the other, a
computable function of a carefully chosen _parameter_ —and this component of
the running time remains feasible in practice because the parameter is
expected to be small. The parameterized perspective also allows us to
formalize ideas about efficient preprocessing, and this is now an active
subfield in its own right. We refer the readers to the books Cygan et al.,
(2015) and Downey and Fellows, (2013) for additional background on this
algorithmic paradigm, while recalling here only the key definitions relevant
to our discussions.

Formally, a parameterized problem $L$ is a subset of
$\Sigma^{*}\times\mathbb{N}$ for some finite alphabet $\Sigma$. An instance of
a parameterized problem consists of $(x,k)$, where $k$ is called the
parameter. A central notion in parameterized complexity is fixed-parameter
tractability (FPT), which means for a given instance $(x,k)$ solvability in
time $f(k)\cdot p(|x|)$, where $f$ is an arbitrary function of $k$ and $p$ is
a polynomial in the input size. The notion of kernelization is defined as
follows.

######  Definition 2.7.

A kernelization algorithm, or in short, a kernel for a parameterized problem
$Q\subseteq\Sigma^{*}\times\mathbb{N}$ is an algorithm that, given
$(x,k)\in\Sigma^{*}\times\mathbb{N}$, outputs in time polynomial in $|x|+k$ a
pair $\left(x^{\prime},k^{\prime}\right)\in\Sigma^{*}\times\mathbb{N}$ such
that (a) $(x,k)\in Q$ if and only if $\left(x^{\prime},k^{\prime}\right)\in Q$
and (b) $\left|x^{\prime}\right|+k^{\prime}\leq g(k)$, where $g$ is an
arbitrary computable function. The function $g$ is referred to as the size of
the kernel. If $g$ is a polynomial function then we say that $Q$ admits a
polynomial kernel.

On the other hand, we also have a well-developed theory of parameterized
hardness. We call a problem para-NP-hard if it is NP-hard even for a constant
value of the parameter. Further, we have the notion of _parameterized
reductions_ , defined as follows.

######  Definition 2.8 (Parameterized reduction).

Let $A,B\subseteq\Sigma^{*}\times\mathbb{N}$ be two parameterized problems, A
parameterized reduction from $A$ to $B$ is an algorithm that, given an
instance $(x,k)$ of $A$, outputs an instance
$\left(x^{\prime},k^{\prime}\right)$ of $B$ such that:

1\. $(x,k)$ is a yes-instance of $A$ if and only if
$\left(x^{\prime},k^{\prime}\right)$ is a yes-instance of $B$.

2\. $k^{\prime}\leq g(k)$ for some computable function $g$, and

3\. the running time is $f(k)\cdot|x|^{O(1)}$ for some computable function
$f$.

A parameterized reduction from a problem known to be $\mathsf{W}[1]$-hard is
considered to be strong evidence that the target problem is not
$\mathsf{FPT}$. The formal definition of W-hardness is beyond the scope of
this discussion, but we state in this section the known W-hard problems from
which we will perform parameterized reductions to obtain our results.

We also note that an instance of integer linear programming is $\mathsf{FPT}$
in the number of variables.

######  Theorem 2.9 (Lenstra Jr., (1983)).

An integer linear programming instance of size $L$ with $p$ variables can be
solved using $\mathcal{O}\left(p^{2.5p+o(p)}\cdot\left(L+\log
M_{x}\right)\log\left(M_{x}M_{c}\right)\right)$ arithmetic operations and
space polynomial in $L+\log M_{x}$, where $M_{x}$ is an upper bound on the
absolute value a variable can take in a solution, and $M_{c}$ is the largest
absolute value of a coefficient in the vector $c$.

Finally, we state some of the problems that we will use in the reductions. We
note that all the problems below are $\mathsf{W}[1]$-hard when parameterized
by $k$.

Clique (respectively, Independent Set)

Input: A graph $G$ and an integer $k$.

Question: Does there exist a subset $S\subseteq V(G)$ such that $G[S]$ is a
clique (respectively, independent set) and $|S|\geq k$?

Balanced Biclique
Input: A graph $G=(L\cup R,E)$ and an integer $k$.

Question: Does there exist a subset $S\subseteq L$ and $T\subseteq R$ such
that $G[S\cup T]$ is a biclique and $|S|=|T|=k$?

Multi-Colored Independent Set
Input: A graph $G=(V_{1}\uplus\cdots\uplus V_{k},E)$.

Question: Does there exist a subset $S\subseteq V(G)$ such that $G[S]$ is an
independent set and $|V_{i}\cap S|=1$ for all $i\in[k]$?

##  3 Pre-processing using Expansion Lemma

In this section, we introduce the expansion lemma, which is a powerful and
popular tool for kernelization. Let $G$ be a bipartite graph with vertex bi-
partitions $(A,B)$. A set of edges $M\subseteq E(G)$ is called an _expansion_
of $A$ into $B$ if:

  * •

every vertex of $A$ is incident to exactly one edge of $M$;

  * •

$M$ saturates exactly $|A|$ vertices in $B$.

Note that an expansion saturates all vertices of $A$.

######  Lemma 3.1 (Expansion lemma Cygan et al., (2015)).

Let $G$ be a bipartite graph with vertex bi-partitions $(A,B)$ such that

  1. 1.

$|B|\geq|A|$, and

  2. 2.

there are no isolated vertices in $B$.

Then there exist non-empty vertex sets $X\subseteq A$ and $Y\subseteq B$ such
that

  * •

there is an expansion of $X$ into $Y$, and

  * •

no vertex in $Y$ has a neighbor outside $X$, that is, $N(Y)\subseteq X$.

Furthermore, the sets $X$ and $Y$ can be found in time polynomial in the size
of $G$.

We now consider an instance $\mathcal{I}=(A,H,\mathcal{P})$ of HA with binary
valuations parameterized by $k$, where $k$ is one of $\kappa^{\\#}$,
$\kappa^{\dagger}$ or $\kappa^{\star}$. We introduce two reduction rules here
whose implementation is parameter-agnostic. We argue the safety of these
reduction rules separately for the three parameters in Theorems 4.15, 5.11 and
6.7, respectively.

Let $G=(A\cup H;E)$ denote the preference graph of $\mathcal{I}$. Note that we
may assume that we have at most $(n-1)$ dummy houses in the instance
$\mathcal{I}$, since instances with at least $n$ dummy houses admit trivial
envy-free allocations, where every agent is given a dummy house. We make this
explicit in the following reduction rule:

If $\mathcal{I}$ has at least as many dummy houses as agents, then return a
trivial Yes-instance. The parameter $k$ is unchanged.

Let $G^{\star}$ denote the preference graph induced by $A\cup(H\setminus D)$,
where $D$ denotes the vertices corresponding to dummy houses in $\mathcal{I}$.
We now propose the following reduction rule based on the expansion lemma.

In $\mathcal{I}$, if $|H\setminus D|\geq|A|$, then let $(X,Y)$ be as given by
Lemma 3.1 applied to $G^{\star}$, and let $M\subseteq E(G^{\star})$ be the
associated expansion. Proceed by eliminating all agents and houses saturated
by $M$. The parameter $k$ is unchanged.

Note that once Reduction Rules 3 and 3 are applied exhaustively, we have that:

$|H|=|H\setminus D|+|D|\leq 2\cdot(|A|-1),$

where we are slightly abusing notation and using $H$ and $A$ to denote the
houses and agents in the reduced instance. Thus, once the safety of these
reduction rules is established, we conclude that all the three problems under
consideration—OHA, EHA and UHA—admit polynomial kernels with
$\mathcal{O}({|{A}|})$ houses when parameterized by the number of agents.

We make a claim here that will be useful in the arguments that we make later
about the safety of Section 3.

######  Definition 3.2.

Let $(A,H,\mathcal{P})$ and $X,Y$ and $M$ be as in the premise of Reduction
Rule 3. An allocation $\phi$ is said to be _nice_ if $\phi(a)=M(a)$ for all
$a\in X$, where $M(a)$ denotes the unique vertex $h\in Y$ such that $(a,h)\in
M$.

######  Claim 1.

Let $(A,H,\mathcal{P})$ and $X,Y$ and $M$ be as in the premise of Section 3.
There is a nice allocation that minimizes the number of envious agents.

######  Proof 3.3.

Let $\phi$ be an allocation that minimizes the number of envious agents. If
$\phi$ is already nice then there is nothing to prove. Otherwise, suppose
$\phi(a)\neq M(a)$ for some $a\in X$. If $\phi$ does not assign the house
corresponding to $M(a)$ to any agent, then consider the modified allocation
$\phi^{\prime}$ where we assign $M(a)$ to $a$ while letting $\phi(a)$ become
an unassigned house, that is:

$\phi^{\prime}(c)=\begin{cases}M(a)&\text{if }c=a,\\\
\phi(c)&\text{otherwise.}\end{cases}$

On the other hand, suppose $b$ is such that $\phi(b)=M(a)$. Then consider the
modified allocation $\phi^{\prime}$ where we swap the houses of $a$ and $b$,
that is:

$\phi^{\prime}(c)=\begin{cases}M(a)&\text{if }c=a,\\\ \phi(a)&\text{if
}c=b,\\\ \phi(c)&\text{otherwise.}\end{cases}$

We keep modifying the original allocation $\phi$ in the manner described above
until we arrive at a nice allocation. Let $\phi^{\star}$ denote this final
allocation.

Now consider an agent $c\notin X$. We claim that the amount of envy
experienced by $c$ does not increase at any step of the process of morphing
$\phi$ to $\phi^{\star}$. Consider the following cases that arise at any step,
where $a\in X$ and by a slight abuse of notation, we use $\phi$ to denote the
allocation that is being modified:

  1. 1.

Suppose $M(a)$ is assigned to $a$ and $\phi(a)$ is unassigned. We know that
$c$ does not value $M(a)$ since $c\notin X$. If $c$ valued $\phi(a)$, then her
envy with respect to the new allocation will be one less than her envy with
respect to the previous allocation.

  2. 2.

Suppose $M(a)$ and $\phi(a)$ are swapped between agents $a$ and $b$; and
$c\neq b$. Then the amount of envy experienced by $c$ does not change.

  3. 3.

Suppose $M(a)$ and $\phi(a)$ are swapped between agents $a$ and $b$; and
$c=b$. If $c$ valued $\phi(a)$, then her envy with respect to the new
allocation will be less than her envy with respect to the previous allocation.
On the other hand, if $c$ does not value $\phi(a)$ then the amount of envy
experienced by $c$ does not change.

Also, in the final allocation $\phi^{\star}$, all agents in $X$ are envy-free,
since they are assigned houses that they value via the expansion $M$.
Therefore, the total number of envious agents in the final allocation
$\phi^{\star}$ is the same as the number of envious agents in the original
allocation $\phi$—recall that $\phi$ minimized the number of envious agents.

The following claims can be shown by the same argument that was used for 1,
since for any agent $a$, the amount of envy experienced by $a$ respect to in
$\phi^{\star}$ is at most the amount of envy experienced by $a$ with respect
to $\phi$.

######  Claim 2.

Let $(A,H,\mathcal{P})$ and $X,Y$ and $M$ be as in the premise of Section 3.
There is a nice allocation that minimizes the maximum envy.

######  Claim 3.

Let $(A,H,\mathcal{P})$ and $X,Y$ and $M$ be as in the premise of Section 3.
There is a nice allocation that minimizes total envy.

#### Applications to Extremal Instances

We observe several properties of instances $\mathcal{I}=(A,H,\mathcal{P};k)$
of $[\nicefrac{{0}}{{1}}]$-HA, where $\mathcal{P}$ has an extremal structure
(with respect to the houses). The properties are parameter-agnostic, and
therefore, hold for instances of $[\nicefrac{{0}}{{1}}]$-OHA,
$[\nicefrac{{0}}{{1}}]$-EHA and $[\nicefrac{{0}}{{1}}]$-UHA. As a shorthand,
we say that $I=(A,H,\mathcal{P};k)$ is an extremal instance (or simply
extremal) if $\mathcal{P}$ has the extremal property.

|  | Left-houses $(H_{L})$ | Dummy houses $(D)$ | Right-houses $(H_{R})$
---|---|---|---|---
|  | $h_{1}$ | $h_{2}$ | $h_{3}$ | $h_{4}$ | $h_{5}$ | $h_{6}$ | $h_{7}$ | $h_{8}$ | $h_{9}$ | $h_{10}$
Left-agents $(A_{L})$ | $a_{1}$ | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
$a_{2}$ | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
$a_{3}$ | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
$a_{4}$ | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0
$a_{5}$ | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0
Right-agents $(A_{R})$ | $a_{6}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1
$a_{7}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1
$a_{8}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1
$a_{9}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1
Table 2: An example of an extremal instance $\mathcal{I}=(A,H,\mathcal{P};k)$,
where $D\subseteq H$ denotes the dummy houses. Once Reduction Rules 3 and 3
are no longer applicable, then dummy houses must necessarily exist, i.e.,
$D\neq\emptyset$; and we must have ${|{H_{L}}|}<{|{A_{L}}|}$ and
${|{H_{R}}|}<{|{A_{R}}|}$.

Consider an extremal instance $\mathcal{I}=(A,H,\mathcal{P};k)$ of
$[\nicefrac{{0}}{{1}}]$-HA. That is, there is an ordering $\sigma$ of the
houses, say, $\sigma=(h_{1},\ldots,h_{m})$ such that for every agent $a\in A$,
there exists an index $i(a)\in[m]$ such that either
$\mathcal{P}(a)=\left\\{{h_{1},h_{2},\ldots,h_{i(a)}}\right\\}$ or
$\mathcal{P}(a)=\left\\{{h_{m},h_{m-1},\ldots,h_{m-{i(a)}}}\right\\}$. (See
Table 2 for an example.) If
$\mathcal{P}(a)=\left\\{{h_{1},h_{2},\ldots,h_{i(a)}}\right\\}$ for every
$a\in A$, then we say that the instance $\mathcal{I}$ is left-extremal. If
$\mathcal{P}(a)=\left\\{{h_{m},h_{m-1},\ldots,h_{m-{i(a)}}}\right\\}$ for
every $a\in A$, then we say that $\mathcal{I}$ is right-extremal.

We can check in polynomial time whether a given instance is
(left/right)-extremal, and if so, then find the ordering $\sigma$ on the
houses. Also, note that removing a subset of houses and agents from an
extremal instance does not destroy the extremal property. That is, if
$\mathcal{I}=(A,H,\mathcal{P})$ is extremal, then so is
$\mathcal{I^{\prime}}=(A^{\prime},H^{\prime},\mathcal{P}^{\prime})$, where
$A^{\prime}=A\setminus X$ and $H^{\prime}=H\setminus Y$ and
$\mathcal{P}^{\prime}$ is the restriction of $\mathcal{P}$ to $(A\cup
H)\setminus(X\cup Y)$. So, in particular, we can safely apply Section 3 to
extremal instances.

Now, consider an extremal instance $\mathcal{I}=(A,H,\mathcal{P};k)$, which is
irreducible with respect to Reduction Rules 3 and 3. Let
$\sigma=(h_{1},h_{2},\ldots,h_{m})$ be an extremal ordering on the houses. Let
$D\subseteq H$ be the set of dummy houses in $\mathcal{I}$. Then, we have seen
that ${|{H\setminus D}|}\leq n-1$. Therefore, $D\neq\emptyset$. Let
$h_{d},h_{d^{\prime}}\in D$ be such that $h_{d}$ is the first dummy house and
$h_{d^{\prime}}$ is the last dummy house in the ordering $\sigma$. It may be
the case that $d=d^{\prime}$. Then, for every $i$, where $d\leq i\leq
d^{\prime}$, the house $h_{i}$ is a dummy house. Let
$H_{L}=\left\\{{h_{1},h_{2},\ldots,h_{d-1}}\right\\}$ and
$H_{R}=\left\\{{h_{d^{\prime}+1},h_{d^{\prime}+2},\ldots,h_{m}}\right\\}$. We
call the houses in $H_{L}$ the left-houses and the houses in $H_{R}$ the
right-houses. And for every agent $a\in A$, either $\mathcal{P}(a)\subseteq
H_{L}$, in which case we call the agent $a$ a left-agent, or
$\mathcal{P}(a)\subseteq H_{R}$, in which case we call the agent $a$ a right-
agent. Let $A_{L}$ and $A_{R}$ respectively denote the set of left- and right-
agents. See Table 2. Thus, we have a partition of $A$ into $A_{L}$ and $A_{R}$
and a partition of $H$ into $H_{L},H_{R}$ and $D$. Notice now that if
${|{H_{L}}|}\geq{|{A_{L}}|}$ or ${|{H_{R}}|}\geq{|{A_{R}}|}$, then Section 3
would apply. We thus have ${|{A_{L}}|}>{|{H_{L}}|}$ and
${|{A_{R}}|}>{|{H_{R}}|}$. For an allocation ${{\phi}:{A}\rightarrow{H}}$ and
an agent $a\in A$, we say that $a$ is extremality-respecting under $\phi$ if
either (a) $a\in A_{L}$ and $\phi(a)\in H_{L}\cup D$ or (b) $a\in A_{R}$ and
$\phi(a)\in H_{R}\cup D$. We say that $\phi$ is extremality-respecting if
every agent is extremality-respecting under $\phi$. We now claim that there
exists an extremality-respecting optimal allocation, irrespective of whether
we are dealing with an instance of $[\nicefrac{{0}}{{1}}]$-OHA,
$[\nicefrac{{0}}{{1}}]$-EHA or $[\nicefrac{{0}}{{1}}]$-UHA.

######  Claim 4.

There exists an extremality-respecting optimal allocation.

######  Proof 3.4.

Let ${{\phi}:{A}\rightarrow{H}}$ be an optimal allocation that maximizes the
number of extremality-respecting agents. If $\phi$ is extremality-respecting,
then the claim trivially holds. So, assume not. Then, assume without loss of
generality that there exists $a\in A_{L}$ with $\phi(a)\in H_{R}$. (The case
when $a\in A_{R}$ with $\phi(a)\in H_{L}$) is symmetric. Since
${|{H_{R}}|}<{|{A_{R}}|}$, there exists an agent $a^{\prime}\in A_{R}$ such
that $\phi(a^{\prime})\notin H_{R}$. Then, $\phi(a^{\prime})\in H_{L}\cup D$.
Let $\phi^{\prime}$ be the allocation obtained by swapping the houses of $a$
and $a^{\prime}$. This house-swapping between $a$ and $a^{\prime}$ does not
cause any increase in the number of envious agents or the envy experienced by
any agent. So we have $\kappa^{\\#}(\phi^{\prime})\leq\kappa^{\\#}(\phi)$,
$\kappa^{\dagger}(\phi^{\prime})\leq\kappa^{\dagger}(\phi)$ and
$\kappa^{\star}(\phi^{\prime})\leq\kappa^{\\#}(\star)$. Therefore,
$\phi^{\prime}$ is optimal. In addition, note that
$\phi^{\prime}(a)=\phi(a^{\prime})\in H_{L}\cup D$, and
$\phi^{\prime}(a^{\prime})=\phi(a)\in H_{R}$, and hence, both $a$ and
$a^{\prime}$ are extremality-respecting under $\phi$. That is the number of
extremality-respecting agents under $\phi^{\prime}$ is strictly greater than
that in $\phi$, a contradiction.

######  Remark 3.5.

4 shows that whenever dealing with an instance $\mathcal{I}=(A,H,\mathcal{P})$
of $[\nicefrac{{0}}{{1}}]$-HA, where $\mathcal{I}$ is extremal, we only need
to look for an extremality-respecting optimal allocation, say $\phi$. Suppose
$n_{L}$ dummy houses get allocated to left-agents under $\phi$, and $n_{R}$
dummy houses get allocated to right-agents under $\phi$. Hence, we can guess
the pair $(n_{L},n_{R})$ and split $\mathcal{I}$ into two instances,
$\mathcal{I}_{L}$ and $\mathcal{I_{R}}$, where $\mathcal{I}_{L}$ consists of
the left-agents, the left-houses and $n_{L}$ dummy houses, and
$\mathcal{I}_{R}$ consists of the right-agents, the right-houses and $n_{R}$
dummy houses. Thus, $\mathcal{I}_{L}$ is left-extremal and $\mathcal{I}_{R}$
is right-extremal. And we only need to solve the problem separately on
$\mathcal{I}_{L}$ and $\mathcal{I}_{R}$. Notice that the number of guesses for
the pair $(n_{L},n_{R})$ is at most $n^{2}$. By reversing the ordering on the
houses in the instance $\mathcal{I}_{R}$, we can turn $\mathcal{I}_{R}$ into a
left-extremal instance as well. So, it suffices to solve the problem for left-
extremal instances. Hence, whenever dealing with an extremal instance
$\mathcal{I}$, we assume without loss of generality that $\mathcal{I}$ is
left-extremal.

######  Remark 3.6.

Consider a left-extremal instance $\mathcal{I}=(A,H,\mathcal{P})$. Let
$\sigma=(h_{1},h_{2},\ldots,h_{m})$ be a left-extremal ordering on the houses.
So for every agent $a\in A$, there exists $i(a)\in[n]$ such that
$\mathcal{P}(a)=\left\\{{h_{1},h_{2},\ldots,h_{i(a)}}\right\\}$. Notice that
$\sigma$ imposes an ordering on the agents, say
$\sigma_{A}=(a_{1},a_{2},\ldots,a_{n})$ so that
$\mathcal{P}(a_{1})\subseteq\mathcal{P}(a_{2})\subseteq\cdots\subseteq\mathcal{P}(a_{n})$.
Notice also that we can check in polynomial time if a given instance is left-
extremal, and if so, find a left-extremal ordering $\sigma$ on the houses and
then the ordering $\sigma_{A}$ on the agents. So, whenever dealing with a
left-extremal instance $\mathcal{I}$, we assume without loss of generality
that $\sigma$ and $\sigma_{A}$ are given. And whenever we talk about, for
example, the “first/last house,” we always mean the first/last house with
respect to the ordering $\sigma$. Same with the ordering $\sigma_{A}$ and the
“first/last agent.”

##  4 Optimal House Allocation

In this section, we deal with the Optimal House Allocation problems, where the
goal is to minimize the number of envious agents. We start by discussing the
cases for which we have polynomial time algorithms for Optimal House
Allocation.

###  4.1 Polynomial Time Algorithms for OHA

We first prove that $[\nicefrac{{0}}{{1}}]$-Optimal House Allocation is
polynomial-time solvable on instances with an extremal structure.

######  Theorem 4.1.

There is a polynomial-time algorithm for $[\nicefrac{{0}}{{1}}]$-Optimal House
Allocation when the agent valuations have an extremal interval structure.

######  Proof 4.2.

In light of Remark 3.5, it suffices to prove for the case when agent
valuations are left extremal. Let $\mathcal{I}:=(A,H,\mathcal{P};k)$ denote an
instance of HA with left extremal valuations, which is irreducible with
respect to Section 3 and Section 3. We say that an agent $a$ is envy-free by
indifference under an allocation $\phi$ if the entire set of houses that $a$
approves remains unallocated under $\phi$. That is, $a$ does not value
$\phi(a)$, neither does she value any house $\phi(a^{\prime})$ for any other
agent $a^{\prime}\in[n]$. Among all the agents who are envy-free by
indifference, let $a_{i}$ be the one who approves the longest interval
$[h_{1},h_{i}]$. Note that none of the houses inside $[h_{1},h_{i}]$ can be
allocated to anyone, else $a_{i}$ will be envious.

We first make the following claim:

######  Claim 5.

Given an instance of $[\nicefrac{{0}}{{1}}]$\- Optimal House Allocation when
the agent valuations are left extremal, there exists an optimal allocation
where the set of allocated houses form an interval.

######  Proof 4.3.

Suppose in any optimal allocation, the set of allocated houses does not form
an interval. Let $h_{i}$ be an unallocated house such that $h_{l}$ and $h_{r}$
are allocated, where $l<i<r$. Note that since we are in the reduced instance,
there must be an $a$ agent who is envious due to the allocation of the house
$h_{r}$. Since $a$ values $h_{r}$, due to the interval structure, she must
value $h_{i}$ as $i<r$. If we swap $\phi(a)$ with $h_{i}$, then $a$ ceases to
be envious. Also, note that allocation of $h_{i}$ does not create any new
envious agent—indeed if an agent $a^{\prime}$ was not envious before $h_{i}$
was allocated, it means either she got a house she likes or her interval ended
before $h_{l}$. In either case, allocation of $h_{i}$ can not be a cause of
envy to her. This contradicts the fact that we started with an optimal
allocation. Also, notice that all the dummy houses (if any), in the reduced
instance, lie to the extreme right of all the houses that are valued. The
allocation of a dummy house can always be done respecting the interval
property, as agents do not distinguish between any two dummy houses.

Based on the above claim, our algorithm Alg works as follows. It loops over
all the possibilities of a house $h_{i}$ such that $[h_{1},h_{i}]$ is the
longest interval among the ones approved by the agents, who are envy-free by
indifference. There are at most $m+1$ such possibilities. For each such
$h_{i}$, Alg chooses the next consecutive $n$ houses to be allocated. This
reduces the instance to the one where $m=n$ and by Proposition 2.1, this can
be done in polynomial time.

To see the correctness, in one direction, if under any iteration $i$, the
allocation $\phi$ constructed by Alg has at most $k$ envious agents, then it
returns Yes, and the allocation is the witness that $\mathcal{I}$ is a Yes
instance. In the other direction, if $\mathcal{I}$ is a Yes instance, then
there exists an optimal allocation Opt such that
$\kappa^{\\#}(\textsc{Opt})\leq k$ and it allocates the consecutive houses,
say $[h_{i},h_{i+n}]$. The algorithm captures this optimal allocation when it
iterates over the house $h_{i}$, and hence returns Yes.

We now present our algorithm for the case when every agent values exactly one
house.

######  Theorem 4.4.

There is a polynomial-time algorithm for $[\nicefrac{{0}}{{1}}]$-Optimal House
Allocation when every agent approves exactly one house.

######  Proof 4.5.

Let $\mathcal{I}:=(A,H,\mathcal{P};k)$ denote an instance of HA such that
every agent approves exactly one house. Consider the associated preference
graph $G=(A\cup H,E)$. By Section 3 and Section 3, and their safeness as
argued in Theorem 4.15, we know that $|H|\leq 2(|A|-1)$. In the reduced
instance, we order the $(n-1)$ houses in $H\setminus D$ as
$\\{h_{1},h_{2},\ldots h_{n-1}\\}$ such that $d(h_{1})\geq d(h_{2})\geq\ldots
d(h_{n-1})$. The last $n-|D|$ of these houses are then allocated to their
neighbors (chosen arbitrarily). The remaining $D$ agents get the $|D|$ dummy
houses.

We argue the correctness of the above algorithm Alg. We show that the number
of envious agents under the allocation $\phi$ returned by Alg is equal to the
number of envious agents under some optimal allocation. We first claim that in
any optimal allocation Opt, all the dummy houses must be allocated. Suppose
$h^{\star}\in D$ is unallocated. Consider a house $h_{i}$ allocated to some
agent $a$ who approves it. This causes $d(h_{i})-1$ agents to have envy, and
since every agent likes exactly one house, there is no way these $d(h_{i})-1$
agents can become envy-free once $h_{i}$ is allocated. Since $h^{\star}$ is
available, we can allocate it to $a$ and add $h_{i}$ to the set of unallocated
houses. This decreases the number of envious agents by $d(h_{i})-1$, without
adding to the envy of anyone else. This contradicts the fact that we started
with an optimal allocation. Therefore all the dummy houses must be allocated.
Now, consider the set $S$ of houses in $H\setminus D$ that are allocated by
Opt. Let $T$ be the set of such houses allocated under $\phi$. $S$ and $T$
both contain exactly $n-|D|$ many houses from $H\setminus D$. Consider any two
house $h_{i}$ and $h_{j}$ in $H\setminus D$ such that $d(h_{i})>d(h_{j})$.
Note that the allocation of $h_{i}$ creates $d(h_{i})-1$ many envious agents,
strictly greater than the number of envious agents created by the allocation
of $h_{j}$, which is $d(h_{j})-1$. Therefore, $S$ contains $n-|D|$ houses of
the least degree from among the set of $H\setminus D$ houses. Since $T$ also
contain the $n-|D|$ houses of the least degree, therefore
$\kappa^{\\#}(\phi)=\kappa^{\\#}(\textsc{Opt})$.

We now state the algorithm when the house degree is bounded, while the agent
degree is not.

######  Theorem 4.6.

There is a polynomial-time algorithm for $[\nicefrac{{0}}{{1}}]$-Optimal House
Allocation when every house is approved by atmost two agents.

######  Proof 4.7.

Consider the agent-house bipartite preference graph $G$. We first apply the
following reduction rules:

For every house $h$ such that $d(h)=1$, we allocate $h$ to $N(h$). The above
reduction is safe. Indeed, if $d(h)=1$, then no one except exactly one agent
$a$ values the house $h$, and so allocating $h$ to $a$ does not generate any
envy.

For every cycle $C=(h_{1},a_{1},h_{2},a_{2},\ldots a_{i},h_{1})$ in $G$,
allocate $h_{i}$ to the agent $a_{i}$. The above reduction is safe. Indeed,
since $d(h)\leq 2\leavevmode\nobreak\ \forall\leavevmode\nobreak\ h\in G$, a
house that participates in a cycle $C$ is valued _only_ by the agents
participating in the same cycle. Since $G$ is a bipartite graph, all cycles
are of even length, so the number of agents in $C$($=|A_{C}|$), is equal to
the number of houses in $C$ ($=|H_{C}|)$. This implies that every agent in $C$
can get a house she values from $C$. This does not make any agent outside $C$
envious.

Consider the remaining graph $G$ after the application of 4.7 and 4.7. Note
that $G$ is a collection of trees, that is, $G=T_{1},T_{2},\ldots T_{r}$. Let
$D$ be the set of dummy houses in $G$. We now describe the algorithm Alg.
First, sort the trees in increasing order of sizes, that is,
$|T_{1}|\leq|T_{2}|,\ldots\leq|T_{r}|$. For each tree $T_{i}$, we root $T_{i}$
at some agent $a_{j}$ such that $d(a_{j})=1$. (After 4.7, such an agent always
exists). Let $n_{1},n_{2},\ldots n_{r}$ be the number of agents in the trees
$T_{1},T_{2},\ldots T_{r}$ respectively. Let $j$ be the first index such that
$(n_{1}+n_{2}\ldots+n_{j})+(r-j)>|D|$ . Then,
$(n_{1}+n_{2}\ldots+n_{j-1})+(r-(j-1))\leq|D|$. We allocate all the agents in
$T_{1},T_{2},\ldots T_{j-1}$ a dummy house. Then, the number of dummy houses
that remain is $|D|-(n_{1}+n_{2}+\ldots+n_{j-1})\geq(r-(j-1))$. For the
remaining trees, $T_{j},\ldots T_{r}$, we match the non-root agents to their
parent house and allocate the root agent a dummy house. There are $r-j+1$ root
agents and there are at least so many dummy houses.

Note that only the root agents in the tree $T_{j},T_{j+1},\ldots T_{r}$ are
the envious ones — indeed, such a root agent gets a dummy house but a house
valued by her is allocated. Notice that every non-root agent in the above
trees got a house she valued, and all the agents in the trees
$T_{1},T_{2},\ldots T_{j-1}$ got a dummy house, and none of the houses they
valued got allocated.

Therefore, under Alg, the number of envious agents = $r-j+1$ = total amount of
envy.

######  Claim 6.

Alg returns an optimal allocation that minimizes the number of envious agents.

######  Proof 4.8.

Let $G$ be the reduced graph after reduction rules 4.7 and 4.7. Note that
$|H_{T_{i}}|=|A_{T_{i}}|-1$ for any $T_{i}\in G$. Indeed, root $T_{i}$ at a
house say $h_{1}$. Let $N(h_{1})=a_{1}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ a_{2}$. Since there is no leaf house, and
$d(h)=2\leavevmode\nobreak\ \forall\leavevmode\nobreak\ h$, every $h\neq
h_{1}$ is incident to a unique agent $a\neq a_{1},a_{2}$. This gives a
bijection from $H_{i}\setminus h_{1}$ to $A_{i}\setminus\\{a_{1},a_{2}\\}$.

Let Opt be the optimal allocation that minimizes the number of envious agents
in the reduced graph $G$. Let $l$ and $l^{\prime}$ be the number of envious
agents under Opt and the allocation returned by Alg respectively.

If $l=l^{\prime}$, we are done. We will now show that $l\nless l^{\prime}$.
Suppose, $l<l^{\prime}$. Notice that every tree $T_{i}$ has either no envious
agents (in the case when every agent in $T_{i}$ gets a dummy house) or exactly
one envious agent (in the case when houses from $T_{i}$ are allocated). So,
under Opt, there are exactly $l$ trees that have exactly one envious agent.
Since these $l$ agents did not get what they value, they must have got a dummy
house because of the reduction rules 4.7, 4.7, and the fact that every tree
has one agent more than the number of houses. Also, since there are no envious
agents in the remaining $r-l$ trees (say, $T_{i_{1}},T_{i_{2}},\ldots
T_{i_{r-l}})$, all the agents in these trees must have got dummy houses each.
Therefore the number of dummy houses allocated under Opt are:

$(n_{i_{1}}+n_{i_{2}}+\ldots n_{i_{r-l}})+l\geq(n_{1}+n_{2}+\ldots+n_{r-l})+l$
(1)

Note that $l^{\prime}=r-j+1$ where $j$ is the first index such that
$n_{1}+n_{2}\ldots+n_{j}+r-j>|D|$. Now since $l<l^{\prime}$, therefore,

$(r-l)>(r-l^{\prime})\Rightarrow(r-l)\geq(r-l^{\prime}+1)=j\Rightarrow(r-l)\geq
j$ (2)

This implies that there are at least $j$ envy-free trees under Opt. Suppose
WLOG there are exactly $j$ envy-free trees under Opt. Then the number of dummy
houses allocated under Opt:

$(n_{i_{1}}+n_{i_{2}}+\ldots
n_{i_{j}})+(r-j)\geq(n_{1}+n_{2}+\ldots+n_{j})+(r-j)>|D|$ which is a
contradiction.

This concludes the argument.

###  4.2 Hardness Results for OHA

In this section, we design three different reductions that will establish the
hardness of Optimal House Allocation (both $\nicefrac{{0}}{{1}}$-OHA and
$[\succeq]$-OHA), including in restricted settings. The first is a
parameterized reduction from Clique to $\nicefrac{{0}}{{1}}$-OHA.

######  Theorem 4.9.

$[\nicefrac{{0}}{{1}}]$-Optimal House Allocation is $\mathsf{NP}$-complete
when every house is approved by at most three agents.

######  Proof 4.10.

We sketch a reduction from Clique. Let $\mathcal{I}:=(G=(V,E);k)$ be an
instance of Clique. We first describe the construction of an instance of OHA
based on $G$:

  * •

We introduce a house $h_{e}$ for every edge $e\in E$. We call these the _edge
houses_.

  * •

We also introduce $m+n-{k\choose 2}$ dummy houses.

  * •

We introduce an agent $a_{v}$ for every vertex $v\in V$ and an agent $a_{e}$
for every edge $e\in E$. We refer to these as the vertex and edge agents,
respectively.

  * •

Every edge agent $a_{e}$ values the house $h_{e}$.

  * •

For every vertex $v\in V$, the vertex agent $a_{v}$ values the edge house
$h_{e}$ if and only if $e$ is incident to $v$ in $G$.

Note that in this instance of OHA, there are $(m-{k\choose 2})$ extra houses,
$m+n-{k\choose 2}$ dummy houses, and every house is approved by at most three
agents. We let $k$ be the target number of envious agents. This completes the
construction of the reduced instance. We now turn to a proof of equivalence.

#### The forward direction.

Let $S\subseteq V$ be a clique of size $k$. Then consider the allocation
$\phi$ that assigns $h_{e}$ to $a_{e}$ for all $e\in E(G[S])$ and dummy houses
to all other agents. Note that no edge agent is envious in this allocation,
and the only vertex agents who are envious are those that correspond to
vertices of $S$. Since $|S|=k$, this establishes the claim in the forward
direction.

#### The reverse direction.

Let $\phi$ be an allocation that has at most $k$ envious agents. We say that
$\phi$ is nice if every edge house is either unallocated by $\phi$ or
allocated to an edge agent who values it. If $\phi$ is not nice to begin with,
notice that it can be converted to a nice allocation by a sequence of
exchanges that does not increase the number of envious agents. In particular,
suppose $h_{e}$ is allocated to an agent $a\neq a_{e}$. Then we obtain a new
allocation by swapping the houses $h_{e}$ and $\phi(a_{e})$ between agents $a$
and $a_{e}$. This causes at least one envious agent to become envy-free (i.e.,
$a_{e}$) and at most one envy-free agent to become envious (i.e., $a$), and
therefore the number of envious agents does not increase. Based on this, we
assume, without loss of generality, that $\phi$ is a nice allocation.

Now note that any nice allocation $\phi$ is compelled to assign $n$ dummy
houses among the $n$ vertex agents, and this leaves us with $m-{k\choose 2}$
dummy houses that can be allocated among $m$ edge agents. Therefore, at least
${k\choose 2}$ edge agents are assigned edge houses.

Let $F\subseteq E$ be the subset of edges corresponding to edge agents who
were assigned edge houses by $\phi$. Let $S\subseteq V$ be the set of vertices
in the span of $F$, that is:

$S:=\bigcup_{e=(u,v)\in F}\\{u,v\\}.$

Note that for all $v\in S$, $a_{v}$ is envious with respect to $\phi$,
since—by the definitions we have so far—$a_{v}$ valued an assigned house and
was assigned a dummy house. Since $\phi$ admits at most $k$ envious agents, we
have that $|S|\leq k$. However, $S$ is also the span of at least ${k\choose
2}$ distinct edges, so it is also true444Intuitively, a smaller set of
vertices would not be able to accommodate as many edges; and specifically a
subset of at most $k-1$ vertices can account for at most ${k-1\choose
2}<{k\choose 2}$ edges. that $|S|\geq k$. Therefore, we conclude that $|S|=k$,
and since every edge in $F$ belongs to $G[S]$ and $F$ has ${k\choose 2}$
edges, it follows that $S$ is a clique of size $k$ in $G$. This concludes the
argument in the reverse direction.

######  Theorem 4.11.

$[\nicefrac{{0}}{{1}}]$-Optimal House Allocation is $\mathsf{NP}$-complete
even when every agent approves at most two houses.

######  Proof 4.12.

Let $\mathcal{I}:=(G=(V,E);k)$ be an instance of Clique where $G$ is a
$d$-regular graph. (The problem of finding a clique restricted to regular
graphs is also $\mathsf{NP}$-complete [Mathieson and Szeider, (2012)]). We
first describe the construction of an instance of OHA based on $G$:

  * •

We introduce a house $h_{v}$ for every vertex $v\in V$. We call these the
_vertex houses_.

  * •

We also introduce $m+n-k$ dummy houses.

  * •

We introduce an agent $a_{v}$ for every vertex $v\in V$ and an agent $a_{e}$
for every edge $e\in E$. We refer to these as the vertex and edge agents,
respectively.

  * •

Every vertex agent $a_{v}$ values the house $h_{v}$.

  * •

For every edge $e=(u,v)$ in $E$, the edge agent $a_{e}$ values the houses
$h_{u}$ and $h_{v}$.

Note that in this instance of OHA, there are $(n-k)$ extra houses, $m+n-k$
dummy houses, and every agent approves at most two houses. We let
$kd-{k\choose 2}$ be the target number of envious agents. This completes the
construction of the reduced instance. We now turn to a proof of equivalence.

#### The forward direction.

Let $S\subseteq V$ be a clique of size $k$. Then consider the allocation
$\phi$ that assigns $h_{v}$ to $a_{v}$ for all $v\in S$ and dummy houses to
all other agents. Note that no vertex agent is envious in this allocation, and
the only edge agents that are envious are those that correspond to edges in
$G$ that have at least one of their endpoints in $S$. The total number of
distinct edges incident on $S$ is at most $kd$, but since $G[S]$ induces a
clique, the exact number of distinct edges incident on $S$ is $kd-{k\choose
2}$, and this establishes the claim in the forward direction.

#### The reverse direction.

Let $\phi$ be an allocation that has at most $kd-{k\choose 2}$ envious agents.
We say that $\phi$ is nice if every vertex house is either unallocated by
$\phi$ or allocated to a vertex agent who values it. If $\phi$ is not nice to
begin with, notice that it can be converted to a nice allocation by a sequence
of exchanges that does not increase the number of envious agents. In
particular, suppose $h_{v}$ is allocated to an agent $a\neq a_{v}$. Then we
obtain a new allocation by swapping the houses $h_{v}$ and $\phi(a_{v})$
between agents $a$ and $a_{v}$. This causes at least one envious agent to
become envy-free (i.e., $a_{v}$) and at most one envy-free agent to become
envious (i.e., $a$), and therefore the number of envious agents does not
increase. Based on this, we assume, without loss of generality, that $\phi$ is
a nice allocation.

Now note that any nice allocation $\phi$ is compelled to assign $m$ dummy
houses among the $m$ edge agents, and this leaves us with $n-k$ dummy houses
that can be allocated among $n$ vertex agents. Therefore, at least $k$ vertex
agents are assigned vertex houses. We may assume that exactly $k$ vertex
agents are assigned vertex houses—indeed if more than $k$ vertex agents are
assigned vertex houses, these houses can be swapped with dummy houses without
changing the number of envious agents, and we perform these swaps until we run
out of dummy houses to swap with. Finally, observe that the set of $k$ vertex
agents who are assigned vertex houses induce a clique of size $k$ in $G$.
Indeed, if not:

$\text{\\# of edges incident on
}S=kd-{\color[rgb]{.804,.36,.36}\definecolor[named]{pgfstrokecolor}{rgb}{.804,.36,.36}|E(G[S])|}>kd-{\color[rgb]{.804,.36,.36}\definecolor[named]{pgfstrokecolor}{rgb}{.804,.36,.36}{k\choose
2}}.$

The claim follows from the fact that every edge incident on $S$ in $G$
corresponds to a distinct edge agent who experiences envy in the reduced
instance, and this would contradict our assumption that the number of agents
envious with respect to $\phi$ was at most $kd-{k\choose 2}$.

######  Theorem 4.13.

$[\succeq]$-Optimal House Allocation is $\mathsf{NP}$-complete by a
polynomial-time reduction from Maximum Balanced Biclique.

######  Proof 4.14.

We show that the reduction proposed by Kamiyama et al., (2021) can be extended
to achieve the above result. Given an instance $G=(L,R,E)$ of Maximum Balanced
Biclique such that $L=\\{b_{1},\ldots,b_{n}\\}$ and
$R=\\{c_{1},\ldots,c_{m}\\}$, we create an instance of $[\succeq]$-OHA as
follows: an agent $a_{i}$ for each $b_{i}\in L$ and a house $h_{j}$ for each
$c_{j}\in R$. We also have $n$ additional starred houses
$\\{h_{1}^{\star},\ldots,h_{n}^{\star}\\}$. This amounts to a total of $n$
agents and $m+n$ houses. An agent $a_{i}$ ranks the houses as follows:

$R(a_{i})=\begin{cases}h_{j}\succ h_{k},\leavevmode\nobreak\
\text{if}\leavevmode\nobreak\ j>k;(b_{i},c_{j})\notin E\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ (b_{i},c_{k})\notin E\\\ h_{j}\succ
h_{k},\leavevmode\nobreak\ \text{if}\leavevmode\nobreak\ (b_{i},c_{j})\notin
E\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\ (b_{i},c_{k})\in E\\\
h_{j}=h_{k},\leavevmode\nobreak\ \text{if}\leavevmode\nobreak\
(b_{i},c_{j})\in E\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\
(b_{i},c_{k})\in E\\\ h_{j}^{\star}\succ h_{k}^{\star},\leavevmode\nobreak\
\text{if}\leavevmode\nobreak\ j>k\\\ h_{i}\succ
h_{j}^{\star},\leavevmode\nobreak\ \forall\leavevmode\nobreak\
i\in[m],j\in[n]\end{cases}$

Essentially, every agent ranks his non-neighbor houses first in a fixed strict
order, then ranks all his neighbors equally, and at last, ranks all the
additional starred houses, again, in some fixed strict order.

We now establish the correctness of the above reduction. In the forward
direction, suppose there is a $k$-sized Balanced Biclique in $G$, consisting
of vertices $\\{b_{i_{1}},b_{i_{2}},\ldots b_{i_{k}}\\}$ from $L$ and
$\\{c_{i_{1}^{\prime}},\ldots c_{i_{k}^{\prime}}\\}$ from $R$. Then consider
the following assignment:

$\phi(a_{i})=\begin{cases}h_{i_{l}^{\prime}}\leavevmode\nobreak\
\text{if}\leavevmode\nobreak\ i=i_{l}\leavevmode\nobreak\ \text{for
some}\leavevmode\nobreak\ l\in[k]\\\ h_{i^{\star}}\leavevmode\nobreak\
\text{otherwise}\end{cases}$

That is, the agents corresponding to the clique vertices get one of their
adjacent houses, again corresponding to the clique vertices. Note that each of
the $\\{a_{i_{1}},\ldots{a_{i_{k}}}\\}$ rank the houses
$\\{h_{i_{1}^{\prime}},\ldots h_{i_{k}^{\prime}}\\}$ equally, so they do not
envy each other. Also, they do not envy the remaining agents who get
$h_{j}^{\star}$, as they all have the ranking $h_{i_{l}}\succ h_{j}^{\star}$
for all $i$ and $j$.

For the reverse direction, suppose there exists an assignment $\phi$ of houses
such that there are $k$ envy-free agents. We claim that there is a balanced
biclique of size $\frac{k}{2}$ in $G$. Let $A_{EF}$ denote the set of envy-
free agents with respect to $\phi$. Notice that none of the agents in $A_{EF}$
owns a starred house under $\phi$. If not, suppose some $a\in A_{EF}$ gets
$h_{j}^{\star}$. Consider another agent $a^{\prime}$ in $A_{EF}$ such that
$a^{\prime}\neq a$. In case $a^{\prime}$ gets a house $h_{j}$ for some
$j\in[m]$, then $a$ would be envious as she ranks all $h_{j}$ better than the
starred houses. Else, if $a^{\prime}$ gets a starred house, say
$h_{k}^{\star}$, then depending on whether $j>k$ or not, one of these two
agents experiences envy, as they both rank all the starred houses in the same
manner. Hence, $\phi(A_{EF})\subseteq\\{h_{1},\ldots,h_{m}\\}$.

Now, let the $k$ houses under $\phi(A_{EF})$ be $\\{h_{j_{1}},\ldots
h_{j_{k}}\\}$ such that $j_{1}<j_{2}<\ldots<j_{k}$. Let
$a_{i_{l}}=\phi^{-1}(h_{j_{l}})$. Then consider the set $S$, consisting of the
vertices in $L$ corresponding to the first half agents in $\phi^{-1}(A_{EF})$
and the set $T$, consisting of the vertices in $R$, corresponding to the
remaining half house vertices in $\phi(A_{EF})$. Precisely,
$S=\\{b_{i_{1}},\ldots b_{i_{\frac{k}{2}}}\\}$ and
$T=\\{c_{j_{\frac{k}{2}+1}},\ldots,c_{j_{k}}\\}$. We claim that $S$ and $T$
together induce a biclique of size $\frac{k}{2}$ in $G$. Suppose
$(b_{i_{l}},c_{j_{k}})\notin E$ for some $b_{i_{l}}\in S$ and some
$c_{j_{k}}\in T$. By the choice of $S$ and $T$, notice that $i_{l}<j_{k}$.
This means that $a_{i_{l}}$ ranks the $h_{j_{k}}\succ h_{j_{l}}$, therefore
envies $a_{i_{k}}$, who is assigned the house $h_{j_{k}}$. In order for
$a_{i_{l}}$ to not envy the owner of $h_{j_{k}}$, it must be the case that
$(b_{i_{l}},c_{j_{k}})\in E$. Therefore $S$ and $T$ form a biclique of size
$\frac{k}{2}$. This completes the correctness of the reduction.

###  4.3 Parameterized Results for OHA

######  Theorem 4.15.

$[\nicefrac{{0}}{{1}}]$-Optimal House Allocation admits a linear kernel
parameterized by the number of agents. In particular, given an instance of
$[\nicefrac{{0}}{{1}}]$-Optimal House Allocation, there is a polynomial time
algorithm that returns an equivalent instance of
$[\nicefrac{{0}}{{1}}]$-Optimal House Allocation with at most twice as many
houses as agents.

######  Proof 4.16.

It suffices to prove the safety of Section 3. Let
$\mathcal{I}:=(A,H,\mathcal{P};k)$ denote an instance of HA with parameter
$k$. Further, let $\mathcal{I}^{\prime}=(H^{\prime}:=H\setminus
X,A^{\prime}:=A\setminus Y,\mathcal{P}^{\prime};k)$ denote the reduced
instance corresponding to $\mathcal{I}$. Note that the parameter for the
reduced instance is $k$ as well.

If $\mathcal{I}$ is a Yes-instance of OHA, then there is an allocation
$\phi:A\rightarrow H$ with at most $k$ envious agents. By 1, we may assume
that $\phi$ is a nice allocation. This implies that the projection of $\phi$
on $H^{\prime}\cup A^{\prime}$ is well-defined, and it is easily checked that
this gives an allocation with at most $k$ envious agents in
$\mathcal{I}^{\prime}$.

On the other hand, if $\mathcal{I}^{\prime}$ is a Yes-instance of OHA, then
there is an allocation $\phi^{\prime}:A^{\prime}\rightarrow H^{\prime}$ with
at most $k$ envious agents. We may extend this allocation to
$\phi:A\rightarrow H$ by allocating the houses in $Y$ to agents in $X$ along
the expansion $M$, that is:

$\phi(a)=\begin{cases}\phi^{\prime}(a)&\text{if }a\notin X,\\\ M(a)&\text{if
}a\in X.\end{cases}$

Since all the newly allocated houses are not valued by any of the agents
outside $X$ and all agents in $X$ are envy-free with respect to $\phi$, it is
easily checked that $\phi$ also has at most $k$ envious agents.

The following results follow from using the algorithm described in Proposition
2.1 after guessing the allocated houses, which adds a multiplicative overhead
of ${m\choose n}\leq 2^{m}$ to the running time.

######  Corollary 4.17.

$[\nicefrac{{0}}{{1}}]$-Optimal House Allocation is fixed-parameter tractable
when parameterized either by the number of houses or the number of agents. In
particular, $[\nicefrac{{0}}{{1}}]$-Optimal House Allocation can be solved in
time $O^{\star}(2^{m})$.

######  Corollary 4.18.

$[\succ]$-Optimal House Allocation is fixed-parameter tractable when
parameterized by the number of houses and can be solved in time
$O^{\star}(2^{m})$.

The next two results follow respectively from Theorem 4.9 and Theorem 4.13.

######  Corollary 4.19.

$[\nicefrac{{0}}{{1}}]$-Optimal House Allocation is W[1]-hard when
parameterized by the solution size, i.e, the number of envious agents, even
when every house is approved by at most three agents.

######  Corollary 4.20.

$[\succ]$-Optimal House Allocation is W[1]-hard when parameterized by the
solution size, i.e., the number of envious agents.

We now show that $[\nicefrac{{0}}{{1}}]$-OHA is fixed-parameter tractable when
parameterized by the number of types of houses or the number of types of
agents.

######  Theorem 4.21.

$[\nicefrac{{0}}{{1}}]$-Optimal House Allocation is fixed-parameter tractable
when parameterized by either the number of houses types or the number of
agents types.

To prove Theorem 4.21, we formulate $[\nicefrac{{0}}{{1}}]$-OHA as an integer
linear program and then invoke Theorem 2.9.

Consider an instance $\mathcal{I}=(A,H,\mathcal{P})$ of
$[\nicefrac{{0}}{{1}}]$-OHA. For two agents $a,a^{\prime}\in A$, we say that
$a$ and $a^{\prime}$ are of the same type if
$\mathcal{P}(a)=\mathcal{P}(a^{\prime})$. That is, for two agents
$a,a^{\prime}\in A$ of the same type and for every house $h\in H$, either both
$a$ and $a^{\prime}$ value $h$ or both $a$ and $a^{\prime}$ do not value $h$.
Similarly, for two houses $h,h^{\prime}\in H$, we say that $h$ and
$h^{\prime}$ are of the same type if for every agent $a\in A$, either $a$
values both $h$ and $h^{\prime}$ or $a$ values neither $h$ nor $h^{\prime}$.
We use $n^{*}$ to denote the number of types of agents in $\mathcal{I}$ and
the $m^{*}$ to denote the number of types of houses in $\mathcal{I}$. With a
slight abuse of notation, for $i\in[n^{*}]$, we use
$\mathcal{P}(i)(\subseteq[m^{*}])$ to denote the set of types of houses that
each agent of type $i$ values. Also, for $i\in[n^{*}],j\in[m^{*}]$ and an
allocation ${{\phi}:{A}\rightarrow{H}}$, let $A(\phi,i,j)\subseteq A$ be the
set of agents of type $i$ who receive a house of type $j$ under $\phi$.

Consider an instance $\mathcal{I}=(A,H,\mathcal{P})$ of
$[\nicefrac{{0}}{{1}}]$-OHA. Then, (1) $n^{*}\leq 2^{m^{*}}$ and (2)
$m^{*}\leq 2^{n^{*}}$. To see (1), for each $i\in[n^{*}]$, the agents of type
$i$ are uniquely identified by the types of houses they prefer, and the number
of distinct choices for the types of houses is at most $2^{m^{*}}$. Similarly,
to see (2), observe that for each $j\in[m^{*}]$, the houses of type $j$ are
uniquely identified by the types of agents who prefer houses of type $j$; and
the number of distinct choices for the types of agents is at most $2^{n^{*}}$.

######  Lemma 4.22.

Consider an instance $\mathcal{I}=(A,H,\mathcal{P})$ of
$[\nicefrac{{0}}{{1}}]$-OHA and an allocation ${{\phi}:{A}\rightarrow{H}}$.
Consider any fixed pair $(i,j)$, where $i\in[n^{*}]$ and $j\in[m^{*}]$. Then,
for every $a\in A$ and for every $a^{\prime},a^{\prime\prime}\in A(\phi,i,j)$,
either both $a^{\prime}$ and $a^{\prime\prime}$ envy $a$, or neither
$a^{\prime}$ nor $a^{\prime\prime}$ envies $a$.

######  Proof 4.23.

Consider $a\in A$ and $a^{\prime},a^{\prime\prime}\in A(\phi,i,j)$. First, if
$j\in\mathcal{P}(i)$, then neither $a^{\prime}$ nor $a^{\prime\prime}$ envies
any agent. So, assume that $j\notin\mathcal{P}(i)$. Let $\phi(a)$ be of type
$\ell$, for some $\ell\in[m^{*}]$. If $\ell\notin\mathcal{P}(i)$, then,
neither $a^{\prime}$ nor $a^{\prime\prime}$ envies $a$. If
$\ell\in\mathcal{P}(i)$, then both $a^{\prime}$ and $a^{\prime\prime}$ envy
$a$.

We now move to formulate the $[\nicefrac{{0}}{{1}}]$-OHA problem as an integer
linear program (ILP). The number of variables in our ILP will be
$\mathcal{O}(n^{*}\cdot m^{*})$, where $n^{*}$ is the number of types of
agents and $m^{*}$ is the number of types of houses. By Section 4.3, the
number of variables will be bounded separately by both $\mathcal{O}(n^{*}\cdot
2^{n^{*}})$ and $\mathcal{O}(m^{*}\cdot 2^{m^{*}})$. That is, the number of
variables will be bounded separately by both the number of house types and the
number of agent types. The result will then follow from Theorem 2.9.

Consider an instance $\mathcal{I}=(A,H,\mathcal{P})$ of
$[\nicefrac{{0}}{{1}}]$-Optimal House Allocation. For each $i\in[n^{*}]$ and
$j\in[m^{*}]$, let $n_{i}$ be the number of agents of type $i$ and $m_{j}$ the
houses of type $j$. To define our ILP, we introduce the following variables.
For each $i\in[n^{*}]$, $j\in[m^{*}]$, we introduce four variables:
$x_{ij},z_{ij},d_{ij}$ and $d^{\prime}_{ij}$. Here, $x_{ij}$ and $z_{ij}$ are
integer variables, and $d_{ij}$ and $d^{\prime}_{ij}$ are binary variables.
The semantics of the variables are as follows. (1) We want $x_{ij}$ to be the
number of agents of type $i$ who receive houses of type $j$. Equivalently, we
want $x_{ij}$ to be the number of houses of type $j$ that are allocated to
agents of type $i$. (2) And we want $z_{ij}$ to be the number of _envious_
agents of type $i$ who receive houses of type $j$. By Lemma 4.22, either all
type $i$ agents who receive type $j$ houses are envious, or none of them is
envious. That is, we must have either $z_{ij}=x_{ij}$ or $z_{ij}=0$. Notice
that type $i$ agents who receive type $j$ houses are envious if and only if
$j\notin\mathcal{P}(i)$, and for some $j^{\prime}\in\mathcal{P}(i)$, at least
one house of type $j^{\prime}$ has been allocated (to, say, an agent of type
$i^{\prime}$ for some $i^{\prime}\in[n^{*}]$). That is, we must have
$z_{ij}>0$ if and only if $j\notin\mathcal{P}(i)$, $x_{ij}>0$ and
$x_{i^{\prime},j^{\prime}}>0$ for some $i^{\prime}\in[n^{*}]$ and
$j^{\prime}\in\mathcal{P}(i)$. Hence, for $j\notin\mathcal{P}(i)$, either
$x_{ij}=0$ or $z_{ij}>0$ if
$\sum_{i^{\prime}\in[n]}\sum_{j^{\prime}\in\mathcal{P}(i)}x_{i^{\prime}j^{\prime}}>0$.
(3) The variables $d_{ij},d^{\prime}_{ij}$ are only dummy variables that we
use to enforce the “either or” constraints.

We now formally describe our ILP. Minimize
$\sum_{i\in[n^{*}]}\sum_{j\in[m^{*}]}z_{ij}$ subject to the constraints in
Table 3.

(C1.$i$). | $\sum_{j\in[m^{*}]}x_{ij}=n_{i}$ | for every $i\in[n^{*}]$
---|---|---
(C2.$j$). | $\sum_{i\in[n^{*}]}x_{ij}\leq m_{j}$ | for every $j\in[m^{*}]$
(C3.a.$i.j$). | $x_{ij}\leq nd^{\prime}_{ij}$ | for every $i\in[n^{*}]$, $j\in[m^{*}]\setminus\mathcal{P}(i)$
(C3.b.$i.j$). | $\sum_{i^{\prime}\in[n^{*}]}\sum_{j^{\prime}\in\mathcal{P}(i)}x_{i^{\prime}j^{\prime}}\leq nmz_{ij}+nm(1-d^{\prime}_{ij})$
(C3.c.$i.j$). | $z_{ij}\leq n_{i}\sum_{i^{\prime}\in[n^{*}]}\sum_{j^{\prime}\in\mathcal{P}(i)}x_{i^{\prime}j^{\prime}}$
(C4.a.$i.j$). | $z_{ij}\leq n_{i}d_{ij}$ | for every $i\in[n^{*}]$, $j\in[m^{*}]$
(C4.b.$i.j$). | $x_{ij}-z_{ij}\leq n_{i}(1-d_{ij})$
(C4.c.$i.j$). | $z_{ij}\leq x_{ij}$
(C5.$i.j$). | $z_{ij}=0$ | for every $i\in[n^{*}],j\in\mathcal{P}(i)$
(C6.a.$i.j$). | $x_{ij}\geq 0$ | for every $i\in[n^{*}]$, $j\in[m^{*}]$
(C6.b.$i.j$). | $z_{ij}\geq 0$
(C6.c.$i.j$). | $d_{ij}\in\\{0,1\\}$
(C6.d.$i.j$). | $d^{\prime}_{ij}\in\\{0,1\\}$
Table 3: The constraints of the ILP $\texttt{P1}(\mathcal{I})$.

For convenience, we name this ILP $\texttt{P1}(\mathcal{I})$, and denote the
set of variables of $\texttt{P1}(\mathcal{I})$ by
$Var(\texttt{P1}(\mathcal{I}))$ and the optimum value of
$\texttt{P1}(\mathcal{I})$ by $opt(\texttt{P1}(\mathcal{I}))$. Constraint
C1.$i$ ensures that for each $i\in[n^{*}]$, the number of houses allocated to
agents of type $i$ is exactly $n_{i}$. In other words, all agents of type $i$
receive houses. Constraint C2.$j$ ensures that for each $j\in[m^{*}]$, the
number of houses of type $j$ that are allocated does not exceed $m_{j}$. For
$i\in[n^{*}]$ and $j\in[m]\setminus\mathcal{P}(i)$, constraints C3.a.$i.j$ and
C3.b.$i.j$ together ensure that depending on whether $d^{\prime}_{ij}=0$ or
$d^{\prime}_{ij}=1$, we have either $x_{ij}=0$ or $z_{ij}>0$ if
$\sum_{i^{\prime}\in[n^{*}]}\sum_{j^{\prime}\in[\mathcal{P}(i)]}x_{i^{\prime}j^{\prime}}>0$.
Constraint C3.c.$i.j$ ensures that if $x_{i^{\prime}j^{\prime}}=0$ for every
$i^{\prime}\in[n^{*}],j^{\prime}\in[m]\setminus\mathcal{P}(i)$, then
$z_{ij}=0$. Constraints C4.a.$i.j$-C4.c.$i.j$ together ensure that depending
on $d_{ij}=0$ or $d_{ij}=1$, we have either $z_{ij}=0$ or $z_{ij}=x_{ij}$.

To establish the correctness of $\texttt{P1}(\mathcal{I})$, we prove the
following two claims.

######  Claim 7.

For any allocation ${{\phi}:{A}\rightarrow{H}}$, there exists a feasible
solution ${{f_{\phi}}:{Var(\texttt{P1}(\mathcal{I}))}\rightarrow{\mathbb{Z}}}$
for $\texttt{P1}(\mathcal{I})$ such that
$\kappa^{\\#}(\phi)=\sum_{i\in[n^{*}]}\sum_{j\in[m^{*}]}f_{\phi}(z_{ij})$.

######  Claim 8.

For every optimal solution
${{f}:{Var(\texttt{P1}(\mathcal{I}))}\rightarrow{\mathbb{Z}}}$ for
$\texttt{P1}(\mathcal{I})$, there exists an allocation
${{\phi_{f}}:{A}\rightarrow{H}}$ such that
$\kappa^{\\#}(\phi_{f})=\sum_{i\in[n^{*}]}\sum_{j\in[m^{*}]}f(z_{ij})$.

######  Remark 4.24.

Notice that 7, in fact, proves that ILP $\texttt{P1}(\mathcal{I})$ is always
feasible as there is always an allocation. Moreover, for an allocation $\phi$,
since $0\leq\kappa^{\\#}(\phi)\leq n$, and since
$\kappa^{\\#}(\phi)=\sum_{i\in[n^{*}]}\sum_{j\in[m^{*}]}f_{\phi}(z_{ij})$, we
can conclude that $\texttt{P1}(\mathcal{I})$ has a bounded solution.
Therefore, $\mathsf{opt}(\texttt{P1}(\mathcal{I}))$ is well-defined.

Assuming Claims 7 and 8 hold, we now prove the following claim.

######  Claim 9.

We have $\kappa^{\\#}(\mathcal{I})=\mathsf{opt}(\texttt{P1}(\mathcal{I}))$.

######  Proof 4.25.

To prove the claim, we will prove that (1)
$\kappa^{\\#}(\mathcal{I})\geq\mathsf{opt}(\texttt{P1}(\mathcal{I}))$ and (2)
$\mathsf{opt}(\texttt{P1}(\mathcal{I}))\geq\kappa^{\\#}(\mathcal{I})$.

To prove (1), consider an optimal allocation ${{\phi}:{A}\rightarrow{H}}$.
That is, $\kappa^{\\#}(\mathcal{I})=\kappa^{\\#}(\phi)$. By 7, we have
$\kappa^{\\#}(\phi)=\sum_{i\in[n^{*}]}\sum_{j\in[m^{*}]}f_{\phi}(z_{ij})\geq\mathsf{opt}(\texttt{P1}(\mathcal{I}))$,
where $f_{\phi}$ is as defined in 7. We thus have
$\kappa^{\\#}(\mathcal{I})\geq\mathsf{opt}(\texttt{P1}(\mathcal{I}))$.

Now, to prove (2), consider an optimal solution $f$ for
$\texttt{P1}(\mathcal{I})$. That is,

$\mathsf{opt}(\texttt{P1}(\mathcal{I}))=\sum_{i\in[n^{*}]}\sum_{j\in[m^{*}]}f(z_{ij})$.
By 8, we have

$\mathsf{opt}(\texttt{P1}(\mathcal{I}))=\sum_{i\in[n^{*}]}\sum_{j\in[m^{*}]}f(z_{ij})=\kappa^{\\#}(\phi_{f})\geq\kappa^{\\#}(\mathcal{I})$,
where $\phi_{f}$ is as defined in 8. We thus have
$\mathsf{opt}(\texttt{P1}(\mathcal{I}))\geq\kappa^{\\#}(\mathcal{I})$.

We are now ready to prove Theorem 4.21.

######  Proof 4.26 (Proof of Theorem 4.21).

Given an instance $\mathcal{I}$ of $[\nicefrac{{0}}{{1}}]$-OHA, observe that
we can construct the ILP $\texttt{P1}(\mathcal{I})$in polynomial time. The
number of variables in $\texttt{P1}(\mathcal{I})$ is bounded by $4n^{*}m^{*}$.
The number of constraints in $\texttt{P1}(\mathcal{I})$ is also bounded by
$\mathcal{O}(n^{*}m^{*})$. The maximum value of any coefficient or constant
term in $\texttt{P1}(\mathcal{I})$ is bounded by $nm$. So,
$\texttt{P1}(\mathcal{I})$ can be encoded using
$\text{poly}(n^{*},m^{*})\cdot\mathcal{O}(\log(nm))$ bits. The result then
follows from Theorem 2.9 and 9.

We now only have to prove Claims 7 and 8.

######  Proof 4.27 (Proof of 7).

Consider any allocation ${{\phi}:{A}\rightarrow{H}}$. Recall that
$A(\phi,i,j)$ is the set of agents of type $i$ who receive houses to type $j$
under $\phi$.

We define a solution
${{f_{\phi}}:{Var(\texttt{P1}(\mathcal{I}))}\rightarrow{\mathbb{Z}}}$ for
$\texttt{P1}(\mathcal{I})$ as follows. For each $i\in[n^{*}],j\in[m^{*}]$, we
set (1) $f_{\phi}(x_{ij})={|{A(\phi,i,j)}|}$; (2)
$f_{\phi}(z_{ij})=f_{\phi}(x_{ij})$ if there exists an envious agent $a\in
A(\phi,i,j)$ and $f_{\phi}(z_{ij})=0$ otherwise; (3) $f_{\phi}(d_{ij})=0$ if
$f_{\phi}(z_{ij})=0$ and $f_{\phi}(d_{ij})=1$ otherwise; and (4)
$f_{\phi}(d^{\prime}_{ij})=0$ if $f_{\phi}(x_{ij})=0$ and
$f_{\phi}(d^{\prime}_{ij})=1$ otherwise.

To see that $f_{\phi}$ satisfies all the constraints of
$\texttt{P1}(\mathcal{I})$, observe first that ${|{A(\phi,i,j)}|}$ is the
number of agents of type $i$ who receive houses of type $j$ under $\phi$;
equivalently, ${|{A(\phi,i,j)}|}$ is the number of houses of type $j$ that
have been allocated to agents of type $i$ under $\phi$. Therefore,
$\sum_{j\in[m^{*}]}{|{A(\phi,i,j)}|}=n_{i}$ and
$\sum_{i\in[n^{*}]}{|{A(\phi,i,j)}|}\leq m_{j}$. Hence, (1)
$\sum_{j\in[m^{*}]}f_{\phi}(x_{ij})=\sum_{j\in[m^{*}]}{|{A(\phi,i,j)}|}=n_{i}$
and
$\sum_{i\in[n^{*}]}f_{\phi}(x_{ij})=\sum_{i\in[n^{*}]}{|{A(\phi,i,j)}|}\leq
m_{j}$. Thus $f_{\phi}$ satisfies constraints C1.$i$ and C2.$j$ for every
$i\in[n^{*}]$ and $j\in[m^{*}]$. Also, note that
$\sum_{i^{\prime}\in[n^{*}]}\sum_{j^{\prime}\in\mathcal{P}(i)}f_{\phi}(x_{i^{\prime}j^{\prime}})\leq\sum_{i^{\prime}\in[n^{*}]}\sum_{j^{\prime}\in[m^{*}]}{|{A(\phi,i,j)}|}\leq
n$.

Now, consider $i\in[n^{*}]$, $j\in[m^{*}]$. Suppose first that
$f_{\phi}(x_{ij})=0$. Then, by the definition of $f_{\phi}$, we have
${|{A(\phi,i,j)}|}=0$, and hence $f_{\phi}(z_{ij})=0$, which implies
$f_{\phi}(d_{ij})=0$; and $f_{\phi}(x_{ij})=0$ implies that
$f_{\phi}(d^{\prime}_{ij})=0$. Note that in this case, $f_{\phi}$ satisfies
all the constraints. In particular, constraint C3.b.$i.j$ is satisfied because
$f_{\phi}(z_{ij})=f_{\phi}(d^{\prime}_{ij})=0$ implies that the right side of
constraint C3.b.$i.j$ is exactly equal to $nm$, and the left side of the
constraint is at most $n$. Since $f_{\phi}(x_{ij})=f_{\phi}(z_{ij})=0$, all
the other constraints corresponding to the pair $(i,j)$ are also satisfied.

Suppose now that $f_{\phi}(x_{ij})>0$. Then by the definition of $f_{\phi}$,
we have $f_{\phi}(d^{\prime}_{ij})=1$. There are two possibilities: (1)
$f_{\phi}(z_{ij})=0$ and (2) $f_{\phi}(z_{ij})>0$.

Assume first that $f_{\phi}(z_{ij})=0$. Again, by the definition of
$f_{\phi}$, we have $f_{\phi}(d_{ij})=0$. Notice that this choice of values
satisfies all the constraints corresponding to the pair $(i,j)$, except
possibly C3.b.$i.j$. To see that C3.c.$i.j$ is also satisfied, assume that
$j\in[m^{*}]\setminus\mathcal{P}(i)$. Since $f_{\phi}(z_{ij})=0$, the
definition of $f_{\phi}$ implies that the agents of type $i$ who receive
houses of type $j$ are not envious. Hence we can conclude that none of the
houses of type $j^{\prime}$ have been allocated under $\phi$, for any
$j^{\prime}\in\mathcal{P}(i)$. That is,
$A(\phi,i^{\prime},j^{\prime})=\emptyset$ for every $i^{\prime}\in[n^{*}]$ and
$[j^{\prime}]\in\mathcal{P}(i)$. Thus the left side of constraint C3.b.$i.j$
is $0$; and the right side is $0$ as well, as $f_{\phi}(z_{ij})=1$ and
$f_{\phi}(d^{\prime}_{ij})=1$.

Finally, assume that $f_{\phi}(z_{ij})>0$. Then, by the definition of
$f_{\phi}$, we have $f_{\phi}(z_{ij})=f_{\phi}(x_{ij})={|{A(\phi,i,j)}|}\leq
n_{i}$ and $f_{\phi}(d_{ij})=1$. Notice that this choice of values satisfies
constraints C4.a.$i.j$-C4.c.$i.j$. From the definition of $f_{\phi}$, we can
also conclude that the agents of type $i$ who receive houses of type $j$ under
$\phi$ are envious, which implies that $j\notin\mathcal{P}(i)$ and
${|{A(\phi,i^{\prime},j^{\prime})}|}=f_{\phi}(x_{i^{\prime}j^{\prime}})>0$ for
some $i^{\prime}\in[n^{*}]$, $j^{\prime}\in\mathcal{P}(i)$. Thus the right
side of constraint C3.c.$i.j$ is strictly positive; and since
$f_{\phi}(z_{ij})\leq n_{i}$, constraint C3.c.$i.j$ is satisfied. Since
$f_{\phi}(d^{\prime}_{ij})=1$ and $f_{\phi}(x_{ij})\leq n$, constraint
C3.a.$i.j$ is satisfied. Finally, constraint C3.b.$i.j$ is satisfied because
its left side is at most $n$, and the right side is at least $nm$ as
$f_{\phi}(z_{ij})>0$. Notice also that in this case $\texttt{P1}(\mathcal{I})$
does not contain constraint C5.$i.j$ as $j\notin\mathcal{P}(i)$.

We have thus shown that $f_{\phi}$ satisfies all the constraints of
$\texttt{P1}(\mathcal{I})$.

Consider $i\in[n^{*}],j\in[m^{*}]$. Suppose that $A(\phi,i,j)\neq\emptyset$.
By Lemma 4.22, either all agents in $A(\phi,i,j)$ are envious or none of them
are. By the definition of $f_{\phi}$, we have
$f_{\phi}(z_{ij})=f_{\phi}(x_{ij})={|{A(\phi,i,j)}|}$ if and only if the
agents in $A(\phi,i,j)$ are envious; and $f_{\phi}(z_{ij})=0$ otherwise.
Therefore, the number of envious agents under $\phi$,
$\kappa^{\\#}(\phi)=\sum_{i\in[n^{*}]}\sum_{j\in[m^{*}]}f_{\phi}(z_{ij})$.

To prove 8, we first prove two preparatory claims below. In both these claims,
${{f}:{Var(\texttt{P1}(\mathcal{I}))}\rightarrow{\mathbb{Z}}}$ is a feasible
solution for $\texttt{P1}(\mathcal{I})$.

######  Claim 10.

For every $i\in[n^{*}],j\in[m^{*}]$, either $f(z_{ij})=0$ or
$f(z_{ij})=f(x_{ij})$.

######  Proof 4.28.

Fix $i\in[n^{*}],j\in[m^{*}]$. Since constraint C6.c.$i.j$ is satisfied, we
have $f(d_{ij})\in\\{0,1\\}$. If $f(d_{ij})=0$, then constraints C4.a.$i.j$
implies that $f(z_{ij})\leq 0$ and then constraint C6.b.$i.j$ implies that
$z_{ij}=0$. Instead, if $f(d_{ij})=1$, then, constraint C4.b.$i.j$ implies
that $f(x_{ij})-f(z_{ij})\leq 0$, which implies that $f(x_{ij})\leq
f(z_{ij})$. But then constraint C4.c.$i.j$ implies that $f(z_{ij})=f(x_{ij})$.

######  Claim 11.

For every $i\in[n^{*}],j\in[m^{*}]$, $f(z_{ij})>0$ if and only if
$j\notin\mathcal{P}(i)$, $f(x_{ij})>0$ and $f(x_{i^{\prime}j^{\prime}})>0$ for
some $i^{\prime}\in[n^{*}]$ and $j^{\prime}\in\mathcal{P}(i)$.

######  Proof 4.29.

Fix $i\in[n^{*}],j\in[m^{*}]$. Assume first that $f(z_{ij})>0$. Then,
constraint C5.$i.j$ implies that $j\notin\mathcal{P}(i)$. And constraint
C4.c.$i.j$ implies that $f(x_{ij})\geq f(z_{ij})>0$. Now, if
$f(x_{i^{\prime}j^{\prime}})=0$ for every
$i^{\prime}\in[n],j^{\prime}\in\mathcal{P}(i)$, then constraint C3.c.i.j would
imply that $f(z_{ij})\leq 0$, which is not possible. Hence, we have
$f(x_{i^{\prime}j^{\prime}})>0$ for some
$i^{\prime}\in[n],j^{\prime}\in\mathcal{P}(i)$.

Assume now that $j\notin\mathcal{P}(i)$, $f(x_{ij})>0$, and
$f(x_{i^{\prime}j^{\prime}})>0$ for some $i^{\prime}\in[n^{*}]$ and
$j^{\prime}\in\mathcal{P}(i)$. Since $f(x_{ij})>0$, constraint C3.a.$i.j$
implies that $f(d^{\prime}_{ij})>0$. By constraint C6.d.$i.j$, we then have
$f(d^{\prime}_{ij})=1$. Then, constraint C3.b.$i.j$ ,along with the fact that
$f(x_{i^{\prime}j^{\prime}})>0$ for some $i^{\prime}\in[n^{*}]$ and
$j^{\prime}\in\mathcal{P}(i)$, implies that
$0<\sum_{i^{\prime}\in[n^{*}]}\sum_{j^{\prime}\in\mathcal{P}(i)}f(x_{i^{\prime}j^{\prime}})\leq
nmf(z_{ij})$, which, then implies that $f(z_{ij})>0$.

######  Proof 4.30 (Proof of 8).

Given ${{f}:{Var(\texttt{P1}(\mathcal{I}))}\rightarrow{\mathbb{Z}}}$, we
define ${{\phi_{f}}:{A}\rightarrow{H}}$ as follows. For each
$i\in[n^{*}],j\in[m^{*}]$, we allocate $f(x_{ij})$ houses of type $j$ to
agents of type $i$ (one house per agent). Thus, we have
${|{A(\phi_{f},i,j)}|}=f(x_{ij})$. Notice that as $f$ satisfies constraints
C1.$i$ and C2.$j$, the allocation $\phi_{f}$ is valid.

To complete the proof of the claim, we only need to prove that for every
$i\in[n^{*}],j\in[m^{*}]$, the number of envious agents of type $i$ who
received houses of type $j$ under $\phi_{f}$ is exactly equal to $f(z_{ij})$.
Fix $i\in[n^{*}],j\in[m^{*}]$. By Lemma 4.22, either all agents in
$A(\phi_{f},i,j)$ are envious or none of them is envious. Notice that the
agents in $A(\phi_{f},i,j)$ (if they exist) are envious if and only if
${|{A(\phi_{f},i,j)}|}>0$, $j\notin\mathcal{P}(i)$ and
$A(\phi_{f},i^{\prime},j^{\prime})\neq\emptyset$ for some
$i^{\prime}\in[n^{*}],j^{\prime}\in[m^{*}]\setminus\mathcal{P}(i)$. That is,
the agents in $A(\phi_{f},i,j)$ are envious if and only if
$f(x_{ij})={|{A(\phi_{f},i,j)}|}>0$, $j\notin\mathcal{P}(i)$ and
$f(x_{i^{\prime}j^{\prime}})={|{A(\phi_{f},i^{\prime},j^{\prime})}|}>0$ for
some $i^{\prime}\in[n^{*}],j^{\prime}\in[m^{*}]\setminus\mathcal{P}(i)$. On
the other hand, by 11, $f(z_{ij})>0$ if and only if $f(x_{ij})>0$,
$j\notin\mathcal{P}(i)$ and $f(x_{i^{\prime}j^{\prime}})>0$ for some
$i^{\prime}\in[n^{*}],j^{\prime}\in[m^{*}]\setminus\mathcal{P}(i)$. We can
thus conclude that the agents in $A(\phi_{f},i,j)$ are envious if and only if
$f(z_{ij})>0$. By 10, we also have $f(z_{ij})=0$ or $f(z_{ij})=f(x_{ij})$.
This implies that the agents in $A(\phi_{f},i,j)$ are envious if and only if
$f(z_{ij})=f(x_{ij})>0$. And by Lemma 4.22, if the agents in $A(\phi_{f},i,j)$
are envious, then the number of envious agents in $A(\phi_{f},i,j)$ is exactly
${|{A(\phi_{f},i,j)}|}=f(x_{ij})=f(z_{ij})$. We thus have
$\kappa^{\\#}(\phi_{f})=\sum_{i\in[n^{*}]}\sum_{j\in[m^{*}]}f(z_{ij})$.

##  5 Egalitarian House Allocation

In this section, we deal with the EHA problems, where the goal is to minimize
the maximum envy experienced by any agent. We first discuss the polynomial
time algorithms for EHA.

###  5.1 Polynomial Time Algorithms for EHA

######  Theorem 5.1.

There is a polynomial-time algorithm for $[\nicefrac{{0}}{{1}}]$-Egalitarian
House Allocation when the agent valuations have an extremal interval
structure.

######  Proof 5.2.

In light of Remark 3.5, it suffices to prove for the case when agent
valuations are left-extremal. Let $\mathcal{I}:=(A,H,\mathcal{P};k)$ be an
instance of EHA with left-extremal valuations. Consider an envious agent
$a_{l}$ in the allocation, who approves the interval $[h_{1},h_{i}]$. Note
that if $\mathcal{I}$ is a Yes instance, no more than $k$ houses can be
allocated from $[h_{1},h_{i}]$, else the envy experienced by $a_{l}$ will be
more than $k$.

Based on this observation, the algorithm works as follows. We order the agents
in the increasing order of the length of their intervals, that is, $a$ appears
before $a^{\prime}$ if $\mathcal{P}(a)\subseteq\mathcal{P}(a^{\prime})$. We
guess the last envious agent $a_{l}$. There are at most $n$ such guesses.
Suppose the interval that $a_{l}$ approves is $[h_{1},h_{j}]$ for some
$j\in[m]$. Since any valid allocation is bound to allocate at most $k$ houses
from $[h_{1},h_{j}]$, we iterate over the number of houses $i$ allocated from
$[h_{1},h_{j}]$. (Note that $i\leq k$). For each such $i$, we construct the
associated preference graph $G_{i}=(A_{\geq l+i+1}\cup H_{\geq j+1};E)$ where
$A_{\geq l+i+1}=\\{a_{l+i+1},a_{l+i+2},\ldots a_{n}\\}$ and $H_{\geq
j+1}=\\{h_{j+1},\ldots h_{m}\\}$. We then find a matching in $G_{i}$ that
saturates $A_{\geq l+i+1}$, and if it does not exist, then the iteration is
discarded. The algorithm then constructs the allocation $\phi_{i}$ as follows.
The matched houses under $M_{i}$ are allocated to the matched agents. The
first $i$ houses from $[h_{1},h_{j}]$ are allocated to the first $i$ agents
whose interval ends after $h_{j}$, particularly, to
$\\{a_{l+1},a_{l+2},\ldots,a_{l+i}\\}$. The remaining unmatched houses are
assigned arbitrarily to the unmatched agents. If the number of remaining
houses is less than the remaining agents, then the iteration is discarded and
the algorithm moves to the next iteration. The algorithm returns Yes if for
some iteration $i$, $\phi_{i}$ is a complete allocation, that is, every agent
gets a house under $\phi_{i}$. Else, it returns No.

To argue the correctness of the above algorithm, we show that if $\mathcal{I}$
is a Yes instance, if and only if for some iteration $i$, there exists a
complete allocation $\phi_{i}$. In the forward direction, suppose
$\mathcal{I}$ is a Yes instance. There must exist some optimal allocation Opt
such that the maximum envy under Opt is at most $k$. Among all the envious
agents under Opt, consider the agent $a$ whose interval $[h_{1},h]$ is
longest, that is, for all envious agents $a^{\prime}$,
$\mathcal{P}(a^{\prime})\subseteq\mathcal{P}(a)$. Suppose Opt allocates
$k^{\prime}$ houses from $[h_{1},h]$. Then consider the iteration in $A$ that
iterates over the agent $a_{l}=a$ and $i=k^{\prime}$. (This implies
$[h_{1},h_{j}]=[h_{1},h]$). Note that under Opt, all the agents whose interval
ends after $h$ must get a house that they like. This implies that for all the
agents $\\{a_{l+1},a_{l+2},\ldots a_{n}\\}$, there exists a house that they
like and that can be allocated to them. As Opt allocates exactly
$k^{\prime}(=i)$ houses from $[h_{1},h_{j}]$, at most $i$ of the agents among
$\\{a_{l+1},a_{l+2},\ldots a_{n}\\}$ can get a house they like from
$[h_{1},h_{j}]$. For the remaining ones, there must exist at least one house
$[h_{j+1},h_{n}]$ that they like and can be allocated to them, which implies
that there must exist a matching saturating the said agents under the said
iteration $i$. Therefore all the agents $\\{a_{l+1},a_{l+2},\ldots a_{n}\\}$
get a house that they like under $\phi_{i}$. Also, since OPT is a complete
allocation, so there are enough remaining houses for the agents
$\\{a_{1},\ldots a_{l}\\}$ that can be allocated to them, once
$\\{a_{l+1},a_{l+2},\ldots a_{n}\\}$ get what they value. This implies that
there are enough houses remaining under $\phi_{i}$ as well to be allocated to
the remaining agents. (Note that even if all the agents $\\{a_{1},\ldots
a_{l}\\}$ are envious, their envy is bounded by at most $i\leq k$). This
implies that the allocation $\phi_{i}$ constructed in the iteration $i$ is
indeed complete, and the algorithm returns Yes.

In the reverse direction, suppose there exists a complete allocation
$\phi_{i}$. Note that all the envious agents under $\phi_{i}$ do not value any
house outside $[h_{1},h_{j}]$ and exactly $i(\leq k)$ houses are allocated
from $\\{h_{1},h_{j}\\}$. Therefore the maximum envy is at most $k$, and
$\mathcal{I}$ is a Yes instance. This concludes the proof.

We now state the algorithm for the restricted setting when every agent
approves exactly one house.

######  Theorem 5.3.

There is a polynomial-time algorithm for $[\nicefrac{{0}}{{1}}]$-Egalitarian
House Allocation when every agent approves exactly one house.

######  Proof 5.4.

Notice that when every agent approves exactly one house, then in any
allocation, the maximum envy $\kappa^{\dagger}(\phi)$ is bounded by $1$. Given
an instance $\mathcal{I}:=(A,H,\mathcal{P};k)$ of HA, we invoke the Hall’s
Violators Algorithm by Gan et al., (2019). The above algorithm checks whether
there is an envy-free allocation and returns one if it exists. Therefore, if
it returns an allocation, then $\kappa^{\dagger}(\phi)=0$, else it has to be
at least $1$ under any allocation.

###  5.2 Hardness Results for EHA

In this section, we establish the hardness of EHA for both binary and linear
orders, even under restricted settings.

######  Theorem 5.5.

There is a polynomial-time reduction from Independent Set to
$[\nicefrac{{0}}{{1}}]$-Egalitarian House Allocation, where every agent
approves at most two houses and every house is approved by at most ten agents.
This reduction shows that $[\nicefrac{{0}}{{1}}]$-Egalitarian House Allocation
is $\mathsf{NP}$-complete even when the target value of the maximum envy is
one.

######  Proof 5.6.

Let $\mathcal{I}:=(G=(V,E);k)$ be an instance of Independent Set. Since
Independent Set is known to be $\mathsf{NP}$-complete even on subcubic graphs,
we assume that $G$ is subcubic, i.e, that the degree of every vertex in $G$ is
at most three. We construct an instance of $[\nicefrac{{0}}{{1}}]$-EHA as
follows.

  * •

We introduce a house $h_{v}$ for every vertex $v$ in $V$. We call these the
_vertex houses_.

  * •

We also introduce $(3m+n)-k$ dummy houses.

  * •

We introduce an agent $a_{v}$ for every vertex $v\in V$ and three agents
$a_{e}^{1},a_{e}^{2},a_{e}^{3}$ for every edge $e\in E$. We refer to these as
the vertex and edge agents, respectively. We refer to the three agents
corresponding to a single edge as the _cohort_ around $e$.

  * •

All three edge agents corresponding to the edge $e=(u,v)$ value the houses
$h_{u}$ and $h_{v}$.

  * •

A vertex agent $a_{v}$ values the house $h_{v}$.

Note that in this instance of EHA, there are $(n-k)$ extra houses, $3m+n-k$
dummy houses, and every agent approves at most two houses. We set the maximum
allowed envy at one, that is, the reduced instance asks for an allocation
where every agent envies at most one other agent. This completes the
construction of the reduced instance. We now turn to a proof of equivalence.

#### The forward direction.

Let $S\subseteq V$ be an independent set of size $k$. Consider the allocation
$\phi$ that assigns $h_{v}$ to $a_{v}$ for all $v\in S$ and dummy houses to
all remaining agents. Note that all vertex agents are envy-free under this
allocation. If an edge agent envies two other agents, it must be two agents
who received vertex houses, since recipients of dummy houses are never a cause
for envy. So suppose an edge agent $a_{e}^{\circ}$ who approves, say, the
houses $h_{u}$ and $h_{v}$ is envious, then it implies that both $a_{u}$ and
$a_{v}$ belong to $S$ while it is also true that $(u,v)\in E$; contradicting
our assumption that $G[S]$ induces an independent set. This completes the
argument in the forward direction.

#### The reverse direction.

Let $\phi$ be an allocation with respect to which every agent envies at most
one other agent. First, note that if $e=(u,v)$ is an edge in $G$, then note
that $\phi$ can allocate at most one of the houses $h_{u}$ and $h_{v}$.
Suppose not. Then notice that at least one of the agents among the cohort of
edge agents corresponding to $e$, i.e, $a_{e}^{1},a_{e}^{2}$ and $a_{e}^{3}$
envy the two agents who were assigned the houses $h_{u}$ and $h_{v}$.

We say that $\phi$ is nice if every vertex house is either unallocated by
$\phi$ or allocated to a vertex agent who values it. If $\phi$ is not nice to
begin with, notice that it can be converted to a nice allocation by a sequence
of exchanges that does not increase the maximum envy of the allocation without
changing the set of allocated houses. In particular, suppose $h_{v}$ is
allocated to an agent $a\neq a_{v}$. Then we obtain a new allocation by
swapping the houses $h_{v}$ and $\phi(a_{v})$ between agents $a$ and $a_{v}$.
This causes $a_{v}$ to become envy-free. If $a$ is a vertex agent, then she
experiences the same envy as before. If $a$ is an edge agent, then we have two
possible scenarios. Suppose $a$ did not value $h_{v}$: then the amount of envy
experienced by $a$ is either the same or less than, the amount of envy she had
in the original allocation. On the other hand, if $a$ did value $h_{v}$, then
$a$ envies $a_{v}$ in the new allocation but nobody else, since $h_{u}$ is
unallocated in $\phi$.

Based on this, we assume, without loss of generality, that $\phi$ is a nice
allocation. Now note that any nice allocation $\phi$ is compelled to assign
$3m$ dummy houses among the $3m$ edge agents, and this leaves us with $n-k$
dummy houses that can be allocated among $n$ vertex agents. Therefore, at
least $k$ vertex agents are assigned vertex houses. Finally, observe that the
corresponding vertices induce an independent set in $G$ of size at least $k$.
Indeed, this follows from a fact that we have already argued: any two houses
corresponding to vertices that are endpoints of an edge cannot be both
allocated by $\phi$. This concludes the argument in the reverse direction.

######  Theorem 5.7.

There is a polynomial-time reduction from Multi-Colored Independent Set to
$[\succ]$-Egalitarian House Allocation. This reduction shows that
$[\succ]$-Egalitarian House Allocation is $\mathsf{NP}$-complete even when the
target value of the maximum envy is one.

######  Proof 5.8.

Let $\mathcal{I}:=(G=(V,E);k)$ be an instance of Multi-Colored Independent Set
with color classes $V_{1},\ldots,V_{k}$. By adding dummy global vertices if
required, we assume that $|V_{i}|=n\geq 3$ for all $i\in[k]$, and denote the
vertices in $V_{i}$ by $\\{u_{1}^{i},\ldots,u_{n}^{i}\\}$.

We now construct an instance of $[\succ]$-EHA as follows.

  * •

We introduce a house for every vertex $v$ in $V$. We call these the _vertex
houses_ and they are denoted by:

$H_{V}:=\\{h_{1}^{1},\ldots,h_{n}^{1}\\}\uplus\cdots\uplus\\{h_{1}^{k},\ldots,h_{n}^{k}\\}.$

  * •

We introduce a house $h_{e}$ for every edge $e$ in $E$. We call these the
_edge houses_ and denote this set of houses by $H_{E}$.

  * •

For each $1\leq i\leq k$, and for every $1\leq p\neq q\leq n$, we introduce
three houses $h_{[i;p,q]}^{1}$, $h_{[i;p,q]}^{2}$ and $h_{[i;p,q]}^{3}$. We
call them _special houses_.

  * •

We also introduce $k\cdot(n-1)$ additional houses, denoted by:

$H_{D}:=\\{d_{1}^{1},\ldots,d_{n-1}^{1}\\}\uplus\cdots\uplus\\{d_{1}^{k},\ldots,d_{n-1}^{k}\\}.$

  * •

We introduce an agent for every vertex $v\in V$, denoted by
$a_{[1,i]},\ldots,a_{[n,i]}$ for $1\leq i\leq k$. We call them _vertex
agents_.

  * •

We introduce an agent $a_{e}$ for every $e\in E$. We call them _edge agents_.

  * •

For each $1\leq i\leq k$, and for every $1\leq p\neq q\leq n$, we introduce
three agents $a_{[i;p,q,1]}$, $a_{[i;p,q,2]}$ and $a_{[i;p,q,3]}$. We call
them _guards_.

For a set $X$, we use $\overline{X}$ to denote an arbitrary order on the set
$X$. Also, for a fixed order, say $\sigma$, we use $[[\sigma]]_{i}$ to denote
the order $\sigma$ rotated $i$ times. For example, $[[x\succ y\succ
z]]_{2}=z\succ x\succ y$. Note that $\sigma$ is an order over $n$ elements,
then $[[\sigma]]_{n}=\sigma$. We also use $H$ to denote the set of houses in
the reduced instance, i.e.: $H=H_{V}\cup H_{E}\cup H_{D}$. We are now ready to
describe the preferences of the agents.

  * •

An edge agent corresponding to an edge $e=(u_{p}^{i},u_{q}^{j})$ that has
endpoints in $V_{i}$ and $V_{j}$ (with $i<j$) ranks the houses as follows:

$\succ_{e}:h_{p}^{i}\succ h_{q}^{j}\succ
h_{e}\succ\overline{H\setminus\\{h_{p}^{i},h_{q}^{j},h_{e}\\}}$

  * •

For each $1\leq i\leq k$, for every $1\leq p\neq q\leq n$, and
$\ell\in\\{1,2,3\\}$ the guard agent $a_{[i;p,q,\ell]}$ has the following
preference:

$\succ_{[i;p,q,\ell]}:h_{p}^{i}\succ h_{q}^{i}\succ
h_{[i;p,q]}^{\ell}\succ\overline{H\setminus\\{h_{p}^{i},h_{q}^{i},h_{[i;p,q]}^{\ell}\\}}.$

  * •

For $1\leq i\leq k$, the vertex agents $a_{[1,i]},\ldots,a_{[n,i]}$ rank the
houses as follows

$\displaystyle{\color[rgb]{.275,.51,.705}\definecolor[named]{pgfstrokecolor}{rgb}{.275,.51,.705}\succ_{[1,i]}}:\leavevmode\nobreak\
\leavevmode\nobreak\ $ $\displaystyle h^{i}_{1}\succ[[d^{i}_{1}\succ
d^{i}_{2}\succ d^{i}_{3}\succ\cdots\succ d^{i}_{n-1}]]_{0}$
$\displaystyle\succ\overline{H\setminus\\{h^{i}_{1},d^{i}_{1},d^{i}_{2},d^{i}_{3},\ldots,d^{i}_{n-1}\\}}$
$\displaystyle{\color[rgb]{.275,.51,.705}\definecolor[named]{pgfstrokecolor}{rgb}{.275,.51,.705}\succ_{[2,i]}}:\leavevmode\nobreak\
\leavevmode\nobreak\ $ $\displaystyle h^{i}_{2}\succ[[d^{i}_{1}\succ
d^{i}_{2}\succ d^{i}_{3}\succ\cdots\succ d^{i}_{n-1}]]_{1}$
$\displaystyle\succ\overline{H\setminus\\{h^{i}_{2},d^{i}_{1},d^{i}_{2},d^{i}_{3},\ldots,d^{i}_{n-1}\\}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \vdots$
$\displaystyle{\color[rgb]{.275,.51,.705}\definecolor[named]{pgfstrokecolor}{rgb}{.275,.51,.705}\succ_{[j,i]}}:\leavevmode\nobreak\
\leavevmode\nobreak\ $ $\displaystyle h^{i}_{j}\succ[[d^{i}_{1}\succ
d^{i}_{2}\succ d^{i}_{3}\succ\cdots\succ d^{i}_{n-1}]]_{j}$
$\displaystyle\succ\overline{H\setminus\\{h^{i}_{j},d^{i}_{1},d^{i}_{2},d^{i}_{3},\ldots,d^{i}_{n-1}\\}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \vdots$
$\displaystyle{\color[rgb]{.275,.51,.705}\definecolor[named]{pgfstrokecolor}{rgb}{.275,.51,.705}\succ_{[n-1,i]}}:\leavevmode\nobreak\
\leavevmode\nobreak\ $ $\displaystyle h^{i}_{n-1}\succ[[d^{i}_{1}\succ
d^{i}_{2}\succ d^{i}_{3}\succ\cdots\succ d^{i}_{n-1}]]_{n-1}$
$\displaystyle\succ\overline{H\setminus\\{h^{i}_{n-1},d^{i}_{1},d^{i}_{2},d^{i}_{3},\ldots,d^{i}_{n-1}\\}}$
$\displaystyle{\color[rgb]{.275,.51,.705}\definecolor[named]{pgfstrokecolor}{rgb}{.275,.51,.705}\succ_{[n,i]}}:\leavevmode\nobreak\
\leavevmode\nobreak\ $ $\displaystyle h^{i}_{n}\succ[[d^{i}_{1}\succ
d^{i}_{2}\succ d^{i}_{3}\succ\cdots\succ d^{i}_{n-1}]]_{n}$
$\displaystyle\succ\overline{H\setminus\\{h^{i}_{n},d^{i}_{1},d^{i}_{2},d^{i}_{3},\ldots,d^{i}_{n-1}\\}}$

Note that in this instance of EHA, there are $k\cdot(n-1)$ extra houses. We
set the maximum allowed envy at one, that is, the reduced instance asks for an
allocation where every agent envies at most one other agent. This completes
the construction of the reduced instance. We now turn to a proof of
equivalence.

#### The forward direction.

Let $S\subseteq V$ be a multicolored independent set. Let
$s:[k]\rightarrow[n]$ be such that:

$S=\\{u^{1}_{s(1)},u^{2}_{s(2)},\ldots,u^{k}_{s(n)}\\}.$

We now describe an allocation $\phi$ based on $S$. First, we let
$\phi(a_{e})=h_{e}$ for all $e\in E$. Also, for each $1\leq i\leq k$, and for
every $1\leq p\neq q\leq n$, we have $\phi(a_{i;p,q,1})=h_{i;p,q}^{1}$,
$\phi(a_{i;p,q,2})=h_{i;p,q}^{2}$ and $\phi(a_{i;p,q,3})=h_{i;p,q}^{3}$.

Now, for the vertex agents corresponding to the vertices of $V_{i}$, we have
the following if $s(i)\geq 2$:

$\phi(a_{j,i})=\begin{cases}d_{j}^{i}&\text{if }1\leq j<s(i),\\\
h^{i}_{j}&\text{if }j=s(i),\\\ d_{j-1}^{i}&\text{if }s(i)<j<n,\\\ \end{cases}$

and if $s(i)=1$, then we proceed as follows instead:

$\phi(a_{j,i})=\begin{cases}h^{i}_{1}&\text{if }j=1,\\\ d_{j-1}^{i}&\text{if
}j>1,\\\ \end{cases}$

Note that every house corresponding to a vertex not in $S$ remains unallocated
in $\phi$, implying, in particular, that exactly one vertex from each color
class corresponds to an allocated vertex house in $\phi$. We now argue that
every agent envies at most one other agent with respect to this allocation.

First, consider an edge agent $a_{e}$ corresponding to an edge
$e=(u_{p}^{i},u_{q}^{j})$ that has endpoints in $V_{i}$ and $V_{j}$ (with
$i<j$). Recall that $a_{e}$ gets her third-ranked house with respect to
$\phi$. Since at most one of $h_{p}^{i}$ or $h_{q}^{j}$ is allocated with
respect to $\phi$, we have that $a_{e}$ envies at most one agent.

Similarly, every guard agent receives the special house that she ranks third,
and at most one of the two top-ranked houses is allocated in $\phi$, since
both of the top-ranked houses belong to the same color class by construction.

Now we turn to the vertex agents. It is easily verified that every vertex
agent gets a house that they rank first (if they correspond to a vertex from
$S$), second, or third. Thus, vertex agents corresponding to vertices in $S$
are envy-free, and all other vertex agents envy at most one other agent. This
concludes the proof in the forward direction.

#### The reverse direction.

Let $\phi$ be an allocation for the reduced instance where every agent envies
at most one other agent. We make a series of claims about the allocation
$\phi$ that allows us to observe that $\phi$ has the following properties: it
allocates exactly one vertex house from the houses corresponding to vertices
in a common color class, and further, it allocates such a house to a vertex
agent. Such vertex houses are then easily seen to correspond to a multi-
colored independent set in $G$: indeed, if not, then the pair of adjacent
vertices would correspond to an edge agent who is envious of at least two
vertex agents, contradicting our assumption about $\phi$.

We first observe that we cannot allocate more than one house from among vertex
houses corresponding to vertices from a common color class of $G$.

######  Claim 12.

Let $i\in[k]$ be arbitrary but fixed. Among the vertex houses
$\\{h_{1}^{i},\ldots,h_{n}^{i}\\}$, $\phi$ leaves at least $(n-1)$ houses
allocated; in other words, $\phi$ allocates at most one house from among these
houses.

######  Proof 5.9.

Suppose not, and in particular, suppose $\phi$ allocates the houses
$h_{p}^{i}$ and $h_{q}^{i}$ for some $1\leq p\neq q\leq n$. Then at least one
of the three guard agents $a_{i;p,q,\ell}$ for $\ell\in\\{1,2,3\\}$ will envy
the two agents who receive these two houses, which contradicts the assumption
that every agent envies at most one other agent in the allocation $\phi$.

Since $k\cdot(n-1)$ vertex houses are unallocated, all remaining houses must
be allocated by $\phi$. In particular, all additional houses are allocated,
and we use this fact in our next claim.

######  Claim 13.

If a vertex house is allocated in $\phi$, then it is assigned to a vertex
agent.

######  Proof 5.10.

Suppose not. Let $i$ be such that the vertex house under consideration
corresponds to a vertex from $V_{i}$. Note that the additional houses
$\\{d_{1}^{i},\ldots,d_{n-1}^{i}\\}$ can be allocated among at most $(n-1)$ of
the agents corresponding to the vertices in $V_{i}$. Therefore, there is at
least one agent $a$ among the agents $a_{[j,i]}$, $j\in[n]$ who does not
receive any of the houses among her top $n$-ranked houses. Further, she was
also not assigned her top-ranked house, by the assumption we made for the sake
of contradiction. Since $\phi$ allocates all the houses in
$\\{d_{1}^{i},\ldots,d_{n-1}^{i}\\}$, the agent $a$ envies at $(n-1)\geq 2$
agents, and this is the desired contradiction.

The previous two claims imply the desired structure on $\phi$, and as argued
earlier, the subset of vertices corresponding to allocated vertex houses
induces a multicolored independent set in $G$, and this concludes the argument
in the reverse direction.

###  5.3 Parameterized Results for EHA

In this section, we present a linear kernel for $[\nicefrac{{0}}{{1}}]$-EHA
and discuss the tractable and the hard cases in the parameterized setting.

######  Theorem 5.11.

$[\nicefrac{{0}}{{1}}]$-Egalitarian House Allocation admits a linear kernel
parameterized by the number of agents. In particular, given an instance of
$[\nicefrac{{0}}{{1}}]$-Egalitarian House Allocation, there is a polynomial
time algorithm that returns an equivalent instance of
$[\nicefrac{{0}}{{1}}]$-Egalitarian House Allocation with at most twice as
many houses as agents.

######  Proof 5.12.

It suffices to prove the safety of Section 3. Let
$\mathcal{I}:=(A,H,\mathcal{P};k)$ denote an instance of HA with parameter
$k$. Further, let $\mathcal{I}^{\prime}=(H^{\prime}:=H\setminus
X,A^{\prime}:=A\setminus Y,\mathcal{P}^{\prime};k)$ denote the reduced
instance corresponding to $\mathcal{I}$. Recall that the parameter for the
reduced instance is $k$ as well.

If $\mathcal{I}$ is a Yes-instance of EHA, then there is an allocation
$\phi:A\rightarrow H$ with maximum envy at most $k$. By 2, we may assume that
$\phi$ is a nice allocation. This implies that the projection of $\phi$ on
$H^{\prime}\cup A^{\prime}$ is well-defined, and it is easily checked that
this gives an allocation with maximum envy at most $k$

On the other hand, if $\mathcal{I}^{\prime}$ is a Yes-instance of EHA, then