On the Complexity of Fair House Allocation

Introduction

We consider the classical setting of house allocation, also known as assignment (Hylland and Zeckhauser 1979; Zhou 1990; Abdulkadiroglu and Sönmez 2003). In this setting, there are $m$ houses to be allocated among $n\leq m$ agents, with no two agents sharing the same house. The agents have possibly different preferences over the houses, and each agent should be assigned exactly one house.

While house allocation has typically been considered from the economic efficiency and strategyproofness perspectives (Abraham et al. 2004; Krysta et al. 2014), another important concern is fairness: it is desirable that the agents feel fairly treated. For example, the prominent fairness notion of envy-freeness means that agents do not envy one another with respect to their assigned houses. When $m=n$, all of the houses must be assigned, so an agent is envy-free if and only if she receives one of her most preferred houses. Thus, in order to compute an assignment with the largest number of envy-free agents, it suffices to find a maximum matching in the bipartite graph where the two sets of vertices correspond to the agents and the houses, respectively, and there is an edge between an agent and a house exactly when the house is among the agent’s most preferred houses—it is well-known that this task can be done in polynomial time. Beynier et al. 2019 assumed that agents can only envy other agents with whom they are acquainted according to a given acquaintance network, and provided algorithms and hardness results for various networks when $m=n$. Gan et al. 2019 addressed the general setting with $m\geq n$ (without an acquaintance network). In this setting, a simple matching algorithm no longer suffices, since even when all agents prefer the same house, it may still be possible to achieve envy-freeness by not allocating this house. Gan et al. devised a polynomial-time algorithm that decides whether an envy-free assignment exists and, if so, computes one such assignment. However, their work left open the question of whether an assignment maximizing the number of envy-free agents can be computed efficiently—after all, when making all agents envy-free is impossible, the number of envy-free agents is a natural optimization objective.

In this note, we give a strong negative answer to the question above by showing that under well-known complexity-theoretic assumptions, perhaps surprisingly, it is hard not only to maximize the number of envy-free agents, but also to obtain any decent approximation thereof. Specifically, assuming the Small Set Expansion Hypothesis (Raghavendra and Steurer 2010), the problem is hard to approximate to within a factor of $n^{1-\gamma}$ for any constant $\gamma>0$. We also establish that even when the agents have binary utilities over the houses, maximizing the number of envy-free agents is NP-hard. In addition, we consider two other important fairness notions: proportionality and equitability. On the one hand, we show that deciding whether a proportional allocation exists is NP-hard, thereby drawing a sharp contrast to the envy-freeness result of Gan et al. 2019; on the other hand, we prove that the corresponding problem for equitability can be solved efficiently.

Preliminaries

Let $[k]$ denote the set $\{1,2,\dots,k\}$ for any positive integer $k$. In the house allocation setting, there is a set $A=\{a_{1},\dots,a_{n}\}$ of $n$ agents and a set $H=\{h_{1},\dots,h_{m}\}$ of $m\geq n$ houses. Each agent $a\in A$ has a utility $u_{a}(h)\geq 0$ for a house $h\in H$. The utilities are said to be binary if $u_{a}(h)\in\{0,1\}$ for all $a\in A$ and $h\in H$. As assignment or house allocation is an injection $\phi:A\to H$. We consider the following fairness properties of assignments:

An agent $a\in A$ is said to be envy-free in an assignment $\phi$ if $u_{a}(\phi(a))\geq u_{a}(\phi(a^{\prime}))$ for all $a^{\prime}\in A$. For an assignment $\phi$, denote by $\val(\phi)$ the number of envy-free agents in $\phi$. The assignment $\phi$ is called envy-free if $\val(\phi)=n$.

An agent $a\in A$ is said to be proportional in an assignment $\phi$ if $u_{a}(\phi(a))\geq\frac{1}{n}\sum_{a^{\prime}\in A}u_{a}(\phi(a^{\prime}))$. An assignment $\phi$ is called proportional if all $n$ agents are proportional.

