Fine-Grained View on Bribery for Group Identification

Boehmer, Niclas; Bredereck, Robert; Knop, Dušan; Luo, Junjie

doi:10.24963/ijcai.2020/10

Fine-Grained View on Bribery for Group Identification

Niclas Boehmer, Robert Bredereck, Dušan Knop, Junjie Luo

Video Download BibTeX Cite

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. Main track. Pages 67-73.

https://doi.org/10.24963/ijcai.2020/10

Keywords

Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Voting

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.

Niclas Boehmer, Robert Bredereck, Dušan Knop, and Junjie Luo. 2020. Fine-Grained View on Bribery for Group Identification. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20. IJCAI, 67–73. https://doi.org/10.24963/ijcai.2020/10

@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},
}

TY  - CPAPER
TI  - Fine-Grained View on Bribery for Group Identification
AU  - Boehmer, Niclas
AU  - Bredereck, Robert
AU  - Knop, Dušan
AU  - Luo, Junjie
T2  - Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2020
SP  - 67
EP  - 73
DO  - 10.24963/ijcai.2020/10
UR  - https://doi.org/10.24963/ijcai.2020/10
ER  -