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