Learning the Expected Core of Strictly Convex Stochastic Cooperative Games

Authors: nam phuong tran
anh  the
  ta
shuqing  shi
debmalya  mandal
yali  du
long  tran-thanh
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 15:05:08

Abstract: Reward allocation, also known as the credit assignment problem, has been an important topic in economics, engineering, and machine learning. An important concept in reward allocation is the core, which is the set of stable allocations where no agent has the motivation to deviate from the grand coalition. In previous works, computing the core requires either knowledge of the reward function in deterministic games or the reward distribution in stochastic games. However, this is unrealistic, as the reward function or distribution is often only partially known and may be subject to uncertainty. In this paper, we consider the core learning problem in stochastic cooperative games, where the reward distribution is unknown. Our goal is to learn the expected core, that is, the set of allocations that are stable in expectation, given an oracle that returns a stochastic reward for an enquired coalition each round. Within the class of strictly convex games, we present an algorithm named \texttt{Common-Points-Picking} that returns a point in the expected core given a polynomial number of samples, with high probability. To analyse the algorithm, we develop a new extension of the separation hyperplane theorem for multiple convex sets.t.

Main paper: 
 introduction: 
 The reward allocation problem is a fundamental challenge in cooperative games that seeks reward allocation schemes to motivate agents to collaborate or satisfy certain constraints, and its solution concepts have recently gained popularity within the machine learning literature through its application in explainable AI (XAI) [17, 28, 13, 31] and cooperative Multi-Agent Reinforcement Learning (MARL) [29, 12, 30] . In the realm of XAI, designers often seek to understand which factors of the model contribute to the outputs. Solution concepts such as the Shapley value [17, 28] and the core [31, 13] provide frameworks for assessing the influence that each factor has on the model'sQuestion: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: Our claims made in the abstract and introduction reflect the paper's contributions and scope.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper.• The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
related work: 
 Stochastic Cooperative Games. The study of stochastic cooperative games can be traced back to at least [9] . The main goal of the allocation scheme is to minimise the probability of objections arising after the realisation of the rewards. [27, 26] later extended and refined the notion of stability in stochastic settings. These seminal works require information about the reward distribution to compute a stable allocation scheme before the game starts. Stochastic cooperative games have also been studied in a Bayesian setting in a series of papers [5, 7, 8, 6] . These works develop a framework for Bayesian stochastic cooperative games, where the distribution of the reward is conditioned on a hidden parameter following a prior distribution. The prior distribution is common knowledge among agents and can be used to define a new concept of stability called Bayesian core. In contrast to previous works, our paper focuses on studying scenarios where the reward distribution or prior knowledge is not disclosed to the principal agent and computing a stable allocation requires a data-driven method.Learning the Core. The literature on learning the core through sample-based methods can be categorised based on the type of core one seeks to evaluate. Two main concepts of the stochastic core are commonly considered, namely the robust core (i.e. core constraints are satisfied with high probability) [11, 22, 19] and the expected core (i.e. core constraints are satisfied in expectation) [10, 20] . The robust core is defined in a manner that allows the core inequalities to be satisfied with high probability when the reward is realised. However, this definition may lead to the practical issue Learning the Shapley Value. Another relevant line of research is the Shapley approximation, as the Shapley value is the barycenter of the core in convex games. Therefore, the approximation error of the Shapley value is an upper bound on the distance between the approximated Shapley value and the expected core [4, 18, 24] . It is worth noting that, in contrast to the Shapley approximation method, our algorithm ensures the return of a point in the core. In comparison, the Shapley approximation approach can only provide an allocation with a bounded distance from the core.3 Problem Description 3.1 Preliminaries Notations. For k ∈ N + , denote [k] as set {1, 2, . . . , k}. For n ∈ N + , let E n be the n-dimensional Euclidean space, and let us denote D as the Euclidean distance in E n . Denote 1 n as the vector [1, ..., 1] ∈ R n . Denote ⟨•, •⟩ as the dot product. For a set C, we denote C \ x as the set resulting from eliminating an element x in C. For C ⊂ E n , let diam(C) := max x,y∈C D(x, y), and Conv (C) denote the diameter and the convex hull of C, respectively. Denote S n := {ω : [n] → [n] | ω is a bijection} as the permutation group of [n] . For any collection of permutations P ⊂ S n , we denote ω p , p ∈ [|P|], as p th permutation order in P. Let s i := (i, i + 1) denote the adjacent transposition between i and i + 1. Given a set C, we denote by M(C) the space of all probability distributions on C.A stochastic cooperative game is defined as a tuple (N, P), where N is a set containing all agents with number of agents to be |N | = n, and P = {P S ∈ M([0, 1]) | S ⊆ N } is the collection of reward distributions with P S to be the reward distribution w.r.t. the coalition S. For any coalition S ⊆ N , we denote µ(S) := E r∼P S [r] as the expected reward of coalition S. For a reward allocation scheme x ∈ R n , let x(S) := i∈S x i as the total reward allocation for players in S. A reward allocation x is effective if x(N ) = µ(N ). The hyperplane of all effective reward allocations, denoted by H N , is defined asH N = {x ∈ R n | x(N ) = µ(N )}.The convex stochastic cooperative game can be defined as follows:Definition 1 (Convex stochastic cooperative game). A stochastic cooperative game is convex if the expected reward function is supermodular [23] , that is,EQUATIONNext, we define the notion of strict convexity as follows:Definition 2 (ς-Strictly convex cooperative game). For some constant ς > 0, a cooperative game is ς-strictly convex if the expected reward function is ς-strictly supermodular [23] , that is, µ is supermodular and µ(S ∪ {i}) -µ(S) ≥ µ(C ∪ {i}) -µ(C) + ς, ∀i / ∈ S ∪ C and ∀C ⊆ S ⊆ N.Following [20] , we define the expected core as follows:Definition 3 (Expected core [20] ). The core is defined as E-Core := {x ∈ R n | x(N ) = µ(N ); x(S) ≥ µ(S), ∀S ⊆ N }.That is, the E-Core is the collection of all effective reward allocation schemes x (i.e., schemes where the total allocation adds up to the expected reward of the grand coalition N -see the definition of effective reward allocation above), where if any agents deviate from the grand coalition N to form a smaller team S, regardless of how they allocate the reward, each individual will not receive more expected reward than if they had stayed in N . Note that, as E-Core ⊂ H N , its dimension is at most (n -1). We say that E-Core is full dimensional whenever its dimension is n -1.In convex games, each vertex of the core in the convex game is a marginal vector corresponding to a permutation order [23] . This is a special property of convex games, which plays a crucial role in our algorithm design. For any ω ∈ S n , define the marginal vector ϕ ω ∈ R n corresponding to ω, that is, its i th entry isEQUATIONwhereP ω i = {j | ω(j) ≤ ω(i)}.It is known from [23] that if the expected reward function is strictly supermodular, the E-Core must be full dimensional.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We discussed the limitations of the work in the main paper and the conclusion.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.• The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.• The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.• The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.• If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.• While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.• Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: We does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.• If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
problem setting: 
 In our setting we assume that there is a principal who does not know the reward distribution P. In each round t, the principal queries a coalition S t ⊂ N . The environment returns a vector r t ∼ P St independently of the past. For simplicity, we assume that the agent knows the expected reward of the grand coalition µ(N ). Additionally, we assume that the convexity of the game, that is, µ is supermodular. Our question is how many samples are needed so that with high probability 1 -δ, the algorithm returns a point x ∈ E-Core. More particularly, we ask whether or not there is an algorithm that can output a point in the E-Core, with probability at least 1 -δ and the number of queriesEQUATIONAs well shall show in Theorem 7, if E-Core is not full-dimensional, no algorithm can output a point in E-Core with finite samples. As such, to guarantee the learnability of the E-Core. From now on in the rest of this paper, we assume that:Assumption 4. The game is ς-strictly convex.Note that strict convexity immediately implies full dimensionality [23] , which is not the case with convexity (refer to Section 5). As we shall show in the next sections, strict convexity is a sufficient condition allowing the principal to learn a point in E-Core with polynomial number of samples. Practical examples of strictly convex games can be found in appendix D. 
