zbMATH — the first resource for mathematics

House allocation with existing tenants. (English) Zbl 0939.91068
Summary: In many real-life applications of house allocation problems, whenever an existing tenant wants to move, he needs to give up his current house before getting another one. This practice discourages existing tenants from such attempts and results in loss of potentially large gains from trade. Motivated by this observation, the authors propose a simple mechanism that is Pareto efficient, individually rational, and strategy-proof. Our approach is constructive and we provide two algorithms, each of which can be used to find the outcome of this mechanism. One additional merit of this mechanism is that it can accommodate any hierarchy of seniorities.

91B32 Resource and cost allocation (including fair division, apportionment, etc.)
Full Text: DOI
[1] Abdulkadiroğlu, A.; Sönmez, T., Random serial dictatorship and the core from random endowments in house allocation problems, Econometrica, 66, 689-701, (1998) · Zbl 1019.91016
[2] A. Bogomolnaia, and, H. Moulin, A simple random assignment problem with a unique solution, mimeo, University of Nottingham and Duke University, 1999. · Zbl 1022.91018
[3] Collins, S.; Krishna, K., The harvard housing lottery: rationality and reform, Working paper, (1995), Georgetown University and Penn State University
[4] Gale, D.; Shapley, L., College admissions and the stability of marriage, Amer. math. monthly, 69, 9-15, (1962) · Zbl 0109.24403
[5] Garratt, R.; Qin, C-Z., Cores and competitive equilibria with indivisibilities and lotteries, J. econ. theory, 68, 531-543, (1996) · Zbl 0854.90024
[6] Gibbard, A., Manipulations of voting schemes: A general result, Econometrica, 41, 587-601, (1973) · Zbl 0325.90081
[7] Gibbard, A., Manipulation of schemes that mix voting with chance, Econometrica, 45, 665-681, (1977) · Zbl 0365.90006
[8] Hylland, A.; Zeckhauser, R., The efficient allocation of individuals to positions, J. polit. econ., 87, 293-314, (1979)
[9] Knuth, D.E., An exact analysis of stable allocation, J. algorithms, 20, 431-442, (1996) · Zbl 0852.68034
[10] Krishna, V.; Perry, M., Efficient mechanism design, Working paper, (1997), Penn State University
[11] Ma, J., Strategy-proofness and the strict core in a market with indivisibilities, Int. J. game theory, 23, 75-83, (1994) · Zbl 0804.90014
[12] Mongell, S.; Roth, A.E., Sorority rush as a two-sided matching mechanism, Amer. econ. rev., 81, 415-440, (1991)
[13] S. Papai, Strategyproof assignment by hierarchical exchance, mimeo, Koç University, 1998.
[14] Roth, A.E., Incentive compatibility in a market with indivisibilities, Econ. lett., 9, 127-132, (1982) · Zbl 0722.90009
[15] Roth, A.E., The evolution of labor market for medical interns and residents: A case study in game theory, J. polit. econ., 92, 991-1016, (1984)
[16] Roth, A.E., A natural experiment in the organization of entry-level labor markets: regional markets for new physicians and surgeons in U.K, Amer. econ. rev., 81, 441-464, (1991)
[17] Roth, A.E.; Peranson, E., The effects of a change in the NRMP matching algorithm, J. amer. medical assoc., 278, 729-732, (1997)
[18] Roth, A.E.; Postlewaite, A., Weak versus strong domination in a market with indivisible goods, J. math. econ., 4, 131-137, (1977) · Zbl 0368.90025
[19] Satterthwaite, M.A., Strategy-proofness and Arrow’s conditions: existence and correspondence theorems for voting procedures and social welfare functions, J. econ. theory, 10, 187-216, (1975) · Zbl 0315.90088
[20] Shapley, L.; Scarf, H., On cores and indivisibility, J. math. econ., 1, 23-28, (1974) · Zbl 0281.90014
[21] L. G. Svensson, Strategy-proof allocation of indivisible goods, mimeo, Lund University, 1998. [Forthcoming in, Social Choice and Welfare, ]
[22] W. Thomson, Consistency in exchange economies, mimeo, University of Rochester, 1992.
[23] Zhou, L., On a conjecture by gale about one-sided matching problems, J. econ. theory, 52, 123-135, (1991) · Zbl 0725.90003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.