×

zbMATH — the first resource for mathematics

Often harder than in the constructive case: destructive bribery in CP-nets. (English) Zbl 1406.91113
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48994-9/pbk; 978-3-662-48995-6/ebook). Lecture Notes in Computer Science 9470, 314-327 (2015).
Summary: We study the complexity of the destructive bribery problem (an external agent tries to prevent a disliked candidate from winning by bribery actions) in voting over combinatorial domains, where the set of candidates is the Cartesian product of several issues. This problem is related to the concept of the margin of victory of an election which constitutes a measure of robustness of the election outcome and plays an important role in the context of electronic voting. In our setting, voters have conditional preferences over assignments to these issues, modelled by CP-nets. We settle the complexity of all combinations of this problem based on distinctions of four voting rules, five cost schemes, three bribery actions, weighted and unweighted voters, as well as the negative and the non-negative scenario. We show that almost all of these cases are \(\mathcal {NP}\)-complete or \(\mathcal {NP}\)-hard for weighted votes while approximately half of the cases can be solved in polynomial time for unweighted votes.
For the entire collection see [Zbl 1326.68026].

MSC:
91B14 Social choice
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Software:
CP-nets
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Boutilier, C., Brafman, R.I., Domshlak, C., Hoos, H.H., Poole, D.: Cp-nets: a tool for representing and reasoning with conditional ceteris paribus preference statements. J. Artif. Intell. Res. 21, 135–191 (2004) · Zbl 1080.68685
[2] Brafman, R., Rossi, F., Salvagnin, D., Venable, K.B., Walsh, T.: Finding the next solution in constraint- and preference-based knowledge representation formalisms. In: 12th International Conference: Principles of Knowledge Representation and Reasoning, pp. 425–433. AAAI Press (2010)
[3] Brandt, F., Conitzer, V., Endriss, U.: Computational social choice. In: Multiagent Systems, pp. 213–283. MIT Press (2013)
[4] Conitzer, V., Lang, J., Sandholm, T.: How many candidates are needed to make elections hard to manipulate? In: 9th Conference on Theoretical Aspects of Rationality and Knowledge, pp. 201–214. ACM (2003) · doi:10.1145/846241.846268
[5] Conitzer, V., Lang, J., Xia, L.: Hypercubewise preference aggregation in multi-issue domains. In: 22nd International Joint Conference on Artificial Intelligence, pp. 158–163. AAAI Press (2011)
[6] Conitzer, V., Sandholm, T.: Complexity of manipulating elections with few candidates. In: 18th National Conference on Artificial Intelligence, pp. 314–319. AAAI Press (2002)
[7] Dorn, B., Krüger, D.: On the hardness of bribery variants in voting with CP-nets. Ann. Math. Artif. Intell., 1–29 (2015). doi: 10.1007/s10472-015-9469-3 · Zbl 1345.91006 · doi:10.1007/s10472-015-9469-3
[8] Dorn, B., Krüger, D., Scharpfenecker, P.: Often harder than in the constructive case: destructive bribery in CP-nets, pp. 1–22 (2015). CoRR abs/1509.08628 · Zbl 1406.91113
[9] Elkind, E., Faliszewski, P., Slinko, A.: Swap bribery. In: Mavronicolas, M., Papadopoulou, V.G. (eds.) Algorithmic Game Theory. LNCS, vol. 5814, pp. 299–310. Springer, Heidelberg (2009) · Zbl 1262.91056 · doi:10.1007/978-3-642-04645-2_27
[10] Faliszewski, P., Hemaspaandra, L., Hemaspaandra, E., Rothe, J.: A richer understanding of the complexity of election systems. In: Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz, 1st edn., chap. 14, pp. 375–406. Springer (2009) · Zbl 1167.91339 · doi:10.1007/978-1-4020-9688-4_14
[11] Faliszewski, P.: Nonuniform bribery. In: 7th International Joint Conference on Autonomous Agents and Multiagent Systems, vol. 3, pp. 1569–1572. IFAAMAS (2008)
[12] Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.A.: How hard is bribery in elections? J. Artif. Intell. Res. 35(2), 485–532 (2009) · Zbl 1180.91090
[13] Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.A., Rothe, J.: Llull and copeland voting computationally resist bribery and constructive control. J. Artif. Intell. Res. (JAIR) 35, 275–341 (2009) · Zbl 1180.91091
[14] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979) · Zbl 0411.68039
[15] Hemaspaandra, E., Hemaspaandra, L.A., Rothe, J.: Anyone but him: the complexity of precluding an alternative. Artif. Intell. 171(5–6), 255–285 (2007) · Zbl 1168.91346 · doi:10.1016/j.artint.2007.01.005
[16] Lang, J.: Vote and aggregation in combinatorial domains with structured preferences. In: 20th International Joint Conference on Artificial Intelligence, pp. 1366–1371 (2007)
[17] Magrino, T.R., Rivest, R.L., Shen, E.: Computing the margin of victory in IRV elections. In: Electronic Voting Technology Workshop / Workshop on Trustworthy Elections. USENIX Association (2011)
[18] Maran, A., Maudet, N., Pini, M.S., Rossi, F., Venable, K.B.: A framework for aggregating influenced CP-nets and its resistance to bribery. In: 27th AAAI Conference on Artificial Intelligence, pp. 668–674. AAAI Press (2013)
[19] Mattei, N., Pini, M.S., Rossi, F., Venable, K.B.: Bribery in voting with CP-nets. Ann. Math. Artif. Intell. 68(1–3), 135–160 (2013) · Zbl 1282.91095 · doi:10.1007/s10472-013-9330-5
[20] Norden, L., Burstein, A., Hall, J.L., Chen, M.: Post-election audits: restoring trust in elections. Brennan Center for Justice at New York University, Tech. report (2007)
[21] Pini, M., Rossi, F., Venable, K.: Bribery in voting with soft constraints. In: 27th AAAI Conference on Artificial Intelligence, pp. 803–809. AAAI Press (2013)
[22] Purrington, K., Durfee, E.H.: Making social choices from individuals’ CP-nets. In: 6th International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 1122–1124. IFAAMAS (2007) · doi:10.1145/1329125.1329341
[23] Reisch, Y., Rothe, J., Schend, L.: The margin of victory in schulze, cup, and copeland elections: complexity of the regular and exact variants. In: 7th European Starting AI Researcher Symposium, pp. 250–259. IOS Press (2014) · Zbl 1394.91121
[24] Rossi, F., Venable, K.B., Walsh, T.: mCP Nets: representing and reasoning with preferences of multiple agents. In: 19th National Conference on Artificial Intelligence, pp. 729–734. AAAI Press (2004)
[25] Stark, P.B.: Risk-limiting post-election audits: P-values from common probability inequalities. IEEE Trans. Inf. Forensics Secur. 4, 1005–1014 (2009) · doi:10.1109/TIFS.2009.2034190
[26] Xia, L.: Computing the margin of victory for various voting rules. In: ACM Conference on Electronic Commerce, EC 2012, Valencia, Spain, 4–8 June 2012, pp. 982–999. ACM (2012) · doi:10.1145/2229012.2229086
[27] Xia, L., Conitzer, V., Lang, J.: Voting on multiattribute domains with cyclic preferential dependencies. In: 23rd AAAI Conference on Artificial Intelligence, pp. 202–207. AAAI Press (2008)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.