Carrot and Stick: Eliciting Comparison Data and Beyond

Authors: yiling  chen
shi  feng
yi  yu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 17:58:59

Abstract: Comparison data elicited from people are fundamental to many machine learning tasks, including reinforcement learning from human feedback for large language models and estimating ranking models. They are typically subjective and not directly verifiable. How to truthfully elicit such comparison data from rational individuals? We design peer prediction mechanisms for eliciting comparison data using a bonus-penalty payment. Our design leverages on the strong stochastic transitivity for comparison data to create symmetrically strongly truthful mechanisms such that truth-telling 1) forms a strict Bayesian Nash equilibrium, and 2) yields the highest payment among all symmetric equilibria. Each individual only needs to evaluate one pair of items and report her comparison in our mechanism.

We further extend the bonus-penalty payment concept to eliciting networked data, designing a symmetrically strongly truthful mechanism when agents’ private signals are sampled according to the Ising models. We provide the necessary and sufficient conditions for our bonus-penalty payment to have truth-telling as a strict Bayesian Nash equilibrium. Experiments on two real-world datasets further support our theoretical discoveries.

Main paper: 
 introduction: 
 In the past two decades, researchers have been embracing the challenge of eliciting private information from individuals when there is no ground truth available to evaluate the quality of elicited contributions, and have made amazing progress. Many mechanisms, collectively called peer prediction [42] , have been developed to incentivize individuals to strictly truthfully report their information at a Bayesian Nash equilibrium (BNE), by artful design of payment functions that only depend on reports from individuals. Moreover, in multi-task peer prediction mechanisms, the truthful BNE gives each individual the highest expected payoff among all BNEs (i.e. it's a strongly truthful BNE). [11, 57, 30] However, all prior multi-task peer prediction mechanisms require tasks being ex-ante identical, and hence individuals' private information is independently and identically distributed (iid) for each task. Multi-task peer prediction leverages this structure of information to succeed at truthful elicitation. But what if such structure of information doesn't hold for an information elicitation problem? One notable application is to elicit pair-wise comparisons of multiple alternatives, such as preferences for consumer products [53] , translation [34] , peer grading [55] , and relevance of language model outputs [9, 10] . Such pair-wise comparison data are crucial for estimating a ranking of the alternatives and for devising reward functions for reinforcement learning. Comparison tasks for different pairs are clearly not ex-ante identical -answers to the tasks demonstrate a certain degree of transitivity (e.g. if 𝑎 is preferred to 𝑎 ′ and 𝑎 ′ is preferred to 𝑎 ′′ , then it's more likely that 𝑎 is preferred to 𝑎 ′′ ), rendering existing peer prediction mechanisms not applicable.In this paper, we design a peer prediction mechanism for eliciting comparison data. We model individuals' private information of pair-wise comparisons as Bayesian strongly stochastically transitive (Bayesian SST), which takes many widely used models (e.g. Thurstone [58] , Bradley-Terry-Luce [4, 38] , and Mallows [39] ) as special cases. Our mechanism uses a simple bonus-penalty payment [11] (hence carrot and stick) that takes three reports as inputs and admits a strongly truthful symmetric BNE. The key insight that we develop is a condition of information structure that we call uniform dominance. When uniform dominance is satisfied, the bonus-penalty payment is the only type of payment that induces a strictly truthful BNE. Information of individuals, 𝑖, 𝑗, and 𝑘, satisfies uniform dominance if, conditioned on any realization of agent 𝑖's information, the probability for 𝑗's information to agree with 𝑖's is higher than the probability for 𝑘's information to agree with 𝑖's. Bayesian SST allows us to group three pairwise comparisons, (𝑎, 𝑎 ′ ), (𝑎 ′′ , 𝑎 ′ ) and (𝑎 ′′ , 𝑎), together such that private information about these pairs satisfies uniform dominance. After identifying uniform dominance as a central structure for incentivizing truthful elicitation, we further generalize the bonus-penalty payment to truthfully elicit private information over social networks that demonstrate homophily (i.e. friends tend to have similar opinions than non-friends) [40] , and our mechanism can be integrated with common survey techniques such as snowball sampling [24] .Our contributions. Our work is a leap forward for designing mechanisms for complex information elicitation settings where ground truth verification is not available.• We are the first to design mechanisms to truthfully elicit pairwise comparison data under Bayesian SST and networked data under Ising models. In our mechanisms, truthful reporting forms a BNE and yields a strictly higher payoff than any symmetric non-permutation equilibrium. • We identify a key structure of information, uniform dominance, as a lever such that the simple bonus-penalty payment is the unique payment inducing a strictly truthful BNE. This identification may offer a path for developing truthful elicitation mechanisms for other settings in the future. • We use Griffiths' inequality and Weitz's self-avoiding walk [65] to prove the uniform dominance property in the Ising model. The resulting correlation bounds may be of independent interest. • We test our mechanisms on real-world data (sushi preference dataset [26, 27] and Last.fm dataset [8] ). Even though these datasets do not perfectly satisfy our theoretical assumptions, our mechanisms still provide a stronger incentive for truthful reporting compared to misreporting.Related work. Information elicitation has two settings according to whether verification is possible.Our paper focuses on elicitation without verification.For information elicitation without verification, Miller et al. [41] introduce the first mechanism for single task signal elicitation that has truth-telling as a strict Bayesian Nash equilibrium but requires full knowledge of the common prior. Bayesian truth serum (BTS) [47] is the first strongly truthful peer prediction mechanism, but requires complicated reports from agents (their private signal and predictions on other's reports). A series of works [48, 49, 67, 66, 68, 3, 51, 31] relax certain assumptions of BTS but still require complicated reports from agents. Dasgupta and Ghosh [11] introduces the multi-task setting where agents are assigned batch iid tasks and only report their signals. Several works extend this to multiple-choice questions [29, 33, 56, 11] , predictions [37] , or even continuous value [50] , and investigate the limitation and robustness [52, 6, 70, 17, 70] . Another related line of work is co-training and federated learning, which wants to elicit models [32, 36] , or samples [64] when multiple iid data or feature of data are available. For more related works, see Faltings [16] .One popular line of work considers information elicitation when verification is possible. Spotchecking requires direct verification of the agent's report [21] . Recent work on comparison data elicitation [19] utilizes spot-checking concepts and focuses on incentivizing effort. Another form of verification involves using additional samples to evaluate how the agent's reports improve model performance [1, 28] . Additionally, the verification may have a general relation to the agent's signal, e.g., proper scoring rules [23, 46, 35, 20] . 
problem formulation: 
 We discuss our model for eliciting comparison data in this section and defer the extensions to Section 5. Given a collection of items A and a set of strategic agents N . Agents privately observeExamples of Bayesian SST models. Bayesian SST models are a general family of models that take many classical parametric ranking models, including Bradley-Terry Luce [4, 38] , Thurstone (Case V) [58] , and Mallows 𝜂-model [39] , as special cases.Example 2.2 (Bradley-Terry-Luce, Thurstone model, and more [59] ). Let 𝜃 ∈ R A = Θ where each coordinate is independently and identically sampled from a fixed non-atomic distribution 𝜈 on R, and each item 𝑎 have a scalar quality 𝜃 𝑎 ∈ R. Let 𝐹 : R → [0, 1] be any strictly increasing function such that 𝐹 (𝑡) = 1 -𝐹 (-𝑡) for all 𝑡 ∈ R. Conditional on a fixed 𝜃,Pr[𝑇 𝜃 (𝑎, 𝑎 ′ ) = 1] = 𝐹 (𝜃 𝑎 -𝜃 𝑎 ′ ) for all 𝑎, 𝑎 ′ ∈ A.This model recovers the Thurstone model [58] by setting 𝐹 (𝑡) = Φ(𝑡) where Φ is the Gaussian CDF, and the Bradley-Terry-Luce model [4] by setting 𝐹 (𝑡) = 𝑒 𝑡 1+𝑒 𝑡 , the sigmoid function. Moreover, this model also contains any additive random utility model [2] where 𝑇 (𝑎, 𝑎 ′ ) = 1 if 𝜃 𝑎 + 𝑍 > 𝜃 𝑎 ′ + 𝑍 ′ with iid noise 𝑍 and 𝑍 ′ , because we can set 𝐹 to be the CDF of the difference of two iid noise. Proposition 2.3. For any strictly increasing 𝐹 and non-atomic 𝜈 on R, the parametric model in Example 2.2 is a Bayesian SST model. Example 2.4 (Mallows 𝜂-model [39] ). Let Θ be the set of rankings on A and 𝜂 > 0 be a dispersion parameter. Given a reference ranking 𝜃 ∈ Θ, the Mallows 𝜂-model generate a ranking 𝜙 ∈ Θ with probability Pr(𝜙) ∝ exp(-𝜂𝑑 (𝜃, 𝜙)) where 𝑑 (𝜃, 𝜙) = {(𝑎, 𝑎 ′ ) ∈ A 2 : 𝜃 (𝑎) < 𝜃 (𝑎 ′ ) and 𝜙(𝑎) > 𝜙(𝑎 ′ )} is Kendall's tau distance, and 𝜃 (𝑎) is the rank of item 𝑎. Therefore, to generate comparisons, we first sample a uniform 𝜃 andPr[𝑇 𝜃 (𝑎, 𝑎 ′ ) = 1] = ∑︁ 𝜙:𝜙 (𝑎) > 𝜙 (𝑎 ′ )Pr(𝜙), for all 𝑎, 𝑎 ′ ∈ A.Proposition 2.5. For any 𝜂 > 0, Mallows 𝜂-model in Example 2.4 with uniform distribution on reference ranking is an Bayesian SST model.The proofs for propositions 2.3 and 2.5 are closely related to strong stochastic transitivity [54, 7] , but are provided in the appendix for completeness.To truthfully elicit comparison data from agents, a peer prediction mechanism creates a game between the agents outlined below: First, we choose an assignment E = {𝑒 𝑖 = (𝑎 𝑢 𝑖 , 𝑎 We introduce three families of strategies, truth-telling, permutation, and uninformed strategy profiles, which are central to understanding effective peer prediction mechanisms.• A strategy 𝜎 𝑖 is truthful (or truth-telling) if it is a deterministic identity map, 𝜎 𝑖 (𝑠 𝑖 ) = 𝑠 𝑖 . A strategy profile is truthful if all agents' strategies are truthful. • A permutation strategy profile is where agents simultaneously relabel their signals and then report the relabeled ones. A permutation strategy is indistinguishable from truth-telling unless the peer prediction mechanism has additional knowledge about the prior signal distribution. [33] • Finally, a strategy is uninformed if it has the same report distribution across all signals, and it is informed otherwise. Common examples include consistently reporting all signals as a constant value, such as 1 or -1, or using a random report regardless of the signal. Uninformed strategies are undesirable as the reports bear no relationship to the private signals.A strategy profile is symmetric if all agents use the same strategy. For example, both truth-telling and permutation strategy profiles are symmetric.We now introduce goals for a peer prediction mechanism that favors truth-telling more than other strategies. First, we want the truth-telling (strategy profile) to be a strict Bayesian Nash equilibrium (BNE) so that any agent's payment would strictly decrease if she unilaterally changes to any nontruthful strategy. Moreover, there may be multiple equilibria, and a desirable mechanism should ensure that truth-telling is better than all other equilibria. In this paper, we aim for symmetrically strongly truthful mechanisms defined below. Definition 2.6. A peer prediction mechanism is symmetrically strongly truthful if truth-telling is a BNE, and each agent's expected payment in truth-telling is no less than the payment in any other symmetric equilibrium with equality for the equilibrium with a permutation strategy profile. 1 
bonus-penalty payment mechanism for comparison data: 
 We now propose a bonus-penalty payment mechanism for eliciting comparison data. The mechanism makes use of a bonus-penalty payment function, which can be seen as an agreement payment and introduced by Dasgupta and Ghosh [11] in a different context (see discussion in appendix A). Formally, for any ŝ𝑖 , ŝ 𝑗 , ŝ𝑘 ∈ {-1, 1}, the bonus-penalty payment function isEQUATIONwhich rewards when the first input agrees with the second but punishes when it agrees with the third.Mechanism 1 uses the bonus-penalty payment eq. ( 1) for each agent 𝑖 by carefully choosing agent 𝑗 and 𝑘 such that agent 𝑗's signal is more likely to agree with agent 𝑖's than agent 𝑘's signal is. The crux of finding such pair of agents is to show that if agent 𝑖 prefers item 𝑎 over 𝑎 ′ , she would expect that others will prefer any third item 𝑎 ′′ over 𝑎 ′ , and prefer 𝑎 over 𝑎 ′′ . Thus, if agent 𝑗 has pair (𝑎 ′′ , 𝑎 ′ ) and agent 𝑘 has pair (𝑎 ′′ , 𝑎), then agent 𝑗's signal is more likely to take the same value as 𝑖's than agent 𝑘's signal is. This is the main idea behind the proof of Theorem 3.1, where we establish the symmetrically strongly truthfulness of Mechanism 1. To ensure the existence of such pairs are assigned, we require the assignment E to be admissible where for all (𝑎, 𝑎 ′ ) ∈ E, there exists 𝑎 ′′ ∈ A so that (𝑎 ′′ , 𝑎 ′ ) and (𝑎 ′′ , 𝑎) ∈ E. We defer the proof of theorem 3.1 to section 4. The admissible condition imposes little overhead on downstream learning problems, including rank recovery [25] and identification of the top 𝑘 items [15] . Specifically, the size of assignment E is the number of comparisons and corresponds to the sample complexity for these learning problems. If a learning algorithm requires a set of pairs to compare E 𝑀 𝐿 , we can construct an admissible superset E that introduces a constant factor overhead and can recover E 𝑀 𝐿 ⊆ E. 2We remark that the bonus-penalty payment function eq. ( 2) can be seen as a boolean function for transitivity [45] ; see remark 3.2 for a formal statement. Hence, theorem 3.1 implies that agents' manipulations can only decrease the probability of transitivity among their reports.Remark 3.2. Note that a deterministic comparison function 𝑡 : A × A → {-1, 1} satisfies transitivity on three items 𝑎, 𝑎 ′ , 𝑎 ′′ ∈ A if and only if 𝑡 (𝑎, 𝑎 ′ ), 𝑡 (𝑎 ′ , 𝑎 ′′ ), 𝑡 (𝑎 ′′ , 𝑎) are not all equal, that is 𝑁 𝐴𝐸 (𝑡 (𝑎, 𝑎 ′ ), 𝑡 (𝑎 ′ , 𝑎 ′′ ), 𝑡 (𝑎 ′′ , 𝑎)) = 1 where𝑁 𝐴𝐸 (𝑤 1 , 𝑤 2 , 𝑤 3 ) = 3 4 - 1 4 𝑤 1 𝑤 2 - 1 4 𝑤 1 𝑤 3 - 1 4 𝑤 2 𝑤 3 .The agent's random noisy comparisons may or may not satisfy transitivity. The probability of transitivity is the probability that they do.We can show that the bonus-penalty payment in eq. ( 2) is equivalent to the above transitivity test when agents are truth-telling. Formally, 𝑁 𝐴𝐸 (𝑆(𝑎, 𝑎 ′ ), 𝑆(𝑎 ′ , 𝑎 ′′ ), 𝑆(𝑎 ′′ , 𝑎)) EQUATION= 1 | 𝑆 𝑖 = 1] > Pr[𝑆 𝑘 = 1 | 𝑆 𝑖 = 1] and Pr[𝑆 𝑗 = -1 | 𝑆 𝑖 = -1] > Pr[𝑆 𝑘 = -1 | 𝑆 𝑖 = -1]. We call such an ordered tuple ⟨𝑆 𝑖 , 𝑆 𝑗 , 𝑆 𝑘 ⟩ a uniformly dominant tuple. 3Lemma 4.2 shows how to identify uniformly dominant tuples under Bayesian SST models. Lemma 4.2. Under any Bayesian SST model, for any agent 𝑖 and items 𝑎, 𝑎 ′ and 𝑎 ′′ , agent 𝑗's signal 𝑆 𝑗 = 𝑆(𝑎 ′′ , 𝑎 ′ ) uniformly dominates agent 𝑘's signal 𝑆 𝑘 = 𝑆(𝑎 ′′ , 𝑎) for signal 𝑆 𝑖 = 𝑆(𝑎, 𝑎 ′ ).In other words, under any Bayesian SST model, the distribution of 𝑆(𝑎, 𝑎 ′ ), 𝑆(𝑎 ′′ , 𝑎 ′ ), 𝑆(𝑎 ′′ , 𝑎) satisfies uniform dominance for any 𝑎, 𝑎 ′ , 𝑎 ′′ . In the rest of this section, we can view (𝑆 𝑖 , 𝑆 𝑗 , 𝑆 𝑘 ) as an abstract random vector with some joint distribution 𝑃.We now establish some implications of uniform dominance on the bonus-penalty payment. Lemma 4.3 shows that truth-telling is the best response if other signals are reported truthfully. Lemma 4.4 states that the expected payment is zero if everyone uses uninformed strategies (random functions independent of input). Lemma 4.5 characterizes the best response under symmetric strategy profiles (the same random function on each coordinate). We'd like to highlight that lemmas 4.3 to 4.5 as well as the proof of theorem 3.1 below hold for any uniformly dominant tuple ⟨𝑆 𝑖 , 𝑆 𝑗 , 𝑆 𝑘 ⟩, not necessarily derived from the Bayesian SST model. This offers a path to generalize our mechanism for comparison data to other settings.𝑠 𝑖 ∈ {-1, 1}, 𝑠 𝑖 = arg max ŝ𝑖 ∈ { -1,1} E 𝑃 𝑈 𝐵𝑃𝑃 ( ŝ𝑖 , 𝑆 𝑗 , 𝑆 𝑘 ) | 𝑆 𝑖 = 𝑠 𝑖 and E 𝑃 𝑈 𝐵𝑃𝑃 (𝑆 𝑖 , 𝑆 𝑗 , 𝑆 𝑘 ) > 0.Proof of theorem 3.1. By lemma 4.2, for any agent 𝑖, the associated agent 𝑗's signal 𝑆 𝑗 = 𝑆(𝑎 ′′ , 𝑎 ′ ) uniformly dominates the associated 𝑘's signal 𝑆 𝑘 = 𝑆(𝑎 ′′ , 𝑎) for signal 𝑆 𝑖 = 𝑆(𝑎, 𝑎 ′ ). By lemma 4.3, if agent 𝑗 and 𝑘 are truthful, agent 𝑖's best response is truthful reporting, so truth-telling is a BNE. Now we show that all other symmetric equilibria are permutation or uninformed equilibria. For any symmetric equilibrium 𝝈 = (𝜎 𝜄 ) 𝜄∈ N so that everyone uses the same strategy 𝜎 𝜄 = 𝜎 for all 𝜄 ∈ N . If 𝜎 is not deterministic so that 𝜎(𝑠, 𝑠), 𝜎(𝑠, -𝑠) > 0 for some 𝑠 ∈ {-1, 1}, agent 𝑖 must be indifferent between reporting 𝑠 and -𝑠 when getting 𝑆 𝑖 = 𝑠. 𝜎(𝑠, 𝑠) -𝜎(-𝑠, 𝑠) = 𝜎(𝑠, -𝑠) -𝜎(-𝑠, -𝑠) by lemma 4.5. This means 𝜎(𝑠, 𝑠) = 𝜎(-𝑠, 𝑠) and 𝜎(𝑠, -𝑠) = 𝜎(-𝑠, -𝑠), and 𝜎 is an uninformed strategy. If the strategy is deterministic, there are two cases. If 𝜎(𝑠) = 𝜎(-𝑠), the strategy is also uninformed. If 𝜎(𝑠) ≠ 𝜎(-𝑠), 𝜎 is either truth-telling 𝑠 ↦ → 𝑠 or flipping 𝑠 ↦ → -𝑠 for all 𝑠.Finally, by lemma 4.4, any uninformed equilibrium's expectation is zero. Additionally, because eq. ( 1) is invariant when all inputs are flipped, the truth-telling and flipping/permutation equilibria has the same expected payment which is positive by lemma 4.3. □ 
