CS Paper Radar

Rethinking Least-Core Computation in Contextual-Distractor Games

Hiroshi Kera, Toshinori Yamauchi, Sai Ganesh Nagarajan

cs.LG cs.GT ·submitted 2026-10-05 10:19 UTC · v1
unusual

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.

Comment
12 + 19 pages, 0 + 7 figures, 5 + 8 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Stability Bands for Feature Attribution: The Core, the Nucleolus and the Bargaining Set of Explained-Variance Games

cs.GT cs.LGecon.EM ·2026-11-18 ·Fernando Delbianco, Fernando Tohmé
published similarity 0.67
Abstract · Presented at the XXV Jornadas Latinoamericanas de Teoría Económica (JOLATE 2026), San Luis, Argentina, October 29, 2026. 24 pages, 5 figures

Shapley-value attributions are the default way of explaining machine-learning predictions in economics, but they report a single number per feature and say nothing about whether a coalition of features that jointly accounts for more than it receives could contest that allocation. We study feature attribution through the core, the nucleolus and the bargaining set of an explained-variance game, in which the worth of a set of features is the variance of the model's predictions that those features generate. For every feature we report a stability band (its range of shares over the core, or over the least core when the core is empty), with the nucleolus as distinguished point and a certificate that the allocation admits no justified objection. Three results organise the approach. First, for linear models the game is exactly 2-additive, with pairwise Harsanyi dividends $2β_iβ_jσ_{ij}$, so multicollinearity is what creates coalitional structure. Second, in every 2-additive game the prenucleolus coincides with the Shapley value, the (least) core is point-symmetric around it, and the core is non-empty if and only if every cut of the interaction graph has non-negative weight. The Shapley value thus always lies in the prebargaining set, and stability adds information only through band widths and interactions of order three or more. Third, for convex games the bands have a closed form and any allocation can be certified with one minimum cut. In a hedonic price model, the usual mean-SHAP explanation admits a justified objection by the coalition {Ratings, ROM, Battery}. In a gradient-boosting forecaster of retail orders the exact game has an empty core and strong higher-order interactions; the nucleolus departs from the Shapley value by up to 0.19 variance shares, and sparse third-order surrogates recover it where pairwise ones cannot.

0.47

ShapleyOG: Fast Adaptive Shapley Value Estimation with Odd Gaussian Processes

cs.LG stat.ML ·2026-11-04 ·David Rundel, R. Teal Witter, Santo M. A. R. Thies, Matthias Feurer, Fabian Fumagalli +1 more
similarity 0.63
Abstract · Preprint under review

Shapley values are a central tool for attribution in machine learning. Since their exact computation requires evaluating the cooperative game to be explained on exponentially many player coalitions, they are typically estimated from a limited number of evaluations. Recently, ShaplEIG has shown that adaptively selecting the coalitions to evaluate substantially improves sample efficiency over classical estimators. This, however, comes at the cost of a sequential procedure that, in every iteration, refits a Gaussian process surrogate of the game and selects the coalition with the largest expected information gain about the Shapley values. The resulting computational overhead limits its applicability to costly games with low evaluation budgets. We present fast adaptive Shapley value estimation with Odd Gaussian Processes (ShapleyOG) to overcome this limitation. ShapleyOG leverages the fact that Shapley values depend only on the odd component of the game, and we show that under paired sampling a Gaussian process surrogate on this component alone yields the same Shapley value posterior and coalition selection criterion from half as many observations. Moreover, ShapleyOG refits the surrogate only on a sparse schedule and efficiently updates the selection criterion in between, and it extends quadrature-based computation schemes to the prior covariance of the Shapley values, which allows for exact or cheaper approximate computation. In extensive experiments on diverse games, ShapleyOG matches the estimation accuracy of ShaplEIG while reducing its overhead by up to three orders of magnitude. As a result, it outperforms state-of-the-art non-adaptive estimators at equal total computation time already when a single evaluation takes a tenth of a second and a budget of a few thousand evaluations suffices, thereby widening the regime in which adaptive coalition selection is applicable and pays off.

0.24

Min-Marginal Power Indices for Multi-Objective Feature Selection

