🤖 machine learning

Generalized Priority-Aware Shapley Value

This paper introduces the Generalized Priority-Aware Shapley Value (GPASV), a novel valuation method that extends Shapley value to arbitrary directed weighted priority graphs by penalizing rather than forbidding order violations, thereby enabling robust valuation in complex real-world scenarios like cyclic LLM ensemble preferences.

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

Published 2026-05-15

📖 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 organizing a massive potluck dinner where everyone brings a dish, and you want to figure out who deserves the most credit for the deliciousness of the final meal. In the world of machine learning, this is called valuation: figuring out how much each data point, feature, or model contributed to the final result.

For decades, the standard tool for this job has been the Shapley Value. Think of it like a fair referee who randomly picks an order in which people arrive at the party. If you arrive early, you might have to cook with fewer ingredients; if you arrive late, you might have plenty to work with. The referee calculates your contribution by seeing how much the meal improves when you show up.

However, the old referee has a blind spot: they assume everyone is equal unless there is a strict, unbreakable rule saying "Person A must arrive before Person B."

The Problem: Real Life is Messy

In the real world, priorities aren't just black-and-white "musts." They are often:

Cyclic: In a group of friends, Alice might prefer Bob's cooking over Charlie's, Bob might prefer Charlie's over Dave's, but Dave might prefer Alice's over Bob's. It's a loop. The old referee gets stuck in a circle and can't make a decision.
Weighted: Sometimes, the rule "Alice must arrive before Bob" is very strong (like a law), but other times it's just a strong suggestion (like a preference). The old referee treats all rules as absolute laws, ignoring the strength of the preference.
Soft: Sometimes, we just trust certain people more or know they cost less to hire. The old referee doesn't know how to factor in this "soft" trust without breaking the hard rules.

The Solution: The "Generalized Priority-Aware Shapley Value" (GPASV)

The authors of this paper invented a new, super-smart referee called GPASV. Here is how it works, using simple analogies:

1. The "Soft Penalty" System (Handling Circles and Weights)

Imagine the old referee would throw out any seating arrangement where the rules were broken, even by a tiny bit. GPASV is more flexible.

The Metaphor: Instead of a strict "No Entry" sign, GPASV uses a speed bump. If you arrange the guests in an order that violates a preference (e.g., putting the "boss" after the "intern"), you don't get banned. Instead, you get a "penalty score."
How it works: The more you violate a strong preference, the higher the penalty. The referee still considers these arrangements, but they are less likely to be picked. This allows the system to handle cycles (loops of preference) and weighted preferences (strong vs. weak rules) without getting stuck.

2. The "Trust Score" (Soft Priority)

GPASV also listens to your "soft" feelings about the guests.

The Metaphor: Imagine you have a list of guests, and you have a "trust score" for each. Maybe you trust your grandma's cooking more than a stranger's, even if the stranger is technically "better" at cooking.
How it works: GPASV mixes the hard rules (the speed bumps) with these trust scores. It creates a balanced view where a highly trusted guest might get a better spot in the lineup, even if they slightly violate a minor rule.

3. The "Sweeping" Diagnostic (The Dial)

One of the coolest features of GPASV is that it doesn't give you just one answer. It gives you a dial.

The Metaphor: Imagine a radio dial. On one side, you have "Strict Rules Only" (Hard Priority). On the other side, you have "Pure Trust/Preference Only" (Soft Priority).
How it works: The authors show that you can turn this dial to see how the credit changes. If you turn the dial toward "Strict Rules," the results look one way. If you turn it toward "Trust," the results change completely. This proves that there isn't one single "correct" answer; the answer depends on how much you value the rules versus the trust.

The Real-World Test: Chatbot Arena

To prove this works, the authors tested it on LLMs (Large Language Models), specifically using data from "Chatbot Arena," where humans vote on which AI chatbot is better.

