$\varepsilon$-fractional core stability in Hedonic Games.
Authors: Simone Fioravanti
Michele Flammini
Bojana Kodric
Giovanna Varricchio
Venue: NeurIPS 2023 poster (2023)
Keywords: Game Theory
Hedonic Games
Core stability
Coalition Formation
Social Choice
PAC learning

Abstract: 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.

e-fractional core stability in Hedonic Games
Simone Fioravanti'
Michele Flammini!. Bojana Kodric
Giovanna Varricchio
Gran Sasso Science Institute (GSSI), L'Aquila, Italy University of Calabria, Rende, Italy
Ca' Foscari University of Venice, Venice, Italy
Univer--tii,,,iiät,, Frankfurt am Main, Germany
{simone fioravanti, michele fl fll.mmmmim@@gss.iii
jojana. kodricuunive...omm ii
Abstract
Hedonic Games (HGs) are a classical framework modeling coalition formation strategic agents guided by their individual preferences. According to these preferences, it is desirable that coalition structure (i.e. partition of agents into coalitions) satisfies some form of stability. The most well-known and natural such notions is arguably core-stability. Informally, partition is core-stable if no subset of agents would like to deviate by regrouping in a so-called core- bore-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 e-fractional core-stability, where at most e-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 e-fractional core-stable partition, with e 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 e-fractional core equivalent requiring that uniformly sampled coalitions core-block with probability lower than we further extend the definition 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 e-fractional core-stable with arbitrarily high confidence.
Introduction
Game-theoretic models of coalition formation have drawn significant interest in the last years, because of their ability to capture meaningful properties multi-agent interactions. In Hedonic Games (HGs) 2 [6] agents gather together without any form of externality, that is only minding the internal composition of their groups. A solution is then a partition the agents (or coalition structure) having some desirable properties, which typically stand for stability against some kinds of deviations. Among the many notions existing in the literature, one of the most fundamental is stability [10 31] A partition is said to be core-stable or in the core if no subset of agents would benefit by regrouping and forming so-called core-blocking coalition. Unfortunately. while being a quite natural requirement, is notably very difficult achieve [5] 25 even under the usual unrealistic assumption of full knowledge of agents' preferences. Furthermore, for the few classes of HGs in which the non-emptiness of the core has been established, stable partition is usually hard compute. Nonetheless, due to its significance, it is still desirable to find an approximation of the core.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

The core was first considered in the setting of cooperative game theory, where the value of a coalition has to be allocated fairly between its members. In this scenario, the most well-known approximation to the core is the so-called strong e-core (26). in which a blocking coalition increases the total value allocated to its members by at least E. A derived notion is the one of least-core [22]. i.e. the (strong) e-core associated to the smallest possible value of e guaranteeing its existence. An adaptation of these concepts to the context of HGs has been proposed in [17. where the authors define k-improvement core stability, requiring each member of blocking coalition to increase her utility by multiplicative factor strictly greater than k 2 1. The same authors also propose to bound by a value q Z 2 the number of agents allowed to form blocking coalition, obtaining what they call q-size core stability.
However, the above stability concepts might still be fragile, especially when many coalitions could anyway benefit by deviating, even if not consistently according to the approximation/sizz factors. In fact, agents might be still inclined to subtle improvements. Interestingly, works like [[I]] experimen- tally show that, sampling random HGs, the fraction of instances with an empty core is small and decreases significantly as the number of agents increases. This could be related to the fact that, even in the instances with empty core, many or almost all the coalitions do not core-block. Consequently, the existence of outcomes having a relatively small number of blocking coalitions appears plausible.
In this work, we investigate the concept of s-fractional core-stable partitions, i.e. partitions that can be wore-blocked by only an E-fraction of all possible coalitions. This notion bears some similarities with FAC-stabilizabiiity as defined in [27]. In this work, the authors lifted for the first time the assumption of complete information HGs and considered learning preferences and core-stable partitions from samples, employing the probably approximately correct (PAC) learning framework [.)). Specifically, possible to
an HGs class PAC stabilizable if, after seeing a certain number of samples, either determine that the core is empty or to return a partition that has probability at most E to be core-blocked by a coalition sampled from the same distribution.
Our Contribution. In this paper, we introduce and study the e-fractional core stability notion in Hedonic Games. We specifically investigate this concept on two of the most fundamental classes of HGs: Simple fractional and anonymous HGs.
Roughly speaking partition of agents is e- c-fractional core-stable, E-FC in short, if at most fraction of coalitions may core-block it. Such a definition has a natural probabilistic interpretation: Indeed, for s-FC partition, é represents an upper bound the probability of drawing core- blocking coalition uniformly at random. Along this line, we broaden the definition to any distribution over coalitions by requiring that the probability of sampling blocking coalition is at most e. Worth noticing, if E = O, we are essentially requiring our solution to be core stable. Hence it is not possible in general to prove the existence and efficiently compute s-FC outcomes, for values of E that are sufficiently close to O. In contrast, our aim is to efficiently compute s-FC solutions for as small as possible values of e. proving in turn also their existence.
Unfortunately, as a first result, we prove that by allowing arbitrary sampling distributions an E E-FC may fail to exist for constant values of e. On the positive side, for the aforementioned classes of HGs, we show that it is possible to efficiently compute an s-FC solution under the uniform distribution, with sub-ex poneenalolyy small in the number of agents. In particular, in the case of anonymous HGs, we present an algorithm computing an s-FC solution under the class of X-bounded distributions, where the ratio of the probabilities of extracting any two coalitions bounded by the parameter X. Notably, this class includes the uniform distribution as the special case X = 1, and can be considered a suitable extension of it. Our algorithms, besides guaranteeing sub-exponentially small values of E, are designed to handle the possible incomplete knowledge of agents' preferences. In fact, in case preferences are unknown, the algorithms can use the sampling distribution learn them in a PAC-learning fashion while maintaining the very same guarantees on E with high confidence.
2 Related Work
Core stability and Hedonic Games. Hedonic Games have captured considerable research attention from the scientific community over the years. One of the main goals their study is understanding how to gather agents in way they won't desire to modify the outcome. For this reason, several stability notions have been considered and studied such as core and Nash stability, or individual rationality. We refer to 2 for comprehensive overview of the subject. Core stability is fundamental

---

concept in multi-agen agent systems, first considered in the context of cooperative games 13 properties and the related complexity have been largely investigated in HGs I
19
Its and
IO
25
23
beyond, such as in house allocation [24]. markets g and many other settings. Recently Donahue
and Kleinberg 14 [5] have modeled federated learning as an HG, where agents evaluate federating
coalitions according to the expected mean squared error of the model they obtain by sharing data with the coalition's 's members. Works like 122 have used core stability to study payoff allocation among team members in collaborative multi-agent settings.
Our definition of e-fractional core stability is also strietly related to PAC stabilizability as defined in [27. This notion was further investigated in several papers. Igarashi et al.
PAC-stabilizabiiity
eC studied the case of HGs with underlying interaction networks. Jha and Zick [2] defined general
framework for learning game-theoretic solution concepts from samples. Trivedi and Hemachandra
considered learning and stabilizing HGs with noisy preferences. Recently, Fioravanti et [8]] proposed to relax the requirements of PAC-stabilizabblityy by considering only restricted distributions and showed stabilizability of W-games under X-bounded distributions.
2
3 Preliminaries
In this section, present the fundamental definitions for our work. Given positive integer & use [k] to denote the set (1....,k) k}.
3.1 Hedonic Games
Let N be a set of agents. We call any non-empty subset C C N coalition and any coalition of size one a singleton. We denote by Ei any binary preference relation of agent over all coalitions containing which is reflexive, transitive, and complete. A Hedonic Game is then pair H (N, k).
where x= (Z....., xn) is a preference profile, i.e., the collection of all agents' preferences.
Throughout this work, we will assume that preferences are expressed as real numbers by means for each i E N. other words, given two coalitions C,C containing agent i, (C) Z (C") if and only if C' X C". We will denote by ō (U),..., Un) collections of agents' valuations and assume that V; is not defined for not containing and write us (C) = Ø. A coalition structure π is partition of agents into coalitions and r(i) denotes the coalition i assigned to. We write is (T)) = (=(()) to denote the utility gets in her assigned coalition x inside π.
of valuation functions U; : 2
With this paper, we aim to relax the concept of core stability defined as follows.
Definition 3.1. Given coalition structure n, coalition S N is said core-block a if. for each i E C, (C)) > (T)). A coalition structure π is said to be core-stable if no coalition C S core-blocks it.
Simple fractional Hedonic Games. In fractioaal HGs (FHGs), first introduced in 3. every agent i N assigns a value vz()) to any other j A i, and then her evaluation for any coalition
is the average value ascribed to the members of C \ {i)). Formally: (C) Σyery v.(5) A FHG is said
[C]
to be simple if (j()) E {0. 1}. for each i.j E N, * j. A natural representation of these games is a directed and unweighted graph G (V, E), where V N and (i. E if and only if vj) 1. Despite their name, Aziz et al. K show that simple FHGs capture the complexity of the entire class w.r.t. stael-ttbillity In fact, deciding if core-stable partition exists is E2-complete.
Anonymous Hedonic Games. An HG said satisfy anonimity 6 10] if agents evaluate coalitions on the sole basis of their size, i.e., (C(C) vz(C") for any i N and any C.C" containing i such that |C| C²). When considering anonymous HGs we will assume v; : [n] + R. An anonymous HGs instance is said to be single-peaked if there exists permutation (si...., sn) of (1....,n) n) for which every agent E N admits a peak p(i) E [r]] such that < k S p(i) or h >> 2 p(i) imply va(sa) 2 (3 Roughly speaking, the higher the distance from the peak in the given ordering, the lower the valuation for the coalition size. If the permutation the identity
function, i.c. the ordering is the usual one over N. we say that the preference is single-peaked in the
3

---

natural ordering. For anonymous HGs, deciding if a core-stable partition exists has been shown to be No-complete
3.2 Epsilon-core, learning, and computation efficiency
Here we formalize our notion of e-fractional core stability.
Definition 3.2. Given a parameter e E [0, 11, we say that a partition a is e-fractional core-stable, c-FC in short, if it holds that at most an e-fraction of all possible coalitions are core-blocking for partition n, i.e.
# of core- core-blocking coalitions for π. <
# of all possible coalitions
This definition has a natural probabilistic interpretation: A partition is c-FC if, by sampling u.a.r. coalition, the probability sampling core-blocking one at most E. Such an interpretation inspired the following extension.
Definition 3.3. Given a parameter & E [0, 1], we say that a partition x is e-fractional core-stable with respect to a distribution D over 2 if
Pr [C core blocking for x E. C
We may assume that agents' preferences unknown and need to learn them by sampling coalitions from a distribution D. Consequently, our algorithms will have learning phase, where preferences learned by observing m samples, and computation phase, where stable outcome is computed upon the learned preferences. We say that an algorithm exactly learns a family T C 2 after seeing sample S it is able to determine the real valuation of any agent for every coalition in T. Note that this does not necessarily mean that T C S; instead, by knowing the properties of the considered HG class, it must be possible derive complete information of T from S. As an example, consider the anonymous HGs class: If T is the family of coalitions of size 8, in order to exactly learn for each agent there must exist S E S such that i and |S] s.
We aim to design polynomial momeeil-timee algorithms for computing F-FC solutions. However, to retrieve enough information the preferences may require a large number of samples. Hence, say that an algorithm is efficient if its computation phase requires polynomial time in the instance size while the learning phase is polynomial in n. 1/5, log 1/8, where is confidence parameter. Clearly, the valuations are known in advance, an efficient algorithm requires polynomial time. Moreover, algorithms will compute be exact as soon as the true agents' preferences are given as input.
s-FC partition with confidence ô and the solution will turn out
3.3 Chernoff Bound and X-bounded distributions
The analysis of our algorithms is mainly probabilistic and will strongly rely the classical Chernoff
bound (see, e.g., Chapter 4 in [23] that we summarize hereafter. Let X = Ei Xi be sum of independent Poisson trials of mean μ,, then for any constant E (0, 1) it holds:
Pr [ (1 b1yb S se- ubb//3
Pr (1 s uub
and
(1)
As we already mentioned, we will study the e-fractional core stability subject to distributions D over 2 We will see that, while for general distributions it is not possible to guarantee good enough values of e, it is indeed possible for X-bounded distributions. This class of distributions has been first introduced
learning context by M. where they consider general continuous distributions over bounded subsets of Rd The idea is that a distribution in this class has constraints (parameterized by the value A) on how much the probability density function can vary.
Definition 3.4. A distribution D over 2 is said to be X-bounded, there exists À 2 1 such that, for every two coalitions C1, Cz, it holds that
[C IC= Cil S Pr IC= C2) C-D
Pr
CND
straightforward consequence of this definition that no coalition has null probability of being sampled. Moreover, it can be noted that, while setting À = 1 we obtain the uniform distribution

---

(0). over 2 as À + -00 every distribution can be considered X-bounded up to an approximation factor. Thus, order to keep the original intended purpose of this definition, in the rest of this work we will consider À to be constant with respect to
The following lemma, adaptation of Lemma 4 in 7 will be useful in our computations. Lemma 3.5. Let distribution 'D be X-bounded. Let F. C P(22)) be family of subsets and let F1/22, Then, the following inequalities hold:
Aa
Pr [CEF] + X(1 a) OND
Aa
Impossibility results
In this section, we explore the boundaries of feasible for simple fractional and anonymous HGs according to general, X-bounded, and uniform distributions.
Simple fractional Hedonic Games. We start by showing that when dealing with arbitrary distribu- tions, an e-FC may not exist for exponentially small w.r.t. the number of agents. Specifically, this impossibility result holds for constant values of e. The informal intuition is that, being the distribution arbitrary, one may choose in an adversarial way with respect to a partition having an empty core.
Proposition 4.1. There exists distribution DD and simple fractional HG instance such that no e-fractional core-stable solution w.r.f. 'D exists for & S 11/240
Proof. Simple fractional HGs have been shown to have an empty core 3.. In particular, the authors provide an instance with 40 agents having an empty core. We can extend this instance an instance T' with N' = [n]] being the set of agents, still having an empty core. Let N {1..... ..... 40} be the set of agents in I. Their mutual preferences remain the same, while they value 0 all the other agents in N' \ N. In turn, the agents in N' N have mutual preferences equal to 1, and they value 0 all the agents in N. I' has an empty core and, in particular, for any coalition structure there exists core blocking coalition in 2d U {411.... ..... }}} {0). In fact, the one hand, the agents in will form blocking coalition whenever we return a partition where they are not in the same coalition. On the other hand, if (41,.... ...,,....' n is coalition of the considered partition, no matter how the agents in N will be partitioned, there exists a blocking coalition in 2 \ {0} because the instance I has empty core. conclusion, by choosing D as the uniform distribution over 2 U ((44,....,,) for any coalition structure π we have Prc-D blocking for π| 1/240 and the thesis follows. O
Similarly, by applying Lemma 3.5
we can easily derive the following generalization. Corollary 4.2. Given parameter X there exists bounded distribution with parameter À such that in simple fractional HGs no e-core exists for < 2"(A-1)+2"
Anonymous Hedonic Games. In the following, we consider single-peaked anonymous HGs. Clearly, all the provided results hold for the more general class of anonymous HGs. Following the same approach of the previous section, knowing that for anonymous HGs there exists an instance with seven agents and single-peaked preferences having empty core 66. can show the following.
Proposition 4.3. There exists a distribution D and an anonymous (single-peaked) HG instance such that for every 1/27 there is no e-fractional core w.r.t. D.
Corollary 4.4. Given a parameter X, there exists a X-bounded distribution such that for < 21(2-1)22 e-fractional core-stable solution exists in anonymous single-peuked HGs.
As consequence, both for simple fractional and anonymous HGs, under uniform distributions, where 1, and constant values of X, the provided bound becomes exponentially small. Hence, in the rest of this paper, we will be focusing these specific classes of distributions.
5 Simple Fractional Hedonic Games
In this section, we present an algorithm returning an e-FC for simple FHGs with e exponentially small in the number of agents, and prove its correctness, as summarized in the following claim.
5

---

Theorem 5.1. Given parameter 6 E (0, we can efficiently compute an E-fractional stable partition for every = 2- 2-50n' 2-0(n'/))
f. for any simple FHG instance and with confidence 1 1 8,
5.1 Computing an e-fractional core-stable partition
We will be working only with the uniform distribution over all possible coalitions denoted by U(2
The proof of the theorem is quite involved and needs several steps. To facilitate the reader, the section is organized as follows: First, we provide a high-level explanation Algorithm || for computing an e-FC partition, then we show various parts of the proof as separate lemmas, and finally, we assemble all together to prove Theorem S.T
As first step, Algorithm ! consists of a learning phase where the exact valuations are computed with confidence 1 5. Then, it starts the computation phase building the graph representation G based on the learned preferences. In order to compute an E-FC partition, the algorithm has to pay attention to the density of G. In particular, the main intuition is to distinguish between instances based on the number of nodes having high out-degrees, treating the two arising cases separately. To this aim, observe first that the biggest fraction of (sampled) coalitions has size close to alll As consequence, if many nodes have low out-degree, matching-lik, partition would be difficult to core-block, since a sampled coalition will often contain very few neighbors of such nodes, compared to its size. Thus, such nodes would have lower utility in C. On the other hand, if a sufficient amount of nodes have a high out-degree, we can form a clique large enough to make any partition containing it hard to sore-block. In fact, with high probability, the sampled coalition C' would contain at least one of such clique nodes, not connected to all the other agents in C. Therefore, it would have lower utility moving to C.
First, we focus on the learning aspect and show that it is possible to learn the exact valuations in simple FHGs, upon sampling a number of sets polynomial in and log 3.
Lemma 5.2. By sampling m 2 16 log + + 4n sets from (2 is possible to learn exactly the valuation functions U1, ui..... Un with confidence 1 5.
The following definition is crucial for proving the main result.
Definition 5.3. Given partition n. agent E N is green with respect to a if
Pr [c:(C) > (t) E C S 2--(2"))) 22) C~U(22)
(2)
Since a coalition containing green agent w.r.t. is unlikely to core-block n. if we manage to show that there are enough green agents in the partition returned by Algorithm [T then we directly prove also its s-fractional core-stability, as in this case any randomly drawn coalition contains at least one green agent with high probability. From now on, let á = Hi s.t. d; S 31m2/33 be as defined in Algorithm] D As already informally explained above, the algorithm follows two different procedures based on being greater equal or lower than 1/3 62 The set Gr defined in Algorithm 1 in both cases is meant to contain exclusively green agents w.r.t. the returned partition. We will start by proving that this is indeed true if < 1//3 62 Since we will never use in-degrees, from now we will
simply use the term degree in place of out-degree.
We first prove the correctness of the easier case of the algorithm in the else part of the if statement (line 19).
Lemma 5.4. Let Φ ns and π be the partition returned by Algorithm Then Gr contains only green agents w.r.t to π.
Proof. Let us say that an agent i N has high degree if d; 2 - 3/3 Observe that, if such an agent is picked at any iteration of the algorithm, then at most 3/n agents are deleted from F at that iteration. By hypothesis, there are at least n picked in non-increasing degree order, after iterations the agents left in F' with high degree are at 1/3
1//
62 agents with high degree. Since they are
least n
62 3/3 which is strictly positive for < 124 This means that all agents in Gr
1/3
Note that | is the average size of coalitions drawn from the uniform distribution.

---

Algorithm 1: Stabilizing Simple FHGs
Input: N, S = ((S), ((()
Output: 262-9(n'23 fractional core-stable partition of NV
Compute 77 and build the corresponding graph G
t- ((i) E N)
3 Let de be the out-degree each i G
Φ -- Mi s.t. d: 31m
Gr 0
1/3
Φ 2
then
62
Sort agents in non nen-deccggsing order of out-degree
H
1/3 62
count 4-
x 3/3
10
while count <
124 do
Select first remaining agent i H in the order
12
Gr + U {
13
Let F; be a set of
n-d
2d,
neighbors of i, giving priority to singleton agents in N I
14
Let C; = {i] (G)UU JER +()
15
x - U \ (T()))ECC
H (i))
17
count + count +1
All remaining singletons =11) {i} in grouped together
19
else
F+N N
for count 1,..., ... 124 do
1/3
22
Pick i E F \ Gr of maximal out-degree
Delete from F all agents not in the neighborhood N; of
24
Gr + U {i}
LE,NA
26
return π
have high degree, so that FF 2 2/3 of the for loop each E Gr is connected to all the other agents F, v,(F) 2 1 1. which is at least the utility would have in a clique of 2 1 agents. Therefore, any coalition of size at most containing cannot core block æ. As consequence, for each Gr it holds that:
1/3 Moreover, since by construction the end
124
3n
Pr (C,(C) us (P))iEC)
Pr
|
>
3n
C
Se a < 22-2mn
C~U((2N)
C~U((2)
where we used Equation
U and the fact that n > 1.
The procedure returning a partition in the complementary case 62 a bit more involved, and we divide the proof in different cases according to the degree of the agents added to Gr.
1/8
Lemma 5.5. Let & 2 n/aa and let æ be the partition returned by Algorithm in this case. Then the following statements hold:
(i) H is never empty when executing line 11 of the while loop of Algorithm ?
7

---

(ii) each agent E Gr is green.
Proof of Theorem 5.7 We are now able to assemble all the above claims together to prove the main
a//a
theorem. According to the above lemmas, in both the cases of Algorithm i.c.
and
62
a//3 the nodes put in Gr are green and y: |Gr] n/3 /124.
62
remains to show that the output π of Algorithm is a 2- -2nn ( frractional core-stable partition:
Pr C~U(2N)
[C blocks क $
Pr C~U(2N)
[CnGr = 0]+
Pr C~U((2)
[CnGr + 0 C' blocks '
2
2"
+
2
n
2
2
1/8
2
1/8
and that concludes the proof.
L
Anonymous Hedonic Games
In this section, we discuss the efficient computation of an c-FC partition the case of anonymous HGs, and focus the more general class of X-bounded distributions.
The main result of this section is given by the following:
Theorem 6.1. Given X-bounded distribution D and parameter 8 (0, for any anonymous HG instance and with confidence - 6, we can efficiently compute e-fractional core-stable partition for every 2 2-(x; $5 where c(A) V13(A+1)
Moreover, when agents' preferences are single-peaked, we can refine the bound on as follows.
Theorem 6.2. Given a X-bounded distribution D and a parameter E (0, 1), for any single-peaker anonymous HG instance and with confidence 1 8, can efficiently compute e-fractional core-stable partition for every E 2 4- 2n/4.
6.1 Distribution over coalitions sizes
Being anonymous preferences uniquely determined by coalition sizes, is important establish how the X-bounded distribution 'D impacts the probability of sampling coalitions of a given size.
Let X N [n]] U {0) be the random variable corresponding to the size of C D, i.e. X(C) [C), and μ := E[X] its average. The following lemma shows some useful properties of X.
Lemma 6.3. Let be the random variable representing the size of D, with D X-bounded, and let = F Then,
n
SPS
An X+1
and
Pr Pr| D
pl
A 1 n E
X+1
where e such that
1 and A is the quantity
3(++1) log
Let us denote by [o( S [n] the open interval ((1 A Hr, (1 + A)H), where is the expected value for the size of coalition sampled from D. Lemma 6.3 implies that with probability least 1 E/2 we draw from D coalition whose size is in (s).
6.2 Properties of TD(e)
The interval (e() will play a central role the computation an e-FC partition. However, under the uncertainty of a distribution DD our algorithms need to i) estimate it (in fact, ID(e) is uniquely determined by the value μ which unknown) and ii) learn exactly the agents' valuations for coalitions whose size is in (E). The technical proofs of this subsection are deferred to the Appendix.

---

Being o unknown, we will work on superset of [=(=) which can be estimated by simply knowing that D is X-bounded. Let S { be sample of size m drawn from D, and let jr m Σ, [S]] be the frequency estimator. By the Hoeffding bound (see Theorem 4.13 in it possible to show that we can estimate with high confidence, as stated in the following.
Lemma 6.4. Given any two constants >> 0, 0 < 1, if
log 2/8
then:
2xa
Pr Smmm
p
a 8
As consequence, can determine good superset of (e( the interval with extreme points (1 A) (/ a).
We now turn our attention to the exact learning of Ip()..
Lemma 6.5. By sampling m 21(1+A)n² log /5 sets from DD it is possible to learn exactly the valuations in Ip(E), with confidence 1 5.
6.3 Computing e-fractional core-stable partition for bounded distributions
Our algorithm will consist of a learning phase and computation phase.
During the learning phase, the algorithm passes through sample of size 2A(1+A)n logn"/6 and for each coalition C in the sample of size e and E C' it stores the value u; (c). Let us denote by X the coalition sizes that have been learned exactly during this learning phase, that is, the coalition sizes for which the algorithm learned the valuations each agent. By the previous lemma, with confidence 1 5, (E) X.
During the computation phase, our algorithm will make sure that a sufficiently large amount of agents have a very small probability of being involved in core blocking coalition. Such agents will be called green agents and are defined as follows. An agent is said to be green in a partition i w.r.t. I S [n]] if (()] maximizes (s)s) for I. We will show that if the probability of sampling coalitions of sizes E I is high enough, then green agents do not want to deviate from their actual partition with high probability well. As consequence, partition containing many green agents is difficult to core-block, as shown in the following:
Lemma 6.6. For any partition n of agents and I C [n]] such that Ip(e) C I. If ग contains at least 22 log2 e green agents w.r.t 1, then, x is e-fractional core-stable.
Proof. Let C ~ D and |C| be its size. We denote by & the event that C core blocks æ, and by Eg then the event that C' does not contain green agents. By definition of green agents, if c and C contains at least one green agent w.r.t. I, then it cannot core block Formally speaking, Eg T EΙ and therefore E = & V & I. As consequence,
Pr
< Pr [c 1 &2 < Pr|c 1] Pr
Being ID(E) S I. by Lemma and Lemma 3.5 we finally get Prp [1 < + long 24
We finally sketch the proof of Theorem for rigorous proof see the Appendix. The key idea is to create a partition π by grouping as many agents as possible in a coalition of preferred size among set of sizes, say that may occur with particularly high probability. Hence, by Lemma 6.6 we only need to find appropriate I and π such that the number of green agents for w.r.t. I is at least log, 2
Proof of Theorem 6. Let us start by defining the set By Lemma we can provide an estimation of μ such that (īz f a)) for certain a with confidence 5. As a consequence, if we can consider / as the intersection of the interval having extreme points (1 + A) (ji + a)) and the set X' of sizes exactly learned during the learning phase. By Lemma 6.5 with confidence 1 5, we can say that (E) C X since with such confidence (e) has been learned. By union bound, with confidence - 26, (E) C I. W.L.ogg we can assume our confidence to be - å by replacing d

---

with 6/2. Moreover, being 2 + a) and f 2 and choosing a = min 1
2 X+I
we can
derive the following bound:
13(A + log
|1| S "V
n2
By the pigeonhole principle, there is one E I such that at least [i] agents prefer s over the other coalition sizes in I. Using the hypothesis on E, we can conclude n
[ 2 log2
Let us now create the desired π. Let q. r be two positive integers s.t. n = qs + r and r < s. Giving priorities to the agents having 8 as the most preferred size in 7, we create q coalitions of size s and coalition of size In this way, at least log2 2A agents are in a coalition having the most preferred size within / and, therefore, they are green agents for π w.r.t. 1. By Lemma 6.6 the thesis follows. C
Finally, we turn our attention to a special but really popular subclass of anonymous HGs. In this case, thanks to the further assumption of values of e. Because of space constraints, the proof of Theorem 6.2 is deferred to the Appendix.
of agents' preferences we can achieve better
7 Conclusions and Future Work
We introduced and studied the e-fractional core stability concept, natural relaxation of core stability where only a small ratio (or a small probability mass) of coalitions is allowed to core-block.
We investigated this concept on two fundamental classes of HGs: Simple FHGs and anonymous HGs. For both these classes the problem of deciding the existence of core-stable partition is notably hard: NP-complete for anonymous HGs and even Σg- complete for simple FHGs. While in Section 4 we showed that very small value of and the choice of the distributions pose limits to the existence of c-FC solutions, we have still been able to obtain positive results for both classes under different assumptions on the considered distributions. For simple FHGs we showed that, when sampling from uniform distribution (that corresponds to c-FC as in Definition 3.2). it is possible to always construct an e-FC under the assumption that e does not decrease faster than sub-exponential value. For anonymous HGs instead, we were able to show the existence of e E-FC for a much broader class of distributions (i.e. the X- bounded ones), under a similar condition over E. These encouraging results show that, while having natural probabilistic nature, the notion of e-FC stability is flexible enough to allow positive results in very complex settings where core-stability is usually considered unattainable. Moreover, its very definition and connection with the concept of PAC stabilizability makes it resilient to possible uncertainty of agents' preferences, increasing its usability in applications.
Limitations of e-fractional core stability. Beyond the core, many stability concepts have been introduced and studied the literature of HGs. Among the others, we mention individual rationality (IR) which is considered the minimum requirement of stability: It postulates that no agent strictly prefers being alone, forming singleton, rather than being in their current coalition. Clearly, core stability implies IR; in fact, if the outcome is not IR there must exist an agent able to form a blocking coalition on her own. Despite IR being implied by core-stability, this is not the case for e-FC and the algorithms presented in this paper do not necessarily satisfy IR. Specifically, in the case of simple fractional HGs, any outcome IR and therefore it is our proposed solution; on the other hand, in the case of anonymous HGs, our algorithm provides an IR solution if coalitions of size 1 are less preferred than any other coalition size. That said, we believe is possible to modify our algorithm, under the reasonable assumption that the value of the singleton coalition is known for each agent, in a way that also IR is satisfied, at the cost of a possible worse lower bound on E.
F Future directions. This contribution has a high potential for future work. A first natural question whether it is possible to extend our positive results for simple FHGs to the more general class of X-bounded distributions. We believe that such an extension is attainable but nonetheless non-trivial. Moreover, although we showed that exponentially small values of are not possible, it still worth investigating which is the best guarantee for general distributions. More broadly, there are several HG classes that have not been considered our work, and understanding for which & an e-FC partition exists is certainly of interest. As discussed in the previous paragraph, it would be definitely of interest to come up with an algorithm for anonymous HGs guaranteeing the solutions be IR. Generally speaking, it would be worth studying e-FC in conjunction with IR in other HGs classes.
10

---

Acknowledgements
We acknowledge the support of the PNRR MIUR project FAIR- Future Research (PE00000013), Spoke 9 Green-aware AI, the PNRR MIUR project VITALITY (ECS00000041), Spoke 2 ASTRA Advanncdd Space Technologies and Research Alliance, the Italian MIUR PRIN 2017 project AL- GADIMAR Algorithms, Games, and Digital Markets (2017R9FHSR_000 (022 and the DFG, German Research Foundation, grant (Ho 3831/5-1).
We thank the anonymous reviewers for their insightful comments and suggestions, which helped us improve the quality of the manuscript.
References
[1] H. Aziz and F. Brandl. Existence stability in hedonic coalition formation games. In Proc.
11th Conf. Autonomous Agents and Multi-Agent Systems (AAMAS), pages 763-770, 2012.
[2] H. Aziz and R. Savani. Hedonic games. In Handbook of Computational Social Choice, pages Cambridge University Press, 2016.
[3] H. Aziz, F. Brandt, and P. Harrenstein. Fractional hedonic games. In Proc. 13th Conf. Au- tonomous Agents and Multi-Agent Systems (AAMAS), pages 5- 2014.
[4] E. Balkanski, U. Syed, and S. Vassilvitskii. Statistical cost sharing. Proc. 30th Conf. Adv. Neural Information Processing Systems (NIPS), pages 6221-6230, 2017.
[5] C. Ballester. Np-completeness in hedonic games. Games Econ. Behav., 49(1):1-30, 2004.
[6] S. Banerjee, H. Konishi, and T. Sönmez. Core in simple coalition formation game. Social Choice and Welfare, 181))135--553 2001.
[7] L. Bartlett and R. C. Williamson. Investigating the distribution assumptions in the PAC learning model. In Proc. 4th Conf. Learning Theory (COLT), 1991.
[8] E. Batziou, M. Bichler, and M. Fichtl. Core-stability in assignment markets with financially constrained buyers. In Proc. 23rd Conf. Econom. Comput. (EC), pages 473-474, 2022.
[9] M. Bichler and S. Waldherr. Core pricing in combinatorial exchanges with financially con- strained buyers: Computational hardness and algorithmic solutions. Oper. Res., 70(1):241-264, 2022.
[10] A. Bogomolnaia and M. O. Jackson. The stability of hedonic coalition structures. Games Econom. Behav., 38(2):201-230, 2002.
[11] A. J. Collins, S. Etemadidavan, and W. Khallouli. Generating empirical core size distributions of hedonic games using a monte carlo method. IGTR, 240)22500011-2500012,, 2022.
[12] D. Corneiisee, T. Rood, Y. Bachrach, M. Malinowski, and T. Kachman. Neural payoff machines: Predicting fair and stable payoff allocations among team members. In Proc. 36th Conf. Adv. Neural Information Processing Systems (NIPS), 2022.
[13] X. Deng and C. H. Papadimitriou. On the complexity of cooperative solution concepts. Math. Oper. Res., 19(2):257-266, 1994.
[14] K. Donahue and J. M. Kleinberg. Model-sharing games: Analyzing federated learning under voluntary participation. Proc. 35th Conf. Artificial Intelligence (AAAI), pages 5303-5311, 2021.
[15] K. Donahue and J. M. Kleinberg. Optimality and stability in federated learning: game- theoretic approach. In Proc. 34th Conf. Adv. Neural Information Processing Systems (NIPS), pages 1287-1298, 2021.
[16] Dreze and J. Greenberg. Hedonic coalitions: Optimality and stability. Econometrica, 48(4): 987-1003, 1980.

---

[17] A. Fanelli, G. Monaco, and L. Moscardelli. Relaxed core stability in fractional hedonic games. In Proc. 30th Intl. Joint Conf. Artif. Intell. (IJCAI), pages 182-188, 2021.
[18] Fioravanti, M. Flammini, B. Kodric, and G. Varriechio. PAC learning and stabilizing hedonic games: Towards unifying approach. In Proc. 37th Conf. Artificial Intelligence (AAAI), pages 5641-5648, 2023.
[19] D. B. Gillies. Solutions to general zero-sum games. Contributions to the Theory of Games IV (Annals of Mathematics Studies, 40), pages 47-85, 1959.
[20] A. Igarashi, J. Sliwinski, and Y. Zick. Forming probably stable communities with limited interactions. In Proc. 33rd Conf. Artificial Intelligence (AAAI), pages 2053-2060, 2019.
[21] T. Jha and Y. Zick. A learning framework for distribution-bused game- came-theoretic solution concepts. In Proc. 21st Conf. Econom. Comput. (EC), pages 355-377, 2020.
[22] M. Maschler, B. Peleg, and L. S. Shapley. Geometric properties of the kernel, nucleolus, and related solution concepts. Math. Oper. Res., 4(4):303- 338, 1979.
[23] M. Mitzenmacher and E. Upfal. Probability and Computing, 2nd edition. Cambridge University Press, 2017. ISBN 9781 1071 154889.
[24] E. Miyagawa. Behav,, 3842)334--36,, 2002.
and the core in house allocation problems. Games Econ.
[25] D. Peters and Elkind. Simple causes of complexity in hedonic games. Proc. 24th Intl. Joint Conf. Artif. Intell. (IJCAI), pages 617-623, 2015.
[26] L. S. Shapley and M. Shubik. Quasi-cores in a monetary economy with nonconvex preferences. Econometrica, 4(34):805-2) -827, 1966.
[27] J. Sliwinski and Y. Zick. Learning hedonic games. In Proc. 26th Intl Joint Conf. Artif. Intell. (IJCAI), pages 2730-2736 2017.
[28] C. Sung and D. Dimitrov. On core membership testing for hedonic coalition formation games. Oper. Res. Lett., 35(2):155-158, 2007.
[29] P. Trivedi and N. Hemachandra. Noise robust core-stable coalitions of hedonic games. In Proc. 14th Asian Conf. Machine Learning, (ACML), volume 189, pages 1038-1053, 2022.
[30] L. Valiant. A theory of the learnable. Commun. ACM,
1984.
[31] G. J. Woeginger. Core stability in hedonic coalition formation. In Proc. 39th Intl. Conf. Current Trends in Theory & Practice of Comput. Sci. (SOFSEM), pages 33-50, 2013.
12


Reviews:
[{"review_id": "XddvN7xJgL", "reviewer": "Reviewer_1m1t", "summary": "This paper is a theory paper analyzing the stability characteristics of the Hedonic Game (HGs). HGs are a class of problems that partition agents considering their preferences. The core stability is the most important characteristic, which measures how well the agents' preferences are fulfilled. Specifically, this paper analyzes the \\epsilon-fractional core (\\epsilon-FC) stability, which means less than the coalitions of a ratio \\epsilon is core-blocked, i.e., the preference was not fulfilled. In short, the paper analyzes famous classes of HGs, simple fractional and anonymous HGs, and shows that we can find \\epsilon-FC solutions if \\epsilon is large enough under \\lambda-bounded distribution, which bounds the size of coalitions so that they are not too unbalanced. The paper also develops algorithms to find the \\epsilon-FC solutions for those HG classes.", "questions": "Q. Theoretical difference from [27]. Specifically, do we require notably different derivations and/or algorithms between PAC stability for W-games and \\epsilon-FC for HGs?\n\nQ. Can we find several practical examples in which cases (i.e., combinations of \\lambda, \\epsilon, and the number of agents) we can find \\epsilon-FC-stabilized partitions? This would be quite useful to understand the usability of the proposed method intuitively.\n", "limitations": "For the theoretical aspect, I did not find notable limitations. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "+ Though I am not familiar with HGs, the definition of \\epsilon-FC and the settings of simple-fractional and anonymous HGs seems to be natural to many practical scenarios. Therefore, I consider this work to be useful for not only theoretical aspects but also practical applications deemed as HGs.\n+ The theory part is well written, which can be easily understood by readers outside HGs (or even outside game theory, like me; I personally enjoyed reading the paper.)", "weaknesses": "- As described in the intros and related work sections, the \\epsilon-FC stability is quite similar to PAC stability. [27] has shown PAC stability under \\lambda-bounded distribution but in different games (W-games). Since I consider the theoretical aspect regarding the analysis of \\epsilon-FC may be similar for many contexts, the theoretical contribution of this paper may be falling in a specific part, in other words, extending the work [27] to different games (i.e., HGs).\n- Since the existence of \\epsilon-FC solutions is bounded by an equation using \\epsilon and \\lambda relying on the number of agents, in practical scenarios, it might be difficult to find \\epsilon-FC for some realistic settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments and the useful feedback.\n\nTo answer effectively to the reviewer's questions, we would like to focus on a couple of points that appear to be unclear. We did not understand exactly if the reviewer here wanted to quote paper [18] instead of [27]. In any case, [27] initiated the study of PAC learnability/stabilizability of HGs classes. In that work, the two subclasses of HGs, namely FHGs and $\\mathcal{W}$-games, are shown not to be PAC stabilizable. [18] continues this line of work and obtains more general results. In particular, the authors first propose the use of $\\lambda$-bounded distributions in the context of $\\mathcal{W}$-games, which are computationally easier to analyze w.r.t. FHGs and Anonymous games. \n\nThe definition and ideas in [18] were an inspiration for us, which is why we mention it in the paper. In that work, however, the authors are able to show a much stronger condition on the provided solution. Namely, regardless of the considered distribution, $\\varepsilon$ can be arbitrarily close to 0. However, such a strong property is not always attainable, because of the freedom of both the distribution and the $\\varepsilon$ parameter. For this reason, to deal with these negative cases, our work is a first attempt of relaxing such strong conditions still achieving good stability guarantees.\n\nIn the following, we will answer the reviewer's questions in the order:\n\n1) The algorithms are very different and strongly depend on the classes considered. We believe that they are interesting on their own, as they are based on novel ideas and the analysis is not trivial. The algorithm in [18] is a greedy procedure that also uses existent algorithms for certain values of $\\varepsilon$ and the analysis is nice but, to our opinion, simpler. Our algorithms are completely different and the probabilistic analysis is more challenging from a technical perspective.\n\n2) For any possible values of $\\lambda$ and $\\varepsilon$, when $n$ is small it is easy to search for blocking coalitions and figure out the existence of $\\varepsilon$-FC partitions. As $n$ grows beyond a certain threshold, we show that such partitions always exist and can be efficiently computed, while conversely the standard problem of computing a core-stable solution is hard, even beyond NP. Thus, from a practical point of view, our results give effective ways to handle large HGs instances.\nAs long as $\\lambda$ is small with respect to $n$, we consider the bounds on $\\varepsilon$ to be pretty powerful for any instance with many agents. Clearly, with a small $n$ it could be easy to search for blocking coalitions and an elaborate concept like $\\varepsilon$-FC stability would not retain much practical sense. Anyway, we believe that the flexibility allowed by the dependence on $\\lambda$ is still of interest in applications where the sampling distribution is somehow more exotic."}, {"review_id": "dVKbchxJ6a", "reviewer": "Reviewer_eoec", "summary": "This paper studies the problem of finding a core-stable partition in the hedonic games. As core-stable partitions seldom exist and they are usually hard to compute, the authors propose a relaxed notion of epsilon-fractional core-stable partitions, in which at most epsilon-fraction of all possible coalitions can core-block the partition. The authors show that the existence of epsilon-fractional core-stable partition depends on the distribution of sampling partitions that are allowed to core-block using the notion of lambda-bounded distributions. With constant lambdas, the authors design efficient algorithms to compute a epsilon-fractional core-stable partition.", "questions": "1. What is the dependence on lambda in Theorem 5.1? Does it only apply to uniform distributions, i.e., when lambda = 1?", "limitations": "The authors adequately addressed the limitations.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is generally well-written and clear. The problem studied in this paper is interesting and relevant to the algorithmic game theory community.\n\n2. This paper provides an almost complete picture of the problem being studied. The results are non-trivial and technically strong.", "weaknesses": "1. It is unclear whether Algorithm 1 can only be applied to uniform distributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful comments. In the following, we will address the comment in 'Weaknesses' and the posed questions:\n\nIn the case of simple FHGs (i.e. Section 5), we assume that the distribution is uniform, thus Theorem 5.1 works under this assumption. This shows that the definition of $\\varepsilon$-FC is meaningful, as it is indeed possible to reach positive results in cases in which they could not be previously obtained without our relaxed requirements on the standard core-stability notion. We believe that it is possible to extend Theorem 5.1 to $\\lambda$-bounded distributions without significantly modifying Algorithm 1. Presumably, this generalization would influence the guarantee on $\\varepsilon$, which we expect to become parameterized in $\\lambda$ as in the case of anonymous HGs. However, such an extension is technically quite challenging and at the moment constitutes an interesting open question. The reviewer might find also interesting our answer to reviewer UFzk who shared similar concerns."}, {"review_id": "nji7VxrdZG", "reviewer": "Reviewer_UFzk", "summary": "This paper introduces and studies the concept of epsilon-fractional core stability in Hedonic Games (HGs), which is a natural relaxation of core stability where a small ratio (or a small probability mass) of coalitions is allowed to core-block. The paper shows that this notion is very flexible and resilient to possible uncertainty of agents’ preferences. \n\nThe paper provides positive results for two fundamental classes of HGs under reasonable assumptions on the considered distributions. Specifically, the paper designs efficient algorithms returning an epsilon-fractional core-stable partition, with epsilon exponentially decreasing in the number of agents, for two classes of HGs: Simple Fractional and Anonymous. \n\nOn the negative side, the authors also prove that by allowing arbitrary sampling distributions an epsilon -FC may fail to exist for constant values of epsilon.\n\nAs discussed in the paper, the concept of epsilon-fractional core stability may stipulate subsequent work, including extending the positive results for simple fractional HGs to the more general class of lambda-bounded distributions, investigating the best guarantee for general distributions, and exploring other HG classes that have not been considered in the paper.", "questions": "Extending the results for simple fractional HGs to lambda-bounded distributions is not a trivial task. Can the authors briefly discuss the difficulties here?\n\nThe authors answered the question in detail in the rebuttal. Thanks!", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The new concept of epsilon-fractional core stability is a natural relaxation of core stability, which deserves to be studied as core-stable partitions seldom exist ( and even when they do it is often computationally intractable to find one).", "weaknesses": "- The Introduction of the paper immediately dives into technical details, which may overwhelm readers.\n\n- There are clear gaps in the results. It will be much better if the results for simple fractional HGs to the more general class of lambda-bounded distributions. As the first work on of epsilon-fractional core stability, I do not view this as a serious drawback.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments and constructive remarks. In the following, we will address the posed questions.\n\nAs we discussed in the paper, $\\lambda$-bounded distributions are a very general class. Lemma 3.4 outlines what we can essentially say about the probability of a certain family of events occurring for any $\\lambda$-bounded distribution $\\mathcal{D}$. When studying random variables of interest, this property and a smart use of known bounds can only help us to obtain confidence intervals on the size of sampled coalitions (see Lemma 6.3). In the anonymous case, the only random variable of interest is the $X$ modeling the size of a sampled coalition, which eased the calculations. Even in this somehow simpler case anyway, estimating the average of $X$ is a crucial step to prove the validity of the algorithm.\n\nOn the other hand, simple FHGs are intrinsically more complex and the algorithm that we built reflects this complexity. In particular, the proof of Lemma 5.5 utilizes $X$ (as defined before) and an extra random variable say $Z$, modeling the number of friends of an agent contained in a sampled coalition. It might be the case that, with a much more elaborate proof, the procedure and the result can be adapted to the $\\lambda$-bounded case. This would require first proving results allowing us to handle the interplay between $X$ and $Z$ and, in addition, carefully revisiting all the parameters involved.\n\nAs the reviewer pointed out, being this work the first on $\\varepsilon$-FC stability, our main aim was to show that positive results were indeed possible in a scenario dominated by powerful negative results. We believe that Theorem 5.1 is relevant even under this restricted assumption and might foster further research."}, {"review_id": "mBTL8dAdad", "reviewer": "Reviewer_ot5e", "summary": "The manuscript at hand proposes a novel relaxation of core stability in coalition formation games, called eps-fractional core stability, which can be viewed as a requirement that a coalition selected uniformly at random from the set of all coalitions (conceptually choices according to some other distribution are also permitted, but the results in the submission are all for uniform selection) witnesses classic core instability with probability at most eps. While this is a relaxation of core stability, just like core stability, it cannot always be achieved, even for uniform distributions, fractional hedonic games and anonymous hedonic games. These impossibility results hold for a constant choice of eps, but on the other hand in these settings, the submission shows that eps-fractional core stable partitions exists for eps growing exponentially in the number of agents.", "questions": "Can you address my concerns above about the naturalness of eps-fractional core stability and the motivation of uniformly selecting coalitions from the set of all coalitions?", "limitations": "No concerns.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The motivating criticism of previous relaxations of core stability is justified and the proposed model is natural from a certain probably-not-discovering-core-instability perspective.\nThe quality of the writeup is high and I did not find any technical errors.", "weaknesses": "I find that it would be justified to contextualise the newly introduced stability notion with respect to more classic ones. For example, from my understanding, eps-fractional core stable outcomes are not even necessarily individually rational which can be viewed as extremely unnatural and should at least be discussed and possibly even somewhat justified.\nOn a related note, I do not really see how the definition reflects the fact that `the probability that groups of agents improve meeting by chance is very low' (l 53). Why would the probability that a coalition meets be uniform in the number of all coalitions. Naively, I would expect something more like the probability of each agent being included in a coalition be i.i.d. with some probability, meaning that small coalitions would be much more likely to meet. I think it would be good it the uniform selection of coalitions from the set of all coalitions could be motivated a bit more.\n\nIn terms of presentation, I do not understand why the impossibility results are stated as existence of some distribution results. Would it not strengthen the statements if one would simply say that D is the uniform distribution?\n\nThe authors satisfactorily addressed all weaknesses in the rebuttal period and I have changed my score to reflect this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments. We reply here to the points raised in the 'Weaknesses' and explain how we will address them in our paper. Before providing our detailed answers, we want to highlight that while for simple FHGs our results hold only for the uniform distribution, for anonymous HGs they apply to any $\\lambda$-bounded distribution. Moreover, we believe that in the first case it would be possible to generalize to $\\lambda$-bounded, even if at the moment this remains an open question.\n\n**Individual rationality:** \nDespite our main focus was relaxing the demanding notion of core stability, the reviewer raised an interesting point. It is indeed correct to claim that our relaxation does not imply individual rationality (IR). However, in the case of simple fractional HGs, any outcome is IR and therefore it is our proposed solution. In the case of anonymous HG, our algorithm provides an IR solution only if coalitions of size $1$ are less preferred than any other coalition size. That said, we believe it is possible to modify our algorithm, under the reasonable assumption that the value of the singleton coalition is known for each agent$^1$, in a way that also IR is satisfied. However, such a requirement may have an impact on the quality of $\\varepsilon$. It would be definitely of interest to come up with such an algorithm and understand what impact the IR requirement would have on $\\varepsilon$. We will include a discussion on IR in our paper and propose the study of $\\varepsilon$-FC solution in conjunction with IR as an important open question. \n\n$^1$ Such an assumption has also been made in [18] to obtain PAC-stabilizability for the class of bottom responsive HGs. Moreover, it can be assumed that agents have been asked to express their valuations in a normalized fashion, that is, they value $0$ their singleton coalition. \n\n\n**Impossibility results:** The distribution $\\mathcal{D}$ can be interpreted as the probability that a group of agents can interact/meet. Despite there exist more reasonable distributions than others, the distribution $\\mathcal{D}$ may be in principle any. Therefore, with our impossibility results, we show that whenever the support of the distribution $\\mathcal{D}$ is not the set of all possible coalitions, the guarantee on $\\varepsilon$ may be very bad. For this reason, we focus on specific classes where the aforementioned condition is not satisfied. Clearly, any distribution whose support is the set of all possible coalitions is a $\\lambda$-bounded distribution (since any coalition has a positive probability to be sampled); however, $\\lambda$ could be an extremely high number.\n\n**Uniform, $\\lambda$-bounded, and i.i.d. distributions:** As just mentioned, our choice of studying uniform and $\\lambda$-bounded distributions follows by the provided negative results. We agree that the idea of having a probability distribution such that the probability of each agent being included in a coalition is i.i.d.\\ with some probability $\\alpha \\in (0,1)$ is natural. Such a distribution is indeed a $\\lambda$-bounded distribution as the support is the set of all possible coalitions. Therefore, our results for $\\lambda$-bounded distributions apply also to this class. Being such a class particularly meaningful, we will point this out in our paper. Moreover, having this class a nice probabilistic structure, it would be interesting to understand if it is possible to improve the bound on $\\varepsilon$ especially when the corresponding parameter $\\lambda$ is extremely high, also exploiting the independence of the membership of each single agent.\n\nOn a final note, despite its ability to properly represent the probability of agents meeting may be questionable, finding an $\\varepsilon$-FC for the uniform distribution is equivalent to the problem of determining a coalition structure having the fraction of possible core-blocking coalitions bounded by $\\varepsilon$. Providing a coalition structure having only a limited number of core-blocking coalitions seems a good compromise in the case in which no core stable outcome exists."}, {"review_id": "siPyRDlqQw", "reviewer": "Reviewer_psiE", "summary": "This paper introduces the concept of an $\\epsilon$-fractional core stability, relaxing the standard notion of core stability by allowing at most an $\\epsilon$ fraction of all possible outcomes to core-block. They show that for sufficiently small values of $\\epsilon$, $\\epsilon$-fractional core stability always exists and can be computed in polynomial time for certain important subclasses of hedonic games, bypassing well-known difficulties with the usual notion of core stability. They also provide learning algorithms with PAC-type guarantees for identifying $\\epsilon$-fractional core-stable outcomes under a broad class of underlying distributions over coalitions, as well as negative results for arbitrary distributions.", "questions": "Some minor issues:\n\n1. Technically speaking, the term $2^{-n^{1/3}}$ (for example in Theorem 5.1) is sub exponential, so maybe it is worth rephrasing the claims that $\\epsilon$ is decreasing exponentially with the number of players (but I leave this up to the authors).\n2. There is something off with the citation style; for example, Line 89 reads \"Donahue u. Kleinberg\" instead of \"Donahue and Kleinberg.\" This also occurs in many places. \n3. There are missing punctuation marks in some equations throughout the paper.\n4. Regarding the title, maybe it is worth considering either removing the word \"epsilon\" or replacing \"epsilon\" with $\\epsilon$; currently it reads slightly weird.", "limitations": "The authors have adequately addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper makes a concrete contribution in the algorithmic study of core-stability notions in important classes of hedonic games, namely simple fractional and anonymous hedonic games. More precisely, the usual notion of core stability is known to suffer from two major drawbacks: it is not universal, and even when it exists it can be hard compute. As a result, different relaxations have been studied over the years that try to address those issues. This paper lies in this line of work, proposing a natural relaxation that only requires most of the coalitions to not be core-blocking. Moreover, they provide a number of non-trivial positive and negative results under this new concept. As such, I believe it makes concrete contributions in this line of work, the results have been nicely placed into the existing literature, and the paper can bring much interesting future work.\n\nMoreover, the paper is well-written and structured, and all the important ideas and techniques and sufficiently exposed in the main body. I did not find any notable issue in the technical part/proofs. The results appear to be sound.", "weaknesses": "One notable weakness is that the central definition of the paper (Definition 3.1), albeit quite natural, is not entirely uncontroversial: the fact that most coalitions are not core-blocking may not be sufficient for certain scenarios. That is, it is not clear whether the introduced notion of fractional core stability is an appropriate notion of stability in hedonic games. It would be good to see some more motivation and suitable applications for this definition, as well scenarios wherein this notion fails to provide meaningful guarantees.\n\nBesides the issue above, another weakness is that most of the results follow rather directly from prior work and standard techniques, but I don't view this as a basis for rejection.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for carefully reading our paper and for the constructive remarks. In the following we will address the comments in the 'Weaknesses' and 'Questions' sections.\n\n**Limitations of the definition:** A possible scenario where the notion of $\\varepsilon$-FC stability shows its limitations are instances with a small number of agents $n$. In fact, in such cases, it is often easy to exhibit eventual core-blocking coalitions. However. as $n$ grows, finding such coalitions becomes computationally too hard, as shown by the many complexity results in the HGs literature. Thus, with a big enough $n$, one must think carefully about how such a coalition could be identified and how suitably degrees of stability can anyway be guaranteed. On this respect, the distribution $\\mathcal{D}$ serves the purpose of modeling the probability of a coalition forming naturally (i.e. of a subset of agents meeting together) and eventually blocking.\n\nHowever, it is crucial to observe that every possible approximate core-stability concept must allow a small fraction of blocking coalitions to exist. Previously introduced notions (like the ones described in [17, 22, 26]) limit the number of allowable coalitions by imposing extra rules to the agents deviating from a certain configuration. In general, in all such relaxations, core-blocking coalitions are still there, but they are filtered out by the corresponding requirements. Since this approach seems unnatural in modeling scenarios in which agents are free to deviate anywhere they like, allowing only a fraction of all possible coalitions to core-block seems the most natural choice. \nAs a concrete example to the above argument, consider the classical approximate core-stability concept in which a core-blocking coalition $C$ is acceptable if and only if the agents deviating to $C$ improve by at least a certain (additive or multiplicative) factor. As also pointed out in the scientific literature, this concept appears fragile, as there is no reason why even a subtle improvement should not be pursued by the agents.\n    \n**Originality of the work:** Our algorithms are original, contain novel ideas, and are not based in any way on existing literature in HGs. Moreover, even if Chernoff bounds are a standard tool in probabilistic analysis and the PAC framework, we used them in an arguably original and non-trivial way, at least for what concerns the setting of HGs.\n    \n**Minor issues:** We thank again the reviewer for pointing out to us the minor issues. We will address all of them in the final version of the paper."}]

Author rebuttal:
We thank the reviewers for their valuable comments. We will take into account their feedback and revisit the paper accordingly. In what follows, we provide a general answer to the reviewers addressing some shared concerns raised in their comments.
The specific questions will be addressed in the dedicated responses to the reviewers. We will be happy to reply to any further questions in the discussion phase.

The idea underlying the definition of $\varepsilon$-fractional core-stability is that a partition that can be core-blocked by at most an $\varepsilon$ fraction of all possible coalitions is a good candidate to approximate a core-stable solution in the classical sense. From a probabilistic viewpoint, this is equivalent to asking that a coalition sampled uniformly at random has a probability of core-blocking the proposed partition upper bounded by $\varepsilon$. Therefore, the most natural choice and the very starting point of our reasoning is the uniform distribution, which is why we consider studying it meaningful and not restricting as meant in this respect.

The probabilistic interpretation led us to generalize the definition to incorporate any possible sampling distribution $\mathcal{D}$. 
As a further step in this direction, this allowed us also to extend our study to all the situations in which preferences are unknown and must be learned by sampling. In such a setting, the sampling distribution $\mathcal{D}$ can also be interpreted as the probability that a group of agents spontaneously meet in the considered case study, and can be used to both learn the agents' utilities and verify the stability of the created partition.

Unfortunately, the results in Section 4 show that not all distributions $\mathcal{D}$ allow positive results: in particular a condition that appears to be crucial is that the support of $\mathcal{D}$ contains all coalitions. We thus decided to focus our attention on the class of $\lambda$-bounded distributions, which is the largest class of distributions having support on the set of all possible coalitions. First introduced in [7] as a reasonable choice for the PAC learning setting and then used in [18] in the context of PAC-stabilizability, it is a general enough class with interesting properties that seems to fit very well in this scenario.

In our view, this work is a first step in understanding which kinds of coalition structures are worthy of being considered stable in real-world applications where the classic definition of core stability might be too demanding and/or hard to compute.

Meta-review: This paper got rather positive reviews, and its scores (7,7,6,5,5) put it clearly in the borderline/accept candidate category. Specifically, when asked to chime into the accept vs reject decision discussion, both of the positive reviewers repeated their support for an accept decision. Overall, I see a solid paper that introduces a natural relaxed notion of core-stability (which is inspired by PAC-stabilizability in [27]). This notion although not free of potential criticism, seems to be a natural one to explore. The paper does a thorough job in understanding its promises and limitations of this notion (by exploring existence and computational aspects for different classes of distributions and different classes of games).
Decision: Accept (poster)