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; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1]
Approximating Weighted and Priced Bribery in Scoring Rules
Authors: Orgad Keller, Avinatan Hassidim, Noam Hazon
JAIR 2019 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We provide an approximate solution for these problems for a broad family of scoring rules (which includes Borda, t-approval, and Dowdall), in the following sense: for constant weights and prices, if there exists a strategy which costs Ψ, we efficiently find a strategy which costs at most Ψ + e O(Ψ). An extension for non-constant weights and prices is also given. Our algorithm is based on a randomized reduction from these Bribery generalizations to weighted coalitional manipulation (WCM). To solve this WCM instance, we apply the Birkhoff-von Neumann (Bv N) decomposition to a fractional manipulation matrix. This allows us to limit the size of the possible ballot search space reducing it from exponential to polynomial, while still obtaining good approximation guarantees. Finding a solution in the truncated search space yields a new algorithm for WCM, which is of independent interest. The paper contains several algorithms (Algorithm 1, 2, 3, 4) and mathematical proofs (Lemmas 1, 3, 6, 8-21, Theorems 2, 5, 7, 22-24). |
| Researcher Affiliation | Academia | Orgad Keller EMAIL Department of Computer Science, Bar-Ilan University, Israel Avinatan Hassidim EMAIL Department of Computer Science, Bar-Ilan University, Israel Noam Hazon EMAIL Department of Computer Science, Ariel University, Israel |
| Pseudocode | Yes | The paper includes clearly labeled algorithm blocks: "Algorithm 1: Min-margin-SR-WCM approximation algorithm", "Algorithm 2: SR-Weighted-$Bribery approximation algorithm", "Algorithm 3: Closing the gap for constant scoring rules", and "Algorithm 4: Closing the gap for non-concentrated scoring rules". |
| Open Source Code | No | The paper does not provide any specific link to a code repository, an explicit statement of code release, or mention of code in supplementary materials. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and approximation guarantees for abstract election scenarios. It does not describe or use any specific datasets, public or otherwise, for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments on datasets, therefore no dataset splits are provided. |
| Hardware Specification | No | The paper is theoretical and does not report on empirical experiments. Therefore, no hardware specifications for running experiments are provided. |
| Software Dependencies | No | The paper mentions solving an LP (Karmarkar, 1984) and finding a bipartite maximum matching (Hopcroft & Karp, 1973), which are theoretical references to algorithms rather than specific software packages with version numbers used for implementation. |
| Experiment Setup | No | The paper is theoretical and does not report on empirical experiments. Therefore, no specific experimental setup details like hyperparameters or training configurations are provided. |