Fine-Grained View on Bribery for Group Identification
Niclas Boehmer, Robert Bredereck, Dušan Knop, Junjie Luo
Abstract
Given a set of individuals qualifying or disqualifying each other, group identification is the task of identifying a socially qualified subgroup of individuals. Social qualification depends on the specific rule used to aggregate individual qualifications. The bribery problem in this context asks how many agents need to change their qualifications in order to change the outcome. Complementing previous results showing polynomial-time solvability or NP-hardness of bribery for various social rules in the constructive (aiming at making specific individuals socially qualified) or destructive (aiming at making specific individuals socially disqualified) setting, we provide a comprehensive picture of the parameterized computational complexity landscape. Conceptually, we also consider a more fine-grained concept of bribery cost, where we ask how many single qualifications need to be changed, and a more general bribery goal that combines the constructive and destructive setting.
BibTeX
@inproceedings{ijcai2020p10,
title = {Fine-Grained View on Bribery for Group Identification},
author = {Boehmer, Niclas and Bredereck, Robert and Knop, Dušan and Luo, Junjie},
booktitle = {Proceedings of the Twenty-Ninth International Joint Conference on
Artificial Intelligence, {IJCAI-20}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Christian Bessiere},
pages = {67--73},
year = {2020},
month = {7},
note = {Main track},
doi = {10.24963/ijcai.2020/10},
url = {https://doi.org/10.24963/ijcai.2020/10},
}