there is an allocation $\phi^{\prime}:A^{\prime}\rightarrow H^{\prime}$ with
maximum envy $k$. 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 maximum envy $k$.

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

######  Corollary 5.13.

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

######  Corollary 5.14.

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

######  Corollary 5.15.

$[\nicefrac{{0}}{{1}}]$-Egalitarian House Allocation is para-NP-hard when
parameterized by the solution size, i.e, the maximum envy, even when every
agent approves at most two houses.

######  Corollary 5.16.

$[\succ]$-Egalitarian House Allocation is para-NP-hard when parameterized by
the solution size, i.e., the maximum envy.

######  Theorem 5.17.

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

As in the case of $[\nicefrac{{0}}{{1}}]$-OHA, we prove Theorem 5.17 by
formulating the $[\nicefrac{{0}}{{1}}]$-EHA problem as an 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^{*}$ the number of types of houses.
Again, by Section 4.3, the number of variables will then be bounded separately
by $2^{\mathcal{O}(m^{*})}$ and $2^{\mathcal{O}(n^{*})}$.

Given an instance $\mathcal{I}=(A,H,\mathcal{P})$ of
$[\nicefrac{{0}}{{1}}]$-Egalitarian House Allocation, we define an ILP
$\texttt{P2}(\mathcal{I})$ that encodes the instance $\mathcal{I}$. The ILP
$\texttt{P2}(\mathcal{I})$ is very similar to $\texttt{P1}(\mathcal{I})$ with
exactly two distinctions. (1) The ILP $\texttt{P2}(\mathcal{I})$ has all the
variables of $\texttt{P1}(\mathcal{I})$. In addition,
$\texttt{P2}(\mathcal{I})$ has an integer variable $w$ that encodes the
maximum envy experienced by an agent. (2) In $\texttt{P2}(\mathcal{I})$, the
variable $z_{ij}$ for $i\in[n^{*}],j\in[m^{*}]$ encodes the envy experienced
by each agent of type $i$ who receives a house of type $j$. Note that the envy
experienced by such an agent is always either $0$, or
$\sum_{i^{\prime}\in[n^{*}]}\sum_{j^{\prime}\in\mathcal{P}(i)}x_{i^{\prime}j^{\prime}}$.
And since $w$ is the maximum envy experienced by an agent, we must also have
$z_{ij}\leq w$ for every $i\in[n^{*}],j\in[m^{*}]$.

(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})$
(C4.a.$i.j$). | $z_{ij}\leq nd_{ij}$ | for every $i\in[n^{*}]$, $j\in[m^{*}]$
(C4.b.$i.j$). | $\left(\sum_{i^{\prime}\in[n^{*}]}\sum_{j^{\prime}\in\mathcal{P}(i)}x_{i^{\prime}j^{\prime}}\right)-z_{ij}\leq n(1-d_{ij})$
(C4.c.$i.j$). | $z_{ij}\leq n\sum_{i^{\prime}\in[n^{*}]}\sum_{j^{\prime}\in\mathcal{P}(i)}x_{i^{\prime}j^{\prime}}$
(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\\}$
(C7). | $w\geq 0$ |
(C8.$i.j$). | $z_{ij}\leq w$ | for every $i\in[n^{*}]$, $j\in[m^{*}]$
Table 4: The constraints of the ILP $\texttt{P2}(\mathcal{I})$.

We now formally describe the ILP. Minimize $w$ subject to the constraints in
Table 4.

######  Proof 5.18 (Proof Outline of Theorem 5.17).

Observe that $\texttt{P2}(\mathcal{I})$differs from
$\texttt{P1}(\mathcal{I})$in constraints C4.a.$i.j$, C4.b.$i.j$ and
C4.c.$i.j$. These three constraints together now ensure that for any feasible
solution $f$ for $\texttt{P2}(\mathcal{I})$, we either have $f(z_{ij})=0$ or
$f(z_{ij})=\sum_{i^{\prime}\in[n^{*}]}\sum_{j^{\prime}\in\mathcal{P}(i)}f(x_{i^{\prime}j^{\prime}})$.
(Also, constraint C4.c.$i.j$ subsumes the constraint C3.c$i.j$ in
$\texttt{P1}(\mathcal{I})$.) The only other difference is the addition of
constraints C7 and C8.$i.j$. We can show that appropriate counterparts of
Claims 10 and 11 hold for $\texttt{P2}(\mathcal{I})$. So do appropriate
counterparts of Claims 7, 8 and 9. In particular, we have
$\kappa^{\dagger}(\mathcal{I})=\mathsf{opt}(\texttt{P2}(\mathcal{I}))$.
Theorem 5.17 will then follow from Theorem 2.9.

######  Remark 5.19.

By modifying $\texttt{P2}(\mathcal{I})$, we can formulate an integer program
for $[\nicefrac{{0}}{{1}}]$-UHA. We only need to remove the variable $w$ and
the constraints C7 and C8.$i.j$ for $i\in[n^{*}],j\in[m^{*}]$ and replace the
objective function with $\sum_{i\in[n^{*}]}\sum_{j\in[m^{*}]}x_{ij}z_{ij}$.
Notice that while all the constraints in this integer program are linear, the
objective function is quadratic. We thus have an integer quadratic program
(IQP). The value of the largest coefficient in the constraints and the
objective function is $nm$. It is known that IQP is fixed-parameter tractable
when parameterized by the number of variables plus the value of the largest
coefficient [Lokshtanov, (2015)]. Fixed-parameter tractability results for IQP
w.r.t. other parameters are also known [Eiben et al., (2019)].

##  6 Utilitarian House Allocation

We now deal with the UHA problems, where the goal is to minimize total envy.
We first discuss the polynomial time algorithms for Utilitarian House
Allocation.

###  6.1 Polynomial Time Algorithms for UHA

######  Theorem 6.1.

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

######  Proof 6.2.

Consider an instance $\mathcal{I}=(H,A,\mathcal{P};k)$ of
$[\nicefrac{{0}}{{1}}]$-UHA. In light of Remark 3.5, assume that the
valuations have a left-extremal structure. Our algorithm relies on the
existence of an optimal allocation with some desirable properties. To that
end, consider an allocation ${{\phi}:{A}\rightarrow{H}}$. We say that an
ordered pair of agents $(a_{i},a_{j})\in A\times A$ is rogue under $\phi$ if
$i<j$, $\phi(a_{i})\in\mathcal{P}(a_{i})$ and
$\phi(a_{j})\notin\mathcal{P}(a_{j})$. That is, for $i<j$, $(a_{i},a_{j})$ is
a rogue pair if the $a_{i}$ values the house that she receives and $a_{j}$
does not value that she receives. Consider a rogue pair $(a_{i},a_{j}).$
Recall that we are in the left-extremal setting, and hence
$\mathcal{P}(a_{i})\subseteq\mathcal{P}(a_{j})$, which implies that
$\phi(a_{i})\in\mathcal{P}(a_{j})$. Thus $a_{j}$ is envious under $\phi$.

We say that $\phi$ is rogue-free if there does not exist any rogue pair under
$\phi$. Notice that if $\phi$ is rogue-free, then there exists
$t(\phi)\in[n]\cup\left\\{{0}\right\\}$ such that for every $i\in[n]$ with
$i>t(\phi)$, we have $\phi(a_{i})\in\mathcal{P}(a_{i})$, and hence the agent
$a_{i}$ envy-free. For $i\leq t(\phi)$, the agent $a_{i}$ may or may not be
envy-free.

