arXiv:1802.09158v1 [cs.GT] 26 Feb 2018

Surrogate Scoring Rules and a Dominant Truth Serum
for Information Elicitation
YANG LIU, Harvard University
YILING CHEN, Harvard University
We study information elicitation without veriﬁcation (IEWV) and ask the following question: Can we achieve
truthfulness in dominant strategy in IEWV? This paper considers two elicitation settings. The ﬁrst setting is
when the mechanism designer has access to a random variable that is a noisy or proxy version of the ground
truth, with known biases. The second setting is the standard peer prediction setting where agents’ reports are
the only source of information that the mechanism designer has. We introduce surrogate scoring rules (SSR)
for the ﬁrst setting, which use the noisy ground truth to evaluate quality of elicited information, and show
that SSR achieve truthful elicitation in dominant strategy. Built upon SSR, we develop a multi-task mechanism, dominant truth serum (DTS), to achieve truthful elicitation in dominant strategy when the mechanism
designer only has access to agents’ reports (the second setting). The method relies on an estimation procedure to accurately estimate the average bias in the reports of other agents. With the accurate estimation, a
random peer agent’s report serves as a noisy ground truth and SSR can then be applied to achieve truthfulness in dominant strategy. A salient feature of SSR and DTS is that they both quantify the quality or value of
information despite lack of ground truth, just as proper scoring rules do for the with veriﬁcation setting. Our
work complements both the strictly proper scoring rule literature by solving the case where the mechanism
designer only has access to a noisy or proxy version of the ground truth, and the peer prediction literature
by achieving truthful elicitation in dominant strategy.

1

INTRODUCTION

Eliciting private information about events and tasks from human agents is an almost universal
problem in our society when there is uncertainty and asymmetric information. For example, ﬁnancial experts are asked to make predictions on whether the S & P 500 index will go up next
week, seismologists attempt to predict future earthquake activities, students doing peer grading
are asked to assess the correctness of others’ solutions. From the perspective of incentive alignment, an important goal of a mechanism designer is to incentivize agents to truthfully reveal their
private information so that high-quality information is obtained.1
Incentive design for information elicitation has been extensively studied. However, proposed
solutions have achieved diﬀerent notions of truthfulness depending on which one of the following two categories an elicitation problem falls into: information elicitation with veriﬁcation and
information elicitation without veriﬁcation.
Information elicitation with veriﬁcation refers to settings where the mechanism designer will
have access to the ground truth at some point (e.g. whether S & P 500 index actually went up
and whether a predicted earthquake actually happened) and can use the ground truth to evaluate
the quality of elicited information. Strictly proper scoring rules [Brier, 1950, Gneiting and Raftery,
2007, Matheson and Winkler, 1976a, Murphy and Winkler, 1970] have been proposed and studied
to incentivize truthful reporting of private predictions (probability assessment of event outcome).
Facing a strictly proper scoring rule, an agent strictly maximizes his expected score by truthfully
revealing his prediction. Hence, truthfulness in dominant strategy is achieved here. Moreover, the
score of an agent measures the quality of his prediction.
1 Many

also consider incentivizing both eﬀort exertion to improve the quality of private information and truthful information revelation.

2

1 INTRODUCTION

Information elicitation without veriﬁcation refers to settings where the mechanism designer
does not have access to the ground truth (e.g. whether a student’s homework solution is correct is unavailable as otherwise peer grading is not needed). An elegant family of incentive
mechanisms [Dasgupta and Ghosh, 2013, Jurca and Faltings, 2006, Miller et al., 2005, Prelec, 2004,
Radanovic and Faltings, 2013, Witkowski and Parkes, 2012], collectively called peer prediction, has
been developed for this category to elicit private signals (e.g. a peer grader’s judgement on the
correctness of a homework solution). Peer prediction leverages the correlation of agents’ private
signals and scores an agent’s report based on how it compares with the reports from other agents.
Agents play a Bayesian game in peer prediction and there exists a Bayesian Nash Equilibrium
(BNE) where every agent reports truthfully. Truthfulness at BNE is clearly a weaker incentive
guarantee than truthfulness in dominant strategy as the former is sensitive to errors and mistakes
of other agents. Peer prediction also suﬀers from multiplicity of equilibria as there are other nontruthful BNE.2 In experiments, the truthful equilibrium was often not reached [Gao et al., 2014].
In addition, the peer prediction score of an agent measures the correlation of his report with those
of others, but it doesn’t reﬂect the quality of the agent’s report.
We focus on information elicitation without veriﬁcation in this paper and ask:
Can we achieve truthfulness in dominant strategy in information elicitation without veriﬁcation?
We provide a positive answer to this question for binary information elicitation. Moreover, in our
proposed mechanisms, the score of an agent measures the quality of his report as in information
elicitation with veriﬁcation.
Two speciﬁc information elicitation without veriﬁcation settings are considered in this paper.
The ﬁrst setting is when the mechanism designer has access to a random variable that is a noisy
or proxy version of the ground truth, with known biases. The second setting is the standard peer
prediction setting where agents’ reports are the only source of information that the mechanism
designer has.
For the ﬁrst setting, we introduce surrogate scoring rules (SSR), which use the noisy ground
truth to evaluate quality of elicited information, and show that SSR achieve truthful elicitation in
dominant strategy without access to the ground truth. These surrogate scoring rules are inspired
by the use of surrogate loss functions in machine learning [Angluin and Laird, 1988, Bylander,
1994, Natarajan et al., 2013, Scott, 2015, Scott et al., 2013] and they remove bias from the noisy
random variable such that in expectation a report is as if evaluated against the ground truth.
Built upon SSR, in the second setting where the mechanism designer only has access to agents’
reports, we develop a multi-task mechanism, dominant truth serum (DTS), to achieve truthful elicitation in dominant strategy. The method relies on an estimation procedure to accurately estimate
the average bias in the reports of other agents. With the accurate estimation, a random peer
agent’s report serves as a noisy ground truth and SSR can then be applied to achieve truthfulness
in dominant strategy. We further show that DTS can be extended to achieve truthful elicitation
in dominant strategy in settings where agents’ signals are correlated conditioned on the ground
truth. This allows us to overcome the failure of classic peer prediction in the presence of weak,
correlated signals, observed by [Gao et al., 2016].
A salient feature of SSR and DTS is that they both quantify the quality or value of information
despite lack of ground truth, just as proper scoring rules do for the with veriﬁcation setting. In this
sense, SSR and DTS unify the with and without veriﬁcation settings by always rewarding agents
2 Several

recent peer prediction mechanisms [Dasgupta and Ghosh, 2013, Kong and Schoenebeck, 2016a, Shnayder et al.,
2016] have made truthful equilibrium focal in the sense that it leads to the highest expected payoﬀ to agents among all
equilibria. But there is at least one other equilibrium that gives the same expected payoﬀ to agents.

1.1 Related work

3

based on their quality of information (and hence achieving truthfulness in dominant strategy). In
addition, SSR and DTS apply to both signal and prediction elicitation.
The rest of the paper is organized as follows. In Section 2, we describe our model and the two
elicitation settings. Section 3 introduces SSR for the ﬁrst elicitation setting. Section 4 details DTS
for the second elicitation setting. Then, in Section 5, we extend DTS to correlated signals. Section 6
concludes with discussions on some additional directions.
1.1

Related work

The most relevant literature to our paper is strictly proper scoring rule and peer prediction. Scoring
rules were developed for eliciting truthful prediction (probability) [Brier, 1950, Gneiting and Raftery,
2007, Jose et al., 2006, Matheson and Winkler, 1976b, Savage, 1971, Winkler, 1969]. For example,
the pioneer works [Brier, 1950] proposed Brier scoring to verify the qualities of forecasts. A full
characterization result is given for strictly proper scoring rules in [Gneiting and Raftery, 2007].
Our work complements the literature of scoring rule by proposing surrogate scoring rules to cope
with the case when there is only access to a noisy or proxy version of the ground truth.
Our surrogate scoring rules can be viewed as a class of proxy scoring rules deﬁned in [Witkowski et al.,
2017]. [Witkowski et al., 2017] proposed to design proper proxy scoring rules by using an unbiased
proxy random variable as the ground truth in a strictly proper scoring rule. Our proxy random
variable is biased. We focus on designing a surrogate scoring function that removes bias in any
noisy ground truth, and thus can deal with a more general setting.
Motivated by the complexity of reporting the probability for events with large outcome space,
property elicitation, such as for mean, variance etc of probability distributions, has been studied
more recently [Frongillo and Kash, 2015, Lambert et al., 2008]. In this paper we do not cover the
property elicitation setting.
The core idea of peer prediction is to score each agent based on another reference report elicited
from the rest of agents, and to leverage on the stochastic correlation between diﬀerent agents’ information. This line of research started with the celebrated Bayesian Truth Serum work [Prelec,
2004], where a surprisingly popular answer methodology is shown to be able to incentivize agents
to truthfully report even they believe they hold the minority answer (but more likely to be true
in their own opinion). The seminal work [Miller et al., 2005] established that strictly proper scoring rule [Gneiting and Raftery, 2007] can be adopted in the peer prediction setting for eliciting
truthful reports (but the mechanism designer need to know details of agents’ model); a sequence
of followed up works have been done to relax the assumptions that have been imposed therein
[Radanovic and Faltings, 2013, Witkowski and Parkes, 2012]. More recently, [Dasgupta and Ghosh,
2013, Witkowski et al., 2013] formally introduced and studied an eﬀort sensitive model for binary signal data elicitation. Particularly [Dasgupta and Ghosh, 2013] proposed a multi-task peer
prediction mechanism that can help remove undesirable equilibria that lead to low quality reports. These results are further strengthened and extended to a non-binary signal setting in
[Kong and Schoenebeck, 2016a, Shnayder et al., 2016]. An information theoretical framework for
studying this type of elicitation problems has been proposed in [Kong and Schoenebeck, 2016a,b].
[Kong and Schoenebeck, 2016b] also proposed a conceptual mechanism to achieve truthfulness in
dominant strategy but it requires inﬁnite number of tasks. Our work is the ﬁrst one to establish
truthfulness in dominant strategy with a ﬁnite number of tasks for a peer prediction setting.
It is worth to mention that our work borrows ideas from the machine learning literature on
learning with noisy data [Bylander, 1994, Menon et al., 2015, Natarajan et al., 2013, Scott, 2015,
van Rooyen and Williamson, 2015]. From a high level’s perspective, our goal in this paper aligns
with the goal in learning from noisy labels - both aim to evaluate a prediction when the ground

