Recent years have seen an increase in democratic innovations [Smith 2009 ] aimed at increasing the participation of the public in policy-making. This observation, coupled with the increasing prevalence of internet-based communication, points to a very real possibility of implementing participatory democracies on a mass-scale in which every individual is invited to contribute their ideas and opinions [Salganik and Levy 2012] . One important question in implementing crowdsourcing experiments of this type is the aggregation problem: given a large number of ideas, how can one identify the top ideas without requiring any individual, whether an appointed government expert or a participant, to spend too much time or effort in the evaluation process? A natural approach to aggregation in the democratic setting is to use voting rules, also known as social choice functions [Brandt et al. 2012] , to find the top ideas. In this paper, we present theoretical and empirical results indicating the usefulness of voting rules for participatory democracies. We first give algorithms which efficiently elicit -approximations to two prominent voting rules: the Borda rule and the Condorcet winner. This result circumvents previous prohibitive lower bounds [Conitzer and Sandholm 2005] [Service and Adams 2012] and is surprisingly strong: even if the number of ideas is as large as the number of participants, each participant will only have to make a logarithmic number of comparisons, an exponential improvement over the linear number of comparisons previously needed. Essentially, we show that these voting rules, which scale inefficiently, can be easy to implement when the winner wins by a margin or an approximation suffices. We demonstrate the approach in an experiment in Finland's recent off-road traffic law reform [Aitamurto and Landemore 2013] . The Finnish experiment, as we will refer to it from this point on, engaged the Finnish people in 1) identifying problems, 2) proposing solutions, and 3) evaluating ideas for the offroad traffic law. In the evaluation stage, 308 participants took part in ranking ideas in 41 different topics, each of which had a number of ideas ranging from 2 to 15. For = 0.05 and 0.1, we show that the total number of comparisons needed for all participants is linear in the number of ideas and that the constant is not large. As an example, when the derived linear trend is extrapolated to the case of aggregating 100 ideas with 1000 participants, an error of 0.05 only requires each participant to make 19 comparisons. If we only need an error of 0.1, then 8 comparisons suffice. Finally, we note a few other experimental observations which support the use of voting rules for aggregation. First, we observe that rating, one of the common alternatives to ranking, manifested effects of bias in our data. Second, we show that very few of the topics lacked a Condorcet winner, one of the prominent negative results in voting. Finally, we show data hinting at a potential future direction: the use of partial rankings as opposed to pairwise comparisons to further decrease the elicitation time.
REF develop an algorithm that can approximate the Borda rule, given a number of comparisons by each voter that is logarithmic in the number of candidates.
Crowdsourcing for Participatory Democracies: Efficient Elicitation of Social Choice Functions
HCOMP
Computer Science