Research map / Learning theory and algorithms / Submodular and game algorithms

Refined Characterizations of Approval-Based Committee Scoring Rules

AAAI 2024 · Learning theory and algorithms › Submodular and game algorithms · approach: Committee voting rules · 3 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives full axiomatic characterizations of Thiele rules and ballot size weighted approval voting (BSWAV) rules for standard approval-based committee choice, using consistency plus other axioms, and derives characterizations of AV, PAV, and SAV.

Problem

Prior characterizations of approval-based committee (ABC) scoring rules hold only for committee ranking rules, and the choice-setting result has an incomplete proof and requires an extra technical axiom excluding AV and SAV. The paper addresses full characterization of ABC scoring rules in the stand

Approach

Characterize two subclasses of ABC scoring rules (Thiele rules and BSWAV rules) in the standard choice model using consistency for variable electorates, adding independence of losers (Thiele) or choice set convexity (BSWAV); then obtain AV, PAV, and SAV characterizations via party-list profile axioms.

Key results

• Thiele rules are exactly the ABC voting rules satisfying anonymity, neutrality, consistency, continuity, and independence of losers.
• BSWAV rules are exactly the ABC voting rules satisfying anonymity, neutrality, consistency, continuity, choice set convexity, and weak efficiency.
• AV is the only Thiele rule satisfying the excellence criterion; PAV is the only Thiele rule satisfying party-proportionality; SAV is the only BSWAV rule satisfying party-proportionality and aversion to unanimous committees.

Surprising findings

• The prior choice-setting characterization of ABC scoring rules has an incomplete proof and relies on an axiom (2-non-imposition) that excludes AV and SAV.
• Every commonly studied ABC scoring rule lies in either the Thiele or BSWAV class, and the two classes intersect only in AV (for k <= m-2) and the trivial rule.

Limitations

• Full characterization of all ABC scoring rules in the standard choice setting remains open.
• Characterizations of AV, PAV, SAV are stated within the Thiele or BSWAV classes and rely on party-list profile axioms.
• Committee size k is fixed; extension to variable k requires additional axioms.

Experimental setup

Baselines: AV PAV SAV CCAV Phragmén's rule

Builds on: Thiele rules ABC scoring rules characterization (ranking setting) consistency axiom from single-winner scoring rule characterization

Closest papers by meaning

• Participation Incentives in Approval-Based Committee Elections (AAAI 2024 · similarity 0.92)
• The Complexity of Learning Approval-Based Multiwinner Voting Rules (AAAI 2022 · similarity 0.90)
• Algorithms for Structured Elections Under Thiele Voting Rules (AAAI 2026 · similarity 0.90)
• Approval-Based Committee Voting under Incomplete Information (AAAI 2022 · similarity 0.89)
• Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences (NeurIPS 2026 · similarity 0.88)
• Multi-Winner Reconfiguration (NeurIPS 2024 · similarity 0.86)