Timezone: »

$\varepsilon$-fractional core stability in Hedonic Games.
Simone Fioravanti · Michele Flammini · Bojana Kodric · Giovanna Varricchio

Wed Dec 13 08:45 AM -- 10:45 AM (PST) @ Great Hall & Hall B1+B2 #1712
Hedonic Games (HGs) are a classical framework modeling coalition formation of strategic agents guided by their individual preferences. According to these preferences, it is desirable that a coalition structure (i.e. a partition of agents into coalitions) satisfies some form of stability. The most well-known and natural of such notions is arguably core-stability. Informally, a partition is core-stable if no subset of agents would like to deviate by regrouping in a so-called core-blocking coalition. Unfortunately, core-stable partitions seldom exist and even when they do, it is often computationally intractable to find one. To circumvent these problems, we propose the notion of $\varepsilon$-fractional core-stability, where at most an $\varepsilon$-fraction of all possible coalitions is allowed to core-block. It turns out that such a relaxation may guarantee both existence and polynomial-time computation. Specifically, we design efficient algorithms returning an $\varepsilon$-fractional core-stable partition, with $\varepsilon$ exponentially decreasing in the number of agents, for two fundamental classes of HGs: Simple Fractional and Anonymous. From a probabilistic point of view, being the definition of $\varepsilon$-fractional core equivalent to requiring that uniformly sampled coalitions core-block with probability lower than $\varepsilon$, we further extend the definition to handle more complex sampling distributions. Along this line, when valuations have to be learned from samples in a PAC-learning fashion, we give positive and negative results on which distributions allow the efficient computation of outcomes that are $\varepsilon$-fractional core-stable with arbitrarily high confidence.

Author Information

Simone Fioravanti (Gran Sasso Science Institute (GSSI))
Michele Flammini (Gran Sasso Science Institute)
Michele Flammini

My research interests include algorithms and computational complexity, game theory, artificial intelligence, optimization problems in distributed systems and communication networks I authored and co-authored more than 170 papers in my fields of interest, published in the most reputed international conferences and journals. Moreover, I served as program chair, member of program committees, guest editor and reviewer for several prestigious international conferences and journals in my fields of interest. I maintain scientific collaborations with the most important national and international research centers. I also have been principal investigator of several joint research projects and technological innovation projects with companies and local authorities. I'm co-founder of the academic spin-off Gunpowder S.r.l..

Bojana Kodric (Ca' Foscari University of Venice)
Giovanna Varricchio (Johann Wolfgang Goethe Universität Frankfurt am Main)

More from the Same Authors