An assignment $\phi$ is called equitable if $u_{a}(\phi(a))=u_{a^{\prime}}(\phi(a^{\prime}))$ for all agents $a,a^{\prime}\in A$.

Notice that for envy-freeness, it suffices to consider the agents’ ordinal rankings over the houses, whereas the cardinal utilities play an important role in the definitions of proportionality and equitability. All three notions are commonly studied in the unconstrained allocation setting where each agent can receive any number of items (Bouveret et al. 2016; Markakis 2017). However, to the best of our knowledge, the latter two notions have not been previously studied in house allocation.

Envy-Freeness

We begin by considering envy-freeness. Recall that Gan et al. 2019 gave a polynomial-time algorithm for deciding whether an envy-free assignment exists for any given instance. We show that their algorithm cannot be generalized to efficiently compute the maximum number of envy-free agents, or even any decent approximation thereof, provided that known complexity-theoretic assumptions hold. We refer to our problem of interest as Maximum Envy-Free Assignment.

For any constant $\varepsilon>0$, if there exists a polynomial-time $f(n)$-approximation algorithm for Maximum Envy-Free Assignment, then there is a polynomial-time $2(1+\varepsilon)\cdot f(N)$-approximation algorithm for Maximum Balanced Biclique.

While Maximum Balanced Biclique is known to be NP-hard (Garey and Johnson 1979), the NP-hardness of approximating it remains open. Nevertheless, several inapproximability results for the problem are known under different complexity-theoretic assumptions (Feige 2002; Khot 2006; Bhangale et al. 2016; Manurangsi 2017a; Manurangsi 2017b). Specifically, assuming that NP cannot be solved in subexponential time (i.e., $NP\nsubseteq\bigcap_{\delta>0}BPTIME(2^{n^{\delta}})$), our theorem together with the hardness result of Khot 2006 implies that Maximum Envy-Free Assignment is hard to approximate to within a factor of $n^{\gamma}$ for some constant $\gamma>0$. Furthermore, combining our theorem with the hardness of Manurangsi 2017b, we can deduce that Maximum Envy-Free Assignment is hard to approximate to within a factor of $n^{1-\gamma}$ for any constant $\gamma>0$—this assumes the so-called Small Set Expansion Hypothesis (Raghavendra and Steurer 2010), which is itself a strengthening of the seminal Unique Games Conjecture (Khot 2002). This $n^{1-\gamma}$ inapproximability ratio nearly matches an $n$-approximation, which can be trivially achieved by ensuring that a single agent is envy-free.

If $NP\nsubseteq\bigcap_{\delta>0}BPTIME(2^{n^{\delta}})$, then, for some constant $\gamma>0$, Maximum Envy-Free Assignment cannot be approximated to within a factor of $n^{\gamma}$ in polynomial time.

If the Small Set Expansion Hypothesis holds, then Maximum Envy-Free Assignment is NP-hard to approximate to within a factor of $n^{1-\gamma}$ for any constant $\gamma>0$.

Our main technical contribution is the following reduction from Maximum Balanced Biclique to Maximum Envy-Free Assignment, as formalized below.

There is a polynomial-time reduction that takes an instance $G=(L,R,E)$ of Maximum Balanced Biclique and produces an instance $(A,H,\{u_{a}\}_{a\in A})$ of Maximum Envy-Free Assignment such that the following properties hold:

If $\opt_{\emph{MBB}}(G)\geq k$, then there exists an assignment $\phi^{*}$ such that $\val(\phi^{*})\geq k$.

Given any assignment $\phi$ such that $\val(\phi)\geq k$, there is a polynomial-time algorithm that outputs $S\subseteq L$ and $T\subseteq R$ such that $|S|=|T|=\lfloor k/2\rfloor$, and $S$ and $T$ together induce a biclique in $G$.

Before we describe the reduction, let us explain how we can use it to prove Theorem 3.1.

