Skip to yearly menu bar Skip to main content


Poster

Multi-Winner Reconfiguration

Jiehua Chen · Christian Hatschka · Sofia Simola

West Ballroom A-D #6801
[ ]
Wed 11 Dec 11 a.m. PST — 2 p.m. PST

Abstract:

We introduce a multi-winner reconfiguration model to examine how to transition between subsets of alternatives (aka. committees) through a sequence of minor yet impactful modifications, called reconfiguration path. We analyze this model under four approval-based voting rules: Chamberlin-Courant (CC), Proportional Approval Voting (PAV), Approval Voting (AV), and Satisfaction Approval Voting (SAV). The problem exhibits computational intractability for CC and PAV, and polynomial solvability for AV and SAV. We provide a detailed multivariate complexity analysis for CC and PAV, demonstrating that although the problem remains challenging in many scenarios, there are specific cases that allow for efficient parameterized algorithms.

Live content is unavailable. Log in and register to view live content