Subset Selection via Implicit Utilitarian Voting

I. Caragiannis, S. Nath, A. Procaccia, N. Shah
IJCAI 2016
Abstract
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.

Remarks: There is a journal version: Ioannis Caragiannis, Swaprava Nath, Ariel D. Procaccia, Nisarg Shah: Subset Selection Via Implicit Utilitarian Voting. J. Artif. Intell. Res. 58: 123-152 (2017)

Experiments:

Election type Culture Candidates Voters Instances Parameters
Ordinal Impartial Culture {10} {8} 10000 None
Ordinal PrefLib {10} {8} 10000 https://www.preflib.org/dataset/00014
Ordinal PrefLib None None None https://www.preflib.org/dataset/00009
Ordinal PrefLib None None None https://www.preflib.org/dataset/00012
Ordinal PrefLib None None None https://www.preflib.org/dataset/00004
Ordinal PrefLib None None None https://www.preflib.org/dataset/00006
Ordinal PrefLib None None None https://www.preflib.org/dataset/00011
Ordinal Real-Life (beyond PrefLib) {10} {8} 10000 None
Ordinal Unknown [10-50] {15} 10000 None