?
Restricted Domains of Dichotomous Preferences with Possibly Incomplete Information
P. 2023–2025.
Restricted domains have been extensively studied within computational social choice, initially for voters’ preferences that are total orders over the set of alternatives and subsequently for preferences that are dichotomous—i.e., that correspond to approved and disapproved alternatives. We contribute to the latter stream of work. We obtain forbidden subprofile characterisations for various important dichotomous domains, and we also study profiles with incomplete information about the voters’ preferences. Specifically, we design polynomial algorithms to determine whether such incomplete profiles admit completions within certain restricted domains.