House allocation problem

Last updated April 30, 2024

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.^[1] 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.^[2] 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 .

Definitions

There are n people (also called: agents), and m objects (also called: houses). The agents may have different preferences over the houses. They may express their preferences in various ways:

Binary valuations: each agent values each house at either 1 (which means that the agent likes the house), or 0 (which means that the agent dislikes the house).
Preference ranking: each agent ranks the houses from best to worst. The ranking may be strict (no indifferences) or weak (indifferences allowed).
Cardinal utility: each agent assigns a non-negative numeric value to each house.

Several considerations may be important in designing algorithms for house allocation.

Pareto efficiency (PE) - no other allocation is better for some agents and not worse to all agents.
Fairness - can be defined in various ways, for example, envy-freeness (EF) - no agent should envy another agent.
Strategyproofness (SP) - each agent has an incentive to report his/her true preferences to the algorithm.
Individual rationality (IR) - no agent should lose from participating in the algorithm.

Efficient allocations

In economics, the primary efficiency requirement in house allocation is PE. There are various algorithms attaining a PE allocation in various settings.

Probably the simplest algorithm for house allocation is serial dictatorship : the agents are ordered in some arbitrary order (e.g. by seniority), and each agent in turn picks the best remaining house by his/her preferences. This algorithm is obviously SP. If the agents' preferences are strict, then it finds a PE allocation. However, it may be very unfair towards the agents who pick last. It can be made fairer (in expectation) by choosing the order uniformly at random; this leads to the mechanism called random serial dictatorship. The mechanism is PE ex-post, but it is not PE ex-ante; see fair random assignment for other randomized mechanisms which are ex-ante PE.

When each agent already owns a house, fairness considerations are less important, it is more important to guarantee to agents that they will not lose from participating (IR). The top trading cycle algorithm is the unique algorithm which guarantees IR, PE and SP. With strict preferences, TTC finds the unique core-stable allocation.^[3]

Abdulkadiroglu and Sönmez ^[1] consider an extended setting in which some agents already own a house while some others are house-less. Their mechanism is IR, PE and SP. They present two algorithms that implement this mechanism.

Ergin^[4] considers rules that are also consistent, that is, their predictions do not depend of the order in which the assignments are realized.

In computer science and operations research, the primary efficiency requirement is maximizing the sum of utilities. Finding a house allocation maximizing the sum of utilities is equivalent to finding a maximum-weight matching in a weighted bipartite graph; it is also called the assignment problem .

Fair allocations

Algorithmic problems related to fairness of the matching have been studied in several contexts.

When agents have binary valuations, their "like" relations define a bipartite graph on the sets of agents and houses. An envy-free house allocation corresponds to an envy-free matching in this graph. The following algorithmic problems have been studied.

Deciding whether a complete EF allocation exists. This holds iff there exists a matching that saturates all the agents; this can be decided in polynomial time by just finding a maximum cardinality matching in the bipartite graph.
Finding a partial EF allocation of maximum cardinality. Aigner-Horev and Segal-Halevi^[5]^{: Thm.1.6(a)} present a polytime algorithm.
Finding a partial EF allocation of maximum cardinality and minimum cost (where each edge has a pre-specified cost for society). Aigner-Horev and Segal-Halevi^[5]^{: Thm.1.6(b)} present a polytime algorithm.
Finding a complete EF allocation, in which the number of envious agents is minimized. Kamiyama, Manurangsi and Suksompong^[6]^: Thm.3.5prove that it is NP-hard. The proof is by reduction from the minimum coverage (aka bipartite expansion) problem. Madathil, Misra and Sethia^[7] prove that it is NP-hard even when each agent values at most 2 houses, and W[1]-hard when parameterized by the number of envious agents. The proof is by reduction from Maximum clique problem. However, the problem is fixed-parameter tractable when parameterized by the total number of house types and agent types, and can be solved efficiently when agents have "extremal intervals" preferences.
Finding a complete EF allocation, in which the maximum number of agents envied by a single agent is minimized. Madathil, Misra and Sethia^[7] prove that it is NP-hard even when each agent values at most 2 houses, every house is approved by a constant number of agents, and the maximum allowed envy is just 1. The proof is by reduction from Maximum independent set on cubic graphs. However, the problem is fixed-parameter tractable when parameterized by the total number of house types and agent types, and can be solved efficiently when agents have "extremal intervals" preferences.

When agents have cardinal valuations, the graph of agents and houses becomes a weighted bipartite graph. The following algorithmic problems have been studied.

