Evaluation of election outcomes under uncertainty

ABSTRACT

We investigate the extent to which it is possible to evaluate the probability of a particular candidate winning an election, given imperfect information about the preferences of the electorate. We assume that for each voter, we have a probability distribution over a set of preference orderings. Thus, for each voter, we have a number of possible preference orderings -- we do not know which of these orderings actually represents the voters' preferences, but we know for each one the probability that it does. We give a polynomial algorithm to solve the problem of computing the probability that a given candidate will win when the number of candidates is a constant. However, when the number of candidates is not bounded, we prove that the problem becomes #P-Hard for the Plurality, Borda, and Copeland voting protocols. We further show that even evaluating if a candidate has any chance to win is NP-Complete for the Plurality voting protocol, in the weighted voters case. We give a polynomial algorithm for this problem when the voters' weights are equal.

REFERENCES

• 1: K. J. Arrow, A. K. Sen, and K. Suzumura, editors. Handbook of Social Choice and Welfare Volume 1. Elsevier Science Publishers B.V.: Amsterdam, The Netherlands, 2002.
• 2: J. J. Bartholdi and J. Orlin. Single transferable vote resists strategic voting. Social Choice and Welfare, 8:341--354, 1991.
• 3: J. J. Bartholdi, C. A. Tovey, and M. A. Trick. The computational difficulty of manipulating an election. Social Choice and Welfare, 6:227--241, 1989.
• 4: J. J. Bartholdi, 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, 6:157--165, 1989.
• 5: Vincent Conitzer , Tuomas Sandholm, Complexity of manipulating elections with few candidates, Eighteenth national conference on Artificial intelligence, p.314-319, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 6: V. Conitzer and T. Sandholm. Universal voting protocol tweaks to make manipulation hard. Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-03), 2003.
• 7: Vincent Conitzer , Tuomas Sandholm , Jérôme Lang, When are elections with few candidates hard to manipulate?, Journal of the ACM (JACM), v.54 n.3, p.14-es, June 2007 [doi>10.1145/1236457.1236461]
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: D. B. West, editor. Introduction to Graph Theory. Prentice Hall, 2 edition, 2001.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

General Terms:
Algorithms, Economics, Theory

Keywords:
computational social choice, voting protocols