More Web Proxy on the site http://driver.im/

article

Towards a dichotomy for the Possible Winner problem in elections based on scoring rules

Authors:

Britta DornAuthors Info & Claims

Journal of Computer and System Sciences, Volume 76, Issue 8

Pages 812 - 836

https://doi.org/10.1016/j.jcss.2010.04.002

Published: 01 December 2010 Publication History

Abstract

To make a joint decision, agents (or voters) are often required to provide their preferences as linear orders. To determine a winner, the given linear orders can be aggregated according to a voting protocol. However, in realistic settings, the voters may often only provide partial orders. This directly leads to the Possible Winner problem that asks, given a set of partial votes, whether a distinguished candidate can still become a winner. In this work, we consider the computational complexity of Possible Winner for the broad class of voting protocols defined by scoring rules. A scoring rule provides a score value for every position which a candidate can have in a linear order. Prominent examples include plurality, k-approval, and Borda. Generalizing previous NP-hardness results for some special cases, we settle the computational complexity for all but one scoring rule. More precisely, for an unbounded number of candidates and unweighted voters, we show that Possible Winner is NP-complete for all pure scoring rules except plurality, veto, and the scoring rule defined by the scoring vector (2,1,...,1,0), while it is solvable in polynomial time for plurality and veto.

References

[1]

Y. Bachrach, N. Betzler, P. Faliszewski, Probabilistic possible winner determination, in: Proc. of 24th AAAI, 2010.

[2]

D. Baumeister, J. Rothe, Taking the final step to a full dichotomy of the Possible Winner problem in pure scoring rules, manuscript, 2010.

[3]

N. Betzler, On problem kernels for possible winner determination under the k-approval protocol, manuscript, 2010.

[4]

Betzler, N., Fellows, M.R., Guo, J., Niedermeier, R. and Rosamond, F.A., Fixed-parameter algorithms for Kemeny rankings. Theoret. Comput. Sci. v410. 4554-4570.

Digital Library

[5]

Betzler, N., Guo, J., Komusiewicz, C. and Niedermeier, R., Average parameterization and partial kernelization for computing medians. In: Lecture Notes in Comput. Sci., Springer.

[6]

Betzler, N., Guo, J. and Niedermeier, R., Parameterized computational complexity of Dodgson and Young elections. Inform. and Comput. v208 i2. 165-177.

[7]

N. Betzler, S. Hemmann, R. Niedermeier, A multivariate complexity analysis of determining possible winners given incomplete votes, in: Proc. of 21st IJCAI, 2009.

[8]

Brelsford, E., Faliszewski, P., Hemaspaandra, E., Schnoor, I. and Schnoor, H., Approximability of manipulating elections. In: Proc. of 23rd AAAI, AAAI Press. pp. 44-49.

[9]

Chevaleyre, Y., Endriss, U., Lang, J. and Maudet, N., A short introduction to computational social choice (invited paper). In: Lecture Notes in Comput. Sci., vol. 4362. Springer. pp. 51-69.

Digital Library

[10]

Y. Chevaleyre, J. Lang, N. Maudet, J. Monnot, Possible winners when new candidates are added, AAAI 2010, in press.

[11]

Conitzer, V. and Sandholm, T., Vote elicitation: Complexity and strategy-proofness. In: Proc. of 18th AAAI, AAAI Press. pp. 392-397.

[12]

Conitzer, V. and Sandholm, T., Communication complexity of common voting rules. In: Proc. of 6th EC, ACM. pp. 78-87.

[13]

Conitzer, V., Sandholm, T. and Lang, J., When are elections with few candidates hard to manipulate?. J. ACM. v54 i3. 1-33.

[14]

Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C., Introduction to Algorithms. 2001. 2nd edition. MIT Press.

[15]

Downey, R.G. and Fellows, M.R., Parameterized Complexity. 1999. Springer.

[16]

Elkind, E., Faliszewski, P. and Slinko, A., Swap bribery. In: Lecture Notes in Comput. Sci., vol. 5814. Springer. pp. 299-310.

[17]

P. Faliszewski, Nonuniform bribery (short paper), in: Proc. 7th AAMAS, 2008, pp. 1569-1572.

