Jump to content

House allocation problem

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Erel Segal (talk | contribs) at 18:57, 29 June 2021 (→See also). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In economics and computer science, the house allocation problem is the problem of assigning objects to people with different preferenes, 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. 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 allocaiton 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.[2]

Abdulkadiroglu and Sonmez[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[3] 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. This can be done in polynomial time.[4]
  • Finding a partial EF allocation of maximum cardinality and minimum cost (where each edge has a pre-specified cost for society). This too can be done in polynomial time.[4]

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[5] present a polynomial-time algorithm that decides, in polynomial time, whether a complete EF allocation exists for any m ≥ n.
  • 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[6] study the problem of deciding whether a complete local-envy-free allocation exists for m=n, for various network structures.

[7]

See also

  • Assignment problem - a combinatorial problem in which the goal is to optimize the sum of valuations.
  • Fair random assignment - a variant in which randomization is allowed, and the allocaiton should be fair in expectation.
  • Rental harmony - a similar problem in which each house may be assigned a monetary price.
  • Envy-free matching - various notions related to envy-freeness in matchings in bipartite graphs.

References

  1. ^ a b "House Allocation with Existing Tenants". Journal of Economic Theory. 88 (2): 233–260. 1999-10-01. doi:10.1006/jeth.1999.2553. ISSN 0022-0531.
  2. ^ 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.
  3. ^ "Consistency in house allocation problems". Journal of Mathematical Economics. 34 (1): 77–97. 2000-08-01. doi:10.1016/S0304-4068(99)00038-5. ISSN 0304-4068.
  4. ^ a b Segal-Halevi, Erel; Aigner-Horev, Elad (2019-01-28). "Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division". arXiv:1901.09527 [cs.DS].
  5. ^ "Envy-freeness in house allocation problems". Mathematical Social Sciences. 101: 104–106. 2019-09-01. doi:10.1016/j.mathsocsci.2019.07.005. ISSN 0165-4896.
  6. ^ 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.
  7. ^ "On the complexity of fair house allocation". Operations Research Letters. 49 (4): 572–577. 2021-07-01. doi:10.1016/j.orl.2021.06.006. ISSN 0167-6377.
Retrieved from "https://en.wikipedia.org/w/index.php?title=House_allocation_problem&oldid=1031086930"