generalization of bonus-penalty payment mechanisms: 
 We now leverage the key idea of uniform dominance to design peer prediction mechanisms for networked data in section 5.1. In section 5.2, we summarize our design approach as a general scheme that first identifies uniform dominance structures and then engages the bonus-penalty payment. We prove the uniqueness of bonus-penalty payment: it is the only payment function, up to some positive affine transformation, that induces truth-telling as a strict BNE for all uniform dominant tuples.Uniform dominance implies agent 𝑖's signal is more likely to agree with agent 𝑗's than with agent 𝑘's. Social networks are another natural domain exhibiting this property, as homophily [40] suggests that agents' opinions or signals in a social network are more likely to agree with their friends than with non-friends. Leveraging this insight, we use a bonus-penalty payment scheme to elicit binary networked data.Mechanism 2: BPP mechanism for networked data Input: Let (𝑉, 𝐸) be a graph of agents in 𝑉, ŝ ∈ {-1, 1} 𝑉 from all agent's reports.for agent 𝑖 ∈ 𝑉 do Find agents 𝑗 (friend) and 𝑘 (non-friend) so that (𝑖, 𝑗) ∈ 𝐸 but (𝑖, 𝑘) ∉ 𝐸, and pay agent 𝑖EQUATIONBelow, we provide a theoretical guarantee for our mechanism under a popular graphical model for social network data, Ising model [14, 43] , which captures the correlation between agents and their friends. where 𝛽 = min (𝑖, 𝑗 ) ∈𝐸 𝛽 𝑖, 𝑗 , 𝛽 = max (𝑖, 𝑗 ) ∈𝐸 𝛽 𝑖, 𝑗 , and 𝑑 is the maximal degree of graph (𝑉, 𝐸).Mechanism 2 does not require knowledge about parameters of the Ising model, but only the connection of the network (𝑉, 𝐸). Social network platforms, which already possess this knowledge, can easily integrate our mechanism when conducting surveys. Additionally, snowball sampling [24] , which relies on participants referring their friends, is also naturally compatible with our mechanism.The complete proof of theorem 5.1 is quite technical and is deferred to the appendix, where we also explain why the bound between 𝜷 and 𝑑 is necessary. Below, we provide a sketch of the proof.Proof sketch for theorem 5.1. As discussed in section 4, we only need to show that for any agent 𝑖, for all agent 𝑗 with (𝑖, 𝑗) ∈ 𝐸 and 𝑘 with (𝑖, 𝑘) ∉ 𝐸, 𝑗's signal uniformly dominates 𝑘's signal for 𝑖's signal. Because the energy function 𝐻 (s) above remains invariant when the signs are flipped,EQUATIONWe then prove a lower bound for the left-hand side and an upper bound for the right-hand side separately. For the left-hand side, we use the Griffiths' inequality [44] to show that the minimum value of Pr[𝑆 𝑖 = 1 | 𝑆 𝑗 = 1] happens when 𝑗 is the only friend of 𝑖. For the right-hand side, we use Weitz's self-avoiding walk [65] and reduce any graph with maximum degree 𝑑 into a 𝑑-ary tree. □The design of BPP mechanisms for comparison data and networked data has suggested a general design scheme for other elicitation settings. That is, if one can identify a uniformly dominant tuple for Mechanism 3: General design scheme using BPP Input: Let ŝ be reports from agents in N . for agent 𝑖 ∈ N do Find two agents 𝑗 and 𝑘 so that 𝑗's signal uniformly dominates 𝑘's for 𝑖's, and pay agent 𝑖𝑀 𝑖 (ŝ) = 𝑈 𝐵𝑃𝑃 ( ŝ𝑖 , ŝ 𝑗 , ŝ𝑘 ) = ŝ𝑖 ŝ 𝑗 -ŝ𝑖 ŝ𝑘 .each agent, adopting the bonus-penalty payment gives a symmetrically strongly truthful mechanism. We further show that the bonus-penalty payment is in some sense unique. Theorem 5.2. If for each agent 𝑖 the associated agent 𝑗's signal uniformly dominates 𝑘's signal for 𝑖's signal, the above scheme is symmetrically strongly truthful.When an agent 𝑖 has multiple pairs of ( 𝑗 1 , 𝑘 1 ), . . . , ( 𝑗 ℓ , 𝑘 ℓ ) so that 𝑗 𝑙 's signal uniformly dominates 𝑘 𝑙 's for 𝑖's for each 𝑙 = 1, . . . , ℓ, we may pay agent 𝑖 the average of bonus-penalty payment on all pairs 𝑀 𝑖 (ŝ) = 1 ℓ ℓ 𝑙=1 𝑈 𝐵𝑃 𝑃 ( ŝ𝑖 , ŝ 𝑗 𝑙 , ŝ𝑘 𝑙 ). This average maintains our symmetrically strongly truthful guarantee while potentially reducing the variance in payments. Theorem 5.2 shows that bonus-penalty payment is a sufficient condition for designing good elicitation mechanisms for information structures with uniform dominance. We now prove it is also a necessary condition: any payment that induces truth-telling as a strict BNE under all uniformly dominant tuples must be an affine transformation of the bonus-penalty payment.Theorem 5.3 (Uniqueness). A payment 𝑈 : {-1, 1} 3 → R satisfies that, for all uniformly dominant tuples ⟨𝑆 𝑖 , 𝑆 𝑗 , 𝑆 𝑘 ⟩, 𝑠 𝑖 = arg max ŝ𝑖 ∈ { -1,1} E 𝑈 ( ŝ𝑖 , 𝑆 𝑗 , 𝑆 𝑘 ) | 𝑆 𝑖 = 𝑠 𝑖 , if and only if there exist 𝜆 > 0 and 𝜇 : {-1, 1} 2 → R so that 𝑈 (𝑠 𝑖 , 𝑠 𝑗 , 𝑠 𝑘 ) = 𝜆𝑈 𝐵𝑃 𝑃 (𝑠 𝑖 , 𝑠 𝑗 , 𝑠 𝑘 ) + 𝜇(𝑠 𝑗 , 𝑠 𝑘 ), for all 𝑠 𝑖 , 𝑠 𝑗 , 𝑠 𝑘 ∈ {-1, 1}where choice of 𝜇 does not affect the set of equilibria.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes]Justification: The code is uploaded in the supplementary material.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experiments: 
 We present experiments on real-world data to evaluate our models and mechanisms. We hope to cast insights on two questions empirically. Does our mechanism provide better rewards when all agents report truthfully than when all agents report randomly? Does our mechanism incentivize truth-telling for each agent if all other agents are truthful? We evaluate Mechanism 1 and 2 by comparing three settings, truth-telling, uninformed, and unilateral deviation, using empirical cumulative distribution functions (ECDF) on agents' payments. Each point on ECDF denotes the fraction of agents who get paid less than a particular value.For both comparison and networked datasets (figs. 1 and 2), we find our mechanisms provide better payments to agents under truthful settings than the other two settings. The ECDF under truth-telling lies below the other two ECDFs, which is known as first-order stochastic dominance. This implies that the truth-telling strategy results in higher average, quantiles (e.g., first quartile, median, and third quartile), and a greater expectation of any monotone function on the empirical distribution than the other two settings. We provide additionalWe consider preference data for a collection of 10 sushi items (item set A) [26, 27] , and focus on a group of 249 agents. Each agent provides a complete ranking of all 10 types of sushi in the dataset. These agents are female, aged thirty to forty-nine, who took more than three hundred seconds to rank the items and mostly lived in Kanto and Shizuoka until age fifteen. We restrict the set of agents to avoid significant violations of transitivity across different agents and to better align with our model assumptions. In the appendix, we will present the experimental results for other groups of users and further test whether the dataset satisfies transitivity.For the first question, we use Mechanism 1 to compute each agent's payment under the truth-telling or uninformed strategy profile. For each agent 𝑖, we 1) randomly sample three items 𝑎, 𝑎 ′ , 𝑎 ′′ and two agents 𝑗, 𝑘, 2) derive agent 𝑖's comparison on the first two items (𝑎, 𝑎 ′ ) from her ranking, (and similarly for agent 𝑗's comparison on (𝑎 ′ , 𝑎 ′′ ), and agent 𝑘's comparison on (𝑎, 𝑎 ′′ )), 3) compute bonus-penalty payment on these three comparisons, 4) repeat the above procedure 100 times and pay agent 𝑖 with the average of those 100 trials. For the uninformed strategy setting, we replace every agent's comparisons with uniform random bits and compute the payment. The left column of fig. 1 presents the ECDF of payments for the agents in both settings. The figure shows that in the uninformed random strategy setting only about 50% of the agents receive positive payments, while in the original dataset (truthful strategy setting) over 75% of the users receive positive payments. The right column of fig. 1 tests the second question if the agent has the incentive to deviate when every other agent is truthful. The truth-telling curve is identical to the left column of fig. 1 . For unilateral deviation, each agent gets the above bonus-penalty payment when her comparisons are replaced by uniform random bits. We plot the ECDFs of payments for both settings in the right column of fig. 1 .The figure shows that the ECDF of the unilateral deviation payments is above the ECDF of human users' payments, indicating that our mechanism pays more to the truth-telling agents. We test our BPP mechanism on the Last.fm dataset from Cantador et al. [8] . This dataset consists of 1892 agents on Last.fm, forming a social network with 12704 edges and an average degree of 6.71. It records agents' top fifty favorite artists whom they have listened to the most. We note that, in the dataset, listener fractions for all artists are much smaller than non-listener fractions. This bias differs from our Ising model in section 5.1 where every agent has the same chance to get both signals. Thus, the result can be seen as a stress test for our mechanism even when the data deviate from the assumption of our theoretical results.Figure 2 focuses on the most popular artist in the dataset, Lady Gaga, who has a listener fraction of 32.3%. The results for additional artists are presented in the supplementary material. The left column of fig. 2 tests the first question. Each agent has a binary signal about whether or not she listens to a particular artist (Lady Gaga in this section). For the truth-telling setting, everyone reports her signal truthfully and gets payment by the bonus-penalty payment (formally defined in section 5.1). For the uninformed setting, everyone gets the bonus-penalty payment when all reports are iid according to the prior (0.322 for Lady Gaga). When everyone is truthful, more than 76% of agents get positive payments and have an average payment of 0.37 for Lady Gaga, while when agents report randomly, only half get positive payments, and have a near zero average payment. These results suggest that agents got more incentive to choose the truth-telling equilibrium than the uninformed equilibrium. The right column of fig. 2 tests the second question. The truth-telling curve is identical to the left column of fig. 2 . For the unilateral deviation setting, each agent gets the bonus-penalty payment when she reports listener/non-listener uniformly at random. The unilateral deviation's payment is worse than the payments for truth-telling, decreasing from 0.37 to near zero for Lady Gaga. Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: Most of these details are explained in section 6 and in the provided code.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
