Fine-Grained View on Bribery for Group Identification

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F20%3A00341907" target="_blank" >RIV/68407700:21240/20:00341907 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.24963/ijcai.2020/10" target="_blank" >https://doi.org/10.24963/ijcai.2020/10</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.24963/ijcai.2020/10" target="_blank" >10.24963/ijcai.2020/10</a>

Result language

angličtina

Original language name

Fine-Grained View on Bribery for Group Identification

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Research Center for Informatics</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2020

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence

ISBN

978-0-9992411-6-5

ISSN

—

e-ISSN

—

Number of pages

7

Pages from-to

67-73

Publisher name

International Joint Conferences on Artificial Intelligence Organization

Place of publication

—

Event location

Yokohama

Event date

Jul 11, 2020

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—