4

2 INTRODUCTION

truth is missing, but instead a noisy signal of the ground truth is available. Our work addresses
additional challenge that the error rate of the noisy signal remains unknown a priori.
2 OUR MODEL
Prior work on information elicitation typically considers one of two types of information: private
signals and private beliefs (i.e. probabilistic predictions). In this paper, we develop mechanisms
that apply to both cases. Hence, in Section 2.1, we ﬁrst introduce our model of information and
notations to unify these two types of information. Then, Section 2.2 and 2.3 will introduce our
model and design goals for two elicitation settings without accessing the ground truth. In the
ﬁrst setting (Section 2.2), the mechanism designer has access to a random variable that is a noisy
version of the ground truth with known bias. The second setting (Section 2.3) is the typical setting
in the peer prediction literature where the mechanism designer only has access to reports from
agents. For both settings, our design goal is to achieve truthful elicitation in dominant strategy.
2.1

Model of information

Suppose we are interested in eliciting information about a binary event y ∈ {0, 1} from a set of
human agents, indexed by [N ] := {1, 2, ..., N }. The realization of the event y has prior distribution
P0 := Pr[y = 0], P1 = Pr[y = 1]. We assume a non-trivial prior distribution that 0 < P0 , P1 < 1.
Each of the N agents holds a noisy observation of y, denoting as si . Agents’ observations are
conditionally independent: Pr[si , s j |y] = Pr[si |y] · Pr[s j |y]. We short-hand the following error
rates:
e 1,i := Pr[si = 0|y = 1], e 0,i := Pr[si = 1|y = 0],
i.e., e 1,i , e 0,i are the “error probabilities” or the subjective “human bias” of agent i’s observation for
y. We do not assume homogeneous agents, that is we allow agents to have diﬀerent e 1,i , e 0,i . The
error rates can also model subjectivity in agents’ private belief and observation. Based on signal
si , each agent can form a posterior belief about y, denoting as pi := Pr[y = 1|si ]. When there
are multiple tasks, we assume the prior, P0 and P1 , and each agent’s error rates, e 1,i and e 0,i , are
homogeneous across tasks.
We consider eliciting either si or pi from agents,3 but we are not able to access the ground truth
y to verify the reported information from agents. We call the elicitation of these two types of
information as signal elicitation and prediction elicitation respectively. The literature on proper
scoring rules has been primarily considering prediction elicitation, while the literature on peer
prediction has focused on signal elicitation. To unify both types of information, we denote the
information space as I, and each agent’s information as Ii . For signal elicitation, Ii = si and
I = {0, 1}. For prediction elicitation, Ii = pi and I = [0, 1]. Denote agent i’s report to a mechanism
as ai ∈ I . Then, for for signal elicitation and prediction elicitation, we have ai : si → {0, 1} and
ai : pi → [0, 1] respectively.
2.2

Model of elicitation with noisy ground truth

The ﬁrst elicitation setting is when the mechanism designer has access to the realization of a binary
random variable z ∈ {0, 1}, which is a noisy or proxy version of the ground truth with known bias.
The bias of z is again captured by the error rates:
e 1,z := Pr[z = 0|y = 1], e 0,z := Pr[z = 1|y = 0].
3 For

clarity of presentation, we assume that we elicit the same type of information from all agents. But our work can be
extended to a mixed elicitation setting.

2.3 Model of elicitation with peer reports

5

We cannot expect to do much if z is independent of y and hence assume that z and y are stochastically relevant, an assumption commonly adopted in the information elicitation literature [Miller et al.,
2005].
Deﬁnition 2.1. z and y are stochastically relevant if there exists an s ∈ {0, 1} such that
Pr[y = s |z = 0] , Pr[y = s |z = 1].
The following lemma shows that the stochastic relevance requirement directly translates to a
constraint on the error rates, that is, e 1,z + e 0,z , 1.
Lemma 2.2. y and z are stochastically relevant if and only if e 1,z + e 0,z , 1. And y and z are
stochastically irrelevant (independent) if and only if e 1,z + e 0,z = 1.
We consider both signal elicitation and prediction elicitation. Our goal is to design a scoring
function φ(ai , z) : I × {0, 1} → R+ such that when agent i’s report ai is evaluated against the
realization of the noisy ground truth z, agent i strictly maximizes his expected score by reporting
his true information ai = Ii . Formally, we want to achieve
Strict properness with noisy ground truth: E[φ(Ii , z)] > E[φ(ai , z)], ∀ai , Ii ,

(1)

where the expectation is taken with respect to the agent’s subjective belief Pr[z|si ].
It’s worth noting that prediction elicitation in this model, as in the literature, doesn’t need agents
to form their prediction pi according to the signal model described in Section 2.1, and instead only
requires that agents each have a subjective belief pi . For simplicity of presentation, we use the
signal model in Section 2.1 throughout the paper.
2.3

Model of elicitation with peer reports

The second elicitation setting is close to the standard setting considered in the peer prediction
literature. Here the only source of information that the mechanism designer has access to is the
agents’ reports. In this setting, we assume ”diﬀerentiable” prior such that P0 , P1 . This is a
technical condition that we need. In practice, with multiple tasks, we can perturb the priors by
adding some known tasks to (or deleting task from) one of the two classes.
2.3.1 Informativeness of signals. We adopt the standard assumption requiring that each agent’s
signal si and the ground truth y are stochastically relevant, i.e. e 1,i +e 0,i , 1. Moreover, we assume
that signals are Bayesian informative of y, that is, Pr[y = s |si = s] > Pr[y = s], ∀i, s. In other
words, the posterior probability for y = s is greater than the prior probability of y = s if an agent
receives a signal s. This assumption has been adopted by [Dasgupta and Ghosh, 2013, Miller et al.,
2005], and has been shown by [Liu and Chen, 2017] to be equivalent to a constraint on the error
rates of agent signals.
Lemma 2.3. (Lemma 2.1 in [Liu and Chen, 2017]) si is Bayesian informative of y if and only if
e 1,i + e 0,i < 1.
The case e 1,i + e 0,i > 1 can be viewed as negative Bayesian informative as always ﬂipping
one’s observation will return a Bayesian informative signal. In this paper we focus only on settings where every agent’s signal is Bayesian informative of y. But this assumption is to simplify
presentation as our results hold for negative Bayesian informative agents, as well as for a mixed
population.

6

3 OUR MODEL

2.3.2 Knowledge of agents and the mechanism designer. For signal elicitation, agents do not need
to be aware of their own values of e 1,i and e 0,i , but they need to know that their own signals are
Bayesian informative and the error rates satisfy e 1,i + e 0,i < 1. For prediction elicitation, agents
need to know their own values of e 1,i and e 0,i to form their predictions. The above knowledge does
not need to be common knowledge among agents. This is because we seek to achieve dominant
strategy truthfulness and hence agents are as if not playing a Bayesian game.
The mechanism designer knows the priors of ground truth P0 , P1 , but not the realized y, nor
the private information si ’s or pi ’s. Further the designer does not know any of the biases of agents’
information, e 1,i and e 0,i , a-priori. This can capture scenarios when we know the prior distribution
of answers for a certain type of questions, but not speciﬁcally the answer for a particular question,
nor how human agents make wrong prediction of such events. In our proposed mechanism, we
will show how to infer the true error rates of agents’ reports.
2.3.3 Design goal. We again aim to achieve truthful elicitation in dominant strategy for both
signal elicitation and prediction elicitation. Denote by D−i the set of information collected from
agents j , i, possibly for multiple tasks, i.e. D−i := {a j }j,i For this part, our goal is to ﬁnd a
reference signal z D−i ∈ {0, 1}, as a function of D−i , and a scoring function
φ D−i (ai , z) : I × {0, 1} → R+ ,
also as a function of D−i , such that it is a dominant strategy for agent i to truthfully report his
private information:
Truthfulness in dominant strategy with peer reports: Ii = argmaxai E[φ D−i (ai , z D−i )], (2)
where the expectation is taken with respect to the agent’s subjective belief Pr[z D−i |si ]. When it’s
clear in context, we’ll use z as shorthand for z D−i and φ for φ D−i .
3 SURROGATE SCORING RULES
In this section we propose surrogates scoring rules (SSR) to address the question of achieving strict
properness when only having access to a noisy ground truth. SSR is built upon strictly proper
scoring rules. Thus, we ﬁrst brieﬂy discuss strictly proper scoring rules. Then, we formally deﬁne
SSR, prove its strict properness and give an implementation of it.
3.1

Strictly proper scoring rules

As mentioned earlier, when ground truth is available, strictly proper scoring rules were designed
to elicit predictions, i.e. the pi ’s. A scoring function S : [0, 1] × {0, 1} → R+ is strictly proper if
and only if
E[S(pi , y)] > E[S(p̃i , y)], ∀p̃i , pi ,
where the expectation is taken with respect to the agent’s belief Pr[y|si ]. There is a rich family of
strictly proper scoring rules, including Brier (S(pi , y) = 1 − (pi − y)2 ), logarithmic and spherical
scoring rules [Gneiting and Raftery, 2007].
Though not enjoying much attention in the literature, the above idea of deﬁning strictly proper
scoring rules also applies to signal elicitation, that is to design a function S : {0, 1}2 → R+ such
that
E[S(si , y)] > E[S(s̃i , y)], ∀s̃i , yi ,
where the expectation is taken with respect to the agent’s belief Pr[y|si ]. For instance, with knowledge of the prior of y (Pr[y = s], s ∈ {0, 1}), the following prior dependent output agreement

3.3 An implementation of SSR

7

scoring function is strictly proper (1/Prior):
S(s̃i , y) =

1
· 1(s̃i = y).
Pr[y = s̃i ]

Lemma 3.1. 1/Prior scoring function is strictly proper.
To unify prediction and signal elicitation, we will denote a strictly proper scoring rule for eliciting agent i’s information Ii as S(ai , y) : I × {0, 1} → R+ .
3.2

Surrogate scoring rules

We deﬁne surrogate scoring rules (SSR), when we only have access to z, a noisy and proxy signal
of the ground truth y, and e 1,z + e 0,z , 1.
Deﬁnition 3.2 (Surrogate Scoring Rules). φ : I × {0, 1} → R+ is a surrogate scoring rule if there
exists a strictly proper scoring rule S : I × {0, 1} → R+ and a strictly increasing function f : R+ →
R+ such that ∀ai ,
Ey,z [φ(ai , z)] = f (Ey [S(ai , y)]).