learning the expected core: 
 In this section, we propose a general-purpose Common-Point-Picking algorithm that is able to return a point of unknown full-dimensional simplex, given an oracle that provides a noisy position of the simplex's verticies. Under the assumption that the game is strictly convex, we show that, when applying Common-Points-Picking algorithm to the ς-strictly convex game, it can return a point in E-Core provided the number of samples is poly(n, ς).Given E-Core polytope of dimension (n -1). In deterministic case when the knowledge of the game is perfect, to compute a point in the core, one can query a marginal vector corresponding to a permutation order ω ∈ S n [23] . Given that we have uncertainty in the estimation of E-Core, this approach is no longer applicable. The reason is that for each vertex ϕ ω , we do not precisely compute its position. Instead, we only have information on its confidence set C(ϕ ω , δ), a compact (n -1)-dimensional set. The confidence set contains ϕ ω with probability at least (1 -δ), as we will define shortly in this section.One approach to overcome the effect of uncertainty is that we can estimate multiple vertices of the E-Core. Let P ⊂ S n be a collection of permutations, and Q = {ϕ ωp | ω p ∈ P} be the set of vertices corresponding to P. For brevity, we denote C p := C(ϕ ωp , δ), ω p ∈ P. In this section, we assume that the confidence sets contain the true vertices, that is, ϕ ωp ∈ C p , ∀p ∈ [|P|], which can be guaranteed with high probability. It is clear that Conv (Q) ⊂ E-Core, since Q is a subset of vertices of E-Core. The challenge is that, as the ground truth of the position of the vertex can be any point in the confidence set, we need to ensure that the algorithm outputs a point in the convex hull of any collection of points in the confidence sets. A sufficient condition to achieve this is that, given |P| confidence sets {C p } p∈[|P|] , for each x p ∈ C p ,EQUATIONThis condition means that there exists a common point among all the convex hulls formed by choosing any point in confidence sets, x p ∈ C p . We call the above intersection a set of common points. The reason why it is a sufficient condition is that this set is a subset of a ground-truth simplex, implying that it is in the E-Core. Formally, we have which means that any common point must be in E-Core. Moreover, the set of common points is learnable. As we shall show in the next section, our algorithm can access the set of common points whenever it is nonempty.x p ∈Cp p∈[|P|] Conv {x p } p∈[|P|] ⊂ Conv (Q) ⊂ E-Core; (6) Algorithm 1 Common Points Picking 1: Input collection of permutation order P = {ω p } p∈[n] . 2: t = 0, ep = 0, Q = ∅ 3: while Stopping-Condition (Q, b ep ) do 4: ep ← ep + 1; 5: for p ∈ [n] do 6: for i ∈ [n]We first state a necessary condition for the number of vertices of E-Core need to estimate for (5) can be satisfied: Proposition 5. Assume that all the confidence sets are full dimensional, that is, dim(C p ) = n -1, ∀p ∈ [|P|],and suppose that |P| < n,EQUATIONProposition 5 implies that one needs to estimate at least n vertices to guarantee the existence of a common point.As Proposition 5 suggests, we need to estimate at least n vertices. As such, from now on, we assume that |P| = n. Based on the above intuition, we propose Common-Points-Picking, whose pseudo code is described in Algorithm 1.The Common-Points-Picking Algorithm can be described as follows. The termination of the Common-Points-Picking algorithm is based on the Stopping-Condition algorithm (Algorithm 2), which can be described as follows.Consider the case where Q ̸ = ∅.For each point x p ∈ Q, the algorithm attempts to calculate the separating hyperplane H p (Q), that separates x p from the rest Q \ x p (line 7). EQUATIONComputing distance:h p := min x:∥x-x p ∥ ∞ <bep c p -⟨v p , x⟩ . 9:if h p < n ϵ ep then 10:Return FALSE.11:end if 12: end for 13: Return TRUE.The hyperplane H p (Q) is defined by two parameters (v p ∈ R n , c p ∈ R), where v p is one of its unit normal vectors, together with c p , satisfying Eq. (8) . Specifically, the second and third equality in (8) implies that H p (Q) is parallel and at a distance of ϵ ep (toward x p ) from the hyperplane that passes through all the points in Q \ x p . The fourth equality in (8) guarantees that H p (Q) is a subset of H N (as the normal vector of H N is 1 n ). After computing H p (Q), the algorithm checks whether the distance from the confidence set C p to H p (Q) is large enough (lines 8-12). The stopping condition checks for all p ∈ [n]; if no condition is violated, then the algorithm returns TRUE. An example of the construction of separating hyperplanes in H N , where n = 3 is depicted in Figure 1 .Note that the input of algorithm P can be any collection of permutation orders such that |P| = n. In the next section, we will provide instances of the collection of permutation orders, in which, under Assumption 4, the algorithm can output a point in E-Core with high probability and a polynomial number of samples. Remark 6. Most of the computational burden lies in computing the separating hyperplane H p (Q) for each p (line 7), and calculating the distance between the confidence set C p and H p (Q) (line 8) in Stopping Condition. Since all tasks can be completed within polynomial time w.r.t. n, our algorithm is polynomial. There are two challenges regarding the Common-Points-Picking algorithm. First, we need to design confidence sets such that they contain the vertices with high probability, which can be done easily using Hoeffding's inequality. Second, we need to define a stopping condition that can guarantee the non-emptiness of the common set and output a point in the common set with a polynomial number of samples. The second question is more involved and requires proving new results in convex geometry, including an extension of the hyperplane separation theorem, as we shall fully explain in Section 5.1.To calculate this set we will use the probability concentration inequality to obtain a confidence set: First, let r ep (∅) = 0, ∀ ep > 0, define the empirical marginal vector w.r.t. permutation ω as φω ∈ R n at epoch ep asEQUATIONBy the Hoeffding's inequality, one has that after ep epochs, ∀ω ∈ P, for each i ∈ [n], with probability at least 1 -δ, ϕ ω must belong to the following set:EQUATION) 