conclusion and discussion: 
 We introduce a symmetrically strongly truthful peer prediction mechanism for eliciting comparison data without verification and extend it to eliciting networked data under Ising models. Our mechanisms are evaluated using real-world data. A key insight from our work is the identification of a structure we term "uniform dominance," which suggests a path for designing mechanisms in more complex elicitation settings. For example, in time-series data, adjacent points tend to be more related than distant ones, and in contextual settings, feedback from similar contexts is typically more related than from different contexts.A central assumption in this study is that agents are a priori similar. Hence, noisy comparisons of item pairs are independent of the assigned agent's identity. This assumption is reasonable for items with widely agreed-upon rankings, such as quality assessments of large language model (LLM) outputs. However, it may break down in settings where preferences are highly polarized, such as political opinions or social choice problems 4 . Despite this, our additional experiments in appendix F, which relax the selection rule used in obtaining fig. 1 , show that the mechanism remains robust even when some dissimilarities among agents exist.Agents in our model are assumed to focus solely on maximizing their payments, without accounting for efforts or external incentives such as minimizing others' rewards or intentionally distorting rankings. While our mechanism may be extended to handle binary effort as suggested in previous work [11, 57] , accommodating more than two effort levels would require additional assumptions [69] . Moreover, one may hope to incorporate the designer's utility, by factoring in downstream learning problems along with elicitation payments. This would necessitate a significant overhaul of the existing learning framework.Our mechanisms achieve a symmetric, strongly truthful equilibrium. This does not rule out the existence of non-symmetric equilibria with potentially higher utility. However, such equilibria would require complex coordination among agents, making them less likely to arise naturally.From a technical standpoint, our approach involves several assumptions that can be generalized or relaxed. Our Bayesian SST model, which relies on strong stochastic transitivity, serves as a non-parametric extension of several widely used parametric ranking models. In appendix C.2, we present both positive and negative results regarding weaker notions of transitivity (e.g., [5] ). While we assume admissible assignments, this can be relaxed to random assignments with full support. Additionally, limited liability can be ensured in our mechanism. For example, adding a constant of 1 to the payment function in eq. ( 2) ensures that the payment is either 2 or 0.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [No] Justification: We believe the error bars are not relevant to our empirical metrics.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: We believe the computer resources are not relevant to our main contributions.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: The research conducted in our paper conforms with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: Our work contributes to the theory of information elicitation. We discussed the applicability and limitations for elicitation settings.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: We believe this paper poses no such risks.Answer: [NA] Justification: The paper does not involve crowdsourcing or research with human subjects. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: In this section, we discuss the connection of bonus-penalty payment and existing peer prediction mechanisms. First, if we substitute the third input with a uniformly random bit, denoted as ŝ𝑘 = 𝑍 ∼ 𝑢 {-1, 1}, the bonus-penalty payment simplifies to the agreement mechanism [62, 61, 63] , one of the most basic peer prediction mechanisms,E 𝑈 𝐵𝑃 𝑃 ( ŝ𝑖 , ŝ 𝑗 , 𝑍) = ŝ𝑖 ŝ 𝑗 = 21[ ŝ𝑖 = ŝ 𝑗 ] -1.However, the agreement mechanism is not symmetrically strongly truthful, as all agents always reporting 1 and -1 can result in higher payments than truth-telling.The bonus-penalty payment eq. ( 1) is originally proposed by [11, 57] for the multi-task setting. Our BPP mechanism in Mechanism 3 can be seen as a generalization of multi-task setting. In the multi-task setting, agents works on multiple tasks and for each task the private signals are jointly identically and independently (iid) sampled from a fixed distribution and the each agent's strategy also are iid. Take two agents (Isabel and Julia) and two tasks as an example: Isabel has a private signal (𝑠 ) are iid from random vector (𝑆 𝑖 , 𝑆 𝑗 ). Isabel and Julia decide their reports on each task using random function 𝜎 𝑖 , 𝜎 𝑗 : {-1, 1} ↦ → {-1, 1} respectively. Dasgupta and Ghosh [11] use the following payments for Isabel1[ ŝ1 𝑖 = ŝ1 𝑗 ] -1[ ŝ1 𝑖 = ŝ2 𝑗 ] = 1 2 𝑈 𝐵𝑃𝑃 ŝ1 𝑖 , ŝ1 𝑗 , ŝ2 𝑗 .The payment is a special case of Mechanism 3 by taking the second input as ŝ1 𝑗 and the third input asŝ2 𝑗 . Additionally, 𝑆 1 𝑗 uniform dominates 𝑆 2 𝑗 for 𝑆 1 𝑖 if and only if Pr[𝑆 𝑗 = 1 | 𝑆 𝑖 = 1] > Pr[𝑆 𝑗 = 1], and Pr[𝑆 𝑗 = -1 | 𝑆 𝑖 = -1] > Pr[𝑆 𝑗 = -1]which is called categorical signal distributions [57] .Finally, similar to Shnayder et al. [57] , we may extend to non-binary signal setting by extending the payment to𝑈 𝐵𝑃 𝑃 ( ŝ𝑖 , ŝ 𝑗 , ŝ𝑘 ) = 2 1[ ŝ𝑖 = ŝ 𝑗 ] -1[ ŝ𝑖 = ŝ𝑘 ]and the definition of uniform dominance to the following. Definition A.1. Given a random vector (𝑆 𝑖 , 𝑆 𝑗 , 𝑆 𝑘 ) ∈ Ω 3 on a discrete domain, we say 𝑆 𝑗 uniformly dominates 𝑆 𝑘 for 𝑆 𝑖 ifPr[𝑆 𝑗 = 𝑠 | 𝑆 𝑖 = 𝑠] -Pr[𝑆 𝑘 = 𝑠 | 𝑆 𝑖 = 𝑠] > 0 and Pr[𝑆 𝑗 = 𝑠 ′ | 𝑆 𝑖 = 𝑠] -Pr[𝑆 𝑘 = 𝑠 ′ | 𝑆 𝑖 = 𝑠] < 0 for all 𝑠, 𝑠 ′ ∈ Ω with 𝑠 ≠ 𝑠 ′ .However, the guarantee for truth-telling (informed truthfulness) is weaker than the binary setting. Theorem A.2. Given any discrete domain Ω, if for each agent 𝑖 the associated agent 𝑗's signal uniformly dominates 𝑘's signal for 𝑖's signal (definition A.1), Mechanism 3's scheme is symmetrically informed truthful so that 1. truth-telling is a strict equilibrium, and 2. each agent's expected payment in truth-telling is no less than the payment in any other symmetric equilibria and strictly better than any uninformed equilibrium's.Proof. For any informed equilibrium, by a direct computation E 𝑈 𝐵𝑃𝑃 ( Ŝ𝑖 , Ŝ 𝑗 , Ŝ𝑘 ) = 0.Finally, we show that the truth-telling has the maximum expected payment for each agents. When all agent use a strategy 𝜎 : Ω → Ω, agent 𝑖's expected payment is∑︁ 𝑠 𝑖 , ŝ𝑖 ∈Ω Pr[𝑆 𝑖 = 𝑠 𝑖 ]𝜎(𝑠 𝑖 , ŝ𝑖 )E 𝑈 𝐵𝑃𝑃 ( ŝ𝑖 , Ŝ 𝑗 , Ŝ𝑘 ) | 𝑆 𝑖 = 𝑠 𝑖 =2 ∑︁ 𝑠 𝑖 , ŝ𝑖 ∈Ω Pr[𝑆 𝑖 = 𝑠 𝑖 ]𝜎(𝑠 𝑖 , ŝ𝑖 ) ∑︁ 𝑠∈Ω (Pr[𝑆 𝑗 = 𝑠 | 𝑆 𝑖 = 𝑠 𝑖 ] -Pr[𝑆 𝑘 = 𝑠 | 𝑆 𝑖 = 𝑠 𝑖 ])𝜎(𝑠, ŝ𝑖 ) =2 ∑︁ 𝑠 𝑖 ∈Ω Pr[𝑆 𝑖 = 𝑠 𝑖 ] ∑︁ ŝ𝑖 ,𝑠∈Ω 𝜎(𝑠 𝑖 , ŝ𝑖 )𝜎(𝑠, ŝ𝑖 ) (Pr[𝑆 𝑗 = 𝑠 | 𝑆 𝑖 = 𝑠 𝑖 ] -Pr[𝑆 𝑘 = 𝑠 | 𝑆 𝑖 = 𝑠 𝑖 ])Let 𝑓 𝑠 𝑖 (𝑠) := ŝ𝑖 ∈Ω 𝜎(𝑠 𝑖 , ŝ𝑖 )𝜎(𝑠, ŝ𝑖 ) which is between 0 and 1, because 𝑓 𝑠 𝑖 (𝑠) ≤ ŝ𝑖 ∈Ω 𝜎(𝑠 𝑖 , ŝ𝑖 ) ŝ𝑖 ∈Ω 𝜎(𝑠, ŝ𝑖 ) = 1. Then the expectation becomes ∑︁𝑠 𝑖 , ŝ𝑖 ∈Ω Pr[𝑆 𝑖 = 𝑠 𝑖 ]𝜎(𝑠 𝑖 , ŝ𝑖 )E 𝑈 𝐵𝑃𝑃 ( ŝ𝑖 , Ŝ 𝑗 , Ŝ𝑘 ) | 𝑆 𝑖 = 𝑠 𝑖 =2 ∑︁ 𝑠 𝑖 ∈Ω Pr[𝑆 𝑖 = 𝑠 𝑖 ] ∑︁ 𝑠∈Ω Pr[𝑆 𝑗 = 𝑠 | 𝑆 𝑖 = 𝑠 𝑖 ] -Pr[𝑆 𝑘 = 𝑠 | 𝑆 𝑖 = 𝑠 𝑖 ] 𝑓 𝑠 𝑖 (𝑠) ≤2 ∑︁ 𝑠 𝑖 ∈Ω Pr[𝑆 𝑖 = 𝑠 𝑖 ] Pr[𝑆 𝑗 = 𝑠 𝑖 | 𝑆 𝑖 = 𝑠 𝑖 ] -Pr[𝑆 𝑘 = 𝑠 𝑖 | 𝑆 𝑖 = 𝑠 𝑖 ] =E 𝑈 𝐵𝑃 𝑃 (𝑆 𝑖 , 𝑆 𝑗 , 𝑆 𝑘 )The inequality holds because 𝑓 𝑠 𝑖 ∈ [0, 1] and definition A.1. Therefore, we complete the proof. □The proofs of propositions 2.3 and 2.5 are standard, and variations can be found in related literature. We include proofs here for completeness.EQUATIONPr[𝑇 𝜃 (𝑎, 𝑎 ′′ ) = 1] =𝐹 (𝜃 𝑎 -𝜃 𝑎 ′′ ) > max 𝐹 (𝜃 𝑎 -𝜃 𝑎 ′ ), 𝐹 (𝜃 𝑎 ′ -𝜃 𝑎 ′′ ) = max Pr[𝑇 𝜃 (𝑎, 𝑎 ′ ) = 1], Pr[𝑇 𝜃 (𝑎 ′ , 𝑎 ′′ ) = 1]and thus 𝑇 𝜃 is strongly stochastically transitive for all 𝜃 with distinct coordinates which happens surely as 𝜈 is non-atomic. Finally, since the distribution on 𝜃 is exchangeable on each coordinate, E [E [𝑇 𝜃 (𝑎, 𝑎 ′ )]] = 0 for all 𝑎, 𝑎 ′ . □ Proof of proposition 2.5. First given 𝜃 ∈ Θ, for all distinct 𝑎, 𝑎 ′ ∈ A, if the rank of 𝑎 is higher than𝑎 ′ , Pr[𝑇 𝜃 (𝑎, 𝑎 ′ ) = 1] = ℎ 𝜂 (𝜃 (𝑎 ′ ) -𝜃 (𝑎) + 1) -ℎ 𝜂 (𝜃 (𝑎 ′ ) -𝜃 (𝑎))where ℎ 𝜂 (𝑥) = > max ℎ(𝜃 (𝑎 ′′ ) -𝜃 (𝑎 ′ ) + 1)ℎ(𝜃 (𝑎 ′′ ) -𝜃 (𝑎 ′ )), ℎ(𝜃 (𝑎 ′ ) -𝜃 (𝑎) + 1)ℎ(𝜃 (𝑎 ′ ) -𝜃 (𝑎))= max Pr[𝑇 𝜃 (𝑎, 𝑎 ′ ) = 1], Pr[𝑇 𝜃 (𝑎 ′ , 𝑎 ′′ ) = 1]where the second inequality is due to claim B.1. Therefore, 𝑇 𝜃 is strongly stochastically transitive for all 𝜃. Finally, E [E [𝑇 𝜃 (𝑎, 𝑎 ′ )]] = 0 for all 𝑎, 𝑎 ′ since 𝜃 is an uniform distribution on rankings. □ Proof of claim B.1. We first prove that the function ℎ 𝜂 (𝑥) = 𝑥 1-exp(-𝜂 𝑥 ) is increasing and strictly convex on 𝑥 ≥ 0. Because ℎ 𝜂 (𝑥) = 1 𝜂 ℎ 1 (𝜂𝑥), for all 𝜂, 𝑥, it is sufficient to consider 𝜂 = 1. First,ℎ ′ 1 (𝑥) = 1-( 𝑥+1)𝑒 -𝑥 (1-𝑒 -𝑥 ) 2 > 0, so ℎ 1 is increasing. Second, as ℎ ′′ 1 (𝑥) = 𝑒 -𝑥 ( ( 𝑥-2)+( 𝑥+2)𝑒 -𝑥 ) (1-𝑒 -𝑥 ) 3, to show ℎ ′′ 1 (𝑥) > 0 for all 𝑥 > 0, it is sufficient to show that 𝑔(𝑥) = (𝑥 -2) + (𝑥 + 2)𝑒 -𝑥 > 0. Because 𝑔(0) = 0 and 𝑔 ′ (𝑥) = 1 -(𝑥 + 1)𝑒 -𝑥 > 0, 𝑔(𝑥) > 0 for all 𝑥 > 0. Therefore, ℎ 1 is strictly convex. On the other hand, ℎ 𝜂 (𝑥+2)-ℎ 𝜂 (𝑥+1) > ℎ 𝜂 (𝑥+1)-ℎ 𝜂 (𝑥) for all 𝑥 by convexity, and ℎ 𝜂 (2)-ℎ 𝜂 (1) = EQUATIONand the other casePr[𝑆(𝑎 ′′ , 𝑎 ′ ) = -1 | 𝑆(𝑎, 𝑎 ′ ) = -1] > Pr[𝑆(𝑎 ′′ , 𝑎) = -1 | 𝑆(𝑎, 𝑎 ′ ) = -1]follows by symmetry. To prove eq. ( 5), we can rewrite the conditional probability in expectations of 𝑇 𝜃 .Pr[𝑆(𝑎 ′′ , 𝑎 ′ ) = 1 | 𝑆(𝑎, 𝑎 ′ ) = 1] = ∫ Pr[𝑇 𝜃 (𝑎 ′′ , 𝑎 ′ ) = 1, 𝑇 𝜃 (𝑎, 𝑎 ′ ) = 1 | 𝜃]𝑑𝑃 Θ ∫ Pr[𝑇 𝜃 (𝑎, 𝑎 ′ ) = 1 | 𝜃]𝑑𝑃 Θ = ∫ Pr[𝑇 𝜃 (𝑎 ′′ , 𝑎 ′ ) = 1 | 𝜃] Pr[𝑇 𝜃 (𝑎, 𝑎 ′ ) = 1 | 𝜃]𝑑𝑃 Θ ∫ Pr[𝑇 𝜃 (𝑎, 𝑎 ′ ) = 1 | 𝜃]𝑑𝑃 Θ (conditional independent) =2 ∫ Pr[𝑇 𝜃 (𝑎 ′′ , 𝑎 ′ ) = 1 | 𝜃] Pr[𝑇 𝜃 (𝑎, 𝑎 ′ ) = 1 | 𝜃]𝑑𝑃 Θ (a prior similar) =2 ∫ E [𝑇 𝜃 (𝑎 ′′ , 𝑎 ′ ) | 𝜃] + 1 2 E [𝑇 𝜃 (𝑎, 𝑎 ′ ) | 𝜃] + 1 2 𝑑𝑃 Θ (binary value) = 1 2 ∫ E [𝑇 𝜃 (𝑎 ′′ , 𝑎 ′ ) | 𝜃] E [𝑇 𝜃 (𝑎, 𝑎 ′ ) | 𝜃] + E [𝑇 𝜃 (𝑎 ′′ , 𝑎 ′ ) | 𝜃] + E [𝑇 𝜃 (𝑎, 𝑎 ′ ) | 𝜃] + 1𝑑𝑃 Θ = 1 2 ∫ E [𝑇 𝜃 (𝑎 ′′ , 𝑎 ′ ) | 𝜃] E [𝑇 𝜃 (𝑎, 𝑎 ′ ) | 𝜃] + 1𝑑𝑃 Θ .(a prior similar)Claim C.1. For any strongly stochastically transitive 𝑇 𝜃 on A, and distinct 𝑎, 𝑎 ′ , 𝑎 ′′ ∈ AE [𝑇 𝜃 (𝑎, 𝑎 ′ ) | 𝜃] E [𝑇 𝜃 (𝑎 ′′ , 𝑎 ′ ) | 𝜃] > E [𝑇 𝜃 (𝑎, 𝑎 ′ ) | 𝜃] E [𝑇 𝜃 (𝑎 ′′ , 𝑎) | 𝜃] .Pr[𝑆(𝑎 ′′ , 𝑎 ′ ) = 1 | 𝑆(𝑎, 𝑎 ′ ) = 1] = 1 2 ∫ E [𝑇 𝜃 (𝑎 ′′ , 𝑎 ′ ) | 𝜃] E [𝑇 𝜃 (𝑎, 𝑎 ′ ) | 𝜃] + 1𝑑𝑃 Θ > 1 2 ∫ E [𝑇 𝜃 (𝑎 ′′ , 𝑎) | 𝜃] E [𝑇 𝜃 (𝑎, 𝑎 ′ ) | 𝜃] + 1𝑑𝑃 Θ = Pr[𝑆(𝑎 ′′ , 𝑎) = 1 | 𝑆(𝑎, 𝑎 ′ ) = 1].This completes the proof of eq. ( 5), and thus the uniform dominance.□ Proof of claim C.1. We let 𝑄(𝛼, 𝛼 ′ ) := E [𝑇 𝜃 (𝛼, 𝛼 ′ ) | 𝜃] = 2 Pr[𝑇 𝜃 (𝛼, 𝛼 ′ ) = 1 | 𝜃] -1 for all 𝛼, 𝛼 ′ . Note that 𝑄(𝛼, 𝛼 ′ ) > 0 if and only if Pr[𝑇 𝜃 (𝛼, 𝛼 ′ ) = 1 | 𝜃] > 1/2 and 𝑄(𝛼, 𝛼 ′ ) = -𝑄(𝛼 ′ , 𝛼).By symmetry, let 𝑄(𝑎, 𝑎 ′ ) > 0. It is sufficient to show that 𝑄(𝑎 ′′ , 𝑎 ′ ) > 𝑄(𝑎 ′′ , 𝑎). If 𝑄(𝑎 ′ , 𝑎 ′′ ) > 0, by definition 2.1 𝑄(𝑎, 𝑎 ′′ ) > 𝑄(𝑎 ′ , 𝑎 ′′ ) > 0 so 𝑄(𝑎 ′′ , 𝑎 ′ ) > 𝑄(𝑎 ′′ , 𝑎). Now consider 𝑄(𝑎 ′ , 𝑎 ′′ ) < 0. If 𝑄(𝑎 ′′ , 𝑎) < 0, 𝑄(𝑎 ′′ , 𝑎 ′ ) > 0 > 𝑄(𝑎 ′′ , 𝑎). If 𝑄(𝑎 ′′ , 𝑎) > 0, we have 𝑄(𝑎 ′′ , 𝑎) > 0, 𝑄(𝑎, 𝑎 ′ ) > 0, and thus 𝑄(𝑎 ′′ , 𝑎 ′ ) > 𝑄(𝑎 ′′ , 𝑎) by definition 2.1 □There are weaker forms of stochastic transitivity, raising the question of whether they are sufficient for uniform dominance as in lemma 4.2. We show that general weak stochastic transitivity is not sufficient. Additionally, we show that although the noisy sorting model from [5] ′ ) = 1] > 1/2 and Pr[𝑇 (𝑎 ′ , 𝑎 ′′ ) = 1] > 1/2, Pr[𝑇 (𝑎, 𝑎 ) = 1] > 1/2.Compared to definition 2.1, the weak stochastic transitivity only require the item 𝑎 is favorable than 𝑎 ′′ . Below we provide a simple weakly stochastically transitive example with a prior similar property that does not satisfy the uniform dominance in eq. ( 5).Example C.3. Consider the set of three items and Θ consists of all ranking on A with uniform prior where 𝜃 maps each items to its value. Given 𝜃 ∈ Θ so that if 𝜃 (𝑎) > 𝜃 (𝑎 ′ ) > 𝜃 (𝑎 ′′ ),Pr[𝑇 𝜃 (𝑎, 𝑎 ′ ) = 1] = Pr[𝑇 𝜃 (𝑎 ′ , 𝑎 ′′ ) = 1] = 0.9 and Pr[𝑇 𝜃 (𝑎, 𝑎 ′′ ) = 1] = 0.6.Note that the model is weakly stochastically transitive, because an item with a larger value is more favorable and the weak stochastic transitivity is reduced to transitivity on the values. However, the model is not strongly stochastically transitive, because Pr[𝑇 𝜃 (𝑎,𝑎 ′′ ) = 1] = 0.6 < max{Pr[(𝑇 (𝑎, 𝑎 ′ ) = 1], Pr[(𝑇 (𝑎 ′ , 𝑎 ′′ ) = 1]]} = 0.9. Finally, as the rank 𝜃 has a uniform prior, the model satisfies a prior similar assumption.To conclude the example, we show that eq. ( 5) does not hold for the above model. By direct computation over all six possible ranking 𝜃, we havePr[𝑆(𝑎 ′′ , 𝑎 ′ ) = 1 | 𝑆(𝑎, 𝑎 ′ ) = 1] = 1 2 ∫ E [𝑇 𝜃 (𝑎 ′′ , 𝑎 ′ ) | 𝜃] E [𝑇 𝜃 (𝑎, 𝑎 ′ ) | 𝜃] + 1𝑑𝑃 Θ = 1 2 1 - 64 6 , but Pr[𝑆(𝑎 ′′ , 𝑎) = 1 | 𝑆(𝑎, 𝑎 ′ ) = 1] = 1 2 1 + 64 6 . Therefore, we have Pr[𝑆(𝑎 ′′ , 𝑎 ′ ) = 1 | 𝑆(𝑎, 𝑎 ′ ) = 1] < Pr[𝑆(𝑎 ′′ , 𝑎) = 1 | 𝑆(𝑎, 𝑎 ′ ) = 1], and show that eq. ( 5) does not hold.Though the above example shows that weak stochastic transitivity is not sufficient. 5 Below we show a popular weakly stochastically transitive model in Braverman and Mossel [5] has uniform dominance as in lemma 4.2. Example C.4. Let Θ be the set of rankings on A and 𝜂 > 0 be a parameter. Given a uniformly distributed reference ranking 𝜃 ∈ Θ, the noise ranking model [5] ensures that for all 𝜃 (𝑎) > 𝜃 (𝑎 ′ )Pr[𝑇 𝜃 (𝑎, 𝑎 ′ ) = 1] = 1 2 + 𝜂Note that the above model does not satisfy the strict inequality in definition 2.1, but by direct computation,Pr[𝑆(𝑎 ′′ , 𝑎 ′ ) = 1 | 𝑆(𝑎, 𝑎 ′ ) = 1] = 1 2 1 + 4𝛾 2 3andPr[𝑆(𝑎 ′′ , 𝑎) = 1 | 𝑆(𝑎, 𝑎 ′ ) = 1] = 1 2 1 -4𝛾 2 3, which satisfies lemma 4.2.Proof of lemma 4.3.Suppose 𝑆 𝑖 = 1. Because Pr[𝑆 𝑗 = 1|𝑆 𝑖 = 1] > Pr[𝑆 𝑘 = 1|𝑆 𝑖 = 1], Pr[𝑆 𝑗 = -1|𝑆 𝑖 = 1] < Pr[𝑆 𝑘 = -1|𝑆 𝑖 = 1]. Therefore, arg max ŝ∈ {-1,1} Pr[𝑆 𝑗 = ŝ|𝑆 𝑖 = 1] -Pr[𝑆 𝑘 = ŝ𝑖 |𝑆 𝑖 = 1] = 1.Identical argument holds for the case of 𝑆 𝑖 = -1 which completes the proof.Additionally, the expected payment of truth-telling is EQUATIONE 𝑈 𝐵𝑃 𝑃 ( ŝ𝑖 , Ŝ 𝑗 , Ŝ𝑘 ) | 𝑆 𝑖 = 𝑠 𝑖 = ∑︁ ŝ𝑗 , ŝ𝑘 𝜇( ŝ 𝑗 )𝜇( ŝ𝑘 )𝑈 𝐵𝑃𝑃 ( ŝ𝑖 , Ŝ 𝑗 , Ŝ𝑘 ) = ∑︁ ŝ𝑗 , ŝ𝑘 𝜇( ŝ 𝑗 )𝜇( ŝ𝑘 ) ( ŝ𝑖 ŝ 𝑗 -ŝ𝑖 ŝ𝑘 ) = 0The first equality holds as the reports are independent of signals.Proof of lemma 4.5.E 𝑃, 𝜎 𝑈 𝐵𝑃 𝑃 ( ŝ𝑖 , Ŝ 𝑗 , Ŝ𝑘 ) | 𝑆 𝑖 = 𝑠 𝑖 = ∑︁ 𝑠 𝑗 ,𝑠 𝑘 , ŝ𝑗 , ŝ𝑘 Pr[𝑆 𝑗 = 𝑠 𝑗 , 𝑆 𝑘 = 𝑠 𝑘 | 𝑆 𝑖 = 𝑠 𝑖 ]𝜎(𝑠 𝑗 , ŝ 𝑗 )𝜎(𝑠 𝑘 , ŝ𝑘 )𝑈 𝐵𝑃𝑃 ( ŝ𝑖 , ŝ 𝑗 , ŝ𝑘 ) =2 ∑︁ 𝑠 𝑗 ,𝑠 𝑘 , ŝ𝑗 , ŝ𝑘 Pr[𝑆 𝑗 = 𝑠 𝑗 , 𝑆 𝑘 = 𝑠 𝑘 | 𝑆 𝑖 = 𝑠 𝑖 ]𝜎(𝑠 𝑗 , ŝ 𝑗 )𝜎(𝑠 𝑘 , ŝ𝑘 ) 1[ ŝ𝑖 = ŝ 𝑗 ] -1[ ŝ𝑖 = ŝ𝑘 ](by eq. ( 1))=2 ∑︁ 𝑠 𝑗 , ŝ𝑗 Pr[𝑆 𝑗 = 𝑠 𝑗 | 𝑆 𝑖 = 𝑠 𝑖 ]𝜎(𝑠 𝑗 , ŝ 𝑗 )1[ ŝ𝑖 = ŝ 𝑗 ] -2 ∑︁ 𝑠 𝑘 , ŝ𝑘 Pr[𝑆 𝑘 = 𝑠 𝑘 | 𝑆 𝑖 = 𝑠 𝑖 ]𝜎(𝑠 𝑘 , ŝ𝑘 )1[ ŝ𝑖 = ŝ𝑘 ] =2 ∑︁ 𝑠, ŝ (Pr[𝑆 𝑗 = 𝑠 | 𝑆 𝑖 = 𝑠 𝑖 ] -Pr[𝑆 𝑘 = 𝑠 | 𝑆 𝑖 = 𝑠 𝑖 ])𝜎(𝑠, ŝ)1[ ŝ𝑖 = ŝ] (renaming dummy variables) =2 ∑︁ 𝑠 (Pr[𝑆 𝑗 = 𝑠 | 𝑆 𝑖 = 𝑠 𝑖 ] -Pr[𝑆 𝑘 = 𝑠 | 𝑆 𝑖 = 𝑠 𝑖 ])𝜎(𝑠, ŝ𝑖 ) Let 𝛿 = Pr[𝑆 𝑗 = 𝑠 𝑖 | 𝑆 𝑖 = 𝑠 𝑖 ] -Pr[𝑆 𝑘 = 𝑠 𝑖 | 𝑆 𝑖 = 𝑠 𝑖 ] > 0, because 𝑆 𝑗 uniformly dominates 𝑆 𝑘 for 𝑆 𝑖 . Additionally, Pr[𝑆 𝑗 = -𝑠 𝑖 | 𝑆 𝑖 = 𝑠 𝑖 ] -Pr[𝑆 𝑘 = -𝑠 𝑖 | 𝑆 𝑖 = 𝑠 𝑖 ] = 1 -Pr[𝑆 𝑗 = 𝑠 𝑖 | 𝑆 𝑖 = 𝑠 𝑖 ] -1 + Pr[𝑆 𝑘 = 𝑠 𝑖 | 𝑆 𝑖 = 𝑠 𝑖 ] = -𝛿. We have E 𝑃, 𝜎 𝑈 𝐵𝑃 𝑃 ( ŝ𝑖 , Ŝ 𝑗 , Ŝ𝑘 ) | 𝑆 𝑖 = 𝑠 𝑖 =2 ∑︁ 𝑠 (Pr[𝑆 𝑗 = 𝑠 | 𝑆 𝑖 = 𝑠 𝑖 ] -Pr[𝑆 𝑘 = 𝑠 | 𝑆 𝑖 = 𝑠 𝑖 ])𝜎(𝑠, ŝ𝑖 ) =2𝛿 (𝜎(𝑠 𝑖 , ŝ𝑖 ) -𝜎(-𝑎, ŝ𝑖 )) , so arg max ŝ𝑖 ∈ { -1,1} E 𝑃, 𝜎 𝑈 𝐵𝑃 𝑃 ( ŝ𝑖 , Ŝ 𝑗 , Ŝ𝑘 ) | 𝑆 𝑖 = 𝑠 𝑖 = arg max ŝ𝑖 ∈ {-1,1} {𝜎(𝑠 𝑖 , ŝ𝑖 ) -𝜎(-𝑠 𝑖 , ŝ𝑖 )} which completes the proof. □ D Proofs in Section 5.1Before diving into the proof, we introduce some notations. We further introduce Ising models with bias parameter 𝜶 ∈ R 𝑉 ≥0 in addition to 𝜷 where𝐻 (s) = ∑︁ 𝑖, 𝑗 ∈𝑉 𝛽 𝑖, 𝑗 𝑠 𝑖 𝑠 𝑗 + ∑︁ 𝑖 ∈𝑉 𝛼 𝑖 𝑠 𝑖and Pr 𝜶,𝜷 [S = s] ∝ exp(𝐻 (s)), for all configuration s. Given 𝑖 ∈ 𝑉, let the expectation and ratio be𝜈 𝑖 (𝜶, 𝜷) = E 𝜶,𝜷 [𝑆 𝑖 ] = Pr 𝜶,𝜷 [𝑆 𝑖 = 1] -Pr 𝜶,𝜷 [𝑆 𝑖 = -1] and 𝜌 𝑖 (𝜶, 𝜷) = Pr 𝜶,𝜷 [𝑆 𝑖 = 1] Pr 𝜶,𝜷 [𝑆 𝑖 = -1]respectively which are monotone to each other. We will omit 𝜶, 𝜷 when clear. Given a subset 𝑈 ⊆ 𝑉, s 𝑈 ∈ {-1, 1} 𝑈 is a configuration over the nodes in 𝑈, and s 𝑈 = 1 if 𝑥 𝜄 = 1 for all 𝜄 ∈ 𝑈. We write Pr[•|S 𝑈 = s 𝑈 ], 𝜈 𝑖 |S 𝑈 =s 𝑈 , and 𝜌 𝑖 |S 𝑈 =s 𝑈 for the conditional probability, expectation and ratio when the configuration in 𝑈 is fixed as specified by s 𝑈 .A lower bound for LHS Informally, we want to lower bound the correlation between adjacent 𝑖 and 𝑗 (friends). Note that as we remove edges (setting coordinates of 𝜷 to zeros), the correlation should decrease, and the smallest correlation between neighboring nodes 𝑖 and 𝑗 happens when 𝐸 = {(𝑖, 𝑗)}. Lemma D.2 formalizes this idea using the following monotone inequality [44, Theorem 17.2] .Theorem D.1 (Griffiths' inequality). For any 𝑖 ∈ 𝑉, 𝜈 𝑖 (𝜶, 𝜷) = E 𝜶,𝜷 [𝑆 𝑖 ] is non-negative and non-decreasing in all 𝛽 𝑗,𝑘 ≥ 0 and 𝛼 𝑗 ≥ 0 with 𝑗, 𝑘 ∈ 𝑉.Lemma D.2. Given 𝑉 and 𝑖, 𝑗 ∈ 𝑉, for all 𝜶, 𝜷, and 𝜷 ′ , if 𝛽 ′ 𝑒 = 𝛽 𝑒 when 𝑒 = (𝑖, 𝑗) and 𝛽 ′ 𝑒 = 0 otherwise, we have𝜈 𝑖 |𝑆 𝑗 =1 (𝜶, 𝜷) ≥ 𝜈 𝑖 |𝑆 𝑗 =1 (𝜶, 𝜷 ′ ) and 𝜌 𝑖 |𝑆 𝑗 =1 (𝜶, 𝜷) ≥ 𝜌 𝑖 |𝑆 𝑗 =1 (𝜶, 𝜷 ′ ).Proof. First, note that we can write the conditional expectation E 𝜶,𝜷 𝑆 𝑖 | 𝑆 𝑗 = 1 as marginal expectation. Formally, consider 𝜶 𝜂 so that 𝛼𝜂 𝜄 = 𝛼 𝜄 if 𝜄 ≠ 𝑗 and 𝛼 𝜂 𝑗 = 𝛼 𝑗 + 𝜂. Because 𝜂 → 𝜶 𝜂 is non-decreasing, 𝜂 → 𝜈 𝑖 (𝜶 𝜂 , 𝜷) is non-decreasing by theorem D.1. In addition, Pr 𝜶 𝜂 ,𝜷 [𝑆 𝑖 | 𝑆 𝑗 = 𝑠] = Pr 𝜶,𝜷 [𝑆 𝑖 | 𝑆 𝑗 = 𝑠] for all 𝑠, and Pr 𝜶 𝜂 ,𝜷 [𝑆 𝑗 = -1] = 𝑂 (𝑒 -2𝜂 ), so 𝜈 𝑖 |𝑆 𝑗 =1 (𝜶, 𝜷) = E 𝜶,𝜷 [𝑆 𝑖 | 𝑆 𝑗 = 1] = lim 𝜂→+∞ 𝜈 𝑖 (𝜶 𝜂 , 𝜷). Similarly, 𝜈 𝑖 |𝑆 𝑗 =1 (𝜶, 𝜷 ′ ) = E 𝜶,𝜷 ′ [𝑆 𝑖 | 𝑆 𝑗 = 1] = lim 𝜂→+∞ 𝜈 𝑖 (𝜶 𝜂 , 𝜷 ′ ).On the other hand, consider 𝜷 𝜆 so that 𝛽 𝜆 𝑒 = 𝛽 𝑒 if 𝑒 ≠ (𝑖, 𝑗) and 𝛽 𝜆 𝑖, 𝑗 = 𝛽 𝑖, 𝑗 + 𝜆. By theorem D.1, 𝜈 𝑖 (𝜶 𝜂 , 𝜷 𝜆 ) is non-decreasing in 𝜆 for all 𝜂. Because 𝜷 0 = 𝜷 ′ and 𝜷 1 = 𝜷, we have𝜈 𝑖 |𝑆 𝑗 =1 (𝜶, 𝜷 ′ ) = lim 𝜂→+∞ 𝜈 𝑖 (𝜶 𝜂 , 𝜷 ′ ) ≤ lim 𝜂→+∞ 𝜈 𝑖 (𝜶 𝜂 , 𝜷) = 𝜈 𝑖 |𝑆 𝑗 =1 (𝜶, 𝜷) Because 𝜌 𝑖 = 1+𝜈 𝑖1-𝜈 𝑖 is monotone in 𝜈 𝑖 , the second part follows. □Given 𝜷 ′ defined in lemma D.2, by some direct computation with 𝜶 = 0EQUATION)An upper bound for RHS Now, we need to upper bound the correlation between non-adjacent 𝑖 and 𝑘 (non-friends). We will use Weitz's self-avoiding walks reduction [65] to upper bound the correlation on general graph 𝐺 by the correlation on trees.Given a general graph 𝐺, and an arbitrary node 𝑖, we can construct the Self Avoiding Walk Tree of 𝐺 rooted at 𝑖, denoted 𝑇 𝑆 𝐴𝑊 (𝐺, 𝑖), so that Pr[𝑆 𝑖 = 1 | S 𝑈 = s 𝑈 ] is the same in 𝐺 as in the tree. We outline the construction. 𝑇 𝑆 𝐴𝑊 (𝐺, 𝑖) enumerates all self-avoiding walks in 𝐺 starting at 𝑖 which terminates when it revisits a previous node (closes a cycle). Then, 𝑇 𝑆 𝐴𝑊 (𝐺, 𝑖) introduces a leaf with a certain boundary condition. The self-avoiding walk never revisits a node immediately, so there all the leaves with fixed boundary conditions are at least three hops away from node 𝑖. Note that if 𝐺 has maximum degree 𝑑, 𝑇 𝑆 𝐴𝑊 is a 𝑑-ary tree.). For any 𝜶, 𝜷, node 𝑖 ∈ 𝑉, and configuration s 𝑈 on 𝑈 ⊂ 𝑉,Pr 𝜶,𝜷 [𝑆 𝑖 = 1 | S 𝑈 = s 𝑈 ] = Pr 𝑇 𝑆 𝐴𝑊 (𝐺,𝑖) [𝑆 𝑖 = 1 | S 𝑈 = s 𝑈 ].First, with the above theorem, we have𝜈 𝑖 |𝑆 𝑘 =1 (𝜶, 𝜷) = E 𝜶,𝜷 [𝑆 𝑖 | 𝑆 𝑘 = 1] = E 𝑇 𝑆 𝐴𝑊 (𝐺,𝑖) [𝑆 𝑖 | 𝑆 𝑘 = 1].By the monotone property in theorem D.1, setting all two-hop neighbors 𝑈 in 𝑇 𝑆 𝐴𝑊 (𝐺, 𝑖) to 1 (recalled that any boundary conditions for 𝑇 𝑆 𝐴𝑊 (𝐺, 𝑖) being at least three hops away) increases the conditional expectation,E 𝑇 𝑆 𝐴𝑊 (𝐺,𝑖) [𝑆 𝑖 | 𝑆 𝑘 = 1] ≤ E 𝑇 𝑆 𝐴𝑊 (𝐺,𝑖) [𝑆 𝑖 | S 𝑈 = 1, 𝑆 𝑘 = 1] .Let 𝑇 be the tree by truncating 𝑇 𝑆 𝐴𝑊 (𝐺, 𝑖) at level 2. By the Markov property of Ising models, the expectation is equal to the expectation on 𝑇.EQUATIONFinally, we can recursively compute the probability ratio 𝜌 𝑖 (and thus expectation 𝜈 𝑖 ) on trees. Specifically, given a rooted tree 𝑇 ′ , we define 𝜌 𝑇 ′ as the ratio of probabilities for the root to be +1 and -1 respectively, and 𝜌 𝑇 ′ |S 𝑈 =s 𝑈 for the ratio of conditional probabilities. As stated in the following lemma, it is well known (see, for example, [22] ) that the ratio of each node can be computed recursively over the children's ratio. Lemma D.4. Given a tree 𝑇 rooted at 𝑖 with parameter (𝜶, 𝜷) and boundary condition s 𝑈 ,𝜌 𝑇 |S 𝑈 =s 𝑈 = 𝑒 2𝛼 𝑖 𝑑 𝑙=1 𝜌 𝑇 𝑙 |S 𝑈 =s 𝑈 𝑒 2𝛽 𝑖, 𝑗 𝑙 + 1 𝑒 2𝛽 𝑖, 𝑗 𝑙 + 𝜌 𝑇 𝑙 |S 𝑈 =s 𝑈where 𝑗 1 , . . . , 𝑗 𝑑 are children of 𝑖 and 𝑇 𝑙 is the subtree rooted at 𝑗 𝑙 for all 𝑙.By the monotone property in theorem D.1, the maximum of right-hand side of eq. ( 7) happens when 𝑇 is a complete 𝑑-ary tree with 𝜷 = 𝛽. Therefore,EQUATIONFinally, with eqs. ( 6) and ( 8), we have𝜌 𝑖 |𝑆 𝑗 =1 (𝜶, 𝜷) ≥ 𝑒 2𝛽 ≥ 𝑒 2(𝑑+1) 𝛽 +1 𝑒 2𝛽 +𝑒 2𝑑𝛽𝑑 ≥ 𝜌 𝑖 |𝑆 𝑘 =1 (𝜶, 𝜷) which implies eq. ( 4).Remark D.5. Note that for any graph 𝐺 there exists small enough 𝛽, 𝛽 so that the condition in and additionally write 𝑝 𝑠 𝑖 = 𝑝 𝑠 𝑖 (1, 1)𝑝 𝑠 𝑖 (1, -1) 𝑝 𝑠 𝑖 (-1, 1) 𝑝 𝑠 𝑖 (-1, -1). Then definition 4.1 ensures that 𝑝 1 (1, -1) > 𝑝 1 (-1, 1) and 𝑝 -1 (1, -1) < 𝑝 -1 (-1, 1).Because 𝑈 is truthful for all uniformly dominant tuples, we haveEQUATIONSuppose the following are trueEQUATIONLet 𝜆 = 𝐷 (1, -1) > 0. By eqs. ( 11) and ( 12), we have 𝑈 (𝑠 𝑖 , 𝑠 𝑗 , 𝑠 𝑘 ) =𝑠 𝑖 • 𝐷 (𝑠 𝑗 , 𝑠 𝑘 ) + 𝜇(𝑠 𝑗 , 𝑠 𝑘 ) (by eq. ( 9)) =𝜆 • 𝑠 𝑖 (𝑠 𝑗 -𝑠 𝑘 ) + 𝜇(𝑠 𝑗 , 𝑠 𝑘 ) (by eqs. ( 9) and ( 11))which completes the proof. Thus, we will construct three joint distributions satisfying definition 4.1 to prove eqs. (11) and (12) .The first joint distribution 𝑝 𝑠 𝑖 1 (𝑠 𝑗 , 𝑠 𝑘 ) with 0 < 𝛿 ≤ 1/2𝑝 1 = 0 1/2 + 𝛿 1/2 -𝛿 0 and 𝑝 -1 = 0 1/2 -𝛿 1/2 + 𝛿 0 .Then eq. ( 10) on the first distribution reduces to0 <𝐷 (1, -1) 𝑝 1 1 (1, -1) + 𝐷 (-1, 1) 𝑝 1 1 (-1, 1) = 1 2 (𝐷 (1, -1) + 𝐷 (-1, 1)) + 𝛿(𝐷 (1, -1) -𝐷 (-1, 1)) 0 >𝐷 (1, -1) 𝑝 -1 1 (1, -1) + 𝐷 (-1, 1) 𝑝 -1 1 (-1, 1) = 1 2 (𝐷 (1, -1) + 𝐷 (-1, 1)) -𝛿(𝐷 (1, -1) -𝐷 (-1, 1)).As we take 𝛿 to zero, we prove 𝐷 (1, -1) = -𝐷 (-1, 1). Then plugging in with nonzero 𝛿, we have 𝐷 (1, -1) > 0 and complete the proof of eq. (11) . also documented in Daskalakis et al. [12] which notes that the Ising model performs much better for rock artists than for pop artists. The authors conjecture that this may be due to the highly divisive popularity of pop artists like Lady Gaga and Britney Spears, whose listeners may form dense cliques within the graph.Note that there is a buck of agent with a payment of around 0.5 under the truth-telling. This is because many non-listeners have no listener friends, and payment is 1 -[(1 -𝑝) -𝑝] = 2𝑝 is twice the popularity 𝑝 ≈ 0.25. Moreover, the jump is most minor for the Beatles, and indicates less agreement between non-listeners. Additionally, by the definition of bonus-penalty payment, we can see the payment of deviation is the minus of the truthful payment, so that the ECDF is symmetric around (0, 0.5). Figure 8 further shows the scatter plot of average payment and fraction of agents with positive payments across the top fifty popular artists where all settings have more than 60% percent of agents get positive payment. However, for less popular artists, the performance of our mechanism declines. This is expected, as we cannot provide effective incentives when only one agent listens to an artist. • If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.38th Conference on Neural Information Processing Systems (NeurIPS 2024).Kong and Schoenebeck [30] shows that it is impossible to pay the truth-telling strategy profile strictly better than other permutation strategy profiles without additional knowledge of the prior signal distribution.Specifically, given any assignment E 0 , we can construct a superset E so that for any (𝑎, 𝑎 ′ ) ∈ E 0 find an arbitrary 𝑎 ′′ ≠ 𝑎, 𝑎 ′ and add (𝑎, 𝑎 ′ ), (𝑎 ′ , 𝑎), (𝑎, 𝑎 ′′ ), (𝑎 ′′ , 𝑎), (𝑎 ′ , 𝑎 ′′ ), (𝑎 ′′ , 𝑎 ′ ) into E. Thus, E is admissible and at most six times larger than E 0 .If we view 𝑆 𝑗 and 𝑆 𝑘 as two statistical tests for a binary event 𝑆 𝑖 , the two inequalities in definition4.1 say that 𝑆 𝑗 has a better type II and type I error than 𝑆 𝑘 respectively.For example, when ranking phone features (e.g., innovation, performance, brand reputation, price, ease of use), consumers often fall into two groups: early adopters, who prioritize cutting-edge technology, and late adopters, who favor stability, affordability, and ease of use. Their opposing preferences violate the a priori similarity assumption. Imagine an early adopter whose payment in eq. (2) depends on two late adopters. Since their preferences may differ significantly, the early adopter might have an incentive to misreport her preferences.In the above example, we can also decrease 0.9 to a smaller number that satisfies both uniform dominance and weak stochastic transitivity. 