(3)

If Eqn .(3) is true, the strict properness of φ(·) holds immediately because of the strict properness
of S and monotonicity of f (·). For instance, a simple such f to aim for can be an aﬃne function
that there exist two constants c 1 > 0, c 2 such that
Ey,z [φ(ai , z)] = c 1 · Ey [S(ai , y)] + c 2 .

(4)

Theorem 3.3. SSR is strictly proper for eliciting Ii .
The above approach seeks a surrogate scoring function φ(·) that helps us remove the bias in z
to return us a strictly proper score in expectation.
SSR can be viewed as a particular class of proxy scoring rules [Witkowski et al., 2017]. But the
approach of [Witkowski et al., 2017] to achieve properness is to plug in an unbiased proxy ground
truth to a strictly proper scoring rule. SSR on the other hand directly works with biased proxy and
the scoring function is designed to de-bias the noise.
3.3 An implementation of SSR
Consider any strictly proper scoring function S for eliciting Ii using y, the ground truth. We deﬁne
the following SSR, which we name as SSR alpha:
(SSR alpha) : φ(ai , z = s) =

(1 − e 1−s,z ) · S(ai , s) − es,z · S(ai , 1 − s)
.
1 − e 1,z − e 0,z

(5)

From above we note that the knowledge of the error rates e 1,z , e 0,z is crucial for deﬁning a SSR.
The above scoring function is inspired by the work ”learning with noisy label” [Natarajan et al.,
2013]. Intuitively speaking, the linear transform will ensure that in expectation, ai is scored against
y:
Lemma 3.4. When e 1,z + e 0,z < 1, we have for (SSR alpha): Ez |y [φ(ai , z)] = S(ai , y), ∀y ∈ {0, 1}.
This can be proved fairly straightforwardly via spelling out the expectation. Interested readers
are also referred to Lemma 1, [Natarajan et al., 2013]. In above, the scoring function φ(·) takes
the form of linear combination of the scoring function evaluated at the noisy outcome z and the
one evaluated at the opposite signal 1 − z. The second term is to account for the fact that the
reference signal is merely a noisy proxy for the ground truth signal. The linear weights, carefully
deﬁned over the bias level of the reference, balance the bias in the noisy signal with respect to

8

4 SURROGATE SCORING RULES

the ground truth. Also note the above unbiasedness is achieved w.r.t. each possible realization of
y, being independent of its prior distribution. This helps us remove the requirement of common
knowledge over the priors among agents, and thus our solution works for the subjective prior
setting. Now we establish the strict properness of SSR:
Theorem 3.5. (SSR alpha) is strictly proper.
Proof. Consider agent i. Consider the case that e 1,z + e 0,z < 1. The proof is straightforward
following the “unbiasedness” property established for φ(·) in Lemma 3.4:


E[φ(ai , z)] = E E[φ(ai , z)|y] = E[S(ai , y)].
The theorem follows immediately from the strictly properness of S.
Now consider the case with e 1,z + e 0,z > 1. We cannot directly apply Lemma 3.4. Now let’s
deﬁne the “ﬂip signal” ẑ of z: ẑ = 1 − z. Easy to see that
e 1, ẑ := Pr[ẑ = 0|z = 1] = Pr[z = 1|z = 1] = 1−e 1,z , e 0, ẑ := Pr[ẑ = 1|z = 0] = Pr[z = 0|z = 0] = 1−e 0,z ,
and e 1, ẑ + e 0, ẑ < 1. The scoring function for agent i then becomes:
(1 − e 1−s,z ) · S(ai , s) − es,z · S(ai , 1 − s)
.
1 − e 1,z − e 0,z
[1 − (1 − es,z )]S(ai , 1 − s) − (1 − e 1−s,z )S(ai , s)
=
1 − (1 − e 1,z ) − (1 − e 0,z )
(1 − e 1−(1−s), ẑ )S(ai , 1 − s) − e 1−s, ẑ S(ai , s)
=
1 − e 1, ẑ − e 0, ẑ
= φ(ai , ẑ = 1 − s).

φ(ai , z = s) =

(6)

Then we have




E[φ(ai , z)] = E[φ(ai , ẑ)] = E E[φ(ai , ẑ)|y] = E[S(ai , y)],
where the last equality is due to the unbiasedness of φ(·) with respect to ẑ (instead of z), and the
fact that e 1, ẑ + e 0, ẑ < 1, so Lemma 3.4 can be applied. Again it is easy to see it would be agent
i’s best interest to tell the truth, due to the strict properness or truthfulness of S(·), ﬁnishing the
proof.

Remark 1. We provide a simple yet eﬀective scoring function to unify the two elicitation scenarios.
Intuitively, the reason we can achieve above is that the core step of surrogate function φ(·) only operates
with the reference answer z, and it is independent of the format of the information being elicited.
4

DOMINANT TRUTH SERUM

The results in previous section are built upon the fact that there exists a reference signal for the
ground truth and we know its error rates. In this section, we apply the idea of SSR to the peer
prediction setting. A reasonable way to do so is to take agents’ reports as the source for this noisy
copy of the ground truth. Yet the mechanism designer cannot assume the knowledge of the noise
in agents’ reports. In this section we discuss how to select the reference answer z and how to learn
e 1,z , e 0,z accurately so that φ(·) will be well deﬁned. Then applying Theorem 3.5, we will be able to
establish a dominant strategy argument in the peer prediction setting.

4.2 Bias learning with matching

4.1

9

Reference report

An intuitive way of selecting a reference report z is to uniformly randomly select a report from
agents j , i, i.e., from D−i . Denote by ẽ 1,i , ẽ 0,i the error rate of agent i’s reported information
ai . For the signal elicitation setting, when agents truthfully report, i.e. ai = si , we have ẽ 1,i =
e 1,i , ẽ 0,i = e 0,i , and when they revert their signals we have ẽ 1,i = 1 − e 1,i , ẽ 0,i = 1 − e 0,i . For
the case with prediction elicitation, we can similarly deﬁne a signal from agent i, via drawing a
random sample: asi ∼ Bernoulli(p̃i ). In this case, we will still call such a asi as agent i’s “signal”
but we should keep in mind this signal is randomly drawn from his reported prediction, instead
of being deterministic. We similarly deﬁne ẽ 1,i , ẽ 0,i , and assume conditional independence among
asi s.
e 1,z and e 0,z can then be characterized fairly easily as follows:
Í
Í
j,i ẽ 1, j
j,i ẽ 0, j
e 1,z :=
, e 0,z :=
.
(7)
N −1
N −1
This can be obtained by the following argument: Denote the following even
Wj := {agent j selected as the reference agent}.
Then we have
Pr[z = 0|y = 1] =

Õ
j,i

=

Õ
j,i



Pr z = 0, Wj |y = 1


 

Pr z = 0|y = 1, Wj · Pr Wj =

Õ
1
·
ẽ 1, j .
N − 1 j,i

We have similar interpretation for e 0,z . The next subsection will detail the steps towards estimating
e 0,z , e 1,z . Note if we know the average error rates when agents truthfully report, the SSR already
gives us an equilibrium implementation of truthful elicitation - as in the equilibrium argument,
every other agent will truthfully report.
4.2 Bias learning with matching
Our learning algorithm for inferring e 0,z , e 1,z relies on establishing three equations towards characterizing e 1,z , e 0,z . We will ﬁrst show that the three equations, with knowing their true parameters,
together will uniquely deﬁne e 1,z , e 0,z . Then we argue that with estimated and imperfect parameters from agents’ report, the solution from the perturbed set of equations will approximate the true
values of e 1,z , e 0,z , with guaranteed accuracy.
(1) Posterior distribution: The ﬁrst equation is based on on the posterior distribution of 0/1
label information collected from D−i , denoting as P0, −i := Pr[z = 0], P1, −i := Pr[z = 1].
For P0, −i we have
P0, −i = P1e 1,z + P0 (1 − e 0,z ).

(8)

Note the above equation is also equivalent with P1, −i = P1 (1 − e 1,z ) + P0e 0,z .
(2) Matching between two signals: The second equation is derived from a second order
statistics, namely the matching probability. Consider the following experiments: draw
two independent signals (for the same task) from the reference agents 4 , denote them as
4 Note in practice,

we won’t obtain independent copies of answers for the same question from the same agents for inferring
the matching probability. However when the number of agent is large enough, we will show that drawing two or three
agents randomly from the population (without replacement) can approximate these independent matching probabilities
with small and diminishing errors (as a function of number of agents N ).

10

4 DOMINANT TRUTH SERUM

z 1 , z 2 . Denote the matching-on-1 probability of the two signals as
Pr[z 1 = z 2 = 1] = q 2, −i .
Further the matching probability can be written as a function of e 0,z , e 1,z :5
2
q 2, −i = P1 (1 − e 1,z )2 + P0e 0,z
.

(9)

(3) Matching among three signals: The third equation is obtained by going one order
higher that, we check the matching-on-1 probability over three independent signals drawn
from reference agents. Similarly as deﬁned for (2) matching between two signals, draw
three independent signals (for the same task) from the reference agents, denote them as
z 1 , z 2 , z 3 . Denote the matching-on-1 probability of the three signals as Pr[z 1 = z 2 = z 3 =
1] = q 3, −i . Then we also have that
2
q 3, −i = P1 (1 − e 1,z )3 + P0e 0,z
.

(10)

The reasons we selected the above three equations are two-fold. The ﬁrst reason is that, as we
will show below, the above three equations uniquely deﬁne e 0,z , e 1,z . The second reason is that
in practice we only need to know P1, −i , q 2, −i , q 3, −i in order to establish the three equations, since
we have assumed the knowledge of priors P0 , P1 . All three parameters P1, −i , q 2, −i , q 3, −i can be
estimated from agents’ reports, without the need of knowing any ground truth labels.
As promised, we ﬁrst establish the following theorem:
Theorem 4.1. (e 0,z , e 1,z ) is the unique pair of solution to Eqn.(8, 9, 10), when P0 , P1 .
Proof. First of all, there are at most two solutions from Eqn. (8) and (9), since the equations
are at most order two. Further we prove the following properties of its solutions:
Lemma 4.2. For the solutions to Eqn.(8) and (9), we have
(1) When the reports are uninformative such that e 0,z + e 1,z = 1, the above equation return
exactly one solution satisfying that e 0,z + e 1,z = 1.
(2) When the reports are informative such that e 0,z + e 1,z , 1, Eqn.(8) and (10) jointly return two
pair of solutions
[e 0,z (1), e 1,z (1)], [e 0,z (2), e 1,z (2)]
and exactly one of them satisﬁes e 0,z (1)+e 1,z (1) < 1 and the other one that e 0,z (2)+e 1,z (2) > 1.
Further their summations of the two pairs have the same distance to the 1 (uninformative):
1 − (e 0,z (1) + e 1,z (1)) = (e 0,z (2) + e 1,z (2)) − 1.
We shall shorthand the following: x 1 := e 0,z , x 2 := 1 − e 1,z .
Proof. Eqn.(8) and (9) become equivalent with the following
(I) : P0x 1 + P1x 2 = P1, −i , (II) : P0x 12 + P1x 22 = q 2, −i .
From the ﬁrst equation (I) we know that x 1 =
x1 − x2 =

