Possible Bribery in k-Approval and k-Veto Under Partial Information

详细信息    查看全文

• 关键词：Computational social choice ; Voting ; Algorithms and complexity
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9883
• 期：1
• 页码：299-309
• 全文大小：226 KB
• 参考文献：1.Baumeister, D., Faliszewski, P., Lang, J., Rothe, J.: Campaigns for lazy voters: truncated ballots. In: Proceedings of the 11th International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 577–584. IFAAMAS, June 2012
  2.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)MathSciNet CrossRef MATH
  3.Betzler, N., Bredereck, R., Niedermeier, R.: Partial kernelization for rank aggregation: theory and experiments. In: Proceedings of the 3rd International Workshop on Computational Social Choice, pp. 31–42 (2010)
  4.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)MathSciNet CrossRef MATH
  5.Briskorn, D., Erdélyi, G., Reger, C.: Bribery in k-approval and k-veto under partial information (extended abstract). In: Proceedings of The 15th International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 1299–1301. IFAAMAS, May 2016
  6.Chevaleyre, Y., Lang, J., Maudet, N., Monnot, J.: Possible winners when new candidates are added: the case of scoring rules. In: Proceedings of the 24th AAAI Conference on Artificial Intelligence, pp. 762–767. AAAI Press, July 2010
  7.Conitzer, V., Walsh, T., Xia, L.: Dominating manipulations in voting with partial information. In: Proceedings of the 25th AAAI Conference on Artificial Intelligence, pp. 638–643. AAAI Press, August 2011
  8.Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods for the web. In: Proceedings of the 10th International World Wide Web Conference, pp. 613–622. ACM Press, May 2001
  9.Ephrati, E., Rosenschein, J.: The Clarke Tax as a consensus mechanism among automated agents. In: Proceedings of the 9th National Conference on Artificial Intelligence, pp. 173–178. AAAI Press (1991)
  10.Ephrati, E., Rosenschein, J.: Multi-agent planning as a dynamic search for social consensus. In: Proceedings of the 13th International Joint Conference on Artificial Intelligence, pp. 423–429. Morgan Kaufmann (1993)
  11.Ephrati, E., Rosenschein, J.: A heuristic technique for multi-agent planning. Ann. Math. Artif. Intell. 20(1–4), 13–67 (1997)MathSciNet CrossRef MATH
  12.Fagin, R., Kumar, R., Sivakumar, D.: Efficient similarity search and classification via rank aggregation. In: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, pp. 301–312. ACM Press (2003)
  13.Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.A.: The complexity of bribery in elections. In: Proceedings of the 20th AAAI Conference on Artificial Intelligence, pp. 641–646. AAAI Press (2006)
  14.Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.A.: How hard is bribery in elections? J. Artif. Intell. Res. 35, 485–532 (2009)MathSciNet MATH
  15.Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.A., Rothe, J.: Llull and Copeland voting computationally resist bribery and constructive control. J. Artif. Intell. Res. 35, 275–341 (2009)MathSciNet MATH
  16.Faliszewski, P., Reisch, Y., Rothe, J., Schend, L.: Complexity of manipulation, bribery, and campaign management in Bucklin and fallback voting. Auton. Agents Multi-Agent Syst. 29(6), 1091–1124 (2015)CrossRef
  17.Ghosh, S., Mundhe, M., Hernandez, K., Sen, S.: Voting for movies: the anatomy of recommender systems. In: Proceedings of the 3rd Annual Conference on Autonomous Agents, pp. 434–435. ACM Press, May 1999
  18.Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Heidelberg (1988)CrossRef MATH
  19.Konczak, K., Lang, J.: Voting procedures with incomplete preferences. In: Proceedings of IJCAI-05 Multidisciplinary Workshop on Advances in Preference Handling, pp. 124–129 (2005)
  20.Lin, A.: The complexity of manipulating \(k\) -approval elections. In: Proceedings of the 3rd International Conference on Agents and Artificial Intelligence, pp. 212–218 (2011)
  21.Parkes, D.C., Xia, L.: A complexity-of-strategic-behavior comparison between schulze’s rule and ranked pairs. In: Proceedings of the 26th AAAI Conference on Artificial Intelligence. AAAI Press (2012)
  22.Reger, C.: Voter control in k-approval and k-veto under partial information. In: Proceedings of the 14th International on Artificial Intelligence and Mathematics, January 2016
  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: Proceedings of the 7th European Starting AI Research Symposium, pp. 250–259. IOS Press (2014)
  24.Xia, L.: Computing the margin of victory for various voting rules. In: Proceedings of the 13th ACM Conference on Electronic Commerce, pp. 982–999. ACM Press, June 2012
  25.Xia, L.: Designing social choice mechanisms using machine learning. In: Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems, pp. 471–474. IFAAMAS, May 2013
  26.Xia, L., Conitzer, V.: Determining possible and necessary winners given partial orders. J. Artif. Intell. Res. 41, 25–67 (2011)MathSciNet MATH
  
• 作者单位：Gábor Erdélyi (15)
  Christian Reger (15)
  
  15. University of Siegen, Unteres Schloß 3, 57072, Siegen, Germany
  
• 丛书名：Artificial Intelligence: Methodology, Systems, and Applications
• ISBN：978-3-319-44748-3
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9883

文摘

We study the complexity of possible bribery under nine different notions of partial information for k-\({\mathsf {Approval}}\) and k-\({\mathsf {Veto}}\). In bribery an external agent tries to change the outcome of an election by changing some voters’ votes. Usually in voting theory, full information is assumed, i.e., the manipulative agent knows the set of candidates, the complete ranking of each voter about the candidates and the voting rule used. In this paper, we assume that the briber only has partial information about the voters’ votes and ask whether the briber can change some voters’ votes such that there is a completion of the partial profile to a full profile such that the briber’s preferred candidate (or most despised candidate in the destructive case) is a winner (not a winner) of the resulting election.