Learning the Expected Core of Strictly Convex Stochastic Cooperative Games
Authors: Nam Phuong Tran
The-Anh Ta
Shuqing Shi
Debmalya Mandal
Yali Du
Long Tran-Thanh
Venue: NeurIPS 2024 poster (2024)
Keywords: Cooperative game theory
convex geometry
bandit theory.
Primary area: algorithmic_game_theory
TL;DR: We address learning stable allocations for stochastic cooperative games with an unknown reward distribution. For strictly convex games, we propose an algorithm that returns a stable allocation with a polynomial number of samples.

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.

Learning the Expected Core of Strictly Convex Stochastic Cooperative Games
Nam Phuong Tran
The Anh Ta CSIRO's Data61 Marsfield, NSW, Australia theanh. cheanh.ta@csirc ta@csiro.....oe au
Shuqing Shi Department of Informatics King's College London London, United Kingdom shuqing. shi mhcklel... ac uk
Department of Computer Science University of Warwick Coventry, United Kingdom
nam.p. p. tranaaarwnicc ac
Debmalya Mandal
Yali Du
Department of Computer Science
Department of Informatics King's College London London, United Kingdom yali du@kcl. ac uk
University of Warwick
Coventry, United Kingdom
debmalya. mandal @warwick mwwcaaaaaaaaaaaaaaaaaaaaaaa ac.uk uk
Long Tran-Thanh Department of Computer Science University of Warwick Coventry, United Kingdom long. tran-thanh@@aat ac uk
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 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 stochastic games. However, this is unrealistic, as the reward function or distribution is often only partially known and may be subject to uncertainty. problem in stochastic cooperative games, where the reward distribution is unknown. Our goal is learn the expected core, that is, the set of allocations that are stable in expectation, given an oracle that returns stochastic reward for an enquired coalition each round. Within the class of strictly convex games, we present an algorithm named core given a polynomial number of samples, with high probability. To analyse the algorithm, we develop new extension of the separation hyperplane theorem for multiple convex sets.
this paper,
consider the core learning
that returns point in the expected
Introduction
The reward allocation problem a fundamental challenge in cooperative games that seeks reward allocation schemes motivate agents 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's
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

behavior. In cooperative MARL, these solution concepts offer framework for distributing team rewards to individual agents, promoting cooperation among players, and preventing the occurrence of lazy learner phenomena [29, 12, 30]. A crucial notion of reward allocation is stability, defined as an allocation scheme wherein no agent has the motivation to deviate from the grand coalition. The set of stable allocations is called the core of the game.
In the classical setting, the reward function is deterministic and commonly known among all agents, with no uncertainty within the game. However, assuming perfect knowledge of the game is often unrealistic, as the outcome of the game may contain uncertainty. This led the study of stochastic cooperative games, dated back to the seminal works of [9, 27], where stability can be satisfied either with high probability, known as the robust core, or in expectation, known as the expected core. However, in these works, the distribution of stochastic rewards is given, allowing agents to calculate the reward before the game starts, which not practical since the knowledge of the reward distribution may only be partially known to the players. When the distribution of the stochastic reward is unknown, the task of learning the stochastic core by sequentially interacting with the environment appears much more challenging. Early attempts [19, 20] studied robust core and expected core learning under full-information, where full information means that the random rewards of all coalitions are observed at each round. However, full-information feedback is strong assumption, which does not hold in many real-world situations. Instead, agents typically observe the reward of their own coalition only (e.g., only know the value of their own action joining a particular coalition in this case), which is typically known as bandit feedback in the online learning literature.
In our work, we focus on learning the expected core, which circumvents the potential emptiness of the robust core in many practical cases. Moreover, instead of full-information feedback, where the stochastic rewards of all coalitions are observed each round, we consider the bandit feedback setting, where only the stochastic reward of the inquired coalition is observed each round. Given the lack of knowledge about the probability distribution of the reward function, learning the expected core using data-driven approaches with bandit feedback is a challenging task.
Against this background, the contribution of this paper is three-fold: (1) We focus on expected core learning problem with unknown reward function, and propose novel algorithm called the -oittnn-ooiittiiiiooe
algorithm, the first of its kind that is designed to learn the expected core with high probability. Notably, this algorithm is capable of returning point in an unknown simplex, given access to the stochastic positions of the vertices, which can also be used in other domains, such as convex geometry. (2) We establish an analysis for finite sample performance of the Common-Pointe Petss-iickng algorithm. The key component of the analysis revolves around a novel extension of the celebrated hyperplane separation theorem, accompanied by further results in convex geometry, which can also be of independent interest. (3) We show that our algorithm returns a point in expected core with at least å probability, using poly(rz ooly,,, log(6-1) number of samples.
2 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 Bayesian setting in a series of papers [5, 7, 8, 6). These works develop framework for Bayesian stochastic cooperative games, where the distribution of the reward is conditioned on 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 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

---

of an empty robust core, as illustrated in [10]. To mitigate the potential emptiness of the robust core, we investigate the learnability of the expected core.
The work most closely related to ours is [20]. in which the authors introduce an algorithm designed to approximate the expected core using a robust optimization framework. In the context of full information feedback, where rewards for all allocations are revealed each round, the algorithm demonstrates asymptotic convergence to the expected core. Furthermore, the authors provide an finite-samples error bound for the distance to the expected core. However, when dealing with bandit feedback, where the reward of the enquired coalition is returned each round, naively applying the algorithm of [20] may result in an exponential number of samples in terms of the number of players. In the bandit feedback setting, as we later establish in Theorem 7 that, general cooperative games, no algorithm can learn the expected core with a finite number of samples without additional assumptions. This highlights the key difference in dealing with bandit feedback compared to full-information feedback. Given this limitation, we narrow our focus to (strictly) convex games, an important class of cooperative games where the expected reward function (strictly) supermodular. By leveraging strict convexity, we introduce the in the expected core with high probability using only a polynomial number of samples. While [20] proposed general algorithm applicable to strictly convex games, we argue that it lacks statistical and computational efficiency due to the absence of a mechanism to exploit the supermodular structure of the expected reward function. Further detailed comparison can be found in Appendix E.
cking algorithm, which efficiently returns point
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 lt E N+, denote [k] as set 21, k).
For n E N+ let E be the n-dimensional Euclidean space, and let us denote D as the Euclidean distance in E", Denote 1, as the vector [L...., 1] E R". Denote (., -) the dot product. For a set C, we denote C' C¹x2 x as the set resulting from eliminating an element x in C. For C C E", let diam(C) == maxa,yec D(x, v). and Conv (C) denote the diameter and the convex hull of C, respectively.
Denote G, := {w [n] + [n] w a bijection] as the permutation group of [n]]. For any collection of permutations P G.. denote wip p E [[P]], 1, as pth permutation order in P. Let 8; == 11) denote the adjacent transposition between i and i + 1. Given set C', we denote by M(C) the space of all probability distributions on C.
Stochastic Cooperative Games. A stochastic cooperative game is defined as tuple (N,P). where N a set containing all agents with number of agents to be [N] n, and (I's E MM[ 1)) S C N) is the collection of reward distributions with Ps to be the reward distri- bution w.r.t. the coalition S. For any coalition S C N, we denote ((S) : Ey-Ps [r] as the expected reward of coalition S. For reward allocation scheme & E R", let xxS) = Eies T3 as the total re- ward allocation for players in S. A reward allocation x is effective if x<N) m(N). The hyperplane of all effective reward allocations, denoted by HN, is defined as H2 x E IR" ((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,
1 (S U (1)) m(S)= 2 م (C (1)) (()),, Vi & SUC and AC CSCN
(1)
Next, we define the notion of strict convexity follows:
Definition 2 (s-Strietly 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
a U (i}) m(S)= Z MCU (C)) p(C) Vi SUC and VC C CSCN
(2)
3

---

