Introduction
Many important evaluation tasks require eliciting ordinal information. Conference program committees rank submissions for acceptance; platforms collect human feedback to compare the quality of LLM responses; and instructors use peer assessment to ask students to rank a small set of assignment submissions. These settings share a common structure: (1) Evaluators often have informative but imperfect signals to judge relative quality. (2) Investing more effort leads to higher-quality judgments. (3) There is often no objective ground truth against which reports can be directly verified.
This absence of ground truth creates a fundamental incentive problem. Without appropriate incentives, agents may invest little effort in evaluation or report strategically. Directly rewarding “correct” answers is not possible when correctness cannot be verified. The peer-prediction literature addresses the challenge of elicitation without ground truth by rewarding agents based on the statistical relationships among their reports. When properly designed, such mechanisms make truthful reporting an equilibrium even in the absence of verifiable outcomes. However, most existing peer-prediction mechanisms require agents to report all of their private information [21 , 24 , 14 ] , typically as a numerical or categorical signal, and their incentive guarantees can fail when agents observe richer information than they are asked to report [8 ] . This creates a mismatch in many evaluation settings: agents may observe rich private information, such as detailed reviews, latent quality assessments, or noisy cardinal scores, while the designer only wants a coarser ordinal report, such as a ranking or a set of pairwise comparisons.
This paper studies peer prediction for coarse ordinal elicitation. Agents may observe rich private information about item quality, but the mechanism asks them to report only ordinal information. We allow several natural ordinal report formats, including full rankings, fixed-shape bucket orders such as top-K K K sets and tiered reports, and rankings over assigned subsets of items. Our goal is to design incentives for truthful ordinal reporting without requiring agents to reveal their full private information. To do so, we leverage the fact that ordinal reports naturally encode pairwise comparisons among items.
This suggests a simple agreement-based mechanism: reward agents according to whether their reported pairwise comparisons agree with those of their peers, equivalently through a Kendall tau-based pairwise-agreement score. Such an approach is attractive because it is simple, transparent, and directly aligned with the ordinal information the designer wants to elicit. In general elicitation settings, however, rewarding agents for agreement can encourage them to suppress private information when they believe their signal is likely to be in the minority [15 ] . For example, if an evaluator believes that most peers will mark nearly every submission as acceptable, then a reward based only on agreement may induce the evaluator to report “acceptable” even for a submission they privately judge to be weak. This is why agreement mechanisms typically require strong self-dominance conditions—after observing a signal, an agent must believe that other agents are more likely to report the same signal than any alternative [31 ] —to have a truthful reporting equilibrium.
Our key observation is that, although such self-dominance conditions are generally strong for arbitrary signals, they become natural at the level of pairwise ordinal comparisons. We identify a broad class of Bayesian Stochastically Order Consistent (Bayesian SOC) information structures under which each truthful pairwise comparison is more likely to agree with a peer’s comparison than to disagree, even after conditioning on the agent’s richer private information. Under this condition, the Kendall tau mechanism makes truthful ordinal reporting stochastically dominant, despite eliciting only a coarse ordinal summary of the agent’s information.
Contributions. We introduce a peer-prediction mechanism for coarse ordinal reports based on Kendall tau distance and its pairwise-agreement extension. The mechanism applies to several natural reporting formats, including full rankings, fixed-shape bucket orders [5 ] , and rankings over assigned subsets of items. The bucket-order setting covers full rankings and top-K K K sets as special cases and also captures tiered reports. Its reward rule is simple and transparent: agents are paid according to agreement with peers on the pairwise comparisons induced by their reports. This simplicity is useful both theoretically and practically. When evaluators are already comparing a small set of alternatives, ordinal reports can be easier to specify and audit than calibrated cardinal scores, consistent with a long line of work in psychometrics on comparative judgment [27 , 26 , 19 ] .
We provide strong incentive guarantees for this mechanism under a class of Bayesian Stochastically Order Consistent (Bayesian SOC) information structures. Bayesian SOC ensures that each truthful pairwise comparison is more likely to agree with a peer’s comparison than to disagree, even after conditioning on the agent’s richer private information. This class includes classical ranking information structures, such as the Thurstone and Mallows models. Under Bayesian SOC, truthful ordinal reporting is stochastically dominant: truth-telling not only maximizes expected payment, but yields a payment distribution that first-order stochastically dominates the distribution under any unilateral deviation. This is stronger than standard equilibrium guarantees based only on expected utility and provides robustness to agents with nonlinear utility functions, such as risk aversion. Moreover, we show that the mechanism is strongly truthful if agents’ strategies cannot coordinate on an external indexing of items.
We also study the measurement accuracy of the mechanism, namely how well payments track the quality of an agent’s report [4 ] . This property is important in practice for fairness [2 ] , motivation [29 ] , and trust in the mechanism. Prior work has shown that strong stochastic-dominance incentives can come at a substantial cost to accuracy [31 ] . In contrast, our experiments on synthetic data from Mallows and Thurstone models, together with a real-data stress test on the SUSHI preference dataset [10 ] , suggest that the Kendall tau mechanism remains sensitive to report quality in the ordinal settings we study.
Relation to Prior Work
Peer prediction began with mechanisms such as Bayesian Truth Serum [21 ] and has developed into a broad literature on eliciting unverifiable information from correlated reports. A central difficulty is that simple agreement can make agents coordinate on common or focal reports rather than reveal their private information [15 ] . Many later mechanisms therefore reward reports through prediction, correlation, or mutual-information-style quantities, including informed-truthful and multi-task mechanisms [24 , 14 , 12 , 22 , 7 ] . These mechanisms typically operate on categorical or numerical reports, often require agents to report a sufficiently rich representation of their signal, or learn/estimate statistical relationships across tasks (items). Our mechanism instead asks for ordinal reports and uses a fixed, transparent pairwise-agreement score.
Our setting connects most directly to the bonus-penalty payment (BPP) mechanism for binary pairwise comparisons [3 ] , which operates under Bayesian Strong Stochastic Transitivity (Bayesian SST). BPP has a three-agent structure: an agent evaluates one pair and is scored using signals from two other agents on related pairs. This makes BPP well suited to sparse pairwise-comparison assignments. By contrast, our mechanism asks agents for richer ordinal reports—full rankings, top-K K K sets, bucket orders, and subset assignments—and scores them by all-pairs agreement on overlapping item pairs. Thus our framework is less general in assignment structure, because pairs must be reviewed by more than one agent, but it handles richer reports directly.
The modeling assumptions are also different. BPP is designed for homogeneous pairwise signals, whereas Bayesian SOC allows heterogeneous agents and full signal vectors. For instance, different reviewers may have different noise levels in a Thurstone or Mallows model. The two frameworks are not compatible. Appendix § 13 compares SOC with SST in detail.
Our stochastic-dominance guarantee is related to recent stochastically dominant peer prediction for multi-task categorical reports [31 ] . Their mechanisms use task partitions to obtain stochastic dominance for categorical signals. Here, the ordered structure of rankings and Bayesian SOC allow a simpler Kendall tau-based pairwise-agreement score: the proof turns a deviation into adjacent pair corrections, each improving the score distribution. Technically, the proof controls weighted peer-alignment margins rather than independent categorical tasks.
Conceptually, our framework also connects to property elicitation [16 ] : the target function maps a rich private signal vector to the ordinal property we want to elicit, such as a ranking, top set, or bucket order. From this perspective, Kendall tau-based pairwise agreement is a scoring rule for an ordinal projection of the agent’s information rather than for the full signal. This distinction is important in settings such as review, peer assessment, and RLHF, where the platform often wants a tractable ordinal judgment even though agents may observe richer cardinal evidence.
Paper organization. § 2.1 introduces the Bayesian SOC framework and § 2.2 formalizes ordinal peer prediction. § 3 proves the full-ranking Kendall tau mechanism is truthful and stochastically dominant truthful. § 4 gives the subset-assignment and bucket-order extensions, the latter also implying the top-K K K result. § 5 reports the main empirical comparison; proofs, specialized top-set details, and additional experiments are in the appendices.
Problem Formulation
We consider a collection of M M M items and a set of N ≥ 2 N \ge2 N ≥ 2 strategic agents. Each agent privately observes noisy signals for the items. Our goal is to design mechanisms to elicit agents’ ordinal information from private signals truthfully. We introduce the joint distributions of agents’ private signals in § 2.1 and then define the information elicitation problem in § 2.2 .
We first define Kendall tau distance between two item rankings. Given two items i i i and j ∈ [ M ] j \in[M] j ∈ [ M ] and an ordering r : [ M ] → [ M ] r : [M] \to[M] r : [ M ] → [ M ] of them, the sign function is
sign ( r ( i ) , r ( j ) ) = { 1 if r ( i ) < r ( j ) − 1 if r ( i ) > r ( j ) 0 otherwise \operatorname{sign}(r(i),r(j)) =
\begin{cases}
1 & \text{if } r(i) < r(j) \\
-1 & \text{if } r(i) > r(j) \\
0 & \text{otherwise}
\end{cases} sign ( r ( i ) , r ( j )) = ⎩ ⎨ ⎧ 1 − 1 0 if r ( i ) < r ( j ) if r ( i ) > r ( j ) otherwise
where r ( i ) r(i) r ( i ) is the rank of the item i i i in the ordering r r r . For notation brevity, given two rankings, r r r and r ′ r' r ′ , we further set
sign ( r ( i ) , r ( j ) ; r ′ ( i ) , r ′ ( j ) ) = sign ( r ( i ) , r ( j ) ) sign ( r ′ ( i ) , r ′ ( j ) ) . \operatorname{sign}(r(i),r(j);r'(i),r'(j)) = \operatorname{sign}(r(i),r(j))\operatorname{sign}(r'(i),r'(j)). sign ( r ( i ) , r ( j ) ; r ′ ( i ) , r ′ ( j )) = sign ( r ( i ) , r ( j )) sign ( r ′ ( i ) , r ′ ( j )) .
We say r r r and r ′ r' r ′ are order consistent at ( i , j ) (i,j) ( i , j ) if sign ( r ( i ) , r ( j ) ; r ′ ( i ) , r ′ ( j ) ) ≥ 0 \operatorname{sign}(r(i),r(j);r'(i),r'(j)) \ge0 sign ( r ( i ) , r ( j ) ; r ′ ( i ) , r ′ ( j )) ≥ 0 , and strictly order consistent if sign ( r ( i ) , r ( j ) ; r ′ ( i ) , r ′ ( j ) ) > 0 \operatorname{sign}(r(i),r(j);r'(i),r'(j)) > 0 sign ( r ( i ) , r ( j ) ; r ′ ( i ) , r ′ ( j )) > 0 .
Definition 2.1. Given two full rankings r , r ′ ∈ S M r, r' \in\mathcal{S}_M r , r ′ ∈ S M , the Kendall tau distance between them counts how many pairs of items are ordered differently in r r r and r ′ r' r ′ . That is,
d τ ( r , r ′ ) : = 1 2 ∑ i < j ( 1 − sign ( r ( i ) , r ( j ) ; r ′ ( i ) , r ′ ( j ) ) ) . (1) d_{\tau}(r,r') := \frac{1}{2}\sum_{i<j}\left(1-\operatorname{sign}(r(i),r(j);r'(i),r'(j))\right). \tag*{(1)} d τ ( r , r ′ ) := 2 1 i < j ∑ ( 1 − sign ( r ( i ) , r ( j ) ; r ′ ( i ) , r ′ ( j )) ) . (1)
Bayesian Stochastically Order Consistent Models
Given the set of M M M items, each item i ∈ [ M ] i \in[M] i ∈ [ M ] has an underlying unknown state θ i ∈ Θ \theta_i \in\Theta θ i ∈ Θ , where Θ \Theta Θ is a (strictly) ordered set defined in Appendix § 7 . The vector of states θ = ( θ 1 , … , θ M ) \boldsymbol{\theta} = (\theta_1,\ldots,\theta_M) θ = ( θ 1 , … , θ M ) is drawn from a prior μ \mu μ . Depending on the model, θ \boldsymbol{\theta} θ may represent either a reference ranking or underlying item costs.
For each item, each agent gets a signal from a (strictly) ordered set X \mathcal{X} X . Conditioned on a realized θ \boldsymbol{\theta} θ , each agent n ∈ [ N ] n \in[N] n ∈ [ N ] independently receives a private signal vector x n ∈ X M \boldsymbol{x}_n \in\mathcal{X}^M x n ∈ X M from a distribution P n ( ⋅ ∣ θ ) P_n(\cdot\mid\boldsymbol{\theta}) P n ( ⋅ ∣ θ ) over these vectors of signals. Let X = ( x n ) n ∈ [ N ] \mathbf{X} = (\boldsymbol{x}_n)_{n\in[N]} X = ( x n ) n ∈ [ N ] be the random matrix of all agents’ signals, where each agent n n n receives a signal vector x n = ( x n , 1 , … , x n , M ) \boldsymbol{x}_n = (x_{n,1},\ldots,x_{n,M}) x n = ( x n , 1 , … , x n , M ) . When realized, these values are denoted as X \mathbf{X} X for the matrix, x n \boldsymbol{x}_n x n for the row of agent n n n , and x n , i x_{n,i} x n , i for the entry for agent n n n and item i i i .
An information structure consists of a prior μ \mu μ on θ \boldsymbol{\theta} θ and the collection of conditional signal distributions P = ( P n ) n ∈ [ N ] \mathbf{P} = (P_n)_{n\in[N]} P = ( P n ) n ∈ [ N ] . Given i , j ∈ [ M ] i,j \in[M] i , j ∈ [ M ] and strictly ordered sets Y , Z \mathcal{Y},\mathcal{Z} Y , Z , y ∈ Y M \boldsymbol{y} \in\mathcal{Y}^M y ∈ Y M , z ∈ Z M \boldsymbol{z} \in\mathcal{Z}^M z ∈ Z M are order consistent at ( i , j ) (i,j) ( i , j ) if their relative orderings at those indices match.
Definition 2.2 (Kleinberg et al. [11 ] ). Given M M M , and ordered sets Θ \Theta Θ and X \mathcal{X} X , a conditional probability P : Θ M → Δ ( X M ) P:\Theta^{M}\to\Delta(\mathcal{X}^{M}) P : Θ M → Δ ( X M ) is stochastically order consistent (SOC) if for any distinct i , j ∈ [ M ] i,j\in[M] i , j ∈ [ M ] , state vector θ ∈ Θ M \theta\in\Theta^{M} θ ∈ Θ M , and signal vector x ∈ X M x\in\mathcal{X}^{M} x ∈ X M which are order consistent at ( i , j ) (i,j) ( i , j ) ,
P ( x = x ∣ θ ) ≥ P ( x = σ i j ( x ) ∣ θ ) P(x=x\mid\theta)\ge P(x=\sigma_{ij}(x)\mid\theta) P ( x = x ∣ θ ) ≥ P ( x = σ ij ( x ) ∣ θ ) where σ i j ( x ) \sigma_{ij}(x) σ ij ( x ) denotes the vector x x x with the i i i -th and j j j -th components swapped.2 Moreover, the inequality is strict when θ \theta θ and x x x are strictly order consistent at ( i , j ) (i,j) ( i , j ) .
Intuitively, for any two items i i i and j j j , it is more probable that their order in the signal is consistent with their true order in θ \theta θ than the reverse, regardless of the realizations of the other items. We discuss the connection to order independence in Appendix § 13 .
Definition 2.3 (Bayesian stochastically order-consistent). An information structure ( μ , P ) (\mu,P) ( μ , P ) is Bayesian stochastically order-consistent (Bayesian SOC) if it satisfies:
Ex-ante identical: θ \theta θ is drawn from an exchangeable prior μ \mu μ .
Neutrality: For each agent n n n , the conditional probability P n P_n P n is invariant to permutations of the items. For all permutations σ ∈ S M \sigma\in\mathcal{S}_M σ ∈ S M , x x x , and θ \theta θ , P n ( x ∣ θ ) = P n ( σ ( x ) ∣ σ ( θ ) ) P_n(x\mid\theta)=P_n(\sigma(x)\mid\sigma(\theta)) P n ( x ∣ θ ) = P n ( σ ( x ) ∣ σ ( θ )) .
Stochastic consistency: Each conditional signal distribution P n P_n P n is SOC (Definition 2.2), so the signals are more likely to be order consistent with the true underlying order.
A Bayesian SOC model is strict if there are no ties: Pr [ x n , i = x n , j ] = 0 \Pr[x_{n,i}=x_{n,j}]=0 Pr [ x n , i = x n , j ] = 0 and Pr [ θ i = θ j ] = 0 \Pr[\theta_i=\theta_j]=0 Pr [ θ i = θ j ] = 0 for all n ∈ [ N ] n\in[N] n ∈ [ N ] and i ≠ j ∈ [ M ] i\ne j\in[M] i = j ∈ [ M ] . Finally, P P P has full support if P n ( ⋅ ∣ θ ) P_n(\cdot\mid\theta) P n ( ⋅ ∣ θ ) assigns positive probability to the same set of signals for all n n n and θ \theta θ .
As shown in Examples 2.4 to 2.6, several classical ranking models embody this setting and satisfy Bayesian SOC, including the Mallows model [18 ] , the Thurstone model [27 ] , and additive random utility models [27 , 25 , 1 ] .
Example 2.4 (Mallows model [18 ] ). Here the vector of item states θ \theta θ and agent n n n ’s signal vector x n x_n x n are each rankings of the items. The signal for each item is then its order in the ranking, so Θ = X = [ M ] \Theta=\mathcal{X}=[M] Θ = X = [ M ] . Because the full signal is a permutation, the vectors lie in the smaller set S M ⊂ Θ M = X M \mathcal{S}_M\subset\Theta^M=\mathcal{X}^M S M ⊂ Θ M = X M . For the Mallows model with η \eta η , θ ∈ S M \theta\in\mathcal{S}_M θ ∈ S M is a reference ranking (e.g., the ground-truth ordering of items) and η = ( η 1 , … , η N ) ∈ R > 0 N \eta=(\eta_1,\ldots,\eta_N)\in\mathbb{R}_{>0}^{N} η = ( η 1 , … , η N ) ∈ R > 0 N is a noise parameter vector, allowing each agent to have their own “ranking noise.”
In this model, agent n n n ’s observed ranking x ∈ S M x\in\mathcal{S}_M x ∈ S M is generated with probability
P n ( x n = x ∣ θ ) ∝ exp ( − 1 η n d τ ( θ , x ) ) P_n(x_n=x\mid\theta)\propto\exp\left(-\frac{1}{\eta_n}d_\tau(\theta,x)\right) P n ( x n = x ∣ θ ) ∝ exp ( − η n 1 d τ ( θ , x ) ) where d τ d_\tau d τ is Kendall’s tau distance (see Definition 2.1), which measures the number of pairwise disagreements between two rankings.
In the Mallows model, smaller η n \eta_n η n yields rankings closer to the reference θ \theta θ , while larger η n \eta_n η n produces noisier (more random) rankings.
Example 2.5 (Thurstone model [27 ] ). Let Θ = X = R \Theta= \mathcal{X} = \mathbb{R} Θ = X = R . The latent state θ \boldsymbol{\theta} θ is a vector in R M \mathbb{R}^{M} R M , each coordinate θ i \theta_i θ i being the true cost of item i i i . We assume an exchangeable prior with pairwise distinct costs almost surely, for example, i.i.d. standard Gaussian costs.
Each agent n n n then sees a noisy version of each θ i \theta_i θ i : they observe Gaussian signals x n , i x_{n,i} x n , i , where
x n , i ∣ θ ∼ N ( θ i , η n ) x_{n,i} \mid\boldsymbol{\theta} \sim\mathcal{N}(\theta_i,\eta_n) x n , i ∣ θ ∼ N ( θ i , η n ) with η n > 0 \eta_n > 0 η n > 0 specifying the noise level for agent n n n . Conditional on θ \boldsymbol{\theta} θ , the signals are independent across items and agents.
In the Thurstone model, each agent sees noisy measurements of the underlying item costs, with more reliable agents having lower η n \eta_n η n . The Thurstone model is a classical foundation for statistical models of ranking and paired comparison. While agents ultimately report an ordering (ranking) derived from these perturbed costs, unlike the Mallows model, in the Thurstone model the agent signal is not a ranking per se.
Example 2.6 (Additive RUM [27 , 25 , 1 ] ). Let Θ = X = R \Theta= \mathcal{X} = \mathbb{R} Θ = X = R . The true item costs θ ∈ R M \boldsymbol{\theta} \in\mathbb{R}^{M} θ ∈ R M have an exchangeable prior and are pairwise distinct almost surely. Each agent n n n observes
x n , i = θ i + ϵ n , i x_{n,i} = \theta_i + \epsilon_{n,i} x n , i = θ i + ϵ n , i for each item i i i . The noise terms are independent of θ \boldsymbol{\theta} θ and of each other, and for each agent they have a common everywhere-positive, strictly log-concave density on R \mathbb{R} R . Examples include Gaussian and reflected Gumbel noise. With reflected Gumbel noise, ranking costs in increasing order is equivalent to ranking the utilities − θ i -\theta_i − θ i plus Gumbel noise in decreasing order, yielding a Plackett–Luce ranking model [17 , 20 ] .
For θ i < θ j \theta_i < \theta_j θ i < θ j and x i < x j x_i < x_j x i < x j , the residuals x i − θ i x_i - \theta_i x i − θ i and x j − θ j x_j - \theta_j x j − θ j lie strictly between the swapped residuals x i − θ j x_i - \theta_j x i − θ j and x j − θ i x_j - \theta_i x j − θ i and have the same sum. Strict concavity of the log density therefore gives a strictly larger product density for the aligned observations. This establishes the SOC swap inequality. The Thurstone model is the Gaussian special case.
Note that agents can be heterogeneous when P n ≠ P n ′ P_n \ne P_{n'} P n = P n ′ . Throughout the paper, for readability, we use probability-mass notation such as P ( x = x ∣ θ ) P(\mathbf{x} = \mathbf{x} \mid\boldsymbol{\theta}) P ( x = x ∣ θ ) and write sums over states or signals. In continuous state or signal spaces, these statements and calculations are interpreted as the relevant densities and integrals under common dominating measures.
Thus, our general requirement is satisfied by several standard ranking models, rather than by a mechanism-specific prior. In Appendix § 13 , we discuss its connection to the Independence of Irrelevant Alternatives principle and give a necessity result illustrating why the SOC orientation matters for agreement-based incentives.
Peer Prediction Mechanism Design for Ordinal Data
We want to elicit ordinal information from agents. For each agent n n n , we formalize this via a target function Γ n : X M → R n \Gamma_n : \mathcal{X}^{M} \to\mathcal{R}_n Γ n : X M → R n , which maps a signal vector to a specific (truthful) report.3
Full ranking R n = S M \mathcal{R}_n = \mathcal{S}_M R n = S M and Γ n = ord ( x ) \Gamma_n = \operatorname{ord}(\mathbf{x}) Γ n = ord ( x ) . The target function ord ( x ) \operatorname{ord}(\mathbf{x}) ord ( x ) outputs a permutation r r r with r ( i ) < r ( j ) r(i) < r(j) r ( i ) < r ( j ) if and only if x i < x j x_i < x_j x i < x j (lower signals are better). Top set Given a size parameter K n ∈ Z > 0 K_n \in\mathbb{Z}_{>0} K n ∈ Z > 0 , R n = ( [ M ] K n ) \mathcal{R}_n = \binom{[M]}{K_n} R n = ( K n [ M ] ) and Γ n = t o p K n ( x ) \Gamma_n = top_{K_n}(x) Γ n = t o p K n ( x ) . The target function outputs the indices of the K n K_n K n smallest signals.
Bucket order [5 ] Given a shape parameter K n = ( K 1 n , … , K L n n ) K^n = (K^n_1,\ldots,K^n_{L_n}) K n = ( K 1 n , … , K L n n ) with ∑ ℓ K ℓ n = M \sum_{\ell} K^n_\ell= M ∑ ℓ K ℓ n = M , R n \mathcal{R}_n R n is the set of ordered partitions of [ M ] [M] [ M ] into buckets B 1 , … , B L n B_1,\ldots,B_{L_n} B 1 , … , B L n with ∣ B ℓ ∣ = K ℓ n |B_\ell| = K^n_\ell ∣ B ℓ ∣ = K ℓ n . The target function Γ n \Gamma_n Γ n places the K 1 n K^n_1 K 1 n items with the smallest signals in B 1 B_1 B 1 , the next K 2 n K^n_2 K 2 n in B 2 B_2 B 2 , and so on. Full rankings and top sets are the shapes ( 1 , … , 1 ) (1,\ldots,1) ( 1 , … , 1 ) and ( K n , M − K n ) (K_n,M-K_n) ( K n , M − K n ) defined in Definition 4.2 .
Subset assignment Given an assigned subset S n ⊆ [ M ] S_n \subseteq[M] S n ⊆ [ M ] , the target function Γ n \Gamma_n Γ n is the ranking ord ( x ) \operatorname{ord}(x) ord ( x ) restricted to these items. For instance, an assigned pair, ∣ S n ∣ = 2 |S_n| = 2 ∣ S n ∣ = 2 , reproduces the setting in Chen et al. [3 ] ; see § 4.1 .
To incentivize agents to truthfully report the target function of their private signals, a peer prediction mechanism creates a game between the agents. Formally, given target functions ( Γ n ) n ∈ [ N ] (\Gamma_n)_{n\in[N]} ( Γ n ) n ∈ [ N ] , each agent n n n privately observes her signal x n ∈ X M x_n \in\mathcal{X}^M x n ∈ X M , and reports r ~ n ∈ R n \tilde{r}_n \in\mathcal{R}_n r ~ n ∈ R n which is potentially different from the truthful target report r n : = Γ n ( x n ) r_n := \Gamma_n(x_n) r n := Γ n ( x n ) . A peer prediction mechanism ( U n ) n ∈ [ N ] (U_n)_{n\in[N]} ( U n ) n ∈ [ N ] takes all agents’ reports r ~ = ( r ~ 1 , … , r ~ N ) \tilde{r} = (\tilde{r}_1,\ldots,\tilde{r}_N) r ~ = ( r ~ 1 , … , r ~ N ) and pays/scores agent n n n with U n ( r ~ ) ∈ R U_n(\tilde{r}) \in\mathbb{R} U n ( r ~ ) ∈ R .
Each agent n n n ’s strategy is a random function from her signal to a report α n : x n ↦ r ~ n \alpha_n : x_n \mapsto\tilde{r}_n α n : x n ↦ r ~ n , and the randomness of their strategies is independent of each other’s and all signals. A (mixed) strategy profile α = ( α 1 , … , α N ) \alpha= (\alpha_1,\ldots,\alpha_N) α = ( α 1 , … , α N ) is a collection of all agents’ strategies. All agents are rational.
Definition 2.7. A mechanism is truthful if the truthful strategies form a Bayesian Nash equilibrium: for every agent n n n , signal x n x_n x n , and strategy α n \alpha_n α n with Pr [ α n ( x n ) ≠ Γ n ( x n ) ] > 0 \Pr[\alpha_n(x_n) \ne\Gamma_n(x_n)] > 0 Pr [ α n ( x n ) = Γ n ( x n )] > 0 ,
E [ U n ( Γ n ( x n ) , r − n ) ∣ x n ] > E [ U n ( α n ( x n ) , r − n ) ∣ x n ] . \mathbb{E}[U_n(\Gamma_n(x_n),r_{-n}) \mid x_n] > \mathbb{E}[U_n(\alpha_n(x_n),r_{-n}) \mid x_n]. E [ U n ( Γ n ( x n ) , r − n ) ∣ x n ] > E [ U n ( α n ( x n ) , r − n ) ∣ x n ] .
Here the deviation probability is over the randomness of α n \alpha_n α n at the fixed signal x n x_n x n . The expectation is over the peers’ truthful reports r − n : = ( Γ n ′ ( x n ′ ) ) n ′ ≠ n r_{-n} := (\Gamma_{n'}(x_{n'}))_{n'\ne n} r − n := ( Γ n ′ ( x n ′ ) ) n ′ = n and the randomness of α n \alpha_n α n .
Beyond expected utility, we also consider a stronger property where the truthful score distribution stochastically dominates the score distribution of any deviation.
Definition 2.8 ([31 ] ). A mechanism is stochastically dominant truthful (SDT) if for every agent n n n , signal x n x_n x n , and deviating strategy α n \alpha_n α n with Pr [ α n ( x n ) ≠ Γ n ( x n ) ] > 0 \Pr[\alpha_n(x_n) \ne\Gamma_n(x_n)] > 0 Pr [ α n ( x n ) = Γ n ( x n )] > 0 , where this deviation probability is over the strategy randomness at the fixed signal, the truthful payment random variable first-order stochastically dominates the payment from the deviation when the peers report truthfully. Formally, for all w ∈ R w \in\mathbb{R} w ∈ R :
Pr [ U n ( Γ n ( x n ) , r − n ) ≥ w ∣ x n ] ≥ Pr [ U n ( α n ( x n ) , r − n ) ≥ w ∣ x n ] \Pr[U_n(\Gamma_n(x_n),r_{-n}) \ge w \mid x_n] \ge\Pr[U_n(\alpha_n(x_n),r_{-n}) \ge w \mid x_n] Pr [ U n ( Γ n ( x n ) , r − n ) ≥ w ∣ x n ] ≥ Pr [ U n ( α n ( x n ) , r − n ) ≥ w ∣ x n ] with strict inequality for at least one w ∈ R w \in\mathbb{R} w ∈ R . The randomness is over the peers’ truthful reports r − n r_{-n} r − n , the randomness of α n \alpha_n α n , and any internal randomness of the mechanism.
Traditional truthful mechanisms require agents to be risk neutral and for their utilities to be linear with respect to their scores . With these assumptions, if the expected score decreases, so does their utility. However, these assumptions are often unrealistic. For example, students typically care about letter grades rather than numerical scores; in a crowd work setting, there may be a minimum score needed for rehiring. SDT addresses this by guaranteeing that the score distribution from truth-telling first-order stochastically dominates any deviation, incentivizing truthfulness for all monotone utility functions. This robustness makes SDT mechanisms suitable for practical applications where agents’ utilities may be unknown or nonlinear and where agents may not be risk neutral, such as peer assessment or human feedback for AI.
ALGORITHM 1: Kendall Tau Mechanism for Full-Rank Data
Input: r ~ ∈ S M N \tilde{r} \in S_M^N r ~ ∈ S M N , the reported full rankings of N N N agents over M M M items
foreach agent n ∈ [ N ] n \in[N] n ∈ [ N ] do
Compute score
U n ( r ~ ) = ∑ n ′ ≠ n ( ( M 2 ) − 2 d τ ( r ~ n , r ~ n ′ ) ) = ∑ n ′ ≠ n ∑ i < j sign ( r ~ n ( i ) , r ~ n ( j ) ; r ~ n ′ ( i ) , r ~ n ′ ( j ) ) . (2) U_n(\tilde{r}) = \sum_{n' \ne n} \left(\binom{M}{2} - 2d_\tau(\tilde{r}_n,\tilde{r}_{n'})\right) = \sum_{n' \ne n}\sum_{i<j}\operatorname{sign}(\tilde{r}_n(i),\tilde{r}_n(j);\tilde{r}_{n'}(i),\tilde{r}_{n'}(j)). \tag*{(2)} U n ( r ~ ) = n ′ = n ∑ ( ( 2 M ) − 2 d τ ( r ~ n , r ~ n ′ ) ) = n ′ = n ∑ i < j ∑ sign ( r ~ n ( i ) , r ~ n ( j ) ; r ~ n ′ ( i ) , r ~ n ′ ( j )) . (2) end
Truthfulness and SDT are unilateral guarantees: they compare truth-telling with a single agent’s deviation while peers report truthfully. They do not rule out other profiles, such as all agents reporting the same fixed ranking, that pay as much as truth-telling. Strong truthfulness, adapted from [24 ] , instead compares truth-telling with every strategy profile in a class A \mathcal{A} A . For full rankings, let r e v ∘ r ( i ) : = M + 1 − r ( i ) rev \circ r(i) := M + 1 - r(i) r e v ∘ r ( i ) := M + 1 − r ( i ) denote the global reversal of a ranking.
Definition 2.9. A mechanism is strongly truthful over a class A \mathcal{A} A of strategy profiles if for every α ∈ A \alpha\in\mathcal{A} α ∈ A and every agent n n n ,
E [ U n ( Γ 1 ( x 1 ) , … , Γ N ( x N ) ) ] ≥ E [ U n ( α 1 ( x 1 ) , … , α N ( x N ) ) ] , \mathbb{E}\left[U_n(\Gamma_1(x_1),\ldots,\Gamma_N(x_N))\right] \ge\mathbb{E}\left[U_n(\alpha_1(x_1),\ldots,\alpha_N(x_N))\right], E [ U n ( Γ 1 ( x 1 ) , … , Γ N ( x N )) ] ≥ E [ U n ( α 1 ( x 1 ) , … , α N ( x N )) ] , where the expectation is ex ante over all signals and strategy randomness, with equality only if α \alpha α is the truthful profile or its global reversal ( r e v ∘ Γ n ) n ∈ [ N ] (rev \circ\Gamma_n)_{n\in[N]} ( r e v ∘ Γ n ) n ∈ [ N ] .
§ 3.3 takes A \mathcal{A} A to be the index-equivariant profiles.
Kendall Tau Mechanisms for Eliciting Full Rankings
We introduce the Kendall tau mechanism for full rankings in Algorithm 1, which penalizes agents based on their Kendall tau distance from peers. We add the constant ( M 2 ) \binom{M}{2} ( 2 M ) to simplify the notation. Since Kendall tau distance treats a ranking as a collection of all pairwise comparisons, the mechanism rewards agents for every pair ( i , j ) (i,j) ( i , j ) whose order is consistent with a peer’s order. Thus, we may view Kendall tau mechanisms as agreement mechanisms on pairwise comparisons.
As a warm-up, § 3.1 proves that the Kendall tau mechanism is truthful. In particular, Lemma 3.2 uses symmetrization to compare the probability of order consistency and inconsistency. § 3.2 strengthens the result to stochastically dominant truthfulness. In particular, Theorem 3.4 implies Proposition 3.1. Finally, § 3.3 shows the mechanism is strongly truthful under index-equivariant strategies. All deferred proofs are in Appendices B and C.
Truthfulness
Proposition 3.1. For any strict Bayesian SOC information structure, the Kendall tau mechanism in Algorithm 1 is truthful.
The following lemma shows that under a Bayesian SOC model, the conditional probability of any peer’s signals given the agent’s private signal is also stochastically order consistent.
Lemma 3.2. If ( x , x ′ ) (\mathbf{x},\mathbf{x}') ( x , x ′ ) are sampled from a strict Bayesian SOC model, then for any distinct i , j ∈ [ M ] i,j \in[M] i , j ∈ [ M ] and signals x , x ′ ∈ X M \mathbf{x},\mathbf{x}' \in\mathcal{X}^{M} x , x ′ ∈ X M that are strictly order consistent at ( i , j ) (i,j) ( i , j ) , with x \mathbf{x} x of positive marginal mass or density,
Pr [ x ′ = x ′ ∣ x = x ] > Pr [ x ′ = σ i , j ( x ′ ) ∣ x = x ] \Pr[\mathbf{x}'=\mathbf{x}' \mid\mathbf{x}=\mathbf{x}] > \Pr[\mathbf{x}'=\sigma_{i,j}(\mathbf{x}') \mid\mathbf{x}=\mathbf{x}] Pr [ x ′ = x ′ ∣ x = x ] > Pr [ x ′ = σ i , j ( x ′ ) ∣ x = x ] where σ i , j \sigma_{i,j} σ i , j is the permutation that swaps coordinates i i i and j j j .
Proposition 3.1 follows immediately from the pairwise posterior-agreement property in Lemma 3.2: the expected utility decomposes pairwise, and each pair is maximized by the truthful comparison. We defer the proof to Appendix § 8 .
To analyze the full mechanism and facilitate the extensions, we define a comparison function from full rankings and rewrite Kendall tau distance.
Definition 3.3 (Comparison function). Let c o m p : S M → { − 1 , 0 , 1 } M × M comp : \mathcal{S}_{M} \to\{-1,0,1\}^{M \times M} co m p : S M → { − 1 , 0 , 1 } M × M output comparison matrix D = c o m p ( r ) D=comp(r) D = co m p ( r ) for any ranking r ∈ S M r \in\mathcal{S}_{M} r ∈ S M so that for all i , j i,j i , j
D ( i , j ) = sign ( r ( i ) , r ( j ) ) . D(i,j)=\operatorname{sign}(r(i),r(j)). D ( i , j ) = sign ( r ( i ) , r ( j )) . We can further define the comparison function on partial orders R ⊂ [ M ] 2 R \subset[M]^2 R ⊂ [ M ] 2 so that D ( i , j ) = 1 [ ( i , j ) ∈ R ] − 1 [ ( j , i ) ∈ R ] D(i,j)=\mathbf{1}[(i,j)\in R]-\mathbf{1}[(j,i)\in R] D ( i , j ) = 1 [( i , j ) ∈ R ] − 1 [( j , i ) ∈ R ] .
With this notation, the Kendall tau distance between r r r and r ′ r' r ′ is d τ ( r , r ′ ) = 1 2 ∑ i < j ( 1 − D ( i , j ) D ′ ( i , j ) ) d_{\tau}(r,r')=\frac{1}{2}\sum_{i<j}(1-D(i,j)D'(i,j)) d τ ( r , r ′ ) = 2 1 ∑ i < j ( 1 − D ( i , j ) D ′ ( i , j )) , where D = c o m p ( r ) D=comp(r) D = co m p ( r ) and D ′ = c o m p ( r ′ ) D'=comp(r') D ′ = co m p ( r ′ ) , and the score in Eq. (2) becomes
U n ( r ~ ) = ∑ n ′ ≠ n ∑ i < j D ~ n ( i , j ) D ~ n ′ ( i , j ) (3) U_n(\tilde r)=\sum_{n'\ne n}\sum_{i<j}\widetilde{D}_n(i,j)\widetilde{D}_{n'}(i,j) \tag*{(3)} U n ( r ~ ) = n ′ = n ∑ i < j ∑ D n ( i , j ) D n ′ ( i , j ) (3)
where D ~ n : = c o m p ( r ~ n ) \widetilde{D}_n:=comp(\tilde r_n) D n := co m p ( r ~ n ) for all n n n . Similarly, define D n : = c o m p ( r n ) D_n:=comp(r_n) D n := co m p ( r n ) for the truthful report of agent n n n .
Stochastically Dominant Truthfulness
Theorem 3.4. For any strict Bayesian SOC information structure, the Kendall tau mechanism in Algorithm 1 is stochastically dominant truthful.
Proof overview. To prove Theorem 3.4, we show that if all other agents are truthful, deviating to any nontruthful report r ~ \tilde r r ~ yields a first-order stochastically dominated score. Specifically, given agent n n n and her private signal x n x_n x n , we construct a sequence of reports ( r t ) t = 0 , … , T (r^t)_{t=0,\ldots,T} ( r t ) t = 0 , … , T for agent n n n with payments U t = U n ( r t , Γ ( X − n ) ) U^t=U_n(r^t,\Gamma(X_{-n})) U t = U n ( r t , Γ ( X − n )) , where Γ ( X − n ) : = ( Γ n ′ ( x n ′ ) ) n ′ ≠ n \Gamma(X_{-n}):=(\Gamma_{n'}(x_{n'}))_{n'\ne n} Γ ( X − n ) := ( Γ n ′ ( x n ′ ) ) n ′ = n denotes the peers’ truthful reports, so that r 0 = r ~ r^0=\tilde r r 0 = r ~ , r T = Γ n ( x n ) r^T=\Gamma_n(x_n) r T = Γ n ( x n ) is the truthful report, and
U t ≥ F O S D U t − 1 for all t = 1 , … , T , U^t \ge_{\mathrm{FOSD}} U^{t-1} \quad\text{for all } t=1,\ldots,T, U t ≥ FOSD U t − 1 for all t = 1 , … , T ,
which completes the proof by transitivity of first-order stochastic dominance. We construct the sequence by bubble sort.
Definition 3.5 (Correction path). Given an agent’s signal x x x and a reported ranking r ~ \tilde r r ~ , we define the correction path as the sequence of rankings r 0 , r 1 , … , r T r^0,r^1,\ldots,r^T r 0 , r 1 , … , r T to transform r ~ \tilde r r ~ into o r d ( x ) ord(x) or d ( x ) through the bubble-sort algorithm.
Start: r 0 = r ~ r^0=\tilde r r 0 = r ~ .
Step t t t : Given r t − 1 r^{t-1} r t − 1 , we find a rank k t k_t k t such that the item at rank k t + 1 k_t+1 k t + 1 (called i t i_t i t ) and the item at rank k t k_t k t (called j t j_t j t ) satisfy x i t < x j t x_{i_t}<x_{j_t} x i t < x j t —out of order relative to the signal. We then swap their ranks, setting r t ( i t ) = k t r^t(i_t)=k_t r t ( i t ) = k t and r t ( j t ) = k t + 1 r^t(j_t)=k_t+1 r t ( j t ) = k t + 1 .
End: r T = ord ( x ) r^T=\operatorname{ord}(x) r T = ord ( x ) , where no such adjacent contradictions exist.
Finally, let U t ( X − n ) = U n ( r t , Γ ( X − n ) ) U^t(\mathbf{X}_{-n})=U_n(r^t,\Gamma(\mathbf{X}_{-n})) U t ( X − n ) = U n ( r t , Γ ( X − n )) denote agent n n n ’s payment at step t t t given peer signals. Each step removes exactly one inversion of r t − 1 r^{t-1} r t − 1 relative to ord ( x ) \operatorname{ord}(x) ord ( x ) , so T T T equals the number of inversions of r ~ \tilde{r} r ~ , and T ≤ ( M 2 ) T\leq\binom{M}{2} T ≤ ( 2 M ) .
Because i t i_t i t and j t j_t j t are adjacent in both r t − 1 r^{t-1} r t − 1 and r t r^t r t , the only comparison that changes is the one between i t i_t i t and j t j_t j t . We therefore can decompose the peers’ signals into magnitude ρ \rho ρ , which specifies everything except how each peer orders this pair, and alignment a = ( a n ′ ) n ′ ≠ n ∈ { − 1 , 1 } N − 1 \mathbf{a}=(a_{n'})_{n'\ne n}\in\{-1,1\}^{N-1} a = ( a n ′ ) n ′ = n ∈ { − 1 , 1 } N − 1 , where a n ′ = 1 a_{n'}=1 a n ′ = 1 if peer n ′ n' n ′ orders ( i t , j t ) (i_t,j_t) ( i t , j t ) consistent with r t r^t r t .
Definition 3.6 (Magnitude, alignment vectors, and margins). Given an item pair ( i t , j t ) (i_t,j_t) ( i t , j t ) and a reference agent n n n with signal vector x n \mathbf{x}_n x n so that x n , i t < x n , j t x_{n,i_t}<x_{n,j_t} x n , i t < x n , j t , we classify the outcome space of peers’ signal matrix X − n ∈ X ( N − 1 ) × M \mathbf{X}_{-n}\in\mathcal{X}^{(N-1)\times M} X − n ∈ X ( N − 1 ) × M into equivalence classes V \mathcal{V} V called magnitude . We say two matrices X − n \mathbf{X}_{-n} X − n and X − n ′ \mathbf{X}'_{-n} X − n ′ have the same magnitude if for every peer n ′ ≠ n n'\ne n n ′ = n :
The set of entries at the pair indices is identical: { x n ′ , i t , x n ′ , j t } = { x n ′ , i t ′ , x n ′ , j t ′ } \{x_{n',i_t},x_{n',j_t}\}=\{x'_{n',i_t},x'_{n',j_t}\} { x n ′ , i t , x n ′ , j t } = { x n ′ , i t ′ , x n ′ , j t ′ } ;
All other entries are identical: x n ′ , k = x n ′ , k ′ x_{n',k}=x'_{n',k} x n ′ , k = x n ′ , k ′ for all k ∉ { i t , j t } k\notin\{i_t,j_t\} k ∈ / { i t , j t } .
For any ρ ∈ V \rho\in\mathcal{V} ρ ∈ V , let X ^ − n \widehat{\mathbf{X}}_{-n} X − n be the canonical element so that each peer’s signal x ^ n ′ \widehat{\mathbf{x}}_{n'} x n ′ and x n \mathbf{x}_n x n are order consistent at ( i t , j t ) (i_t,j_t) ( i t , j t ) , with x ^ n ′ , i t < x ^ n ′ , j t \widehat{x}_{n',i_t}<\widehat{x}_{n',j_t} x n ′ , i t < x n ′ , j t . For any matrix X − n ∈ ρ \mathbf{X}_{-n}\in\rho X − n ∈ ρ , we define the alignment vector a = ( a n ′ ) n ′ ≠ n ∈ { − 1 , 1 } N − 1 \mathbf{a}=(a_{n'})_{n'\ne n}\in\{-1,1\}^{N-1} a = ( a n ′ ) n ′ = n ∈ { − 1 , 1 } N − 1 to indicate whether each peer is order consistent with agent n n n . For all n ′ ≠ n n'\ne n n ′ = n ,
a n ′ = sign ( x n ′ , i t , x n ′ , j t ; x n , i t , x n , j t ) . a_{n'}=\operatorname{sign}(x_{n',i_t},x_{n',j_t};x_{n,i_t},x_{n,j_t}). a n ′ = sign ( x n ′ , i t , x n ′ , j t ; x n , i t , x n , j t ) . Given ρ \rho ρ and a \mathbf{a} a with canonical element X ^ − n \widehat{\mathbf{X}}_{-n} X − n ,
x n ′ , i = { x ^ n ′ , j t if i = i t and a n ′ = − 1 x ^ n ′ , i t if i = j t and a n ′ = − 1 x ^ n ′ , i otherwise. (4) x_{n',i}=
\begin{cases}
\widehat{x}_{n',j_t} & \text{if } i=i_t \text{ and } a_{n'}=-1\\
\widehat{x}_{n',i_t} & \text{if } i=j_t \text{ and } a_{n'}=-1\\
\widehat{x}_{n',i} & \text{otherwise.}
\end{cases} \tag*{(4)} x n ′ , i = ⎩ ⎨ ⎧ x n ′ , j t x n ′ , i t x n ′ , i if i = i t and a n ′ = − 1 if i = j t and a n ′ = − 1 otherwise. (4) We denote the magnitude and alignment vector of a matrix by ρ ( X − n ) \rho(\mathbf{X}_{-n}) ρ ( X − n ) and a ( X − n ) \mathbf{a}(\mathbf{X}_{-n}) a ( X − n ) . We define X ~ − n \widetilde{\mathbf{X}}_{-n} X − n as the fully reversed configuration corresponding to a = − 1 \mathbf{a}=-1 a = − 1 .
Finally, the margin is L ( a ) : = ∑ n ′ ≠ n a n ′ L(\mathbf{a}):=\sum_{n'\ne n}a_{n'} L ( a ) := ∑ n ′ = n a n ′ .
Let Q ( ρ , a ) Q(\rho,\mathbf{a}) Q ( ρ , a ) be the joint conditional mass of ( ρ , a ) (\rho,\mathbf{a}) ( ρ , a ) given x n \mathbf{x}_n x n at ( ρ , a ) (\rho,\mathbf{a}) ( ρ , a ) . In the density setting, Q Q Q is a density in ρ \rho ρ and a mass in a \mathbf{a} a , using the product reference measure restricted to canonical representatives. Sums over ρ \rho ρ then denote integrals. Let U t ( ρ , a ) = U n ( r t , Γ ( X − n ) ) U^t(\rho,\mathbf{a})=U_n(r^t,\Gamma(\mathbf{X}_{-n})) U t ( ρ , a ) = U n ( r t , Γ ( X − n )) be agent n n n ’s payment at step t t t given peer signals parameterized by ( ρ , a ) (\rho,\mathbf{a}) ( ρ , a ) .
Lemma 3.7 shows that, at a fixed magnitude, the score difference depends on the alignment only through the margin L ( a ) L(\mathbf{a}) L ( a ) . Write Q ( ρ , L = d ) = ∑ a : L ( a ) = d Q ( ρ , a ) Q(\rho,L=d)=\sum_{\mathbf{a}:L(\mathbf{a})=d}Q(\rho,\mathbf{a}) Q ( ρ , L = d ) = ∑ a : L ( a ) = d Q ( ρ , a ) .
Lemma 3.7. For each adjacent correction step , fixing the magnitude ρ \rho ρ , the score difference is determined by the peer-alignment margin . In particular, for any alignment vectors a , a ′ \mathbf{a},\mathbf{a}' a , a ′ ,
U t ( ρ , a ) − U t ( ρ , a ′ ) = L ( a ) − L ( a ′ ) (5) U^t(\rho,\mathbf{a})-U^t(\rho,\mathbf{a}')=L(\mathbf{a})-L(\mathbf{a}') \tag*{(5)} U t ( ρ , a ) − U t ( ρ , a ′ ) = L ( a ) − L ( a ′ ) (5) and
U t ( ρ , a ) = U t − 1 ( ρ , a ) + 2 L ( a ) . (6) U^t(\rho,\mathbf{a})=U^{t-1}(\rho,\mathbf{a})+2L(\mathbf{a}). \tag*{(6)} U t ( ρ , a ) = U t − 1 ( ρ , a ) + 2 L ( a ) . (6)
Lemma 3.8. Under strict Bayesian SOC, for any agent signal x n x_n x n of positive marginal mass or density, magnitude ρ \rho ρ , and d > 0 d > 0 d > 0 ,
Q ( ρ , L = d ) ≥ Q ( ρ , L = − d ) . (7) Q(\rho, L = d) \ge Q(\rho, L = -d). \tag*{(7)} Q ( ρ , L = d ) ≥ Q ( ρ , L = − d ) . (7)
By Lemma 3.7 , each correcting swap changes the score by a monotone function of the margin. Pairing opposite margins using Lemma 3.8 gives one-step weak stochastic dominance. We compose these steps and prove strictness separately via expected payments. The proofs of the two lemmas are in Appendix § 8 .
Proof of Theorem 3.4 . Given x n = x n x_n = x_n x n = x n and a correction path r 0 , … , r T r^0, \ldots, r^T r 0 , … , r T as in Definition 3.5 , it is enough to show
U t ≥ F O S D U t − 1 , ∀ t = 1 , … , T . (8) U^t \ge_{\mathrm{FOSD}} U^{t-1}, \qquad\forall t = 1, \ldots, T. \tag*{(8)} U t ≥ FOSD U t − 1 , ∀ t = 1 , … , T . (8)
Then transitivity of stochastic dominance gives, for all w ∈ R w \in\mathbb{R} w ∈ R ,
Pr [ U n ( o r d ( x n ) , Γ ( X − n ) ) ≥ w ∣ x n ] = Pr [ U T ≥ w ∣ x n ] ≥ Pr [ U 0 ≥ w ∣ x n ] = Pr [ U n ( r ~ , Γ ( X − n ) ) ≥ w ∣ x n ] . \begin{aligned}
\Pr[U_n(ord(x_n), \Gamma(X_{-n})) \ge w \mid x_n] &= \Pr[U^T \ge w \mid x_n] \\
&\ge\Pr[U^0 \ge w \mid x_n] \\
&= \Pr[U_n(\tilde r, \Gamma(X_{-n})) \ge w \mid x_n].
\end{aligned} Pr [ U n ( or d ( x n ) , Γ ( X − n )) ≥ w ∣ x n ] = Pr [ U T ≥ w ∣ x n ] ≥ Pr [ U 0 ≥ w ∣ x n ] = Pr [ U n ( r ~ , Γ ( X − n )) ≥ w ∣ x n ] .
(by Eq. (8) )
To prove Eq. (8) , by Eq. (5) , define u ( ρ , d ) = U t ( ρ , a ) u(\rho, d) = U^t(\rho, a) u ( ρ , d ) = U t ( ρ , a ) for all ρ \rho ρ and a a a with L ( a ) = d L(a) = d L ( a ) = d . Then
Pr [ U t ( ρ , a ) ≥ w ∣ x n ] − Pr [ U t − 1 ( ρ , a ) ≥ w ∣ x n ] = ∑ ρ , d ∑ L ( a ) = d Q ( ρ , a ) ( 1 [ U t ( ρ , a ) ≥ w ] − 1 [ U t − 1 ( ρ , a ) ≥ w ] ) = ∑ ρ , d ∑ L ( a ) = d Q ( ρ , a ) ( 1 [ u ( ρ , d ) ≥ w ] − 1 [ u ( ρ , d ) − 2 d ≥ w ] ) = ∑ ρ , d Q ( ρ , L = d ) ( 1 [ u ( ρ , d ) ≥ w ] − 1 [ u ( ρ , d ) − 2 d ≥ w ] ) . \begin{aligned}
\Pr[U^t(\rho, a) \ge w \mid x_n] - \Pr[U^{t-1}(\rho, a) \ge w \mid x_n]
&= \sum_{\rho,d} \sum_{L(a)=d} Q(\rho, a) \left(\mathbf{1}[U^t(\rho, a) \ge w] - \mathbf{1}[U^{t-1}(\rho, a) \ge w]\right) \\
&= \sum_{\rho,d} \sum_{L(a)=d} Q(\rho, a) \left(\mathbf{1}[u(\rho, d) \ge w] - \mathbf{1}[u(\rho, d) - 2d \ge w]\right) \\
&= \sum_{\rho,d} Q(\rho, L = d) \left(\mathbf{1}[u(\rho, d) \ge w] - \mathbf{1}[u(\rho, d) - 2d \ge w]\right).
\end{aligned} Pr [ U t ( ρ , a ) ≥ w ∣ x n ] − Pr [ U t − 1 ( ρ , a ) ≥ w ∣ x n ] = ρ , d ∑ L ( a ) = d ∑ Q ( ρ , a ) ( 1 [ U t ( ρ , a ) ≥ w ] − 1 [ U t − 1 ( ρ , a ) ≥ w ] ) = ρ , d ∑ L ( a ) = d ∑ Q ( ρ , a ) ( 1 [ u ( ρ , d ) ≥ w ] − 1 [ u ( ρ , d ) − 2 d ≥ w ] ) = ρ , d ∑ Q ( ρ , L = d ) ( 1 [ u ( ρ , d ) ≥ w ] − 1 [ u ( ρ , d ) − 2 d ≥ w ] ) .
(by Eq. (6) )
The terms with d = 0 d = 0 d = 0 cancel. Pairing positive and negative margins, the difference becomes
∑ ρ ∈ V , d > 0 [ Q ( ρ , L = d ) ( 1 [ u ( ρ , d ) ≥ w ] − 1 [ u ( ρ , d ) − 2 d ≥ w ] ) + Q ( ρ , L = − d ) ( 1 [ u ( ρ , − d ) ≥ w ] − 1 [ u ( ρ , − d ) + 2 d ≥ w ] ) ] = ∑ ρ ∈ V , d > 0 ( 1 [ u ( ρ , d ) ≥ w ] − 1 [ u ( ρ , d ) − 2 d ≥ w ] ) ( Q ( ρ , L = d ) − Q ( ρ , L = − d ) ) ≥ 0 , \begin{aligned}
&\sum_{\rho\in\mathcal{V},d>0} \bigg[ Q(\rho, L = d) \left(\mathbf{1}[u(\rho, d) \ge w] - \mathbf{1}[u(\rho, d) - 2d \ge w]\right) \\
&\qquad\qquad\qquad\quad+ Q(\rho, L = -d) \left(\mathbf{1}[u(\rho, -d) \ge w] - \mathbf{1}[u(\rho, -d) + 2d \ge w]\right) \bigg] \\
&= \sum_{\rho\in\mathcal{V},d>0} \left(\mathbf{1}[u(\rho, d) \ge w] - \mathbf{1}[u(\rho, d) - 2d \ge w]\right) \left(Q(\rho, L = d) - Q(\rho, L = -d)\right) \\
&\ge0,
\end{aligned} ρ ∈ V , d > 0 ∑ [ Q ( ρ , L = d ) ( 1 [ u ( ρ , d ) ≥ w ] − 1 [ u ( ρ , d ) − 2 d ≥ w ] ) + Q ( ρ , L = − d ) ( 1 [ u ( ρ , − d ) ≥ w ] − 1 [ u ( ρ , − d ) + 2 d ≥ w ] ) ] = ρ ∈ V , d > 0 ∑ ( 1 [ u ( ρ , d ) ≥ w ] − 1 [ u ( ρ , d ) − 2 d ≥ w ] ) ( Q ( ρ , L = d ) − Q ( ρ , L = − d ) ) ≥ 0 ,
where the equality uses Eq. (5) and the final inequality uses Lemma 3.8 together with 1 [ u ( ρ , d ) ≥ w ] ≥ 1 [ u ( ρ , d ) − 2 d ≥ w ] \mathbf{1}[u(\rho, d) \ge w] \ge\mathbf{1}[u(\rho, d) - 2d \ge w] 1 [ u ( ρ , d ) ≥ w ] ≥ 1 [ u ( ρ , d ) − 2 d ≥ w ] . This completes the proof of Eq. (8) .
Payments are bounded and weak dominance holds. It remains to show that misreporting strictly lowers the expected payment. By the pairwise decomposition in the proof of Proposition 3.1 , E [ U n ( r ~ , Γ ( X − n ) ) ∣ x n ] = ∑ n ′ ≠ n ∑ i < j D ~ n ( i , j ) E [ D n ′ ( i , j ) ∣ x n ] \mathbb{E}[U_n(\tilde r, \Gamma(X_{-n})) \mid x_n] = \sum_{n' \ne n} \sum_{i<j} \tilde D_n(i,j)\mathbb{E}[D_{n'}(i,j) \mid x_n] E [ U n ( r ~ , Γ ( X − n )) ∣ x n ] = ∑ n ′ = n ∑ i < j D ~ n ( i , j ) E [ D n ′ ( i , j ) ∣ x n ] , and the strict inequality in Lemma 3.2 makes each E [ D n ′ ( i , j ) ∣ x n ] \mathbb{E}[D_{n'}(i,j) \mid x_n] E [ D n ′ ( i , j ) ∣ x n ] nonzero with the sign of D n ( i , j ) D_n(i,j) D n ( i , j ) . Any ranking r ~ ≠ o r d ( x n ) \tilde r \ne ord(x_n) r ~ = or d ( x n ) flips at least one pair, so its expected payment is strictly below the truthful one, and so is that of any strategy that misreports with positive probability.
Strong Truthfulness under Index-Equivariant Strategies
Theorem 3.4 is a unilateral guarantee and does not rule out coordinated uninformative profiles, such as every agent reporting the same fixed ranking (§ 2.2 ). Such coordination, however, requires a common indexing of the items, which the designer can destroy by presenting the items to each agent under random relabeling (in RLHF, by randomly shuffling and rephrasing the responses shown to each annotator). Under randomized indexing, it is without loss of generality to restrict attention to index-equivariant strategies. A similar notion appears in [32 , 30 ] .
Definition 3.9. A (mixed) strategy α n : X M → Δ ( S M ) \alpha_n : \mathcal{X}^{M} \to\Delta(\mathcal{S}_{M}) α n : X M → Δ ( S M ) is index-equivariant if α n ( σ ( x n ) ) = d σ ( α n ( x n ) ) \alpha_n(\sigma(x_n)) \mathrel{\overset{d}{=}} \sigma(\alpha_n(x_n)) α n ( σ ( x n )) = d σ ( α n ( x n )) for all permutations σ ∈ S M \sigma\in\mathcal{S}_{M} σ ∈ S M and x n ∈ X M x_n \in\mathcal{X}^{M} x n ∈ X M , where σ \sigma σ acts on signal vectors by σ ( x ) i : = x σ − 1 ( i ) \sigma(x)_i := x_{\sigma^{-1}(i)} σ ( x ) i := x σ − 1 ( i ) and on rankings by σ ( r ) ( i ) : = r ( σ − 1 ( i ) ) \sigma(r)(i) := r(\sigma^{-1}(i)) σ ( r ) ( i ) := r ( σ − 1 ( i )) .
Truth-telling Γ n = o r d \Gamma_n = ord Γ n = or d is index-equivariant, as is its composition with the rank reversal r e v ∘ r ( i ) : = M + 1 − r ( i ) rev \circ r(i) := M + 1 - r(i) r e v ∘ r ( i ) := M + 1 − r ( i ) , but a constant strategy is not.
Theorem 3.10 (Strong truthfulness). For any strict, full-support Bayesian SOC information structure, the Kendall tau mechanism in Algorithm 1 is strongly truthful (Definition 2.9 ) over index-equivariant strategy profiles.
We defer the proof to Appendix § 9 and sketch it here. For a fixed pair ( i , j ) (i,j) ( i , j ) , we define the alignment factor κ n ( x ) : = 1 − 2 Pr [ D ~ n ( i , j ) ≠ sign ( x i , x j ) ∣ x n = x ] ∈ [ − 1 , 1 ] \kappa_n(x) := 1 - 2\Pr[\widetilde{D}_n(i,j) \ne\operatorname{sign}(x_i,x_j) \mid x_n = x] \in[-1,1] κ n ( x ) := 1 − 2 Pr [ D n ( i , j ) = sign ( x i , x j ) ∣ x n = x ] ∈ [ − 1 , 1 ] where κ n = 1 \kappa_n = 1 κ n = 1 for truth-telling. With Lemma 3.2 , we show that the expected score can be decomposed as positive terms scaled by the product κ n κ n ′ ∈ [ − 1 , 1 ] \kappa_n\kappa_{n'} \in[-1,1] κ n κ n ′ ∈ [ − 1 , 1 ] , so truth-telling attains the maximum.
For the equality case, full support forces each κ n \kappa_n κ n to be a constant sign ϵ i j ∈ { ± 1 } \epsilon^{ij} \in\{\pm1\} ϵ ij ∈ { ± 1 } identical for all agents, and equivariance ensures the identical flip across all pairs. Hence every agent either reports truthfully on all pairs (ϵ = 1 \epsilon= 1 ϵ = 1 ) or flips all pairs (ϵ = − 1 \epsilon= -1 ϵ = − 1 ), the global reversal.
Extensions
Subset Assignments
In many practical applications, the number of items M M M can be too large for every agent to rank. We therefore allow each agent n n n to report only on a possibly random assigned subset S n ⊆ [ M ] S_n \subseteq[M] S n ⊆ [ M ] and score only common item pairs shared with a randomly selected peer. For the comparison matrix D ~ n \widetilde{D}_n D n induced by agent n n n ’s report and one peer n ′ ≠ n n' \ne n n ′ = n drawn uniformly at random, the generalized score is
U n ( r ~ ) = ∑ i , j ∈ S n ∩ S n ′ : i < j D ~ n ( i , j ) D ~ n ′ ( i , j ) . (9) U_n(\widetilde{r}) = \sum_{\substack{i,j \in S_n \cap S_{n'}: i<j}} \widetilde{D}_n(i,j)\widetilde{D}_{n'}(i,j). \tag*{(9)} U n ( r ) = i , j ∈ S n ∩ S n ′ : i < j ∑ D n ( i , j ) D n ′ ( i , j ) . (9)
For subset top-sets, where D ~ n ( i , j ) \widetilde{D}_n(i,j) D n ( i , j ) records whether one item is inside the reported top set within S n S_n S n and the other is outside, the peer n ′ n' n ′ is instead drawn uniformly from the agents whose subsets contain S n S_n S n . Before reporting, an agent observes her signal and her own assigned subset S n S_n S n , but not the other realized assignments or the identity of her scoring peer. The assignments are independent of states and signals. The peer is sampled after reports, using only the assignments and randomness independent of signals and reports.
Conditional on the assignment and the drawn peer, Eq. (9) is the Kendall tau score on the shared set S n ∩ S n ′ S_n \cap S_{n'} S n ∩ S n ′ , all of which the peer observes. As first-order stochastic dominance is preserved under mixtures, the SDT guarantee is maintained after averaging over assignments and peers. To ensure that every reported comparison can affect the score, we require pairwise coverage assignment: for every agent n n n , every realization of S n S_n S n , and every pair { i , j } ⊆ S n \{i,j\} \subseteq S_n { i , j } ⊆ S n , Pr [ { i , j } ⊆ S n ′ ∣ S n ] > 0 \Pr[\{i,j\} \subseteq S_{n'} \mid S_n] > 0 Pr [{ i , j } ⊆ S n ′ ∣ S n ] > 0 , where the probability is over the assignment and the draw of n ′ n' n ′ .
Theorem 4.1. For any strict Bayesian SOC information structure and any assignment satisfying pairwise coverage, the generalized Kendall tau mechanism in Eq. (9) is SDT for subset rankings.
Here we illustrate why Eq. (9) scores agent n n n against a single random peer rather than summing over all peers. Let M = 3 M = 3 M = 3 with a uniform prior over rankings, and let every agent follow a Mallows model (Example 2.4 ). Agent n n n is assigned all three items, Alice is assigned { 1 , 2 } \{1,2\} { 1 , 2 } , Bob { 2 , 3 } \{2,3\} { 2 , 3 } , and Charlie { 1 , 3 } \{1,3\} { 1 , 3 } , so every pair is covered. Alice and Charlie are accurate, and Bob’s signal is close to uniformly random. Suppose agent n n n observes 1 ≻ 2 ≻ 3 1 \succ2 \succ3 1 ≻ 2 ≻ 3 and considers reporting 2 ≻ 1 ≻ 3 2 \succ1 \succ3 2 ≻ 1 ≻ 3 . When Alice and Charlie report the true order of their pairs, truth-telling disagrees with both of them in two true rankings, 2 ≻ 3 ≻ 1 2 \succ3 \succ1 2 ≻ 3 ≻ 1 and 3 ≻ 2 ≻ 1 3 \succ2 \succ1 3 ≻ 2 ≻ 1 , while the misreport disagrees with both only in 3 ≻ 1 ≻ 2 3 \succ1 \succ2 3 ≻ 1 ≻ 2 . Therefore, truth-telling is more likely to receive the lowest payment, and does not first-order stochastically dominate the misreport.
General Bucket Orders
Bucket orders generalize full rankings, top-K K K reports, and intermediate ordinal reports such as accept/borderline/reject tiers or ranked shortlists with unordered remainders.
Definition 4.2 (Bucket order [5 ] ). A bucket order of shape K = ( K 1 , … , K L ) \mathbf{K} = (K_1,\ldots,K_L) K = ( K 1 , … , K L ) with ∑ ℓ = 1 L K ℓ = M \sum_{\ell=1}^{L} K_\ell= M ∑ ℓ = 1 L K ℓ = M , L ≥ 2 L \ge2 L ≥ 2 , and K ℓ > 0 K_\ell> 0 K ℓ > 0 for all ℓ \ell ℓ is an ordered partition of [ M ] [M] [ M ] into blocks (buckets) B 1 , … , B L B_1,\ldots,B_L B 1 , … , B L with ∣ B ℓ ∣ = K ℓ |B_\ell| = K_\ell ∣ B ℓ ∣ = K ℓ . We encode a report r r r as β r ( i ) ∈ [ L ] \beta_r(i) \in[L] β r ( i ) ∈ [ L ] for the bucket of item i i i under r r r , with β r ( i ) = 1 \beta_r(i) = 1 β r ( i ) = 1 denoting the best bucket, and its comparison matrix D r = comp ( r ) \mathbf{D}_r = \operatorname{comp}(r) D r = comp ( r ) as
D r ( i , j ) = sign ( β r ( i ) , β r ( j ) ) ∈ { − 1 , 0 , 1 } , D_r(i,j) = \operatorname{sign}(\beta_r(i),\beta_r(j)) \in\{-1,0,1\}, D r ( i , j ) = sign ( β r ( i ) , β r ( j )) ∈ { − 1 , 0 , 1 } ,
so D r ( i , j ) = + 1 D_r(i,j) = +1 D r ( i , j ) = + 1 if i i i is in a strictly better bucket than j j j , and D r ( i , j ) = 0 D_r(i,j) = 0 D r ( i , j ) = 0 if i , j i,j i , j share a bucket.
In particular, full rankings have shape ( 1 , … , 1 ) (1,\ldots,1) ( 1 , … , 1 ) , and top-K K K reports have bucket shape ( K , M − K ) (K,M-K) ( K , M − K ) . For odd M M M , a median-pivot report, which identifies the median item and separates the items above it from those below, has shape ( M − 1 2 , 1 , M − 1 2 ) \left(\frac{M-1}{2},1,\frac{M-1}{2}\right) ( 2 M − 1 , 1 , 2 M − 1 ) .
We can generalize our Kendall tau mechanism to bucket orders. The target function Γ n ( x n ) \Gamma_n(x_n) Γ n ( x n ) sorts the signal and assigns the K 1 K_1 K 1 items with the smallest (best) signals to B 1 B_1 B 1 , the next K 2 K_2 K 2 to B 2 B_2 B 2 , and so on. We allow agents to have different shapes K n = ( K 1 n , … , K L n n ) \mathbf{K}^n = (K^n_1,\ldots,K^n_{L_n}) K n = ( K 1 n , … , K L n n ) with B ℓ n B^n_\ell B ℓ n for agent n n n ’s buckets. For comparison matrices, write ⟨ A , B ⟩ : = ∑ i < j A ( i , j ) B ( i , j ) \langle A,B\rangle:= \sum_{i<j} A(i,j)B(i,j) ⟨ A , B ⟩ := ∑ i < j A ( i , j ) B ( i , j ) . The Kendall tau mechanism pays agent n n n
U n ( r ~ ) = ∑ n ′ ≠ n ⟨ D r ~ n , D r ~ n ′ ⟩ . (10) U_n(\tilde r) = \sum_{n' \ne n} \langle D_{\tilde r_n},D_{\tilde r_{n'}}\rangle. \tag*{(10)} U n ( r ~ ) = n ′ = n ∑ ⟨ D r ~ n , D r ~ n ′ ⟩ . (10)
Theorem 4.3. For any strict Bayesian SOC information structure and any per-agent shapes K n \mathbf{K}^n K n , the Kendall tau mechanism in Eq. (10) restricted to shape-K n \mathbf{K}^n K n reports is stochastically dominant truthful.
The proof mirrors the full-ranking argument but lets a correcting step move two items across adjacent bucket boundaries rather than adjacent ranks. Only comparisons involving the swapped items and the two affected buckets can change. For each peer, the score increment has the form c t , n ′ a n ′ c_{t,n'}a_{n'} c t , n ′ a n ′ , where a n ′ ∈ { − 1 , 1 } a_{n'} \in\{-1,1\} a n ′ ∈ { − 1 , 1 } records alignment with the corrected pair and c t , n ′ ≥ 0 c_{t,n'} \ge0 c t , n ′ ≥ 0 is determined by the peer’s bucket placement. Thus the one-step score improvement is a nonnegative weighted margin ⟨ c t , a ⟩ \langle\mathbf{c}_t,\mathbf{a}\rangle ⟨ c t , a ⟩ . Bayesian SOC makes aligned peer configurations dominate anti-aligned ones conditional on the magnitude, yielding one-step stochastic dominance; composing the bucket-correction path proves the theorem. As bucket orders generalize top-set reports, we have the following corollary.
Corollary 4.4 (Top-set elicitation). For any strict Bayesian SOC information structure and fixed top-set sizes ( K n ) n ∈ [ N ] (K_n)_{n\in[N]} ( K n ) n ∈ [ N ] , the Kendall tau mechanism is stochastically dominant truthful for top-K n K_n K n reports.
In particular, for top sets r , r ′ ⊆ [ M ] r,r' \subseteq[M] r , r ′ ⊆ [ M ] with comparison matrices D , D ′ \mathbf{D},\mathbf{D}' D , D ′ , the specialized score has the overlap identity
∑ i < j D ( i , j ) D ′ ( i , j ) = M ∣ r ∩ r ′ ∣ − ∣ r ∣ ∣ r ′ ∣ . \sum_{i<j} D(i,j)D'(i,j) = M|r \cap r'| - |r||r'|. i < j ∑ D ( i , j ) D ′ ( i , j ) = M ∣ r ∩ r ′ ∣ − ∣ r ∣∣ r ′ ∣. Thus, for fixed reported set sizes, the mechanism rewards overlap with peers’ top sets. Equivalently, if a top set is encoded as a binary inclusion vector, this score is an affine transformation of the Enforced Agreement (EA) score [31 ] on binary reports as discussed in Appendix § 12 .
More general partial-order targets. The proof of Theorem 4.3 uses two features of bucket orders: each correcting step is a transposition σ i j \sigma_{ij} σ ij that relabels one report into another, and the resulting comparison-matrix increment is aligned with the corrected pair. More general partial-order targets can create dependencies among elicited comparisons, so extending stochastic-dominance truthfulness beyond fixed-shape bucket orders may require different arguments.
Experiments
Agent Payments Comparison
Figure 1 compares the empirical payment distributions of the Kendall tau peer-prediction mechanism under truthful reporting, uninformed random reporting, and unilateral random deviation.
Figure 1. ECDFs of agent payments under three reporting regimes: truth-telling (observed human rankings for SUSHI), uninformed reporting (uniform random permutations), and unilateral deviation (one agent reports a random permutation while others report truthfully or by their observed SUSHI rankings).
In each trial, agents submit full rankings and payments are computed using the score in Eq. (2) . For the synthetic experiments (Figure 1 (a) and Figure 1 (b)), we use N = 25 N = 25 N = 25 agents, M = 30 M = 30 M = 30 items, and 600 independent trials. In the Thurstone experiment (Figure 1 (a)), item costs are drawn i.i.d. from a standard Gaussian distribution, and each agent observes the costs perturbed by Gaussian noise with variance η n = 1 \eta_n = 1 η n = 1 , as in Example 2.5 . In the Mallows experiment (Figure 1 (b)), a latent reference ranking is sampled and agents’ truthful rankings are noisy Mallows perturbations of this reference with dispersion parameter η n = 0.8 \eta_n = 0.8 η n = 0.8 as defined in Example 2.4 . For SUSHI [10 ] (Figure 1 (c)), we treat the observed human ranking as the truthful/observed report: each trial samples N = 25 N = 25 N = 25 observed human rankings over M = 10 M = 10 M = 10 sushi items. This real-data setting is meant as an empirical stress test rather than a model guaranteed to satisfy Bayesian SOC.
For each model or dataset, we compare three reporting regimes.
In truth-telling , every agent reports the ranking induced by their signal. For SUSHI, this means the observed human ranking.
In uninformed reporting , every report is an independent uniformly random ranking.
In unilateral deviation , one focal agent reports a uniformly random ranking while peers report truthfully or by their observed SUSHI rankings. Repeating over focal agents and trials gives the deviation distribution.
For each regime, we pool payments across trials and plot their empirical cumulative distribution function (ECDF), so a lower, right-shifted curve corresponds to higher payments. Thus stochastic dominance of truthful reporting (Definition 2.8 ) means the truthful ECDF lies weakly below the deviation ECDF at every threshold.
Across the synthetic Bayesian SOC models (Thurstone and Mallows), the empirical payment distributions closely match the theoretical prediction of stochastically dominant truthfulness, with the ECDF of truthful reporting lying uniformly below, or equivalently right-shifted relative to, the alternatives in our simulations (Figure 1 (a) and Figure 1 (b)). On the real-world SUSHI dataset, while the dominance does not hold everywhere, the observed-report regime nevertheless has substantially more mass on higher payments (Figure 1 (c)). Taken together, these results support the distributional incentive prediction in synthetic SOC models and show favorable observed-report score distributions on heterogeneous, nonparametric preference data. In Appendix § 14 , we repeat the comparison against structured unilateral deviations, including near-truthful perturbations and coordination-style reports; the synthetic results remain favorable to truthful reporting, and the SUSHI observed-report distribution is generally the most favorable in this real-data stress test.
Sensitivity to Report Quality
In § 5.1 , we test the distributional incentive prediction. We now ask whether the payment is responsive to the quality of an agent’s report. We measure this by normalized sensitivity in the synthetic models and by a report-degradation test on SUSHI.
Synthetic models. In the Thurstone and Mallows models, we designate one focal agent while all other agents report truthfully, and we vary the focal agent’s noise or dispersion parameter η n \eta_n η n , where a larger η n \eta_n η n corresponds to noisier signals or lower effective effort. Let U n ( η n ) U_n(\eta_n) U n ( η n ) denote the focal agent’s payment. Following [29 ] , we measure normalized sensitivity by
Sens n = − d d η n E [ U n ( η n ) ] σ [ U n ( η n ) ] , \operatorname{Sens}_n = \frac{-\frac{d}{d\eta_n}\mathbb{E}[U_n(\eta_n)]}{\sigma[U_n(\eta_n)]}, Sens n = σ [ U n ( η n )] − d η n d E [ U n ( η n )] ,
so larger sensitivity values mean that expected payment falls more sharply, relative to payoff variability, as the focal agent’s signal becomes noisier.
We fix N = 25 N = 25 N = 25 agents and sweep the number of items M M M . In the Thurstone model, item costs θ ∈ R M \boldsymbol{\theta} \in\mathbb{R}^{M} θ ∈ R M are drawn i.i.d. from N ( 0 , 1 ) \mathcal{N}(0,1) N ( 0 , 1 ) and each agent observes them corrupted by independent Gaussian noise with variance η n \eta_n η n with the baseline η n = 0.7 \eta_n = 0.7 η n = 0.7 for every agent. In the Mallows model, the reference ranking is drawn uniformly from S M \mathcal{S}_M S M and each agent’s ranking is a Mallows perturbation of it with dispersion η n \eta_n η n with the baseline η n = 0.35 \eta_n = 0.35 η n = 0.35 for every agent. Both the derivative and the standard deviation in Sens n \operatorname{Sens}_n Sens n are evaluated at this baseline. We estimate the derivative by a symmetric finite difference in the focal agent’s η n \eta_n η n , with step δ = 0.05 \delta= 0.05 δ = 0.05 for Thurstone and δ = 0.03 \delta= 0.03 δ = 0.03 for Mallows, holding all other agents at the baseline. For each setting, we use 50 independent trials and 200 Monte Carlo samples, with common random numbers to reduce variance.
We compare Kendall tau scoring with six baselines. In Figure 2 , the cardinal baselines observe the agents’ numerical signals: EA1 and EA3 apply Enforced Agreement [31 ] after binarizing each signal by its sign or by whether it exceeds the average signal on that item, respectively. MI [14 ] scores empirical Shannon mutual information after discretizing signals into three quantile buckets, and DMI uses determinant mutual information [12 ] . The ordinal baselines observe only rankings: EA2 applies Enforced Agreement to each ranking’s top-half inclusion vector, and BPP [3 ] treats sampled unordered item pairs as independent binary comparison tasks.
Figure 2. Measurement-quality tests. Panels (a)–(b) compare normalized sensitivity for Kendall tau and baseline mechanisms under the Thurstone and Mallows models. Panel (c) degrades a focal observed SUSHI ranking by random adjacent swaps and plots mean focal-agent payment with a 95% confidence band.
Figure 2 (a) compares against all six baselines. Figure 2 (b) compares only against the ordinal baselines EA2 and BPP, since the Mallows model produces rankings rather than numerical signals. In both models, the Kendall tau mechanism has the largest normalized sensitivity among the tested mechanisms as the number of items grows. Since its sensitivity is positive, a small unilateral increase in the focal agent’s noise or dispersion locally lowers that agent’s expected payment.
SUSHI degradation. SUSHI has no observed signal-noise or effort parameter, so we instead degrade a focal agent’s observed ranking directly. Using the sampling of § 5.1 (N = 25 N = 25 N = 25 observed rankings over M = 10 M = 10 M = 10 items per trial), we apply k ∈ { 0 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 45 } k \in\{0, 1, 2, 3, 5, 8, 13, 21, 34, 45\} k ∈ { 0 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 45 } random adjacent transpositions to the focal agent’s ranking while all peers keep their observed rankings, and record the focal Kendall tau payment. Here k = 0 k = 0 k = 0 is the observed ranking and k = 45 = ( 10 2 ) k = 45 = \binom{10}{2} k = 45 = ( 2 10 ) approaches a random report. We average the focal payment over all N N N focal agents and 600 trials; the band in Figure 2 (c) is a normal-approximation 95% confidence interval for this mean. Mean payment decreases as the observed report is progressively degraded (Figure 2 (c)).
Thus, in these settings, the stochastic-dominance guarantee does not appear to reduce local sensitivity, and the score also tracks report quality on real preference data.
Discussion and Future Work
We introduce a simple peer-prediction mechanism that rewards pairwise agreement using Kendall tau, giving a general framework for ordinal information elicitation. Under Bayesian Stochastically Order Consistent (SOC) information structures—a broad class including Mallows and Thurstone models—truthful reporting stochastically dominates any deviation. Unlike mechanisms that rely on learning or strong prior assumptions, our mechanism handles heterogeneous agents with complex, continuous signal spaces. It also elicits fixed-shape bucket orders, including top-K K K sets, and handles subset assignments. Experiments on synthetic data and SUSHI preferences suggest that truthful or observed reporting receives more favorable score distributions than uninformed or deviating strategies in the tested settings.
While our mechanism has these advantages, there are also limitations. The largest is our assumption of Stochastically Order Consistent (Bayesian SOC), which is satisfied by standard ranking distributions but might not always hold. One example is the case of “cheap signals” [9 , 13 ] . Here agents have additional information on which they can coordinate besides the quality of the items that they are ranking. For example, instead of ranking peer reviews according to their overall quality, agents could rank them according to the institutions of the authors. This is a known issue in the peer-review literature, and our mechanism would not work as well in these cases. Our index-equivariance assumption in Definition 3.9 excludes this setting.
Another limitation occurs when not every agent evaluates every item. We can only reward an ordering of items i i i and j j j if another agent also orders them. This still allows flexible assignments—not every agent needs every item—but other mechanisms allow even more general assignments [22 , 3 ] .
Future research may investigate generalizations of the Bayesian SOC assumption, exploring whether our mechanism extends to alternative conditions such as Multivariate Total Positivity of order 2 [6 ] .
Preliminaries on Partial Orderings
A note on notation: as in the main text, we write probabilities and sums for readability. In continuous state or signal spaces, the corresponding statements are interpreted using densities and integrals with respect to common dominating measures.
A (strict) ordered set Y \mathcal{Y} Y has a strict total order so that for all y , y ′ , y ′ ′ ∈ Y y,y',y'' \in\mathcal{Y} y , y ′ , y ′′ ∈ Y
If y < y ′ y < y' y < y ′ , then not y ′ < y y' < y y ′ < y (asymmetric)
If y < y ′ y < y' y < y ′ , y ′ < y ′ ′ y' < y'' y ′ < y ′′ , then y < y ′ ′ y < y'' y < y ′′ (transitive)
If y ≠ y ′ y \ne y' y = y ′ , then y < y ′ y < y' y < y ′ or y ′ < y y' < y y ′ < y (complete)
A (strict) partially ordered set relaxes completeness.
Full-Ranking Proofs and Details for Theorem 3.4
Proof of Lemma 3.2. Since the conditioning signal has positive marginal mass or density, it suffices to show that Pr [ x ′ = x ′ , x = x ] > Pr [ x ′ = σ ( x ′ ) , x = x ] \Pr[x' = x', x = x] > \Pr[x' = \sigma(x'), x = x] Pr [ x ′ = x ′ , x = x ] > Pr [ x ′ = σ ( x ′ ) , x = x ] . The swapped joint likelihood may be zero. By the definition of a strict Bayesian SOC model, there is a prior μ \mu μ and conditional probabilities P P P and P ′ P' P ′ such that
Pr [ x ′ = x ′ , x = x ] = ∑ θ P ′ ( x ′ ∣ θ ) P ( x ∣ θ ) μ ( θ ) = 1 2 ( ∑ θ P ′ ( x ′ ∣ θ ) P ( x ∣ θ ) μ ( θ ) + ∑ θ P ′ ( x ′ ∣ σ ( θ ) ) P ( x ∣ σ ( θ ) ) μ ( σ ( θ ) ) ) (add twice) = 1 2 ( ∑ θ P ′ ( x ′ ∣ θ ) P ( x ∣ θ ) μ ( θ ) + ∑ θ P ′ ( x ′ ∣ σ ( θ ) ) P ( x ∣ σ ( θ ) ) μ ( θ ) ) ( μ exchangeable) = 1 2 ∑ θ ( P ′ ( x ′ ∣ θ ) P ( x ∣ θ ) + P ′ ( σ ( x ′ ) ∣ θ ) P ( σ ( x ) ∣ θ ) ) μ ( θ ) (neutrality and σ ( σ ( θ ) ) = θ ) \begin{aligned}
\Pr[x' = x',x = x]
&= \sum_{\theta} P'(x'|\theta)P(x|\theta)\mu(\theta) \\
&= \frac{1}{2}\left(\sum_{\theta}P'(x'|\theta)P(x|\theta)\mu(\theta)+\sum_{\theta}P'(x'|\sigma(\theta))P(x|\sigma(\theta))\mu(\sigma(\theta))\right)
\qquad\text{(add twice)} \\
&= \frac{1}{2}\left(\sum_{\theta}P'(x'|\theta)P(x|\theta)\mu(\theta)+\sum_{\theta}P'(x'|\sigma(\theta))P(x|\sigma(\theta))\mu(\theta)\right)
\qquad\text{(}\mu\text{ exchangeable)} \\
&= \frac{1}{2}\sum_{\theta}\left(P'(x'|\theta)P(x|\theta)+P'(\sigma(x')|\theta)P(\sigma(x)|\theta)\right)\mu(\theta)
\qquad\text{(neutrality and }\sigma(\sigma(\theta))=\theta\text{)}
\end{aligned} Pr [ x ′ = x ′ , x = x ] = θ ∑ P ′ ( x ′ ∣ θ ) P ( x ∣ θ ) μ ( θ ) = 2 1 ( θ ∑ P ′ ( x ′ ∣ θ ) P ( x ∣ θ ) μ ( θ ) + θ ∑ P ′ ( x ′ ∣ σ ( θ )) P ( x ∣ σ ( θ )) μ ( σ ( θ )) ) (add twice) = 2 1 ( θ ∑ P ′ ( x ′ ∣ θ ) P ( x ∣ θ ) μ ( θ ) + θ ∑ P ′ ( x ′ ∣ σ ( θ )) P ( x ∣ σ ( θ )) μ ( θ ) ) ( μ exchangeable) = 2 1 θ ∑ ( P ′ ( x ′ ∣ θ ) P ( x ∣ θ ) + P ′ ( σ ( x ′ ) ∣ θ ) P ( σ ( x ) ∣ θ ) ) μ ( θ ) (neutrality and σ ( σ ( θ )) = θ )
Therefore, the difference is
Pr [ x ′ = x ′ , x = x ] − Pr [ x ′ = σ ( x ′ ) , x = x ] = 1 2 ∑ θ ( P ′ ( x ′ ∣ θ ) P ( x ∣ θ ) + P ′ ( σ ( x ′ ) ∣ θ ) P ( σ ( x ) ∣ θ ) − P ′ ( σ ( x ′ ) ∣ θ ) P ( x ∣ θ ) − P ′ ( x ′ ∣ θ ) P ( σ ( x ) ∣ θ ) ) μ ( θ ) = 1 2 ∑ θ ( P ′ ( x ′ ∣ θ ) − P ′ ( σ ( x ′ ) ∣ θ ) ) ( P ( x ∣ θ ) − P ( σ ( x ) ∣ θ ) ) μ ( θ ) \begin{aligned}
\Pr[x' = x',x = x]-\Pr[x' = \sigma(x'),x = x]
&= \frac{1}{2}\sum_{\theta}\left(P'(x'|\theta)P(x|\theta)+P'(\sigma(x')|\theta)P(\sigma(x)|\theta)\right.\\
&\qquad\left.-P'(\sigma(x')|\theta)P(x|\theta)-P'(x'|\theta)P(\sigma(x)|\theta)\right)\mu(\theta)\\
&= \frac{1}{2}\sum_{\theta}\left(P'(x'|\theta)-P'(\sigma(x')|\theta)\right)\left(P(x|\theta)-P(\sigma(x)|\theta)\right)\mu(\theta)
\end{aligned} Pr [ x ′ = x ′ , x = x ] − Pr [ x ′ = σ ( x ′ ) , x = x ] = 2 1 θ ∑ ( P ′ ( x ′ ∣ θ ) P ( x ∣ θ ) + P ′ ( σ ( x ′ ) ∣ θ ) P ( σ ( x ) ∣ θ ) − P ′ ( σ ( x ′ ) ∣ θ ) P ( x ∣ θ ) − P ′ ( x ′ ∣ θ ) P ( σ ( x ) ∣ θ ) ) μ ( θ ) = 2 1 θ ∑ ( P ′ ( x ′ ∣ θ ) − P ′ ( σ ( x ′ ) ∣ θ ) ) ( P ( x ∣ θ ) − P ( σ ( x ) ∣ θ ) ) μ ( θ )
which depends on
( P ′ ( x ′ ∣ θ ) − P ′ ( σ ( x ′ ) ∣ θ ) ) ( P ( x ∣ θ ) − P ( σ ( x ) ∣ θ ) ) . (11) \left(P'(x'|\theta)-P'(\sigma(x')|\theta)\right)\left(P(x|\theta)-P(\sigma(x)|\theta)\right). \tag*{(11)} ( P ′ ( x ′ ∣ θ ) − P ′ ( σ ( x ′ ) ∣ θ ) ) ( P ( x ∣ θ ) − P ( σ ( x ) ∣ θ ) ) . (11)
If θ \theta θ is order consistent with x x x at ( i , j ) (i,j) ( i , j ) , and thus consistent with x ′ x' x ′ , then by Definition 2.2 P ′ ( x ′ ∣ θ ) > P ′ ( σ ( x ′ ) ∣ θ ) P'(x'|\theta) > P'(\sigma(x')|\theta) P ′ ( x ′ ∣ θ ) > P ′ ( σ ( x ′ ) ∣ θ ) and P ( x ∣ θ ) > P ( σ ( x ) ∣ θ ) P(x|\theta) > P(\sigma(x)|\theta) P ( x ∣ θ ) > P ( σ ( x ) ∣ θ ) , so (11) is positive. Similarly, if θ \theta θ is order consistent with σ ( x ) \sigma(x) σ ( x ) , Eq. (11) is also positive. Therefore, Pr [ x ′ = x ′ , x = x ] > Pr [ x ′ = σ ( x ′ ) , x = x ] \Pr[x' = x', \mathbf{x} = x] > \Pr[x' = \sigma(x'), \mathbf{x} = x] Pr [ x ′ = x ′ , x = x ] > Pr [ x ′ = σ ( x ′ ) , x = x ] , which completes the proof.
Proof of Proposition 3.1. By Definition 3.3, the mechanism depends only on pairwise comparisons. Hence, we can extend the Kendall tau mechanism to take comparison matrices as inputs rather than rankings. We show that this extended mechanism maintains truthfulness even when agents report arbitrary comparison matrices that do not correspond to any valid ranking.
Consider agent n n n . If all other agents report truthfully, we need to show that truth-telling maximizes the agent’s score. By Eq. (3) , the agent’s best response consists of choosing D ( i , j ) D(i,j) D ( i , j ) for each pair ( i , j ) (i,j) ( i , j ) separately to maximize her score. For any ( i , j ) (i,j) ( i , j ) with x n , i < x n , j x_{n,i} < x_{n,j} x n , i < x n , j , the score of truth-telling on pair ( i , j ) (i,j) ( i , j ) with agent n ′ n' n ′ is
E [ D n ′ ( i , j ) ∣ x n ] = Pr [ x n ′ , i < x n ′ , j ∣ x n ] − Pr [ x n ′ , i > x n ′ , j ∣ x n ] > 0 \mathbb{E}[D_{n'}(i,j) \mid x_n] = \Pr[x_{n',i} < x_{n',j} \mid x_n] - \Pr[x_{n',i} > x_{n',j} \mid x_n] > 0 E [ D n ′ ( i , j ) ∣ x n ] = Pr [ x n ′ , i < x n ′ , j ∣ x n ] − Pr [ x n ′ , i > x n ′ , j ∣ x n ] > 0
by Lemma 3.2, and it is larger than the score of reporting the wrong comparison − E [ D n ′ ( i , j ) ∣ x n ] -\mathbb{E}[D_{n'}(i,j) \mid x_n] − E [ D n ′ ( i , j ) ∣ x n ] . The case x i > x j x_i > x_j x i > x j holds by symmetry. Summing over all peers n ′ n' n ′ and pairs ( i , j ) (i,j) ( i , j ) , the unique best response is the comparison matrix consistent with the signal x n x_n x n , corresponding to the truthful ranking o r d ( x n ) = Γ n ( x n ) ord(x_n) = \Gamma_n(x_n) or d ( x n ) = Γ n ( x n ) .
Proof of Lemma 3.7. We can decompose the score into three parts.
U t ( ρ , a ) = U t ( X − n ) = ∑ n ′ ( ∑ i < j { i , j } ∉ { i t , j t } sign ( x n ′ , i , x n ′ , j ; r i t , r j t ) + ∑ i < j ∣ { i , j } ∩ { i t , j t } ∣ = 1 sign ( x n ′ , i , x n ′ , j ; r i t , r j t ) ) + L ( a ) , \begin{aligned}
U^t(\rho,a) = U^t(X_{-n}) \\
&= \sum_{n'} \left( \sum_{\substack{i<j\\ \{i,j\}\notin\{i_t,j_t\}}} \operatorname{sign}(x_{n',i},x_{n',j};r_i^t,r_j^t) + \sum_{\substack{i<j\\ |\{i,j\}\cap\{i_t,j_t\}|=1}} \operatorname{sign}(x_{n',i},x_{n',j};r_i^t,r_j^t) \right) + L(a),
\end{aligned} U t ( ρ , a ) = U t ( X − n ) = n ′ ∑ i < j { i , j } ∈ / { i t , j t } ∑ sign ( x n ′ , i , x n ′ , j ; r i t , r j t ) + i < j ∣ { i , j } ∩ { i t , j t } ∣ = 1 ∑ sign ( x n ′ , i , x n ′ , j ; r i t , r j t ) + L ( a ) ,
because
L ( a ) = ∑ n ′ sign ( x n ′ , i t , x n ′ , j t ; x n , i t , x n , j t ) , L(a) = \sum_{n'} \operatorname{sign}(x_{n',i_t},x_{n',j_t};x_{n,i_t},x_{n,j_t}), L ( a ) = n ′ ∑ sign ( x n ′ , i t , x n ′ , j t ; x n , i t , x n , j t ) ,
and
sign ( x n ′ , i t , x n ′ , j t ; x n , i t , x n , j t ) = sign ( x n ′ , i t , x n ′ , j t ; r i t t , r j t t ) . \operatorname{sign}(x_{n',i_t},x_{n',j_t};x_{n,i_t},x_{n,j_t}) = \operatorname{sign}(x_{n',i_t},x_{n',j_t};r_{i_t}^t,r_{j_t}^t). sign ( x n ′ , i t , x n ′ , j t ; x n , i t , x n , j t ) = sign ( x n ′ , i t , x n ′ , j t ; r i t t , r j t t ) .
For the difference U t ( ρ , a ) − U t ( ρ , a ′ ) U^t(\rho,a) - U^t(\rho,a') U t ( ρ , a ) − U t ( ρ , a ′ ) , the first terms agree because of the same class. Hence
U t ( ρ , a ) − U t ( ρ , a ′ ) = U t ( X − n ) − U t ( X − n ′ ) = ∑ n ′ ∑ i < j ∣ { i , j } ∩ { i t , j t } ∣ = 1 ( sign ( x n ′ , i , x n ′ , j ; r i t , r j t ) − sign ( x n ′ , i ′ , x n ′ , j ′ ; r i t , r j t ) ) + L ( a ) − L ( a ′ ) \begin{aligned}
U^t(\rho,a) - U^t(\rho,a') = U^t(X_{-n}) - U^t(X'_{-n}) \\
&= \sum_{n'} \sum_{\substack{i<j\\ |\{i,j\}\cap\{i_t,j_t\}|=1}} \left( \operatorname{sign}(x_{n',i},x_{n',j};r_i^t,r_j^t) - \operatorname{sign}(x'_{n',i},x'_{n',j};r_i^t,r_j^t) \right) + L(a) - L(a')
\end{aligned} U t ( ρ , a ) − U t ( ρ , a ′ ) = U t ( X − n ) − U t ( X − n ′ ) = n ′ ∑ i < j ∣ { i , j } ∩ { i t , j t } ∣ = 1 ∑ ( sign ( x n ′ , i , x n ′ , j ; r i t , r j t ) − sign ( x n ′ , i ′ , x n ′ , j ′ ; r i t , r j t ) ) + L ( a ) − L ( a ′ )
Finally, each term with n ′ n' n ′ and j ∉ { i t , j t } j \notin\{i_t,j_t\} j ∈ / { i t , j t } is equal to zero, because
∑ i ∈ { i t , j t } ( sign ( x n ′ , i , x n ′ , j ; r i t , r j t ) − sign ( x n ′ , i ′ , x n ′ , j ′ ; r i t , r j t ) ) = ∑ i ∈ { i t , j t } ( sign ( x n ′ , i , x n ′ , j ) − sign ( x n ′ , i ′ , x n ′ , j ′ ) ) sign ( r i t , r j t ) = ( sign ( x n ′ , i t , x n ′ , j ) − sign ( x n ′ , i t ′ , x n ′ , j ′ ) ) sign ( k t , r j t ) + ( sign ( x n ′ , j t , x n ′ , j ) − sign ( x n ′ , j t ′ , x n ′ , j ′ ) ) sign ( k t + 1 , r j t ) = ( sign ( x n ′ , i t , x n ′ , j ) − sign ( x n ′ , i t ′ , x n ′ , j ′ ) + sign ( x n ′ , j t , x n ′ , j ) − sign ( x n ′ , j t ′ , x n ′ , j ′ ) ) ⋅ sign ( k t , r j t ) (because sign ( k t + 1 , r j t ) = sign ( k t , r j t ) ) = 0 ( { x n ′ , i t , x n ′ , j t } = { x n ′ , i t ′ , x n ′ , j t ′ } ) . \begin{aligned}
\sum_{i\in\{i_t,j_t\}} \bigl(\operatorname{sign}(x_{n',i},x_{n',j};r_i^t,r_j^t)-\operatorname{sign}(x'_{n',i},x'_{n',j};r_i^t,r_j^t)\bigr)
&=\sum_{i\in\{i_t,j_t\}} \bigl(\operatorname{sign}(x_{n',i},x_{n',j})-\operatorname{sign}(x'_{n',i},x'_{n',j})\bigr)\operatorname{sign}(r_i^t,r_j^t)\\
&=\bigl(\operatorname{sign}(x_{n',i_t},x_{n',j})-\operatorname{sign}(x'_{n',i_t},x'_{n',j})\bigr)\operatorname{sign}(k_t,r_j^t)\\
&\quad+\bigl(\operatorname{sign}(x_{n',j_t},x_{n',j})-\operatorname{sign}(x'_{n',j_t},x'_{n',j})\bigr)\operatorname{sign}(k_t+1,r_j^t)\\
&=\bigl(\operatorname{sign}(x_{n',i_t},x_{n',j})-\operatorname{sign}(x'_{n',i_t},x'_{n',j})+\operatorname{sign}(x_{n',j_t},x_{n',j})-\operatorname{sign}(x'_{n',j_t},x'_{n',j})\bigr)\\
&\quad\cdot\operatorname{sign}(k_t,r_j^t)\qquad\text{(because }\operatorname{sign}(k_t+1,r_j^t)=\operatorname{sign}(k_t,r_j^t)\text{)}\\
&=0 \qquad\bigl(\{x_{n',i_t},x_{n',j_t}\}=\{x'_{n',i_t},x'_{n',j_t}\}\bigr).
\end{aligned} i ∈ { i t , j t } ∑ ( sign ( x n ′ , i , x n ′ , j ; r i t , r j t ) − sign ( x n ′ , i ′ , x n ′ , j ′ ; r i t , r j t ) ) = i ∈ { i t , j t } ∑ ( sign ( x n ′ , i , x n ′ , j ) − sign ( x n ′ , i ′ , x n ′ , j ′ ) ) sign ( r i t , r j t ) = ( sign ( x n ′ , i t , x n ′ , j ) − sign ( x n ′ , i t ′ , x n ′ , j ′ ) ) sign ( k t , r j t ) + ( sign ( x n ′ , j t , x n ′ , j ) − sign ( x n ′ , j t ′ , x n ′ , j ′ ) ) sign ( k t + 1 , r j t ) = ( sign ( x n ′ , i t , x n ′ , j ) − sign ( x n ′ , i t ′ , x n ′ , j ′ ) + sign ( x n ′ , j t , x n ′ , j ) − sign ( x n ′ , j t ′ , x n ′ , j ′ ) ) ⋅ sign ( k t , r j t ) (because sign ( k t + 1 , r j t ) = sign ( k t , r j t ) ) = 0 ( { x n ′ , i t , x n ′ , j t } = { x n ′ , i t ′ , x n ′ , j t ′ } ) .
This completes the proof of Eq. (5) .
Finally, swapping the ( i t , j t ) (i_t,j_t) ( i t , j t ) pair only affects the score difference between r t r^t r t and r t − 1 r^{t-1} r t − 1 on pair ( i t , j t ) (i_t,j_t) ( i t , j t ) across the N − 1 N-1 N − 1 peers. Hence U t − 1 ( ρ , a ) = U t ( ρ , a ) − 2 L ( a ) U^{t-1}(\rho,a)=U^t(\rho,a)-2L(a) U t − 1 ( ρ , a ) = U t ( ρ , a ) − 2 L ( a ) , which proves Eq. (6) .
Proof of Lemma 3.8. Fix x n x_n x n , ρ \rho ρ , and a correcting pair ( i , j ) = ( i t , j t ) (i,j)=(i_t,j_t) ( i , j ) = ( i t , j t ) with x n , i < x n , j x_{n,i}<x_{n,j} x n , i < x n , j . Let σ \sigma σ swap this pair, and write m = N − 1 m=N-1 m = N − 1 . If d ∉ { − m , − m + 2 , … , m } d\notin\{-m,-m+2,\ldots,m\} d ∈ / { − m , − m + 2 , … , m } , both sides are zero.
For each state θ \theta θ and peer n ′ ≠ n n'\ne n n ′ = n , let p n ′ , θ ( 1 ) = P n ′ ( x ~ n ′ ∣ θ ) p_{n',\theta}(1)=P_{n'}(\tilde{x}_{n'}\mid\theta) p n ′ , θ ( 1 ) = P n ′ ( x ~ n ′ ∣ θ ) and p n ′ , θ ( − 1 ) = P n ′ ( x ˘ n ′ ∣ θ ) p_{n',\theta}(-1)=P_{n'}(\breve{x}_{n'}\mid\theta) p n ′ , θ ( − 1 ) = P n ′ ( x ˘ n ′ ∣ θ ) be the likelihoods of the two orientations at the fixed magnitude. Conditional independence gives the likelihood of magnitude ρ \rho ρ and margin d d d in state θ \theta θ as
W θ ( d ) : = ∑ a : L ( a ) = d ∏ n ′ ≠ n p n ′ , θ ( a n ′ ) . W_\theta(d):=\sum_{\substack{a:L(a)=d}}\prod_{n'\ne n}p_{n',\theta}(a_{n'}). W θ ( d ) := a : L ( a ) = d ∑ n ′ = n ∏ p n ′ , θ ( a n ′ ) .
Neutrality implies W σ ( θ ) ( d ) = W θ ( − d ) W_{\sigma(\theta)}(d)=W_\theta(-d) W σ ( θ ) ( d ) = W θ ( − d ) . Write π n ( x n ) \pi_n(x_n) π n ( x n ) for the positive marginal mass or density of the focal signal. Pairing each state with its swap using exchangeability, and using the absence of state ties, gives
π n ( x n ) ( Q ( ρ , L = d ) − Q ( ρ , L = − d ) ) = ∑ θ : θ i < θ j μ ( θ ) ( P n ( x n ∣ θ ) − P n ( x n ∣ σ ( θ ) ) ) ⋅ ( W θ ( d ) − W θ ( − d ) ) . (12) \begin{aligned}
\pi_n(x_n)\bigl(Q(\rho,L=d)-Q(\rho,L=-d)\bigr)
&=\sum_{\theta:\theta_i<\theta_j}\mu(\theta)\bigl(P_n(x_n\mid\theta)-P_n(x_n\mid\sigma(\theta))\bigr)\\
&\quad\cdot\bigl(W_\theta(d)-W_\theta(-d)\bigr). \tag*{(12)}
\end{aligned} π n ( x n ) ( Q ( ρ , L = d ) − Q ( ρ , L = − d ) ) = θ : θ i < θ j ∑ μ ( θ ) ( P n ( x n ∣ θ ) − P n ( x n ∣ σ ( θ )) ) ⋅ ( W θ ( d ) − W θ ( − d ) ) . (12)
In continuous models the sum is an integral with respect to the prior; the likelihoods are densities under the convention of Section 2.1.
For each state in this sum, SOC and neutrality give P n ( x n ∣ θ ) ≥ P n ( x n ∣ σ ( θ ) ) P_n(x_n\mid\theta)\ge P_n(x_n\mid\sigma(\theta)) P n ( x n ∣ θ ) ≥ P n ( x n ∣ σ ( θ )) and p n ′ , θ ( 1 ) ≥ p n ′ , θ ( − 1 ) p_{n',\theta}(1)\ge p_{n',\theta}(-1) p n ′ , θ ( 1 ) ≥ p n ′ , θ ( − 1 ) for every peer. To compare the margin likelihoods even when some weights are zero, add ϵ > 0 \epsilon>0 ϵ > 0 to both orientation weights of every peer. Denote the resulting product-sum by W θ , ϵ ( d ) W_{\theta,\epsilon}(d) W θ , ϵ ( d ) . These are auxiliary weights, not a new probability model. Let k = ( m + d ) / 2 k=(m+d)/2 k = ( m + d ) /2 , and set
A ϵ = ∏ n ′ ≠ n ( p n ′ , θ ( − 1 ) + ϵ ) , λ n ′ = p n ′ , θ ( 1 ) + ϵ p n ′ , θ ( − 1 ) + ϵ ≥ 1. A_\epsilon=\prod_{n'\ne n}\bigl(p_{n',\theta}(-1)+\epsilon\bigr),\qquad
\lambda_{n'}=\frac{p_{n',\theta}(1)+\epsilon}{p_{n',\theta}(-1)+\epsilon}\ge1. A ϵ = n ′ = n ∏ ( p n ′ , θ ( − 1 ) + ϵ ) , λ n ′ = p n ′ , θ ( − 1 ) + ϵ p n ′ , θ ( 1 ) + ϵ ≥ 1.
An alignment with margin d d d has exactly k k k positive signs. Thus
W θ , ϵ ( d ) − W θ , ϵ ( − d ) = A ϵ ( E k ( λ ) − E m − k ( λ ) ) ≥ 0 W_{\theta,\epsilon}(d)-W_{\theta,\epsilon}(-d)=A_\epsilon\bigl(E_k(\lambda)-E_{m-k}(\lambda)\bigr)\ge0 W θ , ϵ ( d ) − W θ , ϵ ( − d ) = A ϵ ( E k ( λ ) − E m − k ( λ ) ) ≥ 0
by Lemma B.1. Each product-sum is a polynomial in the weights, so letting ϵ ↓ 0 \epsilon\downarrow0 ϵ ↓ 0 at this fixed state gives W θ ( d ) ≥ W θ ( − d ) W_\theta(d)\ge W_\theta(-d) W θ ( d ) ≥ W θ ( − d ) . All summands in Eq. (12) are therefore nonnegative, proving Eq. (7) .
For z = ( z 1 , … , z m ) z=(z_1,\ldots,z_m) z = ( z 1 , … , z m ) , the elementary symmetric polynomial of degree k k k is
E k ( z ) = ∑ S ∈ ( [ m ] k ) ∏ ℓ ∈ S z ℓ , E 0 ( z ) = 1. (13) \mathcal{E}_k(z)=\sum_{S\in\binom{[m]}{k}}\prod_{\ell\in S}z_\ell,\qquad\mathcal{E}_0(z)=1. \tag*{(13)} E k ( z ) = S ∈ ( k [ m ] ) ∑ ℓ ∈ S ∏ z ℓ , E 0 ( z ) = 1. (13)
Lemma B.1. If z ℓ ≥ 1 z_\ell\ge1 z ℓ ≥ 1 for all ℓ \ell ℓ and k k k is an integer with m / 2 < k ≤ m m/2<k\le m m /2 < k ≤ m , then E k ( z ) ≥ E m − k ( z ) \mathcal{E}_k(z)\ge\mathcal{E}_{m-k}(z) E k ( z ) ≥ E m − k ( z ) . If all z ℓ > 1 z_\ell>1 z ℓ > 1 , the inequality is strict.
Proof. Take a uniformly random permutation of [ m ] [m] [ m ] . Let S S S contain its first m − k m-k m − k indices and T T T its first k k k indices. Then S ⊂ T S\subset T S ⊂ T , and both sets are uniform among sets of their respective sizes. Since z ℓ ≥ 1 z_\ell\ge1 z ℓ ≥ 1 , the product over T T T is at least the product over S S S for every permutation. Therefore
E k ( z ) ( m k ) = E [ ∏ ℓ ∈ T z ℓ ] ≥ E [ ∏ ℓ ∈ S z ℓ ] = E m − k ( z ) ( m m − k ) . (14) \frac{\mathcal{E}_k(z)}{\binom{m}{k}}=\mathbb{E}\left[\prod_{\ell\in T}z_\ell\right]\ge\mathbb{E}\left[\prod_{\ell\in S}z_\ell\right]=\frac{\mathcal{E}_{m-k}(z)}{\binom{m}{m-k}}. \tag*{(14)} ( k m ) E k ( z ) = E [ ℓ ∈ T ∏ z ℓ ] ≥ E [ ℓ ∈ S ∏ z ℓ ] = ( m − k m ) E m − k ( z ) . (14)
The two denominators agree. When every z ℓ > 1 z_\ell>1 z ℓ > 1 , the product comparison is strict because T ∖ S T\setminus S T ∖ S is nonempty. □ \square □
Proofs and Details for Theorem 3.10
Proof. Fix an index-equivariant profile α \alpha α , and as in Eq. (3) let D ~ n = comp ( α n ( x n ) ) \widetilde{D}_n=\operatorname{comp}(\alpha_n(x_n)) D n = comp ( α n ( x n )) denote agent n n n ’s random reported comparison matrix. By linearity,
E [ U n ( α ( X ) ) ] = ∑ n ′ ≠ n ∑ i < j E [ D ~ n ( i , j ) D ~ n ′ ( i , j ) ] , (15) \mathbb{E}[U_n(\alpha(X))]=\sum_{n'\ne n}\sum_{i<j}\mathbb{E}\left[\widetilde{D}_n(i,j)\widetilde{D}_{n'}(i,j)\right], \tag*{(15)} E [ U n ( α ( X ))] = n ′ = n ∑ i < j ∑ E [ D n ( i , j ) D n ′ ( i , j ) ] , (15)
so we can focus on one peer n ′ ≠ n n'\ne n n ′ = n and one item pair ( i , j ) (i,j) ( i , j ) with i < j i<j i < j . Let σ = σ i j \sigma=\sigma_{ij} σ = σ ij . We define the alignment factor of strategy α n \alpha_n α n at ( i , j ) (i,j) ( i , j ) ,
κ n ( x ) : = 1 − 2 Pr [ D ~ n ( i , j ) ≠ sign ( x i , x j ) ∣ x n = x ] ∈ [ − 1 , 1 ] . \kappa_n(x):=1-2\Pr\left[\widetilde{D}_n(i,j)\ne\operatorname{sign}(x_i,x_j)\mid x_n=x\right]\in[-1,1]. κ n ( x ) := 1 − 2 Pr [ D n ( i , j ) = sign ( x i , x j ) ∣ x n = x ] ∈ [ − 1 , 1 ] .
We can write the expected reported comparison as E [ D ~ n ( i , j ) ∣ x n = x ] = κ n ( x ) sign ( x i , x j ) \mathbb{E}[\widetilde{D}_n(i,j)\mid x_n=x]=\kappa_n(x)\operatorname{sign}(x_i,x_j) E [ D n ( i , j ) ∣ x n = x ] = κ n ( x ) sign ( x i , x j ) , with κ n ≡ 1 \kappa_n\equiv1 κ n ≡ 1 for truth-telling. Moreover, κ n ( σ ( x ) ) = κ n ( x ) \kappa_n(\sigma(x))=\kappa_n(x) κ n ( σ ( x )) = κ n ( x ) because the strategy is index-equivariant. Since the strategies’ randomness is independent across agents and of all signals, conditioning on ( x n , x n ′ ) (x_n,x_{n'}) ( x n , x n ′ ) gives
E [ D ~ n ( i , j ) D ~ n ′ ( i , j ) ] = E [ κ n ( x n ) κ n ′ ( x n ′ ) sign ( x n , i , x n , j ; x n ′ , i , x n ′ , j ) ] . \mathbb{E}\left[\widetilde{D}_n(i,j)\widetilde{D}_{n'}(i,j)\right]=\mathbb{E}\left[\kappa_n(x_n)\kappa_{n'}(x_{n'})\operatorname{sign}(x_{n,i},x_{n,j};x_{n',i},x_{n',j})\right]. E [ D n ( i , j ) D n ′ ( i , j ) ] = E [ κ n ( x n ) κ n ′ ( x n ′ ) sign ( x n , i , x n , j ; x n ′ , i , x n ′ , j ) ] .
In the first part, we prove
E [ D ~ n ( i , j ) D ~ n ′ ( i , j ) ] ≤ E [ sign ( x n , i , x n , j ; x n ′ , i , x n ′ , j ) ] , (16) \mathbb{E}\left[\widetilde{D}_n(i,j)\widetilde{D}_{n'}(i,j)\right]\le\mathbb{E}\left[\operatorname{sign}(x_{n,i},x_{n,j};x_{n',i},x_{n',j})\right], \tag*{(16)} E [ D n ( i , j ) D n ′ ( i , j ) ] ≤ E [ sign ( x n , i , x n , j ; x n ′ , i , x n ′ , j ) ] , (16)
whose right side is the same pair term under truth-telling. Partition the pairs of signal vectors into groups of four, { ( x , x ′ ) , ( σ ( x ) , x ′ ) , ( x , σ ( x ′ ) ) , ( σ ( x ) , σ ( x ′ ) ) } \{(x,x'),(\sigma(x),x'),(x,\sigma(x')),(\sigma(x),\sigma(x'))\} {( x , x ′ ) , ( σ ( x ) , x ′ ) , ( x , σ ( x ′ )) , ( σ ( x ) , σ ( x ′ ))} with the representative satisfying sign ( x i , x j ) = sign ( x i ′ , x j ′ ) = 1 \operatorname{sign}(x_i,x_j)=\operatorname{sign}(x_i',x_j')=1 sign ( x i , x j ) = sign ( x i ′ , x j ′ ) = 1 , and let P ( x , x ′ ) : = Pr [ x n = x , x n ′ = x ′ ] P(x,x'):=\Pr[x_n=x,x_{n'}=x'] P ( x , x ′ ) := Pr [ x n = x , x n ′ = x ′ ] . The contribution of one group to the left side of Eq. (16) is
κ n ( x ) κ n ′ ( x ′ ) P ( x , x ′ ) − κ n ( σ ( x ) ) κ n ′ ( x ′ ) P ( σ ( x ) , x ′ ) − κ n ( x ) κ n ′ ( σ ( x ′ ) ) P ( x , σ ( x ′ ) ) + κ n ( σ ( x ) ) κ n ′ ( σ ( x ′ ) ) P ( σ ( x ) , σ ( x ′ ) ) = κ n ( x ) κ n ′ ( x ′ ) ( P ( x , x ′ ) − P ( σ ( x ) , x ′ ) − P ( x , σ ( x ′ ) ) + P ( σ ( x ) , σ ( x ′ ) ) ) ( κ n ( σ ( x ) ) = κ n ( x ) ) ≤ P ( x , x ′ ) − P ( σ ( x ) , x ′ ) − P ( x , σ ( x ′ ) ) + P ( σ ( x ) , σ ( x ′ ) ) , \begin{aligned}
&\kappa_n(x)\kappa_{n'}(x')P(x,x')-\kappa_n(\sigma(x))\kappa_{n'}(x')P(\sigma(x),x')\\
&\quad-\kappa_n(x)\kappa_{n'}(\sigma(x'))P(x,\sigma(x'))+\kappa_n(\sigma(x))\kappa_{n'}(\sigma(x'))P(\sigma(x),\sigma(x'))\\
&=\kappa_n(x)\kappa_{n'}(x')\left(P(x,x')-P(\sigma(x),x')-P(x,\sigma(x'))+P(\sigma(x),\sigma(x'))\right) \qquad(\kappa_n(\sigma(x))=\kappa_n(x))\\
&\le P(x,x')-P(\sigma(x),x')-P(x,\sigma(x'))+P(\sigma(x),\sigma(x')),
\end{aligned} κ n ( x ) κ n ′ ( x ′ ) P ( x , x ′ ) − κ n ( σ ( x )) κ n ′ ( x ′ ) P ( σ ( x ) , x ′ ) − κ n ( x ) κ n ′ ( σ ( x ′ )) P ( x , σ ( x ′ )) + κ n ( σ ( x )) κ n ′ ( σ ( x ′ )) P ( σ ( x ) , σ ( x ′ )) = κ n ( x ) κ n ′ ( x ′ ) ( P ( x , x ′ ) − P ( σ ( x ) , x ′ ) − P ( x , σ ( x ′ )) + P ( σ ( x ) , σ ( x ′ )) ) ( κ n ( σ ( x )) = κ n ( x )) ≤ P ( x , x ′ ) − P ( σ ( x ) , x ′ ) − P ( x , σ ( x ′ )) + P ( σ ( x ) , σ ( x ′ )) ,
where the inequality uses that ∣ κ n ( x ) κ n ′ ( x ′ ) ∣ ≤ 1 |\kappa_n(x)\kappa_{n'}(x')|\le1 ∣ κ n ( x ) κ n ′ ( x ′ ) ∣ ≤ 1 and the group’s truthful contribution is positive,
( P ( x , x ′ ) − P ( x , σ ( x ′ ) ) ) + ( P ( σ ( x ) , σ ( x ′ ) ) − P ( σ ( x ) , x ′ ) ) > 0 , \left(P(x,x')-P(x,\sigma(x'))\right)+\left(P(\sigma(x),\sigma(x'))-P(\sigma(x),x')\right)>0, ( P ( x , x ′ ) − P ( x , σ ( x ′ )) ) + ( P ( σ ( x ) , σ ( x ′ )) − P ( σ ( x ) , x ′ ) ) > 0 ,
by Lemma 3.2. Summing over groups yields Eq. (16) , with equality if and only if κ n ( x ) κ n ′ ( x ′ ) = 1 \kappa_n(x)\kappa_{n'}(x')=1 κ n ( x ) κ n ′ ( x ′ ) = 1 on every group of positive probability. Summing Eq. (16) over item pairs and peers proves
E [ U n ( α ( X ) ) ] ≤ E [ U n ( Γ ( X ) ) ] . \mathbb{E}[U_n(\alpha(X))]\le\mathbb{E}[U_n(\Gamma(X))]. E [ U n ( α ( X ))] ≤ E [ U n ( Γ ( X ))] .
For the second part, when the agent n n n gets the highest expected score E [ U n ( α ( X ) ) ] = E [ U n ( Γ ( X ) ) ] \mathbb{E}[U_n(\alpha(X))]=\mathbb{E}[U_n(\Gamma(X))] E [ U n ( α ( X ))] = E [ U n ( Γ ( X ))] , equality holds in Eq. (16) for every peer n ′ n' n ′ and every item pair ( i , j ) (i,j) ( i , j ) . By full support, κ n ( x ) κ n ′ ( x ′ ) = 1 \kappa_n(x)\kappa_{n'}(x')=1 κ n ( x ) κ n ′ ( x ′ ) = 1 for almost all ( x , x ′ ) (x,x') ( x , x ′ ) . Hence ∣ κ n ∣ = ∣ κ n ′ ∣ = 1 |\kappa_n|=|\kappa_{n'}|=1 ∣ κ n ∣ = ∣ κ n ′ ∣ = 1 , and fixing any x ′ x' x ′ shows κ n ( x ) = κ n ′ ( x ′ ) = ϵ i j ∈ { ± 1 } \kappa_n(x)=\kappa_{n'}(x')=\epsilon^{ij}\in\{\pm1\} κ n ( x ) = κ n ′ ( x ′ ) = ϵ ij ∈ { ± 1 } , independent of the signal and common to all agents. Finally, by index-equivariance, the alignment factors agree across item pairs, D ~ n ( i , j ) = ϵ sign ( x n , i , x n , j ) \widetilde{D}_n(i,j)=\epsilon\operatorname{sign}(x_{n,i},x_{n,j}) D n ( i , j ) = ϵ sign ( x n , i , x n , j ) almost surely for every pair. If ϵ = 1 \epsilon=1 ϵ = 1 , every agent reports Γ n ( x n ) \Gamma_n(x_n) Γ n ( x n ) . If ϵ = − 1 \epsilon=-1 ϵ = − 1 , every agent reports the reversed ranking r e v ∘ Γ n ( x n ) rev\circ\Gamma_n(x_n) r e v ∘ Γ n ( x n ) .
Subset-Assignment Proofs and Details in Section 4.1
The proof has two steps. Lemma D.1 follows the correction path of a misreport on S n S_n S n and shows that, for a fixed assignment and peer, each step that swaps two shared items strictly improves the score distribution, while every other step leaves the score unchanged. The proof of Theorem 4.1 then averages each step over assignments and peers and composes the steps. Let agent n n n ’s score at step t t t of the correction path against n ′ n' n ′ be
U n ′ t : = ∑ i , j ∈ S n ∩ S n ′ : i < j D n t ( i , j ) D r n ′ ( i , j ) , U_{n'}^t:=\sum_{\substack{i,j\in S_n\cap S_{n'}:i<j}}D_{n}^t(i,j)D_{r_{n'}}(i,j), U n ′ t := i , j ∈ S n ∩ S n ′ : i < j ∑ D n t ( i , j ) D r n ′ ( i , j ) ,
where r n ′ = Γ n ′ ( x n ′ ) r_{n'}=\Gamma_{n'}(x_{n'}) r n ′ = Γ n ′ ( x n ′ ) .
Lemma D.1 (One correcting step). Fix agent n n n ’s signal x n x_n x n , a report r ~ \tilde r r ~ with correction path r 0 , … , r T r^0,\ldots,r^T r 0 , … , r T on S n S_n S n , a realization of the assignment S S S , and a drawn peer n ′ n' n ′ . Then for every t = 1 , … , T t=1,\ldots,T t = 1 , … , T , conditional on ( x n , S , n ′ ) (x_n,S,n') ( x n , S , n ′ ) ,
{ U n ′ t > F O S D U n ′ t − 1 if i t , j t ∈ S n ∩ S n ′ , U n ′ t = U n ′ t − 1 otherwise. \begin{cases}
U_{n'}^t>_{\mathrm{FOSD}}U_{n'}^{t-1} & \text{if } i_t,j_t\in S_n\cap S_{n'},\\
U_{n'}^t=U_{n'}^{t-1} & \text{otherwise.}
\end{cases} { U n ′ t > FOSD U n ′ t − 1 U n ′ t = U n ′ t − 1 if i t , j t ∈ S n ∩ S n ′ , otherwise.
Proof. Write U n ′ s ( x ) U_{n'}^s(x) U n ′ s ( x ) for the value of U n ′ s U_{n'}^s U n ′ s when the peer’s signal is x n ′ = x x_{n'}=x x n ′ = x . Because i t i_t i t and j t j_t j t are adjacent in r t − 1 r^{t-1} r t − 1 , if the pair is not contained in S n ∩ S n ′ S_n\cap S_{n'} S n ∩ S n ′ , swapping it leaves the restricted ranking unchanged and hence U n ′ t ( x ) = U n ′ t − 1 ( x ) U_{n'}^t(x)=U_{n'}^{t-1}(x) U n ′ t ( x ) = U n ′ t − 1 ( x ) for every x x x . Now suppose i t , j t ∈ S n ∩ S n ′ i_t,j_t \in S_n \cap S_{n'} i t , j t ∈ S n ∩ S n ′ . They are still adjacent on the shared set, so the identities of Lemma 3.7 apply to the score on that set:
U n ′ t ( ρ , a n ′ ) − U n ′ t ( ρ , − a n ′ ) = 2 a n ′ , U n ′ t ( ρ , a n ′ ) − U n ′ t − 1 ( ρ , a n ′ ) = 2 a n ′ . U_{n'}^t(\rho,a_{n'})-U_{n'}^t(\rho,-a_{n'})=2a_{n'},
\qquad
U_{n'}^t(\rho,a_{n'})-U_{n'}^{t-1}(\rho,a_{n'})=2a_{n'}. U n ′ t ( ρ , a n ′ ) − U n ′ t ( ρ , − a n ′ ) = 2 a n ′ , U n ′ t ( ρ , a n ′ ) − U n ′ t − 1 ( ρ , a n ′ ) = 2 a n ′ .
Fixing the assignment and sampled peer does not change the law of that peer’s signal given x n x_n x n . Apply Lemma 3.8 to the two-agent marginal containing n n n and n ′ n' n ′ , with L = a n ′ L=a_{n'} L = a n ′ . Writing u ( ρ ) = U n ′ t ( ρ , 1 ) u(\rho)=U_{n'}^t(\rho,1) u ( ρ ) = U n ′ t ( ρ , 1 ) , we obtain for every w w w
Pr [ U n ′ t ≥ w ∣ x n , S , n ′ ] − Pr [ U n ′ t − 1 ≥ w ∣ x n , S , n ′ ] = ∑ ρ ( 1 [ u ( ρ ) ≥ w ] − 1 [ u ( ρ ) − 2 ≥ w ] ) ⋅ ( Q ( ρ , L = 1 ) − Q ( ρ , L = − 1 ) ) ≥ 0. \Pr[U_{n'}^t\ge w\mid x_n,S,n']-\Pr[U_{n'}^{t-1}\ge w\mid x_n,S,n']
=
\sum_{\rho}\left(\mathbf{1}[u(\rho)\ge w]-\mathbf{1}[u(\rho)-2\ge w]\right)
\cdot\left(Q(\rho,L=1)-Q(\rho,L=-1)\right)\ge0. Pr [ U n ′ t ≥ w ∣ x n , S , n ′ ] − Pr [ U n ′ t − 1 ≥ w ∣ x n , S , n ′ ] = ρ ∑ ( 1 [ u ( ρ ) ≥ w ] − 1 [ u ( ρ ) − 2 ≥ w ] ) ⋅ ( Q ( ρ , L = 1 ) − Q ( ρ , L = − 1 ) ) ≥ 0.
For strictness, Lemma 3.2 gives E [ a n ′ ∣ x n , S , n ′ ] > 0 \mathbb{E}[a_{n'}\mid x_n,S,n']>0 E [ a n ′ ∣ x n , S , n ′ ] > 0 , since the posterior comparison is more likely to align than to disagree. Consequently E [ U n ′ t − U n ′ t − 1 ∣ x n , S , n ′ ] > 0 \mathbb{E}[U_{n'}^t-U_{n'}^{t-1}\mid x_n,S,n']>0 E [ U n ′ t − U n ′ t − 1 ∣ x n , S , n ′ ] > 0 . Weak dominance and this strict mean difference for bounded scores imply strict inequality at some threshold. □
Proof of Theorem 4.1 . Fix x n x_n x n , the agent’s assignment S n S_n S n , and a deterministic misreport different from the truthful ranking on S n S_n S n . The correcting path depends only on this information. By Lemma D.1 , each step weakly improves the score distribution conditional on the complete assignment and chosen peer. Averaging over that assignment and peer conditional on ( x n , S n ) (x_n,S_n) ( x n , S n ) , and composing the steps, gives U T ≥ F O S D U 0 U^T\ge_{\mathrm{FOSD}} U^0 U T ≥ FOSD U 0 .
The first correcting pair is covered with positive probability by pairwise coverage. On coverage its expected gain is strictly positive by Lemma D.1 , and otherwise the gain is zero. Later steps have nonnegative expected gains. Hence E [ U T − U 0 ∣ x n , S n ] > 0 \mathbb{E}[U^T-U^0\mid x_n,S_n]>0 E [ U T − U 0 ∣ x n , S n ] > 0 , so the dominance is strict at some threshold. Mixing over reports preserves weak dominance and preserves a strict mean gain for any strategy that misreports with positive probability at the given signal and assignment. □
Bucket-Order Proofs
As in § 3.2 , we analyze the mechanism one correcting adjacent-bucket swap at a time for agent n n n ’s report.
To prove stochastic dominance, we first isolate the contribution of a single peer: for an agent report r r r and the truthful peer report r n ′ = Γ n ′ ( x n ′ ) r_{n'}=\Gamma_{n'}(x_{n'}) r n ′ = Γ n ′ ( x n ′ ) , set u n ′ ( r ) : = ⟨ D r , D r n ′ ⟩ u_{n'}(r):=\langle D_r,D_{r_{n'}}\rangle u n ′ ( r ) := ⟨ D r , D r n ′ ⟩ , so that U n ( r , X − n ) = ∑ n ′ ≠ n u n ′ ( r ) U_n(r,X_{-n})=\sum_{n'\ne n}u_{n'}(r) U n ( r , X − n ) = ∑ n ′ = n u n ′ ( r ) .
Definition E.1 (Bucket correction path). Given a shape-K n K^n K n report r ~ \tilde r r ~ and the truthful target r n : = Γ n ( x n ) r_n:=\Gamma_n(x_n) r n := Γ n ( x n ) , the bucket correction path r 0 , r 1 , … , r T r^0,r^1,\ldots,r^T r 0 , r 1 , … , r T is defined by r 0 = r ~ r^0=\tilde r r 0 = r ~ and, while r t − 1 ≠ r n r^{t-1}\ne r_n r t − 1 = r n , choosing adjacent buckets b , b + 1 b,b+1 b , b + 1 , letting i i i be the best-signal item of B b + 1 n B^n_{b+1} B b + 1 n and j j j the worst-signal item of B b n B^n_b B b n , and—whenever x n , i < x n , j x_{n,i}<x_{n,j} x n , i < x n , j —swapping them to form r t r^t r t .
By transitivity of ≥ F O S D \ge_{\mathrm{FOSD}} ≥ FOSD it suffices to prove that each step improves the score distribution:
U n ( r t , X − n ) ≥ F O S D U n ( r t − 1 , X − n ) given x n with x n , i < x n , j . (17) U_n(r^t,X_{-n})\ge_{\mathrm{FOSD}}U_n(r^{t-1},X_{-n})
\qquad\text{given }x_n\text{ with }x_{n,i}<x_{n,j}. \tag*{(17)} U n ( r t , X − n ) ≥ FOSD U n ( r t − 1 , X − n ) given x n with x n , i < x n , j . (17)
With the magnitude and alignment defined in Definition 3.6 , write U t ( ρ , a ) = U n ( r t , X − n ) U^t(\rho,a)=U_n(r^t,X_{-n}) U t ( ρ , a ) = U n ( r t , X − n ) for the step-t t t score under peer signals of magnitude ρ \rho ρ and alignment a a a . Because r t = σ i j r t − 1 r^t=\sigma_{ij}r^{t-1} r t = σ ij r t − 1 , bucketing commutes with relabeling, and ⟨ ⋅ , ⋅ ⟩ \langle\cdot,\cdot\rangle ⟨ ⋅ , ⋅ ⟩ is invariant under a common relabeling, the peer contribution satisfies
u n ′ t ( σ i j x n ′ ) = u n ′ t − 1 ( x n ′ ) . (18) u_{n'}^t(\sigma_{ij}x_{n'})=u_{n'}^{t-1}(x_{n'}). \tag*{(18)} u n ′ t ( σ ij x n ′ ) = u n ′ t − 1 ( x n ′ ) . (18)
The following lemma shows that we can write the difference as a linear function of the alignment vector a a a .
Lemma E.2. For any ( i t , j t ) (i_t,j_t) ( i t , j t ) , x n x_n x n , magnitude ρ \rho ρ and alignment vectors a , a ′ a,a' a , a ′ , there is a nonnegative integer vector c t \mathbf{c}_t c t so that
U t ( ρ , a ) − U t ( ρ , a ′ ) = 1 2 ⟨ c t , a − a ′ ⟩ (19) U^t(\rho,a)-U^t(\rho,a')=\frac{1}{2}\langle\mathbf{c}_t,a-a'\rangle \tag*{(19)} U t ( ρ , a ) − U t ( ρ , a ′ ) = 2 1 ⟨ c t , a − a ′ ⟩ (19) and
U t ( ρ , a ) − U t − 1 ( ρ , a ) = ⟨ c t , a ⟩ . (20) U^t(\rho,a)-U^{t-1}(\rho,a)=\langle\mathbf{c}_t,a\rangle. \tag*{(20)} U t ( ρ , a ) − U t − 1 ( ρ , a ) = ⟨ c t , a ⟩ . (20)
Proof. When i i i moves from bucket b + 1 b+1 b + 1 to b b b and j j j from b b b to b + 1 b+1 b + 1 , a pair’s comparison can change only if it involves i i i or j j j and the other element lies in bucket b b b or b + 1 b+1 b + 1 : both items cross only the boundary between buckets b b b and b + 1 b+1 b + 1 , so comparisons with items in buckets < b <b < b or > b + 1 >b+1 > b + 1 are unaffected. For the pair ( i , j ) (i,j) ( i , j ) , D r t − 1 ( i , j ) = sign ( b + 1 , b ) = − 1 D_{r_{t-1}}(i,j)=\operatorname{sign}(b+1,b)=-1 D r t − 1 ( i , j ) = sign ( b + 1 , b ) = − 1 and D r t ( i , j ) = sign ( b , b + 1 ) = + 1 D_{r_t}(i,j)=\operatorname{sign}(b,b+1)=+1 D r t ( i , j ) = sign ( b , b + 1 ) = + 1 , so Δ D ( i , j ) = 2 \Delta D(i,j)=2 Δ D ( i , j ) = 2 . For k ∈ ( B b n ∪ B b + 1 n ) ∖ { i , j } k\in(B_b^n\cup B_{b+1}^n)\setminus\{i,j\} k ∈ ( B b n ∪ B b + 1 n ) ∖ { i , j } , with β ( k ) ∈ { b , b + 1 } \beta(k)\in\{b,b+1\} β ( k ) ∈ { b , b + 1 } ,
Δ D ( i , k ) = sign ( b , β ( k ) ) − sign ( b + 1 , β ( k ) ) = + 1 , Δ D ( j , k ) = sign ( b + 1 , β ( k ) ) − sign ( b , β ( k ) ) = − 1 , \begin{aligned}
\Delta D(i,k)&=\operatorname{sign}(b,\beta(k))-\operatorname{sign}(b+1,\beta(k))=+1,\\
\Delta D(j,k)&=\operatorname{sign}(b+1,\beta(k))-\operatorname{sign}(b,\beta(k))=-1,
\end{aligned} Δ D ( i , k ) Δ D ( j , k ) = sign ( b , β ( k )) − sign ( b + 1 , β ( k )) = + 1 , = sign ( b + 1 , β ( k )) − sign ( b , β ( k )) = − 1 ,
and Δ D \Delta D Δ D vanishes on all other pairs. Thus, the difference becomes
u n ′ t − u n ′ t − 1 = ⟨ D r t , D r n ′ ⟩ − ⟨ D r t − 1 , D r n ′ ⟩ = ⟨ Δ D , D r n ′ ⟩ = 2 D r n ′ ( i , j ) + ∑ k ∈ ( B b n ∪ B b + 1 n ) ∖ { i , j } ( D r n ′ ( i , k ) − D r n ′ ( j , k ) ) . \begin{aligned}
u_{n'}^t-u_{n'}^{t-1}
&=\langle D_{r_t},D_{r_{n'}}\rangle-\langle D_{r_{t-1}},D_{r_{n'}}\rangle\\
&=\langle\Delta D,D_{r_{n'}}\rangle\\
&=2D_{r_{n'}}(i,j)+\sum_{k\in(B_b^n\cup B_{b+1}^n)\setminus\{i,j\}}\left(D_{r_{n'}}(i,k)-D_{r_{n'}}(j,k)\right).
\end{aligned} u n ′ t − u n ′ t − 1 = ⟨ D r t , D r n ′ ⟩ − ⟨ D r t − 1 , D r n ′ ⟩ = ⟨ Δ D , D r n ′ ⟩ = 2 D r n ′ ( i , j ) + k ∈ ( B b n ∪ B b + 1 n ) ∖ { i , j } ∑ ( D r n ′ ( i , k ) − D r n ′ ( j , k ) ) .
Now, we want to write the difference as a function of the alignment vector, u n ′ t − u n ′ t − 1 = c n ′ t a n ′ u_{n'}^t-u_{n'}^{t-1}=c_{n'}^t a_{n'} u n ′ t − u n ′ t − 1 = c n ′ t a n ′ . If i , j i,j i , j lie in one bucket of r n ′ r_{n'} r n ′ then D r n ′ ( i , j ) = 0 D_{r_{n'}}(i,j)=0 D r n ′ ( i , j ) = 0 and D r n ′ ( i , k ) = D r n ′ ( j , k ) D_{r_{n'}}(i,k)=D_{r_{n'}}(j,k) D r n ′ ( i , k ) = D r n ′ ( j , k ) for all k k k , so u n ′ t − u n ′ t − 1 = 0 u_{n'}^t-u_{n'}^{t-1}=0 u n ′ t − u n ′ t − 1 = 0 and we can set
c n ′ t : = 0. c_{n'}^t:=0. c n ′ t := 0.
If peer n ′ n' n ′ ranks i i i strictly above j j j , i.e. β r n ′ ( i ) < β r n ′ ( j ) \beta_{r_{n'}}(i)<\beta_{r_{n'}}(j) β r n ′ ( i ) < β r n ′ ( j ) , D r n ′ ( i , j ) = 1 D_{r_{n'}}(i,j)=1 D r n ′ ( i , j ) = 1 contributes 2. For the second term, D r n ′ ( i , k ) − D r n ′ ( j , k ) D_{r_{n'}}(i,k)-D_{r_{n'}}(j,k) D r n ′ ( i , k ) − D r n ′ ( j , k ) equals 2 when β r n ′ ( i ) < β r n ′ ( k ) < β r n ′ ( j ) \beta_{r_{n'}}(i)<\beta_{r_{n'}}(k)<\beta_{r_{n'}}(j) β r n ′ ( i ) < β r n ′ ( k ) < β r n ′ ( j ) , 1 when k k k shares a bucket with exactly one of i , j i,j i , j , and 0 otherwise, so summing the nonnegative terms gives u n ′ t − u n ′ t − 1 = c n ′ t u_{n'}^t-u_{n'}^{t-1}=c_{n'}^t u n ′ t − u n ′ t − 1 = c n ′ t with
c n ′ t = 2 + 2 ∣ { k : i ≺ n ′ k ≺ n ′ j } ∣ + ∣ { k : k ∼ n ′ i xor k ∼ n ′ j } ∣ ≥ 2 , c_{n'}^t=2+2|\{k:i\prec_{n'}k\prec_{n'}j\}|+|\{k:k\sim_{n'}i\mathbin{\operatorname{xor}}k\sim_{n'}j\}|\ge2, c n ′ t = 2 + 2∣ { k : i ≺ n ′ k ≺ n ′ j } ∣ + ∣ { k : k ∼ n ′ i xor k ∼ n ′ j } ∣ ≥ 2 ,
the counts over k ∈ ( B b n ∪ B b + 1 n ) ∖ { i , j } k\in(B_b^n\cup B_{b+1}^n)\setminus\{i,j\} k ∈ ( B b n ∪ B b + 1 n ) ∖ { i , j } and ≺ n ′ \prec_{n'} ≺ n ′ , ∼ n ′ \sim_{n'} ∼ n ′ denoting peer n ′ n' n ′ ’s strict bucket order and same-bucket relation, depending only on the buckets that the magnitude ρ \rho ρ fixes. This completes the case for a n ′ = 1 a_{n'}=1 a n ′ = 1 ; the case a n ′ = − 1 a_{n'}=-1 a n ′ = − 1 holds by symmetry. Applying σ i j \sigma_{ij} σ ij to the peer’s signal negates every sign above and hence the gain, so for every peer there is a coefficient ( c t ) n ′ ≥ 0 (c^t)_{n'}\ge0 ( c t ) n ′ ≥ 0 such that
u n ′ t − u n ′ t − 1 = c n ′ t a n ′ . (21) u_{n'}^t-u_{n'}^{t-1}=c_{n'}^t a_{n'}. \tag*{(21)} u n ′ t − u n ′ t − 1 = c n ′ t a n ′ . (21)
Summing over peers gives Eq. (20) , U t ( ρ , a ) − U t − 1 ( ρ , a ) = ∑ n ′ ( c t ) n ′ a n ′ = ⟨ c t , a ⟩ U^{t}(\rho,a)-U^{t-1}(\rho,a)=\sum_{n'}(c^{t})_{n'}a_{n'}=\langle c^{t},a\rangle U t ( ρ , a ) − U t − 1 ( ρ , a ) = ∑ n ′ ( c t ) n ′ a n ′ = ⟨ c t , a ⟩ . For Eq. (19) , Eq. (18) gives u n ′ t − 1 ( a ) = u n ′ t ( flip a n ′ ) u_{n'}^{t-1}(a)=u_{n'}^{t}(\operatorname{flip}a_{n'}) u n ′ t − 1 ( a ) = u n ′ t ( flip a n ′ ) , so u n ′ t ( + 1 ) − u n ′ t ( − 1 ) = ( c t ) n ′ u_{n'}^{t}(+1)-u_{n'}^{t}(-1)=(c^{t})_{n'} u n ′ t ( + 1 ) − u n ′ t ( − 1 ) = ( c t ) n ′ ; as u n ′ t u_{n'}^{t} u n ′ t is affine in a n ′ ∈ { − 1 , 1 } a_{n'}\in\{-1,1\} a n ′ ∈ { − 1 , 1 } ,
U t ( ρ , a ) − U t ( ρ , a ′ ) = ∑ n ′ ( u n ′ t ( a n ′ ) − u n ′ t ( a n ′ ′ ) ) = 1 2 ∑ n ′ ( c t ) n ′ ( a n ′ − a n ′ ′ ) = 1 2 ⟨ c t , a − a ′ ⟩ . U^{t}(\rho,a)-U^{t}(\rho,a')=\sum_{n'}\left(u_{n'}^{t}(a_{n'})-u_{n'}^{t}(a'_{n'})\right)=\frac{1}{2}\sum_{n'}(c^{t})_{n'}(a_{n'}-a'_{n'})=\frac{1}{2}\langle c^{t},a-a'\rangle. U t ( ρ , a ) − U t ( ρ , a ′ ) = n ′ ∑ ( u n ′ t ( a n ′ ) − u n ′ t ( a n ′ ′ ) ) = 2 1 n ′ ∑ ( c t ) n ′ ( a n ′ − a n ′ ′ ) = 2 1 ⟨ c t , a − a ′ ⟩ .
□
For a full ranking (K = 1 M K=1^{M} K = 1 M ) the buckets B b n , B b + 1 n B_{b}^{n},B_{b+1}^{n} B b n , B b + 1 n are singletons, every peer splits i , j i,j i , j , and c t = 2 1 c_{t}=2\,1 c t = 2 1 , so ⟨ c t , a ⟩ = 2 L ( a ) \langle c_{t},a\rangle=2L(a) ⟨ c t , a ⟩ = 2 L ( a ) , which is Lemma 3.7.
Lemma E.3. Given θ \theta θ with θ i < θ j \theta_i<\theta_j θ i < θ j , U n ( r t , X − n ) ≥ F O S D U n ( r t − 1 , X − n ) U_n(r^t,X_{-n})\ge_{\mathrm{FOSD}}U_n(r^{t-1},X_{-n}) U n ( r t , X − n ) ≥ FOSD U n ( r t − 1 , X − n ) conditional on $\theta.
Proof of Lemma E.3. Conditional on θ \theta θ the peers are independent (Section 2.1). If we condition further on the magnitude ρ \rho ρ (Definition 3.6), stochastic consistency (Definition 2.2) gives p n ′ : = Pr [ a n ′ = + 1 ∣ θ , ρ ] ≥ 1 2 p_{n'}:=\Pr[a_{n'}=+1\mid\theta,\rho]\ge\frac{1}{2} p n ′ := Pr [ a n ′ = + 1 ∣ θ , ρ ] ≥ 2 1 , the configuration a n ′ = + 1 a_{n'}=+1 a n ′ = + 1 being order consistent with θ \theta θ at ( i , j ) (i,j) ( i , j ) .
Fix a peer n ′ n' n ′ and let u + , u − u_+,u_- u + , u − be the values of u n ′ t u_{n'}^{t} u n ′ t at a n ′ = + 1 a_{n'}=+1 a n ′ = + 1 and a n ′ = − 1 a_{n'}=-1 a n ′ = − 1 ; by Eq. (21) the gain is u + − u − = ( c t ) n ′ ≥ 0 u_+-u_-=(c_t)_{n'}\ge0 u + − u − = ( c t ) n ′ ≥ 0 , and by Eq. (18) u n ′ t − 1 u_{n'}^{t-1} u n ′ t − 1 equals u n ′ t u_{n'}^{t} u n ′ t with a n ′ a_{n'} a n ′ flipped, so u n ′ t u_{n'}^{t} u n ′ t takes the larger value u + u_+ u + with probability p n ′ p_{n'} p n ′ whereas u n ′ t − 1 u_{n'}^{t-1} u n ′ t − 1 takes it with probability 1 − p n ′ ≤ p n ′ 1-p_{n'}\le p_{n'} 1 − p n ′ ≤ p n ′ . As u n ′ t u_{n'}^{t} u n ′ t and u n ′ t − 1 u_{n'}^{t-1} u n ′ t − 1 both have support on { u + , u − } \{u_+,u_-\} { u + , u − } and the former has more mass on the larger, u n ′ t ≥ F O S D u n ′ t − 1 u_{n'}^{t}\ge_{\mathrm{FOSD}}u_{n'}^{t-1} u n ′ t ≥ FOSD u n ′ t − 1 given ( θ , ρ ) (\theta,\rho) ( θ , ρ ) .
Finally, because stochastic dominance is preserved by sums of independent random variables [23 ] , summing over the independent coordinates gives
U n ( r t ) = ∑ n ′ u n ′ t ≥ F O S D ∑ n ′ u n ′ t − 1 = U n ( r t − 1 ) U_n(r^t)=\sum_{n'}u_{n'}^{t}\ge_{\mathrm{FOSD}}\sum_{n'}u_{n'}^{t-1}=U_n(r^{t-1}) U n ( r t ) = n ′ ∑ u n ′ t ≥ FOSD n ′ ∑ u n ′ t − 1 = U n ( r t − 1 )
given ( θ , ρ ) (\theta,\rho) ( θ , ρ ) ; averaging over ρ \rho ρ preserves the order.
□
Proof of Theorem 4.3. Fix an agent n n n , signal x n x_n x n , and misreport r ~ \tilde r r ~ , with correction path r 0 , … , r T r^0,\ldots,r^T r 0 , … , r T (Definition E.1). By transitivity of ≥ F O S D \ge_{\mathrm{FOSD}} ≥ FOSD , it suffices to prove the single-step dominance in Eq. (17) .
Fix a step and a threshold w ∈ R w\in\mathbb{R} w ∈ R , and set
G ( θ , w ) : = Pr [ U t ≥ w ∣ θ ] − Pr [ U t − 1 ≥ w ∣ θ ] , G(\theta,w):=\Pr[U^t\ge w\mid\theta]-\Pr[U^{t-1}\ge w\mid\theta], G ( θ , w ) := Pr [ U t ≥ w ∣ θ ] − Pr [ U t − 1 ≥ w ∣ θ ] ,
with U s = U n ( r s , X − n ) U^s=U_n(r^s,X_{-n}) U s = U n ( r s , X − n ) . Lemma E.3 gives G ( θ , w ) ≥ 0 G(\theta,w)\ge0 G ( θ , w ) ≥ 0 whenever θ i < θ j \theta_i<\theta_j θ i < θ j . Moreover, by Eq. (18) , sampling x n ′ ∼ P n ′ ( ⋅ ∣ σ i j θ ) x_{n'}\sim P_{n'}(\mathord\cdot\mid\sigma_{ij}\theta) x n ′ ∼ P n ′ ( ⋅ ∣ σ ij θ ) is the same as sampling x n ′ ∼ P n ′ ( ⋅ ∣ θ ) x_{n'}\sim P_{n'}(\mathord\cdot\mid\theta) x n ′ ∼ P n ′ ( ⋅ ∣ θ ) and relabeling by σ i j \sigma_{ij} σ ij . Hence G ( σ i j θ , w ) = − G ( θ , w ) G(\sigma_{ij}\theta,w)=-G(\theta,w) G ( σ ij θ , w ) = − G ( θ , w ) .
Stochastic consistency applied to the agent’s own signal, together with the exchangeability of μ \mu μ , yields the posterior tilt Pr [ θ ∣ x n ] ≥ Pr [ σ i j θ ∣ x n ] \Pr[\theta\mid x_n]\ge\Pr[\sigma_{ij}\theta\mid x_n] Pr [ θ ∣ x n ] ≥ Pr [ σ ij θ ∣ x n ] for θ i < θ j \theta_i<\theta_j θ i < θ j . Pairing each θ \theta θ with σ i j θ \sigma_{ij}\theta σ ij θ ,
Pr [ U t ≥ w ∣ x n ] − Pr [ U t − 1 ≥ w ∣ x n ] = ∑ θ : θ i < θ j ( Pr [ θ ∣ x n ] − Pr [ σ i j θ ∣ x n ] ) G ( θ , w ) ≥ 0 , \Pr[U^t\ge w\mid x_n]-\Pr[U^{t-1}\ge w\mid x_n]
=\sum_{\theta:\theta_i<\theta_j}\left(\Pr[\theta\mid x_n]-\Pr[\sigma_{ij}\theta\mid x_n]\right)G(\theta,w)\ge0, Pr [ U t ≥ w ∣ x n ] − Pr [ U t − 1 ≥ w ∣ x n ] = θ : θ i < θ j ∑ ( Pr [ θ ∣ x n ] − Pr [ σ ij θ ∣ x n ] ) G ( θ , w ) ≥ 0 ,
which proves Eq. (17) . Composing the T T T steps gives
U n ( r n , X − n ) ≥ F O S D ⋯ ≥ F O S D U n ( r 0 , X − n ) = U n ( r ~ , X − n ) . U_n(r_n,X_{-n})\ge_{\mathrm{FOSD}}\cdots\ge_{\mathrm{FOSD}}U_n(r^0,X_{-n})=U_n(\tilde r,X_{-n}). U n ( r n , X − n ) ≥ FOSD ⋯ ≥ FOSD U n ( r 0 , X − n ) = U n ( r ~ , X − n ) .
A mixed deviation is a mixture of such reports and inherits the dominance.
□
Theorem 4.3 subsumes Theorem 3.4 (shape 1 M 1^{M} 1 M ) and the top-set corollary Corollary 4.4 (shape ( K , M − K ) (K,M-K) ( K , M − K ) ). Subset assignments are treated in Appendix D.
Top-Set Score and Enforced Agreement
Top-K K K reports are bucket orders of shape ( K , M − K ) (K, M-K) ( K , M − K ) , so their truthfulness follows directly from Theorem 4.3 . We record the specialized score identity because it explains the top-set payment and its connection to binary Enforced Agreement.
Given two partial order relations R , R ′ R, R' R , R ′ with comparison matrices D , D ′ ∈ { − 1 , 0 , 1 } M × M D, D' \in\{-1,0,1\}^{M \times M} D , D ′ ∈ { − 1 , 0 , 1 } M × M in Definition 3.3 , define the affine pairwise-loss functional
ℓ τ ( R , R ′ ) = 1 2 ∑ i < j ( 1 − D ( i , j ) D ′ ( i , j ) ) . \ell_{\tau}(R,R') = \frac{1}{2}\sum_{i<j}(1-D(i,j)D'(i,j)). ℓ τ ( R , R ′ ) = 2 1 i < j ∑ ( 1 − D ( i , j ) D ′ ( i , j )) .
For top-set reports r ~ n , r ~ n ′ ⊆ [ M ] \tilde{r}_n,\tilde{r}_{n'} \subseteq[M] r ~ n , r ~ n ′ ⊆ [ M ] of fixed sizes, the score in Eq. (10) is equivalently
U n ( r ~ ) = ∑ n ′ ≠ n ∑ i < j D ~ n ( i , j ) D ~ n ′ ( i , j ) , (22) U_n(\tilde{r}) = \sum_{n'\ne n}\sum_{i<j}\widetilde{D}_{n}(i,j)\widetilde{D}_{n'}(i,j), \tag*{(22)} U n ( r ~ ) = n ′ = n ∑ i < j ∑ D n ( i , j ) D n ′ ( i , j ) , (22)
where D ( i , j ) = 1 [ i ∈ r , j ∉ r ] − 1 [ i ∉ r , j ∈ r ] D(i,j)=\mathbf{1}[i\in r,j\notin r]-\mathbf{1}[i\notin r,j\in r] D ( i , j ) = 1 [ i ∈ r , j ∈ / r ] − 1 [ i ∈ / r , j ∈ r ] .
Lemma F.1. Given sets r , r ′ ⊆ [ M ] r,r'\subseteq[M] r , r ′ ⊆ [ M ] with D = comp ( r ) D=\operatorname{comp}(r) D = comp ( r ) and D ′ = comp ( r ′ ) D'=\operatorname{comp}(r') D ′ = comp ( r ′ ) ,
∑ i < j D ( i , j ) D ′ ( i , j ) = M ∣ r ∩ r ′ ∣ − ∣ r ∣ ∣ r ′ ∣ . \sum_{i<j}D(i,j)D'(i,j)=M|r\cap r'|-|r||r'|. i < j ∑ D ( i , j ) D ′ ( i , j ) = M ∣ r ∩ r ′ ∣ − ∣ r ∣∣ r ′ ∣. Proof. If i , j i,j i , j have the same membership in r r r or the same membership in r ′ r' r ′ , the pair contributes zero. Agreement pairs have i ∈ r ∩ r ′ i\in r\cap r' i ∈ r ∩ r ′ and j ∉ r ∪ r ′ j\notin r\cup r' j ∈ / r ∪ r ′ , contributing + 1 +1 + 1 , while disagreement pairs have i ∈ r ∖ r ′ i\in r\setminus r' i ∈ r ∖ r ′ and j ∈ r ′ ∖ r j\in r'\setminus r j ∈ r ′ ∖ r , contributing − 1 -1 − 1 . Hence
∑ i < j D ( i , j ) D ′ ( i , j ) = ∣ r ∩ r ′ ∣ ( M − ∣ r ∣ − ∣ r ′ ∣ + ∣ r ∩ r ′ ∣ ) − ( ∣ r ∣ − ∣ r ∩ r ′ ∣ ) ( ∣ r ′ ∣ − ∣ r ∩ r ′ ∣ ) = M ∣ r ∩ r ′ ∣ − ∣ r ∣ ∣ r ′ ∣ . \begin{aligned}
\sum_{i<j}D(i,j)D'(i,j)
&=|r\cap r'|(M-|r|-|r'|+|r\cap r'|)\\
&\quad-(|r|-|r\cap r'|)(|r'|-|r\cap r'|)\\
&=M|r\cap r'|-|r||r'|.
\end{aligned} i < j ∑ D ( i , j ) D ′ ( i , j ) = ∣ r ∩ r ′ ∣ ( M − ∣ r ∣ − ∣ r ′ ∣ + ∣ r ∩ r ′ ∣ ) − ( ∣ r ∣ − ∣ r ∩ r ′ ∣ ) ( ∣ r ′ ∣ − ∣ r ∩ r ′ ∣ ) = M ∣ r ∩ r ′ ∣ − ∣ r ∣∣ r ′ ∣.
Proposition F.2 (Top-set Kendall tau and Enforced Agreement). For fixed set sizes K n , K n ′ K_n,K_{n'} K n , K n ′ and number of items M M M , the top-set Kendall tau score is affine equivalent to the Enforced Agreement (EA) score on binary inclusion reports:
U n ( r ~ ) = M 2 ∑ n ′ ≠ n S E A ( y ~ n , y ~ n ′ ) + C , U_n(\tilde{r})=\frac{M}{2}\sum_{n'\ne n}S_{\mathrm{EA}}(\tilde{y}_n,\tilde{y}_{n'})+C, U n ( r ~ ) = 2 M n ′ = n ∑ S EA ( y ~ n , y ~ n ′ ) + C , where S E A ( y ~ n , y ~ n ′ ) = ∑ i = 1 M 1 [ y ~ n , i = y ~ n ′ , i ] S_{\mathrm{EA}}(\tilde{y}_n,\tilde{y}_{n'})=\sum_{i=1}^{M}\mathbf{1}[\tilde{y}_{n,i}=\tilde{y}_{n',i}] S EA ( y ~ n , y ~ n ′ ) = ∑ i = 1 M 1 [ y ~ n , i = y ~ n ′ , i ] and C C C depends on M , K n , K n ′ M,K_n,K_{n'} M , K n , K n ′ but not on the reports.
Proof. For binary inclusion vectors y ~ n , y ~ n ′ \tilde{y}_n,\tilde{y}_{n'} y ~ n , y ~ n ′ ,
S E A ( y ~ n , y ~ n ′ ) = ∣ r ~ n ∩ r ~ n ′ ∣ + ∣ [ M ] ∖ ( r ~ n ∪ r ~ n ′ ) ∣ = M − K n − K n ′ + 2 ∣ r ~ n ∩ r ~ n ′ ∣ . S_{\mathrm{EA}}(\tilde{y}_n,\tilde{y}_{n'})=|\tilde{r}_n\cap\tilde{r}_{n'}|+|[M]\setminus(\tilde{r}_n\cup\tilde{r}_{n'})|=M-K_n-K_{n'}+2|\tilde{r}_n\cap\tilde{r}_{n'}|. S EA ( y ~ n , y ~ n ′ ) = ∣ r ~ n ∩ r ~ n ′ ∣ + ∣ [ M ] ∖ ( r ~ n ∪ r ~ n ′ ) ∣ = M − K n − K n ′ + 2∣ r ~ n ∩ r ~ n ′ ∣. Combining this with Lemma F.1 gives
U n ( r ~ ) = ∑ n ′ ≠ n ( M 2 S E A ( y ~ n , y ~ n ′ ) + M 2 ( K n + K n ′ − M ) − K n K n ′ ) , U_n(\tilde{r})=\sum_{n'\ne n}\left(\frac{M}{2}S_{\mathrm{EA}}(\tilde{y}_n,\tilde{y}_{n'})+\frac{M}{2}(K_n+K_{n'}-M)-K_nK_{n'}\right), U n ( r ~ ) = n ′ = n ∑ ( 2 M S EA ( y ~ n , y ~ n ′ ) + 2 M ( K n + K n ′ − M ) − K n K n ′ ) , which proves the claim.
Additional Discussion of Assumptions and Related Work
In this section, we discuss our model assumptions and connect to the literature. First, we compare the Bayesian Stochastically Order Consistent (SOC) assumption with Strong Stochastic Transitivity (SST) and include a necessity observation for SOC. We then connect our framework to the probabilistic social choice literature through order independence, a relaxed form of independence of irrelevant alternatives.
Additional relation to prior work Compared to multi-task peer prediction mechanisms for categorical reports operating in discrete signal spaces, our model handles continuous underlying signals (real-valued quality scores) from which agents derive ordinal reports. This continuous setting, combined with the ordered structure of rankings, requires different analytical techniques: our proof exploits state-swap symmetry, elementary symmetric polynomial comparisons, and stochastic consistency properties rather than discrete signal correlation structures.
Our framework also bridges peer prediction and property elicitation [16 ] . By defining a target function that projects complex signal spaces onto structural ordinal reports (e.g., full rankings, top-sets), we may view our mechanism as a scoring rule for the ordinal shape of a belief distribution.
SOC and Strong Stochastic Transitivity To formalize this comparison, we say a conditional probability P : Θ M → Δ ( X M ) P : \Theta^{M} \to\Delta(\mathcal{X}^{M}) P : Θ M → Δ ( X M ) satisfies Strong Stochastic Transitivity (SST) if for all i , j , k ∈ [ M ] i,j,k \in[M] i , j , k ∈ [ M ] such that Pr [ x i < x j ∣ θ ] > 1 / 2 \Pr[x_i < x_j \mid\theta] > 1/2 Pr [ x i < x j ∣ θ ] > 1/2 and Pr [ x j < x k ∣ θ ] > 1 / 2 \Pr[x_j < x_k \mid\theta] > 1/2 Pr [ x j < x k ∣ θ ] > 1/2 , the following holds:
Pr [ x i < x k ∣ θ ] ≥ max { Pr [ x i < x j ∣ θ ] , Pr [ x j < x k ∣ θ ] } . \Pr[x_i < x_k \mid\theta] \ge\max\{\Pr[x_i < x_j \mid\theta],\Pr[x_j < x_k \mid\theta]\}. Pr [ x i < x k ∣ θ ] ≥ max { Pr [ x i < x j ∣ θ ] , Pr [ x j < x k ∣ θ ]} .
When SOC and SST are viewed as conditions on the same full-signal distribution, SOC is stronger than SST: SOC imposes pointwise swap inequalities on full signal vectors, while SST is a pairwise condition on comparison probabilities. However, the Bayesian SOC framework and the BPP/SST framework are not directly nested as modeling frameworks. Our framework allows heterogeneous agents and richer ordinal reports such as full rankings and top sets, while the BPP mechanism of Chen et al. [3 ] is designed for homogeneous pairwise-comparison assignments. Conversely, SST does not imply SOC, because a pairwise condition need not control the likelihood of each full signal vector under item swaps.
In addition to the examples in § 2.1 , the standard random binary noise model also satisfies Bayesian SOC, though it is not strict.
Example G.1 (Binary Noise Model). Let Θ = X = { 0 , 1 } \Theta= \mathcal{X} = \{0,1\} Θ = X = { 0 , 1 } . Here, the state vector θ ∈ { 0 , 1 } M \theta\in\{0,1\}^{M} θ ∈ { 0 , 1 } M contains the true costs or qualities of the M M M items, drawn i.i.d. Each agent n n n observes, for each item i i i , a noisy signal:
x n , i = { θ i with probability 2 / 3 1 − θ i otherwise x_{n,i} =
\begin{cases}
\theta_i & \text{with probability } 2/3 \\
1-\theta_i & \text{otherwise}
\end{cases} x n , i = { θ i 1 − θ i with probability 2/3 otherwise The following example illustrates only that SST does not imply SOC.
Example G.2 (RIUM with Cauchy Noise). Consider θ , x ∈ R 2 \theta,x \in\mathbb{R}^{2} θ , x ∈ R 2 in a RIUM with Cauchy noise ϵ ∼ Cauchy ( 0 , 1 ) \epsilon\sim\operatorname{Cauchy}(0,1) ϵ ∼ Cauchy ( 0 , 1 ) , where the PDF is f ( ϵ ) ∝ 1 1 + ϵ 2 f(\epsilon) \propto\frac{1}{1+\epsilon^{2}} f ( ϵ ) ∝ 1 + ϵ 2 1 . We compare the density of the signal x x x (which is consistent with θ \theta θ since x 1 < x 2 x_1 < x_2 x 1 < x 2 given θ 1 < θ 2 \theta_1 < \theta_2 θ 1 < θ 2 ) against the swapped signal x ′ = ( − 4 , − 5 ) x' = (-4,-5) x ′ = ( − 4 , − 5 ) :
f x ∣ θ ( ( − 5 , − 4 ) ∣ ( 0 , 2 ) ) f x ∣ θ ( ( − 4 , − 5 ) ∣ ( 0 , 2 ) ) = ( 1 + ( − 4 ) 2 ) ( 1 + ( − 7 ) 2 ) ( 1 + ( − 5 ) 2 ) ( 1 + ( − 6 ) 2 ) = ( 17 ) ( 50 ) ( 26 ) ( 37 ) = 850 962 < 1. \frac{f_{x\mid\theta}((-5,-4)\mid(0,2))}{f_{x\mid\theta}((-4,-5)\mid(0,2))}
= \frac{(1+(-4)^2)(1+(-7)^2)}{(1+(-5)^2)(1+(-6)^2)}
= \frac{(17)(50)}{(26)(37)}
= \frac{850}{962} < 1. f x ∣ θ (( − 4 , − 5 ) ∣ ( 0 , 2 )) f x ∣ θ (( − 5 , − 4 ) ∣ ( 0 , 2 )) = ( 1 + ( − 5 ) 2 ) ( 1 + ( − 6 ) 2 ) ( 1 + ( − 4 ) 2 ) ( 1 + ( − 7 ) 2 ) = ( 26 ) ( 37 ) ( 17 ) ( 50 ) = 962 850 < 1. Since the consistent signal is less likely than the inconsistent one, the model violates SOC. However, the model satisfies SST by [3 ] .
Necessity of SOC. The SOC assumption is not only a technical condition for our proof. To illustrate this, fix an item-neutrality peer-only scoring rule u ( r , s ) u(r,s) u ( r , s ) that does not depend on the underlying information structure, where r r r is the agent’s report and s s s is the peer’s report. For a comparison between a signal ranking x x x and its swapped version σ ( x ) \sigma(x) σ ( x ) , call the rule correctly oriented if, when the peer is perfectly informative and reports the order consistent with x x x , the rule weakly prefers reporting x x x to reporting σ ( x ) \sigma(x) σ ( x ) . We call it non-degenerate if this preference is strict.
Proposition G.3 (Necessity of SOC). If an SOC swap inequality fails, then there is an elicitation instance in which every fixed non-degenerate correctly oriented peer-only scoring rule fails to make truthful reporting a Bayes–Nash equilibrium.
Proof. Suppose SOC fails for some number of items M M M , state θ \theta θ , signal ranking x x x , and transposition σ = σ i j \sigma=\sigma_{ij} σ = σ ij , with x x x order-consistent with θ \theta θ on ( i , j ) (i,j) ( i , j ) :
P ( x ∣ θ ) < P ( σ ( x ) ∣ θ ) . P(x\mid\theta)<P(\sigma(x)\mid\theta). P ( x ∣ θ ) < P ( σ ( x ) ∣ θ ) .
Consider an instance whose prior is supported uniformly on the two states θ \theta θ and σ ( θ ) \sigma(\theta) σ ( θ ) . Let the peer be perfectly informative about the state and report the order induced by that state. By item-neutrality of the signal channel,
P ( x ∣ σ ( θ ) ) = P ( σ ( x ) ∣ θ ) . P(x\mid\sigma(\theta))=P(\sigma(x)\mid\theta). P ( x ∣ σ ( θ )) = P ( σ ( x ) ∣ θ ) .
Thus, after observing x x x ,
Pr [ θ ∣ x ] < Pr [ σ ( θ ) ∣ x ] . \Pr[\theta\mid x]<\Pr[\sigma(\theta)\mid x]. Pr [ θ ∣ x ] < Pr [ σ ( θ ) ∣ x ] .
The agent therefore believes that a truthful peer is more likely to report the swapped order σ ( θ ) \sigma(\theta) σ ( θ ) than the order θ \theta θ .
For brevity, identify θ \theta θ and σ ( θ ) \sigma(\theta) σ ( θ ) with the peer reports induced by those states. Define
A = u ( x , θ ) = u ( σ ( x ) , σ ( θ ) ) , B = u ( σ ( x ) , θ ) = u ( x , σ ( θ ) ) , A=u(x,\theta)=u(\sigma(x),\sigma(\theta)),\qquad B=u(\sigma(x),\theta)=u(x,\sigma(\theta)), A = u ( x , θ ) = u ( σ ( x ) , σ ( θ )) , B = u ( σ ( x ) , θ ) = u ( x , σ ( θ )) ,
where the equalities follow from item-neutrality of the scoring rule. Correct orientation and non-degeneracy give A > B A>B A > B . Writing π = Pr [ θ ∣ x ] \pi=\Pr[\theta\mid x] π = Pr [ θ ∣ x ] , the expected-payoff gain from reporting x x x rather than σ ( x ) \sigma(x) σ ( x ) is
π A + ( 1 − π ) B − ( π B + ( 1 − π ) A ) = ( 2 π − 1 ) ( A − B ) < 0. \pi A+(1-\pi)B-\bigl(\pi B+(1-\pi)A\bigr)=(2\pi-1)(A-B)<0. π A + ( 1 − π ) B − ( π B + ( 1 − π ) A ) = ( 2 π − 1 ) ( A − B ) < 0.
Thus the agent strictly prefers the swapped report to the truthful report. Truthful reporting is therefore not a Bayes–Nash equilibrium in this instance. □ \square □
SOC and Order Independence. The SOC property also connects to order independence in probabilistic social choice, which is a relaxed form of independence of irrelevant alternatives [28 ] . Specifically, a choice function specifies the probability of selecting an item from a given set. Formally, let F ( i , A ) = Pr [ choose i ∣ A ] F(i,A)=\Pr[\text{choose }i\mid A] F ( i , A ) = Pr [ choose i ∣ A ] . A choice function F F F is order independent if for all disjoint subsets A , B ⊂ [ M ] A,B\subset[M] A , B ⊂ [ M ] and items i , j ∈ A i,j\in A i , j ∈ A and k ∈ B k\in B k ∈ B :
F ( i , A ) > F ( j , A ) ⟺ F ( k , B ∪ { i } ) < F ( k , B ∪ { j } ) . F(i,A)>F(j,A)\Longleftrightarrow F(k,B\cup\{i\})<F(k,B\cup\{j\}). F ( i , A ) > F ( j , A ) ⟺ F ( k , B ∪ { i }) < F ( k , B ∪ { j }) .
Given a conditional probability P : Θ M → Δ ( X M ) P:\Theta^M\to\Delta(\mathcal{X}^M) P : Θ M → Δ ( X M ) , we define the induced choice function F P F_P F P such that F P ( i , A ) = Pr [ x i < min j ∈ A ∖ { i } x j ∣ θ ] F_P(i,A)=\Pr[x_i<\min_{j\in A\setminus\{i\}}x_j\mid\theta] F P ( i , A ) = Pr [ x i < min j ∈ A ∖ { i } x j ∣ θ ] which outputs the top item based on the noisy signals. We use the convention min ∅ = + ∞ \min\varnothing=+\infty min ∅ = + ∞ .
Proposition G.4. If P P P is SOC, then the induced choice function F P F_P F P is order independent.
Proof. We know F P ( i , A ) > F P ( j , A ) F_P(i,A)>F_P(j,A) F P ( i , A ) > F P ( j , A ) if and only if θ i < θ j \theta_i<\theta_j θ i < θ j . Otherwise, if θ i > θ j \theta_i>\theta_j θ i > θ j , by Definition 2.2
F P ( i , A ) − F P ( j , A ) = Pr [ x i < min k ∈ A ∖ { i } x k ∣ θ ] − Pr [ x j < min k ∈ A ∖ { j } x k ∣ θ ] = ∑ x : x i < min k ∈ A ∖ { i } x k Pr [ x ∣ θ ] − ∑ x : x i < min k ∈ A ∖ { i } x k Pr [ σ i , j ( x ) ∣ θ ] = ∑ x : x i < min k ∈ A ∖ { i } x k ( Pr [ x ∣ θ ] − Pr [ σ i , j ( x ) ∣ θ ] ) < 0 \begin{aligned}
F_P(i,A)-F_P(j,A)=\Pr\left[x_i<\min_{k\in A\setminus\{i\}}x_k\mid\theta\right]-\Pr\left[x_j<\min_{k\in A\setminus\{j\}}x_k\mid\theta\right] \\
&=\sum_{x:x_i<\min_{k\in A\setminus\{i\}}x_k}\Pr[x\mid\theta]-\sum_{x:x_i<\min_{k\in A\setminus\{i\}}x_k}\Pr[\sigma_{i,j}(x)\mid\theta] \\
&=\sum_{x:x_i<\min_{k\in A\setminus\{i\}}x_k}\left(\Pr[x\mid\theta]-\Pr[\sigma_{i,j}(x)\mid\theta]\right)<0
\end{aligned} F P ( i , A ) − F P ( j , A ) = Pr [ x i < k ∈ A ∖ { i } min x k ∣ θ ] − Pr [ x j < k ∈ A ∖ { j } min x k ∣ θ ] = x : x i < m i n k ∈ A ∖ { i } x k ∑ Pr [ x ∣ θ ] − x : x i < m i n k ∈ A ∖ { i } x k ∑ Pr [ σ i , j ( x ) ∣ θ ] = x : x i < m i n k ∈ A ∖ { i } x k ∑ ( Pr [ x ∣ θ ] − Pr [ σ i , j ( x ) ∣ θ ] ) < 0
which is a contradiction. The opposite direction is similar.
Finally, given θ i < θ j \theta_i<\theta_j θ i < θ j , we have
F P ( k , B ∪ { i } ) − F P ( k , B ∪ { j } ) = ∑ x : x k < min { min ℓ ∈ B ∖ { k } x ℓ , x i } Pr [ x ∣ θ ] − ∑ x : x k < min { min ℓ ∈ B ∖ { k } x ℓ , x j } Pr [ x ∣ θ ] . \begin{aligned}
F_P(k,B\cup\{i\})-F_P(k,B\cup\{j\}) \\
&=\sum_{x:x_k<\min\{\min_{\ell\in B\setminus\{k\}}x_\ell,x_i\}}\Pr[x\mid\theta]
-\sum_{x:x_k<\min\{\min_{\ell\in B\setminus\{k\}}x_\ell,x_j\}}\Pr[x\mid\theta].
\end{aligned} F P ( k , B ∪ { i }) − F P ( k , B ∪ { j }) = x : x k < m i n { m i n ℓ ∈ B ∖ { k } x ℓ , x i } ∑ Pr [ x ∣ θ ] − x : x k < m i n { m i n ℓ ∈ B ∖ { k } x ℓ , x j } ∑ Pr [ x ∣ θ ] .
Terms with x k < x i x_k<x_i x k < x i and x k < x j x_k<x_j x k < x j cancel out. The remaining terms are those where x k x_k x k is smaller than one of { x i , x j } \{x_i,x_j\} { x i , x j } but larger than the other. Thus, the difference reduces to:
∑ x : x j ≤ x k < min { min ℓ ∈ B ∖ { k } x ℓ , x i } Pr [ x ∣ θ ] − ∑ x : x i ≤ x k < min { min ℓ ∈ B ∖ { k } x ℓ , x j } Pr [ x ∣ θ ] < 0 \sum_{x:x_j\le x_k<\min\{\min_{\ell\in B\setminus\{k\}}x_\ell,x_i\}}\Pr[x\mid\theta]
-\sum_{x:x_i\le x_k<\min\{\min_{\ell\in B\setminus\{k\}}x_\ell,x_j\}}\Pr[x\mid\theta]<0 x : x j ≤ x k < m i n { m i n ℓ ∈ B ∖ { k } x ℓ , x i } ∑ Pr [ x ∣ θ ] − x : x i ≤ x k < m i n { m i n ℓ ∈ B ∖ { k } x ℓ , x j } ∑ Pr [ x ∣ θ ] < 0
by stochastic order transitivity.
Additional Experimental Results
Structured unilateral deviations We reuse the payment-distribution protocol of Section 5.1 but replace the single uniform-random deviation with a family of structured deviations. This tests the score against near-truthful and coordination-style reports rather than only against a uniformly random report. In each trial, we draw the truthful profile as in Section 5.1, or the observed-report profile for SUSHI. For a focal agent n n n , peers keep their truthful reports, or their observed reports for SUSHI, while agent n n n ’s report is replaced by one of four deviations:
uniform , a uniformly random permutation, matching the unilateral deviation in Section 5.1;
partial shuffle , the truthful or observed ranking perturbed by ⌊ M / 2 ⌋ \lfloor M/2\rfloor ⌊ M /2 ⌋ random adjacent transpositions;
constant , a fixed exogenous reference ranking reported regardless of the private signal, capturing a coordination-style report; and
reverse , the exact reversal of the truthful or observed ranking.
Figure 3. Structured unilateral deviations. Peers report truthfully, or by observed rankings for SUSHI, while the focal agent reports a uniform random permutation, a partially shuffled ranking, a constant ranking, or the reverse ranking.
Aggregating the focal agent’s Kendall tau payment over all focal agents and trials yields one empirical payment distribution per deviation. As before, lower ECDFs correspond to more favorable payment distributions.
In the synthetic Thurstone and Mallows models (Figure 3a and Figure 3b ), truthful reporting remains right-shifted relative to these structured deviations, with the partial-shuffle deviation closest to truthful reporting and the reverse report performing worst. On SUSHI (Figure 3c ), the observed-report distribution is also generally the most favorable: although exact pointwise dominance need not hold at every threshold in this real-data stress test, the observed-report ECDF lies below or to the right of the structured-deviation curves over most of the payment range.