🤖 machine learning

Priority-Aware Shapley Value

This paper introduces Priority-Aware Shapley Value (PASV), a novel framework that extends traditional Shapley values by incorporating hard precedence constraints and soft priority weights to better handle dependent contributors and trust factors, supported by an efficient sampling algorithm and validated through experiments on data valuation and feature attribution tasks.

Original authors: Kiljae Lee, Ziqi Liu, Weijing Tang, Yuan Zhang

Published 2026-06-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kiljae Lee, Ziqi Liu, Weijing Tang, Yuan Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a massive potluck dinner where everyone brings a dish, and the goal is to figure out exactly how much each person contributed to the deliciousness of the final feast. In the world of machine learning, this "potluck" is a model trained on data, and the "dishes" are individual data points or features.

For decades, scientists have used a mathematical tool called the Shapley Value to split the credit fairly. The traditional rule is simple: imagine every possible order in which people could arrive at the party. If you arrive first, you get credit for the whole table. If you arrive last, you only get credit for what you added to the already-full table. The Shapley Value averages your contribution across all possible arrival orders.

The Problem: The "Interchangeable" Assumption
The old method assumes everyone is interchangeable. It treats the potluck as if it doesn't matter who brings the salad first or who brings the cake last. But in real life, this isn't true.

Hard Precedence (The "Recipe" Rule): Sometimes, you must bring the dough before you can bring the pizza toppings. If you try to add toppings before the dough, the pizza is ruined. In data terms, some data is "copied" from other data, or some features (like age) must logically come before others (like occupation). The old method ignores these rules, allowing impossible scenarios (like toppings before dough) to skew the results.
Soft Priority (The "VIP" Rule): Sometimes, we trust some guests more than others. Maybe one guest is a famous chef (high trust), while another is known for bringing burnt toast (low trust/risk). The old method treats them equally, just because they arrived at different times. We need a way to say, "We trust the chef's contribution more," without changing the recipe rules.

The Solution: Priority-Aware Shapley Value (PASV)
The authors propose a new method called PASV. Think of it as a smarter potluck planner that understands two things:

The Hard Rules (The DAG): It respects the "recipe." It knows that the dough must come before the toppings. It only considers arrival orders that make sense (e.g., no toppings before dough).
The Soft Weights (The VIPs): It knows that some guests are more "trustworthy" or "risky." It adjusts the math so that high-trust guests are more likely to be evaluated in contexts where their true value shines, while risky guests are evaluated more carefully to see if they actually add value or just noise.

How It Works (The Creative Analogy)
Imagine you are trying to judge a team of detectives solving a mystery.

The Old Way: You ask every possible order of detectives to solve the case. You average their success. But this is unfair if Detective A must find the clue before Detective B can solve the puzzle. The old method counts scenarios where B tries to solve it first, which is impossible.
The PASV Way:
- Hard Priority: You only let the detectives solve the case in orders that respect the clues (A before B).
- Soft Priority: You have a "trust meter" for each detective. If Detective C is a known liar (high risk), PASV doesn't just ignore them; it simulates scenarios where they arrive later in the investigation. This tests: "If we already have solid evidence, does this liar's clue actually help, or does it confuse things?" If they are a genius (high trust), PASV tests them in rich contexts to see their full potential.

The "Priority Sweeping" Tool
One of the coolest features of PASV is a diagnostic tool the authors call "Priority Sweeping."
Imagine you are the manager of the potluck. You aren't sure how much to trust the guest who brought the "mystery casserole."

With PASV, you can run a simulation: "What happens to the credit score if I treat this guest as a 'Super VIP' (max trust)?" Then, "What if I treat them as 'High Risk' (min trust)?"
By sliding a slider from "Total Trust" to "Total Distrust," you can see if their contribution score stays steady or crashes. If it crashes, you know their value is unstable and depends heavily on how much you trust them. This helps you make safer decisions about who to invite next time.

What the Paper Actually Found
The authors tested this on two main scenarios:

