Control complexity in Bucklin and fallback voting: a theoretical analysis. (English) Zbl 1320.91055
Summary: Electoral control models ways of changing the outcome of an election via such actions as adding, deleting, or partitioning either candidates or voters. To protect elections from such control attempts, computational complexity has been used to establish so-called resistance results. We show that fallback voting, an election system proposed by S. J. Brams and M. R. Sanver [in: The mathematics of preference, choice and order. Essays in honor of Peter C. Fishburn. Berlin: Springer. 215–237 (2009; Zbl 1173.91349)] to combine Bucklin with approval voting, displays the broadest control resistance currently known to hold among natural election systems with a polynomial-time winner problem. We also study the control complexity of Bucklin voting and show that it performs almost as well as fallback voting in terms of control resistance. Furthermore, we investigate the parameterized control complexity of Bucklin and fallback voting, according to several parameters that are often likely to be small for typical instances. In a companion paper [ibid. 81, No. 4, 661–670 (2015; Zbl 1320.91056)], we challenge our worst-case complexity results from an experimental point of view.
Keywords:
computational social choice; control complexity; Bucklin voting; fallback voting; parameterized complexity; election systemsReferences:
| [1] | Bachrach, Y.; Elkind, E.; Faliszewski, P., Coalitional voting manipulation: A game-theoretic perspective, (Proceedings of the 22nd International Joint Conference on Artificial Intelligence (July 2011), IJCAI), 49-54 |
| [2] | Balinski, M., Fair majority voting (or how to eliminate gerrymandering), Am. Math. Mon., 115, 2, 97-113 (2008) · Zbl 1151.91036 |
| [3] | Bartholdi, J.; Orlin, J., Single transferable vote resists strategic voting, Soc. Choice Welf., 8, 4, 341-354 (1991) · Zbl 0735.90001 |
| [4] | Bartholdi, J.; Tovey, C.; Trick, M., The computational difficulty of manipulating an election, Soc. Choice Welf., 6, 3, 227-241 (1989) · Zbl 0682.90007 |
| [5] | Bartholdi, J.; Tovey, C.; Trick, M., How hard is it to control an election?, Math. Comput. Model., 16, 8/9, 27-40 (1992) · Zbl 0757.90008 |
| [6] | Baumeister, D.; Erdélyi, G.; Hemaspaandra, E.; Hemaspaandra, L.; Rothe, J., Computational aspects of approval voting, (Laslier, J.; Sanver, R., Handbook on Approval Voting (2010), Springer), 199-251, chapter 10 · Zbl 1348.91101 |
| [7] | Baumeister, D.; Roos, M.; Rothe, J., Computational complexity of two variants of the possible winner problem, (Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (May 2011), IFAAMAS), 853-860 |
| [8] | Betzler, N.; Uhlmann, J., Parameterized complexity of candidate control in elections and related digraph problems, Theor. Comput. Sci., 410, 52, 5425-5442 (2009) · Zbl 1176.68138 |
| [9] | Betzler, N.; Niedermeier, R.; Woeginger, G., Unweighted coalitional manipulation under the Borda rule is NP-hard, (Proceedings of the 22nd International Joint Conference on Artificial Intelligence (2011), IJCAI), 55-60 |
| [10] | Betzler, Nadja; Bredereck, Robert; Chen, Jiehua; Niedermeier, Rolf, Studies in computational aspects of voting - a parameterized complexity perspective, (The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, Lecture Notes in Computer Science, vol. 7370 (2012), Springer), 318-363 · Zbl 1358.68118 |
| [11] | Brams, S.; Sanver, R., Critical strategies under approval voting: Who gets ruled in and ruled out, Elect. Stud., 25, 2, 287-305 (2006) |
| [12] | Brams, S.; Sanver, R., Voting systems that combine approval and preference, (Brams, S.; Gehrlein, W.; Roberts, F., The Mathematics of Preference, Choice, and Order: Essays in Honor of Peter C. Fishburn (2009), Springer), 215-237 · Zbl 1173.91349 |
| [13] | Brandt, F.; Brill, M.; Hemaspaandra, E.; Hemaspaandra, L., Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates, (Proceedings of the 24th AAAI Conference on Artificial Intelligence (July 2010), AAAI Press), 715-722 |
| [14] | Conitzer, V., Making decisions based on the preferences of multiple agents, Commun. ACM, 53, 3, 84-94 (2010) |
| [15] | Conitzer, V.; Sandholm, T., Universal voting protocol tweaks to make manipulation hard, (Proceedings of the 18th International Joint Conference on Artificial Intelligence (August 2003), Morgan Kaufmann), 781-788 |
| [16] | Conitzer, V.; Sandholm, T.; Lang, J., When are elections with few candidates hard to manipulate?, J. ACM, 54, 3, 14 (2007) · Zbl 1292.91062 |
| [17] | Davies, J.; Katsirelos, G.; Narodytska, N.; Walsh, T., Complexity of and algorithms for Borda manipulation, (Proceedings of the 25th AAAI Conference on Artificial Intelligence (August 2011), AAAI Press), 657-662 |
| [18] | Downey, R.; Fellows, M., Parameterized Complexity (1999), Springer-Verlag · Zbl 0914.68076 |
| [19] | Dwork, C.; Kumar, R.; Naor, M.; Sivakumar, D., Rank aggregation methods for the web, (Proceedings of the 10th International World Wide Web Conference (2001), ACM Press), 613-622 |
| [20] | Elkind, E.; Erdélyi, G., Manipulation under voting rule uncertainty, (Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (June 2012), IFAAMAS), 627-634 |
| [21] | Elkind, E.; Lipmaa, H., Hybrid voting protocols and hardness of manipulation, (Proceedings of the 16th International Symposium on Algorithms and Computation. Proceedings of the 16th International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, vol. 3827 (December 2005), Springer-Verlag), 206-215 · Zbl 1173.91350 |
| [22] | Ephrati, E.; Rosenschein, J., A heuristic technique for multi-agent planning, Ann. Math. Artif. Intell., 20, 1-4, 13-67 (1997) · Zbl 0880.68121 |
| [23] | Erdélyi, G.; Fellows, M., Parameterized control complexity in Bucklin voting and in fallback voting, (Conitzer, V.; Rothe, J., Proceedings of the 3rd International Workshop on Computational Social Choice (September 2010), Universität Düsseldorf), 163-174 |
| [24] | Erdélyi, G.; Rothe, J., Control complexity in fallback voting, (Proceedings of Computing: the 16th Australasian Theory Symposium. Proceedings of Computing: the 16th Australasian Theory Symposium, Conferences in Research and Practice in Information Technology Series, vol. 32 (8) (January 2010), Australian Computer Society), 39-48 |
| [25] | Erdélyi, G.; Nowak, M.; Rothe, J., Sincere-strategy preference-based approval voting fully resists constructive control and broadly resists destructive control, Math. Log. Q., 55, 4, 425-443 (2009) · Zbl 1177.91065 |
| [26] | Erdélyi, G.; Piras, L.; Rothe, J., The complexity of voter partition in Bucklin and fallback voting: Solving three open problems, (Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (May 2011), IFAAMAS), 837-844 |
| [27] | Erdélyi, G.; Fellows, M.; Rothe, J.; Schend, L., Control complexity in Bucklin and fallback voting (March 2012), Computing Research Repository, arXiv.org/corr/ March, 2011. Revised August, 2012 |
| [28] | Erdélyi, G.; Fellows, M.; Rothe, J.; Schend, L., Control complexity in Bucklin and fallback voting: An experimental analysis, J. Comput. Syst. Sci., 81, 4, 661-670 (2015), in this issue · Zbl 1320.91056 |
| [29] | Faliszewski, P.; Procaccia, A., AI’s war on manipulation: Are we winning?, AI Mag., 31, 4, 53-64 (2010) |
| [30] | Faliszewski, P.; Rothe, J., Control and bribery in voting, (Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; Procaccia, A., Handbook of Computational Social Choice (2015), Cambridge University Press), in press · Zbl 1452.91125 |
| [31] | Faliszewski, P.; Hemaspaandra, E.; Schnoor, H., Copeland voting: Ties matter, (Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (May 2008), IFAAMAS), 983-990 |
| [32] | Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L., How hard is bribery in elections?, J. Artif. Intell. Res., 35, 485-532 (2009) · Zbl 1180.91090 |
| [33] | Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L.; 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 (2009), Springer), 375-406, Chapter 14 · Zbl 1167.91339 |
| [34] | Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L.; Rothe, J., Llull and Copeland voting computationally resist bribery and constructive control, J. Artif. Intell. Res., 35, 275-341 (2009) · Zbl 1180.91091 |
| [35] | Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L., Using complexity to protect elections, Commun. ACM, 53, 11, 74-82 (2010) |
| [36] | Faliszewski, P.; Hemaspaandra, E.; Schnoor, H., Manipulation of Copeland elections, (Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (May 2010), IFAAMAS), 367-374 |
| [37] | Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L., Multimode control attacks on elections, J. Artif. Intell. Res., 40, 305-351 (2011) · Zbl 1242.91055 |
| [38] | Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L.; Rothe, J., The shield that never was: Societies with single-peaked preferences are more open to manipulation and control, Inf. Comput., 209, 2, 89-107 (2011) · Zbl 1218.91042 |
| [39] | Flum, J.; Grohe, M., Parameterized Complexity Theory, EATCS Texts in Theoretical Computer Science (2006), Springer-Verlag · Zbl 1143.68016 |
| [40] | Friedgut, E.; Kalai, G.; Nisan, N., Elections can be manipulated often, (Proceedings of the 49th IEEE Symposium on Foundations of Computer Science (October 2008), IEEE Computer Society), 243-249 |
| [41] | Garey, M.; Johnson, D., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company · Zbl 0411.68039 |
| [42] | Ghosh, S.; Mundhe, M.; Hernandez, K.; Sen, S., Voting for movies: The anatomy of recommender systems, (Proceedings of the 3rd Annual Conference on Autonomous Agents (1999), ACM Press), 434-435 |
| [43] | Hemaspaandra, E.; Hemaspaandra, L.; Rothe, J., Anyone but him: The complexity of precluding an alternative, Artif. Intell., 171, 5-6, 255-285 (2007) · Zbl 1168.91346 |
| [44] | Hemaspaandra, E.; Hemaspaandra, L.; Rothe, J., Hybrid elections broaden complexity-theoretic resistance to control, Math. Log. Q., 55, 4, 397-424 (2009) · Zbl 1177.91066 |
| [45] | Hemaspaandra, E.; Hemaspaandra, L.; Rothe, J., Controlling candidate-sequential elections, (Proceedings of the 20th European Conference on Artificial Intelligence (August 2012), IOS Press), 905-906 |
| [46] | Hemaspaandra, E.; Hemaspaandra, L.; Rothe, J., Online voter control in sequential elections, (Proceedings of the 20th European Conference on Artificial Intelligence (August 2012), IOS Press), 396-401 · Zbl 1327.68119 |
| [47] | Hemaspaandra, E.; Hemaspaandra, L.; Menton, C., Search versus decision for election manipulation problems, (Proceedings of the 30th International Symposium in Theoretical Aspects of Computer Science (February 2013), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), 377-388 · Zbl 1354.91054 |
| [48] | Hemaspaandra, E.; Hemaspaandra, L.; Rothe, J., The complexity of online manipulation of sequential elections, J. Comput. Syst. Sci., 80, 4, 697-710 (2014) · Zbl 1285.68223 |
| [49] | Hoag, C.; Hallett, G., Proportional Representation (1926), Macmillan |
| [50] | Isaksson, M.; Kindler, G.; Mossel, E., The geometry of manipulation - a quantitative proof of the Gibbard-Satterthwaite theorem, Combinatorica, 32, 2, 221-250 (2012) · Zbl 1265.05015 |
| [51] | Liu, H.; Zhu, D., Parameterized complexity of control problems in maximin election, Inf. Process. Lett., 110, 10, 383-388 (2010) · Zbl 1229.68045 |
| [52] | Liu, H.; Feng, H.; Zhu, D.; Luan, J., Parameterized computational complexity of control problems in voting systems, Theor. Comput. Sci., 410, 27-29, 2746-2753 (2009) · Zbl 1164.91004 |
| [53] | Meir, R.; Procaccia, A.; Rosenschein, J.; Zohar, A., Complexity of strategic behavior in multi-winner elections, J. Artif. Intell. Res., 33, 149-178 (2008) · Zbl 1165.91361 |
| [54] | Menton, C., Normalized range voting broadly resists control (June 2012), [cs.GT], Computing Research Repository, arXiv.org/corr/. April, 2011. Revised June, 2012 |
| [55] | Menton, C., Normalized range voting broadly resists control, Theory Comput. Syst., 53, 4, 507-531 (2013) · Zbl 1386.91063 |
| [56] | Mossel, E.; Racz, M., A quantitative Gibbard-Satterthwaite theorem without neutrality, (Proceedings of the 44th Symposium on Theory of Computing (May 2012), ACM), 1041-1060 · Zbl 1286.91046 |
| [57] | Niedermeier, R., Invitation to Fixed-Parameter Algorithms (2006), Oxford University Press · Zbl 1095.68038 |
| [58] | Obraztsova, S.; Elkind, E.; Hazon, N., Ties matter: Complexity of voting manipulation revisited, (Proceedings of the 22nd International Joint Conference on Artificial Intelligence (July 2011), IJCAI), 2698-2703 |
| [59] | Papadimitriou, C., Computational Complexity (1994), Addison-Wesley · Zbl 0833.68049 |
| [60] | Procaccia, A.; Rosenschein, J., Junta distributions and the average-case complexity of manipulating elections, J. Artif. Intell. Res., 28, 157-181 (2007) · Zbl 1165.91362 |
| [61] | Rothe, J., Complexity Theory and Cryptology. An Introduction to Cryptocomplexity, EATCS Texts in Theoretical Computer Science (2005), Springer-Verlag · Zbl 1082.94002 |
| [62] | Rothe, J.; Schend, L., Control complexity in Bucklin, fallback, and plurality voting: an experimental approach, (Proceedings of the 11th International Symposium on Experimental Algorithms. Proceedings of the 11th International Symposium on Experimental Algorithms, Lecture Notes in Computer Science (June 2012), Springer-Verlag), 356-368 |
| [63] | Rothe, J.; Baumeister, D.; Lindner, C.; Rothe, I., Einführung in Computational Social Choice: Individuelle Strategien und kollektive Entscheidungen beim Spielen, Wählen und Teilen (2011), Spektrum Akademischer Verlag, in German |
| [64] | Xia, L.; Conitzer, V., Generalized scoring rules and the frequency of coalitional manipulability, (Proceedings of the 9th ACM Conference on Electronic Commerce (June 2008), ACM Press), 109-118 |
| [65] | Xia, L.; Conitzer, V., A sufficient condition for voting rules to be frequently manipulable, (Proceedings of the 9th ACM Conference on Electronic Commerce (June 2008), ACM Press), 99-108 |
| [66] | Xia, L.; Zuckerman, M.; Procaccia, A.; Conitzer, V.; Rosenschein, J., Complexity of unweighted coalitional manipulation under some common voting rules, (Proceedings of the 21st International Joint Conference on Artificial Intelligence (July 2009), IJCAI), 348-353 |
| [67] | Xia, L.; Conitzer, V.; Procaccia, A., A scheduling approach to coalitional manipulation, (Proceedings of the 11th ACM Conference on Electronic Commerce (June 2010), ACM Press), 275-284 |
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.
