Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Institut für Informatik

Verteidigung Masterarbeit: Maximilian Joecks

Adjusting Group Identification Towards Non-Binary Decisions

Die Verteidigung findet digital via Zoom statt. Die Zugangsdaten teilt Prof. Kratsch auf Anfrage gern mit.

Robert Bredereck (jetzt TU Clausthal)


For the Group Identification problem we are given a set of individuals and have the task of identifying a socially qualified group amongst them. Additionally, each individual has opinions about the other individuals on whether they should be socially qualified. A social rule is then used to aggregate these opinions into a decision of social qualifications for each individual. There are several different social rules that can be used for this aggregation.
However, all the commonly researched social rules share a common weakness: They do not allow the shaping of the socially qualified groups according to some desired metrics. Furthermore they always result in a fixed binary decision of group membership for each individual. We might however, want a group of specific size or identify multiple distinct subgroups or desire a smaller group compare to what the rules naturally result in. For this purpose, we study the iteration in which an individual becomes socially qualified as a differentiator for some of the social rules and introduce the margin of victory as a differentiator between individuals.
In the recent literature, manipulate attacks against group identification rules and their complexity were examined. In a manipulative attack an attacker can manipulate the outcome of a social rule towards a desired objective by way of manipulative attacks. We adapt this concept and introduce two new bribery attacks against group identification rules: The so called property-pursuing bribery attacks. The two properties we examine are the group size and the number of distinct subgroups. We provide a theoretical complexity analysis of these attacks for our rules and examine their effect on synthetic social network data.