Core-Stable Committees under Restricted Domains
This addresses fairness and stability issues in collective decision-making for applications like political elections and participatory budgeting, though it is incremental as it builds on existing core concepts in restricted domains.
The paper tackles the problem of ensuring proportional and stable committee elections by proving that the core is non-empty and computable in polynomial time for several restricted preference domains, such as single-peaked and single-crossing preferences, while also identifying cases where it fails and proposing a relaxation to guarantee non-emptiness.
We study the setting of committee elections, where a group of individuals needs to collectively select a given size subset of available objects. This model is relevant for a number of real-life scenarios including political elections, participatory budgeting, and facility-location. We focus on the core -- the classic notion of proportionality, stability and fairness. We show that for a number of restricted domains including voter-interval, candidate-interval, single-peaked, and single-crossing preferences the core is non-empty and can be found in polynomial time. We show that the core might be empty for strict top-monotonic preferences, yet we introduce a relaxation of this class, which guarantees non-emptiness of the core. Our algorithms work both in the randomized and discrete models. We also show that the classic known proportional rules do not return committees from the core even for the most restrictive domains among those we consider (in particular for 1D-Euclidean preferences). We additionally prove a number of structural results that give better insights into the nature of some of the restricted domains, and which in particular give a better intuitive understanding of the class of top-monotonic preferences.