main results: 
 Before proceeding to the analysis of Algorithm 1, let us exclude the case where learning a stable allocation is not possible, thereby emphasizing the need of the strict convexity assumption.Theorem 7. Suppose that E-Core has dimension k < n -1, for any 0.2 > δ > 0 and with finite samples, no algorithm can output a point in E-Core with probability at least 1 -δ.The proof of Theorem 7 employs an information-theoretic argument. In particular, we construct two game instances with low-dimensional cores, utilising the concept of face games introduced in [14] .The construction of the two games is designed to ensure that, despite the KL distance between their reward distributions being arbitrarily small, their low-dimensional cores are parallel and maintain a positive distance from each other. Consequently, their cores have empty intersections. This implies that, given finite samples, no algorithm can reliably distinguish between the two games. Since these games lack a mutually stable allocation, if an algorithm fails to differentiate between them, it is likely to choose the wrong core with a certain probability.It is worth noting that convex games may have a low-dimensional core, as demonstrated in the following example.Example 8. Let µ(S) = |S| for all S ⊆ N . It is easy to verify that µ is indeed convex. The marginal contribution of any player i to any set S ⊆ N isEQUATIONTherefore, the only stable allocation is 1 n , which coincides with the Shapley value. Hence, the core is one-point set. According to Theorem 7, since the core has a dimension of 0 in this case, it is impossible to learn a stable allocation with a finite number of samples.Example 8 suggests that convexity alone does not ensure the problem's learnability, emphasizing the requirement for strict convexity.In this subsection, we explain the construction of the stopping condition in Algorithm 2. We will show that the stopping condition can always be satisfied with the number of samples needed polynomially w.r.t the width of the ground truth simplex. Intuitively, the confidence sets need to shrink to be sufficiently small, relative to the width of the simplex, to guarantee the existence of a common point.To simplify the presentation, we restrict our attention to H N and consider it as E n-1 . First, we state a necessary condition for the existence of common points.Proposition 9. Suppose there is a (n -2)-dimensional hyperplane that intersect with all the interior of confidence sets C p , ∀p ∈ [n] , then common points do not exist.Proposition 9 suggests that if the ground truth simplex Conv (Q) is not full-dimensional, then the common set is empty. In addition, even if Conv (Q) is full-dimensional, but the confident sets are not sufficiently small, one can also create a hyperplane that intersects with all the confidence sets. For example, when the intersection of the confidence sets is not empty.On the other hand, when the confidence sets are well-arranged and sufficiently small, that is, there does not exist a hyperplane that intersects with all of them, a nice separating property emerges, as stated in the next theorem. This new result can be considered as an extension of the classic separating hyperplane theorem [3] . First, let us recap the notion of separation as follows.Definition 10 (Separating hyperplane). Let C and D be two compact and convex subsets of E n-1 . Let H be a hyperplane defined by the tuple (v, c), where v is a unit normal vector and c is a real number, such that ⟨x, v⟩ = c, ∀x ∈ H. We say H separates C and D if ⟨x, v⟩ > c, ∀x ∈ C; and ⟨y, v⟩ < c, ∀y ∈ D.Theorem 11 (Hyperplane separation theorem for multiple convex sets). Assume that {C p } p∈[n] are mutually disjoint compact and convex subsets in E n-1 . Suppose that there does not exist a (n -2)-dimensional hyperplane that intersects with confidence sets C p , ∀p ∈ [n], then for each p ∈ [n], there exists a hyperplane that separates C p from q̸ =p C q .Remark 12 (Non-triviality of Theorem 11). At a first glance, Theorem 11 may appear as a trivial extension of the classic hyperplane separation theorem due to the following reasoning: Consider the union of all hyperplanes that intersect q̸ =p C q , which trivially contains q̸ =p C q . Then, by assuming that these hyperplanes do not intersect C p , the separation between C p and q̸ =p C q appears to follow from the classic separation hyperplane theorem. However, there is a flaw in the above reasoning: The union of these hyperplanes is not necessarily convex. Therefore, the classic separation hyperplane theorem cannot be applied directly. Instead, employing Carathéodory's theorem, we prove in Theorem 11 by contra-position that if the intersection between C p and Conv( q̸ =p C q ) is non-empty, then we can construct a low-dimensional hyperplane that intersects with all the set.When those confidence sets are well-separated, we can provide a sufficient condition for that the common points exist. Let H p be a separating hyperplane that separate C p from q̸ =p C q . We define H p corresponding with tuple (v p , c p ). Now, denote E p = x ∈ E n-1 | ⟨v p , x⟩ < c p as the half space containing C p . We have that:EQUATIONConsequently, ifp∈[n]E p is nonempty, it is the subset of common points.From Lemma 13, as p∈[n] E p is the subset of any simplex defined by a set of points in the confidence sets, p∈[n] E p must be either empty or bounded subset of E n-1 . The key implication here is that Lemma 13 provides us a method to find a point in the common set. An example of Lemma 13 in E 2 is illustrated in Figure 1 .E p is nonempty. Next we show that the nonemptiness of p∈[n] E p can be guaranteed if the diameter of the confidence sets is sufficiently small. This establishes a condition for the number of samples required by the algorithm.Theorem 14. Given a collection of confident set {C p } p∈[n] and let Q = {x p } p∈[n] , for any x p ∈ C p . For any p ∈ [n], denote H p (Q) as the (n -1)-dimensional hyperplane with constant (v p , c p ),EQUATIONFor all p ∈ [n], if the following holdsEQUATIONthen there exists a common point. In particular, the pointx ⋆ = 1 n p∈[n] x p is a common point.Intuitively, Theorem 14 states that if the distance from a confidence set C p to the hyperplane H p (Q) is relatively large compared to the sum of the diameters of all other confidence sets, then the average of any collection of points in the confidence set must be a common point. As such, Theorem 14 determines the stopping condition for Algorithm 1 and provide us a explicit way to find a common point, which validates the correctness of Algorithm 1. In particular, Algorithm 2 checks if conditions (14) are satisfied for the confidence sets in each round. If the conditions are satisfied, then Algorithm 1 stops sampling and returns x ⋆ as the common point.Note that while the diameters of confidence sets can be controlled by the number of samples regarding the marginal vector, D(C p , H p (Q)) is a random variable and needs to be handled with care. We show that there exist choices of n vertices such that the simplex formed by them has a sufficiently large width, resulting in the stopping condition being satisfied with high probability after poly(n, ς -1 ) number of samples.Now, we show that, the conditions of Theorem 14 can be satisfied with high probability. The distance D(C p , H p (Q)), p ∈ [n] can be lower bounded by the width of the ground-truth simplex, which is defined as follows:Definition 15 (Width of simplex). Given n points {x 1 , ...x n } in R n , let matrix P = [x i ] i∈[n] ,we define the matrix of coordinates of the points in P w.r.t. 1) . Denote σ k (M ) as the k th singular value of matrix M (with descending order). We define the width of the simplex whose coordinate matrix is P as followsx i as coM(P, i) := [(x j -x i )] j̸ =i ∈ R n×(n-EQUATIONLemma 16. Given n points {x 1 , ..., x n } in R n , let M be the matrix corresponding to these points, assume that 0 < M ij < 1 and ϑ(M ) ≥ σ, for some constant σ > 0. Let R ∈ R n×n be a perturbation matrix, such that its entries |R ij | < ϵ/2, ∀(i, j), and 0 < ϵ < σ 2 /3n 3 . Let h min be a smallest magnitude of the altitude of the simplex corresponding to the matrix M + R. One has thatEQUATION)Lemma 16 guarantees that if the width of the ground truth simplex is relatively large compared to the diameter of the confidence set, then the heights of the estimated simplex are also large. We now provide an example of a collection of permutation orders corresponding to a set of vertices as follows.Proposition 17. Fix any ω ∈ S n , consider the collection of permutation P = {ω, ωs 1 , . . . , ωs n-1 } and matrix M = [ϕ ω ′ ] ω ′ ∈P . The width of the simplex that corresponds to M , is upper bounded as ϑ(M ) ≥ 0.5ςn EQUATIONthe Common-Points-Picking algorithm returns a point in E-Core with probability at least 1 -δ.While the choice of vertices in Proposition 17 achieves polynomial sample complexity, the width of the simplex decreases with dimension growth, hindering its sub-optimality. An alternative choice of vertices is those corresponding to cyclic permutation, denoted as C n ⊂ S n , which have a larger width in large subsets of strictly convex games (as observed in simulations) but can be difficult to verify in the worst case. We refer readers to Appendix A.4 for the detail simulation and discussion on the choice of set of n vertices. Based on this observation, we achieve the sample complexity which better dependence on n as follows.Theorem 19. Suppose Assumption 4 holds. Let P = S n the collection of cyclic permutations, and denote the coordinate matrix of the corresponding vertices as W . Assume that the width of the simplex ϑ(W ) ≥ nς c W for some c W > 0. Then, for any δ ∈ [0, 1],if number of samples isEQUATIONthe Common-Points-Picking algorithm returns a point in E-Core with probability at least 1 -δ.It is worth noting that our algorithm does not require information about the constants of the game ς, c W ; instead, the number of samples required automatically scales with these constants. This indicates that our algorithm is highly adaptive and requires fewer samples for benign game instances.Remark 20 (Comment on sample complexity lower bounds). Deriving a lower bound is indeed important, but comes with several significant challenges. E.g., one possible direction is to extend the game instances in Theorem 7. However, there are two key technical issues with this idea: (1) Modifying the face game instance to ensure strict convexity is challenging; (2) It remains unclear how to generalize two face-game instances into poly(n) game instances such that their cores do not intersect and the statistical distance of the reward can be upper bounded, which is crucial for showing poly(n) dependencies in the lower bound (we refer the reader to appendix E.2 for further discussions). Given the unresolved challenges, deriving a lower bound remains an open question. 
