Weighted Electoral Control
Authors: Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra
JAIR 2015 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we study the complexity of controlling the outcome of weighted elections through adding and deleting voters. We obtain polynomial-time algorithms, NP-completeness results, and for many NP-complete cases, approximation algorithms. In particular, for scoring rules we completely characterize the complexity of weighted voter control. |
| Researcher Affiliation | Academia | Piotr Faliszewski EMAIL Department of Computer Science AGH University of Science and Technology Krakow, Poland Edith Hemaspaandra EMAIL Department of Computer Science Rochester Institute of Technology Rochester, NY 14623, USA Lane A. Hemaspaandra EMAIL Department of Computer Science University of Rochester Rochester, NY 14627, USA |
| Pseudocode | Yes | Algorithm 1: 2-approval-WCCAV Input: (C, V, W, p, k) forall c C {p} do let sc = score(C,V)(c) score(C,V)(p). Delete from W all voters that do not approve of p. repeat forall c C {p} do if the sum of the weights of the k heaviest voters in W that do not approve of c is less than sc then reject // It is impossible to get score(c) score(p) by adding less than or equal to k voters from W. forall c C {p} and ℓ {1, . . . , k 1} do if the sum of the weights of the k ℓ heaviest voters in W that do not approve of c is less than sc then delete from W all voters approving c except for the ℓ 1 heaviest such voters. // We need to add at least k ℓ + 1 voters that do not approve of c, and so we can add at most ℓ 1 voters approving c. until no more changes. if W k then accept // We can make p a winner by adding the k heaviest voters from W. if W < k then if adding all of W will make p a winner then accept else reject |
| Open Source Code | No | The paper discusses theoretical complexity results and algorithms, but there is no explicit statement about releasing source code or a link to a code repository for the methodologies described. |
| Open Datasets | No | The paper focuses on theoretical complexity analysis and the design of algorithms for weighted electoral control, using abstract constructions of election instances for proofs and examples. It does not mention or use any publicly available or open datasets for empirical evaluation. |
| Dataset Splits | No | The paper does not conduct experiments on empirical datasets, and therefore, there is no mention of dataset splits like training, validation, or test sets. |
| Hardware Specification | No | The paper focuses on theoretical computer science, analyzing the complexity of algorithms and voting systems. It does not report on experimental results that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical in nature, presenting algorithms and complexity results rather than implementations or experimental evaluations. As such, it does not list any specific software dependencies or version numbers. |
| Experiment Setup | No | The paper is focused on theoretical complexity analysis and algorithm design. It does not include an experimental section or describe any experimental setup, hyperparameter values, or system-level training settings. |