Research map / Graph learning / Graph algorithms and clustering

Generalized Priority-Aware Shapley Value

NeurIPS 2026 · Graph learning › Graph algorithms and clustering · approach: Continuous DAG structure learning · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces the generalized priority-aware Shapley value (GPASV), a random-order value over weighted, possibly cyclic priority graphs plus player-level soft priorities, with axiomatic characterization, MCMC computation, priority sweeps, and an LLM ensemble valuation on Chatbot Arena.

Problem

Existing priority-aware Shapley values (PSV, WSV, PASV) require pairwise priorities to form a binary acyclic graph, which fails for cyclic aggregated human preferences and weighted comparisons.

Approach

Replace the hard DAG constraint with a weighted directed graph penalized via a Gibbs-style exponential of total pairwise violation, combined with stage-wise soft priority weights, yielding a random-order value that reduces to SV, PSV, WSV, PASV and Plackett-Luce/Mallows as special cases.

Key results

• On the LLM ensemble task, at beta=32 with alpha=0, gpt-4 attains GPASV value 6.85, over 5x the runner-up, while most other paid models fall to about 0.1.
• At (alpha,beta)=(32,32), guanaco-33b leads at 3.98 while gpt-4 drops to rank 4 at 1.05, showing the soft priority dominates the graph priority on the joint slice.
• Simulation 3 reports that the impact of soft priority lambda is substantially larger under GPASV than under PASV when beta is small.

Surprising findings

• Soft priority effects under GPASV are substantially larger than under PASV because softened pairwise priorities allow any permutation.
• Along the beta-only slice, the graph priority concentrates value on a single hub model (gpt-4) rather than spreading across the paid group.

Limitations

• Each utility evaluation is expensive (320 LLM calls) and the cost scales with players and sweep settings.
• Priority graph is treated as given; noisy estimated graphs may cause instability near the hard-penalty limit, with no formal error bars.
• MCMC mixing time bounds are intractable; mixing is studied only empirically.

Experimental setup

Datasets: MT-Bench Chatbot Arena pairwise preferences

Benchmarks: MT-Bench Chatbot Arena

Metrics: GPASV value mixing time (pairwise-order probability accuracy) runtime memory error vs closed-form GPASV

Baselines: Shapley value PASV PSV WSV Plackett-Luce

Builds on: Shapley value precedence Shapley value weighted Shapley value priority-aware Shapley value Mallows model Plackett-Luce

Closest papers by meaning

• DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation (NeurIPS 2024 · similarity 0.87)
• Shapley-Guided Utility Learning for Effective Graph Inference Data Valuation (ICLR 2025 · similarity 0.85)
• shapiq: Shapley Interactions for Machine Learning (NeurIPS 2024 · similarity 0.85)
• KernelSHAP-IQ: Weighted Least Square Optimization for Shapley Interactions (ICML 2024 · similarity 0.84)
• Incorporating Information into Shapley Values: Reweighting via a Maximum Entropy Approach (ICML 2024 · similarity 0.84)
• Faithful Group Shapley Value (NeurIPS 2025 · similarity 0.83)