Generalized Priority-Aware Shapley Value
arXiv:2605.15018v1 [cs.LG] 14 May 2026
Kiljae Lee The Ohio State University [email protected]
Ziqi Liu Carnegie Mellon University [email protected] Yuan Zhang∗ The Ohio State University [email protected]
Weijing Tang Carnegie Mellon University [email protected]
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.
1
Introduction
Shapley value [38] and its variants are widely used in machine 1 2 1 2 learning to accredit content contributors, including training examples, data providers, features, or model components [16, 32, 40]. 3 3 4 4 Their appeal lies in being both principled (uniquely determined by a small set of axioms) and model-agnostic. A central axiom is (a) Hard priority (b) Soft priority symmetry: two players who contribute identical contents should 1 2 1 2 receive the same credit. While this is reasonable on its face, its key vulnerability is the copier attack: symmetry rewards copiers 3 3 4 4 equally to originators, when rationality says all credit should go to the originators. Modern AI/ML problems contain many examples (c) PASV (d) GPASV where for similar or related reasons, contributors should be valued Figure 1: Illustration of priordifferently for reasons beyond their contributed contents: data ity structures. Dashed arrows lineage, causal precedence among features, differing trust or cost in (b): [35, 46] require special across data providers. Recent work has incorporated this contexprecedence structures. tual information into Shapley-type valuations [41, 9], including precedence Shapley values (PSV) [11], weighted Shapley values (WSV) [20, 35], machine-learning adaptations [13, 46], and most recently the priority-aware Shapley value (PASV) [26]. A common assumption across all these works is that the pairwise priority relations can be captured by a directed acyclic graph (DAG). The meaning of DAG assumption is two-fold: (i) it has no cycles (e.g., i → j → k → i); (ii) precedences are unweighted; both aspects are violated in many ∗ Corresponding author.
Preprint.
modern AI/ML applications. A prominent example of cyclic priority is aggregated human preferences, where Condorcet cycles are ubiquitous [8, 2, 12, 29]; multi-criterion model comparison is another example in similar spirits [44]. Weighted priority arises whenever the strength of evidence varies, encompassing pairwise win counts in tournament analysis, Bradley-Terry log-odds [3], ELO ratings [17], and Plackett-Luce-style worth scores [36, 31]; all of these carry magnitude that a DAG discards. Some applications, such as Chatbot Arena [45, 7], present cyclic, weighted priority graphs. We propose generalized priority-aware Shapley value (GPASV), a valuation method that simultaneously handles cyclic and weighted priority graphs. Technically speaking, Shapley-style valuation methods all build on permutations of the players (see Section 2). Within this language, the DAG assumption amounts to rigidly restricting to admissible permutations. Our GPASV instead, for each permutation, counts its total amount of precedence violations and inversely weights its probability accordingly, thereby naturally handling cycles and weighted pairwise priorities. Apart from pairwise priority, represented by the priority graph, GPASV also incorporates the playerlevel “soft priority”, which encodes individual information such as trust, cost, or compliance risk. While the idea of this component was inherited from the WSV-to-PASV line of prior work, integrating it with our “upgraded” priority-graph component requires rather nontrivial adaptation. 1.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. Theory: a principled, expressive extension of PASV. GPASV admits an axiomatic characterization that generalizes PASV’s, with GSCF fixing the canonical stage-wise form (Section 3.4). Furthermore, on cyclic graphs GPASV admits limiting distributions that no PASV can express (Section 3.6), marking GPASV as a highly nontrivial extension rather than a wrapper around PASV. 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.3.1), SNIS reuse for priority sweeping (Section F.3.2), and a surrogate-assisted estimator adapted from regression-based semi-value methods (Section F.2.2). 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. We extend PASV’s priority sweeping diagnostic to GPASV. A central finding is that the impact of individual soft priorities λ is substantially larger under GPASV than under PASV, due to the softened pairwise priority relations. This carries two practical implications: priority sweeping becomes essential rather than optional for interpreting GPASV valuations, and metadata translatable into soft priorities becomes far more consequential to collect. Validation and application. Extensive simulations validate GPASV’s accuracy and confirm our theoretical predictions. A large-scale experiment on LLM ensemble valuation on MT-Bench and the cyclic Chatbot Arena preference graph demonstrates GPASV’s practicality and scalability.
2
Preliminaries
2.1
From Shapley Value to Random Order Values (ROV)
Shapley value (SV). Let [n] = {1, . . . , n} be a set of players. For any S ⊆ [n], let U (S) be the revenue earned by the joint work of S. We call U a utility function with U (∅) = 0. The Shapley value [38] o X |S|!(n − |S| − 1)! n νi (U ) := U (S ∪ {i}) − U (S) . (1) n! S⊆[n]\{i}
2
is a payoff method that uniquely satisfies four widely-desired axioms (see Appendix B). Random order values (ROV). Shapley value is prone to copier attack – an attacker i can unfairly split j’s pay by simply copying her. To defend against this attack, it is essential to consider the order/rank among players, thus if i consulted j’s work, then j should always be present in the prefix S in (1) when evaluating i’s contribution. This leads to a generic notion: random order value (ROV). Definition 1 (Random Order Value (ROV)). Let π = (π1 , . . . , πn ) be a permutation of [n] and π i be the set of players located before i in π. The random order value (ROV) of i is defined as νip (U ) := Eπ∼p U (π i ∪ {i}) − U (π i ) , (2) where p is a distribution over Π, the set of all permutations of [n]. Different choices of p yield different priority-aware extensions of Shapley value. Examples include: (i) Shapley value, with p = Uniform(Π); (ii) precedence Shapley value (PSV) [11], with p uniform over a set of “permitted permutations” induced by a directed acyclic graph (DAG) encoding hard, pairwise priority; (iii) weighted Shapley value (WSV) [20, 35] incorporates individual-level weights to encode soft priority. Going forward, we will describe each method by its p, without repeating (2). 2.2
Priority-Aware Shapley Value (PASV)
Hard vs. soft priority. Priority information available to the user typically comes in two forms. Hard priority specifies pairwise constraints that must be respected at all times, e.g., a causal ancestor must precede its descendant. Hard priority is encoded by a directed acyclic graph (DAG) G = ([n], E), where an edge (i, j) ∈ E means that i must appear before j in any π. Soft priority, in contrast, expresses individual-level preferences without forbidding any order; instead, it adjusts the ordering within the boundary permitted by the hard priority. Players who are more trusted, less costly, or carry less legal/compliance risk than others should be rewarded by an earlier spot in π, thus face less peer competition when evaluated. Soft priority is encoded by individual weights on each player: λ = (λ1 , . . . , λn ), where λi > 0. Priority-aware Shapley value (PASV). [26] proposed PASV to combine hard and soft priority in one ROV. For π ∈ Π and prefix St := {π1 , . . . , πt }, let max(St ) denote the set of players i ∈ St such that no j ∈ St is a descendant of i in G; these are the elements admissible to be πt . PASV is p(λ,G) (π) ∝ 1[π∈ΠG ] ·
n Y λ | max(St )| Pπt , k∈max(St ) λk t=1
(3)
where ΠG := {π ∈ Π : i appears before j in π for all (i, j) ∈ E} is the set of permutations consistent with G. In (3), the indicator 1[π∈ΠG ] enforces hard priority. The second part of (3) uses a stage-wise formulation to encode soft priority λ. This part can be roughly understood as follows: starting from position t = n down to t = 1, πt is drawn from the admissible set max(S Qnt ) with probability proportional to λπt ; the resulting π’s probability is then rescaled by the factor t=1 | max(St )| — this rescaling is essential for PASV to satisfy its axioms (see Remark 3.3 in [26]). PASV recovers SV, PSV and WSV as special cases under proper choices of λ and G.
3
Our Method
3.1
Limitations of PASV and Motivation for a Generalization
PASV encodes hard priority as a binary DAG, which can be restrictive in modern AI/ML applications. Hard priority may not be that “hard” in practice. In (3), every edge of G is enforced as an absolute constraint: any π violating even one edge is ruled out. But real pairwise priority is often a matter of degree rather than black/white. For example, NeurIPS 2026 draws a line at March 1, 2026: papers appearing before are treated as prior work, those after as concurrent [34], even though two papers posted one day before/after carry nearly identical priority. Similarly, a domain expert may believe feature i causally impacts feature j based on informative but non-determining evidence. In both cases, PASV discards magnitude information and becomes sensitive to borderline edges. 3
Pairwise priority may be cyclic. PASV requires G to be acyclic. But cyclic pairwise signals arise naturally when priority is aggregated across a population or across criteria. In aggregated human preferences, model i may beat j, j beats k, and yet k beats i – the classical Condorcet cycle [2, 12], shown to occur with high probability in LLM preference networks [29]. Multi-criterion comparison can be similarly cyclic: A beats B on criterion 1, B beats C on criterion 2, C beats A on criterion 3. Forcing such data into a DAG requires unfairly favoring certain players or biasing criteria. 3.2
Generalized Priority-Aware Shapley Value (GPASV)
To address the two limitations of PASV in Section 3.1, we first replace the binary DAG G with a weighted directed graph (ωij )i,j∈[n],i̸=j , where each ωij ≥ 0 encodes the strength of the pairwise priority “i should precede j”: ωij = 0 means no such priority; we set ωii ≡ 0 throughout. This convention directly accommodates common forms of user data – pairwise win counts, Bradley-Terry log-odds, ELO differences, or expert-assigned confidence scores – without ad-hoc transformations. Note that ωij and ωji are independent: in encoding a DAG-style precedence “i ≺ j” at most one of them is nonzero, while in encoding pairwise comparison records (e.g., i and j’s head-to-head wins), both can be positive. Unlike PASV, we impose no acyclicity requirement on ω. For simplicity, P we start with a simplified case where λi ≡ 1. For any π, its total violation against ω is Vω (π) := i̸=j ωij · 1[j appears before i in π] . A Gibbs-style distribution that penalizes total violation is pω β (π) ∝ exp{−β · Vω (π)},
(4)
where β ≥ 0 is a temperature controlling the overall penalty strength. When ω is a DAG and β → ∞, G we have pω β (π) = Uniform(Π ), recovering PSV, a special case of PASV when λi ≡ constant. Next, P we incorporate λ stage-wise, following PASV. Define the stage-wise violation cost Vω (k; St ) := j∈St ωkj , i.e., the total strength of priorities that k would violate by being placed at position t. The Generalized Priority-Aware Shapley Value (GPASV) is defined as: " # n Y X λπt exp{−β · Vω (πt ; St )} (λ,ω) P p (π) ∝ · exp{−β · Vω (k; St )} . (5) λ exp{−β · Vω (k; St )} t=1 | k∈St k k∈S {z } | t {z } (Part 1)
(Part 2)
Part 1 generalizes PASV’s stage-wise softmax: in PASV, every player in max(St ) is equally eligible to be πt and competes solely through λ; in GPASV, the weighted graph ω no longer issues each player k just a pass/fail ticket, but instead a continuous eligibility score exp{−β · Vω (k; St )} that discounts k by the total amount of pairwise priority violation it would cause if placed at position t; we naturally let this score rescale λk . Part 2 is the soft generalization of | max(St )| in (3). When λi ≡ c, it is not difficult to verify that (5) reduces to (4). When ω encodes a DAG with equal nonzero ω’s and β → ∞, (5) reduces to PASV (3); see Section 3.6 for formal limiting analysis. 3.3
Connections to Existing Literature
Gibbs distribution [5]. GPASV adopts a Gibbs-style encoding of pairwise priority weights; but due to the incorporation of λ, GPASV does not exactly fall into the Gibbs family. Mallows model [33]. The Mallows model specifies a reference permutation π0 ∈ Π and a distribution pM (π) ∝ exp{−d(π, π0 )}, where d(·, ·) is a dissimilarity measure, e.g., Kendall distance. Mallows is a narrow special case of GPASV: it does not consider λ and implicitly assumes that the priority graph can be induced by a single reference π0 (in particular, ω must be acyclic). Plackett-Luce model [36, 31]. When ω ≡ 0, (5) reduces to a Plackett-Luce distribution with “worths” (λi ), sampled stage-wise backward from position t = n to t = 1. 3.4
Axiomatic Characterization of GPASV
Here, we outline the axiomatization, using some acronyms that will be defined later and in Appendix B. First, using Weber’s axioms [41], we have E + L + NP + M ⇒ ROV – notice that GPASV is supported on the entire Π and does not use PASV’s Maximal-Support (MS) axiom. Second, GSCF 4
fixes a canonical stage-wise form for ROV distributions, rather than by itself imposing a new payofffairness requirement. Third, we engage boundary axioms: GWP and PVF to guarantee reduction to important special cases. Here, PASV’s SCF, WP and EWU axioms are generalized to GSCF, GWP and PVF to suit generalized hard priority. Finally, ROV + GSCF + GWP + PVF ⇒ GPASV (see Theorem 1). Now we carry out the outline. The first step (E+L+NP+M⇒ROV) is due to [41]. We start with GSCF. Generalized state-choice factorization (GSCF). We use GSCF to specify this canonical stage-wise form, compatible with the sampling scheme in Section 3.2. Definition 2 (GSCF). A distribution family pλ,ω on Π satisfies GSCF if there exist a state factor sω : 2[n] → R≥0 and a choice factor cλ,ω (· ; ·) : [n] × 2[n] → [0, 1], s.t. n Y pλ,ω (π) ∝ sω (St ) · cλ,ω (πt ; St ), π ∈ Π, ∀(λ, ω), (6) t=1
with
P
i∈S cλ,ω (i; S) = 1 for every nonempty S ⊆ [n].
GSCF is a canonical-form axiom: sω (St ) is a prefix-dependent rescaling, and cλ,ω (i; St ) is the conditional probability of picking i as πt . Plackett-Luce is a familiar simple instance (s ≡ 1, c = λsoftmax over St ); GPASV is another, where ω enters both factors. GSCF generalizes PASV’s SCF [26, Definition 3.9] along two directions that reflect GPASV’s weighted-graph nature: the choice factor ranges over the full St rather than the admissible subset max(St ) (hard priority is no longer absolute), and the state factor depends on ω rather than on the DAG alone (recall Section 3.2). Boundary axioms. Within the canonical GSCF family, we identify two important boundary cases. Axiom 1 (Generalized Weight Proportionality (GWP)). For every nonempty S ⊆ [n], cλ,ω (i; S) λi exp{−β · Vω (i; S)} = , ∀ i, j ∈ S. (7) cλ,ω (j; S) λj exp{−β · Vω (j; S)} Equivalently, the log-odds of choosing i over j at stage t depends on λi /λj and Vω (i; S) − Vω (j; S); PASV’s Weight Proportionality (WP) axiom only encodes the former – the two coincide in the same limiting case under which GPASV reduces to PASV (Section 3.2). Axiom 2 (Pairwise-Violation Factorization (PVF)). If λi ≡ 1, then p(π) ∝ exp{−β · Vω (π)}. That is, when players’ soft priority weights λi ’s are equal, p recovers the Gibbs-style form (4). Theorem 1 (Uniqueness of GPASV). The only ROV satisfying GSCF + GWP + PVF is GPASV. 3.5
Diagnostic Tool: Priority Sweeping
Soft priority sweep (inherited from [26]). As pointed out by [26], soft priority λ is often unavailable in practice, since relevant metadata such as trustworthiness, compliance risk, or originality scores are not routinely collected. Following [26], we equip GPASV with priority sweeping: one can vary a single λi over (0, ∞) to diagnose whether the unknown soft priority materially affects the valuation. This inherits the idea from [26] but not the algorithm: since GPASV’s stage-wise softmax acts on the full St rather than the admissible subset max(St ), the computation needs adaptation (see Section 4). Hard priority sweep (new to GPASV). GPASV’s weighted graph ω opens a sweeping axis that PASV’s binary DAG does not admit. The two extremes are β = 0 (no pairwise priority) and β → ∞ (hard priority; see Section 3.6), and sweeping intermediate β traces the transition between them. Overall, priority sweeping should report λ-only, ω-only, and joint sweeping: this reveals robustness and flags possible double-counting when λ aligns with priority graph; see Sections 5–6. 3.6
Limiting-Case Analysis
Let Gω = ([n], Eω ) with Eω = {(i, j) : ωij > 0} denote the directed graph induced by ω. Theorem 2 (Hard-penalty limit). For every fixed λ and ω, we have n Y λ |Mω (St )| Pπt , lim p(λ,ω) (π) ∝ 1[π∈Π · e Gω ] β→∞ k∈Mω (St ) λk t=1 5
(8)
e Gω := arg minπ∈Π Vω (π) and where recall Vω (π) and Vω (k; S) from Section 3.2, and define Π Mω (S) := arg mink∈S Vω (k; S). e Gω collects permutations with minimum total violation; while Mω (S) is the soft In Theorem 2, Π analogue of max(S), it collects the members of S whose placement at the end of S incurs the least e Gω = ΠGω , Mω (St ) = max(St ) for prefix St , and total violation within S. If Gω is a DAG: Π Theorem 2 shows that GPASV reduces to PASV (3) on Gω . But if Gω is cyclic, the limit in Theorem 2 generally does not reduce to any PASV. A simple example is a big cycle (equal edge weights). Appendix D gives a sharper example: support becomes DAG, but distribution is still not PASV.
4
Computation
Recall that GPASV is defined by (2) and (5). Naturally, we discuss three main topics: (i) how to sample π from (5); (ii) how to compute (2); (iii) acceleration tricks. Due to page limit, here we only present the gist and relegate detailed algorithms, and auxiliary derivations to Appendix F. Sampling π. We draw π from p(λ,ω) (5) using an adjacent-swap Metropolis–Hastings (MH) chain [22, 4, 26]. At each iteration, propose to swap (πi , πi+1 ) with acceptance probability min{1, p(λ,ω) (π swap )/p(λ,ω) (π)}. It turns out that for GPASV, almost all factors in this ratio cancel and only a local expression remains, making computation efficient (see Proposition 1). Initialization for this MCMC requires extra care. PASV can conveniently start from any valid linear extension, but for GPASV, when ω is cyclic, no linear extension exists; a cold start can waste many burn-in iterations. To address this challenge, we devise a dedicated stage-wise greedy method (see Algorithm 2): sample players backward from position n, each with probability proportional to a term that turns out to be exactly the GSCF choice factor cλ,ω in (6) instantiated for GPASV, see Appendix F.1.2. Mixing time bounds for this chain are generally intractable; we study mixing empirically in Section 5. Estimating the expectation in (2). Given sampled permutations, the most straightforward estimator simply replaces the expectation in (2) by a Monte Carlo average, which we use as our default. In Appendix F.2.2, we additionally describe a surrogate-assisted variant adapted from [30, 32, 15, 43]: first fit a cheap surrogate b h ≈ U , whose GPASV is usually easier to compute; second, bias-correct for h in lieu of U . This method works when b h well-captures U ; otherwise, the extra surrogate-fitting using b cost can outweigh its merit. Further acceleration. A simple trick allows substantial cost reduction with minimal implementation effort: we cache U (S) the first time it is evaluated and reuse the cached value thereafter. A separate acceleration is specific to priority sweeping (Section 3.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. See Appendix F.3 for details.
Empirical Validation
We conduct three simulations to assess the accuracy of our GPASV, test speed-up tricks, and compare its priority sweeping results with its counterpart from the previous work PASV to deepen our understanding.
DAG
104 Mixing Time
5
General Graph
Weak , Strong Weak , Weak Strong , Strong Strong , Weak
103 102 101
Greedy Random n4 2 (ideal) 3 2 n logn
Simulation 1: mixing time of MCMC. Re4 8 12 16 20 4 8 12 16 20 call from Section 4 that GPASV requires samn n pling from a non-uniform distribution on permutations; the first step is to burn-in the MH Figure 2: Simulation 1: mixing time, greedy (solid) chain until stationarity; the number of iterations vs random (dashed) initializations. needed is called mixing time. We diagnose mixing by the accuracy of pairwise-order probabilities P({i appears before j}) and tested both DAG 6
0
10k m
×104
5
20k 0 0
10k m
20k
Scenario 2 Unique S's
-2
log10 (ARE(m))
-1
Unique S's
log10 (ARE(m))
Scenario 1
n = 257 n = 2911 n=2 n=2
0 -1
10k m
0
20k
2 ×10
6
1 00
10k m
20k
Figure 3: Accuracy and acceleration by caching (case 2); full grids are in Appendix G.2. Table 1: Runtime (seconds) and training memory (GB) under matched utility budgets (case 2). Values are mean (std.dev.). Permutation reports runtime only. Full results are in Appendix G.2. Scenario 1 n
Permutation Time (s)
Linear Time (s) Mem (GB)
64 4.94 (0.01) 26.51 (0.15) 8.53 (0.02) 46.72 (0.19) 128 256 15.94 (0.03) 91.73 (0.17) 512 36.45 (0.16) 191.07 (0.65) 1024 195.76 (2.46) 663.81 (6.91)
Scenario 2 Quadratic Time (s) Mem (GB)
0.001 (0.000) 26.49 (0.10) 0.002 (0.000) 46.89 (0.26) 0.009 (0.000) 92.30 (0.28) 0.031 (0.000) 194.82 (0.74) 0.106 (0.001) 700.01 (6.31)
Permutation Time (s)
Linear Time (s) Mem (GB)
Time (s)
Quadratic Mem (GB)
0.002 (0.000) 4.69 (0.02) 35.50 (0.38) 0.093 (0.000) 36.08 (0.24) 0.290 (0.001) 0.012 (0.000) 8.15 (0.04) 61.27 (0.28) 0.194 (0.000) 63.95 (0.22) 0.986 (0.003) 0.081 (0.001) 15.99 (0.07) 120.17 (0.39) 0.592 (0.000) 138.65 (0.88) 5.620 (0.008) 0.566 (0.006) 34.36 (0.06) 231.47 (1.18) 1.158 (0.001) 317.75 (3.33) 21.000 (0.027) 3.724 (0.031) 205.55 (0.51) 725.34 (4.64) 2.312 (0.002) 1378.02 (9.58) 108.276 (0.155)
and general graphs. Due to page limit, here we only plot for a representative setting and relegate all details to Appendix G.1. Figure 2 suggests that the mixing speed of our algorithm is competitive compared to literature. In particular, we find that our greedy initialization method (Algorithm 2) can significantly speed up mixing. Simulation 2: Monte Carlo accuracy and surrogate-assisted acceleration. After the MH chain mixes well, the next question is the accuracy of the Monte Carlo estimation of (2). 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.
ARE at Convergence
Figure 3 shows that the error of direct MC quickly decreases with samScenario 1 Scenario 2 ple budget; the problem’s difficulty 0.03 Permutation 0.3 Linear increases with n (# of players), deQuadratic creases for graphs with stronger pri0.02 0.2 ority structures; caching U (S) significantly reduces computational cost. In 0.01 0.1 Figure 4 and Table 1, we compared (i) our direct MC estimator on (2) to 6 8 9 10 7 2 2 2 2 2 26 27 28 29 210 two surrogate-assisted estimators inn n troduced in F.2.2 using (ii) linear; and (iii) quadratic surrogates – roughly Figure 4: Surrogate-assisted methods (case 2). Full results speaking, (ii) fits U (S) ≈ U (∅) + are in Appendix G.2. P , while (iii) i∈S aiP P fits U (S) ≈ U (∅) + i∈S ai + i,j∈S bi,j .
0
1000
Value-Sum (SOR)
24 22 20 18 16 0 1 2 3 4 5 6 7 2 2 2 2 2 2 2 2
Value-Sum (SOU)
Simulation 3: priority sweeping. This simulation compares the impact of the soft priority λi under GPASV and PASV. Recall from [26] that under PASV, the impact of λi is limited by the hard priority. However, since GPASV has softened the hard priority, any permutation is possible. To stabilize
Mean Rank
Key takeaway: while surrogate methods improve estimation accuracy in most cases, they (especially the quadratic method) could introduce remarkable runtime and memory overhead. 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.
800 600 400
20 21 22 23 24 25 26 27
600
=0 =1 =2 =4 =8 (PASV)
400 200 0
20 21 22 23 24 25 26 27
0
Figure 5: Simulation 3: priority sweeping. 7
0
results, here we pick a subset of size n/2 and set their λi ’s to a common value λ0 and sweep. Figure 5 reports the mean rank and valuation of this group. As expected, when β is small, λ0 has much more impact on results under GPASV than under PASV (black curve). When β = 0, GPASV recovers Plackett-Luce, in which scenario λ’s impact is maximized.
6
Application: LLM Evaluation under Human Preference Graphs
We apply GPASV to LLM ensemble valuation, using Chatbot Arena’s [7] pairwise human preferences as a cyclic, weighted priority graph that PASV cannot handle. Aggregated human preferences over LLMs are known to contain cycles with high probability [29], so a cycle-aware method is not a corner case but an essential ingredient for this application. 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. Data and setup. Our goal is to apply GPASV to value each candidate LLM. Running GPASV on this task requires three inputs, each sourced from a public benchmark: a coalition utility, a pairwise priority graph, and a soft priority. We restrict attention to the 20 models that appear in both MT-Bench [45] and Chatbot Arena [7], so each player is one model and a coalition S is a subset of these models. Coalition utility. The coalition utility is supplied by MT-Bench [45], which consists of 80 two-turn prompts together with released responses from a large set of models scored by an LLM-as-a-judge protocol on a 1–10 scale. For a coalition S and a prompt q, we first pass the first-turn responses of models in S through a third-party LLM aggregator to synthesize a single ensemble answer, then ask a third-party LLM judge to score that answer against the MT-Bench protocol; we repeat the aggregator-judge pipeline for the second turn, conditioned on the first-turn dialogue so that coherence is scored as well. The prompt-level utility is the mean of the two turn scores, and the coalition utility Uens (S) is the mean over all 80 prompts, with Uens (∅) = 0. Both aggregator and judge are instantiated by Qwen3.5-35B-A3B-fp8 [37]; further details are relegated to Appendix H.2; templates are in Appendix H.5. Pairwise priority graph. Chatbot Arena [7] supplies pairwise human preferences. For each model pair (i, j) with at least 50 recorded comparisons, let i denote the majority-preferred model and set ωij = pbij − 1/2 and ωji = 0, where pbij is the empirical win probability of i over j. The graph has cycles and is not a DAG [29]. The temperature β in (5) controls how strongly this graph shapes the GPASV order distribution: β = 0 turns off the priority graph entirely, leaving only λ (SV if all λi ’s are equal); larger β enforces the Arena majority directions more strongly. Soft priority. The soft priority encodes a deployment preference for open-source models over paid proprietary APIs. Let zi = 1 if model i is open-source and zi = 0 otherwise (the paid models in our set are gpt-4, gpt-3.5-turbo, claude-v1, claude-instant-v1, and palm-2). A non-negative temperature α converts this raw preference into the player weights λi = exp(−αzi ) that enter GPASV in (5), so that α = 0 recovers λi ≡ 1 (no soft priority). Because GPASV samples backward, larger α places open-source models earlier in the sampled permutation. This is not a claim that open-source models are intrinsically better; it simply reflects an evaluator who wants to know how much of the ensemble’s performance open-source models are responsible for before reaching for proprietary APIs. Experimental design. Our experiments scan (α, β) along three one-dimensional slices: α varies alone (with β = 0), β varies alone (with α = 0), and the two vary together with α = β. Along each slice the non-zero temperature takes the values {1, 2, 4, 8, 16, 32}, and all three slices share the baseline (α, β) = (0, 0), at which GPASV reduces to the classical Shapley value with no priority applied. This gives 19 settings in total. The α-only and β-only slices are ablations for diagnosing whether the node and graph priorities encode overlapping signals, while the joint slice studies the evaluator’s deliberate decision to combine them. Due to space, the main paper presents a few representative (α, β) pairs; full results across all 19 settings are in Appendix H.4. 8
Paid
Favoring Open-Source Models Favoring Human Preferences ( , ) = (1, 0) ( , ) = (0, 1)
Open-source
0.0
0.71 2.46 gpt 4 gpt 4 0.70 1.39 vicuna 13b claude v1 0.67 claude instant v1 1.23 claude v1 0.66 1.04 wizardlm 13b gpt 3. 5 turbo 0.51 0.39 vicuna 13b guanaco 33b 0.51 0.32 claude instant v1 guanaco 33b 0.48 0.32 gpt 3. 5 turbo palm 2 0.45 0.25 vicuna 7b wizardlm 13b 0.5 0 2 0
0.0
0.82 gpt 4 0.80 1.29 claude v1 0.66 guanaco 33b 0.14 0.62 0.13 mpt 7b chat 0.60 chatglm 6b 0.13 0.49 dolly v2 12b 0.13 0.48 koala 13b 0.12 0.47 stablelm tuned alpha 7b 0.11 0.5 1.0 0 5
guanaco 33b gpt 4 vicuna 13b wizardlm 13b vicuna 7b koala 13b gpt4all 13b snoozy mpt 7b chat
Equal Treatment (SV) ( , ) = (0, 0) gpt 4 claude instant v1 gpt 3. 5 turbo claude v1 vicuna 13b wizardlm 13b guanaco 33b vicuna 7b
0
0.80 0.74 0.61 0.54 0.46 0.45 0.39 1
GPASV
1.26
Favoring Both ( , ) = (1, 1)
( , ) = (32, 0)
vicuna 13b wizardlm 13b guanaco 33b vicuna 7b gpt4all 13b snoozy koala 13b gpt 4 mpt 7b chat
GPASV
( , ) = (0, 32)
GPASV
6.85
0.91 0.76 0.73 0.63 0.63 0.53 0.48 1
1.64
2
( , ) = (32, 32)
guanaco 33b wizardlm 13b vicuna 13b gpt 4 vicuna 7b claude instant v1 claude v1 chatglm 6b
1.34 1.27 1.05 0.19 0.18 0.17 0.14 0 2
GPASV
3.98
4
Figure 6: Top-valued models under different priority balances. Colors: paid vs open-source.
Computation. The LLM inference cost in utility evaluations dominates that of permutation sampling: one un-cached Uens (S) evaluation costs 4 × 80 = 320 calls. Naively evaluating every prefix over 19 settings would require O(108 ) LLM calls. We use the two accelerations from Section 4: cache each (S, q) aggregator-judge output, and reuse neighboring-setting permutations by SNIS, drawing fresh samples only when effective sample size is low. Appendix H.3 reports a realized 5.4× reduction in distinct utility evaluations.
Results. Figures 6 and 7 report the scan outcomes: top-8 GPASV values under 7 representative (α, β) settings, and group-sum GPASV along the three slices. Four observations. 1. Paid dominates the no-priority baseline. At (0, 0), GPASV reduces to the Shapley value, and paid models hold ranks 1–4 led by gpt-4 at 1.26; the first open-source model only appears at rank 5. The paid group-sum exceeds the open-source group-sum, even though paid contains only 5 of the 20 models; equivalently, the paid per-model average is substantially higher. This skew comes from the coalition utility alone — the aggregator-and-judge pipeline simply scores paid responses higher. All later observations are to be read against this baseline.
Value-Sum
2. α lifts the favored group uniformly. Along Sweep ( = 0) Sweep ( = 0) = Sweep the β = 0 slice, the paid and open-source group7.5 sum curves cross near α ≈ 2 and then separate sharply, with open-source climbing and paid col5.0 Paid Open-source lapsing (Figure 7, left). Even at α = 1, gpt-4 2.5 has lost rank 1 to guanaco-33b and the other 0.0 paid models fall out of the top 8; at α = 32 0 20 21 22 23 24 25 0 20 21 22 23 24 25 0 20 21 22 23 24 25 = every open-source model is lifted by a similar multiplicative factor, because α enters each Figure 7: Group-sum GPASV for paid and openλi = exp(−αzi ) independently. source models across priority sweeps. The α 3. β concentrates GPASV on a single preference- sweep strengthens open-source node priority, the graph hub. Along the α = 0 slice, increasing β β sweep strengthens the preference graph priority, does not spread the gain across paid models. At and the joint sweep increases both together. β = 32, gpt-4 alone attains GPASV value 6.85 over 5× the runner-up, while most other paid models fall to the open-source tail (∼ 0.1). The paid group-sum in Figure 7 (middle) rises, but is carried by this one model rather than spread across the five. The structural reason is that β acts through the pairwise violation Vω , which couples every player to every other, so graph-theoretic hubs absorb attribution rather than uniform category members. 4. On the joint slice, α wins. The joint slice α = β could a priori track either axis or interpolate between them; empirically it tracks the α-only axis (Figure 7, right). At (32, 32), guanaco-33b leads at 3.98, while gpt-4 drops to rank 4 at 1.05 — nowhere near the 6.85 it commands under β-only. The player-level soft priority, which operates through an additive log-factor for every player, dominates the edge-level graph priority, which concentrates into a small number of hubs. 9
7
Key Takeaway and Limitations
Take-home message. Priority-aware valuation is not a one-button operation: whenever both player-level and pairwise priority information are present (e.g., open-source deployment preference + Chatbot Arena preference graph), the user must decide how to balance the two sources, and the resulting valuation can materially depend on that decision. This is not a method-level inconsistency but a natural property of the problem: unless an external objective is specified, the data alone cannot identify a uniquely correct priority trade-off; different evaluator preferences define different coherent valuations. The value of GPASV is to keep these modeling choices visible: it exposes the priority trade-off as an explicit, sweepable input and accepts cyclic priority graphs without first reducing them to a DAG. Limitations. We discuss two main limitations: utility calls and priority graph stability. Due to page limit, we relegate the detailed discussion to Appendix A.
Acknowledgements Lee and Zhang were supported by NSF DMS-2311109. Liu and Tang were supported by NSF DMS-2412853 and Jane Street Group, LLC.
References [1] J. F. Banzhaf III. Weighted voting doesn’t work: A mathematical analysis. Rutgers L. Rev., 19: 317, 1964. [2] D. Black et al. The theory of committees and elections. 1958. [3] R. A. Bradley and M. E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324–345, 1952. [4] R. Bubley and M. Dyer. Faster random generation of linear extensions. Discrete mathematics, 201(1-3):81–88, 1999. [5] G. T. Cantwell and C. Moore. Belief propagation for permutations, rankings, and partial orders. Physical Review E, 105(5):L052303, 2022. [6] J. Castro, D. Gómez, and J. Tejada. Polynomial calculation of the shapley value based on sampling. Computers & operations research, 36(5):1726–1730, 2009. [7] W.-L. Chiang, L. Zheng, Y. Sheng, A. N. Angelopoulos, T. Li, D. Li, B. Zhu, H. Zhang, M. Jordan, J. E. Gonzalez, et al. Chatbot arena: An open platform for evaluating llms by human preference. In Forty-first International Conference on Machine Learning, 2024. [8] J. A. M. N. C. Condorcet et al. Essai sur l’application de l’analyse à la probabilité des décisions, rendues à la pluralité des voix/| c par m. le marquis de condorcet..., 1785. [9] J. Derks. A new proof for weber’s characterization of the random order values. Mathematical Social Sciences, 49(3):327–334, 2005. [10] P. Dubey, A. Neyman, and R. J. Weber. Value theory without efficiency. Mathematics of Operations Research, 6(1):122–128, 1981. [11] U. Faigle and W. Kern. The shapley value for cooperative games under precedence constraints. International Journal of Game Theory, 21(3):249–266, 1992. [12] P. C. Fishburn. Condorcet social choice functions. SIAM Journal on applied Mathematics, 33 (3):469–489, 1977. [13] C. Frye, C. Rowat, and I. Feige. Asymmetric shapley values: incorporating causal knowledge into model-agnostic explainability. Advances in neural information processing systems, 33: 1229–1239, 2020. [14] F. Fumagalli, L. Butler, J. S. Kang, K. Ramchandran, and R. T. Witter. An odd estimator for shapley values. arXiv preprint arXiv:2602.01399, 2026. [15] F. Fumagalli, R. T. Witter, and C. Musco. PolySHAP: Extending kernelSHAP with interactioninformed polynomial regression. In The Fourteenth International Conference on Learning Representations, 2026. URL https://openreview.net/forum?id=M19J8UGguq. 10
[16] A. Ghorbani and J. Zou. Data shapley: Equitable valuation of data for machine learning. In International conference on machine learning, pages 2242–2251. PMLR, 2019. [17] M. E. Glickman. Parameter estimation in large dynamic paired comparison experiments. Journal of the Royal Statistical Society Series C: Applied Statistics, 48(3):377–394, 1999. [18] T. Hesterberg. Weighted average importance sampling and defensive mixture distributions. Technometrics, 37(2):185–194, 1995. [19] A. B. Kahn. Topological sorting of large networks. Communications of the ACM, 5(11): 558–562, 1962. [20] E. Kalai and D. Samet. On weighted Shapley values. International journal of game theory, 16 (3):205–222, 1987. [21] K. Kangas, T. Hankala, T. M. Niinimäki, and M. Koivisto. Counting linear extensions of sparse posets. In IJCAI, volume 16, pages 603–609, 2016. [22] A. Karzanov and L. Khachiyan. On the conductance of order markov chains. Order, 8(1):7–15, 1991. [23] A. Kong, J. S. Liu, and W. H. Wong. Sequential imputations and bayesian missing data problems. Journal of the American statistical association, 89(425):278–288, 1994. [24] W. Kwon, Z. Li, S. Zhuang, Y. Sheng, L. Zheng, C. H. Yu, J. Gonzalez, H. Zhang, and I. Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th symposium on operating systems principles, pages 611–626, 2023. [25] Y. Kwon and J. Zou. Beta shapley: a unified and noise-reduced data valuation framework for machine learning. arXiv preprint arXiv:2110.14049, 2021. [26] K. Lee, Z. Liu, W. Tang, and Y. Zhang. Priority-aware shapley value. arXiv preprint arXiv:2602.09326, 2026. [27] W. Li and Y. Yu. Robust data valuation with weighted banzhaf values. Advances in Neural Information Processing Systems, 36:60349–60383, 2023. [28] W. Li and Y. Yu. One sample fits all: Approximating all probabilistic values simultaneously and efficiently. Advances in Neural Information Processing Systems, 37:58309–58340, 2024. [29] K. Liu, Q. Long, Z. Shi, W. J. Su, and J. Xiao. Statistical impossibility and possibility of aligning llms with human preferences: From condorcet paradox to nash equilibrium. arXiv preprint arXiv:2503.10990, 2025. [30] Z. Liu, K. Lee, Y. Zhang, and W. Tang. First-order efficiency for probabilistic value estimation via a statistical viewpoint. arXiv preprint arXiv:2605.02827, 2026. [31] R. D. Luce et al. Individual choice behavior, volume 4. Wiley New York, 1959. [32] S. M. Lundberg and S.-I. Lee. A unified approach to interpreting model predictions. Advances in neural information processing systems, 30, 2017. [33] C. L. Mallows. Non-null ranking models. i. Biometrika, 44(1/2):114–130, 1957. [34] NeurIPS. Neurips 2026 main track handbook, 2026. Conferences/2026/MainTrackHandbook.
URL https://neurips.cc/
[35] A. S. Nowak and T. Radzik. On axiomatizations of the weighted shapley values. Games and Economic Behavior, 8(2):389–405, 1995. [36] R. L. Plackett. The analysis of permutations. Journal of the Royal Statistical Society Series C: Applied Statistics, 24(2):193–202, 1975. [37] Qwen Team. Qwen3.5: Towards native multimodal agents, February 2026. URL https: //qwen.ai/blog?id=qwen3.5. [38] L. S. Shapley. A value for n-person games. Contributions to the Theory of Games, 2, 1953. [39] T. Talvitie, T. M. Niinimäki, and M. Koivisto. The mixing of markov chains on linear extensions in practice. In IJCAI, pages 524–530, 2017. [40] J. T. Wang and R. Jia. Data Banzhaf: A robust data valuation framework for machine learning. In International Conference on Artificial Intelligence and Statistics, pages 6388–6421. PMLR, 2023. 11
[41] R. J. Weber. Probabilistic values for games, page 101–120. Cambridge University Press, 1988. [42] D. B. Wilson. Mixing times of lozenge tiling and card shuffling markov chains. The Annals of Applied Probability, 14(1):274–325, 2004. [43] R. T. Witter, Y. Liu, and C. Musco. Regression-adjusted monte carlo estimators for shapley values and probabilistic values. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. URL https://openreview.net/forum?id=Qabko39AS5. [44] Y. Xu, L. Ruis, T. Rocktäschel, and R. Kirk. Investigating non-transitivity in llm-as-a-judge. arXiv preprint arXiv:2502.14074, 2025. [45] L. Zheng, W.-L. Chiang, Y. Sheng, S. Zhuang, Z. Wu, Y. Zhuang, Z. Lin, Z. Li, D. Li, E. Xing, et al. Judging llm-as-a-judge with mt-bench and chatbot arena. Advances in neural information processing systems, 36:46595–46623, 2023. [46] X. Zheng, Y. Huang, X. Chang, R. Jia, and Y. Tan. Rethinking data value: Asymmetric data Shapley for structure-aware valuation in data markets and machine learning pipelines. arXiv preprint arXiv:2511.12863, 2025.
12
Computer Code Computer code is available at: https://github.com/KiljaeL/GPASV
A
Limitations
A.1
Utility Calls
The main computational cost of GPASV lies in repeated evaluations of the coalition utility U (S). This cost is shared by essentially all model-agnostic data valuation methods in the random-order family, and is, in our view, unavoidable: any method that treats U as a black box has no recourse but to query it, and accurate estimation of marginal contributions imposes a minimum query budget that scales with the number of players. The cost becomes especially salient when each query to U is itself expensive, as in the LLM ensemble setting of Section 6, where evaluating U (S) for a single coalition requires running an LLM-as-an-aggregator and an LLM-as-a-judge over all 80 MT-Bench questions, with 20 candidate models giving 220 possible coalitions. To address this limitation, our framework incorporates three computational devices that work jointly with the GPASV definition rather than being bolted on after the fact. Subset caching (Section 4) exploits the fact that the same subset S recurs many times across both the permutation-based estimator and the surrogate-based estimator, so each distinct U (S) is evaluated at most once. Self-normalized importance sampling (Section F.3.2) reuses permutations already drawn under one (λ, ω) to estimate GPASV at neighboring parameter values, which is what makes the priority sweeps in Section 6 affordable. The two-stage surrogate-adjusted residual estimator (Section F.2.2) further reduces variance per utility query by absorbing most of the signal into a fitted surrogate and spending the remaining query budget on residual correction. Together, these devices allow the full LLM application of Section 6, including its priority sweeps, to be carried out within a fixed and modest LLM-call budget. A.2
Priority Graph
A second limitation concerns the priority graph itself. Throughout this paper we treat the priority graph as a given input and study how it shapes the resulting valuation, but in practice the graph is often estimated from finite, noisy, or partially observed data, as is the case for the Chatbot Arena pairwise preferences used in Section 6. At finite β, GPASV remains a smooth function of the edge weights, but the β → ∞ hard-penalty boundary can amplify near-ties in violation cost. Hence priority sweeps can diagnose empirical instability, but they are not formal statistical error bars. Deriving finite-sample error bounds or sharper stability diagnostics for noisy estimated graphs is beyond the present work and is an important direction for future research.
B
Background for the Shapley Value and Random Order Values
This appendix collects the standard axioms invoked throughout the paper. We fix the player set [n] and consider utility functions U : 2[n] → R with U (∅) = 0. A value is a mapping ψ assigning to each such U a payoff vector ψ(U ) = (ψi (U ))i∈[n] . The following four axioms are originally due to Shapley [38]. P Axiom 3 (Efficiency (E)). i∈[n] ψi (U ) = U ([n]). Axiom 4 (Linearity (L)). For utilities U, V and scalars α, β ∈ R, ψ(αU + βV ) = αψ(U ) + βψ(V ). Axiom 5 (Null Player (NP)). If player i contributes nothing, i.e., U (S ∪ {i}) = U (S) for all S ⊆ [n] \ {i}, then ψi (U ) = 0. Axiom 6 (Symmetry (S)). If two players i, j are interchangeable, i.e., U (S ∪ {i}) = U (S ∪ {j}) for all S ⊆ [n] \ {i, j}, then ψi (U ) = ψj (U ). E says the grand-coalition revenue U ([n]) is fully distributed; L says the value commutes with affine combinations of utilities; NP rules out paying a player whose marginal contribution is identically zero; S enforces anonymity by treating exchangeable players identically. Shapley [38] shows that E + L + NP + S uniquely characterize the Shapley value ψ SV in (1). 13
For random order values, anonymity is precisely what one wants to relax in order to encode priority. Weber [41] replaces S with the following monotonicity (M) axiom and obtains a strictly larger class. Axiom 7 (Monotonicity (M)). If U is monotone in the sense S ⊆ T ⇒ U (S) ≤ U (T ), then ψi (U ) ≥ 0 for every i ∈ [n]. M rules out negative payoffs whenever larger coalitions never reduce revenue. Weber [41] shows that a value satisfies E + L + NP + M if and only if it admits the ROV form (2) for some distribution p over Π. In other words, ROV is exactly the family obtained by deliberately relaxing Symmetry: it preserves the additive, contribution-based fairness ideals (E, L, NP, M) while opening room to treat players asymmetrically through the choice of permutation distribution p.
C
Two Equivalent Representations of GPASV
The definition of GPASV in (5) encodes pairwise priorities based on a Gibbs-style representation with additive priorities ωij ≥ 0. However, the same family of distributions can be expressed in an alternative, multiplicative representation. Define ω eij = exp(−βωij ). Note that the temperature β is absorbed in the multiplicative representation. By one-to-one correspondence, ω eij ∈ (0, 1] and ω eij = 1 corresponds to the absence of pairwise priority. In this representation, the stepwise violation factor is the product Y ω ekS := ω ekj , S ⊆ [n], k ∈ [n], (9) j∈S\{k}
with ω ekk = 1, so that we have the equivalence Y Y exp{−β · Vω (k; S)} = exp(−βωkj ) = ω ekj = ω ekS . j∈S
(10)
j∈S
Under this equivalence, the GPASV distribution (5) admits the equivalent product form " # n Y X λπt ω eπStt St (λ,ω) p (π) ∝ · ω ek . P ekSt k∈St k∈St λk ω t=1
(11)
Reading off (11), GPASV’s GSCF factorization (Definition 2) instantiates as λi ω eiS , ekS k∈S λk ω
cλ,ω (i; S) = P
sω (S) =
X
ω ekS .
(12)
k∈S
That is, the choice factor is a λ-weighted softmax over S with weights ω ekS , and the state factor is the corresponding partition sum. Table 2 summarizes the relationship between the two representations. Table 2: Correspondence between the multiplicative representation ω eij = exp(−βωij ) and the additive representation ωij used in the main text. Quantity/Case Correspondence Pairwise priority Stepwise violation No priority Hard priority
D
ω eij = exp(−βωij ) ω ekS = exp(−β · Vω (k; S)) (e ωij = 1) ∼ (ωij = 0) (e ωij → 0) ∼ (ωij or β → ∞)
A Detailed Example of the GPASV under Cyclic Graph
Here we provide a detailed analysis of the cyclic counterexample where GPASV does not reduce to PASV, as mentioned in Section 3.6. Consider five players with node weights λ1 = 1, λ2 = 2, λ3 = 14
1
4 1
3
GPASV (
Gω⋆ 1
4
5
6
5 β→∞
2
4
3
2
3
Probability
Gω
)
PASV
0.3 0.2 0.1
0.0 ,4,5) ,5,4) ,3,4) ,3,4) ,3,4) (1,2,3 (1,2,3 (1,2,5 (1,5,2 (5,1,2
(a)
(b)
Figure 8: Example showing that cyclic GPASV does not reduce to PASV; (a) the support of the limiting GPASV distribution collapses to the feasible permutations of the DAG obtained by deleting the minimum-violation edge; (b) Yet the unnormalized distribution of the limiting GPASV differs from that of the PASV on the reduced DAG. 3, λ4 = 4, λ5 = 5 and directed edge weights ω12 = 3, ω23 = 4, ω31 = 1, ω34 = 6 (player 5 isolated), see Figure 8. If we delete the edge 3 → 1, the graph becomes acyclic, and the permutations obeying the remaining edges achieve the minimum total violation of ω31 = 1. Write ω ⋆ for the edge weights of the reduced ⋆ ⋆ DAG, so that ω31 = 0 and ωij = ωij for all other pairs. Then, the support of the limiting GPASV matches the support of the PASV on G⋆ω : e Gω = ΠG⋆ω = (1, 2, 3, 4, 5), (1, 2, 3, 5, 4), (1, 2, 5, 3, 4), (1, 5, 2, 3, 4), (5, 1, 2, 3, 4) . Π It is enough to compare with G⋆ω : if the limiting GPASV law coincided with PASV on some DAG H, e Gω = ΠG⋆ω . The set of linear extensions determines the same then its support would satisfy ΠH = Π partial order up to transitive closure, and PASV depends only on this induced partial order. Thus PASV on H coincides with PASV on G⋆ω , and it suffices to show that the limiting GPASV law differs from PASV on G⋆ω . Since the two supports agree, we may compare the unnormalized distributions of the limit of GPASV in Theorem 2 with the PASV (3) on Gω⋆ , which are given by: lim pe(λ,ω) (π) =
β→∞
n Y λ |Mω (St )| Pπt , k∈Mω (St ) λk t=1
pe(λ,Gω⋆ ) (π) =
n Y λ | max(St )| Pπt . k∈max(St ) λk t=1
For a permutation π = (1, 2, 3, 4, 5), their ratio (PASV/GPASV) is 1. However, on the permutation π = (1, 2, 3, 5, 4), their ratio is PASV 2λ5 = . GPASV λ3 + λ5 Their key discrepancy happens when discussing π4 . Under GPASV, Mω (S4 ) = {5}, while under PASV, max(S4 ) = {3, 5}, leading to the crucial difference between these two schemes. From this observation, we emphasize following understandings: • In terms of the support of the distribution of π, a GPASV under a cyclic graph may reduce to a PASV. However, their π distributions are still different; • In PASV, at each stage t, the maximal set max(St ) is the range of candidate players eligible for competing for πt ; however, in GPASV, this is completely different: the set of eligible players for πt is not determined by Mω (St ), moreover, it cannot be determined locally, but e Gω . only through the global rule π ∈ Π
E
Proofs of Theoretical Results
E.1
Proof of Theorem 1
We first record the reduction from the four background axioms to the ROV class; this is the entry point for the GSCF/GWP/PVF analysis below. 15
Lemma 1 (Weber [41]). A value ψ satisfies E + L + NP + M (Appendix B) if and only if ψ = ν p for some probability distribution p on Π, where ν p is defined in (2). A proof of Lemma 1 is given by Weber [41]; we take it as a starting point and focus on the GSCF/GWP/PVF analysis below. Proof of Theorem 1. We prove the two implications (⇒) and (⇐) separately. (⇒) Suppose p is aP ROV satisfying GSCF, GWP and PVF. By GSCF (6), there exist sω : 2[n] → R≥0 and cλ,ω (·; ·) with i∈S cλ,ω (i; S) = 1 for every nonempty S ⊆ [n] such that p(π) ∝
n Y
π ∈ Π.
sω (St ) cλ,ω (πt ; St ),
(13)
t=1
Fix any nonempty S ⊆ [n] and any reference j ∈ S. For every i ∈ S, GWP (7) yields λi exp{−β · Vω (i; S)} . λj exp{−β · Vω (j; S)} P Summing over i ∈ S and using the GSCF normalization i∈S cλ,ω (i; S) = 1 identifies cλ,ω (i; S) = cλ,ω (j; S) ·
λi exp{−β · Vω (i; S)} , k∈S λk exp{−β · Vω (k; S)}
cλ,ω (i; S) = P
i ∈ S,
(14)
which determines the GSCF choice factor uniquely from (λ, ω, β). Substituting (14) into (13) gives, for every π ∈ Π, p(π) ∝
n Y
sω (St ) P λ exp{−β · Vω (k; St )} k∈St k t=1
! ·
n Y
λπt exp{−β · Vω (πt ; St )}.
(15)
t=1
The exponents in the second product simplify by re-indexing the double sum n X t=1
Vω (πt ; St ) =
t n X X
ωπt ,πs =
t=1 s=1
X
ωπt ,πs = Vω (π),
(16)
1≤s<t≤n
where the last equality re-indexes by the ordered pairs (πs , πt ) for which πs appears before πt . Specializing to λi ≡ 1, (15) then reduces to n Y sω (St ) P p(π) ∝ exp{−β · Vω (π)} · . exp{−β · Vω (k; St )} k∈St t=1 Comparing with PVF, which asserts p(π) ∝ exp{−β · Vω (π)}, the prefix product must be a πindependent constant: there exists K > 0 such that n Y sω (St ) P = K for every π ∈ Π. (17) exp{−β · Vω (k; St )} k∈St t=1 The factor on the left is independent of λ, so (17) continues to hold for arbitrary λ. Returning to (15) for arbitrary λ, we factor each stage to expose the GPASV form: n Y sω (St ) λπt exp{−β · Vω (πt ; St )} P p(π) ∝ k∈St λk exp{−β · Vω (k; St )} t=1 ! n Y sω (St ) P = k∈St exp{−β · Vω (k; St )} t=1 # " n Y X λπt exp{−β · Vω (πt ; St )} P × · exp{−β · Vω (k; St )} k∈St λk exp{−β · Vω (k; St )} k∈St t=1 # " n Y X λπt exp{−β · Vω (πt ; St )} P ∝ · exp{−β · Vω (k; St )} , k∈St λk exp{−β · Vω (k; St )} t=1 k∈St
16
which is exactly p(λ,ω) (π) in (5). (⇐) Conversely, take p = p(λ,ω) defined in (5). Setting X λi exp{−β · Vω (i; S)} sω (S) := exp{−β · Vω (k; S)}, cλ,ω (i; S) := P , k∈S λk exp{−β · Vω (k; S)} k∈S P Q we have sω : 2[n] → R≥0 , i∈S cλ,ω (i; S) = 1, and p(λ,ω) (π) ∝ t sω (St ) cλ,ω (πt ; St ), so GSCF holds. The ratio cλ,ω (i; S)/cλ,ω (j; S) matches (7) by construction, so GWP holds. When λ Qi ≡ 1, the stage-wise product Part 1·Part 2 in (5) collapses to exp{−β · Vω (πt ; St )}, and (16) gives t exp{−β · Vω (πt ; St )} = exp{−β · Vω (π)}, recovering (4); hence PVF holds. E.2
Proof of Theorem 2
Proof. We will first isolate the dominant exponential factor in β that controls the limiting support, and then evaluate the residual factor on that support. By (5), for every π ∈ Π, n Y
P exp{−β · Vω (k; St )} p (π) ∝ λπt exp{−β · Vω (πt ; St )} · P k∈St . k∈St λk exp{−β · Vω (k; St )} t=1 Qn Using the identity (16), t=1 exp{−β · Vω (πt ; St )} = exp{−β · Vω (π)}, so P n Y exp{−β · Vω (k; St )} (λ,ω) λπt · P k∈St p (π) ∝ exp{−β·Vω (π)}·Aβ (π), Aβ (π) := . (18) k∈St λk exp{−β · Vω (k; St )} t=1 (λ,ω)
We now study the limit of Aβ (π) for a fixed π ∈ Π. For each stage t, set mω (St ) := min Vω (k; St ), k∈St
Mω (St ) = arg min Vω (k; St ), k∈St
−β·mω (St )
and factor out e from both the numerator and the denominator inside Aβ (π) to obtain P P exp{−β · [Vω (k; St ) − mω (St )]} k∈St exp{−β · Vω (k; St )} P = P k∈St . k∈St λk exp{−β · Vω (k; St )} k∈St λk exp{−β · [Vω (k; St ) − mω (St )]} Each exponent in the rewritten sums is nonpositive and equals zero precisely whenP k ∈ Mω (St ), so as β → ∞ every term with k ∈ / Mω (St ) vanishes and the ratio tends to |Mω (St )|/ k∈Mω (St ) λk ∈ (0, ∞). Taking the product over t = 1, . . . , n yields β→∞
Aβ (π) −−−−→ A∞ (π) :=
n Y λ |Mω (St )| Pπt ∈ (0, ∞), k∈Mω (St ) λk t=1
π ∈ Π.
(19)
e Gω = arg minπ∈Π Vω (π) and let It remains to handle the exponential factor in (18). Recall Π V ⋆ := min Vω (π). π∈Π
⋆
Multiplying every unnormalized weight in (18) by the common factor eβ·V leaves the induced probability distribution unchanged, so p(λ,ω) (π) ∝ exp{−β · [Vω (π) − V ⋆ ]} · Aβ (π),
π ∈ Π.
(20)
e Gω , the exponential factor in (20) is identically 1, and by (19) the unnormalized weight For π ∈ Π e Gω , we have Vω (π) − V ⋆ > 0 while Aβ (π) stays bounded converges to A∞ (π) ∈ (0, ∞). For π ∈ /Π by (19), so the unnormalized weight tends to 0. Consequently the total normalizing mass converges P to the strictly positive quantity π∈Π e Gω A∞ (π), and P A∞ (π) e Gω , , π∈Π (λ,ω) ′) A (π lim p (π) = ′ G ∞ e ω π ∈Π β→∞ e Gω , 0, π∈ /Π which, by the definition of A∞ in (19), is exactly (8). 17
E.3
Proof of Proposition 1
Proof. Recall St = {π1 , . . . , πt }, so the prefix shared by π and π ′ before the swapped pair is Si−1 = {π1 , . . . , πi−1 }, and Si′ = Si−1 ∪ {b},
Si = Si−1 ∪ {a},
′ Si+1 = Si+1 = Si−1 ∪ {a, b}.
For any stage t ∈ / {i, i + 1}, swapping positions i and i + 1 leaves both πt and St unchanged, so the corresponding factor in (5) is identical for π and π ′ and cancels in the ratio p(λ,ω) (π ′ )/p(λ,ω) (π). It therefore suffices to compare the contributions at stages t = i and t = i + 1. Write the stagewise factor of (5) at (x, S) as X λx exp{−β · Vω (x; S)} λx exp{−β · Vω (x; S)} · exp{−β · Vω (k; S)} = , ζλ,ω (S) k∈S λk exp{−β · Vω (k; S)} k∈S (21) where the second equality follows from the definition of ζλ,ω (S) in the proposition. With this notation, ′ F (b; Si′ ) F (a; Si+1 ) p(λ,ω) (π ′ ) = . (22) (λ,ω) F (a; Si ) F (b; Si+1 ) p (π) ′ Since Si+1 = Si+1 , the factor ζλ,ω (Si+1 ) appears once in the numerator and once in the denominator of (22) and cancels. The λ factors λa and λb likewise appear once in each, and cancel. Substituting (21) and collecting the surviving terms yields n o ζλ,ω (Si ) p(λ,ω) (π ′ ) . (23) = exp − β Vω (b; Si′ ) + Vω (a; Si+1 ) − Vω (a; Si ) − Vω (b; Si+1 ) · (λ,ω) ζλ,ω (Si′ ) p (π) F (x; S) := P
P It remains to evaluate the bracketed exponent. Using Vω (x; S) = j∈S ωxj and the convention ωxx = 0, X X Vω (b; Si′ ) = ωbj , Vω (a; Si+1 ) = ωaj + ωab , j∈Si−1
X
Vω (a; Si ) =
j∈Si−1
ωaj ,
Vω (b; Si+1 ) =
j∈Si−1
X
ωbj + ωba .
j∈Si−1
Hence
Vω (b; Si′ ) + Vω (a; Si+1 ) − Vω (a; Si ) − Vω (b; Si+1 ) = ωab − ωba . Substituting into (23) gives (36). E.4
Proof of Proposition 2
Proof. Throughout we work in the multiplicative representation ω eij = exp(−βωij ) and ω ekS = Q ekj of Appendix C, and abbreviate j∈S ω X X µλ,ω (S) := λk ω ekS , sω (S) := ω ekS . k∈S
k∈S
Under the Scenario 1 total order, ω eij = ω e0 for i < j and ω eij = 1 otherwise (with the convention ω eii = 1), so for every k ∈ [n] and S ⊆ [n], |{j∈S: j>k}|
ω ekS = ω e0
.
(24)
By (44) and linearity of the ROV, X cj · Pπ∼p(λ,ω) i is the last member of Tj in π , ψi (U ) =
(25)
j: i∈Tj
so it suffices to fix one interval T = Tj = {ℓ, . . . , r} (writing ℓ = ℓj , r = rj ) and prove λi ω e0r−i Pπ∼p(λ,ω) i is the last of T in π = Pr , e0r−k k=ℓ λk ω 18
i ∈ T.
(26)
We first observe that the GPASV distribution admits a particularly clean form under Scenario 1. By (24), for any S ⊆ [n] with |S| = t, sω (S) =
X
|{j∈S: j>k}|
ω e0
=
t−1 X
ω e0q ,
q=0
k∈S
because the exponent |{j ∈ S : j > k}| ranges over {0, 1, . . . , t − 1} as k ranges over S, regardless of which elements of [n] populate S. Hence sω (St ) depends on π only through |St | = t, and Q n t=1 sω (St ) is a π-independent constant. Substituting into (5) (equivalently (11)) yields p(λ,ω) (π) ∝
n Y λπt ω eπSt t
µ (St ) t=1 λ,ω
,
(27)
which is exactly the joint law of the following backward sequential sampler: set Sn = [n], and for t = n, n − 1, . . . , 1, draw P(πt = k | St ) =
λk ω ekSt , µλ,ω (St )
k ∈ St ,
(28)
then set St−1 := St \ {πt }. Under this sampler, the last member of T to appear in π (in the forward ordering) is the first T -element drawn in reverse time. Define the reverse-time stopping stage τ := max{t ∈ [n] : πt ∈ T }. At stage τ no T -element has yet been drawn, so T ⊆ Sτ , and (28) gives λi ω eiSτ , ekSτ k∈T λk ω
P(πτ = i | Sτ , πτ ∈ T ) = P
i ∈ T.
(29)
By (24), for k ∈ T = {ℓ, . . . , r}, |{j ∈ Sτ : j > k}| = |{j ∈ T : j > k}|+|{j ∈ Sτ \T : j > k}| = (r−k)+|{j ∈ Sτ \T : j > k}|. Since [n] \ T = {1, . . . , ℓ − 1} ∪ {r + 1, . . . , n} and k ∈ [ℓ, r], the set {j ∈ [n] \ T : j > k} equals {r + 1, . . . , n}, which is independent of the choice of k ∈ T . Writing |S ∩{r+1,...,n}|
C(Sτ ) := ω e0 τ
,
we therefore have ω ekSτ = ω e0r−k · C(Sτ ) for every k ∈ T , and the factor C(Sτ ) cancels between numerator and denominator of (29): λi ω e0r−i . e0r−k k=ℓ λk ω
P(πτ = i | Sτ , πτ ∈ T ) = Pr
The right-hand side does not depend on Sτ , and τ is well-defined almost surely (some T -element is eventually drawn), so marginalization yields (26). Substituting into (25) completes the proof. E.5
Proof of Proposition 3
Proof. We retain the notation ω ekS , sω (S), and µλ,ω (S) from the proof of Proposition 2. Specializing (44) to Tj = Bj and using linearity of the ROV, for i ∈ Bj , ψi (U ) = cj · Pπ∼p(λ,ω) i is the last of Bj in π , (30) so it suffices to show that Pπ∼p(λ,ω) i is the last of Bj in π =
1 , |Bj |
i ∈ Bj .
(31)
We will prove (31) by exhibiting a bijection of [n] that leaves the GPASV distribution invariant and acts as a single cycle on Bj . Let Bj = {b1 , b2 , . . . , bm } with m = |Bj |, labeled so that the withinblock directed cycle is b1 → b2 → · · · → bm → b1 , and adopt the cyclic convention bm+1 := b1 19
throughout this proof. Thus ω ebs bs+1 = ω ejcyc for s = 1, . . . , m (the common within-block cycle weight), while every other ordered within-block pair is a non-edge with ω e -value 1. Define the bijection ϕ : [n] → [n] by ϕ(bs ) = bs+1 (s = 1, . . . , m),
ϕ(x) = x for x ∈ [n] \ Bj .
We first establish the pairwise invariance ω eϕ(k)ϕ(ℓ) = ω ekℓ ,
k, ℓ ∈ [n].
(32)
If k, ℓ ∈ Bj , the shift s 7→ s + 1 preserves the cycle edge set {(bs , bs+1 ) : s = 1, . . . , m} (using the convention bm+1 = b1 ) and its common weight ω ejcyc , so both sides of (32) agree (either both equal cyc ω ej or both equal 1). If k ∈ Bj and ℓ ∈ Bm′ with Bm′ ̸= Bj , then by assumption ω ekℓ is constant in (k, ℓ) ∈ Bj × Bm′ (the block-pair common weight if Bj → Bm′ is a block edge, otherwise 1), and ϕ(ℓ) = ℓ, hence ω eϕ(k)ϕ(ℓ) = ω eϕ(k)ℓ = ω ekℓ ; the case k ∈ / Bj , ℓ ∈ Bj is symmetric, and the case k, ℓ ∈ / Bj is trivial since ϕ fixes both arguments. Moreover λϕ(k) = λk for all k ∈ [n], since λ is constant on Bj and ϕ fixes every element of [n] \ Bj . From (32) we obtain, for every k ∈ [n] and S ⊆ [n], Y Y ϕ(S) ω eϕ(k) = ω eϕ(k)ϕ(ℓ) = ω ekℓ = ω ekS , ℓ∈S
(33)
ℓ∈S
where the first equality uses the reindexing ℓ 7→ ϕ(ℓ) of the product over ϕ(S). Consequently sω (ϕ(S)) = sω (S) and, since λϕ(k) = λk , µλ,ω (ϕ(S)) = µλ,ω (S). For any permutation π = (π1 , . . . , πn ) ∈ Π, write ϕ(π) := (ϕ(π1 ), . . . , ϕ(πn )) for the componentwise action of ϕ on the tuple π; since ϕ is a bijection on [n], ϕ(π) ∈ Π as well. Denote its prefix sets ′ by π ′ := ϕ(π), so that πt′ = ϕ(πt ) and Stπ = ϕ(Stπ ). Combining the three invariances above, each stagewise factor of (5) is preserved under π 7→ π ′ : Sπ
′
λπt′ ω eπ′t t
′
µλ,ω (Stπ )
′ · sω (Stπ ) =
Sπ
λπt ω eπtt · sω (Stπ ). µλ,ω (Stπ )
Taking the product over t = 1, . . . , n yields p(λ,ω) (ϕ(π)) = p(λ,ω) (π),
π ∈ Π.
(34)
It remains to convert (34) into uniformity of the last-of-Bj element. Define t⋆ (π) := max{t ∈ [n] : πt ∈ Bj } and L(π) := πt⋆ (π) . Because ϕ(Bj ) = Bj , for π ′ = ϕ(π) we have {t : πt′ ∈ Bj } = {t : πt ∈ Bj }, so t⋆ (π ′ ) = t⋆ (π) and L(ϕ(π)) = πt′ ⋆ (π) = ϕ(πt⋆ (π) ) = ϕ(L(π)). Combining this equivariance with (34) and bijectivity of ϕ, for every i ∈ Bj , P L(π) = i = P L(ϕ(π)) = ϕ(i) = P L(π) = ϕ(i) . Since ϕ acts on Bj as a single m-cycle, iterating this identity shows that P(L(π) = i) is constant in i ∈ Bj , so it equals 1/|Bj |. This proves (31), and substitution into (30) gives ψi (U ) = cj /|Bj | for i ∈ Bj .
F
Computational Details for GPASV
Section 4 outlines the high-level computational pipeline. This appendix collects the detailed derivations and algorithms. F.1
Permutation Sampling
GPASV is defined as an expectation under p(λ,ω) , so the principal computational primitive is sampling permutations from this distribution. We describe an adjacent-swap Metropolis–Hastings sampler with a local acceptance ratio (Section F.1.1), and a greedy initialization that mirrors the GPASV choice factor (Section F.1.2). 20
F.1.1
Adjacent-Swap Metropolis–Hastings Sampler
GPASV is defined as an expectation with respect to a permutation distribution on the full space Π. Accordingly, the main computational task is to sample permutations approximately from p(λ,ω) . Adjacent-swap Metropolis-Hastings (MH) is a canonical local approach for sampling permutations, both in uniform and non-uniform settings [22, 4, 26]. We adopt this proposal because it preserves the permutation structure while allowing the target distribution to be the GPASV distribution on the full space Π. Let p be any target distribution on Π and let q(π, π ′ ) be a proposal kernel. The general MH acceptance probability is p(π ′ )q(π ′ , π) ′ AMH (π, π ) := min 1, . (35) p(π)q(π, π ′ ) In our implementation, given the current permutation π = (π1 , . . . , πn ), we choose an index i ∈ [n − 1] uniformly at random and propose π ′ by swapping the adjacent pair a := πi , b := πi+1 . This adjacent-swap proposal is symmetric, so q(π, π ′ ) = q(π ′ , π) and the proposal term in (35) cancels. Therefore the acceptance probability reduces to p(λ,ω) (π ′ ) ′ AMH (π, π ) = min 1, (λ,ω) . p (π) Proposition 1 (Local Adjacent-Swap Ratio for GPASV). Let π ′ ∈ Π be obtained from π ∈ Π by swapping the adjacent pair (a, b) = (πi , πi+1 ) at positions (i, i + 1). Write Si′ = {π1 , . . . , πi−1 , b},
Si = {π1 , . . . , πi−1 , a}, and define, for any nonempty S ⊆ [n],
P k∈S λk exp{−β · Vω (k; S)} ζλ,ω (S) := P . k∈S exp{−β · Vω (k; S)} Then
ζλ,ω (Si ) p(λ,ω) (π ′ ) = exp{−β(ωab − ωba )} · . ζλ,ω (Si′ ) p(λ,ω) (π)
(36)
Proposition 1 shows that the acceptance ratio depends only on the swapped pair (a, b) and the two competing sets Si , Si′ , not on the entire permutation. This locality is the key structural reason why adjacent-swap MH remains practical for GPASV. Algorithm 1 summarizes the resulting sampler. F.1.2
Greedy Initialization
Algorithm 1 is valid for any initial permutation π (0) ∈ Π, but in practice, initialization can matter because GPASV lives on the full permutation space Π while the adjacent-swap proposal is purely local. This is especially relevant in concentrated regimes, where a poor starting permutation can increase the transient cost before the chain reaches a representative high-probability region. In a DAG, this issue is comparatively mild. A zero-violation initialization is easy to obtain, since finding one linear extension is computationally feasible (e.g. Kahn’s algorithm [19]). By contrast, on a general directed graph a linear extension may not exist at all; a good starting permutation must instead balance unavoidable edge violations against node-wise priorities. Rather than solving a separate global optimization problem, we use a stagewise greedy initialization that mirrors the GPASV choice factor itself. For a current P remaining set R ⊆ [n] and a player i ∈ R, the quantity exp{−β · Vω (i; R)} = exp{−β j∈R ωij } is exactly the stage-wise edge factor incurred when i is placed at the current rightmost position relative to the other players still in R. Larger values of this factor (equivalently, smaller Vω (i; R)) correspond to fewer or weaker immediate priority violations, while neutral nonedges (ωij = 0) contribute factor 1. The strategy constructs the permutation backward. At each step it samples a player with probability proportional to the local GPASV choice factor λi exp{−β · Vω (i; R)}, places that player at the rightmost unfilled position, and removes it from the remaining set. 21
Algorithm 1 Adjacent-swap MH for sampling from p(λ,ω) Require: Parameters (λ, ω), lazy probability ξ ∈ [0, 1), burn-in B, thinning τ , target sample size NMC 1: Initialize π (0) ∈ Π via Algorithm 2 2: Initialize the sample set T ← ∅ 3: for t = 1 to B + τ (NMC − 1) + 1 do 4: Set π (t) ← π (t−1) 5: with probability 1 − ξ do 6: Draw i uniformly from [n − 1] (t−1) (t−1) 7: Let a ← πi and b ← πi+1 ′ 8: Form π by swapping the adjacent pair (a, b) 9: Compute the local ratio in (36) 10: Accept π ′ with probability min{1, p(λ,ω) (π ′ )/p(λ,ω) (π (t−1) )} 11: if accepted then 12: π (t) ← π ′ 13: end if 14: end with 15: if t > B and (t − B − 1) mod τ = 0 then 16: Append π (t) to T 17: end if 18: end for 19: return T Algorithm 2 Greedy initialization for GPASV Require: Parameters (λ, ω) 1: Initialize the remaining set R ← [n] 2: for t = n down to 1 do 3: For each i ∈ R, compute the weight w(i; R) ← λi exp{−β · Vω (i; R)} 4: Sample i⋆ ∈ R with probability proportional to w(i; R) (0) 5: Set πt ← i⋆ 6: Update R ← R \ {i⋆ } 7: end for 8: return π (0) Algorithm 2 summarizes the resulting initialization rule. When Gω is a DAG, every maximal node in the induced subgraph on R has Vω (i; R) = 0, whereas every non-maximal node has Vω (i; R) > 0. Thus Algorithm 2 systematically favors maximal nodes (whose stage-wise factor equals 1) while still retaining the node-weight term λi in the local sampling weights. In the hard-priority limit β → ∞, non-maximal nodes receive vanishing relative weight, so the rule collapses to a λ-weighted randomized linear extension. F.2
GPASV Estimators
We use two estimators for the GPASV target in (2): a direct permutation-based Monte Carlo estimator and a subset-reweighted surrogate estimator. F.2.1
Direct Permutation Monte Carlo
The most direct estimator follows from the random order value representation in (2). A natural choice is to sample permutations π (1) , . . . , π (NMC ) from p(λ,ω) and average the corresponding marginal contributions along those permutations. This mirrors the standard permutation-based estimator for the classical Shapley value, where the order distribution is uniform over Π [6]. Define the marginal contribution ∆i (π; U ) := U (π i ∪ {i}) − U (π i ). 22
Then, if π (1) , . . . , π (NMC ) ∼ p(λ,ω) , the direct estimator is ψbiMC (U ) :=
1
N MC X
NMC m=1
∆i (π (m) ; U ).
(37)
Its finite-sample behavior is controlled by the quality and effective size of the sampled permutation pool. F.2.2
Surrogate-Assisted Subset Estimator
The second route provides a bridge between GPASV computation and a line of semivalue estimation methods familiar in data valuation and feature attribution. Semivalues are a class of attribution rules that generalize the Shapley value by relaxing the efficiency (E in Appendix B) [10]: fixing Pn−1 n−1 a = 1 is defined by n, a semivalue with weights a , . . . , a satisfying a ≥ 0 and s 0 n−1 s s=0 s P φi (U ) = S⊆[n]\{i} a|S| U (S ∪ {i}) − U (S) . Unlike a random order value, semivalues average subset-based marginal contributions rather than marginal contributions along sampled permutations. Existing semivalue estimators differ in their observation design and in the rule used to recover the target from sampled utilities; these include regression-based methods [32, 15, 14], direct weightedaverage methods [28, 40], and surrogate-adjusted residual estimators [43]. A recent work [30] shows that these can be described by a unified framework. We adapt [30] and extend its method to the setting where the priority relationship between data points should be considered. The main obstacle is that GPASV is not a semivalue in general: random order values including GPASV may break symmetry, whereas semivalues need not satisfy efficiency. Nevertheless, the subset-linear viewpoint remains useful. Following [28, 30], we first rewrite a semivalue as a pure weighted sum over subsets: X φi (U ) = ρi (S)U (S), ρi (S) = 1{i ∈ S}ρ+ / S}ρ− i (S) − 1{i ∈ i (S), S⊆[n] − with ρ+ i (S) = a|S|−1 , ρi (S) = a|S| . The signed coefficient ρi (S) depends on whether i belongs − to S, but the positive and negative subset weights ρ+ i (S) and ρi (S) are anonymous functions of coalition size, and known in closed form for several semivalues including the (beta) Shapley value [38, 25] and the (weighted) Banzhaf value [1, 27].
Random order values admit an analogous subset-based representation, but the positive and negative coefficients depend on the player i and the actual subset S. If a random order value is induced by a distribution p on Π, i i ρ+ ρ− i (S) = Pπ∼p π = S \ {i} , i (S) = Pπ∼p π = S . For GPASV, p = p(λ,ω) , so these coefficients depend on the player, the actual subset, and the priority structure encoded by (λ, ω); they are not cardinality-based closed-form weights. To make the semivalue-style construction usable, we first draw and store utility-free permutations π e(1) , . . . , π e(M ) ∼ p(λ,ω) and estimate these coefficients by ρbi (S) :=
M i 1 Xh 1{i ∈ S}1{(eπ(r) )i = S \ {i}} − 1{i ∈/ S}1{(eπ(r) )i = S} . M r=1
(38)
To build a shared proposal over subsets, we use b A(S) :=
n X
|b ρi (S)|,
b Sbρ := {S ⊆ [n] : A(S) > 0},
qb(S) := P
b A(S) , b b A(T )
S ∈ Sbρ .
T ∈Sρ
i=1
This allocates more mass to subsets that carry larger aggregate coefficient magnitude across players. Assume the proposal qb satisfies qb(S) > 0 whenever ρi (S) ̸= 0 for some i. With γi (S) := ρi (S)/b q (S) and γ bi (S) := ρbi (S)/b q (S), GPASV admits the rewritten form ψi (U ) = ES∼bq [γi (S)U (S)] . 23
Since random order values still obey linearity, for any fixed surrogate h, ψi (U ) = ψi (h) + ψi (U − h). Hence, conditional on a fixed proposal qb with valid support and using exact ρi , the estimator ψi (h) +
Kadjust
1
X
Kadjust
γi (S (k) ) U (S (k) ) − h(S (k) ) ,
S (k) ∼ qb,
k=1
is unbiased for ψi (U ), where Kadjust is the number of residual-correction subsets. In practice we use the plug-in form below with ρbi : ψbi2stage := ψbi (b h) +
Kadjust
1
X
Kadjust
γ bi (S (k) ) U (S (k) ) − b h(S (k) ) ,
S (k) ∼ qb.
(39)
k=1
It remains to specify how b h is obtained. We fit the surrogate on training subsets sampled independently from qb, separately from the subsets later used for residual correction. Given Ktrain evaluated training subsets T (1) , . . . , T (Ktrain ) ∼ qb and a surrogate class H, we adapt the weighted least squares procedure in [30] to the GPASV setting by defining b h ∈ arg min h∈H
KX train
n o2 c (T (ℓ) ) U (T (ℓ) ) − h(T (ℓ) ) , W
c (S) := W
n X ρbi (S)2 i=1
ℓ=1
qb(S)2
.
c (S) emphasizes subsets that contribute more strongly to the vector of GPASV coordiThe weight W nates. Pn For a linear surrogate [32] with fitted form b hlin (S) = U (∅)+ k=1 b ak 1{k ∈ S}, we have ψbi (b hlin ) = b ai . For a quadratic surrogate [15] with selected interaction set I ⊆ {{k, ℓ} : 1 ≤ k < ℓ ≤ n}, b hquad (S) = U (∅) +
n X
b ak 1{k ∈ S} +
X
bbkℓ 1{k, ℓ ∈ S},
{k,ℓ}∈I
k=1
where bbkℓ = bbℓk and bbij = 0 if {i, j} ∈ / I. For brevity in the calculations below, let πi−1 ∈ [n] denote the position of player i in π, i.e., πi−1 = t iff πt = i; the prefix set π i from (2) can then be written as π i = {j ∈ [n] : πj−1 < πi−1 }. With this notation, the one-step marginal term satisfies P b ∆i (π; b hquad ) = b ai + bij 1{π −1 < π −1 }. Taking expectation over π ∼ p(λ,ω) yields j
j̸=i
ψbi (b hquad ) = b ai +
i
X
ηjibbij ,
ηji := Pπ∼p(λ,ω) πj−1 < πi−1 .
j̸=i
In practice these pairwise probabilities are estimated from previously stored utility-free permutations: M
ηbji :=
o 1 X n (r) −1 1 (eπ )j < (eπ(r) )−1 . i M r=1
We use a fixed training/correction split for simplicity; optimizing this allocation for the two-stage estimator is orthogonal to GPASV and left to future work. F.3
Acceleration via Computational Reuse
The sampler above addresses the distributional side of GPASV, but in many applications the dominant cost is not the MH move itself. Rather, it is often the repeated evaluation of the cooperative game. This imbalance is well known in the broader Shapley literature: in feature attribution, utility evaluation may require many model inferences [32]; in data valuation, it may require repeated model retraining [16, 40]. This motivates two complementary acceleration mechanisms: reusing utility evaluations on repeated subsets, and reusing permutations across nearby target distributions. 24
F.3.1
Utility Reuse Across Repeated Subsets
The utility-caching mechanism described here applies to both estimators in Sections F.2.1 and F.2.2. Given sampled permutations π (1) , . . . , π (NMC ) , estimating GPASV requires the marginal contributions ∆i (π (m) ; U ) from (37): ∆i (π (m) ; U ),
i ∈ [n], m ∈ [NMC ],
Each term is determined by a subset induced by the relative order in π (m) . Because adjacent-swap proposals modify permutations only locally, and because many sampled permutations share long initial segments, the same subset often appears repeatedly across MCMC iterations and across players. We therefore maintain a cache of utility evaluations indexed by the subset itself. Whenever a subset S is encountered for the first time, we evaluate U (S) once and store the result; every later appearance of the same subset reuses the cached value. The same cache applies whether S arises as a permutation prefix or as a subset sampled from qb in the surrogate estimator. This does not change the estimator at all, but it can reduce the number of expensive utility calls by a large factor. The practical consequence is that the total runtime separates naturally into two parts: runtime ≈ (# unique subsets) × (cost per utility evaluation) + (sampling overhead). This decomposition is particularly important in applications such as LLM evaluation, where utility computation can be much more expensive than sampling permutations. F.3.2
SNIS for Permutation Reuse Across Priority Sweeps
The second acceleration mechanism is useful when the target distribution changes but the underlying attribution problem remains fixed. A canonical case is priority sweeping. Section 3.5 sweeps a single λi over (0, ∞) to probe the sensitivity of one player’s valuation. A useful complementary view, when e (with the relative scales among players are themselves meaningful, is to fix a latent node priority λ e λi ≥ 0) and control its overall strength through a scalar temperature α ≥ 0 via ei }. λi := exp{−αλ (40) α is its λ-side analogue of β: α = 0 removes the soft-priority contrast (all λi ≡ 1), while α → ∞ ei progressively earlier in π. Substituting (40) into (5) yields a twopushes players with larger λ parameter family (λ,ω) pα,β (π) := p(λ,ω) (π) , ei } λi =exp{−αλ
and a sweep traces a continuous curve in (α, β)-space rather than along a single coordinate. This is the parameterization used, e.g., in our LLM application (Section 6). Within such a sweep, instead of redrawing a full Monte Carlo sample at every new (α, β), we may reuse previously sampled permutations through importance weighting. Let (λ,ω)
p(π) := pα,β (π),
(λ,ω)
p′ (π) := pα′ ,β ′ (π),
and let pe and pe′ denote the corresponding unnormalized PMFs. Equivalently, we may write pe(π) pe′ (π) p(π) = , p′ (π) = , Zp Z p′ where the normalizing constants Zp and Zp′ are intractable in general. Thus, although evaluating the ratio pe′ (π)/e p(π) is straightforward, directly using the ordinary importance-sampling correction would still require the unknown ratio Zp /Zp′ . Self-normalized importance sampling avoids this obstacle by estimating that ratio from the same weighted sample [18]. If π (1) , . . . , π (N ) ∼ p, define the importance weights pe′ (π (m) ) , m ∈ [N ]. w(m) := pe(π (m) ) Before introducing reuse, applying the direct estimator (37) under the target distribution p′ would require fresh samples π (1) , . . . , π (N ) ∼ p′ . With the importance weights above, however, the same pool π (1) , . . . , π (N ) ∼ p delivers a valid self-normalized estimator of GPASV at the new target p′ : PN w(m) ∆i (π (m) ; U ) SNIS b ψi (U ) := m=1PN , i ∈ [n]. (41) (m) m=1 w 25
This justifies permutation reuse across nearby temperature settings. As an aside, computing only the numerator of (41) and then rescaling the resulting vector so that its coordinates sum to U ([n]) − U (∅) recovers exactly (41) itself; this follows immediately from the efficiency axiom. To monitor the quality of this reuse, we use the usual effective sample size [23], defined as P 2 N (m) w m=1 . ESS := PN (m) )2 m=1 (w
(42)
For example, suppose that one first samples permutations at (α, β) = (0, 0) and then moves to a nearby target such as (1, 0). Once (42) is computed and the desired Monte Carlo budget at the new target is N , one may draw only Nnew := max{0, N − ⌊ESS⌋} fresh permutations π e(1) , . . . , π e(Nnew ) ∼ p′ . One may then combine them with the reused sample through the hybrid estimate below: PN Nnew (m) ∆i (π (m) ; U ) Nnew ESS 1 X m=1 w + ∆i (e π (r) ; U ). ψbihyb (U ) := PN (m) ESS + Nnew ESS + N N new new w r=1 m=1 When Nnew = 0, the second term is omitted. This hybrid estimate interprets the reused sample as contributing roughly ESS effective draws and fills the remaining budget with fresh target samples. In this way, ESS serves as an operational measure of how much of the next budget can be inherited from the previous point in the sweep.
G
Additional Details and Results for Empirical Studies in Section 5
This appendix collects the implementation details and full empirical results of the three simulation studies in Section 5. All experiments in this appendix are CPU-only and were run on the Unity high-performance computing cluster, provided by the College of Arts and Sciences at The Ohio State University across multiple Intel Xeon CPUs; the runtime-reporting experiments were pinned to Intel Xeon Platinum 8468 CPU with 128 GB RAM to keep wall-clock times comparable across configurations. G.1
Simulation 1: Mixing Behavior of MCMC
Sampling π ∼ p(λ,ω) from (5) relies on an adjacent-swap Metropolis–Hastings chain (Algorithm 1), whose mixing time is not known in closed form. We provide a practical way to declare the chain mixed, describe the setup used for the grid of graphs in Section 5, explain the exact pairwise-order target against which the chain is compared, and report the full mixing-time grid that the main text only shows for one representative panel. Throughout Section G.1 we work in the multiplicative representation of GPASV introduced in Appendix C, which absorbs the temperature β into the edge weights and makes the weak/strongpriority regimes easier to parametrize. G.1.1
Mixing Diagnostic and Threshold Protocol
In the classical theory of Markov chains, the mixing time is defined as the first t at which the total variation between the chain’s distribution at step t and its stationary distribution falls below a target threshold; once that is met, any functional of the chain is guaranteed to be close to its stationary expectation up to a uniform constant. On the permutation space Π, however, directly tracking this total variation is combinatorially out of reach: even representing the chain’s current distribution over Π already requires O(n!) numbers, and the stationary distribution p(λ,ω) in (5) does not admit a closed-form normalizer. We therefore follow Talvitie et al. [39] and diagnose mixing empirically through pairwise-order probabilities and compare the resulting practical mixing times against reference growth rates from the literature. (rand) (greedy) Let Pbt (i ≺ j) and Pbt (i ≺ j) denote the empirical probability that player i appears before player j after t proposal steps under random and greedy initialization, respectively. For each
26
initialization scheme, we track the worst-case pairwise-order deviation from the stationary target P ⋆ (i ≺ j) := Pπ∼p(λ,ω) (i appears before j): (init)
Dt
:=
(init) Pbt (i ≺ j) − P ⋆ (i ≺ j) ,
max i,j∈[n],i̸=j
init ∈ {rand, greedy}.
(init)
(43) (init)
The quantity Dt is the primary mixing diagnostic, and we report the first t at which Dt falls below the target threshold ϵ = 1/4 as the practical mixing time. Comparing random against greedy initialization isolates how much of the practical speedup is attributable to initialization alone. (init)
In practice, Dt is evaluated at doubling checkpoints t = 1, 2, 4, . . . up to a horizon T (n) := ⌈n3 log n⌉, and the first crossing is localized by binary search between consecutive checkpoints. A guard band ϵ0 = 0.02 prevents Monte Carlo noise from producing spurious crossings. That (init) is, a crossing is certified only once Dt ≤ ϵ − ϵ0 , while values in [ϵ − ϵ0 , ϵ + ϵ0 ] are handled conservatively during the binary search. If no crossing is observed before T (n), the replicate is recorded as not mixed within the simulated horizon. The greedy scheme follows Algorithm 2, and the random scheme draws the starting permutation uniformly from Π. G.1.2
Experimental Setup
Experiments cover n ∈ {4, 6, 8, . . . , 22}, which is the range where the ground-truth P ⋆ in (43) can be computed exactly by the dynamic program described below; beyond that, exact pairwise probabilities are no longer tractable. Graphs are drawn from two families. In the DAG family, each ordered pair (i, j) with i < j is included as an edge independently with probability pedge ; the resulting graph is automatically acyclic. In the general directed-graph family, each ordered pair (i, j) with i ̸= j is included independently with probability pedge , so the graph may contain cycles. We run pedge ∈ {0.2, 0.8, 1.0} to cover sparse, dense, and saturated regimes. iid
Node weights are sampled as λi ∼ Unif(1, Uλ ) with Uλ ∈ {1, 100}; Uλ = 1 gives a homogeneous regime λi ≡ 1, and Uλ = 100 gives a heterogeneous regime. On present edges, the multiplicative iid edge weight ω eij is sampled as ω eij ∼ Unif(Lωe , Uωe ) with (Lωe , Uωe ) ∈ {(0, 0.5), (0.5, 1)}, corresponding to a strong and a weak pairwise-priority regime respectively (recall ω eij → 0 is the hard limit and ω eij = 1 is no priority). Non-edge pairs are assigned ω eij = 1, so that they contribute a neutral factor to the stage-wise form (12). For each parameter setting, we run 1000 independent adjacent-swap MH chains in Algorithm 1 per initialization scheme, with lazy probability 1/2 to remove periodicity of the adjacent-swap proposal. Each setting is replicated over five graph draws and, within each graph draw, five initialization draws; the saturated graph (pedge = 1) is deterministic, so only one graph draw is used there. Within each initialization replication, the 1000 chains share the starting permutation but use independent MCMC seeds. G.1.3
Exact Pairwise-Order Ground Truth
The diagnostic (43) requires the stationary pairwise-order probabilities P ⋆ (i ≺ j) under p(λ,ω) . Computing all n(n − 1) pairwise probabilities by enumeration over Π costs O(n2 n!) time, which is already infeasible at n = 22. We instead adapt the subset dynamic programming (DP) of Kangas et al. [21], originally designed for the uniform distribution on linear extensions of a DAG, to the non-uniform GPASV distribution on the full Π. Working in the multiplicative representation from Appendix C, the GPASV mass function can be written as n Y pe(π) p(λ,ω) (π) = , pe(π) = ℓλ,eω (πt ; St (π)), Z t=1 where the stage-wise factor at step t is, reading off (11), X λi ω eiS · ω eS , S ek k∈S k k∈S λk ω
ℓλ,eω (i; S) := P
27
i ∈ S,
ω ekS :=
Y r∈S\{k}
ω ekr .
Algorithm 3 Dynamic programming computation of P ⋆ (i ≺ j) under GPASV. Require: Node weights λ, multiplicative pairwise weights ω e 1: for all nonempty S ⊆ [n] do 2: for all i ∈ Q S do 3: ω eiS ← r∈S\{i} ω eir 4: end for 5: for all i ∈ S do P P ekS ekS 6: ℓλ,eω (i; S) ← λi ω eiS k∈S ω k∈S λk ω 7: end for 8: end for 9: A(∅) ← 1 10: for s = 1 to n do 11: for all S ⊆ [n] Pwith |S| = s do 12: A(S) ← i∈S A(S \ {i}) ℓλ,eω (i; S) 13: end for 14: end for 15: Z ← A([n]) and B([n]) ← 1 16: for s = n − 1 down to 0 do 17: for all S ⊆ [n] Pwith |S| = s do 18: B(S) ← k∈S ω (k; S ∪ {k}) B(S ∪ {k}) / ℓλ,e 19: end for 20: end for 21: Initialize P ⋆ (i ≺ j) ← 0 for all i, j 22: for all j ∈ [n] do 23: for all S ⊆ [n] \ {j} do 24: C ← A(S) ℓλ,eω (j; S ∪ {j}) B(S ∪ {j})/Z 25: for all i ∈ S do 26: P ⋆ (i ≺ j) ← P ⋆ (i ≺ j) + C 27: end for 28: end for 29: end for 30: Set the diagonal to zero and rescale complementary pairs to sum to one 31: return P ⋆ Intuitively, ℓλ,eω (i; S) is the contribution i last in prefix S: the first quotient is the conditional P of placing probability of that step, and the sum k ω ekS is the state rescaling. Let A(S) be the total unnormalized mass over all partial orders whose prefix is S, built up from shorter prefixes by inductively placing one more element last: X A(∅) = 1, A(S) = A(S \ {i}) ℓλ,eω (i; S). i∈S
Then Z = A([n]). Similarly, let B(S) be the total unnormalized mass of all completions from prefix S to the full set: X B([n]) = 1, B(S) = ℓλ,eω (k; S ∪ {k}) B(S ∪ {k}). k∈S /
Combining the prefix mass, the step that inserts j at the end, and the continuation mass gives, for i ̸= j, X 1 P ⋆ (i ≺ j) = A(S) ℓλ,eω (j; S ∪ {j}) B(S ∪ {j}). Z S⊆[n]\{j} i∈S
Each summand is the unnormalized mass of permutations whose prefix immediately before j’s insertion is S; the condition i ∈ S picks out the permutations in which i is earlier than j. After the DP, we set P ⋆ (i ≺ i) = 0 and, for numerical stability at larger n, rescale each complementary pair {P ⋆ (i ≺ j), P ⋆ (j ≺ i)} to sum to one. The whole procedure runs in O(n2 2n ) time, replacing the O(n2 n!) enumeration cost. This is what makes exact ground-truth computation tractable up to n = 24. Algorithm 3 summarizes the resulting DP procedure. 28
G.1.4
Two Special Regimes and Reference Rates
Two limiting regimes give useful reference points for reading the mixing plot. Both correspond to the e Gω . hard-priority limit ω eij → 0 on every present edge, which by Theorem 2 concentrates p(λ,ω) on Π e Gω = ΠGω and the limit is uniform on the linear extensions of Gω , When Gω is a DAG and λi ≡ 1, Π which is exactly the target distribution of PSV. When Gω is the saturated directed graph (pedge = 1) with λi ≡ 1, every π incurs the same total raw violation, so the limit becomes uniform on the full Π, which is the target of the standard Shapley value. These two regimes bound the sampling difficulty within our grid and motivate the reference growth lines n2 and (4/π 2 ) n3 log n that we overlay in the mixing figures; the former is the practical mixing rate reported by Talvitie et al. [39], and the latter is the known best theoretical rate [4, 42]. G.1.5
Full Results
Figure 9 reports practical mixing times across the full grid described above. Panels separate the DAG and general directed graph families, the density pedge , the node heterogeneity Uλ , and the weak/strong edge-priority regime. Greedy initialization tracks or beats random initialization throughout the grid, and the gap is largest in dense and saturated regimes, where random initialization often fails to cross the threshold within the T (n) horizon. The greedy-initialized curves remain close to the n2 reference in saturated regimes and close to the n3 log n reference in sparse DAG regimes, matching the two limiting targets discussed above.
pedge = 0.2
pedge = 0.8
pedge = 1.0
DAG
104 103 102 101
General Graph
100 104 103 102 101 100
4
6
8
1, 1,
10 12 14 16 18 20 22
n
Unif(0, 0.5) Unif(0.5, 1)
4
6
8
10 12 14 16 18 20 22
n Unif(1, 100), Unif(0, 0.5) Unif(1, 100), Unif(0.5, 1) Greedy Random 4 n 3logn n2 (ideal) 2
4
6
1, 1,
8
10 12 14 16 18 20 22
n 0 (PSV) 0 (SV)
Figure 9: Practical mixing-time diagnostic for the adjacent-swap MH chain on GPASV. Solid curves use greedy initialization (Algorithm 2); dashed curves use uniform random initialization. Both axes are in log-scale, so the slope of each curve corresponds to the empirical growth rate of the mixing time. Panels vary graph family (DAG vs. general directed), density pedge . Reference lines show the n2 (practical mixing time reported by Talvitie et al. [39]) and (4/π 2 )n3 log n (best known theoretical mixing time reported by Bubley and Dyer [4], Wilson [42]) growth rates. G.2
Simulation 2: Monte Carlo Accuracy and Estimator Comparison
Once the adjacent-swap MH chain is mixed, the remaining source of error is Monte Carlo noise in the ROV expectation (2). This subsection isolates that error by running the direct permutation estimator and the surrogate-assisted estimator from Section 4 on two synthetic families for which the exact GPASV value ψ ⋆ is known in closed form. We also compare the three estimators, including surrogate-assisted estimators introduced in Appendix F.2.2 under matched utility-evaluation budgets. As in Section G.1, we work in the multiplicative representation of Appendix C: the edge weight ω eij = exp(−βωij ) ∈ (0, 1], with ω eij = 1 corresponding to no pairwise priority, ω eij → 0 to the hard-priority limit, and non-edge pairs set to ω eij = 1. 29
G.2.1
Closed-Form Targets for Benchmark Scenarios
Both benchmarks belong to a common sum-of-unanimity family: U (S) =
d X
cj 1{Tj ⊆ S},
Tj ⊆ [n],
cj ≥ 0.
(44)
j=1
Under (44), the ROV marginal contribution of player i ∈ Tj to the j-th term is cj exactly when i is the last member of Tj to arrive in π, and zero otherwise. By linearity, the ROV expectation (2) therefore reduces to X ψi (U ) = cj · Pπ∼p(λ,ω) i is the last member of Tj in π , j: i∈Tj
so the two scenarios differ only in how the graph and the subset family {Tj } are chosen to make this last-arrival probability tractable. Scenario 1: line DAG with contiguous-interval utilities. Players are totally ordered 1 ≺ 2 ≺ · · · ≺ n, and every precedence edge i < j shares a common multiplicative weight ω eij ≡ ω e0 ∈ (0, 1]; non-edge pairs (i.e. i > j) take ω eij ≡ 1. The subsets Tj in (44) are contiguous intervals Tj = {ℓj , ℓj + 1, . . . , rj } of [n]. Under this structure, the last-arrival probability within each interval r −i reduces to a λ-weighted softmax in which the total-order weight ω e0 j discounts position i ∈ Tj . Proposition 2 (Closed form on Scenario 1). Let the players be arranged in the total order 1 ≺ 2 ≺ · · · ≺ n with ω eij ≡ ω e0 ∈ (0, 1] for i < j and ω eij ≡ 1 on non-edge pairs. Consider a sum-of-unanimity utility (44) with d = n2 and Tj = {ℓj , ℓj + 1, . . . , rj } a contiguous interval for each j. Then the exact GPASV value is r −i
ψi (U ) =
λi ω e0 j c j P rj r −q , e0 j q=ℓj λq ω j: i∈Tj X
i ∈ [n].
For each interval term, player i ∈ Tj receives cj exactly when i is the last element of Tj to appear in π. Under the total-order priority structure, the last-arrival probability within Tj is proportional to r −i λi ω e0 j ; normalizing over Tj and summing over j by linearity gives the stated form. The full proof is given in Appendix E.4. Scenario 2: block DAG with cyclic blocks and block-completion utilities. Partition [n] = B1 ∪ · · · ∪ BK into disjoint equal-sized blocks, and build a directed graph in which each block Bk carries an internal directed cycle, and whenever Bk → Bℓ is present in an underlying DAG on {B1 , . . . , BK }, every ordered pair (i, j) ∈ Bk × Bℓ is an edge. We take λi constant within each block; on each cycle within a block Bk we take ω eij to be a single common value, and on each present ordered block pair Bk → Bℓ we take ω eij to be a single common value over all (i, j) ∈ Bk × Bℓ . Nonedge pairs take ω eij ≡ 1. The subsets in (44) are the blocks themselves, Tj = Bj for j = 1, . . . , K, so U rewards the completion of entire blocks. Within-block cyclic symmetry, combined with equal λ’s inside a block, makes every member of Bj equally likely to be the last to arrive among Bj . Proposition 3 (Closed form on Scenario 2). Let [n] = B1 ∪ · · · ∪ BK be a partition into disjoint blocks, and let the directed graph satisfy the block-structured assumptions above: each block induces a directed cycle, every present block edge Bk → Bℓ contributes all pairs (i, j) ∈ Bk × Bℓ as edges, λi is constant within each block, each block’s cycle edges share a common weight, each present block pair shares a common weight, and non-edge pairs take ω eij ≡ 1. Consider the block-completion utility (44) with d = K and Tj = Bj . Then the exact GPASV value is cj ψi (U ) = for every i ∈ Bj . |Bj | For the block-completion term associated with Bj , only the final member of Bj to appear can receive cj . Because node weights are constant within each block and every priority factor affecting Bj ’s members is symmetric under cyclic relabeling inside Bj , each member of Bj is equally likely to be this final member. The block reward thus splits uniformly within the block, and linearity over j gives the stated form. The full proof is given in Appendix E.5. 30
G.2.2
Experimental Design
Across both scenarios we draw iid coefficients cj ∼ Unif(0.5, 1.5). The graph and priority choices specialize the closed-form setups of Proposition 2 and Proposition 3 to the two-dimensional (λ, ω e )regime grid used in the main text. For Scenario 1, we fix d = n2 and sample each interval Tj independently with replacement from the set of contiguous intervals of [n]. Node priorities follow either the homogeneous regime λi ≡ 1 or the iid
heterogeneous regime λi ∼ Unif(1, 10). The common precedence-edge weight is ω e0 ∈ {0.3, 0.7}, with ω e0 = 0.7 corresponding to the weak-priority regime (close to no priority) and ω e0 = 0.3 to the strong-priority regime. For Scenario 2, we take K = n/16 equal-sized blocks. The between-block DAG is generated by including each ordered block pair Bk → Bℓ with k < ℓ independently with probability 0.8, and every block carries a fixed internal directed cycle. Node priorities are either λi ≡ 1 or block-constant iid λi = λ0k for i ∈ Bk with λ0k ∼ Unif(1, 10). Edge priorities are block-structured: for each present bet block pair Bk → Bℓ , the pair-level common weight ω eij ≡ ω ekℓ over all (i, j) ∈ Bk × Bℓ , and within cyc bet each block Bk the cycle edges share a common weight ω ek . Both ω ekℓ and ω ekcyc are drawn either from Unif(0.5, 1) (weak-priority regime) or from Unif(0, 0.5) (strong-priority regime). Case 1–4 regimes. The two λ-regimes and the two ω e -regimes factor into four cases, shared between the two scenarios so that the ARE, AUCC, unique-subset, and runtime reports use the same column layout. The homogeneous λ-regime is identical across scenarios, while the heterogeneous one differs: Scenario 1 uses a per-player draw, whereas Scenario 2 uses the block-constant version λi = λ0k for i ∈ Bk .
G.2.3
Scenario 1 ω e0 (i < j)
Case
λi
1 2 3 4
≡1 ≡1 ∼ Unif(1, 10) ∼ Unif(1, 10)
≡ 0.7 ≡ 0.3 ≡ 0.7 ≡ 0.3
Scenario 2 bet , ω ekcyc λi (for i ∈ Bk ) ω ekℓ ≡1 ≡1 ≡ λ0k ∼ Unif(1, 10) ≡ λ0k ∼ Unif(1, 10)
∼ Unif(0.5, 1) ∼ Unif(0, 0.5) ∼ Unif(0.5, 1) ∼ Unif(0, 0.5)
Accuracy Metrics and MH Protocol
We report results for n ∈ {32, 128, 512, 2048} with a total Monte Carlo budget of NMC = 20,000 post-burn-in permutations. For each (n, Case), we fix one synthetic instance and run 10 independent MH chains with greedy initialization (Algorithm 2), burn-in ⌈n2.5 ⌉, and thinning interval 1000. Standard deviations reported throughout Section G.2 are taken across these 10 repetitions on the fixed instance. Every 100 samples we record the absolute relative error ARE(m) :=
∥ψb(m) − ψ ⋆ ∥2 , ∥ψ ⋆ ∥2
where ψb(m) is the direct Monte Carlo estimate of ψ after m post-burn-in samples and ψ ⋆ is the closed-form target from Proposition 2 or 3. We summarize the whole convergence path by the area under the convergence curve, 200
AUCC :=
1 X ARE(100ℓ), 200 ℓ=1
which penalizes slow initial convergence and high terminal error on a common scale. Every 100 samples we also record the number of distinct subsets whose utility U (S) has been evaluated up to that point, which measures cache reuse, and the cumulative non-utility runtime, which isolates sampling and bookkeeping cost from the utility evaluation. Concretely, we fix λi ≡ 1 and sweep two axes: the common edge weight ω e0 ∈ {0.1, 0.3, 0.5, 0.7, 0.9} and the burn-in exponent c in nc with c ∈ {0, 0.5, 1, 1.5, 2, 2.5}. All other MH settings match the main Section G.2 protocol. For each (e ω0 , c) we run both random and greedy initialization and report 31
AUCC. This ablation separates two questions: how much of the greedy benefit is simply a shorter burn-in substitute, and how that tradeoff depends on the pairwise-priority strength. G.2.4
Matched-Budget Surrogate Comparison Protocol
Beyond the direct permutation estimator, GPASV admits a surrogate-assisted variant that first fits a cheap surrogate b h ≈ U on a limited set of evaluated subsets and then corrects the surrogate’s GPASV by a residual term; see Section F.2.2 for the full construction. We compare three estimators: (i) the direct permutation estimator of Section 4; P (ii) a linear surrogate b h(S) = U (∅) + i∈S b ai , in which each player contributes additively; P P b ai + i,j∈S bbij that includes a randomly (iii) a quadratic surrogate h(S) = U (∅) + i∈S b chosen 10% of the pairwise interactions. Since the dominant cost of GPASV is direct utility evaluation, we compare the estimators by matching them on the number of distinct evaluated subsets. For each problem instance we first run the direct estimator and record the number Keval of distinct subsets whose U (S) was evaluated. The surrogate estimators are then given the same budget: Ktrain := min{⌊0.2 Keval ⌋, 200,000} evaluations go toward fitting b h, and the remaining Kadjust := Keval − Ktrain evaluations go toward the residual correction. The two phases share the same utility cache, so Keval is counted over the union of evaluated subsets rather than the sum. Permutation samples that do not require utility evaluation, namely those used to estimate subset coefficients and pairwise-order probabilities, do not count toward Keval ; we use M = 100,000 such utility-free permutation samples. Problem sizes are n ∈ {64, 128, 256, 512, 1024}, and all other MH settings (burn-in, thinning, greedy initialization) match the main Section G.2 setup. G.2.5
Full Results
Direct permutation estimator. Figure 10 reports ARE(m) over the sampling budget on the shared 2 × 4 Scenario×Case grid; Table 3 reports the final AUCC; Figure 11 reports the number of distinct coalition subsets evaluated; Table 4 reports the final non-utility runtime. Error drops with the sampling budget throughout the grid, and the slope flattens as n grows. Scenario 2 is harder than Scenario 1 at matched n, consistent with the extra mixing burden from within-block directed cycles. The unique-subset curves flatten as m grows, reflecting increasing cache reuse along each chain. Surrogate-assisted estimators. Figure 12 compares the direct permutation estimator with the two surrogate variants under matched utility-evaluation budgets. Surrogate methods reduce ARE in most settings, and the quadratic surrogate tends to dominate on Scenario 2 where pairwise interactions are informative. Table 5 and Table 6 report the non-utility runtime and the surrogate training memory. The gain in ARE is bought at a substantial computational cost: quadratic-surrogate runtime and memory both grow quickly with n. Unlike PASV, which can zero out bij for any pair that violates the DAG, the GPASV quadratic surrogate has to retain all sampled pairwise coefficients, so memory is harder to trim. G.3
Simulation 3: Priority Sweeping
Simulations 1 and 2 study the computational side of GPASV. Simulation 3 asks a different question: how does the attribution respond when we move a single soft-priority scalar along a sweep, and how does that response differ between GPASV and PASV? This is the empirical counterpart to the priority-sweeping diagnostic introduced in Section 3.5, and it exposes an effect that is specific to GPASV, as ω at finite β leaves more room for λ to reshape the order distribution than PASV’s binary DAG does. G.3.1
Setup: Group Selection and Utility Functions
We fix n = 32 and for each pedge ∈ {0.2, 0.5, 0.8}, draw a single DAG on [n] by including each precedence edge i < j independently with probability pedge . We then fix a single group H ⊆ [n] with |H| = n/2, and sweep two parameters: the soft-priority level λ0 on H and the hard-priority 32
strength β. Throughout, we write πi−1 for the position of player i in the permutation π, i.e. the unique t ∈ [n] with πt = i. We set λi = λ0 for i ∈ H and λi = 1 otherwise, and sweep λ0 ∈ {1, 2, 4, 8, 16, 32, 64, 128}. At λ0 = 1 all players share the same soft priority, so GPASV and PASV both assign the same value to H as to [n] \ H up to graph effects; larger λ0 progressively up-weights the members of H in the backward stage-wise softmax, making them more likely to be selected for later forward positions, hence pushing them toward the tail of π. Soft-priority sweep.
We vary the temperature β in (5) over β ∈ {1, 2, 4, 8}, and include the hard-priority extreme β → ∞ (which, on a DAG, reduces GPASV to PASV by Theorem 2) as a reference curve. Hard-priority sweep.
Utility functions. We again use the sum-of-unanimity (SOU) family from Section G.2, but now with Tk ranging over general nonempty subsets of [n] rather than contiguous intervals. Concretely, we draw d = n2 subsets T1 , . . . , Td iid uniformly from the nonempty subsets of [n] together with iid coefficients ck ∼ Unif(0.5, 1.5), and set d X U SOU (S) := ck 1{Tk ⊆ S}. k=1
For each k, the marginal value of player i ∈ Tk under the indicator 1{Tk ⊆ S} is Pπ∼p(λ,ω) i is the last member of Tk in π . Hence U SOU rewards late-positioned players. To probe the opposite end of the position axis, we additionally introduce the sum-of-race (SOR) family, obtained by replacing the indicator of Tk ⊆ S with that of Tk ∩ S ̸= ∅: d X U SOR (S) := ck 1{Tk ∩ S ̸= ∅}. k=1
For each k, the marginal value of player i ∈ Tk under 1{Tk ∩ S ̸= ∅} is Pπ∼p(λ,ω) i is the first member of Tk in π , so U SOR rewards early-positioned players. We write U SOU and U SOR throughout to distinguish the two utilities. Running the same sweep on U SOU and U SOR therefore exposes λ0 -sensitivity from two opposite ends. G.3.2
Connection to Limiting Cases
Two extremes of β bracket the sweep curves and help interpret the intermediate β’s. e Gω , and β → ∞ (hard-priority limit). By Theorem 2, the GPASV distribution concentrates on Π e Gω = ΠGω together with Mω (S) = max(S). The stage-wise factors when Gω is a DAG we have Π in (5) then reduce to PASV’s stage-wise factors in (3), so the group-sum curve at β → ∞ coincides with the PASV group-sum on the same DAG. This is the dashed reference shown in the sweep plots. Under PASV, the impact of λ0 is bounded by the hard constraints of Gω : once the DAG order is satisfied, λ can only redistribute within admissible sub-permutations, which already fixes most of the relative order of H against [n] \ H. β = 0 (no pairwise priority). When β = 0, the graph term Vω drops out of (5) and the distribution reduces to the Plackett–Luce distribution with worths (λi ) (Section 3.3). In this regime, λ0 has the largest room to move the group-sum attribution because there is no hard constraint to pull the order back; the position of each member of H is determined by the worths alone. Intermediate β ∈ {1, 2, 4, 8} interpolates between the two extremes. Because GPASV softens the hard priority at finite β, λ0 can push members of H later even when such moves violate an edge of Gω ; the softness is controlled by β. 33
G.3.3
Implementation and Baseline Computation
For each (λ0 , β) pair with finite β, we sample NMC = 10,000 after 10, 000 burn-in periods from p(λ,ω) using the adjacent-swap MH sampler (Algorithm 1) with greedy initialization (Algorithm 2). We replicate each setting over 10 independent chains and report mean and standard deviation. Along the λ0 sweep at fixed β, we reuse previous samples through the SNIS rule described in Section F.3.2, monitoring the effective sample size and drawing additional fresh samples when it falls below target. This keeps the number of utility evaluations manageable across the sweep. The PASV reference is obtained by sampling PASV permutations directly on ΠGω following the adjacent-swap MH sampler of Lee et al. [26] and estimating the group-sum PASV by the same Monte Carlo averaging, with matched sample count. For each sample we record both the position πi−1 of every member i ∈ H, used to compute the mean forward position 1 X r̄H (λ0 , β) := Eπ∼p(λ,ω) [πi−1 ], |H| i∈H
SOU by its empirical estimate and U SOR , used to form the P and the marginal contributions under U group-sum GPASV i∈H ψi (U ).
G.3.4
Full Results
FigureP 13 shows the full sweep. The left panel reports r̄H (λ0 , β), the middle and right panels report i∈H ψi (U ) under U SOU and U SOR , and the dashed black curve in each panel is the PASV reference. Three patterns are visible. First, the mean forward position is monotone in λ0 : larger λ0 pushes members of H later in the sampled order under both GPASV and PASV. Second, the slope of the position curve is steeper at smaller β, reflecting softer pairwise priority; at β = 1, λ0 moves the mean position over a wider range than at β = 8 or at β → ∞ (PASV). Third, the group-sum curves under U SOU and U SOR move in opposite directions, as expected from their definitions: the U SOU group sum rises with λ0 (more H-members arrive late and thus collect unanimity rewards), whereas the U SOR group sum falls with λ0 (fewer H-members arrive early and thus collect first-arrival rewards). The transition sharpens monotonically in β, and the β → ∞ reference tracks the β = 8 curve closely throughout, consistent with Theorem 2.
34
Scenario 2
ARE(m)
Scenario 1
Case 1
Case 2
Case 3
Case 4
100 10 1 10 2 100 10 1 10 2
10k m
0
20k 0
10k m
n = 32
20k 0
n = 128
10k m
20k 0
n = 512
10k m
20k
n = 2048
Figure 10: Monte Carlo accuracy of the direct permutation estimator, reported as ARE(m) over the post-burn-in sampling budget m. All curves use greedy initialization. Rows correspond to Scenario 1 and Scenario 2; columns correspond to Cases 1–4.
Scenario 2
Unique S's
Scenario 1
×106 Case 1
×106 Case 2 0.05
1 0 4
0.00 ×106
2
2 0
2
×106
10k m
20k
0
×106 Case 4
1
0.05
0
0.00
6 4 ×10
2
2
1 0
×106 Case 3
10k m
0
n = 32
20k
n = 128
0
×106
1 10k m
0
n = 512
0
20k
0
10k m
20k
n = 2048
Figure 11: Number of distinct coalition subsets evaluated by the direct permutation estimator, over the sampling budget. Flatter growth indicates stronger cache reuse.
Table 3: Final AUCC for the direct permutation estimator under greedy initialization. Rows index n; columns index Cases 1–4 within each scenario. Entries are mean (standard deviation) across 10 independent MH repetitions on the fixed instance. Scenario 1
Scenario 2
n
Case 1
Case 2
Case 3
Case 4
Case 1
Case 2
Case 3
Case 4
32 128 512 2048
0.0310 (0.0024) 0.0875 (0.0052) 0.1919 (0.0072) 0.3799 (0.0129)
0.0111 (0.0012) 0.0167 (0.0006) 0.0326 (0.0006) 0.0641 (0.0012)
0.0278 (0.0033) 0.0811 (0.0040) 0.1726 (0.0085) 0.3465 (0.0099)
0.0115 (0.0011) 0.0170 (0.0010) 0.0319 (0.0008) 0.0634 (0.0009)
0.0708 (0.0075) 0.2491 (0.0076) 0.5831 (0.0310) 0.9900 (0.0178)
0.1772 (0.0249) 0.2685 (0.0116) 0.2540 (0.0078) 0.6552 (0.0113)
0.0741 (0.0050) 0.2361 (0.0144) 0.4506 (0.0327) 1.0791 (0.0274)
0.0681 (0.0048) 0.2160 (0.0151) 0.3246 (0.0079) 0.6352 (0.0076)
Table 4: Final non-utility runtime (seconds) for the direct permutation estimator under greedy initialization. This excludes the time spent evaluating U (S) and isolates sampling plus bookkeeping cost. Entries are mean (standard deviation) across 10 independent MH repetitions. Scenario 1 n
Case 1
Case 2
Case 3
Case 4
Case 1
32 128 512 2048
4.37 (0.50) 10.41 (0.08) 45.52 (0.47) 1240.88 (49.17)
3.15 (0.07) 8.48 (0.01) 38.23 (0.26) 1199.02 (64.10)
4.26 (0.01) 10.88 (0.05) 43.10 (0.23) 1195.87 (57.89)
3.31 (0.01) 8.72 (0.01) 39.08 (0.20) 1232.67 (66.66)
2.82 (0.01) 10.89 (0.09) 47.98 (0.62) 1503.55 (53.94)
35
Scenario 2 Case 2 Case 3 2.54 (0.01) 8.57 (0.02) 38.91 (0.34) 1045.47 (8.85)
3.14 (0.01) 10.61 (0.02) 47.34 (0.67) 1205.56 (24.25)
Case 4 2.71 (0.01) 8.70 (0.18) 38.86 (0.34) 993.38 (25.95)
Case 1
0.10 0.05 26 27 28 29 210
Scenario 2
ARE at Convergence
Scenario 1
0.15
0.4 0.3 0.2 0.1
0.025 0.020 0.015 0.010 0.005
Case 2
0.020 0.015 0.010
0.05 26 27 28 29 210
26 27 28 29 210 0.6
0.2
0.4 0.2
0.1
n
Case 4
0.10
0.3
26 27 28 29 210
Case 3
0.15
26 27 28 29 210
n
Permutation
26 27 28 29 210 Linear
n
0.005 0.25 0.20 0.15 0.10 0.05
26 27 28 29 210
26 27 28 29 210
Quadratic
n
Figure 12: Final ARE under matched utility-evaluation budgets for the direct and the two surrogateassisted estimators.
Table 5: Non-utility runtime (seconds) for the three estimators under matched utility budgets. Entries are mean (standard deviation) across independent repetitions. Method
n
Permutation 64 128 256 512 1024
Case 1 5.98 (0.02) 9.73 (0.01) 17.72 (0.03) 39.77 (0.19) 209.25 (3.47)
Scenario 1 Case 2 Case 3
Case 4
Case 1
Case 2
Scenario 2 Case 3
Case 4
4.94 (0.01) 8.53 (0.02) 15.94 (0.03) 36.45 (0.16) 195.76 (2.46)
6.31 (0.01) 10.13 (0.01) 18.12 (0.05) 39.68 (0.10) 203.22 (1.79)
5.17 (0.01) 8.80 (0.01) 16.21 (0.02) 36.67 (0.12) 196.92 (1.99)
5.21 (0.01) 10.13 (0.02) 19.37 (0.06) 41.84 (0.15) 254.92 (3.92)
4.69 (0.02) 8.15 (0.04) 15.99 (0.07) 34.36 (0.06) 205.55 (0.51)
5.28 (0.02) 10.89 (0.10) 19.65 (0.16) 42.44 (0.17) 255.72 (3.14)
4.68 (0.02) 8.26 (0.02) 15.94 (0.04) 34.03 (0.15) 206.43 (1.47)
Linear surrogate 36.40 (0.26) 26.51 (0.15) 64 128 66.61 (0.34) 46.72 (0.19) 256 131.41 (0.51) 91.73 (0.17) 290.04 (1.83) 191.07 (0.65) 512 1024 1053.69 (19.83) 663.81 (6.91)
38.81 (0.23) 69.92 (0.19) 133.43 (0.76) 272.53 (1.29) 835.67 (4.70)
27.21 (0.19) 48.57 (0.23) 92.27 (0.53) 188.95 (0.92) 649.31 (4.14)
44.20 (0.39) 91.95 (0.24) 174.25 (1.43) 309.91 (2.41) 886.68 (10.01)
35.50 (0.38) 61.27 (0.28) 120.17 (0.39) 231.47 (1.18) 725.34 (4.64)
44.38 (0.24) 98.72 (0.20) 180.50 (0.31) 311.12 (1.90) 893.16 (6.54)
35.58 (0.26) 61.63 (0.36) 117.79 (0.51) 226.24 (1.08) 735.43 (3.17)
Quadratic surrogate 64 36.77 (0.25) 26.49 (0.10) 39.15 (0.25) 27.15 (0.21) 45.32 (0.45) 36.08 (0.24) 45.28 (0.34) 36.26 (0.25) 68.86 (0.19) 46.89 (0.26) 71.97 (0.24) 48.63 (0.16) 95.70 (0.36) 63.95 (0.22) 103.02 (0.61) 65.00 (0.33) 128 256 144.39 (0.74) 92.30 (0.28) 152.45 (1.20) 92.73 (0.18) 191.26 (1.16) 138.65 (0.88) 198.05 (0.71) 138.68 (1.59) 512 359.25 (3.06) 194.82 (0.74) 342.59 (2.79) 193.55 (0.82) 382.64 (1.43) 317.75 (3.33) 388.41 (2.06) 315.09 (2.61) 1024 1599.66 (23.32) 700.01 (6.31) 1558.86 (18.52) 701.05 (4.81) 1520.96 (14.39) 1378.02 (9.58) 1575.88 (16.45) 1409.52 (10.56)
Table 6: Training memory (GB) used by the surrogate fit under matched utility budgets. The permutation estimator does not fit a surrogate and is omitted. Method
n
Linear surrogate 64 128 256 512 1024
Case 1 0.033 (0.000) 0.132 (0.001) 0.443 (0.003) 1.151 (0.001) 2.294 (0.003)
Quadratic surrogate 64 0.094 (0.001) 128 0.666 (0.008) 256 4.030 (0.024) 512 20.592 (0.042) 1024 106.818 (0.211)
Scenario 1 Case 2 Case 3 0.001 (0.000) 0.002 (0.000) 0.009 (0.000) 0.031 (0.000) 0.106 (0.001)
0.037 (0.000) 0.155 (0.002) 0.547 (0.004) 1.144 (0.002) 2.298 (0.004)
0.002 (0.000) 0.102 (0.001) 0.012 (0.000) 0.772 (0.009) 0.081 (0.001) 4.922 (0.041) 0.566 (0.006) 20.403 (0.041) 3.724 (0.031) 107.120 (0.217)
Scenario 2 Case 4
Case 1
Case 2
Case 3
Case 4
0.001 (0.000) 0.003 (0.000) 0.011 (0.000) 0.036 (0.000) 0.126 (0.001)
0.138 (0.000) 0.298 (0.000) 0.580 (0.001) 1.146 (0.001) 2.304 (0.003)
0.093 (0.000) 0.194 (0.000) 0.592 (0.000) 1.158 (0.001) 2.312 (0.002)
0.139 (0.000) 0.289 (0.000) 0.580 (0.001) 1.144 (0.002) 2.297 (0.003)
0.092 (0.000) 0.183 (0.000) 0.568 (0.006) 1.155 (0.001) 2.318 (0.002)
0.002 (0.000) 0.409 (0.001) 0.290 (0.001) 0.409 (0.000) 0.288 (0.000) 0.015 (0.000) 1.526 (0.003) 0.986 (0.003) 1.474 (0.003) 0.915 (0.002) 0.098 (0.001) 5.305 (0.008) 5.620 (0.008) 5.336 (0.011) 5.394 (0.061) 0.657 (0.006) 20.549 (0.034) 21.000 (0.027) 20.477 (0.041) 20.989 (0.042) 4.409 (0.035) 107.556 (0.187) 108.276 (0.155) 107.107 (0.175) 108.548 (0.215)
36
Mean Rank Value-Sum (SOU) Value-Sum (SOR)
24 22 20 18 16
pedge = 0.2
pedge = 0.5
pedge = 0.8
20 21 22 23 24 25 26 27
20 21 22 23 24 25 26 27
20 21 22 23 24 25 26 27
0
0
1000 800 600 400 400 200 0
:
=0
=1
=2
=4
=8
0
(PASV)
Figure 13: Priority sweeping results. Rows: mean forward position, SOU group-sum, and SOR group-sum. Colored curves vary β ∈ {1, 2, 4, 8}; the dashed black curve is the β → ∞ (PASV on Gω ) reference.
37
H
Additional Details and Results for LLM Evaluation in Section 6
This appendix collects the implementation details and the full empirical results of the LLM evaluation in Section 6. Throughout, a player i is one of the n = 20 LLMs in Table 7 and a coalition S ⊆ [n] is a subset of them; GPASV attributes the coalition utility Uens (S) across players under the hard-priority weights ωij and the soft-priority vector λi = exp(−αzi ) from Section 6. The utility-evaluation stage of this experiment requires GPU computing and was run on the same computing cluster as Appendix G, pinned to NVIDIA H200 GPUs serving Qwen3.5-35B-A3B-FP8 via vLLM, for a total of approximately 30 GPU-days across the 80 MT-Bench prompts. All downstream stages are CPU-only, and were run on the same cluster on multiple Intel Xeon CPUs. H.1
Data and Priority Construction
Model set and open/paid labels. Table 7 lists the 20 models used as players in Section 6, together with the binary label zi ∈ {0, 1} used for the soft priority. The model set is exactly the intersection of MT-Bench [45] and Chatbot Arena [7]: every model we score on MT-Bench must also have a sufficient number of Chatbot Arena comparisons for the hard priority to be well-defined. We label the five proprietary API models (gpt-4, gpt-3.5-turbo, claude-v1, claude-instant-v1, palm-2) as paid, and all remaining MT-Bench/Arena-overlap models as open-source. The label is a coarse deployment signal rather than a license audit; the point of the soft priority in Section 6 is merely to study how strongly an evaluator who explicitly prefers open-source models over paid APIs reshapes the attribution, so zi is set to 1 for open-source and 0 for paid. Model
Label
Model
Label
gpt-4 claude-v1 claude-instant-v1 gpt-3.5-turbo guanaco-33b vicuna-13b wizardlm-13b palm-2 vicuna-7b koala-13b
paid paid paid paid open-source open-source open-source paid open-source open-source
gpt4all-13b-snoozy mpt-7b-chat rwkv-4-raven-14b alpaca-13b oasst-pythia-12b fastchat-t5-3b chatglm-6b stablelm-tuned-alpha-7b dolly-v2-12b llama-13b
open-source open-source open-source open-source open-source open-source open-source open-source open-source open-source
Table 7: Model set and open/paid labels zi used in the LLM evaluation experiment. Coalition utility from MT-Bench. MT-Bench consists of Q = 80 two-turn prompts organized into eight categories with ten prompts each: Writing, Roleplay, Reasoning, Math, Coding, Extraction, Knowledge I, and Knowledge II. The released benchmark bundles first- and secondturn model responses for every player, and these responses are treated as fixed candidate answers throughout the experiment; we never re-query the 20 players themselves. Following the MT-Bench judging protocol, we use two judge variants. For Reasoning, Math, and Coding, the judge is given MT-Bench’s released reference answer and is asked to score correctness relative to it (with-reference variant). For the remaining five categories the judge scores the answer directly from the user prompt and the assistant response (no-reference variant). For a coalition S and a prompt q, the first-turn (1) candidates {yi }i∈S are passed to an aggregator LLM that synthesizes a single ensemble answer (1) (1) yS ; a judge LLM scores yS on {1, . . . , 10}, producing a score r(1) (S, q). For the second turn we (1) feed the first-turn aggregated answer yS as the previous assistant turn, aggregate the second-turn (2) candidates into yS , and score analogously, producing r(2) (S, q). The prompt-level score is the mean of the two turn scores, and the coalition utility is the average over prompts, Q
Uens (S) =
1 X r(1) (S, q) + r(2) (S, q) , Q q=1 2
Uens (∅) := 0.
Hard-priority graph from Chatbot Arena. Chatbot Arena supplies pairwise human preferences between model responses; we use the public comparison counts to construct the hard priority. For 38
every ordered pair (i, j) with at least 50 recorded comparisons, let pbij denote the empirical win probability of i over j, and let i denote the majority-preferred side so that pbij ≥ 1/2. We then set ωij = pbij − 12 ,
ωji = 0,
so that the additive priority on edge i → j encodes how strongly the Arena crowd prefers i over j. Pairs with fewer than 50 comparisons are treated as non-edges (ωij = ωji = 0). Larger β in (5) more strongly suppresses permutations that place a majority-losing model before its majority-preferred counterpart. The resulting graph Gω is not a DAG: majority preferences form several intransitive triangles among mid-tier models, which is precisely the regime that motivates GPASV over PASV. H.2
Aggregator–Judge Pipeline
Model choice and inference setup. Both the aggregator and the judge are instantiated with Qwen3.5-35B-A3B-FP8 [37]. The model is chosen because (i) it is strong enough to aggregate and score MT-Bench responses reliably yet (ii) small enough in FP8 form to be served locally with batched vLLM inference [24], which is essential at the cached-computation scale described in Section H.3. Using a single model for both roles removes judge–aggregator style mismatches. We cap generation at 4096 new tokens per call, and sample with temperature 1.0, top-p = 0.95, top-k = 20, following the official Qwen3.5 recommendation for instruct (non-thinking) mode on reasoning tasks. Every realized (S, q) output is cached and reused across all priority regimes, so all priority comparisons are made against the same fixed utility realization. Prompt templates. The aggregator and judge prompt templates are shown in Appendix H.5; we summarize their structure here. The aggregator receives the user prompt together with a randomly shuffled list of candidate responses, each delimited by explicit start/end markers, and is instructed to merge, edit, and reorganize the candidates while preserving the user’s requested format and without (1) adding external facts. For the second turn, the first-turn aggregated answer yS is inserted as the previous assistant message before presenting the second-turn candidates. The no-reference judge prompt consists of an [Instruction] block, the [Question] block, and the assistant answer delimited by start/end markers; the with-reference variant additionally inserts a reference-answer block and asks the judge to evaluate correctness against it. For second-turn judging, the full two-turn conversation is presented in the Assistant A format, so that coherence across turns is scored rather than each turn in isolation. In all variants, the judge is asked for a brief explanation followed by a final [[rating]] on the 1–10 scale. Placeholders {x1}, {x2}, {y1S}, {y2S}, {r1}, {r2}, and {candidate answer k} are filled by the corresponding MT-Bench prompt, aggregated response, reference answer, or candidate-model response at runtime. H.3
Sampling and Computation Protocol
MH hyperparameters. For every priority regime (α, β) with β > 0, we draw NMC = 1000 permutations from p(λ,ω) using the adjacent-swap Metropolis–Hastings sampler of Section F.1.1 with greedy initialization (Algorithm 2). We use burn-in 105 and thinning interval 103 ; at n = 20 the adjacent-swap chain mixes quickly relative to the simulation-study scales, so this conservative schedule leaves the effective sample size close to NMC . At the baseline (α, β) = (0, 0) the sampler reduces to uniform sampling over Π, which we implement by direct iid uniform draws. Utility cache design. Evaluating one coalition on the full MT-Bench set requires four LLM calls per prompt: aggregation and judging for each of the two turns. A naive direct Monte Carlo over NMC permutations of n players with Q prompts would therefore require 4NMC nQ calls, which at NMC = 1000, n = 20, Q = 80 amounts to 6.4 × 106 calls for a single priority regime, and across the 19 regimes of Section 6 it would scale linearly in the number of regimes. We avoid this by caching at the level of (subset, prompt) pairs: each cache row is keyed by a 20-bit subset mask and an MT-Bench (1) (2) prompt index, and stores both aggregated answers yS , yS , both raw judge responses, and the two parsed ratings. Because GPASV only evaluates Uens on prefix coalitions of sampled permutations, and because neighboring priority regimes along each sweep share most prefixes through the SNIS permutation reuse described next, the realized number of distinct subset evaluations is far below the worst-case NMC n. Once the cache has been populated along the first sweep, all subsequent priority regimes read the same cache: changing (α, β) changes only the sampled order distribution, not Uens . 39
Sweep traversal and SNIS/ESS reuse. The three sweeps of Section 6 are traversed in increasing temperature order from the shared baseline: (0, 0) → (1, 0) → (2, 0) → (4, 0) → (8, 0) → (16, 0) → (32, 0), and analogously for the β-only and joint α = β sweeps. Between neighboring regimes we apply the SNIS/ESS reuse rule from Section F.3.2. Given the reweighted effective sample size ESS of the previous-regime samples under the new target, we add Nnew = min{NMC , max(500, ⌈NMC − ESS⌉)} fresh permutations from the new target and combine the reweighted estimate with the fresh Monte Carlo estimate using weights proportional to ESS and Nnew . The lower bound of 500 ensures that even near-overlapping regimes refresh a meaningful fraction of the sample; the upper bound of NMC caps the cost of any single transition at a full fresh draw. Realized acceleration. Table 8 reports the realized utility-evaluation cost under the four combinations of the two reuse mechanisms: subset reuse via the cache and permutation reuse via SNIS. The cache provides the dominant fraction of the saving, reducing the per-prompt distinct subset count by a factor of ≈ 4.9 on its own (B vs. A); SNIS trims the effective permutation count from 19,000 to 15,840 along the three sweeps (Table 9) but on its own only yields a ≈ 1.2× reduction (C vs. A). Combining both gives a realized ≈ 5.4× reduction over the naive baseline (D vs. A). Table 8: Realized utility-evaluation cost under the four combinations of subset reuse (cache) and permutation reuse (SNIS). “# of Permutations” is the total number of permutations sampled across the 19 regimes after SNIS thinning along the three sweeps (with the baseline (0, 0) shared once); “# of Subsets” is the number of distinct prefix coalitions evaluated per MT-Bench prompt. Scenario A. No reuse B. Subset reuse only C. Permutation reuse only D. Both
Cache
SNIS
✗ ✓ ✗ ✓
✗ ✗ ✓ ✓
# of Permutations
# of Subsets
19,000 19,000 15,840 15,840
380,000 78,220 316,800 70,511
Table 9: Permutations saved by SNIS along the three sweep traversals. “Without SNIS” is the 6 NMC fresh permutations that would P be drawn per sweep (6 non-baseline temperatures × NMC = 1,000); “with SNIS” is the realized Nnew under the rule above. The shared baseline (0, 0) contributes a single NMC = 1,000 draw across all three sweeps and is excluded from this table. Sweep
H.4
Without SNIS
With SNIS
Saved
α-only (β = 0) β-only (α = 0) joint (α = β)
6,000 6,000 6,000
4,007 5,403 5,430
1,993 597 570
Three-sweep total
18,000
14,840
3,160
Full Results
Section 6 showed results for representative regimes; this subsection reports the full results across all 19 settings generated by the three one-dimensional sweeps on (α, β), in three views: per-player value trajectories along each sweep (Figure 14), per-player rank under every (α, β) cell (Figure 15), and the top-8 ranked players at every individual regime (Figure 16). Per-player value trajectories. Figure 14 plots ψi (Uens ) for each of the 20 players as a function of the sweep temperature, one panel per sweep (α-only, β-only, joint α = β). Solid lines are open-source models and dashed lines are paid. This view emphasizes the trajectory of each player as the priority strength is increased and is the curve-level companion to the group-sum view in Figure 7. Per-player rank on the (α, β) grid. Figure 15 reports, for each of the 20 players, the rank of that player among all 20 models on every supported (α, β) cell of the 7 × 7 grid (the 19 cells along the three sweeps; off-support cells are masked white). Each per-player heatmap shares the same color 40
scale: rank 1 (best) is dark and rank 20 (worst) is light. Per-panel titles are colored by group (paid in dark blue, open-source in burnt orange) for quick reading; the same color convention is used in the bar charts of Figure 16. This view is the cell-level dual of Figure 14: the trajectory in the latter corresponds to a row or column of cells in the former. Top-8 ranking under every regime. Figure 6 in the main text visualizes the top-8-valued models under representative regimes. Figure 16 extends the same view to all 19 regimes, arranged as a 7 × 3 grid: rows index the temperature value (0 baseline together with {1, 2, 4, 8, 16, 32}) and columns index the sweep type. Walking down a column traces how the top-8 shifts as that sweep is strengthened from the baseline; walking across a row contrasts the three sweep types at a fixed temperature. Model
Sweep ( = 0) 6
1.0 GPASV
Sweep ( = 0)
3
4 0.5 0.0
0 1 2 4 8 16 32
4
Sweep =
2
2
1
0
0 0 1 2 4 8 16 32 paid
open-source
0 1 2 4 8 16 32 =
gpt-4 claude-v1 claude-instant-v1 gpt-3.5-turbo palm-2 guanaco-33b vicuna-13b wizardlm-13b vicuna-7b koala-13b gpt4all-13b-snoozy mpt-7b-chat rwkv-4-raven-14b alpaca-13b oasst-pythia-12b fastchat-t5-3b chatglm-6b stablelm-tuned-alpha-7b dolly-v2-12b llama-13b
Figure 14: Per-player GPASV ψi (Uens ) along the three sweeps, averaged over the 80 MT-Bench prompts. Left: α-only sweep (β = 0). Middle: β-only sweep (α = 0). Right: joint sweep (α = β). Solid lines are open-source models; dashed lines are paid (gpt-4, gpt-3.5-turbo, claude-v1, claude-instant-v1, palm-2).
41
claude-v1
claude-instant-v1
gpt-3.5-turbo
palm-2 20
vicuna-13b
wizardlm-13b
vicuna-7b
koala-13b
gpt4all-13b-snoozy
mpt-7b-chat
rwkv-4-raven-14b
alpaca-13b
oasst-pythia-12b
0 1 2 4 8 1632
0 1 2 4 8 1632
0 1 2 4 8 1632
guanaco-33b
15 Rank (1 = Best)
0 1 2 4 8 1632
gpt-4
10
6
fastchat-t5-3b
chatglm-6b stablelm-tuned-alpha-7b dolly-v2-12b
llama-13b 1
0 1 2 4 8 1632
0 1 2 4 8 1632
0 1 2 4 8 1632
0 1 2 4 8 1632
0 1 2 4 8 1632
Figure 15: Per-player rank heatmaps over the supported (α, β) cells. Each subplot is one player; rows index β and columns index α (both on the grid {0, 1, 2, 4, 8, 16, 32}). Cells off the three sweep paths are masked. Per-panel title color encodes paid (blue) vs. open-source (orange), matching Figure 16.
42
Sweep ( = 0)
Sweep ( = 0)
Sweep =
( , ) = (0, 0)
( , ) = (0, 0)
( , ) = (0, 0)
gpt 4 claude instant v1 gpt 3. 5 turbo claude v1 vicuna 13b wizardlm 13b guanaco 33b vicuna 7b
0.80 0.74 0.61 0.54 0.46 0.45 0.39
0
1.26
gpt 4 claude instant v1 gpt 3. 5 turbo claude v1 vicuna 13b wizardlm 13b guanaco 33b vicuna 7b
1
0
( , ) = (1, 0) 0.71 0.70 0.67 0.66 0.51 0.51 0.48 0.45
guanaco 33b gpt 4 vicuna 13b wizardlm 13b vicuna 7b koala 13b gpt4all 13b snoozy mpt 7b chat
0.0
0.5
0.77 0.68 0.63 0.62 0.59 0.58 0.47 0.46
0.0
1
1.39 1.23 1.04 0.39 0.32 0.32 0.25
0 gpt 4 claude v1 claude instant v1 gpt 3. 5 turbo palm 2 guanaco 33b wizardlm 13b vicuna 13b
0.5
1.83 1.23 0.94 0.24 0.23 0.17 0.16
0.0
2.5
0.5
0.0
0.76 gpt 4 0.71 claude v1 0.70 claude instant v1 0.62 gpt 3. 5 turbo 0.56 guanaco 33b 0.53 stablelm tuned alpha 7b 0.50 wizardlm 13b 0.49 dolly v2 12b
1.89 1.08 0.37 0.05 0.05 0.05 0.03
0.0
0.5
0
4.74
0
1
0
( , ) = (32, 0)
0
GPASV
0
guanaco 33b vicuna 13b wizardlm 13b gpt 4 vicuna 7b koala 13b claude instant v1 claude v1
5
1
0
paid
6.85
1.29 0.14 0.13 0.13 0.13 0.12 0.11
2
1.71 1.30 1.09 0.53 0.27 0.21 0.17
0
2.99
2
( , ) = (32, 32) guanaco 33b wizardlm 13b vicuna 13b gpt 4 vicuna 7b claude instant v1 claude v1 chatglm 6b
5
GPASV
1
( , ) = (8, 8)
( , ) = (16, 16)
( , ) = (0, 32)
0.82 gpt 4 0.80 claude v1 0.66 guanaco 33b 0.62 mpt 7b chat 0.60 chatglm 6b 0.49 dolly v2 12b 0.48 koala 13b 0.47 stablelm tuned alpha 7b
vicuna 13b wizardlm 13b guanaco 33b vicuna 7b gpt4all 13b snoozy koala 13b gpt 4 mpt 7b chat
1.60 1.57 1.28 1.23 1.06
2.17 1.71 1.38 1.15 0.87 0.48 0.22 0.18
guanaco 33b vicuna 13b wizardlm 13b gpt 4 vicuna 7b koala 13b claude instant v1 claude v1
5
6.04
0.59 0.25 0.24
0
( , ) = (0, 16)
0.83 gpt 4 0.76 1.76 claude v1 0.67 0.18 claude instant v1 0.63 0.11 guanaco 33b 0.58 0.08 koala 13b 0.50 stablelm tuned alpha 7b 0.08 0.49 0.07 gpt 3. 5 turbo 0.45 0.06 dolly v2 12b
1
( , ) = (4, 4)
vicuna 13b guanaco 33b wizardlm 13b gpt 4 vicuna 7b koala 13b claude v1 claude instant v1
2.5
2
1.46 1.31 1.09 0.92 0.84 0.60 0.48 0.42
0
( , ) = (0, 8)
( , ) = (16, 0)
vicuna 13b wizardlm 13b guanaco 33b vicuna 7b gpt4all 13b snoozy koala 13b gpt 4 mpt 7b chat
3.93
1.64
( , ) = (2, 2)
gpt 4 vicuna 13b guanaco 33b wizardlm 13b vicuna 7b koala 13b claude v1 claude instant v1
( , ) = (0, 4)
( , ) = (8, 0)
vicuna 13b wizardlm 13b guanaco 33b vicuna 7b gpt4all 13b snoozy koala 13b gpt 4 mpt 7b chat
3.13
1
0.91 0.76 0.73 0.63 0.63 0.53 0.48
0
1.26
( , ) = (1, 1)
gpt 4 vicuna 13b claude v1 wizardlm 13b guanaco 33b claude instant v1 gpt 3. 5 turbo vicuna 7b
2
0.76 gpt 4 0.70 1.83 claude v1 0.69 1.40 claude instant v1 0.63 0.71 gpt 3. 5 turbo 0.61 0.11 guanaco 33b 0.53 0.07 wizardlm 13b 0.52 0.06 palm 2 0.49 stablelm tuned alpha 7b 0.03
wizardlm 13b vicuna 13b guanaco 33b vicuna 7b gpt4all 13b snoozy gpt 4 koala 13b mpt 7b chat
2.46
0.80 0.74 0.61 0.54 0.46 0.45 0.39
0
( , ) = (0, 2)
0.0
( , ) = (4, 0)
gpt 4 claude instant v1 gpt 3. 5 turbo claude v1 vicuna 13b wizardlm 13b guanaco 33b vicuna 7b
( , ) = (0, 1)
gpt 4 claude v1 claude instant v1 gpt 3. 5 turbo vicuna 13b guanaco 33b palm 2 wizardlm 13b
( , ) = (2, 0)
wizardlm 13b vicuna 13b vicuna 7b guanaco 33b gpt4all 13b snoozy gpt 4 koala 13b mpt 7b chat
0.80 0.74 0.61 0.54 0.46 0.45 0.39
1.26
open-source
1.34 1.27 1.05 0.19 0.18 0.17 0.14
0.0
3.98
2.5
GPASV
Figure 16: Top-8-valued models across all 19 priority regimes. Rows: temperature values (baseline (0, 0) together with {1, 2, 4, 8, 16, 32}). Columns: α-only sweep (β = 0), β-only sweep (α = 0), joint sweep (α = β). Bar color encodes paid vs. open-source, matching the color scheme of Figure 6 in the main text.
43
H.5
Prompt Templates
Aggregator prompt template: 1st turn [Instruction] You are an impartial aggregator. Given a user prompt and multiple candidate answers, produce one final answer. Your aggregation is merge-leaning: - Primarily combine, edit, and reorganize what is already in the candidates. - Do not add new substantive content or external facts. Rules: 1) Follow the user’s requested format, constraints, and style exactly. 2) Use only information explicitly stated in the candidates. You may add minimal connective wording for readability. 3) If candidates disagree and you cannot resolve it from the candidates, omit the claim or mark it as uncertain. 4) Remove redundancy and irrelevant parts; choose the clearest phrasing among candidates. 5) If JSON/code/strict format is required, keep it valid and do not introduce new APIs/libraries not present in candidates. 6) Two-turn consistency: if the prompt is multi-turn, treat the turn-1 aggregated answer as the assistant’s previous message when producing the turn-2 aggregated answer. After synthesizing, output ONLY the final aggregated answer, with no extra commentary. [Question] {x1} <|The Start of Candidates|> [The Start of Candidate 1 Answer] {candidate answer 1} [The End of Candidate 1 Answer] ... [The Start of Candidate K Answer] {candidate answer K} [The End of Candidate K Answer] <|The End of Candidates|>
44
Aggregator prompt template: 2nd turn [Instruction] You are an impartial aggregator. Given a user prompt and multiple candidate answers, produce one final answer. Your aggregation is merge-leaning: - Primarily combine, edit, and reorganize what is already in the candidates. - Do not add new substantive content or external facts. Rules: 1) Follow the user’s requested format, constraints, and style exactly. 2) Use only information explicitly stated in the candidates. You may add minimal connective wording for readability. 3) If candidates disagree and you cannot resolve it from the candidates, omit the claim or mark it as uncertain. 4) Remove redundancy and irrelevant parts; choose the clearest phrasing among candidates. 5) If JSON/code/strict format is required, keep it valid and do not introduce new APIs/libraries not present in candidates. 6) Two-turn consistency: if the prompt is multi-turn, treat the turn-1 aggregated answer as the assistant’s previous message when producing the turn-2 aggregated answer. After synthesizing, output ONLY the final aggregated answer, with no extra commentary. <|The Start of Previous Conversation with User|> ### User: {x1} ### Assistant: {y1S} ### User: {x2} <|The End of Previous Conversation with User|> <|The Start of Candidates|> [The Start of Candidate 1 Answer] {candidate answer 1} [The End of Candidate 1 Answer] ... [The Start of Candidate K Answer] {candidate answer K} [The End of Candidate K Answer] <|The End of Candidates|>
45
Judge prompt template without reference: 1st turn [Instruction] You are an impartial judge evaluating the quality of an assistant’s response. Evaluate the response based on the following criteria: - helpfulness - relevance - accuracy - clarity - completeness Think carefully about the response before rating it. Provide at most three short sentences summarizing the main reason for your score. Then, on a new final line, output the rating strictly in the format "[[rating ]]", where rating is an integer from 1 to 10, for example: "[[5]]". Do not use any other rating format. Do not output anything after the final rating line. [Question] {x1} [The Start of Assistant’s Answer] {y1S} [The End of Assistant’s Answer]
Judge prompt template without reference: 2nd turn [Instruction] You are an impartial judge evaluating the quality of an assistant’s response. Evaluate the response based on the following criteria: - helpfulness - relevance - accuracy - clarity - completeness Think carefully about the response before rating it. Provide at most three short sentences summarizing the main reason for your score. Then, on a new final line, output the rating strictly in the format "[[rating ]]", where rating is an integer from 1 to 10, for example: "[[5]]". Do not use any other rating format. Do not output anything after the final rating line. <|The Start of Assistant A’s Conversation with User|> ### User: {x1} ### Assistant A: {y1S} ### User: {x2} ### Assistant A: {y2S} <|The End of Assistant A’s Conversation with User|>
46
Judge prompt template with reference: 1st turn [Instruction] You are an impartial judge evaluating the quality of an assistant’s response using a reference answer. Evaluate the response by comparing it with the reference answer based on the following criteria: - correctness - helpfulness - relevance - clarity - completeness Think carefully about the response before rating it. If the assistant’s response misses important points or contains mistakes compared with the reference answer, take that into account. Provide at most three short sentences summarizing the main reason for your score. Then, on a new final line, output the rating strictly in the format "[[rating ]]", where rating is an integer from 1 to 10, for example: "[[5]]". Do not use any other rating format. Do not output anything after the final rating line. [Question] {x1} [The Start of Reference Answer] {r1} [The End of Reference Answer] [The Start of Assistant’s Answer] {y1S} [The End of Assistant’s Answer]
47
Judge prompt template with reference: 2nd turn [Instruction] You are an impartial judge evaluating the quality of an assistant’s response using a reference answer. Evaluate the response by comparing it with the reference answer based on the following criteria: - correctness - helpfulness - relevance - clarity - completeness Think carefully about the response before rating it. If the assistant’s response misses important points or contains mistakes compared with the reference answer, take that into account. Provide at most three short sentences summarizing the main reason for your score. Then, on a new final line, output the rating strictly in the format "[[rating ]]", where rating is an integer from 1 to 10, for example: "[[5]]". Do not use any other rating format. Do not output anything after the final rating line. <|The Start of Reference Answer|> ### User: {x1} ### Reference answer: {r1} ### User: {x2} ### Reference answer: {r2} <|The End of Reference Answer|> <|The Start of Assistant A’s Conversation with User|> ### User: {x1} ### Assistant A: {y1S} ### User: {x2} ### Assistant A: {y2S} <|The End of Assistant A’s Conversation with User|>
48