Generalized Priority-Aware Shapley Value
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.
Tom: We're looking at the paper: "Generalized Priority-Aware Shapley Value".
Jane: Here's the gist of the paper. We introduce the generalized priority-aware Shapley value (GPASV), a random order value defined on arbitrary directed weighted priority graphs where pairwise edges penalize rather than forbid order violations.
Tom: GPASV is designed to handle cyclic and weighted priority graphs while incorporating individual soft priorities, making it the first valuation method capable of simultaneously managing cyclic pairwise priorities, weighted pairwise priorities, and individual soft priorities.
Jane: It encompasses classical models as boundary cases, containing the classical Shapley value (SV), PSV, WSV, and PASV as special cases.
Tom: The core contribution is GPASV's ability to handle cyclic and weighted priority graphs through an axiomatic characterization that generalizes PASV.
Title and authors: Tom: So, what does that actually mean for the application? They built this framework by establishing some axioms—Generalized State-Choice Factorization, Generalized Weight Proportionality, and Pairwise-Violation Factorization. These are the rules the GPASV has to follow >
Jane: It’s like they’re saying "this is what a good valuation method should look like," which gives us a solid foundation to trust it when we apply it to messy data, not just some neat, simple cases >
Meng: But how do we actually use this thing? If the underlying structure is an arbitrary graph, the math has to be tough. I’m wondering about the computational side—how complex are these calculations compared to standard Shapley values when you introduce all those weights and cycles >
Lu: They’ve developed some specific computational methods for it, like a GPASV-specific local adjacentswap Metropolis–Hastings ratio, which is one way to estimate the value >
Tom: And they also have this stage-wise greedy initialization specifically for cyclic graphs, which sounds like a smart way to get started when you know the structure is going to be complicated >
Jane: I also saw something that suggests a diagnostic tool called priority sweeping under GPASV that actually shows larger effects from those soft priorities compared to the older method, PASV >
Meng: If the diagnostic shows those soft priorities matter more, it means we can’t just ignore them when we try to estimate how much something is worth at scale. That tells us they’re not just adding noise >
Lu: And the paper validates this by showing how it handles cyclic and weighted priority graphs really well when applied to things like LLM ensemble valuation on the Chatbot Arena preference graph >
The paper's summary: Tom: So, they’re using this framework to look at a specific real-world example: valuing an ensemble of large language models based on preferences from people in the Chatbot Arena, which is known for having those cyclic and weighted preference structures >
Jane: This is where it gets concrete. They show that priority-aware valuation isn't just some simple operation you can run with a button press; the specific balance you strike between those pairwise graph priorities and those individual soft priorities actually changes the final value of the same data set >
Meng: That’s a crucial point for deployment. If one configuration yields a very different score than another, then we have to be very deliberate about setting up our valuation parameters when we deploy these models >
Lu: The paper confirms that GPASV is defined by a Gibbs-style distribution that penalizes total violation against weighted pairwise priorities while also incorporating player-level "soft priority" >
Tom: So, the method essentially balances two things: sticking to the known pairwise preferences, and respecting the individual soft priorities we assign to each player >
Jane: And they formalized it mathematically through Theorem one which proves that GPASV is unique because it satisfies those four specific axioms we mentioned earlier: GSCF, GWP, and PVF > <ref:2605.15018#pg3>
Meng: It sounds like they’ve essentially created a unique mathematical definition for this complex valuation problem when you have these mixed inputs >
Lu: And the empirical validation confirms that the user has to actively decide how to weigh those soft, individual priorities against the pairwise user-preference priorities because that choice materially affects the final result >
The paper's improvements: Tom: Beyond just handling cycles and weights, they also offer these specific computational enhancements. They have an adjacent-swap Metropolis–Hastings ratio for estimating the value, which is their method for sampling from that complex distribution >
Jane: And they’ve introduced two different estimators: a direct permutation-based Monte Carlo estimator and a subset-reweighted surrogate estimator, which are used to get the actual numbers >
Meng: I looked at their acceleration techniques too. They mention utility caching and self-normalized importance sampling, which cut the total cost of evaluation by about five point four times compared to the standard baseline methods >
Lu: That speedup is significant for scaling these kinds of calculations, especially when you’re dealing with large ensembles where you need to evaluate many different permutations >
Jane: And they even have some closed-form solutions for specific structured problems, like line directed acyclic graphs or block directed acyclic graphs that have cyclic blocks >
Tom: It sounds like they’ve tried to make the heavy lifting feasible by giving us faster ways to calculate the answers without having to run through every single permutation exhaustively >
Meng: But what they don't do, and this is important for production, is that the method still requires us to figure out how much weight we should give those individual soft priorities, because that’s where the human decision comes back in >
Conclusion: Tom: So, to wrap up on the "Generalized Priority-Aware Shapley Value," it means that when you have data with cycles and varying weights between players, you can use this method to get a valuation that respects those complex structures >
Jane: The main thing we learned is that priority-aware valuation isn't a simple one-button operation; whenever both player-level and pairwise priority information are present, the user must actively decide how to balance the two sources >
Lu: And they’ve shown that this GPASV framework, defined by satisfying those four axioms, gives us a way to handle these difficult scenarios with a unique mathematical definition >
Meng: From an engineering standpoint, the five point four times reduction in evaluation cost is a solid win for making these kinds of complex comparisons practical for large-scale model evaluation >
Lalam: I’m confident that this GPASV method provides a robust way to estimate value on preference graphs that don't fit the traditional acyclic requirements, and the empirical results support its use >
Kiljae Lee, Ziqi Liu, Weijing Tang, *Yuan Zhang
The Ohio State University · Carnegie Mellon University
cs.LG, cs.AI
Submitted: 2026-05-14
Updated: 2026-11-05
Comments: Accepted at NeurIPS 2026. 49 pages, 16 figures, 12 tables
Code: https://github.com/KiljaeL/GPASV
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 100/100
The gist: We introduce the generalized priority-aware Shapley value (GPASV), a random order value defined on arbitrary directed weighted priority graphs where pairwise edges penalize rather than forbid order…
Key concepts
- Generalized Priority-Aware Shapley Value (GPASV)
- A valuation method designed for complex preference graphs that include cycles and weighted edges. It calculates a fair value by balancing pairwise constraints with individual soft priorities, making it suitable for real-world scenarios like LLM comparisons.
- Individual Soft Priorities ($\lambda_i$)
- These are personal factors assigned to each player, such as trust or cost. They allow the valuation to capture individual preferences beyond just how one model compares to another, reflecting unique player biases.
- Priority Sweeping
- A diagnostic tool where a single soft priority value is varied across a range. This helps determine if the unknown soft priority significantly changes the final valuation, revealing its material impact on results.
Terminology
Summary
We introduce the generalized priority-aware Shapley value (GPASV), a random order value defined on arbitrary directed weighted priority graphs where pairwise edges penalize rather than forbid order violations. p. 0 edu
Abstract
Shapley value and its priority-aware extensions are widely used for valuation in
machine learning, but existing methods require pairwise priority to be binary and
acyclic, a restriction spectacularly violated in real-data examples such as aggregated
human preferences and multi-criterion comparisons. We introduce the generalized
priority-aware Shapley value (GPASV), a random order value defined on arbitrary
directed weighted priority graphs, in which pairwise edges penalize rather than
forbid order violations. 1 Our Contributions
Method (core contribution): GPASV handles cyclic and weighted priority graphs while incorporating individual soft priority. GPASV is the first valuation method that simultaneously
handles cyclic pairwise priorities, weighted pairwise priorities, and individual soft priorities, while
still containing the classical Shapley value, PSV, WSV, and PASV as special cases. 1 Our Contributions
Method (core contribution): GPASV handles cyclic and weighted priority graphs while incorporating individual soft priority. GPASV is the first valuation method that simultaneously
handles cyclic pairwise priorities, weighted pairwise priorities, and individual soft priorities, while
still containing the classical Shapley value, PSV, WSV, and PASV as special cases.Where the paper says it
Where the paper says it
Where the paper says it
The core contribution is GPASV's ability to handle cyclic and weighted priority graphs through an axiomatic characterization that generalizes PASV. This framework is supported by scalable computational methods, including a GPASV-specific local adjacentswap Metropolis–Hastings (MH) ratio (Proposition 1) and a stage-wise greedy initialization for cyclic graphs (Algorithm 2). p. 1 Scalable computation and acceleration methods. We derive a GPASV-specific local adjacentswap MH ratio (Proposition 1) and design a stage-wise greedy initialization for cyclic graphs
(Algorithm 2), then integrate these sampling components with direct Monte Carlo estimation, utility
caching (Section F. While some acceleration
components build on standard Monte Carlo and regression-surrogate ideas, their adaptation to the
GPASV permutation distribution and priority-sweeping workflow significantly enhances scalability. Diagnostic: priority sweeping under GPASV reveals larger soft-priority effects than under
PASV.Where the paper says it
Where the paper says it
The paper validates GPASV by applying it to LLM ensemble valuation on the cyclic Chatbot Arena preference graph, demonstrating that priority-aware valuation is not a simple operation; different balances between pairwise graph priorities and individual soft priorities yield substantively different valuations of the same data. p. 0 We establish GPASV through an axiomatic characterization, develop the
associated computational methods, and introduce a priority sweeping diagnostic
extending PASV’s. We apply GPASV to LLM ensemble valuation on the cyclic
Chatbot Arena preference graph, illustrating that priority-aware valuation is
not a one-button operation: different balances of pairwise graph priority versus
individual soft priority produce substantively different valuations of the same data.Where the paper says it
soft priority.
Theorem 1 establishes GPASV as the unique random order value satisfying Generalized State-Choice Factorization (GSCF), Generalized Weight Proportionality (GWP), and Pairwise-Violation Factorization (PVF).
Empirical validation shows that the user must actively decide how to weigh soft, individual priorities against pairwise user-preference priorities, as this choice materially affects the final valuation. p. 7 The main takeaway is that valuation should not
be treated as a single, best-chosen number automatically read off from the data. Instead, the user
must decide how to weigh soft, individual priorities against pairwise user-preference priorities, and
this choice materially affects the eventual valuation. Figure 3 shows that the error of direct MC quickly decreases with sample budget; the problem’s difficulty
increases with n (# of players), decreases for graphs with stronger priority structures; caching U(S) significantly reduces computational cost. In
Figure 4 and Table 1, we compared
(i) our direct MC estimator on (2) to
two surrogate-assisted estimators introduced in F. 5), where the target p
(λ,ω) moves
along a trajectory. Since nearby targets along this trajectory are similar, we may largely reuse
the previous permutation sample instead of redrawing, via self-normalized importance sampling
(SNIS) [18], and monitor to ensure sufficient effective sample size. Computation. The LLM inference cost in utility evaluations dominates that of permutation sampling: one un-cached Uens(S) evaluation costs 4 × 80 = 320 calls. To separate
sampling error from modeling error, we use two synthetic game families with closed-form GPASV
values. Scenario 1 uses a line DAG: 1 → · · · → n; Scenario 2 has the structure of a DAG of cycles:
players are partitioned into blocks, the blocks form a DAG among themselves, and each block is
internally a big directed cycle. These additional
costs can be much more significant than PASV, since PASV can zero out bi,j ’s corresponding to DAG
edges, while under GPASV this is impossible. 2
0 2
1 2
2 2
3 2
4 2
5 2
6 2
7
0
16
18
20
22
24
Mean Rank
2
0 2
1 2
2 2
3 2
4 2
5 2
6 2
7
0
400
600
800
1000
Value-Sum (SOU)
2
0 2
1 2
2 2
3 2
4 2
5 2
6 2
7
0
0
200
400
600
Value-Sum (SOR)
= 0 = 1 = 2 = 4 = 8
(PASV) Figure 5: Simulation 3: priority sweeping.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Priority-aware valuation is not a one-button operation: whenever both player-level and pairwise priority information are present, the user must decide how to balance the two sources.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Generalized Priority-Aware Shapley Value (GPASV) can be applied to valuation problems involving aggregated human preferences and multi-criterion comparisons that exhibit cyclic and weighted priority graphs, which are typically violated by standard methods requiring acyclic DAGs.
-
The system can incorporate individual soft priority encoded by a vector lambda i, which represents information such as trust or cost for each player, allowing the valuation to reflect differing levels of individual preference beyond just pairwise constraints.
-
The GPASV method allows the user to decide
how to weigh soft, individual priorities against pairwise user-preference priorities,
exposing thepriority trade-off as an explicit, sweepable input.
-
The system can perform priority sweeping diagnostics by varying a single soft priority scalar lambda i over (0, infinity) to diagnose whether the unknown soft priority materially affects the valuation.
-
The system can handle complex preference structures like those found in Chatbot Arena graphs where
majority preferences form several intransitive triangles among mid-tier models,
which is precisely the regime that motivates GPASV over PASV.
Abstract
Shapley value and its priority-aware extensions are widely used for valuation in machine learning, but existing methods require pairwise priority to be binary and acyclic, a restriction spectacularly violated in real-data examples such as aggregated human preferences and multi-criterion comparisons. We introduce the generalized priority-aware Shapley value (GPASV), a random order value defined on arbitrary directed weighted priority graphs, in which pairwise edges penalize rather than forbid order violations. GPASV covers a range of classical models as boundary cases. We establish GPASV through an axiomatic characterization, develop the associated computational methods, and introduce a priority sweeping diagnostic extending PASV's. We apply GPASV to LLM ensemble valuation on the cyclic Chatbot Arena preference graph, illustrating that priority-aware valuation is not a one-button operation: different balances of pairwise graph priority versus individual soft priority produce substantively different valuations of the same data.
Sources
- An Odd Estimator for Shapley Values
- Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning
- Priority-Aware Shapley Value
- Statistical Impossibility and Possibility of Aligning LLMs with Human Preferences: From Condorcet Paradox to Nash Equilibrium
- First-Order Efficiency for Probabilistic Value Estimation via A Statistical Viewpoint
- Investigating Non-Transitivity in LLM-as-a-Judge
- Rethinking Data Value: Asymmetric Data Shapley for Structure-Aware Valuation in AI Model Markets
Related papers
- A Physics-Regulated Neural Framework for Learning 3D Grain Growth Dynamics
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis