research-article

Sample Complexity for Winner Prediction in Elections

Authors:

Arnab BhattacharyyaAuthors Info & Claims

AAMAS '15: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems

Pages 1421 - 1430

Published: 04 May 2015 Publication History

Abstract

Predicting 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 algorithm used for winner prediction is to run the election on a small sample of randomly chosen votes and output the winner as the prediction. We analyze the performance of this algorithm for many common voting rules.

More formally, we introduce the (ε, δ)-winner determination problem, where given an election on n voters and m candidates in which the margin of victory is at least εn votes, the goal is to determine the winner with probability at least 1-δ. The margin of victory of an election is the smallest number of votes that need to be modified in order to change the election winner. We show interesting lower and upper bounds on the number of samples needed to solve the (ε, δ)-winner determination problem for many common voting rules, including scoring rules, approval, maximin, Copeland, Bucklin, plurality with runoff, and single transferable vote. Moreover, the lower and upper bounds match for many common voting rules in a wide range of practically appealing scenarios.

References

[1]

N. Alon, E. Fischer, I. Newman, and A. Shapira. A combinatorial characterization of the testable graph properties: it's all about regularity. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pages 251--260, 2006.

Digital Library

[2]

Y. Bachrach, N. Betzler, and P. Faliszewski. Probabilistic possible winner determination. In International Conference on Artificial Intelligence (AAAI), volume 10, pages 697--702, 2010.

[3]

Z. Bar-Yossef. Sampling lower bounds via information theory. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pages 335--344. ACM, 2003.

Digital Library

[4]

Z. Bar-Yossef, R. Kumar, and D. Sivakumar. Sampling algorithms: lower bounds and applications. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pages 266--275. ACM, 2001.

Digital Library

[5]

J. Bartholdi III, C. A. Tovey, and M. A. Trick. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare (SCW), 6(2):157--165, 1989.

[6]

P. Boldi, F. Bonchi, C. Castillo, and S. Vigna. Voting in social networks. In Proceedings of the 18th ACM Conference on Information and Knowledge Mmanagement, pages 777--786. ACM, 2009.

Digital Library

[7]

C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, B. Szegedy, and K. Vesztergombi. Graph limits and parameter testing. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pages 261--270, 2006.

Digital Library

[8]

C. Boutilier, J. Lang, J. Oren, and H. Palacios. Robust winners and winner determination policies under candidate uncertainty. In Proceedings of the International Conference on Artificial Intelligence (AAAI), 2014.

[9]

R. Canetti, G. Even, and O. Goldreich. Lower bounds for sampling algorithms for estimating the average. Information Processing Letters (IPL), 53(1):17--25, 1995.

Digital Library

[10]

V. Conitzer. Eliciting single-peaked preferences using comparison queries. Journal of Artificial Intelligence Research (JAIR), 35:161--191, 2009.

Digital Library

[11]

V. Conitzer and T. Sandholm. Vote elicitation: Complexity and strategy-proofness. In Eighteenth International Conference on Artificial Intelligence (AAAI), pages 392--397, Menlo Park, CA, USA, 2002. American Association for Artificial Intelligence.

Digital Library

[12]

S. Dhamal and Y. Narahari. Scalable preference aggregation in social networks. In First AAAI Conference on Human Computation and Crowdsourcing (HCOMP), 2013.

[13]

N. Ding and F. Lin. Voting with partial information: Minimal sets of questions to decide an outcome. In Proc. Fourth International Workshop on Computational Social Choice (COMSOC-2012), Kraków, Poland, 2012.

[14]

J. A. Doucette, K. Larson, and R. Cohen. Approximate winner selection in social choice with partial preferences. In Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). International Foundation for Autonomous Agents and Multiagent Systems, 2014.

[15]

A. Dvoretzky, J. Kiefer, and J. Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pages 642--669, 1956.

[16]

E. Ephrati and J. Rosenschein. The Clarke tax as a consensus mechanism among automated agents. In Proceedings of the Ninth International Conference on Artificial Intelligence (AAAI), pages 173--178, 1991.

Digital Library

[17]

D. Falik, R. Meir, and M. Tennenholtz. On coalitions and stable winners in plurality. In 8th International Workshop on Internet and Network Economics (WINE), pages 256--269. Springer, 2012.

Digital Library

[18]