cs.LG ·2026-10-24 ·Wenjie Shi, Chi Zhao
benchmark similarity 0.61
Abstract · 12 pages, 3 figures

Game-theoretic feature selection scores each feature by its average marginal contribution across coalitions. An average shows whether a feature helps overall, but not whether, in some coalition, adding it turns an acceptable model into an unacceptable one. Building on minimum marginal aggregation, we define the Min-Marginal Power Index (MinPI) on a binary utility-threshold game. For a fixed quota, MinPI takes the value -1, 0, or +1 and labels each feature harmful, neutral, or decisive. A harmful label carries its own evidence, an evaluated coalition in which adding the feature drops utility below the quota, so no score cutoff is needed; finite-budget estimators keep this property but may miss harmful features. We use MinPI to propose feature removals, which are accepted only if they pass a validation gate, and to prefilter multi-objective search. On six benchmark datasets over five seeds, MinPI removed 12.5% of analyzed features with almost no loss of held-out utility. On Madelon and Abalone, where it removed the most, its removals cost far less held-out utility than random removals of the same size. Prefiltering increased the dataset-averaged hypervolume of multi-objective search in all five seeds. MinPI is therefore a conservative feature-deletion step whose gains are largest where the data contain many removable features.

0.27

Choosing LLMs for Strategic Agent Interactions

cs.AI cs.IRcs.MA ·2026-10-13 ·Arastun Mammadli, Herbert Woisetschläger, Jawad Fayaz, Shiqiang Wang
published similarity 0.57
Abstract · NeurIPS workshop on Foundations of Agentic Systems Theory (FAST), 2026

Game-theoretic benchmarks claim that large language model (LLM) strategic decision-making varies across game types, interaction structures, and capability dimensions. However, they only evaluate strategic performance across individual fixed models. In parallel, contemporary LLM routers pick models under quality-cost trade-offs, but with no notion of a strategic structure. They do not account for an opponent that might be unknown, and that can adapt over time and shift the feedback signal. To address this, we extend the game-theoretic evaluations and define strategic selection as the meta game layered on top of the base game. In each round, a strategic selector fields an LLM from a portfolio of models to navigate a game payoff matrix that is latent and learned online. We find that the evaluation signal is game-specific, and that extracting a reliable signal requires a much higher number of seed runs $N$ compared to traditional benchmarking setups. Evaluating across 5 games and 10 LLMs, we show a model's strategic competence varies significantly depending on the game setup and the opponent faced. Building on this, we implement a suite of selector methods and find that approaches that rely on query embeddings or LLM self-reflection do not consistently capture the underlying strategic signal. A lightweight multi-armed bandit algorithm performs more reliably across games, though it still falls short of the best fixed model. Finally, we show that simple non-stationary and adversarial bandit variants fail to outperform a stationary bandit baseline, pointing to a gap in how current methods handle a shifting opponent in strategic settings.

0.32

Leverage-Enhanced Sampling Owen Method for Explainable Artificial Intelligence

cs.GT cs.LG ·2026-11-16 ·Jing Liu, Elena Parilina, Chi Zhao
similarity 0.57
Abstract · 25 pages, 6 figures

Recently, the Shapley value has been widely applied in machine learning for feature importance analysis and model explainability. The multilinear extension of games proposed by Owen (1972) expresses the Shapley value as the integral of partial derivatives along the main diagonal of the cube. Direct evaluation of this integral requires exponential-time computation of the partial derivatives. To improve computational efficiency, we propose a sampling-based estimation strategy within Owen's multilinear extension framework, combining stratified sampling with coalition leverage scores. Experimental results demonstrate that the proposed method significantly reduces computational costs while maintaining explanation accuracy.

0.42

Efficient Nash Equilibrium Computation for Cybersecurity Games

cs.GT cs.AI ·2026-09-16 ·Michael Lanier, David Farmer, Yevgeniy Vorobeychik
theory similarity 0.57
Abstract