######  Claim 14.

There exists a rogue-free optimal allocation.

######  Proof 6.3.

Consider an optimal allocation ${{\phi}:{A}\rightarrow{H}}$ that minimizes the
number of rogue pairs. By optimal, we mean that
$\kappa^{\star}(\mathcal{I})=\kappa^{\star}(\phi)$. If $\phi$ is rogue-free,
then the claim trivially holds. So, assume that $\phi$ is not rogue-free. Then
there exists a rogue pair under $\phi$. We fix a rogue pair $(a_{i},a_{j})$ as
follows. Let $a_{i}$ be the first agent such that $(a_{i},a_{p})$ is a rogue
pair for some $p\in[n]$. Then choose $j$ such that $a_{j}$ is the last agent
such that $(a_{i},a_{j})$ is a rouge pair. Since $(a_{i},a_{j})$ is a rogue
pair, we have $i<j$, $\phi(a_{i})\in\mathcal{P}(a_{i})$ and
$\phi(a_{j})\notin\mathcal{P}(a_{j})$. Since $i<j$, we have
$\mathcal{P}(a_{i})\subseteq\mathcal{P}(a_{j})$, which implies that
$\phi(A)\cap\mathcal{P}(a_{i})\subseteq\phi(A)\cap\mathcal{P}(a_{j})$. Notice
first that $a_{j}$ is envious as
$\phi(a_{i})\in\mathcal{P}(a_{i})\subseteq\mathcal{P}(a_{j})$. And that the
number of agents that $a_{j}$ envies,
$\mathcal{E}_{\phi}(a_{j})={|{\phi(A)\cap\mathcal{P}(a_{j})}|}$.

Let $\phi^{\prime}$ be the allocation obtained from $\phi$ by swapping the
houses of $a_{i}$ and $a_{j}$. That is, $\phi^{\prime}(a_{i})=\phi(a_{j})$,
$\phi^{\prime}(a_{j})=\phi(a_{i})$ and $\phi^{\prime}(a_{r})=\phi(a_{r})$ for
every $r\in[n]\setminus\left\\{{i,j}\right\\}$. Then, $a_{i}$ is envious under
$\phi^{\prime}$ as
$\phi^{\prime}(a_{i})=\phi(a_{j})\notin\mathcal{P}(a_{j})\supseteq\mathcal{P}(a_{i})$.
And the number of agents $a_{i}$ envies,
${|{\mathcal{E}_{\phi^{\prime}}(a_{i})}|}={|{\phi^{\prime}(A)\cap\mathcal{P}(a_{i})}|}$.
Now, $a_{j}$ is not envious under $\phi^{\prime}$ as
$\phi^{\prime}(a_{j})=\phi(a_{i})\in\mathcal{P}(a_{i})\subseteq\mathcal{P}(a_{j})$.

Notice that $\phi(A)=\phi(A^{\prime})$. We thus have
${|{\mathcal{E}_{\phi^{\prime}}(a_{i})}|}={|{\phi^{\prime}(A)\cap\mathcal{P}(a_{i})}|}\leq{|{\phi(A)\cap\mathcal{P}(a_{j})}|}={|{\mathcal{E}_{\phi}(a_{j})}|}$.
Therefore,
$\kappa^{\star}(\phi^{\prime})=\kappa^{\star}(\phi)-{|{\mathcal{E}_{\phi}(a_{j})}|}+{|{\mathcal{E}_{\phi^{\prime}}(a_{i})}|}\leq\kappa^{\star}(\phi)$.
Since $\phi$ is optimal, we can conclude that $\phi^{\prime}$ is optimal as
well.

Now, we claim that the number of rogue pairs under $\phi^{\prime}$ is strictly
less than that under $\phi$, which will contradict the definition of $\phi$.
Notice first that $(a_{i},a_{j})$ is a rogue-pair under $\phi$ but not under
$\phi^{\prime}$. Consider $p,q\in[n]$ such that $(a_{p},a_{q})$ is a rogue
pair under $\phi^{\prime}$, but not under $\phi$. Then, either $q=i$ or $p=j$.
If $q=i$, then $p<q=i<j$ and $(a_{p},a_{j})$ is a rogue pair under $\phi$,
which contradicts our choice of $i$. If $p=j$, then $j=p<q$, then
$(a_{i},a_{q})$ is a rogue pair, which contradicts our choice of $j$. Thus the
number of rogue pairs under $\phi^{\prime}$ is strictly less than that under
$\phi$, a contradiction. Hence, we conclude that $\phi$ is rogue-free.

For an allocation ${{\phi}:{A}\rightarrow{H}}$, let $S_{\phi}=\left\\{{a\in
A\leavevmode\nobreak\ |\leavevmode\nobreak\
\phi(a)\notin\mathcal{P}(a)}\right\\}$ and $T_{\phi}=\\{a\in
A\leavevmode\nobreak\ |\leavevmode\nobreak\ \phi(a)\in\mathcal{P}(a)\\}$. Note
that $\left\\{{S_{\phi},T_{\phi}}\right\\}$ is a partition of $A$ (with one of
the parts possibly being empty). We say that $\phi$ is nice if no agent in
$S_{\phi}$ envies any other agent in $S_{\phi}$. Equivalently, $\phi$ is nice
if $\phi(S_{\phi})\cap\mathcal{P}(S_{\phi})=\emptyset$.

######  Claim 15.

There exists an optimal rogue-free allocation that is also nice.

######  Proof 6.4.

Let $\phi$ be an optimal (i.e.,
$\kappa^{\star}(\mathcal{I})=\kappa^{\star}(\phi)$) rogue-free allocation that
minimizes ${|{S_{\phi}}|}$. then there exists
$t_{\phi}\in[n]\cup\left\\{{0}\right\\}$ such that
$S_{\phi}=\left\\{{a_{1},\ldots,a_{t(\phi)}}\right\\}$ and
$T_{\phi}=\left\\{{a_{t(\phi)+1},\ldots,a_{n}}\right\\}$. If
${|{S_{\phi}}|}\leq 1$, then the claim trivially holds. So, assume that
${|{S_{\phi}}|}>2$. Suppose that there exist $a_{i},a_{j}\in S$ such that
$a_{j}$ envies $a_{i}$. Then, as
$\mathcal{P}(a_{j})\subseteq\mathcal{P}(a_{t(\phi)})$, $a_{t(\phi)}$ envies
$a_{i}$ as well. Let $\phi^{\prime}$ be the allocation obtained from $\phi$ by
swapping the houses of $a_{i}$ and $a_{t(\phi)}$. Then we have
$S_{\phi^{\prime}}=S_{\phi}\setminus\left\\{{a_{t(\phi)}}\right\\}$ and
$T_{\phi^{\prime}}=T_{\phi}\cup\left\\{{a_{t(\phi)}}\right\\}$. Thus,
${|{S_{\phi^{\prime}}}|}<{|{S_{\phi}}|}$, which contradicts the definition of
$\phi$. We can thus conclude that no agent in $S_{\phi}$ envies any agent in
$S_{\phi}$.

######  Claim 16.

