Generalized Priority-Aware Shapley Value

arXiv:2605.15018 · cs.LG, cs.AI · Submitted 2026-05-14 · Read on arXiv

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

Where the paper says it

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.

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. p. 1
Where the paper says it

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.

It encompasses classical models as boundary cases, containing the classical Shapley value (SV), PSV, WSV, and PASV as special cases. p. 1
Where the paper says it

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.

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

Where the paper says it

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.

A diagnostic tool, priority sweeping under GPASV, reveals larger soft-priority effects compared to PASV. p. 1
Where the paper says it

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.

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

Where the paper says it

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.

Key findings confirm that GPASV is defined by a Gibbs-style distribution penalizing total violation against weighted pairwise priorities and incorporating player-level 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

Where the paper says it

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.

Computational details include an adjacent-swap MH sampler and two estimators: a direct permutation-based Monte Carlo estimator and a subset-reweighted surrogate estimator. p. 6
Where the paper says it

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.

Acceleration techniques like utility caching and self-normalized importance sampling (SNIS) yield an approximately 5. p. 5
Where the paper says it

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.

4× reduction in total utility evaluation cost over the naive baseline. p. 8
Where the paper says it

Computation. The LLM inference cost in utility evaluations dominates that of permutation sampling: one un-cached Uens(S) evaluation costs 4 × 80 = 320 calls.

The method also provides closed-form solutions for specific structured scenarios, such as line DAGs and block DAGs with cyclic blocks. p. 6
Where the paper says it

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.

Furthermore, group-sum GPASV curves under Utility Sum of Unanimity (SOU) reward late-positioned players with higher soft priority, while Sum of Race (SOR) utility rewards early-positioned players. p. 6
Where the paper says it

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.

The overarching takeaway is that 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

  1. 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.

  2. 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.

  3. The GPASV method allows the user to decide how to weigh soft, individual priorities against pairwise user-preference priorities, exposing the priority trade-off as an explicit, sweepable input.

  4. 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.

  5. 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

Related papers