zbMATH — the first resource for mathematics

Size versus truthfulness in the house allocation problem. (English) Zbl 1431.91257
Summary: We study the house allocation problem (also known as the assignment problem), i.e., the problem of allocating a set of objects among a set of agents, where each agent has ordinal preferences (possibly involving ties) over a subset of the objects. We focus on truthful mechanisms without monetary transfers for finding large Pareto optimal matchings. It is straightforward to show that no deterministic truthful mechanism can approximate a maximum cardinality Pareto optimal matching with ratio better than 2. We thus consider randomised mechanisms. We give a natural and explicit extension of the classical random serial dictatorship mechanism (RSDM) specifically for the house allocation problem where preference lists can include ties. We thus obtain a universally truthful randomised mechanism for finding a Pareto optimal matching and show that it achieves an approximation ratio of \(\frac{e}{e-1}\). The same bound holds even when agents have priorities (weights) and our goal is to find a maximum weight (as opposed to maximum cardinality) Pareto optimal matching. On the other hand we give a lower bound of \(\frac{18}{13}\) on the approximation ratio of any universally truthful Pareto optimal mechanism in settings with strict preferences. By using a characterisation result of Bade, we show that any randomised mechanism that is a symmetrisation of a truthful, non-bossy and Pareto optimal mechanism has an improved lower bound of \(\frac{e}{e-1}\). Since our new mechanism is a symmetrisation of RSDM for strict preferences, it follows that this lower bound is tight. We moreover interpret our problem in terms of the classical secretary problem and prove that our mechanism provides the best randomised strategy of the administrator who interviews the applicants.

