arXiv CSopen access

Dynamic Shapley Computation

Dynamic Shapley Computation

arXiv:2605.20620v1 [cs.LG] 20 May 2026

Xuan Yang1 Hsi-Wen Chen2 Ming-Syan Chen2 Jian Pei1 1 Duke University 2 National Taiwan University {xuan.yang, j.pei}@duke.edu {hwchen, mschen}@ntu.edu.tw

Abstract Shapley-based data valuation provides a principled way to quantify the contribution of training data, but its high computational cost makes it impractical in dynamic settings where tasks and training players evolve. Existing methods treat Shapley computation as a one-shot process and collapse contributions into aggregated scores, preventing reuse and requiring recomputation under any change. We introduce a new perspective that represents Shapley values as a player-by-task matrix and formulates dynamic valuation as a structured matrix maintenance problem. We exploit the fact that each task depends on a small subset of training players and that similar tasks yield similar valuations, leading to utility locality and coalition locality. Based on these insights, we propose D-Shap, a dynamic valuation framework that enables efficient updates by modifying only a small portion of the matrix: new task valuations are inferred via structure-aware interpolation, while updates induced by new players are confined to affected local matrix blocks. To eliminate the need for pre-specified evaluation tasks, we introduce self-valuation, which constructs the initial matrix directly from training data, supported by scalable subset reuse and coverage-aware anchor selection. Experiments across diverse models show that D-Shap performs task updates in milliseconds and reduces the cost of player updates by up to three orders of magnitude, while achieving valuation quality competitive with full recomputation.

1

Introduction

The Shapley value [39] has become a standard tool for data valuation in machine learning [16], supporting applications such as data pricing [27], dataset curation [4], and model debugging [1]. In these applications, Shapley value evaluates the contribution of each contributor (player) to a given task. Here, a task refers to an evaluation objective defined by a utility function, such as model performance on a query, a subset of data, or an application-specific criterion [22][28]. In practice, tasks can be instantiated by individual queries, batches of queries, or downstream evaluation workloads [23, 29]. Modern applications are inherently dynamic: new tasks continuously arise, and new data contributors expand the training set [10, 35]. As a result, dynamic Shapley value computation—updating valuations efficiently under evolving tasks and training data—becomes a fundamental requirement. At a high level, Shapley value quantifies the contribution of each training player by averaging its marginal contribution over all subsets [39]. In dynamic settings, this leads to two core challenges: (i) task-incremental updates, where valuations must be computed for newly arriving tasks, and (ii) player-incremental updates, where new training players alter the underlying cooperative game and affect existing valuations. In practice, the two types of updates often occur simultaneously, requiring the valuation method to handle evolving tasks and players in a unified manner. Existing methods are fundamentally static: they assume fixed data and fixed tasks, and therefore must recompute from scratch for every update [16][42]. The few works on dynamic Shapley [45, 50] handle limited scenarios and still rely on global recomputation, making them unable to scale to realistic workloads. Preprint.

(a) Player-by-task Shapley matrix ©

(b) Task-incremental update

players zi

t1

t2

t3

t4

(c) Player-incremental update

interpolate

tasks tj

t5

t6

t1

t2

t3

t4

t5

t6

t0

t1

z1

z1

z1

z2

z2

z2

z3

z3

z3

z4

z4

z4

z5

z5 © i; j = Á(zi ; tj ) 2 ℝ

n£m

t2

R(z 0 )

t3

t4

t5

t6

z5 c

Á(t 0 ) =

X

t 2 A(t 0 )

w(t 0 ; t) Á(t)

z0 0

0

0

