{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T10:22:01Z","timestamp":1778494921191,"version":"3.51.4"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T00:00:00Z","timestamp":1737331200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T00:00:00Z","timestamp":1737331200000},"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\/X039862\/1"],"award-info":[{"award-number":["EP\/X039862\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We consider a truthful facility location game in which there is a set of agents with private locations on the line of real numbers, and the goal is to place a number of facilities at different locations chosen from the set of those reported by the agents. Given a feasible solution, each agent suffers an individual cost that is either its total distance to all facilities (sum-variant) or its distance to the farthest facility (max-variant). For both variants, we show tight bounds on the approximation ratio of strategyproof mechanisms in terms of the social cost, the total individual cost of the agents.\n<\/jats:p>","DOI":"10.1007\/s10878-025-01258-7","type":"journal-article","created":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T18:52:30Z","timestamp":1737399150000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Agent-constrained truthful facility location games"],"prefix":"10.1007","volume":"49","author":[{"given":"Argyrios","family":"Deligkas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad","family":"Lotfi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandros A.","family":"Voudouris","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,20]]},"reference":[{"key":"1258_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal P, Balkanski E, Gkatzelis V, Ou T, Tan X (2022) Learning-augmented mechanism design: leveraging predictions for facility location. In: Proceedings of the 23rd ACM conference on economics and computation (EC), pp 497\u2013528","DOI":"10.1145\/3490486.3538306"},{"key":"1258_CR2","doi-asserted-by":"crossref","unstructured":"Chan H, Filos-Ratsikas A, Li B, Li M, Wang C (2021) Mechanism design for facility location problems: a survey. In: Proceedings of the thirtieth international joint conference on artificial intelligence (IJCAI), pp 4356\u20134365","DOI":"10.24963\/ijcai.2021\/596"},{"key":"1258_CR3","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.114208","volume":"979","author":"H Chan","year":"2023","unstructured":"Chan H, Gong Z, Li M, Wang C, Zhao Y (2023) Facility location games with ordinal preferences. Theoret Comput Sci 979:114208","journal-title":"Theoret Comput Sci"},{"key":"1258_CR4","doi-asserted-by":"crossref","unstructured":"Chen Z, Fong KCK, Li M, Wang K, Yuan H, Zhang Y (2020) Facility location games with optional preference. Theor Comput Sci 847:185\u2013197","DOI":"10.1016\/j.tcs.2020.10.004"},{"key":"1258_CR5","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.tcs.2011.11.041","volume":"497","author":"Y Cheng","year":"2013","unstructured":"Cheng Y, Yua W, Zhang G (2013) Strategy-proof approximation mechanisms for an obnoxious facility game on networks. Theoret Comput Sci 497:154\u2013163","journal-title":"Theoret Comput Sci"},{"key":"1258_CR6","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/j.geb.2023.03.001","volume":"139","author":"A Deligkas","year":"2023","unstructured":"Deligkas A, Filos-Ratsikas A, Voudouris AA (2023) Heterogeneous facility location with limited resources. Games Econom Behav 139:200\u2013215","journal-title":"Games Econom Behav"},{"key":"1258_CR7","unstructured":"Feigenbaum I, Sethuraman J (2015) Strategyproof mechanisms for one-dimensional hybrid and obnoxious facility location models. In: AAAI workshop on incentive and trust in e-communities, volume WS-15-08"},{"key":"1258_CR8","doi-asserted-by":"crossref","unstructured":"Feldman M, Fiat A, Golomb I (2016) On voting and facility location. In: Proceedings of the 2016 ACM conference on economics and computation (EC), pp 269\u2013286","DOI":"10.1145\/2940716.2940725"},{"key":"1258_CR9","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2024.104066","volume":"328","author":"A Filos-Ratsikas","year":"2024","unstructured":"Filos-Ratsikas A, Kanellopoulos P, Voudouris AA, Zhang R (2024) The distortion of distributed facility location. Artif Intell 328:104066","journal-title":"Artif Intell"},{"key":"1258_CR10","doi-asserted-by":"crossref","unstructured":"Fong CKK, Li M, Lu P, Todo T, Yokoo M (2018) Facility location games with fractional preferences. In: Proceedings of the 32nd AAAI conference on artificial intelligence (AAAI), pp 1039\u20131046","DOI":"10.1609\/aaai.v32i1.11458"},{"key":"1258_CR11","doi-asserted-by":"crossref","unstructured":"Fotakis D, Tzamos C (2014) On the power of deterministic mechanisms for facility location games. ACM Trans Econ Comput 2(4):15:1\u201315:37","DOI":"10.1145\/2665005"},{"key":"1258_CR12","volume":"466","author":"L Gai","year":"2024","unstructured":"Gai L, Liang M, Wang C (2024) Two-facility-location games with mixed types of agents. Appl Math Comput 466:128479","journal-title":"Appl Math Comput"},{"key":"1258_CR13","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1137\/22M149908X","volume":"37","author":"P Kanellopoulos","year":"2023","unstructured":"Kanellopoulos P, Voudouris AA, Zhang R (2023) On discrete truthful heterogeneous two-facility location. SIAM J Discrete Math 37:779\u2013799","journal-title":"SIAM J Discrete Math"},{"key":"1258_CR14","doi-asserted-by":"crossref","unstructured":"Li M, Lu P, Yao Y, Zhang J (2020) Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio. In Proceedings of the 29th international joint conference on artificial intelligence (IJCAI), pp 238\u2013245","DOI":"10.24963\/ijcai.2020\/34"},{"key":"1258_CR15","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2023.107060","volume":"52","author":"M Lotfi","year":"2024","unstructured":"Lotfi M, Voudouris AA (2024) On truthful constrained heterogeneous facility location with max-variant cost. Oper Res Lett 52:107060","journal-title":"Oper Res Lett"},{"key":"1258_CR16","doi-asserted-by":"crossref","unstructured":"Lu P, Sun X, Wang Y, Zhu ZA (2010) Asymptotically optimal strategy-proof mechanisms for two-facility games. In: Proceedings of the 11th ACM conference on electronic commerce (EC), pp 315\u2013324","DOI":"10.1145\/1807342.1807393"},{"key":"1258_CR17","doi-asserted-by":"crossref","unstructured":"Procaccia AD, Tennenholtz M (2013) Approximate mechanism design without money. ACM Trans Econ Comput 1(4):18:1\u201318:26","DOI":"10.1145\/2542174.2542175"},{"key":"1258_CR18","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.tcs.2016.04.033","volume":"636","author":"P Serafino","year":"2016","unstructured":"Serafino P, Ventre C (2016) Heterogeneous facility location without money. Theoret Comput Sci 636:27\u201346","journal-title":"Theoret Comput Sci"},{"key":"1258_CR19","doi-asserted-by":"crossref","unstructured":"Tang Z, Wang C, Zhang M, Zhao Y (2020) Mechanism design for facility location games with candidate locations. In: Proceedings of the 14th international conference on combinatorial optimization and applications (COCOA), pp 440\u2013452","DOI":"10.1007\/978-3-030-64843-5_30"},{"key":"1258_CR20","doi-asserted-by":"crossref","unstructured":"Xu C, Lu P (2022) Mechanism design with predictions. In Proceedings of the 31st international joint conference on artificial intelligence (IJCAI), pp 571\u2013577","DOI":"10.24963\/ijcai.2022\/81"},{"key":"1258_CR21","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1613\/jair.1.12319","volume":"70","author":"X Xinping","year":"2021","unstructured":"Xinping X, Li B, Li M, Duan L (2021) Two-facility location games with minimum distance requirement. J Artif Intell Res 70:719\u2013756","journal-title":"J Artif Intell Res"},{"issue":"3","key":"1258_CR22","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/s10878-023-01017-6","volume":"45","author":"Q Zhao","year":"2023","unstructured":"Zhao Q, Liu W, Nong Q, Fang Q (2023) Constrained heterogeneous facility location games with max-variant cost. J Comb Optim 45(3):90","journal-title":"J Comb Optim"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01258-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-025-01258-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01258-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T21:06:57Z","timestamp":1741900017000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-025-01258-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,20]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["1258"],"URL":"https:\/\/doi.org\/10.1007\/s10878-025-01258-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,20]]},"assertion":[{"value":"2 January 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2025","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 have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"24"}}