Abstract
Baumeister et al. [8] introduced the possible winner with uncertain weights problem which, given a weighted election with the weights of some voters as yet unspecified, asks whether one can assign weights to these voters such that a distinguished candidate wins. Solving all questions they specifically left open for nonnegative integer weights, we show that two variants of this problem for 3-approval and four variants for plurality with runoff can be solved efficiently. In addition, we study variants of this problem for Borda, k-veto, and veto with runoff in terms of their computational complexity. Finally, we also prove that the problem of constructive control by adding voters in succinct representation belongs to P for plurality with runoff and veto with runoff.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Baumeister et al. [8] define and study these problems for nonnegative integer and nonnegative rational weights, and accordingly append either \(\mathbb {N}\) or \(\mathbb {Q}^+\) to their problems. We will consider the case of nonnegative integer weights only, but for clarity and consistency with the literature, we append the suffix “-\(\mathbb {N}\)” to our problems.
- 2.
Formally, Gabow [17] and Grötschel et al. [20, p. 259] define a maximization variant of \(\textsc {GWbEM}\) and show its polynomial-time solvability, which immediately implies that \(\textsc {GWbEM}\) is in \(\textsc {P}\). The same problem was first used by Lin [27] in the context of voting and later on also, for example, by Erdélyi et al. [15].
- 3.
This assumption does make sense indeed: Otherwise, the parameter B would be meaningless and our instance becomes a \(\textsc {PWUW}\text {-}{}\textsc {rw}\text {-}{}\mathbb {N}\) instance which, as mentioned earlier, is efficiently solvable.
- 4.
As pointed out by Zack Fitzsimmons and Edith Hemaspaandra, for \(3\text {-approval}\), that \(\textsc {PWUW}\text {-}{}\textsc {bw}\text {-}{}\mathbb {N}\) is (and, possibly, other of our problems are) in \(\textsc {P}\) also follows immediately from the results of Baumeister et al. [8] and Fitzsimmons and Hemaspaandra [16]. Even more, they note that since the dichotomy for the problem CCAV (the definition of which is recalled in Footnote 5 in the next section) shown by Hemaspaandra et al. [22] is exactly the same as for its succinct variant CCAV \(_{\text {succinct}}\) [16], it follows that the same dichotomy holds for all problems X such that
. Hence, this immediately gives the same dichotomy for \(\textsc {PWUW}\text {-}{}\textsc {bw}\text {-}{}\mathbb {N}\) (both its general and its succinct variant), for example. - 5.
As a reminder, CCAV is a shorthand for the problem Constructive-Control-by-Adding-Voters introduced by Bartholdi et al. [1]. The input of \(\mathcal {E}\)-CCAV consists of a set C of candidates with a distinguished candidate \(c \in C\), a list V of registered (unit-weight) votes over C, an additional list W of as yet (unit-weight) unregistered votes, and a positive integer \(\ell \). The question is whether it is possible to make c win the election under \(\mathcal {E}\) by adding at most \(\ell \) votes from W to the election.
- 6.
References
Bartholdi III, J., Tovey, C., Trick, M.: How hard is it to control an election? Math. Comput. Model. 16(8/9), 27–40 (1992)
Baumeister, D., et al.: Positional scoring-based allocation of indivisible goods. J. Auton. Agents Multi-Agent Syst. 31(3), 628–655 (2017). https://doi.org/10.1007/s10458-016-9340-x
Baumeister, D., Erdélyi, G., Erdélyi, O., Rothe, J.: Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules. Math. Soc. Sci. 76, 19–30 (2015)
Baumeister, D., Erdélyi, G., Erdélyi, O., Rothe, J., Selker, A.: Complexity of control in judgment aggregation for uniform premise-based quota rules. J. Comput. Syst. Sci. 112, 13–33 (2020)
Baumeister, D., Järvisalo, M., Neugebauer, D., Niskanen, A., Rothe, J.: Acceptance in incomplete argumentation frameworks. Artif. Intell. 295 (2021). Article No. 103470
Baumeister, D., Neugebauer, D., Rothe, J., Schadrack, H.: Verification in incomplete argumentation frameworks. Artif. Intell. 264, 1–26 (2018)
Baumeister, D., Roos, M., Rothe, J.: Computational complexity of two variants of the possible winner problem. In: Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems, pp. 853–860. IFAAMAS (2011)
Baumeister, D., Roos, M., Rothe, J., Schend, L., Xia, L.: The possible winner problem with uncertain weights. In: Proceedings of the 20th European Conference on Artificial Intelligence, pp. 133–138. IOS Press (2012)
Baumeister, D., Rothe, J.: Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules. Inf. Process. Lett. 112(5), 186–190 (2012)
Betzler, N., Dorn, B.: Towards a dichotomy for the possible winner problem in elections based on scoring rules. J. Comput. Syst. Sci. 76(8), 812–836 (2010)
Borda, J.: Mémoire sur les élections au scrutin. Histoire de L’Académie Royale des Sciences, Paris (1781). English translation appears in the paper by de Grazia [19]
Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A. (eds.): Handbook of Computational Social Choice. Cambridge University Press, Cambridge (2016)
Conitzer, V., Sandholm, T., Lang, J.: When are elections with few candidates hard to manipulate? J. ACM 54(3), Article 14 (2007)
Elkind, E., Faliszewski, P., Slinko, A.: Swap bribery. In: Mavronicolas, M., Papadopoulou, V.G. (eds.) SAGT 2009. LNCS, vol. 5814, pp. 299–310. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04645-2_27
Erdélyi, G., Reger, C., Yang, Y.: Towards completing the puzzle: Solving open problems for control in elections. In: Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems, IFAAMAS, pp. 846–854 (2019)
Fitzsimmons, Z., Hemaspaandra, E.: High-multiplicity election problems. Auton. Agent. Multi-Agent Syst. 33(4), 383–402 (2019). https://doi.org/10.1007/s10458-019-09410-4
Gabow, H.: An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: Proceedings of the 15th ACM Symposium on Theory of Computing, pp. 448–456. ACM Press (1983)
Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H Freeman and Company, New York (1979)
de Grazia, A.: Mathematical deviation of an election system. Isis 44(1–2), 41–51 (1953)
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Heidelberg (1988). https://doi.org/10.1007/978-3-642-97881-4
Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Anyone but him: the complexity of precluding an alternative. Artif. Intell. 171(5–6), 255–285 (2007)
Hemaspaandra, E., Hemaspaandra, L., Schnoor, H.: A control dichotomy for pure scoring rules. In: Proceedings of the 28th AAAI Conference on Artificial Intelligence, pp. 712–720. AAAI Press (2014)
Kerkmann, A., Lang, J., Rey, A., Rothe, J., Schadrack, H., Schend, L.: Hedonic games with ordinal preferences and thresholds. J. Artif. Intell. Res. 67, 705–756 (2020)
Konczak, K., Lang, J.: Voting procedures with incomplete preferences. In: Proceedings of the Multidisciplinary IJCAI-05 Workshop on Advances in Preference Handling, pp. 124–129 (2005)
Kuckuck, B., Rothe, J.: Duplication monotonicity in the allocation of indivisible goods. AI Commun. 32(4), 253–270 (2019)
Lang, J.: Collective decision making under incomplete knowledge: Possible and necessary solutions. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence, pp. 4885–4891. ijcai.org (2020)
Lin, A.: Solving hard problems in election systems. Ph.D. thesis, Rochester Institute of Technology, Rochester, NY, USA (2012)
Niskanen, A., Neugebauer, D., Järvisalo, M., Rothe, J.: Deciding acceptance in incomplete argumentation frameworks. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence, pp. 2942–2949. AAAI Press (2020)
Papadimitriou, C.: Computational Complexity, 2nd edn. Addison-Wesley, Boston (1995)
Rothe, J.: Complexity Theory and Cryptology. An Introduction to Cryptocomplexity. EATCS Texts in Theoretical Computer Science, Springer, Heidelberg (2005). https://doi.org/10.1007/3-540-28520-2
Rothe, J.: Borda count in collective decision making: a summary of recent results. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pp. 9830–9836. AAAI Press (2019)
Skiba, K., Neugebauer, D., Rothe, J.: Complexity of nonempty existence problems in incomplete argumentation frameworks. IEEE Intell. Syst. 36(2), 13–24 (2021)
Xia, L., Conitzer, V.: Determining possible and necessary winners given partial orders. J. Artif. Intell. Res. 41, 25–67 (2011)
Acknowledgments
This work was supported in part by Deutsche Forschungsgemeinschaft under grants RO 1202/14-2 and RO 1202/21-1.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Neveling, M., Rothe, J., Weishaupt, R. (2021). The Possible Winner Problem with Uncertain Weights Revisited. In: Bampis, E., Pagourtzis, A. (eds) Fundamentals of Computation Theory. FCT 2021. Lecture Notes in Computer Science(), vol 12867. Springer, Cham. https://doi.org/10.1007/978-3-030-86593-1_28
Download citation
DOI: https://doi.org/10.1007/978-3-030-86593-1_28
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-86592-4
Online ISBN: 978-3-030-86593-1
eBook Packages: Computer ScienceComputer Science (R0)