{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T02:56:21Z","timestamp":1777517781146,"version":"3.51.4"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,7,15]],"date-time":"2021-07-15T00:00:00Z","timestamp":1626307200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NWO","award":["024.002.003"],"award-info":[{"award-number":["024.002.003"]}]},{"name":"ARC","award":["DP150101134, DP180102870"],"award-info":[{"award-number":["DP150101134, DP180102870"]}]},{"name":"NSF","award":["CCF-15-40656, CCF-12-18791"],"award-info":[{"award-number":["CCF-15-40656, CCF-12-18791"]}]},{"name":"BSF","award":["2014\/170"],"award-info":[{"award-number":["2014\/170"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,7,31]]},"abstract":"<jats:p>\n            Let\n            <jats:italic>V<\/jats:italic>\n            be a set of\n            <jats:italic>n<\/jats:italic>\n            points in mathcal R\n            <jats:sup>d<\/jats:sup>\n            , called\n            <jats:italic>voters<\/jats:italic>\n            . A point\n            <jats:italic>p<\/jats:italic>\n            \u2208 mathcal R\n            <jats:sup>d<\/jats:sup>\n            is a\n            <jats:italic>plurality point<\/jats:italic>\n            for\n            <jats:italic>V<\/jats:italic>\n            when the following holds: For every\n            <jats:italic>q<\/jats:italic>\n            \u2208 mathcal R\n            <jats:sup>d<\/jats:sup>\n            , the number of voters closer to\n            <jats:italic>p<\/jats:italic>\n            than to\n            <jats:italic>q<\/jats:italic>\n            is at least the number of voters closer to\n            <jats:italic>q<\/jats:italic>\n            than to\n            <jats:italic>p<\/jats:italic>\n            . Thus, in a vote where each\u00a0\n            <jats:italic>v<\/jats:italic>\n            \u2208\n            <jats:italic>V<\/jats:italic>\n            votes for the nearest proposal (and voters for which the proposals are at equal distance abstain), proposal\u00a0\n            <jats:italic>p<\/jats:italic>\n            will not lose against any alternative proposal\u00a0\n            <jats:italic>q<\/jats:italic>\n            . For most voter sets, a plurality point does not exist. We therefore introduce the concept of\n            <jats:italic>\u03b2-plurality points<\/jats:italic>\n            , which are defined similarly to regular plurality points, except that the distance of each voter to\n            <jats:italic>p<\/jats:italic>\n            (but not to\u00a0\n            <jats:italic>q<\/jats:italic>\n            ) is scaled by a factor\u00a0\n            <jats:italic>\u03b2<\/jats:italic>\n            , for some constant\u00a00&lt; \u03b2 \u2a7d 1. We investigate the existence and computation of\n            <jats:italic>\u03b2<\/jats:italic>\n            -plurality points and obtain the following results.\n          <\/jats:p>\n          <jats:p>\n            \u2022 Define \u03b2\n            <jats:sup>*<\/jats:sup>\n            <jats:sub>d<\/jats:sub>\n            := {\u03b2 : any finite multiset\n            <jats:italic>V<\/jats:italic>\n            in mathcal R\n            <jats:sup>d<\/jats:sup>\n            admits a \u03b2-plurality point. We prove that \u03b2\n            <jats:sup>*<\/jats:sup>\n            <jats:sub>d<\/jats:sub>\n            = \u221a3\/2, and that 1\/\u221a\n            <jats:italic>d<\/jats:italic>\n            \u2a7d \u03b2\n            <jats:sup>*<\/jats:sup>\n            <jats:sub>d<\/jats:sub>\n            \u2a7d \u221a 3\/2 for all\n            <jats:italic>d<\/jats:italic>\n            \u2a7e 3.\n          <\/jats:p>\n          <jats:p>\n            \u2022 Define \u03b2 (\n            <jats:italic>p, V<\/jats:italic>\n            ) := sup {\u03b2 :\n            <jats:italic>p<\/jats:italic>\n            is a \u03b2 -plurality point for\n            <jats:italic>V<\/jats:italic>\n            }. Given a voter set\n            <jats:italic>V<\/jats:italic>\n            in mathcal R\n            <jats:sup>2<\/jats:sup>\n            , we provide an algorithm that runs in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) time and computes a point\n            <jats:italic>p<\/jats:italic>\n            such that \u03b2 (\n            <jats:italic>p<\/jats:italic>\n            ,\n            <jats:italic>V<\/jats:italic>\n            ) \u2a7e \u03b2\n            <jats:sup>*<\/jats:sup>\n            <jats:sub>b<\/jats:sub>\n            . Moreover, for\n            <jats:italic>d<\/jats:italic>\n            \u2a7e 2, we can compute a point\u00a0\n            <jats:italic>p<\/jats:italic>\n            with \u03b2 (\n            <jats:italic>p<\/jats:italic>\n            ,\n            <jats:italic>V<\/jats:italic>\n            ) \u2a7e 1\/\u221a\n            <jats:italic>d<\/jats:italic>\n            in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) time.\n          <\/jats:p>\n          <jats:p>\n            \u2022 Define \u03b2 (\n            <jats:italic>V<\/jats:italic>\n            ) := sup { \u03b2 :\n            <jats:italic>V<\/jats:italic>\n            admits a \u03b2 -plurality point}. We present an algorithm that, given a voter set\n            <jats:italic>V<\/jats:italic>\n            in mathcal R\n            <jats:sup>d<\/jats:sup>\n            , computes an ((1-\u025b)\u010b \u03b2 (\n            <jats:italic>V<\/jats:italic>\n            ))-plurality point in time\n            <jats:italic>O<\/jats:italic>\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            \u025b\n            <jats:sup>3d-2<\/jats:sup>\n            \u010b log\n            <jats:italic>n<\/jats:italic>\n            \u025b\n            <jats:sup>d-1<\/jats:sup>\n            \u010b log\n            <jats:sup>2<\/jats:sup>\n            1\u025b).\n          <\/jats:p>","DOI":"10.1145\/3459097","type":"journal-article","created":{"date-parts":[[2021,7,16]],"date-time":"2021-07-16T05:26:33Z","timestamp":1626413193000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["On \u03b2-Plurality Points in Spatial Voting Games"],"prefix":"10.1145","volume":"17","author":[{"given":"Boris","family":"Aronov","sequence":"first","affiliation":[{"name":"Tandon School of Engineering, New York University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"De Berg","sequence":"additional","affiliation":[{"name":"Department of Computing Science, TU Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joachim","family":"Gudmundsson","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Horton","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(00)00022-5"},{"key":"e_1_2_1_2_1","volume-title":"Algorithms in Real Algebraic Geometry","author":"Basu Saugata","unstructured":"Saugata Basu , Richard Pollack , and Marie-Fran\u00e7oise Roy . 2006. Algorithms in Real Algebraic Geometry , 2 nd ed. Springer-Verlag , Berlin . Saugata Basu, Richard Pollack, and Marie-Fran\u00e7oise Roy. 2006. Algorithms in Real Algebraic Geometry, 2nd ed. Springer-Verlag, Berlin.","edition":"2"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"key":"e_1_2_1_4_1","article-title":"Faster algorithms for computing plurality points","volume":"14","author":"de Berg Mark","year":"2018","unstructured":"Mark de Berg , Joachim Gudmundsson , and Mehran Mehr . 2018 . Faster algorithms for computing plurality points . ACM Trans. Algor. 14 , 3, Article 36 (2018), 23 pages. Mark de Berg, Joachim Gudmundsson, and Mehran Mehr. 2018. Faster algorithms for computing plurality points. ACM Trans. Algor. 14, 3, Article 36 (2018), 23 pages.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1086\/256633"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189314"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90261-Y"},{"key":"e_1_2_1_8_1","volume-title":"Optimally Locating a New Candidate in Spatial and Valence Models of Voting Games. Honours thesis","author":"Chung Jonathan","unstructured":"Jonathan Chung . 2018. Optimally Locating a New Candidate in Spatial and Valence Models of Voting Games. Honours thesis , University of Sydney . Jonathan Chung. 2018. Optimally Locating a New Candidate in Spatial and Valence Models of Voting Games. Honours thesis, University of Sydney."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009354"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1086\/257897"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.37236\/2356"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00114527"},{"key":"e_1_2_1_13_1","volume-title":"Oxford Handbook of Public Choice, Roger D","author":"Evrenk Haldun","unstructured":"Haldun Evrenk . 2019. Valence politics . In Oxford Handbook of Public Choice, Roger D . Congleton, Bernard Grofman, Stefan Voigt, and Haldun Evrenk (Eds.). Oxford University Press , Oxford, UK , Chapter 13, 266\u2013291. Haldun Evrenk. 2019. Valence politics. In Oxford Handbook of Public Choice, Roger D. Congleton, Bernard Grofman, Stefan Voigt, and Haldun Evrenk (Eds.). Oxford University Press, Oxford, UK, Chapter 13, 266\u2013291."},{"key":"e_1_2_1_14_1","volume-title":"Centripetal forces in spatial voting: On the size of the Yolk. Public Choice 59 (Oct","author":"Feld Scott","year":"1988","unstructured":"Scott Feld , Bernard Grofman , and Nicholas Miller . 1988. Centripetal forces in spatial voting: On the size of the Yolk. Public Choice 59 (Oct . 1988 ), 37\u201350. Scott Feld, Bernard Grofman, and Nicholas Miller. 1988. Centripetal forces in spatial voting: On the size of the Yolk. Public Choice 59 (Oct. 1988), 37\u201350."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 35th AAAI Conference on Artificial Intelligence. AAAI Press, Online, 1\u201312","author":"Filtser Arnold","year":"2021","unstructured":"Arnold Filtser and Omrit Filtser . 2021 . Plurality in spatial voting games with constant . In Proceedings of the 35th AAAI Conference on Artificial Intelligence. AAAI Press, Online, 1\u201312 . To appear. Retrieved from https:\/\/arxiv.org\/abs\/ 2005.04799. Arnold Filtser and Omrit Filtser. 2021. Plurality in spatial voting games with constant . In Proceedings of the 35th AAAI Conference on Artificial Intelligence. AAAI Press, Online, 1\u201312. To appear. Retrieved from https:\/\/arxiv.org\/abs\/2005.04799."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.mathsocsci.2018.12.001"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-010-0495-0"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33012012"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpubeco.2007.11.001"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9779.2008.00371.x"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017460.1017461"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.2307\/2111098"},{"key":"e_1_2_1_23_1","volume-title":"Handbook of Social Choice and Voting, Jac C","author":"Miller Nicholas R.","unstructured":"Nicholas R. Miller . 2015. The spatial model of social choice and voting . In Handbook of Social Choice and Voting, Jac C . Heckelman and Nicholas R. Miller (Eds.). Edward Elgar Publishing , Cheltenham, UK , Chapter 10, 163\u2013181. Nicholas R. Miller. 2015. The spatial model of social choice and voting. In Handbook of Social Choice and Voting, Jac C. Heckelman and Nicholas R. Miller (Eds.). Edward Elgar Publishing, Cheltenham, UK, Chapter 10, 163\u2013181."},{"key":"e_1_2_1_24_1","first-page":"787","article-title":"A notion of equilibrium and its possibility under majority rule","volume":"57","author":"Plott Charles R.","year":"1967","unstructured":"Charles R. Plott . 1967 . A notion of equilibrium and its possibility under majority rule . Amer. Econ. Rev. 57 , 4 (1967), 787 \u2013 806 . Charles R. Plott. 1967. A notion of equilibrium and its possibility under majority rule. Amer. Econ. Rev. 57, 4 (1967), 787\u2013806.","journal-title":"Amer. Econ. Rev."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0007123410000505"},{"key":"e_1_2_1_26_1","volume-title":"Agarwal","author":"Sharir Micha","year":"1995","unstructured":"Micha Sharir and Pankaj K . Agarwal . 1995 . Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press , Cambridge, UK. Micha Sharir and Pankaj K. Agarwal. 1995. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.2307\/1952828"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1177\/0951629806061858"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-45030-3_64"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3459097","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3459097","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3459097","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:02Z","timestamp":1750193222000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3459097"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,15]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,7,31]]}},"alternative-id":["10.1145\/3459097"],"URL":"https:\/\/doi.org\/10.1145\/3459097","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,15]]},"assertion":[{"value":"2020-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}