A note on the complexity of manipulating weighted Schulze voting. (English) Zbl 1466.91110
Summary: We prove that the constructive weighted coalitional manipulation problem for the Schulze voting rule can be solved in polynomial time for an unbounded number of candidates and an unbounded number of manipulators.
MSC:
| 91B14 | Social choice |
| 91B86 | Mathematical economics and fuzziness |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | Bartholdi, J. J.; Tovey, C. A.; Trick, M. A., The computational difficulty of manipulating an election, Soc. Choice Welf., 6, 3, 227-241 (1989) · Zbl 0682.90007 |
| [2] | Conitzer, V.; Sandholm, T.; Lang, J., When are elections with few candidates hard to manipulate?, J. ACM, 54, 3, 14 (2007) · Zbl 1292.91062 |
| [3] | Conitzer, V.; Walsh, T., Barriers to manipulation in voting, (Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; Procaccia, A. D., Handbook of Computational Social Choice (2016), Cambridge University Press: Cambridge University Press Cambridge), 127-145, Ch. 6 · Zbl 1448.91097 |
| [4] | Duggan, J.; Schwartz, T., Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized, Soc. Choice Welf., 17, 1, 85-93 (2000) · Zbl 1069.91548 |
| [5] | Gaspers, S.; Kalinowski, T.; Narodytska, N.; Walsh, T., Coalitional manipulation for Schulze’s rule, (Proceedings of the 12th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS’13) (2013), IFAAMAS), 431-438 |
| [6] | Gibbard, A., Manipulating of voting schemes: a general result, Econometrica, 41, 4, 587-601 (1973) · Zbl 0325.90081 |
| [7] | Hemaspaandra, L. A.; Lavaee, R.; Menton, C. G., Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control, Ann. Math. Artif. Intell., 77, 3-4, 191-223 (2016) · Zbl 1346.91072 |
| [8] | Müller, J., The complexity of manipulating Schulze voting (2013), Department of Computer & Information Science, University of Konstanz: Department of Computer & Information Science, University of Konstanz Konstanz, Bachelor’s thesis |
| [9] | Menton, C. G.; Singh, P., Control complexity of Schulze voting, (Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI’13) (2013), AAAI Press: AAAI Press Palo Alto, CA), 286-292 |
| [10] | Parkes, D. C.; Xia, L., A complexity-of-strategic-behavior comparison between Schulze’s rule and ranked pairs, (Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI’12) (2012), AAAI Press: AAAI Press Palo Alto, CA), 1429-1435 |
| [11] | Reisch, Y.; Rothe, J.; Schend, L., The margin of victory in Schulze, cup, and Copeland elections: complexity of the regular and exact variants, (Proceedings of the 7th European Starting AI Researcher Symposium (STAIRS’14) (2014), IOS Press: IOS Press Amsterdam), 250-259 · Zbl 1394.91121 |
| [12] | Satterthwaite, M. A., Strategy-proofness and arrow’s conditions: existence and correspondence theorems for voting procedures and social welfare functions, J. Econ. Theory, 10, 2, 187-217 (1975) · Zbl 0315.90088 |
| [13] | Schulze, M., A new monotonic, clone-independent, reversal symmetric, and Condorcet-consistent single-winner election method, Soc. Choice Welf., 36, 2, 267-303 (2011) · Zbl 1232.91185 |
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.
