Ella Barkan, Ibrahim Siddiqui, et al.
Computational And Structural Biotechnology Journal
The classical house allocation problem involves assigning n houses (or items) to n agents according to their preferences. A key criterion in such problems is satisfying some fairness constraints such as envy-freeness. We consider a generalization of this problem, called Graphical House Allocation, wherein the agents are placed along the vertices of a graph (corresponding to a social network), and each agent can only experience envy towards its neighbors. Our goal is to minimize the aggregate envy among the agents as a natural fairness objective, i.e., the sum of the envy value over all edges in a social graph. We focus on graphical house allocation with identical valuations. When agents have identical and evenly-spaced valuations, our problem reduces to the well-studied Minimum Linear Arrangement. For identical valuations with possibly uneven spacing, we show a number of deep and surprising ways in which our setting is a departure from this classical problem. More broadly, we contribute several structural and computational results for various classes of graphs, including NP-hardness results for disjoint unions of paths, cycles, stars, cliques, and complete bipartite graphs; we also obtain fixed-parameter tractable (and, in some cases, polynomial-time) algorithms for paths, cycles, stars, cliques, complete bipartite graphs, and their disjoint unions. Additionally, a conceptual contribution of our work is the formulation of a structural property for disconnected graphs that we call splittability, which results in efficient parameterized algorithms for finding optimal allocations.
Ella Barkan, Ibrahim Siddiqui, et al.
Computational And Structural Biotechnology Journal
Amarachi Blessing Mbakwe, Joy Wu, et al.
NeurIPS 2023
Ronen Feldman, Martin Charles Golumbic
Ann. Math. Artif. Intell.
Els van Herreweghen, Uta Wille
USENIX Workshop on Smartcard Technology 1999