Structure in Dichotomous Preferences
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 2019-2024.
Abstract
Many hard computational social choice problems are known to become tractable when voters' preferences belong to a restricted domain, such as those of single-peaked or single-crossing preferences. However, to date, all algorithmic results of this type have been obtained for the setting where each voter's preference list is a total order of candidates. The goal of this paper is to extend this line of research to the setting where voters' preferences are dichotomous, i.e., each voter approves a subset of candidates and disapproves the remaining candidates. We propose several analogues of the notions of single-peaked and single-crossing preferences for dichotomous profiles and investigate the relationships among them. We then demonstrate that for some of these notions the respective restricted domains admit efficient algorithms for computationally hard approval-based multi-winner rules.
@inproceedings{ijcai2015p286,
title = {Structure in Dichotomous Preferences},
author = {Elkind, Edith and Lackner, Martin},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-15}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Qiang Yang and Michael Wooldridge},
pages = {2019--2024},
year = {2015},
month = {7},
note = {Main Track},
url = {https://ijcai.org/proceedings/2015/286},
}
TY - CPAPER TI - Structure in Dichotomous Preferences AU - Elkind, Edith AU - Lackner, Martin T2 - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 PB - International Joint Conferences on Artificial Intelligence PY - 2015 SP - 2019 EP - 2024 UR - https://ijcai.org/proceedings/2015/286 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
