On coalition formation: durable coalition structures. (Q1398328)

A hedonic game consists of a finite set of players and, for each one of them, a preference relation (complete preordering) on the set of coalitions to which the player belongs. The concept is hereditary for subsets of players. A coalition structure (CS, in the sequel) is a partition of the player set. By induction on the number of players, the notion of durable CS is introduced. To this end, the key idea is the disruption of a CS by means of some coalitions, a process that leads to other CSs and can be iterated. It naturally gives rise to speak of transient or (oppositely) durable CSs. Although rigorously formalized, the topic admits a helpful intuitive view. The main results are the following. (a) From any transient CS a durable one can be always obtained, and this guarantees the existence of some durable CS for any hedonic game. (b) All core CSs are durable, and all durable CSs are individually rational -no player strictly prefers being alone instead of the coalition he belongs to in the given CS. (c) If there is just one durable CS, it is the only member of the core of the hedonic game; for example, this is the case if the top-coalition property is satisfied and preferences are strict. Interesting numerical examples are also provided. Cases with empty core or where the core is nonempty but a strict subset of the set of durable CSs and, especially, three detailed samples of one-to-one and many-to-one matching problems, which are interpreted as hedonic games by assuming that all unfeasible coalitions are not individually rational.