[18]

Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.A. and Rothe, J., Llull and Copeland voting computationally resist bribery and constructive control. J. Artificial Intelligence Res. v35. 275-341.

Digital Library

[19]

Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.A. and Rothe, J., A richer understanding of the complexity of election systems. In: Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz, Springer. pp. 375-406.

[20]

Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.A. and Rothe, J., The shield that never was: societies with single-peaked preferences are more open to manipulation and control. In: Proc. of TARK XII, ACM. pp. 118-127.

[21]

P. Faliszewski, E. Hemaspaandra, H. Schnoor, Copeland voting: Ties matter, in: Proc. of 7th AAMAS, 2008, pp. 983-990.

[22]

Fellows, M.R., Hermelin, D., Rosamond, F.A. and Vialette, S., On the parameterized complexity of multiple-interval graph problems. Theoret. Comput. Sci. v410 i1. 53-61.

[23]

Flum, J. and Grohe, M., Parameterized Complexity Theory. 2006. Springer.

[24]

Garey, M.R. and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness. 1979. W.H. Freeman.

[25]

Hemaspaandra, E. and Hemaspaandra, L.A., Dichotomy for voting systems. J. Comput. System Sci. v73 i1. 73-83.

[26]

K. Konczak, J. Lang, Voting procedures with incomplete preferences, in: Proc. of IJCAI-2005 Multidisciplinary Workshop on Advances in Preference Handling, 2005.

[27]

J. Lang, M.S. Pini, F. Rossi, K.B. Venable, T. Walsh, Winner determination in sequential majority voting, in: Proc. of 20th IJCAI, 2007, pp. 1372-1377.

[28]

Niedermeier, R., Invitation to Fixed-Parameter Algorithms. 2006. Oxford University Press.

[29]

R. Niedermeier, Reflections on multivariate algorithmics and problem parameterization, in: Proc. of 27th STACS, 2010, pp. 17-32.

[30]

Papadimitriou, C.H., Computational Complexity. 1994. Addison-Wesley.

[31]

M.S. Pini, F. Rossi, K.B. Venable, T. Walsh, Incompleteness and incomparability in preference aggregation, in: Proc. of 20th IJCAI, 2007, pp. 1464-1469.

[32]

Simjour, N., Improved parameterized algorithms for the Kemeny aggregation problem. In: Lecture Notes in Comput. Sci., vol. 5917. pp. 312-323.

[33]

Walsh, T., Uncertainty in preference elicitation and aggregation. In: Proc. of 22nd AAAI, AAAI Press. pp. 3-8.

[34]

Xia, L. and Conitzer, V., Determining possible and necessary winners under common voting rules given partial orders. In: Proc. of 23rd AAAI, AAAI Press. pp. 196-201.

[35]

L. Xia, V. Conitzer, A.D. Procaccia, A scheduling approach to coalitional manipulation, in: Proc. of 11th EC, ACM, 2010, in press.

Digital Library

[36]

L. Xia, M. Zuckerman, A.D. Procaccia, V. Conitzer, J.S. Rosenschein, Complexity of unweighted coalitional manipulation under some common voting rules, in: Proc. 21st IJCAI, 2009, pp. 348-353.

[37]

Zuckerman, M., Procaccia, A.D. and Rosenschein, J.S., Algorithms for the coalitional manipulation problem. Artificial Intelligence. v173 i2. 392-412.

Cited By

Schlotter ICechlárová KTrellová D(2024)Parameterized complexity of candidate nomination for elections based on positional scoring rulesAutonomous Agents and Multi-Agent Systems10.1007/s10458-024-09658-538:2Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s10458-024-09658-5
Baumeister DHogrebe T(2023)On the Complexity of Predicting Election Outcomes and Estimating Their RobustnessSN Computer Science10.1007/s42979-023-01725-04:4Online publication date: 28-Apr-2023
https://dl.acm.org/doi/10.1007/s42979-023-01725-0
Cechlárová KLesca JTrellová DHančová MHanč J(2023)Hardness of candidate nominationAutonomous Agents and Multi-Agent Systems10.1007/s10458-023-09622-937:2Online publication date: 16-Aug-2023
https://dl.acm.org/doi/10.1007/s10458-023-09622-9
Show More Cited By

