Proceedings of the AAAI Conference on Artificial Intelligence · 2019 · 10 citations · 22 references
Natural SciencesPolitical ScienceAlgorithmsDecision TheoryProbability TheoryElectionsStatistical InferenceVoting RulesApproximation GuaranteesPartial OrderingPolynomial-time AlgorithmsPolynomial-time Approximation SchemeProbabilistic Approximation AlgorithmsProbabilistic Voting ModelsScoring Rules
We study the complexity of estimating the probability of an outcome in an election over probabilistic votes. The focus is on voting rules expressed as positional scoring rules, and two models of probabilistic voters: the uniform distribution over the completions of a partial voting profile (consisting of a partial ordering of the candidates by each voter), and the Repeated Insertion Model (RIM) over the candidates, including the special case of the Mallows distribution. Past research has established that, while exact inference of the probability of winning is computationally hard (#P-hard), an additive polynomial-time approximation (additive FPRAS) is attained by sampling and averaging. There is often, though, a need for multiplicative approximation guarantees that are crucial for important measures such as conditional probabilities. Unfortunately, a multiplicative approximation of the probability of winning cannot be efficient (under conventional complexity assumptions) since it is already NP-complete to determine whether this probability is nonzero. Contrastingly, we devise multiplicative polynomial-time approximations (multiplicative FPRAS) for the probability of the complement event, namely, losing the election.
22
A New Measure of Rank Correlation
M. G. Kendall · Biometrika · 1938 · 2.3K citations
The Theory of Committees and Elections.
Anwesha Roy, D. Black · The Economic Journal · 1959 · 743 citations