{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T17:42:49Z","timestamp":1783791769576,"version":"3.55.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,10,28]],"date-time":"2014-10-28T00:00:00Z","timestamp":1414454400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004895","name":"European Social Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004895","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Greek national funds"},{"name":"Operational Program \u201cEducation and Lifelong Learning\u201d of the National Strategic Reference Framework (NSRF) -- Research Funding Program: THALES"},{"name":"project Algorithmic Game Theory"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2014,10,28]]},"abstract":"<jats:p>\n            We consider\n            <jats:italic>K<\/jats:italic>\n            -Facility Location games, where\n            <jats:italic>n<\/jats:italic>\n            strategic agents report their locations in a metric space and a mechanism maps them to\n            <jats:italic>K<\/jats:italic>\n            facilities. The agents seek to minimize their connection cost, namely the distance of their true location to the nearest facility, and may misreport their location. We are interested in deterministic mechanisms that are strategyproof, that is, ensure that no agent can benefit from misreporting her location, do not resort to monetary transfers, and achieve a bounded approximation ratio to the total connection cost of the agents (or to the\n            <jats:italic>L<\/jats:italic>\n            <jats:sub>\n              <jats:italic>p<\/jats:italic>\n            <\/jats:sub>\n            norm of the connection costs, for some\n            <jats:italic>p<\/jats:italic>\n            \u2208 [1, \u221e) or for\n            <jats:italic>p<\/jats:italic>\n            = \u221e).\n          <\/jats:p>\n          <jats:p>\n            Our main result is an elegant characterization of deterministic strategyproof mechanisms with a bounded approximation ratio for 2-Facility Location on the line. In particular, we show that for instances with\n            <jats:italic>n<\/jats:italic>\n            \u2265 5 agents, any such mechanism either admits a unique dictator or always places the facilities at the leftmost and the rightmost location of the instance. As a corollary, we obtain that the best approximation ratio achievable by deterministic strategyproof mechanisms for the problem of locating 2 facilities on the line to minimize the total connection cost is precisely\n            <jats:italic>n<\/jats:italic>\n            -2. Another rather surprising consequence is that the Two-Extremes mechanism of Procaccia and Tennenholtz [2009] is the only deterministic anonymous strategyproof mechanism with a bounded approximation ratio for 2-Facility Location on the line.\n          <\/jats:p>\n          <jats:p>\n            The proof of the characterization employs several new ideas and technical tools, which provide new insights into the behavior of deterministic strategyproof mechanisms for\n            <jats:italic>K<\/jats:italic>\n            -Facility Location games and may be of independent interest. Employing one of these tools, we show that for every\n            <jats:italic>K<\/jats:italic>\n            \u2265 3, there do not exist any deterministic anonymous strategyproof mechanisms with a bounded approximation ratio for\n            <jats:italic>K<\/jats:italic>\n            -Facility Location on the line, even for simple instances with\n            <jats:italic>K<\/jats:italic>\n            +1 agents. Moreover, building on the characterization for the line, we show that there do not exist any deterministic strategyproof mechanisms with a bounded approximation ratio for 2-Facility Location and instances with\n            <jats:italic>n<\/jats:italic>\n            \u2265 3 agents located in a star.\n          <\/jats:p>","DOI":"10.1145\/2665005","type":"journal-article","created":{"date-parts":[[2014,10,28]],"date-time":"2014-10-28T12:40:29Z","timestamp":1414500029000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":62,"title":["On the Power of Deterministic Mechanisms for Facility Location Games"],"prefix":"10.1145","volume":"2","author":[{"given":"Dimitris","family":"Fotakis","sequence":"first","affiliation":[{"name":"National Technical University of Athens, Athens, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos","family":"Tzamos","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,10,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0457"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA'07)","author":"Arthur D.","unstructured":"D. Arthur and S. Vassilvitskii . 2007. k-means&plus;&plus;: The advantages of careful seeding . In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA'07) . 1027--1035. D. Arthur and S. Vassilvitskii. 2007. k-means&plus;&plus;: The advantages of careful seeding. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA'07). 1027--1035."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003550100151"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.08.002"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229045"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"B.\n      Escoffier L.\n      Gourv\u00e8s N. K.\n      Thang F.\n      Pascual and \n      O.\n      Spanjaard\n  . \n  2011\n  . Strategy-proof mechanisms for facility location games with many facilities. In Proceedings of the 2nd International Conference on \n  Algorithmic Decision Theory (ADT\n  '11) Lecture Notes in Artificial Intelligence Vol. \n  6992 67--81.   B. Escoffier L. Gourv\u00e8s N. K. Thang F. Pascual and O. Spanjaard. 2011. Strategy-proof mechanisms for facility location games with many facilities. In Proceedings of the 2nd International Conference on Algorithmic Decision Theory (ADT'11) Lecture Notes in Artificial Intelligence Vol. 6992 67--81.","DOI":"10.1007\/978-3-642-24873-3_6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482543"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482595"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.11.036"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.2307\/1914083"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2007.03.006"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2050805.2050824"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807342.1807393"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_14"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.41"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003550000074"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00128122"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090254"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566401"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(75)90050-2"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.2001.2807"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481.012"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2665005","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2665005","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:25Z","timestamp":1750227205000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2665005"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,28]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,10,28]]}},"alternative-id":["10.1145\/2665005"],"URL":"https:\/\/doi.org\/10.1145\/2665005","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,28]]},"assertion":[{"value":"2013-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}