updates only t2R(z ), z2N(t)[N + (t) 0

Figure 1: Overview of D-Shap. (a) D-Shap represents Shapley values as a player-by-task matrix Φ, where Φi,j = ϕ(zi , tj ) denotes player zi ’s contribution to task tj . (b) Task-incremental update (Sec. 3.3): a new task t′ is valued by interpolating nearby columns (green) under the model-induced distance dΓ . (c) Player-incremental update (Sec. 3.4): a new player z ′ affects only columns whose local games involve it (coral); other entries (gray) stay frozen. The root cause is the prohibitive cost of Shapley computation. Exact computation is #P-hard [11], requiring exponentially many coalition evaluations. Even approximate methods [3, 7, 16, 25, 44] remain expensive, as each evaluation typically involves training or updating a machine learning model. In dynamic settings, repeatedly retraining models for every update is infeasible. More fundamentally, existing approaches reduce Shapley values to a single aggregated score per training player [16, 43], discarding how contributions vary across different tasks. This loss of information prevents reuse and forces global recomputation. This paper introduces a fundamentally different perspective: Shapley values should be represented as a collection of per-task contributions that can be maintained and reused. Instead of treating valuation as a one-shot computation, we explicitly model how each training player contributes to each task. Our key insight is that, for a given task, the model typically depends only on a small subset of relevant training instances [21, 46–48]. This local dependency implies that both task-incremental and player-incremental updates can be performed by focusing only on the affected subsets, rather than recomputing globally. Building on this insight, we propose D-Shap, a new framework for dynamic Shapley value computation. D-Shap represents Shapley values as a player-by-task matrix, where each entry records the contribution of a training instance to a task. This representation preserves fine-grained information that is lost in prior aggregation-based methods and enables two key operations: (i) task-incremental updates, which estimate valuations for new tasks by leveraging similar existing tasks, and (ii) playerincremental updates, which update only the affected parts of the matrix when new training players arrive. By maintaining and reusing this matrix, D-Shap avoids repeated global recomputation.1 This perspective transforms Shapley computation from an exponential, one-shot procedure into a reusable and incremental process. It opens a new direction for scalable data valuation in dynamic machine learning systems, making Shapley-based methods practical in settings that were previously computationally prohibitive.

2

Dynamic Shapley Computation

Shapley value for data valuation in Machine Learning. Let D = {zi }ni=1 be a set of training contributors (players), and let T = {tj }m j=1 be a set of tasks. Each task t ∈ T specifies an evaluation objective through a utility function. Given a task t, the utility of a subset S ⊆ D is vt (S) = g(θ(S), t), where θ(S) is the model trained on S, and g(·, t) evaluates the model on task t (e.g., loss, accuracy, or confidence) [16, 21]. The Shapley value [16, 34, 39] of training player z ∈ D with respect to task t is 1 X vt (S ∪ {z}) − vt (S)
ϕ(z, t) = . n−1 n |S|

(1)

S⊆D\{z}

1 D-Shap also supports deletion and replacement: task-side updates remove or replace the corresponding Shapley-matrix

column, while player-side updates identify the coalitions affected by the player change and update them selectively.

2

It measures the average marginal contribution of z to task t. However, computing ϕ(z, t) requires evaluating exponentially many subsets, making it #P-hard [11]. The player-by-task Shapley matrix. Existing methods can compute ϕ(z, t) for each player–task pair. However, they typically aggregate these values across tasks into a single score per player, or treat each task independently in a one-shot manner. As a result, the per-task contributions are not explicitly maintained or reused. This lack of a persistent representation fundamentally limits reuse: when tasks or players change, Shapley values must be recomputed from scratch. Our key idea is to retain this information by representing Shapley values as a player-by-task matrix, Φ ∈ Rn×m ,

Φi,j = ϕ(zi , tj ),

(2)

where each entry records the contribution of player zi to task tj . This matrix has a clear interpretation: each row Φi,: captures how a player performs across tasks, while each column Φ:,j represents the Shapley values for a specific task. By explicitly modeling who contributes to which task, this representation enables reuse across both players and tasks, which is not possible under aggregated formulations. Dynamic Shapley valuation. We study dynamic updates where tasks and players evolve over time. Problem 1 (Task-Incremental Valuation). Given a Shapley matrix Φ and a set of new tasks ∆T = {tm+1 , . . . , tm+∆m }, estimate n×(m+∆m) [Φ:,1:m | Φnew , :, m+1:m+∆m ] ∈ R new

where Φ

(3)

contains the columns for the new tasks.

Here, the player set is fixed, and the goal is to compute Shapley values for new tasks without recomputing existing ones. Problem 2 (Player-Incremental Valuation). Given a Shapley matrix Φ and a set of new players ∆D = {zn+1 , . . . , zn+∆n }, estimate   Φupd 1:n,: ∈ R(n+∆n)×m . (4) Φnew n+1:n+∆n,: In this case, the cooperative game changes, requiring both new rows (for new players) and updates to existing rows. Our goal is to maintain the Shapley matrix incrementally with fewer model trainings than full recomputation by treating it as a maintained object and updating only the necessary parts rather than recomputing values from scratch. In practice, task-incremental and player-incremental updates may occur simultaneously, which requires a unified solution.

3

D-Shap

Given the player-by-task Shapley matrix in Section 2, our goal is to maintain this matrix under dynamic updates. Dynamic Shapley computation thus reduces to updating Φ when new tasks arrive (adding columns) and when new players are introduced (adding rows and modifying affected entries). Rather than recomputing all values, D-Shap updates only a small portion of Φ by exploiting the fact that each task depends on a limited subset of players and that similar tasks exhibit similar contribution patterns. 3.1

D-Shap Framework

Let Φ ∈ Rn×m denote the maintained Shapley matrix. We consider two update operators: (i) a task update, which takes a new task t′ , computes its Shapley column ϕ(t′ ), and appends it to Φ; and (ii) a player update, which takes a new player z ′ , adds a new row for z ′ , and updates only the entries whose values change under the expanded player set. The central challenge is to identify the affected entries for each update. For a task t, let N (t) ⊆ D denote the subset of training players that determine its utility. This induces a sparse dependency: ϕ(z, t) is nonzero only if z ∈ N (t) [47]. Consequently, a task update requires estimating ϕ(t′ ) from related tasks, while a player update modifies only the columns whose dependency sets change. 3

This view reduces dynamic Shapley computation to localized matrix updates. In the following subsections, we formalize this dependency and derive efficient procedures for task-incremental updates, player-incremental updates, and matrix construction. 3.2

Model-Induced Locality

A key observation enabling efficient dynamic Shapley computation is that, in many machine learning models, the utility of a task is dominated by a small subset of training players [33, 46, 48]. This phenomenon, referred to as model-induced locality [47], implies that Shapley values are inherently sparse and structured, and therefore do not require global recomputation under updates. In contrast, recomputing Shapley values directly would revisit all players and tasks, with each entry defined by averaging marginal contributions over exponentially many coalitions [16, 39]. Following Yang et al. [47], we formalize this property through a local support set. For each task t, let N (t) ⊆ D denote the subset of players that influence its utility and thus may receive nonzero Shapley value.2 This notion captures how the model uses training data for a given task and naturally varies across model classes. For example, in KNN, N (t) consists of nearest neighbors [21, 31]; in decision trees, training players in the same leaf [29]; in kernel methods, players with high similarity [8]; and in graph neural networks, nodes within a local neighborhood [19, 24]. The existence of small support sets has two important consequences for maintaining the Shapley matrix. First, tasks with similar supports tend to have similar contribution patterns, enabling efficient estimation of new columns. Second, a new player can affect only the tasks whose support sets change, restricting updates to a small subset of entries. These effects give rise to task-side locality and player-side locality, which form the foundation of our incremental update methods. Together, model-induced locality reduces dynamic Shapley computation from a global problem to a localized update problem, where only a small portion of the matrix needs to be recomputed. 3.3

Task-Incremental Valuation via Utility Locality

We first address Problem 1. Given a Shapley matrix Φ, a new task t′ = tm+1 corresponds to adding a new column ϕ(t′ ). The goal is to estimate this column efficiently without recomputing Shapley values from scratch. The key challenge is to identify existing tasks that are informative for estimating ϕ(t′ ). This is enabled by utility locality: tasks with similar local dependencies induce similar utility functions and therefore have similar Shapley columns. A natural baseline is to use feature-space proximity to find similar tasks [20, 41]. However, feature similarity does not capture how the model uses training data. For example, in a graph neural network, two nodes with similar attributes but different neighborhoods induce different local computation structures, leading to very different Shapley values [13, 19, 49]. As a result, feature-based similarity can produce misleading estimates. To address this, we compare tasks based on their local computation structure. Let Γ(t) denote the local computation structure of task t, which captures both the supporting players N (t) and how their contributions are combined by the model (e.g., through weights, aggregation, or connectivity). This structure reflects how the model computes the utility of t from its relevant players. Examples include decision paths in trees, message-passing neighborhoods in GNNs, weighted neighbor profiles in KNN, and kernel-relevance patterns in kernel models. We define a model-induced distance
dΓ (t, t′ ) = d Γ(t), Γ(t′ ) , (5) where dΓ is instantiated according to the model (e.g., path overlap, graph distance, or support overlap); see Appendix C for concrete instantiations across different model families. A small value of dΓ (t, t′ ) indicates that t and t′ share similar computation structures and therefore exhibit utility locality. To connect this notion of similarity—captured by the model-induced distance dΓ between local computation structures—to Shapley values, we impose a stability condition on the evaluation function. Assumption 1 (Model-induced Lipschitz continuity). For every coalition S ⊆ D, the trained model θ(S) lies in a hypothesis class Θ. Moreover, for any fixed model θ ∈ Θ, the evaluation function 2 If the utility is only approximately determined by N (t) with error at most ϵ, the induced Shapley error is bounded by 2ϵ;

see Lemma 1 in Appendix B.1.

4

g(θ, t) varies smoothly across tasks with respect to the model-induced distance dΓ , i.e., |g(θ, t) − g(θ, t′ )| ≤ LΓ dΓ (t, t′ )

for all t, t′ .

Assumption 1 ensures that tasks with similar computation structures induce similar utility values under the same model. This condition holds for regularized ERM models and more broadly for models with bounded parameters and Lipschitz losses [5, 37]; see Appendix B.9 for a derivation showing how these conditions imply the Lipschitz bound. Under this condition, Shapley columns inherit the same smoothness [15, 22]. Proposition 1 (Utility locality). Under Assumption 1, for any two test points t and t′ , ∥ϕ(t) − ϕ(t′ )∥∞ ≤ 2LΓ dΓ (t, t′ ).

Proposition 1 shows that tasks that are close under dΓ have similar Shapley columns. This directly enables column interpolation: we estimate ϕ(t′ ) by combining nearby columns, X b ′) = ϕ(t w(t′ , t)ϕ(t), (6) t∈A(t′ )

where A(t′ ) contains tasks nearest to t′ under dΓ , and the weights are convex. We formalize the accuracy of this estimator as follows. Theorem 1 (Interpolation error). Under Assumption 1, if every reference point t ∈ A(t′ ) satisfies dΓ (t′ , t) ≤ ε, then b ′ ) − ϕ(t′ ) ϕ(t ≤ 2LΓ ε. ∞

Theorem 1 shows that the estimation error is controlled by the distance between t′ and its neighbors under dΓ . This yields an efficient update rule: new columns are inferred from nearby columns rather than recomputed, reducing exponential computation to a local interpolation step. The same procedure applies independently to each task in ∆T , producing Φnew :, m+1:m+∆m . 3.4

Player-Incremental Valuation via Coalition Locality

We next address Problem 2. Given a Shapley matrix Φ, the arrival of a new player z ′ = zn+1 upd expands the matrix by adding a new row Φnew n+1,: and may also change existing entries Φ1:n,: . A naive approach would recompute all entries, which is prohibitively expensive. The key observation is that these updates are inherently localized. For each task t, its utility depends only on a subset of players N (t), which we refer to as its local dependency structure. This induces a local cooperative game restricted to players in N (t), which fully determines the Shapley values for task t. When a new player z ′ is added, only the tasks whose local dependency structures change need to be updated. Formally, let N (t) and N + (t) denote the support sets of task t before and after inserting z ′ . The set of affected tasks is R(z ′ ) = {t ∈ T : N + (t) ̸= N (t)}, (7) i.e., the tasks whose local dependency structures, and hence local games, change. Let ϕ+ (z, t) and ϕ(z, t) denote the Shapley values under the updated and original games, respectively. The following result formalizes the coalition locality. Proposition 2 (Coalition locality). If the model evaluation at t depends only on its local support, then for any t ∈ / R(z ′ ), the valuation at t remains unchanged, i.e., ϕ+ (zj , t) = ϕ(zj , t) for all zj ∈ D. Proposition 2 shows that only tasks in R(z ′ ) require updates. Moreover, within each affected task, only players in N (t) ∪ N + (t) can change. All other entries remain unchanged and are directly reused. Thus, updates are restricted to a small local block of the matrix. We summarize the update rule as follows. 5

Theorem 2 (Local player update). Under coalition locality, for any t ∈ R(z ′ ), the updated Shapley values are determined by the new local game restricted to N + (t):

ϕ+ (z, t) =

 X vt (S ∪ {z}) − vt (S) 1  , 
 + (t)| |N + (t)|−1  |N  |S| S⊆N + (t)\{z}

z ∈ N + (t), z ∈ N (t) \ N + (t),

0,      ϕ(z, t),

z∈ / N (t) ∪ N + (t).

The theorem partitions players into three groups: (i) players in N + (t), which are evaluated under the updated local game; (ii) players removed from the support, whose contributions become zero; and (iii) unaffected players, whose values remain unchanged. This decomposition makes the update entirely local. A particularly efficient case arises when the support only expands. Corollary 1 (Monotone support expansion). For any t ∈ R(z ′ ), if N + (t) = N (t) ∪ {z ′ }, then the local update can reuse the original Shapley matrix. Specifically, z ′ is valued on N + (t) using coalitions from N (t), since N + (t) \ {z ′ } = N (t). Each existing player zj ∈ N (t) is updated by ϕ+ (zj , t) = ϕ(zj , t) + ∆j,t (z ′ ).

Here, ∆j,t (z ′ ) captures the change in the marginal contribution of zj caused by inserting z ′ on t. Corollary 1 shows that when N + (t) = N (t) ∪ {z ′ }, the update can reuse existing Shapley values. The new row is computed from the marginal effect of z ′ , while existing players receive an additive correction that accounts for how z ′ changes their contributions.3 In this case, the number of new evaluations is bounded by X 2|N (t)| ≤ |R(z ′ )|2Kmax ,

(8)

t∈R(z ′ )

where Kmax = maxt∈R(z′ ) |N (t)|; see Corollary 2 in Appendix B.8. Overall, inserting new players expands Φ by new rows, while existing entries are updated only for affected tasks and local dependency structures. Since these local games are typically much smaller than the full player set [21, 47], the cost depends on local structure size rather than the entire matrix, turning global recomputation into efficient localized updates. General Dynamic Updates. D-Shap also supports deletion under the same matrix-maintenance principle. For task deletion, removing a task simply deletes its corresponding column from Φ. For player deletion, removing a player z deletes its row from Φ and updates only the tasks whose local support sets are affected. Let N − (t) denote the support set after deleting z. If N − (t) = N (t), coalition locality implies that the remaining entries are unchanged. Otherwise, D-Shap recomputes only the local game induced by N − (t) while reusing all other entries. More broadly, simultaneous task and player updates are handled by composing task-side interpolation with player-side localized row/block updates. The new task columns are estimated using the interpolation guarantee in Theorem 1, while entries affected by newly added players are updated using the local-game principle in Theorem 2. Their interaction is confined to new task columns whose support sets include new players. Therefore, task/player addition, deletion, replacement, and joint updates are unified as localized Shapley-matrix maintenance; see Appendix E. 3.5

Constructing the Shapley Matrix via Self-Valuation

The effectiveness of D-Shap relies on an initial player-by-task Shapley matrix that can support future updates. However, in dynamic settings, such a matrix is often unavailable: an external set of tasks may not exist at initialization time, or may be poorly aligned with future tasks, leading to inaccurate interpolation and degraded performance. Therefore, we introduce self-valuation, a new mechanism that constructs the Shapley matrix directly from the training data itself, without requiring any external tasks. The key idea is to treat each player as a proxy task, thereby turning the training set into a self-contained set of evaluation tasks. 3We assume that N (t) fully determines the utility of t; the approximate case is given in Theorem 3 in Appendix B.7.

6

Specifically, for each player zi ∈ D, we define a leave-one-out game with player set D−i = D \ {zi } and treat zi as a task. This yields a self-valuation Shapley matrix Φ ∈ Rn×n with entries ϕ(zj , zi ) computed under D−i . Diagonal entries are undefined since zi is excluded. This construction avoids the degenerate case where a player explains itself, while producing a matrix that reflects intrinsic relationships within the data. Shared Subset Scheduling. A naive construction would solve n independent leave-one-out Shapley games, each requiring Θ(2n−1 ) model trainings, resulting in Θ(n · 2n−1 ) total cost. This is prohibitively expensive. To eliminate redundancy, we introduce shared subset scheduling, which reorganizes computation around coalition reuse. Instead of evaluating each coalition separately for each task, we assign every coalition S ⊆ D a unique pivot zπ(S) ∈ D \ S. The model θ(S) is trained once at its pivot and its utility is reused across all tasks zi ∈ / S, contributing to ϕ(·, zi ) with appropriate weights. This design evaluates each coalition exactly once while preserving the exact Shapley estimator. Thus, self-valuation requires no more training runs than a single global Shapley computation, yet produces n valuation columns. This transforms an otherwise prohibitive cost into a practical one. Coverage-Aware Anchor Selection. Even with shared subset scheduling, constructing the full matrix can be expensive for large datasets. We therefore build a compact Shapley matrix using a small set of representative players, called anchors. Specifically, we select {a1 , . . . , ak } ⊆ D with k ≪ n and construct Φ ∈ Rn×k . Anchor quality is measured by the covering radius rmax = max

min

zi ∈D a∈{a1 ,...,ak }

dΓ (zi , a).

(9)

A smaller radius improves coverage and makes interpolation more reliable. We minimize this radius using farthest-point sampling, which gives a standard 2-approximation [18]. During online updates, if a new task t′ is poorly covered, i.e., mina dΓ (t′ , a) > τ , we explicitly compute its Shapley column and add it as a new anchor, enabling adaptive matrix expansion to maintain accuracy over time. Overall, self-valuation provides a self-contained and scalable initialization of the Shapley matrix. Combined with shared subset scheduling and adaptive anchor selection, it enables D-Shap to operate without external tasks while maintaining both efficiency and accuracy.

4

Experiments

We evaluate D-Shap across five representative model families with distinct locality mechanisms and compare it against both static and dynamic baselines. Our goal is to examine whether D-Shap maintains high-quality Shapley values while avoiding expensive recomputation in dynamic settings. The evaluation is organized around four questions: RQ1 (Task-incremental) asks whether D-Shap can accurately and efficiently estimate Shapley values for new tasks; RQ2 (Player-incremental) asks whether D-Shap can efficiently update valuations when new players arrive; RQ3 (Locality) studies whether model-induced locality is necessary for reliable valuation updates; and RQ4 (Scalability) evaluates whether constructing the Shapley matrix is efficient and scalable in practice. 4.1

Experimental Setup

Datasets and models. We evaluate D-Shap across five representative model–dataset pairs that exhibit diverse forms of model-induced locality, where each model defines locality through a different notion of supporting players and computation structure. We consider: (i) Weighted K-Nearest Neighbors (WKNN) [12] on MNIST [26] (neighbor-based locality); (ii) Decision Trees (DT) [6] on Iris [14] (partition-based locality); (iii) RBF Kernel SVM [8] on Breast Cancer [40] (kernel-relevance locality); (iv) Convolutional Neural Networks (CNN) [26] on MNIST (representation-space locality); and (v) Graph Convolutional Networks (GCN) [24] on Cora [32] (graph neighborhood locality). These models span both classical and deep learning settings, highlighting the generality of our framework. Dataset statistics and hyperparameters are provided in Appendix D.1. Baselines. We compare against both static and dynamic baselines. Static methods include GlobalMC Recompute (high-budget Monte Carlo reference), TMC-Shapley [16], and Comple-S [42]. For task-incremental settings, we include learning-based baselines Fast-DataShapley [41] and AmortizedS [9], which predict Shapley scores without explicit update rules. For player-incremental settings, we 7

Table 1: Task-Incremental Valuation WKNN/MNIST

Method

DT/Iris

SVM/BC

CNN/MNIST

GNN/Cora

ρ

r

T

ρ

r

T

ρ

r

T

ρ

r

T

ρ

r

T

Global-MC† TMC-Shapley Comple-S

1.000 0.881 0.502

1.000 0.858 0.750

2.0e4 6.9e3 2.6e3

1.000 0.805 0.821

1.000 0.906 0.928

2.1e3 1.6e3 1.7e2

1.000 0.776 0.648

1.000 0.850 0.782

1.2e4 5.6e3 3.7e3

1.000 0.678 0.708

1.000 0.921 0.937

2.1e5 9.6e4 5.4e4

1.000 0.788 0.804

1.000 0.947 0.952

1.2e5 1.3e5 8.6e4

Amortized-S Fast-DataShapley D-Shap

0.114 0.291 0.908

0.106 0.130 0.819

2.2e-2 9.6e-1 4.1e-3

0.594 0.523 0.801

0.647 0.481 0.847

3.1e-2 4.4e-2 3.4e-4

0.612 0.477 0.870

0.569 0.246 0.922

3.5e-2 2.7e-2 3.6e-4

0.376 0.130 0.752

0.809 0.126 0.905

6.8e-2 5.1e-2 3.1e-4

-0.002 0.030 0.532

0.061 0.116 0.630

8.2e-2 7.1e-2 1.2e-3

Table 2: Player-Incremental Valuation WKNN/MNIST

Method

DT/Iris

SVM/BC

CNN/MNIST

GNN/Cora

ρ

r

T

ρ

r

T

ρ

r

T

ρ

r

T

ρ

r

T

Global-MC† TMC-Shapley Comple-S

1.000 0.878 0.425

1.000 0.752 0.710

2.3e4 8.4e3 4.5e3

1.000 0.786 0.719

1.000 0.833 0.912

1.3e3 9.1e2 6.7e2

1.000 0.814 0.498

1.000 0.961 0.879

2.2e4 6.8e3 4.2e3

1.000 0.426 0.439

1.000 0.687 0.675

3.9e5 1.3e5 8.6e4

1.000 0.822 0.629

1.000 0.972 0.837

7.0e5 7.2e5 4.6e5

B-Delta D-Shap

0.753 0.875

0.663 0.933

1.2e4 5.9e1

0.733 0.760

0.813 0.811

1.1e3 7.5e1

0.698 0.636

0.657 0.701

1.3e3 9.3e1

0.318 0.462

0.280 0.680

2.1e5 3.9e2

0.643 0.705

0.829 0.697

5.1e5 2.5e2

compare with B-Delta [45]. We exclude DeltaShap [50] as it does not finish within our compute budget. These baselines represent state-of-the-art approaches for static estimation, amortized prediction, and incremental updates. Evaluation protocol. We construct the initial Shapley matrix using self-valuation, making the setup fully self-contained without external tasks. We then reserve a held-out pool to simulate dynamic updates. In the task-incremental setting, held-out points arrive as new tasks, while the player set remains fixed. In the player-incremental setting, they arrive as new players, while evaluation tasks remain fixed. The held-out pool is processed as a stream, with updates performed online after each arrival. We reserve 30% of the data for Iris and Breast Cancer, and 1,000 points for MNIST and Cora. Metrics. We evaluate both accuracy and efficiency. Accuracy is measured by Spearman rank correlation ρ (filtering < 10−3 entries dominated by MC noise) and Pearson correlation r against a high-budget Global-MC reference. Efficiency is measured by wall-clock time T per update [50]. This setup directly evaluates whether D-Shap achieves accurate valuation while avoiding recomputation. Implementation details. All Monte Carlo methods use a shared stopping criterion and are capped at 5,000 samples [16]. Convergence is checked every 100 samples using relative change. Each experiment is repeated with five random seeds. Experiments are run on a single machine with 64 Intel Xeon E5-2640 v4 CPUs and 64 GB RAM; CNN and GNN models additionally use four NVIDIA RTX A5000 GPUs. 4.2

Task-Incremental Valuation (RQ1)

Table 1 evaluates D-Shap on task-incremental valuation. D-Shap achieves accuracy comparable to static baselines while reducing per-task cost by 106 –108 ×, enabling real-time valuation. This is achieved by replacing recomputation with interpolation over existing columns under utility locality. Learning-based baselines assume feature similarity implies valuation similarity. However, Proposition 1 shows that valuation similarity is governed by model-induced computation structure. When these diverge, learning-based methods fail. This is most evident in GNNs, where feature-based baselines collapse, while D-Shap reaches 0.532. Although performance on GNNs is weaker due to limitations of dΓ , D-Shap consistently outperforms learning-based methods. 4.3

Player-Incremental Valuation (RQ2)

Table 2 evaluates D-Shap on player-incremental valuation. D-Shap maintains comparable accuracy while reducing update cost by 101 –103 ×. This efficiency comes from exploiting coalition locality: D-Shap identifies the affected set R(z ′ ) and updates only the corresponding local games using Theorem 2 and Corollary 1, while reusing all unaffected entries. In contrast, dynamic baselines still require repeated Monte Carlo updates, whose cost grows with dataset size, making them expensive for deep models. In general, D-Shap avoids global recomputation by converting player updates into localized matrix updates, achieving up to 1000× speedup and maintaining competitive quality. 8

Table 3: Utility Locality

Table 4: Coalition Locality

Table 5: Matrix Efficiency

Model

Feature ρ

D-Shap ρ

Feature r

D-Shap r

Dataset

Pred.

Support

ρ

r

Model

Naive

D-Shap

Speedup

WKNN DT SVM CNN GNN

0.685 0.758 0.807 0.596 −0.003

0.908 0.800 0.870 0.752 0.532

0.621 0.794 0.913 0.876 0.006

0.819 0.847 0.922 0.905 0.630

MNIST MNIST MNIST

WKNN WKNN WKNN

WKNN SVM DT

0.875 0.534 0.658

0.933 0.716 0.390

Cora Cora Cora

GNN GNN GNN

GNN WKNN DT

0.705 0.308 0.417

0.697 0.491 0.510

WKNN DT SVM CNN GNN

4102 s 12724 s 9165 s >100 hrs >100 hrs

149 s 251 s 262 s 5410 s 3432 s

27.6× 50.7× 35.0× >66.5× >104.9×

4.4

Role of Model-Induced Locality (RQ3)

We evaluate the necessity of model-induced locality from two perspectives. First, Table 3 analyzes utility locality by comparing the model-induced distance dΓ with L2 feature-space proximity for task-incremental valuation. Across models, dΓ improves ρ by 5.5%–32.6%, with the largest gap on GNNs, where feature proximity fails (ρ = −0.003) while dΓ reaches 0.532; even for WKNNs, dΓ improves ρ from 0.685 to 0.908. Second, Table 4 studies coalition locality by testing whether the support-set definition N (t) aligns with the prediction model in player-incremental valuation. Matched support performs best, improving ρ by 33.0%–63.9% on WKNNs and by 69.1%–128.9% on GNNs, while mismatched support captures only partial task-specific utility. The sensitivity to support-set size is provided in Appendix D.2. 4.5

Efficiency of Shapley Matrix Construction (RQ4)

Table 5 evaluates the cost of constructing the Shapley matrix Φ. D-Shap achieves over 25× speedup across all settings, with even larger gains for deep models, where model training is more expensive and naive methods fail to finish within 100 hours. This efficiency comes from shared subset scheduling, which removes redundant evaluations. Appendix D.3 studies coverage-aware anchor selection, which further reduces matrix construction cost while preserving update quality. These results show that D-Shap makes Shapley matrix construction practical.

5

Related Work

Shapley values originate from cooperative game theory [39] and were introduced to ML data valuation by Data Shapley [16], where training instances are treated as players and utility is measured on a held-out validation set. They have since been used for feature attribution [30], data selection [17], model debugging [1], and data marketplace pricing [2, 27]. To reduce estimation cost, prior work uses Monte Carlo coalition sampling [7], truncated coalition evaluation [16], complementary-contribution averaging [42], and group testing [22], or exploits model structure via TreeSHAP [29], KNNShapley [21], and Local Shapley [47]. Gradient- and influence-based proxies [3, 25, 36, 44] trade exact Shapley semantics for tractable per-trajectory or per-update attribution. All of the above assume a fixed player-task set; revaluation under change requires re-running the estimator. As the player set evolves, dynamic Shapley methods [45, 50] update values for arriving contributors, but still require global recomputation and are limited to fixed tasks. For task dynamics, amortized explainers [9, 20, 41] train a model once and produce per-task Shapley values via a single forward pass, but require explainer retraining whenever a new player arrives. In contrast, D-Shap unifies task- and player-incremental valuation by exploiting model-induced locality to update only affected entries in the player-by-task Shapley matrix. It provides principled update rules for both task-side and player-side changes (Propositions 1 and 2) with error guarantees (Theorems 1 and 3), achieving substantial speedup while maintaining valuation quality comparable to full recomputation.

6

Conclusion

We introduced D-Shap, a new framework for dynamic Shapley computation that redefines data valuation as a structured matrix maintenance problem. By representing Shapley values as a playerby-task matrix and leveraging model-induced locality, D-Shap enables efficient updates through localized interpolation and restricted recomputation, avoiding costly global recalculation. We further proposed self-valuation, which eliminates the need for pre-specified evaluation tasks and makes the framework fully self-contained and scalable. These ideas transform Shapley computation from an expensive one-shot process into a reusable and incremental procedure, significantly improving practicality in dynamic machine learning systems. 9

References [1] J. Adebayo, M. Muelly, I. Liccardi, and B. Kim. Debugging tests for model explanations. arXiv preprint arXiv:2011.05429, 2020. [2] A. Agarwal, M. Dahleh, and T. Sarkar. A marketplace for data: An algorithmic solution. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 701–726, 2019. [3] S. Basu, P. Pope, and S. Feizi. Influence functions in deep learning are fragile. arXiv preprint arXiv:2006.14651, 2020. [4] E. Bhardwaj, H. Gujral, S. Wu, C. Zogheib, T. Maharaj, and C. Becker. The state of data curation at neurips: An assessment of dataset development practices in the datasets and benchmarks track. Advances in Neural Information Processing Systems, 37:53626–53648, 2024. [5] O. Bousquet and A. Elisseeff. Stability and generalization. Journal of machine learning research, 2(Mar):499–526, 2002. [6] L. Breiman, J. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth International Group, 1984. [7] J. Castro, D. Gómez, and J. Tejada. Polynomial calculation of the shapley value based on sampling. Computers & operations research, 36(5):1726–1730, 2009. [8] C. Cortes and V. Vapnik. Support-vector networks. Machine learning, 20(3):273–297, 1995. [9] I. Covert, C. Kim, S.-I. Lee, J. Zou, and T. Hashimoto. Stochastic amortization: A unified approach to accelerate feature and data attribution. Advances in Neural Information Processing Systems, 37:4374–4423, 2024. [10] M. De Lange, R. Aljundi, M. Masana, S. Parisot, X. Jia, A. Leonardis, G. Slabaugh, and T. Tuytelaars. A continual learning survey: Defying forgetting in classification tasks. IEEE transactions on pattern analysis and machine intelligence, 44(7):3366–3385, 2021. [11] X. Deng and C. H. Papadimitriou. On the complexity of cooperative solution concepts. Mathematics of operations research, 19(2):257–266, 1994. [12] S. Dudani. The distance-weighted k-nearest-neighbor rule. IEEE Transactions on Systems, Man, and Cybernetics, SMC-6(4):325–327, 1976. [13] A. Duval and F. D. Malliaros. Graphsvx: Shapley value explanations for graph neural networks. In Joint European conference on machine learning and knowledge discovery in databases, pages 302–318. Springer, 2021. [14] R. A. Fisher. The use of multiple measurements in taxonomic problems. Annals of Eugenics, 7(2):179–188, 1936. [15] A. Ghorbani, M. Kim, and J. Zou. A distributional framework for data valuation. In International Conference on Machine Learning, pages 3535–3544. PMLR, 2020. [16] A. Ghorbani and J. Zou. Data shapley: Equitable valuation of data for machine learning. In International conference on machine learning, pages 2242–2251. PMLR, 2019. [17] A. Ghorbani, J. Zou, and A. Esteva. Data shapley valuation for efficient batch active learning. In 2022 56th asilomar conference on signals, systems, and computers, pages 1456–1462. IEEE, 2022. [18] T. F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical computer science, 38:293–306, 1985. [19] W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017. 10

[20] N. Jethani, M. Sudarshan, I. C. Covert, S.-I. Lee, and R. Ranganath. Fastshap: Real-time shapley value estimation. In International conference on learning representations, 2021. [21] R. Jia, D. Dao, B. Wang, F. A. Hubis, N. M. Gurel, B. Li, C. Zhang, C. J. Spanos, and D. Song. Efficient task-specific data valuation for nearest neighbor algorithms. arXiv preprint arXiv:1908.08619, 2019. [22] R. Jia, D. Dao, B. Wang, F. A. Hubis, N. Hynes, N. M. Gürel, B. Li, C. Zhang, D. Song, and C. J. Spanos. Towards efficient data valuation based on the shapley value. In The 22nd international conference on artificial intelligence and statistics, pages 1167–1176. PMLR, 2019. [23] K. Jiang, W. Liang, J. Y. Zou, and Y. Kwon. Opendataval: a unified benchmark for data valuation. Advances in Neural Information Processing Systems, 36:28624–28647, 2023. [24] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017. [25] P. W. Koh and P. Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pages 1885–1894. PMLR, 2017. [26] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998. [27] J. Liu, J. Lou, J. Liu, L. Xiong, J. Pei, and J. Sun. Dealer: An end-to-end model marketplace with differential privacy. Proceedings of the VLDB Endowment, 14(6), 2021. [28] Z. Liu, Y. Chen, H. Yu, Y. Liu, and L. Cui. Gtg-shapley: Efficient and accurate participant contribution evaluation in federated learning. ACM Transactions on intelligent Systems and Technology (TIST), 13(4):1–21, 2022. [29] S. M. Lundberg, G. Erion, H. Chen, A. DeGrave, J. M. Prutkin, B. Nair, R. Katz, J. Himmelfarb, N. Bansal, and S.-I. Lee. From local explanations to global understanding with explainable ai for trees. Nature machine intelligence, 2(1):56–67, 2020. [30] S. M. Lundberg and S.-I. Lee. A unified approach to interpreting model predictions. Advances in neural information processing systems, 30, 2017. [31] J. Mairal, J. Ponce, G. Sapiro, A. Zisserman, and F. Bach. Supervised dictionary learning. Advances in neural information processing systems, 21, 2008. [32] A. K. McCallum, K. Nigam, J. Rennie, and K. Seymore. Automating the construction of internet portals with machine learning. In Information Retrieval, volume 3, pages 127–163. Springer, 2000. [33] B. Mirzasoleiman, J. Bilmes, and J. Leskovec. Coresets for data-efficient training of machine learning models. In International Conference on Machine Learning, pages 6950–6960. PMLR, 2020. [34] M. J. Osborne and A. Rubinstein. A course in game theory. MIT press, 1994. [35] G. I. Parisi, R. Kemker, J. L. Part, C. Kanan, and S. Wermter. Continual lifelong learning with neural networks: A review. Neural networks, 113:54–71, 2019. [36] S. M. Park, K. Georgiev, A. Ilyas, G. Leclerc, and A. Madry. ˛ Trak: attributing model behavior at scale. In Proceedings of the 40th International Conference on Machine Learning, pages 27074–27113, 2023. [37] S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 11:2635–2670, 2010. [38] N. Z. Shapiro and L. S. Shapley. Values of large games, i: A limit theorem. Mathematics of Operations Research, 3(1):1–9, 1978. [39] L. S. Shapley et al. A value for n-person games. 1953. 11

[40] W. N. Street, W. H. Wolberg, and O. L. Mangasarian. Nuclear feature extraction for breast tumor diagnosis. IS&T/SPIE 1993 International Symposium on Electronic Imaging: Science and Technology, 1905:861–870, 1993. [41] H. Sun, Y. Xiong, R. Wu, X. Cai, C. Fan, L. Zhang, and X.-Y. Li. Fast-datashapley: Neural modeling for training data valuation. In Proceedings of the Nineteenth ACM International Conference on Web Search and Data Mining, pages 607–617, 2026. [42] Q. Sun, J. Zhang, J. Liu, L. Xiong, J. Pei, and K. Ren. Shapley value approximation based on complementary contribution. IEEE Transactions on Knowledge and Data Engineering, 2024. [43] J. T. Wang and R. Jia. Data banzhaf: A robust data valuation framework for machine learning. In International conference on artificial intelligence and statistics, pages 6388–6421. PMLR, 2023. [44] J. T. Wang, P. Mittal, D. Song, and R. Jia. Data shapley in one training run. In The Thirteenth International Conference on Learning Representations. [45] H. Xia, J. Zhang, Q. Sun, J. Liu, K. Ren, L. Xiong, and J. Pei. Computing shapley values for dynamic data. IEEE Transactions on Knowledge and Data Engineering, 37(6):3253–3271, 2025. [46] K. Xu, C. Li, Y. Tian, T. Sonobe, K.-i. Kawarabayashi, and S. Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pages 5453–5462. pmlr, 2018. [47] X. Yang, H.-W. Chen, M.-S. Chen, and J. Pei. Local shapley: Model-induced locality and optimal reuse in data valuation. arXiv preprint arXiv:2603.03672, 2026. [48] C.-K. Yeh, J. Kim, I. E.-H. Yen, and P. K. Ravikumar. Representer point selection for explaining deep neural networks. Advances in neural information processing systems, 31, 2018. [49] H. Yuan, H. Yu, J. Wang, K. Li, and S. Ji. On explainability of graph neural networks via subgraph explorations. In International conference on machine learning, pages 12241–12252. PMLR, 2021. [50] J. Zhang, H. Xia, Q. Sun, J. Liu, L. Xiong, J. Pei, and K. Ren. Dynamic shapley value computation. In 2023 IEEE 39th International Conference on Data Engineering (ICDE), pages 639–652. IEEE, 2023.

12

A

Notations Table 6: Summary of notation. Notation

Description

D = {zi }n i=1 T = {tj }m j=1 zi tj n m S⊆D θ(S) g(θ(S), t) vt (S) ϕ(z, t) Φ ∈ Rn×m Φi,j Φ:,j Φi,:

Training players, also called players Evaluation tasks The i-th training player or player The j-th task Number of training players Number of tasks A coalition of players Model trained on coalition S Evaluation function of model θ(S) on task t Task-specific utility, vt (S) = g(θ(S), t) Shapley value of player z with respect to task t Player-by-task Shapley matrix Entry of Φ, where Φi,j = ϕ(zi , tj ) Shapley column for task tj Shapley row for player zi

∆T ∆D t′ z′ Φnew Φupd

Set of newly arriving tasks Set of newly arriving players A newly arriving task A newly arriving player Newly added rows or columns in the updated Shapley matrix Updated entries for existing players or tasks

N (t) N + (t) R(z ′ ) dΓ (t, t′ ) Γ(t) LΓ ϵ b ′) ϕ(t A(t′ ) w(t′ , t)

Local support set of task t before an update Local support set of task t after inserting a new player Affected task set after inserting z ′ Model-induced distance between tasks t and t′ Local computation structure of task t Lipschitz constant with respect to dΓ Coverage radius or locality error tolerance Interpolated Shapley column for a new task t′ b ′) Neighboring anchor tasks used to interpolate ϕ(t Interpolation weight assigned to task t for estimating t′

A k k/n rmax τ Kmax

Anchor set for self-valuation matrix construction Number of selected anchors Anchor ratio Maximum covering radius of anchors under dΓ Threshold for adaptive anchor expansion Maximum local support size among affected tasks

r ρ T

Pearson correlation with the Global-MC reference Spearman rank correlation with the Global-MC reference Wall-clock update or construction time

13

B

Detailed Proof

B.1

Proof of Lemma 1

Lemma 1. Let v̄t (S) = vt (S ∩ N (t)) be the localized game, and let ηt = supS⊆D |vt (S) − v̄t (S)| denote the localization error. If ηt ≤ ϵ, then for every zj ∈ D, |ϕ(zj , t) − ϕ̄(zj , t)| ≤ 2ϵ, where ϕ̄(zj , t) is the Shapley value under v̄t . Proof. By the definition of ηt , for every coalition S ⊆ D, |vt (S) − v̄t (S)| = |vt (S) − vt (S ∩ N (t))| ≤ ηt ≤ ϵ. Fix any training instance zj ∈ D. By the Shapley definition,     X vt (S ∪ {zj }) − vt (S) − v̄t (S ∪ {zj }) − v̄t (S) 1
ϕ(zj , t) − ϕ̄(zj , t) = n−1 n |S|

(10)

S⊆D\{zj }

≤ ≤

1 n 1 n

X

|vt (S ∪ {zj }) − v̄t (S ∪ {zj })| + |vt (S) − v̄t (S)|
n−1

S⊆D\{zj }

|S|

X

2ϵ

S⊆D\{zj }

n−1 |S|

= 2ϵ.

The last equality follows because, for each coalition size k, there are size k, and therefore n−1 X 1X 1 1
= 1 = 1. n−1 n n |S| S⊆D\{zj }

n−1 k

subsets of D \ {zj } with

k=0

Thus, ϕ(zj , t) − ϕ̄(zj , t) ≤ 2ϵ. B.2

Proof of Proposition 1

Proposition 1. Under Assumption 1, for any two test points t and t′ , ∥ϕ(t) − ϕ(t′ )∥∞ ≤ 2LΓ dΓ (t, t′ ).

Proof. Fix any coalition S ⊆ D. By definition, vt (S) = g(θ(S), t). Since θ(S) ∈ Θ, Assumption 1 gives |vt (S) − vt′ (S)| = |g(θ(S), t) − g(θ(S), t′ )| ≤ LΓ dΓ (t, t′ ). Now fix any training instance zi ∈ D. By the Shapley definition, 1 X vt (S ∪ {zi }) − vt (S)
. ϕi (t) = n−1 n |S| S⊆D\{zi }

Therefore, |ϕi (t) − ϕi (t′ )| ≤ ≤

1 n 1 n

X

(11)

|vt (S ∪ {zi }) − vt′ (S ∪ {zi })| + |vt (S) − vt′ (S)|
n−1 |S|

S⊆D\{zi } ′

X

2LΓ dΓ (t, t )
. n−1

S⊆D\{zi }

|S|

Since the Shapley weights sum to one, we obtain |ϕi (t) − ϕi (t′ )| ≤ 2LΓ dΓ (t, t′ ). Taking the maximum over all zi ∈ D gives ∥ϕ(t) − ϕ(t′ )∥∞ ≤ 2LΓ dΓ (t, t′ ).

14

(12)

B.3

Proof of Theorem 1

Theorem 1. Under Assumption 1, if every reference point t ∈ A(t′ ) satisfies dΓ (t′ , t) ≤ ε, then b ′ ) − ϕ(t′ ) ϕ(t ≤ 2LΓ ε. ∞

Proof. By the interpolation estimator, X

b ′ ) − ϕ(t′ ) = ϕ(t

w(t′ , t) (ϕ(t) − ϕ(t′ )) ,

(13)

t∈A(t′ )

where the weights form a convex combination. Therefore, X b ′ ) − ϕ(t′ ) ≤ w(t′ , t) ϕ(t) − ϕ(t′ ) ∞ ϕ(t ∞

(14)

t∈A(t′ )

X

≤

w(t′ , t)2LΓ dΓ (t′ , t)

(15)

w(t′ , t)2LΓ ε

(16)

t∈A(t′ )

X

≤

t∈A(t′ )

= 2LΓ ε.

(17)

The P second ′ inequality follows from Proposition 1, and the last equality follows from t∈A(t′ ) w(t , t) = 1. The theorem follows. B.4

Proof of Proposition 2

Proposition 2. If the model evaluation at t depends only on its local support, then for any t ∈ / R(z ′ ), + the valuation at t remains unchanged, i.e., ϕ (zj , t) = ϕ(zj , t) for all zj ∈ D. Proof. Let D+ = D ∪ {z ′ }. For any t ∈ / R(z ′ ), by the definition of R(z ′ ), we have N + (t) = N (t). Since z ′ is not in the original player set D, this implies z ′ ∈ / N + (t). Because the model evaluation at t depends only on its local support, and the local support is unchanged after inserting z ′ , the new player has no effect on the utility at t. Thus, for any coalition A ⊆ D+ , vt+ (A) = vt (A ∩ D).

(18)

′

In particular, z is a null player at t, and hence ϕ+ (z ′ , t) = 0.

(19)

It remains to show that the Shapley values of existing players are unchanged. Fix any zj ∈ D and let n = |D|. For any S ⊆ D \ {zj }, define ∆t (S; zj ) = vt (S ∪ {zj }) − vt (S).

(20)

′

′

Since z is null at t, the same marginal contribution is obtained whether or not z is included in the coalition: vt+ (S ∪ {zj }) − vt+ (S) = vt+ (S ∪ {z ′ } ∪ {zj }) − vt+ (S ∪ {z ′ }) = ∆t (S; zj ).

(21)

Therefore, the Shapley value of zj in the new game is 1 ϕ (zj , t) = n+1

X

+

=

1 n

∆t (S; zj )

S⊆D\{zj }

X

∆t (S; zj )
n−1

S⊆D\{zj }

|S|

= ϕ(zj , t).

1

+

n |S|

!

1 n |S|+1

(22) (23) (24)

′

Thus, for any t ∈ / R(z ), the valuation of every existing player remains unchanged, and the new player has zero value at t. The proposition follows. 15

B.5

Proof of Theorem 2

Theorem 2. Under coalition locality, for any t ∈ R(z ′ ), the updated Shapley values are determined by the new local game restricted to N + (t):

ϕ+ (z, t) =

 X vt (S ∪ {z}) − vt (S) 1  , 
 + (t)| |N + (t)|−1  |N  |S| S⊆N + (t)\{z}

z ∈ N + (t), z ∈ N (t) \ N + (t),

0,      ϕ(z, t),

z∈ / N (t) ∪ N + (t).

Proof. Fix an affected test point t ∈ R(z ′ ). Under coalition locality, the updated utility at t depends only on the players in the new local support N + (t). Hence, the updated cooperative game can be restricted to the player set N + (t). For any player z ∈ N + (t), its updated Shapley value is the Shapley value in this restricted game: ϕ+ (z, t) =

1 |N + (t)|

X

vt (S ∪ {z}) − vt (S) .
|N + (t)|−1

S⊆N + (t)\{z}

|S|

(25)

If z ∈ N (t) \ N + (t), then z belongs to the old local support but is removed from the new local support. Since the updated game at t is restricted to N + (t), the utility is independent of z. Thus, for every coalition S ⊆ N + (t), we have vt (S ∪ {z}) = vt (S), and the marginal contribution of z is zero. Hence, ϕ+ (z, t) = 0. Finally, if z ∈ / N (t) ∪ N + (t), then z is outside both the old and new local supports of t. By coalition locality, inserting z ′ does not change the contribution of such a player to test point t. Therefore, ϕ+ (z, t) = ϕ(z, t). Combining the three cases, the theorem follows. B.6

Proof of Corollary 1

Corollary 1. For any t ∈ R(z ′ ), if N + (t) = N (t) ∪ {z ′ }, then the local update can reuse the original Shapley matrix. Specifically, z ′ is valued on N + (t) using coalitions from N (t), since N + (t) \ {z ′ } = N (t). Each existing player zj ∈ N (t) is updated by ϕ+ (zj , t) = ϕ(zj , t) + ∆j,t (z ′ ).

Here, ∆j,t (z ′ ) captures the change in the marginal contribution of zj caused by inserting z ′ on t. Proof. Fix any t ∈ R(z ′ ) such that N + (t) = N (t) ∪ {z ′ }, and let nt = |N (t)|. By Theorem 2, the updated Shapley values are computed in the local game restricted to N + (t). For the new player z ′ , the Shapley formula averages its marginal contribution over coalitions that do not contain z ′ . Since N + (t) \ {z ′ } = N (t), these coalitions are exactly subsets of the old support N (t). Hence, X vt (S ∪ {z ′ }) − vt (S) 1
ϕ+ (z ′ , t) = . (26) nt nt + 1 |S| S⊆N (t)

′

Thus, z is valued by its marginal effects over coalitions in N (t). Next, consider an existing player zj ∈ N (t). For any S ⊆ N (t) \ {zj }, define mj (S) = vt (S ∪ {zj }) − vt (S). In the updated local game, coalitions excluding zj either do not contain z ′ and have the form S, or contain z ′ and have the form S ∪ {z ′ }. Therefore, " # X 1 mj (S) mj (S ∪ {z ′ }) +
+
ϕ (zj , t) = . (27) nt nt nt + 1 |S| |S|+1 S⊆N (t)\{zj }

16

The original Shapley value of zj in the old local game is ϕ(zj , t) =

1 nt

X

mj (S)
nt −1 .

S⊆N (t)\{zj }

|S|

(28)

Using the identity 1
= t −1 nt + 1 nt n|S| 1

1 nt |S|

+

!

1 nt |S|+1

,

we can subtract ϕ(zj , t) from ϕ+ (zj , t) and obtain ϕ+ (zj , t) − ϕ(zj , t) =

1 nt + 1

X

mj (S ∪ {z ′ }) − mj (S)
. nt

S⊆N (t)\{zj }

|S|+1

(29)

Since     mj (S ∪ {z ′ }) − mj (S) = vt (S ∪ {zj , z ′ }) − vt (S ∪ {z ′ }) − vt (S ∪ {zj }) − vt (S) , this difference is exactly the change in the marginal contribution of zj caused by inserting z ′ . Defining ∆j,t (z ′ ) = ϕ+ (zj , t) − ϕ(zj , t), we obtain ϕ+ (zj , t) = ϕ(zj , t) + ∆j,t (z ′ ). Therefore, under monotone support expansion, the local update reuses the original Shapley values and updates existing players through an additive correction. The corollary follows. B.7

Proof of Theorem 3

Theorem 3. Let D+ = D ∪ {z ′ } and let N + (t) be the local support of t after inserting z ′ . Define the localized updated game v̄t+ (S) = vt+ (S ∩ N + (t)),

S ⊆ D+ .

If ηt+ = sup vt+ (S) − v̄t+ (S) ≤ ϵ, S⊆D +

then for every z ∈ D+ , ϕ+ (z, t) − ϕ̄+ (z, t) ≤ 2ϵ, where ϕ̄+ (z, t) is the Shapley value under v̄t+ . Equivalently, the local update over N + (t) approximates the full updated Shapley value within 2ϵ. Proof. The result follows by applying Lemma 1 to the updated game with player set D+ , utility vt+ , and local support N + (t). The condition ηt+ ≤ ϵ is exactly the corresponding utility approximation condition for this updated game. Hence, for every z ∈ D+ , the Shapley value computed under the localized updated game v̄t+ differs from the full updated Shapley value by at most 2ϵ. B.8

Proof of Corollary 2

Corollary 2. Assume the monotone support expansion condition in Corollary 1. Then, for updating all affected columns t ∈ R(z ′ ), the number of new utility evaluations is at most X 2|N (t)| ≤ |R(z ′ )|2Kmax , (30) t∈R(z ′ )

where Kmax = max′ |N (t)|. t∈R(z )

17

Proof. Under monotone support expansion, for every affected test point t ∈ R(z ′ ), the updated support satisfies N + (t) = N (t) ∪ {z ′ }. By Corollary 1, the update only requires evaluating coalitions that contain the new player z ′ together with a subset of the original support N (t). Since N (t) has 2|N (t)| subsets, the number of such coalitions for a fixed affected test point t is at most 2|N (t)| . Summing over all affected test points gives X

2|N (t)| .

t∈R(z ′ )

By the definition of Kmax = max′ |N (t)|, t∈R(z )

we have 2|N (t)| ≤ 2Kmax for every t ∈ R(z ′ ). Therefore, X X 2|N (t)| ≤ 2Kmax = |R(z ′ )|2Kmax . t∈R(z ′ )

t∈R(z ′ )

The corollary follows. B.9

Utility Locality under Regularized ERM

We provide a representative derivation showing that Assumption 1 holds under a standard regularized empirical risk minimization setting. Let each test point be denoted by t = (xt , yt ), and let the model trained on a nonempty coalition S ⊆ D be obtained by θ(S) = arg min θ

1 X µ ℓ(fθ (xi ), yi ) + ∥θ∥22 , |S| z ∈S 2

(31)

i

where µ > 0 is the regularization strength. For the empty coalition, we use a fixed reference model θ(∅) satisfying the same norm bound stated below. Assume that the predictor is linear in a model-induced representation ψ(t): fθ (xt ) = θ⊤ ψ(t).

(32)

vt (S) = g(θ(S), t) = −ℓ(fθ(S) (xt ), yt ).

(33)

The utility is defined as the negative loss, Proposition 3 (Utility locality under regularized ERM). Assume that the model prediction has the form aθ (t) = ⟨θ, ψ(t)⟩, where ψ(t) is the local computation representation of t. Assume that the loss ℓ(a, y) is nonnegative and Lℓ -Lipschitz in its prediction argument a for every fixed label y, and that ℓ(0, y) ≤ C0 for all labels y. For µ-regularized ERM, any solution θ(S) for coalition S ⊆ D satisfies r ∥θ(S)∥2 ≤ B :=

2C0 . µ

(34)

Consequently, for any two test points t and t′ with the same evaluation label, Assumption 1 holds with dΓ (t, t′ ) = ∥ψ(t) − ψ(t′ )∥2 ,

r LΓ = Lℓ B = Lℓ

2C0 . µ

(35)

Proof. Consider the µ-regularized ERM objective for any coalition S ⊆ D: X µ 1 θ(S) ∈ arg min ℓ(aθ (xi ), yi ) + ∥θ∥22 . θ∈Θ |S| 2 (xi ,yi )∈S

Assume aθ (t) = ⟨θ, ψ(t)⟩. Since θ(S) minimizes the objective, its objective value is no larger than that of θ = 0. Therefore, X X 1 µ 1 ℓ(aθ(S) (xi ), yi ) + ∥θ(S)∥22 ≤ ℓ(0, yi ). |S| 2 |S| (xi ,yi )∈S

(xi ,yi )∈S

18

By nonnegativity of the loss and the assumption ℓ(0, y) ≤ C0 , we have µ ∥θ(S)∥22 ≤ C0 . 2 Thus, s 2C0 ∥θ(S)∥2 ≤ B := . µ Now consider two test points t and t′ with the same evaluation label yt = yt′ . Let the evaluation function be g(θ, t) = −ℓ(aθ (t), yt ). Then, for any θ(S), |g(θ(S), t) − g(θ(S), t′ )| = |ℓ(aθ(S) (t), yt ) − ℓ(aθ(S) (t′ ), yt )| ≤ Lℓ |aθ(S) (t) − aθ(S) (t′ )| = Lℓ |⟨θ(S), ψ(t) − ψ(t′ )⟩| ≤ Lℓ ∥θ(S)∥2 ∥ψ(t) − ψ(t′ )∥2 ≤ Lℓ B∥ψ(t) − ψ(t′ )∥2 . Therefore, Assumption 1 holds with s dΓ (t, t′ ) = ∥ψ(t) − ψ(t′ )∥2 ,

LΓ = Lℓ B = Lℓ

2C0 . µ

The proposition follows. Proposition 3 applies to test points with the same evaluation label. When the utility explicitly depends on the evaluation label and yt may differ from yt′ , the same argument can be extended by augmenting the model-induced distance with a label-mismatch term. For example, if the utility is bounded as |vt (S)| ≤ Bv for all t and S, then Assumption 1 holds under dΓ (t, t′ ) = ∥ψ(t) − ψ(t′ )∥2 + 1[yt ̸= yt′ ],

(36)

LΓ = max {Lℓ B, 2Bv } .

(37)

with When yt = yt′ , the representation term gives the Lipschitz bound from Proposition 3. When yt ̸= yt′ , the indicator term ensures dΓ (t, t′ ) ≥ 1, while boundedness gives |vt (S) − vt′ (S)| ≤ 2Bv . Furthermore, the ERM derivation provides one sufficient condition rather than a complete characterization. Similar utility-locality bounds can be derived by defining dΓ according to each model’s local computation structure, such as neighbor-weight profiles for weighted KNN, kernel-relevance profiles for kernel models, and path or leaf overlap for decision trees. When the utility is Lipschitz or bounded with respect to the chosen structure, Assumption 1 follows with the corresponding constant. For neural models, this reasoning applies most directly when the encoder is fixed or the learned representation is uniformly stable.

C

Model-Induced Locality

Here, we define the support set and model-induced distance dΓ used in Section 3.2 for each model family in our experiments. In all cases, dΓ compares the local computation structures that determine the task-specific games vt and vt′ , rather than raw input features. The concrete form of dΓ depends on the model family: neighbor relevance for KNN, decision paths for trees, kernel relevance for SVMs, propagation influence for GNNs, and representation-space alignment for deep neural networks. C.1

Weighted K-nearest-neighbor classifiers

For WKNN, the local game at task t is determined by its K nearest training points and their distancebased voting weights. We define N (t) as the K-nearest-neighbor set of t. Let ωt (z) ≥ 0 be the relevance weight assigned to training point z ∈ D, with ωt (z) = 0 for z ∈ / N (t). We set P ′ min{ω (z), ω (z)} t t dΓ (t, t′ ) = 1 − P z∈D . max{ω (z), ω t t′ (z)} z∈D 19

This is the weighted Tanimoto distance between the two neighbor-relevance profiles. In the unweighted case, it reduces to Jaccard distance between K-neighbor supports. C.2

Decision trees

For a fitted decision tree, the local computation structure of t is its root-to-leaf decision path. We define N (t) as the set of training points that fall into the same leaf as t, and let Path(t) denote the set of internal nodes on the decision path of t. The model-induced distance is dΓ (t, t′ ) = 1 −

|Path(t) ∩ Path(t′ )| ∈ [0, 1]. |Path(t) ∪ Path(t′ )|

This distance captures how much of the recursive partition structure is shared by the two tasks. If two points reach the same leaf, their paths coincide and dΓ (t, t′ ) = 0. C.3

Kernel support-vector machines

For an RBF-SVM with bandwidth γ > 0 and kernel Kγ (t, z) = exp(−γ∥t − z∥2 ), the local game at task t is determined by the kernel relevance of training points to t. We define N (t) as the training points with non-negligible kernel relevance, such as the top-K points under Kγ (t, z) or those above a fixed threshold. The model-induced distance compares the two kernel-relevance profiles: P min{Kγ (t, z), Kγ (t′ , z)} ′ dΓ (t, t ) = 1 − P z∈D . ′ z∈D max{Kγ (t, z), Kγ (t , z)} Thus, two tasks are close when they rely on similar training points under the kernel geometry. C.4

Graph neural networks

For an L-layer message-passing GNN, the prediction at a node task t depends on training nodes that can influence t through graph propagation. We define N (t) as the training nodes with non-negligible propagation influence on t, implemented by an L-hop neighborhood or by retaining the top-influence training nodes. To measure influence, we use the personalized PageRank vector π t , centered at t and defined by e t, π t = αet + (1 − α)Aπ e is the normalized adjacency matrix and α ∈ (0, 1) is the teleport probability. The modelwhere A induced distance is P min{π t (z), π t′ (z)} dΓ (t, t′ ) = 1 − P z∈D . max{π t (z), π t′ (z)} z∈D Compared with hard neighborhood overlap, this distance accounts for heterogeneous propagation strength induced by the graph structure. C.5

Deep neural networks

For a deep neural network classifier f = h ◦ ϕ, where ϕ : X → Rd is a learned representation encoder and h is the prediction head, the local computation structure of task t is represented by its embedding ϕ(t). We define N (t) as the nearest training points to t in the embedding space and measure task similarity by angular alignment:   1 ⟨ϕ(t), ϕ(t′ )⟩ dΓ (t, t′ ) = 1− ∈ [0, 1]. 2 ∥ϕ(t)∥2 ∥ϕ(t′ )∥2 This formulation applies to CNNs, RNNs, and Transformers by taking ϕ(t) as the penultimate-layer representation, final hidden state, or pooled token representation, respectively. The factor 1/2 rescales cosine distance to the unit interval. The encoder ϕ is fixed during incremental updates, so dΓ provides a stable geometry for both task-incremental and player-incremental valuation. 20

C.6

Label compatibility

For supervised classification, the utility vt (S) = g(θ(S), t) depends on the label of the task. Therefore, two tasks with similar local computation structures but different labels may still induce different cooperative games. When labels are available, we restrict interpolation to label-compatible columns. Equivalently, we set dΓ (t, t′ ) = ∞ if yt ̸= yt′ . This restriction simply reflects that the label is part of the evaluation condition defining vt .

D

Additional Experimental Results

D.1

Detailed Setup

Table 7: Dataset statistics used across all experiments. Dataset

|Dtrain |

|Dtest |

Features

Classes

Domain

Iris Breast Cancer MNIST Cora

105 398 1,000 1,708

45 171 1,000 1,000

4 30 784 1,433

3 2 10 7

Tabular Tabular Image Graph

Datasets and model families. Each setting pairs a model family with a dataset whose structure matches the model’s locality mechanism, providing a direct test of whether utility and coalition locality hold across qualitatively distinct prediction structures. • WKNN/MNIST. We use a weighted K-nearest-neighbor classifier with K=5 over CNN-extracted MNIST image features. The local support N (t) is the set of 2K=10 nearest training points to t in feature space, chosen to cover the effective neighborhood of the K-NN decision rule with a small buffer beyond the K predicting neighbors. • Decision Tree/Iris. We use a depth-limited decision tree trained with the Gini criterion. The local support N (t) is the set of training points reaching the same leaf as t under the fitted tree, which coincides with the players that determine the prediction at t under the partition structure. • SVM/Breast Cancer. We use an RBF-kernel support-vector machine with bandwidth tuned by cross-validation on the precomputation set. The local support is N (t) = {z ∈ D : Kγ (t, z) ≥ 0.5}, retaining training points with non-negligible kernel relevance to the test point. • CNN/MNIST. We use a three-layer convolutional network trained on raw MNIST pixel inputs. The local support N (t) is the top-20 training points by penultimate-layer embedding similarity to ϕ(t), where ϕ is the encoder trained on the precomputation set and held fixed throughout incremental updates. • GNN/Cora. We use a two-layer graph convolutional network on the Cora citation network. The local support N (t) is the set of training nodes within the two-hop ego network of t, matching the receptive field of the two-layer message-passing model. Dataset statistics are summarized in Table 7. Evaluation Protocol. We use D to construct the self-valuation matrix Φ and reserve a held-out pool that is not used during precomputation. The role of the held-out pool depends on the incremental setting. In task-incremental valuation, the reserved points are treated as incoming prediction tasks while the training set remains fixed. In player-incremental valuation, they are treated as newly arriving training instances that expand the training set, while the evaluation points are kept fixed. We reserve 30% of the data for this held-out pool on Iris, Breast Cancer, and Cora, and sample 1,000 held-out points for MNIST. In all incremental experiments, the held-out pool is processed as a stream, where points are introduced one at a time and the valuation matrix is updated upon each arrival. Baselines. We compare D-Shap with both static and dynamic baselines. • Static baselines. We include three static Shapley estimators that recompute values from scratch after each update. Global-MC Recompute is a high-budget Monte Carlo estimator and serves as 21

the reference for quality evaluation. TMC-Shapley [16] estimates marginal contributions over random permutations and truncates a permutation once the coalition utility has converged, thereby reducing unnecessary evaluations for late-arriving players in a permutation. Comple-S [42] improves sampling efficiency by pairing each sampled coalition with its complementary coalition, so that one sampled subset provides information about two coupled marginal-contribution terms. These methods are general-purpose but do not reuse the existing Shapley matrix, so they still require substantial recomputation under task or player arrivals. • Task-incremental baselines. For learned Shapley predictors, Fast-DataShapley [41] trains a query-conditioned explainer ϕθ (x, y), implemented as a two-layer MLP supervised by the Shapleykernel CWLS loss. We train it for 105 iterations across all settings, requiring more than 10 hours on CNN/MNIST and GNN/Cora. Amortized-S [9] predicts scalar Shapley scores via a regressor fθ (t, z), implemented as a two-layer MLP that takes a task–player pair as input and is trained on samples from the self-valuation matrix Φself to convergence under early stopping. Reported T for learned predictors is inference-only, and training cost is excluded. • Player-incremental baselines. For dynamic shapley valuation, B-Delta [45] incrementally updates marginal contribution estimates by reusing previously sampled permutations and updating the terms affected by inserted players. However, its update cost still grows with the number of existing players and sampled permutations, and it does not exploit task-specific coalition locality. We exclude another player-incremental baseline, DeltaShap [50], from the main comparison because it fails to produce results within our compute budget. Metrics. We measure update quality by comparing each method’s final Shapley matrix, after the b denote the estimated entire stream of arrivals, against the high-budget Global-MC reference. Let Φ ⋆ Shapley matrix and Φ denote the Global-MC reference. Following the large-game perspective in cooperative game theory, many players in large cooperative games can be individually insignificant, with non-negligible value concentrated on a small subset of influential players [38]. This phenomenon is also consistent with model-induced locality in data valuation: each task depends primarily on a small local support set, while players outside the support have zero or near-zero contribution. Therefore, when computing correlation metrics, we filter entries whose reference magnitude is below 10−3 , since these near-zero values are dominated by Monte Carlo noise and do not provide reliable ordering information. This filtering removes numerically unstable entries rather than excluding meaningful contributors. Specifically, we evaluate only entries in Ω = {(i, j) : |Φ⋆i,j | > 10−3 }. • Spearman rank correlation ρ. We compute 

 b Ω , rank Φ⋆ , ρ = corr rank Φ Ω which measures whether a method preserves the relative ordering of Shapley values. • Pearson correlation r. We compute  
P ¯ b b Φ⋆i,j − Φ̄⋆ (i,j)∈Ω Φi,j − Φ r=r ,   q
2 P ¯ 2 P ⋆ ⋆ b b (i,j)∈Ω Φi,j − Φ (i,j)∈Ω Φi,j − Φ̄ ¯ b where Φ and Φ̄⋆ are the averages over Ω. Pearson r measures calibration, i.e., linear agreement between estimated and reference values. • Wall-clock time T . Following [50], we report wall-clock time T in seconds, defined as the time required to process an arriving task or training instance. This metric evaluates update efficiency. Implementation details. We use high-budget Global-MC recomputation as the reference for evaluating the quality of all baselines. Following [16], all Monte Carlo methods use the same stopping criterion and are capped at 5,000 samples. Every 100 samples, we compare the current estimates with those from the previous batch and stop if (m)

(m−100)

1 X |ϕi − ϕi | < 0.05. (m) −12 n i |ϕ | + 10 i

22

Table 8: Effect of support set size |N (t)|. Task-Incremental |N (t)| ρ r T (10−4 s)

2 0.9053 0.7957 39.7

4 0.9078 0.8121 40.0

6 0.9088 0.8181 40.0

8 0.9079 0.8186 40.0

10 0.9075 0.8189 40.5

12 0.9066 0.8179 40.7

14 0.9059 0.8167 40.9

16 0.9047 0.8147 41.1

18 0.9036 0.8128 41.2

20 0.9029 0.8112 41.3

10 0.8649 0.8995 28.1

15 0.8696 0.9228 42.2

20 0.8745 0.9329 58.7

25 0.8789 0.9391 76.4

30 0.8836 0.9441 97.9

35 0.8886 0.9476 122.0

40 0.8918 0.9500 148.8

45 0.8944 0.9529 179.9

50 0.8975 0.9554 203.2

Player-Incremental |N (t)| ρ r T

5 0.8589 0.8065 16.1

Table 9: Effect of the anchor ratio k/n on self-valuation build time and valuation quality. k/n

0.20

0.40

0.60

0.80

1.00

ρ r T

0.6297 0.4735 29.8

0.8923 0.7559 59.6

0.9018 0.7965 89.4

0.9067 0.8126 119.2

0.9090 0.8189 149.0

This criterion corresponds to an average relative change below 5%. Each experiment is repeated with five independent random seeds, and we report the average performance. All experiments are conducted on a single machine with 64 Intel Xeon E5-2640 v4 CPUs and 64 GB RAM. For GNN and CNN workloads, we additionally use four NVIDIA RTX A5000 GPUs. D.2

Further Analysis of Model-Induced Locality

While the previous results evaluate the model-induced distance dΓ and support-set alignment, we further analyze the sensitivity of the local support N (t) to its size. The support size |N (t)| determines the size of the local coalition game. We sweep |N (t)| on WKNNs under both task-incremental and player-incremental settings, as shown in Table 8. In the task-incremental setting, quality saturates quickly: ρ peaks at 0.9088 when |N (t)| = 6 and changes only slightly as the support grows, while T remains nearly constant at around 4 × 10−3 s, approximately 4 ms. This indicates that taskincremental interpolation requires only a small neighborhood once the effective local structure is captured. In contrast, player-incremental quality improves steadily with larger support sets, with ρ increasing from 0.8589 at |N (t)| = 5 to 0.8975 at |N (t)| = 50. However, this improvement comes with a clear cost increase, as T grows from 16.1 seconds to 203.2 seconds. These results suggest different operating points for the two regimes: a small support, around |N (t)| = 6, is sufficient for task-incremental updates, whereas player-incremental updates benefit from larger supports, with |N (t)| ∈ [25, 35] providing a practical quality-cost trade-off. D.3

Anchor Selection Trade-off for Self-Valuation Matrix

Self-valuation construction admits a quality–efficiency trade-off controlled by the anchor ratio k/n: smaller anchor ratios reduce the number of columns to precompute and maintain, but provide weaker coverage for task interpolation under Theorem 1. We sweep k/n from 0.20 to 1.00 on WKNNs and report build time together with task-incremental valuation quality, measured by Pearson r and Spearman ρ against the full-budget Global-MC reference. Table 9 shows a clear trade-off between construction cost and valuation quality. Build time grows linearly with k/n, as expected from the per-anchor cost of shared subset scheduling, with each 0.20 increment adding about 30 seconds. Quality, in contrast, saturates quickly: ρ rises from 0.6297 at k/n = 0.20 to 0.8923 at 0.40, while r increases from 0.4735 to 0.7559. Beyond this point, additional anchors yield smaller gains, with ρ improving by less than 0.02 as k/n increases from 0.40 to 1.00. This pattern is consistent with the coverage analysis: once anchors are sufficiently dense under dΓ , most incoming tasks can be interpolated from nearby precomputed columns, and additional anchors mainly refine an already stable estimate. In practice, k/n ∈ [0.4, 0.6] offers a favorable operating point, achieving near-saturated valuation quality at 40–60% of the full-budget construction cost. 23

E

Additional Cases for Shapley Matrix Maintenance

D-Shap also supports deletion, replacement, and simultaneous task–player updates under the same matrix-maintenance principle. The key idea is to treat each dynamic event as a localized update of the player-by-task Shapley matrix Φ: task-side changes modify columns, while player-side changes modify rows and only the local blocks whose support sets change. Task deletion and replacement. For task-side changes, deleting a task t simply removes its corresponding column Φ:,t from Φ. Since the player set and all other task utilities remain unchanged, no other entries need to be updated. Replacing a task t with a new task t̃ can be handled as deletion followed by insertion: D-Shap first removes the old column Φ:,t and then estimates the new task valuation ϕ̂(t̃) using the interpolation rule in Eq. (6). Thus, task replacement only changes one column of the maintained matrix. Player deletion and replacement. For player-side changes, deleting a player z removes its row from Φ and updates only tasks whose local support changes. Let N (t) and N − (t) denote the support set of task t before and after deleting z, respectively. The affected task set is R− (z) = {t ∈ T : N − (t) ̸= N (t)}. For any t ∈ / R− (z), coalition locality implies that the remaining entries are unchanged. For any − t ∈ R (z), D-Shap recomputes only the local game induced by N − (t) and reuses all entries outside the affected local block. In particular, players in N − (t) are revalued under the updated local game, players removed from the support receive zero contribution, and players outside N (t)∪N − (t) remain unchanged. Replacing a player z with z̃ is handled as deletion followed by insertion. D-Shap first deletes the row corresponding to z, updates the tasks in R− (z), and then inserts z̃ as a new player using the player-incremental update rule in Section 3. Equivalently, the affected task set is the union of the tasks affected by deletion and insertion: R(z → z̃) = {t ∈ T : N − (t) ̸= N (t)} ∪ {t ∈ T : N + (t) ̸= N − (t)}, where N + (t) is the support set after inserting z̃. D-Shap updates only the local games associated with tasks in R(z → z̃) and reuses all other entries. Simultaneous task and player arrivals. In practice, new tasks and new players may arrive at the same time. Let ∆T denote the newly arriving tasks and ∆D denote the newly arriving players. A simple strategy is to process the two updates sequentially. D-Shap first applies the player update to obtain the expanded player set D+ = D ∪ ∆D and the updated matrix over existing tasks. It then estimates the columns for new tasks in ∆T under the updated player set D+ . This order is preferable when accuracy is prioritized, because the valuation of a new task should be defined with respect to the current player set, including newly arrived players. If task interpolation were performed before inserting new players, the resulting new columns would be estimated under the old game and would still need to be corrected for the newly added players. More concretely, D-Shap performs the following two-stage update: player update on ∆D

task update on ∆T

Φ −−−−−−−−−−−→ Φ+ −−−−−−−−−→ Φ+ D,T − D + ,T ∪∆T . The first stage updates only the affected columns R(∆D) = {t ∈ T : N + (t) ̸= N (t)}, where N + (t) is computed after inserting ∆D. The second stage estimates each new task column ϕ̂(t′ ) for t′ ∈ ∆T using neighboring columns from the already updated matrix Φ+ D,T . Thus, the interpolation anchors and the resulting task valuations are consistent with the expanded player set. Joint local update for higher efficiency. When ∆T and ∆D are both small, the sequential update is already efficient. However, for larger update batches, D-Shap can further improve efficiency by using a joint affected-block update. Instead of first updating all affected old tasks and then estimating all new tasks independently, D-Shap forms the joint affected task set Rjoint (∆D, ∆T ) = R(∆D) ∪ ∆T. 24

For each t ∈ Rjoint (∆D, ∆T ), D-Shap constructs the updated support N + (t) under the expanded player set D+ . It then recomputes exact local Shapley values only when necessary, namely when the task is poorly covered by existing anchors or when the support change is large. Otherwise, it estimates the column by interpolation from updated neighboring columns. This gives the following update rule: ( LocalShapley(N + (t), t), mina∈A dΓ (t, a) > τ or |N + (t)△N (t)| > κ, + ϕ̂ (t) = P + otherwise, a∈A(t) w(t, a)ϕ (a), where A(t) denotes the neighboring anchor tasks under dΓ , τ is the coverage threshold, and κ controls when support changes are large enough to justify explicit local recomputation. This joint strategy improves efficiency by avoiding duplicate work. If a new player changes the support of a task that is also used as an interpolation anchor for new tasks, D-Shap updates that anchor once and reuses it for all downstream task interpolations. It can also improve quality because new task columns are interpolated from columns that have already been made consistent with the updated player set. Thus, simultaneous task and player arrivals are handled as a single localized maintenance operation over the affected block of Φ, rather than as global recomputation. Summary. Task addition, deletion, and replacement correspond to adding, removing, or replacing columns of Φ. Player addition, deletion, and replacement correspond to adding, removing, or replacing rows, together with localized recomputation over tasks whose support sets change. When task and player updates occur simultaneously, D-Shap processes player updates first for consistency, or uses a joint affected-block update for better efficiency. Therefore, common dynamic cases are unified as localized maintenance of the player-by-task Shapley matrix.

25

F

Pseudocode

Algorithm 1 Task-Incremental Valuation ′ Require: Players D; anchors A; Shapley matrix ΦD A ; distance dΓ ; new task t ; neighborhood size K. 1: Find the K nearest anchors ′ ′ AK (t ) = KNNa∈A (t ; dΓ ). P ′ ′ ′ 2: Compute convex weights w(t , a) over AK (t ) with w(t , a) ≥ 0 and a∈AK (t′ ) w(t′ , a) = 1. 3: Estimate X ′ D bD (t′ ) = ϕ w(t , a) ΦA [:, a]. a∈AK (t′ )

bD (t′ ). 4: return ϕ

Algorithm 2 Player-Incremental Valuation ′ Require: Training players D; anchor set A; Shapley matrix ΦD A ; support extractor N (·); local utility va (·); new player z . +

1: Set D+ ← D ∪ {z ′ } and initialize ΦD by appending a zero row (for z ′ ) to ΦD A A. 2: Compute N (a) ⊆ D and N + (a) ⊆ D+ for each a ∈ A, and identify affected anchors ′

+

R(z ) = {a ∈ A : N (a) ̸= N (a)}. +

+

D ′ 3: For a ∈ / R(z ′ ): keep ΦD A [ · , a] unchanged; ΦA [z , a] is already 0 from line 1. 4: for each a ∈ R(z ′ ) do + + 5: Set ΦD A [z, a] ← 0 for z ∈ N (a). + 6: Set ΦD [z, a] ← 0 for z ∈ N (a) \ N + (a). A 7: for all subsets S ⊆ N + (a) do 8: Evaluate va (S). 9: for all z ∈ N + (a) do 10: if z ∈ S then va (S) + 11: ΦD A [z, a] +=
+

|N + (a)| ·

12: 13: 14:

|N

(a)|−1 |S|−1

else +

ΦD A [z, a] −=

va (S) |N + (a)| ·

|N + (a)|−1
|S|

+ return ΦD A .

Algorithm 3 Self-Valuation Matrix Construction via Shared Subset Scheduling Require: Training players D = {z1 , . . . , zn }; model-induced distance dΓ ; anchor budget k; local utility va (·). 1: Select anchors A = {a1 , . . . , ak } ⊆ D by farthest-point sampling under dΓ , fixing an ordering ΠA . n×k D 2: Initialize ΦD with ΦD A ∈ (R ∪ {NA}) A [a, a] ← NA for a ∈ A and ΦA [z, a] ← 0 otherwise. 3: for each anchor a ∈ A in order ΠA do 4: for all subsets S ⊆ D \ {a} do 5: RS ← A \ S 6: a∗ ← first anchor in RS under ΠA 7: if a = a∗ then 8: Train θ(S) and evaluate va′ (S) for all a′ ∈ RS 9: for all a′ ∈ RS do 10: for all z ∈ D \ {a′ } do 11: if z ∈ S then va′ (S) ′ 12: ΦD A [z, a ] += n−2
(n − 1) · |S|−1 13: else va′ (S) ′ 14: ΦD
A [z, a ] −= (n − 1) · n−2 |S|

15: return A, ΦD A.

26

Algorithm 4 Online Anchor Expansion ′ Require: Anchor set A with ordering ΠA ; matrix ΦD A ; distance dΓ ; expansion threshold τ ; incoming task t . 1: Compute coverage radius r(t′ ; A) = mina∈A dΓ (t′ , a). 2: if r(t′ ; A) ≤ τ then bD (t′ ) by Algorithm 1. 3: Estimate ϕ 4: else 5: Compute ϕD (t′ ) by exact or high-budget estimation. ′ ′ 6: Append ϕD (t′ ) as a new column to ΦD A ; set A ← A ∪ {t } and append t to ΠA . D ′ 7: return A, ΦA , valuation for t .

27

Related documents

• String Diagrams for Process Mining#978502
• ZigZag Trie: A Novel Index for Contextual Queries#978503
• A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval#978504
• Efficiently Linking Unstructured Data for Multi-step Reasoning#978505