Efficient Algorithms for Electing Successive Committees
This work addresses the practical usability of temporal committee election models for scenarios with constraints, though it is incremental as it builds on prior NP-hardness results.
The paper tackled the NP-hard problem of finding optimal sequences of committees in successive elections under constraints, and developed parameterized algorithms that efficiently solve these hard cases for moderate candidate numbers or limited time horizons.
In a recently introduced model of successive committee elections (Bredereck et al., AAAI-20) for a given set of ordinal or approval preferences one aims to find a sequence of a given length of "best" same-size committees such that each candidate is a member of a limited number of consecutive committees. However, the practical usability of this model remains limited, as the described task turns out to be NP-hard for most selection criteria already for seeking committees of size three. Non-trivial or somewhat efficient algorithms for these cases are lacking too. Motivated by a desire to unlock the full potential of the described temporal model of committee elections, we devise (parameterized) algorithms that effectively solve the mentioned hard cases in realistic scenarios of a moderate number of candidates or of a limited time horizon.