P 1, −i −P1 ·x 2
.
P0

Then

P1, −i − P1 · x 2
P1, −i − x 2
− x2 =
P0
P0

5 Note here we implicitly assumed that agents’ reported signals are also conditional

independent of the ground truth signal.
In practice, without knowing the ground truth, it is hard for agents to coordinate based on the ground truth. In fact if
the reporting strategies are functions of each agent’s observation, we will have the conditional independence established
immediately, according to the conditional independence of agents’ observations.

4.3 Statistical consistency results

11

Further plug x 1 into the second equation (II) we have
P1x 22 − 2P1 P1, −i x 2 + P1,2 −i − P0q 2, −i = 1 ⇒ x 2 = P1, −i ± ∆,
q
(2P1P1, −i )2 − 4P1 (P1,2 −i − P0q 2, −i )
.
where ∆ :=
2P1
From above we have derived the following e 0,z + e 1,z − 1 = x 1 − x 2 = ± P∆0 . When e 0,z + e 1,z = 1,
we know we must have ∆ = 0 so we land at an unique solution. When e 0,z + e 1,z , 1, we know
that ∆ > 0 and we have two solutions – but both solutions satisfy that
|e 0,z + e 1,z − 1| =

∆
,
P0

ﬁnishing the proof.
We now show the following fact:



Eqn.(10) − Eqn.(8) · Eqn.(9)
⇔P0x 13 + P1x 23 − (P0x 1 + P1x 2 )(P0x 12 + P1x 22 ) = q 3,i − q 2,i P1
⇔P0 P1 (x 13 + x 23 − x 12x 2 − x 1x 22 ) = q 3, −i − q 2, −i P1, −i
⇔P0 P1 (x 1 − x 2 )2 (x 1 + x 2 ) = q 3, −i − q 2, −i P1, −i
(q 3, −i − q 2, −i P1, −i )P0
∆2 P1
The above equation, together with equation (I), will uniquely identify the solution for x 1 , x 2 when
P0 , P1 :


q 3, −i − q 2, −i P1, −i
1
P1 − P1, −i ,
x1 =
P1 − P0
q 2, −i − P1,2 −i


q 3, −i − q 2, −i P1, −i
1
x2 =
P
P1, −i −
0 .
P1 − P0
q 2, −i − P1,2 −i
⇔x 1 + x 2 =

This completes the proof.



This result implies that when there is no ground truth data, knowing how frequently human
agents reach consensus with each other will help us characterize their (average) subjective biases.
We conjecture that the above estimation method can be extended to the case with unknown
priors of the ground truth. The idea is very straightforward following our approach: We can relax
the knowledge of the priors to have two additional unknown variables. Then we will go two orders
up to have additional two equations characterizing the matchings among four and ﬁve reference
signals, to cop with the two more unknown variables. This merits future studies.
4.3 Statistical consistency results
Now we detail the learning procedure. Our method relies on multiple tasks (thus our mechanism
is naturally a multi-task one). We will collect information on multiple independently drawn events
from priors y(1), y(2), · · · ∼ P0 , P1 by randomly assigning them to agents. Each task will be randomly assigned to three agents. Suppose there are K tasks that have been assigned to agents j , i
- this is not hard to guarantee ∀i when we assign more than K tasks to the entire set of agents
randomly, and when N is large.
The algorithm ﬁrst estimates the following three quantities for each agent i: q̃ 2, −i , q̃ 3, −i and
P̃1,i −i based on above information. Denote the three agents that are assigned task k = 1, ..., K as

12

4 DOMINANT TRUTH SERUM

r 1 (k), r 2 (k), r 3 (k) , i, and their reports for task k as ỹr idx (k) (k), idx = 1, 2, 3. Then we estimate the
three parameters as follows:
ÍK
1(ỹr 1 (k) (k) = 1)
,
P̃1, −i = k=1
K
ÍK
1(ỹr 1 (k) (k) = ỹr 2 (k) (k) = 1)
,
q̃ 2, −i = k=1
K
ÍK
1(ỹr 1 (k) (k) = ỹr 2 (k) (k) = ỹr 3 (k) (k) = 1)
.
q̃ 3, −i = k=1
K
Mechanism 1 Learning of e 1,z , e 0,z
1. Estimate q̃ 2, −i , q̃ 3, −i and P̃1, −i using {ỹr idx (k) (k), k = 1, 2, ..., K, idx = 1, 2, 3}.
2. Compute the following:


q̃ 3, −i − q̃ 2, −i P̃1, −i
1
ẽ 0,z : =
· P1 − P̃1, −i ,
P1 − P0 q̃ 2, −i − (P̃1, −i )2


q̃ 3, −i − q̃ 2, −i P̃1, −i
1
· P0 ,
ẽ 1,z : = 1 −
P̃1, −i −
P1 − P0
q̃ 2, −i − (P̃1, −i )2

(11)
(12)

Remark 2. We notice that the sensitivity in computing e 0,z , e 1,z is inversely proportional to P1 −P0 .
This implies that the diﬃculty in selecting the right pair of root increases when the priors are less
diﬀerentiable.
We would like to show that the estimation error in estimating reports’ error rate can be bounded
as a function of K and N . The ﬁrst source of errors is the imperfect estimations of q 2, −i , q 3, −i , P1, −i .
The second is due to estimation errors for matching probability with heterogeneous agents. Formally we have the following theorem:

0.12

1.8
1.7

0.08

Reward gap

Estimation error

0.1

0.06
0.04

1.5
1.4

0.02
0
500

1.6

1000
1500
Number of tasks

2000

1.3
500

1000
1500
Number of tasks

2000

Fig. 1. Convergence of the estimation. Left: convergence with diﬀerent number of tasks. e 0,z = 0.85, e 1,z =
0.83. Right: gap in reward functions (1/Prior scores) between truth-telling and mis-reporting.

Theorem 4.3. The mechanism designer can learn noisy copies of e 1,z , e 0,z , φ(·) for each agent i
using data collected from agents j , i, satisfying that

4.4 Truth-telling is a dominant strategy

13

