标题：Parameterized Complexity of Committee Elections with Dichotomous and Trichotomous Votes
作者：Zhou, Aizhong; Yang, Yongjie; Guo, Jiong
作者机构：[Zhou, Aizhong; Guo, Jiong] Shandong Univ, Sch Comp Sci & Technol, Jinan, Shandong, Peoples R China.; [Yang, Yongjie] Cent S Univ, Changsha, Hunan, 更多
会议名称：18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS)
会议日期：MAY 13-17, 2019
来源：AAMAS '19: PROCEEDINGS OF THE 18TH INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS
关键词：Committee elections; parameterized complexity; maximin
摘要：We study the winner determination problem for three prevalent committee election rules: Chamberlin-Courant Approval Voting (CCA), Proportional Approval Voting (PAV), and Satisfaction Approval Voting (SAV). Axiomatic and algorithmic studies of elections under these rules have been conducted recently. It is known that the winner determination problem is NP-hard for CCA and PAV and polynomial-time solvable for SAV, if the input votes are dichotomous. Moreover, parameterized complexity of the two NP-hard cases has been examined with respect to some natural parameters such as the number of candidates or the number of votes. In this paper, we extend the above studies to committee elections with trichotomous votes and identify cases, where trichotomous votes lead to an increase of parameterized complexity. We also consider the maximin (or egalitarian) variations of the rules, where the minimum satisfaction of the voters is maximized.