We investigate the complexity of several manipulation and control problems under numerous prevalent approval-based multiwinner voting rules. Particularly, the rules we study include approval voting (AV), satisfaction approval voting (SAV), net-satisfaction approval voting (NSAV), proportional approval voting (PAV), approval-based Chamberlin-Courant voting (ABCCV), minimax approval voting (MAV), etc. We show that these rules generally resist the strategic types scrutinized in the paper, with only a few exceptions. In addition, we also obtain many fixed-parameter tractability results for these problems with respect to several natural parameters, and derive polynomial-time algorithms for certain special cases.
翻译：特别是,我们研究的规则包括批准投票(AV)、满意批准投票(SAV)、净满意批准投票(NSAV)、按比例批准投票(PAV)、以核准为基础的会议厅-乡村投票(ABCCV)、小额批准投票(MAV)等。 我们表明,这些规则一般抵制文件中审查的战略类型,只有少数例外。 此外,我们还取得了关于这些问题的若干自然参数的许多固定参数可追溯性结果,并得出了某些特殊案例的混合时间算法。
相关内容
微信扫码咨询专知VIP会员