Subset Selection via Implicit Utilitarian Voting

Caragiannis, Ioannis; Nath, Swaprava; Procaccia, Ariel D.; Shah, Nisarg

Subset Selection via Implicit Utilitarian Voting

Ioannis Caragiannis, Swaprava Nath, Ariel D. Procaccia, Nisarg Shah

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 151-156.

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.

Ioannis Caragiannis, Swaprava Nath, Ariel D. Procaccia, and Nisarg Shah. 2016. Subset Selection via Implicit Utilitarian Voting. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 151–156. https://ijcai.org/proceedings/2016/29

@inproceedings{ijcai2016p29,
  title     = {Subset Selection via Implicit Utilitarian Voting},
  author    = {Caragiannis, Ioannis and Nath, Swaprava and Procaccia, Ariel D. and Shah, Nisarg},
  booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-16}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Subbarao Kambhampati},
  pages     = {151--156},
  year      = {2016},
  month     = {7},
  url       = {https://ijcai.org/proceedings/2016/29},
}

TY  - CPAPER
TI  - Subset Selection via Implicit Utilitarian Voting
AU  - Caragiannis, Ioannis
AU  - Nath, Swaprava
AU  - Procaccia, Ariel D.
AU  - Shah, Nisarg
T2  - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2016
SP  - 151
EP  - 156
UR  - https://ijcai.org/proceedings/2016/29
ER  -