Towards a dichotomy for the Possible Winner problem in elections based on scoring rules
1. Theory of computation

Recommendations

Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules
MFCS '09: Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science 2009

To make a joint decision, agents (or voters) are often required to provide their preferences as linear orders. To determine a winner, the given linear orders can be aggregated according to a voting protocol. However, in realistic settings, the voters ...
Possible and Necessary Winner Problems in Iterative Elections with Multiple Rules
Frontiers of Algorithmic Wisdom
Abstract
An iterative election eliminates some candidates in each round until the remaining candidates have the same score according to a given voting rule. Prominent iterative voting rules include Hare, Coombs, Baldwin, and Nanson. The Hare/Coombs/Baldwin ...
Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules

The Possible Winner problem asks, given an election where the voters@? preferences over the candidates are specified only partially, whether a designated candidate can become a winner by suitably extending all the votes. Betzler and Dorn (2010) [2] ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computer and System Sciences

Journal of Computer and System Sciences Volume 76, Issue 8

December, 2010

206 pages

ISSN:0022-0000

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2010.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 December 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

50
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Schlotter ICechlárová KTrellová D(2024)Parameterized complexity of candidate nomination for elections based on positional scoring rulesAutonomous Agents and Multi-Agent Systems10.1007/s10458-024-09658-538:2Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s10458-024-09658-5
Baumeister DHogrebe T(2023)On the Complexity of Predicting Election Outcomes and Estimating Their RobustnessSN Computer Science10.1007/s42979-023-01725-04:4Online publication date: 28-Apr-2023
https://dl.acm.org/doi/10.1007/s42979-023-01725-0
Cechlárová KLesca JTrellová DHančová MHanč J(2023)Hardness of candidate nominationAutonomous Agents and Multi-Agent Systems10.1007/s10458-023-09622-937:2Online publication date: 16-Aug-2023
https://dl.acm.org/doi/10.1007/s10458-023-09622-9
Fitzsimmons ZHemaspaandra E(2023)Complexity of Conformant Election ManipulationFundamentals of Computation Theory10.1007/978-3-031-43587-4_13(176-189)Online publication date: 18-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-43587-4_13
Tao LChen LXu LShi WSunny AZaman MPelachaud CTaylor MFaliszewski PMascardi V(2022)How Hard is Bribery in Elections with Randomly Selected VotersProceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems10.5555/3535850.3535991(1265-1273)Online publication date: 9-May-2022
https://dl.acm.org/doi/10.5555/3535850.3535991
Imber AKimelfeld BDignum FLomuscio AEndriss UNowé A(2021)Probabilistic Inference of Winners in Elections by Independent Random VotersProceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3463952.3464031(647-655)Online publication date: 3-May-2021
https://dl.acm.org/doi/10.5555/3463952.3464031
Imber AKimelfeld BDignum FLomuscio AEndriss UNowé A(2021)Computing the Extremal Possible Ranks with Incomplete PreferencesProceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3463952.3464030(638-646)Online publication date: 3-May-2021
https://dl.acm.org/doi/10.5555/3463952.3464030
Chakraborty VKolaitis PDignum FLomuscio AEndriss UNowé A(2021)Classifying the Complexity of the Possible Winner Problem on Partial ChainsProceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3463952.3463992(297-305)Online publication date: 3-May-2021
https://dl.acm.org/doi/10.5555/3463952.3463992
Chakraborty VDelemazure TKimelfeld BKolaitis PRelia KStoyanovich J(2021)Algorithmic Techniques for Necessary and Possible WinnersACM/IMS Transactions on Data Science10.1145/34584722:3(1-23)Online publication date: 21-Jul-2021
https://dl.acm.org/doi/10.1145/3458472
Neveling MRothe JWeishaupt R(2021)The Possible Winner Problem with Uncertain Weights RevisitedFundamentals of Computation Theory10.1007/978-3-030-86593-1_28(399-412)Online publication date: 12-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-86593-1_28
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents