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.

Erstbetreuer:
Robert Bredereck (jetzt TU Clausthal)

Abstract:

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.