论文标题
多方竞选活动
Multi-Party Campaigning
论文作者
论文摘要
我们研究了选举中操纵的社会选择环境，并以两种主要方式扩展了通常的模型：首先，在我们的环境中，没有考虑单个操纵代理，而是有几种可能竞争的。其次，我们没有在第一次操纵行动之后评估选举，而是允许进行几轮来回。我们表明，在某些情况下，例如在只有几个候选人的选举中，可以有效地计算每个操纵代理的最佳策略。 我们的算法结果依赖于制定找到最佳策略作为短期句子的句子的问题，这些句子是短的，仅涉及小系数，我们表明这是固定参数可拖动的 - 的确，我们的贡献之一是，我们的一般结果是在Presburger Arithmetic的固定参数障碍中可能在其他设置中有用的固定参数。遵循我们的一般定理，我们设计了相当一般的算法。特别是，我们描述了如何为各种设置设计有效的算法，包括在社交网络中对意见扩散的设置，可用于操纵代理的复杂预算方案的扩散以及对敌对行动的各种现实限制。
We study a social choice setting of manipulation in elections and extend the usual model in two major ways: first, instead of considering a single manipulating agent, in our setting there are several, possibly competing ones; second, instead of evaluating an election after the first manipulative action, we allow several back-and-forth rounds to take place. We show that in certain situations, such as in elections with only a few candidates, optimal strategies for each of the manipulating agents can be computed efficiently. Our algorithmic results rely on formulating the problem of finding an optimal strategy as sentences of Presburger arithmetic that are short and only involve small coefficients, which we show is fixed-parameter tractable -- indeed, one of our contributions is a general result regarding fixed-parameter tractability of Presburger arithmetic that might be useful in other settings. Following our general theorem, we design quite general algorithms; in particular, we describe how to design efficient algorithms for various settings, including settings in which we model diffusion of opinions in a social network, complex budgeting schemes available to the manipulating agents, and various realistic restrictions on adversary actions.
