{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T16:46:45Z","timestamp":1769273205427,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","funder":[{"name":"Simons Institute","award":["Simons Investigator Award"],"award-info":[{"award-number":["Simons Investigator Award"]}]},{"name":"NSF","award":["1942123"],"award-info":[{"award-number":["1942123"]}]},{"name":"NSERC","award":["2022-04191"],"award-info":[{"award-number":["2022-04191"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718235","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"1590-1601","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Six Candidates Suffice to Win a Voter Majority"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0807-3389","authenticated-orcid":false,"given":"Moses","family":"Charikar","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6215-066X","authenticated-orcid":false,"given":"Alexandra","family":"Lassota","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8853-3578","authenticated-orcid":false,"given":"Prasanna","family":"Ramakrishnan","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2213-4937","authenticated-orcid":false,"given":"Adrian","family":"Vetta","sequence":"additional","affiliation":[{"name":"McGill University, Montreal, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8688-2478","authenticated-orcid":false,"given":"Kangning","family":"Wang","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Proceedings of International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). 78\u201384","author":"Anbalagan Yogesh","year":"2015","unstructured":"Yogesh Anbalagan, Hao Huang, Shachar Lovett, Sergey Norin, Adrian Vetta, and Hehui Wu. 2015. Large supports are required for well-supported Nash equilibria. In Proceedings of International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). 78\u201384."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-016-1019-3"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-007-0268-6"},{"key":"e_1_3_2_1_4_1","unstructured":"Suzanne Bloks. 2018. Condorcet Winning Sets. Master\u2019s thesis. Department of Mathematics London School of Economics and Political Science."},{"key":"e_1_3_2_1_5_1","unstructured":"Zarathustra Brady. 2013. Circular domination in R^4. MathOverflow. arxiv:https:\/\/mathoverflow.net\/q\/151008. https:\/\/mathoverflow.net\/q\/151008"},{"key":"e_1_3_2_1_6_1","volume-title":"Tournament solutions","author":"Brandt Felix","unstructured":"Felix Brandt, Markus Brill, and Paul Harrenstein. 2016. Tournament solutions. Cambridge University Press, 57\u201384."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3580507.3597785"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3417750"},{"key":"e_1_3_2_1_9_1","unstructured":"Danilo Coelho. 2005. Understanding evaluating and selecting voting rules through games and axioms. Universitat Aut\u00f2noma de Barcelona ."},{"key":"e_1_3_2_1_10_1","unstructured":"Nicolas de Condorcet. 1785. Essai sur l\u2019application de l\u2019analyse \u00e0 la probabilit\u00e9 des d\u00e9cisions rendues \u00e0 la pluralit\u00e9 des voix. Imprimerie royale."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.2307\/2339223"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-017-1026-z"},{"key":"e_1_3_2_1_13_1","volume-title":"Twenty-Second International Joint Conference on Artificial Intelligence.","author":"Elkind Edith","year":"2011","unstructured":"Edith Elkind, J\u00e9r\u00f4me Lang, and Abdallah Saffidine. 2011. Choosing collectively optimal sets of alternatives based on the Condorcet criterion. In Twenty-Second International Joint Conference on Artificial Intelligence."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-014-0853-4"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219174"},{"key":"e_1_3_2_1_16_1","volume-title":"Multiwinner voting: A new challenge for social choice theory. Trends in computational social choice, 74","author":"Faliszewski Piotr","year":"2017","unstructured":"Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. 2017. Multiwinner voting: A new challenge for social choice theory. Trends in computational social choice, 74, 2017 (2017), 27\u201347."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3296672"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1609\/AAAI.V31I1.10611"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0133030"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0141041"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(81)90005-3"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.2307\/2297786"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Duncan K. Foley. 1970. Lindahl\u2019s Solution and the Core of an Economy with Public Goods. Econometrica 66\u201372.","DOI":"10.2307\/1909241"},{"key":"e_1_3_2_1_24_1","unstructured":"Christian Geist. 2014. Finding Preference Profiles of Condorcet Dimension k via SAT. arXiv preprint arXiv:1402.4303."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.7155\/JGAA.00331"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Irving John Good. 1971. A note on Condorcet sets. Public Choice 97\u2013101.","DOI":"10.1007\/BF01718625"},{"key":"e_1_3_2_1_27_1","unstructured":"G\u00fcnter H\u00e4gele and Friedrich Pukelsheim. 2000. Lulls Schriften zu Wahlverfahren. Augsburg Universit\u00e4tsbibliothek und Institut f\u00fcr Mathematik."},{"key":"e_1_3_2_1_28_1","volume-title":"Phragm\u00e9n\u2019s and Thiele\u2019s election methods. CoRR, abs\/1611.08826","author":"Janson Svante","year":"2016","unstructured":"Svante Janson. 2016. Phragm\u00e9n\u2019s and Thiele\u2019s election methods. CoRR, abs\/1611.08826 (2016), arXiv:1611.08826. arxiv:1611.08826"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384238"},{"key":"e_1_3_2_1_30_1","volume-title":"Handbook on approval voting","author":"Kilgour D. Marc","unstructured":"D. Marc Kilgour. 2010. Approval balloting for multi-winner elections. In Handbook on approval voting. Springer, 105\u2013124."},{"key":"e_1_3_2_1_31_1","volume-title":"Mathematics and Social Sciences I: Proceedings of the seminars of Menthon-Saint-Bernard, France (1\u201327","author":"Kreweras Germain","year":"1965","unstructured":"Germain Kreweras. 1965. Aggregation of preference orderings. In Mathematics and Social Sciences I: Proceedings of the seminars of Menthon-Saint-Bernard, France (1\u201327 July 1960) and of G\u00f6sing, Austria (3\u201327 July 1962). 73\u201379."},{"key":"e_1_3_2_1_32_1","volume-title":"Multi-winner voting with approval preferences","author":"Lackner Martin","unstructured":"Martin Lackner and Piotr Skowron. 2023. Multi-winner voting with approval preferences. Springer Nature."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1993.1010"},{"key":"e_1_3_2_1_34_1","volume-title":"The Condorcet Dimension of Metric Spaces. CoRR, abs\/2410.09201","author":"Lassota Alexandra","year":"2024","unstructured":"Alexandra Lassota, Adrian Vetta, and Bernhard von Stengel. 2024. The Condorcet Dimension of Metric Spaces. CoRR, abs\/2410.09201 (2024), arXiv:2410.09201. arxiv:2410.09201"},{"key":"e_1_3_2_1_35_1","unstructured":"Ramon Llull. 1274\u201383. Artifitium electionis personarum. Manuscript written between 1274\u201383"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Nicholas R. Miller. 1980. A new solution set for tournaments and majority voting: Further graph-theoretical approaches to the theory of voting. American Journal of Political Science 68\u201396.","DOI":"10.2307\/2110925"},{"key":"e_1_3_2_1_37_1","unstructured":"D\u00f6m\u00f6t\u00f6r P\u00e1lv\u00f6lgyi. 2013. Is there a finite family of functions such that the max of any two functions can be dominated by a third? MathOverflow. arxiv:https:\/\/mathoverflow.net\/q\/148466. https:\/\/mathoverflow.net\/q\/148466"},{"key":"e_1_3_2_1_38_1","volume-title":"Proportional Participatory Budgeting with Additive Utilities. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems (NeurIPS). 12726\u201312737","author":"Peters Dominik","year":"2021","unstructured":"Dominik Peters, Grzegorz Pierczynski, and Piotr Skowron. 2021. Proportional Participatory Budgeting with Additive Utilities. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems (NeurIPS). 12726\u201312737."},{"key":"e_1_3_2_1_39_1","unstructured":"Dominik Peters and Piotr Skowron. [n. d.]. Method of Equal Shares. https:\/\/equalshares.net\/"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399465"},{"key":"e_1_3_2_1_41_1","volume-title":"Sur une m\u00e9thode nouvelle pour r\u00e9aliser, dans les \u00e9lections, la repr\u00e9sentation proportionnelle des partis. \u00d6fversigt af Kongliga Vetenskaps-Akademiens F\u00f6rhandlingar, 51, 3","author":"Phragm\u00e9n Edvard","year":"1894","unstructured":"Edvard Phragm\u00e9n. 1894. Sur une m\u00e9thode nouvelle pour r\u00e9aliser, dans les \u00e9lections, la repr\u00e9sentation proportionnelle des partis. \u00d6fversigt af Kongliga Vetenskaps-Akademiens F\u00f6rhandlingar, 51, 3 (1894), 133\u2013137."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Herbert E. Scarf. 1967. The core of an N person game. Econometrica 50\u201369.","DOI":"10.2307\/1909383"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2018.12.011"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"John H. Smith. 1973. Aggregation of preferences with variable electorate. Econometrica 1027\u20131041.","DOI":"10.2307\/1914033"},{"key":"e_1_3_2_1_45_1","unstructured":"David Speyer. 2013. Strongly connected directed graphs with large directed diameter and small undirected diameter? MathOverflow. arxiv:https:\/\/mathoverflow.net\/q\/150574. https:\/\/mathoverflow.net\/q\/150574"},{"key":"e_1_3_2_1_46_1","unstructured":"Thorvald N. Thiele. 1895. Om flerfoldsvalg. Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger 415\u2013441."},{"key":"e_1_3_2_1_47_1","volume-title":"Zur theorie der gesellschaftsspiele. Mathematische annalen, 100, 1","author":"von Neumann John","year":"1928","unstructured":"John von Neumann. 1928. Zur theorie der gesellschaftsspiele. Mathematische annalen, 100, 1 (1928), 295\u2013320."},{"key":"e_1_3_2_1_48_1","unstructured":"Sam Zbarsky. 2014. Is there a finite family of functions such that the max of any two functions can be dominated by a third? MathOverflow. arxiv:https:\/\/mathoverflow.net\/q\/157982. https:\/\/mathoverflow.net\/q\/157982"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia","acronym":"STOC '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718235","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:45:25Z","timestamp":1750693525000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718235"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":48,"alternative-id":["10.1145\/3717823.3718235","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718235","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}