  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.
