Learning Hedonic Games

Coalitional stability in hedonic games has usually been considered in the setting where agent preferences are fully known. We consider the setting where agent preferences are unknown; we lay the theoretical foundations for studying the interplay between coalitional stability and (PAC) learning in hedonic games. We introduce the notion of PAC stability - the equivalent of core stability under uncertainty - and examine the PAC stabilizability and learnability of several popular classes of hedonic games.