Subordinated Hedonic Games

Hedonic games are simple models of coalition formation whose main solution concept is that of core partition. Several conditions guaranteeing the existence of core partitions have been proposed so far. In this paper, we explore hedonic games where a reduced family of coalitions determines the development of the game. We allow each coalition to select a subset of it so as to act as its set of representatives (a distribution). Then, we introduce the notion of subordination of a hedonic game to a given distribution. Subordination roughly states that any player chosen as a representative for a coalition has to be comfortable with this decision. With subordination we have a tool, within hedonic games, to compare how a “convenient” agreement reached by the sets of representatives of different groups of a society is “valued” by the rest of the society. In our approach, a “convenient” agreement is a core partition, so this paper is devoted to relate the core of a hedonic game with the core of a hedonic game played by the sets of representatives. Thus we have to tackle the existence problem of core partitions in a reduced game where the only coalitions that matter are those prescribed by the distribution as a set of representatives. We also study how a distribution determines the whole set of core partitions of a hedonic game. As an interesting example, we introduce the notion of hedonic partitioning game, which resembles partitioning games studied in the case where a utility, transferable or not, is present. The existence result obtained in this new class of games is later used to provide a nonconstructive proof of the existence of a stable matching in the marriage model. 1. Introduction Coalitional games are models which take into account the interaction between the players of the game. In general, any subgroup of players (a coalition) can influence the result of the game. However, it has been recognized that, sometimes, some of the coalitions can completely determine the development of the game. In their seminal paper, Kaneko and Wooders [1] introduce the class of partitioning games as a way to capture the fact that “In an -cooperative game it may not be equally easy to form every coalition.” In those games, only a subset of coalitions play such an essential role that determines the behavior of all the other coalitions. This characteristic is shared for several of the games studied in the literature such as the marriage game [2], the bridge game [3], the assignment game [4], and the m-sided assignment game [5] among others. Kaneko and Wooders [1] present a