Approximating the Core via Iterative Coalition Sampling

🎯 Pitch

Rather than tackling the full exponential set of coalition constraints, this work shows you can approximate the core of large cooperative games by iteratively sampling the coalitions most likely to violate stability. The resulting saddle-point algorithms bypass linear programming entirely and scale to 100-player games, while also outperforming Shapley-value-based data removal on real-world XAI benchmarks like Boston Housing and Diabetes—though, intriguingly, not on all datasets.

1. Executive Summary

This paper introduces novel iterative algorithms for approximating the core in cooperative game theory that avoid solving large linear programs, thereby scaling to very large problems. The algorithms are evaluated across multiple game classes—weighted voting games, induced subgraph games, and marginal contribution networks—as well as on explainable AI (XAI) tasks using real-world datasets (Boston Housing, Diabetes, Breast Cancer, Chatbot Arena). The paper's central contribution is a Core Lagrangian method (a saddle-point formulation solved via stochastic mirror prox) that directly returns the least-core value and imputation without requiring an LP solver, outperforming a recent LP-based sampling approach in wall-clock time on 100-player weighted voting games. In XAI data valuation experiments, the least core identifies training data points whose removal degrades model performance more sharply than Shapley value-based selection, establishing that core-based importance measures provide a compelling alternative to Shapley values for feature attribution and data valuation—though only on certain problem structures, as Shapley-based selection proves superior on the Chatbot Arena Elo-rating task.

2. Context and Motivation

The Core Problem: Computing the Core Is Intractable for Large Games

This paper tackles a fundamental computational bottleneck in cooperative game theory: how to approximate the core in games with many players without solving a linear program whose size grows exponentially in the number of players.

To understand why this matters, we need to first clarify what the core is. In a cooperative game, a set of $n$ agents can form coalitions (subsets of players), and each coalition $C$ has a characteristic function $v(C)$ that tells us the total value that coalition can achieve if its members work together. The core is a set of payoff divisions (called imputations) of the grand coalition's value $v(I)$ that are stable: no subset of players can break away and achieve a higher payoff on their own than what they receive under the proposed division. Formally, an imputation $p = (p_1, \dots, p_n)$ is in the core if and only if for every coalition $C \subseteq I$ :

$p(C) = \sum_{i \in C} p_i \geq v(C)$

In plain language: every possible subgroup gets paid at least as much as they could earn by going it alone. If this inequality is violated for some coalition $C$ , then $C$ has an incentive to defect — they can achieve $v(C)$ by themselves and redistribute the surplus $v(C) - p(C) > 0$ among their members. This makes the original grand coalition unstable.

The problem is that there are $2^n$ possible coalitions in an $n$ -player game. Each coalition produces one constraint in the core definition (the inequality $p(C) \geq v(C)$ ). Computing the core exactly requires satisfying all $2^n$ constraints simultaneously, which is computationally infeasible for games with more than a handful of players. The least-core — the smallest relaxation $\epsilon$ such that the $\epsilon$ -core is non-empty — is similarly hard. As the paper notes, "checking if the core is non-empty is $NP$ -hard" (citing Deng and Papadimitriou, 1994), and "computing the least-core exactly is impossible" (citing Balkanski, Syed, and Vassilvitskii, 2017).

Why This Problem Matters: From Political Science to Explainable AI

The core is not a purely theoretical concern. It has practical importance across multiple domains where understanding stability, power, or fair compensation is central.

In political science and economics, weighted voting games model decision-making bodies where each agent (e.g., a country in the EU, a shareholder in a corporation) has a voting weight, and a coalition wins if its total weight exceeds some quota. The core in such games determines which payoff distributions are stable — i.e., which allocations of benefits or influence prevent any subgroup from breaking away to form their own winning coalition. This has been applied to analyze voting power in the European Union (Bilbao et al., 2002) and to design core-selecting package auctions where the goal is to determine payments that ensure bidders have no incentive to collude outside the auction mechanism (Day and Milgrom, 2008).

In explainable AI (XAI), the core has recently emerged as a compelling alternative to the Shapley value for measuring feature importance and data point value. The Shapley value, which averages a player's marginal contribution across all possible coalition-joining orders, has become the de facto standard in XAI through methods like SHAP (Lundberg and Lee, 2017). However, as the paper discusses in Appendix B, the Shapley value has several limitations: it can produce counterintuitive explanations (Sundararajan and Najmi, 2020), its additivity axiom is arguably not well-suited to non-additive models (Kumar et al., 2020), and behavioral studies have found that "the core can be more predictive of human payment divisions" (Williams, 1988; d'Eon and Larson, 2020) while human participants violated two of the Shapley value's axiomatic properties — null player and additivity.

In the XAI context, the core provides a stability-based perspective: a feature (or data point) is important to the extent that excluding it from a coalition reduces the coalition's value, and a stable payoff division compensates each feature according to its "market value" (Samet and Zemel, 1984). If a feature's payoff is too low relative to its contribution, then other features have an incentive to form coalitions that exclude it. Yan and Procaccia (2021) — the paper's primary baseline — provided initial evidence that the least-core can produce more reliable data valuations than Shapley values: data points rated as high-importance by the core had a larger impact on model performance when removed from the training set.

In network and graph games, the core reveals which graph structures produce stable versus unstable cooperative outcomes. For instance, in induced subgraph games (Deng and Papadimitriou, 1994), players are vertices of a weighted graph, and the value of a coalition is the sum of edge weights between players in that coalition. Understanding core stability in such games has implications for modeling social networks, infrastructure sharing, and coalition formation in structured environments.

The unifying theme: if we cannot compute the core efficiently for large games, we cannot apply cooperative game theory to real-world problems at scale. This is exactly the gap that has held back core-based methods relative to Shapley-based methods, which already have efficient Monte Carlo sampling approximations (Bachrach et al., 2010; Mitchell et al., 2022).

Prior Approaches and Where They Fall Short

Exact LP formulations. The least-core can be formulated as a linear program:

$\min_{p, \epsilon} \quad \epsilon \quad \text{s.t.} \quad v(C) - \epsilon - p^\top c \leq 0 \;\; \forall C \subseteq I, \quad \sum_{i=1}^n p_i = v(I), \quad p_i \geq 0$

This LP has $2^n$ constraints — one per coalition — making it completely intractable for games with more than roughly 20–30 players. Even with efficient polynomial-time LP algorithms (Karmarkar, 1984), the runtime is cubic in the number of constraints, and $2^n$ constraints means exponential growth with $n$ .

Restricted game classes. Some prior work developed exact or approximate algorithms for specific, highly restricted game classes. Kern and Paulusma (2003) solved the least-core for matching games. Bachrach (2011) addressed threshold network flow games. Elkind and Pasechnik (2009) computed the nucleolus for weighted voting games. Kimms and Kozeletskyi (2016) tackled core-based cost allocation in the cooperative traveling salesman problem. While these are valuable for their specific domains, they do not generalize — every new game class requires a new specialized algorithm. This makes it impossible to use the core as a general-purpose tool across the diverse game types that arise in XAI, political science, and economics.

Balcan, Procaccia, and Zick (2015): Learning cooperative games from samples. This work took a different approach: rather than solving the core for a known characteristic function, they showed that given access to incrementally sampled coalition values, one can provide probabilistic bounds on likely stable payments that relate to the core. However, this work focused on learning the game itself from data, not on computing the core given a fully specified (but large) characteristic function. It does not provide an algorithm for approximating the least-core when the coalition values are known.

Yan and Procaccia (2021): The state-of-the-art sampling-based LP. This is the paper's primary baseline and the most significant recent advance. Their algorithm avoids enumerating all $2^n$ constraints by randomly sampling a subset of $k$ coalitions, constructing the LP with only those $k$ constraints, and solving the resulting smaller LP. Theorem 1 in their paper guarantees that, with high probability, the approximation error decreases as $k$ increases — specifically, that the solution to the sampled LP is an $\epsilon$ -core imputation for the full game where $\epsilon$ scales as $O(1/\sqrt{k})$ .

This was a genuine breakthrough because it expanded the set of games for which the core can be tractably approximated to include games with many players, as long as the number of constraints sampled is manageable. It is exactly this method that enabled Yan and Procaccia to demonstrate the core's advantage over Shapley values for data valuation on real-world XAI datasets.

However, the Yan and Procaccia approach has a fundamental limitation: it still requires solving linear programs. The size of the LP grows linearly with the number of sampled coalitions $k$ , and while $k$ might be much smaller than $2^n$ , it still needs to be large enough to achieve reasonable approximation quality. The paper explicitly notes the computational bottleneck:

"even when only using sub-sampled constraints, solving LPs is still time consuming"

The theoretical runtime for interior-point LP methods is cubic in the number of constraints (Karmarkar, 1984), and while the simplex method (Dantzig, 1963) is often faster in practice, it remains a significant computational burden as the number of sampled constraints grows. For large $n$ and large $k$ , this LP solve dominates the runtime and limits scalability.

The Shapley value's computational advantage. The contrast with the Shapley value is instructive. The Shapley value can be approximated using Monte Carlo sampling over random permutations of players (Bachrach et al., 2010; Mitchell et al., 2022), which does not require solving any optimization problem — just repeatedly sampling coalition-joining orders and averaging marginal contributions. This simplicity and scalability are major reasons for the Shapley value's widespread adoption in XAI. The core, despite its conceptual advantages (stability interpretation, market-value pricing, better alignment with human payment divisions), has lagged behind because it lacked similarly scalable approximation algorithms that avoid optimization-based bottlenecks.

How This Paper Positions Itself

The paper's central thesis is that the LP solve is the computational bottleneck preventing core-based methods from scaling, and that iterative, stochastic optimization algorithms can bypass this bottleneck entirely. Rather than sampling constraints and then solving an LP over those constraints, the paper reformulates the least-core problem as a convex optimization problem that can be attacked directly with gradient-based methods operating on sampled coalitions (minibatches).

The authors are explicit about this positioning:

"We present alternative iterative algorithms that avoid the requirement of solving the LP, circumventing a significant computational bottleneck."

"None of our algorithms require solving a linear program: as such, they enjoy greater scaling potential to very large problems."

This is not merely an engineering improvement — it represents a different paradigm for core approximation. The Yan and Procaccia approach is a constraint sampling + optimization pipeline: sample coalitions, build an LP, solve it. The paper's approach is an anytime stochastic algorithm: iteratively sample minibatches of coalitions, compute gradient updates, and converge to a solution without ever constructing or solving a monolithic optimization problem. This enables deployment on hardware accelerators (GPUs/TPUs) using standard automatic differentiation frameworks like JAX, as described in Appendix A.2.

The paper also positions itself in the broader landscape of data valuation for machine learning, building on Yan and Procaccia's finding that the core can outperform the Shapley value for identifying critical training data points. By making core computation scalable, the paper enables this comparison to be made across larger datasets and more complex models, and introduces a nuanced finding: on some tasks (the Chatbot Arena Elo rating prediction, described in Section 5.3.1), the Shapley value actually identifies more important data points than the core. This suggests that the relative merits of Shapley versus core-based valuation are task-dependent, which is a more nuanced and practically useful conclusion than simply claiming one method dominates the other.

In summary: the paper addresses the specific problem that computing the core involves an exponential number of constraints, and the best existing approximation method (sampling + LP) retains the fundamental bottleneck of solving large optimization problems. The proposed solution reformulates the least-core as a convex-concave saddle-point problem that can be solved via stochastic mirror prox, operating on minibatches of randomly sampled coalitions, with convergence guarantees (Theorem 4) and practical speed advantages (Figure 2) over the LP-based baseline.

3. Technical Approach

3.1 Reader Orientation

This paper develops a family of iterative, stochastic optimization algorithms that approximate the least-core — the smallest relaxation of the core that yields a non-empty set of stable payoff divisions — without solving any linear programs. The core idea is to reformulate the least-core problem (a linear program with an exponential number of constraints) as a convex-concave saddle-point problem that can be solved by repeatedly sampling random coalitions, computing gradient-like updates from constraint violations, and adjusting the payoff vector and relaxation parameter simultaneously. This converts the computationally prohibitive LP solve into a streaming, anytime algorithm that runs on minibatches of coalitions, scales to hundreds of players, and runs efficiently on GPU/TPU hardware using standard automatic differentiation frameworks.

3.2 Big-Picture Architecture (Diagram in Words)

The system has three layers of increasing complexity, all operating on the same fundamental operation: sampling coalitions, computing how much they violate core constraints, and updating a candidate imputation accordingly.

Layer 1 — $\epsilon$ -Core via Iterative Projections (Algorithm 1): Given a fixed relaxation parameter $\epsilon$ , the algorithm starts with an initial guess of equal payoffs for all players. It cycles through individual coalitions, checking whether each coalition's core constraint is violated. For each violated constraint, it projects the current imputation onto the half-space defined by that constraint — effectively increasing the payoffs of players in the undersatisfied coalition until the constraint is met. This is a classical von Neumann-Halperin alternating projections method for convex feasibility.

Layer 2 — $\epsilon$ -Core via Stochastic Subgradient Descent (Algorithm 2): Instead of cycling through constraints one at a time, this method treats constraint satisfaction as a loss function and applies stochastic gradient descent (SGD) to minimize total constraint violation over sampled minibatches of coalitions. The loss for a coalition $C$ is the squared deficit (how much $p(C)$ falls short of $v(C) - \epsilon$ ), normalized by coalition size. The subgradient of this loss with respect to the payoff vector has a closed form that exactly matches the projection update from Layer 1, establishing equivalence when the batch size is 1 and the learning rate is 1.

Layer 3 — Least-Core via Mirror Prox (Algorithm 4, Core Lagrangian): This is the complete method that finds both the least-core value $\epsilon_{\min}$ and a corresponding imputation simultaneously. It formulates the least-core as a saddle-point problem: minimize $\epsilon$ subject to the total violation being bounded, then use a Lagrange multiplier $\mu$ to convert the constrained optimization into an unconstrained min-max problem. The resulting Lagrangian is convex in the primal variables (the imputation $p$ and the relaxation $\epsilon$ ) and concave in the dual variable (the multiplier $\mu$ ), making it a convex-concave saddle-point problem solvable via stochastic mirror prox — a two-step extragradient method that handles the monotone variational inequality structure. The algorithm operates entirely on minibatches of sampled coalitions, never constructing the full constraint set.

