  This paper considers the problem of dividing agents among coalitions. We
concentrate on Additively Separable Hedonic Games (ASHG's), in which each agent
has a non-negative value for every other agent and her utility is the sum of
the values she assigns to the members of her coalition. Unlike previous work,
we analyze a model where exactly $k$ coalitions must be formed, and the goal is
to maximize the utility of the agent which is worst off, i.e., the egalitarian
social welfare. We show that this problem is hard, even when the number of
agents should be equally divided among the coalitions. We thus propose a
heuristic that maximizes the egalitarian social welfare and maximizes the
average utility of each agent as a secondary goal. Using extensive simulations,
both on synthetic and real data, we demonstrate the effectiveness of our
approach. Specifically, our heuristic provides solutions that are much fairer
than the solutions that maximize the average social welfare, while still
providing a relatively high average social welfare.
