标题： 最小 envy 房屋分配图的复杂性 显示英文标题

标题： The Complexity of Minimum-Envy House Allocation Over Graphs

摘要： 本文研究了房屋分配问题的一个推广。在我们的问题中，代理由图$\GG_{\mathcal{A}} = (\AA, E_\AA)$的顶点表示，每个代理$a \in \AA$关联一组偏好的房屋$\PP_a \subseteq \HH$，其中$\AA$是代理的集合，$\HH$是房屋的集合。 房屋分配是一个单射函数 $\phi: \AA \rightarrow \HH$，如果代理人 $a$ 在 $\phi$ 下羡慕邻居 $a' \in N_{\GG_\AA}(a)$，则 $\phi(a) \notin \PP_a$ 和 $\phi(a') \in \PP_a$。 我们研究了两个自然的目标：第一个问题称为\ohaa ，旨在计算一种分配方式，以使嫉妒的代理人数最少；第二个问题称为\ohaah ，旨在最大化所有最小嫉妒分配中获得他们偏好的房屋的代理人数。 这两个目标捕捉了互补的公平性和个人满意度的概念。 我们为每个代理恰好偏好一个房屋的变体设计了多项式时间算法来解决这两个问题。另一方面，当每个代理偏好的房屋列表大小最多为$2$时，我们证明即使代理图$\GG_\AA$是一个完全二分图，这两个问题也是\NP -难解的。 我们还证明，即使房屋数量 $|\mathcal H|$ 等于代理数量 $|\mathcal A|$，这两个问题仍然是 \NP 难的。 这与经典的房屋分配问题形成了对比，在经典的房屋分配问题中，当 $|\mathcal H| = |\mathcal A|$ 时，该问题可以在多项式时间内求解。 当代理图的顶点覆盖较小时，这两个问题仍然是 \NP 难的。 积极的一面是，我们设计了精确的算法，利用了 $\GG_{\AA}$ 的某些结构特性，例如稀疏性、存在平衡分离器或存在较小的顶点覆盖，并且比简单的蛮力算法表现更好。 显示英文摘要

摘要： In this paper, we study a generalization of the House Allocation problem. In our problem, agents are represented by vertices of a graph $\GG_{\mathcal{A}} = (\AA, E_\AA)$, and each agent $a \in \AA$ is associated with a set of preferred houses $\PP_a \subseteq \HH$, where $\AA$ is the set of agents and $\HH$ is the set of houses. A house allocation is an injective function $\phi: \AA \rightarrow \HH$, and an agent $a$ envies a neighbour $a' \in N_{\GG_\AA}(a)$ under $\phi$ if $\phi(a) \notin \PP_a$ and $\phi(a') \in \PP_a$. We study two natural objectives: the first problem called \ohaa, aims to compute an allocation that minimizes the number of envious agents; the second problem called \ohaah aims to maximize, among all minimum-envy allocations, the number of agents who are assigned a house they prefer. These two objectives capture complementary notions of fairness and individual satisfaction. We design polynomial time algorithms for both problems for the variant when each agent prefers exactly one house. On the other hand, when the list of preferred houses for each agent has size at most $2$ then we show that both problems are \NP-hard even when the agent graph $\GG_\AA$ is a complete bipartite graph. We also show that both problems are \NP-hard even when the number $|\mathcal H|$ of houses is equal to the number $|\mathcal A|$ of agents. This is in contrast to the classical {\sc House Allocation} problem, where the problem is polynomial time solvable when $|\mathcal H| = |\mathcal A|$. The two problems are also \NP-hard when the agent graph has a small vertex cover. On the positive side, we design exact algorithms that exploit certain structural properties of $\GG_{\AA}$ such as sparsity, existence of balanced separators or existence of small-sized vertex covers, and perform better than the naive brute-force algorithm.