experiment: 
 To illustrate the sample complexity of our algorithm in practice and compare it with our theoretical upper bound, we have conducted a simulation as described below. Code is available at: https: //github.com/NamTranKekL/ConstantStrictlyConvexGame.git.Simulation setting: We generate convex game of n players with the expected reward function f defined recursively as follows:For each S ⊂ N s.t. i / ∈ S, f (S ∪ {i}) = f (S) + |S| + 1 + 0.9ω.for some ω sampled i.i.d. from the uniform distribution Unif([0, 1]). We then normalize the value of the reward function within the range [0, 1]. It is straightforward to verify that the strict convexity constant is ς ≈ 0.1/n. From the simulation results in Figure 2 (LHS), we can see that the growth pattern nearly matches that of the theoretical bound given in Theorem 19, indicating that our theoretical bound is highly informative.Moreover, to demonstrate that our algorithm is robust even when the strict convexity assumption is violated, we ran a simulation where the characteristic function is only convex, i.e., the strict convexity constant is arbitrarily small, as follows:f (S ∪ {i}) = f (S) + |S| + 1 + ω.We use the cyclic permutations C n as the input for the algorithm. In Figure 2 (RHS), one can see that the number of samples required as n grows is sub-exponential, indicating that our algorithm is robust when the strict convexity assumption is violated.  
