Parameterized Algorithmics for Voting Systems

许多投票问题是NP难的，因此没有希望得到多项式时间的解决方案。在这些问题中，我们发现了赢家确定或在多次公投中优化游说的具体情况。然而，投票问题通常带有自然的参数化;例如，明显的参数是候选人的数量或投票的数量。根据后面的具体应用，这些参数中的每一个都可能很小。PAWS项目的目标是确定各种参数化对自然投票问题计算复杂性的影响。所采用的方法包括复杂性理论的技术，以及新开发的算法的实施和实证测试。

Many voting problems are NP-hard, hence there is no hope for polynomial-time solutions. Among such problems we find specific cases of winner determination or the optimization of lobbying in multiple referenda. However, voting problems typically carry natural parameterizations; for instance, obvious parameters are the number of candidates or the number of votes. Depending on the concrete application behind, each of these parameters may be small. The project PAWS targets at determining the influence of various parameterizations on the computational complexity of natural voting problems. The employed methods include complexity-theoretic techniques as well as implementation and empirical testing of newly developed algorithms.