Date
2020
Dewey
Recherche opérationnelle
Sujet
Computational Social Choice; Cooperative Games
Conference name
Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence
Conference date
2020
Conference country
JAPAN
Book title
Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}
Author
Christian Bessiere
Publisher
IJCAI
ISBN
978-0-9992411-6-5
Author
Allouche, Tahar
Escoffier, Bruno
Moretti, Stefano
Ozturk, Meltem
Type
Communication / Conférence
Item number of pages
17-23
Abstract (EN)
We investigate the issue of manipulability for social ranking rules, where the goal is to rank individuals given the ranking of coalitions formed by them and each individual prefers to reach the highest positions in the social ranking. This problem lies at the intersection of computational social choice and the algorithmic theory of power indices. Different social ranking rules have been recently proposed and studied from an axiomatic point of view. In this paper, we focus on rules representing three classical approaches in social choice theory: the marginal contribution approach, the lexicographic approach and the (ceteris paribus) majority one. We first consider some particular members of these families analysing their resistance to a malicious behaviour of individuals. Then, we analyze the computational complexity of manipulation, and complete our theoretical results with simulations in order to analyse the manipulation frequencies and to assess the effects of manipulations.