Following [20], we define the expected core as follows: Definition 3 (Expected core [20]). The core defined as
E-Core {I R" xxN) ((N); x(S) 2 MS)), AS N..
That is, the F-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 receive more expected reward than if they had stayed in N. Note that, as E-Core C Hy, its dimension is at most (n 1). We say that E-Core is full dimensional whenever its dimension
In convex games, each vertex of the core in the convex game is a marginal vector corresponding to a permutation order [23]. This is special property of convex games, which plays crucial role in our algorithm design. For any w E Gn, define the marginal vector o² E IR" corresponding to w, that is, its jth entry is
of := H(P (i) p (1) ())
(3)
where P. = (i w(f) S w())) It is known from [23] that the expected reward function is strictly supermodular, the E-Core must be full dimensional.
3.2 Problem Setting
In our setting we assume that there is a principal who does not know the reward distribution IP. In each round I, the principal queries a coalition S, C N. The environment returns a vector V2 ~ Pss. assume that the agent knows the expected reward of independently of the past. For simplicity,
the grand coalition μ(N). Additionally, we assume that the convexity of the game, that is, μ is supermodular. Our question is how many samples needed that with high probability 1 - 8, the algorithm returns a point x E E-Core. More particularly, we ask whether or not there an algorithm that output point in the E-Core, with probability least 1 - 5 and the number of queries
T = poly(n, log(o-1)).
As well shall show Theorem 7, 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 in the rest of this paper, we assume that:
Assumption 4. The game is s-strictly convex.
Note that striet convexity immediately implies full dimensionality [23]. which 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.
4 Learning the Expected Core
In this section, we propose a general-purpose Common Poontnt--oon---ooo Point-Piikiii PPickin algorithm that is able to return point of unknown full-dimensional simplex, given an oracle that provides a noisy position of the simplex's 's verticies. Under the assumption that the game is strictly convex, show that, when applying CoimmoonPoonnsssoo Picking algorithm to the s-strictly convex game, it can return a point in E-Core provided the number of samples is (n)y(n,s).
4.1 Geometric Intuition
Given E-Core polytope of dimension (n - 1). In deterministic case when the knowledge of the game is perfect, to compute point in the core, one can query a marginal vector corresponding to permutation order E G, [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 6", we do not precisely compute its position. Instead, we only have information on its confidence set C(d .6), compact (n -iddieensil set. The confidence set contains de with probability at least (1 6), 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 C Gn be collection of permutations, and Q {6tt Wp E P) be the set of

---

vertices corresponding to P. For brevity, we denote Cp := C( up E P. In this section, we assume that the confidence sets contain the true vertices, that is, 80D E Cp. Vp E [[P]]. which can be guaranteed with high probability. It is clear that Conv (Q) C E-Core, since Q is subset of vertices of E-Core. The challenge 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 point in the convex hull of any collection of points in the confidence sets. A sufficient condition to achieve this that, given [P] confidence sets pellp) for each x? Cp.
n Conv (f*") (pe(IP1) & Ø. EEEC
(5)
PE[[PI]
This condition means that there exists a common point among all the convex hulls formed by choosing any point in confidence sets, x" E Cp. We call the above intersection set of common points. The reason why it sufficient condition that this is subset ground simplex, implying that it is in the E-Core. Formally, we have
Conv ({*")pel(pp) }PE(PP)) C Conv (Q) C E-Core;
(6)
EC PE[[P]]
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
Algorithm 1 Common Points Picking
1: Input collection of permutation order P
(wp pepn)
points whenever it is nonempty.
2: = 0, ep 0, Q Ø
3:
while Coopping-Cooniitie (Q, hep) do
We first state necessary condition for the num- ber of vertices of E-Core need to estimate for (5) can be satisfied:
4:
ep <- ep 1;
5:
for E [n] do
6:
for E [n] do
Proposition 5. Assume that all the confidence sets are full dimensional, that is, dC,)(C,) =
7:
Query P.r.
Orcale returns Kep (P:")) t rt-
8:
1, Vp [[P|], and suppose that [P]
9:
+
10: Computing 8; (ep) as (9).
Conv EC PEIIPÍ]
n
Ø.
end for
12:
end for
13: Assign Q Q= (ep) pe(n]
Proposition 5 implies that one needs to estimate at least n vertices to guarantee the existence of common point.
Compute dep as (10)
15: end while
Return x² 1 E (ep).
4.2
CiamoonPooint--iice
Algorithm
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--iccingg whose pseudo code described in Algorithm 1.
The Conmon-Points-PPn Picking Algorithm can be described as follows. First, let us explain the notation. In epoch ep, the variable Top (-) the algorithm represents the reward value of the enquired coalition; 80hh (ep) represents the estimated marginal vector w.r.t. wp. In each epoch ep, assuming that the stopping condition is not satisfied, the algorithm estimates the marginal vectors corresponding to
the collection of given permutation orders Q { (0'0(e))
(lines 6-10). For each p E [n], the pE(N)
estimation can be done by querying the value of the nested sequence pirr, P then estimating the marginal contribution of each player with respect to the permutation order up (line 10). Next, it calculates the confidence bonus bep of the confidence sets and checks the stopping condition for the next epoch. The algorithm continues until the stopping condition satisfied, and then returns the average of the most recent values of the marginal vectors corresponding to P.
P (line 6-7),
The termination of the Common-Points-Picce algorithm (Algorithm 2). which can be described as follows. Consider the case where Q Ø. For each point z² Q. the algorithm attempts to calculate the separating hyperplane Hy(Q), that separates x" from the rest Q \ x" (line 7).
algorithm based on the Stopping-Condite
5

---

The hyperplane (Q(Q) is defined by two param- eters (e R c' E R), where of one of its unit normal vectors, together with cº, satis- fying Eq. (8). Specifically, the second and third equality in (8) implies that (Q) is parallel and at distance Eep (toward x²) from the hyperplane that passes through all the points in Q x.. The fourth equality in (8) guarantees that Hp(Q) is subset of Hy (as the normal vector of Hy is 1,). After computing (Q(Q), the algorithm checks whether the distance from the confidence set Cp to (Q) is large enough (lines 8-12). 12). The stopping condition checks for all E [n]] if no condition violated, then the algorithm returns TRUE. An example of the construction of separating hyperplanes in HN. where n 3 is depicted Figure 1.
Algorithm 2 Stopping Condition
1: Input collection of points Q, confidence bonus bep.
2: Compute Cep = 2
3: if Q = Ø then
4: Return FALSE.
5: end if
6: for p E [n] do
7: Computing Hp (p(Q),ie.
compute (v IR",, ce" l R) such that.
|100112
=
{uP, x))
c² Cep: Vz E Q \ xr.
(UP 22)
< c Copi
(UP, 1n)
0:
(8)
Note that the input of algorithm P can be any collection of permutation orders such that [P] 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 polynomial number of samples.
8:
Computing distance:
hp ia ae <hep
min e - .x).
9: if ho n Eep then
10: Return FALSE.
end if
Remark 6. Most of the computational burden
12: end for
lies in computing the separating hyperplane (Q) for each p (line 7), and calculating the distance between the confidence set C, and H₂ (line 8) in Stopping Condition. Since all tasks be completed within polynomial time w.r.t. n, algorithm is polynomial.
Return TRUE.
There are two challenges regarding the 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 s inequality. Second, we need to define a stopping condi- tion that can guarantee the non-emptiness of the common set and output point in the common set with polynomial number of samples. The second question more involved and requires proving results in convex geometry, includ- ing an extension of the hyperplane separation theorem, shall fully explain in Section 5.
HHQ)
Esp
Eup
Hr(())
Iute
Eup
Figure 1: Set of common points constructed by separating hyperplanes. The intersection half- spaces defined by H₂(Q), Vp E [n]], creates subset of common points. The common points in E-Core. provided that the confidence sets contain the ground- -ruth vertices.
Confidence Set To calculate this set will use the probability concentration inequality to obtain confidence set: First, let Tep (Ø)
0, V Vep > 0, define the empirical marginal vec- tor w.r.t. permutation w as dt E R" at epoch ep
as
(cp) =
ep Σ (P.) (P. \i).
(9)
By the Hoeffding's inequality, one has that after ep epochs, Vw E P, for each e [n]. with probability least 1 - d, ol must belong the following set:
C( { E HN 1x
2 loggneepo-1
g00
< bep
s.t. Dep
(10)
ep

---

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 < - for any 0.2 > ô > 0 and with finite samples, no algorithm can output a point E-Core with probability at least 1 - 8.
The proof of Theorem 7 employs an information-theoreti argument. In particular, we construct two game instances with low-dimensional cores, utilissng 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 low-dimensional core, demonstrated in the following example.
Let μ(S) |S| for all S S N. is easy to verify that p indeed convex. The marginal contribution of any player to any set S _ N is
Example 8.
(S) ((S) 1, AA C.
(11)
Therefore, the only stable allocation is 1,, which coincides with the Shapley value. Hence, the core one-point set. According to Theorem 7, since the core has a dimension of in this case, is impossible to learn stable allocation with a finite number of samples.
Example suggests that convexity alone does not ensure the problem's 's learnability, emphasizing the requirement for strict convexity.
5.1 On the Stopping Condition
In this subsection, 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, restrict our attention H and consider it En-1, First, we state a necessary condition for the existence of common points.
Proposition 9. Suppose there is a (n -)-dimensia hyperplane that intersect with all the interior of confidence sets Cp. Vp E [n]. then common points do not exist.
Proposition suggests that if the ground truth simplex Conv (Q) 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 recap the notion of separation as follows.
Definition 10 (Separating hyperplane). Let C and D) be two compact and convex subsets of 1=-1 Let H be hyperplane defined by the tuple (v, c). where v is unit normal vector and is a real number, such that (a., v) = Vr E H. We say H separates C and D if (z, v) > Vr C: and (y. v) < c, Vy D.
Theorem 11 (Hyperplane separation theorem for multiple convex sets). Assume that (Cp) pe(n)
mutually disjoint compact and convex subsets in En-1, Suppose that there does not exist (n d)-dimmnsio hyperplane that intersects with confidence sets Cp, Vp E [n], then for each p E [n], there exists hyperplane that separates C,, from UC,.
9$p
7

---

Remark 12 (Non-triviality of Theorem 11). At first glance, Theorem 11 may appear trivial extension of the classic hyperplane separation theorem due to the following reasoning: Consider the union of all hyperplanes that intersect UĄpt Cg. which trivially contains Ugptp Cg. Then, by assuming that these hyperplanes do not intersect Cp. the separation between Cp and U gøp C2 appears to follow from the classic separation hyperplane theorem. However, there is 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 's theorem, prove in Theorem I by contra-position that the intersection between Cp and Conv(U upp Cg) is non-empty, then we can construct now-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 Hp be separating hyperplane that separate Cp from Undo Cy. We define Hp corresponding with tuple (vP, c²). Now, denote Ep = { En-1 (uP, < cP) as the half space containing Cp. We have that:
Lemma 13. For any x Cy. p E [n]]
n pE(n)
Ep Conv
(12)
Consequently, if n Ep nonempty, it is the subset of common points. pEiu]
From Lemma 13, as peIn) Es is the subset of any simplex defined by set of points in the confidence sets, Ope(n) Ep must be either empty or bounded subset of En-1, The key implication here is that Lemma 13 provides us method to find point in the common set. An example of Lemma 13 in E² illustrated in Figure 1.
Now, the main question is under what conditions Apein] Ep is nonempty. Next we show that the nonemptiness of (ne(n) Ep 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 collection of confident set (Cp)pe(m) and let Q {x" ppe[n]. for any x² E Cp. For any p E [n]. denote (Q) the (n 1)-dimensional hyperplane with constant (v. cP), || = 1 such that
(uP 2) = d + max diam(C,)) x0)) < d² + max (C,..
Vx E Q xP.
(13)
For all [n], if the following holds
DC,,, H2( 2n
max diam (Cg)
(14)
then there exists common point. In particular, the point x: EpEnn x" is a common point.
Intuitively, Theorem 14 states that if the distance from a confidence set C, to the hyperplane H, (Q) 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 explicit way find common
determines the stopping condition for Algorithm 1 and provide 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,,, (Q)) is a random variable and needs to handled with care. We show that there exist choices of vertices such that the simplex formed by them has sufficiently large width, resulting in the stopping condition being satisfied with high probability after poly (n, number of samples.
8

---

5.2 Sample Complexity Analysis
Now, we show that, the conditions of Theorem 14 can be satisfied with high probability. The distance D(Cp, (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',....") in RR,, let matrix P = [x"] [e')
we define the matrix of coordinates the points in w.r.t xf as c) == [(x] - x² 5 E
R=x(n=1), Denote o₂ (M) as the 1eth singular value of matrix M (with descending order). We define the width of the simplex whose coordinate matrix is P follows
O(P) = min 0 (coM(P,
(15)
iE[n]
Lemma 16. Given n points {a' ..... x²) } in R", let M be the matrix corresponding to these points, assume that O <, Mej and (M) 2 for some constant
0. Let R R=x" be a perlurbation matrix, such that its entries RRyl < e/2, V(ij), and 0 < a² /3n . Let limin be smallest magnitude of the altitude of the simplex corresponding to the matrix R. One has that
hain 2 2V02 c.
(16)
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 set of vertices as follows.
Proposition 17. Fix any E G., consider the collection of permutation P = {w, wo,,ws...... , (u.. and mutrix M = [000 Ju' The width of the simplex that corresponds to M, is upper bounded as ((M) 0.5cn
The vertex set in Proposition 17 comprises one vertex and its (n - 1) adjacent vertices. Combining Lemma 16, Proposition 17 with the stopping condition provided by Theorem 14, we now can guarantee the sample complexity of our algorithm:
Theorem 18. With the choice of collection of permutation order P as in Proposition 17, and suppose that Assumption 4 holds. Then, for any 8 E [0, 1), if the number of samples is bounded by
T= log(nd -11)
(17)
the -iiirr--Poottss-PPoi algorithm returns point in E-Core with probability at least 6.
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 e., C G,, 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 as follows.
Theorem 19. Suppose Assumption holds. Let P = 6G, the collection cyclic permutations, and denote the coordinate matrix of the corresponding vertices W. Assume that the width of the simplex ((W) 2 as. for some > 0. Then, for any ô E [0, 1),if number of samples is ew
== ( (neety log(ncww-- ( )
(18)
the Pomnion--Ponttt--Pi-cee algorithm returns a point in E-Core with probability at least 8.
It is worth noting that our algorithm does not require information about the constants of the game S: Cw: 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 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-gan seee-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 (nly(n) dependencies in the lower bound (we refer the reader to appendix E.2 for further discussions). Given the unresolved challenges, deriving lower bound remains an open question.
Experiment
To illustrate the sample complexity of our algorithm in practice and compare with our theoretical upper bound, we have conducted a simulation as described below. Code is available at: https: //githin com/NaaTranneekL//// Cons tan waanttttittttittaat Stttrictyyoooeeaamm git.
Simulation setting: We generate convex game of n players with the expected reward function f defined recursively as follows: For each S C N s.t. i S,
U (i}) f(S) + [| +
for some w sampled i.i.d. from the uniform distribution [ni 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.c., the strict convexity constant is arbitrarily small, follows:
f(S U (i)) f(S) + |S| +
We use the cyclic permutations C, the input for the algorithm. In Figure 2 (RHS), 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.
Strict rynuecity constrst 1/m
Strit conneccly corstart
Humber sunds
Murberr runnd bypothetic expeertil
Varlanie
22.5
Upor Souidd Gronth Carve
20.0
12.5
15.0
12.5
10.0
TAYYDOT BAGGNNS
Figure 2: Simulation with game of (2..., 10) players, where the strict convexity constant is 0.1/n in the LHS and 0 in the RHS.
7 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 large interior of the core, we introduce an algorithm named Common -owtno-ooonttttiiieoeee
to learn the expected core. Our algorithm guarantees termination after poly (n, log(8-1 )) ) samples and returns point in the expected core with probability (1 5). 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 lower bound for the class of games.
10

---

References
[1] David Aadland and Van Kolpin. Shared irrigation costs: an empirical and axiomatic analysis. Mathematical Social Sciences, 35(2):203-218, 1998.
[2] Stefan Ambec and Lars Ehlers. Sharing river among satiable agents. Games and Economic Behavior, 64(1) (4555)35-50 2008.
[3] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[4] Javier Castro, Daniel Gómez, and Juan Tejada. Polynomial calculation of the shapley value based on sampling. Computers and Operations Research, 36, 2009. ISSN 03050548. doi: 10.10166j.co..2088.4.0000 04.000
[5] Georgios Chalkiadakis and Craig Boutilier. Bayesian reinforcement learning for coalition formation under uncertainty. Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 2004, 3, 2004.
[6] Georgios Chalkiadakis and Craig Boutilier. Sequentially optimal repeated coalition formation under uncertainty, Autonomous Agents and Multi-Agent Systems, 24, 2012. ISSN 13872532. doi: 10.10077/104558-100-9955
[7] Georgios Chalkiadakis, Evangelos Markakis, and Craig Boutilier. Coalition formation under uncertainty: Bargaining equilibria and the bayesian core stability concept. Proceedings of the International Conference on Autonomous Agents, 2007. doi: 10. 44511329115.1122200.
[8] Georgios Chalkiadakis, Edith Elkind, and Michael Wooldridge. Computational aspects of cooperative game theory. Synthesis Lectures Artificial Intelligence and Machine Learning, 16, 2011. ISSN 19394608. doi: 10.2200/500355ED Y201 107 A1M016.
[9] A. Charnes and Daniel Granot. Coalitional and chance-constrained solutions to -person games, it: Two-stage solutions. Operations Research, 25, 1977. ISSN 0030-364X. doi: 10. 10.1287/0pre.2566.011
[10] Xin Chen and Jiawei Zhang. stochastic programming duality approach to inventory central- ization games. Operations Research, 57, 2009. ISSN 0030364X. doi: 10. 10.1287/ppr..100000000
[11] Xuan Vinh Doan and Tri Dung Nguyen. Robust stable payoff distribution stochastic coopera- tive games. Operations Research, 2014.
[12] Jakob N. Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In 32nd AAAI Conference on Artificial Intelligence, AAAI 2018, 2018
[13] Ian Gemp, Mare Lanctot, Luke Marris, Yiran Mao, Edgar Duéñez Guzmán, Sarah Perrin, Andras Gyorgy, Romuald Elie, Georgios Piliouras, Michael Kaisers. Daniel Hennes, Kalesha Bullard, Kate Larson, and Yoram Bachrach. Approximating the core via iterative coalition sampling. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, 2024.
[14] Julio González-Der Diaz and Estela Sinchez-RRodrgun Cores of convex and strictly convex games. Games and Economic Behavior, 62, 2008. ISSN 08998256. doi: 2..1016j..eb.20077. 2000003.0...
[15] Isse C.F. Ipsen and Rizwana Rehman. Perturbation bounds for determinants and characteristic polynomials. SIAM Journal on Matrix Analysis and Applications, 30, 2008. ISSN 08954798. doi: 10.1 00.11370007044770.
[16] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Bandits and experts in metric spaces. Journal of the ACM, 66, 2019. ISSN 1557735X. doi: 10. 10.1145/3299873.
[17] Scott M. Lundberg and Su-In Lee. A unified approach interpreting model predictions. In Neural Information Processing Systems, 2017.

---

[18] Sasan Maleki, Long Tran- Thanh, Greg Hines, Talal Rahwan, and Alex Rogers. Bounding the es- timation error of sampling based shapley value approximation. arXiv preprint 13x6v:130..4266 2013.
[19] George Pantazis, Filippo Fabiani, Filiberto Fele, and Kostas Margellos. Probabilistically robust stabilizing allocations in uncertain coalitional games. arXiv preprint arXiv:2203.11322, 2022.
[20] George Pantazis, Barbara Franci, Sergio Grammatico, and Kostas Margellos. Distribution- ally robust stability of payoff allocations in stochastic coalitional games. arXiv preprint arX4v:230..01786 2023.
[21] Alexander Postnikov. Permutohedra, associahedra, and beyond. urXiv:math/0007163,, 2005.
arXiv
preprint
[22] Aitazaz Ali Raja and Sergio Grammatico. Payoff distribution in robust coalitional games on time-varying networks. IEEE Transactions on Control of Network Systems, 9 2020.
[23] Lloyd S. Shapley. Cores of convex games. International Journal of Game Theory, 1971. ISSN 00207276. doi: 10.1007/BF01553431.
[24] Grah Simon and Thouvenot Vincent. A projected stochastic gradient algorithm for estimating shapley value applied in attribute importance. In Lecture Notes in Computer Science, volume 12279 LNCS, 2020. doi: 10. 1000/978----00-55322--1113
[25] Milan Studený and Tomá' Kroupa. Core-based criterion for extreme supermodular functions. Discrete Applied Mathematics, 206, 2016.
[26] Jeroen Suijs and Peter Borm. Stochastic cooperative games: superadditivity, convexity, and certainty equivalents. Games and Economic Behavior, 27, 1999. ISSN 08998856. doi: 10. 10.1006/game. 19tp://aa...999900000 1998.0672.
[27] Jeroen Suijs, Peter Borm, Anja De Waegenaere, and Stef Tijs. Cooperative games with stochastic payoffs. European Journal of Operational Research, 113, 1999. ISSN 03772217. doi: 001006690377-22177999944221
[28] Mukund Sundararajan and Amir Najmi. The many shapley values for model explanation. In Proceedings of the 37th International Conference Machine Learning, 2020.
[29] Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czareekki, Vinicius Zam- baldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, and Thore Graepel. Value-decomposiiion networks for cooperative multi-agent learning. arXiv preprint arXiv: 1706.00200099 6 2017.
[30] Jianhong Wang, Yuan Zhang, Yunjie Gu, and Tae-Kyun Kim. Shaq; Incorporating shapley value theory into multi multi-agent q-learning. Advances in Neural Information Processing Systems, 5 2022.
[31] Tom Yan and Ariel D. Procaccia. If you like shapley then you'll love the core. In AAAI Conference on Artificial Intelligence, 2021.
[32] Miguel Ángel Mirás Calvo, Carmen Quinteiro Sandomingo, and Estela Sánchez Rodríguez. The boundary of the core a balanced game: face games. International Journal of Game Theory, 49, 2020. ISSN 14321270. doi: 10.10077:00118--01-0007000
12

---

Contents of Appendix
Preliminary and Convex Game
13
A.I Proof of Theorem 7
13
A.2 E-Core of convex games and Generalised Permutahedra
15
A.3 Proof of Proposition 17
16
A.4 Alternative choice of vertices of E-Core
17
On the Stopping Condition
20
Sample Complexity Analysis
23
D Examples of Strietly Convex Games
26
Further Discussions
27
E.1
Comparison with Pantazis al. [20]
27
E,2 Comment Lower Bounds
28
A Preliminary and Convex Game
A.1 Proof of Theorem
Here and onwards, we adopt following notation convention: for real numbers a, E [0, 1]. KL (a, b) represents the KL-divergence KL (p, q) where p. q probability distributions on {0, 1) such that p(1) = a, q(1) = b. In other words,
KL (a, b) = a aln (i) + +1 a) In (t=8)
Lemma 21 ([16)). For any 0 < E < y - 1, KL (y - E.y) < e² //v(1 y).
Before stating the proof of Theorem 7, let us introduce some extra notations. Given a game =
(N,P), with the expected reward function μ., define the following.
Hc(G) {a R
(c())= ((C)} is the hyperplane corresponding to the effective
allocation w.r.t coalition C.
E--Crr(G) is the expected core of the game G.
Fo(G) == E-Core(G) Hx) 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].
Definition 22 (Face Game). Given a game G = (N, P) with y(S) = Er-Ps [r], VS C N. For any C' C N, define a face game G(C) = (N, with pree (S) = Ey- [r] such that, for any N,
PFcc (S)
U ()) ,(N C) +
(19)
[14] showed that the expected core of G(C) is exactly the facet of E-Core corresponding C, that is, E-Core(G((C) = (G). As noted in [32], one can decompose the reward function of the face game follows. For any S C N, have that
pr. (S) MFg (S + MF (S (N C)).
(20)
We now proceed the proof of Theorem 7.
13

---

Proof of Theorem 7. Denote the set convex games with Bernolli reward as GB, that is,
GB = {G (N, P = (Ps)scN; Ps E M((0, AS
Face-game instances and the distance between their E-Core. We first define two games, Go and G1, with mull-dimensional E-Core, such that G1 is slight perturbation of Gg. Next, we define face games corresponding to Go and G1 using the perturbed facet. We then show that the distance between the cores of these face games is at least some positive number 0.
Define a strictly convex game Go == (N, GB, such that (²()) By-Py [r]. and assume that St is s-strictly supermodular. Now, fix subset C' C N, let define perturbed game instance G1 = (N, Q) E GB, with μ (5) == E [r] such that
(C) (C) E; (== (S): N, S+C;
(21)
for some < It is straightforward that Gi is (s s)-strictly convex. Therefore, E-Core(Go) and EE-Core(G]) (G1) are both full-dimensional.
Fixing a coalition C C N, we now construct the face games from Go. G₁ as Definition 22. Let Go(C) (N, IPC), (C) == (N, QC) GB, whose expected rewards 1 and / defined by applying (19) to nº and μ² respectively. Now, we consider the difference between the expected reward function of these two games.
luko (S) (5) = luke (5) - ( =E 1u4 (N \ () 1f |0]==
AA C
ASSA
(22)
As one can always decompose the set S = (SNC) (Sn C), by the decomposibility of the face game (20), we has that
1nto (S) 1x sc, AS C.
(23)
As the core of face game Go(C) and (C) lie on the hyperplane corresponding to the coalition N \. C, and the distance between the hyperplanes of Go and G₁ is which lower bounds the distance between the expected core of Go(C) and G) In particular, as E-Core(Gn(C)) = Fo ) and (N (N C) pN \ C)I e, which leads to
FG(Go) and E-Core(Gi C(H)) HN)o(Gi)) = e, we have that
D (E-Core(Go(C)), (-Core(G((C))) 2
(24)
The KL distance and imposibility of learning low-dimensional E-Core. We show that, with probability E (0, 0.2). any learner cannot distinguish between Go(C') and G₂ given there finite number of samples. We use the cetimaation-hhhoree framework similar which is well developed within multi-armed bandit literature.
We first upper bound the KL-distance between PS. Q
VS C
N.
Denote C1 =
minsen
Pr. (S))) > by Lemma 21, we have that
KL (FS, Q9) KL (L% (8), M (S)
VS N.
C1
Define the probability space v 2N x {0, 1}. Fix any algorithm (possibly randomised) A. At round 4, denote rt) E V as the coalition selected by the algorithm and the reward return by the environment. At round s < I, denote u/ of as the prohability distribution over & determined by A and P. Q accordingly.
14

---

We have the following, as stated in the appendix of [16]. For any u < t, one has that,
V (1 u 13a-1)
KL (v
Σ
(xb")) log
1/ (S
Vo (rx Sun 35mm1)
vo (+) log
(S, rja-1)
Vi (Tu Sus 25u-1)
pn- Ega-r
Sus 1) M (ru
vo (e) log
(ru
Sus z)
[As the distribution of Su depends only on A, not on the distribution 1/6, 21-1
1 (Na u Su 1/ 1/-11))
Σ
Σ (r Sus Suu:"~1) log
(ri Sus v/u-1)) 1/ (Sus v--1)
Su ENE (0,(0,1)
Σ
Σ
KL (ulo (S.), (sw))) vi (Su, 1
1n-1e
SLE2N
g2
The last inequality hold because KL (1 (5),
(S)) S S VS 2%
We have that
1s2
KI. (V6. 11) - KL. (x), S
(25)
C2
As we can choose E to be arbitrarily small, we can choose e such that KT. (v/, u4) s 0.1.
Now, define the event & as the event that A outputs a point in (-Core(G,(C)), assume that EE) with probability at least 0.8. Note that, as E-Core (CC)) n E-Core(Gr event where the algorithm fails to output a stable allocation with the game instance G₁ (C). We have that from [16]'s Lemma A.5,
& represents the
(E) 2 16(E)) exp (- KL (vh. v1) + 1/e
(- (- 0.8
0.1 0..1+1/e 1/c
0.8exp
0.8 exp
> 0.3.
(26)
E9(E)
As it holds for any & > O, this means that for any finite number of samples, with probability at least 0.1, the algorithm will output the incorrect point.
Remark 23. Upon closely examining the face game instances in the proof of Theorem 7, we can that even if the E-Core is full-dimensional, but the width of the interior of E-Core is arbitrarily small, it is still not possible to learn a point in E-Core with high probability and finite samples. To see this, let us create two perturbed game instances of the face game instances such that their E-Core full-dimensional but have an arbitrarily narrow interior. The construction can be done by applying modification of equation (19) with an arbitrarily small constant Ç > on the game Go. G1, as follows.
PF. (S) p((S n CN \ -0)) (C) (N
(27)
Now, long < < e/2, meaning that the width of the interior of their E-Core is less than half of the distance between the original face games, the distance between their E-Core remains positive. Therefore, the KL distance between the reward distributions is arbitrarily small but the two games do not share any common stable allocation, no algorithm can output a stable allocation of the ground truth game with high probability and finite samples.
A.2 E-Core of convex games and Generalised Permutahedra
Formulating the coordinates of the vertices of the core can be achieved using the connection between the core of convex game and the generalised permutahedron. There is equivalence between
15

---

generalised permutahedra and polymatroids; it was also shown in [25] that the core of each convex game is a generalised permutahedron.
For any w E Gn. let = Conv ([I" w E Gn)). generalised permutahedron can be defined as deformation of the permu- tahedron, that is, 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 adjacent vertices 6", Suss can be written as
The n-permutaheerro defined as
8" 6udi (ew()) - ew(i+1));
(28)
Where, Rw,i 2 O, and 6 On are the coordinate vectors in R If the game is ç-strictly convex, ku,á > Ç.
A.3 Proof of Proposition 17
We utilise the formulation of edges of the generalized permutahedron as described in Subsection A.2 calculate the matrix of coordinates for the vertices of E-Core. Based the matrix of coordinates, we now state the proof of Proposition 17.
Proof of Proposition 17. As the set of vertices is dt and its neighbors, there only two cases to consider. First, we need to consider the matrix created by using d. as the reference, that CoM [M, 1). As the neighbors have the same roles, bounding the width of the matrices using any neighbor as reference point can be done identically. Therefore, we will prove the theorem for CoM(M 2), and the proof for coM M, i), * 1 can be done in the same manner. Let us denote
C1
0
0
C1
0
0
C2
0
0
V = coM
:
:
(x-11
R
(29)
Cn-2
Gp
0
C1
-0
C1
C1
C1 02
0
02
0
0
0
0
U = (M,2)
R
(30)
Cn--2
Cp-1
0
- 1
in which each c >.
We will exploit the following norm inequality in the proof. For any A An E R, we use the following inequality (norm vs. norm vectors)
Di=1 A,2
A
(31)
n
Consider V. Consider unit vector
(I), Zn-1).
We have
C1
C1 .1 + 62
C232 + C3
Vr
(32)
Cn 2 n + Cn- 1nn-1
- 1p-1
16

---

Applying the Ineq. (31) for A1 = C1 A2 = -1 + C2 An-1 -c--2 +
Cn-12p-1.
A, 12 gives
||V2|/ 2 cja9 2
n
2
5
||2| 2 911
2
+ (-1 0222))
(33)
5k
||
Therefore,
n||VI|2 2 (2 + x x 5²
(34)
Therefore ||V||| 2 s/n, hence aa
o (V) 2 s/n.
Consider U. Similarly, consider unit vector x: = (I1, .... En 2n-1). 1). We have
ci (01 + +22 + + In xn-11)
9 (2) 32 ... 1n-1) 02
C2 + C333
Ur
C343 + C4
(35)
Cn 22-22mn nn + Cn-1 1n
1
Applying the Ineq. (31) for A1 = -2.. 1) Ag = Ci t.. + As
-C222 + Cz33, A4 C3 C4 An-1 -G-22nn22 + 12-1 An Cn-1- gives
Note that
||>|| > <2 + x2 + + 1n
2.2
2212
| 2 (z) + + + In )² (c1(21 + + + xn-1) + 22
52
||xx||2 2 (Z) + 02 ... + xn-1) 2 (c1(11 + x2 + ... + xn + o242)
C202
c333)3
71
22 n
||
(36)
Therefore, we also have
n U2 5²((x) + 02 + ... + In ) + x2 +
5227
(37)
n2
From that, we have that
2 x
... +
2
2
2n| 2x] 2 n2
as
| =
(38)
n.
n2.
That is, ||x V2n
Therefore, (a-)(U)= 2
Therefore, have that 0(M)
2
A.4 Alternative choice of n vertices of E-Core
In this subsection, we provide an alternative choice of vertices rather than that Proposition 17. Recall that, with the choice of vertices in Proposition 17, the lower bound for the width of the simplex
17

---

diminishes when the dimension increases. This leads to large dependence of the sample complexity on n. To mitigate this, we investigate other choices 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 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 w 6 consider the matrix W = [6" I0 1uss ..... 1= 1. The width of the simplex that corresponds to M, is upper bounded as follows:
3 n
((M)
(39)
Proof. The coordinate matrix w.r.t. d², that is, coM(M, 1) can be written follows.
0
0 E R (p-x(n0))
V
(40)
Therefore, the Gram matrix is
2
1
0
0
0
0
1
0
-1
1
2
-1
0
0
G=vVV=
E R (n-1))xxem 11x
(41)
0
-1
0
-1
2
Note that a tridiagonal matrix and also Toeplitz matrix, therefore, its minimum eigenvalues has closed form as follows
A (G) = 200s ( (n (n- 1)TT
2 2sin
(42)
n
2m
n
as sin
Therefore, 0(M) S on) V <
3
2m
2n
Proposition 24 highlights the challenge of selecting set of vertices such that the width does not contract with the increasing dimension, even in the case of a simple permutahedron. Denote E, C 6, as the group of cyclic permutations of length n. One potential candidate for such a of vertices the collection corresponding to cyclic permutations C,,, as described in the next proposition.
Proposition 25, Consider the matrix W = [']eee, We have that
n
O(W)
(43)
2
18

---

Proof. The form of matrix W is as follows
n
N
1
2
3
...
3
1
W
(44)
1
2
3
11
71
71
2
The coordinate matrix w.r.t the first column is follows
1
n
1
1
n - 2
2
= coM
(45)
:
-1
-2
1
-1
-2
(n
Let E Rn be any unit vector, and let : = Vu E R We have that
2, 2++1 nug.
(46)
Let us consider
4 || = 42, + +22 + + 42
22 + [(2 + =2) + (21 z2)²1 $1 + [[22 + 23)²
(=2 =23)
+... [[2 )n)² 2 + (2n-1 2n)² )1 + 2:
(47)
2 (21 22)² + (22 23)
(Zn-1 2n.
n² (uî + ub ..... u n²
Therefore, have that
n Vull |u 2
min
(48)
=1
2
It is straightforward that if one takes any column of W as reference column, the resulting coordinate matrices have identical singular values. In particular, for any i, E [n]]
coM(W, i) P co.(M. .j),
where a permutation matrix, thus, their singular values are identical. Therefore, we have that
n 2
((W)
As result, the set of vertices corresponding to eyclic permutations is sensible choice. In case of generalised permutahedron, let us define
W
[ wee..
(49)
As generalised permutahedra are deformations of the permutahedron, 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, in the following assumption:
Assumption 26. The width of the simplex that corresponds to W in (49) is bounded as follows
ns
O(W) 2
(50)
CW
for some constant cw 0.
19

---

400
300
150
300
300
306
150
430
300
102
Figure 3: Ow with n E {10, 50, 100, 150, 200, 300, 500, 1000], < 0.1 and 20000 trials
These parameters will eventually play a crucial role in determining the number of samples required using this choice of permutation orders. Although proving an exact upper bound for ow in all strictly convex games is challenging, we conjecture that cw is relatively small in a large subset of the games.
To investigate Assumption 26, we conducted simulation to compute the constant cw of the minimum singular value On). 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 cw tend to relatively small and highly concentrated within the interval (0, 30). This observation suggests that for most cases of strictly convex games, ew remains reasonably small. Consequently, our algorithm exhibits relatively low sample complexity. Code of the experiment is available https: // thut..u.... com/NamTranKeki coesttanttrriclyyooveeeeet
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 nn. As depicted in Figure 3, the values of cw tend to be relatively small and highly concentrated within the interval 30, This observation suggests that for most cases of strictly convex games, ew remains reasonably small. The results indicate that ow tends to be relatively small with high probability, and does not depend on the value n.
B On the Stopping Condition
Proof of Proposition For each Cp. choose a point in interior, denote as x.. As there are most 1 points {x") [es[[P]] there exists (n - 2) dimeenssoa hyperplane H that contains {-*] ]pe[[P])
Let H be a hyperplane parallel to H and let the distance D(H, H) be arbitrary small.
As confidence sets are dull-dimensional (n - 1), É must also intersect with the interiors of all confidence sets. Since H and A are parallel, any convex hull of points within and Á cannot intersect. Therefore, there is no common point.
20

---

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 hyperplane parallel to H and let the distance (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 following lemma.
combination of the classic hyperplane separation theorem and the
Lemma 27. Let {Cpl [Cplpe[n] be mutually disjoint compact and convex subsets in En Suppose there does not exist a (n - -i-dimnnsi hyperplane that intersects with all confidence sets Cp. Vp E [n]. then for each p [n]
(Ucr) atp
Cp n Conv
Ø.
(51)
Proof. We prove this lemma by contra-position, that is, there Cp such that
Uc,,
Cp n Conv
* Ø;
prt
then there exist hyperplane that intersects with all the Cp. Vp E [n].
First, assume there is point x = Cp n Conv
Upp
By Carathéodory's theorem, there are at
opp
most n points x² E C.g such that
spp
Σ
axr..
(52)
kE[n]
As each x² Cyy for some C., one can rewrite the equation above
Σ
Σ
(53)
oxP
2*EC.
Furthermore, we can write
Σ ax ānJ" in which, 59 = Ets Oga
and āg == Σ
ax
(54)
Ek ahrec Onk
z+ EC
k: ah EC,
Since Cy convex, E Cg. Substituting (54) into (52), one obtains
Σ 5%
(55)
Define H as a hyperplane that passes through all T.g. we have that x E H.
Second, show how construct hyperplane that intersects with all C.. [m]. Let I be the set of indices such that Cy 3 Z.y- We have two following cases.
(i) First, if I Cm. m E [n].
then H is the (n 2) dimeensioon hyperplane that intersect with all
(ii) Second, if [ < n-11, for any Cg Cp that does not contain any 29, choose any arbitrary point o E Czr. As there are n 1 points of 1a and x there exists hyperplane H that contains all these points. Furthermore, H must contain æ, so it is the (n d)-dimensional hyperplane that intersects with all sets Cm. Vm E [n].
21

---

Now, we state the proof of Theorem 11.
Proof of Theorem 11. As result Lemma 27, we have that for all Cp. vp [n].
Cp Conv Uc,, spp
(56)
Therefore, by the hyperplane separation theorem, there must exist hyperplane that separates Cp and
Conv
Uc
qFP
Proof of Lemma 13. Let us denote A, as Conv ((x²) pp())) As there is no hyperplane of dimen- sion n - 2 go through all the set Cp. the simplex An is (n 1) dimensional. We have that
F S An
A S
pE[n]
pE(n)
where Ep is the complement of the set Ep-
We will prove the RHS of the above. Consider & E A as An is full dimensional, & can be uniquely written affine combination of the vertices, that is,
i =
Ape
10=1
pEIn]
PE|n]
As AS there must exist some λ < O.
Now, we shall prove Dig. Consider the following.
(0*, = b
Apoo
dx (er a.tt)
Σ to Cark 2.))
pE(n
Auc k +
Σ Axp
(57)
poft
*
The above inequality holds since (u" 2tt C₁ and da < O. Therefore, & E EG. This means that
A C U Ez
(58)
kE[n]
Proof of Theorem 14. Before proceeding the main proof, show two simple consequences of the construction H, (Q), p E [n] and the assumption (14).
Fact 1: Consider p e [n). Hp(Q) acts as a separating hyperplane for Cp. To see this, assume that (Q) is not separate hyperplane for Cp. then there exists z² E Cp such that (oP,²P) 2 cº. From (13), we have (vP, xpP) S cº max,elp]yp diam(C,).. Then, there are two cases. First, assume that (uP IP) cP, As xP. 2 EC, and (P) 2 c there must exist a point æ in the line segment Io 2P| such that (v" x)) = c² This means that D(Cp. Hp) = O. which violates assumption (14).
Second, assume that cº S (o") S d + max di.m(C,)) Then, we have that
DCC,, Hp) S D(x", Hp) = (1P,x") - dll < max diam((.))
/E[n]
22

---

This also violates assumption (14). This implies that if (14) is satisfied, Hp(Q) must separate Cp from ug
Fact 2: The distance from any point in Cy from H2( is bounded follows. For z E Cy. q # have that
D(a, H2)))) ((x,,)) + D(x", H2)))) S 2 max diam(C.').
(59)
d'E/n/
Now, we proceed to the main proof. For the ease of notation, we simply write Hp for Hp
First, from assumption (14), we has that for any p E [mx].
DCCp, Hp) = min ((x, Hp) = min |ce - - (0P,x)) 1,) sECp
(60)
=ECp
We have that
min rECp
((x, Hp) 2n max diam 97p
Σ
max ((x, Hp).
(61)
=EC,
qEIn]/p
Second, we shows that how to pick a common point which exists when (61) is satisfied. Let us choose a collection of points x" Cp. p E [ni], and define
x
PEIn]
Now, we show that x² E Ep, Vp E [m]. For each p E [n]], consider Hp. We denote
Spp == (0" ,-) > 0;
Saq := (v",x") x - -c 0, q tpp.
Note that D(x, Hp) = (00, xx) cº). Follows (61), have that
Spp 2 min (xr, Hp) scC,
max D(r, Hp) 2
Σ Spq-
(62)
=EC,
Now, let consider
1 Σ (u*
(v x
Σ gE|nlip
(c + Spq) + (ce Spp)
gE|n]
(63)
= c² +
Spg Spp < Ce.
Therefore, x² E Ep. As it true for Ep, one has that
n Ep.
(64)
PE(m)
Finally, by Lemma 13, can conclude that x* is common point.
C Sample Complexity Analysis
Proof of Lemma 16. Denote as the simplex corresponding to AM = [x] opposite the vertex zf, and (2(A) is the height of simplex w.r.t. the vertex x' Denote Vol, the
...,, ...,,",,, A, as the facet
k-dimensional content C C ER-1 where dim(C) = k. Using simple calculus, one has that
(A)
(A) n- Vol (A,
(65)
23

---

We also denote Á as the perturbed simplex corresponding to M + R and A as the facet opposite the the perturbation of x².
we bound the height (A) for all E |n-1], For the height h,, (n.(A) (4), one can apply similar reasoning. Let define the coordinate matrix and the pertubation matrix w.r.t x follows
co)
U = coM(R,,))
(66)
We have that [U:y] <,, j. j. By the definition of width v(M), we have that
nn-1(V) 2 0(M) 2 a.
(67)
Let define the Gram matrix and perturbed Gram matrix as follows
G=vVVV (V+
(68)
One has that,
G G- G-G=VTU+UR + -U--=U.
One has that Un - 3ne, Viyl < and أزن 1. We also has that ||U||2 < ||||| S ne.
First step. we bound the quantity
[de((G+U)
By [15]'s Corollary 2.14, one has that det(G))
MeetG'+UD) + det(())
1 (G)
-1
ne 1.
(69)
(dct(G))
σ²
As (1 2) S I-ns
when 2 (0, 2 and n > 0. One has that Idet(G + U) de) [del(G)]
n²e
(70)
03 n²
when é S Ro, or e S
2
3nd
Let us define k
n== one has that n
UU)
1
(71)
[det(Gi)
K
It means that
det(G +U) 2 1 (1-1) det(G)
(72)
Second step. we bound the change in content of the ith facets of the simplex, for i E [n 1]. Consider the facet that is opposite to the vertex x², and denote Vii,, U₁ as the sub-matrices of V, U by removing ith column. Denote the Gram matrix
G(i) Vv))
(73)
G()) = (V()) +
Note that one obtain G(i), G(1) and by removing 7th row and column of G(i), G(1) respectively.
Denote (ii) G(i) G(i), has that all entries of Ui) smaller than
Moreover, by Singular Value Interlacing Theorem, has that o2 2 ar (G(i) 2 (G) 2 oz(((i)) 2 ... on (nn(((((i) 2 zon2(G((i) 2 on-1(G), (74)
Similarly, one has that
(det(G(() + det det))() (de((G(i))
< (1 (1+ xn-2(G(i))
(1)l22
n-2
-1 (1+ 7²
"
-15 (75)
1

---

It means that
dct(G())+U(1) - [ 21 det det(G
(76)
Third step. We bound the height h, corresponding to the vertices of in this step. For E [n 1] one has that
Vola(A) = (n 1)! V det(G + +8).
(77)
V (n2 - 2) V (et(
Furthermore, by the Eigenvalue Interlacing Theorem, we have det(G)/dett(G) 2 on-1(G) o². Putting things together, one has that
Voln-1 (D) (A) n1 Vol, 2((,) V det(GG()++ (i))
(et(G+UU
1 det(G)
02
6n
k 1 det (G(i)
(78)
We note that, the above holds for i [n [n-1] 1].
Fourth Step. Now, we bound the height corresponding to the vertex x. We can define the coordination matrix and pertubation matrix w.r.t x as follows.
V coM(M,1), U' coM(R,
(79)
Note that, by the definition of the width, we have that
On-1(V)) 2 ((M) 2 o;
(80)
and also, |Un] < e. Similarly, applying Steps 1-3, we also have that
h v 0² 6n3e
Therefore, na( 2 V02 6n holds true for all i [n]. We conclude that
Hain 2 - 6n
(81)
whenever, <
o² 3n
Proof of Theorem 18. Note that |P| Denote cu := 2 maxpe(m) diam(C,)) For any wi E P.
define the event
ε = ( E Cp. Vp E [n]]
By the construction of the confidence set, we guarantee that & happen with probability at least 1 1-n28.
Consider E [n]. for any g [n] \ p, let 2 be the projection of dt onto Hp. and x² ==
arg mogmin pEC, D(I, H,), We have that
D(k* S co. Vk E [m].
We need to bound D(2?, R, Hp) by bounding the minimum height of simplex Conv ({x*) )pem)) which a pertubation of Conv ((d))) )petn).
Define matrix M = [ pe[n] and M = [ Let := M MM be the perturbation matrix, one has that Riy S co. ((i,j). By Lemma 16, we have that
D(o Hp) oo 12n
(82)
Therefore, for D(x?, Hp) 2 neo holds it is sufficient to provide the condition for such that
o02 12n''c0 nec.
(83)
25

---

Assuming that 60 < 1, for the condition of Lemma 16 and the above inequality to hold, it is sufficient choose
co
13n
Now, we calculate the upper bound for sample needed. At epoch K, we have that
2n log
2diam 2 41
K
(84)
ow
Then we have K = =0 number of sample needed
nn log (na (2-))
). As each phase, there are at most n² queries, then the total
T ( 25 log(nn-11s-)
(85)
for the algorithm return common point, with probability of least 1- 8.
Proof of Theorem 19. The proof identical to that of Theorem 18, with the width of the simplex bounded by ((W) 2 ns.
D Examples of Strictly Convex Games
Consider facility-sharing game (a generalisation of cost-sharing games [2, 1J) where joining
a coalition S would provide each player of that coalition a utility value ukk where |S] and they have to pay average maintenance cost c(k). The expected reward of S is defined as ((S) = ukk - 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 shared computing lab. The value of using the lab 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 (c.g., the more participate the less the average maintenance cost becomes). An example to such maintenance cost function is, e.g., c(k) C1 C2ke2 where and C1, C2 are appropriately set constants such that the total maintenance cost ko(k) = C C2k(f++) I) 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.
1
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 (e.g., integration cost), while the benefit they can gain through this collaboration, (A:), 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.. u(k) k" with 1. The corporate's task then to invite local companies join their Doalition/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 o(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 o(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 coalition.
-((S))-(((S) For each of the scenarios above, we can see that the expected reward function ((S) = - indeed strictly supermodular. The reason that u(k) and c(k) are discrete and finite on (0, n). and thus, can casily find > 0 for which these games also admit s-strict convexity.
26

---

E
Further Discussions
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 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 (222)) 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 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 is > 1. For each coalition S, the empirical mean is denoted as g (S), and confidence set for the given mean reward is constructed, denoted as,
C(r(S)) = (A(S) E 10, 1] (A(S) Ftg (S) S Ets for some Etg > 0.
We note that while the algorithm in [20] constructs the confidence set using Wasserstein distance, simplify it by using the mean reward
in the case of distributions with bounded support, difference. After constructing the confidence set for the mean reward of each coalition, the algorithm solves the following robust optimization problem:
min ||=:12 =EX"
s.t. x xNN) = ((N)
x(S) sup(C(n(S)), VS C.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 is 1. This inevitably leads to a complexity of f2(2") samples, regardless of the sampling scheme one employs. In term of computation, with 2 confidence sets for all coalitions S C. 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" sample complexity, and the main reason is because it requires constructing confidence sets for the mean reward for all coalitions S C N. As such, if we want to apply their algorithm efficiently the bandit setting, we need address this limitation.
To do so, one may need to develop an approach to design confidence set for specific class of strictly convex games. For instance, we can consider the following approach: Given historical data, instead of writing confidence set for each individual coalition, let us define confidence set for the mean reward function as follows:
C(μ)= { N + [0, 1] [C(u(S))sCNN, is strictly supermodular))
(86)
where the confidence C(u(S)) could potentially be [0,1] for some coalition S, as there is no data available for these coalitions. Let Core(f) be the core with respect to the reward function f. We propose a generalization of the framework from the robust optimization problem adapt the structure of the game as follows.
min | *ER"
s.t. xNN)= ((N)
(87)
E Core(ūi. pEC(K)
That 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 tight confidence set [C(u(S)))scN such that all functions within
27

---

this collection are strictly supermodular. We are not aware of a method to explicitly construct [C(u(S))sseN containing only strictly supermodular functions, and we believe this set could poten- tially be very complicated. To illustrate, consider the scenario where we have samples from two coalitions, {1} and (1, 2), with the following empirical means:
((13) 0.11; (((,2)) 0.1
This 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), (TS) is not supermodular (as {1} C {1,2), yet (T() > (11, 2)). Consequently, either the confidence set ((((1)) or C(u(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 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.
E.2 Comment on Lower Bounds
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 deriving meaningful lower bound for strictly convex games. The main problem is twofold: Firstly, not every small perturbation of the face game may result in strictly convex game; therefore, careful tailoring to ensure strict convexity required. Second, to show a polynomial dependence of sample complexity on n. we need to generalise the two game instances in Theorem into poly(n) game instances for the inoommation-thoreee argument. 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 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 very loose lower bound. Particularly, The two game instances in Theorem are originally constructed using two strictly convex games Go and G1, whose ex expected rewards differ in only one coalition, denoted as C N. This setup simplifies the computation of the statistical distance of the nace-games which are perturbations of Go and G1 corresponding to the same coalition C. However, since only two game instances are used to derive the result of Theorem 7, if we employ mally-dimensional-com 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.
perturbed
Secondly, generalising the approach to (nly(n) game instances is not straightforward, as it requires choosing (nly(1) coalitions to perturb the rewards of the original game Go. not just one coalition. This results in significant differences in the expected reward functions of the corresponding face games, each face game is 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.
28

---

NeurIPS Paper Checklist
1. Claims
Question: 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 's contribu- tions 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 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.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
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 separate "Limitations" section 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 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, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails 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 faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, 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 impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
29

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
We stated the assumptions in the main paper and provide the proof in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification:
We described our simulations and provided a link to the code available online.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
30

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We provided link to the code available online.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cr httiii//giidees/ddeSuubmiii sosoooooooss for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //nips.cc///cccc ppwpic/guudes..///.pppppppop /eeo/eoodSSbiic ssi criionPolicee for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
We described our simulations and provided a link to the code available online.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
31

---

7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We described our simulations and statistical significance of the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula. call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (c.g. negative етror rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We discussed the time complexity of algorithm.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https://neurips.ccmm http://ppp.ppppppppccccccccceeea
Answer: [Yes]
Justification:
We have reviewed the NeurIPS Code of Ethics.
32

---

Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is primarily theoretical and may have limited direct impact or implications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors impact or why the paper does not address societal impact.
NA No, they should explain why their work has no societal
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For cxample, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
33

---

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 require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
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 used and, 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 provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/dttasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. 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 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.
14. 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]
34

---

Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/teview based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "z6aXrMVS4C", "reviewer": "Reviewer_1Z68", "summary": "The paper studies the problem of finding the core for Reward allocation\nwhen the information about reward functions is incomplete.\nSpecifically, previous works either study deterministic\ngames and assume that the reward function is known, or study stochastic games\nand assume that the reward distribution is known.\nIn contrast, this paper assumes that we have access to an oracle\nthat takes as input a coalition and outputs a stochastic reward for that coalition.\nThe paper obtains an algorithm for the special case of strictly convex games\nwhich outputs a point in the expected core and with high probability uses as most\na polynomial number of samples.\n\nThe main idea behind the algorithm is as follows. If there was no issue with the noise,\nthen one could simply take the marginal vector of an arbitrary distribution as done by [21].\nThe noise prohibits us from estimating this vector exactly however and one can form only a confidence set.\nThe main idea is to form multiple confidence sets around multiple marginal vectors.\nNext, we look for *common points* which are points $p$ with the following property:\nif we choose one arbitrary point from each of the confidence sets, and calculate\nthe convex combination of these points, then this will contain $p$. \nPerhaps surprisingly, this set is non-empty.", "questions": "Questions:\n- Are there any works that are similar to yours in terms of techniques?\n  Seems to me like similar ideas should appear in the bandits literature but the only citation\n  I can find is [14].\n\n\nTypo: Equation 2 should require $C \\ne S$.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper studies an interesting problem, and provides an elegant solution for it.\n- The paper is well-written; the algorithm in particular is explained very well and is easy to understand.", "weaknesses": "- It would be good to obtain a lower bound.\n  As is, the sample complexity is a (large) polynomial in $n$.\n  Not clear to what extent this can be improved.\n  While the authors discuss this briefly, it is an important drawback of the work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to reviewer 1Z68\nWe thank the reviewer for the insightful comments. Below are our responses/clarifications to your questions:\n\n## Question 1: Are there any works that are similar to yours in terms of techniques?\n### Response: \nLearning the core via sampling is typically considered to be a difficult problem within both the algorithmic game theory and learning theory communities, and thus, not many results have been published to date. Nevertheless, you are correct that our technique borrow some ideas from the bandit and learning theory literature:\n\nOur problem formulation can be viewed as finding a point within an unknown feasible set, defined by $f: 2^N\\rightarrow [0,\\;1]$. \nFrom this perspective, it is somewhat related to the literature on linear bandits with constraints [1, 2].\nHowever, existing techniques require the number of samples to scale with the number of free parameters that define the feasible set, which is not desirable in our problem as it leads to $\\Omega(2^n)$ number of samples required. \nIn contrast, we exploit the property of supermodular functions, where each marginal vector corresponds to a vertex of the feasible set, i.e., the core. Hence, we only need to estimate $n$ vertices.\nMoreover, we believe our CPP framework and *the development of an extension of the separating hyperplane is the first of its kind*, and we hope that it can find its application in other domains such as stochastic optimization and bandit theory.\n\nRegarding the impossibility results on sample complexity, the information-theoretic framework is typically used to derive lower bounds for bandit algorithms. While this framework is general, the main challenge and novelty of new lower bounds often lie in finding a collection of hard problem instances that satisfy the assumptions of the particular setting, which has led to various lower bounds in the literature [3, 4, 5].\nOur impossibility result follows this approach as the key challenge in deriving our Theorem 7 lies in constructing hard game instances such that their cores do not intersect, while the KL distance between the games is arbitrarily small, making it difficult to distinguish them with a finite number of samples. \nWhile existing techniques in the online learning literature are typically not suitable to derive lower bounds for our setting, we found that face-game problem instances [6] perfectly strike that balance, allowing us to derive the impossibility result through the information-theoretic framework.\n\n## Comment 1: 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.\n\n### Response:\nWe agree that having a matching lower bound would be ideal. As currently we do not have it, we have conducted some additional experiments to compare the sample complexity our algorithm needs in practice with the derived theoretical upper bound from Theorem 19. \n\n**Simulation setting:**\nWe generate convex game of $n$ players with the expected reward function $f$ defined recursively as follows:\nFor each $S \\subset N$,\n$$\nf(S \\cup \\{i\\}) = f(S) + |S| + 1 + 0.9\\omega,\n$$\nfor some $\\omega$ sampled i.i.d. from the uniform distribution $\\mathrm{Unif}([0,1])$.\nWe then normalize the value of the reward function within the range $[0,1]$.\nThe strict convexity constant is $\\varsigma \\approx 0.1/n$.\nWe plot the samples required by the algorithm to find a point in the true core in the attached PDF file (Figure 1).\n\nFrom the simulation results, we can see that the growth pattern nearly matches that of the theoretical bound given in Theorem 19 in our paper, indicating that our theoretical bound is highly informative.\n\n\n## References:\n[1] Shipra Agrawal and Nikhil R. Devanur. Bandits with concave rewards and convex knapsacks. Proceedings of the 15th ACM Conference on Economics and Computation, 2014.\n\n[2] Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear stochastic bandits under safety constraints. In Advances in Neural Information Processing Systems, 2019.\n\n[3] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The non-stochastic multi-armed bandit problem. SIAM journal on computing 32(1), 2002.\n\n[4] Paat Rusmevichientong and John N. Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35, 2010.\n\n[5] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Bandits and experts in metric spaces. Journal of the ACM, 66, 2019.\n\n[6] Miguel Ángel Mirás Calvo, Carmen Quinteiro Sandomingo, and Estela Sánchez Rodríguez. The boundary of the core of a balanced game: face games. International Journal of Game Theory, 49, 2020", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mrfoQT3Rnj", "reviewer": "Reviewer_oJVQ", "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.", "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?\n- If the strict convexity assumption is replaced with purely the full dimensionality assumption, do the authors expect CPP to work?", "limitations": "I don't see any limitations or potential negative societal impact of this work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is in general well-written and smooth to follow. The technical proofs seem to be rigorous. The proposed CPP algorithm is novel to me and has a sound theoretical guarantee.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Responses to Reviewer oJVQ\n\nWe thank the reviewer for the insightful comments. Below are our responses/clarifications to your questions:\n\n## Comment 1 - Simulation results for sample complexity\n### Response:\nTo illustrate the sample complexity of our algorithm in practice and how it is compared to our theoretical upper bound, we have conducted a simulation as described below.\n\n**Simulation setting:**\nWe generate convex game of $n$ players with the expected reward function $f$ defined recursively as follows:\nFor each $S \\subset N$,\n$$\nf(S \\cup \\{i\\}) = f(S) + |S| + 1 + 0.9\\omega,\n$$\nfor some $\\omega$ sampled i.i.d. from the uniform distribution $\\mathrm{Unif}([0,1])$.\nWe then normalize the value of the reward function within the range $[0,1]$.\nThe strict convexity constant is $\\varsigma \\approx 0.1/n$.\nWe plot the samples required by the algorithm to find a point in the true core in the attached PDF file (Figure 1).\n\nFrom the simulation results, we can see that the growth pattern nearly matches that of the theoretical bound given in Theorem 19 in our paper, indicating that our theoretical bound is highly informative.\n\n## Question 1: If the strict convexity assumption is replaced with purely the full dimensionality assumption, do the authors expect CPP to work?\n### Response:\nOur algorithm exploits the property of convex games where each vertex corresponds to some marginal vectors. Hence, convexity is necessary. However, we expect that the CPP algorithm can work well even when the strict convexity assumption is violated and replaced by convexity and full-dimensionality.\nIn fact, our algorithm operates quite independently of the strict convexity assumption, as it does not require the knowledge of the strict convexity constant $\\varsigma$ neither the width constant $c_W$ of the function. \n\nIn more detail, from a theoretical perspective, strict convexity allows us to provide a provable approach to find an input for the algorithm easily, which is the set of any permutation and its adjacent permutations. \nHowever, in practice, the algorithm works independently of the strict convexity assumption by using the collection of cyclic permutations $\\mathfrak{C}_n$ as the input.\n\nTo demonstrate that our algorithm is indeed still robust even when the strict convexity assumption is violated, we ran a simulation where the characteristic function is only convex, or the strict convexity constant is arbitrarily small as follows:\n\n**Simulation setting:**\nWe generate convex game of $n$ player with the expected reward function $f$ defined recursively as follows:\nFor each $S \\subset N$,\n$$\nf(S \\cup \\{i\\}) = f(S) + |S| + 1 + \\omega.\n$$\nfor some $\\omega$ sampled i.i.d. from the uniform distribution $\\mathrm{Unif}([0,1])$.\nWe then normalize the value of the reward function within the range $[0,1]$.\n\nTo see that the strict convexity constant $\\varsigma$ can be $0$, consider the example:\nLet $S = \\\\{1\\\\}$, and $T=\\\\{1,2\\\\}$, and suppose that\n$$\nf(S\\cup \\{3\\}) = f(S) + 3, \\text{suppose that $\\omega = 1$}; \\quad \\quad  f(T\\cup \\{3\\}) = f(T) + 3,  \\text{suppose that $\\omega = 0$}. \n$$\nTherefore, the marginal contribution of player $3$ to both $S$ and $T$ is $3$, hence the game is only convex, not strictly convex.\n\nWe then generate stochastic rewards following the Bernoulli distribution $r_t(S) \\sim \\mathrm{Ber}(f(S))$.\nFor each $n \\in \\\\{2,...,10\\\\}$ we ran $100$ game samples.\nWe use the cyclic permutations $\\mathfrak{C}_n$ as the input for the algorithm.\nWe plot the samples required by the algorithm to find a point in the true core in the attached PDF file (Figure 2).\nOn the log scale, 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.\n\n## Question 2: Figure 2 shows that tends to be long-tailed, which makes the empirical validation relatively weak. Could the authors comment more on this?\n### Response:\nFrom our simulation, we can observe that with significantly high probability (i.e., 99.6 percent), the constant $c_W$ falls into the $[0,30]$ interval, independently from other parameter settings. This indicates that this constant is relatively small for the majority of strictly convex game instances.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SEmFlhXAgL", "reviewer": "Reviewer_f4nV", "summary": "The paper tries to find an expected core under the assumption that a characteristic function is $\\varsigma$-strictly convex cooperation game. \nThe 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.\nThey prove that strictly convex is a sufficient condition to find an expected core with the polynomial number of samples.", "questions": "Could you please comment about the weakness comments if I have misunderstood something? The following is a comment rather than a question.\n\nq1. 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.\n\n[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": "Yes, they adequately address the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "s1. The paper discusses the learnability of the expected core and shows that strict convexity is a sufficient condition to guarantee thelearnability.\n\ns2. The paper also provides a novel algorithm based on convex geometry and the proposed algorithm outputs an expected core with probability 1 - $\\delta$. \n\ns3. The sample complexity of the proposed algorithm is polynomial in the size of the players.", "weaknesses": "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.\nIt 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. \n\nw2. 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. \n\nw3. 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.\n\n[1] Deng, X., & Papadimitriou, C. H. (1994). On the complexity of cooperative solution concepts. Mathematics of operations research, 19(2), 257-266.\n\n[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.\n\n[3] Oishi, T., & Nakayama, M. (2009). Anti-dual of economic coalitional TU games. The Japanese Economic Review, 60, 560-566.\n\n[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.\n\n[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.\n\n[6] O'Neill, B. (1982). A problem of rights arbitration from the Talmud. Mathematical social sciences, 2(4), 345-371. \n\n[7] Liben-Nowell, David, et al. \"Computing shapley value in supermodular coalitional games.\" Computing and Combinatorics: 18th Annual International Conference, COCOON 2012, 2012. \n\n[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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to reviewer f4nV\nWe thank the reviewer for the insightful comments. Below are our responses/clarifications to your questions:\n\n## Comment 1: Practical example is needed.\n### Response:\n\nConsider a facility-sharing game (a generalisation of cost-sharing games [1, 2]) 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 $\\mu(S) = v(k) - c(k)$, representing the average utility of its coalitional members. \nThis setting represents many real-world scenarios, such as:\n\n- 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_2k^\\alpha$, where $\\alpha > 1$ and $C_1, C_2$ are appropriately set constants such that the total maintenance cost $kc(k) = C_1k - C_2k^{(\\alpha +1)}$ is non-negative and monotone increasing in the $[0,n]$ range ($n$ is the total number of departments). \n\n- (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. An example for strictly convex and monotone increasing benefit function is, e.g., $v(k) = k^\\alpha$ with $\\alpha > 1$. \n \nFor each of the scenarios above, we can see that the expected reward function $\\mu(S) = v(|S|) - c(|S|)$ is indeed strictly supermodular. \nIn addition, due to the fact that $v(k)$ and $c(k)$ are discrete and finite on $[0,n]$, we can easily find $\\varsigma > 0$ for which these games also admit $\\varsigma$-strict convexity.\n\n## Comment 2: Discussion on parameters of practical convex games and the conditions for strict convexity.\n### Response:\nIt is indeed challenging to determine the conditions under which the core of popular games, such as induced subgraph games and airport games, is full-dimensional, let alone strictly convex. We conjecture that additional conditions on the parameters of the game would be needed to guarantee either strict convexity or full-dimensionality of the core, which would enable the learnability of the problem.\n\nWhile the primary goal of this paper is to identify a general sufficient condition to achieve polynomial sample complexity, it is indeed interesting to investigate the conditions for particular games. Therefore, we leave this to future work.\n\nNote that in our response to your Comment 1 (see above), we have demonstrated how strict convexity can occur in other types of popular games such as cost/facility sharing games, when additional structures of the reward functions are included. \n\n## Comment 3:  It would be better to discuss other sampling-based algorithms for computing core.\n### Response:\nWe thank the reviewer for the suggestion of comparing our result to the literature on Shapley value approximation and learning PAC-stable allocations from samples.\n\nCompared to [3] and other works on Shapley approximation, their key limitation is that they can only return a value that is within a bounded distance of the Shapley value, which may not necessarily be in the core. Our algorithm is designed to directly return a point in the core instead.\n\nRegarding the literature on learning PAC-stable allocations from given samples [4, 5], the goal is to find an $(\\delta, \\epsilon)$-PAC stable allocation $x$, that is, an allocation that satisfies\n$$\n\\mathrm{Pr}[(1-\\epsilon) x(S) \\leq f(S)] \\geq 1-\\delta.\n$$\nIn some sense, our result can be understood as $(\\delta, 0)$-PAC. However, to achieve $\\epsilon = 0$, we require active sampling, not just from a given set of data, and also assumptions on the strict convexity of the game. As such, existing PAC-stable allocations would not work well in our setting.\n\n## Comment 4: Relation to balanced game.\n### Response: \nWe thank the reviewer for the suggestion. Although a totally balanced game is both a necessary and sufficient condition for guaranteeing the non-emptiness of the core, it is unclear how to strengthen the condition of a totally balanced game to guarantee the full-dimensionality of the core, which enables the learnability of the problem. The setting of totally balanced games and its further conditions is indeed an interesting area that we wish to explore in future work.\n\n## Comment 5: on the lower bound.\n### Response: \n\nWe agree that having a matching lower bound would be ideal. As currently we do not have it, we have conducted some additional experiments to compare the sample complexity our algorithm needs in practice with the derived theoretical upper bound from Theorem 19. Due to space constraints, we refer to the discussion with Reviewer 1Z68 (Comment 1) for the simulation details. The simulation results can be found in the attached PDF and they show that our theoretical upper bound is comparable with the empirical numbers (Figure 1); that is, the order of the polynomial in $n$ more or less matches the experimental results.\n\n### References:\n\n[1]Aadland\\&Kolpin. Shared irrigation costs: an empirical and axiomatic analysis. 1998.\n\n[2]Ambec\\&Ehlers. Sharing a river among satiable agents. 2008.\n\n[3]Liben-Nowell et al. Computing shapley value in supermodular coalitional games. 2012.\n\n[4]Balcan et al. Learning cooperative games, 2015.\n\n[5]Balkanski et al. Statistical cost sharing. 2017.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you for your valuable and constructive feedbacks. We have performed the additional simulations as requested by the reviewers and have provided the results in this pdf file.

Meta-review: 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.
Decision: Accept (poster)