Elections with Few Candidates: Prices, Weights, and Covering Problems
Elections with Few Candidates: Prices, Weights, and Covering Problems
复制标题
候选人很少的选举：价格、权重和覆盖问题
DOI：
10.1007/978-3-319-23114-3_25
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Nimrod Talmon
中科院分区：
文献类型：
--
作者：
Robert Bredereck;Piotr Faliszewski;Rolf Niedermeier;Piotr Skowron;Nimrod Talmon
我们表明，当通过候选人数量进行参数化时，许多与选举相关的价格问题（例如贿赂）是固定参数可处理的（in）。对于行贿问题，这解决了一个近10年的家庭悬而未决的问题。我们的结果遵循一种通用技术，将投票问题表述为覆盖问题，并扩展了使用整数线性规划和 Lenstra 算法的经典方法 [19]。在这种情况下，我们的中心结果是，由宇宙大小参数化的加权集多重覆盖是固定参数易于处理的。我们的方法也适用于批准投票的加权选举控制。我们将以前已知的会员资格改进为会员资格。我们对基于现实世界的数据进行的初步实验表明，我们的方法对于候选者很少的情况具有实际用途。
We show that a number of election-related problems with prices (such as, for example, bribery) are fixed-parameter tractable (in) when parameterized by the number of candidates. For bribery, this resolves a nearly 10-year old family of open problems. Our results follow by a general technique that formulates voting problems as covering problems and extends the classic approach of using integer linear programming and the algorithm of Lenstra [19]. In this context, our central result is thatWeighted Set Multicoverparameterized by the universe size is fixed-parameter tractable. Our approach is also applicable to weighted electoral control for Approval voting. We improve previously known-memberships to-memberships. Our preliminary experiments on real-world-based data show the practical usefulness of our approach for instances with few candidates.
批准驱动的投票规则下的竞选管理
影响因子：
1.1
作者：
Ildikó Schlotter;Piotr Faliszewski;Edith Elkind
通讯作者：
Edith Elkind
加权选举控制
DOI：
10.1613/jair.4621
发表时间：
2013
期刊：
ArXiv
影响因子：
--
作者：
Piotr Faliszewski;E. Hemaspaandra;L. Hemaspaandra
通讯作者：
L. Hemaspaandra
控制巴克林和后备投票的复杂性：实验分析
DOI：
10.1016/j.jcss.2014.11.003
发表时间：
2015
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
G. Erdélyi;M. Fellows;J. Rothe;Lena Schend
通讯作者：
Lena Schend