Axiomatic characterization of committee scoring rules

Piotr Skowron, Piotr Faliszewski, Arkadii Slinko

TL;DR

This paper provides a foundational axiomatic characterization for "committee scoring rules," a class of voting systems designed to select multiple winners (committees) rather than a single one. The authors demonstrate that these rules, despite their generality, can be precisely defined by a set of four standard axioms (anonymity, neutrality, consistency, continuity) plus a new axiom called "committee dominance," which is specific to multiwinner settings. This work offers a theoretical framework for understanding and designing multiwinner voting systems.

What Problem Does This Paper Address?

In social choice theory, a significant amount of research has focused on single-winner voting rules, leading to well-established axiomatic characterizations (like those for Borda or Plurality rules). However, the field of multiwinner voting, where the goal is to select a committee of a certain size (e.g., a parliament, a shortlist of candidates), has been less explored from an axiomatic perspective. This paper aims to bridge this gap by providing a comprehensive axiomatic characterization for "committee scoring rules," a broad and important class of multiwinner voting systems. The challenge lies in extending the principles and techniques used for single-winner rules to the more complex scenario of selecting multiple candidates simultaneously, where interdependencies between committee members can arise.

Methods

The core of this paper is the development of an axiomatic characterization for committee scoring rules. The authors introduce and define several key concepts:

  • k-Decision Rules: A generalization of voting rules that map voter preferences to pairwise comparisons of committees, without necessarily requiring transitivity.
  • Decision Scoring Rules: A specific type of k-decision rule that assigns scores to pairs of committees based on a decision scoring function. This class is shown to generalize the notion of a majority relation.
  • Committee Scoring Rules: The main focus, defined as multiwinner voting rules that are based on committee scoring functions. These functions assign scores to committees based on the positions of their members in individual ballots.

The axiomatic characterization is achieved by identifying a set of axioms that uniquely define committee scoring rules. These include:

  • Anonymity: All voters are treated equally.
  • Neutrality: All candidates are treated equally.
  • Consistency: If two groups of voters agree on the relative ranking of two committees, then the combined group will also agree.
  • Continuity: A large majority of voters can override a minority's preference.
  • Committee Dominance: A new axiom specific to multiwinner rules, which captures a form of Pareto superiority for committees. If every voter weakly prefers the candidates in committee X to the candidates in committee Y, then the society should weakly prefer X to Y.

The proof involves several technical steps, including domain changes (from preference profiles to voting situations and then to fractional voting situations) and the construction of specific voting situations to test the axioms. A key technical tool developed is the "position-difference function," which helps in analyzing the relationship between committees.

Datasets

Not discussed in the paper. The paper is theoretical and focuses on axiomatic characterizations rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Generalizing Single-Winner Axioms: The paper successfully extends well-known axioms like anonymity, neutrality, and consistency to the multiwinner setting, demonstrating their continued relevance.
  • The Novelty of Committee Dominance: The introduction of "committee dominance" is crucial. It captures the intuition that if every individual voter's preference for one committee over another is unanimous, this should translate to a social preference for that committee. This axiom is essential for distinguishing committee scoring rules from other multiwinner rules.
  • Decision Scoring Rules as a Bridge: The introduction of "decision scoring rules" and their axiomatic characterization (symmetric, consistent, continuous) serves as a crucial intermediate step. This class is broader than committee scoring rules and helps in building the proof for the main result.
  • Axiomatic Foundation for a Broad Class: Committee scoring rules are shown to be a remarkably general class, encompassing many existing multiwinner rules. Providing a unified axiomatic characterization offers a powerful theoretical lens for understanding and comparing these diverse rules.

Key Results

The paper's main result is Theorem A, which states that a multiwinner voting rule is a committee scoring rule if and only if it satisfies anonymity, neutrality, consistency, continuity, and committee dominance.

Additionally, the paper establishes Theorem B, which axiomatically characterizes "decision scoring rules" (a generalization of majority relations) by the axioms of symmetry, consistency, and continuity.

Limitations and Future Work

  • Complexity of Proof: The authors acknowledge that the proof is involved and requires several technical lemmas and domain changes.
  • Computational Complexity: While the paper focuses on axiomatic characterization, it mentions that many committee scoring rules are NP-hard to compute, a point explored in related work.
  • Future Research: The authors suggest that their work on decision scoring rules opens avenues for exploring tournament solution concepts in the context of multiwinner rules. They also believe that the developed tools and concepts could be valuable for further research into multiwinner voting systems.

Summary updated

Abstract

Committee scoring rules form a rich class of aggregators of voters' preferences for the purpose of selecting subsets of candidates of a given size. We provide an axiomatic characterization of committee scoring rules in the spirit of celebrated Young's characterization of single-winner scoring rules. We show that committee scoring rules are characterized by the set of four standard axioms: symmetry, consistency, continuity and Pareto dominance. In the course of our proof, we introduce and axiomatically characterize multiwinner decision scoring rules, a class of rules that generalizes the well-known majority relation.
BibTeX
@article{skowron2019axiomatic,
  author = {Piotr Skowron and Piotr Faliszewski and Arkadii Slinko},
  title = {{Axiomatic characterization of committee scoring rules}},
  journal = {J. Econ. Theory},
  year = {2019},
  doi = {10.1016/j.jet.2018.12.011},
}
Figure