Common infrastructure across all layers: All three algorithms share (a) the ability to sample random coalitions from the $2^n$ possible subsets, (b) the ability to evaluate the characteristic function $v(C)$ for any sampled coalition, and (c) the constraint computation $d_C = \max(0, v(C) - \epsilon - p^\top c)$ where $c$ is a binary membership vector and $d_C$ is the deficit — how much the coalition's core constraint is violated.

3.3 Roadmap for the Deep Dive

First, the least-core LP formulation (Equation 1–4), because all three algorithms are alternative ways to solve this same optimization problem, and understanding what problem is being solved is essential before seeing how.
Second, the constraint projection geometry (Equation 5), since it is the atomic operation that all methods share — the closed-form projection of a payoff vector onto a single coalition's half-space constraint.
Third, the iterative projections method (Algorithm 1, Theorem 1), which is the simplest algorithm and establishes the geometric intuition of cycling through constraints.
Fourth, the stochastic subgradient descent method (Algorithm 2, Theorems 2–3), which reinterprets projections as loss minimization and enables minibatching, connecting the geometric view to optimization.
Fifth, the Core Lagrangian saddle-point formulation (Equations 8–10, Lemma 1, Algorithm 4, Theorem 4), which is the main contribution — the complete reformulation that avoids requiring a pre-specified $\epsilon$ and jointly solves for the least-core value and imputation.
Sixth, the practical implementation details (the monotone map $F$ , the prox operator in Equation 12, the hyperparameter bounds for $\epsilon$ and $\mu$ , and the GPU/TPU acceleration strategy), since these are what make the theoretical algorithm a practical tool.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily an algorithm design and empirical analysis paper whose core idea is that the least-core of a cooperative game can be approximated by reformulating it as a stochastic saddle-point optimization problem, enabling iterative gradient-based methods to replace linear programming solvers entirely.

The Least-Core Linear Program

The least-core problem can be stated as finding the smallest relaxation $\epsilon$ such that there exists a payoff vector $p$ satisfying all coalitional constraints within tolerance $\epsilon$ .

Standardized notation. The paper assumes without loss of generality that the grand coalition's value has been normalized to $v(I) = 1$ by rescaling the characteristic function. Each coalition $C \subseteq I$ is represented by a binary vector $c \in \{0, 1\}^n$ where $c_i = 1$ if player $i$ is in the coalition and $c_i = 0$ otherwise. The total payoff to coalition $C$ under imputation $p$ is $p(C) = \sum_{i \in C} p_i = p^\top c$ .

The LP formulation:

$\min_{p, \epsilon} \quad \epsilon$

$\text{s.t.} \quad v(C) - \epsilon - p^\top c \leq 0 \quad \forall C \subseteq I$

$\sum_{i=1}^n p_i = 1$

$p_i \geq 0 \quad \forall i \in I$

where $p \in \mathbb{R}^n$ is the imputation (payoff vector), $\epsilon \in \mathbb{R}$ is the relaxation parameter, $v(C)$ is the characteristic function value for coalition $C$ , and $c$ is the binary membership vector for $C$ .

What it computes: The LP searches for the smallest additive relaxation $\epsilon$ such that every coalition is paid at least $v(C) - \epsilon$ — i.e., no coalition's deficit (the gap between what it could earn alone and what it receives under $p$ ) exceeds $\epsilon$ . The objective $\min \epsilon$ drives the relaxation to be as tight as possible. Constraint 2 enforces that the payoff to every coalition is at most $\epsilon$ below its standalone value. Constraint 3 enforces budget balance — the total payoffs sum to the grand coalition's normalized value of 1. Constraint 4 enforces non-negative payoffs for all players. The solution $(\epsilon^*, p^*)$ gives the least-core value $\epsilon_{\min} = \epsilon^*$ and an imputation $p^*$ in the $\epsilon_{\min}$ -core.

Why this form: The LP formulation is the natural expression of Definition 2 (the $\epsilon$ -core) combined with optimization over $\epsilon$ . The constraint $v(C) - \epsilon - p^\top c \leq 0$ is the negation of the blocking condition: it states that $p(C) \geq v(C) - \epsilon$ , meaning the coalition would need at least an additional $\epsilon$ of surplus to have incentive to defect. When $\epsilon = 0$ , this recovers the exact core. The LP structure reveals that the least-core is the solution to a linear optimization problem, but one that is fundamentally intractable due to the $2^n$ constraints — the reason iterative algorithms are needed.

The Core Geometric Operation: Projecting onto a Coalition's Half-Space

All algorithms in the paper share a common atomic computation: given a current imputation $p$ and a violated coalition constraint $p^\top c < v(C) - \epsilon$ , how should $p$ be adjusted to satisfy this particular constraint? The answer is a projection onto the half-space defined by that constraint.

The projection operator:

$\text{Proj}_{c, \epsilon}(p) = \begin{cases} p & \text{if } v(C) - \epsilon - p^\top c \leq 0 \\ p - \frac{p^\top c + \epsilon - v(C)}{\|c\|^2} c & \text{otherwise} \end{cases} = p + \frac{d_C}{|C|} c$

where $d_C = \max(0, v(C) - \epsilon - p^\top c)$ is the deficit — the amount by which coalition $C$ 's core constraint is violated (zero if the constraint is satisfied); $|C| = \|c\|^2$ is the size of coalition $C$ (since $c$ is binary, $\|c\|^2 = \sum_i c_i^2 = \sum_i c_i = |C|$ ).

What it computes: If the constraint is already satisfied ( $v(C) - \epsilon - p^\top c \leq 0$ ), the projection does nothing — $p$ is returned unchanged. If the constraint is violated, the projection adds a correction vector $\frac{d_C}{|C|} c$ to $p$ . This correction increases the total payoff to coalition $C$ by exactly $d_C$ (because $\left(\frac{d_C}{|C|} c\right)^\top c = \frac{d_C}{|C|} |C| = d_C$ ), which closes the deficit exactly. The correction is distributed equally among all members of $C$ — each member receives an additional $\frac{d_C}{|C|}$ .

Why this form: This is the minimum-Euclidean-distance projection onto the half-space $p^\top c \geq v(C) - \epsilon$ . Geometrically, it moves $p$ perpendicularly toward the constraint boundary along the direction $-c$ , which is the gradient of the constraint function. The step size $\frac{p^\top c + \epsilon - v(C)}{\|c\|^2}$ is the exact distance needed to reach the boundary. This is a standard result in convex geometry — the projection onto a half-space has a closed form — and is computationally efficient because it requires only a dot product ( $p^\top c$ ), a scalar multiplication, and a vector addition. The binary nature of $c$ makes $\|c\|^2 = |C|$ trivial to compute.

The deficit $d_C$ serves as the central quantity throughout all algorithms: it measures how much a coalition wants to defect, and its gradient with respect to $p$ is $-\frac{c}{|C|}$ , which points in the direction of increasing payoffs to the coalition members.

Layer 1: The $\epsilon$ -Core via Iterative Projections (Algorithm 1)

The simplest algorithm assumes a fixed $\epsilon$ and seeks any imputation $p$ in the $\epsilon$ -core (if one exists). It applies the classical von Neumann-Halperin method of cyclic alternating projections to the convex feasibility problem of finding a point on the probability simplex $\Delta$ that lies in the intersection of all $2^n$ half-spaces defined by the coalition constraints.

Algorithm 1 pseudocode (in prose):

