On the Tree Representations of Dichotomous Preferences

On the Tree Representations of Dichotomous Preferences

Yongjie Yang

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 644-650. https://doi.org/10.24963/ijcai.2019/91

We study numerous restricted domains of dichotomous preferences with respect to some tree structures. Particularly, we study the relationships among these domains and the ones proposed by Elkind and Lackner [2015]. We also show that recognizing all the restricted domains proposed in this paper is polynomial-time solvable. Finally, we explore the complexity of winner determination for several important approval-based multiwinner voting rules when restricted to these domains.
Keywords:
Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Algorithmic Game Theory