Carrot and Stick: Eliciting Comparison Data and Beyond

Thank you for your valuable input!

---

Question 1: What is the randomness of $T_\theta$?

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'}$.

---

Question 2: External incentives: minimizes other's payment of obfuscate identification of the true ranking.

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.

---

Question 3: Are these considered families of strategies sufficient to consider some robustness to misbehaving agent?

Answer: In our problem setting, since we work with binary reports, the only two pure strategies of the agent are truth-telling and flipping. Therefore, any mixed strategy of the agent can be represented by a linear combination of truth-telling and an uninformed strategy (and flipping). Consequently, our comparison of truth-telling and uninformed agents already indicates the higher payment of truthful agents over any other individual strategic behavior. Still, we add experiments of more 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!

---

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?

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.

---

Question 5: Line 190-191. What is the implication of decreasing the probability of transitivity among their reports.

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.

---

Question 6: The method requires a specific problem setting or model called the Bayesian SST.

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.

---

Question 7: Admissible assignments.

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. The admissible condition requires some control over the assignment $\mathcal{E}$. This 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}$.

---

Question 8: Empirical results are less extensive.

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.

---

Reference:

Braverman, Mark, and Elchanan Mossel. "Noisy sorting without resampling." Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms (SODA), 2008.

Thank you for your valuable input.

---

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?

Answer: Mechanism 3 offers a general scheme for designing peer prediction mechanisms, which requires finding uniformly dominant tuples. Identifying tuples that are uniformly dominant for different settings is a critical and nontrivial task. Mechanism 1 and mechanism 2 identify uniformly dominant tuples for the pairwise comparison setting under Bayesian SST model and networked data setting under the Ising model respectively. Theorem 3.1 and Theorem 5.1 can be viewed as instantiations of Theorem 5.2, with identifying and proving uniformly dominant tuples in the respective settings as a main contribution.

---

Question 2: What are the implications of a priori similar but ex-post distinct?

Answer: The a priori similar assumption implies that agents do not favor any item before observing their noisy comparison. Our mechanism allows agents to know the assignment $\mathcal{E}$ in advance. The a priori similar assumption means that, before observing the noisy comparison, agents do not have strict ordering of any pair of items even with the knowledge of the assignment $\mathcal{E}$. This assumption can be relaxed if we further randomize the assignment $\mathcal{E}$ by a uniform random permutation.

The ex-post distinct assumption requires that the realized state $\theta$ is distinct for each item. Under the Bradley-Terry model (a special case of our Bayesian SST), this assumption means that no two candidates have the same realized scalar quality. The Mallow’s model (another special case of ours) always satisfies this assumption.

---

Question 3: Limited liability? (e.g. if the agent can choose not to participate in the game when they may get negative reward)

Answer: We do not require our mechanism to penalize users (i.e. give them a negative payment) because any positive affine transformation of the payment function preserves the equilibrium. For example, we can add a constant of 1 to the payment function in Equation (2). This ensures that the payment is either 2 or 0.

---

Question 4: Possible typo: ...Percentages seem to add to more than 100%.

Answer: Our experiment shows the histogram of agent’s payment under three different settings: (1) Truth-telling, where every agent uses the truthful strategy, we treat the original data as agents’ true preferences. (2) Uninformed, where every agent plays the same uninformed random strategy. (3) Unilateral deviation, where a single agent plays a non-truthful strategy while all other agents report truthfully.

The numbers are for different settings and do not sum to 100%. We will rewrite the sentence to the following “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”.

---

Question 5: Symmetric deviation.

Answer: Our symmetric strong truthfulness does not require symmetric deviation. The truth-telling strategy profile is a Bayesian Nash equilibrium where any individual’s unilateral deviation results in a worse payment for the agent. Additionally, we show that our mechanism ensures the truth-telling strategy profile is better (gives higher payoff) than any other symmetric strategy profile. Considering symmetric strategy profiles is reasonable because they do not require complicated coordination among all agents.

---

Question 6: More sophisticated form of strategic behavior.

Answer: In our problem setting, since we work with binary reports, the only two pure strategies of the agent are truth-telling and flipping. Therefore, any mixed strategy of the agent can be represented by a linear combination of truth-telling and an uninformed strategy (and flipping). Consequently, our comparison of truth-telling and uninformed agents already indicates the higher payment of truthful agents over any other individual strategic behavior. Still, we add experiments of more complex group strategic behaviors to test the robustness of our mechanism.

In the attached PDF, we ran the experiment on all datasets with a new group strategic behavior to further stress test our mechanism. For each dataset, we randomly divided the truth-telling agents originally in the dataset into two groups of equal numbers. In the first group, the agents remained truthful, but in the second group, the agents were replaced by uninformed agents. We then mixed the two groups of agents and adopted our mechanism on the mixed group of agents. Finally, we compared the payments of agents in the two groups (see the last 3 figures for the results). The results show that the payments of truth-telling agents still dominate the payments of uninformed agents.

Also, 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.

---

Question 7: Is it possible to have a better BNE which is not symmetric?

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 some asymmetric equilibrium leading to higher agent payoff. However, such asymmetric equilibrium may require complicated coordination and hence is difficult to reach.

We greatly appreciate your valuable input! Below, we will address your question in this paper.

---

Question: Weak stochastic transitivity.

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.

---

Reference:

Braverman, Mark, and Elchanan Mossel. "Noisy sorting without resampling." Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms (SODA), 2008.