Research map / Learning theory and algorithms / Submodular and game algorithms
Multi-Winner Reconfiguration
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.
Introduces a multi-winner reconfiguration model where committees move via small swaps while keeping score within a bound, and gives complexity results for CC, PAV, AV, and SAV (PSPACE-complete for CC/PAV, polynomial for AV/SAV, plus multivariate analysis).
Problem
Transitioning between two size-k committees through a sequence of intermediate committees that are close to each other and nearly as good as the initial committee, under approval-based multi-winner voting rules.
Approach
Define reconfiguration paths for committees with bounded symmetric-difference steps (delta_c) and bounded score loss (delta_s) relative to the initial committee, then analyze complexity across CC, PAV, AV, SAV, using reconfiguration graphs and parameterized reductions from independent set and dominating set reconfiguration.
Key results
- CC-MR and PAV-MR are PSPACE-complete, even with each voter approving at most two alternatives (b=2).
- AV-MR and SAV-MR always admit a reconfiguration path, and a shortest one is computable in polynomial time with length ceil(|W \ W'|/delta_c).
- CC-MR is FPT wrt. n, and PAV-MR is FPT wrt. n + ell; CC-MR is W[2]-hard wrt. k + ell and PAV-MR is W[1]-hard wrt. k + ell.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use CC rather than an additive approval rule | Multi-winner reconfiguration · CC-MR | computational complexity | Hurt |
| use PAV rather than an additive approval rule | Multi-winner reconfiguration · PAV-MR | computational complexity | Hurt |
| use AV rather than CC or PAV | Multi-winner reconfiguration · AV-MR | computational complexity | Helped |
| use SAV rather than CC or PAV | Multi-winner reconfiguration · SAV-MR | computational complexity | Helped |
| parameterize CC-MR by the number of alternatives m | CC-MR · CC-MR | parameterized complexity | Helped |
| parameterize PAV-MR by the number of alternatives m | PAV-MR · PAV-MR | parameterized complexity | Helped |
| parameterize CC-MR by the number of voters n | CC-MR · CC-MR | parameterized complexity | Helped |
| parameterize PAV-MR by voter count n and path length ℓ | PAV-MR · PAV-MR | parameterized complexity | Helped |
| parameterize PAV-MR by voter count n alone | PAV-MR · PAV-MR | parameterized complexity | Mixed |
| parameterize CC-MR by committee size k | CC-MR · CC-MR | parameterized complexity | Hurt |
| parameterize PAV-MR by committee size k | PAV-MR · PAV-MR | parameterized complexity | Hurt |
| bound both maximum ballot size b and path length ℓ | CC-MR and PAV-MR · CC-MR and PAV-MR | computational complexity | Hurt |
Surprising findings
- Bodlaender et al. (2021) claimed W[2]-hardness of dominating set reconfiguration via token jumping by referring to the token addition/removal model; the authors correct this with a direct reduction.
Limitations
- PAV-MR is open for FPT wrt. number of voters n alone.
- Hardness holds even for b=2, so polynomial-time solvability for constant b is not established.
- Results are for score-based rules; non-score-based rules need different closeness measures.
Experimental setup
Builds on: token jumping reconfiguration IPWSPLT (Yang and Wang 2023) Chamberlin-Courant rule Proportional Approval Voting
Closest papers by meaning
- Reconfiguring Proportional Committees (AAAI 2026 · similarity 0.89)
- Algorithms for Structured Elections Under Thiele Voting Rules (AAAI 2026 · similarity 0.89)
- Single-Peakedness and Total Unimodularity: New Polynomial-Time Algorithms for Multi-Winner Elections (AAAI 2018 · similarity 0.87)
- Maintaining Proportional Committees with Dynamic Candidate Sets (ICML 2025 · similarity 0.86)
- Refined Characterizations of Approval-Based Committee Scoring Rules (AAAI 2024 · similarity 0.86)
- Participation Incentives in Approval-Based Committee Elections (AAAI 2024 · similarity 0.85)
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.