Parameterized computational complexity of Dodgson and Young elections. (English) Zbl 1191.68338
Summary: We show that the two NP-complete problems of Dodgson Score and Young Score have differing computational complexities when the winner is close to being a Condorcet winner. On the one hand, we present an efficient fixed-parameter algorithm for determining a Condorcet winner in Dodgson elections by a minimum number of switches in the votes. On the other hand, we prove that the corresponding problem for Young elections, where one has to delete votes instead of performing switches, is W[2]-complete. In addition, we study Dodgson elections that allow ties between the candidates and give fixed-parameter tractability as well as W[2]-completeness results depending on the cost model for switching ties.
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
Keywords:
computational social choice; voting systems; winner determination; fixed-parameter tractability; W[2]-completenessReferences:
| [1] | Bartholdi, J.; Tovey, C. A.; Trick, M. A., Voting schemes for which it can be difficult to tell who won the election, Social Choice and Welfare, 6, 157-165 (1989) · Zbl 0672.90004 |
| [5] | Christian, R.; Fellows, M. R.; Rosamond, F. A.; Slinko, A. M., On complexity of lobbying in multiple referenda, Review of Economic Design, 11, 3, 217-224 (2007) · Zbl 1136.91376 |
| [7] | Conitzer, V.; Sandholm, T.; Lang, J., When are elections with few candidates hard to manipulate?, Journal of the ACM, 54, 3, 1-33 (2007) · Zbl 1292.91062 |
| [9] | Downey, R. G.; Fellows, M. R., Threshold dominating sets and an improved version of W[2], Theoretical Computer Science, 209, 123-140 (1998) · Zbl 0912.68075 |
| [10] | Downey, R. G.; Fellows, M. R., Parameterized Complexity (1999), Springer · Zbl 0914.68076 |
| [11] | Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. A.; Rothe, J., A richer understanding of the complexity of election systems, (Ravi, S.; Shukla, S., Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz (2008), Springer), 375-406, (Chapter 14) · Zbl 1167.91339 |
| [13] | Flum, J.; Grohe, M., Parameterized Complexity Theory (2006), Springer · Zbl 1143.68016 |
| [14] | Guo, J.; Niedermeier, R., Invitation to data reduction and problem kernelization, ACM SIGACT News, 38, 1, 31-45 (2007) |
| [15] | Hemaspaandra, E.; Hemaspaandra, L. A., Dichotomy for voting systems, Journal of Computer and System Sciences, 73, 1, 73-83 (2007) · Zbl 1154.91381 |
| [16] | Hemaspaandra, E.; Hemaspaandra, L. A.; Rothe, J., Exact analysis of Dodgson elections: Lewis Caroll’s 1876 voting system is complete for parallel access to NP, Journal of the ACM, 44, 6, 806-825 (1997) · Zbl 0904.68111 |
| [17] | Hemaspaandra, E.; Hemaspaandra, L. A.; Rothe, J., Anyone but him: the complexity of precluding an alternative, Artificial Intelligence, 171, 5-6, 255-285 (2007) · Zbl 1168.91346 |
| [18] | Homan, C. M.; Hemaspaandra, L. A., Guarantees for the success frequency of an algorithm for finding Dodgson-election winners, Journal of Heuristics, 15, 4, 403-423 (2009) · Zbl 1188.91062 |
| [19] | Lenstra, H. W., Integer programming with a fixed number of variables, Mathematics of Operations Research, 8, 538-548 (1983) · Zbl 0524.90067 |
| [21] | McCabe-Dansted, J. C.; Pritchard, G.; Slinko, A., Approximability of Dodgson’s rule, Social Choice and Welfare, 31, 2, 311-330 (2008) · Zbl 1163.91344 |
| [22] | McLean, I.; Urken, A., Classics of Social Choice (1995), University of Michigan Press: University of Michigan Press Ann Arbor, Michigan |
| [23] | Meir, R.; Procaccia, A. D.; Rosenschein, J. S.; Zohar, A., The complexity of strategic behavior in multi-winner elections, Journal of Artificial Intelligence Research, 33, 49-178 (2008) · Zbl 1165.91361 |
| [24] | Niedermeier, R., Invitation to Fixed-Parameter Algorithms (2006), Oxford University Press · Zbl 1095.68038 |
| [25] | Rothe, J.; Spakowski, H.; Vogel, J., Exact complexity of the winner problem for Young elections, Theory of Computing Systems, 36, 375-386 (2003) · Zbl 1061.90084 |
| [26] | Young, H. P., Extending Condorcet’s rule, Journal of Economic Theory, 16, 35-353 (1977) · Zbl 0399.90006 |
| [27] | Zuckerman, M.; Procaccia, A. D.; Rosenschein, J. S.; problem, Algorithms for the coalitional manipulation, Artificial Intelligence, 173, 2, 392-412 (2009) · Zbl 1187.91062 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