Let $\phi$ be a nice rogue-free allocation. Consider a house
$h\in\phi(T_{\phi})$. Then, (1) the number of agents who envy $\phi^{-1}(h)$
is exactly $|\\{a^{\prime}\in S_{\phi}\leavevmode\nobreak\
|\leavevmode\nobreak\ h\in\mathcal{P}(a^{\prime})\\}|$. And (2)
$\kappa^{\star}(\phi)=\sum_{h\in T_{\phi}}{|{a^{\prime}\in
S_{\phi}\leavevmode\nobreak\ |\leavevmode\nobreak\
h\in\mathcal{P}(a^{\prime})}|}$.

######  Proof 6.5.

By the definition of $T_{\phi}$, no agent in $T_{\phi}$ envies $\phi^{-1}(h)$.
Hence the number of agents who envy $\phi^{-1}(h)$ is exactly equal to the
number of agents in $S_{\phi}$ who value $h$. This is precisely what assertion
(1) says. Now, to compute $\kappa^{\star}(\phi)$, for all
$h\in\phi(T_{\phi})$, we only need to sum the number of agents in $S^{\prime}$
value $h$. This is precisely what assertion (2) says.

Informal description of our algorithm: Based on Claims 14-16, we are now ready
to describe our algorithm. Informally, our algorithm works as follows. We are
given an instance $\mathcal{I}=(A,H,\mathcal{P};k)$. Suppose that $\phi$ is
the optimal allocation that we are looking for. By 15, we can assume that
$\phi$ is rogue-free and nice. We guess $t_{\phi}$. There are at most $n+1$
guesses. For the correct guess, we correctly identify $S_{\phi}$ and
$T_{\phi}$. Then, $\phi$ must allocate to each $a\in T_{\phi}$ a house that
$a$ values. To each agent $a^{\prime}\in S_{\phi}$, $\phi$ must allocate a
house that no agent in $S_{\phi}$ values. And for a house $h\in H$, the envy
generated by allocating $h$ is precisely the number of agents in $S_{\phi}$
who value $h$. We can thus reduce the problem to a minimum cost maximum
matching problem, where the cost of matching each $h\in H$ to (1) an agent
$a\in T_{\phi}$ who values $h$ is precisely ${|{a^{\prime}\in
S_{\phi}\leavevmode\nobreak\ |\leavevmode\nobreak\ a^{\prime}\text{ values
}h}|}$; (2) an agent $a\in T_{\phi}$ who does not value $h$ is prohibitively
high; (3) an agent $a^{\prime}\in S_{\phi}$ is $0$ if no agent in $S_{\phi}$
values $h$, and prohibitively high otherwise. And we can compute a minimum
cost maximum matching in polynomial time.

Algorithm: We are given an instance $\mathcal{I}=(A,H,\mathcal{P};k)$ as
input. For each fixed $t\in[n]\cup\left\\{{0}\right\\}$, we do as follows. We
partition $A$ into two sets $S$ and $T$ as follows:
$S=\left\\{{a_{1},\ldots,a_{t}}\right\\}$ and
$T=\left\\{{a_{t+1},\ldots,a_{n}}\right\\}$. We construct a complete bipartite
graph $G_{t}^{\star}$, with vertex bipartition $A\uplus H$ and a cost function
$c_{t}$ on the edges defined as follows:

$c_{t}({\color[rgb]{.185,.31,.31}\definecolor[named]{pgfstrokecolor}{rgb}{.185,.31,.31}(a,h)})=\begin{cases}{|{a^{\prime}\in
S\leavevmode\nobreak\ |\leavevmode\nobreak\
h\in\mathcal{P}(a^{\prime})}|}&\text{if }a\in T\text{ and }a\text{ values
}h,\\\ 0&\text{if }a\in S\text{ and no agent }a^{\prime}\in S\text{ values
}h,\\\ k+1&\text{otherwise.}\end{cases}$

If $G_{t}^{\star}$ contains a matching of size $n$ and cost at most $k$ for
any $t\in[n]\cup\left\\{{0}\right\\}$, then we return that $\mathcal{I}$ is a
yes-instance of [$\nicefrac{{0}}{{1}}$]-UHA. If $G_{t}^{\star}$ does not
contain such a matching for any choice of $t\in[n]\cup\left\\{{0}\right\\}$,
then we return that $\mathcal{I}$ is a no-instance of
[$\nicefrac{{0}}{{1}}$]-UHA.

Correctness: To see the correctness of our algorithm, assume first that there
exists $t\in[n]\cup\left\\{{0}\right\\}$ for which $G_{t}^{\star}$ contains a
matching, say $M$, of size $n$ and cost at most $k$. Then, since ${|{M}|}=n$,
$M$ saturates $A$. Consider an allocation ${{\phi_{M}}:{A}\rightarrow{H}}$
defined as follows: for each $(a,h)\in M$, $\phi_{M}$ allocates $h$ to $a$. We
claim that $\kappa^{\star}(\phi_{M})=c_{t}(M)\leq k$. First, each $a\in T$
values $\phi_{M}(a)$, for otherwise, $c_{t}((a,\phi_{M}(a)))=k+1$, which is
not possible. So, $a\in T$ does not envy any agent. Similarly, each
$a^{\prime}\in S$ does not value $\phi_{M}(a^{\prime\prime})$ for any
$a^{\prime\prime}\in S$, for otherwise,
$c_{t}((a^{\prime\prime},\phi_{M}(a^{\prime\prime})))=k+1$, which is not
possible. So, for $a^{\prime},a^{\prime\prime}\in S$, $a^{\prime}$ does not
envy $a^{\prime\prime}$. Also, for $(a^{\prime},h)\in M$ with $a^{\prime}\in
S$, we have $c_{t}((a^{\prime},h))=0$. Now, an agent $a^{\prime}\in S$ may
envy an agent $a\in T$. But note that every $h\in\phi_{M}(T)$ contributes
exactly ${|{a^{\prime}\in S\leavevmode\nobreak\ |\leavevmode\nobreak\
h\in\mathcal{P}(a^{\prime})}|}=c_{t}((a,h))$ , where $\phi_{M}(a)=h$, to
$\kappa^{\star}(\phi_{M})$. Hence,
$\kappa^{\star}(\phi_{M})=\sum_{\begin{subarray}{c}h\in\phi_{M}(T)\\\ (a,h)\in
M\end{subarray}}c_{t}((a,h))=\sum_{\begin{subarray}{c}(a,h)\in M\\\ a\in
T\end{subarray}}c_{t}((a,h))\leq k$.

Conversely, assume that $\mathcal{I}=(A,H,\mathcal{P};k)$ is a yes-instance.
Let ${{\phi}:{A}\rightarrow{H}}$ be an optimal allocation. By 15, we assume
without loss of generality that $\phi$ is rogue-free and nice. Consider the
iteration of our algorithm for which $t=t_{\phi}$. And consider the matching
$M_{\phi}$ in $G_{t}^{\star}$ defined as
$M_{\phi}=\left\\{{(a,\phi(a))\leavevmode\nobreak\ |\leavevmode\nobreak\ a\in
A}\right\\}$. We claim that $c_{t}(M_{\phi})=\kappa^{\star}(\phi)\leq k$.
First, consider $a\in S$. Since $\phi$ is nice, no $a^{\prime}\in S$ values
$\phi(a)$, which implies that $c_{t}(a,\phi(a))=0$. Now, consider $a\in T$.
Since $\phi$ is rogue-free, $a$ values $\phi(a)$. By 16, $\phi(a)$ contributes
exactly ${|{\\{a^{\prime}\in S\leavevmode\nobreak\ |\leavevmode\nobreak\
a^{\prime}\text{ values }\phi(a)\\}}|}=c_{t}(a,\phi(a))$ to
$\kappa^{\star}(\phi)$. Thus, $c_{t}(M_{\phi})=\sum_{(a,\phi(a))\in
M_{\phi}}c_{t}(a,\phi(a))=\sum_{\begin{subarray}{c}(a,\phi(a))\in M_{\phi}\\\
a\in T\end{subarray}}c_{t}((a,\phi(a)))=\sum_{a\in T}{|{\\{a^{\prime}\in
S\leavevmode\nobreak\ |\leavevmode\nobreak\ a^{\prime}\text{ values
}\phi(a)\\}}|}=\kappa^{\star}(\phi)\leq k$.

