  We consider cost allocation for set covering problems. We allocate as much
cost to the elements (players) as possible without violating the group
rationality condition (no subset of players pays more than covering this subset
would cost), and so that the excess vector is lexicographically maximized. This
is identical to the well-known nucleolus if the core of the corresponding
cooperative game is nonempty, i.e., if some optimum fractional cover is
integral. In general, we call this the 'happy nucleolus'. Like for the
nucleolus, the excess vector contains an entry for every subset of players, not
only for the sets in the given set covering instance. Moreover, it is NP-hard
to compute a single entry because this requires solving a set covering problem.
Nevertheless, we give an explicit family of at most $mn$ subsets, each with a
trivial cover (by a single set), such that the happy nucleolus is always
completely determined by this proxy excess vector; here $m$ and $n$ denote the
number of sets and the number of players in our set covering instance. We show
that this is the unique minimal such family in a natural sense. While computing
the nucleolus for set covering is NP-hard, our results imply that the happy
nucleolus can be computed in polynomial time.
