Rethinking Least-Core Computation in Contextual-Distractor Games

Hiroshi Kera; Toshinori Yamauchi; Sai Ganesh Nagarajan

cs.LGOct 5, 2026

Rethinking Least-Core Computation in Contextual-Distractor Games

Authors: Hiroshi Kera, Toshinori Yamauchi, Sai Ganesh Nagarajan

Organizations: Chiba University; National Institute of Informatics · University of Southern Denmark, IMADA

Abstract

Game-theoretic attribution explains a model by assigning credit to its features or training examples. The least core has attracted interest as an alternative to Shapley-style averaging because it can expose players that cause substantial harm in rare, high-value contexts. However, least-core allocations are generally nonunique, and the choice of allocation can affect the resulting explanation. In this study, we investigate how payoff selection and coalition sampling affect least-core attribution. Our experiments show that selector choice matters for distinguishing useful and harmful contributions, and that sampling can degrade harmful-player identification across the tested selectors even when useful players remain well identified. These observations motivate efficient computation with all coalition constraints and a well-defined selector. We introduce entropic least core (ELC), a smooth approximation whose unique minimizer follows a continuous path along the temperature to the nucleolus, a classical refinement of the least core. Our experiments show that ELC approximates the nucleolus faster than an LP-based nucleolus solver while retaining small payoff errors, with further GPU acceleration at larger problem sizes. In the tested full-coalition contextual-distractor games, ELC matches the minimum-norm selector in identification accuracy and more accurately ranks distractors by harm.

Figures & tables

Player	Shapley	LP	LP + min-norm	LP + nucleolus	ELC
useful 1 ( $m_{1}=6$ )	$7$	$6$	$17.5$	$13.5$	$13.5$
useful 2 ( $m_{2}=8$ )	$9$	$8$	$17.5$	$15.5$	$15.5$
useful 3 ( $m_{3}=12$ )	$13$	$12$	$17.5$	$19.5$	$19.5$
useful 4 ( $m_{4}=14$ )	$15$	$44$	$17.5$	$21.5$	$21.5$
distractor 1	$3$	$5$	$-10$	$-10$	$-10$
distractor 2	$3$	$-25$	$-10$	$-10$	$-10$

Table 1: Attribution in a six-player contextual-distractor game. Shapley assigns positive credit to both distractors. Least-core allocations assign negative total credit to the pair, but differ in individual signs and the relative credit of useful players.

$n$	$M$	Gap ( $10^{-3}$ )	Rel. gap ( $10^{-4}$ )
8	254	$0.81\pm 0.17$	$4.00\pm 0.81$
10	1,022	$0.96\pm 0.30$	$4.20\pm 1.32$
12	4,094	$1.23\pm 0.12$	$4.96\pm 0.50$
14	16,382	$1.34\pm 0.14$	$5.19\pm 0.51$
16	65,534	$1.17\pm 0.10$	$4.17\pm 0.35$
18	262,142	$1.64\pm 0.15$	$5.72\pm 0.62$

Table 2: Least-core quality. Entries are mean

\pm

standard error over five games. Rel. gap uses the coalition-value range.

	ELC (CPU)			Reference
Setting ( $n$ )	Time (s)	$d_{\rm nuc}$ ( $10^{-3}$ )	Gap ( $10^{-3}$ )	$d_{\rm mn}$ ( $10^{-3}$ )	LP + nucleolus (s)
Random (6)	0.253	1.97	0.59	98.28	1.117
Random (7)	0.190	1.66	0.79	24.38	1.065
Random (8)	0.384	2.84	0.28	81.36	1.369
Medical (9)	0.089	0.90	0.10	4.56	1.041
Chemical (13)	1.146	9.64	1.02	21.59 †	45.321

Table 3: ELC approximates the nucleolus at lower computational cost. Distances are

d_{\rm nuc}=\|x_{\rm ELC}-x_{\rm nuc}\|_{2}

and

d_{\rm mn}=\|x_{\rm ELC}-x_{\rm mn}\|_{2}

; gap is

\hat{\varepsilon}(x_{\rm ELC})-\varepsilon^{*}

. Distances and gaps use medians across 20 games per random setting or ten UCI splits, after taking within-game medians over three repetitions. Times average optimization runtimes, excluding game construction and independent evaluation. Further details are in Section F.1 .

\dagger

One failed min-norm reference is excluded.

\ddagger

House nucleolus time averages 15 completed repetitions, excluding 15 timeouts under a 60-minute limit; distances use all ten splits.

Constraints	Method	AP +	AP -	Distractor	Useful	Harm
				negative rate	order accuracy	order accuracy