(1) |ẽ 1,z − e 1,z | ≤ ϵ, |e˜0,z − e 0,z | ≤ ϵ with probability at least 1 − δ .
(2) For the scoring function φ(·) deﬁned using ẽ 1,z , ẽ 0,z , we have with probability at least 1 − δ 1
that |φ̃(t, y) − φ(t, y)| ≤ ϵ1 , ∀t, y.
q
q
log K 
log K 
1
1
),
ϵ
=
O
+
,
δ
=
O(
, δ 1 = O( K1 ) can be made arbitrarily
All terms ϵ = O N1 +
1
K
K
N
K
small with increasing number of samples K and N .
Proof can be found in Appendix. The main steps of the proof are based on Theorem 4.1 and
sensitivity analysis of the solutions Eqn. (11,12). A set of simple simulation results are shown in
Figure 1. We simulated a scenario with e 0,z = 0.85, e 1,z = 0.83, i.e., majority people are wrong
from the reference set of agents. Nevertheless the Left side ﬁgure shows a nice decay in the errors
of estimating e 0,z , e 1,z . The Right side ﬁgure shows the gap in expected score between truthful
reporting and misreporting (denoted as ”Reward gap”) with the estimated e 0,z , e 1,z (for the same
simulation setting). Indeed we show truthful reporting is better (positive gap, increasing with more
accurate estimations of e 0,z , e 1,z ) even when majority of people are wrong (as e 0,z = 0.85, e 1,z =
0.83).
4.4 Truth-telling is a dominant strategy
The above results readily imply that our strategy is asymptotically (in K, N ) dominant. To see this,
suppose both ẽ 1,z , ẽ 0,z have converged to their true values. We deﬁne dominant truth serum as
follows:
Mechanism 2 Dominant Truth Serum (DTS)
1. For each task agent i received and reported information, randomly select one of the rest two
reference reports (recall each task is randomly assigned to three agents) as the reference z.
2. When z is uninformative that ẽ 1,z + ẽ 0,z = 1:
• Score agent i zero regardless of his report.
3. When z is informative that ẽ 1,z + ẽ 0,z , 1:
• Score agents via (SSR alpha) deﬁned using z, ẽ 1,z , ẽ 0,z . (with possible scalings)
Note again in above, if the collected reports are in the format of prediction, we will draw a signal
according to the reported prediction - this is the z that we will use.
Theorem 4.4. Asymptotically it is a dominant strategy for agent i to report truthfully under DTS.
Proof. First for the case that ẽ 1,z + ẽ 0,z = 1, it is indiﬀerent for agent i to truthfully report, or
to misreport, or to randomize between the two strategies. Thus truth-telling is a weakly dominant
strategy. When ẽ 1,z +ẽ 0,z , 1, the dominant strategy argument follows from the strictly properness

of (SSR alpha).
Remark 3. Several remarks follow.
• We would like to emphasize again that both z and φ come from D−i : z will be decided by
agents j , i’s reports D−i . φ not only has z as input, but its deﬁnition also depends on e 1,z
and e 0,z , which will be learned from D−i .
• When making decisions on reporting, we show under our mechanisms agents can choose to
be oblivious of how much error presents in others’ reports. This removes the practical concern
of implementing a particular Nash Equilibrium.
• Another salient feature of our mechanism is that we have migrated the cognitive load for
having prior knowledge from agents to the mechanism designer. Yet we do not assume the

14

4 DOMINANT TRUTH SERUM

designer has direct knowledge neither; instead we will leverage the power of estimation from
reported data to achieve our goal.
Now we argue the dominant strategy in ﬁnite sample regime, under noisy estimations. We ﬁrst
deﬁne the informative region. When e 0,z + e 1,z is arbitrarily close to 1, we have the diﬃculty in
determining the number of samples needed for the learning process. With this in mind, we will
modify our mechanism to the following:
• Pre-select a small constant 0 < κ < 1 (but close to 0).
• When |ẽ 1,z + ẽ 0,z − 1| ≤ κ (instead of setting it to be exactly 0; this characterizes our
informative region), pay agent i nothing;
• Else follow our original mechanism and pay according to (SSR alpha).
κ can then help us quantify the number of K, N needed. With this we prove the following theorem:
Theorem 4.5. When set κ small enough, and K, N large enough, we have that with ﬁnite number
of tasks:
(1) For signal elicitation, it is a dominant strategy for each agent i to report si truthfully under
DTS;
(2) For prediction elicitation, it is a dominant strategy to report pi truthfully when S(·) is strictly
concave in report ai and Lipschitz.
(3) For prediction elicitation, it is an ϵ(K, Nq)-dominant strategy to report pi truthfully for any

log K
1
Lipschitz S(·), where ϵ(K, N ) = O N1 +
K + K is a diminishing term in both K and N .

Above we adopt the classical approximate-dominant strategy deﬁnition that truth-telling is ϵdominant strategy if E[φ(Ii , z)] > E[φ(ai , z)] − ϵ, ∀ai , Ii .
The proof for the signal elicitation case is rather straightforward. We need to show that when
the estimation errors of the error rates e 0,z , e 1,z are small enough, the scores under each basic
reporting strategy (truthful, always reverting the observation, always reporting 1 and always reporting 0) will be close to the true score. Then the truthfulness follows from the strict properness
of S. It is slightly more challenging for the prediction elicitation setting (reporting pi s), due to
the continuous reporting space. The main idea is that when the estimation error drops below the
regularization term that corresponds to S’s strict concavity, any possible gain from deviating from
truthful reporting due to the error terms is less than the loss due to the drop in the regularization
term. Note it is not hard to ﬁnd strictly concave scoring function S - both Brier and logarithmic
scores are strictly concave.
4.5

Weak dominance v.s. strong dominance

We have shown when we cannot learn an informative enough reference report from the rest of
the agents, there is very little we can do regarding that. With this note, our deterministic payment
strategy is only weakly dominant. We argue that if agents’ reports can be modeled as being from
certain distributions, the weak dominance case happens rarely.
Í
Denote by X i = ẽ 1,i +ẽ 0,i , the weakly dominant case happens only when j,i X j = 1. Potentially
there are inﬁnitely many strategies that lead to this state. However, suppose agents’ reporting
strategies are drawn from a distribution deﬁned over a continuous space (mixed strategy space),
Í
Í
then we can easily argue that {ω : j,i X j (ω) = 1} (via taking j,i X j as a random variable) is a
zero measure event.
Also we would like to point out that, as long as each agent believes that this uninformative state
happens with probability < 1, DTS induces strong dominant strategy in truthful reporting, as a
non-trivial mix between weak and strong dominance returns strong dominance.

5.1 Learning the error rate

15

Í
Also, as a matter of fact, j,i X j = 1 corresponds to the case that the reference signal is
stochastically irrelevant to the ground truth. Theoretically speaking, there is little one can do for
eliciting private signals using such a reference signal, via a peer prediction method. In practice,
one can use screening tasks to remove some workers to move away from this uninformative state.
5

CORRELATED SIGNALS

Earlier on, we have assumed that agents’ private signals are conditional independent (on ground
truth). In this section, we discuss the generalization of our method to the case when agents’ observations are correlating with each other. The intuition for why we can hope for this extension is
that we do not explore the correlation structure among signals explicitly. Technically this is due
to our scoring system’s dependence on the reference answer z through e 1,z , e 0,z , which is independent of whether z is drawn from a set of independent signals or a set of correlated ones. Being
correlated or not, as long as we can learn the average error rate from the rest of agents, we will
have an unbiased score for each agent w.r.t. the ground truth signal. To extend our results, the
only challenge we need to address is to accurately estimate Pr[z = 1|y = 0], Pr[z = 0|y = 1].
5.1

Learning the error rate

However, learning Pr[z = 1|y = 0], Pr[z = 0|y = 1] with correlated signals is not as straightforward
as before. The reason is in Eqn. (9, 10) of our proposed method in Section 4.2, the second and thirdorder terms for characterizing the matching probability will not hold. Correlation among signals
will violate the product structure of the matching equations we had earlier. Nonetheless we would
like to stick with our idea of using the matching probabilities among agents to obtain additional
information. We show this is not entirely hopeless:
Lemma 5.1. The second order matching probabilities are the same for the cases with correlated and
independent signals:
Pr[z 1 = 1, z 2 = 1|y = 0] + Pr[z 1 = 0, z 2 = 0|y = 0]
= Pr[z 1 = 1|y = 0] Pr[z 2 = 1|y = 0] + Pr[z 1 = 0|y = 0] Pr[z 2 = 0|y = 0]
Pr[z 1 = 1, z 2 = 1|y = 1] + Pr[z 1 = 0, z 2 = 0|y = 1]
= Pr[z 1 = 1|y = 1] Pr[z 2 = 1|y = 1] + Pr[z 1 = 0|y = 1] Pr[z 2 = 0|y = 1]
With above lemma, we know the correlation structure does not aﬀect estimating the second
order matching probability. Similar to what we have detailed earlier that, the ﬁrst order and second
order equation together will help us reduce the possible solutions to at most two pairs. Particularly
we can do the following:
1. Estimate q̃i using {ỹr idx (k) (k), k = 1, 2, ..., K, idx = 1, 2, 3}:
ÍK
1(ỹr 1 (k) (k) = ỹr 2 (k) (k))
.
q̃ −i = k=1
K
i.e., q̃ −i is the empirical matching probability (on both 0 & 1).
2. Solve the following set of equations.
2
2
(I): P0 [e 0,z
+ (1 − e 0,z )2 ] + P1 [e 1,z
+ (1 − e 1,z )2 ] = q̃ −i ,

(II): P0e 0,z + P1 (1 − e 1,z ) = P̃1, −i .
First notice that Eqn. (I) doesn’t contain additional information than
2
P0e 0,z
+ P1 (1 − e 1,z )2 = q 2, −i (please refer to Eqn. (9) in previous estimation)

16

5 CORRELATED SIGNALS

, in light of P0e 0,z + P1 (1 − e 1,z ) as:
2
2
2
P0 [p0,z
+ (1 − p0,z )2 ] + P1 [p1,z
+ (1 − p1,z )2 ] = 2[P0p0,z
+ P1 (1 − p1,z )2 ]

− 2[P0p0,z + P1 (1 − p1,z )] + 1
So they necessarily lead to the same set of solutions, and thus Lemma 4.2 will hold too.
We need a third equation for picking the exact solution. The idea is to similarly check one order
higher matching, but we will use Pr[z 1 = z 2 , z 3 = 1] instead of Pr[z 1 = z 2 = z 3 = 1]. To let our
presentation stay focused, we make the following assumption:
Assumption 1. With three drawn reference signals z 1 , z 2 , z 3 from j , i, we have Pr[z 1 , z 2 , z 3 |y] =
Pr[z 1 , z 2 |y] · Pr[z 3 |y].
That is the conditional dependency is up to order two. This is not entirely unreasonable to assume: when signals’ correlations are due to a common set of observed attributes (e.g., essay length
to essay quality), we can assume that one another signal z 2 already encodes suﬃcient correlational
information with z 1 , and thus the conditional independence between (z 1 , z 2 ) and z 3 . We then note
the following fact: adopting the short-hand notation x 1 := e 0,z , x 2 := 1 − e 1,z we show
Pr[z 1 = z 2 , z 3 = 1] = P0 Pr[z 1 = z 2 , z 3 = 1|y = 0] + P1 Pr[z 1 = z 2 , z 3 = 1|y = 1]
= P0 Pr[z 1 = z 2 |y = 0] Pr[z 3 = 1|y = 0] + P1 Pr[z 1 = z 2 |y = 1] Pr[z 3 = 1|y = 1]
= P0 (x 12 + (1 − x 1 )2 )x 1 + P1 (x 22 + (1 − x 2 )2 )x 2 .
The ﬁrst equation is based on the Bayesian structure of ground truth signal. The second is due
to Assumption 1. The third equation is due to Lemma 5.1. The following Lemma can then be
established:
Lemma 5.2.
x1 + x2 =

1
Pr[z 1 = z 2 , z 3 = 1] − Pr[z 1 = z 2 ] Pr[z 1 = 1]
+
.
2P0 P1 (x 1 − x 2 )2
P0 P1 (x 1 − x 2 )2

Similarly with knowing |x 1 − x 2 | (jointly determined by the ﬁrst order and second order equations, as detailed in Lemma 4.2), we are able to formulate another equation regarding x 1 , x 2 .
All three parameters Pr[z 1 = z 2 , z 3 = 1], Pr[z 1 = z 2 ], Pr[z 1 = 1] are estimable from agents’
reports. Together with P0x 1 + P1x 2 = P1, −i , we are able to solve for x 1 , x 2 . The rest of arguments
follow the proof of Theorem 4.1.
5.2

Application: removing curse of weak signals

Extending our results to the correlated signal case not only removes one technical assumption,
but also helps remove a curse for peer prediction introduced by the existence of weak but strongly
correlated signals. Consider the case where besides the quality signal (i.e., the true signal we really
want to elicit) si , each agent i also observes a cheap signal, denoting as sil . Such cheap signals often
exist in practice. For example in peer grading, the length of an assignment is one of such signals.
Cheap signals are often less accurate than the quality signals in that
Pr[sil = 1|y = 0] > Pr[si = 1|y = 0], Pr[sil = 0|y = 1] > Pr[si = 0|y = 1],
and further such weak signals do not always satisfy conditional independence in that Pr[sil , s lj |y] ,
Pr[sil |y] Pr[s lj |y]. Nonetheless it is also often true that weak signals correlate with each other more
than the quality signals: Pr[sil , s lj |y] > Pr[si , s j |y].
The existence of weak signals has been observed to be harmful in that reporting such weak yet
more correlated signals may lead to higher utilities for agents [Gao et al., 2016], as peer prediction

17

essentially checks the correlation among signals. Suppose si and sil are conditionally independent
given y, formally we prove the following results.
Theorem 5.3. When S is taken as the 1/Prior scoring rule, reporting si (instead of the weak signal
sil ) is a dominant strategy with DTS.
6

DISCUSSIONS AND CONCLUDING REMARKS
Recovering the ground truth. Though being a fundamental step, truthful elicitation is also often
not the ultimate goal, as the mechanism designer may want to infer the ground truth answer in
the end. As a by-product, our framework for inferring the error rates from agents would allow us
to do so. The reasoning is as follows: ﬁrst ask each agent j , i to report a label. If the ground
truth label is 0, the posterior distribution of agents’ reports being 1 will converge to e 0,z with high
probability; while on the other hand, if the ground truth is 1, this posterior distribution converges
to 1 − e 1,z . When e 0,z , 1 − e 1,z (reference answer being informative), we will know the ground
truth label with high probability via posterior distribution testing.
Unbiased estimator of the true score. Our paper proposes a novel and robust way for quantifying
the quality of information when there is no ground truth veriﬁcation, using peer evaluation, as well
as an estimation procedure for learning the bias in peer evaluation. This may ﬁnd applications in a
sequential elicitation setting, where such scores can provide informative feedbacks to contributed
information before the outcome reveals.
Eﬀort exertion. So far our discussion focuses on eliciting truthful reports, our results extend
to the scenario for eliciting high quality data. For instance, when workers can choose to exert
costly eﬀort (consider a binary eﬀort level case, and denote the cost as c for exerting eﬀorts) to
improve the quality of their answers, and once the reference signal is informative (either positively
or negatively), we can scale up the scoring functions to cover the cost c, as similarly done in
[Miller et al., 2005], to establish the dominance of reporting a high-eﬀort signal.
Heterogeneous error rates. In order to estimate error rates correctly, we needed to make the assumption that agents have homogeneous error rates over multiple tasks. We now discuss the
applicability of our method in light of the heterogeneity issue. First we would like to emphasize that in practice, for each set of experiments we can choose to group tasks according to their
types (e.g., image labeling, solving puzzles, objects recognition), and run our mechanism over each
group separately. For this setting, we can assume the homogeneity more comfortably. When it is
not quite possible to group tasks together, suppose that each human agent’s error rates are also
task contingent in that for each possible task, we show our solution can be viewed as a linear
approximation for this task contingent case. We have more details on this matter in the Appendix.
A Machine Learning method. To echo recent works on using machine learning techniques [Liu and Chen,
2017] to learn a machine learning model to generate a reference answer, instead soliciting from
other agents, we show this idea is also ready to be plugged into our SSR solution framework. Consider the current task that needs to be elicited and denote its feature vector as x ∈ Rd . Suppose
we have learned (following the results in [Liu and Chen, 2017], such a classiﬁer is learnable purely
from agent’s reported noisy data) a good classiﬁer f˜ ∗ (x) for predicting its true outcome. Replace
the reference answer z with f˜ ∗ (x) and plug in its error rates. The rest of job is to reason about
e 1,z , e 0,z (for f˜ ∗ (x)). There are possibly many diﬀerent ways to do so. We sketch its possibility
when there is again no ground truth label being available in Appendix.

18

6 DISCUSSIONS AND CONCLUDING REMARKS

Conclusion. In this paper we propose surrogate scoring rules (SSR), which complement the literature of strictly proper scoring rules by considering the setting when there is only access to a
noisy copy of the ground truth. We further extend SSR to the peer prediction setting where the
noisy ground truth can only be inferred via collecting reports from other reference agents. This
returns us a dominant truth serum (DTS), which achieves truthful elicitation in dominant strategy.
REFERENCES
Dana Angluin and Philip Laird. 1988. Learning from noisy examples. Machine Learning 2, 4 (1988), 343–370.
Glenn W Brier. 1950. Veriﬁcation of forecasts expressed in terms of probability. Monthey Weather Review 78, 1 (1950), 1–3.
Tom Bylander. 1994. Learning linear threshold functions in the presence of classiﬁcation noise. In Proceedings of the seventh
annual conference on Computational learning theory. ACM, 340–347.
Anirban Dasgupta and Arpita Ghosh. 2013. Crowdsourced judgement elicitation with endogenous proﬁciency. In Proceedings of the 22nd international conference on World Wide Web. International World Wide Web Conferences Steering
Committee, 319–330.
Rafael Frongillo and Ian A Kash. 2015. Vector-valued property elicitation. In Conference on Learning Theory. 710–727.
Alice Gao, James R Wright, and Kevin Leyton-Brown. 2016. Incentivizing evaluation via limited access to ground truth:
Peer-prediction makes things worse. arXiv preprint arXiv:1606.07042 (2016).
Xi Alice Gao, Andrew Mao, Yiling Chen, and Ryan Prescott Adams. 2014. Trick or treat: putting peer prediction to the test.
In Proceedings of the ﬁfteenth ACM conference on Economics and computation. ACM, 507–524.
Tilmann Gneiting and Adrian E. Raftery. 2007. Strictly Proper Scoring Rules, Prediction, and Estimation. J. Amer. Statist.
Assoc. 102, 477 (2007), 359–378.
Victor Richmond Jose, Robert F. Nau, and Robert L. Winkler. 2006. Scoring Rules, Generalized Entropy and utility maximization. (2006). Working Paper, Fuqua School of Business, Duke University.
R. Jurca and B. Faltings. 2006. Minimum payments that reward honest reputation feedback. In Proceedings of the 7th ACM
conference on Electronic commerce (EC ’06). ACM, 190–199.
Yuqing Kong and Grant Schoenebeck. 2016a. Equilibrium selection in information elicitation without veriﬁcation via
information monotonicity. arXiv preprint arXiv:1603.07751 (2016).
Yuqing Kong and Grant Schoenebeck. 2016b. A Framework For Designing Information Elicitation Mechanisms That Reward
Truth-telling. arXiv preprint arXiv:1605.01021 (2016).
N.S. Lambert, D.M. Pennock, and Y. Shoham. 2008. Eliciting properties of probability distributions. In Proceedings of the
9th ACM Conference on Electronic Commerce (EC ’08). ACM, 129–138.
Yang Liu and Yiling Chen. 2017. Machine Learning aided Peer Prediction. ACM EC (June 2017).
Yang Liu and Mingyan Liu. 2015. An Online Learning Approach to Improving the Quality of Crowd-Sourcing. In Proceedings
of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS
’15). ACM, New York, NY, USA, 217–230. DOI:http://dx.doi.org/10.1145/2745844.2745874
James E Matheson and Robert L Winkler. 1976a. Scoring rules for continuous probability distributions. Management science
22, 10 (1976), 1087–1096.
James E. Matheson and Robert L. Winkler. 1976b. Scoring Rules for Continuous Probability Distributions. Management
Science 22, 10 (1976), 1087–1096.
Aditya Menon, Brendan Van Rooyen, Cheng Soon Ong, and Bob Williamson. 2015. Learning from corrupted binary labels
via class-probability estimation. In International Conference on Machine Learning. 125–134.
Nolan Miller, Paul Resnick, and Richard Zeckhauser. 2005. Eliciting Informative Feedback: The Peer-Prediction Method.
Management Science 51, 9 (2005), 1359 –1373.
Allan H Murphy and Robert L Winkler. 1970. Scoring rules in probability assessment and evaluation. Acta psychologica 34
(1970), 273–286.
Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. 2013. Learning with noisy labels. In
Advances in neural information processing systems. 1196–1204.
Dražen Prelec. 2004. A Bayesian Truth Serum for Subjective Data. Science 306, 5695 (2004), 462–466.
G. Radanovic and B. Faltings. 2013. A Robust Bayesian Truth Serum for Non-Binary Signals. In Proceedings of the 27th
AAAI Conference on Artiﬁcial Intelligence (AAAI ’13).
Leonard J Savage. 1971. Elicitation of personal probabilities and expectations. J. Amer. Statist. Assoc. 66, 336 (1971), 783–801.
Clayton Scott. 2015. A Rate of Convergence for Mixture Proportion Estimation, with Application to Learning from Noisy
Labels.. In AISTATS.
Clayton Scott, Gilles Blanchard, Gregory Handy, Sara Pozzi, and Marek Flaska. 2013. Classiﬁcation with Asymmetric Label
Noise: Consistency and Maximal Denoising.. In COLT. 489–511.

