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.5 prove 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
for some
; if the small set expansion hypothesis is true, then it cannot be approximated to within a factor of
for any
(for
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
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.