Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Elections with Few Voters: Candidate Control Can Be Easy
Authors: Jiehua Chen, Piotr Faliszewski, Rolf Niedermeier, Nimrod Talmon
JAIR 2017 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the computational complexity of candidate control in elections with few voters, that is, we consider the parameterized complexity of candidate control in elections with respect to the number of voters as a parameter. We consider both the standard scenario of adding and deleting candidates, where one asks whether a given candidate can become a winner (or, in the destructive case, can be precluded from winning) by adding or deleting few candidates, as well as a combinatorial scenario where adding/deleting a candidate automatically means adding or deleting a whole group of candidates. Considering several fundamental voting rules, our results show that the parameterized complexity of candidate control, with the number of voters as the parameter, is much more varied than in the setting with many voters. ... Our W[1]-hardness results follow via reductions from the W[1]-complete Multi Colored Clique problem ... Our FPT algorithms also have a fairly universal structure and are based on what we call the Signature Proof Technique. |
| Researcher Affiliation | Academia | Jiehua Chen EMAIL Ben-Gurion University of the Negev, Israel Piotr Faliszewski EMAIL AGH University of Science and Technology, Poland Rolf Niedermeier EMAIL TU Berlin, Germany Nimrod Talmon EMAIL Weizmann Institute of Science, Israel |
| Pseudocode | Yes | ALGORITHM 1: FPT algorithm for t-Approval-DCDC. ((C, V ), d, k) input: an instance of t-Approval-DCDC p a guessed candidate who is to defeat d 1 foreach δ = (δ1, δ2, . . . , δn) [4]n with |{i | δi = 1}| < |{i | δi = 2}| do 2 Run ILP for each sane δ such that p beats d. 3 foreach i [n] do 4 if Sanity Check (δi) = false then 6 if p has more points than d when p and d receive points as described by δ and there is a solution for ILP ( δ) then 9 Sanity Check(δi) 10 if δi = 1 and (vi : p d) then 11 δi = 1: only d gains one point. 12 return false; 13 if δi = 2 and (vi : d p) then 14 δi = 2: only p gains one point. 15 return false; 16 return true; 17 ILP( δ = (δ1, δ2, . . . , δn)): 18 Variables 19 γ [3]n : x γ # deleted candidates with {d, p}-signature γ 20 Constants 21 γ [3]n : z γ # existing candidates with {d, p}-signature γ 22 Constraints γ x γ k γ [3]n : x γ z γ 25 if δi = 1 or δi = 2 then 26 vi : d p and only d gains one point, or 27 vi : p d and only p gains one point γ:γi=3(z γ x γ) t 1 γ:γi=3 γi=2(z γ x γ) t 1 30 else if δi = 3 then 31 Both d and p gain one point each γ:γi=3 γi=2(z γ x γ) + 2 t 34 No one gains one point γ:γi=3(z γ x γ) t |
| Open Source Code | No | The paper does not contain any explicit statement about the release of source code or a link to a code repository. |
| Open Datasets | No | The paper is theoretical and focuses on computational complexity. It does not refer to or use any public or open datasets for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and focuses on computational complexity. It does not perform empirical evaluations on datasets, therefore, the concept of dataset splits is not applicable. |
| Hardware Specification | No | The paper is theoretical and focuses on computational complexity. It does not describe any experimental setup or report on experiments run on specific hardware. |
| Software Dependencies | No | The paper is theoretical and focuses on computational complexity. It discusses algorithms and integer linear programming conceptually but does not mention specific software dependencies or their version numbers for implementation. |
| Experiment Setup | No | The paper is theoretical and focuses on computational complexity. It does not describe an experimental setup or provide details on hyperparameters or training configurations. |