{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,26]],"date-time":"2026-07-26T04:08:09Z","timestamp":1785038889682,"version":"3.55.0"},"publisher-location":"Cham","reference-count":50,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032036384","type":"print"},{"value":"9783032036391","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T00:00:00Z","timestamp":1756684800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T00:00:00Z","timestamp":1756684800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-03639-1_7","type":"book-chapter","created":{"date-parts":[[2025,8,31]],"date-time":"2025-08-31T13:24:05Z","timestamp":1756646645000},"page":"119-136","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Constant-Approximate and\u00a0Constant-Strategyproof Two-Facility Location"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-7254-5952","authenticated-orcid":false,"given":"Elijah Journey","family":"Fullerton","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3036-2777","authenticated-orcid":false,"given":"Zeyuan","family":"Hu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7084-1612","authenticated-orcid":false,"given":"C. Gregory","family":"Plaxton","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,9,1]]},"reference":[{"issue":"3","key":"7_CR1","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1287\/moor.1100.0457","volume":"35","author":"N Alon","year":"2010","unstructured":"Alon, N., Feldman, M., Procaccia, A., Tennenholtz, M.: Strategyproof approximation of the minimax on networks. Math. Oper. Res. 35(3), 513\u2013526 (2010)","journal-title":"Math. Oper. Res."},{"key":"7_CR2","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1016\/j.jet.2018.07.001","volume":"177","author":"I Ashlagi","year":"2018","unstructured":"Ashlagi, I., Gonczarowski, Y.A.: Stable matching mechanisms are not obviously strategy-proof. J. Econ. Theory 177, 405\u2013425 (2018)","journal-title":"J. Econ. Theory"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"Auricchio, G., Zhang, J.: The $$k$$-facility location problem via optimal transport: a Bayesian study of the percentile mechanisms. In: Proceedings of the 17th International Symposium on Algorithmic Game Theory, pp. 147\u2013164 (2024)","DOI":"10.1007\/978-3-031-71033-9_9"},{"issue":"2","key":"7_CR4","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1006\/jeth.1993.1069","volume":"61","author":"S Barber\u00e0","year":"1993","unstructured":"Barber\u00e0, S., Gul, F., Stacchetti, E.: Generalized median voter schemes and committees. J. Econ. Theory 61(2), 262\u2013289 (1993)","journal-title":"J. Econ. Theory"},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"Birrell, E., Pass, R.: Approximately strategy-proof voting. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence, pp. 67\u201372 (2011)","DOI":"10.21236\/ADA582553"},{"issue":"1","key":"7_CR6","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1086\/256633","volume":"56","author":"D Black","year":"1948","unstructured":"Black, D.: On the rationale of group decision-making. J. Polit. Econ. 56(1), 23\u201334 (1948)","journal-title":"J. Polit. Econ."},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Candogan, O., Feng, Y.: Mobility data in operations: multi-location facility location problem. In: Proceedings of the 25th ACM Conference on Economics and Computation, p.\u00a0201 (2024)","DOI":"10.1145\/3670865.3673557"},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"Chan, H., Filos-Ratsikas, A., Li, B., Li, M., Wang, C.: Mechanism design for facility location problems: a survey. In: Proceedings of the 13th International Joint Conference on Artificial Intelligence, pp. 4356\u20134365 (2021)","DOI":"10.24963\/ijcai.2021\/596"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"Chen, N., Deng, X., Zhang, J.: How profitable are strategic behaviors in a market? In: Proceedings of the European Symposium on Algorithms, pp. 106\u2013118 (2011)","DOI":"10.1007\/978-3-642-23719-5_10"},{"issue":"2","key":"7_CR10","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1257\/mic.20150035","volume":"8","author":"P Chen","year":"2016","unstructured":"Chen, P., Egesdal, M., Pycia, M., Yenmez, M.B.: Manipulability of stable mechanisms. Am. Econ. J. Microecon. 8(2), 202\u201314 (2016)","journal-title":"Am. Econ. J. Microecon."},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"Cheng, Y., Yu, W., Zhang, G.: Mechanisms for obnoxious facility game on a path. In: Proceedings of the 5th International Conference on Combinatorial Optimization and Applications, pp. 262\u2013271 (2011)","DOI":"10.1007\/978-3-642-22616-8_21"},{"key":"7_CR12","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., Yu, W., Zhang, G.: Strategy-proof approximation mechanisms for an obnoxious facility game on networks. Theor. Comput. Sci. 497, 154\u2013163 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"7_CR13","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1287\/trsc.12.2.107","volume":"12","author":"RL Church","year":"1978","unstructured":"Church, R.L., Garfinkel, R.S.: Locating an obnoxious facility on a network. Transp. Sci. 12(2), 107\u2013118 (1978)","journal-title":"Transp. Sci."},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Dale, E., Fielding, J., Ramakrishnan, H., Sathyanarayanan, S., Weinberg, S.M.: Approximately strategyproof tournament rules with multiple prizes. In: Proceedings of the 23rd ACM Conference on Economics and Computation, pp. 1082\u20131100 (2022)","DOI":"10.1145\/3490486.3538242"},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"Deligkas, A., Lotfi, M., Voudouris, A.A.: Agent-constrained truthful facility location games. In: Proceedings of the 17th International Symposium on Algorithmic Game Theory, pp. 129\u2013146 (2024)","DOI":"10.1007\/978-3-031-71033-9_8"},{"key":"7_CR16","unstructured":"Ding, K., Weinberg, S.M.: Approximately strategyproof tournament rules in the probabilistic setting. In: Proceedings of the 12th Innovations in Theoretical Computer Science Conference, pp. 14:1\u201314:20 (2021)"},{"key":"7_CR17","doi-asserted-by":"crossref","unstructured":"Escoffier, B., Gourv\u00e8s, L., Nguyen, K.T., Pascual, F., Spanjaard, O.: Strategy-proof mechanisms for facility location games with many facilities. In: Proceedings of the 2nd International Conference on Algorithmic Decision Theory, pp. 67\u201381 (2011)","DOI":"10.1007\/978-3-642-24873-3_6"},{"issue":"2","key":"7_CR18","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1007\/s10107-014-0821-x","volume":"153","author":"CG Fernandes","year":"2015","unstructured":"Fernandes, C.G., Meira, L.A.A., Miyazawa, F.K., Pedrosa, L.L.C.: A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems. Math. Program. 153(2), 655\u2013685 (2015)","journal-title":"Math. Program."},{"key":"7_CR19","doi-asserted-by":"crossref","unstructured":"Filimonov, A., Meir, R.: Strategyproof facility location mechanisms on discrete trees. Auton. Agents Multi-Agent Syst. 37(10) (2022)","DOI":"10.1007\/s10458-022-09592-4"},{"key":"7_CR20","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2021.01.028","volume":"858","author":"D Fotakis","year":"2021","unstructured":"Fotakis, D., Kavouras, L., Kostopanagiotis, P., Lazos, P., Skoulakis, S., Zarifis, N.: Reallocating multiple facilities on the line. Theor. Comput. Sci. 858, 13\u201334 (2021)","journal-title":"Theor. Comput. Sci."},{"key":"7_CR21","doi-asserted-by":"crossref","unstructured":"Fotakis, D., Tzamos, C.: On the power of deterministic mechanisms for facility location games. ACM Trans. Econ. Comput. 2(4) (2014)","DOI":"10.1145\/2665005"},{"key":"7_CR22","doi-asserted-by":"crossref","unstructured":"Fukui, Y., Shurbevski, A., Nagamochi, H.: $$\\lambda $$-group strategy-proof mechanisms for the obnoxious facility game in star networks. IEICE Trans. Fundam. E102-A(9), 1179\u20131186 (2019)","DOI":"10.1587\/transfun.E102.A.1179"},{"key":"7_CR23","doi-asserted-by":"crossref","unstructured":"Fullerton, E.J., Hu, Z., Plaxton, C.G.: Constant-approximate and constant-strategyproof two-facility location (2025). https:\/\/arxiv.org\/abs\/2507.04485","DOI":"10.1007\/978-3-032-03639-1_7"},{"issue":"1","key":"7_CR24","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/s00355-022-01435-1","volume":"61","author":"S Goel","year":"2023","unstructured":"Goel, S., Hann-Caruthers, W.: Optimality of the coordinate-wise median mechanism for strategyproof facility location in two dimensions. Soc. Choice Welfare 61(1), 11\u201334 (2023)","journal-title":"Soc. Choice Welfare"},{"key":"7_CR25","doi-asserted-by":"crossref","unstructured":"Gonczarowski, Y.A., Heffetz, O., Thomas, C.: Strategyproofness-exposing mechanism descriptions. In: Proceedings of the 24th ACM Conference on Economics and Computation, p.\u00a0782 (2023)","DOI":"10.1145\/3580507.3597742"},{"key":"7_CR26","doi-asserted-by":"crossref","unstructured":"Gupta, S., Moondra, J., Singh, M.: Which $$L_p$$ norm is the fairest? Approximations for fair facility location across all \u201c$$p$$\u201d. In: Proceedings of the 24th ACM Conference on Economics and Computation, p.\u00a0817 (2023)","DOI":"10.1145\/3580507.3597664"},{"key":"7_CR27","doi-asserted-by":"crossref","unstructured":"Hossain, S., Micha, E., Shah, N.: The surprising power of hiding information in facility location. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence, pp. 2168\u20132175 (2020)","DOI":"10.1609\/aaai.v34i02.5592"},{"key":"7_CR28","unstructured":"Hyafil, N., Boutilier, C.: Regret-based incremental partial revelation mechanisms. In: Proceedings of the 21st AAAI Conference on Artificial Intelligence, pp. 672\u2013678 (2006)"},{"key":"7_CR29","unstructured":"Istrate, G., Bonchis, C.: Mechanism design with predictions for obnoxious facility location (2022). https:\/\/arxiv.org\/abs\/2212.09521"},{"key":"7_CR30","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2024.114913","volume":"1024","author":"P Kanellopoulos","year":"2025","unstructured":"Kanellopoulos, P., Voudouris, A.A., Zhang, R.: Truthful two-facility location with candidate locations. Theor. Comput. Sci. 1024, 114913 (2025)","journal-title":"Theor. Comput. Sci."},{"issue":"10","key":"7_CR31","doi-asserted-by":"publisher","first-page":"2898","DOI":"10.1007\/s00453-022-00993-1","volume":"84","author":"B de Keijzer","year":"2022","unstructured":"de Keijzer, B., Wojtczak, D.: Facility reallocation on the line. Algorithmica 84(10), 2898\u20132925 (2022)","journal-title":"Algorithmica"},{"issue":"1","key":"7_CR32","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0165-4896(84)90059-3","volume":"8","author":"KH Kim","year":"1984","unstructured":"Kim, K.H., Roush, F.W.: Nonmanipulability in two dimensions. Math. Soc. Sci. 8(1), 29\u201343 (1984)","journal-title":"Math. Soc. Sci."},{"key":"7_CR33","doi-asserted-by":"crossref","unstructured":"Klootwijk, S., Manthey, B.: Probabilistic analysis of facility location on random shortest path metrics. In: Proceedings of the 15th Conference on Computability in Europe, pp. 37\u201349 (2019)","DOI":"10.1007\/978-3-030-22996-2_4"},{"key":"7_CR34","unstructured":"Lee, D.T.: Efficient, private, and $$\\epsilon $$-strategyproof elicitation of tournament voting rules. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence, pp. 2026\u20132032 (2015)"},{"issue":"11","key":"7_CR35","doi-asserted-by":"publisher","first-page":"3257","DOI":"10.1257\/aer.20160425","volume":"107","author":"S Li","year":"2017","unstructured":"Li, S.: Obviously strategy-proof mechanisms. Am. Econ. Rev. 107(11), 3257\u20133287 (2017)","journal-title":"Am. Econ. Rev."},{"key":"7_CR36","doi-asserted-by":"crossref","unstructured":"Lu, P., Sun, X., Wang, Y., Zhu, Z.A.: Asymptotically optimal strategy-proof mechanisms for two-facility games. In: Proceedings of the 11th ACM Conference on Electronic Commerce, pp. 315\u2013324 (2010)","DOI":"10.1145\/1807342.1807393"},{"issue":"9","key":"7_CR37","first-page":"1021","volume":"103","author":"B Lubin","year":"2012","unstructured":"Lubin, B., Parkes, D.C.: Approximate strategyproofness. Curr. Sci. 103(9), 1021\u20131032 (2012)","journal-title":"Curr. Sci."},{"issue":"2","key":"7_CR38","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/S0097539703435716","volume":"36","author":"M Mahdian","year":"2006","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Approximation algorithms for metric facility location problems. SIAM J. Comput. 36(2), 411\u2013432 (2006)","journal-title":"SIAM J. Comput."},{"key":"7_CR39","unstructured":"Micha, E., Shah, N.: Proportionally fair clustering revisited. In: Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (2020)"},{"issue":"4","key":"7_CR40","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/BF00128122","volume":"35","author":"H Moulin","year":"1980","unstructured":"Moulin, H.: On strategy-proofness and single peakedness. Public Choice 35(4), 437\u2013455 (1980)","journal-title":"Public Choice"},{"issue":"3","key":"7_CR41","doi-asserted-by":"publisher","first-page":"247","DOI":"10.7155\/jgaa.00415","volume":"21","author":"M Oomine","year":"2017","unstructured":"Oomine, M., Shurbevski, A., Nagamochi, H.: Parameterization of strategy-proof mechanisms in the obnoxious facility game. J. Graph Algorithms Appl. 21(3), 247\u2013263 (2017)","journal-title":"J. Graph Algorithms Appl."},{"key":"7_CR42","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/BF01258276","volume":"21","author":"H Peters","year":"1992","unstructured":"Peters, H., van der Stel, H., Storcken, T.: Pareto optimality, anonymity, and strategy-proofness in location problems. Int. J. Game Theory 21, 221\u2013235 (1992)","journal-title":"Int. J. Game Theory"},{"key":"7_CR43","doi-asserted-by":"crossref","unstructured":"Procaccia, A.D., Tennenholtz, M.: Approximate mechanism design without money. ACM Trans. Econ. Comput. 1(4) (2013)","DOI":"10.1145\/2542174.2542175"},{"key":"7_CR44","unstructured":"Schneider, J., Schvartzman, A., Weinberg, S.M.: Condorcet-consistent and approximately strategyproof tournament rules. In: Proceedings of the 8th Innovations in Theoretical Computer Science Conference, pp. 35:1\u201335:20 (2017)"},{"issue":"2","key":"7_CR45","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1006\/jeth.2001.2807","volume":"104","author":"J Schummer","year":"2002","unstructured":"Schummer, J., Vohra, R.V.: Strategy-proof location on a network. J. Econ. Theory 104(2), 405\u2013428 (2002)","journal-title":"J. Econ. Theory"},{"key":"7_CR46","unstructured":"Schvartzman, A., Weinberg, S.M., Zlatin, E., Zuo, A.: Approximately strategyproof tournament rules: on large manipulating sets and cover-consistence. In: Proceedings of the 11th Innovations in Theoretical Computer Science Conference, pp. 3:1\u20133:25 (2020)"},{"key":"7_CR47","doi-asserted-by":"crossref","unstructured":"Sui, X., Boutilier, C.: Approximately strategy-proof mechanisms for (constrained) facility location. In: Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems, pp. 605\u2013613 (2015)","DOI":"10.65109\/EYET5628"},{"key":"7_CR48","unstructured":"Sui, X., Boutilier, C., Sandholm, T.: Analysis and optimization of multi-dimensional percentile mechanisms. In: Proceedings of the 23rd International Joint Conference on Artificial Intelligence, pp. 367\u2013374 (2013)"},{"key":"7_CR49","doi-asserted-by":"crossref","unstructured":"Tang, P., Yu, D., Zhao, S.: Characterization of group-strategyproof mechanisms for facility location in strictly convex space. In: Proceedings of the 21st ACM Conference on Economics and Computation, pp. 133\u2013157 (2020)","DOI":"10.1145\/3391403.3399471"},{"key":"7_CR50","doi-asserted-by":"crossref","unstructured":"Zhou, H., Li, M., Chan, H.: Strategyproof mechanisms for group-fair facility location problems. In: Proceedings of the 31st International Joint Conference on Artificial Intelligence (2022)","DOI":"10.24963\/ijcai.2022\/87"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Game Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-03639-1_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T15:37:39Z","timestamp":1784993859000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-03639-1_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,1]]},"ISBN":["9783032036384","9783032036391"],"references-count":50,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-03639-1_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,1]]},"assertion":[{"value":"1 September 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SAGT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Algorithmic Game Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bath","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sagt2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}