Deciding whether a complete EF allocation exists.
- 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^[8] 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^[9] 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.^[6]^: Thm.3.1 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 <1$ (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^[6]^: Thm.4.1 prove that it is NP-complete, by reduction from exact 3-set cover.
Deciding whether a complete equitable allocation exists. Kamiyama, Manurangsi and Suksompong^[6]^: Thm.5.1 present a polytime algorithm.
Finding a partial EF allocation of maximum cardinality. The runtime complexity of this problem is open.^[5]^{: open question 2}

Related Research Articles

Fair cake-cutting is a kind of fair division problem. The problem involves a heterogeneous resource, such as a cake with different toppings, that is assumed to be divisible – it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible. The division should be unanimously fair – each person should receive a piece believed to be a fair share.

Efficient cake-cutting is a problem in economics and computer science. It involves a heterogeneous resource, such as a cake with different toppings or a land with different coverings, that is assumed to be divisible - it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible, etc. The allocation should be economically efficient. Several notions of efficiency have been studied:

Fair item allocation is a kind of the fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:

Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by any other agent. In other words, no person should feel envy.

Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are alternative names to the same problem.

Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent.

Fair random assignment is a kind of a fair division problem.

Random priority (RP), also called Random serial dictatorship (RSD), is a procedure for fair random assignment - dividing indivisible items fairly among people.

In economics and social choice theory, an envy-free matching (EFM) is a matching between people to "things", which is envy-free in the sense that no person would like to switch their "thing" with that of another person. This term has been used in several different contexts.

In graph theory, a Hall violator is a set of vertices in a graph, that violate the condition to Hall's marriage theorem.

Truthful resource allocation is the problem of allocating resources among agents with different valuations over the resources, such that agents are incentivized to reveal their true valuations over the resources.

Round robin is a procedure for fair item allocation. It can be used to allocate several indivisible items among several people, such that the allocation is "almost" envy-free: each agent believes that the bundle he received is at least as good as the bundle of any other agent, when at most one item is removed from the other bundle. In sports, the round-robin procedure is called a draft.

When allocating objects among people with different preferences, two major goals are Pareto efficiency and fairness. Since the objects are indivisible, there may not exist any fair allocation. For example, when there is a single house and two people, every allocation of the house will be unfair to one person. Therefore, several common approximations have been studied, such as maximin-share fairness (MMS), envy-freeness up to one item (EF1), proportionality up to one item (PROP1), and equitability up to one item (EQ1). The problem of efficient approximately fair item allocation is to find an allocation that is both Pareto-efficient (PE) and satisfies one of these fairness notions. The problem was first presented at 2016 and has attracted considerable attention since then.

Birkhoff's algorithm is an algorithm for decomposing a bistochastic matrix into a convex combination of permutation matrices. It was published by Garrett Birkhoff in 1946. It has many applications. One such application is for the problem of fair random assignment: given a randomized allocation of items, Birkhoff's algorithm can decompose it into a lottery on deterministic allocations.

Proportional item allocation is a fair item allocation problem, in which the fairness criterion is proportionality - each agent should receive a bundle that they value at least as much as 1/n of the entire allocation, where n is the number of agents.

An agreeable subset is a subset of items that is considered, by all people in a certain group, to be at least as good as its complement. Finding a small agreeable subset is a problem in computational social choice.

In economics and computer science, Fractional Pareto efficiency or Fractional Pareto optimality (fPO) is a variant of Pareto efficiency used in the setting of fair allocation of discrete objects. An allocation of objects is called discrete if each item is wholly allocated to a single agent; it is called fractional if some objects are split among two or more agents. A discrete allocation is called Pareto-efficient (PO) if it is not Pareto-dominated by any discrete allocation; it is called fractionally Pareto-efficient (fPO) if it is not Pareto-dominated by any discrete or fractional allocation. So fPO is a stronger requirement than PO: every fPO allocation is PO, but not every PO allocation is fPO.

Fair division among groups is a class of fair division problems, in which the resources are allocated among groups of agents, rather than among individual agents. After the division, all members in each group consume the same share, but they may have different preferences; therefore, different members in the same group might disagree on whether the allocation is fair or not. Some examples of group fair division settings are:

Fair allocation of items and money is a class of fair item allocation problems in which, during the allocation process, it is possible to give or take money from some of the participants. Without money, it may be impossible to allocate indivisible items fairly. For example, if there is one item and two people, and the item must be given entirely to one of them, the allocation will be unfair towards the other one. Monetary payments make it possible to attain fairness, as explained below.

References

1 2 Abdulkadiroğlu, Atila; Sönmez, Tayfun (1999-10-01). "House Allocation with Existing Tenants". Journal of Economic Theory. 88 (2): 233–260. doi: 10.1006/jeth.1999.2553 . ISSN 0022-0531.
↑ Aziz, Haris; Keijzer, Bart de (2012). "Housing Markets with Indifferences: A Tale of Two Mechanisms". Proceedings of the AAAI Conference on Artificial Intelligence. 26 (1): 1249–1255. doi: 10.1609/aaai.v26i1.8239 . ISSN 2374-3468. S2CID 15395473.
↑ Roth, Alvin E. (1982-01-01). "Incentive compatibility in a market with indivisible goods". Economics Letters. 9 (2): 127–132. doi:10.1016/0165-1765(82)90003-9. ISSN 0165-1765.
↑ Ergin, Haluk İ. (2000-08-01). "Consistency in house allocation problems". Journal of Mathematical Economics. 34 (1): 77–97. doi:10.1016/S0304-4068(99)00038-5. hdl: 11693/18154 . ISSN 0304-4068.
1 2 3 Segal-Halevi, Erel; Aigner-Horev, Elad (2022). "Envy-free matchings in bipartite graphs and their applications to fair division". Information Sciences. 587: 164–187. arXiv: 1901.09527 . doi:10.1016/j.ins.2021.11.059. S2CID 170079201.
1 2 3 4 Kamiyama, Naoyuki; Manurangsi, Pasin; Suksompong, Warut (2021-07-01). "On the complexity of fair house allocation". Operations Research Letters. 49 (4): 572–577. arXiv: 2106.06925 . doi:10.1016/j.orl.2021.06.006. ISSN 0167-6377. S2CID 235422019.
1 2 Madathil, Jayakrishnan; Misra, Neeldhara; Sethia, Aditi (2023-05-30). "The Complexity of Minimizing Envy in House Allocation". Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems. AAMAS '23. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 2673–2675. ISBN 978-1-4503-9432-1.
↑ Gan, Jiarui; Suksompong, Warut; Voudouris, Alexandros A. (2019-09-01). "Envy-freeness in house allocation problems". Mathematical Social Sciences. 101: 104–106. arXiv: 1905.00468 . doi:10.1016/j.mathsocsci.2019.07.005. ISSN 0165-4896. S2CID 143421680.
↑ Beynier, Aurélie; Chevaleyre, Yann; Gourvès, Laurent; Harutyunyan, Ararat; Lesca, Julien; Maudet, Nicolas; Wilczynski, Anaëlle (2019-09-01). "Local envy-freeness in house allocation problems". Autonomous Agents and Multi-Agent Systems. 33 (5): 591–627. doi:10.1007/s10458-019-09417-x. ISSN 1573-7454. S2CID 51869987.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:0-1] 1 2 Abdulkadiroğlu, Atila; Sönmez, Tayfun (1999-10-01). "House Allocation with Existing Tenants". Journal of Economic Theory. 88 (2): 233–260. doi: 10.1006/jeth.1999.2553 . ISSN 0022-0531.