The Situation: Human votes often create loops (AI A beats B, B beats C, but C beats A). The old methods couldn't handle this.
The Experiment: They treated the AI models as the "guests" at the potluck. They had two types of priorities:
1. Hard Priority: Who humans actually voted for (the vote counts).
2. Soft Priority: Whether the AI is "Open Source" (free) or "Paid" (expensive).
The Result: They found that the "winner" of the valuation changed dramatically depending on how they turned the dial.
- If they focused only on human votes, the expensive, paid models (like GPT-4) dominated.
- If they focused on the "Open Source" preference, the free models shot to the top.
- The Lesson: You can't just press a "Calculate Value" button and get a single truth. You have to decide how much weight to give to human votes versus your own preferences (like supporting open source). GPASV makes this trade-off visible and adjustable.

Summary

The paper introduces GPASV, a new mathematical tool that fixes the flaws of older methods by:

Allowing loops in preferences (cycles) instead of getting stuck.
Respecting the strength of preferences (weights) instead of treating them all as absolute laws.
Combining these with personal trust scores (soft priority).
Showing users that the final "score" depends on how they balance these different factors, rather than being a single, fixed number.

It's like upgrading from a rigid, rule-bound referee to a flexible, wise mediator who understands that real-life priorities are messy, weighted, and sometimes circular.

Problem Statement

Shapley values and their priority-aware extensions are standard tools for attributing value to contributors in machine learning (e.g., data points, features, or model components). However, existing priority-aware methods, such as the Priority-Aware Shapley Value (PASV), rely on restrictive assumptions that often fail in modern AI/ML applications:

Binary and Acyclic Constraints: PASV requires pairwise priority relations to be encoded as a Directed Acyclic Graph (DAG). This forbids cycles (e.g., $A \succ B \succ C \succ A$ ) and treats priority as a hard, binary constraint. Real-world data, such as aggregated human preferences (Condorcet cycles) or multi-criterion comparisons, frequently exhibit cyclic structures.
Loss of Magnitude: PASV discards the strength of priority evidence. In scenarios like tournament win counts, Bradley-Terry log-odds, or ELO ratings, the magnitude of preference matters, but DAG-based methods only capture the existence of a precedence.
Copier Attacks: Standard Shapley values are vulnerable to "copier attacks" where a contributor who copies another receives equal credit. While PASV addresses this via hard priorities, it cannot handle the nuanced, weighted, or cyclic nature of real-world precedence.

Methodology: Generalized Priority-Aware Shapley Value (GPASV)

The authors propose GPASV, a Random Order Value (ROV) defined on arbitrary directed weighted graphs that simultaneously handles cyclic structures, weighted pairwise priorities, and individual "soft" priorities.

1. Core Definition
Unlike PASV, which restricts permutations to those consistent with a DAG, GPASV defines a probability distribution $p(\lambda, \omega)$ over the entire set of permutations $\Pi$ .

Pairwise Priority ( $\omega$ ): Represented by a weighted directed graph where $\omega_{ij} \ge 0$ encodes the strength that player $i$ should precede $j$ . Cycles are permitted.
Soft Priority ( $\lambda$ ): Individual weights representing trust, cost, or compliance risk.
Violation Penalty: For a permutation $\pi$ , the total violation cost $V_\omega(\pi)$ is the sum of weights for all pairs where the precedence is violated.
Distribution Formulation: The distribution combines a Gibbs-style penalty for violations with a stage-wise soft priority mechanism:
$p(\lambda, \omega)(\pi) \propto \prod_{t=1}^n \left[ \frac{\lambda_{\pi_t} \exp\{-\beta \cdot V_\omega(\pi_t; S_t)\}}{\sum_{k \in S_t} \lambda_k \exp\{-\beta \cdot V_\omega(k; S_t)\}} \cdot \sum_{k \in S_t} \exp\{-\beta \cdot V_\omega(k; S_t)\} \right]$
Here, $\beta$ is a temperature parameter controlling the strictness of the pairwise priority. As $\beta \to \infty$ , the method recovers PASV on DAGs; as $\beta = 0$ , it reduces to a Plackett-Luce distribution.

2. Axiomatic Characterization
The paper establishes GPASV through a set of axioms that generalize those of PASV:

