Haoyue Ping
Skip Abstract Section
Skip Supplemental Material SectionAbstract
It remains an open question how to determine the winner of an election when voter preferences are incomplete or uncertain. One option is to assume some probability space over the voting profile and select the Most Probable Winner (MPW) -- the candidate or candidates with the best chance of winning. In this paper, we propose an alternative winner interpretation, selecting the Most Expected Winner (MEW) according to the expected performance of the candidates.
We separate the uncertainty in voter preferences into the generation step and the observation step, which gives rise to a unified voting profile combining both incomplete and probabilistic voting profiles. We use this framework to establish the theoretical hardness of MEW over incomplete voter preferences, and then identify a collection of tractable cases for a variety of voting profiles, including those based on the popular Repeated Insertion Model (RIM) and its special case, the Mallows model. We develop solvers customized for various voter preference types to quantify the candidate performance for the individual voters, and propose a pruning strategy that optimizes computation. The performance of the proposed solvers and pruning strategy is evaluated extensively on real and synthetic benchmarks, showing that our methods are practical.
Supplemental Material
Available for Download
pdf
3588702_readme.pdf (21 KB)
Read me
zip
3588702_source_code.zip (3.4 MB)
Source Code
- Yoram Bachrach, Nadja Betzler, and Piotr Faliszewski. 2010. Probabilistic Possible Winner Determination. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11--15, 2010. http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1692Google Scholar
Cross Ref
- Graham R. Brightwell and Peter Winkler. 1991. Counting Linear Extensions is #P-Complete. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5--8, 1991, New Orleans, Louisiana, USA. 175--181. https://doi.org/10.1145/103418.103441Google ScholarDigital Library
- Rainer Bruggemann and Paola Annoni. 2014. Average heights in partially ordered sets. MATCH Commun Math Comput Chem, Vol. 71 (2014), 117--142.Google Scholar
- Vishal Chakraborty, Theo Delemazure, Benny Kimelfeld, Phokion G. Kolaitis, Kunal Relia, and Julia Stoyanovich. 2021. Algorithmic Techniques for Necessary and Possible Winners. Trans. Data Sci., Vol. 2, 3 (2021), 22:1--22:23. https://doi.org/10.1145/3458472Google ScholarDigital Library
- Karel De Loof, Bernard De Baets, and Hans De Meyer. 2011. Approximation of average ranks in posets. Match Commun Math Comput Chem, Vol. 66 (2011), 219--229.Google Scholar
- Jean-Paul Doignon, Aleksandar Pekevc, and Michel Regenwetter. 2004. The repeated insertion model for rankings: Missing link between two subset choice models. Psychometrika, Vol. 69, 1 (2004), 33--54.Google ScholarCross Ref
- Judy Goldsmith, Jé rô me Lang, Nicholas Mattei, and Patrice Perny. 2014. Voting with Rank Dependent Scoring Rules. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27 -31, 2014, Qué bec City, Qué bec, Canada, Carla E. Brodley and Peter Stone (Eds.). AAAI Press, 698--704. http://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8549Google Scholar
- Noam Hazon, Yonatan Aumann, Sarit Kraus, and Michael J. Wooldridge. 2012. On the evaluation of election outcomes under uncertainty. Artif. Intell., Vol. 189 (2012), 1--18. https://doi.org/10.1016/j.artint.2012.04.009Google ScholarDigital Library
- Aviram Imber and Benny Kimelfeld. 2021. Probabilistic Inference of Winners in Elections by Independent Random Voters. In AAMAS '21: 20th International Conference on Autonomous Agents and Multiagent Systems, Virtual Event, United Kingdom, May 3--7, 2021, Frank Dignum, Alessio Lomuscio, Ulle Endriss, and Ann Nowé (Eds.). ACM, 647--655. https://dl.acm.org/doi/10.5555/3463952.3464031Google ScholarDigital Library
- Marie Jacob, Benny Kimelfeld, and Julia Stoyanovich. 2014. A System for Management and Analysis of Preference Data. Proc. VLDB Endow., Vol. 7, 12 (2014), 1255--1258. https://doi.org/10.14778/2732977.2732998Google ScholarDigital Library
- Richard M. Karp, Michael Luby, and Neal Madras. 1989. Monte-Carlo Approximation Algorithms for Enumeration Problems. J. Algorithms, Vol. 10, 3 (1989), 429--448. https://doi.org/10.1016/0196--6774(89)90038--2Google ScholarDigital Library
- Batya Kenig, Lovro Ilijasic, Haoyue Ping, Benny Kimelfeld, and Julia Stoyanovich. 2018. Probabilistic Inference Over Repeated Insertion Models. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), New Orleans, Louisiana, USA, February 2--7, 2018. 1897--1904. https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/16252Google ScholarCross Ref
- Batya Kenig and Benny Kimelfeld. 2019. Approximate Inference of Outcomes in Probabilistic Elections. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019. AAAI Press, 2061--2068. https://doi.org/10.1609/aaai.v33i01.33012061Google ScholarDigital Library
- Batya Kenig, Benny Kimelfeld, Haoyue Ping, and Julia Stoyanovich. 2017. Querying Probabilistic Preferences in Databases. In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14--19, 2017, Emanuel Sallinger, Jan Van den Bussche, and Floris Geerts (Eds.). ACM, 21--36. https://doi.org/10.1145/3034786.3056111Google ScholarDigital Library
- Kathrin Konczak and Jérôme Lang. 2005. Voting procedures with incomplete preferences. In Proc. IJCAI-05 Multidisciplinary Workshop on Advances in Preference Handling, Vol. 20.Google Scholar
- Dorte Lerche and Peter B Sørensen. 2003. Evaluation of the ranking probabilities for partial orders based on random linear extensions. Chemosphere, Vol. 53, 8 (2003), 981--992.Google ScholarCross Ref
- Karel De Loof. 2009. Efficient computation of rank probabilities in posets. Ph.,D. Dissertation. Ghent University.Google Scholar
- Tyler Lu and Craig Boutilier. 2011. Robust Approximation and Incremental Elicitation in Voting Protocols. In IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16--22, 2011. 287--293. https://doi.org/10.5591/978--1--57735--516--8/IJCAI11-058Google ScholarCross Ref
- R.D. Luce. 1959. Individual Choice Behavior: A Theoretical Analysis. Wiley. 59009346 https://books.google.com/books?id=a80DAQAAIAAJGoogle Scholar
- C. L. Mallows. 1957. Non-Null Ranking Models. Biometrika, Vol. 44 (1957), 114--130.Google ScholarCross Ref
- John I Marden. 1995. Analyzing and modeling rank data. CRC Press.Google Scholar
- Frederick Mosteller. 1951. Remarks on the method of paired comparisons: I. The least squares solution assuming equal standard deviations and equal correlations. Psychometrika, Vol. 16, 1 (March 1951), 3--9. https://doi.org/10.1007/BF02313422Google ScholarCross Ref
- Ritesh Noothigattu, Snehalkumar (Neil) S. Gaikwad, Edmond Awad, Sohan Dsouza, Iyad Rahwan, Pradeep Ravikumar, and Ariel D. Procaccia. 2018. A Voting-Based System for Ethical Decision Making. In Proceedings of AAAI, New Orleans, Louisiana, USA. 1587--1594. https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/17052Google Scholar
- Haoyue Ping and Julia Stoyanovich. 2021. Most Expected Winner: An Interpretation of Winners over Uncertain Voter Preferences. CoRR, Vol. abs/2105.00082 (2021). showeprint[arXiv]2105.00082 https://arxiv.org/abs/2105.00082Google Scholar
- Haoyue Ping, Julia Stoyanovich, and Benny Kimelfeld. 2020. Supporting Hard Queries over Probabilistic Preferences. Proc. VLDB Endow., Vol. 13, 7 (2020), 1134--1146. https://doi.org/10.14778/3384345.3384359Google ScholarDigital Library
- Robin L Plackett. 1975. The analysis of permutations. Journal of the Royal Statistical Society: Series C (Applied Statistics), Vol. 24, 2 (1975), 193--202.Google ScholarCross Ref
- Geoffrey Pritchard and Mark C. Wilson. 2007. Exact results on manipulability of positional voting rules. Soc. Choice Welf., Vol. 29, 3 (2007), 487--513. https://doi.org/10.1007/s00355-007-0216--5Google ScholarCross Ref
- 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). 127--131. https://doi.org/10.1109/RAICS.2018.8635080Google ScholarCross Ref
- Roman Seidl. 2018. Handbook of Computational Social Choice by Brandt Felix, Vincent Conitzer, Ulle Endriss, Jerome Lang, Ariel Procaccia. J. Artif. Soc. Soc. Simul., Vol. 21, 2 (2018). http://jasss.soc.surrey.ac.uk/21/2/reviews/4.htmlGoogle Scholar
- Julia Stoyanovich, Marie Jacob, and Xuemei Gong. 2015. Analyzing Crowd Rankings. In Proceedings of the 18th International Workshop on Web and Databases, Melbourne, VIC, Australia, May 31, 2015, Julia Stoyanovich and Fabian M. Suchanek (Eds.). ACM, 41--47. https://doi.org/10.1145/2767109.2767110Google ScholarDigital Library
- L. L. Thurstone. 1927. A Law of Comparative Judgment. Psychological Review, Vol. 34, 4 (1927), 273--286. https://doi.org/10.1037/h0070288Google ScholarCross Ref
- Zhibing Zhao, Haoming Li, Junming Wang, Jeffrey O. Kephart, Nicholas Mattei, Hui Su, and Lirong Xia. 2018. A Cost-Effective Framework for Preference Elicitation and Aggregation. In Proceedings of UAI, Monterey, California, USA. 446--456. http://auai.org/uai2018/proceedings/papers/179.pdfGoogle Scholar
Index Terms
- Most Expected Winner: An Interpretation of Winners over Uncertain Voter Preferences
Recommendations
The possible winner with uncertain weights problem
AbstractThe original possible winner problem consists of an unweighted election with partial preferences and a distinguished candidate c and asks whether the preferences can be extended to total ones such that c wins the given election. We ...
Computational complexity of two variants of the possible winner problem
AAMAS '11: The 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 2A possible winner of an election is a candidate that has, in some kind of incomplete-information election, the possibility to win in a complete extension of the election. The first type of problem we study is the Possible co-Winner with respect to the ...
Sample Complexity for Winner Prediction in Elections
AAMAS '15: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent SystemsPredicting the winner of an election is a favorite problem both for news media pundits and computational social choice theorists. Since it is often infeasible to elicit the preferences of all the voters in a typical prediction scenario, a common ...
Comments