Targeted Negative Campaigning: Complexity and Approximations
Authors: Avishai Zagoury, Orgad Keller, Avinatan Hassidim, Noam Hazon5768-5778
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | When the goal is constructive (making a preferred candidate win), we prove that finding such a demotion strategy is easy for Plurality and Veto, while generally hard for t-approval and Borda. We also provide a t-factor approximation for tapproval for every fixed t, and a 3-factor approximation algorithm for Borda. We prove that for t 3, t-approval TNC is NP-hard, but that if t is fixed, it can be approximated in polynomial-time within a factor of t, even when each voter has a different price. The same algorithm can compute the exact solution for the plurality scoring rule. We then show that Borda-TNC is NP-hard as well, and provide a 3-multiplicative approximation to the problem. We also show that if we introduce prices that are a function of both the voter and candidate, then Borda-TNC cannot be approximated within (1 ϵ) ln(m/2 1) unless P = NP, where m is the number of candidates. |
| Researcher Affiliation | Collaboration | Avishai Zagoury,1 Orgad Keller,2 Avinatan Hassidim,1, 2 Noam Hazon 3 1Department of Computer Science, Bar-Ilan University, Israel 2Google Research 3Department of Computer Science, Ariel University, Israel |
| Pseudocode | Yes | Algorithm 1: BTNCRV((C, V ), k, T) and Algorithm 2: TNC for Borda |
| Open Source Code | No | The paper does not provide any statements about releasing open-source code or links to a code repository for the described methodology. |
| Open Datasets | No | The paper is theoretical and focuses on complexity and approximation algorithms for electoral manipulation. It does not conduct empirical experiments, use datasets, or specify public dataset availability. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical validation on datasets, therefore, there are no mentions of training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and describes algorithms and proofs, but it does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper focuses on theoretical complexity and approximation algorithms, not empirical experiments. Therefore, it does not describe experimental setup details such as hyperparameters or training settings. |