conclusion and future work: 
 In this paper, we address the challenge of learning the expected core of a strictly convex stochastic cooperative game. Under the assumptions of strict convexity and a large interior of the core, we introduce an algorithm named Common-Points-Picking to learn the expected core. Our algorithm guarantees termination after poly n, log(δ -1 ), ς -1 samples and returns a point in the expected core with probability (1 -δ). For future work, we will investigate whether the sample complexity of our algorithm can be further improved by incorporating adaptive sampling techniques into the algorithm, along with developing a lower bound for the class of games. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification: This paper does not release new assets Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.• The paper should discuss whether and how consent was obtained from people whose asset is used.• At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA]  
 
 Appendix: A. A.1 Proof of Theorem 7Here and onwards, we adopt the following notation convention: for real numbers a, b ∈ [0, 1], KL (a, b) represents the KL-divergence KL (p, q) where p, q are probability distributions on {0, 1} such that p(1) = a, q(1) = b. In other words,KL (a, b) = a ln a b + (1 -a) ln 1-a 1-b .Lemma 21 ([16] ). For any 0 < ε < y ≤ 1, KL (y -ε, y) < ε 2 /y(1 -y).Before stating the proof of Theorem 7, let us introduce some extra notations. Given a game G = (N, P), with the expected reward function µ, we define the following.• H C (G) := {x ∈ R n | x(C) = µ(C)}is the hyperplane corresponding to the effective allocation w.r.t coalition C.• E-Core(G) is the expected core of the game G.• F C (G) := E-Core(G) ∩ H N \C (G) is facet of the E-Core corresponding to the coalition C.We use the following definition of the face games in Theorem 7, introduced by [14] .EQUATION[14] showed that the expected core ofG(C) is exactly the facet of E-Core(G) corresponding C, that is, E-Core(G(C)) = F C (G).As noted in [32] , one can decompose the reward function of the face game as follows. For any S ⊂ N , we have thatEQUATIONWe now proceed the proof of Theorem 7.Proof of Theorem 7 . Denote the set convex games with Bernolli reward as GB, that is,GB = {G = (N, P) | P = {P S } S⊆N ; P S ∈ M({0, 1}), ∀S ⊆ N }.Face-game instances and the distance between their E-Core. We first define two games, G 0 and G 1 , with a full-dimensional E-Core, such that G 1 is a slight perturbation of G 0 . Next, we define face games corresponding to G 0 and G 1 using the perturbed facet. We then show that the distance between the cores of these two face games is at least some positive number ε > 0.Define a strictly convex game G 0 := (N, P) ∈ GB, such that µ 0 (S) := E r∼P S [r], and assume that µ 0 is ς-strictly supermodular. Now, fix a subset C ⊂ N , let define a perturbed game instanceEQUATIONfor some0 < ε < ς. It is straightforward that G 1 is (ς -ε)-strictly convex.Therefore, E-Core(G 0 ) and E-Core(G 1 ) are both full-dimensional.Fixing a coalition C ⊂ N , we now construct the face games from G 0 , G 1 as in Definition 22.Let G 0 (C) := (N, P C ), G 1 (C) := (N, Q C ) ∈ GB, whose expected rewards µ 0 F C and µ 1 F C are defined by applying (19) to µ 0 and µ 1 respectively. Now, we consider the difference between the expected reward function of these two games.EQUATIONAs one can always decompose the set S = (S ∩ C) ∪ (S ∩ N \ C), by the decomposibility of the face game (20) , we has thatEQUATION)As the core of face game G 0 (C) and G 1 (C) lie on the hyperplane corresponding to the coalition N \ C, and the distance between the hyperplanes of G 0 and G 1 is ε, which lower bounds the distance between the expected core of G 0 (C) and G 1 (C). In particular, asEQUATIONThe KL distance and imposibility of learning low-dimensional E-Core. We show that, with probability δ ∈ (0, 0.2), any learner cannot distinguish between G 0 (C) and G 1 (C) given there are finite number of samples. We use the information-theoretic framework similar which is well developed within multi-armed bandit literature.We first upper bound the KL-distance betweenP C S , Q C S , ∀S ⊂ N . Denote c 1 := min S⊂N µ 0 F C (S)(1 -µ 0 F C (S)) > 0, by Lemma 21, we have thatKL P C S , Q C S = KL µ 0 F C (S), µ 1 F C (S) ≤ ε 2 c 1 , ∀S ⊂ N.Define the probability space Ψ = 2 N × {0, 1}. Fix any algorithm (possibly randomised) A. At round t, denote (S t , r t ) ∈ Ψ as the coalition selected by the algorithm and the reward return by the environment. At round s < t, denote ν t 0 , ν t 1 as the probability distribution over Ψ t determined by A and P, Q accordingly. generalised permutahedra and polymatroids; it was also shown in [25] that the core of each convex game is a generalised permutahedron.For any ω ∈ S n , let I ω = (ω(1), ..., ω(n)).The n-permutahedron is defined as Conv ({I ω | ω ∈ S n }). A generalised permutahedron can be defined as a deformation of the permutahedron, that is, a polytope obtained by moving the vertices of the usual permutohedron so that the directions of all edges are preserved [21] . Formally, the edge of the core corresponding to adjacent vertices ϕ ω , ϕ ωsi can be written asEQUATIONWhere, k ω,i ≥ 0, and e 1 , . . . e n are the coordinate vectors in R n . If the game is ς-strictly convex, k ω,i > ς.We utilise the formulation of edges of the generalized permutahedron as described in Subsection A.2 to calculate the matrix of coordinates for the vertices of E-Core. Based on the matrix of coordinates, we now state the proof of Proposition 17.Proof of Proposition 17. As the set of vertices is ϕ ω and its n -1 neighbors, there are only two cases to consider. First, we need to consider the matrix created by using ϕ ω as the reference, that is coM(M, 1). As the neighbors have the same roles, bounding the width of the matrices using any neighbor as a reference point can be done identically. Therefore, we will prove the theorem for coM(M, 2), and the proof for coM(M, i), i ̸ = 1 can be done in the same manner. Let us denote V = coM(M, 1) =            c 1 0 0 • • • 0 0 -c 1 c 2 0 • • • 0 0 0 -c 2 c 3 • • • 0 0 . . . . .EQUATIONU = coM(M, 2) =              -c 1 -c 1 -c 1 -c 1 • • • -c 1 -c 1 c 1 c 1 + c 2 c 1 c 1 • • • c 1 c 1 0 -c 2 c 3 0 • • • 0 0 0 0 -c 3 c 4 • • • 0 0 . . . .EQUATIONin which each c i > ς.We will exploit the following norm inequality in the proof. For any A 1 , . . . , A n ∈ R, we use the following inequality (norm 2 vs. norm 1 of vectors)EQUATION)Consider V. Consider a unit vector x = (x 1 , ..., x n-1 ). We haveEQUATIONApplying the Ineq. (31) forA 1 = c 1 x 1 , A 2 = -c 1 x 1 + c 2 x 2 , A n-1 = -c n-2 x n-2 + c n-1 x n-1 , A n = -c n-1 x n-1 gives ∥V x∥ 2 ≥ c 2 1 x 2 1 n ≥ ς 2 x 2 1 n ; ∥V x∥ 2 ≥ c 2 1 x 2 1 + (-c 1 x 1 + c 2 x 2 ) 2 ≥ c 2 2 x 2 2 n ≥ ς 2 x 2 2 n ;. . .EQUATIONTherefore,n∥V x∥ 2 ≥ ς 2 (x 2 1 + • • • + x 2 n-1 ) n = ς 2 n (34) Therefore ∥V x∥ ≥ ς/n, hence σ n-1 (V ) ≥ ς/n.Consider U. Similarly, consider a unit vector x = (x 1 , ..., x n-1 ). We haveEQUATIONApplying the Ineq. (31) forEQUATIONFrom that, we have that2n∥U x∥ 2 ≥ ς 2 x 2 1 n 2 + x 2 2 n + • • • + x 2 n-1 n ≥ x 2 1 + ... + x 2 n-1 n 2 = ς 2 n 2 , as ∥x∥ = 1 (38) That is, ∥U x∥ ≥ ς 2 √ 2n 3 . Therefore, σ n-1 (U ) ≥ ς 2 √ 2n 3 .Therefore, we have that ϑ(M ) > ς 2 √ 2n 3 .In this subsection, we provide an alternative choice of vertices rather than that in Proposition 17.Recall that, with the choice of vertices in Proposition 17, the lower bound for the width of the simplex diminishes when the dimension increases. This leads to a large dependence of the sample complexity on n. To mitigate this, we investigate other choices of n vertices. To see this, we first recall the equivalence between E-Core and generalized permutahedra as explained in Subsection A.2.However, even in the case of a simple permutahedron, if the set of vertices is not carefully chosen, the width of their convex can be proportionally small w.r.t. n, as demonstrated in the next proposition.In particular, the same choice of vertices as in 17 results in the simplex with diminishing width as follows.Proposition 24. Consider a permutahedron, fix ω ∈ S n , consider the matrix W = [ϕ ω , I ωs1 , I ωs2 , . . . , I ωsn-1 ]. The width of the simplex that corresponds to M , is upper bounded as follows:EQUATION)Proof. The coordinate matrix w.r.t. ϕ ω , that is, coM(M, 1) can be written as follows. V =            1 0 0 • • • 0 0 -1 1 0 • • • 0 0 0 -1 1 • • • 0 0 . . . .EQUATIONTherefore, the Gram matrix is G := V ⊤ V =                  2 -1 0 0 0 • • • 0 0 0 -1 2 -1 0 0 • • • 0 0 0 0 -1 2 -1 0 • • • 0 0 0 .EQUATION)Note that G is a tridiagonal matrix and also Toeplitz matrix, therefore, its minimum eigenvalues has closed form as followsλ n-1 (G) = 2 + 2 cos (n -1)π n = 2 sin 2 π 2n ≤ 5 n 2 ; (42) as sin π 2n ≤ π 2n . Therefore, ϑ(M ) ≤ σ n-1 (V ) = λ n-1 (G) ≤ 3 n .Proposition 24 highlights the challenge of selecting a set of vertices such that the width does not contract with the increasing dimension, even in the case of a simple permutahedron. Denote C n ⊂ S n as the group of cyclic permutations of length n. One potential candidate for such a set of vertices is the collection corresponding to cyclic permutations C n , as described in the next proposition.Proposition 25. Consider the matrix W = [I ω ] ω∈Cn . We have thatEQUATION)Proof. The form of matrix W is as followsEQUATION)The coordinate matrix w.r.t. the first column is as followsEQUATION)Let u ∈ R n-1 be any unit vector, and let z = V u ∈ R n . We have thatEQUATIONLet us consider4 ∥z∥ 2 = 4z 2 1 + 4z 2 2 + • • • + 4z 2 n = 2z 2 1 + [(z 1 + z 2 ) 2 + (z 1 -z 2 ) 2 ] + [(z 2 + z 3 ) 2 + (z 2 -z 3 ) 2 ] + • • • + [(z n-1 + z n ) 2 + (z n-1 -z n ) 2 ] + 2z 2 n ≥ (z 1 -z 2 ) 2 + (z 2 -z 3 ) 2 + • • • + (z n-1 -z n ) 2 = n 2 (u 2 1 + u 2 2 + • • • + u 2 n-1 ) = n 2 .(47)Therefore, we have thatEQUATION)It is straightforward that if one takes any column of W as a reference column, the resulting coordinate matrices have identical singular values. In particular, for any i, j∈ [n] coM(W , i) = P • coM(W , j),where P is a permutation matrix, thus, their singular values are identical. Therefore, we have thatϑ(W ) ≥ n 2 .As a result, the set of vertices corresponding to cyclic permutations is a sensible choice. In case of a generalised permutahedron, let us defineEQUATION)As generalised permutahedra are deformations of the permutahedron, we expect that ϑ(W ) is reasonably large for a broad class of strictly convex games. In particular, we consider the class of strictly convex games in which the width ϑ(W ) is lower bounded, as in the following assumption:Assumption 26. The width of the simplex that corresponds to W in (49) is bounded as followsEQUATION)for some constant c W > 0. These parameters will eventually play a crucial role in determining the number of samples required using this choice of n permutation orders. Although proving an exact upper bound for c W in all strictly convex games is challenging, we conjecture that c W is relatively small in a large subset of the games.To investigate Assumption 26, we conducted a simulation to compute the constant c W of the minimum singular value σ n-1 (M ).For each case where n takes values of (10, 50, 100, 150, 200, 300, 500, 1000), the simulation consisted of 20000 game trials with ς = 0.1/n. As depicted in Figure 3 , the values of c W tend to be relatively small and highly concentrated within the interval (0, 30). This observation suggests that for most cases of strictly convex games, c W remains reasonably small. Consequently, our algorithm exhibits relatively low sample complexity. Code of the experiment is available at: https://github.com/NamTranKekL/ ConstantStrictlyConvexGame.git.For each case where n takes values of (10, 50, 100, 150, 200, 300, 500, 1000), the simulation consisted of 20000 game trials with ς = 0.1/n. As depicted in Figure 3 , the values of c W tend to be relatively small and highly concentrated within the interval (0, 30). This observation suggests that for most cases of strictly convex games, c W remains reasonably small. The results indicate that c W tends to be relatively small with high probability, and does not depend on the value of n.Proof of Proposition 5. For each C p , choose a point in its interior, denote as x p . As there are at most n -1 points {x p } p∈ [|P|] , there exists a (n -2)-dimensional hyperplane H that contains {x p } p∈ [|P|] . Let H be a hyperplane parallel to H and let the distance D(H, H) be arbitrary small.As confidence sets are full-dimensional (n -1), H must also intersect with the interiors of all confidence sets. Since H and H are parallel, any convex hull of points within H and H cannot intersect. Therefore, there is no common point.Proof of Proposition 9. The proof spirit is similar to that of Proposition 5.Let H be the (n -2)-dimensional hyperplane that intersects with the interiors of all confidence sets. Let H be a hyperplane parallel to H and let the distance D(H, H) be arbitrary small.As confidence sets are full-dimensional, H must also intersect with the interiors of all confidence sets. Since H and H are parallel, any convex hull of points within H and H cannot intersect. Therefore, there is no common point.The proof of Theorem 11 is a combination of the classic hyperplane separation theorem and the following lemma.Lemma 27. Let {C p } p∈[n] be mutually disjoint compact and convex subsets in E n-1 . Suppose there does not exist a (n -2)-dimensional hyperplane that intersects with all confidence sets C p , ∀p ∈ [n], then for each p ∈ [n]EQUATION)Proof. We prove this lemma by contra-position, that is, if there is C p such thatC p ∩ Conv   p̸ =q C q   ̸ = ∅;then there exist a hyperplane that intersects with all the C p , ∀p ∈ [n].First, assume there is a point x = C p ∩ Conv q̸ =p C p . By Carathéodory's theorem, there are atEQUATION)As each x k ∈ C q for some C q , one can rewrite the equation above asEQUATION)Furthermore, we can writex k ∈Cq α k x k = αq xq , in which, xq := k: x k ∈Cq α k x k k: x k ∈Cq α k, and αq :=EQUATION)Since C q is convex, xq ∈ C q . Substituting (54) into (52), one obtainsEQUATION)Define H as a hyperplane that passes through all xq , we have that x ∈ H.Second, we now show how to construct a hyperplane that intersects with all C m , m ∈ [n]. Let I be the set of indices such that C q ∋ xq . We have two following cases.(i) First, if |I| = n -1, then H is the (n -2)-dimensional hyperplane that intersect with all C m , m ∈ [n].(ii) Second, if |I| < n-1, for any C q ′ ̸ = C p that does not contain any xq , we choose any arbitrary point x q ′ ∈ C q ′ . As there are n -1 points of xq and x q ′ , there exists a hyperplane H that contains all these points. Furthermore, H must contain x, so it is the (n -2)-dimensional hyperplane that intersects with all sets C m , ∀m ∈ [n]. Now, we state the proof of Theorem 11.Proof of Theorem 11. As a result of Lemma 27, we have that for all C p , ∀p ∈ [n],EQUATION)Therefore, by the hyperplane separation theorem, there must exist a hyperplane that separates C p andConv q̸ =p C q .Proof of Lemma 13. Let us denote ∆ n as Conv {x p } p∈ [n] . As there is no hyperplane of dimension n -2 go through all the set C p , the simplex ∆ n is (n -1) dimensional. We have thatp∈[n] E p ⊆ ∆ n ⇐⇒ ∆ c n ⊆ p∈[n] E c p ;where E c p is the complement of the set E p . We will prove the RHS of the above. Consider x ∈ ∆ c n , as ∆ n is full dimensional, x can be uniquely written as affine combination of the vertices, that is,x = p∈[n] λ p x p , p∈[n] λ p = 1. As x ∈ ∆ cn , there must exist some λ k < 0. Now, we shall prove x ∈ E c k . Consider the following,EQUATIONThe above inequality holds since v k , x k < c k and λ k < 0. Therefore, x ∈ E c k . This means thatEQUATIONProof of Theorem 14. Before proceeding the main proof, we show two simple consequences of the construction of H p (Q), p ∈ [n] and the assumption (14) .Fact 1: Consider p ∈ [n], H p (Q) acts as a separating hyperplane for C p . To see this, assume that H p (Q) is not a separate hyperplane for C p , then there exists z p ∈ C p such that ⟨v p , z p ⟩ ≥ c p . From (13), we have ⟨v p , x p ⟩ ≤ c p + max q∈[n]\p diam(C p ). Then, there are two cases. First, assume that ⟨v p , x p ⟩ ≤ c p . As x p , z p ∈ C p and ⟨v p , z p ⟩ ≥ c p , there must exist a point x in the line segment [x p , z p ] such that ⟨v p , x⟩ = c p . This means that D(C p , H p ) = 0, which violates assumption (14) . Second, assume that c p ≤ ⟨v p , x p ⟩ ≤ c p + max q∈[n]\p diam(C p ). Then, we have thatD(C p , H p ) ≤ D(x p , H p ) = | ⟨v p , x p ⟩ -c p | ≤ max q∈[n]\p diam(C q ).This also violates assumption (14) . This implies that if ( 14) is satisfied,H p (Q) must separate C p from ∪ q̸ =p C q .Fact 2: The distance from any point in C q from H p (Q) is bounded as follows. For x ∈ C q , q ̸ = p, we have thatEQUATIONNow, we proceed to the main proof. For the ease of notation, we simply write H p for H p (Q).First, from assumption ( 14), we has that for any p ∈ [n],EQUATIONWe have that minEQUATIONSecond, we shows that how to pick a common point which exists when (61) is satisfied. Let us choose a collection of points x p ∈ C p , p ∈ [n], and definex ⋆ = 1 n p∈[n] x p . Now, we show that x ⋆ ∈ E p , ∀p ∈ [n].For each p ∈ [n], consider H p . We denoteζ pp := c p -⟨v p , x p ⟩ > 0; ζ pq := ⟨v p , x q ⟩ -c p > 0, q ̸ = p.Note that D(x, H p ) = | ⟨v p , x⟩ -c p |. Follows (61), we have thatEQUATIONNow, let considerEQUATIONTherefore, x ⋆ ∈ E p . As it is true for all E p , one has thatEQUATIONFinally, by Lemma 13, we can conclude that x ⋆ is a common point.Proof of Lemma 16. Denote ∆ as the simplex corresponding to M = [x 1 , ..., x n ], ∆ i as the facet opposite the vertex x i , and h i (∆) is the height of simplex w.r.t. the vertexx i . Denote Vol k (C) as the k-dimensional content of C ⊂ E n-1, where dim(C) = k. Using simple calculus, one has thatEQUATIONWe also denote ∆ as the perturbed simplex corresponding to M + R and ∆i as the facet opposite the to the perturbation of x i .we bound the height h i ( ∆) for all i ∈ [n -1]. For the height h n ( ∆), one can apply similar reasoning. Let define the coordinate matrix and the pertubation matrix w.r.t x n as followsEQUATIONWe have that |U ij | < ϵ, ∀i, j. By the definition of width ϑ(M ), we have thatEQUATIONLet define the Gram matrix and perturbed Gram matrix as followsEQUATIONOne has that, Ĝ -G = V ⊤ U + U ⊤ V + U ⊤ U := U . One has that U ij ≤ ε := 3nϵ, as |V ij | < 1 and |U ij | < ϵ < 1.We also has that ∥U ∥ ≤ ∥U ∥ F ≤ nε.First step. we bound the quantity |det(G+U)-det(G)| |det(G)|. By [15] 's Corollary 2.14, one has thatEQUATIONAsEQUATIONEQUATIONIt means thatEQUATIONSecond step. we bound the change in content of the i th facets of the simplex, for i ∈[n -1].Consider the facet that is opposite to the vertex x i , and denote V (i), U i as the sub-matrices of V, U by removing i th column. Denote the Gram matrixEQUATIONNote that one can obtain G(i), Ĝ(i) and by removing i th row and column of G(i), Ĝ(i) respectively. Denote U (i) := Ĝ(i) -G(i), we has that all entries of U (i) smaller than ε.Moreover, by Singular Value Interlacing Theorem, one has thatEQUATIONSimilarly, one has thatEQUATIONIt means thatEQUATIONThird step. We bound the height h i corresponding to the vertices x i in this step. For i ∈EQUATIONFurthermore, by the Eigenvalue Interlacing Theorem, we havedet(G)/det(G i ) ≥ σ n-1 (G) ≥ σ 2 .Putting things together, one has thath i ( ∆) = 1 n -1 Vol n-1 ( ∆) Vol n-2 ( ∆i ) = det(G + U ) det(G(i) + U (i)) ≥ k -1 k + 1 det(G) det(G(i)) ≥ σ σ 2 -6n 3 ϵ σ 2(78) We note that, the above holds true for i ∈ [n -1].Step. Now, we bound the height corresponding to the vertex x n . We can define the coordination matrix and pertubation matrix w.r.t x 1 as follows.V ′ = coM(M, 1), U ′ = coM(R, 1).(79)Note that, by the definition of the width, we have thatEQUATIONand also, |U ′ ij | ≤ ϵ. Similarly, applying Steps 1-3, we also have thath n ( ∆) ≥ σ 2 -6n 3 ϵTherefore, h i ( ∆) ≥ √ σ 2 -6n 3 ϵ holds true for all i ∈ [n]. We conclude thatEQUATIONwhenever, ϵ ≤ σ 2 3n 3 .Proof of Theorem 18. Note that |P| = n. Denote ϵ 0 := 2 max p∈[n] diam(C p ). For any ω p ∈ P, define the eventE = {ϕ ωp ∈ C p , ∀p ∈ [n]}By the construction of the confidence set, we guarantee that E happen with probability at least 1 -n 2 δ.Consider p ∈ [n], for any q ∈ [n] \ p, let x q be the projection of ϕ ωq onto H p , and x p := arg min p∈Cp D(x, H p ). We have thatD(x k , ϕ ω k ) ≤ ϵ 0 , ∀k ∈ [n].We . Let R := M -M be the perturbation matrix, one has that R ij ≤ ϵ 0 , ∀(i, j). By Lemma 16, we have thatD(x p , H p ) ≥ σ 2 -12n 3 ϵ 0 (82)Therefore, for D(x p , H p ) ≥ nϵ 0 holds , it is sufficient to provide the condition for σ such thatEQUATIONAssuming that ϵ 0 < 1, for the condition of Lemma 16 and the above inequality to hold, it is sufficient to chooseϵ 0 = σ 2 13n 3 .Now, we calculate the upper bound for sample needed. At epoch K, we have thatEQUATIONThen we have K = O n 13 log(nδ -1 ς -1 )ς 4. As each phase, there are at most n 2 queries, then the total number of sample needed isEQUATIONfor the algorithm to return a common point, with probability of at least 1 -δ.Proof of Theorem 19. The proof is identical to that of Theorem 18, with the width of the simplex bounded by ϑ(W ) ≥ nς c W .Consider a facility-sharing game (a generalisation of cost-sharing games [2, 1] ) where joining a coalition S would provide each player of that coalition a utility value v(k) where |S| = k, and they have to pay an average maintenance cost c(k). The expected reward of S is defined as µ(S) = v(k) -c(k), representing the average utility of its coalitional members. This setting represents many real-world scenarios, such as:• University departments together plan to set up and maintain a shared computing lab. The value of using the lab is the same v(k) = v for each department (e.g., their students can have access computing facilities), but the maintenance cost c(k) is monotone decreasing and strictly concave (e.g., the more participate the less the average maintenance cost becomes).An example to such maintenance cost function is, e.g., c(k) = C 1 -C 2 k α , where α > 1 and C 1 , C 2 are appropriately set constants such that the total maintenance cost kc(k) = C 1 k -C 2 k (α+1) is non-negative and monotone increasing in the [0, n] range (n is the total number of departments). A coalition S here represents the cooperating departments.• An international corporate is expanding its international markets via mutual collaborations with multiple local companies. The cost for each potential local member company to join the consortium is fixed c (e.g., integration cost), while the benefit they can gain through this collaboration, v(k), is a strictly monotone convex function in the number of local markets k (assuming that each local partner is in charge of their own local market), due to the potential synergies between different markets. An example benefit/utility function is, e.g., v(k) = k α with α > 1. The corporate's task is then to invite local companies to join their coalition/consortium S.• (An alternative version of airport games) Airlines decide whether they launch a flight from a particular airport. The more airlines decide to do so, the higher value v(k) (e.g., more connection options), and the lower average buy-in cost c(k) (e.g., runway maintenance, staff cost etc.) each airlines can have. It's reasonable to assume that v(k) is strictly convex and monotone increasing (e.g., the number of connecting combinations grows exponentially) and c(k) is monotone decreasing and strictly concave. Those airlines who decide to invest into that airport will form a coalition.For each of the scenarios above, we can see that the expected reward function µ(S) = v(|S|) -c(|S|) is indeed strictly supermodular. The reason is that v(k) and c(k) are discrete and finite on [0, n], and thus, we can easily find ς > 0 for which these games also admit ς-strict convexity.E.1 Comparison with Pantazis et al. [20] While the algorithm in [20] is proposed for general cooperative games and conceptually applicable to the class of strictly convex games, we argue that their algorithm is not statistically and computationally efficient when applied to strictly convex games, due to the absence of a specific mechanism to leverage the supermodular structure of the expected reward function. In particular, firstly, we argue that without any modification and with bandit feedback, their algorithm would require a minimum of Ω(2 n ) samples. Secondly, although we believe the framework of [20] could be conceptually applied to strict convex games, significant non-trivial modifications may be necessary to leverage the supermodular structure of the mean reward function.Appplying [20] to strictly convex games without any modifications. We first briefly outline their algorithmic framework. In this paper, the authors assume that each coalition S ⊂ N has access to a number of samples, denoted as t S > 1. For each coalition S, the empirical mean is denoted as µ t S (S), and a confidence set for the given mean reward is constructed, denoted as,C(µ(S)) = μ(S) ∈ [0, 1] | |μ(S) -µ t S (S)| ≤ ε t S , for some ε t S > 0 .We note that while the algorithm in [20] constructs the confidence set using Wasserstein distance, in the case of distributions with bounded support, we can simplify it by using the mean reward difference. After constructing the confidence set for the mean reward of each coalition, the algorithm solves the following robust optimization problem:min x∈R n ∥x∥ 2 2 s.t. x(N ) = µ(N ) x(S) ≥ sup(C(µ(S)), ∀S ⊂ N.That is, finding the stable allocation for the worst-case scenario within the confidence sets. It is clear that when directly applying this framework to the bandit setting, each coalition must be queried at least once, that is t S > 1. This inevitably leads to a complexity of Ω(2 n ) samples, regardless of the sampling scheme one employs. In term of computation, with 2 n -2 confidence sets for all coalitions S ⊂ N , tabular representation of the confidence set incurs extreme computational cost.Significant modifications required for [20] . As described above, the algorithm in [20] suffers from 2 n sample complexity, and the main reason is because it requires constructing confidence sets for the mean reward for all coalitions S ⊂ N . As such, if we want to apply their algorithm efficiently to the bandit setting, we need to address this limitation.To do so, one may need to develop an approach to design a confidence set for a specific class of strictly convex games. For instance, we can consider the following approach: Given historical data, instead of writing a confidence set for each individual coalition, let us define a confidence set for the mean reward function as follows:EQUATIONwhere the confidence set C(µ(S)) could potentially be [0, 1] for some coalition S, as there is no data available for these coalitions. Let Core(μ) be the core with respect to the reward function μ.We propose a generalization of the framework from the robust optimization problem to adapt to the structure of the game as follows.EQUATIONThat is, we find a stable allocation x for every possible supermodular function within the confidence set of the reward function.However, implementing and analyzing this approach may pose significant challenges. The first challenge lies in constructing a tight confidence set [C(µ(S))] S⊂N such that all functions within this collection are strictly supermodular. We are not aware of a method to explicitly construct [C(µ(S))] S⊂N containing only strictly supermodular functions, and we believe this set could potentially be very complicated. To illustrate, consider the scenario where we have samples from two coalitions, {1} and {1, 2}, with the following empirical means:µ({1}) = 0.11; µ({1, 2}) = 0.1This situation might occurs when the number of samples is insufficient. In such cases, regardless of the value chosen for the remaining coalition rewards in the function µ(S), µ(S) is not supermodular (as {1} ⊂ {1, 2}, yet µ(1) > µ(1, 2)). Consequently, either the confidence set C(µ(1)) or C(µ(1, 2)) does not contain the empirical mean reward, indicating the highly complicated shape of the confidence set.The second challenge is that while computing a stable allocation for a given supermodular reward function μ is a straightforward task, computing a stable allocation for all supermodular reward functions in the confidence set C(µ) in a computationally efficient way is an open problem, to the best of our knowledge.The discussion above also highlights the key difference between our work and that of [20] : Instead of explicitly constructing the confidence set of the expected mean reward function to integrate the supermodular structure for computing a stable allocation, which might be a sophisticated task, we directly exploit the geometry of the core of strictly convex games. Specifically, in strictly convex games, each vertex of the core corresponds to a marginal vector with respect to some permutation orders. Given that one can construct the confidence set of marginal vectors easily, our method is conceptually and computationally simpler. However, we believe that adopting the more general framework of robust optimization as presented in [20] is a very interesting, but non-trivial, direction, and we leave it for future work.It is also crucial to develop the lower bound for the class of strict convex game. One promising direction is to extend the game instances in Theorem 7. However, there could be several technical issues when it comes to deriving a meaningful lower bound for strictly convex games. The main problem is twofold: Firstly, not every small perturbation of the face game may result in a strictly convex game; therefore, careful tailoring to ensure strict convexity is required. Second, to show a polynomial dependence of sample complexity on n, we need to generalise the two game instances in Theorem 7 into poly(n) game instances for the information-theoretic argument. It is not clear how to construct them so that their core has no intersection, and the statistical distance of the reward can be upper bounded. This can be further detailed as follows:Firstly, as proven in [14] , a face game is only guaranteed to be a convex game, and not all perturbations of it can result in a strictly convex game. In fact, we believe great care is required to ensure that the perturbations of the face games are strictly convex, thereby allowing them to be used to derive lower bounds for strictly convex games. Moreover, even if one can guarantee that the perturbation of the two face-game instances in Theorem 7 is strictly convex, they can only result in a very loose lower bound. Particularly, The two game instances in Theorem 7 are originally constructed using two strictly convex games G 0 and G 1 , whose expected rewards differ in only one coalition, denoted as C ⊂ N . This setup simplifies the computation of the statistical distance of the face-games which are perturbations of G 0 and G 1 corresponding to the same coalition C. However, since only two game instances are used to derive the result of Theorem 7, if we employ fully-dimensional-core perturbed game instances of them, the resulting lower bound will be independent of the dimension n. In other words, the finite-sample lower bound can be very loose and does not show any dependence on the dimension n.Secondly, generalising the approach to poly(n) game instances is not straightforward, as it requires choosing poly(n) coalitions to perturb the rewards of the original game G 0 , not just one coalition. This results in significant differences in the expected reward functions of the corresponding face games, as each face game is a perturbation with respect to several different coalitions. Consequently, upper-bounding the pairwise KL distance between these games is highly nontrivial and would require sophisticated exploitation of the structure of strictly convex games.NeurIPS Paper Checklist 


