Response to reviewer f4nV

We thank the reviewer for the insightful comments. Below are our responses/clarifications to your questions:

Comment 1: Practical example is needed.

Response:

Consider 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. This setting represents many real-world scenarios, such as:

• University departments together plan to set up and maintain a shared computing lab. The value of using the lab is the same $v(k) = v$ for each department (e.g., their students can have access computing facilities), but the maintenance cost $c(k)$ is monotone decreasing and strictly concave (e.g., the more participate the less the average maintenance cost becomes). An example to such maintenance cost function is, e.g., $c(k) = C_1 - C_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).

• (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$.

For each of the scenarios above, we can see that the expected reward function $\mu(S) = v(|S|) - c(|S|)$ is indeed strictly supermodular. In 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.

Comment 2: Discussion on parameters of practical convex games and the conditions for strict convexity.

Response:

It 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.

While 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.

Note 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.

Comment 3: It would be better to discuss other sampling-based algorithms for computing core.

Response:

We thank the reviewer for the suggestion of comparing our result to the literature on Shapley value approximation and learning PAC-stable allocations from samples.

Compared 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.

Regarding 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

$$\mathrm{Pr}[(1-\epsilon) x(S) \leq f(S)] \geq 1-\delta.$$

In 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.

Comment 4: Relation to balanced game.

Response:

We 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.

Comment 5: on the lower bound.

Response:

We 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.

References:

[1]Aadland&Kolpin. Shared irrigation costs: an empirical and axiomatic analysis. 1998.

[2]Ambec&Ehlers. Sharing a river among satiable agents. 2008.

[3]Liben-Nowell et al. Computing shapley value in supermodular coalitional games. 2012.

[4]Balcan et al. Learning cooperative games, 2015.

[5]Balkanski et al. Statistical cost sharing. 2017.

Responses to Reviewer oJVQ

We thank the reviewer for the insightful comments. Below are our responses/clarifications to your questions:

Comment 1 - Simulation results for sample complexity

Response:

To 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.

Simulation setting: We generate convex game of $n$ players with the expected reward function $f$ defined recursively as follows: For each $S \subset N$,

$$f(S \cup \{i\}) = f(S) + |S| + 1 + 0.9\omega,$$

for some $\omega$ sampled i.i.d. from the uniform distribution $\mathrm{Unif}([0,1])$. We then normalize the value of the reward function within the range $[0,1]$. The strict convexity constant is $\varsigma \approx 0.1/n$. We plot the samples required by the algorithm to find a point in the true core in the attached PDF file (Figure 1).

From 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.

Question 1: If the strict convexity assumption is replaced with purely the full dimensionality assumption, do the authors expect CPP to work?

Response:

Our 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. In 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.

In 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. However, in practice, the algorithm works independently of the strict convexity assumption by using the collection of cyclic permutations $\mathfrak{C}_n$ as the input.

To 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:

Simulation setting: We generate convex game of $n$ player with the expected reward function $f$ defined recursively as follows: For each $S \subset N$,

$$f(S \cup \{i\}) = f(S) + |S| + 1 + \omega.$$

for some $\omega$ sampled i.i.d. from the uniform distribution $\mathrm{Unif}([0,1])$. We then normalize the value of the reward function within the range $[0,1]$.

To see that the strict convexity constant $\varsigma$ can be $0$, consider the example: Let $S = \\{1\\}$, and $T=\\{1,2\\}$, and suppose that

$$f(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$}.$$

Therefore, the marginal contribution of player $3$ to both $S$ and $T$ is $3$, hence the game is only convex, not strictly convex.

We then generate stochastic rewards following the Bernoulli distribution $r_t(S) \sim \mathrm{Ber}(f(S))$. For each $n \in \\{2,...,10\\}$ we ran $100$ game samples. We use the cyclic permutations $\mathfrak{C}_n$ as the input for the algorithm. We plot the samples required by the algorithm to find a point in the true core in the attached PDF file (Figure 2). On 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.

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?

Response:

From 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.

Response to reviewer 1Z68

We thank the reviewer for the insightful comments. Below are our responses/clarifications to your questions:

Question 1: Are there any works that are similar to yours in terms of techniques?

Response:

Learning 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:

Our problem formulation can be viewed as finding a point within an unknown feasible set, defined by $f: 2^N\rightarrow [0,\;1]$. From this perspective, it is somewhat related to the literature on linear bandits with constraints [1, 2]. However, 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. In 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. Moreover, 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.

Regarding 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]. Our 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. While 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.

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.

Response:

We 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.

Simulation setting: We generate convex game of $n$ players with the expected reward function $f$ defined recursively as follows: For each $S \subset N$,

$$f(S \cup \{i\}) = f(S) + |S| + 1 + 0.9\omega,$$

for some $\omega$ sampled i.i.d. from the uniform distribution $\mathrm{Unif}([0,1])$. We then normalize the value of the reward function within the range $[0,1]$. The strict convexity constant is $\varsigma \approx 0.1/n$. We plot the samples required by the algorithm to find a point in the true core in the attached PDF file (Figure 1).

From 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.

References:

[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.

[2] Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear stochastic bandits under safety constraints. In Advances in Neural Information Processing Systems, 2019.

[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.

[4] Paat Rusmevichientong and John N. Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35, 2010.

[5] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Bandits and experts in metric spaces. Journal of the ACM, 66, 2019.

[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