Let $\varepsilon>0$ be any constant, and suppose that there exists a polynomial-time $f(n)$-approximation algorithm $\mathcal{A}$ for the Maximum Envy-Free Assignment problem. We can use it to approximate Maximum Balanced Biclique on input $G$ as follows:

Run the reduction from Lemma 3.4 to produce an instance $(A,H,\{u_{a}\}_{a\in A})$ of Maximum Envy-Free Assignment.

Run $\mathcal{A}$ on $(A,H,\{u_{a}\}_{a\in A})$ to get an assignment $\phi$.

Run the algorithm described in the second property of the reduction in Lemma 3.4 on $\phi$ to get a balanced biclique $(S,T)$ in $G$.

Let $\beta:=2\left(\frac{1}{\varepsilon}+1\right)$. Use a brute-force $(|L|+|R|)^{O(\beta)}$ algorithm to enumerate through all subsets of size at most $2\beta$, and consider the largest balanced biclique found.

Output the larger of the two bicliques computed in the previous two steps.

If $\opt_{\text{MBB}}(G)/f(N)\leq\beta$, then the brute-force step of the algorithm ensures that the output biclique has size at least $\opt_{\text{MBB}}(G)/f(N)$. As a result, we may henceforth assume that $\opt_{\text{MBB}}(G)>f(N)\cdot\beta$.

Now, from the first property of the reduction, there exists $\phi^{*}$ such that $\val(\phi^{*})\geq\opt_{\text{MBB}}(G)$. Thus, $\mathcal{A}$ must output $\phi$ satisfying $\val(\phi)\geq\opt_{\text{MBB}}(G)/f(n)$, which is equal to $\opt_{\text{MBB}}(G)/f(N)$ due to the third property of the reduction. Then, the second property of the reduction ensures that our algorithm outputs a balanced biclique $(S,T)$ satisfying

where the second inequality follows from $\opt_{\text{MBB}}(G)>f(N)\cdot\beta$ and the last equality follows from our choice of $\beta$. It follows that our algorithm achieves an approximation ratio of $2f(N)\cdot(1+\varepsilon)$ for Maximum Balanced Biclique, as desired. ∎

To establish Theorem 3.1, it therefore remains to prove Lemma 3.4.

Given an instance $G=(L,R,E)$ of Maximum Balanced Biclique where $L=\{b_{1},\dots,b_{N}\}$ and $R=\{c_{1},\dots,c_{M}\}$, we create one agent $a_{i}$ for each vertex $b_{i}\in L$ and one house $h_{j}$ for each vertex $c_{j}\in R$. Moreover, we create $N$ additional houses $h^{*}_{1},\dots,h^{*}_{N}$. (So, in total, there are $N$ agents and $M+N$ houses.) The utility of each agent $a_{i}$ is defined by

This completes the description of the reduction. It is clear that the reduction runs in polynomial time, and that the third property of the reduction holds. We will now prove the first two properties of the reduction.

Suppose that $\opt_{\text{MBB}}(G)\geq k$, i.e., there exists a balanced biclique in $G$ where each side has $k$ vertices. Assume that this biclique consists of the vertices $b_{i_{1}},\dots,b_{i_{k}}$ and $c_{i^{\prime}_{1}},\dots,c_{i^{\prime}_{k}}$. Let us consider the following assignment:

Notice that each of $a_{i_{1}},\dots,a_{i_{k}}$ has value $N$ for her own house, and does not value any assigned house more than $N$. As such, the assignment is envy-free for these $k$ agents, so $\val(\phi^{*})\geq k$.

Suppose that there exists an assignment $\phi$ such that $\val(\phi)\geq k$. We may assume that $k\geq 2$, as otherwise we can simply output $S=T=\emptyset$.

