Research map / Learning theory and algorithms / Submodular and game algorithms
The Complexity of Learning Approval-Based Multiwinner Voting Rules
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Learn the scoring function from profile–winning-committee samples using the PAC framework | ABCS rules · Approval-based profiles with m alternatives and committee size k | PAC sample complexity: s(δ,ε) ∈ Ω(ε^{-1}(|𝒳_{m,k}|+ln(1/δ))); s(δ,ε) ∈ 𝒪(ε^{-1}(|𝒳_{m,k}|·k·ln m·ln(1/ε)+ln(1/δ))) | Helped |
| Learn the scoring function from profile–winning-committee samples using the PAC framework | Sequential Thiele rules · Approval-based profiles with committee size k | PAC sample complexity: s(δ,ε) ∈ Ω(ε^{-1}(k+ln(1/δ))); s(δ,ε) ∈ 𝒪(ε^{-1}(k^2·ln m·ln(1/ε)+ln(1/δ))) | Helped |
| Decide whether any non-trivial ABCS rule makes the given committee winning | TargetABCS · Approval-based profile and a specified committee | parameterized complexity | Hurt |
| Decide whether any non-trivial sequential Thiele rule makes the given committee winning | TargetSeqThiele · Approval-based profile and a specified committee | computational complexity | Hurt |
| Check committee-winner membership under a specified sequential Thiele rule | Sequential Thiele rules · Approval-based profile and a specified committee | parameterized complexity | Helped |
Closest papers by meaning
- Algorithms for Structured Elections Under Thiele Voting Rules (AAAI 2026 · similarity 0.91)
- Refined Characterizations of Approval-Based Committee Scoring Rules (AAAI 2024 · similarity 0.90)
- Participation Incentives in Approval-Based Committee Elections (AAAI 2024 · similarity 0.89)
- Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences (NeurIPS 2026 · similarity 0.87)
- Maintaining Proportional Committees with Dynamic Candidate Sets (ICML 2025 · similarity 0.87)
- Multi-Winner Reconfiguration (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.