19

V. Shnayder, A. Agarwal, R. Frongillo, and D. C. Parkes. 2016. Informed Truthfulness in Multi-Task Peer Prediction. ACM
EC (March 2016). arXiv:cs.GT/1603.03151
Brendan van Rooyen and Robert C Williamson. 2015. Learning in the Presence of Corruption. arXiv preprint
arXiv:1504.00091 (2015).
Robert L. Winkler. 1969. Scoring rules and the evaluation of probability assessors. J. Amer. Statist. Assoc. 64, 327 (1969),
1073–1078.
Jens Witkowski, Pavel Atanasov, Lyle H Ungar, and Andreas Krause. 2017. Proper proxy scoring rules.
Jens Witkowski, Yoram Bachrach, Peter Key, and David C. Parkes. 2013. Dwelling on the Negative: Incentivizing Eﬀort in
Peer Prediction. In Proceedings of the 1st AAAI Conference on Human Computation and Crowdsourcing (HCOMP’13).
J. Witkowski and D. Parkes. 2012. A Robust Bayesian Truth Serum for Small Populations. In Proceedings of the 26th AAAI
Conference on Artiﬁcial Intelligence (AAAI ’12).

20

6 DISCUSSIONS AND CONCLUDING REMARKS

APPENDIX

PROOF OF LEMMA 2.2
Proof. Suppose not we will have
Pr[y = 0|si = 0] = Pr[y = 0|si = 1],

(13)

Pr[y = 1|si = 0] = Pr[y = 1|si = 1].

(14)

From Eqn. (13) we know that
Pr[y = 0, si = 1] Pr[y = 0, si = 0]
=
Pr[si = 1]
Pr[si = 0]
Pr[y = 0](1 − e 0,i )
Pr[y = 0]p0,i
=
,
⇔
Pr[si = 1]
Pr[si = 0]
when Pr[y = 0] , 0 we know that
e 0,i
Pr[si = 1]
.
=
Pr[si = 0] 1 − e 0,i

(15)

Pr[si = 1] 1 − e 1,i
.
=
Pr[si = 0]
e 1,i

(16)

Similarly from Eqn. (14) we know

Therefore we know

e 0, i
1−e 0, i

=

1−e 1, i
e 1, i

from which we know e 0,i + e 1,i = 1. Contradiction.



PROOF OF LEMMA 3.1
Proof. This can be fairly easily established by noting the following: by truthful reporting agent
i’s expected score is
Pr[y = si |si ] Pr[y = si ]
>
= 1.
E[S(si , y)|si ] =
Pr[y = si ]
Pr[y = si ]
On the other hand, by reverting the observation, the agent has
E[S(1 − si , y)|si ] =

