Fishing out Winners from Vote Streams
This addresses the challenge of real-time winner determination in streaming data for social choice applications, though it is incremental as it builds on existing streaming and voting theory.
The paper tackles the problem of determining winners from vote streams in computational social choice, showing that exact winner determination requires storing all votes, and focuses on finding an ε-winner with space-efficient data structures, providing non-trivial upper and lower bounds for various voting rules.
We investigate the problem of winner determination from computational social choice theory in the data stream model. Specifically, we consider the task of summarizing an arbitrarily ordered stream of $n$ votes on $m$ candidates into a small space data structure so as to be able to obtain the winner determined by popular voting rules. As we show, finding the exact winner requires storing essentially all the votes. So, we focus on the problem of finding an {\em $\eps$-winner}, a candidate who could win by a change of at most $\eps$ fraction of the votes. We show non-trivial upper and lower bounds on the space complexity of $\eps$-winner determination for several voting rules, including $k$-approval, $k$-veto, scoring rules, approval, maximin, Bucklin, Copeland, and plurality with run off.