We study winner determination for three prevalent $k$-committee selection rules, namely minimax approval voting (MAV), proportional approval voting (PAV), and Chamberlin-Courant's approval voting (CCAV). It is known that winner determination for these rules is NP-hard. Parameterized complexity of the problem has been studied with respect to some natural parameters recently. However, there are still numerous parameters that have not been considered. We revisit the parameterized complexity of winner determination by considering several important single parameters, combined parameters, and structural parameters, aiming at detecting more interesting parameters leading to fixed-parameter tractability res
翻译：我们研究三项通行的美元委员会甄选规则的获胜者确定办法,即小额最高批准投票(MAV)、比例批准投票(PAV)和Camberlin-Courant的核准投票(CCAV),众所周知,这些规则的获胜者确定办法是硬的。最近就一些自然参数研究了这一问题的复杂性。然而,仍有许多参数尚未考虑。我们通过考虑一些重要的单一参数、综合参数和结构参数,重新审视确定胜者决定的参数复杂性,目的是发现更有趣的参数,导致固定参数的可移动性。
相关内容
微信扫码咨询专知VIP会员