Data Valuation (The Potluck): They simulated a data market where some data was original, some was copied, and some was "poisoned" (bad data).
- The old methods gave credit to the "copiers" because they didn't realize the data was just a copy.
- PASV correctly penalized the copiers and the "poisoners," giving more credit to the original sources, especially when the "trust" settings were adjusted.
Feature Attribution (The Detective Team): They analyzed a dataset predicting income.
- They showed that the way you order the features (e.g., does age come before education?) changes the results.
- PASV allowed them to see which features were robust (their value didn't change much no matter the trust level) and which were unstable (like "native country," which swung wildly depending on the settings).

In Summary
PASV is a new way to fairly split credit in machine learning. It fixes the old method's blindness to rules (you can't have toppings before dough) and trust (some data is riskier than others). It gives us a tool to not just get a single answer, but to stress-test our decisions by asking, "How much does my trust in this data point actually change the outcome?"

Technical Summary: Priority-Aware Shapley Value (PASV)

Problem Statement

Shapley values are the standard tool for model-agnostic data valuation and feature attribution, relying on the axiom that contributors (players) are interchangeable. This assumption requires averaging marginal contributions over all possible permutations of players. However, in modern machine learning applications, this exchangeability is often invalid for two primary reasons:

Precedence Constraints: Contributors may exhibit hard precedence relations. For instance, training data may be augmented or copied from upstream sources (making downstream contributions derivative), or domain knowledge may dictate that certain features (e.g., causal ancestors) must be considered before others. Existing methods like Precedence Shapley Value (PSV) handle these constraints but treat all valid linear extensions uniformly, ignoring individual differences.
Soft Priority Weights: Practitioners often have context-specific considerations such as trust, risk, or curation costs. For example, a data point might be less trusted or carry higher legal risk. Existing Weighted Shapley Value (WSV) methods incorporate such weights but are restricted to specific structural assumptions (ordered partitions) and cannot handle general Directed Acyclic Graphs (DAGs).

Current approaches typically address hard precedence and soft weights in isolation. There is a lack of a unified framework that simultaneously incorporates general precedence constraints and player-specific priority weights while remaining computationally feasible.

Methodology: Priority-Aware Shapley Value (PASV)

The authors propose Priority-Aware Shapley Value (PASV), a unified Shapley-type attribution method that integrates both hard precedence constraints and soft priority weights within a single random-order framework.

1. Theoretical Formulation

PASV defines the value of player $i$ as the expected marginal contribution over a distribution $p$ supported on the set of linear extensions $\Pi_{\preceq}$ of a poset (or DAG) $([n], \preceq)$ . The distribution $p$ is constructed to satisfy:

Hard Priority: The support is restricted to $\Pi_{\preceq}$ , ensuring no permutation violates the precedence constraints.
Soft Priority: Among admissible candidates at any step of the permutation construction, the selection probability is biased by player-specific weights $\lambda = (\lambda_1, \dots, \lambda_n)$ .

The probability of a permutation $\pi = (\pi_1, \dots, \pi_n)$ is given by:
$p^{(\preceq, \lambda)}(\pi) \propto \prod_{t=1}^n \frac{\lambda_{\pi_t} |\max_{\preceq}(S_t)|}{\sum_{k \in \max_{\preceq}(S_t)} \lambda_k}$
where $S_t = \{\pi_1, \dots, \pi_t\}$ is the set of players selected so far, and $\max_{\preceq}(S_t)$ denotes the set of maximal elements in $S_t$ (the admissible candidates for the next position).

2. Axiomatic Characterization

The paper provides a rigorous axiomatic characterization that uniquely identifies PASV. The derivation proceeds through:

Precedence Random Order Value (PROV): A family of values satisfying Efficiency, Linearity, Null Player, Monotonicity, and Maximal Support (credit only goes to maximal elements in feasible sets).
State-Choice Factorization (SCF): Restricting the distribution to a factorized form where the probability of a permutation is the product of a "state" factor (global bias from the DAG) and a "choice" factor (local bias from weights).
Boundary Axioms:
- Weight Proportionality (WP): Selection probabilities among admissible candidates are proportional to their weights $\lambda$ .
- Equal-Weight Uniformity (EWU): If all weights are equal, the distribution reduces to the uniform distribution over $\Pi_{\preceq}$ (recovering PSV).
  The combination of PROV, SCF, WP, and EWU uniquely yields PASV.

