{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T07:10:40Z","timestamp":1777619440597,"version":"3.51.4"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T00:00:00Z","timestamp":1558137600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T00:00:00Z","timestamp":1558137600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/K01000X\/1"],"award-info":[{"award-number":["EP\/K01000X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/K010042\/1"],"award-info":[{"award-number":["EP\/K010042\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/P028306\/1"],"award-info":[{"award-number":["EP\/P028306\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,9]]},"DOI":"10.1007\/s00453-019-00584-7","type":"journal-article","created":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T14:01:16Z","timestamp":1558188076000},"page":"3422-3463","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Size Versus Truthfulness in the House Allocation Problem"],"prefix":"10.1007","volume":"81","author":[{"given":"Piotr","family":"Krysta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6754-7308","authenticated-orcid":false,"given":"David","family":"Manlove","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baharak","family":"Rastegari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jinshan","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,5,18]]},"reference":[{"issue":"3","key":"584_CR1","doi-asserted-by":"publisher","first-page":"689","DOI":"10.2307\/2998580","volume":"66","author":"A Abdulkadiro\u01e7lu","year":"1998","unstructured":"Abdulkadiro\u01e7lu, A., S\u00f6nmez, T.: Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66(3), 689\u2013701 (1998)","journal-title":"Econometrica"},{"key":"584_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, D.J., Cechl\u00e1rov\u00e1, K., Manlove, D.F., Mehlhorn, K.: Pareto optimality in house allocation problems. In: Proceedings of ISAAC \u201904: the 15th Annual International Symposium on Algorithms and Computation, vol. 3341 of Lecture Notes in Computer Science, pp. 3\u201315. Springer (2004)","DOI":"10.1007\/978-3-540-30551-4_3"},{"key":"584_CR3","doi-asserted-by":"crossref","unstructured":"Aggarwal, G., Goel, G., Karande, C., Mehta, A.: Online vertex-weighted bipartite matching and single-bid budgeted allocations. In: Proceedings of SODA \u201911: the 22nd ACM-SIAM Symposium on Discrete Algorithms, pp. 1253\u20131264 (2011)","DOI":"10.1137\/1.9781611973082.95"},{"key":"584_CR4","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1016\/j.geb.2013.08.006","volume":"82","author":"H Aziz","year":"2013","unstructured":"Aziz, H., Brandt, F., Harrenstein, P.: Pareto optimality in coalition formation. Games Econ. Behav. 82, 562\u2013581 (2013)","journal-title":"Games Econ. Behav."},{"key":"584_CR5","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.artint.2015.06.002","volume":"227","author":"H Aziz","year":"2015","unstructured":"Aziz, H., Gaspers, S., Mackenzie, S., Walsh, T.: Fair assignment of indivisible objects under ordinal preferences. Artif. Intell. 227, 71\u201392 (2015)","journal-title":"Artif. Intell."},{"issue":"2","key":"584_CR6","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1145\/1399589.1399596","volume":"7","author":"M Babaioff","year":"2008","unstructured":"Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: Online auctions and generalized secretary problems. SIGecom Exch. 7(2), 7 (2008)","journal-title":"SIGecom Exch."},{"key":"584_CR7","unstructured":"Bade, S.: Random serial dictatorship: the one and only. Math. Oper. Res. (2019, to appear)"},{"key":"584_CR8","doi-asserted-by":"crossref","unstructured":"Bhalgat, A., Chakrabarty, D., Khanna, S.: Social welfare in one-sided matching markets without money. In: Proceedings of APPROX+RANDOM \u201911: 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\u201398. Springer (2011)","DOI":"10.1007\/978-3-642-22935-0_8"},{"issue":"2","key":"584_CR9","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1006\/jeth.2000.2710","volume":"100","author":"A Bogomolnaia","year":"2001","unstructured":"Bogomolnaia, A., Moulin, H.: A new solution to the random assignment problem. J. Econ. Theory 100(2), 295\u2013328 (2001)","journal-title":"J. Econ. Theory"},{"issue":"1","key":"584_CR10","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1111\/j.1468-0262.2004.00483.x","volume":"72","author":"A Bogomolnaia","year":"2004","unstructured":"Bogomolnaia, A., Moulin, H.: Random matching under dichotomous preferences. Econometrica 72(1), 257\u2013279 (2004)","journal-title":"Econometrica"},{"key":"584_CR11","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.geb.2014.11.006","volume":"90","author":"A Bogomolnaia","year":"2015","unstructured":"Bogomolnaia, A., Moulin, H.: Size versus fairness in the assignment problem. Games Econ. Behav. 90, 119\u2013127 (2015)","journal-title":"Games Econ. Behav."},{"key":"584_CR12","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/j.disopt.2014.09.002","volume":"14","author":"K Cechl\u00e1rov\u00e1","year":"2014","unstructured":"Cechl\u00e1rov\u00e1, K., Eirinakis, P., Fleiner, T., Magos, D., Mourtos, I., Potpinkov\u00e1, E.: Pareto optimality in many-to-many matching problems. Discrete Optim. 14, 160\u2013169 (2014)","journal-title":"Discrete Optim."},{"key":"584_CR13","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Swamy, C.: Welfare maximization and truthfulness in mechanism design with ordinal preferences. In: Proceedings of ITCS \u201914: ACM the 5th Innovations in Theoretical Computer Science conference, pp. 105\u2013120 (2014)","DOI":"10.1145\/2554797.2554810"},{"issue":"3","key":"584_CR14","doi-asserted-by":"publisher","first-page":"722","DOI":"10.1287\/moor.2013.0625","volume":"39","author":"N Chen","year":"2014","unstructured":"Chen, N., Garvin, N., Lu, P.: Truthful generalized assignments via stable matching. Math. Oper. Res. 39(3), 722\u2013736 (2014)","journal-title":"Math. Oper. Res."},{"key":"584_CR15","unstructured":"Chen, N., Ghosh, A.: Algorithms for Pareto stable assignment. In: Conitzer, V., Rothe, J. (eds.) Proceedings of COMSOC \u201910: the 3rd International Workshop on Computational Social Choice, D\u00fcsseldorf University Press, pp. 343\u2013354 (2010)"},{"key":"584_CR16","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Jain, K., Kleinberg, R.: Randomized primal-dual analysis of RANKING for online bipartite matching. In: Proceedings of SODA \u201913: the 24th ACM-SIAM Symposium on Discrete Algorithms, pp. 101\u2013107 (2013)","DOI":"10.1137\/1.9781611973105.7"},{"issue":"1\u20132","key":"584_CR17","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/s00453-010-9457-2","volume":"62","author":"NB Dimitrov","year":"2012","unstructured":"Dimitrov, N.B., Plaxton, C.G.: Competitive weighted matching in transversal matroids. Algorithmica 62(1\u20132), 333\u2013348 (2012)","journal-title":"Algorithmica"},{"key":"584_CR18","doi-asserted-by":"crossref","unstructured":"Dughmi, S., Ghosh, A.: Truthful assignment without money. In: Proceedings of EC \u201910: the 11th ACM Conference on Electronic Commerce, pp. 325\u2013334 (2010)","DOI":"10.1145\/1807342.1807394"},{"issue":"3","key":"584_CR19","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1287\/mnsc.20.3.331","volume":"20","author":"P G\u00e4rdenfors","year":"1973","unstructured":"G\u00e4rdenfors, P.: Assignment problem based on ordinal preferences. Manag. Sci. 20(3), 331\u2013340 (1973)","journal-title":"Manag. Sci."},{"issue":"2","key":"584_CR20","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1086\/260757","volume":"87","author":"A Hylland","year":"1979","unstructured":"Hylland, A., Zeckhauser, R.: The efficient allocation of individuals to positions. J. Polit. Econ. 87(2), 293\u2013314 (1979)","journal-title":"J. Polit. Econ."},{"issue":"5","key":"584_CR21","doi-asserted-by":"publisher","first-page":"1913","DOI":"10.1016\/j.jet.2012.05.017","volume":"147","author":"P Jaramillo","year":"2012","unstructured":"Jaramillo, P., Manjunath, V.: The difference indifference makes in strategy-proof allocation of objects. J. Econ. Theory 147(5), 1913\u20131946 (2012)","journal-title":"J. Econ. Theory"},{"key":"584_CR22","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V. : An optimal algorithm for on-line bipartite matching. In: Proceedings of STOC \u201990: the 22nd ACM Symposium on Theory of Computing, pp. 352\u2013358 (1990)","DOI":"10.1145\/100216.100262"},{"key":"584_CR23","doi-asserted-by":"crossref","unstructured":"Korte, B., Hausmann, D.: An analysis of the greedy heuristic for independence systems. In: Annals of Discrete Mathematics, vol.\u00a02, pp. 65\u201374. North-Holland (1978)","DOI":"10.1016\/S0167-5060(08)70322-4"},{"key":"584_CR24","doi-asserted-by":"publisher","DOI":"10.1142\/8591","volume-title":"Algorithmics of Matching Under Preferences","author":"DF Manlove","year":"2013","unstructured":"Manlove, D.F.: Algorithmics of Matching Under Preferences. World Scientific, Singapore (2013)"},{"key":"584_CR25","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"issue":"6","key":"584_CR26","doi-asserted-by":"publisher","first-page":"1403","DOI":"10.1111\/1468-0262.00166","volume":"68","author":"S P\u00e1pai","year":"2000","unstructured":"P\u00e1pai, S.: Strategyproof assignment by hierarchical exchange. Econometrica 68(6), 1403\u20131433 (2000)","journal-title":"Econometrica"},{"key":"584_CR27","unstructured":"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 \n                    https:\/\/www.cs.utexas.edu\/users\/plaxton\/pubs\/2013\/icgt.pdf"},{"issue":"4","key":"584_CR28","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/2542174.2542175","volume":"1","author":"AD Procaccia","year":"2013","unstructured":"Procaccia, A.D., Tennenholtz, M.: Approximate mechanism design without money. ACM Trans. Econ. Comput. 1(4), 18 (2013)","journal-title":"ACM Trans. Econ. Comput."},{"key":"584_CR29","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0165-1765(82)90003-9","volume":"9","author":"AE Roth","year":"1982","unstructured":"Roth, A.E.: Incentive compatibility in a market with indivisible goods. Econ. Lett. 9, 127\u2013132 (1982)","journal-title":"Econ. Lett."},{"key":"584_CR30","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0304-4068(77)90004-0","volume":"4","author":"AE Roth","year":"1977","unstructured":"Roth, A.E., Postlewaite, A.: Weak versus strong domination in a market with indivisible goods. J. Math. Econ. 4, 131\u2013137 (1977)","journal-title":"J. Math. Econ."},{"issue":"2","key":"584_CR31","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/j.jet.2005.04.004","volume":"125","author":"AE Roth","year":"2005","unstructured":"Roth, A.E., Sonmez, T., \u00dcnver, M.U.: Pairwise kidney exchange. J. Econ. Theory 125(2), 151\u2013188 (2005)","journal-title":"J. Econ. Theory"},{"key":"584_CR32","doi-asserted-by":"crossref","unstructured":"Saban, D., Sethuraman, J.: House allocation with indifferences: A generalization and a unified view. In: Proceedings of EC \u201913: the 14th ACM Conference on Electronic Commerce, pp. 803\u2013820 (2013)","DOI":"10.1145\/2492002.2482574"},{"issue":"4","key":"584_CR33","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1287\/moor.2014.0707","volume":"40","author":"D Saban","year":"2015","unstructured":"Saban, D., Sethuraman, J.: The complexity of computing the random priority allocation matrix. Math. Oper. Res. 40(4), 797\u20131088 (2015)","journal-title":"Math. Oper. Res."},{"key":"584_CR34","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-4068(74)90033-0","volume":"1","author":"L Shapley","year":"1974","unstructured":"Shapley, L., Scarf, H.: On cores and indivisibility. J. Math. Econ. 1, 23\u201337 (1974)","journal-title":"J. Math. Econ."},{"issue":"4","key":"584_CR35","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/BF00183301","volume":"11","author":"L-G Svensson","year":"1994","unstructured":"Svensson, L.-G.: Queue allocation of indivisible goods. Social Choice Welf. 11(4), 323\u2013330 (1994)","journal-title":"Social Choice Welf."},{"key":"584_CR36","doi-asserted-by":"crossref","unstructured":"Uno, T.: Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs. In: Proceedings of ISAAC \u201997: The 8th International Symposium on Algorithms and Computation, vol. 1350, pp. 92\u2013101. Springer (1997)","DOI":"10.1007\/3-540-63890-3_11"},{"key":"584_CR37","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Probabilistic computations: Toward a unified measure of complexity (extended abstract). In: Proceedings of FOCS \u201977: IEEE Computer Society 18th Annual IEEE Symposium on Foundations of Computer Science, pp. 222\u2013227 (1977)","DOI":"10.1109\/SFCS.1977.24"},{"issue":"1","key":"584_CR38","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0022-0531(90)90070-Z","volume":"52","author":"L Zhou","year":"1990","unstructured":"Zhou, L.: On a conjecture by Gale about one-sided matching problems. J. Econ. Theory 52(1), 123\u2013135 (1990)","journal-title":"J. Econ. Theory"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00584-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00584-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00584-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,16]],"date-time":"2020-05-16T23:35:02Z","timestamp":1589672102000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00584-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,18]]},"references-count":38,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["584"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00584-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,18]]},"assertion":[{"value":"31 July 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 May 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}