Subset Selection via Implicit Utilitarian Voting / 151
Ioannis Caragiannis, Swaprava Nath, Ariel D. Procaccia, Nisarg Shah

How should one aggregate ordinal preferences expressed by voters into a measurably superior social choice? A well-established approach — which we refer to as implicit utilitarian voting — assumes that voters have latent utility functions that induce the reported rankings, and seeks voting rules that approximately maximize utilitarian social welfare. We extend this approach to the design of rules that select a subset of alternatives. We derive analytical bounds on the performance of optimal (deterministic as well as randomized) rules in terms of two measures, distortion and regret. Empirical results show that regret-based rules are more compelling than distortion-based rules, leading us to focus on developing a scalable implementation for the optimal (deterministic) regret-based rule. Our methods underlie the design and implementation of an upcoming social choice website.

PDF