We present theoretical and empirical results demonstrating the usefulness of social choice functions incrowdsourcing for participatory democracies. First, we demonstrate the scalability of social choice functions by defining a natural notion of -approximation, and giving algorithms which efficiently elicit such approximations for two prominent social choice functions: the Borda rule and the Condorcet winner. This result circumvents previous prohibitive lower bounds 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. Second, we apply these ideas to Finland's recent off-road traffic law reform, an experimenton participatory democracy in real life. This allows us to verify the scaling predicted in our theoryand show that the constant involved is also not large. In addition, by collecting data on the time that users take to complete rankings of varying sizes, we observe that eliciting partial rankings can further decrease elicitation time as compared to the common method of eliciting pairwise comparisons.
- Published by
- Proceedings of the Second AAAI Conference on Human Computation and Crowdsourcing (HCOMP 2014)
- Document type
- Copyright: 2014, Association for the Advancement of Artificial Intelligence