House allocation problem
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.
Considerations
Several considerations are important in designing algorithms for house allocation.
- Pareto efficiency - no other allocation is better for some agents and not worse to all agents.
- Fairness - can be defined in various ways, for example, no agent should envy another agent.
- Strategyproofness - each agent has an incentive to report his/her true preferences to the algorithm.
- Individual rationality - no agent should lose from participating in the algorithm.
Algorithms
References
- ^ 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.
- ^ "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.
- ^ "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.