3. Limiting Regimes

The authors analyze the behavior of PASV as weights become extreme ( $\lambda_i \to \infty$ or $\lambda_i \to 0$ ). They demonstrate that extreme weights can induce an almost deterministic tie-breaking mechanism among simultaneously admissible players. In specific cases (e.g., ordered partitions or globally maximal players), extreme weights effectively translate into new edges in the DAG, refining the precedence structure.

4. Scalable Computation

Since the number of linear extensions grows exponentially, exact computation is intractable for large $n$ . The authors develop an efficient Adjacent-Swap Metropolis-Hastings (M-H) sampler:

Initialization: A valid linear extension is found via topological sorting.
Transition: The sampler proposes a swap of adjacent incomparable elements in the current permutation.
Acceptance: The Metropolis-Hastings acceptance ratio is computed using local information (Lemma 4.1), allowing the sampler to converge to the non-uniform distribution $p^{(\preceq, \lambda)}$ without enumerating all permutations.
Estimation: PASV is estimated via Monte Carlo averaging of marginal contributions over the sampled permutations.

5. Diagnostic Tool: Priority Sweeping

Beyond point estimates, PASV enables a "priority sweeping" analysis. By varying a single player's (or group's) weight $\lambda_i$ while holding others fixed, practitioners can trace how the valuation changes. This serves as a sensitivity analysis to identify contributors whose credit is unstable or highly dependent on trust/risk assumptions.

Key Results

The paper evaluates PASV on two datasets:

Data Valuation (MNIST/CIFAR10):
- Setup: A data market scenario with 8 providers, including original data, augmented data, generative model outputs (Boosters), copies, and poisoned data. A complex DAG encodes the data lineage (e.g., copies depend on originals).
- Findings: Standard Shapley Value (SV) over-credits reused data. PSV correctly penalizes copies but treats all synthetic data equally. PASV, by adjusting weights, successfully differentiates between high-quality synthetic data (Boosters) and low-quality/reused data (Copier/Poisoner). The "priority sweeping" analysis reveals that the value of copied/poisoned data is highly sensitive to weight adjustments, whereas original data remains stable.
Feature Attribution (Census Income):
- Setup: Predicting income >$50k using 12 features. The authors compare a coarse "ordered partition" DAG (demographics $\prec$ socioeconomic) against a detailed DAG derived from domain knowledge (e.g., education $\prec$ occupation).
- Findings: The choice of DAG significantly alters attribution values. PASV's priority sweeping identifies that certain features (e.g., native-country, relationship) have unstable attributions depending on their priority weight, while others (e.g., marital-status) are robust. This highlights the importance of modeling precedence correctly and provides a tool to diagnose attribution sensitivity.

Significance and Claims

The paper claims that PASV offers a unified, expressive, and practically feasible framework for attribution in settings with dependencies and varying trust levels. Its primary contributions are:

Unification: It is the first method to simultaneously handle general precedence constraints (DAGs) and soft priority weights, recovering PSV and WSV as special cases.
Theoretical Grounding: It provides a solid axiomatic foundation, proving PASV is the unique rule satisfying natural properties for precedence-aware, weight-aware valuation.
Scalability: The proposed MCMC sampler enables application to large player sets where exact enumeration is impossible.
Practical Utility: The "priority sweeping" diagnostic provides a novel mechanism for sensitivity analysis, allowing practitioners to quantify the impact of trust/risk assumptions on valuation outcomes.

The authors emphasize that PASV does not claim to be a "black box" solution but rather a tool that makes the structural assumptions (DAG) and priority assumptions (weights) explicit and tunable, thereby supporting more robust and interpretable decision-making in data-centric AI.