Full	Shapley	1.000	0.794	0.639	1.000	1.000
	LP	1.000	0.826	0.667	0.918	0.617
	LP + min-norm	1.000	1.000	1.000	0.667	0.333
	ELC	1.000	1.000	1.000	1.000	1.000
50% sample	Shapley	0.920	0.689	0.635	0.563	0.740

Table 4: Full-coalition ELC identifies and orders both player groups; sampling mainly reduces distractor identification. AP + /AP - measure useful/distractor identification. Negative rate is the fraction of distractors receiving negative credit; order accuracy is the fraction of distinct-strength pairs ranked correctly, counting ties as incorrect. All scores range from 0 to 1; higher is better, and bold marks the best mean within each budget, including ties. Means average samples within each of 60 games, then across games. Sampled methods share coalition observations. Further evaluation details are in Appendix G .

		ELC $-$ min-norm LC		ELC $-$ Shapley
$N_{\mathrm{query}}$	Removal	Mean	95% CI	Mean	95% CI
Gaussian (20 repetitions per budget)
5K	Best $\downarrow$	$-0.463$	$[-0.613,\,-0.306]$	$-3.312$	$[-3.889,\,-2.769]$
5K	Worst $\uparrow$	$+0.118$	$[+0.037,\,+0.197]$	$+0.076$	$[-0.206,\,+0.330]$
10K	Best $\downarrow$	$-0.439$	$[-0.582,\,-0.305]$	$-4.646$	$[-5.330,\,-4.023]$
10K	Worst $\uparrow$	$+0.121$	$[+0.046,\,+0.193]$	$+0.468$	$[+0.097,\,+0.831]$

Table 5: Paired differences in normalized removal AUC (percentage points): ELC minus each baseline. Best removes the highest-ranked training points; Worst removes the lowest-ranked. Negative differences favor ELC for Best; positive differences favor ELC for Worst. CI denotes the 95% bootstrap confidence interval for the mean difference.

N_{\mathrm{query}}

is the coalition-query budget.

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

$n$	Games	Diameter ( $\times 10^{-12}$ )		Max hard gap ( $\times 10^{-4}$ )	Capped games
		Mean $\pm$ SE	Max	Mean $\pm$ SE	Any stage	Final stage
6	20	$1.269\pm 0.350$	5.594	$4.605\pm 0.998$	4	0
7	20	$1.007\pm 0.382$	5.776	$7.069\pm 1.059$	4	2
8	20	$2.275\pm 0.451$	5.439	$4.836\pm 1.166$	11	4

Appendix

Table 6: Endpoint variability across five initializations under nine-stage annealing. Diameter is the maximum pairwise endpoint

\ell_{2}

distance; hard gap is maximized over the five starts. Values use 20 random games per size. The last two columns count games reaching an iteration limit at any stage or at the final stage, respectively.

Figure 1: Annealing toward the nucleolus: median and interquartile range for 60 random games, ten medical splits, and nine chemical splits. Iteration-limited paths are retained; one chemical split lacks a valid reference and is excluded. Temperature decreases left to right.

$n$	Method	Time (s)	Gap	AP +	AP -	Timeout/15	Num. err./15
8	LP	0.003	0	1.000	1.000	0/15	0/15
8	LP + min-norm	0.005	1e-09	1.000	1.000	0/15	0/15
8	50% LP	0.003	0.2	1.000	1.000	0/15	0/15
8	50% LP + min-norm	0.004	0.2	1.000	1.000	0/15	0/15
8	10% LP	0.003	0.32	1.000	1.000	0/15	0/15
8	10% LP + min-norm	0.004	0.278	1.000	1.000	0/15	6/15

Appendix

Table 7: Computational scaling and attribution on contextual-distractor games. Time averages all 15 runs; Gap and AP average successful runs only.

+

marks a time lower bound; – in Gap or AP indicates no successful runs. Settings and aggregation are described in Section F.2 .

Constraints	Method	AP +	AP -	Distractor	Useful	Harm
				negative rate	order accuracy	order accuracy
Full	Shapley	1.000	0.750	0.500	1.000	—
	LP	1.000	0.698	0.417	0.909	—
	LP + min-norm	1.000	1.000	1.000	0.667	—
	ELC	1.000	1.000	1.000	1.000	—
50% sample	Shapley	0.884	0.562	0.506	0.566	—

Appendix

Table 8: Equal-harm counterpart to Table 4 :

h_{j}=b

for all distractors, with 60 games and the same metrics and aggregation. Higher is better; bold marks the best mean within each budget, including ties. Harm order is undefined and shown as a dash.

Constraints	Method	AP +	AP -	Distractor	Useful	Harm
				negative rate	order accuracy	order accuracy