Decision: The paper studies the problem of finding the core for the reward allocation problem when the information about reward functions is incomplete. Specifically, this paper assumes that we have access to an oracle that takes as input a coalition and outputs a stochastic reward for that coalition. The paper obtains an algorithm for the special case of strictly convex games which outputs a point in the expected core and with high probability uses at most a polynomial number of samples.

The paper studies an interesting problem, and provides an elegant solution for it. The paper is well-written. For this reason, we recommend 
 acceptance. Anyway, it would be desirable that authors revise the paper by including more motivations and discussion about the large sample complexity, and the validity of the assumption of strict convexity, as highlighted by the discussion.

Reviews: review: paper_summary: paper_summary: The paper studies the problem of finding the core for Reward allocation
when the information about reward functions is incomplete.
Specifically, previous works either study deterministic
games and assume that the reward function is known, or study stochastic games
and assume that the reward distribution is known.
In contrast, this paper assumes that we have access to an oracle
that takes as input a coalition and outputs a stochastic reward for that coalition.
The paper obtains an algorithm for the special case of strictly convex games
which outputs a point in the expected core and with high probability uses as most
a polynomial number of samples.

The main idea behind the algorithm is as follows. If there was no issue with the noise,
then one could simply take the marginal vector of an arbitrary distribution as done by [21].
The noise prohibits us from estimating this vector exactly however and one can form only a confidence set.
The main idea is to form multiple confidence sets around multiple marginal vectors.
Next, we look for *common points* which are points $p$ with the following property:
if we choose one arbitrary point from each of the confidence sets, and calculate
the convex combination of these points, then this will contain $p$. 
Perhaps surprisingly, this set is non-empty.
strength_weakness: strength_weakness: - It would be good to obtain a lower bound.
  As is, the sample complexity is a (large) polynomial in $n$.
  Not clear to what extent this can be improved.
  While the authors discuss this briefly, it is an important drawback of the work.