Decision: This paper proposes a peer-prediction based mechanism for truthfully eliciting noisy pairwise comparisons from multiple agents whose preferences are drawn from a common prior, but not otherwise observable by the center.  The mechanism is proven truthful in a particularly strong sense (truthtelling is both strictly Bayes-Nash and the highest-payoff symmetric equilibrium).  Results are validated against a number of datasets from the literature.

The reviewers were uniformly positive about this paper.  Its results and new concepts are likely to be relevant beyond the specific setting of the paper.  There were some concerns about the need for strong assumptions, but these were largely addressed during the discussion period.

Reviews: review: paper_summary: paper_summary: * This paper proposes a peer prediction mechanism for elicitation of comparison data.
* In the model, there is a collection of items $A$, and a set of agents $N$ which privately observe noisy comparisons between items. Comparisons are characterized by a stochastic comparison function $T_\\theta$, parameterized by $\\theta \\in \\Theta$ and drawn from a common prior $P_\\Theta$.
* A peer prediction mechanism assigns a pair of items for each agent $i$ to compare. Each agent then observes a noisy comparison signal $s_i$ and strategically reports a possibly different value $\\hat{s}_i$ to maximize their ex-ante payment $\\mathbb{E} [M_i (\\hat{\\mathbf{s}})]$. The goal is to design a mechanism $M$ which elicits truthful reporting.
* The authors present Mechanism 1 for elicitation of comparison data, and prove that it is symmetrically strongly truthful (Theorem 3.1). The mechanism is based on a bonus-penalty payment function, which for agent $i$ awards agreement with some agent $j$, and penalizes agreement with some agent $k$.
* Section 5.1 presents a generalization of the mechanism to networked data, proving that it is symmetrically strongly truthful for signals sampled from the graph Ising model (Theorem 5.1). Section 5.2 further generalizes by showing a mechanism which is symmetrically strongly truthful for data with uniform dominance.
* Finally, empirical evaluation is performed on two datasets (Sushi preferences and Last.fm). Results seem to show stochastic dominance of payout in truthful reporting vs. random reporting.
strength_weakness: strength_weakness: * Empirical evaluation compares truthful reporting against benchmarks which seem relatively “simple” - uninformed random reporting, as opposed to more sophisticated forms of strategic behavior.
* Empirical evaluation procedure is not sufficiently clear. Method of constructing the graphs in the empirical section is not presented sufficiently formally. Graph legends and captions are uninformative.
* Implications of assumptions are not discussed in detail. Examples for such assumptions - assuming symmetric deviation, the ability to penalize users, assuming that items are a priori similar but ex-post distinct. See below.
questions: questions: * What is the relation between Mechanism 3 and Mechanisms 1,2? Is it possible to think about Theorem 3.1 and Theorem 5.1 as corollaries of Theorem 5.2? If not, how do they fundamentally differ?
* “We assume items are a priori similar but ex-post distinct” L106 - What are the implications of this assumption? When does it apply, and does it restrict generality?
* For the given mechanism, is it possible to have a better BNE which is not symmetric? (e.g, a beneficial equilibrium where only some agents report truthfully?)
* What would be the implications of agents having limited liability? (e.g if the agents can choose not to participate in the game when they may get negative reward)
* Possible typo in L318: “ The figure shows that only about 50% of the agents using an uninformed random strategy receive positive payments, while over 75% of the users in the original dataset receive positive payments” - Percentages seem to add to more than 100%.
limitations: limitations: Results seem to rely on relatively strong assumptions, such as symmetric deviation, and the ability to penalize users. Despite that, such limitations don’t seem to be discussed in detail.
paper_summary: paper_summary: This paper considers the problem of eliciting pairwise comparisons truthfully from strategic agents in the absence of ground truth. It considers the popular framework of peer prediction which is a class of mechanisms where reports from "peer" agents are used as a proxy for ground truth in order to design a payment scheme. The problem with using existing peer prediction mechanisms is that they mainly work for settings where tasks are drawn from the same distribution. However, this does not apply to the case of pairwise comparisons, as the two items being compared can be very different. 

