{"id":"416de036-9b57-4fd6-8eef-49b793f08867","arxiv_id":"2507.01267","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"The paper defines counterfactual explanations for Shapley values in data coalitions and proposes SV-Exp, a greedy algorithm that efficiently finds small data transfers to flip the value ranking.","lead":"This paper asks which data records make one data seller's Shapley value higher than another's, and finds the smallest set of records that, if transferred, would flip the ranking. The authors show the problem is computationally hard and propose a greedy algorithm, SV-Exp, that can approximate such 'counterfactual explanations' quickly on real datasets.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's NP-hardness proof uses a non-monotone utility, contradicting the paper's own monotonicity assumption; the existence guarantee and the experiments therefore cover different settings.","rationale":"The paper has real substance: the differential-Shapley formula (Theorem 3) is correct, the Monte Carlo estimators are unbiased, the greedy framework is clearly specified, and the artifact is public. My objection is not that the heuristics fail; it is that the theoretical wrapper around them is internally inconsistent. The monotonicity assumption is what makes counterfactuals always exist (Proposition 2), and the paper explicitly adopts it. The NP-hardness reduction in Theorem 1, however, defines a utility that strictly decreases when a redundant set-cover element is added, so the theorem is proved for a non-monotone problem and does not establish hardness for the paper's own problem. Because the experimental utility functions are raw errors/losses, they too are outside the monotone regime; the existence guarantee does not transfer to the experiments. These are fixable: one can either prove hardness for monotone utilities, or explicitly scope the theory to non-monotone utilities and re-validate. Since the reader's verdict was already conditional on essentially this concern, my stress-test does not move it.","tokens_in":22957,"tokens_out":15682,"duration_ms":183186,"concrete_test":"Analytical check: re-derive Theorem 1 under monotonicity by replacing the cover-based U with a monotone utility (e.g., U(S)=|∪_{S_i∈S}S_i| or the monotone closure U*(S)=max_{T⊆S}U(T)) and test whether a minimal counterfactual still encodes a minimum set cover. If no monotone reduction is produced, the theorem should be restated as NP-hard only for non-monotone utilities, and the experimental claims should be re-run with U* to see whether success rates and counterfactual sizes survive.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2 states 'we from now on assume that the utility function is monotonic.' Proposition 2 (feasibility) uses this assumption to show that transferring all of A leaves ψ(A\\ΔA)=0 and ψ(B∪ΔA)>0. Theorem 1 (NP-hardness) then constructs U(S)=0 if ∪_{S_i∈S}S_i≠D and U(S)=m-|S|+f(S) otherwise. This U is not monotone: for a cover S and any redundant x, U(S∪{x})=m-|S|-1+f(S)+2^{i_x}/2^{m+1} < m-|S|+f(S)=U(S), because 2^{i_x}/2^{m+1}≤1/2. Adding data decreases utility, so the reduction is outside the problem class for which existence was proved. Thus the hardness of the exact counterfactual-explanation problem under monotone utilities is not established. The empirical utilities (η minus test error or log loss) are also not monotone and are not replaced by the monotone closure U*(D)=max_{D'⊆D}U(D') mentioned in Section 2. The central claim's two theoretical pillars therefore rest on incompatible assumptions, and the experiments inherit the same mismatch.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the counterfactual explanation of the Shapley value in data coalitions: given two data owners A and B with psi(A) > psi(B), it seeks a smallest subset of A's data whose transfer to B reverses the inequality. The paper claims that such an explanation always exists under monotone utilities, that finding the exact explanation is NP-hard, and it develops a differential-Shapley estimator and a greedy algorithm (SV-Exp) with Thompson sampling to approximate the explanation. Experiments on three datasets compare runtime and success rates against a Monte Carlo baseline and include two case studies on feature selection and distributional differences.","tokens_in":23206,"tokens_out":15471,"duration_ms":188129,"significance":"The problem is novel and practically motivated, and the differential-Shapley machinery in Theorems 3--5 and Corollaries 1--2 is a clean technical contribution: the direct estimators of the difference between two owners' Shapley values are unbiased and avoid estimating each value separately. The two case studies show that the proposed counterfactual can yield interpretable insights. However, the paper's central theoretical claim is not coherent as written: the NP-hardness reduction in Theorem 1 uses a non-monotone utility, contradicting the paper's own standing monotonicity assumption, and the experimental utilities are also non-monotone. These issues are load-bearing because feasibility (Proposition 2) and the intended problem setting both depend on monotonicity.","major_comments":[{"comment":"The NP-hardness reduction in Theorem 1 constructs a utility U(S) = 0 for non-covers and U(S) = m - |S| + f(S) for covers. This utility is not monotone: for a cover S and a redundant element x, U(S union {x}) = m - |S| - 1 + f(S) + 2^{i_x}/2^{m+1} < m - |S| + f(S) = U(S), since 2^{i_x}/2^{m+1} <= 1/2. This directly contradicts the monotonicity assumption stated immediately before the theorem ('we from now on assume that the utility function is monotonic'). Consequently, the reduction establishes hardness only for a larger class of arbitrary utilities, not for the monotone problem whose feasibility is guaranteed by Proposition 2. The theorem should be reworked for the monotone setting (for example, by reasoning about the monotone closure U*(D) = max_{D' subset of D} U(D') mentioned in Section 2) or the paper must explicitly restrict the NP-hardness claim to non-monotone utilities and qualify the abstract accordingly.","section":"Section 2, Theorem 1"},{"comment":"The experimental utilities are defined as eta minus test error, log loss, or MSE. Such utilities are not monotone in general, and the experiments do not replace them by the monotone closure U*(D) = max_{D' subset of D} U(D') that Section 2 invokes to justify the monotonicity assumption. Therefore the feasibility guarantee of Proposition 2 and the interpretation of the outputs as minimal transferring subsets are not theoretically supported in the evaluation. Moreover, the success-rate measurements in Table 4 and Figure 5 use a Monte Carlo estimate of the final differential Shapley value; under a non-monotone utility a true feasible counterfactual may not even exist, so a 'failure' can reflect nonexistence rather than algorithmic error. The experiments should either use utility functions that are monotone (or explicitly use the monotone closure) or be reframed as heuristic evidence for arbitrary utilities without invoking Proposition 2.","section":"Section 4.1 (with Section 2)"}],"minor_comments":[{"comment":"Algorithm 1 loops over i = 1 to |A|-1 and has no fallback return. Since Proposition 2 guarantees that Delta_A = A is always feasible, the pseudocode should end with an explicit 'return A', as Algorithm 2 does.","section":"Section 2, Algorithm 1"},{"comment":"Algorithm 3 can exit its while loop without returning a counterfactual (for example, if the estimated differential d is converged and positive). The intended behavior should be clarified, and the convergence criterion for d should be defined precisely rather than left as 'converged'.","section":"Section 3.4, Algorithm 3"},{"comment":"The proof of Proposition 2 asserts that because B union Delta_A is nonempty, its Shapley value is positive. Nonemptiness alone does not imply a positive Shapley value under monotonicity, since a nonempty owner can still be a dummy; the argument should instead use the fact that psi(A) > 0 ensures some positive marginal contribution from A's data, which then implies a positive marginal for the enlarged owner.","section":"Section 2, Proposition 2"},{"comment":"There are several typographical errors: 'trail' should be 'trial' in Section 4.2, 'Wassertein' should be 'Wasserstein' in Section 4.7, and 'nueral networks' in reference [8] should be 'neural networks'.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"I agree with the stress-test concern: the monotonicity mismatch in Theorem 1 is real and affects the central theoretical claim, and the experimental setup inherits the same mismatch. The differential-Shapley results are solid and the algorithmic idea is promising, so the issue is plausibly fixable by reworking the hardness proof or carefully scoping the problem statement. I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know upfront: this paper is worth reading as an applied contribution, but don't take the complexity theorem at face value. The problem—finding a smallest subset of data that, when transferred from a higher-Shapley owner to a lower-Shapley owner, flips the Shapley ordering—is genuinely new. The differential Shapley estimator is a clean variation of Jia et al.'s lemma, and the SV-Exp greedy algorithm plus case studies on feature selection and distribution shift are a real practical contribution. The code and data are released, so the empirical part is reproducible.\n\nWhere it gets soft: Theorem 1 claims NP-hardness by reduction from set cover, but the constructed utility is U(S)=m-|S|+f(S) when S is a cover. That function strictly decreases when you add a redundant element. The paper explicitly assumes monotone utilities in Section 2 and uses that to prove existence (Proposition 2). So the reduction is outside the problem class the paper actually studies. The hardness of the counterfactual explanation problem under monotone utilities is not established. This is not a nitpick—it's the main theoretical pillar. The experiments inherit the same mismatch: utility is eta minus error or log loss, which is not monotone, and the paper doesn't apply the monotone closure it mentions. In practice that's fine and arguably more realistic, but it means the experiments and the existence guarantee live in different worlds.\n\nThe success check in Section 4.5 uses a fresh Monte Carlo estimate of the differential Shapley value. That's a reasonable sanity check, not true circularity, but it's still an estimate, not ground truth, for the large datasets. The paper acknowledges this.\n\nOverall, the problem is well motivated and the algorithmic machinery is sound for what it does. The theoretical claims need reworking—either prove NP-hardness under monotone utilities (the reduction may be repairable) or explicitly reframe the problem for non-monotone utilities. The authors should also address the utility mismatch in the experiments.\n\nFor a reading group on data valuation or explainability, it's a decent discussion piece. For a referee, I'd send it back with major revision, focusing on the complexity claim and the monotonicity issue. It doesn't deserve a desk reject; the practical value is real.","headline":"New problem and a useful heuristic, but the NP-hardness proof uses utilities that violate the paper's own monotonicity assumption, so the theory as stated is not airtight.","tokens_in":23721,"tokens_out":2176,"would_cite":true,"duration_ms":129487,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A12","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that the Shapley-value gap between two data owners always admits a smallest record-transfer that flips the ranking, that finding it is NP-hard, and that the SV-Exp algorithm approximates it.","keywords":["Shapley value","data valuation","counterfactual explanation","data coalition","NP-hardness","Monte Carlo estimation","differential Shapley value","greedy algorithm"],"falsifier":"Enumerate all monotone utility functions over a small universe of data entries (say, all non-decreasing set functions on four entries) and check, by exact Shapley computation, every pair $A,B$ with $\\psi(A) > \\psi(B)$ to see whether a transfer $\\Delta_A$ that flips the inequality always exists; finding one monotone instance with no flip would refute Proposition 2. The same search can test whether the NP-hardness reduction's survival of the monotone assumption matters, since that reduction's own utility is non-monotone.","tokens_in":22751,"feed_emoji":"📊","tokens_out":15612,"duration_ms":151863,"temperature":0.7,"pith_summary":"In a data coalition, each owner's Shapley value measures their expected contribution, but it does not say which records drive the difference between two owners. This paper defines a counterfactual explanation as the smallest subset of the higher-valued owner's records that, when transferred to the lower-valued owner, makes the lower-valued owner's Shapley value exceed the higher one. Under a monotone utility function, the paper proves such an explanation always exists, yet finding the exact minimum-size transfer is NP-hard. It then derives a differential Shapley identity that estimates the gap between two owners directly, and builds SV-Exp, a Thompson-sampling greedy algorithm that moves the most powerful record at a time until the ranking flips. Experiments on real datasets and two case studies indicate that the approximations flip rankings efficiently and that the transferred records carry interpretable meaning, such as which features or data distributions create the advantage.","feed_headline":"Finding smallest data transfer that flips Shapley values is NP-hard","feed_subtitle":"SV-Exp greedily moves the most powerful records until the ownership ranking flips, using Monte Carlo sampling.","key_machinery":"The load-bearing identity is the differential Shapley value, $\\Psi_O(A,B) = \\psi_O(A) - \\psi_O(B)$, which Theorem 3 expresses as a weighted sum over coalitions $S$ containing neither $A$ nor $B$ of the utility differences $U(S \\cup \\{A\\}) - U(S \\cup \\{B\\})$. This identity turns a two-owner comparison into a single object, permits an unbiased Monte Carlo estimate from random permutations (Corollary 2), and defines the power of a data entry $x$: the expected change in the differential when $x$ is moved from $A$ to $B$. SV-Exp uses Thompson sampling to pick the entry currently estimated to have the largest power, moves that entry, and repeats until the estimated differential goes negative.","core_discovery":"The central claim is that the difference in Shapley value between two data owners $A$ and $B$, with $\\psi(A) > \\psi(B)$, can be explained counterfactually: there is always at least one subset $\\Delta_A \\subseteq A$ whose transfer to $B$ makes $\\psi(A \\setminus \\Delta_A) < \\psi(B \\cup \\Delta_A)$, and the smallest such subset is a well-defined but NP-hard optimization problem. The existence proof rests on monotonicity, because moving all of $A$ empties it to Shapley value $0$ while $B$ gains $A$'s records and remains positive. The NP-hardness proof reduces the set cover problem to the search for a minimum flipping subset. To make the problem tractable, the paper proves that the differential Shapley value $\\Psi(A,B) = \\psi(A) - \\psi(B)$ can be written as a weighted sum over coalitions containing neither owner, gives an unbiased permutation-based Monte Carlo estimator for it, and introduces the power of a data entry—the estimated drop in the differential when that record moves—so that a greedy iteration can assemble an approximate counterfactual. The resulting SV-Exp algorithm is demonstrated to beat a Monte Carlo subset-search baseline in runtime and flip success rate, and its outputs are shown to behave as feature selection and distribution-difference detectors.","pith_inferences":["Beyond the paper: if monotonicity fails—as it does for raw model-error utilities—the existence guarantee collapses, so SV-Exp's outputs on such utilities should be read as empirical heuristics rather than theorem-backed explanations.","Beyond the paper: records that repeatedly appear in small counterfactuals are candidate 'star' rows, so the power ranking could be reused as a data-pricing signal in markets that want to charge more for high-marginal-value data.","Beyond the paper: the greedy transfer framework extends to deletion-only variants (the paper notes this) and to other cooperative valuation schemes such as beta Shapley, but each extension requires re-deriving the differential identity.","Beyond the paper: the case study's finding that a less-correlated feature is chosen over a more-correlated one predicts that counterfactual explanations act as a multicollinearity-aware selection rule, a claim testable on synthetic data with controlled correlations."],"forward_implications":["Under a monotone utility, every pair of unequal owners has at least one feasible counterfactual explanation, so the search is over how small the transfer can be, not whether one exists.","Because exact minimization is NP-hard, practical deployments must approximate, and SV-Exp supplies a greedy sampling-based candidate that the experiments show flips rankings faster than a Monte Carlo subset-search baseline.","Estimating the differential Shapley value directly removes the need to estimate two Shapley values separately and subtract them, reducing sampling cost and error.","The size of a counterfactual carries semantic content: a small set of records signals that a few 'star' records dominate an owner's advantage, while a large set signals a distributed advantage.","The same machinery can be applied as a feature-selection heuristic and as a detector of distributional differences between data owners, as the two case studies demonstrate."],"supporting_citations":[{"why":"This reference defines the Shapley value and its axiomatic basis, which is the valuation measure being explained.","marker":"[52]"},{"why":"This reference supplies the efficient differential-valuation lemma that Theorem 3 adapts into the direct differential Shapley identity.","marker":"[28]"},{"why":"This reference provides the set-cover NP-hardness result used to prove that exact counterfactual explanation is NP-hard.","marker":"[30]"},{"why":"This reference establishes that exact Shapley computation is #P-hard, motivating the Monte Carlo and greedy approximations.","marker":"[14]"},{"why":"These references provide Thompson sampling, which SV-Exp's Phase 1 uses to find the highest-power data entry.","marker":"[50, 55, 56]"},{"why":"This reference supplies the Breast Cancer Wisconsin dataset used in the main efficiency and accuracy experiments.","marker":"[63]"}],"fun_headline_variants":["Smallest data transfer to flip Shapley values? NP-hard","SV-Exp: greedy heuristic for Shapley counterfactuals","NP-hard to find smallest data subset that flips Shapley rankings","Counterfactual Shapley: minimal data shift is NP-hard"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the utility function is monotone—adding more data never lowers a coalition's utility—and that is what guarantees a counterfactual explanation always exists; the paper's own NP-hardness reduction uses a utility that drops when a redundant element is added to a cover, and the experimental utilities are raw model errors, so outside the monotone regime feasibility and the interpretation of SV-Exp's outputs are not theoretically supported.","fun_headline_variants_meta":{"raw":{"variants":["Smallest data transfer to flip Shapley values? NP-hard","SV-Exp: greedy heuristic for Shapley counterfactuals","NP-hard to find smallest data subset that flips Shapley rankings","Counterfactual Shapley: minimal data shift is NP-hard"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001003,"raw_usage":{"total_tokens":4308,"prompt_tokens":1075,"completion_tokens":3233,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":691,"completion_tokens_details":{"reasoning_tokens":3158}},"tokens_in":691,"tokens_out":3233,"duration_ms":25154,"temperature":1.0,"reasoning_tokens":3158,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:57:23.809493+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all monotone utility functions over a small universe of data entries (say, all non-decreasing set functions on four entries) and check, by exact Shapley computation, every pair $A,B$ with $\\psi(A) > \\psi(B)$ to see whether a transfer $\\Delta_A$ that flips the inequality always exists; finding one monotone instance with no flip would refute Proposition 2. The same search can test whether the NP-hardness reduction's survival of the monotone assumption matters, since that reduction's own utility is non-monotone.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"This reference defines the Shapley value and its axiomatic basis, which is the valuation measure being explained."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"This reference supplies the efficient differential-valuation lemma that Theorem 3 adapts into the direct differential Shapley identity."}],"review_version":1}