questions: questions: Questions:
- Are there any works that are similar to yours in terms of techniques?
  Seems to me like similar ideas should appear in the bandits literature but the only citation
  I can find is [14].


Typo: Equation 2 should require $C \ne S$.
limitations: limitations: N/A
paper_summary: paper_summary: This paper studies the problem of learning the expected core when only bandit feedback is available, under the assumption that the problem is strictly convex. They proposed Common-Point-Picking (CPP) algorithm that returns a point in the expected core given an oracle that provides noisy samples of the unknown (full-dimensional) simplex's vertices. Sample complexity analysis is provided.
strength_weakness: strength_weakness: Although the paper is basically theoretical, I would appreciate it if simulation results could be provided. For example, the authors could plot the actual number of samples used to reach the given precision to validate the sample complexity results. Also, as this paper is motivating CPP using geometric intuitions, some illustrations about this would be helpful. Currently, the only simulation result is providing empirical evidence of the conjecture that $C_W$ is relatively small. Moreover, although full-dimensionality is used as an intuition for assuming strict convexity, the latter seems too strong.
questions: questions: - Figure 2 shows that $C_W$ tends to be long-tailed, which makes the empirical validation relatively weak. Could the authors comment more on this?
- If the strict convexity assumption is replaced with purely the full dimensionality assumption, do the authors expect CPP to work?
limitations: limitations: I don't see any limitations or potential negative societal impact of this work.
paper_summary: paper_summary: The paper tries to find an expected core under the assumption that a characteristic function is $\varsigma$-strictly convex cooperation game. 
The authors provide a bandit-based sampling algorithm called Common-Points-Picking, which allows us to compute the expected core in a polynomial number of samples.
They prove that strictly convex is a sufficient condition to find an expected core with the polynomial number of samples.
strength_weakness: strength_weakness: w1. My main concern is that the assumption of strict convexity is not very natural while providing the hardness of learnability in a non-strict convexity situation is good.
It would be more better to show the validity of the assumption by showing that some known application of cooperative games satisfies it. For example, it is better to provide a discussion that in some known convex games, such as induced subgraph games with positive weights[1], airport games[2], and some others[3-6], which parameters of these convex games are related to the parameter \varsigma. 

