Coalition Formation Games: Inner Stability

In this theses, we study a special topic from Cooperative Game Theory which is Hedonic Coalition Formation Games. In a hedonic coalition formation game, there exists finite number of individuals. Every individual only cares about which individuals are in her coalition, but does not care how other individuals are grouped. Every individual has reflexive, anti symmetric, complete, and transitive preferences over the coalitions of which she is a member. The duple, finite set of individuals and preferences of individuals, is called as hedonic coalition formation game, or simply hedonic game. The solution of a hedonic game is partitioning of individuals into disjoint coalitions. The solution is called as coalition structure. When analyzing, comparing, and classifying coalition structures, stability concepts are used. A coalition structure is called stable if and only if no individual or no group of individuals engage in coalition change. There exist several stability concepts in the literature. Most of the study in the literature is about finding the domains (set of hedonic games) in which stable coalition structures exist or unique. Nash stability and core stability are the most predominantly studied stability concepts. However, they do not exist in the full domain, that is the set of all hedonic games. The main reason of the non-existence is, they require a lot from a coalition structure to become stable. In the full domain, they require that a coalition structure should not be blocked by an individual or a group of individuals. When we consider the complement of the domain in which coalition structures are either blocked by an individual or a group of individuals, we find the sub-domain which guarantees the existence of stable coalition structures. However, the complement sub-domain is very tiny. Studying with tiny sub-domains are not satisfactory because we ignore the generality of preferences of individuals. Thus, incoming coalition structures in sub-domains are not representative and natural. In this thesis, we study a new stability concept called inner stability. This stability concept is proposed in order to cure the deficiencies of the core stability and the Nash stability. A coalition structure is called inner stable if and only if there exists no coalition in the given coalition structure and no proper subset of that coalition such that individuals of the proper subset strictly prefer being in that proper subset to being in the coalition. Inner stable coalition structures exist for all hedonic games. Thus, we do not need to restrict preferences of individuals. As a result, stability analyzes become more representative than Nash stability or core stability. In the first chapter, we introduce the model of hedonic game and stability concepts. Then we present the theoretical literature. In addition, we briefly analyze the computational complexity literature. In the second chapter, we introduce the inner stability. We explain the relation of inner stability with other stability concepts. Then, we study the inner algorithm. We give the proof of our main result: In the domain of all hedonic coalition formation games, every coalition structure which is brought out by inner algorithm is always inner stable. In addition, we briefly talk about the computational complexity of the inner algorithm. In the last chapter, we conclude and present some open research questions for future. Lastly, in the appendix, we touch on the domain restrictions that we present in the first chapter. Additionally, we study some real life applications of hedonic games.