{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T08:41:47Z","timestamp":1776847307746,"version":"3.51.2"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,9,24]],"date-time":"2024-09-24T00:00:00Z","timestamp":1727136000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,24]],"date-time":"2024-09-24T00:00:00Z","timestamp":1727136000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001827","name":"Universiteit van Amsterdam","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001827","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider one-sided matching problems, where agents are allocated items based on stated preferences. Posing this as an assignment problem, the average rank of obtained matchings can be minimized using the rank minimization (RM) mechanism. RM matchings can have significantly better rank distributions than matchings obtained by mechanisms with random priority, such as Random Serial Dictatorship. However, these matchings are sensitive to preference manipulation from strategic agents. In this work we consider a scenario where agents aim to be matched to their top-<jats:italic>n<\/jats:italic> preferred items using the RM mechanism, and strategically manipulate their preferences to achieve this. We derive a best response strategy for an agent to be assigned to their <jats:italic>n<\/jats:italic> most preferred items using the Hungarian algorithm, under a simplified cost function. This strategy is then extended to a first-order heuristic strategy for being matched to the top-<jats:italic>n<\/jats:italic> items in a setup that minimizes the average rank. Based on this finding, an empirical study is conducted examining the impact of the first-order heuristic strategy. The study utilizes data from both simulated markets and real-world matching markets in Amsterdam, taking into account variations in item popularity, fractions of strategic agents, and the preferences for the <jats:italic>n<\/jats:italic> most favored items. For most scenarios, RM yields more rank efficient matches than Random Serial Dictatorship, even when agents apply the first-order heuristic strategy. However, although highly market dependent, the matching performance can become worse when 50% of agents or more want to be matched to their top-1 or top-2 preferred items and apply the first-order heuristic strategy to achieve this.<\/jats:p>","DOI":"10.1007\/s10458-024-09676-3","type":"journal-article","created":{"date-parts":[[2024,9,24]],"date-time":"2024-09-24T13:22:34Z","timestamp":1727184154000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Strategic manipulation of preferences in the rank minimization mechanism"],"prefix":"10.1007","volume":"38","author":[{"given":"Mayesha","family":"Tasnim","sequence":"first","affiliation":[]},{"given":"Youri","family":"Weesie","sequence":"additional","affiliation":[]},{"given":"Sennay","family":"Ghebreab","sequence":"additional","affiliation":[]},{"given":"Max","family":"Baak","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,24]]},"reference":[{"key":"9676_CR1","unstructured":"Bir\u00f3, P. (2017). Applications of matching models under preferences. In U. Endriss (Ed.), Trends in Computational Social Choice (pp. 345\u2013373). AI Access."},{"issue":"1","key":"9676_CR2","first-page":"88","volume":"9","author":"F Bloch","year":"2017","unstructured":"Bloch, F., & Cantala, D. (2017). Dynamic assignment of objects to queuing agents. American Economic Journal: Microeconomics, 9(1), 88\u2013122.","journal-title":"American Economic Journal: Microeconomics"},{"key":"9676_CR3","unstructured":"Delacr\u00e9taz, D., Kominers, S.D. & Teytelboym, A. (2016). Refugee resettlement. University of Oxford Department of Economics Working Paper"},{"issue":"3","key":"9676_CR4","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/s00182-008-0117-6","volume":"36","author":"AE Roth","year":"2008","unstructured":"Roth, A. E. (2008). Deferred acceptance algorithms: History, theory, practice, and open questions. International Journal of Game Theory, 36(3), 537\u2013569.","journal-title":"International Journal of Game Theory"},{"issue":"2","key":"9676_CR5","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. (2001). A new solution to the random assignment problem. Journal of Economic Theory, 100(2), 295\u2013328.","journal-title":"Journal of Economic Theory"},{"issue":"3","key":"9676_CR6","doi-asserted-by":"publisher","first-page":"689","DOI":"10.2307\/2998580","volume":"66","author":"A Abdulkadiro\u011flu","year":"1998","unstructured":"Abdulkadiro\u011flu, A., & S\u00f6nmez, T. (1998). Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica, 66(3), 689\u2013701.","journal-title":"Econometrica"},{"key":"9676_CR7","unstructured":"Featherstone, C. R. (2020). Rank efficiency: Modeling a common policymaker objective. Unpublished paper, The Wharton School, University of Pennsylvania. [25, 28, 45]"},{"issue":"2","key":"9676_CR8","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1257\/000282805774669637","volume":"95","author":"A Abdulkadiro\u011flu","year":"2005","unstructured":"Abdulkadiro\u011flu, A., Pathak, P. A., Roth, A. E., & S\u00f6nmez, T. (2005). The Boston public school match. American Economic Review, 95(2), 368\u2013371.","journal-title":"American Economic Review"},{"issue":"5","key":"9676_CR9","doi-asserted-by":"publisher","first-page":"1954","DOI":"10.1257\/aer.99.5.1954","volume":"99","author":"A Abdulkadiro\u011flu","year":"2009","unstructured":"Abdulkadiro\u011flu, A., Pathak, P. A., & Roth, A. E. (2009). Strategy-proofness versus efficiency in matching with indifferences: Redesigning the nyc high school match. American Economic Review, 99(5), 1954\u201378.","journal-title":"American Economic Review"},{"key":"9676_CR10","unstructured":"Aksoy, S., Azzam, A. A., Coppersmith, C., Glass, J., Karaali, G., Zhao, X. & Zhu, X. (2013). School choice as a one-sided matching problem: Cardinal utilities and optimization. arXiv preprint arXiv:1304.7413"},{"key":"9676_CR11","doi-asserted-by":"crossref","unstructured":"Troyan, P. (2022). Non-obvious manipulability of the rank-minimizing mechanism. arXiv preprint arXiv:2206.11359","DOI":"10.2139\/ssrn.4649965"},{"key":"9676_CR12","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2023.07.008","author":"J Ortega","year":"2023","unstructured":"Ortega, J., & Klein, T. (2023). The cost of strategy-proofness in school choice. Games and Economic Behavior. https:\/\/doi.org\/10.1016\/j.geb.2023.07.008","journal-title":"Games and Economic Behavior"},{"issue":"2","key":"9676_CR13","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1006\/jagm.1996.0020","volume":"20","author":"DE Knuth","year":"1996","unstructured":"Knuth, D. E. (1996). An exact analysis of stable allocation. Journal of Algorithms, 20(2), 431\u2013442.","journal-title":"Journal of Algorithms"},{"issue":"1","key":"9676_CR14","doi-asserted-by":"publisher","first-page":"25","DOI":"10.3982\/TE4171","volume":"17","author":"A Nikzad","year":"2022","unstructured":"Nikzad, A. (2022). Rank-optimal assignments in uniform markets. Theoretical Economics, 17(1), 25\u201355.","journal-title":"Theoretical Economics"},{"key":"9676_CR15","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/s003550050160","volume":"16","author":"L-G Svensson","year":"1999","unstructured":"Svensson, L.-G. (1999). Strategy-proof allocation of indivisible goods. Social Choice and Welfare, 16, 557\u2013567.","journal-title":"Social Choice and Welfare"},{"key":"9676_CR16","doi-asserted-by":"publisher","first-page":"104970","DOI":"10.1016\/j.jet.2019.104970","volume":"185","author":"P Troyan","year":"2020","unstructured":"Troyan, P., & Morrill, T. (2020). Obvious manipulations. Journal of Economic Theory, 185, 104970.","journal-title":"Journal of Economic Theory"},{"key":"9676_CR17","doi-asserted-by":"crossref","unstructured":"Lev, O., Meir, R., Obraztsova, S. & Polukarov, M. (2019). Heuristic voting as ordinal dominance strategies. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 2077\u20132084","DOI":"10.1609\/aaai.v33i01.33012077"},{"key":"9676_CR18","unstructured":"Scheuerman, J., Harman, J. L., Mattei, N. & Venable, K. B. (2019). Heuristic strategies in uncertain approval voting environments. arXiv preprint arXiv:1912.00011"},{"issue":"1","key":"9676_CR19","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1146\/annurev-economics-061109-080213","volume":"3","author":"PA Pathak","year":"2011","unstructured":"Pathak, P. A. (2011). The mechanism design approach to student assignment. Annual Review of Economics, 3(1), 513\u2013536.","journal-title":"Annual Review of Economics"},{"issue":"1","key":"9676_CR20","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9\u201315.","journal-title":"The American Mathematical Monthly"},{"key":"9676_CR21","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/S1574-0005(05)80019-0","volume":"1","author":"AE Roth","year":"1992","unstructured":"Roth, A. E., & Sotomayor, M. (1992). Two-sided matching. Handbook of Game Theory with Economic Applications, 1, 485\u2013541.","journal-title":"Handbook of Game Theory with Economic Applications"},{"key":"9676_CR22","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1017\/9781108227162.006","volume":"1","author":"PA Pathak","year":"2017","unstructured":"Pathak, P. A. (2017). What really matters in designing school choice mechanisms. Advances in Economics and Econometrics, 1, 176\u2013214.","journal-title":"Advances in Economics and Econometrics"},{"issue":"1","key":"9676_CR23","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1257\/aer.103.1.80","volume":"103","author":"PA Pathak","year":"2013","unstructured":"Pathak, P. A., & S\u00f6nmez, T. (2013). School admissions reform in Chicago and England: Comparing mechanisms by their vulnerability to manipulation. American Economic Review, 103(1), 80\u2013106.","journal-title":"American Economic Review"},{"issue":"1","key":"9676_CR24","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/j.jet.2009.09.002","volume":"145","author":"F Kojima","year":"2010","unstructured":"Kojima, F., & Manea, M. (2010). Incentives in the probabilistic serial mechanism. Journal of Economic Theory, 145(1), 106\u2013123.","journal-title":"Journal of Economic Theory"},{"issue":"4","key":"9676_CR25","doi-asserted-by":"publisher","first-page":"1636","DOI":"10.1257\/aer.98.4.1636","volume":"98","author":"PA Pathak","year":"2008","unstructured":"Pathak, P. A., & S\u00f6nmez, T. (2008). Leveling the playing field: Sincere and sophisticated players in the Boston mechanism. American Economic Review, 98(4), 1636\u201352.","journal-title":"American Economic Review"},{"issue":"1","key":"9676_CR26","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/j.geb.2008.01.008","volume":"64","author":"J Pais","year":"2008","unstructured":"Pais, J., & Pint\u00e9r, \u00c1. (2008). School choice and information: An experimental study on matching mechanisms. Games and Economic Behavior, 64(1), 303\u2013328.","journal-title":"Games and Economic Behavior"},{"issue":"4","key":"9676_CR27","doi-asserted-by":"publisher","first-page":"1860","DOI":"10.1257\/aer.100.4.1860","volume":"100","author":"C Calsamiglia","year":"2010","unstructured":"Calsamiglia, C., Haeringer, G., & Klijn, F. (2010). Constrained school choice: An experimental study. American Economic Review, 100(4), 1860\u201374.","journal-title":"American Economic Review"},{"issue":"4","key":"9676_CR28","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1145\/1198513.1198520","volume":"2","author":"RW Irving","year":"2006","unstructured":"Irving, R. W., Kavitha, T., Mehlhorn, K., Michail, D., & Paluch, K. (2006). Rank-maximal matchings. ACM Transactions on Algorithms (TALG), 2(4), 602\u2013610.","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"9676_CR29","doi-asserted-by":"crossref","unstructured":"Paluch, K. (2013). Capacitated rank-maximal matchings. In Algorithms and Complexity: 8th International Conference, CIAC 2013, Barcelona, Spain. Proceedings 8, pp. 324\u2013335. Springer","DOI":"10.1007\/978-3-642-38233-8_27"},{"issue":"1","key":"9676_CR30","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1137\/0105003","volume":"5","author":"J Munkres","year":"1957","unstructured":"Munkres, J. (1957). Algorithms for the assignment and transportation problem. Journal of the Society for Industrial and Applied Mathematics, 5(1), 32\u201338.","journal-title":"Journal of the Society for Industrial and Applied Mathematics"},{"key":"9676_CR31","doi-asserted-by":"crossref","unstructured":"Burkard, R. E., Dell\u2019Amico, M., & Martello, S. (2009). Assignment Problems. Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9780898717754"},{"issue":"4","key":"9676_CR32","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0167-6377(86)90073-8","volume":"5","author":"R Jonker","year":"1986","unstructured":"Jonker, R., & Volgenant, T. (1986). Improving the hungarian assignment algorithm. Operations Research Letters, 5(4), 171\u2013175.","journal-title":"Operations Research Letters"},{"key":"9676_CR33","doi-asserted-by":"crossref","unstructured":"Bazaraa, M. S., Jarvis, J. J. & Sherali, H. D. (2010). Linear programming and network flows, 4th Ed.","DOI":"10.1002\/9780471703778"},{"key":"9676_CR34","unstructured":"Hermanussen, L., Groot Beumer, T. & Grond, A. (2019). Evaluatie van het plaatsingssysteem"},{"key":"9676_CR35","unstructured":"Beek, K., Bootsma, E., Buma, J., Macdonald, I., Colen, D. & Smit, J. (2022). Stichting Vrije Schoolkeuze Amsterdam. http:\/\/stichtingvsa.nl"},{"key":"9676_CR36","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1038\/s41592-019-0686-2","volume":"17","author":"P Virtanen","year":"2020","unstructured":"Virtanen, P., Gommers, R., Oliphant, T. E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., van der Walt, S. J., Brett, M., Wilson, J., Millman, K. J., Mayorov, N., Nelson, A. R. J., Jones, E., Kern, R., Larson, E., \u2026 van Mulbregt, P. (2020). SciPy 1.0 contributors: SciPy 1.0: Fundamental algorithms for scientific computing in Python. Nature Methods, 17, 261\u2013272. https:\/\/doi.org\/10.1038\/s41592-019-0686-2","journal-title":"Nature Methods"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-024-09676-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-024-09676-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-024-09676-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,13]],"date-time":"2024-11-13T15:24:32Z","timestamp":1731511472000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-024-09676-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,24]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["9676"],"URL":"https:\/\/doi.org\/10.1007\/s10458-024-09676-3","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,24]]},"assertion":[{"value":"3 September 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 September 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"44"}}