91B68 Matching models
91B32 Resource and cost allocation (including fair division, apportionment, etc.)
91B03 Mechanism design theory
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] Abraham, D.J., Cechlárová, K., Manlove, D.F., Mehlhorn, K.: Pareto optimality in house allocation problems. In: Proceedings of ISAAC ’04: the 15th Annual International Symposium on Algorithms and Computation, vol. 3341 of Lecture Notes in Computer Science, pp. 3-15. Springer (2004) · Zbl 1116.90393
[3] Aggarwal, G., Goel, G., Karande, C., Mehta, A.: Online vertex-weighted bipartite matching and single-bid budgeted allocations. In: Proceedings of SODA ’11: the 22nd ACM-SIAM Symposium on Discrete Algorithms, pp. 1253-1264 (2011) · Zbl 1375.68221
[4] Aziz, H.; Brandt, F.; Harrenstein, P., Pareto optimality in coalition formation, Games Econ. Behav., 82, 562-581, (2013) · Zbl 1283.91011
[5] Aziz, H.; Gaspers, S.; Mackenzie, S.; Walsh, T., Fair assignment of indivisible objects under ordinal preferences, Artif. Intell., 227, 71-92, (2015) · Zbl 1346.68106
[6] Babaioff, M.; Immorlica, N.; Kempe, D.; Kleinberg, R., Online auctions and generalized secretary problems, SIGecom Exch., 7, 7, (2008)
[7] Bade, S.: Random serial dictatorship: the one and only. Math. Oper. Res. (2019, to appear)
[8] Bhalgat, A., Chakrabarty, D., Khanna, S.: Social welfare in one-sided matching markets without money. In: Proceedings of APPROX+RANDOM ’11: the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and the 15th International Workshop on Randomization and Computation, vol. 6845 of Lecture Notes in Computer Science, pp. 87-98. Springer (2011) · Zbl 1343.91023
[9] Bogomolnaia, A.; Moulin, H., A new solution to the random assignment problem, J. Econ. Theory, 100, 295-328, (2001) · Zbl 1134.91357
[10] Bogomolnaia, A.; Moulin, H., Random matching under dichotomous preferences, Econometrica, 72, 257-279, (2004) · Zbl 1142.91691
[11] Bogomolnaia, A.; Moulin, H., Size versus fairness in the assignment problem, Games Econ. Behav., 90, 119-127, (2015) · Zbl 1318.91131
[12] Cechlárová, K.; Eirinakis, P.; Fleiner, T.; Magos, D.; Mourtos, I.; Potpinková, E., Pareto optimality in many-to-many matching problems, Discrete Optim., 14, 160-169, (2014) · Zbl 1308.91117
[13] Chakrabarty, D., Swamy, C.: Welfare maximization and truthfulness in mechanism design with ordinal preferences. In: Proceedings of ITCS ’14: ACM the 5th Innovations in Theoretical Computer Science conference, pp. 105-120 (2014) · Zbl 1366.91091
[14] Chen, N.; Garvin, N.; Lu, P., Truthful generalized assignments via stable matching, Math. Oper. Res., 39, 722-736, (2014) · Zbl 1307.91133
[15] Chen, N., Ghosh, A.: Algorithms for Pareto stable assignment. In: Conitzer, V., Rothe, J. (eds.) Proceedings of COMSOC ’10: the 3rd International Workshop on Computational Social Choice, Düsseldorf University Press, pp. 343-354 (2010)
[16] Devanur, N.R., Jain, K., Kleinberg, R.: Randomized primal-dual analysis of RANKING for online bipartite matching. In: Proceedings of SODA ’13: the 24th ACM-SIAM Symposium on Discrete Algorithms, pp. 101-107 (2013) · Zbl 1421.68244
[17] Dimitrov, NB; Plaxton, CG, Competitive weighted matching in transversal matroids, Algorithmica, 62, 333-348, (2012) · Zbl 1239.05148
[18] Dughmi, S., Ghosh, A.: Truthful assignment without money. In: Proceedings of EC ’10: the 11th ACM Conference on Electronic Commerce, pp. 325-334 (2010)
[19] Gärdenfors, P., Assignment problem based on ordinal preferences, Manag. Sci., 20, 331-340, (1973) · Zbl 0326.90006
[20] Hylland, A.; Zeckhauser, R., The efficient allocation of individuals to positions, J. Polit. Econ., 87, 293-314, (1979) · Zbl 0448.62088
[21] Jaramillo, P.; Manjunath, V., The difference indifference makes in strategy-proof allocation of objects, J. Econ. Theory, 147, 1913-1946, (2012) · Zbl 1247.91101
[22] Karp, R.M., Vazirani, U.V., Vazirani, V.V. : An optimal algorithm for on-line bipartite matching. In: Proceedings of STOC ’90: the 22nd ACM Symposium on Theory of Computing, pp. 352-358 (1990)
[23] Korte, B., Hausmann, D.: An analysis of the greedy heuristic for independence systems. In: Annals of Discrete Mathematics, vol. 2, pp. 65-74. North-Holland (1978) · Zbl 0392.90058
[24] Manlove, D.F.: Algorithmics of Matching Under Preferences. World Scientific, Singapore (2013) · Zbl 1283.68018
[25] Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995) · Zbl 0849.68039
[26] Pápai, S., Strategyproof assignment by hierarchical exchange, Econometrica, 68, 1403-1433, (2000) · Zbl 1023.91019
[27] Plaxton, C.G.: A simple family of top trading cycles mechanisms for housing markets with indifferences. In: Proceedings of the 24th International Conference on Game Theory, Stony Brook, New York, USA (2013). Available from https://www.cs.utexas.edu/users/plaxton/pubs/2013/icgt.pdf
[28] Procaccia, AD; Tennenholtz, M., Approximate mechanism design without money, ACM Trans. Econ. Comput., 1, 18, (2013)
[29] Roth, AE, Incentive compatibility in a market with indivisible goods, Econ. Lett., 9, 127-132, (1982) · Zbl 0722.90009
[30] Roth, AE; Postlewaite, A., Weak versus strong domination in a market with indivisible goods, J. Math. Econ., 4, 131-137, (1977) · Zbl 0368.90025
[31] Roth, AE; Sonmez, T.; Ünver, MU, Pairwise kidney exchange, J. Econ. Theory, 125, 151-188, (2005) · Zbl 1081.92023
[32] Saban, D., Sethuraman, J.: House allocation with indifferences: A generalization and a unified view. In: Proceedings of EC ’13: the 14th ACM Conference on Electronic Commerce, pp. 803-820 (2013)
[33] Saban, D.; Sethuraman, J., The complexity of computing the random priority allocation matrix, Math. Oper. Res., 40, 797-1088, (2015) · Zbl 1409.91187
[34] Shapley, L.; Scarf, H., On cores and indivisibility, J. Math. Econ., 1, 23-37, (1974) · Zbl 0281.90014
[35] Svensson, L-G, Queue allocation of indivisible goods, Social Choice Welf., 11, 323-330, (1994) · Zbl 0812.90034
[36] Uno, T.: Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs. In: Proceedings of ISAAC ’97: The 8th International Symposium on Algorithms and Computation, vol. 1350, pp. 92-101. Springer (1997) · Zbl 0897.05066
[37] Yao, A.C.-C.: Probabilistic computations: Toward a unified measure of complexity (extended abstract). In: Proceedings of FOCS ’77: IEEE Computer Society 18th Annual IEEE Symposium on Foundations of Computer Science, pp. 222-227 (1977)
[38] Zhou, L., On a conjecture by Gale about one-sided matching problems, J. Econ. Theory, 52, 123-135, (1990) · 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.