The Complexity of Bribery in Network-Based Rating Systems
Authors: Umberto Grandi, James Stewart, Paolo Turrini
AAAI 2018 | Conference PDF | Archive PDF | Plain Text | 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 umberto.grandi@irit.fr James Stewart Imperial College London United Kingdom james.stewart13@imperial.ac.uk Paolo Turrini University of Warwick United Kingdom p.turrini@warwick.ac.uk |
| 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. |