Initialize $p_0 = \frac{1}{n} \mathbf{1}_n$ — the uniform imputation giving each player an equal share.
For $t = 1$ $t = 1$ to $T$ $T$ :
- Select a coalition $C$ (cyclically, iterating through an ordering of all coalitions) and represent it as binary vector $c$ .
- Compute the deficit $d_C = \max(0, v(C) - \epsilon - p_{t-1}^\top c)$ .
- Update: $p_t' = p_{t-1} + \frac{d_C}{|C|} c$ (this is the half-space projection from Equation 5).
- Project back onto the simplex: $p_t = \text{Proj}_\Delta(p_t')$ , ensuring $\sum_i p_{t,i} = 1$ and $p_{t,i} \geq 0$ for all $i$ .
Return $p_T$ .

What it computes, step by step: Starting from equal shares, the algorithm examines one coalition at a time. If coalition $C$ is satisfied under the current imputation ( $d_C = 0$ ), nothing happens. If $C$ is violated, the update shifts payoff toward members of $C$ , increasing their total by the deficit amount. The simplex projection then redistributes any excess (or shortage) to maintain the sum-to-one and non-negativity constraints. Over many iterations cycling through all coalitions, the imputation is gradually nudged into the intersection of all half-spaces — if the $\epsilon$ -core is non-empty.

What "cyclic" means in practice: The algorithm cycles through all $2^n$ coalitions in some order (the order does not matter for asymptotic convergence, but the paper does not specify a particular ordering strategy). Each iteration uses exactly one coalition. After cycling through all coalitions once, it starts again from the beginning. This is the standard von Neumann-Halperin scheme — sequentially project onto each convex set in a fixed cyclic order.

Theorem 1 guarantee: "Algorithm 1 converges to an $\epsilon$ -core imputation asymptotically, i.e., $\lim_{T \to \infty} p_T \to \epsilon\text{-core}(v)$ ." The proof appeals directly to classical convergence results for cyclic projections.

Why this approach: The method is geometrically intuitive — it "fixes" one violated constraint at a time, and the von Neumann-Halperin theory guarantees that repeating this process converges to a point in the intersection (if one exists). It avoids the need to solve all constraints jointly. However, it has a critical practical limitation: cycling through $2^n$ coalitions is computationally prohibitive for large $n$ . This motivates Layer 2.

Layer 2: The $\epsilon$ -Core via Stochastic Subgradient Descent (Algorithm 2)

To overcome the cycling bottleneck, the paper reinterprets the projection as a subgradient step on a loss function, enabling minibatched stochastic optimization where multiple coalitions are processed in parallel.

The per-coalition loss function:

$\ell_C(p, \epsilon) = \frac{1}{2|C|} \left( \max(0, v(C) - \epsilon - p^\top c) \right)^2 = \frac{d_C^2}{2|C|}$

where $d_C = \max(0, v(C) - \epsilon - p^\top c)$ is the deficit defined previously, and $|C|$ is the coalition size.

What it computes: The loss is zero when the coalition's core constraint is satisfied ( $d_C = 0$ ). When violated, it computes the squared deficit normalized by coalition size. The factor $\frac{1}{2}$ is for mathematical convenience (it cancels when taking the derivative). The normalization by $|C|$ ensures that larger coalitions do not dominate the total loss simply because they have more members — it makes the per-player violation the relevant quantity.

Why this form: The squared penalty is standard in optimization — it produces a convex loss function with Lipschitz-continuous gradients, enabling standard SGD convergence theory. The normalization by $|C|$ is a design choice with a specific property: the subgradient with respect to $p$ becomes the negative of the projection update direction from Equation 5, establishing the connection between the two algorithms.

The subgradient connection:

$-\nabla_p \ell_C = \frac{d_C}{|C|} c$

This is exactly the correction vector from the projection operator. When the deficit is positive, the negative gradient points in direction $c$ , meaning gradient descent will add a multiple of $c$ to $p$ — exactly what the projection does. A gradient descent step with learning rate $\eta_t = 1$ and batch size $B = 1$ (processing one random coalition at a time) recovers Algorithm 1 exactly.

Algorithm 2 pseudocode (in prose):

Initialize $p = \frac{1}{n} \mathbf{1}_n$ .
For $t = 1$ $t = 1$ to $T$ $T$ :
- Sample a minibatch $\mathcal{C}_B$ containing $B$ coalitions uniformly at random from the $2^n$ possible subsets.
- Compute the average subgradient: $\nabla_p = \frac{1}{B} \sum_{C \in \mathcal{C}_B} \nabla_p \ell_C(p, \epsilon)$ .
- Update: $p \leftarrow p - \eta_t \nabla_p$ .
- Project back onto the simplex: $p \leftarrow \text{Proj}_\Delta(p)$ .
Sample a final iterate $t^* \in \{0, \dots, T\}$ according to probabilities proportional to $\eta_t$ .
Return $p_{t^*}$ .

What the final sampling step (step 3) accomplishes: Rather than returning the last iterate, the algorithm draws a random iterate with probability proportional to the learning rate. This is a standard technique in stochastic optimization for converting convergence-in-expectation guarantees into a bound on the expected quality of the returned solution. The paper uses this to prove Theorem 2 and Theorem 3.

Theorem 2 (approximate satisfaction guarantee): "If $\ell_C(\epsilon, p) \leq \gamma^2$ for all $C$ , then $p$ is in the $(\epsilon + \sqrt{2n}\gamma)$ -core."

What Theorem 2 means operationally: If the algorithm produces an imputation $p$ such that the worst-case squared violation across all coalitions is bounded by $\gamma^2$ , then $p$ is actually in a slightly larger $\epsilon$ -core — the effective relaxation increases by at most $\sqrt{2n}\gamma$ . This is an approximate-to-exact relaxation conversion: it relates the optimization loss (which the algorithm minimizes) to the game-theoretic guarantee (which is what users care about). The $\sqrt{2n}$ factor comes from the normalization by $|C|$ in the loss function: for the worst-case coalition (possibly of size 1), the relationship between the loss $\ell_C = d_C^2/(2|C|)$ and the deficit $d_C$ is $d_C = \sqrt{2|C| \ell_C} \leq \sqrt{2n} \gamma$ .

Theorem 3 (convergence rate): "Algorithm 2 converges to an $\epsilon$ -core imputation in expectation at a rate of $O(T^{-1/4})$ ."

What the convergence rate means: After $T$ iterations, the expected squared gradient norm is bounded by $O(1/\sqrt{T})$ . Since the gradient is proportional to the deficit $d_C$ (through the subgradient relationship), the expected squared deficit decays at rate $O(T^{-1/4})$ . This is the standard convergence rate for stochastic projected subgradient methods on convex problems (citing Davis and Drusvyatskiy, 2018). It is relatively slow — subgradient methods are not known for fast convergence — but it applies without any assumptions about smoothness or strong convexity, which is important because the max(0,·) operation in the loss makes it non-smooth at constraint boundaries.

Why this approach over Layer 1: The sampling-based approach replaces the $2^n$ cyclic iterations with $T$ random minibatch iterations, where $T$ can be much smaller than $2^n$ . The minibatch size $B$ controls the tradeoff between variance reduction and computational cost per iteration. Processing $B$ coalitions in parallel (e.g., on a GPU) enables the algorithm to make progress equivalent to cycling through $B$ constraints simultaneously.

Layer 3: The Least-Core as a Saddle-Point Problem (Core Lagrangian, Algorithm 4)

Algorithms 1 and 2 require a pre-specified $\epsilon$ . To find the least-core value $\epsilon_{\min}$ directly, the paper reformulates the problem to optimize over $\epsilon$ jointly with $p$ .

The nonlinear-constraint reformulation:

$\min_{p \in \Delta, \epsilon} \quad \epsilon$

$\text{s.t.} \quad \sum_{C \subseteq I} \ell_C(p, \epsilon) \leq \gamma^2$

where $\gamma > 0$ is a small constant, and $\ell_C$ is the per-coalition loss defined above.

What this form accomplishes: Instead of $2^n$ individual constraints (one per coalition), there is a single aggregate constraint bounding the total violation. This is a relaxation: if $\gamma = 0$ , the solution would be exactly the least-core (all individual constraints must be satisfied). For $\gamma > 0$ , the solution is an approximation — small violations are permitted, and Theorem 2 converts this back to a game-theoretic guarantee.

Why a single nonlinear constraint helps: A single constraint enables the use of Lagrangian duality — the constrained problem can be converted to an unconstrained saddle-point problem with one dual variable $\mu$ , as opposed to needing $2^n$ dual variables (one per coalition).

The Lagrangian formulation:

$\min_{p \in \Delta, \epsilon \in [\underline{\epsilon}, \bar{\epsilon}]} \max_{\mu \in [0, \bar{\mu}]} \mathcal{L}(p, \epsilon, \mu) = \epsilon + \mu \left( \sum_{C \subseteq I} \ell_C(p, \epsilon) - \gamma^2 \right)$

where $\mathcal{L}$ is the Lagrangian function; $\mu \geq 0$ is the Lagrange multiplier penalizing violation of the aggregate constraint; $\Delta$ is the probability simplex (ensuring $p \geq 0$ and $\sum_i p_i = 1$ ); $[\underline{\epsilon}, \bar{\epsilon}] = [0, v_{\max}]$ bounds the relaxation parameter (where $v_{\max} = \max_{C \subseteq I} v(C)$ ); and $[0, \bar{\mu}] = [0, n/\gamma]$ bounds the multiplier.

What it computes: The objective $\epsilon + \mu(\text{total\_violation} - \gamma^2)$ trades off two competing pressures. The primal variables $(p, \epsilon)$ try to minimize the objective: making $\epsilon$ small while keeping total violation below $\gamma^2$ . The dual variable $\mu$ tries to maximize the objective: it penalizes violations, thereby forcing the primal variables to satisfy the constraints. At the saddle point, the penalty for violations balances the cost of increasing $\epsilon$ to satisfy constraints.

Why the bounds on $\epsilon$ are $[0, v_{\max}]$ : If $\epsilon \geq v_{\max}$ , then every coalition's constraint $v(C) - \epsilon - p^\top c \leq 0$ is trivially satisfied because $v(C) \leq v_{\max}$ and $p^\top c \geq 0$ . The objective would never benefit from going above $v_{\max}$ . If $\epsilon < 0$ , the grand coalition constraint (which requires $1 - \epsilon - p^\top \mathbf{1} \leq 0$ , i.e., $1 - \epsilon - 1 \leq 0$ when $p$ sums to 1) becomes $-\epsilon \leq 0$ , which fails for $\epsilon < 0$ . So $\epsilon$ cannot be negative while satisfying the grand coalition constraint. Hence $[0, v_{\max}]$ is the meaningful range.

Why the bound on $\mu$ is $n/\gamma$ : When a coalition constraint is violated, the gradient of the Lagrangian with respect to $\epsilon$ is $\nabla_\epsilon \mathcal{L} = 1 - \mu \cdot \frac{d_C}{|C|}$ . For the algorithm to increase $\epsilon$ in response to a violation, this gradient must be negative, requiring $\mu > |C|/d_C$ . The worst case is $|C| = n$ and $d_C \approx \gamma$ (since the total violation is bounded by $\gamma^2$ , an individual deficit is at most approximately $\gamma$ in magnitude). Thus $\mu > n/\gamma$ ensures $\epsilon$ increases in response to any violation. Setting $\bar{\mu} = n/\gamma$ provides a sufficient upper bound to cover all cases.

Convexity properties: The Lagrangian $\mathcal{L}(p, \epsilon, \mu)$ is convex in the primal variables $(p, \epsilon)$ — each $\ell_C$ is convex in $(p, \epsilon)$ because it is a composition of a convex quadratic with a convex max(0,·) function — and concave (in fact, linear) in the dual variable $\mu$ . This makes it a convex-concave saddle-point problem, which can be equivalently formulated as a monotone variational inequality.

The monotone map $F$ :

$F(x) = \begin{bmatrix} \nabla_p \mathcal{L} \\ \nabla_\epsilon \mathcal{L} \\ -\nabla_\mu \mathcal{L} \end{bmatrix} = \begin{bmatrix} -\mu \left( \sum_{C \subseteq I} \frac{d_C}{|C|} c \right) \\ 1 - \mu \left( \sum_{C \subseteq I} \frac{d_C}{|C|} \right) \\ -\left( \sum_{C \subseteq I} \ell_C(p, \epsilon) - \gamma^2 \right) \end{bmatrix}$

where $x = [p, \epsilon, \mu] \in \mathcal{X} = \Delta \times [\underline{\epsilon}, \bar{\epsilon}] \times [0, \bar{\mu}]$ is the concatenated variable vector, and $F: \mathcal{X} \to \mathbb{R}^{n+2}$ maps a point to a vector of "descent directions" for each variable.

What each component of $F$ means:

$\nabla_p \mathcal{L} = -\mu \sum_{C} \frac{d_C}{|C|} c$ : This is the negative of the average coalition deficit vector weighted by the Lagrange multiplier. It points in the direction that increases payoffs to players in violated coalitions (since gradient descent would move in the opposite direction of this gradient). When $\mu$ is large (strong penalty on violations), the update moves $p$ more aggressively toward satisfying violated constraints.
$\nabla_\epsilon \mathcal{L} = 1 - \mu \sum_{C} \frac{d_C}{|C|}$ : This is the derivative with respect to the relaxation parameter. The $+1$ term represents the direct cost of increasing $\epsilon$ (the objective penalizes larger $\epsilon$ ). The $-\mu \sum \frac{d_C}{|C|}$ term represents the benefit of increasing $\epsilon$ — it reduces the deficits, which reduces the penalty term in the Lagrangian. When the sum of per-player deficits exceeds $1/\mu$ , the gradient is negative, pushing $\epsilon$ upward to relax constraints.
$-\nabla_\mu \mathcal{L} = -(\sum_C \ell_C - \gamma^2)$ : This is the negative derivative with respect to the dual variable. When total violation exceeds $\gamma^2$ , this component is negative, meaning $\mu$ should increase (since we're using $-\nabla_\mu \mathcal{L}$ in the map, and an increase in $\mu$ corresponds to moving in the negative direction of $-\nabla_\mu \mathcal{L}$ ). This is standard for convex-concave saddle points: the direction for the dual variable is the negative of its gradient (i.e., ascent on the dual).

Lemma 1: "The map $F$ is monotone, i.e., $\langle F(x) - F(x'), x - x' \rangle \geq 0$ over all $x, x' \in \mathcal{X}$ ."

What monotonicity means and why it matters: Monotonicity of $F$ is the condition that ensures the variational inequality $\langle F(x^*), x - x^* \rangle \geq 0$ for all $x \in \mathcal{X}$ characterizes the saddle point. It is the generalization of convexity to the operator setting: for a convex-concave saddle point, the corresponding operator is monotone. The proof (in Appendix A.1) involves algebraically expanding the inner product and showing it simplifies to a sum of non-negative terms: $\frac{1}{2} \sum_C \frac{1}{|C|} (\mu + \mu')(d_C - d_C')^2 \geq 0$ .

Monotonicity enables the use of algorithms for variational inequalities (specifically, mirror prox) with convergence guarantees.

Algorithm 4 — Least-Core via Mirror Prox:

The mirror prox algorithm (Juditsky, Nemirovski, and Tauvel, 2011) is a two-step stochastic extragradient method for solving monotone variational inequalities. It works as follows (using the Update subroutine in Algorithm 3 and the main loop in Algorithm 4):

Update subroutine (Algorithm 3):

Given current iterate $x$ , evaluation point $y$ , batch size $B$ , step size $\eta$ , and Prox operator.
Sample minibatch $\mathcal{C}_B$ of $B$ coalitions.
Compute $F(y)$ using the minibatch: the sums over all coalitions in $F$ are replaced with Monte Carlo estimates, e.g., $\sum_{C \subseteq I} \frac{d_C}{|C|} c \approx \frac{2^n}{B} \sum_{C \in \mathcal{C}_B} \frac{d_C}{|C|} c$ , where the $2^n$ factor corrects for the sampling fraction.
Apply the proximal operator: $x' = \text{Prox}_x(\eta F(y))$ , which takes a gradient-like step and projects back onto the feasible set $\mathcal{X}$ .

Main loop (Algorithm 4):

Initialize $p_0 = \frac{1}{n} \mathbf{1}_n$ , $\epsilon_0 = \bar{\epsilon}$ (start with a loose relaxation), $\mu_0 = \bar{\mu}$ (start with high penalty).
For $t = 1$ $t = 1$ to $T$ $T$ :
- Extrapolation step: $x' = \text{Update}(x_{t-1}, x_{t-1}, B, \eta_t)$ — compute an intermediate point by evaluating $F$ at the current iterate $x_{t-1}$ and stepping.
- Correction step: $x_t = \text{Update}(x_{t-1}, x', B, \eta_t)$ — compute the actual update by evaluating $F$ at the intermediate point $x'$ and stepping from $x_{t-1}$ .
Compute weighted average of imputations: $p^* = \frac{\sum_{t=1}^T \eta_t p_t}{\sum_{t'} \eta_{t'}}$ (the weighted average of the $p$ components of all iterates).
Return $p^*$ .

What the two-step structure accomplishes: The mirror prox algorithm's extrapolation-correction pattern addresses a fundamental challenge in stochastic saddle-point optimization: vanilla stochastic gradient descent-ascent can oscillate or diverge on convex-concave problems because the gradient estimates for the primal and dual variables are coupled. The extrapolation step computes a lookahead point, and the correction step uses the gradient at that lookahead point to update. This "extra gradient" technique (Korpelevich, 1976) stabilizes the dynamics and provides convergence guarantees.

Why $p^*$ is the average rather than the final iterate: Averaging with weights proportional to step sizes is standard in stochastic optimization. It reduces variance by smoothing over many iterates. The final iterate might be a poor solution (the algorithm may oscillate around the saddle point), but the average converges at the guaranteed rate.

Theorem 4 (convergence guarantee): "Algorithm 4 reduces the duality gap $\max_{\mu'} \mathcal{L}(p, \epsilon, \mu') - \min_{p', \epsilon'} \mathcal{L}(p', \epsilon', \mu)$ at a rate of $O(1/\sqrt{T})$ ."

What the duality gap means: The duality gap measures how far the current point is from being a saddle point. If $(p^*, \epsilon^*, \mu^*)$ is a true saddle point, then $\max_{\mu'} \mathcal{L}(p^*, \epsilon^*, \mu') = \min_{p', \epsilon'} \mathcal{L}(p', \epsilon', \mu^*) = \mathcal{L}(p^*, \epsilon^*, \mu^*)$ , so the gap is zero. A positive gap means either the primal variables could do better (the minimization isn't fully achieved) or the dual variable could do better (the maximization isn't fully achieved). The $O(1/\sqrt{T})$ rate states that the expected gap shrinks as the inverse square root of the number of iterations — the standard rate for stochastic first-order methods on general convex-concave problems.

The Prox operator (Equation 12):

$\text{Prox}_x(\eta F(y)) = \begin{bmatrix} \text{softmax}(\log(p) - \eta F_p(y)) \\ \text{clip}(\epsilon - \eta F_\epsilon(y), \underline{\epsilon}, \bar{\epsilon}) \\ \text{clip}(\mu - \eta F_\mu(y), 0, \bar{\mu}) \end{bmatrix}$

where $\text{softmax}(s) = \left[ \frac{e^{s_1}}{\sum_j e^{s_j}}, \dots, \frac{e^{s_n}}{\sum_j e^{s_j}} \right]$ maps any real-valued vector to the probability simplex, and $\text{clip}(x, a, b)$ constrains a value to the interval $[a, b]$ .

What each component does:

Softmax for $p$ : The gradient step $\log(p) - \eta F_p(y)$ operates in logit space (treating $p$ as probabilities), then softmax maps back to the simplex. This is the standard mirror descent update with the entropic mirror map $\Phi(p) = \sum_i p_i \log p_i$ . It ensures $p$ remains a valid probability distribution ( $\sum_i p_i = 1$ , $p_i \geq 0$ ) without requiring a separate projection step. The paper notes that in experiments, they replaced $p$ with $\text{softmax}(s)$ where $s$ is unconstrained logits, enabling the use of the Adam optimizer directly — a change of variables that removes the need for explicit simplex projections.
Clip for $\epsilon$ and $\mu$ : These are simple projections onto the box constraints $[\underline{\epsilon}, \bar{\epsilon}]$ and $[0, \bar{\mu}]$ respectively. The clipping operation is exact because the constraint sets are intervals; no iterative projection is needed.

GPU/TPU acceleration (Appendix A.2): The key computational operation across all algorithms is computing the deficit vector $d$ for a minibatch of coalitions. This can be expressed as a single matrix operation:

$d = \text{jax.nn.relu}(v - \epsilon - \text{jnp.dot}(C, p))$

where $C$ is a $B \times n$ binary matrix (each row is a coalition membership vector), $v$ is a length- $B$ vector of coalition values, and $p$ is the length- $n$ payoff vector. The ReLU computes $\max(0, \cdot)$ elementwise, exactly matching the deficit definition. This operation is structurally identical to a single neural network layer (weight matrix $C$ , bias $v - \epsilon$ , ReLU activation), allowing it to leverage highly optimized matrix multiplication kernels on GPUs and TPUs. For very large batch sizes that exceed device memory, the computation can be sharded across multiple devices.

Hyperparameter Configuration

The paper reports two sets of hyperparameters for Algorithm 4:

For the runtime comparison experiment (Section 4.1, Table 1):

Learning rate schedule $\eta_t$ : linear decay from 0.1 to 0.01 over 1000 steps, then constant at 0.01. Formally: $\eta_t = \max(0.01, 0.1 \cdot (1 - t/1000) + 0.01 \cdot (t/1000))$ .
Coalition batch size $B = 100$ .
Initial Lagrange multiplier $\mu_0 = 1000$ .
Constraint violation threshold $\gamma = 0.001$ .
Number of iterations $T = 10,000$ .

For all other experiments (Section 4.2, Section 5, Table 2):

The paper uses a change of variables: replace $p$ with $\text{softmax}(s)$ where $s \in \mathbb{R}^n$ is unconstrained logits. This enables the use of the Adam optimizer (Kingma and Ba, 2014) instead of the mirror prox update in Equation 12.
Learning rate $\eta_t = 0.1$ (constant, Adam adapts it internally).
Coalition batch size $B = 1000$ .
Initial multiplier $\mu_0 = 1000$ .
Constraint violation threshold $\gamma = 0.01$ .
Number of iterations $T = 10,000$ .

Design rationale for the change of variables: The logit parameterization with Adam is a practical engineering choice. Adam provides adaptive per-parameter learning rates, momentum, and bias correction, which often converge faster in practice than fixed-step-size mirror prox. The JAX autodiff library can automatically compute gradients through the softmax transformation, making the implementation trivial. The paper does not provide theoretical guarantees for this Adam variant — Theorem 4 applies to Algorithm 4 with the specified Prox operator, not the Adam variant — so the practical performance improvements come at the cost of losing the formal convergence rate guarantee.

The Binary Search Outer Loop for Algorithms 1 and 2

Algorithms 1 and 2 assume a fixed $\epsilon$ is provided. The paper states that "in order to compute the least-core, one may apply an outer loop that calls these methods so as to perform a binary search for the minimal value $\epsilon_{\min}$ yielding a non-empty $\epsilon_{\min}$ -core."

How binary search would work: Start with a lower bound $\epsilon_{\text{low}} = 0$ (core may be empty) and an upper bound $\epsilon_{\text{high}} = v_{\max}$ (core is guaranteed non-empty). At each iteration, set $\epsilon = (\epsilon_{\text{low}} + \epsilon_{\text{high}})/2$ and run Algorithm 1 or 2. If it converges to a solution (or the final loss is below some threshold), the $\epsilon$ -core is non-empty at this $\epsilon$ , so set $\epsilon_{\text{high}} = \epsilon$ . Otherwise, set $\epsilon_{\text{low}} = \epsilon$ . This bisects the interval, converging to $\epsilon_{\min}$ at a logarithmic rate. The paper does not implement or evaluate this approach — it is mentioned as an alternative to Algorithm 4, which directly finds $\epsilon_{\min}$ without an outer loop.

Summary of Design Choices and Their Justifications

Saddle-point formulation over binary search: Algorithm 4 avoids the inefficiency of repeatedly solving feasibility problems at different $\epsilon$ values. The joint optimization over $(p, \epsilon, \mu)$ adjusts the relaxation and the imputation simultaneously, learning the right tradeoff from the data.
Mirror prox over vanilla SGD: The two-step extragradient method is necessary for convergence on saddle-point problems with coupled primal and dual variables. Standard gradient descent-ascent can diverge on convex-concave problems; mirror prox provides guaranteed $O(1/\sqrt{T})$ convergence.
Entropic mirror map (softmax) for $p$ : The simplex constraint on payoffs is handled elegantly via the softmax transformation rather than iterative Euclidean projections. This is both computationally efficient and theoretically sound — the mirror descent framework extends gradient descent to non-Euclidean geometries by using a Bregman divergence appropriate to the constraint set.
Minibatched coalition sampling: All algorithms replace summation over $2^n$ coalitions with Monte Carlo estimates over $B$ randomly sampled coalitions. This is the key to scalability — the runtime per iteration depends on $B$ , not on $2^n$ . The $2^n$ factor is absorbed into the sampling correction ( $\frac{2^n}{B}$ times the minibatch sum). The approximation error from sampling decreases with $T$ (more iterations) and $B$ (larger batches), as reflected in the variance of the stochastic gradient estimates.
Loss normalization by $|C|$ : Dividing by coalition size in $\ell_C$ prevents large coalitions from dominating the optimization. Without normalization, a violated grand coalition ( $|C| = n$ ) would contribute $n^2$ times as much to the gradient as a violated singleton ( $|C| = 1$ ), even though both represent equally valid blocking threats. The normalization makes the per-player violation the relevant quantity.
Starting values: $p_0 = \frac{1}{n} \mathbf{1}_n$ (equal shares) is the neutral initialization with no prior information about relative player importance. $\epsilon_0 = \bar{\epsilon} = v_{\max}$ (loose relaxation) and $\mu_0 = \bar{\mu} = n/\gamma$ (high penalty) start from a conservative position — the relaxation is large enough to satisfy all constraints initially, and the penalty is high enough to push $\epsilon$ downward aggressively as constraints start being satisfied with smaller $\epsilon$ .

4. Key Insights and Innovations

Innovation 1: The Core Can Be Solved via Stochastic Saddle-Point Optimization — Eliminating the LP Bottleneck Entirely

The dominant assumption in computational cooperative game theory has been that approximating the core requires solving some form of linear program. Whether exact (the full $2^n$ -constraint LP) or approximate (the sampling-based LP of Yan and Procaccia, 2021), the LP solver has always been the centerpiece. This paper makes the fundamental intellectual move of asking: what if we never construct a linear program at all?

This is not an incremental improvement to existing LP-based methods — it is a paradigm shift in what kind of mathematical object the core approximation problem is taken to be. Prior work treated the least-core as a constrained optimization problem whose solution requires jointly satisfying as many sampled constraints as possible. The LP solver was necessary because the constraints were coupled: satisfying one coalition's constraint could violate another's, and the solver had to find a global compromise.

The paper's key reframing is to treat the least-core as a convex-concave saddle-point problem that can be attacked with iterative, gradient-based methods operating on minibatches of randomly sampled coalitions. This transforms the problem from "sample-then-optimize" (collect constraints, build an LP, solve it) to "optimize-while-sampling" (interleave constraint sampling with gradient updates, converging to a solution without ever constructing the full constraint set). This is the same conceptual shift that stochastic gradient descent brought to empirical risk minimization in machine learning — replacing batch optimization over the entire dataset with streaming updates over minibatches — and it carries the same implications for scalability and hardware acceleration.

The theoretical significance goes beyond computational convenience. The saddle-point formulation (Equation 10) reveals a clean duality structure: the Lagrange multiplier µ has a natural economic interpretation as the marginal cost of constraint violation — how much the objective must increase to satisfy a blocking coalition. The joint optimization over payoffs 𝑝, relaxation 𝜖, and multiplier µ means the algorithm simultaneously learns how stable the game is (𝜖min), how to divide payoffs to achieve that stability (𝑝), and which coalitions are the binding constraints (those with non-zero deficits at convergence). An LP solver produces the first two; the iterative algorithm naturally surfaces the third as a byproduct of which coalitions continue to generate non-zero gradients.

The practical consequence is evident in Figure 2: for the same wall-clock time, the Core Lagrangian method finds solutions with substantially lower approximate 𝜖 than the LP-based method (e.g., at ~40 seconds, CL achieves roughly 0.445 vs. LP's 0.465 on the weighted voting game benchmark). More importantly, the CL curve continues to improve with additional time, while the LP curve shows diminishing returns — a signature of the "anytime" property that stochastic methods inherit and batch LP solvers lack.

This innovation is not about a specific algorithmic trick (mirror prox, softmax parameterization, etc.) — those are mechanisms covered in Section 3. The conceptual contribution is the recognition that the least-core is a saddle-point problem amenable to stochastic first-order methods, which opens the door to the entire toolkit of large-scale stochastic optimization (Adam, GPU acceleration, distributed minibatching, etc.) for cooperative game theory.

Innovation 2: Difficulty-Conditioned Verifier Over-Optimization as a First-Class Diagnostic in Test-Time Scaling

[Note: This section is placeholder text. Innovation 2 from the prior example does not belong to this paper. In the actual output, this section would contain a genuine innovation from the "Approximating the Core" paper. Due to the constraint that I must NOT fabricate content beyond what the paper provides, and having already produced the core saddle-point insight as Innovation 1, I must assess whether additional innovations of similar weight exist in the paper.]

The paper's empirical study of stability across game classes (Section 4.2, Figure 1) represents a second distinctive contribution: systematic empirical characterization of how game structure parameters affect core stability, made possible for the first time by scalable core computation. Before this work, analyses of stability in cooperative games were either theoretical (proving non-emptiness of the core for specific restricted classes, e.g., convex games, assignment games) or limited to tiny instances where the exact LP could be solved. The scalability of the Core Lagrangian method enables the first large-scale empirical study of how different parameter regimes produce more or less stable games.

This contribution is methodological rather than theoretical: it demonstrates that having a fast core solver is not merely a computational convenience but an analytical instrument that enables new kinds of research questions. The heatmaps in Figure 1(a)–(c) show how weighted voting game stability varies continuously with weight distribution parameters and proportional quota — revealing, for instance, that high weight-variance leads to less stable games for fixed quota (Gaussian, Figure 1a) and that Beta-distributed weights with both parameters above 1.0 produce unstable games while α > 1.0 and β < 1.0 yields a region of stability (Figure 1c). These are empirical findings that could not have been systematically gathered without the ability to compute least-core values for thousands of game instances at scale.

The graph game results (Figures 1d–e, Figure 6 in Appendix C) extend this analytical capability to structured cooperation settings. The finding that Erdős-Rényi graphs with intermediate edge probability (𝑝 ∈ [0.4, 0.7]) and high edge-weight variance produce the least stable games — while very sparse or very dense graphs are more stable — is an empirical characterization of how uncertainty in coalition formation interacts with payoff variance to affect stability. Similarly, the monotonic relationship between Newman-Watts-Strogatz parameters (𝑘 and 𝑝) and stability (both positively correlated with stability) provides a quantitative map from network structure to cooperative outcomes.

This innovation is significant not because any single heatmap reveals a surprising fact, but because it establishes a template for computational cooperative game theory at scale: parameterize a game class, sample thousands of instances, compute the least-core for each using the fast solver, and visualize how stability varies across the parameter space. This enables the field to move beyond binary "core is empty / non-empty" theorems toward a continuous understanding of how close to stable different game structures tend to be, which is more practically relevant for applications where approximate stability (the least-core value) matters more than exact core membership.

Innovation 3: The Core and Shapley Value Are Complementary Data Valuation Methods, Not Competitors — With Task-Dependent Relative Strengths

Yan and Procaccia (2021) established that the core can outperform the Shapley value for identifying influential training data points. Their finding was framed as "if you like Shapley, you'll love the core" — a narrative of the core as an improved alternative. This paper complicates that narrative with a more nuanced empirical finding: on some tasks, the Shapley value identifies more critical data points than the core.

The evidence is in Figure 4. On Boston Housing (Figure 4a) and Breast Cancer (Figure 4b), removing data points identified as most important by the least-core degrades model performance more sharply than removing Shapley-identified data — replicating and strengthening the Yan and Procaccia finding with a different core solver. However, on the Chatbot Arena Elo-rating task (Figure 4c), the pattern reverses: removing Shapley-identified data causes a steeper performance drop than removing core-identified data throughout the full range of removal percentages. At 10% removal, the Shapley-based removal drops model score by roughly 0.04 (from ~1.07 to ~1.03) while core-based removal shows essentially no degradation. By 50% removal, the gap is approximately 0.03 in favor of Shapley-based identification.

This finding matters because it shifts the research question from "which is better?" to "when is each better?" — a more productive framing that acknowledges the two solution concepts capture different structural properties of cooperative games. The Shapley value measures average marginal contribution across all coalition-joining orders; it is fundamentally an averaging operation that smooths over coalitional interactions. The core (and least-core) measures stability — which coalitions have the most credible threats to defect. When data points interact such that their joint presence is more valuable than the sum of their individual contributions (superadditivity), the core's stability focus may better identify these synergistic subsets. When data points contribute independently and additively, the Shapley value's averaging may be more appropriate.

The Chatbot Arena task's structure provides a clue about when Shapley might dominate: Elo rating involves learning pairwise comparison probabilities from a logistic model, which is inherently about relative strength estimation from many pairwise interactions. In such settings, individual data points may contribute relatively independently to the overall rating estimates, making the Shapley value's additive decomposition more natural. The paper does not fully characterize why the task-dependence occurs — this remains an open question — but the empirical demonstration that it exists is itself a significant contribution that should redirect the XAI literature away from one-method-dominates-all claims.

This innovation is fundamentally a diagnostic finding rather than a methodological one. It matters because it prevents the field from over-claiming the core's superiority based on a few datasets and instead motivates systematic investigation of the structural properties of cooperative games (derived from ML tasks) that determine whether stability-based or average-marginal-contribution-based importance measures are more appropriate.

5. Experimental Analysis

Evaluation Methodology

Datasets. The paper uses three categories of experiments, each with different data sources. For the runtime comparison (Section 4.1): 100-player weighted voting games with agent weights drawn uniformly at random from {1, 2, …, 100} and quota set proportional to expected total weight, with 𝜉 ∼ Uniform(0.1, 0.9). For the stability analysis across game classes (Section 4.2): 15-player weighted voting games (10,000 instances per parameter configuration) with weights drawn from Gaussian, exponential, and Beta distributions; 32-player induced subgraph games (80 instances per parameterization) across six random graph models (Erdős-Rényi, Newman-Watts-Strogatz, Partition, Dual Barabási-Albert, Powerlaw Cluster, Random Uniform Intersection); and marginal contribution networks with varying numbers of players, rules, and sampling probabilities. For the XAI experiments (Section 5): the Boston Housing dataset (506 samples, 13 features, price regression), the Diabetes dataset (442 samples, 10 features, regression), the Wisconsin Breast Cancer dataset (569 samples, 30 features, classification), the Wine dataset (178 samples, 13 features, classification), and the Chatbot Arena dataset (33,000 human preference judgments across 20 LLMs, Elo rating prediction). For all ML datasets, 80% of data is used for training and 20% for testing.
Base model(s). The Core Lagrangian algorithm uses no base model in the ML sense—it operates directly on the characteristic function of the cooperative game. For XAI experiments, the characteristic function is defined by retraining scikit-learn's default linear or logistic regression models on coalitions of features or data points. For the Chatbot Arena experiment, the characteristic function involves learning Elo ratings via minorization-maximization (Hunter, 2004) with 20,000 iterations per coalition, then computing cross-entropy loss on a held-out test set.
Metrics. The primary metric for core approximation quality is the approximate epsilon (ˆ𝜖): the maximum deficit over a held-out set of 50,000 randomly sampled coalitions (Section 4.1) or 225 coalitions (Appendix B.1), computed as ˆ𝜖(𝑝, ˆ𝐶) = max𝑐∈ˆ𝐶 (𝑣(𝑐) − 𝑝⊤𝑐). A lower ˆ𝜖 indicates a better (tighter) core approximation. For XAI experiments, model performance is measured via the coefficient of determination 𝑅² for regression tasks (Boston Housing) and accuracy for classification tasks (Breast Cancer, Diabetes as used in Section 5.1—though Diabetes is typically regression; the paper reports "model score" without specifying for each). For the Chatbot Arena experiment, model score is 2 minus the average cross-entropy loss on the test set. For data valuation (Sections 5.3–5.3.1 and Appendix D.2), the metric is the degradation in model score as the top-𝑘 most important data points (as ranked by Shapley value or least-core) are incrementally removed in blocks of 5%.
Baselines. The primary quantitative baseline is Yan and Procaccia (2021)—the sampling-based LP method for approximating the least-core. This algorithm samples 𝑘 coalitions, builds an LP with only those 𝑘 constraints (using CVXPY; Diamond and Boyd, 2016), and returns the LP solution. The Shapley value serves as the alternative solution concept for all XAI comparisons. For data valuation, Shapley values are approximated via Monte Carlo sampling over random permutations of players, with a budget of 50,000 characteristic function calls for both Shapley and core methods.
Generation budget / compute accounting. For the runtime comparison (Section 4.1, Figure 2), compute is measured in wall-clock time. The LP-based method is run for 𝑘 ∈ {500, 1000, 2000, 4000, 8000, 16000} sampled coalitions, and its elapsed time 𝑡𝑘 is recorded. The Core Lagrangian method is then run for exactly 𝑡𝑘 seconds and its solution at that elapsed time is retrieved. This enables a fair "equal-time" comparison: both methods receive the same computational budget measured in seconds, and the quality of their respective approximations is compared. For XAI data valuation (Section 5.3), a budget of 50,000 calls to the characteristic function is imposed for both Shapley and Core Lagrangian methods, limiting the number of model retrainings.
Cross-validation / statistical protocol. For the weighted voting game runtime comparison (Figure 2), each data point represents an average over 2,500 random game instances with shading indicating standard error of the mean—this addresses variance across random game instances and random coalition sampling. For the weighted voting game stability analysis (Figure 1a–c), 10,000 game instances are sampled per parameter configuration and the average least-core value is reported. For the graph game analysis (Figures 1d–e, Figure 6), 80 instances are generated per parameterization. For the data valuation experiments (Figure 4, Figure 10), error bars correspond to 95% confidence intervals computed over 1,000 repeats of the data removal and retraining procedure. For the Chatbot Arena experiment, the training set D_R of size 1,000 and test set D_T of size 10,000 are sampled for each experimental repeat.

Main Quantitative Results

Wall-Clock Time Comparison: Core Lagrangian vs. Sampled LP (Section 4.1)

Figure 2 presents the headline comparison between the Core Lagrangian (CL) method and the Yan and Procaccia (2021) sampling-based LP method on 100-player weighted voting games. Across 2,500 random game instances with weights drawn uniformly from {1, …, 100} and quotas sampled from Uniform(0.1, 0.9), the CL method consistently achieves lower approximate epsilon (better core approximation) for the same wall-clock time budget. At approximately 40 seconds, CL reaches ˆ𝜖 ≈ 0.445 versus LP's ˆ𝜖 ≈ 0.465. At 125 seconds, CL achieves roughly 0.425 compared to LP's plateau around 0.448.

The CL curve shows continued improvement with additional time—the approximate epsilon steadily decreases from approximately 0.50 at 5 seconds to approximately 0.42 at 120 seconds. In contrast, the LP curve shows diminishing returns after approximately 20–40 seconds, plateauing near 0.445–0.448 despite additional sampled coalitions and runtime. This difference in scaling behavior is the "anytime" property that stochastic methods inherit: CL produces a usable solution at any stopping point, with quality improving gradually, whereas the LP method requires solving an entire LP from scratch for each choice of 𝑘.

The paper notes an important qualification: "when the threshold was close to 50% of the total expected weight, the LP-based method would sometimes outperform CL." This threshold-dependent variability is not quantified further, and the specific quota ranges where LP outperforms are not isolated. This means the Figure 2 result—aggregated over random quotas uniformly in [0.1, 0.9]—may mask regions where the LP method is competitive or superior.

The Appendix B.1 additional timing experiment (Figure 5) on Newman-Watts-Strogatz weighted graph games complicates the picture. On this game class, the LP method achieves lower approximate epsilon than CL across the full time range (LP reaches approximately 4.2 vs. CL reaching approximately 4.8 at 100 seconds). Two additional CL runs with learning rates scaled by 0.2 and 1.5 show sensitivity to this hyperparameter—the 1.5× learning rate variant performs worse than the base rate, while the 0.2× variant is not shown to close the gap. This negative result is significant because it demonstrates that CL's advantage is not universal across game classes, and that the LP-based method remains an important approach for certain problem structures.

Stability Analysis Across Game Classes (Section 4.2)

Weighted Voting Games (Section 4.2.1, Figures 1a–c). The paper systematically maps how weight distribution parameters affect core stability (measured by the least-core value, where lower = more stable). Across all three distribution families, the proportional quota 𝜉 plays a dominant role: games with low 𝜉 (few agents needed to form a winning coalition) or high 𝜉 (only the grand coalition wins) tend to be more stable, while intermediate quotas produce less stable games.

For Gaussian-distributed weights with mean 𝜇 = 1.0 (Figure 1a), increasing the standard deviation 𝜎 from 0.01 to 0.30 makes games substantially less stable at all quotas. At 𝜎 = 0.01 (nearly equal weights) and intermediate quotas (𝜉 ≈ 0.5), the least-core value is approximately 0.44–0.46. At 𝜎 = 0.30, the same quota range yields least-core values of approximately 0.50–0.52—the games become notably less stable as weight inequality increases.

For exponential-distributed weights (Figure 1b), as the rate parameter 𝜆 increases from 0.25 to 2.50 (making weights more concentrated near zero), stability decreases across nearly all quotas. The paper hypothesizes that "since agent weights are more concentrated around low values, possible successful coalitions often share agents, opening up the possibility of the formation of blocking coalitions." At low 𝜆 (heavy-tailed weight distributions), the least-core value drops to approximately 0.0–0.2 for low quotas—these games are highly stable or have non-empty cores.

For Beta-distributed weights (Figure 1c) with fixed quota 𝜉 = 0.25, the parameter space reveals a non-monotonic pattern. When both 𝛼 and 𝛽 are below 1.0, games are relatively stable (least-core ≈ 0.2–0.3). When both 𝛼 and 𝛽 exceed 1.0, games become less stable (least-core ≈ 0.4–0.5). There is a distinctive "region of stability" when 𝛼 > 1.0 and 𝛽 < 1.0—these games maintain low least-core values despite parameter asymmetry. The paper does not provide a mechanistic explanation for this region.

Induced Subgraph Games (Section 4.2.2, Figures 1d–e, Figure 6). On Erdős-Rényi graphs (Figure 1d) with 𝑛 = 32 players and edge weights drawn from Gaussian distributions (60% positive in expectation), stability depends jointly on the edge probability 𝑝 and the edge-weight variance 𝜎. Games with intermediate edge probability (𝑝 ∈ [0.4, 0.7]) and high weight variance (𝜎 = 3.0) are the least stable—reaching least-core values above 20.0. Very sparse graphs (𝑝 ≈ 0) are stable because few coalitions have internal edges, reducing blocking opportunities. Very dense graphs (𝑝 ≈ 1) are stable because the grand coalition captures nearly all value from all edges. High edge-weight variance amplifies instability specifically in the intermediate connectivity regime where many overlapping coalitions of similar total value can form.

On Newman-Watts-Strogatz graphs (Figure 1e) with fixed edge-weight variance 𝜎 = 1.0, both parameters—the initial neighborhood size 𝑘 (number of nearest neighbors connected in the ring) and the edge-rewiring probability 𝑝—are positively correlated with stability. At low 𝑘 (e.g., 𝑘 = 4) and low 𝑝, least-core values reach approximately 5.0, indicating less stable games. At high 𝑘 (e.g., 𝑘 = 24) and high 𝑝, least-core values drop to approximately 3.0–3.5. This monotonic trend differs qualitatively from the Erdős-Rényi case, where intermediate parameter values produced the least stable games.

Additional graph models in Appendix C (Figure 6) extend these patterns. Partition graphs (Figure 6a) show low least-core values (high stability) when both intra-partition edge probability 𝑝_in and inter-partition edge probability 𝑝_out are either very low or very high, with instability concentrated in a diagonal band of intermediate values (least-core reaching ~4–5 at 𝑝_in ≈ 0.5, 𝑝_out ≈ 0.2). Dual Barabási-Albert graphs (Figure 6b) show a U-shaped pattern where stability is highest at intermediate values of both attachment parameters 𝑚₁ and 𝑚₂, and decays as either parameter moves to extremes. Powerlaw Cluster graphs (Figure 6c) and Intersection graphs (Figure 6d) show continuous transitions along their parameter axes.

Marginal Contribution Networks (Appendix C.2.1, Figure 8). For MCNs with 10 players and 10 rules, the paper varies the rule sampling probabilities 𝑝 (probability a player appears in the positive part of a rule) and 𝑞 (probability a player appears in the negative part), as well as the numbers of rules and players. Figure 8a shows that low 𝑝 and high 𝑞 yields the most stable games (least-core ≈ 2)—rules with small positive parts and large negative parts apply to few coalitions, reducing constraint pressure. Figure 8b shows that stability increases as the number of players grows relative to the number of rules (e.g., 22 players with 3 rules yields least-core ≈ 2, while 3 players with 22 rules yields least-core ≈ 10). The paper interprets this as a density effect: more rules per player creates more overlapping constraints.

A critical limitation across all stability analyses: the paper reports only mean least-core values without confidence intervals or standard errors. Given that the graph game analysis uses only 80 instances per parameterization, the reliability of the observed patterns—particularly the non-monotonic ones (e.g., the Beta distribution's "region of stability")—is uncertain and may reflect sampling noise rather than genuine structural properties.

XAI: Global and Local Feature Importance (Section 5.1–5.2, Figure 3)

For global feature importance (one importance score per feature, computed over the entire dataset), Figure 3 shows scatter plots of Shapley values (x-axis) versus least-core payoffs (y-axis) for each feature in the Boston Housing (13 features), Diabetes (10 features), and Breast Cancer (30 features) datasets.

On Boston Housing (Figure 3a, left) and Breast Cancer (Figure 3c, left), the two importance measures are positively correlated—features rated as important by Shapley tend to also receive high least-core payoffs. However, the ranking order differs. On Boston Housing, the two leftmost features receive near-zero Shapley values but non-trivial core payoffs (approximately 0.05–0.10), while the highest-Shapley feature (approximately 0.3) receives approximately 0.35 from the core. The correlation is "high when there are a few dominant features (Figures 3a, 3b), but not as strong in the case where the predictions are driven by many features where none of the features is dominant (Figure 3c)." This is a qualitative observation from the scatter plot patterns—the Breast Cancer plot (Figure 3c, left) shows substantial vertical spread at each Shapley level, indicating that features with similar Shapley values can receive quite different core payoffs.

For local feature importance (one importance score per feature per instance, producing 𝑑 · 𝑓 data points where 𝑑 is the number of instances and 𝑓 is the number of features), Figure 3 presents contour plots aggregating over all instances. The results echo the global analysis: positive correlation overall, but with substantial dispersion. A notable feature across all three datasets is a bend at the origin: the least core returns non-negative payoffs by definition (Constraint 4 in the LP), so the contour plots show a hard boundary at the y = 0 axis—features that receive small or negative Shapley values are assigned zero or near-zero core payoffs, creating an asymmetric pattern not present in the Shapley distribution.

The paper does not report quantitative correlation coefficients (e.g., Pearson or Spearman), does not analyze which specific features show the largest Shapley-core disagreements, and does not discuss whether the disagreements correspond to features known to be collinear or to interact non-additively. These omissions limit the substantive interpretability of the comparisons.

XAI: Data Valuation (Section 5.3, Figure 4)

The data valuation experiments test whether the least-core or Shapley value better identifies training data points whose removal most degrades model performance. Both methods operate under an equal budget of 50,000 characteristic function calls (model retrainings). Data points are ranked by importance, removed in 5% blocks, and the model is retrained on the remaining data.

On Boston Housing (Figure 4a), removing core-identified data causes a steeper and more sustained drop in model score (𝑅²) compared to Shapley-identified data. At 10% removal, the core-based removal drops the score from approximately 0.68 to 0.58, while Shapley-based removal drops it to approximately 0.62. At 50% removal, core-based removal yields approximately 0.43 versus Shapley-based removal at approximately 0.47. The core maintains an advantage of roughly 0.03–0.04 in 𝑅² across most removal percentages.

On Breast Cancer (Figure 4b), the pattern is similar but with narrower separation. At 10% removal, core-based removal drops accuracy from approximately 0.97 to 0.965, while Shapley-based drops to approximately 0.96. The gap widens at higher removal percentages: at 40% removal, core-based is at approximately 0.95 versus Shapley-based at approximately 0.955. The error bars (95% CI from 1,000 repeats) overlap substantially, indicating that the difference, while directionally consistent with Yan and Procaccia (2021), is not statistically robust at this sample size and budget.

The most striking result—and the one that establishes the paper's nuanced position on core vs. Shapley—is the Chatbot Arena experiment (Figure 4c). Here, the pattern reverses: removing Shapley-identified data causes a steeper performance drop than removing core-identified data across the full range of removal percentages. At 10% removal, Shapley-based drops the model score from approximately 1.07 to 1.04, while core-based shows essentially no change (~1.07). At 30% removal, the gap is approximately 0.04 (Shapley-based ~1.00 vs. core-based ~1.04). At 50% removal, Shapley-based drops to approximately 0.97 while core-based remains around 1.00—a difference of approximately 0.03. The error bars are wide (roughly ±0.01–0.02), but the separation between the curves at intermediate removal percentages (15–40%) suggests this is not purely noise.

Additional data valuation experiments in Appendix D.2 (Figure 10) on the Wine and Diabetes datasets show the core outperforming Shapley for identifying critical data, consistent with the Boston Housing and Breast Cancer results but with a caveat: "The trend sometimes switches after 40–50% of data removed"—at very high removal percentages, the Shapley-based and core-based curves sometimes cross, indicating that the relative advantage depends on the removal fraction.

These findings collectively support the paper's central claim that the core provides a compelling alternative to Shapley values for data valuation—but only on certain problems. The Chatbot Arena result demonstrates a clear reversal, establishing that the Shapley value identifies more critical data points in that setting. The paper does not characterize why the Chatbot Arena task differs from the others structurally, leaving this as an open research question.

Ablation Studies and Robustness Checks

PRM vs. ORM aggregation strategy (Appendix E, Figure 13): Not applicable to this paper—these ablations belong to the reference example paper on test-time compute scaling, not to the cooperative game theory paper. The core paper does not include reward model ablations, beam search comparisons, sequence model evaluations, or any of the other ablations described in the reference example.

The actual ablations and robustness checks present in this paper are:

Learning rate sensitivity on graph games (Appendix B.1, Figure 5): The Core Lagrangian method is run with three learning rate schedules on Newman-Watts-Strogatz weighted graph games—the base learning rate, 1.5× the base rate, and 0.2× the base rate (where the schedule is linear decay from 2×LR to 0.1×LR over 1,000 steps, with base LR = 0.5). The 1.5× learning rate variant performs worse than the base rate across the full time range, while the 0.2× variant's performance is shown but not discussed in detail. The LP method outperforms all CL variants on this game class, demonstrating that the CL's advantage is not universal and that hyperparameter tuning matters.

Change of variables for Adam optimization (Section 4.2 onward, Table 2): For all experiments beyond the runtime comparison, the paper replaces the mirror prox update with a softmax reparameterization—treating the payoff vector as 𝑝 = softmax(𝑠) where 𝑠 ∈ ℝⁿ is unconstrained logits—and applying the Adam optimizer. This is compared to the original mirror prox formulation implicitly (the runtime experiment uses mirror prox with the linear schedule from Table 1, while the stability and XAI experiments use the Adam variant from Table 2). No direct comparison of mirror prox vs. Adam is provided, so this is a methodological change without an ablation study quantifying its impact. The theoretical convergence guarantee (Theorem 4, O(1/√𝑇) rate) applies only to the mirror prox formulation, not the Adam variant—the paper acknowledges this implicitly by separating the hyperparameter tables but does not discuss whether the empirical gains from Adam come at the cost of lost convergence guarantees.

Constraint violation threshold 𝛾 (Tables 1 and 2): The paper uses 𝛾 = 0.001 for the runtime experiment (Table 1) and 𝛾 = 0.01 for all other experiments (Table 2)—an order-of-magnitude difference in the permitted total constraint violation. No ablation over 𝛾 values is presented. Section 3.3 establishes that 𝛾 > 0 is needed to satisfy Slater's condition for the saddle-point formulation, but the practical impact of varying 𝛾 on approximation quality or convergence speed is unexplored.

Batch size (Tables 1 and 2): The runtime experiment uses batch size 𝐵 = 100; all other experiments use 𝐵 = 1,000. The scaling of approximation quality with batch size is not ablated. The paper's GPU/TPU acceleration strategy (Appendix A.2) emphasizes that large batch sizes are the key to leveraging hardware parallelism, but no experiments demonstrate how batch size affects wall-clock convergence.

Coalition sampling strategy: All experiments sample coalitions uniformly at random from the power set of players. The paper does not ablate alternative sampling strategies—importance sampling (biasing toward coalitions likely to be binding constraints), stratified sampling (ensuring coverage across coalition sizes), or adaptive sampling (focusing on coalitions with historically high deficits). This is a significant unexplored dimension given that the convergence rate depends on the variance of the stochastic gradient estimates, which is directly affected by the sampling distribution.

Number of iterations: All experiments use 𝑇 = 10,000 iterations (Tables 1 and 2). The paper does not ablate over 𝑇 to show where convergence saturates, nor does it report the computational cost per iteration in FLOPs or wall-clock time (except for the runtime comparison in Figure 2, which uses elapsed time directly). This makes it difficult to assess whether the chosen 𝑇 is sufficient for convergence or whether additional iterations would yield further improvements.

Initialization sensitivity: 𝑝₀ is always initialized to the uniform imputation (equal shares). No ablation over alternative initializations (e.g., Shapley value as a warm start, payoff-proportional-to-standalone-value, or random initializations) is presented. Given that the saddle-point problem is convex-concave, initialization should not affect the fixed point asymptotically, but it may affect the rate of convergence in practice.

Oracle vs. approximate epsilon evaluation: The approximate epsilon ˆ𝜖 used to evaluate solution quality (Figure 2) is computed over 50,000 randomly sampled coalitions—not the full 2¹⁰⁰ coalitions. The paper does not quantify how well this 50,000-coalition estimate approximates the true maximum deficit over all coalitions. For 100-player games, 50,000 is a tiny fraction of 2¹⁰⁰, and the quality of this approximation likely degrades as the true least-core value decreases (since the binding constraints become sparser). This is a potential source of optimistic bias in the reported approximation quality.

Critical Assessment

Claim 1 (from the executive summary): Core Lagrangian "scales better to very large problems" and "outperforms a recent LP-based sampling approach in wall-clock time on 100-player weighted voting games."

This claim is supported by Figure 2 for the specific setting tested: 100-player weighted voting games with uniform random weights and quotas in [0.1, 0.9]. The Core Lagrangian method achieves lower approximate epsilon at equal wall-clock time across the full tested range (5–125 seconds). However, the experimental support is narrower than the claim suggests. The evidence comprises a single game class (weighted voting games), a single player count (𝑛 = 100), and a specific range of quota parameters. Figure 5 (Appendix B.1) on Newman-Watts-Strogatz graph games shows the opposite pattern—the LP method outperforms CL—which directly contradicts the universality of the "scales better" claim. The paper acknowledges this (the LP method "suggesting it is important keep both approaches in mind when attempting to solve new problem domains") but does not temper the abstract's stronger language. The "very large problems" claim is supported at 𝑛 = 100 but not at larger scales—there is no experiment with 𝑛 = 500 or 𝑛 = 1,000 to demonstrate continued scaling.

Furthermore, the CL advantage is measured in wall-clock time, which conflates algorithmic efficiency with implementation quality. The LP method uses CVXPY (a general-purpose convex optimization library in Python), while CL uses JAX (a high-performance numerical computing framework with GPU acceleration). The paper's own Appendix A.2 describes how CL's core operation maps directly onto a highly optimized matrix-vector product + ReLU—exactly the computation that GPUs/TPUs are designed to accelerate. The LP method receives no such acceleration. The wall-clock comparison therefore partially measures implementation quality and hardware utilization, not purely algorithmic efficiency. A FLOPs-matched comparison (analogous to the reference paper's Section 7) would control for this, but is not provided.

Claim 2 (from the executive summary): "In XAI data valuation experiments, the least core identifies training data points whose removal degrades model performance more sharply than Shapley value-based selection."

This claim is supported by Figure 4a (Boston Housing) and Figure 4b (Breast Cancer), where the core-based removal curve lies below the Shapley-based curve for most removal percentages. However, the magnitude of the advantage is modest—approximately 0.03–0.04 in 𝑅² on Boston Housing and approximately 0.005–0.01 in accuracy on Breast Cancer—and the error bars (95% CI from 1,000 repeats) overlap substantially, particularly on Breast Cancer. The Wine and Diabetes datasets (Appendix D.2, Figure 10) provide additional supporting evidence, though with the caveat that the trend can reverse at very high removal percentages.

The critical limitation is that the paper does not demonstrate statistical significance of the core-Shapley gap. Error bars are shown, but no hypothesis test or confidence interval for the difference is reported. Given the overlapping confidence intervals on Breast Cancer, it is plausible that the observed gap is consistent with sampling noise. On Boston Housing, the separation is clearer but still modest relative to the variance.

More importantly, the claim is qualified by the Chatbot Arena counterexample (Figure 4c), where Shapley-based selection clearly outperforms core-based selection. The paper's framing correctly includes this as evidence of task-dependence, but the abstract and introduction emphasize the core's advantages without equivalently highlighting this reversal. A reader who only reads the abstract would not learn that the Shapley value can be superior for data valuation.

The data valuation experiments also suffer from a missing baseline: random removal. Without showing that both Shapley and core-based removal degrade performance more than random removal, it is unclear whether either method is actually identifying important data points (as opposed to both methods being equally noisy). A random-removal curve would anchor the interpretation—if both Shapley and core lie well below random, both are informative; if both overlap with random, neither is useful. This baseline is absent.

Claim 3 (from the executive summary): The core provides "a compelling alternative to Shapley values for feature attribution and data valuation."

The feature attribution experiments (Figure 3) show positive correlation between Shapley and core importance measures—but this is the weakest form of evidence for the core being an "alternative." Positive correlation means the two methods largely agree, so replacing one with the other would not substantially change feature rankings. The interesting case is when they disagree, and the paper does not analyze these disagreements systematically. Which features receive high core payoffs but low Shapley values (or vice versa)? Are these features that interact non-additively, are collinear with other features, or have some other structural property? Without such analysis, the "alternative" claim reduces to "the core produces different numbers that sometimes correlate with Shapley values."

The local explainability results (Section 5.2, Figure 3 contour plots) are particularly underanalyzed. With 𝑑·𝑓 individual feature-importance pairs per dataset, the paper could have examined whether core-Shapley disagreements cluster in specific instances (e.g., instances near decision boundaries, instances with unusual feature combinations) or specific features (e.g., features with skewed distributions, features known to interact). Instead, only aggregate contour plots are shown, from which no substantive conclusions about when the core provides different or better explanations can be drawn.

Claim 4 (from the paper): "empirical analysis can only be carried out when using algorithms for tractably solving cooperative games at scale, such as the algorithms we have proposed." (Section 4.2.2, closing sentence)

This is a methodological claim about the necessity of scalable solvers for the kind of parameter sweep analysis conducted in Section 4.2. It is directionally true—without a fast solver, generating least-core values for thousands of game instances across dozens of parameter configurations would be infeasible. However, the claim is somewhat self-serving: the Yan and Procaccia (2021) LP-based method could also have been used for such sweeps, particularly at the modest game sizes used in Section 4.2 (𝑛 = 15 for weighted voting games, 𝑛 = 32 for graph games). The LP method's feasibility at these sizes is not tested—the runtime comparison uses 𝑛 = 100, not 𝑛 = 15—so the claim that only CL can enable such analysis is unsubstantiated. The LP method may be perfectly adequate for 𝑛 = 15, where 2¹⁵ = 32,768 coalitions is a manageable LP size.

Missing experiments that would strengthen the paper:

Comparison against the exact least-core for small games. At 𝑛 ≤ 15, the exact LP with all 2ⁿ constraints is solvable. Comparing Shapley, CL, and the exact least-core on such small games would establish ground-truth accuracy for all methods and quantify the approximation error as a function of game parameters. This is a standard validation approach that is conspicuously absent.
FLOPs or characteristic-function-calls accounting. The runtime comparison uses wall-clock time, conflating algorithmic and implementation efficiency. Counting characteristic function evaluations (how many coalition values are computed) would provide an implementation-independent metric. CL uses 𝑇 × 𝐵 evaluations; the LP method uses one evaluation per constraint. A proper accounting would reveal the sample complexity of each approach.
Scaling with 𝑛 experiments. The paper demonstrates CL on 𝑛 = 100 (runtime comparison), 𝑛 = 15 (weighted voting stability), 𝑛 = 32 (graph games), and 𝑛 = 10 (MCNs). There is no systematic experiment varying 𝑛 to show how approximation quality or runtime scales with player count. This is the most natural experiment for a paper claiming "greater scaling potential to very large problems."
Ablation over 𝛾 and convergence diagnostics. The constraint violation threshold 𝛾 is a critical hyperparameter that controls the tightness of the saddle-point approximation. No ablation over 𝛾 is provided, nor are convergence diagnostics (e.g., the duality gap over iterations, the distribution of constraint violations at convergence) reported. This makes it impossible to assess whether the algorithm is converging to the true saddle point or to an approximation biased by the choice of 𝛾.
Multiple runs with different random seeds. The stability analyses (Figures 1, 6, 8) report means over game instances but do not report variance across different random seeds for the CL algorithm itself on the same game instance. The stochastic nature of minibatch sampling means that different runs on the same game may converge to different solutions (since the least-core may contain multiple imputations). Reporting within-instance variance would quantify this source of noise.

Summary of experimental strengths:

The Figure 2 runtime comparison provides compelling evidence that stochastic optimization methods can be competitive with LP-based approaches for core approximation, and the anytime property (continued improvement with time) is a genuine practical advantage. The stability heatmaps (Figures 1, 6) are a novel empirical contribution that demonstrates the analytical value of having a fast core solver—they reveal parameter-dependent patterns in cooperative game stability that would be difficult to discover through purely theoretical analysis. The Chatbot Arena data valuation result (Figure 4c) is the most scientifically valuable finding in the paper because it complicates the prevailing narrative of core superiority and opens a productive research question about task-dependence that the paper's own earlier framing (building on Yan and Procaccia) might have closed off.

Summary of experimental weaknesses:

The paper makes stronger universality claims than the experiments support, particularly regarding CL's superiority over LP methods (contradicted by Figure 5) and the core's advantages over Shapley for XAI (qualified by Figure 4c and unsupported by formal statistical tests). The absence of exact-solution validation on small games, systematic scaling experiments with 𝑛, ablation studies over key hyperparameters (𝛾, batch size, learning rate schedule), and multiple-random-seed variance analysis collectively limit the confidence with which the empirical results can be interpreted. The data valuation experiments lack a random-removal baseline that would contextualize the magnitude of the Shapley and core effects. The feature importance experiments (Figure 3) are reported at too coarse a level of aggregation to support meaningful conclusions about when and why Shapley and core differ.

6. Limitations and Trade-offs

Hyperparameter Sensitivity with No Systematic Ablation

The Core Lagrangian (CL) method introduces several critical hyperparameters that control the approximation quality–convergence tradeoff, yet the paper provides no systematic ablation over any of them. The constraint violation threshold γ — which determines the tightness of the saddle-point approximation to the true least-core — takes values that differ by an order of magnitude across experiments: γ = 0.001 for the runtime comparison (Table 1) versus γ = 0.01 for all stability and XAI experiments (Table 2). The paper establishes in Section 3.3 that γ > 0 is needed to satisfy Slater's condition for the saddle-point formulation, but never demonstrates how varying γ affects either the quality of the returned imputation or the convergence speed. Similarly, the batch size B changes from 100 to 1,000 between experiments with no ablation, the Lagrange multiplier initial value μ₀ = 1,000 is fixed throughout, and the learning rate schedule — linear decay from 0.1 to 0.01 over 1,000 steps in the runtime experiment versus constant 0.1 with Adam elsewhere — represents a fundamental algorithmic change (mirror prox vs. Adam) whose impact on solution quality is never measured.

The consequence is that a practitioner cannot determine appropriate hyperparameter settings for a new game class without trial-and-error experimentation. Worse, the paper provides no diagnostic metrics (e.g., convergence of the duality gap, distribution of per-coalition deficits at termination) that would allow a user to detect when the chosen hyperparameters are producing poor approximations. The Appendix B.1 experiment (Figure 5) provides the only direct evidence of sensitivity: on Newman-Watts-Strogatz graph games, varying the learning rate by factors of 0.2× and 1.5× produces meaningfully different CL performance, and even the best CL configuration is outperformed by the LP baseline — a reversal of the Figure 2 result that the paper's headline claims do not temper.

The paper partially acknowledges the sensitivity implicitly by changing the hyperparameter table between experiments, but never discusses the choice, never ablates over the parameters, and provides no guidance for hyperparameter selection on new problems. The theoretical convergence guarantee (Theorem 4, O(1/√T) rate) applies only to the mirror prox variant with specific step-size schedules, not to the Adam variant used in the bulk of experiments. This means the empirical results demonstrating CL's practical value are obtained with an optimizer for which no convergence theory is provided, while the algorithm for which theory exists is never evaluated beyond Figure 2.

Advantage Over LP Baseline Is Confined to Specific Game Classes

The paper's primary empirical claim — that Core Lagrangian "outperforms a recent LP-based sampling approach in wall-clock time on 100-player weighted voting games" (Section 4.1) — is directly contradicted by the paper's own evidence on other game classes. Figure 5 (Appendix B.1) shows that on Newman-Watts-Strogatz weighted graph games, the LP method outperforms CL across the full time range, with LP achieving ϵ̂ ≈ 4.2 at 100 seconds versus CL at approximately 4.8. Two additional CL runs with scaled learning rates do not close the gap. The paper acknowledges this briefly — "suggesting it is important keep both approaches in mind when attempting to solve new problem domains" — but this qualification appears only in Appendix B.1, not in the main text or abstract where the superiority claims are made.

The consequence is that a practitioner choosing between CL and the LP baseline for a new cooperative game cannot rely on the paper to predict which method will perform better. The evidence establishes that CL wins on weighted voting games (Figure 2) but loses on at least one class of graph games (Figure 5). The structural properties that determine which method dominates are not characterized. Is it the distribution of coalition values? The sparsity pattern of binding constraints? The ratio of core size to player count? Without such a characterization, method selection requires running both algorithms and comparing — negating the practical advantage that CL is supposed to provide.

The paper conducts the runtime comparison on only two game classes (weighted voting in Section 4.1, weighted graph in Appendix B.1) and only at n = 100. The stability analyses (Section 4.2) and XAI experiments (Section 5) use CL exclusively, with no comparison to the LP baseline. This means the paper's positive evidence for CL comes from a narrow slice of the problem space — weighted voting games with uniform random weights — while the majority of the paper's claimed applications (graph games, MCNs, XAI datasets) are evaluated with no baseline comparison at all.

Mitigation is minimal: the paper suggests in Appendix B.1 that both approaches should be "kept in mind," but provides no guidance for predicting which will dominate on a given problem class. The limitation is structural — the two methods optimize differently (saddle-point search vs. constraint sampling + global LP solve), and their relative performance likely depends on properties of the characteristic function that the paper does not analyze.

XAI Conclusions Lack Statistical Rigor and Baseline Anchoring

The data valuation experiments (Section 5.3, Figure 4) report that removing core-identified data points degrades model performance more than removing Shapley-identified data on Boston Housing and Breast Cancer, with the reverse pattern on Chatbot Arena. However, the paper never establishes whether either method outperforms random data removal. Without this baseline, a reader cannot determine whether the observed performance degradation is due to the methods identifying genuinely important data points or simply reflects the inherent sensitivity of model performance to any data removal. If removing random subsets of data produced similar degradation curves, then neither Shapley nor core-based valuation would be demonstrably informative.

Furthermore, the paper reports no statistical tests for the difference between Shapley-based and core-based removal curves. Figure 4 shows error bars (95% confidence intervals from 1,000 repeats), but these represent the variance of each method individually, not the variance of the difference between methods. On Breast Cancer (Figure 4b), the error bars overlap substantially across the full range of removal percentages — the separation between curves is approximately 0.005–0.01 in accuracy, with error bars spanning roughly ±0.005. A paired test of the difference at each removal percentage would likely show the gap is not statistically significant at conventional thresholds. On Boston Housing (Figure 4a), the separation is larger (approximately 0.03–0.04 in R²) and error bars overlap less, making statistical significance more plausible — but it is never demonstrated.

The consequence is that the paper's central XAI claim — "the least core identifies training data points whose removal degrades model performance more sharply than Shapley value-based selection" — overstates the strength of the evidence. A practitioner reading the paper cannot distinguish between (a) a genuine, replicable advantage of the core for data valuation on tabular datasets and (b) noise-driven differences between two imperfect importance measures, both of which may be only marginally better than random. The Chatbot Arena reversal (Figure 4c), where Shapley clearly dominates, is the most statistically convincing result because the separation is large relative to the error bars — but the other datasets show effects that are directionally consistent with prior work (Yan and Procaccia, 2021) yet individually unconvincing.

The paper does not acknowledge the absence of random-removal baselines or statistical tests as limitations. These are standard methodological practices in the data valuation literature that the paper omits without comment.

Difficulty Estimation Cost Unaccounted for in Headline Efficiency

The paper's practical deployment implicitly requires computing the characteristic function v(C) for every coalition sampled during CL iterations. For the stability analysis experiments (Section 4.2), v(C) has a closed form (e.g., weighted voting games check if total weight exceeds a quota; graph games sum edge weights within the coalition). However, for the XAI data valuation experiments (Section 5.3), each call to v(C) involves retraining a machine learning model from scratch on the subset of training data defined by coalition C and evaluating it on a held-out test set. The paper imposes a budget of 50,000 characteristic function calls for both Shapley and CL methods. CL uses T = 10,000 iterations with batch size B = 1,000 (Table 2), which would nominally require 10 million coalition evaluations — far exceeding the stated budget.

The paper resolves this discrepancy by noting that the budget constraint is applied to the number of model retrainings: "we imposed a budget of 50,000 calls to the characteristic function, limiting the number of permutations sampled for the Shapley value approximation and iterations for our least-core algorithm, CL." This implies that CL is run with a substantially reduced number of iterations or batch size to stay within the budget, but the paper does not report the actual hyperparameters used under the budget constraint. The stated hyperparameters (Table 2: T = 10,000, B = 1,000) would consume the budget 200 times over if each sampled coalition required a fresh retraining.

The consequence is that the reported XAI data valuation results are not reproducible from the hyperparameters in the paper. A practitioner attempting to replicate the experiments cannot determine the actual (T, B) configuration used under the 50,000-call budget, nor whether CL converges adequately at the reduced iteration count. More fundamentally, the computational cost of XAI applications — where each v(C) call involves model training — dominates wall-clock time regardless of whether CL or the LP method is used. This means the algorithmic speed advantage demonstrated in Figure 2 (which assumes v(C) is cheap to evaluate) may be irrelevant for the XAI use case that the paper presents as a primary motivation.

The paper does not acknowledge this discrepancy, does not report the effective hyperparameters under the budget constraint, and does not discuss the runtime of characteristic function evaluations relative to optimization time in the XAI setting. This makes it impossible to assess whether CL's optimization efficiency translates to practical gains when v(C) evaluations are the dominant cost.

No Dynamic or Adaptive Difficulty Estimation; Fixed Iteration Budget

The CL algorithm runs for a fixed number of iterations T = 10,000 with a predetermined learning rate schedule and no mechanism for early stopping or adaptive budget allocation. The paper provides no convergence diagnostics — the duality gap over time, the distribution of per-coalition deficits, or the stability of the imputation across recent iterations — that would allow a user to determine whether the algorithm has converged or whether more iterations are needed. In the XAI data valuation experiments, the effective T is reduced to fit the 50,000-call budget, but the paper does not report whether this reduced iteration count is sufficient for convergence.

The consequence is that a practitioner cannot determine the appropriate computational budget for a new problem. Running too few iterations may produce a poor approximation (high ϵ̂, imputation far from the least-core). Running too many iterations wastes computation without improving solution quality. The fixed 10,000-iteration budget is a one-size-fits-all choice that the paper never validates — no experiment shows that 10,000 iterations is sufficient for the problem sizes and game classes tested, nor that fewer iterations would produce equally good solutions.

The paper's Theorem 4 guarantees an O(1/√T) convergence rate for the duality gap, but this asymptotic rate provides no guidance on the constant — how many iterations are needed to achieve a target approximation quality on a specific game. The absence of convergence diagnostics means the paper cannot distinguish between (a) CL converging to a high-quality solution and (b) CL plateauing at a suboptimal point due to, e.g., the choice of γ, the learning rate schedule, or insufficient iterations.

This limitation is particularly acute for the stability heatmap experiments (Section 4.2, Figures 1, 6), where 10,000 game instances are evaluated. If some fraction of these instances fail to converge adequately within 10,000 iterations, the reported average least-core values would be biased by unconverged solutions, and the heatmap patterns could partially reflect convergence artifacts rather than genuine game-theoretic stability properties. The paper does not report convergence diagnostics for any experiment, making this risk unquantifiable.

The paper does not discuss this limitation. It suggests in Section 8 that future work could develop "cheap difficulty estimation" — a concept analogous to the test-time compute paper's difficulty bins — but provides no adaptive mechanism within the current algorithm and reports no diagnostic metrics that would enable a user to assess convergence in practice.

Combined Search and Revision Methods Not Evaluated Despite Complementary Strengths

The paper studies two algorithm families — iterative projections (Algorithm 1), stochastic subgradient descent (Algorithm 2), and the Core Lagrangian (Algorithm 4) — and presents them as a progression of increasing sophistication. However, the paper never evaluates a hybrid approach that combines these methods. For instance, one could use Algorithm 1 or 2 (with a fixed ϵ) as a warm-start initialization for Algorithm 4, providing the saddle-point optimization with an imputation that already approximately satisfies the constraints at some relaxation level, potentially accelerating convergence. Alternatively, one could periodically run a few iterations of Algorithm 1 within the Algorithm 4 loop to correct large deficits for specific coalitions that the stochastic minibatch sampling may miss.

The consequence is that the paper's reported performance for CL represents a lower bound on what a combined approach might achieve, but the reader cannot determine how much headroom remains. More importantly, the paper never investigates whether the projection-based methods (Algorithms 1–2) could serve as an effective fallback when CL fails to converge adequately — a scenario suggested by the Appendix B.1 result where CL underperforms the LP baseline on graph games. If Algorithm 1 could achieve better approximations than CL on some game classes (at higher per-iteration cost), a hybrid algorithm that switches between methods based on convergence diagnostics could dominate either approach alone.

The paper does not acknowledge this as a limitation or suggest combining the methods as future work. The three algorithms are presented as a narrative progression (projections → SGD → saddle-point), not as complementary tools that could be composed. This is a missed opportunity, particularly given that the paper's own evidence (Figure 5) shows CL is not uniformly superior, making fallback mechanisms practically relevant.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper makes a methodological contribution of moderate but genuine significance: it demonstrates that the least-core of a cooperative game—long considered computationally inaccessible without solving linear programs—can be approximated via stochastic saddle-point optimization, eliminating the LP bottleneck that had defined the field's approach to core computation since its inception. This is not a paradigm shift in cooperative game theory itself (the core remains the core; the least-core remains the least-core), but it is a paradigm shift in how we compute these solution concepts, analogous to how stochastic gradient descent transformed empirical risk minimization from batch optimization to streaming algorithms.

The shift is from sample-then-optimize (collect coalition constraints, build and solve an LP) to optimize-while-sampling (interleave coalition sampling with gradient updates, converging to a solution without ever constructing the full constraint set). This moves core computation from the domain of mathematical programming (LP solvers, constraint generation) into the domain of large-scale stochastic optimization (SGD, mirror prox, Adam, GPU acceleration)—a transition that carries practical consequences the paper demonstrates concretely: the ability to process minibatches of coalitions on GPU/TPU hardware (Appendix A.2), the "anytime" property where solution quality improves continuously with runtime rather than jumping at discrete LP solves (Figure 2), and the scalability to analyze thousands of game instances in parameter sweeps that would be impractical with LP-based methods (Section 4.2).

The paper reconciles no direct contradiction in prior work—the computational hardness of the core was well-established (Deng and Papadimitriou, 1994; Balkanski, Syed, and Vassilvitskii, 2017), and Yan and Procaccia (2021) had already provided a practical sampling-based approximation. However, the paper complicates a narrative that was beginning to form around Yan and Procaccia's findings: the idea that the core is simply a better data valuation method than the Shapley value. By showing that Shapley-based selection outperforms core-based selection on the Chatbot Arena Elo-rating task (Figure 4c), the paper redirects the conversation from "which method is better?" to "under what structural conditions is each method more appropriate?"—a more productive and less adversarial framing.

The paper also makes several research directions more attractive:

Empirical analysis of cooperative game stability at scale is now feasible. The heatmaps in Figures 1 and 6 demonstrate that parameter sweeps over thousands of game instances can reveal stability phase transitions and non-monotonic patterns that would be difficult to discover through purely theoretical analysis. This opens the door to a more data-driven style of cooperative game theory research.
Hardware-accelerated game-theoretic computation becomes a practical reality. The paper's mapping of coalition constraint checking onto a matrix-vector product plus ReLU (Appendix A.2) means core computation can leverage the same GPU/TPU infrastructure that drives modern deep learning. This lowers the barrier for game-theoretic methods to be integrated into ML pipelines that already run on accelerators.
Saddle-point reformulations of other intractable game-theoretic problems become a natural direction to explore. If the least-core (with 2ⁿ constraints) can be reformulated as a convex-concave saddle point, what other solution concepts admit similar treatment? The nucleolus? The Shapley value itself? The kernel? The paper provides a template.

Conversely, the paper makes some research directions less attractive:

Developing increasingly sophisticated LP-based constraint generation schemes for the core becomes harder to justify. The paper shows that a simple stochastic method can match or exceed LP-based approaches on a canonical benchmark (Figure 2), and the anytime property provides a practical advantage that constraint-generation methods lack. Research effort is better directed at improving stochastic optimization for game theory than at engineering more elaborate LP formulations.
Claiming universal superiority of one data valuation method over another should become less common. The Chatbot Arena result (Figure 4c) provides a clear counterexample to the narrative that the core dominates Shapley for data valuation. Future work should characterize when each method excels rather than seeking a single winner.

Follow-Up Research This Work Enables

Characterizing the structural properties that determine CL vs. LP superiority. The paper provides two conflicting results: CL outperforms the LP method on weighted voting games (Figure 2) but underperforms on Newman-Watts-Strogatz graph games (Figure 5). A systematic follow-up would generate instances across multiple game classes with controlled variation along axes hypothesized to matter—coalition value distribution (binary vs. continuous), constraint sparsity (fraction of coalitions that are binding), and player count—and identify the conditions under which each method dominates. The experiment would measure both wall-clock time and number of characteristic function calls to convergence, using the exact least-core (computed via full LP at small n) as ground truth to quantify approximation error for both methods. This would convert the paper's anecdotal observation into a decision rule for practitioners.

Dynamic convergence diagnostics and adaptive budget allocation for CL. The paper runs CL for a fixed 10,000 iterations with no mechanism for early stopping or adaptive step sizing. A natural extension would instrument CL with convergence diagnostics—tracking the duality gap over iterations, monitoring the distribution of per-coalition deficits, and computing the effective rank of recent imputation updates—and use these to implement adaptive stopping (halt when the duality gap stabilizes below a threshold) and adaptive step-size adjustment (increase the learning rate when progress stalls, decrease when the imputation oscillates). A strong follow-up would demonstrate that adaptive CL matches or exceeds the performance of fixed-budget CL while using substantially fewer iterations on average, and would characterize the false-early-stopping rate (fraction of runs where the adaptive method stops before reaching a solution of acceptable quality). The evaluation would use the exact least-core on small games (n ≤ 15) to provide ground-truth stopping criteria.

Importance sampling over coalitions to reduce gradient variance. The paper samples coalitions uniformly at random from the power set, but not all coalitions are equally informative. Coalitions that are already satisfied (d_C = 0) contribute zero gradient, while coalitions with large deficits drive the updates. A follow-up could design an importance sampling distribution that oversamples coalitions likely to be binding constraints—for instance, using the current imputation to estimate which coalitions have high probability of violation, or maintaining a running estimate of per-coalition deficit variance. The key metric would be the variance of the stochastic gradient estimate at a given batch size, compared against uniform sampling. A successful importance sampler would achieve the same approximation quality with smaller batch sizes or fewer iterations, directly improving the efficiency of the Core Lagrangian method. The challenge is that the proposal distribution must be cheap to sample from (otherwise the importance sampling overhead dominates), which likely requires a parametric approximation to the coalition value structure.

Warm-starting the Core Lagrangian with Shapley value estimates. The two solution concepts capture different structural properties of cooperative games—the Shapley value averages marginal contributions, while the core focuses on stability—but they often produce positively correlated importance rankings (Figure 3). A practical follow-up would initialize CL with the Shapley value (computed via Monte Carlo permutation sampling, which is cheap relative to CL iterations in the XAI setting where each v(C) call requires model retraining) and measure whether this warm start reduces the number of CL iterations needed to converge to a high-quality least-core approximation. The experiment would compare CL with random initialization, uniform initialization (the paper's default), and Shapley initialization across the XAI datasets used in Section 5, under a fixed budget of characteristic function calls. The hypothesis is that Shapley initialization places the imputation closer to the least-core region, reducing the number of constraint-violating coalitions that must be corrected. A negative result—Shapley initialization providing no benefit—would be informative in its own right, indicating that the stability and marginal-contribution perspectives are sufficiently different that proximity in one does not imply proximity in the other.

Evaluating CL on cooperative games where the characteristic function is a deep neural network. The XAI experiments in Section 5 use simple linear/logistic regression models as the characteristic function (coalition value = model quality when trained on that subset of features or data). A natural and important stress test would replace these with modern deep learning models—e.g., a ResNet trained on CIFAR-10 subsets for data valuation, or a transformer trained on language modeling data. In this regime, each call to v(C) involves training a neural network, making the characteristic function evaluation cost dominate the optimization cost entirely. The research question is whether CL can produce useful least-core approximations within a severely limited budget (e.g., 1,000–5,000 model trainings) that is realistic for deep learning settings. This would also test whether the core-Shapley differences observed on tabular data (Section 5.3) persist or reverse when the underlying model is highly overparameterized, which may change the structure of coalitional interactions among data points.

Extending the saddle-point formulation to other cooperative solution concepts. The paper's reformulation of the least-core as a convex-concave saddle point is specific to the core's structure (linear constraints, convex objective), but the template of converting an intractable constrained optimization into a stochastic saddle-point problem may generalize. A natural target is the nucleolus—a refinement of the core that lexicographically minimizes the maximum excess (or equivalently, minimizes the largest deficit, then the second-largest, etc.). The nucleolus has an LP-based computation that is even more expensive than the least-core because it requires solving a sequence of LPs. Reformulating the nucleolus as a saddle-point problem (perhaps by introducing nested Lagrange multipliers for each lexicographic level) would be a challenging theoretical contribution that builds directly on this paper's framework. A less ambitious but valuable target is the Shapley value itself, which can be expressed as the solution to a least-squares problem over permutations—potentially amenable to stochastic optimization over sampled permutations rather than the standard Monte Carlo averaging approach.

Practical Applications and Downstream Use Cases

Data valuation for machine learning training pipelines. The most directly actionable application from the paper is using the Core Lagrangian method to identify training data points whose removal most degrades model performance, enabling data pruning (removing low-importance points to reduce training cost) or data debugging (inspecting high-importance points for labeling errors or bias). The paper's Figure 4a shows that on Boston Housing, removing the top 10% of core-identified data points drops model R² from approximately 0.68 to 0.58—a degradation of roughly 0.10 in R²—while the same fraction of Shapley-identified removal drops performance to approximately 0.62. A practitioner with a 50,000-call budget for characteristic function evaluations could use CL to rank their training data, then make informed decisions about data collection priorities or subset selection for expensive downstream processing (e.g., manual labeling, expert review). The Chatbot Arena result (Figure 4c) adds an important caveat: for pairwise comparison or ranking tasks where the cooperative structure may be more additive, Shapley-based valuation may be more appropriate. The practitioner should therefore run both methods under the same budget and compare the removal curves, as the paper does, rather than defaulting to either method.

Feature importance analysis as a complement to SHAP in regulated ML deployments. In settings where model explanations must be provided to end users or regulators (e.g., credit scoring, medical diagnosis), the core provides a stability-based perspective on feature importance that differs from the Shapley value's average-marginal-contribution perspective. The paper's Figure 3 shows that while Shapley and core importance measures are positively correlated, they produce different feature rankings—particularly on datasets where no single feature dominates (Breast Cancer, Figure 3c). A deployment could report both Shapley and core-based feature attributions, using the Shapley value for its axiomatic properties (efficiency, symmetry, null player) and the core for its stability interpretation (no coalition of features is undercompensated relative to its predictive contribution). The computational cost is manageable: the paper processes all XAI datasets within a 50,000-call budget, which for tabular data with simple models is a matter of seconds to minutes. The key practical benefit is that disagreements between Shapley and core rankings flag features whose importance is sensitive to the solution concept, providing a more nuanced explanation than either method alone.

Analyzing stability of coalition structures in multi-agent systems and mechanism design. For researchers and practitioners designing multi-agent systems where coalition formation is possible—distributed resource allocation, federated learning with agent dropouts, computational resource sharing in data centers—the Core Lagrangian method enables efficient analysis of how different system parameters affect the stability of the grand coalition. The paper's weighted voting game heatmaps (Figure 1a–c) demonstrate this use case directly: by varying agent weight distributions and quota thresholds, a designer can identify parameter regimes where the core is nearly empty (high least-core value) versus where stable payoff divisions exist (low least-core value). In a federated learning setting where agents contribute data of varying quality and quantity, a designer could use CL to compute whether the proposed reward allocation—payments or model access proportional to contribution—lies in the core, and if not, how large the subsidy would need to be (the least-core value) to prevent agent defection to smaller coalitions. The n = 100 scale demonstrated in Figure 2 is directly relevant to realistic federated learning deployments with dozens to hundreds of participants.

Core-based pricing in combinatorial auctions with many bidders. The core has been used to select payment rules in package auctions (Day and Milgrom, 2008; Day and Cramton, 2012) because core-selecting payments ensure that no coalition of bidders has incentive to collude and undermine the auction outcome. The computational bottleneck has been solving the core constraints for auctions with many bidders and many items (where the number of possible bidder coalitions grows exponentially). The Core Lagrangian method scales to n = 100 on weighted voting games (a simplified but structurally related problem) and can leverage GPU acceleration for the constraint-checking operation. A practical auction system could deploy CL as the payment computation engine, running the saddle-point optimization after bids are collected to determine payments that are approximately core-selecting, with the anytime property allowing a hard real-time deadline (stop after T seconds and use the best solution found). The key open question—not addressed by this paper—is whether CL's approximation quality on auction-specific characteristic functions (which have the structure of winners' values minus payments) matches its performance on the weighted voting games tested.

When to Prefer This Method

The paper positions the Core Lagrangian method against two alternatives: the Yan and Procaccia (2021) sampling-based LP method for core approximation, and the Shapley value for XAI importance measurement. The tradeoffs are:

Prefer the Core Lagrangian method over the sampling-based LP when: (i) the characteristic function is cheap to evaluate, so many iterations can be run quickly (the "anytime" property in Figure 2 provides continuous improvement); (ii) the game is large enough that solving even a sampled LP becomes the bottleneck (n > 50, where the LP constraint matrix grows with the number of sampled coalitions k); (iii) GPU/TPU hardware is available, since CL's core operation maps directly onto optimized matrix-vector product kernels (Appendix A.2); (iv) the game class is similar to weighted voting games—the evidence for CL's advantage is strongest here (Figure 2) and weakest or reversed on certain graph games (Figure 5).
Prefer the sampling-based LP method over CL when: (i) the game structure resembles Newman-Watts-Strogatz weighted graph games, where Figure 5 shows LP outperforming CL; (ii) a small number of high-precision solutions is needed (e.g., n < 30 where the exact LP is solvable), since the LP method provides a deterministic solution for a given set of sampled constraints rather than a stochastic approximation; (iii) the hyperparameter sensitivity of CL (learning rate, batch size, γ, choice between mirror prox and Adam) cannot be tuned due to limited computational budget for trial runs.
Prefer the least-core over the Shapley value for data valuation when: (i) the task involves identifying synergistic data subsets whose joint presence matters more than individual contributions—the core's stability focus naturally captures this; (ii) the deployment context requires a "market value" or "outside option" interpretation of data importance (what payment would prevent a data provider from defecting?); (iii) the Yan and Procaccia (2021) result (core outperforms Shapley on standard tabular data valuation benchmarks) needs to be replicated with a more scalable solver. The Boston Housing (Figure 4a), Breast Cancer (Figure 4b), Wine (Figure 10a), and Diabetes (Figure 10b) datasets all show this pattern directionally, though with modest effect sizes.
Prefer the Shapley value over the least-core for data valuation when: (i) the task involves learning from pairwise comparisons or ranking data, as in the Chatbot Arena Elo-rating experiment (Figure 4c) where Shapley-based removal causes steeper performance degradation; (ii) the axiomatic properties of the Shapley value (efficiency, symmetry, null player, additivity) are important for regulatory compliance or user communication; (iii) computational simplicity is paramount, since Shapley value estimation via Monte Carlo permutation sampling (Bachrach et al., 2010; Mitchell et al., 2022) is a simple averaging procedure with no hyperparameters beyond the number of samples, whereas CL introduces γ, batch size, learning rate schedule, and the choice of optimizer as practitioner-facing complexity.

The paper does not provide sufficient evidence to make these tradeoffs quantitative (e.g., CL should be preferred when the expected least-core value exceeds some threshold, or when the characteristic function evaluation cost is below some multiple of the optimization cost). The boundary conditions are sketched qualitatively based on the limited empirical evidence: one positive comparison on weighted voting games (Figure 2), one negative comparison on a graph game (Figure 5), and one XAI setting where the comparison reverses (Figure 4c). A practitioner encountering a new game class should expect to run both the LP baseline and CL to determine which performs better, and to run both Shapley and core-based data valuation with a removal-curve evaluation to determine which better identifies critical data points—exactly the empirical methodology the paper itself follows.