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].
Control by Adding or Deleting Edges in Graph-Restricted Weighted Voting Games
Authors: Joanna Kaczmarek, Jörg Rothe, Nimrod Talmon
JAIR 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We model these settings by graph-restricted weighted voting games and study the computational problems of control by adding or deleting edges in the underlying communication structure. In particular, we consider two classical power indices, namely the Shapley Shubik (SSI) and the probabilistic Penrose Banzhaf index (PBI). For each of these power indices, we study the complexity of controlling the power of players via an alteration of the graph. Our hardness results (i.e., the lower bounds for the related computational problems) are summarized in Table 1 (for control by adding edges) and Table 2 (for control by deleting edges). |
| Researcher Affiliation | Academia | Joanna Kaczmarek EMAIL J org Rothe EMAIL Heinrich-Heine-Universit at D usseldorf MNF, Institut f ur Informatik Universit atsstraße 1, 40225 D usseldorf, Germany. Nimrod Talmon EMAIL Ben-Gurion University of the Negev Department of Industrial Engineering and Management Beer Sheva blvd 1, 84105 Beer Sheva, Israel |
| Pseudocode | No | The paper describes algorithms conceptually through theorems and proofs related to computational complexity but does not present any formal pseudocode blocks or algorithms. |
| Open Source Code | No | The paper does not contain any explicit statement about code availability for the methodology described, nor does it provide any links to a code repository. |
| Open Datasets | No | The paper uses real-world examples (e.g., 36th Israeli government, 2021 Israeli elections) to illustrate concepts but does not conduct experiments on, or provide access information for, any specific open datasets. |
| Dataset Splits | No | Since the paper is theoretical and focuses on computational complexity analysis rather than empirical studies, there is no mention of dataset splits for training, validation, or testing. |
| Hardware Specification | No | As a theoretical paper focusing on computational complexity and proofs, it does not describe any experimental setup that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and describes computational complexity problems and proofs; therefore, no software dependencies with version numbers are listed for experimental replication. |
| Experiment Setup | No | The paper is theoretical and focuses on complexity analysis, theorems, and proofs, thus it does not include details on experimental setup, hyperparameters, or training configurations. |