Abstract
We address a general housing market problem with a set of agents and a set of houses. Each agent has a weak ordinal preference list that allows ties on houses as well as an initial endowment; moreover, each agent wishes to reallocate to a better house on the housing market. In this work, we reduces the complexity of the family of top trading cycles algorithms by selecting a specific house from the preferred set during the trading phase. The rule of construction digraphs is used to select an appropriate house. Based on these digraphs, we propose an extended top trading cycles algorithm with complexity \(O(n^{2} r)\), where \(n\) is the number of agents and \(r\) is the maximum length of ties in the preference lists. The algorithm complexity is lower than that of the state-of-the-art algorithms. We show that the proposed algorithm is individually rational, Pareto efficient, and strategy-proof. It thus overcomes the limitations of a classic top trading cycles algorithm, and features Pareto efficiency and strategy-proofness on the weak preference domain.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abdulkadiroğlu A, Pathak PA, Roth AE (2009) Strategy-proofness versus efficiency in matching with indifferences: redesigning the NYC high school match. Amer Econ Rev 99:1954–1978
Abdulkadiroğlu A, Sӧnmez T (2003) School choice: a mechanism design approach. Am Econ Rev 93:729–747
Alcalde-Unzu J, Molis E (2011) Exchange of indivisible goods and indifferences: the top trading absorbing sets mechanisms. Game Econ Behav 73:1–16
Anderson R, Ashlagi I et al (2015) Kidney Exchange and the alliance for paired donation: operations research changes the way kidneys are transplanted. Interfaces 45:26–42
Aziz H, Keijzer B (2016) Housing markets with indifferences: a tale of two mechanisms. In: Proceedings of the twenty-sixth AAAI conference on artificial intelligence 2012, pp 1249–1255
Bird CG (1984) Group incentive compatibility in a market with indivisible goods. Econ Lett 14:309–313
Ding T, Schotter A (2016) Matching and chatting: an experimental study of the impact of network communication on school-matching mechanisms. Game Econ Behav
Ehlers L (2014) Top trading with fixed tie-breaking in markets with indivisible goods. J Econ Theory 151:64–87
Ghodsi A, Sekar V et al (2012) Multi-resource fair queueing for packet processing. Proc. SIGCOMM 42:1–12
Glorie K, Haase-Kromwijk B et al (2014) Allocation and matching in kidney exchange programs. Transpl Int 27:333–343
Huh W, Liu N, Truong VA (2013) Multiresource allocation scheduling in dynamic environments. M & Som-Manuf Serv Op 15:280–291
Jaramillo P, Manjunath V (2012) The difference indifference makes in strategy-proof allocation of objects. J Econ Theory 147:1913–1946
Ma J (1994) Strategy-proofness and strict core in a market with indivisibilities. Int J Game Theory 23:75–83
Miyagawa E (2002) Strategy-proofness and the core in house allocation problems. Games Econ Behav 38:347–361
Roth AE (1982) Incentive compatibility in a market with indivisible goods. Econ Lett 9:127–132
Roth AE, Postlewaite A (1977) Weak versus strong domination in a market with indivisible goods. J Math Econ 4:131–137
Roth AE, Sӧnmez T, Üver MU (2007) Efficient kidney exchange: coincidence of wants in markets with compatibility-based preferences. Am Econ Rev 97:828–851
Saban D, Sethuraman J (2013) House allocation with indifferences: a generalizationand a unified view. In: Proceedings of the EC’13. ACM, 2013, pp 803–820
Shapley L, Scarf H (1974) On cores and indivisibility. J Math Econ 1:23–37
Svensson LG (1994) Queue allocation of indivisible goods. Soc Choice Welfare 11:323–330
Taijan R (1972) Depth-first search and linear graph algorithms. SIAM J Comput 1:146–160
Xiong XS, He K, Zhao Y (2014) Mechanism design for the house allocation problem with indifferent houses and existing tenants. Sci China Inf Sci 44:1140–1155
Acknowledgements
This work was supported by the National Natural Science Foundation of China (Grant Nos. 71701076, 72031009, 71871171) and the Scientific Research Foundation of Hunan Provincial Education Department (Grant Nos. 17C1282).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Xiong, X., Wang, X. & He, K. A new allocation rule for the housing market problem with ties. J Comb Optim 43, 98–115 (2022). https://doi.org/10.1007/s10878-021-00727-z
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-021-00727-z