N. Hazon, Y. Aumann, S. Kraus, and M. Wooldridge. Evaluation of election outcomes under uncertainty. In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 959--966. International Foundation for Autonomous Agents and Multiagent Systems, 2008.

Digital Library

[19]

E. Hemaspaandra, L. A. Hemaspaandra, and J. Rothe. Exact analysis of dodgson elections: Lewis carroll's 1876 voting system is complete for parallel access to np. Journal of the ACM (JACM), 44(6):806--825, 1997.

Digital Library

[20]

E. Hemaspaandra, H. Spakowski, and J. Vogel. The complexity of kemeny elections. Theoretical Computer Science (TCS), 349(3):382--391, 2005.

Digital Library

[21]

S. Kullback and R. A. Leibler. On information and sufficiency. The Annals of Mathematical Statistics, pages 79--86, 1951.

[22]

J. Lin. Divergence measures based on the shannon entropy. IEEE Transactions on Information Theory, 37(1):145--151, 1991.

Digital Library

[23]

T. Lu and C. Boutilier. Robust approximation and incremental elicitation in voting protocols. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), volume 22, page 287, 2011.

Digital Library

[24]

T. Lu and C. Boutilier. Vote elicitation with probabilistic preference models: Empirical estimation and cost tradeoffs. In Algorithmic Decision Theory, pages 135--149. Springer, 2011.

Digital Library

[25]

T. Lu and C. Boutilier. Multi-winner social choice with incomplete preferences. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI), pages 263--270. AAAI Press, 2013.

Digital Library

[26]

J. Oren, Y. Filmus, and C. Boutilier. Efficient vote elicitation under candidate uncertainty. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI), pages 309--316. AAAI Press, 2013.

Digital Library

[27]

D. M. Pennock, E. Horvitz, and C. L. Giles. Social choice theory and recommender systems: Analysis of the axiomatic foundations of collaborative filtering. In Proceedings of the 17th International Conference on Artificial Intelligence (AAAI), 2000.

Digital Library

[28]

