Algorithmic Complexity of Control in Hedonic Games

Abstract

Die Bildung von Koalitionen spielt eine zentrale Rolle im wirtschaftlichen, politischen und sozialen Leben. Unternehmen schließen strategische Allianzen, politische Parteien bilden Koalitionen zur Regierungsbildung, und Einzelpersonen organisieren sich in Teams, um gemeinsame Ziele zu verfolgen. Koalitionsbildungsspiele werden in der algorithmischen Spieltheorie und in Computational Social Choice umfassend untersucht, insbesondere bieten Hedonic Games einen bedeutenden Rahmen zur Modellierung dafür. In Hedonic Games haben Agenten Präferenzen über Koalitionen (Teilmengen von Agenten), denen sie angehören, und das Ziel besteht darin, die Agenten in disjunkte Koalitionen zu partitionieren, sodass die resultierende Partition bestimmte Stabilitätskriterien erfüllt. Diese Diplomarbeit erweitert Hedonic Games durch die Einführung eines Kontrollframeworks in Hedonic Games. In diesem Kontrollframework hat ein externer Akteur die Möglichkeit, den Koalitionsbildungsprozess durch das Hinzufügen oder Entfernen von Agenten zu beeinflussen, um folgende Kontrollziele in einer stabilen Partition zu erreichen: (1) sicherzustellen, dass ein bestimmter Agent nicht allein ist, (2) sicherzustellen, dass ein bestimmtes Paar von Agenten derselben Koalition angehört, oder (3) sicherzustellen, dass alle Agenten in einer einzigen Grand Coalition enthalten sind. Wir analysieren das Kontrollframework unter drei Settings von Hedonic Games mit kompakten Präferenzkodierungen: Hedonic Games mit freundschaftsorientierten Präferenzen (FriHG), feindschaftsorientierten Präferenzen (EneHG) und additiv separablen Präferenzen (AddHG), kombiniert mit vier weit verbreiteten Stabilitätskriterien, die eine Partition der Agenten erfüllen soll: individuelle Rationalität, individuelle Stabilität, Nash-Stabilität und Kernstabilität. Wir führen eine detaillierte klassische Komplexitätsanalyse durch und liefern eine vollständige Klassifikation der resultierenden Kontrollprobleme hinsichtlich polynomieller Lösbarkeit und NP-Schwere. Darüber hinaus untersuchen wir deren parametrisierte Komplexität bezüglich problemspezifischer Parameter, wie der Anzahl erlaubter Aktionen und der maximalen Anzahl von Freunden eines Agenten, sowie die Komplexität eingeschränkter Instanzklassen. Für FriHG präsentieren wir mehrere polynomielle Algorithmen zur Lösung der entsprechenden Kontrollprobleme. Für EneHG und AddHG erweisen sich die meisten dieser Kontrollprobleme als NP-schwer, und wir geben Reduktionen von bekannten NP-schweren Problemen an, die die NP-Schwere der Kontrollprobleme zeigen. In EneHG zeigen wir jedoch einen FPT-Algorithmus, der bezüglich der maximalen Anzahl von Freunden eines Agenten parametrisiert ist und aus dem sich mehrere XP-Algorithmen ableiten lassen.

Forming coalitions plays a central role in economic, political, and social life. Companies form strategic alliances, political parties join coalitions to form governments, and individuals organize themselves into teams to pursue common goals. Coalition formation games are extensively studied in algorithmic game theory and computational social choice. In particular, hedonic games provide a prominent framework for modeling coalition formation problems. In hedonic games, agents have preferences over coalitions (i.e., subsets of agents) they belong to, and the goal is to partition the set of agents into disjoint coalitions such that the resulting partition satisfies certain stability notions. This thesis extends the study of hedonic games by introducing a control framework for hedonic games. In this control framework, an external actor can influence the coalition formation process by adding or deleting agents in order to achieve certain control goals in a stable partition: (1) ensuring a certain agent is not alone, (2) ensuring a specific pair of agents is in the same coalition, or (3) ensuring all agents are in the same grand coalition. We analyze this control framework under three hedonic game settings with compact preference encodings: hedonic games with friend-oriented preferences (FriHG), enemy-oriented preferences (EneHG), and additively separable preferences (AddHG), together with four widely used stability notions that a partition of agents should satisfy: individual rationality, individual stability, Nash stability, and core stability. We conduct a classical computational complexity analysis and provide a complete complexity classification of the resulting control problems with respect to polynomial-time solvability and NP-hardness. In addition, we investigate their parameterized complexity with respect to problem-specific parameters, such as the number of allowed actions and the maximum number of friends of an agent, as well as the complexity of restricted classes of instances. For FriHG, we present several polynomial-time algorithms for solving the corresponding control problems. For EneHG and AddHG, most of these control problems turn out to be computationally intractable, and we provide hardness reductions from well-known NP-hard problems. However, for EneHG we develop an FPT algorithm with respect to the maximum number of friends of an agent, from which we derive several XP algorithms.