Full	Shapley	1.000	0.673	0.208	1.000	1.000
	LP	1.000	0.761	0.256	0.897	0.373
	LP + min-norm	1.000	1.000	1.000	0.667	0.000
	ELC	1.000	1.000	1.000	1.000	0.633
50% sample	Shapley	0.845	0.654	0.429	0.572	0.593

Appendix

Table 9: Equal useful and distractor counts with varying distractor harm. As in Table 4 ,

h_{j}/b

ranges from

0.25

0.75

across distractors, but group sizes are now equal:

(n,|U|,|D|)=(10,4,4)

and

(14,6,6)

, with two neutrals. Means use 60 games; metrics, aggregation, and boldface follow Table 4 . Game generation and exclusion rules are in Section G.1 .

Constraints	Method	AP +	AP -	Distractor	Useful	Harm
				negative rate	order accuracy	order accuracy
Full	Shapley	1.000	0.764	0.167	1.000	—
	LP	1.000	0.757	0.208	0.896	—
	LP + min-norm	1.000	1.000	1.000	0.667	—
	ELC	1.000	1.000	1.000	1.000	—
50% sample	Shapley	0.804	0.603	0.370	0.574	—

Appendix

Table 10: Equal useful and distractor counts with identical distractor harm. Group sizes match Table 9 , but every distractor has

h_{j}=b

, so any one distractor removes the entire bonus. Means use 60 games with the same metrics, aggregation, and boldface. Harm order is undefined because all distractors are equally harmful and is shown as a dash.

Figure 2: Threshold comparisons at

n=10

, with homogeneous harm above and heterogeneous harm below. Columns compare methods; each pair of rows shows AP + and AP - . Full, 50%, and 10% coalition families use dark-to-light shades and distinct line styles and markers. Sampled Shapley uses the estimator in Section G.3 . Means and SEs use ten games after averaging samples within each game.

Figure 3: Threshold comparisons at

n=14

, with the same layout, aggregation, and line conventions as Figure 2 .

Figure 4: Gaussian training-point removal at all four query budgets. Lines are means over 20 repetitions and bands are

\pm 1

sample standard deviation. Best-first removal favors lower accuracy; worst-first removal favors higher accuracy. Vertical scales are shared across budgets within each removal direction.

Figure 5: Dogfish training-point removal at all four query budgets. Lines are means over five repetitions and bands are

\pm 1

sample standard deviation. Layout and scale conventions match Figure 4 .

Dataset	Lowest first	Highest first
Medical	$-0.032\pm 0.056$	$+0.000\pm 0.068$
Chemical	$+0.299\pm 0.214$	$-0.449\pm 0.217$
House	$+0.029\pm 0.031$	$+0.244\pm 0.242$

Appendix

Table 11: Feature-removal accuracy differences, ELC minus (LP + min-norm), in percentage points: each split contributes its mean over removal steps, followed by mean

\pm

SE over ten splits. Positive favors ELC for lowest-first removal; negative favors ELC for highest-first removal.

Method	Corr. norm. AUC	Corr. acc. at 35%	Mislabel AP	Flip recall
Random	$0.7200\mathbin{\pm}0.011$	$0.723\mathbin{\pm}0.013$	$0.211\mathbin{\pm}0.005$	$0.204\mathbin{\pm}0.018$
Shapley	$0.7306\mathbin{\pm}0.011$	$\mathbf{0.743}\mathbin{\pm}0.012$	$\mathbf{0.456}\mathbin{\pm}0.023$	$\mathbf{0.433}\mathbin{\pm}0.036$
LP + min-norm	$\underline{0.7310}\mathbin{\pm}0.013$	$0.741\mathbin{\pm}0.012$	$0.268\mathbin{\pm}0.015$	$0.273\mathbin{\pm}0.016$
ELC	$\mathbf{0.7336}\mathbin{\pm}0.013$	$\underline{0.742}\mathbin{\pm}0.012$	$\underline{0.274}\mathbin{\pm}0.015$	$\underline{0.286}\mathbin{\pm}0.014$

Appendix

Table 12: Enron label-correction and mislabel-identification results (mean

\mathbin{\pm}

SE over five repetitions). Bold and underline mark the highest and second-highest mean in each performance column, respectively.

Figure 6: Enron label correction after restoring an increasing fraction of the lowest-valued training points. Curves are means over five repetitions and bands are mean

\pm

SE.

Method	Images	Mean $x(D)$	Negative rate	Negative on harmful
Shapley	100	$+0.294$	31.0%	37.8%
LP	100	$-0.259$	67.0%	77.0%
LP + min-norm	97	$-0.250$	67.0%	76.4%
ELC	100	$-0.257$	67.0%	77.0%

Appendix