M. A. Rodriguez, D. J. Steinbock, J. H. Watkins, C. Gershenson, J. Bollen, V. Grey, and B. Degraf. Smartocracy: Social networks for collective decision making. In In 40th Annual Hawaii International Conference on Systems Science (HICSS'07). Waikoloa, pages 90--90. IEEE, 2007.

Digital Library

[29]

D. Ron. Property testing. Combinatorial Optimization-Dordrecht, 9(2):597--643, 2001.

[30]

D. Shiryaev, L. Yu, and E. Elkind. On elections with robust winners. In Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 415--422. International Foundation for Autonomous Agents and Multiagent Systems, 2013.

Digital Library

[31]

B. Waggoner. Lp testing and learning of discrete distributions. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS '15, pages 347--356, New York, NY, USA, 2015. ACM.

Digital Library

[32]

L. Xia. Computing the margin of victory for various voting rules. In Proceedings of the 13th ACM Conference on Electronic Commerce (EC), pages 982--999. ACM, 2012.

Digital Library

Cited By

Dey PNath SShakya GElkind EVeloso MAgmon NTaylor M(2019)Testing Preferential Domains Using SamplingProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3306127.3331777(855-863)Online publication date: 8-May-2019
https://dl.acm.org/doi/10.5555/3306127.3331777
Dey PKothari PNath SDey LChaudhury SKrishnapuram RSingla PRoy R(2019)The Social Network Effect on Surprise in ElectionsProceedings of the ACM India Joint International Conference on Data Science and Management of Data10.1145/3297001.3297002(1-9)Online publication date: 3-Jan-2019
https://dl.acm.org/doi/10.1145/3297001.3297002
Bhattacharyya ADey PWoodruff D(2018)An Optimal Algorithm for ℓ1-Heavy Hitters in Insertion Streams and Related ProblemsACM Transactions on Algorithms10.1145/326442715:1(1-27)Online publication date: 22-Oct-2018
https://dl.acm.org/doi/10.1145/3264427
Show More Cited By

Index Terms

Sample Complexity for Winner Prediction in Elections
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
      1. Multi-agent systems
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Sampling-Based Winner Prediction in District-Based Elections
AAMAS '23: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems

In a district-based election, we apply a voting rule r to decide the winners in each district, and a candidate who wins in a maximum number of districts is the winner of the election. We present efficient sampling-based algorithms to predict the winner ...
Winner Determination and Manipulation in Minisum and Minimax Committee Elections
ADT 2015: Proceedings of the 4th International Conference on Algorithmic Decision Theory - Volume 9346

In a committee election, a set of candidates has to be determined as winner of the election. Baumeister and Dennisenï ź[2] proposed to extend the minisum and minimax approach, initially defined for approval votes, to other forms of votes. They define ...
Complexity of Shift Bribery in Iterative Elections
AAMAS '18: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems

In iterative voting systems, candidates are eliminated in consecutive rounds until either a fixed number of rounds is reached or the set of remaining candidates does not change anymore. We focus on iterative voting systems based on the positional ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

AAMAS '15: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems

May 2015

2072 pages

ISBN:9781450334136

General Chairs:
Gerhard Weiss
Maastricht University, The Netherlands
,
Pınar Yolum
Bogazici University, Turkey
,
Program Chairs:
Rafael H. Bordini
PUCRS, Brazil
,
Edith Elkind
University of Oxford, UK

Sponsors

IFAAMAS

In-Cooperation

SIGAI: ACM Special Interest Group on Artificial Intelligence

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 04 May 2015

Check for updates

Author Tags

Qualifiers

Research-article

Conference

AAMAS'15

Sponsor:

AAMAS'15: International Conference on Autonomous Agents and Multiagent Systems

May 4 - 8, 2015

Istanbul, Turkey

Acceptance Rates

AAMAS '15 Paper Acceptance Rate 108 of 670 submissions, 16%;

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
118
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dey PNath SShakya GElkind EVeloso MAgmon NTaylor M(2019)Testing Preferential Domains Using SamplingProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3306127.3331777(855-863)Online publication date: 8-May-2019
https://dl.acm.org/doi/10.5555/3306127.3331777
Dey PKothari PNath SDey LChaudhury SKrishnapuram RSingla PRoy R(2019)The Social Network Effect on Surprise in ElectionsProceedings of the ACM India Joint International Conference on Data Science and Management of Data10.1145/3297001.3297002(1-9)Online publication date: 3-Jan-2019
https://dl.acm.org/doi/10.1145/3297001.3297002
Bhattacharyya ADey PWoodruff D(2018)An Optimal Algorithm for ℓ1-Heavy Hitters in Insertion Streams and Related ProblemsACM Transactions on Algorithms10.1145/326442715:1(1-27)Online publication date: 22-Oct-2018
https://dl.acm.org/doi/10.1145/3264427
Dey P(2018)Manipulative elicitation A new attack on elections with incomplete preferencesTheoretical Computer Science10.1016/j.tcs.2018.03.028731:C(36-49)Online publication date: 30-Jun-2018
https://dl.acm.org/doi/10.1016/j.tcs.2018.03.028
Caragiannis IMicha E(2017)Learning a ground truth ranking using noisy approval votesProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171642.3171665(149-155)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171642.3171665
Filtser ATalmon NLarson KWinikoff MDas SDurfee E(2017)Distributed Monitoring of Election WinnersProceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems10.5555/3091125.3091287(1160-1168)Online publication date: 8-May-2017
https://dl.acm.org/doi/10.5555/3091125.3091287
Dey PTalmon Nvan Handel OLarson KWinikoff MDas SDurfee E(2017)Proportional Representation in Vote StreamsProceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems10.5555/3091125.3091134(15-23)Online publication date: 8-May-2017
https://dl.acm.org/doi/10.5555/3091125.3091134
Bhattacharyya ADey PWoodruff DMilo TTan W(2016)An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related ProblemsProceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/2902251.2902284(385-400)Online publication date: 15-Jun-2016
https://dl.acm.org/doi/10.1145/2902251.2902284
Dey PNarahari Y(2015)Estimating the margin of victory of an election using samplingProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832249.2832404(1120-1126)Online publication date: 25-Jul-2015
https://dl.acm.org/doi/10.5555/2832249.2832404
Dey PWeiss GYolum PBordini RElkind E(2015)Computational Complexity of Fundamental Problems in Social Choice TheoryProceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems10.5555/2772879.2773532(1973-1974)Online publication date: 4-May-2015
https://dl.acm.org/doi/10.5555/2772879.2773532

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents