Carrot and Stick: Eliciting Comparison Data and Beyond
Authors: Yiling Chen
Shi Feng
Fang-Yi Yu
Venue: NeurIPS 2024 poster (2024)
Keywords: information elicitation
mechanism design
crowdsourcing
ranking data
social network
Primary area: algorithmic_game_theory

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.

Carrot and Stick:
Eliciting Comparison Data and Beyond
Yiling Chen
Shi Feng Harvard University shifeng@fas harvard. edu
Fang-Yi Yu George Mason University Langyiyu@gra edu
Harvard University yilingSseas. harvard.
Abstract
Comparison data elicited from people fundamental 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 bonus-penalty payment [[]] Our design leverages the strong stochastic transitivity for comparison data 66 to create symmetrically strongly truthful mechanisms such that truth-telling 1) forms a strict Bayesian Nash equilibrium, and 2) yields the highest payment among symmetric equilibria. Each individual only needs to evaluate one pair of items and report her comparison in mechanism.
We further extend the bonus-penales payment concept to eliciting networked data, designing 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 have truth-telling strict Bayesian Nash equilibrium. Experiments on two real-world datasets further support our theoretical discoveries.
Introduction
In the past two decades, researchers have been embracing the challenge of eliciting private information from individuals when there is ground truth available evaluate the quality of elicited contribu- tions, and have made amazing progress. Many mechanisms, collectively called peer prediction [42] have been developed incentivize individuals to strictly truthfully report their information 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.c. it's a strongly truthful BNE). 51 30
However, all prior multi- taiki 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 succeed truthful elicitation. But what if such structure of information doesn't it 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 [0) Such pair-wise comparison data are crucial for estimating ranking of the alternatives and for devising reward functions for reinforcement learning. Comparison tasks for different pairs clearly not ex-ante identical answers to the tasks demonstrate certain degree of transitivity (e.g. if a is preferred to a' and a' preferred to a", then it's more likely that a is preferred to a"), rendering existing peer prediction mechanisms not applicable.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In this paper, we design peer prediction mechanism for eliciting comparison data. We model individuals' private information of pair-wise comparisons as Bayesian strongly stochastically tran- sitive (Bayesian SST), which takes many widely used models (e.g. Thurstone (58), Bradley-TTery- 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 vonus-penalty payment is the only type of payment that induces a strictly truthful BNE, Information of individuals, i, J. and k, satisfies uniform dominance if, conditioned on any realization of agent i's information, the probability for i's information to agree with i's is higher than the probability for k's information to agree with i's. Bayesian SST allows us group three pairwise comparisons, a'), (a", aa)) and (a" a), together such that private information about these pairs satisfies uniform dominance. After identifying uniform dominance central structure for incentivizing truthful elicitation, 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].
Luce 4
38
Our contributions. Our work is 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. our mechanisms, truthful reporting forms BNE and yields a strictly higher payoff than any symmetric non-permutation equilibrium.
We identify a key structure of information, uniform dominance, as lever such that the simple bonus-penalty payment is the unique payment inducing strictly truthful BNE. This identification may offer a path for developing truthful elicitation mechanisms for other settings 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 independent interest.
We test our mechanisms dataset ( Even though these datasets do not perfectly satisfy our theoretical assumptions, our mechanisms still provide a stronger incentive for truthful reporting compared to misreporting.
real-world data (sushi preference dataset [26] 27 and Last.fm
Information elicitation has two settings according to whether verification is possible. Our paper focuses on elicitation without verification.
Related work.
For information elicitation without verification, Miller al. [4] 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) [7 is the first strongly truthful peer prediction mechanism, but requires complicated reports from agents (their private signal and predictions on other's 's reports). A series of works 48 assumptions of BTS but still require complicated reports from agents. Dasgupta and Ghosh [II] introduces the multi-task setting where agents are assigned batch iid tasks and only report their
49
67
66,
68
3
51 31 relax certain
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 [22
77]. 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. Spot- checking requires direct verification of the agent's '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 's reports improve model performance [
28
Additionally, the verification may have a general relation the agent's signal,
e.g., proper scoring rules
23
35 20
2 Problem Formulation
We discuss our model for eliciting comparison data in this section and defer the extensions to Section Given a collection of items A and set of strategic agents N. Agents privately observe

---

noisy comparisons between pairs of items. Our goal is to design mechanisms to truthfully elicit agents' private information. We will first introduce the information structure of agents' private information of pairwise comparisons in Section 2.1 and then define the information elicitation problem in Section 2.2
2.1 Bayesian SST Models for Comparison Data
We introduce Bayesian Strong Stochastic Transitivity (Bayesian SST) models capture the structure of agents' private information for comparison data.
Given the set of items A, the underlying unknown state about the items is 0 E e. 0 can be the vector of quality scores for the items (Example (..2) or a reference ranking (Example 2.4). 0 is drawn according to common prior Pe: 0 Po. Any realized has associated stochastic comparison two items a and a', To (a. a') and To stochastically take value -1, 1, with Pr[Z's (a, a') = Pr( =-1. For any 0 To is strongly stochastically transitive as defined below.
function To R - (-1,1). 1). For comparisons
(660 I3). A stochastic comparison function, Ω² - {-1,1), is strongly stochastically transitive (SS7) if for all a, a.a E A with Pr[T(a,a') = 1] > 1/2 and Pr[T(a', a") = 1] 1/2, we have
Definition 2.1
Pr(T(a, 1] > max = 11, a") =1]].
Intuitively, a comparison function is SST when for any three items a, a'.a'. if a is more favorable than a' and a' is more favorable than a", then is even more favorable than a". The concept of SST is a well-cstablished property of comparisons in social science and psychology (18).
Each agent i E N has the knowledge of (To)oeo and Pa. When asked compare pair of items (a, a'), the agent observes an independent draw according to the stochastic comparison function: S; To To(a, a'), where realization s; = represent item is preferred over item a' by agent i. We assume items are priori similar but ex-post distinct so that for all a' A, B[Ta(a, a')] = B[B(Ta(a, 0]] = and B[Ta(a,a') 0] # for e.
Examples of Bayesian SST models. Bayesian SST models are a general family of models that take many classical parametric ranking models, including Bradley-Terry Luce Thurstone (Case
V) 158. and Mallows model [39]. as special cases.
Example 2.2 (Bradley-Toe Terry-LLuce Thurstone model, and more [59 ). 8 = θ where each coordinate is independently and identically sampled from fixed non-atomic distribution R. and each item a have scalar quality 0, E R. Let F - [0. 1] be any strictly increasing function such fixed
that F(1) = 1 F(-r) for all E R. Conditional
Pr(To(a,a') = 1] = F (0a - Oar) for all a, a' E A.
This model recovers the Thurstone model 558 by setting F(r) 4(t) where 4 is the Gaussian CDF, and the Bradley- Terry-Luce model 4 by setting F(r) I+e' the sigmoid function. Moreover, this model also contains any additive random utility model (2 where T(a, a') = 0a + + > 0g + Z' with iid noise Z and Z', because we can F be the CDF of the difference of two iid noise.
Proposition 2.3. For any strictly increasing F and non 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 A and l 0 be dispersion parameter. Given a reference ranking 0 E Q, the Mallows m--mdee generate a ranking & E @ with prob- Ω² 0(a) 0(a') and d(a) s(a'))
ability Pr( o exp(-nd(O, σ)) where d(0,, Φ) = [{(a,a') Kendall's tau distance, and ((a) is the rank of item a. Therefore, to generate comparisons, we first sample uniform and
Σ d:b(a)=<(aa))
Pr(Ø), for a, e A.
Proposition 2.5. For any > 0, Mallows n-model in Example 2.4 with uniform distribution on reference ranking is Bayesian SST model.
The proofs for propositions and 2.5 are closely related to strong stochastic transitivity 54 provided in the appendix for completeness.
3

---

2.2 Peer Prediction Mechanism Design
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; = (Any av,) : i E N) where agent i E N gets pair of items e = (Am.aay) E R² to compare. Then each agent i e N privately observes the realization of the comparison (signal) 8; E {-1, 1]. which is an independent realization of o ( and reports 3; E {-1, 1) potentially different from her signal. We use S; S(a av,) to denote the random variable of agent i's signal, where the randomness of S(...) comes from both and Ta. Let S represent the random vector of all agents' signals, s (si)ieN be all agents' realized private signals and $ = (&: N y be all agents' reports. Finally, a peer prediction mechanism (Mi)ien takes all agents' reports & and pays agent i with (S) E R.
Each agent i's strategy is random function from her signal a report Ti : Sy + St. and the randomness of their strategies is independent of each other's and all signals. With slight abuse of notation, we write (s, S;) = Pr[S; 3; S = si] as the conditional probability of reporting š; given private signal sj. A strategy profile is collection of all agent's strategies. All agents are rational and risk-neutral, so they want to maximize their expected payments. Thus, given prior Pe. randomness of To and strategy profile o,, agent wants maximize her ex-ante payment denoted as Egr 8. (S) where S is the random vector of all agents' report that depends on the signals and strategy profile or.
We introduce three families of strategies, truth-telling. permutation, and uninformed strategy profiles, which are central to understanding effective peer prediction mechanisms.
A strategy o; is truthful (or truth-telling) if it is deterministic identity map, oz = S;. A strategy profile truthful if all agents' strategies are truthful.
A permutation strategy profile is where agents simultaneously relabel their signals and then report the relabeled ones. permutation strategy indistinguishable from truth-telling unless the peer
prediction mechanism has additional knowledge about the prior signal distribution. (33)
Finally, strategy is uninformed if has the same report distribution across all signals, and is informed otherwise. Common examples include consistently reporting all signals as a constant value, such as or -1, or using a random report regardless of the signal. Uninformed strategies are undesirable as the reports bear relationship to the private signals.
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 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 non- truthful 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 ss 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
3 Bonus-penalty Payment Mechanism for Comparison Data
We now propose a bonus-penatyy payment mechanism for eliciting comparison data. The mechanism makes use of bonus- conus-penalty payment function, which can be seen as an agreement payment and introduced by Dasgupta and Ghosh [T in different context (see discussion in appendix A)
Formally, for any 3, $y. Sk f-1, 1), the bonus-penalty payment function
UBPP (5 Sj. 8x) S;55 3 = 2 (1[3; 3,] 1[3 3x.)
(1)
which rewards when the first input agrees with the second but punishes when it agrees with the third.
Konn 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.

---

Mechanism Juses the bonus penalty payment eq. ① for each agent i by carefully choosing agent and & such that agent j's signal more likely agree with agent i's than agent k's signal is. The crux of finding such pair of agents is to show that if agent prefers item over a', she would expect that others will prefer any third item a" over a', and prefer a over a". Thus, if agent j has pair (a".a') and agent & has pair (a", d), then agent j's signal is more likely to take the same value as i's than agent k signal is. This is the main idea behind the proof of Theorem 3.1| where we establish the symmetrically strongly truthfulness of Mechanism [ To ensure the existence of such pairs are assigned, we require the assignment to be admissible where for all (a.a') E &, there exists a" E A so that (a", d') and (a" .d) E
Mechanism 1: BPP mechanism for comparison data
Input: Let A be a collection of items, & be an admissible assignment, and & be agents' reports.
for agent E N with pair e (an, av;) (a, a') do
Find a" E A and two agents j and k so that ej = (a",a' and ex = (a"..), and pay agent i
Mi( U RPP (3 $,, 3k) 8 S,Sk.
(2)
Theorem 3.1. Given collection of items A and a set of agents N with |A), 2 3, for any admissible assignment matrix & and Bayesian SST model with (To)oee and Pe, the BPP mechanism for comparison (Mechanism [ is symmetrically strongly truthful.
We defer the proof of theorem 3.1 to section The admissible condition imposes little overhead on
downstream learning problems, including rank recovery [25] and identification of the top k items [[5]. Specifically, the size of assignment & 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,L, we can construct an admissible superset & that introduces a constant factor overhead and can recover ML C & M
We remark that the bonus-penalty payment function eq. can be seen as a boolean function for transitivity 45]; see remark 3.2 for a formal statement. Hence, theorem [.1 implies that agents' manipulations can only decrease the probability of transitivity among their reports.
Remark 3.2. Note that a deterministic comparison function 1: AxA - (-1, 1) satisfies transitivity on three items a', .a" A if and only if ((a, ((',(('),,,))) "aal(aaa"")tttta aa"),(a",,,,........ a) are not all equal, that is NAE(I(a. a'), (a', a") ((",,((a,a))) a)) = where
1
1
NAE(W1, W2, wa) = 4 wIW WIW3
W3
W2W3-
4
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. is equivalent to the above transitivity test when agents are truth-telling. Formally.
S(d',
3 1
4 (S(a, d") S(a, S(a"" "a aadda"""ss""
4
1
3 +
(S(a, a'ssaa"""aa"""aaa a)) S(a,aaaaaaa0 S(a.a')S(a" .4) +
"(a",a")S(a".ee -Saa",
4
4 4
3 =7 (Nis) - -188)-1558) + I " 155 (s) 1
(truth-telling)
Therefore, arg max, EINAE (3;, -S SR)(S: = s/ arg max; E (3, + 4 sy] arg max; (I,, S,. St) = st
2Specifically, given any assignment E0 can construct a superset & so that for any (a,a') E find an arbitrary a" # a, and add (a, a') (a',a), (a, (a", (a",a), (a', a"), (a".a") into &. Thus, & is admissible and most six times larger than g
5

---

4 Proof of Theorem 3.1: from Bayesian SST Model to Uniform Dominance
To prove theorem 3.1
we formalize the idea that agent j's signal is more likely to agree with agent i's than agent k's is as what we call uniform dominance in definition 4.1 We 'llll show that any Bayesian SST model satisfies this property. Then, we 'll prove that BPP mechanism is symmetrically strongly truthful when agents' private signals satisfy uniform dominance.
S..,s,,J)) S2) E (-1, with joint distribution P. uniformly Definition 4.1. Given a random vector (S S,.
dominates S₁ for S; if Pr[S;
S 1] Pr[S2 1 S; = IJ and Pr[S, -1 S; = Pr[Sx = 11 S -1.. We call such an ordered tuple (S.. S uniformly dominant tuple
Lemma 4.2 shows how to identify uniformly dominant tuples under Bayesian SST models.
Lemma 4.2. Under any Bayesian SST model, for any agent i and items a, a' and a", agent j signal Sj S(a", s() uniformly dominates agent k's signal S S(a", a) for signal ((a,a').
In other words, under any Bayesian SST model, the distribution of S(a, S(a", S.). a) satisfies uniform dominance for any a, aa.a". In the rest of this section, we can view (S,, S. St)) as an abstract random vector with some joint distribution P.
We now establish some implications of uniform dominance on the bonus-penalty payment. Lemma 4.3 shows that truth-telling 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).
Lemma 4.3 (Truthfulness). Given uniformly dominant tpll (Si, j.. Sk) with distribution P. for all 8 E 13,, 8j = arg max Bp [UPP (3;, Sk) S; = si] and Ep [U (S.. > O.
Lemma 4.4. Given uniformly dominant tuple (Si, j.. with joint distribution P if agent j and k both use an uninformed strategy o so that S, = (S and S₁ = (St), all s; and &; in (-1, 13, Eo. |
Ss (3,
| S = = = =0.
Lemma 4.5. Given uniformly dominant tuple (S Sj. St)) with distribution foror any strategy o and 8 E 1- when agent] j and k both use or, arg max B..P arg g, (or(s, 8,) (:))
S = sy]
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 (S, Sy. S&), not necessarily derived from the Bayesian SST model. This offers a path to generalize our mechanism for comparison data to other settings.
By lemma 4.2 for any agent i, the associated agent j's signal S S(a", "aa",dl a') uniformly dominates the associated k's signal S& S(a", .a) for signal S; a().a)) By lemma 4.3 if agent j and & are truthful, agent i's best response is truthful reporting, so truth-telling is a BNE
Proof of theorem 3.7
Now show that all other symmetric equilibria are permutation uninformed equilibria. For any symmetric equilibrium o = (or) so that everyone uses the same strategy 0r, = o for all i E N. is not deterministic so that orss, s), o (s. > 0 for some {-1, agent / must be indifferent between reporting s and -s when getting S; = s. (s, (--s, = os, -)) - (--s.-ss) -s) by lemma 4.5 This means sss,s) = s) and o(s, -s) (--s.-s) and is uninformed strategy. If the strategy is deterministic, there are two cases. If (s)) = (--)) the strategy is also uninformed. If (s)) (--)), is either truth-telling + s or flipping + -s for all
Finally, by lemma 4..4 any uninformed equilibrium's expectation zero. Additionally, because eq. ! is invariant when all inputs are flipped, the truth-telling and flipping/permutationn equilibria has the same expected payment which positive by lemma
If we view S and St as two statistical tests for binary event Sj, the two inequalities in definition 4.1 say that Sy has better type 1l and type error than Sş respectively.

---

5 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 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.
5.1 Bonus-penalty Payment Mechanisms for Networked Data
Uniform dominance implies agent i's signal is more likely to agree with agent j's than with agent k'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 (V, E) be a graph of agents in V, å 1) from all agent's reports.
for agent i E V do
Find agents j (friend) and (non-friend) so that (i. but (i, k) @ E, and pay agent
M(( = UBP (Si, $x) 3k) 8 - S,8k.
Below, we provide 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. Formally, an Ising model consists of an undirected graph (V, E) and correlation parameter Bı, 2 for each edge (i,j) E E. Each agent is a node in the graph, N = V, and has a binary private signal (1 or -1) jointly distributed as the following: For = (St)svv (-,, Pr = s] cxp(H((s) where the energy function is (s)) = EiEDEE Si.j
Theorem 5.1. If agents' signals are sampled from an Ising model on undirected graph (V, E) with 2B correlation parameters B, Mechanism 2 is symmetrically strongly trutfful, when J > In 2damp4
20
where B = (i, Br.j, B (E Br.j. and d is the maximal degree of graph E).
Mechanism D does not require knowledge about parameters of the Ising model, but only the connection of the network (V, E). 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, 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 show that for any agent i, for all agent j with (i. E E and with (i, k) & E, i's signal uniformly dominates & t's signal for i's signal. Because the energy function (s) above remains invariant when the signs are flipped,
Pr[S; 1] = Pr[S; = 1] Pr[SA = 1] = 1/2, it is sufficient to prove that
Pr[S; = S 1 > Pr[S, = | S = 1].
4
We then prove 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[S, = 1 S, =1] happens when j is the only friend of i. For the right-hand side, we use Weitz's self-avoiding walk (65] and reduce any graph with maximum degree d into d-ary tree.
5.2 General Design Scheme and Uniqueness
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 identify uniformly dominant tuple for
7

---

Mechanism 3: General design scheme using BPP
Input:
Let & be reports from agents in N.
for agent E N do
Find two agents and k so that j's signal uniformly dominates k's for i's, and pay agent
M2( UBPP (3t, (x, 8,8J 3,
each agent, adopting the conus-penalty payment gives a symmetrically strongly truthful mechanism. We further show that the bonus-penalty payment is in some sense unique.
Theorem 5.2. for each agent the associated agent j's signal uniformly dominates k signal for i's signal, the above scheme symmetrically strongly truthful.
When an agent has multiple pairs of (/1, fi...)...... .Jt kt) so that ji signal uniformly dominates ky's for i's for each I = 1,...., C, we may pay agent the average of bonus ponus-penalty payment all pairs (8) = Σi UBPP ($; J.- St,). This average maintains symmetrically strongly truthful guarantee while potentially reducing the variance in payments.
Theorem 5.2 shows that bonus- menus- payment is sufficient condition for designing good elicitation mechanisms for information structures with uniform dominance. We now prove is also a necessary condition: any payment that induces truth-telling must be an affine transformation of the bonus-penan canus-pnnaaty payment.
strict BNE under all uniformly dominant tuples
Theorem 5.3 (Uniqueness). A payment U {-1, 1)3 - R satisfies that, for all uniformly dominant tuples Sy. 8t = arg s|-.11 (U, Sx) SS = si). if and only if there exist A O and μ : 1)1 - R so that
S(, = AUBP (si, S). u(s), sk), for all SJ. (-1,1}
where choice of does not affect the of equilibria.
6 Experiments
We present experiments on real-world data to evaluate our models and mechanisms. We hope to cast insights 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 I and 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 particular value.
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 first-order stochastic dominance. This implies that the truth-telling strategy results higher average, quantiles (e.g., first quartile, median, and third quartile), and greater expectation of any monotone function on the empirical distribution than the other two settings. We provide additional
For both comparison and networked datasets (figs. T and
6.1 SUSHI Preference Dataset for Comparison Data
We consider preference data for collection of 10 sushi items (item set A) 226 27 and focus 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 model assumptions. 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 T compute each agent's 's payment under the truth-telling or uninformed strategy profile. For each agent i, we 1) randomly sample three items a, a', a" and

---

two agents J, k. 2) derive agent i's comparison on the first two items d') from her ranking, (and similarly for agent j's comparison on (a', aa'aa)). and agent k's comparison on (a. a)). 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. 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. I tests the second question if the agent has the incentive to deviate when every other agent is truthful. The truth-telliing curve is identical to the left column of fig. [ For unilateral deviation, each agent gets the above bonus-penalty payment when her comparisons uniform random bits. We plot the ECDFs of payments for both settings in the right column of fig. [ 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.
replaced by
ELUE of Payments
ELUP Psyments
bnth lefing 1n1 wdltfmmed
Iuth lefinng unibserri 5ex orton
04
0.5
0.4
0.4
0.2
0.-
-0.4
-20
60
62
266
-0.4
0.1
64
Payner
Figure 1: SUSHI preference dataset
6.2 Last.fm Dataset for Networked Data
We test our BPP mechanism on the Last.fm dataset from Cantador et al. [ 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 [. where every agent has the same chance to get both signals. Thus, the result can be seen as stress test for our mechanism even when the data deviate from the assumption of our theoretical results.
Figure 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. tests the first question. Each agent has binary signal about whether or not she listens to particular artist (Lady Gaga in this section). For the truth-telling setting, everyone reports her signal truthfully and gets payment by the bonus bonus-penalty payment (formally defined in section 5.1). For the uninformed setting, everyone gets the bonus-penalle 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 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 identical to the left column of fig- 2 For the unilateral deviation setting, each agent gets the bonus-penalty payment when she reports woaeeerr/noo--sstene uniformly at random. The unilateral deviation's 's payment worse than the payments for truth-telling, decreasing from 0.37 to near zero for Lady Gaga.

---

for Lady Gaga
Lady Gaga
2.4
butt-relling inntommdd
1.
ruth-teling
urtisteral sev
0.8
0.8
0.6
-1.0
-0.5
0.C
0.5
1.0
-2.0 -0.5
0.0
Paymant
Paymert
Figure 2: Last.fm dataset for Lady Gaga
7 Conclusion and Discussion
We introduce a symmetrically strongly truthful peer prediction mechanism for eliciting comparison data without verification and extend to eliciting networked data under Ising models. Our mech- anisms are evaluated using real-world data. A key insight from our work is the identification of structure we term "uniform dominance," which suggests path for designing mechanisms 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 typically more related than from different contexts.
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 '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 Despite this, our additional experiments in appendix F which relax the selection rule used in obtaining fig. [ 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 external incentives such minimizing others" rewards intentionally distorting rankings, While our mechanism may be extended to handle binary effort as suggested in previous work [1] 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 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 arise naturally.
From a technical standpoint, our approach involves several assumptions that can be generalized relaxed. Our Bayesian SST model, which relies strong stochastic transitivity, serves non-pan 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 be ensured in mechanism. For example, adding constant of to the payment function in eq. (2) ensures that the payment is either 2 or 0.
*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 outting-edge technology, and adopters, who favor stability, affordability, and ease of use. Their opposing preferences violate the a priori similarity assumption. Imagine early adopter whose payment in eq. ( depends on two late adopters. Since their preferences may differ significantly, the early adopter might have incentive misreport her preferences.
10

---

Acknowledgments
This research was partially supported by the National Science Foundation under grant no. IIS- 2147187.
References
[1] Jacob D Abernethy and Rafacl Frongillo. A collaborative mechanism for crowdsoureing prediction problems. Advances in neural information processing systems, 24, 2011.
[2] Hossein Azari, David Parks, and Lirong Xia. Random utility theory for social choice. Advances in Neural Information Processing Systems, 25, 2012.
[3] Aurélien Baillon. Bayesian markets to elicit private information. Proceedings of the National Academy of Sciences, 114(3))7958-7999 2017.
[4] Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4)3324 345, 1952.
[5] Mark Braverman and Elchanan Mossel. Noisy sorting without resampling. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium Discrete Algorithms, SODA '08, page 268-276, USA, 2008. Society for Industrial and Applied Mathematics.
[6] Noah Burrell and Grant Schoenebeck. Measurement integrity in peer prediction: A peer assess- ment study. In Proceedings of the 24th ACM Conference Economics and Computation, pages 369-389, 2023.
[7] Róbert Busa-Fekete, Eyke Hüllermeier, and Balázs Szörényi. Preference-based rank clicitation using statistical models: The case of mallows. In International conference on machine learning, pages 1071-1079. PMLR, 2014.
[8] Iván Cantador, Peter Brusilovsky, and Tsvi Kuflik. Second workshop information hetero- geneity and fusion in recommender systems. In Proceedings of the fifth ACM conference on Recommender systems, pages 387-388, 2011.
[9] Mingyue Cheng, Hao Zhang, Jiqian Yang, Qi Liu, Li Li, Xin Huang, Liwei Song, Zhi Li, Zhenya Huang, and Enhong Chen. Towards personalized evaluation of large language models with an anonymous crowd-sourcing platform. Companion Proceedings of the ACM Web Conference 2024, pages 1035-1038, 2024.
[10] Wei-Lin Chiang, Lianmin Zheng, Ying Sheng, Anastasios Nikolas Angelopoulos, Tianle Li, Dacheng Li, Hao Zhang, Banghua Zhu, Michael Jordan, Joseph Gonzalez, et al. Chatbot arena: An open platform for evaluating Iims by human preference. arXiv preprint 20X3::2403.04132 2024.
[11] Anirban Dasgupta and Arpita Ghosh. Crowdsourced judgement elicitation with endogenous proficiency. In Proceedings of the 22nd international conference on World Wide Web, pages 319-330, 2013.
[12] Constantinos Daskalakis, Nishanth Dikkala, and Gautam Kamath. Concentration of multilinear functions of the ising model with applications network data. Advances in Neural Information Processing Systems, 30, 2017.
[13] Donald Davidson and Jacob Marschak. Experimental tests of stochastic decision theory. Measurement: Definitions and theories, 17(2), 1959.
[14] Glenn Ellison. Learning, local interaction, and coordination. Econometrica: Journal of the Econometric Society, pages 1047-1071, 1993.
[15] Brian Eriksson. Learning to top-k search using pairwise comparisons. In Artificiall Intelligence and Statistics, pages 265-273. PMLR, 2013.
[16] Boi Faltings. Game-theoretic mechanisms for eliciting accurate information. In IJCAI 2022.

---

[17] Shi Feng, Fang- Yi Yu, and Yiling Chen. Peer prediction for learning agents. Advances in Neural Information Processing Systems, 35:17276-17286, 2022.
[18] Peter C Fishburn. Binary choice probabilities: on the varieties of stochastic transitivity. Journal of Mathematical psychology, 10(4):327-352, 1973.
[19] Kiriaki Frangias, Andrew Lin, Ellen Vitercik, and Manolis Zampetakis. Algorithmic contract design for crowdsourced ranking. arXiv preprint arXiv:23 10. 10.09974, 2023.
[20] Rafael Frongillo and Ian A Kash. dector-values property elicitation. In Conference on Learning Theory, pages 7 710-727. PMLR, 2015.
[21] Xi Alice Gao, James R Wright, and Kevin Leyton- Leyton-Brown. Incentivizing evaluation with peer prediction and limited access to ground truth. Artificial Intelligence, 275:618 668,, 2019.
[22] Hans-Otto Georgii. Gibbs measures and phase transitions. Walter de Gruyter GmbH & Co. KG, Berlin, 2011.
[23] Tilmann Gneiting and Adrian E Raftery. Strictly proper scoring rules, prediction, and estimation. Journal of the American statistical Association, 102(477):359-378 2007.
[24] Leo Goodman. Snowball sampling. The annals of mathematical statisties, pages 148-170, 1961.
[25] David R Hunter. Mm algorithms for generalized bradley-terry models. The annals of statistics, 32(1):384-406, 2004.
[26] Toshihiro Kamishima. Nantonac collaborative filtering: recommendation based on order responses. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 583-588, 2003.
[27] Toshihiro Kamishima and Shotaro Akaho. Efficient clustering for orders. In Sixth IEEE International Conference on Data Mining- Whiing--Wrosspps (ICDMW'06), pages 274-278. IEEE, 2006.
[28] Sai Praneeth Karimireddy, Wenshuo Guo, and Michael Jordan. Mechanisms that incentivize data sharing in federated learning. arXiv preprint arXiv:2207.04557, 2022.
[29] Yuqing Kong. Dominantly truthful multi-task peer prediction with constant number of tasks. In Proceedings of the fourteenth annual acm-siam symposium on discrete algorithms, pages 2398 2411. SIAM, 2020.
[30] Yuqing Kong and Grant Schoenebeck. A framework for designing information elicitation mechanisms that reward truth-telling. CoRR, abs/ abss/1605.0121, 2016. http::/ttt///r
org/abs/ 1105../165...0 01021
[31] Yuqing Kong and Grant Schoenebeck. Equilibrium selection in information elicitation without verification via information monotonicity. In 9th Innovations Theoretical Computer Science Conference (ITCS 2018). Schloss-Dagstuhl-LLettt
Zentrum für Informatik, 2018.
[32] Yuqing Kong and Grant Schoenebeck. Water from two rocks: Maximizing the mutual infor- mation. In Proceedings of the 2018 ACM Conference on Economies and Computation, pages 177-194, 2018.
[33] Yuqing Kong and Grant Schoenebeck. An information theoretic framework for designing information elicitation mechanisms that reward truth-telling. ACM Transactions on Economics and Computation (TEAC), 7(1):1-33, 2019.
[34] Julia Kreutzer, Joshua Uyheng, and Stefan Riezler. Reliability and learnability of human bandit feedback for sequence-to-sequence reinforcement learning. arXiv preprint arXiv: 1805. 10627, 2018.
[35] Nicolas S Lambert, David M Pennock, and Yoav Shoham. Eliciting properties of probability distributions. In Proceedings of the 9th ACM Conference on Electronic Commerce, pages 138,138, 2008.
12

---

[36] Yang Liu, Rixing Lou, and Jiaheng Wei. Auditing for federated learning: A model elicitation approach. In Proceedings of the Fifth International Conference on Distributed Artificial Intelligence, DAI '23, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400708480. doi: 10.1 00.1144/36627766.6676633 URL. httpt::/p//: wrg/10.g....ooo http:////o...//.....11 1145/ 3627676. 3627683
[37] Yang Liu, Juntao Wang. and Yiling Chen. Surrogate scoring rules. ACM Transactions on Economics and Computation, 10(3):1-36, 2023.
[38] Duncan Luce. Individual choice behavior: A theoretical analysis. Courier Corporation, 2005.
[39] C. L. Mallows. Non-null ranking models. i. Biometrika, 14412): 1957. ISSN 00063444. http:://www.
arggsstablee2333244
[40] Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415 2001.
[41] N. Miller, P. Resnick, and R. Zeckhauser. Eliciting informative feedback: The peer-pred peer-prediction method. Management Science, pages 1359-1373, 2005.
[42] Nolan Miller, Paul Resnick, and Richard Zeckhauser. Eliciting informative feedback: The peer-prediction method. Management Science, 5 5199:1155-1137, 2005.
[43] Andrea Montanari and Amin Saberi. The spread of innovations in social networks. Proceedings of the National Academy of Sciences, 107(47):20196-22) 20201, 2010.
[44] Mare Mézard and Andrea Montanari. Information, Physics, and Computation. Oxford Univer- sity Press, 2009, ISBN 9780198570837. doi: 10. (01109//hcppo0000007709999977770 URL
00..0011.00111. org/ 10 w0w3//9993//..... ost. /ttp//999819997733777777 .01.000.0000 0001
[45] Ryan O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014.
fooleanfunctions.
[46] Kent Harold Osband. Providing Incentives for Better Cost Forecasting (Prediction, Uncertainty Elicitation). University of California, Berkeley, 1985.
[47] Drazen Prelec. A bayesian truth serum for subjective data. science, 306(5695):462-4666, 2004.
[48] Goran Radanovic and Boi Faltings. A robust bayesian truth serum for non-binary signals. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 27, pages 833-839, 2013.
[49] Goran Radanovic and Boi Faltings. Incentives for truthful information elicitation continuous signals. In Proceedings of the Tweety-Fightt AAAI Conference on Artificial Intelligence, pages 770-776, 2014.
[50] Grant Schoenebeck and Fang- Yi Yu. Learning and strongly truthful multi-tast -asti peer prediction: variational approach. In 12th Innovations Theoretical Computer Science Conference (ITCS für Informatik, 2021.
202/) I). Schloss
[51] Grant Schoenebeck and Fang-Yi Yi Yu. Two strongly truthful mechanisms for three heterogeneous agents answering one question. ACM Transactions on Economics and Computation, 10(4):1-26. 2023.
[52] Grant Schoenebeck, Fang-Yi Yu, and Yichi Zhang. Information elicitation from rowdy crowds. In Proceedings of the Web Conference 202/, pages 3974-3986, 2021.
[53] Sören W Scholz, Martin Meissner, and Reinhold Decker. Mcasuring consumer preferences for complex products: A compositional approach basedonpaired comparisons. Journal of Marketing Research, 47(4):685 698, 2010.
[54] Nihar Shah, Sivaraman Balakrishnan, Aditya Guntuboyina, and Martin Wainwright, Stochas- tically transitive models for pairwise comparisons: Statistical and computational issues. In International Conference Machine Learning, pages 11-20. PMLR, 2016.
13

---

[55] Nihar B Shah, Joseph K Bradley, Abhay Parekh, Martin Wainwright, and Kannan Ramchandran. case for ordinal peer-evaluation in moocs. In NIPS workshop on data driven education. volume 15, page 67, 2013.
[56] Victor Shnayder, Arpit Agarwal, Rafael Frongillo, and David C. Parkes. Informed truthfulness in multi-task peer prediction. In Proceedings of the 2016 ACM Conference on Economics and Computation, EC' 16, pages 179-196, New York, NY, USA, 2016. ACM. ISBN 978-1-4505 1-400- 3936-0.
[57] Victor Shnayder, Arpit Agarwal, Rafael M. Frongillo, and David C. Parkes. Informed truthfulness in multi-task peer prediction. CoRR, abs/1603.03151, 2016. URL http:
Sarxiv.org/aat htte/abb/16033... 03151
[58] Louis L Thurstone. A law of comparative judgment. In Scaling, pages 81-92. Routledge, 2017.
[59] Amos Tversky and J Edward Russo. Substinutability and similarity in binary choices. Journal of Mathematical psychology. 6(1):1-12, 1969.
[60] Stephan Vail. A stochastic model for utilities. Unpublished manuscript, 1953.
[61] Luis Von Ahn and Laura Dabbish. Labeling images with a computer game. In Proceedings of the SIGCHI conference on Human factors computing systems, pages 319-326, 2004.
[62] Luis von Ahn and Laura Dabbish. Designing games with purpose. Commun. ACM, 51(8): 58-67, aug 2008. ISSN 0001-0782, doi: 10. 10.1445//377704413777799 URL https://doi
org/10.
1378719
[63] Waggoner and Yiling Chen. Output agreement mechanisms and common knowledge. In Proceedings of the AAAI Conference on Human Computation and Crowdsourcing, volume 2, pages 220-226, 2014.
[64] Jiaheng Wei, Zuyue Fu, Yang Liu, Xingyu Li, Zhuoran Yang, and Zhaoran Wang. Sample clicitation. In International Conference Artificial Intelligence and Statistics, pages 2692- 2700. PMLR, 2021.
[65] Dror Weitz. Counting independent sets up to the tree threshold. In Proceedings of the thirty- eighth annual ACM symposium on Theory of computing, pages 140-149, 2006.
[66] Jens Witkowski and David C. Parkes. A Robust Bayesian Truth Serum for Small Populations. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI 2012), 2011.
[67] Jens Witkowski and David C. Parkes. Peer prediction without common prior. In Proceedings of the 13th ACM Conference on Electronic Commerce, EC 2012, Valencia, Spain, June 4-8, 2012, pages 964-981. ACM, 2012.
[68] Peter Zhang and Yiling Chen. Elicitability and knowledge freee elicitation with peer prediction. In Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems, pages 245 252. International Foundation for Autonomous Agents and Multiagent Systems, 2014.
[69] Yichi Zhang and Grant Schoenebeck. High-effort crowds: Limited liability via tournaments. In Proceedings of the ACM Web Conference 2023, WWW '23, page 3467-3477, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 978145039411 3543507.3583334, URL http::://ool http:///00..../11.../
doi: 10.1
org 1145//543077 3583334
[70] Shuran Zheng, Fang-Y Yi Yu, and Yiling Chen. The limits of multi-task peer prediction. In Proceedings of the 22nd ACM Conference Economics and Computation, pages 907-926. 1.21.
14

---

A Further discussion on BPP payment
In this section, we discuss the connection of bonus-penalty payment and existing peer prediction mechanisms. First, if we substitute the third input with uniformly random bit, denoted as & = Z ~ {-1,1) 1), the bonus-penall payment simplifies to the agreement mechanism 63 one of the most basic peer prediction mechanisms,
BPP (3,, S 2) 3,3, 21[3; = 8,] 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- penulty payment eq. T originally proposed by I for the multi-task setting. Our BPP mechanism in Mechanism 3 can be seen as 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 sf) and reports 57) and Julia has (s). s²) and reports (7) where (s). are iid from random vector (S;,S,) Isabel and Julia decide their reports on each task using random function
Ti ojj [-1, (-1,1) respectively. Dasgupta and Ghosh [1I] use the following payments for Isabel
1 |[s = 1[5) = 53) - UBPP (s). 8).
The payment is special case of Mechanism by taking the second input as 8) and the third input as 83. Additionally, S) uniform dominates 53 for s if and only if
Pr[S, = S = Pr[S, 1]. and Pr[S, = -1 | S = -1] Pr[S] -1]
which is called categorical signal distributions [57]
Finally, similar to Shnayder et al. payment to
[57 we may extend to non-binary signal setting by extending the
(5,.3, UBPP(3,
BPP
= 2 (1[5, = = - 1[3; = 5x])
and the definition of uniform dominance to the following.
Definition A.1. Given random vector Sy E Ω on discrete domain, say Sy uniformly dominates Sş for S; if
Pr[S) = S, = Px[S3 = S = s] > and Pr[S, = s' S Pr[S2 s' S < 0
for all s' e Q with # s'.
However, the guarantee for truth-telling (informed truthfulness) is weaker than the binary setting.
Theorem A.2. Given any discrete domain Q2 if for each agent i the associated agent j's signal uniformly dominates k k's signal for i's signal (definition A.7 Mechanism 3 scheme is symmetrically informed truikful so that
1. truth-telling a strict equilibrium, and
2. each agent's '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. First truth-telling is a strict equilibrium, because if S; =s,
arg max B U BPP Ss. S, =]
arg max Pr[S, 3 S; s] Pr[S $ S; =]
(by definition A.1
15

---

Additionally, because Pr[S, s S; S; = s] for all s' s. summinn over all possible s' e on both sides gets Pr[S] S s] Pr[Sk = S = s] > 0 and
= | S = s] > Pr[S) 5 S s| - Pr(St
B SS. 0.
For any informed equilibrium, by a direct computation B (S, Sy) =0. Finally, show that the auth-telling has the maximum expected payment for each agents. When all agent use a strategy or : Ω - Q, agent i's expected payment is
Σ
Pr[S) = s, (, 8/) BPP (8,,
( S).)) xx]
$
=2
Σ
Pr[S; s,),
Σ (Pr[S) = S s; Pr[S> = S; = (s,)
=2
Σ
Pr[S; = s,}
Σ
(s (s) (Pr[)) = S = s, Pr[S> = s S = s,]))
$,3e
Let (s) = (s, (s) 3;) which is between and 1, because fa, (s)
Σie0 (St 3;) Es, 1. Then the expectation becomes
Σ
Pr[S; = s; B BPP (3:, SJ. Sc) S; = si
Nr FQ
=2
Σ
Pr[S; = s; Σ
[Pr[S] s S = s Pr s S; = =;s= (s)
sel
<2
Σ
Pr[S: = s;] (Pr[S] S = - Pr[S, |s: = =s,)))
S,E
=B
BPP SJ. Sx)
The inequality holds because fa, E [0, 1] and definition A.1
Therefore, we complete the proof.
B Proofs in Section 2: Bayesian SST model and other models
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.
Proof of proposition 2.3 First given R for all distinct a,a', a" E A, Pr[To(a, a') =
1], Pr[To(a' a")) T] 1/2 implies that 0a 0 and far Pa becuase F is strictly
increasing and F(0) = 1/2. Because fa 0r 0. 0a + 0o 0," > max(O, fa 0, - 0a
we have
Pr[To(a,a") 1] =F )ar))
> max F(A, F(,) -rr) max Pr[To a') 1], Pr[To(a' (aap(aaa"")" =]
and thus To is strongly stochastically transitive for all with distinct coordinates which happens surely as y is non-atomic. Finally, since the distribution on 0 is exchangeable on each coordinate, [To(aa a')] 0 for all a."
Proof of proposition 2.5 a'.
First given 0 e O for all distinct a, a' E A. if the rank of a is higher than
Pr[To(a, a') = h,, (ac((aa)(((il))))) ((a)+(()++)))) h,,((a')) E(a))
where (x)(x)= T-exp(-mpx by Busa-Fekete al. 7
Claim B.1. For any 17 and E Zoo, the difference h + 1) h,((x) is increasing and larger than 1/2 where (x) T-axp-nxxi'
16

---

By claim B.1 Pr(To(a,a') = 1). 1] 1/2 implies that 0(a') - 0(a) > 0 and
-ax(0("") 0(a") O(a') O. Thus, - 0(a)), and
max =maxxdcch--a()------0000-------- max "1
0(a) + 1(0((')-000)
where the second inequality due to claim B. Therefore, To is strongly stochastically transitive for all B. Finally, [ (T a']]] for all a since 0 is uniform distribution rankings.
Proof of claim B. We first prove that the function M, = I-exp(-ppx] is increasing and strictly
convex on 2 0. Because hn (x)(x) 7 (1x),, for n, sufficient to consider 1j = First,
k((x) = > > 0, so ht increasing. Second, as (x(x)) = (1-e-x)) ((x)))))()))))))) to show (1-e-x32
hM (x) 0 for all 0, it is sufficient to show that gxx) (x - (x + 2)e 0. Because
(0)) = O and g' ox(x) = (x + l)ee O, gx) for all > O. Therefore, h1 is strictly convex.
On the other hand, (x, > (x,xx))) for all by convexity, and , (2) (1)
Ite which completes the proof.
C Proofs in Section 3 and 4
C.1 Uniform dominance from Bayesian SST
Proof of lemma 4.2 With prior similar assumption for Bayesian SST model, only need to show
Pr[S(a",a') = S(a, = = Pr[S(a", a) = S(a, = =].
(5)
and the other case Pr[S(a", a') - S(a. - > Pr[S(a",
(af(""aa) a) =-1 S(a,a') = follows by symmetry. To prove eq. ( we can rewrite the conditional probability in expectations of To.
I PP([Vo(""''')
/ /P(To(a.d)=1|])ddP)
1 /P(TT((..a==110)dPP
(conditional independent)
-2
(a prior similar)
E B(To(a".a') (2)])]]]]]]]]1((.. |0]]]]))))]]]]111 10]+1 dPe
-2
(binary value)
2
1
/ [d)((]][[T((u.. |0] (Ta
-
[]] IdPe
-
B [To(a". dd) (T(aaa)) 0] IdPo.
(a prior similar)
Claim C.1. For any strongly stochastically transitive Ty on A, and distinct a, d'.a" e A
B[To(a, d') B [To(", [T) [To(a, d') | [T(aa" .a) 0).
With claim C.I we have
1
Pr[S(a", a') = 1]= = [TTo(a",d (8]][((aa)) | [0]
IdPo
! > B[To(a",a)) B [To a') 0) + IdP = Pr(S(d", = S(a,a') = 1].
This completes the proof of eq. 5 and thus the uniform dominance.
17

---

Proof of claim C.1 We let Q(a, a²) := B - = (0] for all a. a.a'. Note that @(a. a') By symmetry, let Q(a, a²) > 0. It is sufficient to show that
Of and only if Pr(Za(a. = 0] 1/2 and @(a, -Q(a'.a)
Q(a".a)) > Q(a".a).
If Q(a', "laa,aa)= > O. by definition 2.1 Q(a, a > Q(d',a") > 0 so Q(a",a)) ) > Q(a", a). Now consider 1(a', a"" 0. If Q(a"
Qa" .a') ) 0 > Q(a", a). If Q("". a) 0, have Q(a". a) > 0, Q(a, a') > 0, and thus Q(a", ,a) ) > Q(a" ,a) by definition 2.1
C.2 Uniform dominance and weak notions of stochastic transitivity
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 [S) is only weakly stochastically transitive but does not satisfy definition 2.T it exhibits uniform dominance.
Definition C.2 (13)). A stochastic comparison function. T: R (-1,1), 1), is weakly stochastically transitive for all a, a', a'"a" A with Pr[T(a, a') = 1/2 and Pr[T(a', ,a'd"""") = 1] 1/2,
Pr[T(a, a") = 1] 1/2.
Compared to definition 2.1 the weak stochastic transitivity only require the item is favorable than a". 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 O consists of all ranking on A with uniform prior where & maps each items to its value. Given 0 so that if ((a) > 0(a') > 0(a"),
Pr[To(a,a') 1] Pr[To(a', a") 1] 0.9 and (r[ a")
0.6.
Note that the model is weakly stochastically transitive, because item with larger value is fa- vorable and the weak stochastic transitivity is reduced to transitivity on the values. However, the model not strongly stochastically transitive, because Pr[To(a, a") = 0.6 max (a, a') I]. (T (a',aaa))) aa" = 1]]} = 0.9. Finally, as the rank has a uniform prior, the model satisfies 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
have
Pr[ , ,a) 1 \
B [To a') (Toaaa)) 10]+
2
1
6
2
but Pr[S(a", ((a,a') = 1] (1 (1+ 6d Therefore, have Pr[S(a", a') S(a,
1] Pr(S(a", 1 S(a. a') 1]. and show that (5) does not hold.
Though the above example shows that weak stochastic transitivity is not sufficient Below show popular weakly stochastically transitive model Braverman and Mossel [ has uniform dominance as in lemma 4.2
Example C.4. Let θ be the set of rankings on A and 17 > be a parameter. Given a uniformly distributed reference ranking 0 O, the noise ranking model [5] ensures that for all 0(a) 0(a')
1 +1
Pr[To(a, a')
Note that the above model does not satisfy the strict inequality in definition 2.1 but by direct computation, Pr[S(a", a') a()aaa))== 1] = [1 41²) and Pr[S(a", a) | 1]
4 which satisfies lemma 4.2
'In the above example. we can also decrease 0.9 to smaller number that satisfies both uniform dominance and weak stochastic transitivity.
18

---

C.3 Symmetrically strongly fruthful from uniform dominance
Proof of lemma 4.3 Suppose S, 1. Because Pr[S, 1|S; = 1] > Pr[SA 1|5; = Pr(s
-1|S; = 1] < Pr[S = S = I]. Therefore. arg e (-1.1) Pr[S; = B|S; = - 3,1S;
[] 1. Identical argument holds for the case of S; = -1 which completes the proof.
Additionally, the expected payment of truth-telliing is
E | SJ.
Σ Pr[S; =s
Σ
Pr[S,
sj, Sk 5k S = = Sj.
=2
Σ Pr[S; si]
Σ
Pr[S; sj. sk S s; ssa]
[[s; sk))
53.32
22
Σ Pr[S; = s:1 (Pr[S) s S = s:l Pr[S = =s | = =
>
The last inequality holds due to definition
Proof of lemma 4.4
As or is uninformed, let u(s) = o(s,s) = (0(-s,)) and (r( = =o(s,-0)
o(-s.-s) for all s. (
Sx) = s/|= =
Σ (S, Σ (( -(8k) =0
8y.81
The first equality holds as the reports are independent of signals.
Proof of lemma 4.5
Bp. RUP
($ Sy. 5x) S si]
Σ
Pr[S, sj. Sk sk | S = silor ( BPP (
=2
Σ
Pr[S; S. s s s; 5,) (s 5k) (1[3, šy] -1[3, = =x,)
(by eq.
-2
Σ = - š 2 Σ
Pr[Sk sy S = s/ 8 1 = 3x]
$J.8
Sk.8k
-2
Σ (Pr[S, s = 5
= (s)))r(s, 1) 3]
(renaming dummy variables)
3.8
=2 >( (Pr[S) s S, v, - Pr( = S (s,)
Let Pr[s, s S = s,] Pr[S s; 5 = sy] > because S, uniformly dominates Sk
for S,. Additionally, Pr[S, -y S = = -Pr[Sa = - S sil = 1 Pr[[S = S
sy] 1 Pr[S2 = =; | s/ 5. We have
Bp,or [UBP (8, S,. St) =
2 Σ (Pr[S) = s| S; = =il -Pr[S = S; s)
=26 (o(s,, 31) o(-a, 8)))
so arg max; Bp. [UBP (5), S, Sx) S sy arg m (o(s,, 5,) (o(s,, $1)
which completes the proof.
D Proofs in Section 5.1
Before diving into the proof, we introduce some notations. We further introduce Ising models with bias parameter a e R.Y in addition to B where
H(s) Σ
BiisiSJ
Σ
aasi
LJEE
lcV
19

---

and pra, = cc ex)( for all configuration s. Given i E V, let the expectation and ratio be vi(a, = B [S:] [s; a.B
[s; = -1] and pi B) Pia, Pra.plS; -1]
-
a.
respectively which are monotone to each other. We will omit a, B when clear. Given a subset U S V, St {-1, 1) is configuration over the nodes in U, and Sy 1 if 1 for all U. We write Pr[-ISu = -ul. = and PijSe=su for the conditional probability, expectation and ratio when the configuration U is fixed as specified by SU.
A lower bound for LHS Informally, want lower bound the correlation between adjacent and j (friends). Note that as we remove edges (setting coordinates B to zeros), the correlation should decrease, and the smallest correlation between neighhoring nodes and j happens when E {(i, J) Lemma D.2 formalizes this idea using the following monotone inequality [44] Theorem 17.2).
Theorem D.1 (Griffiths' inequality). For any E V, vi(a, B) Bu, [Si] is non-negative and non-decreasing in all Bj.k z 0 and jj O with k V.
Lemma D.2. Given V and j. V, for all a. B. and B', if Be when (i and B² 0 otherwise, we have
(a, 2 (0. B') and Piis,- (a. 2 Pr,))=((a,B"))
Proof. First, note that can write the conditional expectation Ba SS |S 1] as marginal expectation. Formally, consider a² that a. a, if # j and 0² (rj + 17. Because 1 a is non-decreasing, 17 v;(a"", B) is -en-eacrgg by theorem D.1 In addition,
Præn,ple S = s] = Pra,p [S; Sj s] for all and Præ",p(S; = -1] 0(e" 22), so
Viss (a., B) = E, [S; {S =1] 1]= lim v, B).
70000
Similarly,
(a. =B, [S; |Sj = 1] lim vi BB). 170000
On the other hand, consider B so that Be Be if (i. and Bi, BB.j + d. By theorem D.I vi(a" B²) is non-decreasing in A for all Because 8 = B³ and B¹ = B. we have
\,,, = lim vi(a" s lim (a" B) = Vils,=1 (a. B) 174000
Because Pt T-
is monotone in vi, the second part follows.
Given B8 defined in lemma D.2 by some direct computation with a 0
Pis) (a. (a.,
B) Pns) B¹) 20r 20
(6)
An upper bound for RHS Now, need to upper bound the correlation between non-adjacent i and & (non-friends), We will use Weitz's 's self-avoiding walks reduction [65] to upper bound the correlation on general graph G by the correlation on trees.
Given a general graph G, and an arbitrary node i, we can construct the Self Avoiding Walk Tree of G rooted at i, denoted Aw (G, i), so that Pr[S; = 1 Su St:] is the same in G as in the tree. We outline the construction. TsAw (G, enumerates all self-avoiding walks in G starting at which terminates when it revisits previous node (closes a cycle). Then, Ts. () introduces 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 i. Note that if G has maximum degree d, Tsaw is a d-ary tree.
Theorem D.3 (665) For any a, B. node i E V, and configuration Sy on U C V.
Pr [S = 1 Su sul = Pr TSAw(G.)
[S = | = su)-
e.B
20

---

First, with the above theorem, we have = (a. B) = = Aw [S; Sx 1]. By the monotone property in theorem D.1 setting all two-hop neighbors U TsAw(G.) (recalled that any boundary conditions for AsAw (G. being at least three hops away) increases the conditional expectation,
Brs (G.)) [S; S2 = =] S (G.I) [S; Su = S, = 1].
Let be the tree by truncating As expectation is equal to the expectation on T.
level 2. By the Markov property of Ising models, the
B [S Sk 1] (G.)) [S; Sy 1] Br [S; Sy 1].
Finally, we can recursively compute the probability ratio pt (and thus expectation vi) on trees. Specifically, given rooted tree T", we define pr as the ratio of probabilities for the root to be +1 and -1 respectively, and pris, 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 tree T rooted at i with parameter (a. B) and boundary condition Su-
d
e 22 +
PT = e220
1
PT
2 + PT, S8
1=1
where Ji....,Ja la are children i and Ti is the subtree rooted at ji for all I.
By the monotone property in theorem D.I] the maximum right-hand side of eq. 7 happens when T is a complete d-ary tree with B = B. Therefore,
e 21d+1]B +
PMSS Pa.
(8)
e e2dB
Finally, with eqs. (6) and (8), we have pijs,= B) 2 2 implies eq. (4).
e2id-10+11 +
2 (ar (ar B) which
Remark D.5. Note that for any graph G there exists small enough B. so that the condition in
theorem 5.1 is satisfied, because the inequality become equality when B = 0. and aB d 0
28
In 2010111 06
The bound between B and necessary as shown in fig. On the other hand, by the Markov property of the Ising model, the majority of all neighbor's signals is sufficient statistic, and can show the majority all neighbor's ' signals are uniformly dominant to a non-neighbor's signal. Therefore, can get symmetrically strongly truthful mechanism by replacing j's reports with the majority of reports from i's neighbors.
E Proof of Theorem 5.3
The sufficient condition is done by lemma because
arg max E BUPPP (3, + (K) S =s] (-((-1,1)
arg max E (S, SJ Sx) SS; = si (
= arg max E [UPPP (5,, Sy. Sx) |s si 66(-1.1)
(1 > 0)
=S;
(by lemma 4.3
For the necessary, given U, define D(sj, sk) (U((,, + +U(1, sk)) for all sy and s4 in (-1, 1}. Hence
(j. (U)L.,),))--U---,,..... and μlsي, sk)
U(S..JJ, 5; Sk) μ(ك). sk). Vs, (-1.1)
(9)
21

---

111
122
1/3
Vo
Vn-1
14
Vn-22
Figure 3: As fixing any B.B. can construct a simple graph with V {vo.... ...,, ..no-. and E {(vo, vi), (vi, Fn-1) -l n 2] where agent vo and Fn-1 are not connected but share common friends. We can show that the correlation between So and Sn-1 converge to I as the number of common friends d increases, while the correlation between So and S is bounded away from 1.
Given joint distribution satisfying definition 4.1
we let p (S). Pr[S, Sk = s2 S; s;
and additionally write p" 10 ()
p".
Then definition 4.1 ensures that
(-1,1)
(-1,-.-1)
p'(1.-1) p² (-1, and (1 < (-1,
Because U is truthful for all uniformly dominant tuples, we have
0 <B [U(I, S; = 1| (U(-1. S; =1 =2 = Σ stsj.st)p'(ss. (s).s))
81-31
(10)
0 >B (U. S; = - - - = 2 Σ D(s) (1)
5j.5k
Suppose the following are true
D(1,-)==D(-11))>0 Let 1 = D(1,-)) > 0. By eqs.
(11)
= D(-1)=-(--.-1)==
(12)
and (12. we have
U(s Sj. 5k) 5; (s) 5x) SK) =d s:ss - -s)) S1)
(by eq.
9
(by eqs.
9 and [11
which completes the proof. Thus, we will construct three joint distributions satisfying definition to prove eqs. 11I) and (12).
The first joint distribution p" (Sj. sk) with 0 < 5 1/2
1/2+
0
1/2- 0
p = 1/2-
and p p- = 0
1/2+6 6
Then eq. 110 on the first distribution reduces
0 o,tp::/hheeeeciooooooooo""oooo""
D(11,))
As we take to zero, we prove -11,-))=-((11, Then plugging in with nonzero 6, we have
D -1) 0 and complete the proof of eq. ||
22

---

The second joint distribution P/ [s 5k) with 0 s 6 15.11. is
f 0
p - e
and p -1
3e
0
With eq. (IT). eq.
reduces to
0 <<(1- -01,--))-((-L1))
0 - (1)11))
- -D(1,)))-D(11,))
By taking e to zero, we prove D(1, = 0. We can prove (--1, -1) = 0 using the similar trick and complete the proof of eq. [12
F
Additional empirical results
F.1
Comparison data
Here we test if the dataset satisfy transitivity property. We denote the proportion rankings such that item is higher than item a' in the dataset by Paza'. If Pazar 1/2, Patsa" 1/2, and Pa>a" > 1/2, we say the triple items {a, a', a"} empirically satisfies transitivity. If Pasa' > 1/2, Pa'>a" > 1/2. and Pa>a" > max Pa>a'' Pa'>a"); ), say the triple of items {a, a',aaaa) empirically satisfies strong transitivity. We first test the transitivity of the SUSHI subdataset selected in section 6.1 We find that 100% of the item triples empirically satisfy transitivity, and 69.17% of the item triples empirically satisfy strong transitivity. This suggests that our transitivity assumption for the comparison data is mostly aligned.
Moreover, we conducted an experiment on the entire SUSHI dataset without any selection criteria and demonstrated the results in fig. 4 Observe that the ECDF of payments from original human users also dominates the payments under the uninformed strategy and the unilateral deviating strategy. This is consistent with our experimental results in section 6.1 However, there are two minor difference. First the separation of truth-telling from the other two is slightly less prominent than fig. with the selection criteria. This may be due to slightly lower degree of transitivity acToss agents with different backgrounds. In particular, we found the average value of Pasa" max (P Paza' Pa'>a" is 0.0559 without the selection criteria which is less than 0.0604 with the selection criteria in fig. Second, the fraction of agents receiving positive payments is slightly higher than in fig. [ (0.785 and 0.763 respectively). This aligned with or empirical (strong) transitively which are and 0. 0.7667 compared to the above I and 0.69117. 17. Furthermore, we also conducted experiments on other groups of users by changing the selection criteria. Those interested can refer to fig. 5 fig. and table for the results, which further verify the effectiveness of our mechanism.
Selection criteria
Number of users
Average utility
Fraction of positive utility
All (No selection)
5000
0. 138
78.5%
Female, 30-49, Kanto/Shizuoka
249
0.137
76.3%
Male. 30-49, Kanto/Shizuoka
185
0.167
82.2%
Female, 5-29, Kanto/Shizuoka
146
0.175
84.2%
Female, 50+, Kanto/Shizuoka
26
0.13
80.8%
Female, 30-49, Tohoku
30
0.174
83.3%
Female, 30-49, Hokuriku
23
0.105
69.6%
Table 1: Summary of truth-telling utility in appendix F.1
F.2 Networked data
Alongside fig. Figure and table empirical results for the top five popular artists in the dataset, excluding Lady Gaga, who are Britney Spears, Rihanna, The Beatles, and Katy Perry. All these settings show similar results. However, the Beatles' data less conclusive as the payment distribution under the uninformed strategy profile is close the truth-telling. This observation is
23

---

ECOI Payments
suth milnng iiithvmed
calling
00
0.3
04
0.4
0.2
0.
22
022 0.0
Paprtct, Amsontt
Figure 4: ECDF comparisons on all users without any selection.
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 Britncy 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 because many non-listeners have no listener friends, and payment is [(1 popularity p x 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, can the payment of deviation is the minus of the truthful payment, so that the ECDF is symmetric around 0.5).
2p is twice the
Artists
Fraction of listener
Average utility
Fraction of positive utility
Lady Gaga
32.2%
0.37
76%
Britney Spears
27.6%
0,420
82.6%
Rihanna
25.6%
0,422
83.4%
The Beatles
25.4%
0.137
68.5%
Katy Perry
25.0%
0.361
79.9%
Table
Summary of truth-telling utility appendix [2
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.
24

---

ECOF of Tayments
ECOT Payments
usidared
06
12
12-
143 Irg
1.0
108-1 kig
-02
ECDT Taumerts
ECBF Daemeris
1.5
10-
342 kng
3.4
3.4
Figure 5: In each of the rows, we present the ECDF comparisons after changing the selection criteria for the user group as follows: from female to male, from ages 30-49 to ages 5-29, from ages 30-49 to ages 50+, respectively.
25

---

07
102
0.2
14.
Figure 6: In each of the rows, we present the ECDF comparisons after changing the location criteria for the user group as follows: from mostly living in Kanto or Shizuoka to Tohoku until age 15, and from mostly living Kanto Shizuoka Hokuriku until age 15, respectively.
26

---

[CD1 for Brtney Spears
ECOF for lrtrey Speers
mumnteing uniformdd
untatara decitton
0.
2.
025F
6007
-2.5
-3.0
-2.
0.5
0.3
3.2
-3.
-3.0
-0.5
0000
3.0
ECF for Rihamns
EC for Rihanns
3.0
mmn-oeing uniformed
2.0
must-telin
undatera desition
02
0.2
0.0
5.0
-1.5
-3.5
-0.5
0.0
3.0
-1.5
-3.5
-0.5
0.0
Pryitect
ECDF for The Beatles
ECDF for The Buacles
toa uniformed
Inttteling uniilow diaiiion
0:2
-1.5
-1.0
3.0
Payment
Paymennt
ECCF
ECDF
0.11
0-1
Dayment
Payment
Figure 7: Last.fm dataset for other top five popular artists excluding Lady Gaga.
27

---

Truthful payment accross top fifty artists
1.0
30
fraction of non-negative payment
0.9
Populaniy (percent)
0.8
0.7
0.6
0.5
10
0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.35
0.40
average payment
Figure 8: Average payment and fraction of positive payment under the truth-telling across top fifty popular artists.
28

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], , [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper the relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] pprovided proper justification is given (e.g., "error bars are not reported because would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Our claims accurately reflect the contributions and scope of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: section 7, we discuss potential future research directions, which are the limitations of our current work.
29

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, authors should discuss possible limitations of their approach to address problems of privacy and faireess
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We present all the assumptions. The complete proofs are provided in the appendix.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: The code is uploaded in the supplementary material. All the information required to reproduce the experimental results is provided.
Guidelines:
The answer NA means that the paper does not include experiments.
30

---

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 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 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 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 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 NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions 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.
Please see the NeurIPS code and data submission guidelines (nttps://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7 /ttppp.cc/pbllc/guudeeee http://oeeeubbissnooooooooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
31

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: Most of these details 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 the core the paper to 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, supplemental material.
7. Experiment Statistical Significance
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 accompanied by error bars, confi- dence 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.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 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 out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We believe the computer resources are not relevant to our main contributions.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
32

---

The paper should provide the amount of compute required for each of the individual experimental runs as well 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 failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The research conducted in our paper conforms with the NeurlPS 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 deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. 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 no societal impact of the work performed.
the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt 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 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 (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper deseribe 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)?
Question:
Answer: [NA]
Justification: We believe this paper poses such risks.
33

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The datasets used in this paper are mentioned with URLs and the licenses and terms of use are properly respected.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each
For scraped data from a particular source (c.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pww.::s...aaseiiiia...... thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information is available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
34

---

Answer:
[NA]
Justification:
The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS 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.
35


Reviews:
[{"review_id": "p9RjPo0dJQ", "reviewer": "Reviewer_c3bN", "summary": "* This paper proposes a peer prediction mechanism for elicitation of comparison data.\n* 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$.\n* 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.\n* 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$.\n* 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.\n* 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.", "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?\n* “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?\n* 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?)\n* 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)\n* 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": "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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* Presentation is clear and concise. Intuition is given for formal proofs.\n* The concept of uniform dominance is interesting and seems to be generalizable.\n* Theoretical results seem to be quite general, and applicable to many pairwise choice models.", "weaknesses": "* Empirical evaluation compares truthful reporting against benchmarks which seem relatively “simple” - uninformed random reporting, as opposed to more sophisticated forms of strategic behavior.\n* 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.\n* 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable input.\n***\n**Question 1**: What are the relations between Mechanism 3 and Mechanisms 1 and 2? Is it possible to think about Theorem 3.1 and Theorem 5.1 as corollaries of Theorem 5.2?\n\n**Answer**: Mechanism 3 offers a general scheme for designing peer prediction mechanisms, which requires finding uniformly dominant\ntuples. Identifying tuples that are uniformly dominant for different settings is a critical and nontrivial\ntask. Mechanism 1 and mechanism 2 identify uniformly dominant tuples for the pairwise comparison\nsetting under Bayesian SST model and networked data setting under the Ising model respectively.\nTheorem 3.1 and Theorem 5.1 can be viewed as instantiations of Theorem 5.2, with identifying and\nproving uniformly dominant tuples in the respective settings as a main contribution.\n***\n**Question 2**: What are the implications of a priori similar but ex-post distinct?\n\n**Answer**: The a priori similar assumption implies that agents do not favor any item before observing their noisy comparison. Our\nmechanism allows agents to know the assignment $\\mathcal{E}$ in advance. The a priori similar assumption\nmeans that, before observing the noisy comparison, agents do not have strict ordering of any pair of\nitems even with the knowledge of the assignment $\\mathcal{E}$. This assumption can be relaxed if we further\nrandomize the assignment $\\mathcal{E}$ by a uniform random permutation.\n\nThe ex-post distinct assumption requires that the realized state $\\theta$ is distinct for each item. Under\nthe Bradley-Terry model (a special case of our Bayesian SST), this assumption means that no two\ncandidates have the same realized scalar quality. The Mallow’s model (another special case of ours)\nalways satisfies this assumption.\n***\n**Question 3**: Limited liability? (e.g. if the agent can choose not to participate in the game when they may get\nnegative reward) \n\n**Answer**: We do not require our mechanism to penalize users (i.e. give them\na negative payment) because any positive affine transformation of the payment function preserves the\nequilibrium. For example, we can add a constant of 1 to the payment function in Equation (2). This\nensures that the payment is either 2 or 0.\n***\n**Question 4**: Possible typo: ...Percentages seem to add to more than 100%.\n\n**Answer**: Our experiment shows the\nhistogram of agent’s payment under three different settings: (1) Truth-telling, where every agent uses\nthe truthful strategy, we treat the original data as agents’ true preferences. (2) Uninformed, where\nevery agent plays the same uninformed random strategy. (3) Unilateral deviation, where a single\nagent plays a non-truthful strategy while all other agents report truthfully.\n\nThe numbers are for different settings and do not sum to 100%. We will rewrite the sentence to the\nfollowing “The figure shows that in the uninformed random strategy setting only about 50% of the\nagents receive positive payments, while in the original dataset (truthful strategy setting) over 75% of\nthe users receive positive payments”.\n***\n**Question 5**: Symmetric deviation.\n\n**Answer**: Our symmetric strong truthfulness does not require symmetric deviation.\nThe truth-telling strategy profile is a Bayesian Nash equilibrium where any individual’s unilateral\ndeviation results in a worse payment for the agent. Additionally, we show that our mechanism\nensures the truth-telling strategy profile is better (gives higher payoff) than any other symmetric\nstrategy profile. Considering symmetric strategy profiles is reasonable because they do not require\ncomplicated coordination among all agents.\n***\n**Question 6**: More sophisticated form of strategic behavior.\n\n**Answer**: In our problem setting, since we work with binary reports, the only two pure\nstrategies of the agent are truth-telling and flipping. Therefore, any mixed strategy of the agent can\nbe represented by a linear combination of truth-telling and an uninformed strategy (and flipping).\nConsequently, our comparison of truth-telling and uninformed agents already indicates the higher\npayment of truthful agents over any other individual strategic behavior. Still, we add experiments of\nmore complex group strategic behaviors to test the robustness of our mechanism.\n\nIn the attached PDF, we ran the experiment on all datasets with a new group strategic behavior to\nfurther stress test our mechanism. For each dataset, we randomly divided the truth-telling agents\noriginally in the dataset into two groups of equal numbers. In the first group, the agents remained\ntruthful, but in the second group, the agents were replaced by uninformed agents. We then mixed\nthe two groups of agents and adopted our mechanism on the mixed group of agents. Finally, we\ncompared the payments of agents in the two groups (see the last 3 figures for the results). The\nresults show that the payments of truth-telling agents still dominate the payments of uninformed\nagents. \n\nAlso, we run our experiments on a new dataset: HuggingFace H4 Stack Exchange Preference Dataset, a dataset used to align LLMs with human preferences. The dataset contains questions and their corresponding answers, each with voting data. In our experiment, we treat each vote as the report of an agent.  We compare the payments of truth-telling agents with the new group behavior (see the third figure). The ECDF of payments for truth-telling agents clearly dominates. Please find the detailed setting in our global rebuttal.\n***\n**Question 7**: Is it possible to have a better BNE which is not symmetric?\n\n**Answer**: From the mechanism designer’s perspective, the truth-telling equilibrium is the best equilibrium for the purpose of information elicitation. We focus on equilibria with symmetric strategy profiles. Our results do not rule out the possibility that there is\nsome asymmetric equilibrium leading to higher agent payoff. However, such asymmetric equilibrium\nmay require complicated coordination and hence is difficult to reach.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7j7oYLJwl9", "reviewer": "Reviewer_oRu4", "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. \n\nThis 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.", "questions": "Perhaps the framework also works for weak stochastic transitivity?", "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.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "In my opinion, the paper makes a good contribution to the literature on peer prediction. While the proposed mechanism is mainly based on the Dasgupta-Ghosh mechanism, it is a principled way of extending the Dasgupta-Ghosh mechanism to heterogenous tasks and utilizing task specific properties (such as SST) for incentive design. I really like that the paper connects the peer prediction literature to the ranking literature in a meaningful manner.", "weaknesses": "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.\n\nThe results on networked elicitation seem a bit disconnected from the results on elicitation of comparison data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate your valuable input!  Below, we will address your question in this paper.\n***\n**Question**: Weak stochastic transitivity.\n\n**Answer**: This is an interesting question.  We conjecture that weak stochastic transitivity alone is not sufficient.  Our proof requires $\\Pr[T_\\theta(a'', a') = 1\\mid T_\\theta(a, a') = 1]$ is larger than $\\Pr[T_\\theta(a'', a) = 1\\mid T_\\theta(a, a') = 1]$, but weak stochastic transitivity only decides whether each term is greater than $1/2$ instead of magnitude.   For instance, we can make $\\Pr[T_\\theta(a'', a') = 1\\mid \\theta]$ always close to $1/2$ and $\\Pr[T_\\theta(a'', a) = 1\\mid \\theta]$ to almost one if $\\Pr[T_\\theta(a'', a) = 1\\mid \\theta]\\ge 1/2$.  Thus, the conditional expectation $\\Pr[T_\\theta(a'', a) = 1\\mid T_\\theta(a, a') = 1]$ can be larger than $\\Pr[T_\\theta(a'', a') = 1\\mid T_\\theta(a, a') = 1]$, which will break our proof. That being said, our mechanism may still be symmetrically strongly truthful under Braverman and Elchanan's model, which is weakly stochastic transitive but not strongly stochastic transitive.  \n***\n**Reference**:\n\nBraverman, Mark, and Elchanan Mossel. \"Noisy sorting without resampling.\" Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms (SODA), 2008.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TZ8OXBLcYn", "reviewer": "Reviewer_A4wM", "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.", "questions": "In lines 132-133,\n\n> ... where the randomness of $S(\\cdot, \\cdot)$ comes from both $\\theta$ and $T_{\\theta}$\nThe 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?\n\nWhat 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)?\n\nIn lines 173-174,\n\n> ... she would expect that others will ... prefer $a$ over $a''$\n\nWhat 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'$?\n\nIn line 190-191,\n> Hence, theorem 3.1 implies that agents’ manipulations can only decrease the probability of transitivity among their reports.\n\nWhat is the implication of \"decreasing the probability of transitivity among their reports\"?", "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.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The studied problem is important and relevant.\n- The theoretical rigor is appreciated.\n- The proposed approach seems sound, and the definition of Bayesian SST to generalize several existing models is interesting.", "weaknesses": "- 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).\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable input!\n***\n**Question 1**: What is the randomness of $T_\\theta$?\n\n**Answer**: $T_\\theta$ is a stochastic comparison function that outputs random comparison given parameter $\\theta$. The randomness of $T_\\theta$ captures noise in observing comparisons. For instance, in the Bradley-Terry-Luce model, $\\theta$ encodes each item's quality, and fixing the parameter $\\theta$, the comparison outcome between two items $a$ and $a'$ is noisy and with level of randomness decided by $\\theta_a-\\theta_{a'}$.  \n***\n**Question 2**: External incentives: minimizes other's payment of obfuscate identification of the true ranking.\n\n**Answer**: Our setting focuses on agents who only care about their own payment and do not consider agents who have external incentives, for example, incentives to minimize someone else's expected payment or to obfuscate identification of the true comparison. Several previous works, however, offer potential solutions to handle such external incentives. For instance, as [49], we may incorporate robust statistics (or different privacy techniques) to mitigate the impact of a small group of agents attempting to attack one agent's payment or learning outcomes.\n***\n**Question 3**: Are these considered families of strategies sufficient to consider some robustness to misbehaving agent?\n\n**Answer**: In our problem setting, since we work with binary reports, the only two pure\nstrategies of the agent are truth-telling and flipping. Therefore, any mixed strategy of the agent can\nbe represented by a linear combination of truth-telling and an uninformed strategy (and flipping).\nConsequently, our comparison of truth-telling and uninformed agents already indicates the higher\npayment of truthful agents over any other individual strategic behavior. Still, we add experiments of\nmore complex group strategic behaviors to test the robustness of our mechanism. Please see the answer to question 6 in the rebuttal for Reviewer c3bN. Thank you!\n\n***\n**Question 4**: Line 173-174. Why would $a$ be preferred over $a''$ when the agent itself only has information that $a$ is preferred over $a'$.}\\yc{Can you check that this response is correct?\n\n**Answer**: When an agent observes that $a$ is preferred over $a'$, denoting this as $T(a,a')=1$, the agent considers two conditional probabilities for any given third item $a''$: $P[T(a'',a')=1|T(a,a')=1]$ and $P[T(a'',a)=1|T(a,a')=1]$. The first is the conditional probability that the third item $a''$ is preferred over the $a'$ and the second is the conditional probability that the third item $a''$ is preferred over $a$. Since the agent himself thinks $a$ is better than $a'$, it's more likely that the third item $a''$ is better than $a'$, than better than $a$. The first conditional probability is higher than the second conditional probability. We'll provide more explanation on this point in the paper. \n***\n**Question 5**: Line 190-191. What is the implication of decreasing the probability of transitivity among their reports.\n\n**Answer**: Given three items $a,a',a''$ and three comparison outcomes $x = 1[a\\prec a']$, $y = 1[a'\\prec a'']$, and $z = 1[a''\\prec a]$, these comparison outcomes satisfy transitivity if they form one of the $3!$ valid rankings. As agent's noisy comparisons are random, some comparison outcomes satisfy transitivity and some do not. The probability of transitivity is the probability that noisy comparison outcomes satisfy transitivity.\n***\n**Question 6**: The method requires a specific problem setting or model called the Bayesian SST.\n\n**Answer**: We emphasize that Bayesian SST model is general. It is not a restriction for the comparison data application. Instead, it is a non-parametric generalization of several most commonly used parametric ranking models. \n***\n**Question 7**: Admissible assignments.\n\n**Answer**: We do not require a single agent to compare additional pairs of items; instead, we only need that some other agents are assigned to those pairs.\nThe admissible condition requires some control over the assignment $\\mathcal{E}$. \nThis is reasonable for the purpose of rank learning because these algorithms also need certain controls on $\\mathcal{E}$. Otherwise, it would be impossible to rank an item if it is never compared to any other item. Moreover, several works on rank learning (e.g., [51] and Braverman and Mossel) require $\\mathcal{E}$ to include all possible pairwise comparisons, which automatically satisfies our admissible condition.   Several platforms (including Amazon) actively encourage users to submit reviews on specific items, which can be considered a method to control $\\mathcal{E}$.\n***\n**Question 8**: Empirical results are less extensive.\n\n**Answer**: In the attached PDF, we run our mechanism on a new dataset: the HuggingFace H4 Stack Exchange Preference Dataset, which is a dataset used to align LLMs with human preferences. The experiment on this new dataset aligns with our introduction and abstract of improving the data quality of human preference training for LLMs. The dataset contains questions and their corresponding answers, each with voting data. In our experiment, we treat each vote as the report of an agent. For example, suppose a question has three answers, $a_1, a_2, a_3$, with vote numbers $v_1, v_2, v_3$. A vote (downvote) for $a_1$ means that the agent reports $a_2 \\prec (\\succ) a_1$ and $a_3 \\prec (\\succ) a_1$. Hence, there are $|v_1| + |v_2| + |v_3|$ agents in this example. We treat the original agents in the dataset as truth-telling agents. As in the experiment on the SUSHI dataset, we compare the payments of truth-telling agents with uninformed agents and unilateral strategies (see the first two figures). The ECDF of payments for truth-telling agents clearly dominates. \n***\n**Reference**:\n\nBraverman, Mark, and Elchanan Mossel. \"Noisy sorting without resampling.\" Proceedings of the\nnineteenth annual ACM-SIAM symposium on Discrete algorithms (SODA), 2008.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Please find our additional experiment results attached. Thanks!

In the first three figures, we run our experiments, including the new group strategical behavior, on a new dataset: the HuggingFace H4 Stack Exchange Preference Dataset, which is a dataset used to align LLMs with human preferences. The dataset contains questions and their corresponding answers, each with voting data. For example, suppose a question has three answers, $a_1, a_2, a_3$, with vote numbers $v_1, v_2, v_3$. A vote (downvote) for $a_1$ means that the agent reports $a_2 \prec (\succ) a_1$ and $a_3 \prec (\succ) a_1$. Hence, there are $|v_1| + |v_2| + |v_3|$ agents in this example. We treat the original agents in the dataset as truth-telling agents. In our experiment, we treat each vote as the report of an agent.  As in the experiment on the SUSHI dataset, we compare the payments of truth-telling agents with uninformed agents, unilateral strategies, as well as the new group behavior (which is introduced in the rebuttal for Reviewer c3bN). The ECDF of payments for truth-telling agents clearly dominates. Due to limited computing resources, we only selected the first 100 questions in the dataset with at least three answers with nonzero votes.

The last three figures are the experiment of the new group behavior on our original datasets.
***
**Reference**:

Lambert, Nathan, Lewis Tunstall, Nazneen Rajani, and Tristan Thrush. "HuggingFace H4 Stack Exchange Preference Dataset." Hugging Face, 2023.

Meta-review: 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.
Decision: Accept (poster)