{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,26]],"date-time":"2024-10-26T04:18:35Z","timestamp":1729916315718,"version":"3.28.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T00:00:00Z","timestamp":1712275200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T00:00:00Z","timestamp":1712275200000},"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":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider a setting with agents that have preferences over alternatives and are partitioned into disjoint districts. The goal is to choose one alternative as the winner using a mechanism which first decides a representative alternative for each district based on a local election with the agents therein as participants, and then chooses one of the district representatives as the winner. Previous work showed bounds on the distortion of a specific class of deterministic plurality-based mechanisms depending on the available information about the preferences of the agents in the districts. In this paper, we first consider the whole class of deterministic mechanisms and show asymptotically tight bounds on their distortion. We then initiate the study of the distortion of randomized mechanisms in distributed voting and show bounds based on several informational assumptions, which in many cases turn out to be tight. Finally, we also experimentally compare the distortion of many different mechanisms of interest using synthetic and real-world data.<\/jats:p>","DOI":"10.1007\/s00224-024-10171-1","type":"journal-article","created":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T08:01:54Z","timestamp":1712304114000},"page":"1138-1159","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Revisiting the Distortion of Distributed Voting"],"prefix":"10.1007","volume":"68","author":[{"given":"Aris","family":"Filos-Ratsikas","sequence":"first","affiliation":[]},{"given":"Alexandros A.","family":"Voudouris","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,4,5]]},"reference":[{"key":"10171_CR1","doi-asserted-by":"crossref","unstructured":"Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.D., editors.: Handbook of computational social choice. Cambridge University Press (2016)","DOI":"10.1017\/CBO9781107446984.002"},{"key":"10171_CR2","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), pages 4294\u20134301 (2021)","DOI":"10.24963\/ijcai.2021\/589"},{"key":"10171_CR3","doi-asserted-by":"crossref","unstructured":"Procaccia, A.D., Rosenschein, J.S.: The distortion of cardinal preferences in voting. In International Workshop on Cooperative Information Agents (CIA), pages 317\u2013331 (2006)","DOI":"10.1007\/11839354_23"},{"key":"10171_CR4","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/j.artint.2015.06.003","volume":"227","author":"C Boutilier","year":"2015","unstructured":"Boutilier, C., Caragiannis, I., Haber, S., Lu, T., Procaccia, A.D., Sheffet, O.: Optimal social choice functions: A utilitarian view. Artificial Intelligence 227, 190\u2013213 (2015)","journal-title":"Artificial Intelligence"},{"key":"10171_CR5","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. Artificial Intelligence 264, 27\u201351 (2018)","journal-title":"Artificial Intelligence"},{"key":"10171_CR6","doi-asserted-by":"crossref","unstructured":"Gkatzelis, V., Halpern, D., Shah, N.: Resolving the optimal metric distortion conjecture. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 1427\u20131438 (2020)","DOI":"10.1109\/FOCS46700.2020.00134"},{"key":"10171_CR7","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2020.103343","volume":"286","author":"A Filos-Ratsikas","year":"2020","unstructured":"Filos-Ratsikas, A., Micha, E., Voudouris, A.A.: The distortion of distributed voting. Artificial Intelligence 286, 103343 (2020)","journal-title":"Artificial Intelligence"},{"key":"10171_CR8","doi-asserted-by":"publisher","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. Artificial Intelligence 308, 103713 (2022)","journal-title":"Artificial Intelligence"},{"key":"10171_CR9","doi-asserted-by":"crossref","unstructured":"Filos-Ratsikas, A., Voudouris, A.A.: Approximate mechanism design for distributed facility location. In International Symposium on Algorithmic Game Theory, pages 49\u201363. Springer (2021)","DOI":"10.1007\/978-3-030-85947-3_4"},{"key":"10171_CR10","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, A.A., Zhang, R.: The distortion of distributed facility location. Artificial Intelligence 328, 104066 (2024)","journal-title":"Artificial Intelligence"},{"issue":"3","key":"10171_CR11","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1016\/j.orl.2023.03.004","volume":"51","author":"AA Voudouris","year":"2023","unstructured":"Voudouris, A.A.: Tight distortion bounds for distributed metric voting on a line. Operations Research Letters 51(3), 266\u2013269 (2023)","journal-title":"Operations Research Letters"},{"key":"10171_CR12","doi-asserted-by":"crossref","unstructured":"Ebadian, S., Kahng, A., Peters, D., Shah, N.: Optimized distortion and proportional fairness in voting. In Proceedings of the 23rd ACM Conference on Economics and Computation (EC), pages 563\u2013600 (2022)","DOI":"10.1145\/3490486.3538339"},{"key":"10171_CR13","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), pages 175\u2013188 (2014)","DOI":"10.1007\/978-3-319-13129-0_13"},{"key":"10171_CR14","unstructured":"Bhaskar, U., Ghosh, A.: On the welfare of cardinal voting mechanisms. In Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 27:1\u201327:22 (2018)"},{"key":"10171_CR15","doi-asserted-by":"crossref","unstructured":"Bhaskar, U., Dani, V., Ghosh, A.: Truthful and near-optimal mechanisms for welfare maximization in multi-winner elections. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), pages 925\u2013932 (2018)","DOI":"10.1609\/aaai.v32i1.11480"},{"key":"10171_CR16","doi-asserted-by":"crossref","unstructured":"Gibbard, A.: Manipulation of schemes that mix voting with chance. Econometrica: Journal of the Econometric Society 665\u2013681 (1977)","DOI":"10.2307\/1911681"},{"key":"10171_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-9838-4_4","volume-title":"Nice decision schemes","author":"S Barbera","year":"1978","unstructured":"Barbera, S.: Nice decision schemes. Springer, Netherlands (1978)"},{"key":"10171_CR18","doi-asserted-by":"crossref","unstructured":"Kizilkaya, F.E., Kempe, D.: Plurality veto: A simple voting rule achieving optimal metric distortion. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pages 349\u2013355 (2022)","DOI":"10.24963\/ijcai.2022\/50"},{"key":"10171_CR19","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1613\/jair.5282","volume":"58","author":"I Caragiannis","year":"2017","unstructured":"Caragiannis, I., Nath, S., Procaccia, A.D., Shah, N.: Subset selection via implicit utilitarian voting. Journal of Artificial Intelligence Research 58, 123\u2013152 (2017)","journal-title":"Journal of Artificial Intelligence Research"},{"key":"10171_CR20","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Shah, N., Voudouris, A.A.: The metric distortion of multiwinner voting. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pages 4900\u20134907 (2022)","DOI":"10.1609\/aaai.v36i5.20419"},{"key":"10171_CR21","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 Symposium of Algorithmic Game Theory (SAGT), pages 1\u201312 (2014)","DOI":"10.1007\/978-3-662-44803-8_1"},{"key":"10171_CR22","doi-asserted-by":"crossref","unstructured":"Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., Voudouris, A.A.: A few queries go a long way: Information-distortion tradeoffs in matching. Journal of Artificial Intelligence Research 74 (2022a)","DOI":"10.1613\/jair.1.12690"},{"key":"10171_CR23","doi-asserted-by":"crossref","unstructured":"Benad\u00e8, G., Nath, S., Procaccia, A.D., Shah, N.: Preference elicitation for participatory budgeting. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pages 376\u2013382 (2017)","DOI":"10.1609\/aaai.v31i1.10563"},{"key":"10171_CR24","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), pages 390\u2013396 (2016)","DOI":"10.1609\/aaai.v30i1.10032"},{"key":"10171_CR25","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103488","volume":"296","author":"G Amanatidis","year":"2021","unstructured":"Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., Voudouris, A.A.: Peeking behind the ordinal curtain: Improving distortion via cardinal queries. Artificial Intelligence. 296, 103488 (2021)","journal-title":"Artificial Intelligence."},{"key":"10171_CR26","unstructured":"Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., Voudouris, A.A.: Don\u2019t roll the dice, ask twice: The two-query distortion of matching problems and beyond. In Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS) (2022b)"},{"key":"10171_CR27","unstructured":"Mandal, D., Procaccia, A.D., Shah, N., Woodruff, D.P.: Efficient and thrifty voting by any means necessary. In Proceedings of the 32nd Annual Conference on Neural Information Processing Systems (NeurIPS), pages 7178\u20137189 (2019)"},{"key":"10171_CR28","doi-asserted-by":"crossref","unstructured":"Mandal, D., Shah, N., Woodruff, D.P.: Optimal communication-distortion tradeoff in voting. In Proceedings of the 21st ACM Conference on Economics and Computation (EC), pages 795\u2013813 (2020)","DOI":"10.1145\/3391403.3399510"},{"key":"10171_CR29","doi-asserted-by":"crossref","unstructured":"Abramowitz, B., Anshelevich, E., Zhu, W.: Awareness of voter passion greatly improves the distortion of metric social choice. In Proceedings of the The 15th Conference on Web and Internet Economics (WINE), pages 3\u201316 (2019)","DOI":"10.1007\/978-3-030-35389-6_1"},{"key":"10171_CR30","doi-asserted-by":"crossref","unstructured":"Ma, T., Menon, V., Larson, K.: Improving welfare in one-sided matchings using simple threshold queries. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pages 321\u2013327 (2021)","DOI":"10.24963\/ijcai.2021\/45"},{"key":"10171_CR31","doi-asserted-by":"crossref","unstructured":"Borodin, A., Lev, O., Shah, N., Strangway, T.: Primarily about primaries. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), pages 1804\u20131811 (2019)","DOI":"10.1609\/aaai.v33i01.33011804"},{"key":"10171_CR32","unstructured":"Bachrach, Y., Lev, O., Lewenberg, Y., Zick, Y.: Misrepresentation in district voting. In IJCAI, pages 81\u201387 (2016)"},{"key":"10171_CR33","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2020.103401","volume":"290","author":"E Elkind","year":"2021","unstructured":"Elkind, E., Gan, J., Obraztsova, S., Rabinovich, Z., Voudouris, A.A.: Protecting elections by recounting ballots. Artificial Intelligence 290, 103401 (2021)","journal-title":"Artificial Intelligence"},{"key":"10171_CR34","unstructured":"Lewenberg, Y., Lev, O., Rosenschein, J.S.: Divide and conquer: Using geographic manipulation to win district-based elections. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, pages 624\u2013632 (2017)"},{"key":"10171_CR35","doi-asserted-by":"publisher","first-page":"2069","DOI":"10.1609\/aaai.v33i01.33012069","volume":"33","author":"O Lev","year":"2019","unstructured":"Lev, O., Lewenberg, Y.: \u201cReverse gerrymandering\u2019\u2019: Manipulation in multi-group decision making. In Proceedings of the AAAI Conference on Artificial Intelligence 33, 2069\u20132076 (2019)","journal-title":"In Proceedings of the AAAI Conference on Artificial Intelligence"},{"key":"10171_CR36","doi-asserted-by":"crossref","unstructured":"Borodin, A., Lev, O., Shah, N., Strangway, T.: Big city vs. the great outdoors: Voter distribution and how it affects gerrymandering. In IJCAI, pages 98\u2013104 (2018)","DOI":"10.24963\/ijcai.2018\/14"},{"key":"10171_CR37","unstructured":"Hylland, A.: Strategy proofness of voting procedures with lotteries as outcomes and infinite sets of strategies. Technical report, 1980"},{"issue":"2","key":"10171_CR38","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1023\/A:1011419012209","volume":"4","author":"K Goldberg","year":"2001","unstructured":"Goldberg, K., Roeder, T., Gupta, D., Perkins, C.: Eigentaste: A constant time collaborative filtering algorithm. Information Retrieval 4(2), 133\u2013151 (2001)","journal-title":"Information Retrieval"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10171-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10171-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10171-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T09:54:02Z","timestamp":1729850042000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10171-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,5]]},"references-count":38,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["10171"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10171-1","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2024,4,5]]},"assertion":[{"value":"7 March 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 April 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}