[edit]

# Noise Robust Core-stable Coalitions of Hedonic Games

*Proceedings of The 14th Asian Conference on Machine Learning*, PMLR 189:1038-1053, 2023.

#### Abstract

In this work, we consider the coalition formation
games with an additional component, ‘noisy
preferences’. Moreover, such noisy preferences are
available only for a sample of coalitions. We
propose a multiplicative noise model (equivalent to
an additive noise model) and obtain the prediction
probability, defined as the probability that the
estimated PAC core-stable partition of the
\emph{noisy} game is also PAC core-stable for the
\emph{unknown noise-free} game. This prediction
probability depends on the probability of a
combinatorial construct called an ‘agreement
event’. We explicitly obtain the agreement
probability for $n$ agent noisy game with $l\geq 2$
support noise distribution. For a user-given
satisfaction value on this probability, we identify
the noise regimes for which an estimated partition
is noise robust; that is, it is PAC core-stable in
both the noisy and noise-free games. We obtain
similar robustness results when the estimated
partition is not PAC core-stable. These noise
regimes correspond to the level sets of the
agreement probability function and are non-convex
sets. Moreover, an important fact is that the
prediction probability can be high even if high
noise values occur with a high probability. Further,
for a class of top-responsive hedonic games, we
obtain the bounds on the extra noisy samples
required to get noise robustness with a user-given
satisfaction value. We completely solve the noise
robustness problem of a $2$ agent hedonic game. In
particular, we obtain the prediction probability
function for $l=2$ and $l=3$ noise support
cases. For $l=2$, the prediction probability is
convex in noise probability, but the noise robust
regime is non-convex. Its minimum value, called the
safety value, is 0.62; so, below 0.62, the noise
robust regime is the entire probability
simplex. However, for $l \geq 3$, the prediction
probability is non-convex; so, the safety value is
the global minima of a non-convex function and is
computationally hard.