This paper designs a new peer prediction mechanism that is based on the Dasgupta-Ghosh mechanism where the agents also suffer a penalty in addition to rewards so as to avoid spurious "agree to agree" equilibria. The main novelty of the paper comes from the connection it makes to the well-known strong stochastic transitivity (SST) condition for pairwise comparison data. Under the assumption that pairwise comparisons satisfy SST condition, the mechanism cleverly utilizes this condition to ensure that the reward term exceeds the penalty term for truthful agents which is one of the main requirements for truthfulness. The paper also considers other elicitation tasks beyond pairwise comparisons, such as eliciting networked data, and give a general framework for extending.
strength_weakness: strength_weakness: I am only concerned about the relevance of this paper to NeurIPS as this is mainly a mechanism design paper. But given the usefulness of pairwise comparisons in training LLMs, there is definitely need for truthful elicitation of comparison data.

The results on networked elicitation seem a bit disconnected from the results on elicitation of comparison data.
questions: questions: Perhaps the framework also works for weak stochastic transitivity?
limitations: limitations: I did not find adequate discussion about limitations. Perhaps a section on limitations of the mechanism and peer prediction in-general might be useful.
paper_summary: paper_summary: This paper studies elicting comparison data with truthfulness guarantees, specifically strict Bayesian Nash equilbrium. The authors utilize strong stochastic transitivity to define a Bayesian strong stochastic transitivity model and generalize several existing models. Under this model (i.e., problem setting), the authors propose a peer prediction mechanism based on bonus-penalty and show that it achieves symmetrically strong truthfulness, for both comparison data. Moreover, the authors also identify the conditions (in theoretical results) and the corresponding mechanism that achieves symmetric strong truthfulness for networked data and the general setting. Empirical results on two real-world datasets show that the proposed mechanism achieves better truthfulness or incentive, by showing that being truthful leads to a higher payment.
strength_weakness: strength_weakness: - An important requirement or assumption is the admissible condition to ensure that the assignment contains the necessary triplets. While the authors describe that one can create a superset, with a bounded size, to ensure the admissible condition. It appears that in doing so, one may need the agents to observe and report additional pairs of items (correct me if I am wrong). If so, in practice, one may not always be able to ask the agents to make addtional observations on required pairs of items (e.g., customers' reviews of products of services).

- The abstract and introduction motivates the importance of eliciting comparison data by citing several applications and use cases. However, the covered use cases by the empirical results seem to be less extensive than these.
questions: questions: In lines 132-133,

> ... where the randomness of $S(\cdot, \cdot)$ comes from both $\theta$ and $T_{\theta}$
The randomness of $\theta$ is due to $\theta \sim P_{\Theta}$. What is the randomness of $T_{\theta}$? How should one interpret this, and its implications?

What other families of strategies are useful? Can strategically mis-behaving agents be accounted for, for instance to exploit this system to minimize someone's expected payment or intentionally aiming to obfuscate identification of the true comparison or ranking? In other words, are these considered families of strategies sufficient to consider some robustness to mis-behaving agents (and which types)?

In lines 173-174,

> ... she would expect that others will ... prefer $a$ over $a''$

What is the intuition behind this? Why would $a$ be preferred over $a''$ when the agent itself only has information that $a$ is preferred over $a'$?

In line 190-191,
> Hence, theorem 3.1 implies that agents’ manipulations can only decrease the probability of transitivity among their reports.

What is the implication of "decreasing the probability of transitivity among their reports"?
limitations: limitations: The method requires a specific problem setting or model called the Bayesian strong stochastic transitivity. But it is shown to generalize several other existing models.

Comments: title: Post rebuttal
comment: Thank you for checking our response!
Thank you for the response! The rebuttal seems to address my main concerns. I increase my score to 6.
Thank you for acknowledging this!
Thank you for your response! I have no further questions and would like to keep my original score.
We would greatly appreciate your response to our rebuttal, which, in our view, effectively addresses your main concerns. If there are lingering questions, we would gladly engage in a discussion.
We thank the reviewer for acknowledging this!
I thank the authors for their prepared response. Most of my questions are clarified and I am happy to maintain my current recommendation of weak accept.