House allocation problem

In economics and computer science, the house allocation problem is the problem of assigning objects to people with different preferences, such that each person receives exactly one object. The name "house allocation" comes from the main motivating application, which is assigning dormitory houses to students. Other commonly used terms are assignment problem and one-sided matching. When agents already own houses (and may trade them with other agents), the problem is often called a housing market. In house allocation problems, it is assumed that monetary transfers are not allowed; the variant in which monetary transfers are allowed is known as rental harmony.

In economics and computer science, the house allocation problem is the problem of assigning objects to people with different preferences, such that each person receives exactly one object. The name "house allocation" comes from the main motivating application, which is assigning dormitory houses to students. Other commonly used terms are assignment problem and one-sided matching. When agents already own houses (and may trade them with other agents), the problem is often called a housing market. In house allocation problems, it is assumed that monetary transfers are not allowed; the variant in which monetary transfers are allowed is known as rental harmony. When m=n, all houses must be assigned, so an allocation is EF iff each agent gets a house with a highest value. Therefore, it is possible to reduce the original graph to an unweighted graph, in which each agent is adjacent only to his highest-valued houses, and look for a perfect matching in this graph. When m>n, the above algorithm may not work, since not all houses must be assigned: even if a single house is most-preferred by all agents, there may exist a complete EF allocation in which this specific house is not assigned. Gan, Suksompong and Voudouris present a polynomial-time algorithm that decides, in polynomial time, whether a complete EF allocation exists for any m ≥ n. Their algorithm uses, as a subroutine, an algorithm for finding an inclusion-minimal Hall violator. Deciding whether a complete local-envy-free allocation exists. Local envy-freeness means that the agents are located on a social network, and they only envy their neighbors in that network. Beynier, Chevaleyre, Gourves, Harutyunyan, Lesca, Maudet and Wilczynski study the problem of deciding whether a complete local-envy-free allocation exists for m=n, for various network structures. Finding a complete EF allocation, in which the number of non-envious agents is maximized. Kamiyama, Manurangsi and Suksompong. prove that, under common complexity theoretic assumption, this problem is hard to approximate. In particular, if NP cannot be solved in subexponential time, then it cannot be approximated to within a factor of n^{\gamma} for some \gamma > 0 ; if the small set expansion hypothesis is true, then it cannot be approximated to within a factor of n^{\gamma} for any \gamma (for \gamma =1 it is trivial to approximate: just give one agent his favorite house, and allocate the other agents arbitrarily). The proof is by reduction from the maximum balanced biclique problem. Deciding whether a complete proportional allocation exists. Kamiyama, Manurangsi and Suksompong prove that it is NP-complete, by reduction from exact 3-set cover. Deciding whether a complete equitable allocation exists. Kamiyama, Manurangsi and Suksompong present a polytime algorithm. Finding a partial EF allocation of maximum cardinality. The runtime complexity of this problem is open.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374128617 under CC BY-SA 4.0; modifications have been made.