Pareto-efficiency of ordinal multiwinner voting rules

Abstract

We investigate the Pareto-efficiency of ordinal multiwinner voting rules, that is, voting rules based on ordinal preference profiles over candidates. Defining Pareto-optimality of a committee requires relating the voters' rankings over individual candidates to their preferences over committees. We consider two well-known extension principles that extend rankings over candidates to preferences over committees: the responsive extension and the lexicographic extension. As the responsive extension outputs partial orders, we consider two Pareto-optimality notions: a committee is possibly (respectively, necessary) Pareto-optimal if it is Pareto-optimal for some (respectively, every) completion of these partial orders. As the lexicographic extension principle outputs a total order, it leads to only one Pareto-optimality notion. We then define several notions of Pareto-efficiency of multiwinner rules, depending on whether some (respectively, all) committees in the output are Pareto-optimal for one of the latter notions. We review what we believe to be a complete list of ordinal multiwinner rules that have been studied in the literature, and identify which Pareto-efficiency notions they satisfy. Our finding is that, somewhat surprisingly, these rules show a huge diversity: some satisfy the strongest notion, some do not even satisfy the weakest one, with many other rules at various intermediate levels.