Pr[y = 1 − si |si ] Pr[y = 1 − si ]
<
= 1.
Pr[y = 1 − si ]
Pr[y = 1 − si ]

Both of above inequalities are due to Bayesian informativeness (and correspondingly negative
Bayesian informativeness).

PROOF OF THEOREM 4.3
Proof. Estimation error due to heterogeneous agents: The ﬁrst challenge lies in the fact that the
higher order equations doesn’t capture the true matching probability with heterogeneous workers.
If we assign one task (to be labeled) to two diﬀerent workers, due to the asymmetric error rate,
the LHS of Eqn. (I) is not precise– drawing a worker without replacement leads to a diﬀerent
labeling accuracy, and will complicate the solution for the system of equations. We show that our
estimation, though being ignoring above bias, will not aﬀect our results by too much: denoting by
e 1 the accuracy of ﬁrst drawn sample (for checking the matching) when y = 1 (we can similarly
argue for y = 0). Then we have E[e 1 ] = e 1,z . And the average accuracy of the second drawn

21

sample e 2 (conditional on e 1 ) is given by
following:

e 1, z (N −1)−e 1
.
N −2

Further the matching probability satisﬁes the



E[e 1 · e 2 ] = E E[e 1 · e 2 |e 1 ]


e 1,z (N − 1) − e 1
=E e 1 ·
N −2
e 1,z (N − 1) E[e 12 ]
=E[e 1 ] ·
−
N −2
N −2
E[e 12 ]
N −1 2
e −
=
N − 2 1,z N − 2
Note both e 1,z and E[e 12 ] are no more than 1. Then
|

2 |
|e 1,z
E[e 12 ]
E[e 12 ]
N −1
2
2
e 1,z −
− e 1,z
|≤
+
≤
.
N −2
N −2
N −2 N −2 N −2

That the estimated quantity is bounded away from the true parameter by at most Θ(1/N ). Similarly
for the third order equation we have
3
|E[e 1 · e 2 · e 3 ] − e 1,z
|≤

3
.
N −3

Estimation errors due to ﬁnite estimation samples: The second sources of errors come from the
estimation errors of q̃ 2, −i , q̃ 3, −i and P̃1, −i . We have the following lemma:
Lemma 6.1. When there are K samples for estimating q̃ 2, −i , q̃ 3, −i and P̃1, −i respectively (total budgetlog 6/δ
ing 3K) and K ≥ 2ϵ 2 for any ϵ, δ > 0, we have with probability at least 1 − δ
|q̃ 2, −i − q 2, −i | ≤ ϵ +

3
2
, |q̃ 3, −i − q 3, −i | ≤ ϵ +
, |P̃1, −i − P1, −i | ≤ ϵ.
N −2
N −3

The above lemma can be easily established using Chernoﬀ bound, and our arguments in estimating with heterogeneous agents above. We now bound the error in estimating p0,z , p1,z , under
the (ϵ, δ )-event proved in Lemma 6.1. First of all
|e˜0,z





q̃ 3, −i − q̃ 2, −i P̃1, −i
q 3, −i − q 2, −i P1
1
1
P1 − P̃1, −i −
− e 0,z | = |
P1 − P1, −i
P1 − P0 q̃ 2, −i − (P̃1, −i )2
P1 − P0
q 2, −i − P12


q̃ 3, −i − q̃ 2, −i P̃1, −i q 3, −i − q 2, −i P1
1
|
|P
+
|
P̃
−
P
|
≤
−
1
1, −i
1, −i .
P1 − P0 q̃ 2, −i − (P̃1, −i )2
q 2, −i − P12

According to Lemma 7 of [Liu and Liu, 2015], which we reproduce as follows:
Lemma 6.2. For k ≥ 1 and two sequences {li }im=1 and {qi }im=1 and 0 ≤ li , qi ≤ 1, ∀i = 1, ..., k., we
have
|

m
Ö
i =1

li −

m
Ö
j=1

qj | ≤

m
Õ
i =1

|li − qi | .

(17)

22

6 DISCUSSIONS AND CONCLUDING REMARKS

We know the following facts
2
N −2
− q 2, −i P1, −i |

|q̃ 2, −i − (P̃1, −i )2 ) − (q 2, −i − P1,2 −i )| ≤ |(P̃1, −i )2 − P1,2 −i | + |q̃ 2, −i − q 2, −i | ≤ 3ϵ +
|(q̃ 3, −i − q̃ 2, −i P̃1, −i ) − (q 3, −i − q 2, −i P1, −i )| ≤ |q̃ 3, −i − q 3, −i | + |q̃ 2, −i P̃1, −i
2
3
≤ 3ϵ +
+
.
N −2 N −3
First we prove that

q 2, −i − P1,2 −i =P0x 12 + P1x 22 − (P0x 1 + P1x 2 )2 = P0 P1 (x 1 − x 2 )2 ≥ P0 P1κ 2 .
Let 3ϵ +

2
N −2

|

≤ P0 P1κ 2 /2, we know that (using mean-value theorem/inequality)

q̃ 3, −i − q̃ 2, −i P̃1, −i
q̃ 2, −i − (P̃1, −i

)2

−

q 3, −i − q 2, −i P1, −i
q̃ 3, −i − q̃ 2, −i P̃1, −i q 3, −i − q 2, −i P1, −i
−
|
|≤|
2
q 2, −i − P1
q̃ 2, −i − (P̃1, −i )2
q̃ 2, −i − (P̃1, −i )2
q 3, −i − q 2, −i P1, −i q 3, −i − q 2, −i P1, −i
|
+|
−
q 2, −i − P1,2 −i
q̃ 2, −i − (P̃1, −i )2

≤2

ϵ+

2
3
N −2 + N −3
κ 2 P02 P12

+2

2
N −2
.
(κ 2 P02 P12 )2

ϵ+

Together we proved that
|e˜0,z



ϵ + N2−2 + N3−3
ϵ + N2−2
1
2P1
+ 2P1 2 2 2 2 + ϵ .
− e 0,z | ≤
P1 − P0
κ 2 P02 P12
(κ P0 P1 )

Similarly we are able to work out sensitivity analysis for e 1,z that


ϵ + N2−2
ϵ + N2−2 + N3−3
1
|e˜1,z − e 1,z | ≤
+ 2P0 2 2 2 2 + ϵ .
2P0
P1 − P0
κ 2 P02 P12
(κ P0 P1 )
q
log K 
. With the error rates bounds for
Summarizing and set δ = O( K1 ) we have ϵ = O N1 +
K
e 0,z , e 1,z , from Lemma 5.4 [Liu and Chen, 2017], which we reproduce in our contexts as follows:
Lemma 6.3. When K, N are large enough s.t. ϵ ≤ (1 −e 0,z −e 1,z )/4 := ∆e , with probability at least
e
1 − 2δ , |φ̃(t, y) − φ(t, y)| ≤ 1+∆
· ϵ.
2∆2
e

We then obtain a bound on estimating φ(·).



PROOF OF THEOREM 4.5
Proof. Suppose |e 0,z + e 1,z − 1| ≥ 2κ. Then when the estimation errors are small enough such
that |ẽ 0,z − e 0,z | + |ẽ 1,z − e 1,z | ≤ κ, we know that |ẽ 0,z + ẽ 1,z − 1| ≥ κ. Denote by
∆φ = E[S(si , y)] − max E[S(ai , y)],
ai ,si

the minimum gap between the scores for truthfully reporting and mis-reporting. We can easily
show that ∆φ > 0 for signal elicitation case, as we can take ai to be the three basis of mis-reporting:
always reverting the observation, always reporting 1 and always reporting 0. Then with a noisy
estimation of φ(·), we have (using Theorem 4.3)
|E[φ̃(ai , z)] − E[φ(ai , z)]| ≤ ϵ1 + δ 1 · max φ̃, ∀ai .

23

