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 Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
The Complexity of Bribery in Network-Based Rating Systems
Authors: Umberto Grandi, James Stewart, Paolo Turrini
AAAI 2018 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the complexity of bribery in a network-based rating system, where individuals are connected in a social network and an attacker, typically a service provider, can influence their rating and increase the overall profit. We derive a number of algorithmic properties of this framework, in particular we show that establishing the existence of an optimal manipulation strategy for the attacker is NP-complete, even with full knowledge of the underlying network structure. We establish that even when the attacker has full knowledge of the network the problem of determining the existence of a manipulation strategy guaranteeing at least a given reward and, notably, an optimal one is NP-complete. We do so by giving a polynomial-time reduction from the problem of finding an independent set of a given size k in a 3-regular graph. |
| Researcher Affiliation | Academia | Umberto Grandi University of Toulouse France EMAIL James Stewart Imperial College London United Kingdom EMAIL Paolo Turrini University of Warwick United Kingdom EMAIL |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. Algorithmic ideas are described in natural language. |
| Open Source Code | No | The paper does not provide any concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not use or provide access to any publicly available or open dataset for training. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical validation, therefore, it does not provide specific dataset split information for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments, thus no specific hardware details are provided for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not describe experiments, thus no specific ancillary software details with version numbers are provided. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with specific hyperparameters or training configurations. |