{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T14:50:27Z","timestamp":1776351027877,"version":"3.51.2"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["1814152 and 1916647"],"award-info":[{"award-number":["1814152 and 1916647"]}]},{"name":"US-Israel Binational Science Foundation","award":["201775"],"award-info":[{"award-number":["201775"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM\/IMS Trans. Data Sci."],"published-print":{"date-parts":[[2021,8,31]]},"abstract":"<jats:p>We investigate the practical aspects of computing the necessary and possible winners in elections over incomplete voter preferences. In the case of the necessary winners, we show how to implement and accelerate the polynomial-time algorithm of Xia and Conitzer. In the case of the possible winners, where the problem is NP-hard, we give a natural reduction to Integer Linear Programming (ILP) for all positional scoring rules and implement it in a leading commercial optimization solver. Further, we devise optimization techniques to minimize the number of ILP executions and, oftentimes, avoid them altogether. We conduct a thorough experimental study that includes the construction of a rich benchmark of election data based on real and synthetic data. Our findings suggest that, the worst-case intractability of the possible winners notwithstanding, the algorithmic techniques presented here scale well and can be used to compute the possible winners in realistic scenarios.<\/jats:p>","DOI":"10.1145\/3458472","type":"journal-article","created":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T16:17:23Z","timestamp":1626884243000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Algorithmic Techniques for Necessary and Possible Winners"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0997-4149","authenticated-orcid":false,"given":"Vishal","family":"Chakraborty","sequence":"first","affiliation":[{"name":"University of California Santa Cruz, Santa Cruz, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Theo","family":"Delemazure","sequence":"additional","affiliation":[{"name":"Ecole Normale Superieure, PARIS, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benny","family":"Kimelfeld","sequence":"additional","affiliation":[{"name":"Technion - Israel Institute of Technology, Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Phokion G.","family":"Kolaitis","sequence":"additional","affiliation":[{"name":"University of California Santa Cruz and IBM Research, Santa Cruz, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kunal","family":"Relia","sequence":"additional","affiliation":[{"name":"New York University, Brooklyn, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1587-0450","authenticated-orcid":false,"given":"Julia","family":"Stoyanovich","sequence":"additional","affiliation":[{"name":"New York University, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2343776.2343779"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.11.016"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.002"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1661445.1661455"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2283396.2283407"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/3033138"},{"key":"e_1_2_1_7_1","volume-title":"Kolaitis","author":"Chakraborty Vishal","year":"2020","unstructured":"Vishal Chakraborty and Phokion G. Kolaitis. 2020. The complexity of possible winners on partial chains. CoRR abs\/2002.12510 (2020). arxiv:2002.12510. https:\/\/arxiv.org\/abs\/2002.12510."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2900423.2900528"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02295838"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(86)90066-0"},{"key":"e_1_2_1_11_1","volume-title":"Gurobi Optimizer Reference Manual. Gurobi Optimization LLC","author":"Gurobi Optimisation","unstructured":"Optimisation Gurobi. 2019. Gurobi Optimizer Reference Manual. Gurobi Optimization LLC, Beaverton, OR. http:\/\/www.gurobi.com\/."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/3306127.3332007"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3304415.3304461"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319692"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the IJCAI-05 Multidisciplinary Workshop on Advances in Preference Handling","volume":"20","author":"Konczak Kathrin","year":"2005","unstructured":"Kathrin Konczak and J\u00e9r\u00f4me Lang. 2005. Voting procedures with incomplete preferences. In Proceedings of the IJCAI-05 Multidisciplinary Workshop on Advances in Preference Handling, Vol. 20. IJCAI."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/44.1-2.114"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1016\/j.ejor.2015.08.052","article-title":"Solving hard control problems in voting systems via integer programming","volume":"250","author":"Polyakovskiy Sergey","year":"2016","unstructured":"Sergey Polyakovskiy, Rudolf Berghammer, and Frank Neumann. 2016. Solving hard control problems in voting systems via integer programming. Eur. J. Oper. Res. 250, 1 (2016), 204\u2013213.","journal-title":"Eur. J. Oper. Res."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Shini Renjith A. Sreekumar and M. Jathavedan. 2018. Evaluation of partitioning clustering algorithms for processing social media data in tourism domain. In 2018 IEEE Recent Advances in Intelligent Computational Systems (RAICS\u201918). IEEE 127\u2013131.","DOI":"10.1109\/RAICS.2018.8635080"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2932194.2932202"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.3186"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/3006652.3006902"}],"container-title":["ACM\/IMS Transactions on Data Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3458472","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3458472","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T13:56:30Z","timestamp":1776347790000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3458472"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,8,31]]}},"alternative-id":["10.1145\/3458472"],"URL":"https:\/\/doi.org\/10.1145\/3458472","relation":{},"ISSN":["2691-1922"],"issn-type":[{"value":"2691-1922","type":"print"}],"subject":[],"published":{"date-parts":[[2021,7,21]]},"assertion":[{"value":"2020-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-21","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}