Above, we implicitly assumed the boundedness of φ̃(·): notice with bounded scoring function
S
. Since E[φ(si , z)] = E[S(si , y)], choose ϵ1 , δ 1 such that
S, indeed we know that max φ̃ ≤ 2 max
κ
ϵ1 + δ 1 · max φ̃ < ∆φ /2 we will have (for ai , si )
E[φ̃(si , z)] > E[S(si , y)] − ∆φ /2
> E[S(ai , y)] + ∆φ /2 > E[φ̃(ai , z)].
i.e., the strict properness will preserve, under the noisy estimations. From above results we also
observe that a larger ∆φ will allow more noisy estimations. We thus can trade more payment with
sample complexity, via designing the strictly proper scoring functions to increase ∆φ .
Now consider the prediction elicitation case. Suppose that S(p, y) is strictly concave w.r.t. p ∀y
with parameter λ.
˜ i , y) = S(ai , y) + ϵ(ai , y) ,
S(a
where ϵ(ai , y) indicates the error term. First notice that
E[S(ai , y)] − E[S(ai′ , y)] ≥ λ|ai − ai′ |.
Further we notice that
˜ i , y) − S(ai , y)
ϵ(ai , y) = S(a
1 − ẽ 1−y,z
1 − e 1−y,z
−
)S(ai , y)
1 − ẽ 1,z − ẽ 0,z 1 − e 1,z − e 0,z
ey,z
ey,z
−
)S(ai , −y).
−(
1 − e 1,z − e 0,z 1 − e 1,z − e 0,z
Due to the sample complexity results we know that with probability at least 1 − δ that
1 − ẽ 1−y,z
1 − e 1−y,z
|
−
| ≤ ϵ1 ,
1 − ẽ 1,z − ẽ 0,z 1 − e 1,z − e 0,z
ey,z
ey,z
−
| ≤ ϵ1 .
|
1 − e 1,z − e 0,z 1 − e 1,z − e 0,z
=(

Suppose S(p, y) is also Lipschitz w.r.t. p ∀y with parameter L. By Lipschitz conditions we know
that
δ
|E[ϵ(ai , y)] − E[ϵ(ai , y)]| ≤ ϵ1 L · |ai − ai′ | + 2 L · |ai − ai′ |.
κ
Therefore when ϵ1 , δ are small enough such that
δ
ϵ1 L + 2 L < λ,
κ
no deviation is proﬁtable.
q

log K
1
The ϵ(K, N ) = ϵ1 L + κδ2 L = O N1 +
K + K -dominant strategy argument follows naturally
from above error term analysis. We will not repeat the details.

HETEROGENEOUS ERROR RATES ACROSS TASKS
In order to estimate error rates correctly, we needed to make the assumption that human workers
have homogeneous error rates across multiple tasks. We now discuss the applicability of our
method in light of the heterogeneity issue. Before starting, we would like to emphasize that in
practice, for each set of experiments we can choose to group tasks according to their types (e.g.,
image labeling, solving puzzles, objects recognition), and run our mechanism over each group
separately. For this setting, we can assume the homogeneity more comfortably.

24

6 DISCUSSIONS AND CONCLUDING REMARKS

Nonetheless when it is not quite possible to group tasks together, suppose that each human
agent’s error rates are also task contingent in that for each possible task x with y ∼ P := {P0 , P1 }
we have e 0,i (y), e 1,i (y). Redeﬁne the error rate of the reference answer as follows:
Í
Í
j,i Ex,y |y=0 [ẽ 0, j (x)]
j,i Ex,y |y=1 [ẽ 1, j (x)]
, e 0,z =
.
e 1,z =
N −1
N −1
Again e 1,z , e 0,z captures the error rate of the reference answer. With knowing e 1,z , e 0,z , the dominant strategy argument in Theorem 3.4 holds.
So far so good. However it becomes less clear in how to estimate e 1,z , e 0,z . If we follow the idea
in Section 4.2, the ﬁrst order equation holds as before
Í
Í
j,i Ex,y |y=0 [ẽ 0, j (x)]
j,i Ex,y |y=1 [ẽ 1, j (x)]
P0
+ P1 (1 −
) = P1, −i ,
N −1
N −1
i.e., P0e 0,z + P1 (1 − e 1,z ) = P1, −i . However the higher order matching statistics appear to be
very diﬀerent. For example, the second order matching probability between two agents on label 1
becomes
Í
Í
2
2
j,i Ex,y |y=0 [ẽ 0, j (x)]
j,i Ex,y |y=1 [1 − ẽ 1, j (x)]
P0
+ P1
= P1, −i ,
N −1
N −1
Instead we would like a equation as a function of
Í
2  Í
2
j,i Ex,y |y=0 [ẽ 0, j (x)]
j,i Ex,y |y=1 [1 − ẽ 1, j (x)]
,
N −1
N −1
in order to identify the true error rates on average. To get around of this issue, we can adopt the
following approximation for ẽ 0,2 j (x) using Taylor expansion:
2
2
ẽ 0,2 j (x) ≈ e 0,z
+ 2e 0,z (ẽ 0, j (x) − e 0,z ) = 2e 0,z · ẽ 0, j (x) − e 0,z
.

Then we claim that
Í

j,i

Ex,y |y=0 [ẽ 0,2 j (x)]
N −1

≈

Í

j,i

2 ]
Ex,y |y=0 [2e 0,z · ẽ 0, j (x) − e 0,z

N −1
2
2
= 2e 0,z · e 0,z − e 0,z
= e 0,z

Similarly we have
Í

j,i

Ex,y |y=1 [1 − ẽ 1,2 j (x)]

≈ (1 − e 1,z )2 .
N −1
From above, we see we are able to recover the matching equations deﬁned in our earlier solution
for task homogeneous cases; and it can be viewed as a linear approximation for this task contingent
case.
PROOF OF LEMMA 5.1
Proof. W.l.o.g., consider y = 0. We ﬁrst derive the following diﬀerence term
Pr[z 1 = 1, z 2 = 1|y = 0] − Pr[z 1 = 1|y = 0] Pr[z 2 = 1|y = 0]
= (Pr[z 1 = 1|z 2 = 1, y = 0] − Pr[z 1 = 1|y = 0]) Pr[z 2 = 1|y = 0]
= (Pr[z 1 = 1|z 2 = 1, y = 0] − Pr[z 1 = 1|z 2 = 1, y = 0] Pr[z 2 = 1|y = 0]
− Pr[z 1 = 1|z 2 = 0, y = 0] Pr[z 2 = 0|y = 0]) Pr[z 2 = 1|y = 0]
= Pr[z 2 = 0|y = 0] Pr[z 2 = 1|y = 0](Pr[z 1 = 1|z 2 = 1, y = 0] − Pr[z 1 = 1|z 2 = 0, y = 0]).

25

On the other hand,
Pr[z 1 = 0, z 2 = 0|y = 0] − Pr[z 1 = 0|y = 0] Pr[z 2 = 0|y = 0]
= (Pr[z 1 = 0|z 2 = 0, y = 0] − Pr[z 1 = 0|y = 0]) Pr[z 2 = 0|y = 0]
= (Pr[z 1 = 0|z 2 = 0, y = 0] − Pr[z 1 = 0|z 2 = 0, y = 0] Pr[z 2 = 0|y = 0]
− Pr[z 1 = 0|z 2 = 1, y = 0] Pr[z 2 = 1|y = 0]) Pr[z 2 = 0|y = 0]
= Pr[z 2 = 0|y = 0] Pr[z 2 = 1|y = 0](Pr[z 1 = 0|z 2 = 1, y = 0] − Pr[z 1 = 0|z 2 = 0, y = 0]).
The above two terms add up to 0. The proof for y = 1 is symmetric. Proved.



PROOF OF LEMMA 5.2
Proof.
Pr[z 1 = z 2 , z 3 = 1] − Pr[z 1 = z 2 ] Pr[z 1 = 1] = P0 (x 12 + (1 − x 1 )2 )x 1 + P1 (x 22 + (1 − x 2 )2 )x 2


− P0 (x 12 + (1 − x 1 )2 ) + P1 (x 22 + (1 − x 2 )2 ) (P0x 1 + P1x 2 )
= P0 P1 (x 1 − x 2 )2 (2(x 1 + x 2 ) − 1).

(18)

Similarly with knowing |x 1 −x 2 | (jointly determined by the ﬁrst order and second order equations,
as detailed in Lemma 4.2), we are able to formulate another equation regarding x 1 , x 2 that
x1 + x2 =

1
Pr[z 1 = z 2 , z 3 = 1] − Pr[z 1 = z 2 ] Pr[z 1 = 1]
+
.
2P0 P1 (x 1 − x 2 )2
P0 P1 (x 1 − x 2 )2


PROOF OF THEOREM 5.3
Proof. We only need to prove for the case when si , sil , there is no incentive for agents to
report sil . With accurately learning e 0,z , e 1,z , we know
E[φ(ai , z)|si , sil ] = E[S(ai , y)|si , sil ] =

Pr[y = ai |si , sil ]
Pr[y = ai ]

Suppose si = 1 − ŝ, sil = ŝ. Next we prove that
Pr[y = 1 − ŝ|si = 1 − ŝ, sil = ŝ] > P1−ŝ
Pr[y = ŝ |si = 1 − ŝ, sil = ŝ] < Pŝ
following which, our claim is clearly true. First
ˆ sil = ŝ] =
Pr[y = ŝ |si = 1 − s,
=

ˆ si = 1 − ŝ, sil = s]
ˆ
Pr[y = s,

Pr[si = 1 − ŝ, sil = ŝ |y = ŝ]Py=ŝ
Pr[si = 1 − ŝ, sil = ŝ]

ˆ
Pr[si = 1 − ŝ, sil = s]
.

26

6 DISCUSSIONS AND CONCLUDING REMARKS

Then
ˆ < Pŝ
Pr[y = ŝ |si = 1 − ŝ, sil = s]
ˆ < Pr[si = 1 − s,
ˆ sil = ŝ]
⇔ Pr[si = 1 − ŝ, sil = ŝ |y = s]
Õ
Pŷ · Pr[si = 1 − ŝ|y = ŷ] Pr[sil = ŝ |y = ŷ]
⇔ Pr[si = 1 − ŝ |y = ŝ] Pr[sil = ŝ|y = ŝ] <
ŷ

⇔ Pr[si = 1 − ŝ |y =
⇔ Pr[si = 1 − ŝ |y =

ŝ](1 − Pr[sil = 1 − ŝ |y = ŝ])
ŝ] < Pr[sil = 1 − ŝ|y = ŝ],

< (1 − Pr[si = 1 − ŝ |y = ŝ]) Pr[sil = 1 − ŝ|y = ŝ]

which holds by the deﬁnition of weak signal (a higher error rate).



A MACHINE LEARNING METHOD
Suppose that each task is associated with a corresponding feature vector. Consider the current
task that needs to be elicited and denote its feature vector as x ∈ Rd . Suppose we have learned
(following the results in [Liu and Chen, 2017], such a classiﬁer is learnable purely from agent’s
reported noisy data) a good classiﬁer f˜ ∗ (x) for predicting its true outcome. Our ML-aided SSR
simply works in the following ways: replacing the reference answer z with f˜ ∗ (x) and plug in its
error rates. The rest of job is to reason about e 1,z , e 0,z (for f˜ ∗ (x)). There are possibly many diﬀerent
ways of doing so. We demonstrate its possibility when there is again no ground truth label being
available with the following simple estimation procedure:
• Assign K tasks x1 , x2 , ..., xK to three randomly drawn peers, denote them as ziref (xk ), i =
1, 2, 3, k = 1, 2, ..., K.
• Estimate Pr[ f˜ ∗ (xi ) = z 1ref (xi ) = 1] and Pr[ f˜ ∗ (xi ) = 1].
• Estimate Pr[z 1ref (xi ) = 1|y = 0] (follow Mechanism 1) using the three reference answers
ziref (xk ), i = 1, 2, 3, k = 1, 2, ..., K.
Then note the following fact:
Pr[ f˜ ∗ (xi ) = z ref (xi ) = 1] = P0 Pr[ f˜ ∗ (xi ) = 1|y = 0] Pr[z ref (xi ) = 1|y = 0]
1

1

+ P1 Pr[ f˜ ∗ (xi ) = 1|y = 1] Pr[z 1ref (xi ) = 1|y = 1]
Together with
Pr[ f˜ ∗ (xi ) = 1] = P0 Pr[ f˜ ∗ (xi ) = 1|y = 0] + P1 Pr[ f˜ ∗ (xi ) = 1|y = 1],
we will be able to solve for e 1,z , e 0,z when we have a good estimates of Pr[ f˜ ∗ (xi ) = z 1ref (xi ) = 1] and
Pr[ f˜ ∗ (xi ) = 1], and that Pr[z 1ref (xi ) = 1|y = 0] , Pr[z 1ref (xi ) = 1|y = 1]. With above argument, we
see that we will be able to achieve dominant strategy scorings without even the need of reassigning
all tasks.