w2. Providing the upper bound of sampling complexity is good, but I cannot measure how tight the bound is. Since the paper provides a discussion of the hardness of calculating the lower bound, providing the tight lower bound of sample complexity is ideal. 

w3. It would be better to discuss other sampling-based algorithms for computing core. For example, [7] provides an FPRAS algorithm for the convex(supermodular) cooperative game, and [8] provides a PAC-learning-based algorithm for finding the core. While they each have different assumptions and problem settings, the discussion about them is useful for readers to clarify where the paper stands.

[1] Deng, X., & Papadimitriou, C. H. (1994). On the complexity of cooperative solution concepts. Mathematics of operations research, 19(2), 257-266.

[2] Littlechild, S. C., and Owen, G. 1973. A simple expression for the shapley value in a special case. Management Science 20(3):370–372.

[3] Oishi, T., & Nakayama, M. (2009). Anti-dual of economic coalitional TU games. The Japanese Economic Review, 60, 560-566.

[4] Graham, D. A., Marshall, R. C., & Richard, J. F. (1990). Differential payments within a bidder coalition and the Shapley value. The American Economic Review, 493-510.

[5] Feigenbaum, J.; Papadimitriou, C. H.; and Shenker, S. 2001. Sharing the cost of multicast transmissions. Journal of computer and system sciences 63(1):21–41.

[6] O'Neill, B. (1982). A problem of rights arbitration from the Talmud. Mathematical social sciences, 2(4), 345-371. 

[7] Liben-Nowell, David, et al. "Computing shapley value in supermodular coalitional games." Computing and Combinatorics: 18th Annual International Conference, COCOON 2012, 2012. 

[8] Igarashi, A., Sliwinski, J., & Zick, Y. (2019). Forming probably stable communities with limited interactions. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 33, No. 01, pp. 2053-2060).
questions: questions: Could you please comment about the weakness comments if I have misunderstood something? The following is a comment rather than a question.

q1. Is there any relationship between totally balanced games [9]? Totally balanced condition is a necessary and sufficient condition for guaranteeing the existence of the core. It may be useful for generalizing the proposed problem setting.

[9] Shapley, L. S., & Shubik, M. (1969). On the core of an economic system with externalities. The American Economic Review, 59(4), 678-684.
limitations: limitations: Yes, they adequately address the limitations.

Comments: comment: Thank you very much for your suggestion. We will incorporate the examples we wrote in the rebuttal phase into the final version of the paper.

Best regards,
The Authors
Thanks for taking the time to address my questions. I have no further question. 

With respect to the assumption that I raised as a main concern, It would be good to add an example the authors wrote in the rebuttal because the convexity assumption is one of the major assumptions in the cooperative game community, but not so much in the machine learning community.
Dear Reviewer,

Thank you for your time and effort in reviewing our paper. We hope our responses have addressed your concerns and questions. If you have any further questions, please don’t hesitate to let us know.

Best regards, 

The Authors
Dear Reviewer,

Thank you for your time and effort in reviewing our paper. We hope our responses have addressed your concerns and questions. If you have any further questions, please don’t hesitate to let us know.

Best regards,
The Authors
Thank you for the response. I have no further questions at this time.