The Complexity of Bribery in Network-Based Rating Systems

Authors

  • Umberto Grandi University of Toulouse
  • James Stewart Imperial College London
  • Paolo Turrini University of Warwick

Keywords:

Rating-Systems, Bribery, Complexity

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.

Downloads

Published

2018-04-25

How to Cite

Grandi, U., Stewart, J., & Turrini, P. (2018). The Complexity of Bribery in Network-Based Rating Systems. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/11474

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms