Probabilistic Possible Winner Determination

Yoram Bachrach, Nadja Betzler, Piotr Faliszewski

Introduction

In the field of computational social choice, determining the winner of an election is straightforward when all preferences are known. However, real-world scenarios often involve incomplete data: voters may only provide top-tier rankings, or a subset of ballots may still be in transit. Traditionally, researchers have addressed this uncertainty through two binary lenses: the Possible Winner problem (is there any completion of votes where a candidate wins?) and the Necessary Winner problem (does a candidate win in all completions?).

While these categories provide a baseline, they lack nuance. A candidate who wins in 99% of possible vote completions is categorized the same as one who wins in only 1%—both are merely "possible winners." This paper, originally presented at AAAI-10, introduces a probabilistic framework to bridge this gap, shifting the focus from binary possibility to the quantitative likelihood of victory.

The Counting Problem: #POSSIBLE-WINNER

The authors define the #POSSIBLE-WINNER problem as the task of counting exactly how many ways partial votes can be completed to result in a specific candidate's victory. By assuming that all valid completions (linear extensions of the partial orders) are equally likely—a variation of the "impartial culture" assumption—this count directly translates to a winning probability.

This transition from a decision problem ("Can they win?") to a counting problem ("How often do they win?") significantly increases computational complexity. The paper investigates this complexity across various voting rules, primarily focusing on scoring protocols.

Complexity and Exact Algorithms

The research reveals a stark contrast between the ease of determining if a win is possible and the difficulty of counting those wins.

#P-Hardness Results

One of the paper's most significant findings is that exact counting is computationally intractable (#P-hard) for common rules like Plurality and Veto. Remarkably, this hardness persists even under extremely restrictive conditions. For instance, the authors prove that #POSSIBLE-WINNER remains #P-hard for Plurality even if every voter has ranked all candidates except for a single undetermined pair. This demonstrates that even minimal uncertainty can make exact probabilistic analysis "impossible" for large-scale elections (assuming P ≠ NP).

Tractable Subsets: #MANIPULATION

Despite the general hardness, the authors identify specific scenarios where exact counting is feasible. They focus on the #MANIPULATION problem, a subset of the possible winner problem where a specific group of voters has entirely unspecified preferences. For "$k$-valued" scoring protocols—where only a constant number of positions $k$ receive non-standard point values (e.g., Plurality, Veto, and $k$-approval)—the authors develop a polynomial-time algorithm using dynamic programming.

Randomized Approximation (PWP)

Given the #P-hardness of exact counting, the authors propose a practical alternative: the Probabilistic Winning Probability (PWP) algorithm. This is a Monte Carlo-style sampling approach.

The algorithm relies on the ability to uniformly sample linear extensions of partial orders. By repeatedly sampling completions and checking the winner under the chosen voting rule, the PWP algorithm can estimate a candidate's winning probability. The authors prove that for any voting rule computable in polynomial time, one can estimate the winning probability within an error margin of ε with high confidence (1-δ) in time polynomial to the number of candidates, voters, 1/ε, and ln(1/δ). This result suggests that while exact probabilities are hard to find, highly accurate approximations are remarkably accessible.

Key Insights and Implications

The research provides a more granular tool for election analysis. By ranking candidates by their "winning probability" rather than just their "possibility," the framework offers a more realistic assessment of frontrunners in incomplete elections.

The study also highlights a significant "complexity jump." In many cases, the decision version of the Possible Winner problem is in P (easy), while the counting version is #P-hard. This emphasizes that understanding the distribution of outcomes is fundamentally more difficult than identifying a single outlier outcome.

Limitations and Future Directions

The primary limitation of the current model is the assumption of a uniform distribution over vote completions. In practice, voter preferences are often correlated or influenced by external factors. The authors suggest that future research could incorporate more sophisticated distributions, perhaps by learning from the partial data already available.

Additionally, the complexity of counting for certain rules, such as the Borda count, remained an open question at the time of publication. Further exploration into fixed-parameter tractability—determining if algorithms become efficient when the number of candidates or specific scoring positions are limited—remains a fertile ground for future work in computational social choice.

Summary updated

Abstract

We study the computational complexity of the counting version of the POSSIBLE-WINNER problem for elections. In the POSSIBLE-WINNER problem we are given a profile of voters, each with a partial preference order, and ask if there are linear extensions of the votes such that a designated candidate wins. We also analyze a special case of POSSIBLE-WINNER, the MANIPULATION problem. We provide polynomial-time algorithms for counting manipulations in a class of scoring protocols and in several other voting rules. We show #P-hardness of the counting variant of POSSIBLE-WINNER for plurality and veto and give a simple yet general and practically useful randomized algorithm for a variant of POSSIBLE-WINNER for all voting rules for which a winner can be computed in polynomial time.
BibTeX
@inproceedings{bachrach2010probabilistic,
  author = {Yoram Bachrach and Nadja Betzler and Piotr Faliszewski},
  title = {{Probabilistic Possible Winner Determination}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7609},
}
Figure