[2] Aziz, Haris; Keijzer, Bart de (2012). "Housing Markets with Indifferences: A Tale of Two Mechanisms". Proceedings of the AAAI Conference on Artificial Intelligence. 26 (1): 1249–1255. doi: 10.1609/aaai.v26i1.8239 . ISSN 2374-3468. S2CID 15395473.

[3] Roth, Alvin E. (1982-01-01). "Incentive compatibility in a market with indivisible goods". Economics Letters. 9 (2): 127–132. doi:10.1016/0165-1765(82)90003-9. ISSN 0165-1765.

[4] Ergin, Haluk İ. (2000-08-01). "Consistency in house allocation problems". Journal of Mathematical Economics. 34 (1): 77–97. doi:10.1016/S0304-4068(99)00038-5. hdl: 11693/18154 . ISSN 0304-4068.

[:02-5] 1 2 3 Segal-Halevi, Erel; Aigner-Horev, Elad (2022). "Envy-free matchings in bipartite graphs and their applications to fair division". Information Sciences. 587: 164–187. arXiv: 1901.09527 . doi:10.1016/j.ins.2021.11.059. S2CID 170079201.

[:1-6] 1 2 3 4 Kamiyama, Naoyuki; Manurangsi, Pasin; Suksompong, Warut (2021-07-01). "On the complexity of fair house allocation". Operations Research Letters. 49 (4): 572–577. arXiv: 2106.06925 . doi:10.1016/j.orl.2021.06.006. ISSN 0167-6377. S2CID 235422019.

[:2-7] 1 2 Madathil, Jayakrishnan; Misra, Neeldhara; Sethia, Aditi (2023-05-30). "The Complexity of Minimizing Envy in House Allocation". Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems. AAMAS '23. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 2673–2675. ISBN 978-1-4503-9432-1.

[8] Gan, Jiarui; Suksompong, Warut; Voudouris, Alexandros A. (2019-09-01). "Envy-freeness in house allocation problems". Mathematical Social Sciences. 101: 104–106. arXiv: 1905.00468 . doi:10.1016/j.mathsocsci.2019.07.005. ISSN 0165-4896. S2CID 143421680.

[9] Beynier, Aurélie; Chevaleyre, Yann; Gourvès, Laurent; Harutyunyan, Ararat; Lesca, Julien; Maudet, Nicolas; Wilczynski, Anaëlle (2019-09-01). "Local envy-freeness in house allocation problems". Autonomous Agents and Multi-Agent Systems. 33 (5): 591–627. doi:10.1007/s10458-019-09417-x. ISSN 1573-7454. S2CID 51869987.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]