Let $A_{\text{EF}}$ denote the set of agents that are envy-free with respect to $\phi$, so $|A_{\text{EF}}|\geq k$. We start by showing that $\phi(A_{\text{EF}})\cap\{h^{*}_{1},\dots,h^{*}_{N}\}=\emptyset$. Suppose for the sake of contradiction that for some $a\in A_{\text{EF}}$, we have $\phi(a)=h^{*}_{j}$ for some $j\in[N]$. Let $a^{\prime}$ be another agent in $A_{\text{EF}}$. Consider two cases based on whether $\phi(a^{\prime})\in\{h^{*}_{1},\dots,h^{*}_{N}\}$.

$\phi(a^{\prime})=h_{j^{\prime}}$ for some $j^{\prime}\in[M]$. In this case, we have $u_{a}(h_{j^{\prime}})\geq N>u_{a}(h^{*}_{j})$, so the assignment is not envy-free for $a$.

$\phi(a^{\prime})=h^{*}_{j^{\prime}}$ for some $j^{\prime}\in[N]$. In this case, if $j<j^{\prime}$, then $a$ would envy $a^{\prime}$; otherwise, if $j>j^{\prime}$, then $a^{\prime}$ would envy $a$.

Hence, our reduction satisfies the claimed properties. ∎

Next, we show that even if the agents have binary utilities, maximizing the number of envy-free agents remains computationally hard. This hardness only relies on the standard assumption P $\neq$ NP.

The problem of determining whether for a given positive integer $k$, there exists an assignment $\phi$ such that $\val(\phi)\geq k$, is NP-complete even when all agents have binary utilities.

Suppose that we are given an instance of the decision version of Minimum Coverage. Then we construct an instance of our house allocation problem as follows.

For each element $e\in E$, define the utility function $u_{a_{e}}\colon H\to\{0,1\}$ by

For each integer $t\in[d]$, define the utility function $u_{a^{*}_{t}}\colon H\to\{0,1\}$ by

($\Rightarrow$) Assume first that there exists a feasible solution $I\subseteq[d]$ to the decision version of Minimum Coverage. We will show that there exists a feasible solution to our house allocation problem. Define the assignment $\phi$ as follows.

For each integer $t\in I$, let $\phi(a^{*}_{t}):=h^{*}_{t}$.

We claim that $\val(\phi)\geq k=|E|+d-q$. More precisely, we prove that every agent in

is envy-free in $\phi$; notice that this is sufficient since $|A\setminus X|=|\{a_{e}\mid e\in\bigcup_{t\in I}S_{t}\}|\leq q$.

Let $e$ be an element in $E\setminus\bigcup_{t\in I}S_{t}$. Then since house $h^{*}_{t}$ is unassigned for every integer $t\in[d]$ such that $e\in S_{t}$, $e$ has value $0$ for all assigned houses, and so $e$ is envy-free in $\phi$.

Let $t$ be an integer in $[d]$. If $t\in I$, then since $u_{a^{*}_{t}}(\phi(a^{*}_{t}))=u_{a^{*}_{t}}(h^{*}_{t})=1$, $a^{*}_{t}$ is envy-free in $\phi$. Else, $t\notin I$, and since house $h^{*}_{t}$ is unassigned, $a^{*}_{t}$ is again envy-free in $\phi$.

This completes the proof of this direction.

($\Leftarrow$) Next, we prove the opposite direction. That is, we assume that there exists an assignment $\phi$ such that $\val(\phi)\geq k$. We first prove that in this case, there exists an assignment $\sigma$ satisfying the following conditions.

For every integer $t\in[d]$, if $\sigma^{-1}(h^{*}_{t})\neq\emptyset$, then $\sigma^{-1}(h^{*}_{t})=\{a^{*}_{t}\}$.

There exists an assignment $\sigma$ satisfying (A1) and (A2).

Assume that there exists an integer $t\in[d]$ such that $\phi^{-1}(h^{*}_{t})\neq\emptyset$ and $\phi^{-1}(h^{*}_{t})\neq\{a^{*}_{t}\}$. Let $\widehat{a}$ be the agent in $A$ such that $\phi(\widehat{a})=h^{*}_{t}$. Since $\phi(a^{*}_{t})\neq h^{*}_{t}$, we have $u_{a^{*}_{t}}(\phi(a^{*}_{t}))=0$ and $u_{a^{*}_{t}}(h^{*}_{t})=1$, which implies that $a^{*}_{t}$ is not envy-free in $\phi$.