GSCF (Generalized State-Choice Factorization): Ensures the distribution follows a canonical stage-wise form compatible with the sampling scheme.
GWP (Generalized Weight Proportionality): The log-odds of choosing player $i$ over $j$ at any stage depend on their soft weights $\lambda$ and their relative violation costs.
PVF (Pairwise-Violation Factorization): When soft weights are uniform, the distribution reduces to the Gibbs form penalizing total violations.
The authors prove that GPASV is the unique ROV satisfying these axioms.

3. Computational Framework
Calculating GPASV is challenging due to the non-uniform distribution over permutations. The authors develop:

Sampling: An adjacent-swap Metropolis-Hastings (MH) chain with a local acceptance ratio that cancels most global terms, making it efficient.
Initialization: A stage-wise greedy initialization (Algorithm 2) that samples players backward from position $n$ to mitigate the "cold start" problem in cyclic graphs where no valid linear extension exists.
Acceleration:
- Utility Caching: Reusing $U(S)$ evaluations for repeated subsets.
- SNIS (Self-Normalized Importance Sampling): Reusing permutation samples across different temperature settings ( $\beta$ ) or soft priority scales ( $\lambda$ ) during "priority sweeping."
- Surrogate-Assisted Estimation: Using regression-based surrogates (linear or quadratic) to reduce variance, though the authors note this incurs higher memory costs for GPASV compared to PASV due to the inability to zero out interaction terms for DAG edges.

Key Results and Empirical Validation

1. Simulations

Mixing Time: The greedy initialization significantly accelerates the mixing of the MH chain compared to random initialization, particularly in dense or cyclic graphs.
Accuracy: Direct Monte Carlo estimation converges as expected. Surrogate-assisted methods improve accuracy but introduce substantial runtime and memory overhead, especially for quadratic surrogates, which cannot exploit DAG sparsity.
Priority Sweeping: A diagnostic tool where soft priorities ( $\lambda$ ) are varied. The authors find that under GPASV, the impact of soft priorities is substantially larger than under PASV. Because GPASV "softens" hard constraints, individual soft priorities can more effectively reshape the valuation, whereas PASV's hard DAG constraints limit their influence.

2. Application: LLM Ensemble Valuation
The method is applied to value 20 Large Language Models (LLMs) using:

Utility: Performance on MT-Bench (aggregated and judged by an LLM).
Pairwise Priority: A cyclic, weighted graph derived from Chatbot Arena human preferences.
Soft Priority: A preference for open-source models over paid proprietary APIs.

Findings:

Non-Unique Valuation: Valuation is not a single "correct" number. Different balances between pairwise preferences ( $\beta$ ) and soft priorities ( $\alpha$ ) yield substantively different rankings.
Soft Priority Dominance: In joint sweeps, the node-level soft priority (open-source preference) tends to dominate the edge-level graph priority. For instance, increasing soft priority for open-source models can elevate them to the top ranks even when the pairwise preference graph favors paid models.
Graph Hubs: When prioritizing pairwise preferences ( $\beta$ ) alone, the valuation concentrates on specific "hubs" in the preference graph (e.g., GPT-4), rather than spreading value across a category of models.

Significance and Claims

The paper claims that GPASV is a principled, expressive extension of existing Shapley variants. Its primary significance lies in:

Handling Real-World Complexity: It is the first method to simultaneously handle cyclic, weighted pairwise priorities and individual soft priorities, covering classical Shapley, PSV, WSV, and PASV as special cases.
Transparency in Trade-offs: The authors argue that priority-aware valuation is "not a one-button operation." GPASV exposes the trade-off between different sources of priority information (e.g., human preference graphs vs. deployment constraints) as an explicit, sweepable input.
Diagnostic Necessity: The "priority sweeping" diagnostic reveals that soft priorities have a much larger impact under GPASV than previously thought under PASV, suggesting that metadata regarding soft priorities (trust, cost, risk) is far more consequential for valuation than previously recognized.

The paper concludes that while GPASV introduces computational challenges, its ability to model cyclic and weighted structures makes it essential for applications like LLM evaluation where standard DAG assumptions are violated.