OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

The Complexity of Bribery in Network-Based Rating Systems

Grandi, Umberto and Stewart, James and Turrini, Paolo The Complexity of Bribery in Network-Based Rating Systems. (2018) In: Thirty-Second AAAI Conference on Artificial Intelligence (AAAI 2018), 2 February 2018 - 7 February 2018 (New Orleans, United States).

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: https://aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/17201


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.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Association for the Advancement of Artificial Intelligence
HAL Id:hal-03621486
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > University of Warwick (UNITED KINGDOM)
Other partners > Imperial College London (UNITED KINGDOM)
Laboratory name:
Deposited On:26 Mar 2019 11:11

Repository Staff Only: item control page