Game-theoretic analyses of cyber defence often compute equilibria of games whose payoffs exist only as the output of a simulator. Iterative equilibrium-finding methods grow a set of attacker and defender policies and need the payoff of every attacker--defender pair, so they are bottlenecked by payoff estimation: each payoff costs many simulator runs. We introduce Regret-Weighted Payoff Sampling (RWPS), which spends a fixed simulation budget on the payoffs the equilibrium actually depends on and predicts the rest with a model trained on every payoff measured so far. Standard error bounds for estimated games are driven by the worst-estimated payoff, so they cannot credit an estimator that is inaccurate only where accuracy does not matter. We prove a bound that weights payoff errors by the opponent's equilibrium strategy, a certificate that can be computed from simulated payoffs alone, and a condition under which errors in the predicted payoffs cannot change either player's regret. On three synthetic general-sum games, one of them a Colonel Blotto game of military resource allocation, the new bounds are four to six times tighter than the standard one, and RWPS finds less exploitable equilibria than minimum-regret-first search, information-gain search and progressive sampling at the same budget. On two cyber-defence simulators, CyGym and a new game whose hosts are LLM agents exposed to prompt injection, it gives the least exploitable equilibria at the smallest budgets.

0.26

Aligning Performance with Contribution: Towards Contribution-Aware Fair Recommendation

cs.IR ·2026-10-06 ·Shuai Zhang, Hui Fang, Zun Sun
position similarity 0.56
Abstract

Existing research on user fairness in recommender systems has developed diverse objectives. However, it has paid limited attention to a distinct distributive perspective: whether users' contributions to model learning should be reflected in the recommendation benefits they receive. We argue that, in addition to existing fairness protections, a fair system may account for the alignment between users' estimated contributions and the recommendation performance they receive. Such alignment can incentivize sustained and informative engagement, thereby supporting a sustainable recommendation ecosystem. To this end, we propose Contribution-Performance Fairness, a novel fairness perspective which requires recommendation performance to be aligned with estimated contribution across user groups and to remain equitable among users with comparable contributions within a same group. To instantiate this perspective, we introduce the Contribution-Performance Fair Recommender (CPFR), a framework applicable to different backbone recommenders. CPFR constructs ordered user groups from a training-dependent contribution considering interaction volume, loss alignment, and optimization intensity, and jointly optimizes recommendation accuracy with the two fairness requirements. A game-theoretic analysis shows that such alignment can strengthen contribution incentives and improve system-level recommendation accuracy under voluntary contribution. Experiments on three datasets and three backbone models demonstrate that CPFR achieves a strong accuracy--fairness trade-off under the proposed operational metric.

0.30

CASI: Credit Assignment via Set Intervention for Agentic Retrieval

cs.AI cs.IRcs.LG ·2026-10-14 ·Xinyi Cheng, Tianfu Zhang, Jiwen Li, Xuesen Zhang, Shihao Yu +3 more
similarity 0.56
Abstract · 19 pages, 2 figures, 8 tables

Large language models increasingly generate multiple retrieval actions jointly, while downstream systems often provide only one reward for the resulting set. Broadcasting this reward provides a valid score-function gradient estimator for the expected set-level objective, but does not determine a coalition-dependent within-set attribution. We introduce CASI (Credit Assignment via Set Intervention for Agentic Retrieval), which constructs the missing counterfactual information through snapshot-grounded set intervention: generate and retrieve once, hold replayable snapshot components fixed, and evaluate alternative subsets under common conditions. Shapley aggregation converts these marginals into within-set credit, which bounded zero-sum advantage shaping incorporates into policy optimization. For m >= 4, singleton, leave-one-out, and full-set endpoints do not generally determine the Shapley allocation; under additive set values, extra coalition evaluations are redundant. In a five-action sponsored-search setting, exhaustive auction replay over 1,200 requests reveals substantial coalition dependence. Under the training-time evaluator, CASI achieves the highest median cosine similarity to a replay-defined Shapley reference among evaluated credit rules; under a sensitivity backend, CASI does not outperform Singleton. Across five independent training runs, CASI-trained policies achieve higher held-out auction-replay set value than Singleton- or Broadcast-trained policies. In a randomized seven-day production A/B test on 10% of traffic, the CASI-trained policy yields an observed 3.51% lift in the primary advertiser-value metric over production control.

0.23