We now turn to the restricted setting where every agent likes exactly one
house. In this case, the total envy is equal to the number of envious agents,
that is, $\kappa^{\star}(\phi)=\kappa^{\\#}(\phi)$, so the following result
follows from Theorem 4.4.

######  Corollary 6.6.

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

###  6.2 Parameterized Results

In this section, we discuss the parameterized results for UHA. First, we
design a linear kernel for $[\nicefrac{{0}}{{1}}]$-UHA.

######  Theorem 6.7.

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

######  Proof 6.8.

It suffices to prove the safety of Section 3. Let
$\mathcal{I}:=(A,H,\mathcal{P};k)$ denote an instance of HA. 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 UHA, then there is an allocation
$\phi:A\rightarrow H$ with total envy at most $k$. By 3, 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 total envy at most $k$.

On the other hand, if $\mathcal{I}^{\prime}$ is a Yes-instance of UHA, then
there is an allocation $\phi^{\prime}:A^{\prime}\rightarrow H^{\prime}$ with
total envy at most $k$. 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 total envy at most $k$.

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

######  Corollary 6.9.

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

######  Corollary 6.10.

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

($n,m,n^{\star}$) | OHA | EHA |  |  | Time/Instance
---
OHA, EHA
(in sec.)
|  | Env.
---
Agents
($\kappa^{\star}(\phi))$
| Max
---
Envy
| Total
---
Envy
| Env.
---
Agents
| Max
---
Envy
($\kappa^{\dagger}(\phi)$)
| Total
---
Envy
(30, 30, 1) | 15.11 | 14.89 | 216.71 | 15.11 | 14.89 | 216.71 | 0.003, 0.002
(30, 30, 5) | 0.95 | 8.78 | 12.33 | 9.07 | 7.56 | 11.29 | 0.19, 0.10
(30, 30, 15) | 0 | 0 | 0 | 0 | 0 | 0 | 0.20, 0.33
(30, 40, 1) | 10.18 | 19.82 | 191.76 | 20.18 | 9.82 | 188.16 | 0.01, 0.003
(60, 60, 1) | 30.36 | 29.64 | 888.08 | 30.36 | 29.64 | 888.08 | 0.006, 0.002
(60, 60, 15) | 0.01 | 0.31 | 0.31 | 0.21 | 0.21 | 0.21 | 0.57, 0.10
(60, 60, 30) | 0 | 0 | 0 | 0 | 0 | 0 | 2.00, 4.21
(120, 120, 1) | 59.45 | 60.55 | 3567.8 | 59.45 | 60.55 | 3567.8 | 0.01, 0.002
(120, 120, 5) | 3.83 | 57.07 | 218.79 | 66.62 | 51.07 | 200.63 | 0.11, 0.20
(120, 120, 15) | 0 | 0 | 0 | 0 | 0 | 0 | 1.98, 4.26
(120, 130, 5 ) | 0 | 0 | 0 | 0 | 0 | 0 | 0.11, 0.10
Table 5: A summary of the results, averaged over 100 instances of each type.
The OHA column corresponds to the solution from OHA ILP and the max-envy and
total envy in that column shows those values when the number of envious agents
is minimized. Similarly for the EHA column.

##  7 Experiments

We implemented the ILP for OHA and EHA over synthetic datasets of house
allocation problems generated uniformly at random. We used Gurobi Optimizer
version $9.5.1$. The average was taken over $100$ trials for each instance. A
summary is recorded in Table 5. For a fixed number of houses and agents,
notice that as the number of agent types, $n^{\star}$ increases, the number of
envious agents and the maximum envy decreases. Instances with identical
valuations (where $n^{\star}=1$) seem to admit more envy than the other
extreme (where $n^{\star}=n$). This is due to the fact when valuations are
identical, there is more contention on the specific subset of goods. On the
contrary, for instances with $m^{\star}=1$, envy-free allocations always
exist. Indeed, when $m^{\star}=1$, all houses are of the same type, which
means that an agent either likes all the houses or dislikes all of them and in
either case, she is envy-free no matter which house she gets. Also note that,
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.

##  8 Price of Fairness

In this section, in addition to the envy-minimization, we will focus on the
social welfare of an allocation, as captured by the sum of the individual
agent utilities. An allocation is considered more efficient when it results in
a higher level of social welfare. Minimizing the envy objectives can lead to
inefficient allocations with poor social welfare. Indeed, our algorithms for
OHA, EHA and UHA first check if there are enough (more than $n$) dummy houses
and if so, allocate these dummy houses to everyone, potentially leading to an
envy-free solution, but with no social welfare gain. Quantifying this welfare
loss, incurred as the cost of minimizing envy is, therefore, an imperative
consideration. In particular, we discuss the worst-case welfare loss under
different scenarios when any of the envy objectives is supposed to be
minimized, and give tight bounds for the same.

We first define the Price of Fairness in the house allocation setting as
follows. We use the notation $PoF_{OHA}$ to denote the fact that the fairness
notion under consideration is the minimum number of envious agents.
$PoF_{EHA}$ and $PoF_{UHA}$ defined analogously. When the meaning is clear
from the context, we drop the subscript and simply write $PoF$.

######  Definition 8.1.

For a house allocation instance $\mathcal{I}:=(A,H,\mathcal{P})$ with $n$
agents and $m$ houses, consider an allocation $\phi^{\star}$ that maximizes
the social welfare, denoted by $SW(\phi^{\star})$. Let $\phi$ be the optimal
allocation that minimizes the number of envious agents and $SW(\phi)$ be the
social welfare of $\phi$. Then, the price of fairness $PoF_{OHA}$ is defined
as

$PoF_{OHA}=\sup_{\mathcal{I}}\frac{SW(\phi^{\star})}{SW(\phi)}=\sup_{\mathcal{I}}\frac{\sum_{i\in
A}v_{i}(\phi^{\star}(i))}{\sum_{i\in A}v_{i}(\phi(i))},$

where the supremum is taken over all instances with $n$ agents and $m$ houses.

We say that an instance with binary valuations is normalized if every agent
likes an equal number of houses. Moreover, if every house is also liked by an
equal number of agents, then we say that the instance is doubly normalized. We
now present the bounds for $PoF$. We show that if $m=n$, then $PoF=1$ for all
the three envy minimization objectives. When $m>n$, if the instance is doubly
normalized, then $PoF=1$ but it can be as large as $n$ if we drop the double
normalization assumption.

Towards proving our results for the case when $m=n$, we first present the
following lemma based on the characterization that a matching $M$ in a graph
$G$ is maximum if and only if $G$ has no $M$-augmenting path. An
$M$-augmenting path is a path in $G$ that starts and ends at unmatched
vertices (vertices not included in $M$) and alternates between edges in the
matching $M$ and edges that are not in $M$.

######  Proposition 8.2 (folklore).

Let $G$ be a graph. For any $A^{\prime}\subseteq V(G)$, if $G$ contains a
matching that saturates $A^{\prime}$, then $G$ contains a maximum matching
that saturates $A^{\prime}$.

######  Proof 8.3.

Let $M^{\prime}$ be the matching that saturates $A^{\prime}$ in $G$. If
$M^{\prime}$ is itself a maximum matching, then we are done. Suppose not. Then
there exists an $M^{\prime}$-augmenting path $P$ in $G$ which starts and ends
at a vertex in $A\setminus A^{\prime}$. Replacing the edges of $M$ in $P$ by
the other edges in $P$ gives a strictly larger matching $M$ (with exactly one
more edge) which saturates $A^{\prime}$ and in addition, saturates two
vertices from $A\setminus A^{\prime}$. For every such augmentation, the set of
saturated vertices increases by two, keeping the original set of saturated
vertices intact. When no augmenting path exists, then by the characterization
of maximum matchings, the resulting matching $M$ must be a maximum matching
that saturates $A^{\prime}$.

We now consider the case when the number of houses is equal to the number of
agents, and show that $PoF=1$ in this case. Recall that we are under the
assumption that every agent values at least one house. Hence, when $m=n$ (and
the valuations are binary), in any allocation, an agent either receives a
house she values or she is envious; in particular, if agent $a$ is envious,
then she envies exactly $d(a)$ other agents, where $d(a)$ is the degree of $a$
in the associated preference graph. We will crucially rely on this fact to
prove that $PoF=1$. Our arguments will also use the correspondence between
matchings in the preference graph and allocations: For a matching $M$ in the
preference graph, we denote the allocation corresponding to $M$ by $\phi_{M}$,
which allocates the house $M(a)$ to the agent $a$ and allocates houses to the
remaining unmatched agents arbitrarily. Notice that the allocation $\phi_{M}$
need not be unique.

######  Lemma 8.4.

For an instance of house allocation with $m=n$ and binary valuations, there
exists an allocation that simultaneously maximizes the social welfare and
minimizes the number of envious agents.

######  Proof 8.5.

By Proposition 2.1, we know that any allocation that minimizes the number of
envious agents has exactly $|M|$ envy-free agents, where $M$ is the maximum
matching in the associated preference graph $G$. It is easy to see that the
maximum social welfare of the instance is also exactly $|M|$, hence any
allocation, say $\phi_{M}$, corresponding to a maximum matching $M$ in $G$
maximizes the welfare and minimizes the number of envious agents.

######  Lemma 8.6.

For an instance of house allocation with $m=n$ and binary valuations, there
exists an allocation that simultaneously maximizes social welfare and
minimizes the maximum envy.

######  Proof 8.7.

Let $M$ be a maximum matching in the associated preference graph $G$. Since
$m=n$, all the agents that are unmatched under $M$ are envious under
$\phi_{M}$. This implies that at least $n-|M|$ agents are envious. In
particular, if $|M|=n$, then under the allocation $\phi_{M}$, all agents are
envy-free, and $\phi_{M}$ simultaneously maximizes welfare and minimizes the
maximum envy, and thus the lemma trivially holds. So, assume that $|M|<n$. As
$M$ is a maximum matching, we can conclude that there is no matching that
saturates all the agents.

Let us now order the agents in the non-increasing order of their degrees, that
is, $a_{1},a_{2},\ldots,a_{n}$ such that $d(a_{1})\geq d(a_{2})\geq\cdots\geq
d(a_{n})$. Let $p_{1}\in[n]$ be the least index such that there is no matching
that saturates all of $a_{1},a_{2},...,a_{p_{1}}$. This implies that there is
a matching that saturates $a_{1},a_{2},\ldots a_{p_{1}-1}$ but none that
saturates the agents $a_{1},a_{2},...,a_{p_{1}}$. That is, in any allocation,
at least one agent among $a_{1},\ldots a_{p_{1}}$ is envious. Thus, the
maximum envy of the instance is at least $d(a_{p_{1}})$. But there is a
matching that saturates $a_{1},a_{2},\ldots,a_{p_{1}-1}$, which can be
extended to a corresponding allocation; and under such an allocation,
$a_{p_{1}}$ would be the first envious agent (first in the ordering
$a_{1},a_{2},\ldots,a_{n}$). Therefore, we can conclude that the maximum envy
of the instance is precisely equal to $d(a_{p_{1}})$. Now, we only have to
prove that there is indeed a _maximum_ matching that saturates
$a_{1},a_{2},\ldots,a_{p_{1}-1}$; and Proposition 8.2 guarantees that $G$ does
contain such a maximum matching (we simply need to apply Proposition 8.2 with
$A^{\prime}=\left\\{{a_{1},a_{2},\ldots,a_{p_{1}-1}}\right\\}$). This implies
that there is a welfare-maximizing allocation that also minimizes the maximum
envy.

######  Lemma 8.8.

For an instance of house allocation with $m=n$ and binary valuations, there
exists an allocation that simultaneously maximizes social welfare and
minimizes total envy.

######  Proof 8.9.

Consider an allocation, say $\phi$, that minimizes the total envy. We claim
that the matching $M$ corresponding to $\phi$ in the associated preference
graph $G$ is a maximum matching. If $M$ is not a maximum matching, then we
have an augmenting path, and we get a strictly larger matching $M^{\prime}$
such that the vertices saturated by $M$ are also saturated under $M^{\prime}$.
Now consider the allocation corresponding to $M^{\prime}$, say
$\phi_{M^{\prime}}$. Since $|M|<|M^{\prime}|$, the number of envious agents
under $\phi_{M^{\prime}}$ is strictly less than those under $\phi$; also all
envy-free agents under $\phi$ remain envy-free under $\phi_{M^{\prime}}$.
These arguments imply that the total envy under $\phi_{M^{\prime}}$ is less
than the total envy under $\phi$. This is a contradiction to the fact that
$\phi$ minimizes the total envy.

The following result now follows from Lemma 8.4, Lemma 8.6 and Lemma 8.8.

######  Theorem 8.10.

For an instance of house allocation with $m=n$ and binary valuations, $PoF=1$
for all the three envy-minimization objectives.

Theorem 8.10 tells us that when $m=n$, there is an allocation that
simultaneously maximizes welfare and minimizes any _one_ of the three measures
of envy. This does raise the following question: Can we simultaneously
maximize welfare and minimize _all_ three measures of envy? We show that we
can indeed do this; that is, there is an allocation that simultaneously
minimizes the number of envious agents, the maximum and total envy while
maximizing social welfare.

######  Theorem 8.11.

For an instance of house allocation with $m=n$ and binary valuations, 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.

######  Proof 8.12.

Let $M$ be a maximum matching in the associated preference graph $G$. First,
the corresponding allocation $\phi_{M}$ maximizes social welfare. Since $m=n$,
all the agents that remain unmatched under $M$ are envious under $\phi_{M}$.
This implies that at least $n-|M|$ agents are envious under any allocation.
Thus, if ${|{M}|}=n$, then every agent is envy-free under $\phi_{M}$, and
thus, the theorem trivially holds. So, assume from now on that ${|{M}|}<n$.

We first order the agents in the non-increasing order of their degrees, that
is, $a_{1},a_{2},\ldots,a_{n}$ such that $d(a_{1})\geq d(a_{2})\geq\cdots\geq
d(a_{n})$. Let $p_{1}\in[n]$ be the least index such that $G$ does not contain
a matching that saturates $\\{a_{1},a_{2},...,a_{p_{1}}\\}$. That is, there is
a matching that saturates all of $a_{1},a_{2},\ldots a_{p_{1}-1}$ but none
that saturates all of $a_{1},a_{2},...,a_{p_{1}}$. Now, let $p_{2}\in[n]$ be
the least index such that $p_{2}>p_{1}$ and $G$ does not contain a matching
that saturates $\\{a_{1},a_{2},\ldots a_{p_{2}}\\}\setminus\\{a_{p_{1}}\\}$
(if such an index $p_{2}$ exists); In general, having defined
$p_{1},p_{2},\ldots,p_{i-1}$, we define $p_{i}$ to be the least index in $[n]$
such that $p_{i}>p_{i-1}$ and $G$ does not contain a matching that saturates
$\\{a_{1},a_{2},\ldots
a_{p_{i}}\\}\setminus\\{a_{p_{1}},a_{p_{2}},\ldots,a_{p_{i-1}}\\}$. Let
$p_{1},p_{2},\ldots,p_{k}$ (for some $k\geq 1$), be the indices defined this
way. By their definition, $G$ contains a matching, say $M^{\prime}$, that
saturates $\\{a_{1},a_{2},\ldots
a_{n}\\}\setminus\\{a_{p_{1}},a_{p_{2}},\ldots a_{p_{k}}\\}$. Consider the
corresponding allocation $\phi_{M^{\prime}}$; recall that $\phi_{M^{\prime}}$
allocates houses along the edges of $M^{\prime}$ and the remaining agents,
i.e., $a_{p_{1}}\ldots a_{p_{k}}$, receive the remaining houses in an
arbitrary manner.

Before we proceed further, let us observe that we can indeed compute
$M^{\prime}$ and hence the corresponding allocation $\phi_{M^{\prime}}$ in
polynomial time. The arguments we have used so far are constructive. To
compute $M^{\prime}$, we only need to identify the indices
$p_{1},p_{2},\ldots,p_{k}$ and find a matching that saturates
$\left\\{{a_{1},a_{2},\ldots,a_{n}}\right\\}\setminus\left\\{{a_{p_{1}},a_{p_{2}},\ldots,a_{p_{k}}}\right\\}$.
And notice that to find each $p_{i}$, we only need to check if $G$ contains a
matching that saturates
$\left\\{{a_{1},a_{2},\ldots,a_{j}}\right\\}\setminus\left\\{{a_{p_{1}},a_{p_{2}},\ldots,a_{p_{i-1}}}\right\\}$
for each $j>p_{i-1}$, which we can do in polynomial time.

We will now show that the allocation $\phi_{M^{\prime}}$ satisfies all the
properties required by the statement of the theorem; that is,
$\phi_{M^{\prime}}$ maximizes welfare and minimizes the number of envious
agents, the maximum envy and the total envy. To that end, observe first that
$M^{\prime}$ does not saturate any of the agents
$a_{p_{1}},a_{p_{2}},\ldots,a_{p_{k}}$. Otherwise, let $p_{i}$ be the least
index in $\left\\{{p_{1},p_{2},\ldots,p_{k}}\right\\}$ such that $M^{\prime}$
saturates $a_{p_{i}}$. In particular, $M^{\prime}$ is a matching that
saturates
$\left\\{{a_{1},a_{2},\ldots,a_{p_{i}}}\right\\}\setminus\left\\{{a_{p_{1}},a_{p_{2}},\ldots,a_{p_{i-1}}}\right\\}$,
which contradicts the definition of $p_{i}$. By the same reasoning, we can
also conclude that that $M^{\prime}$ is indeed a maximum matching. If not,
then there is a larger matching, say $M^{\prime\prime}$, which also saturates
at least one of the $a_{p_{i}}$ in addition to saturating
$\\{a_{1},a_{2},\ldots a_{n}\\}\setminus\\{a_{p_{1}},a_{p_{2}},\ldots
a_{p_{k}}\\}$ (by Proposition 8.2), which again will lead to a contradiction.

Now, the fact that $M^{\prime}$ is a maximum matching immediately implies that
the corresponding allocation $\phi_{M^{\prime}}$ maximizes social welfare and
minimizes the number of envious agents. We will now use the same arguments we
used in the proof of Lemma 8.6 to show that $\phi_{M^{\prime}}$ minimizes the
maximum envy. Notice that the set of agents that are _not_ saturated by
$M^{\prime}$ is precisely
$\left\\{{a_{p_{1}},a_{p_{2}},\ldots,a_{p_{k}}}\right\\}$. This fact, along
with the fact that $M^{\prime}$ is a maximum matching, implies that the set of
envious agents under $\phi_{M^{\prime}}$ is precisely
$\left\\{{a_{p_{1}},a_{p_{2}},\ldots,a_{p_{k}}}\right\\}$. In particular,
$a_{p_{1}}$ is the first envious agent under $\phi_{M^{\prime}}$ (again, first
in the ordering $a_{1},a_{2},\ldots,a_{n}$). Thus, the maximum envy of the
allocation $\phi_{M^{\prime}}$ is $d(a_{p_{i}})$. By the definition of
$p_{1}$, in any allocation, at least one agent among $a_{1},\ldots a_{p_{1}}$
is envious, and hence the maximum envy in any allocation is at least
$d(a_{p_{i}})$ (because $d(a_{1})\geq d(a_{2})\geq\cdots\geq d(a_{n})$). From
these arguments, we can conclude that $\phi_{M^{\prime}}$ minimizes the
maximum envy.

To complete the proof, now we only need to argue that $\phi_{M^{\prime}}$
minimizes the total envy. To that end, we first prove the following claim.

######  Claim 17.

For every $i\in[k]$, every matching in $G$ does _not_ saturate at least $i$
agents from the set $\left\\{{a_{1},a_{2},\ldots,a_{p_{i}}}\right\\}$. Or
equivalently, for every $i\in[k]$, at least $i$ agents from the set
$\left\\{{a_{1},a_{2},\ldots,a_{p_{i}}}\right\\}$ are envious under every
allocation.

Suppose for a contradiction that $G$ contains a matching
$M^{\prime\prime\prime}$ such that the number of agents from
$\left\\{{a_{1},a_{2},\ldots,a_{p_{i}}}\right\\}$ that are not saturated by
$M^{\prime\prime\prime}$ is strictly less than $i$. Therefore,
$M^{\prime\prime\prime}$ saturates at least one agent from the set
$\left\\{{a_{p_{1}},a_{p_{2}},\ldots,a_{p_{i}}}\right\\}$; let $p_{j}$ be the
least such index such that $M^{\prime\prime\prime}$ saturates $a_{p_{j}}$. But
then $M^{\prime\prime\prime}$ saturates
$\left\\{{a_{1},a_{2},\ldots,a_{p_{j}}}\right\\}\setminus\left\\{{a_{p_{1}},a_{p_{2}},\ldots,a_{p_{j-1}}}\right\\}$,
which contradicts the definition of $p_{j}$. Notice that the second sentence
in the statement of the claim is merely a restatement of the first, because of
the correspondence between matchings and allocations: Under any allocation,
the envy-free agents and the houses they received form a matching in $G$.

Now, to complete the proof of the theorem, recall that the set of envious
agents under $\phi_{M^{\prime}}$ is precisely
$\left\\{{a_{p_{1}},a_{p_{2}},\ldots,a_{p_{k}}}\right\\}$, and thus the total
envy under $\phi_{M^{\prime}}$ is precisely $\sum_{i=1}^{k}d(a_{p_{i}})$.
Also, as we have already argued, $\phi_{M^{\prime}}$ minimizes the number of
envious agents, and hence we can conclude that at least $k$ agents are envious
under _every_ allocation. Assume now for a contradiction that
$\phi_{M^{\prime}}$ does not minimize the total envy. Let $\phi$ be an
allocation that minimizes the total envy. Again, at least $k$ agents are
envious under $\phi$; let $1\leq q_{1}<q_{2}<\cdots<q_{k}\leq n$ be such that
the agents $a_{q_{1}},a_{q_{2}},\ldots,a_{q_{k}}$ are the first $k$ envious
agents under $\phi$ (first in the ordering $a_{1},a_{2},\ldots,a_{n}$). Thus
the total envy under $\phi$ is at least $\sum_{i=1}^{k}d(a_{q_{i}})$. Now, by
our assumption, $\phi_{M^{\prime}}$ does not minimize the total envy and
$\phi$ does, and thus $\sum_{i=1}^{k}d(a_{p_{i}})>\sum_{i=1}^{k}d(a_{q_{i}})$;
we will derive a contradiction from this. Since
$\sum_{i=1}^{k}d(a_{p_{i}})>\sum_{i=1}^{k}d(a_{q_{i}})$, there exists an index
$i\in[k]$ such that $d(a_{p_{i}})>d(a_{q_{i}})$; let $i\in[k]$ be the least
index such that $d(a_{p_{i}})>d(a_{q_{i}})$. Hence $p_{i}<q_{i}$, which
implies that the set $\left\\{{a_{1},a_{2},\ldots,a_{p_{i}}}\right\\}$
contains at most $i-1$ of the agents $a_{q_{1}},a_{q_{2}},\ldots,a_{q_{i}}$.
But by the definition of the $q_{j}$s, the agents
$a_{q_{1}},a_{q_{2}},\ldots,a_{q_{k}}$ are the first $k$ envious agents under
$\phi$. We can thus conclude that the set
$\left\\{{a_{1},a_{2},\ldots,a_{p_{i}}}\right\\}$ contains at most $i-1$
agents who are envious under $\phi$, which contradicts Claim 17.

We have thus shown that $\phi_{M^{\prime}}$ minimizes the total envy, and this
completes the proof of the theorem.

We now consider the case when $m>n$ and the setting of the doubly normalized
valuations. The following result follows from the proof of Theorem $5$ in
Bhaskar et al., (2023), where they show that for such structured valuations,
every good can be assigned non-wastefully such that every agent derives the
value of at least one. In our setting, we can find an envy-free allocation
that is non-wasteful and hence, welfare maximizing as well, proving the
following result.

######  Corollary 8.13.

For $m>n$ and doubly normalized binary valuations, $PoF=1$ for all three envy-
minimization objectives.

It is easy to see that when there are dummy houses, then there can be
instances where the fair allocation can be highly inefficient. Consider the
case when number of dummy houses is at least the number of agents. Then,
irrespective of the individual valuations, every agent can get a dummy house
and be envy-free, leading to no social welfare at all. But, the following
result suggests that even when there aren’t any dummy houses, there are
instances where the price of fairness can be high.

######  Theorem 8.14.

For $m>n$ and binary valuations, $PoF=\Theta(n)$, for all the three envy
optimization objectives, even when there are no dummy houses to begin with.

######  Proof 8.15.

We first show that $PoF\geq\nicefrac{{n}}{{2}}$. We say that a house is
allocated non-wastefully if the receiving agent values it at $1$. Consider an
instance with $2n$ agents and $3n$ houses, such that $n>2$. Agent $1$ likes
the first $n$ houses, $2$ likes the next $n$ houses, and all of the remaining
$2n-2$ agents collectively like the last $n$ houses. The instance does not
have any dummy houses. Note that any welfare-maximizing allocation
$\phi^{\star}$ allocates $n+2$ houses non-wastefully. So $SW(\phi^{\star})\geq
n+2$. But in this instance, there exists an envy-free allocation $\phi$ that
allocates exactly $2$ houses non-wastefully to the first two agents. The last
$n$ houses remain unallocated under $\phi$, as they create Hall’s violator for
the set of last $2n-2$ agents. Therefore, the last $2n-2$ agents receive the
houses they don’t like, and the set of their liked houses remains unallocated.
This implies that $SW(\phi)\leq 2$. The PoF for this particular instance is,
therefore, $\nicefrac{{(n+2)}}{{2}}\approx n$. Since the instance had $2n$
agents to begin with, we have that in general, $PoF\geq\nicefrac{{n}}{{2}}$.

We now show that $PoF\leq n$. Since the valuations are binary, the maximum
possible social welfare under any allocation is $n$. Consider an envy-free
allocation $\phi$, if it exists. We claim that there is at least one house
that is allocated non-wastefully under $\phi$. Suppose not. Then every house
is allocated wastefully, and hence, $SW(\phi)=0$. But since there are no dummy
houses, there is at least one agent $a$ who likes (a subset of) the allocated
houses. But since welfare is zero, $a$ is an envious agent, which contradicts
the fact that we started with an envy-free allocation. Therefore,
$SW(\phi)\geq 1$. This implies that $PoF\leq n$.

If an envy-free allocation does not exist, consider $\phi$ to be an allocation
that minimizes the number of envious agents. Suppose the number of envious
agents under $\phi$ is $k$ and let $a$ be one such envious agent. If
$SW(\phi)=0$, then everyone, including $a$ receives a house that they do not
like. Now $a$ is envious because one of his liked houses, say $h$ is allocated
to some agent $\phi^{\prime}$ and that too wastefully. Consider the re-
allocation of the house $h$ to $a$ and the house $\phi(a)$ to $a^{\prime}$.
Then $a$ becomes envy-free, and no agent (including $a^{\prime}$) becomes
newly envious of this re-allocation, since the set of allocated houses is
exactly the same and $SW(\phi)=0$. This re-allocation has $k-1$ envious
agents, which contradicts the fact that we started with an optimal allocation.
Therefore, $SW(\phi)\geq 1$. This implies that $PoF\leq n$.

The argument for EHA and UHA is analogous. This settles our claim.

In the proof of Theorem 8.14, although the number of agent types in the lower
bound instance is $3$, the $PoF$ is linear in the number of agents. This
implies that we do not expect better bounds for instances with few agent
types.

##  9 Conclusion

We studied three kinds of natural quantifications of envy to be minimized in
the setting of house allocation: OHA, EHA, and UHA. Most of our results are
summarized in Table 1. We also show that both OHA and EHA are $\mathsf{FPT}$
when parameterized by the total number of house types or agent types. We also
look at the price of fairness in the context of house allocation and give
tight bounds for the same.

We leave several questions related to UHA open. Also, finding interesting
classes of structured input—beyond extremal intervals—for which these problems
are tractable is an important direction for future work.

## References

  * Abdulkadiroğlu and Sönmez, (1999) Abdulkadiroğlu, A. and Sönmez, T. (1999).  House allocation with existing tenants.  Journal of Economic Theory, 88(2):233–260.
  * Abraham et al., (2004) Abraham, D. J., Cechlárová, K., Manlove, D. F., and Mehlhorn, K. (2004).  Pareto optimality in house allocation problems.  In International Symposium on Algorithms and Computation, pages 3–15. Springer.
  * Aigner-Horev and Segal-Halevi, (2021) Aigner-Horev, E. and Segal-Halevi, E. (2021).  Envy-free matchings in bipartite graphs and their applications to fair division.  Information Sciences.
  * Barman et al., (2020) Barman, S., Bhaskar, U., and Shah, N. (2020).  Optimal Bounds on the Price of Fairness for Indivisible Goods.  In Proceedings of the 16th International Conference on Web and Internet Economics, pages 356–369.
  * Barman et al., (2018) Barman, S., Krishnamurthy, S. K., and Vaish, R. (2018).  Greedy algorithms for maximizing nash social welfare.  In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’18, page 7–13, Richland, SC. International Foundation for Autonomous Agents and Multiagent Systems.
  * Bei et al., (2021) Bei, X., Lu, X., Manurangsi, P., and Suksompong, W. (2021).  The Price of Fairness for Indivisible Goods.  Theory of Computing Systems, 65(7):1069–1093.
  * Bertsimas et al., (2011) Bertsimas, D., Farias, V. F., and Trichakis, N. (2011).  The Price of Fairness.  Operations Research, 59(1):17–31.
  * Beynier et al., (2019) Beynier, A., Chevaleyre, Y., Gourvès, L., Harutyunyan, A., Lesca, J., Maudet, N., and Wilczynski, A. (2019).  Local envy-freeness in house allocation problems.  Autonomous Agents and Multi-Agent Systems, 33(5):591–627.
  * Bhaskar et al., (2023) Bhaskar, U., Misra, N., Sethia, A., and Vaish, R. (2023).  The price of equity with binary valuations and few agent types.  In Deligkas, A. and Filos-Ratsikas, A., editors, Algorithmic Game Theory, pages 271–289, Cham. Springer Nature Switzerland.
  * Caragiannis et al., (2012) Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., and Kyropoulou, M. (2012).  The Efficiency of Fair Division.  Theory of Computing Systems, 50(4):589–610.
  * Choo et al., (2024) Choo, D., Ling, Y. H., Suksompong, W., Teh, N., and Zhang, J. (2024).  Envy-free house allocation with minimum subsidy.  Operations Research Letters, 54:107103.
  * Cygan et al., (2015) Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015).  Parameterized Algorithms.  Springer.
  * Downey and Fellows, (2013) Downey, R. G. and Fellows, M. R. (2013).  Fundamentals of Parameterized Complexity.  Texts in Computer Science. Springer.
  * Eiben et al., (2019) Eiben, E., Ganian, R., Knop, D., and Ordyniak, S. (2019).  Solving integer quadratic programming via explicit and structural restrictions.  In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, pages 1477–1484. AAAI Press.
  * Elkind and Lackner, (2015) Elkind, E. and Lackner, M. (2015).  Structure in dichotomous preferences.  In Proceedings of the 24th International Conference on Artificial Intelligence, IJCAI’15, page 2019–2025. AAAI Press.
  * Gan et al., (2019) Gan, J., Suksompong, W., and Voudouris, A. A. (2019).  Envy-freeness in house allocation problems.  Mathematical Social Sciences, 101:104–106.
  * Halpern et al., (2020) Halpern, D., Procaccia, A. D., Psomas, A., and Shah, N. (2020).  Fair division with binary valuations: One rule to rule them all.  In Web and Internet Economics: 16th International Conference, WINE 2020, Beijing, China, December 7–11, 2020, Proceedings 16, pages 370–383. Springer.
  * Hosseini et al., (2024) Hosseini, H., McGregor, A., Sengupta, R., Vaish, R., and Viswanathan, V. (2024).  Tight approximations for graphical house allocation.  In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’24, page 825–833, Richland, SC. International Foundation for Autonomous Agents and Multiagent Systems.
  * Hosseini et al., (2023) Hosseini, H., Payan, J., Sengupta, R., Vaish, R., and Viswanathan, V. (2023).  Graphical house allocation.  In 22nd International Conference on Autonomous Agents and Multiagent Systems, AAMAS.
  * Hylland and Zeckhauser, (1979) Hylland, A. and Zeckhauser, R. (1979).  The efficient allocation of individuals to positions.  Journal of Political Economy, 87(2):293–314.
  * Irving et al., (2006) Irving, R. W., Kavitha, T., Mehlhorn, K., Michail, D., and Paluch, K. E. (2006).  Rank-maximal matchings.  ACM Trans. Algorithms, 2(4):602–610.
  * Kamiyama et al., (2021) Kamiyama, N., Manurangsi, P., and Suksompong, W. (2021).  On the complexity of fair house allocation.  Operations Research Letters, 49(4):572–577.
  * Krysta et al., (2019) Krysta, P., Manlove, D. F., Rastegari, B., and Zhang, J. (2019).  Size versus truthfulness in the house allocation problem.  Algorithmica, 81(9):3422–3463.
  * Lackner and Skowron, (2023) Lackner, M. and Skowron, P. (2023).  Multi-winner voting with approval preferences.  Springer Nature.
  * Lenstra Jr., (1983) Lenstra Jr., H. W. (1983).  Integer programming with a fixed number of variables.  Math. Oper. Res., 8(4):538–548.
  * Lokshtanov, (2015) Lokshtanov, D. (2015).  Parameterized integer quadratic programming: Variables and coefficients.  CoRR, abs/1511.00310.
  * Manlove, (2013) Manlove, D. F. (2013).  Algorithmics of Matching Under Preferences, volume 2 of Series on Theoretical Computer Science.  WorldScientific.
  * Mathieson and Szeider, (2012) Mathieson, L. and Szeider, S. (2012).  Editing graphs to satisfy degree constraints: A parameterized approach.  Journal of Computer and System Sciences, 78(1):179–191.  JCSS Knowledge Representation and Reasoning.
  * Nguyen and Rothe, (2013) Nguyen, T. T. and Rothe, J. (2013).  How to decrease the degree of envy in allocations of indivisible goods.  In Algorithmic Decision Theory: Third International Conference, ADT 2013, Bruxelles, Belgium, November 12-14, 2013, Proceedings, page 271–284, Berlin, Heidelberg. Springer-Verlag.
  * Shams et al., (2021) Shams, P., Beynier, A., Bouveret, S., and Maudet, N. (2021).  Minimizing and balancing envy among agents using Ordered Weighted Average.  In 7th International Conference on Algorithmic Decision Theory, Toulouse, France.
  * Shapley and Scarf, (1974) Shapley, L. and Scarf, H. (1974).  On cores and indivisibility.  Journal of Mathematical Economics, 1(1):23–37.
  * Shende and Purohit, (2020) Shende, P. and Purohit, M. (2020).  Strategy-proof and envy-free mechanisms for house allocation.  J. Econ. Theory, 213:105712.
  * Sun et al., (2023) Sun, A., Chen, B., and Doan, X. V. (2023).  Equitability and Welfare Maximization for Allocating Indivisible Items.  Autonomous Agents and Multi-Agent Systems, 37(8).
  * Zhou, (1990) Zhou, L. (1990).  On a conjecture by gale about one-sided matching problems.  Journal of Economic Theory, 52(1):123–135.