Table of COMSOC FPT Races
Problems in context of Computation Social Choice typically have a two-dimensional input ($m$ alternatives/candidates/issues and $n$ ranking/votes).
| Problem | Parameter | $f(k)$ | kernel size ($m \times n$) | Reference / Comments |
|---|---|---|---|---|
| Winner determination for Kemeny voting | Kemeny score $k$ | $2^{O(\sqrt{k})}$ | $2k \times 2k$ | [1], [2] |
| #candidates $m$ | $2^m$ | unknown | [2] | |
| average Kendall-Tau distance $d_a$ | $2^{O(\sqrt{d_a})}$ | $16/3 \cdot d_a \times \infty$ | [1], [3] partial problem kernel | |
| Winner Determination for Dodgson | Dodgson score $k$ | $2^k$ | no poly kernel | [4], [5] |
| Possible Winner for Borda | #undetermined pairs $s$ | $1.82^s$ | unknown | [6] |
| Possible Winner for $k$-Approval | #undetermined pairs $s$ | $1.82^s$ | unknown | [6] |
| Possible Winner for Copeland | #undetermined pairs $s$ | $2^s$ | unknown | [6], holds for all voting rules with polynomial-time Winner Determination |
| Swap Bribery for $k$-Approval | $k$ + budget $\beta$ | ? | $n^2\beta^2 \times n^2\beta$ | [7], $k$ is part of the input |
| $n$ ($k$ is constant) | $2^{O(n \log n)}$ | unknown | [7], $k$ is a constant | |
| Optimal Lobbying | #issues $m$ | $(2^m)^{2.5(2^m)+o(2^m)}$ | no poly kernel | [7], [8] integer linear feasibility |
| #issues $m$ + max gap $g$ | $(g+1)^m$ | no poly kernel | [8] |
Furthermore, many other problems are known to be fixed-parameter tractable with respect to the number of alternatives/candidates/issues only due to integer linear feasibility with bounded number of variables. More precisely, such ILP-formulations can (among others) be found for Possible Winner, Manipulation (weighted and unweighted) and several variants of Control for all voting rules which can be described by linear inequalities [7]. A direct algorithm for any of these problems could give new insights. In contrast to (Optimal) Lobbying (see above) for most problems nothing is known about polynomial-size problem kernels.
Concrete Examples:
- Swap Bribery for $k$-Approval [7],
- Winner Determination for Dodgson [9],
- Possible Winner for Borda,
- Possible Winner for $k$-Approval,
- Possible Winner for Copeland, and
- Unweighted Coalitional Manipulation for Borda [10].
Parameterized Complexity of Bribery Problems for instances with $n$ voters and $m$ candidates, and fixed voting rule $\mathcal R$:
| Problem | Fastest algorithm for rules R (except Kemeny rule) | Reference |
|---|---|---|
| R-$Bribery | $2^{2^{O(m)}}$ | Bredereck et al. Elections with few candidates: Prices, weights, and covering problems. Proc. ADT 2015 |
| R-Manipulation | $2^{2^{O(m)}}$ | Bredereck et al. Elections with few candidates: Prices, weights, and covering problems. Proc. ADT 2015 |
| R-CCAV/R-CCDV | $2^{2^{O(m)}}$ | Bredereck et al. Elections with few candidates: Prices, weights, and covering problems. Proc. ADT 2015 |
| R-Swap Bribery | $2^{2^{O(m)}}$ for unit cost | Dorn and Schlotter. Multivariate complexity analysis of swap bribery. Algorithmica, 64(1):126–151, 2012. |
| R-Shift Bribery | $2^{2^{O(m)}}$ for unit cost | Dorn and Schlotter. Multivariate complexity analysis of swap bribery. Algorithmica, 64(1):126–151, 2012. |
| $n^{f(m)}$ for arbitrary cost | Bredereck et al. Complexity of shift bribery in committee elections. Proc. AAAI 2016, 2016. | |
| FPT-Approximation Scheme for restriction | Bredereck et al. Complexity of shift bribery in committee elections. Proc. AAAI 2016, 2016. | |
| R-Support Bribery | NP-complete | Schlotter et al. Campaign management under approval-driven voting rules. Proc. AAAI 2011, 2011. |
| R-Mixed Bribery | NP-complete | Elkind et al. Swap Bribery. Proc. SAGT 2009, pages 299-310, 2009. |
| R-Extension Bribery | NP-complete | Baumeister et al. Campaigns for lazy voters: truncated ballots. Proc. AAMAS 2012, pages 577–584, 2012. |
| R-Possible Winner | $2^{2^{O(m)}}$ | Betzler et al. A multivariate complexity analysis of determining possible winners given incomplete votes. Proc. IJCAI 2009, pages 53–58, 2009. |
| Dodgson Score | $2^{2^{O(m)}}$ | Bartholdi III et al. Voting schemes for which it can be difficult to tell who won the election. Soc. Choice Welfare, 6(2):157–165, 1989. |
| Young Score | $2^{2^{O(m)}}$ | Young. Extending Condorcet's rule. J. Econ. Theory, 16:335–353, 1977 |
References:
- Marek Karpinski and Warren Schudy. Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament. In Proceedings of the 21st International Symposium on Algorithms and Computation, volume 6506 of LNCS, pages 3–14. Springer, 2010.
- Nadja Betzler, Michael R. Fellows, Jiong Guo, Rolf Niedermeier, and Frances A. Rosamond. Fixed-Parameter Algorithms for Kemeny Rankings. Theoretical Computer Science, 410:4554–4570, 2009.
- Nadja Betzler, Robert Bredereck, and Rolf Niedermeier. Partial Kernelization for Rank Aggregation: Theory and Experiments. In Proceedings of 5th International Symposium on Parameterized and Exact Computation, volume 6478 of LNCS, pages 26–37. Springer, 2010.
- Nadja Betzler, Jiong Guo, and Rolf Niedermeier. Parameterized Computational Complexity of Dodgson and Young Elections. Information and Computation, 208(2):165–177, 2010.
- Michael R. Fellows, Bart Jansen, Daniel Lokshtanov, Frances A. Rosamond, and Saket Saurabh. Determining the Winner of a Dodgson Election is Hard. In Proceedings of the 29th Conference on Foundations of Software Technology and Theoretical Computer Science, pages 459–469. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010.
- Nadja Betzler. A Multivariate Complexity Analysis of Voting Problems. PhD thesis, Friedrich-Schiller-Universität Jena, 2010.
- Britta Dorn and Ildikó Schlotter. Multivariate Complexity Analysis of Swap Bribery. Algorithmica, 64(1):126-151, 2012.
- Robert Bredereck and Jiehua Chen and Sepp Hartung and Stefan Kratsch and Rolf Niedermeier and Ondřej Suchý. A Multivariate Complexity Analysis of Lobbying in Multiple Referenda. In Proceedings of the 26th Conference on Artificial Intelligence, pages 1292-1298, 2012.
- John J. Bartholdi III, Craig A. Tovey, and Michael A. Trick. Voting Schemes for Which It Can Be Difficult to Tell Who Won the Election. Social Choice and Welfare, 6(2):157–165, 1989.
- Nadja Betzler and Rolf Niedermeier and Gerhard Woeginger. Unweighted Coalitional Manipulation Under the Borda Rule is NP-Hard. In Proceedings of the 22th International Joint Conference on Artificial Intelligence, pages 55-60, 2011.