The Complexity of Bribery in Network-Based Rating Systems

2018-02-08

Proceedings of the AAAI Conference on Artificial Intelligence, 32

Volume

Thirty-Second AAAI Conference on Artificial Intelligence 2018

AAAI Technical Track: Game Theory and Economic Paradigms

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.

10.1609/aaai.v32i1.11474