Notice that the set of assigned houses in $\psi$ remains the same as in $\phi$. This implies that for every agent $a\in A\setminus\{a^{*}_{t},\widehat{a}\}$, $a$ is envy-free in $\phi$ if and only if $a$ is envy-free in $\psi$. Furthermore, since $u_{a^{*}_{t}}(\psi(a^{*}_{t}))=u_{a^{*}_{t}}(h^{*}_{t})=1$, $a^{*}_{t}$ is envy-free in $\psi$. Thus, we have $\val(\psi)\geq\val(\phi)\geq k$. By setting $\phi:=\psi$ and repeating this procedure, we eventually obtain a desired assignment $\sigma$. ∎

Let $\sigma$ be an assignment satisfying (A1) and (A2) according to Claim 1. Define $I$ as the set of integers $t\in[d]$ such that $\sigma(a^{*}_{t})=h^{*}_{t}$. Notice that

For every element $e\in E$, if $e\in\bigcup_{t\in I}S_{t}$, then since there exists an integer $t\in[d]$ such that $e\in S_{t}$ and $\sigma(a^{*}_{t})=h^{*}_{t}$, $a_{e}$ is not envy-free in $\sigma$. Thus, since $\val(\sigma)\geq k=|E|+d-q$, we have $|\bigcup_{t\in I}S_{t}|\leq q$. This completes the proof. ∎

We remark that the Minimum Coverage problem—also referred to as Bipartite Expansion—is known to be hard to approximate (Louis et al. 2013; Khot and Saket 2016). However, since our reduction in Theorem 3.5 is not approximation-preserving, it does not directly translate into a hardness of approximation for Maximum Envy-Free Assignment in the case of binary utilities.

Proportionality

In this section, we address proportionality. We show that deciding the existence of a proportional assignment is already NP-hard. This is in contrast to envy-freeness, where Gan et al. 2019 gave an efficient algorithm for deciding whether an envy-free assignment exists.

Deciding whether a proportional assignment exists in any given instance is NP-complete.

Membership in NP is clear: given an assignment, we can verify in polynomial time whether it is proportional. For the hardness, we reduce from the Exact 3-Set Cover (X3C) problem, where we are given a universe $V=\{v_{1},\dots,v_{N}\}$ and subsets $S_{1},\dots,S_{M}\subseteq V$, each of size $3$; the goal is to determine whether there exists a set cover of size $k:=N/3$. This problem is known to be NP-complete (Garey and Johnson 1979).

Given an instance of X3C, we perform the following reduction. For convenience, we will think of each subset $S_{i}$ as having ordered elements $e^{0}_{i},e^{1}_{i},e^{2}_{i}$.

We create $N$ agents $a_{1},\dots,a_{N}$, each corresponding to an element in the universe, and $T:=100(M+N)$ additional agents $a^{*}_{1},\dots,a^{*}_{T}$. Similarly, we create $3M$ houses $h^{0}_{1},h^{1}_{1},h^{2}_{1},\dots,h^{0}_{M},h^{1}_{M},h^{2}_{M}$, where $h^{0}_{j},h^{1}_{j},h^{2}_{j}$ correspond to the subset $S_{j}$ for $j\in[M]$, as well as $T$ additional houses $h^{*}_{1},\dots,h^{*}_{T}$. (So there are $N+T$ agents and $3M+T$ houses in total.) Let $C:=8T+8N-19$. The utilities for each of the first $N$ agents are defined by

This completes the description of the reduction. It is clear that the reduction runs in polynomial time and that each utility value can be represented in $O(\log(NM))$ bits. We now establish the validity of the reduction.