Table 13: Marker attribution with one sampling seed. Credit is the sum

x(D)

in logit units; negative rate is the fraction with

x(D)<0

. The last column restricts this rate to images where adding

D

to its complement lowers the target logit: 74 images, or 72 among successful LP + min-norm runs.

Figure 7: Marker attribution: Shapley versus least-core marker credit

x(D)

, in logit units. Each point represents one image: the horizontal coordinate is ELC (yellow diamonds, 100 images) or LP + min-norm (blue open circles, 97 successful solves), and the vertical coordinate is the corresponding Shapley estimate. The dashed line denotes equal credit; gray lines mark zero. The two least-core series largely overlap.

Explore similar work

May 7, 2026cs.GT

In-Context Credit Assignment via the Core

We propose incentive-aligned mechanisms for in-context credit assignment: the task of assigning credit for AI-generated content among creators whose intellectual property appears in the context window. Our approach is based on the least core solution concept from cooperative game theory, which distributes value in a way that is as stable as possible by ensuring that no subset of creators is significantly under-compensated relative to the value they could generate on their own. We develop algorithms for approximating the least core, which leverage novel routines for constraint seeding and constraint separation. On a web retrieval credit assignment task, we find that our approaches approximate the least core using an order of magnitude fewer LLM calls compared to alternative methods.

Keegan Harris, Siddharth Prasad, Asher Trockman

UC Berkeley · Toyota Technological Institute at Chicago · Google Research

Credit Assignment Incentives

Ask PDF

Jul 10, 2026cs.LG

Nonlinear Axiomatic Attribution for Cooperative Games

The Shapley value is a widely used concept in attribution problems, as it uniquely satisfies the axioms of linearity, consistency, equal treatment, and efficiency. Often, the inclusion AUC metric is used to evaluate the quality of player rankings, in order to identify positively participating players. However, it can be established that the Shapley value is not always reliable for this purpose. The core issue lies in its linearity: the Shapley value acts as a linear operator with an excessively large null space, which is likely to contain non-negligible perturbations that remain indistinguishable to the operator. To address this limitation, we explore the design of nonlinear axiomatic attribution methods. Inspired by the least core, which is a popular nonlinear substitute for the Shapley value, we introduce a class of nonlinear attribution methods that retain the remaining necessary axioms. Each method yields a contribution vector that is the unique optimal solution to a minimization problem, which aims to approximate utility functions as faithfully as possible. In terms of the inclusion AUC metric, our experiments demonstrate the potential effectiveness of these methods compared to Shapley value variants that relax only the efficiency axiom. Our code is available at https://github.com/watml/nonlinear-axiom.

Weida Li, Zhuanghua Liu, Yaoliang Yu +1

Department of Computer Science, National University of Singapore, Republic of Singapore · School of Computer Science, University of Waterloo, Canada · Vector Institute, Canada

Shapley Value Optimal Roc-Auc

Ask PDF

May 7, 2026cs.LG

QuadraSHAP: Stable and Scalable Shapley Values for Product Games via Gauss-Legendre Quadrature

We study the efficient computation of Shapley values for \emph{product games} -- cooperative games in which the coalition value factorizes as a product of per-player terms. Such games arise in machine learning explainability whenever the value function inherits a multiplicative structure from the underlying model, as in kernel methods with product kernels and tree-based models. Our key result is that the Shapley value of each player in a product game admits an exact one-dimensional integral representation: the weighted sum over exponentially many feature coalitions collapses to the integral of a degree-

(d-1)

polynomial over

[0,1]

, where

d

is the total number of features. This yields a Gauss--Legendre quadrature scheme that is \emph{provably exact} whenever the number of nodes satisfies

m_q \geq \lceil d/2 \rceil

, and otherwise provides a \emph{near-exact} approximation with error provably decaying geometrically in

m_q

. In practice, a few hundred nodes can achieve highly precise estimates even with thousands of features. Building on this formulation, we derive a numerically stable implementation via log-space evaluation, together with an efficient parallel implementation based on associative scan primitives that achieves

O(d\,m_q)

total work and

O(\log d)

parallel time. Experiments show that \textsc{QuadraSHAP} is the fastest numerically stable method across all tested configurations.

Majid Mohammadi, Grigory Reznikov, Pavel Sinitcyn +2

AI Technology for Life, Information and Computing Sciences, Utrecht University, The Netherlands · Biomolecular Mass Spectrometry and Proteomics, Pharmaceutical Sciences, Utrecht University, The Netherlands · Rational Intelligence Lab, CISPA Helmholtz Center for Information Security, Germany +1

Shapley Value Coalition Formation Bayesian Quadrature Value Kernel Method

Ask PDF