The Complexity of Bribery in Network-Based Rating Systems
Abstract
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.
Cite
Text
Grandi et al. "The Complexity of Bribery in Network-Based Rating Systems." AAAI Conference on Artificial Intelligence, 2018. doi:10.1609/AAAI.V32I1.11474Markdown
[Grandi et al. "The Complexity of Bribery in Network-Based Rating Systems." AAAI Conference on Artificial Intelligence, 2018.](https://mlanthology.org/aaai/2018/grandi2018aaai-complexity/) doi:10.1609/AAAI.V32I1.11474BibTeX
@inproceedings{grandi2018aaai-complexity,
title = {{The Complexity of Bribery in Network-Based Rating Systems}},
author = {Grandi, Umberto and Stewart, James and Turrini, Paolo},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2018},
pages = {1047-1054},
doi = {10.1609/AAAI.V32I1.11474},
url = {https://mlanthology.org/aaai/2018/grandi2018aaai-complexity/}
}