Winner Determination in Huge Elections with MapReduce

Theresa Csar, Martin Lackner, Reinhard Pichler, Emanuel SallingerAAAI 2017 · DOI

Introduction

Modern digital platforms like Netflix, Amazon, and search engines generate massive volumes of preference data. Every interaction—rating a movie or clicking one search result over another—can be viewed as a "vote." However, traditional computational social choice often assumes a manageable number of voters ($n$) and candidates ($m$). When these numbers reach the millions, standard sequential algorithms become impractical. This paper addresses the "Winner Determination Problem" for large-scale elections using the MapReduce framework, providing parallel algorithms for rules such as Borda, the Schwartz set, the Smith set, and the Copeland set.

The MapReduce Framework for Voting

The authors leverage MapReduce to distribute the computational load across clusters. The process involves a Map phase, where data is filtered and sorted into key-value pairs, followed by a Shuffle phase for grouping, and a Reduce phase for aggregation.

The MapReduce workflow applied to preference aggregation.

For many voting rules, the primary challenge is not just the number of votes, but the number of candidates. If $m$ is large, the $m \times m$ dominance matrix (where entry $(i, j)$ indicates if $i$ is preferred over $j$ by a majority) may exceed the memory of a single machine. MapReduce is essential for constructing and processing this matrix.

Parallelizing Complex Voting Rules

While scoring rules like Borda are "embarrassingly parallel," others require more sophisticated iterative designs.

Iterative Reachability and the Schwartz Set

Determining the Schwartz set involves finding paths in the dominance graph. The authors propose a "path doubling" strategy. In each MapReduce round, the algorithm discovers paths twice as long as those found in the previous round, allowing the process to complete in $O(\log m)$ rounds.

Iterative set updates for path discovery in the dominance graph.

The Smith Set and Copeland Scores

The Smith set calculation is optimized to just three MapReduce rounds by exploiting specific graph properties. Copeland scores, which count pairwise wins, are also highly parallelizable once the dominance matrix is established.

The STV Bottleneck

A key theoretical contribution of the paper is the proof that determining a Single Transferable Vote (STV) winner is P-complete. This classification suggests that STV is "inherently sequential." Because STV requires eliminating candidates one by one based on the evolving state of all ballots, it resists massive parallelization; each round must wait for the previous one to finish.

Experimental Evaluation

The algorithms were tested on the Amazon Elastic MapReduce (EMR) platform using synthetic datasets with up to 7,000 candidates and varying graph densities (sparse vs. dense).

  • Scalability: The Schwartz set algorithm demonstrated excellent horizontal scaling. On a sparse graph with 7,000 candidates, increasing worker nodes from 2 to 32 reduced computation time from over an hour to under 15 minutes.
  • Density Impact: Denser dominance graphs required more processing time, but the scaling trends remained consistent across different configurations.

Conclusion

This work provides a roadmap for implementing democratic processes at scale. While many rules scale beautifully with MapReduce, the P-completeness of STV highlights a fundamental trade-off between certain social choice properties and computational efficiency in the big data era. Future work may explore newer frameworks like Apache Spark or GraphX for even faster iterative graph processing.

Summary updated

BibTeX
@inproceedings{csar2017winner,
  author = {Theresa Csar and Martin Lackner and Reinhard Pichler and Emanuel Sallinger},
  title = {{Winner Determination in Huge Elections with MapReduce}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10606},
}
Figure