Proportionality is clearly satisfied for the last $T$ agents. Furthermore, for each $i\in[N]$, agent $a_{i}$ has utility exactly $8T$ for her assigned house, whereas $a_{i}$’s total utility for the $N+T$ assigned houses is

Hence, proportionality is also satisfied for $a_{i}$.

($\Leftarrow$) Suppose that there exists a proportional assignment $\phi$. We will show that the starting instance of X3C is a YES instance.

To this end, let us first observe that since $N+T>3M$, at least one of the houses $h^{*}_{i}$ must be assigned in $\phi$. From this and the assumption that $\phi$ is proportional for $a^{*}_{1},\dots,a^{*}_{T}$, we must have

Let us denote $P:=\phi(\{a_{1},\dots,a_{N},a^{*}_{1},\dots,a^{*}_{T}\})$ and $Q:=\phi(\{a_{1},\dots,a_{N}\})$. Observe that for each $i\in[N]$, (1) implies that

Furthermore, since $\phi$ is proportional for $a_{i}$, we have

This implies that $u_{a_{i}}(\phi(a_{i}))\geq\frac{TC}{N+T}>6T$, where the latter inequality follows from our choice of parameters. As a result, we must have

Summing (2) over $i\in[N]$ and plugging in the above relation, we get

From (3), this inequality is an equality and, as a result, (2) must be an equality for all $i\in[N]$ as well. This implies that

We remark that the difficulty of deciding the existence of a proportional allocation stems from the fact that unallocated houses are not taken into account in the definition of proportionality. In particular, if we were to use an alternative definition wherein each agent calculates her proportional share based on her utility for the set of all houses, the problem would become solvable in polynomial time, since we would know the desired threshold for every agent and could then check whether a proportional allocation exists by matching.

For binary utilities, envy-freeness and proportionality are equivalent. Indeed, if an agent has utility $0$ for all $n$ assigned houses, then she is both envy-free and proportional, while if the agent has utility $1$ for at least one assigned house, then envy-freeness and proportionality are both equivalent to the condition that the agent receives a house for which she has utility $1$. Theorem 3.5 therefore implies the following corollary.

The problem of determining whether for a given positive integer $k$, there exists an assignment such that at least $k$ agents are proportional, is NP-complete even when all agents have binary utilities.

Equitability

Finally, we turn our attention to equitability and show that in contrast to proportionality, deciding whether an equitable assignment exists can be done efficiently.

There is a polynomial-time algorithm that, for any given instance, decides whether an equitable allocation exists.

We iterate over the values $u_{a_{i}}(h_{j})$ for all $i\in[n]$ and $j\in[m]$. For such each value $k$, we construct a bipartite graph $G=(A,H,E)$, where there is an edge between agent $a_{i}$ and house $h_{j}$ if and only if $u_{a_{i}}(h_{j})=k$, and compute a maximum matching of the graph. We return that an equitable assignment exists exactly when the maximum matching has size $n$ for at least one constructed graph.

It is well-known that computing a maximum matching in a bipartite graph can be done in polynomial time, and the number of values $u_{a_{i}}(h_{j})$ is $O(mn)$. If we find a matching of size $n$, this clearly corresponds to an equitable assignment. Conversely, if there is an equitable assignment with value $k$, then the assignment gives rise to a matching of size $n$ in the bipartite graph constructed for value $k$. ∎

Concluding Remarks

In this paper, we have studied the complexity of computing fair house allocations with respect to envy-freeness, proportionality, and equitability. We conclude with some questions that remain from our work.

What is the best approximation ratio for maximizing the number of envy-free agents under binary utilities in polynomial time?

What is the complexity of deciding whether a proportional assignment exists under binary utilities?

Define the inequity of an assignment $\phi$ as the difference between the highest and lowest utilities in $\phi$. What is the complexity of computing an assignment with the smallest inequity?

This work was partially supported by JSPS KAKENHI Grant Number JP20H05795, Japan and by an NUS Start-up Grant. We thank the anonymous reviewer for valuable feedback.

References