{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T18:13:10Z","timestamp":1778004790906,"version":"3.51.4"},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2022,11,2]],"date-time":"2022-11-02T00:00:00Z","timestamp":1667347200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,11,2]],"date-time":"2022-11-02T00:00:00Z","timestamp":1667347200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the<jats:italic>truthful facility assignment<\/jats:italic>problem, where a set of agents with private most-preferred points on a metric space have to be assigned to facilities that lie on the metric space, under capacity constraints on the facilities. The goal is to produce such an assignment that minimizes the social cost, i.e., the total distance between the most-preferred points of the agents and their corresponding facilities in the assignment, under the constraint of truthfulness, which ensures that agents do not misreport their most-preferred points. We propose a<jats:italic>resource augmentation framework<\/jats:italic>, where a truthful mechanism is evaluated by its worst-case performance on an instance with enhanced facility capacities against the optimal mechanism on the same instance with the original capacities. We study a well-known mechanism, Serial Dictatorship, and provide an exact analysis of its performance. Among other results, we prove that Serial Dictatorship has approximation ratio<jats:inline-formula><jats:alternatives><jats:tex-math>$$g\/(g-2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>g<\/mml:mi><mml:mo>\/<\/mml:mo><mml:mo>(<\/mml:mo><mml:mi>g<\/mml:mi><mml:mo>-<\/mml:mo><mml:mn>2<\/mml:mn><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>when the capacities are multiplied by any integer<jats:inline-formula><jats:alternatives><jats:tex-math>$$g \\ge 3$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>g<\/mml:mi><mml:mo>\u2265<\/mml:mo><mml:mn>3<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Our results suggest that with a limited augmentation of the resources we can achieve exponential improvements on the performance of the mechanism and in particular, the approximation ratio goes to 1 as the augmentation factor becomes large. We complement our results with bounds on the approximation ratio of Random Serial Dictatorship, the randomized version of Serial Dictatorship, when there is no resource augmentation.<\/jats:p>","DOI":"10.1007\/s10107-022-01902-8","type":"journal-article","created":{"date-parts":[[2022,11,2]],"date-time":"2022-11-02T20:23:37Z","timestamp":1667420617000},"page":"901-930","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship"],"prefix":"10.1007","volume":"203","author":[{"given":"Ioannis","family":"Caragiannis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7868-8114","authenticated-orcid":false,"given":"Aris","family":"Filos-Ratsikas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S\u00f8ren Kristoffer Stiil","family":"Frederiksen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kristoffer Arnsfelt","family":"Hansen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zihan","family":"Tan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,11,2]]},"reference":[{"key":"1902_CR1","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.: Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66, 689\u2013701 (1998)","journal-title":"Econometrica"},{"issue":"1","key":"1902_CR2","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/s00453-016-0238-4","volume":"80","author":"F Abed","year":"2018","unstructured":"Abed, F., Caragiannis, I., Voudouris, A.A.: Near-optimal asymmetric binary matrix partitions. Algorithmica 80(1), 48\u201372 (2018)","journal-title":"Algorithmica"},{"issue":"1","key":"1902_CR3","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/1980534.1980538","volume":"9","author":"E Anshelevich","year":"2010","unstructured":"Anshelevich, E., Das, S.: Matching, cardinal utility, and social welfare. ACM SIGECom Exch. 9(1), 4 (2010)","journal-title":"ACM SIGECom Exch."},{"key":"1902_CR4","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1613\/jair.5340","volume":"58","author":"E Anshelevich","year":"2017","unstructured":"Anshelevich, E., Postl, J.: Randomized social choice functions under metric preferences. J. Artif. Intell. Res. 58, 797\u2013827 (2017)","journal-title":"J. Artif. Intell. Res."},{"key":"1902_CR5","doi-asserted-by":"crossref","unstructured":"Anshelevich, E., Sekar, S.: Blind, greedy, and random: algorithms for matching and clustering using only ordinal information. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), pp. 390\u2013396 (2016)","DOI":"10.1609\/aaai.v30i1.10032"},{"key":"1902_CR6","doi-asserted-by":"crossref","unstructured":"Anshelevich, E., Sekar, S.: Truthful mechanisms for matching and clustering in an ordinal world. In: Proceedings of the 12th International Conference on Web and Internet Economics (WINE), pp. 265\u2013278 (2016)","DOI":"10.1007\/978-3-662-54110-4_19"},{"issue":"2","key":"1902_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3434417","volume":"9","author":"E Anshelevich","year":"2021","unstructured":"Anshelevich, E., Zhu, W.: Ordinal approximation for social choice, matching, and facility location problems given candidate positions. ACM Trans. Econ. Comput. 9(2), 1\u201324 (2021)","journal-title":"ACM Trans. Econ. Comput."},{"key":"1902_CR8","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.artint.2018.07.006","volume":"264","author":"E Anshelevich","year":"2018","unstructured":"Anshelevich, E., Bhardwaj, O., Elkind, E., Postl, J., Skowron, P.: Approximating optimal social choice under metric preferences. Artif. Intell. 264, 27\u201351 (2018)","journal-title":"Artif. Intell."},{"key":"1902_CR9","doi-asserted-by":"crossref","unstructured":"Anshelevich, E., Filos-Ratsikas, A., Shah, N., Voudouris, A.A.: Distortion in social choice problems: the first 15 years and beyond. In: Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pp. 4294\u20134301 (2021)","DOI":"10.24963\/ijcai.2021\/589"},{"key":"1902_CR10","doi-asserted-by":"publisher","first-page":"103713","DOI":"10.1016\/j.artint.2022.103713","volume":"308","author":"E Anshelevich","year":"2022","unstructured":"Anshelevich, E., Filos-Ratsikas, A., Voudouris, A.A.: The distortion of distributed metric social choice. Artif. Intell. 308, 103713 (2022)","journal-title":"Artif. Intell."},{"key":"1902_CR11","doi-asserted-by":"crossref","unstructured":"Antoniadis, A., Fischer, C., T\u00f6nnis, A.: A collection of lower bounds for online matching on the line. In: Proceedings of the 13th Latin American Symposium on Theoretical Informatics (LATIN), pp. 52\u201365 (2018)","DOI":"10.1007\/978-3-319-77404-6_5"},{"issue":"7","key":"1902_CR12","doi-asserted-by":"publisher","first-page":"2917","DOI":"10.1007\/s00453-019-00565-w","volume":"81","author":"A Antoniadis","year":"2019","unstructured":"Antoniadis, A., Barcelo, N., Nugent, M., Pruhs, K., Scquizzato, M.: A $$o(n)$$-competitive deterministic algorithm for online matching on a line. Algorithmica 81(7), 2917\u20132933 (2019)","journal-title":"Algorithmica"},{"issue":"3","key":"1902_CR13","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/s00224-008-9112-3","volume":"45","author":"S Athanassopoulos","year":"2009","unstructured":"Athanassopoulos, S., Caragiannis, I., Kaklamanis, C.: Analysis of approximation algorithms for k-set cover using factor-revealing linear programs. Theory Comput. Syst. 45(3), 555\u2013576 (2009)","journal-title":"Theory Comput. Syst."},{"key":"1902_CR14","unstructured":"Aziz, H., Chen, J., Filos-Ratsikas, A., Mackenzie, S., Mattei, N.: Egalitarianism of random assignment mechanisms. In: Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1267\u20131268 (2016)"},{"key":"1902_CR15","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/s00453-012-9676-9","volume":"2","author":"N Bansal","year":"2014","unstructured":"Bansal, N., Buchbinder, N., Gupta, A., Naor, J.: A randomized $$o(\\log ^2{k})$$-competitive algorithm for metric bipartite matching. Algorithmica 2, 390\u2013403 (2014)","journal-title":"Algorithmica"},{"issue":"2","key":"1902_CR16","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/s00453-012-9676-9","volume":"68","author":"N Bansal","year":"2014","unstructured":"Bansal, N., Buchbinder, N., Gupta, A., Naor, J.S.: A randomized o (log 2 k)-competitive algorithm for metric bipartite matching. Algorithmica 68(2), 390\u2013403 (2014)","journal-title":"Algorithmica"},{"issue":"5","key":"1902_CR17","doi-asserted-by":"publisher","first-page":"1288","DOI":"10.1007\/s00224-017-9826-1","volume":"62","author":"V Bil\u00f2","year":"2018","unstructured":"Bil\u00f2, V.: A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games. Theory Comput. Syst. 62(5), 1288\u20131317 (2018)","journal-title":"Theory Comput. Syst."},{"key":"1902_CR18","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, 295\u2013328 (2001)","journal-title":"J. Econ. Theory"},{"issue":"2","key":"1902_CR19","doi-asserted-by":"publisher","first-page":"959","DOI":"10.1137\/06067660X","volume":"23","author":"I Caragiannis","year":"2009","unstructured":"Caragiannis, I.: Wavelength management in WDM rings to maximize the number of connections. SIAM J. Discrete Math. 23(2), 959\u2013978 (2009)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"1902_CR20","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/s00224-011-9359-y","volume":"50","author":"I Caragiannis","year":"2012","unstructured":"Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M.: The efficiency of fair division. Theory Comput. Syst. 50(4), 589\u2013610 (2012)","journal-title":"Theory Comput. Syst."},{"key":"1902_CR21","doi-asserted-by":"crossref","unstructured":"Christodoulou, G., Filos-Ratsikas, A., Frederiksen, S.K., Goldberg, P.W., Zhang, J., Zhang, J.: Social welfare in one-sided matching mechanisms. In: Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1297\u20131298 (2016)","DOI":"10.1007\/978-3-319-46882-2_3"},{"key":"1902_CR22","doi-asserted-by":"crossref","unstructured":"Chung, C., Pruhs, K., Uthaisombut, P.: The online transportation problem: on the exponential boost of one extra server. In: Proceedings of the 8th Latin American Symposium on Theoretical Informatics (LATIN), pp. 228\u2013239 (2008)","DOI":"10.1007\/978-3-540-78773-0_20"},{"key":"1902_CR23","doi-asserted-by":"crossref","unstructured":"Eden, A., Feldman, M., Friedler, O., Talgam-Cohen, I., Weinberg, S.M.: The competition complexity of auctions: a Bulow-Klemperer result for multi-dimensional bidders. In: Proceedings of the 18th ACM Conference on Economics and Computation (EC), p. 343 (2017)","DOI":"10.1145\/3033274.3085115"},{"key":"1902_CR24","doi-asserted-by":"crossref","unstructured":"Emek, Y., Langner, T., Wattenhofer, R.: The price of matching with metric preferences. In: Proceedings of the 23rd Annual European Symposium on Algorithms (ESA), pp. 459\u2013470 (2015)","DOI":"10.1007\/978-3-662-48350-3_39"},{"key":"1902_CR25","volume-title":"The Spatial Theory of Voting: An Introduction","author":"JM Enelow","year":"1984","unstructured":"Enelow, J.M., Hinich, M.J.: The Spatial Theory of Voting: An Introduction. Cambridge University Press, Cambridge (1984)"},{"issue":"2","key":"1902_CR26","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/s00453-013-9806-z","volume":"71","author":"U Feige","year":"2015","unstructured":"Feige, U., Jozeph, S.: Oblivious algorithms for the maximum directed cut problem. Algorithmica 71(2), 409\u2013428 (2015)","journal-title":"Algorithmica"},{"key":"1902_CR27","doi-asserted-by":"crossref","unstructured":"Feige, U., Tennenholtz, M.: Responsive lotteries. In: Proceedings of the 3rd International Symposium on Algorithmic Game Theory (SAGT), pp. 150\u2013161 (2010)","DOI":"10.1007\/978-3-642-16170-4_14"},{"key":"1902_CR28","doi-asserted-by":"crossref","unstructured":"Filos-Ratsikas, A., Miltersen, P.B.: Truthful approximations to range voting. In: Proceedings of the 10th International Conference on Web and Internet Economics (WINE), pp. 175\u2013188 (2014)","DOI":"10.1007\/978-3-319-13129-0_13"},{"key":"1902_CR29","doi-asserted-by":"crossref","unstructured":"Filos-Ratsikas, A., Frederiksen, S.K.S., Zhang, J.: Social welfare in one-sided matchings: random priority and beyond. In: Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT), pp. 1\u201312 (2014)","DOI":"10.1007\/978-3-662-44803-8_1"},{"key":"1902_CR30","doi-asserted-by":"crossref","unstructured":"Filos-Ratsikas, A., Frederiksen, S.K., Zhang, J.: Social welfare in one-sided matchings: random priority and beyond. arXiv preprint arXiv:1403.1508 (2014b)","DOI":"10.1007\/978-3-662-44803-8_1"},{"issue":"3","key":"1902_CR31","doi-asserted-by":"publisher","first-page":"665","DOI":"10.2307\/1911681","volume":"45","author":"A Gibbard","year":"1977","unstructured":"Gibbard, A.: Manipulation of schemes that mix voting with chance. Econometrica 45(3), 665\u201381 (1977)","journal-title":"Econometrica"},{"key":"1902_CR32","unstructured":"Guo, M., Conitzer, V.: Strategy-proof allocation of multiple items between two agents without payments or priors. In: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 881\u2013888 (2010)"},{"issue":"2","key":"1902_CR33","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":"6","key":"1902_CR34","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1145\/950620.950621","volume":"50","author":"K Jain","year":"2003","unstructured":"Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50(6), 795\u2013824 (2003)","journal-title":"J. ACM"},{"issue":"3","key":"1902_CR35","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1006\/jagm.1993.1026","volume":"14","author":"B Kalyanasundaram","year":"1993","unstructured":"Kalyanasundaram, B., Pruhs, K.: Online weighted matching. J. Algorithms 14(3), 478\u2013488 (1993)","journal-title":"J. Algorithms"},{"issue":"3","key":"1902_CR36","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1137\/S0895480198342310","volume":"13","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.: The online transportation problem. SIAM J. Discrete Math. 13(3), 370\u2013383 (2000)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"1902_CR37","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1145\/347476.347479","volume":"47","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47(4), 617\u2013643 (2000)","journal-title":"J. ACM"},{"issue":"2","key":"1902_CR38","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0304-3975(94)90042-6","volume":"127","author":"S Khuller","year":"1994","unstructured":"Khuller, S., Mitchell, S.G., Vazirani, V.V.: On-line algorithms for weighted bipartite matching and stable marriages. Theor. Comput. Sci. 127(2), 255\u2013267 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"1902_CR39","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E.: Weak adversaries for the k-server problem. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pp. 444\u2013449 (1999)","DOI":"10.1109\/SFFCS.1999.814616"},{"key":"1902_CR40","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., Nanavati, A.: The online matching problem on a line. In: Proceedings of the 1st International Workshop on Approximation and Online Algorithms (WAOA), pp. 179\u2013191 (2003)","DOI":"10.1007\/978-3-540-24592-6_14"},{"issue":"9","key":"1902_CR41","doi-asserted-by":"publisher","first-page":"3422","DOI":"10.1007\/s00453-019-00584-7","volume":"81","author":"P Krysta","year":"2019","unstructured":"Krysta, P., Manlove, D.F., Rastegari, B., Zhang, J.: Size versus truthfulness in the house allocation problem. Algorithmica 81(9), 3422\u20133463 (2019)","journal-title":"Algorithmica"},{"key":"1902_CR42","doi-asserted-by":"crossref","unstructured":"Kulkarni, J., Mirrokni, V.: Robust price of anarchy bounds via LP and Fenchel duality. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1030\u20131049 (2015)","DOI":"10.1137\/1.9781611973730.70"},{"key":"1902_CR43","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Yan, Q.: Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps. In: Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pp. 597\u2013606 (2011)","DOI":"10.1145\/1993636.1993716"},{"key":"1902_CR44","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511605864","volume-title":"A Unified Theory of Voting: Directional and Proximity Spatial Models","author":"S Merrill III","year":"1999","unstructured":"Merrill, S., III., Merrill, S., Grofman, B.: A Unified Theory of Voting: Directional and Proximity Spatial Models. Cambridge University Press, Cambridge (1999)"},{"key":"1902_CR45","doi-asserted-by":"crossref","unstructured":"Meyerson, A., Nanavati, A., Poplawski, L.: Randomized online algorithms for minimum metric bipartite matching. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 954\u2013959 (2006)","DOI":"10.1145\/1109557.1109662"},{"key":"1902_CR46","doi-asserted-by":"crossref","unstructured":"Nadav, U., Roughgarden, T.: The limits of smoothness: a primal-dual framework for price of anarchy bounds. In: Proceedings of the 6th International Workshop on Internet and Network Economics (WINE), pp. 319\u2013326 (2010)","DOI":"10.1007\/978-3-642-17572-5_26"},{"key":"1902_CR47","doi-asserted-by":"crossref","unstructured":"Nayyar, K., Raghvendra, S.: An input sensitive online algorithm for the metric bipartite matching problem. In: Proceedings of the 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 505\u2013515 (2017)","DOI":"10.1109\/FOCS.2017.53"},{"issue":"4","key":"1902_CR48","doi-asserted-by":"publisher","first-page":"1","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), 1\u201326 (2013)","journal-title":"ACM Trans. Econ. Comput."},{"key":"1902_CR49","unstructured":"Raghvendra, S.: A robust and optimal online algorithm for minimum metric bipartite matching. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM), vol. 18, pp. 1\u201316"},{"key":"1902_CR50","unstructured":"Raghvendram, S.: Optimal analysis of an online algorithm for the bipartite matching problem on a line. In: Proceedings of the 34th International Symposium on Computational Geometry (SoCG), vol. 67, pp. 1\u201314 (2018)"},{"key":"1902_CR51","unstructured":"Roughgarden, T.: Beyond worst-case analysis lecture #3: online paging and resource augmentation. https:\/\/theory.stanford.edu\/~tim\/f14\/l\/l3.pdf (2014)"},{"issue":"2","key":"1902_CR52","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"issue":"4","key":"1902_CR53","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/s003550050160","volume":"16","author":"L-G Svensson","year":"1999","unstructured":"Svensson, L.-G.: Strategy-proof allocation of indivisble goods. Soc. Choice Welf. 16(4), 557\u2013567 (1999)","journal-title":"Soc. Choice Welf."},{"issue":"6","key":"1902_CR54","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/BF01189992","volume":"11","author":"N Young","year":"1994","unstructured":"Young, N.: The k-server dual and loose competitiveness for paging. Algorithmica 11(6), 525\u2013541 (1994)","journal-title":"Algorithmica"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01902-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01902-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01902-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T03:34:56Z","timestamp":1728272096000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01902-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,2]]},"references-count":54,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["1902"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01902-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,2]]},"assertion":[{"value":"28 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 October 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 November 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}