A Truth Serum for Large-Scale Evaluations
Vijay Kamble1 , David Marn3 , Nihar Shah2 , Abhay Parekh3 , and Kannan Ramachandran3
1

University of Illinois at Chicago, kamble@uic.edu
Carnegie Mellon University, nihars@cs.cmu.edu
3
University of California, Berkeley, {marn, parekh, kannanr}@eecs.berkeley.edu

arXiv:1507.07045v4 [cs.GT] 16 Feb 2018

2

February 20, 2018

Abstract
A major challenge in obtaining large-scale evaluations, e.g., product or service reviews on
online platforms, labeling images, grading in online courses, etc., is that of eliciting honest
responses from agents in the absence of verifiability. We propose a new reward mechanism with
strong incentive properties applicable in a wide variety of such settings. This mechanism has a
simple and intuitive output agreement structure: an agent gets a reward only if her response
for an evaluation matches that of her peer. But instead of the reward being the same across
different answers, it is inversely proportional to a popularity index of each answer. This index
is a second order population statistic that captures how frequently two agents performing the
same evaluation agree on the particular answer. Rare agreements thus earn a higher reward
than agreements that are relatively more common.
In the regime where there are a large number of evaluation tasks, we show that truthful
behavior is a strict Bayes-Nash equilibrium of the game induced by the mechanism. Further,
we show that the truthful equilibrium is approximately optimal in terms of expected payoffs
to the agents across all symmetric equilibria, where the approximation error vanishes in the
number of evaluation tasks. Moreover, under a mild condition on strategy space, we show that
any symmetric equilibrium that gives a higher expected payoff than the truthful equilibrium
must be close to being fully informative if the number of evaluations is large. These last two
results are driven by a new notion of an agreement measure that is shown to be monotonic in
information loss. This notion and its properties are of independent interest.

1

Introduction

Systems that leverage the wisdom of the crowd are ubiquitous today. Feedback and reputation
systems, in which people provide ratings and reviews for entities based on their personal experiences,
are a critical component of online platforms and marketplaces [Luc17]. Commercial crowd-sourcing
platforms such as Amazon Mechanical Turk, where workers perform microtasks in exchange for
payments over the Internet, are employed for a variety of purposes such as collecting labeled data to
train machine learning algorithms [RYZ+ 10]. In massive open online courses (MOOCs), students’
exams or assignments are often evaluated by means of peer-grading, where the students grade each
others’ work [PHC+ 13].
A major practical challenge in these systems is that of eliciting truthful and high-quality responses
from the agents. In the absence of appropriate incentives, agents could shirk investing effort,
1

provide uninformative feedback, or could even try to exploit these systems for selfish motives, thus
undermining their utility. For instance, recent works have found significant empirical evidence of
bias in user ratings on many online platforms [HG15, NT15]. In this work, we design a new and
simple reward mechanism with strong incentive properties that attempts to address this concern in
a wide variety of situations.
We consider a general setup, where a principal is interested in obtaining responses for a large
number of evaluation tasks from a pool of agents. Our central assumption is that in each evaluation task, the population performing that evaluation is statistically homogeneous, that is, the true
response of each agent is an independent sample from an unknown distribution of answers, which
is common across agents. For example, this is the case for objective questions like:
1. What was your waiting time to get a table in the restaurant? (Less than 15 mins/Between
15-30 mins/More than 30 mins)
2. Did the handyman show up on time for your appointment? (Yes/No)
3. Did the received product match the description given by the seller? (Yes/No)
In each of these questions, the answer is independent of the personal preferences and individual
characteristics of the evaluating agent. In the first situation, we can assume that each customer
experiences an independently sampled waiting time from a common unknown distribution that is
specific to that restaurant. In the second situation, the customer’s experience is sampled from the
distribution of whether or not the handyman is punctual. Similarly, in the third question, the
customer’s true experience is a sample of the selling practices of the seller.
Moreover, population homogeneity is a reasonable assumption for surveys comprising of questions
regarding subjective preferences, like,
4. Do you prefer cats or dogs?
5. What type of movies do you prefer? (Action/Comedy/Drama/..)
6. What color do you prefer for the walls in your local Starbucks1 ? (Green/White/Blue/..)
In each of these cases, the agent’s preferences can be seen as a sample from a common distribution of
population preferences, where this distribution could be specific to certain features of the population,
e.g., a geographical region, gender, ethnicity, etc.
When the principal either has access to the true answers for some of the evaluation tasks or
can verify the answers accurately, she can score the agents based on their performance on these
tasks. Proper scoring rules [Bri50, GR07, Sav71, LS09] provide a precise and elegant framework
to induce truthfulness in such cases. This approach, coupled with the anonymity of these special
tasks, incentivizes truthful behavior in all evaluations as long as the threat of being scored on a
verifiable task is high enough relative to the incentive to shirk effort or to lie [GWLB16].
On the other hand, such an approach is impractical in cases where either the true responses
are intrinsically unknowable to the principal because of their subjectivity or are difficult to obtain
in significant numbers. In such cases, the alternative is to score the agents’ responses based on
comparisons with the responses of other agents who have provided answers for the same or similar
1

Starbucks is a chain of coffee shops.

2

questions [MRZ05]. The situation is then inherently strategic, in which one hopes to sustain truthful
reporting as an equilibrium of a game that the scoring mechanism induces. The present work falls
into this category.
When the population is homogeneous, the true responses of the agents are an informative sample
of the unknown distribution of answers across the population for the same question. This correlation
between an agent’s response and the response of a typical agent in the population provides key
leverage to the principal in designing incentive mechanisms. This is not necessarily the case when the
population is heterogeneous, i.e., when the agents’ responses strongly depend on their characteristics
that vary widely across the population. For instance, consider the question: Did you like this movie?
The answer to this question would depend on the personal preferences of the agent – one agent could
strongly prefer action movies, while some other agent could strongly prefer dramas. In both these
extreme cases, the ratings given by these agents reveal little information about the average rating
that the movie is expected to receive. One encounters similar problems while implementing peergrading for certain kinds of courses where clear rubrics for grading are difficult to specify, and the
grade assignment could depend on individual characteristics of the graders. In these cases, designing
mechanisms that induce truthfulness is inherently harder, and in some settings even impossible
[RF15].2
In the homogeneous population setting in the absence of verifiability, the pioneering work
[MRZ05] described the ‘Peer Prediction’ mechanism that incentivizes truthful answers to a single evaluation task. The main requirement is that there is a commonly held prior on the unknown
distribution from which the agents’ answers are sampled, and this prior is known to the principal.
Truthfulness is achieved by scoring an agent’s prediction of her peer’s answer, as implied by her own
answer, using a proper scoring rule (hence the name). Another influential design in this domain, the
Bayesian Truth Serum (BTS) [Pre04], and its subsequent refinements [WP12b, RF13], preserved
the common prior assumption but relaxed the requirement that the principal needs to know this
prior.3 But these mechanisms instead require the agents to make extraneous reports about their
beliefs in addition to their answers. Such extraneous reports of beliefs, although undesirable, are
indispensable in this setting, since it has been shown that it is impossible to design mechanisms
that incentivize truthfulness without utilizing some information about the agents’ belief structure
[JF11].
A common feature of the applications that we consider is that they involve a large number of
similar evaluation tasks, although every agent performs only a small subset of these tasks. For
instance, there are thousands of similar restaurants (with similar existing ratings) listed on review
platforms like Yelp that users rate. Online marketplaces like Amazon or eBay would like to obtain
reviews for a large number of existing sellers on these platforms. The coffee chain Starbucks may
be interested in learning customer preferences for the wall color or the temperature of the coffee in
all of its stores across the country.
The presence of multiple similar tasks hints at an approach for circumventing the strong knowl2
Nevertheless, we are optimistic that designing good mechanisms for homogeneous settings is expected to help
heterogeneous settings as well. The primary reason is that in many cases, it is possible to categorize a heterogeneous
population into homogeneous sub-groups by asking preliminary questions, where the population can be assumed to
be homogeneous with respect to the answers to these preliminary questions. For instance, in the example above,
before asking an agent whether or not she liked a movie, one could ask what type of movies she prefers. Before
allotting an assignment for grading to a student, one could ask the grader what subject areas she is comfortable
with grading. A similar approach that relies on ‘clustering’ heterogeneous agents has been proposed recently in this
domain [AMPS17].
3
[WP12a] later relaxed the common prior assumption for the case of binary evaluations.

3

edge assumptions that are necessary for designing mechanisms that do not require extraneous
belief reports from agents (such mechanisms have been called ‘minimal’ in literature). This information can instead be replaced by consistent statistical estimates obtained from the response
data across multiple tasks. Recently, several designs have successfully exploited this possibility
[JF11, WP13, DG13, SAFP16, RF15, RFJ16, LC17]. Of course, this assumes that the responses
are truthful. But it turns out that in many of these situations, truthfulness becomes a self-fulfilling
prophecy – truthful behavior is an equilibrium in the induced game when the mechanism simply
assumes that these reports are truthful. This is the basic principle underlying our design.
Our mechanism builds upon the structure of output agreement mechanisms [VAD08, VAD04]
that are simple, intuitive, and have been quite popular in practice, except they suffer from a critical
drawback of not incentivizing truthful responses in general. In an output agreement mechanism,
two agents answer the same question, and they are both rewarded if their answers match. Under
such a scheme, the agents tend to gravitate towards answers that are more likely to be popular
rather than submitting their true responses. Our mechanism overcomes this drawback by giving
proportionately lower rewards for answers that turn out to be more popular. This is achieved by
inversely scaling the rewards for agreement by a popularity index for each answer. This is not a new
idea: such biased output agreement schemes have been explored earlier in prior works; for instance,
a well-known scheme of this type is the ‘Peer Truth Serum’ [JF11, RFJ16].
The key innovation in our design relative to these works is in the way these popularity indices
are defined. In fact, all the strong incentive properties of our mechanism trace their origin to this
novel definition. In our mechanism, these indices are certain second order population statistics that
capture how frequently two people performing the same task agree on a particular answer on average
across all tasks. Thus rare agreements receive higher rewards than agreements that are relatively
common. As the number of tasks increases, the accuracy of these indices improves and truthfulness
is obtained as a Bayes-Nash equilibrium when the number of tasks is large enough. A common
prior is not necessary for this result; it should just be common knowledge that the prior satisfies
a certain non-degeneracy property (this property is related to the ‘stochastic relevance’ condition
that appears frequently in this domain; for instance, in [MRZ05]).
An important goal for any payment mechanism is to strictly incentivize truthfulness. That
is, it is not sufficient to ensure that truthful behavior is simply an equilibrium in the resulting
game. It is also important to ensure that at equilibrium, each agent gets a strictly higher reward
by being truthful than by adopting any other strategy. Mechanisms that achieve this are referred
to as ‘strictly proper’ in literature. Without this requirement, trivial mechanisms like the one
that gives a fixed payment to each agent already, in principle, weakly incentivize truthfulness.
Moreover, it is also important to ensure that at the truthful equilibrium, the difference in the payoffs
to an agent resulting from the truthful strategy and any strategy in which an agent’s reported
response is independent of her true response, is bounded away from zero. Such strict incentives
allow the principal to account for any costs that the agents may incur for their evaluation effort by
appropriately scaling the rewards in the mechanism.
Another important concern in these mechanisms is that the induced game may possess multiple
equilibria. In such cases, there needs to be an adequate rationale for the truthful equilibrium to be
selected. This issue has increasingly been brought into focus recently. It is known that mechanisms
for a single task with no extraneous reporting (which includes [MRZ05]) possess uninformative
equilibria that give a higher expected payoff to each agent than in the truthful equilibrium [JF05].
Bayesian Truth Serum demonstrated that this issue can be overcome by requiring extraneous reports
of beliefs; the truthful equilibrium under BTS gives the highest expected payoff to an agent across

4

all equilibria.
A few recent works have discovered that similarly strong truthfulness properties can be obtained
in the multi-task setting without requiring extraneous reports from the agents [DG13, SAFP16,
KS16]. [KS16] expounds a remarkably general information theoretic analysis of incentive mechanisms in this space, and has shown that most mechanisms achieve such properties by (implicitly or
explicitly) connecting the loss in the agents’ expected payoff relative to the truthful equilibrium, to
some form of mutual information loss or correlation loss in the population due to deviation from
truthfulness. Both, extraneous reports of beliefs about the play, or statistical estimates of the play
across multiple tasks, in some sense allow these mechanisms to obtain a handle on an appropriate
mutual information measure.
Addressing these concerns, we show that under the non-degeneracy assumptions that we mentioned earlier, truthful behavior is a strict Bayes-Nash equilibrium under our mechanism, i.e., our
mechanism is strictly proper. Also, at this equilibrium, the difference in the payoffs to an agent under
the truthful strategy and under any strategy in which an agent’s reported response is independent
of her true response, is bounded away from zero.
Moreover, we obtain a vanishing uniform upper bound (in the number of tasks) on the difference
between the expected payoff obtained by the truthful equilibrium and that obtained under any other
symmetric equilibrium (equilibrium in which all players choose the same strategy). Asymptotically,
the limiting expected payoff under a truthful strategy profile is higher than that under any other
symmetric strategy profile. Under a mild assumption on the strategy spaces, we also show that
any symmetric equilibrium that gives the highest reward to an agent across all symmetric equilibria
must be close to being fully informative (in a precise sense) when the number of tasks is large. A
fully informative strategy is simply a permutation map from the set of answers to itself; this includes
truthfulness. In line with the framework in [KS16], these results are obtained by showing that the
expected payoff of an agent under any symmetric strategy profile is connected to a novel notion of
an agreement measure between two independent responses that is monotonic in information loss.
Both the measure and this monotonicity property are of independent interest.
Our mechanism adds to a small but growing set of elicitation mechanisms that establish compelling guarantees on payoff-dominant equilibria in addition to truthfulness, without assuming the
knowledge of the generating model or requiring extraneous reporting of beliefs. It has certain key
operational differences from these mechanisms that could make it preferred in certain situations.
The mechanism in [DG13] restricts itself only to evaluations with binary responses, whereas we have
no such restrictions. The mechanisms proposed in both [SAFP16] and [KS16] require each agent
to perform a large number of tasks, whereas we only require a large number of evaluation tasks in
total– each agent can perform as few as a single task. Moreover, in settings where task allocations
are controlled by the principal, and each agent can perform a large number of tasks, we show that
we can utilize our agreement measure to design a different mechanism in the framework described
in [KS16]. In this mechanism, as the number of tasks performed by an agent goes to infinity, and
as long as agents choose the same reporting strategy for each task, the truthful strategy profile
gives the highest expected payoff in the limit as compared to any other strategy profile. It will be
beneficial to describe our mechanism and results before we make a detailed comparison, and hence
we defer this discussion to Section 4.
The remainder of the paper is organized as follows. Section 2 presents a formal description of
the model considered in the paper. Section 3 presents our mechanism and our main results. We
discuss some comparisons and relations with existing mechanisms in Section 4. We finally summarize
our contributions and conclude in Section 5. The proofs of all of our results can be found in the
5

Appendix.

2

Model

We consider a setting with N evaluation tasks denoted by the set N and labeled as i = 1, · · · , N . Let
M denote the population of agents, labeled as j = 1, . . . , M . Let Mi ⊆ M denote the subset of agents
that perform task i, and let Nj be the set of tasks that an agent j performs. We assume that the
sets Mi and Nj are exogenously specified. The set of answers in each evaluation task is assumed to
be finite and denoted as Y. The unknown distribution of answers in population Mi is parameterized
by a type Xi that takes values in the set X, also finite, for all populations. The distribution of
the answers in the population as a function of type x ∈ X is denoted as p(x) = (py (x); y ∈ Y).
The answer Yji of each agent j in Pi is independently drawn from p(Xi ). Further, the types of
different tasks are independently sampled from a common distribution PX . We further assume that
the different answers of any person j for all the evaluation tasks in Nj are mutually independent.4
The answers of different agents for a single task i need not be independent unless conditioned on
Xi .
The probability distribution over types, PX , and the function p together form a generating
model, denoted as the pair (PX , p). In particular, this pair fully specifies a joint distribution on
the underlying types of the different evaluation tasks and the answers of the different agents across
tasks.
Our goal is to design a payment mechanism that elicits true responses from the agents. We are
specifically interested in the case where N is large, although Nj is relatively small for each j. The
principal is not assumed to know PX or p. We do not make any additional assumptions on the
agents’ knowledge of (PX , p) other than the assumption that every agent knows the structure of
the underlying generating model, i.e., the existence of some PX and the function p that is common
across tasks. In particular, this means that all the agents know that all the tasks are statistically
similar and the population of agents performing each evaluation is homogeneous.
Example 2.1. Consider a situation where a labor platform wants to obtain feedback on punctuality
of handymen that operate on the platform. In this case, each handyman could be of 2 types X =
{Punctual, Not Punctual}. The question could be “Did the handyman show up on time for your
appointment?”. The two answers are Y = {Yes, No}. And the distributions of answers as a function
of type are p(Punctual) = (0.95, 0.05) and p(Not Punctual) = (0.5, 0.5).
Note that the above example is simply illustrative. For obtaining our results, it doesn’t matter
what the specifics of the generating model are, as long as every agent believes that there is a
generating model with this structure.
An agent j’s strategy is a set of mappings {qij : i ∈ Nj } where qij (y) = (qyij′ (y); y ′ ∈ Y) is the
probability distribution over answers for evaluation task i ∈ Nj conditional on the true response
being y. We do not consider reporting strategies in which the reported answer of an evaluation
depends not just on the true answer for that evaluation, but also on the true answers to all the
other evaluations that the agent performs. This restriction is simply for the ease of exposition. It
will become clear that all the incentive properties continue to hold for our proposed mechanism
4

This assumption precludes the possibility of dependence induced by lack of knowledge of some hidden information
about an agent, e.g., if an agent’s mood is bad on a particular day, there may be a bias in all her evaluations.

6

even if such strategies are allowed. For any j ∈ Mi , let rji denote agent j’s reported answer for task
i. We define a payment mechanism as follows.
Definition 2.1. a) A payment (or scoring) mechanism is a set of functions {τj : j ∈ M}, one for
each person in the population, that map the reports {rji : j ∈ M, i ∈ Nj } to a real valued payment
(or score).
We define the notion of a Bayes-Nash equilibrium in the game induced by a payment mechanism.
The definition assumes that the generating model is commonly known to the agents, but this
assumption will be appropriately relaxed later.
Definition 2.2. Given a generating model (PX , p) that is common knowledge amongst the agents,
we say that a strategy profile {qij : j ∈ M, i ∈ Nj } comprises a Bayes-Nash equilibrium in the game
induced by the payment mechanism if for each j ∈ M,






′
′
i
ij
i
ij ′
′
i
ij ′
E τj {q (Yj ′ ) : j ∈ M, i ∈ Nj ′ } ≥ E τj {q̄ (Yj ) : i ∈ Wj } ∪ {q (Yj ′ ) : j ∈ M, j 6= j, i ∈ Nj ′ } ,
(1)

for each {qij : i ∈ Nj } =
6 {q̄ij : i ∈ Nj }, where the expectation is with respect to the joint distribution
on the responses of the population specified by the generating model (PX , p). We say that the strategy
profile is a strict Bayes-Nash equilibrium if the above inequality is strict.
Next, we define Bayes-Nash incentive compatibility.
Definition 2.3. We say that a payment mechanism is Bayes-Nash incentive compatible with respect
to the generating model (PX , p) if the truthful reporting strategy profile, i.e., where qyij′ (y) = 1{y′ =y}
for all j ∈ M and i ∈ Nj , is a Bayes-Nash equilibrium. If this equilibrium is strict, we say that the
mechanism is strictly Bayes-Nash incentive compatible.

3

Main results

The simplest description of the core idea of our mechanism is obtained in the case of a single
evaluation task, in which the generating model (PX , p) is commonly known to the principal and
the agents (this is the setting in [MRZ05]). In this setting, consider the following output agreement
scheme. Each agent j is paired with another randomly chosen agent j ′ and their responses are
compared. If their responses don’t match, then j gets no reward. If their responses
qP match and this
p
2
common response is y ∈ Y, then j gets a reward K/ P (Yj = Yj ′ = y) = K/
x∈X PX (x)py (x),
where K is some positive constant. That is, she gets a reward that is inversely proportional to the
square root of the probability that both the agents form the same response y. Or to put it simply,
the reward for an agreement is inversely proportional to the square root of the probability of that
agreement. Thus an agreement that is more probable earns a lower reward than an agreement that
is relatively less probable.
Let us see why truthful behavior is a Bayes-Nash equilibrium in this mechanism. Consider an
agent j, and suppose that all other agents are truthful. Then if j’s true response is y, her expected
reward for a truthful report is,
p
P(Yj ′ = Yj = y)
P(Yj ′ = y | Yj = y)
=K
.
(2)
Kp
P(Yj = y)
P(Yj = Yj ′ = y)
7

Similarly, her reward for any other report y ′ is,
P(Yj ′ = y ′ | Yj = y)
P(Yj ′ = y ′ , Yj = y)
p
Kp
=K
.
P(Yj = Yj ′ = y ′ )
P(Yj = y) P(Yj = Yj ′ = y ′ )

(3)

Thus being truthful gives a higher reward if,
q
q
P(Yj ′ = Yj = y) P(Yj = Yj ′ = y ′ ) ≥ P(Yj ′ = y ′ , Yj = y),
i.e., if,

sX

PX (x)py

(x)2

x∈X

sX

x∈X

PX (x)py′ (x)2 ≥

X

PX (x)py (x)py′ (x).

(4)

x∈X

But this is precisely the Cauchy-Schwarz inequality.
Now there are three concerns. First, we need truthfulness to be a strict Bayes-Nash equilibrium.
This means that we need the above inequality to be strict. It turns out that this is true under
natural assumptions on the generating model. Second, in our original setting, the principal does
not know the generating model. This can be addressed by replacing the required agreement probabilities by consistent statistical estimates computed from reports obtained across multiple tasks.
As the number of tasks grows, the accuracy of these estimates improves and for a large enough N ,
truthfulness is recovered as a strict equilibrium. Finally, we need to tackle the issue of multiple
equilibria. We elaborate on all these aspects one by one.

3.1

Obtaining strictness

For truthfulness to be a strict equilibrium, we need the Cauchy-Schwarz inequality in (4) to be strict
for every pair y, y ′ ∈ Y. It will be useful to define the following “inequality gap”.
Definition 3.1. For a generating model (PX , p) defined on X and Y, define
s X
X
X
PX (x)py (x)2 )(
PX (x)py′ (x)2 ) −
δ(PX , p) = ′min ′ (
PX (x)py (x)py′ (x).
y, y ∈Y, y6=y

x∈X

x∈X

x∈X

By the Cauchy-Schwarz inequality, δ(PX , p) ≥ 0. If δ(PX , p) > 0 for some generating model
(PX , p), then truthfulness is a strict Nash equilibrium in the game induced by the mechanism we
described earlier for the case where the principal knows this generating model. To understand
whether this is a reasonable assumption, a little demystification of this condition is in order.
For any answer y ∈ Y, define the vector
p

PX (x)py (x); x ∈ X .
v(y) ,

(5)

Then the Cauchy-Schwarz inequality says that for any two answers y and y ′ , the magnitude (in the
Euclidean norm) of the projection of the vector v(y) on the unit vector in the direction v(y ′ ) is less
than the magnitude of the vector v(y) itself (one can reverse the roles of y and y ′ ), i.e.,

or

|v(y).v(y ′ )|
≤ kv(y ′ )k,
kv(y)k
|v(y).v(y ′ )| ≤ kv(y)kkv(y ′ )k.
8

(6)

Let θ(u, v) denote the angle in radians between two non-zero vectors u and v, defined as
θ(u, v) , arccos

u.v
.
kukkvk

(7)

Then it is clear that the inequality in (6) is strict if and only if the angle between the vectors v(y)
and v(y ′ ) is positive and their magnitude is non-zero. In fact, under the condition that kv(y)k ≤ 1
for all y ∈ Y, which holds in our case, we can show that the gap in (6) is bounded away from 0
if and only if the angle between the vectors v(y) and v(y ′ ), and their magnitudes are all bounded
away from 0. The following proposition gives a precise statement.
Proposition 1. For a generating model (PX , p) defined on X and Y, the following two conditions
are equivalent.
1. There is some α > 0 such that δ(PX , p) > α.
2. There is some τ > 0 such that
P
(a)
x∈X PX (x)py (x) > τ for each y ∈ Y, and,

(b) θ(v(y), v(y ′ )) > τ for all y, y ′ ∈ Y such that y 6= y ′ .

Condition 2(a) says that the probability of an agent forming any response y ∈ Y is bounded away
from zero. This condition is naturally satisfied in practice. If this doesn’t hold for some answer,
then one can simply eliminate that answer from the admissible set.
Condition 2(b) says that the the angle between v(y) and v(y ′ ) is bounded away from zero for
any y 6= y ′ . If this is not true for some y and y ′ then there is a C ∈ R such that py (x) = Cpy′ (x) for
each x ∈ X such that PX (x) > 0. But in this case, the responses y and y ′ need not be distinguished
at all, since they contain the same information about X, and hence about the rest of the random
quantities. In particular, P (Xi = x|Yji = y) = P (Xi = x|Yji = y ′ ) for each x ∈ X. Hence, the
principal can simply ask the agents to map both these responses to a single response.
In the context of our model, the condition θ(v(y), v(y ′ )) > 0 for any y 6= y ′ is weaker than the
stochastic relevance condition that is imposed to obtain strictness in several works in this domain,
starting from [MRZ05]. An agent’s answer to a question is a stochastically relevant random variable
if no two answers induce the same conditional distribution on the answers of some other agent who
has answered the same question. Clearly, if θ(v(y), v(y ′ )) = 0, then stochastic relevance is violated,
and thus stochastic relevance implies that θ(v(y), v(y ′ )) > 0.

3.2

Relaxing the knowledge assumption: the large N regime

Next, we tackle the problem of the principal not knowing the generating model. In this case, the
principal can simply replace the parameters of the mechanism by consistent statistical estimates
obtained from the reports across multiple tasks, assuming these reports are truthful. We thus
present our main mechanism.
Definition 3.2 (Main mechanism. Assumes Mi ≥ 2 for all j ∈ M). The responses of agents
for the different evaluation tasks are solicited. Let these be denoted by {rji : j ∈ M, i ∈ Nj }. An
agent j’s payment is computed as follows:

9

• For each population Mi such that i ∈
/ Nj , choose any two agents j1 (i), j2 (i) ∈ Mi , and for
each possible evaluation y ∈ Y, compute the quantity
f¯j (y) =

X
1
1{ri =y} 1{ri =y} .
j1 (i)
j2 (i)
N − |Nj |
i∈N\Nj

• For each answer y, fix a payment ej (y) defined as
ej (y) =

(

√K

f¯j (y)

if f¯j (y) 6= 0,
if f¯j (y) = 0,

0
q
where K > 0 is any positive constant. f¯j (y) is the popularity index of answer y.

• For computing agent j’s payment for evaluation task i ∈ Wj , choose another agent j ′ ∈ Mi ,
who will be called j’s peer for task i. If their responses match, i.e., if rji = rji ′ = y, then j gets
a reward of ej (y). If the responses do not match, then j gets 0 payment for that task.
Observe that if everyone except agent j is truthful, then E[f¯j (y)] = P[Yji1 (i) = Yji2 (i) = y], i.e.,
f¯j (y) is a consistent estimate of P[Yji1 (i) = Yji2 (i) = y]. In fact, as N grows large, assuming |Nj |
remains bounded, f¯j (y) almost surely converges to P[Yji1 (i) = Yji2 (i) = y] by the strong law of large
numbers. For an N large enough, we can show that the quality of the estimate is sufficiently high
to ensure that truthfulness is sustained as a strict equilibrium under appropriate conditions on the
generating model. Following is our main result.
Theorem 2. Consider a generating model (PX , p) such that δ(PX , p) > α for some α > 0. Further,
suppose that Nj ≤ n for all j ∈ M. Then for any ω ∈ (0, αK(|Y| − 1)), there exists a positive integer
N0 that depends only on ω, α, |Y|, n, and K such that if the number of evaluation tasks N > N0 ,
then
• Our mechanism is strictly Bayes-Nash incentive compatible with respect to (PX , p), and,
• At the truthful Bayes-Nash equilibrium, the expected payoff to an agent under the truthful
strategy is at least ω higher than the expected payoff under any reporting strategy where the
agent’s reported response is independent of her true response.
This result implies that if it is common knowledge amongst agents that the generating model
(PX , p) is such that δ(PX , p) > α for some α > 0, then irrespective of their beliefs about the specifics
of the generating model, truthful reporting is a strict Bayes-Nash equilibrium in the game induced
by the mechanism for a large enough N . Moreover, the truthful equilibrium can be sustained even
when the agents incur a bounded cost for their evaluation effort by scaling the rewards appropriately.

3.3

Equilibrium selection

Next, we address the issue of multiplicity of equilibria. First, observe that if truthful behavior is
an equilibrium, then so is any symmetric fully informative strategy profile where all agents apply
a common permutation map to the responses they receive. And all such equilibria are payoffequivalent. But the significantly higher degree of coordination needed for the agents to play a fully
informative equilibrium other than truthful behavior, coupled with the fact that there is no real
10

benefit in doing so, makes it unlikely that such equilibria will emerge in practice. But even if they
do arise, it should be simple to infer the permutation map by obtaining a few evaluations from
trusted agents and comparing these to the reported evaluations. The important point is that there
is no loss in information transferred from the agents to the principal. Thus full informativeness
shall be our benchmark as we focus on other equilibria that may emerge.
The equilibria that give high expected payoffs are arguably the most attractive for the agents
and thus can be assumed to have an increased likelihood of being chosen. In what follows, we show
that for a large N , the truthful equilibrium is approximately payoff-optimal across all symmetric
equilibria, with an approximation error that vanishes in N . In the limit, any symmetric fully
informative strategy profile gives a strictly higher expected payoff to any agent than any other
symmetric strategy profile. We also show that under certain assumption on the strategy spaces, any
symmetric equilibrium that results in the highest expected payoff to an agent across all symmetric
equilibria cannot be too “uninformative” when N is large, where uninformativeness is a precise
notion that we will define in due course.
3.3.1

Truthfulness vs. symmetric equilibria in the large N regime

Before we discuss the result for a large but finite N , let us first discuss the result in the limiting
case as N → ∞, which is easier to obtain, and sheds light on the core idea. Consider a symmetric
strategy profile in which every agent adopts a reporting strategy q, where q(y) = (qy′ (y); y ′ ∈ Y)
is the distribution over the reported response conditional on the true response. Let us denote the
reported responses under this strategy by the random variables {Zji ; i = 1, · · · , N, j ∈ Mi }. Under
the truthful strategy profile (or equivalently, any symmetric fully informative strategy profile), in the
limit as N → ∞, the expected reward of each agent performing task i converges to (see Equation 2),
q
P(Yji′ = Yji = y)
Xq
X sX
X
i = Y i = y) = K
P(Y
=
K
PX (x)py (x)2 . (8)
P(Yji = y)K
j
j′
P(Yji = y)
y∈Y

y∈Y

y∈Y

x∈X

Whereas, under any other symmetric strategy profile, the expected reward of each agent converges
to,
X sX
X
Xq
P(Zji′ = Zji = y) = K
PX (x)(
(9)
py′ (x)qy (y ′ ))2 .
K
y∈Y

y∈Y

x∈X

y ′ ∈Y

It turns out that the quantity in (9) is in general lower than the quantity in (8). How much lower
depends on the ‘uninformativeness’ of the strategy q: more uninformative the strategy q, the higher
is the difference. Speaking informally, a reporting strategy is more uninformative if it frequently
maps multiple true responses to a single reported response, the extreme case being when a report
is chosen independently of the true response. The following definition formalizes this notion.
Definition 3.3 (An uninformativeness measure). The uninformativeness of a reporting strategy
q is defined as
q
X
X
1
qy (y ′ )qy (y ′′ ).
(10)
Ω(q) =
|Y|(|Y| − 1)
′
′′
′
′′
y∈Y y ∈Y, y ∈Y; y 6=y

We say that a strategy q is ω−uninformative if Ω(q) ≥ ω.
Clearly, Ω(q) = 0 if and only if (q(y); y ∈ Y) have disjoint supports across all y ∈ Y, i.e., if and
only if q is fully informative. On the other hand Ω(q) attains its highest value of 1, if and only if
11

q(y) = q(y ′ ) for any y 6= y ′ , i.e., if the report is chosen independent of the true answer. To see this,
observe that,
X X q
1
qy (y ′ )qy (y ′′ )1y′ 6=y′′
|Y|(|Y| − 1)
y∈Y y ′ ∈Y,y ′′ ∈Y
v
 X

X
Xu
(a)
u
1
t
≤
qy (y ′ )1y′ 6=y′′
qy (y ′′ )1y′ 6=y′′
|Y|(|Y| − 1)
′
′′
′
′′
y ∈Y,y ∈Y
y∈Y
y ∈Y,y ∈Y
v
X
2
Xu
u
1
2
′
t
(|Y| − 1)
=
qy (y )
|Y|(|Y| − 1)
′
y∈Y

1 XX
qy (y ′ )
=
|Y|
′

y ∈Y

y∈Y y ∈Y

= 1.

Here, (a) follows from the Cauchy-Schwarz inequality. We will see that higher the uninformativeness
of a strategy, the higher is the gap between the payoffs in equations (8) and (9). It is useful to
describe this phenomenon more generally, since it could be of independent interest beyond this
work. We define the following notion of an agreement measure.
Definition 3.4 (An agreement measure). Consider a generating model (PX , p) defined over X
and Y, and consider two random responses Y1 and Y2 drawn from this model. Then the agreement
measure between Y1 and Y2 is defined as
X sX
Xp
P (Y1 = Y2 = y) =
Γ(Y1 , Y2 ) =
PX (x)py (x)2
y∈Y

y∈Y

x∈X

Under a symmetric strategy profile in which every agent adopts a reporting strategy q, the
expected payoff to each agent in the limit as N → ∞ is K times the agreement measure between
the reported responses (see Equation 9). The agreement measure has the following properties:
1. Γ(Y1 , Y2 ) ≥ 1. To see this, note that Jensen’s inequality implies that
X sX
XX
PX (x)py (x)2 ≥
PX (x)py (x) = 1.
y∈Y

x∈X

y∈Y x∈X

In fact Γ(Y1 , Y2 ) = 1 only when Y1 and Y2 are independent.
p
2. Γ(Y1 , Y2 ) ≤ |Y|. To see this, note that Jensen’s inequality implies that
s
X sX
1 XX
2
PX (x)py (x) ≤ |Y|
PX (x)py (x)2
|Y|
y∈Y
x∈X
y∈Y x∈X
s
p
1 XX
PX (x)py (x) = |Y|.
≤ |Y|
|Y|
y∈Y x∈X

p

In fact Γ(Y1 , Y2 ) = |Y| only when Y1 and Y2 are identical and they are distributed uniformly,
i.e., Y1 = Y2 and P (Y1 = y) = 1/|Y| for all y ∈ Y.
12

The following information monotonicity property is key to our results.
Proposition 3 (A monotonicity property). Consider a generating model (PX , p) defined over
X and Y, and consider two random responses Y1 and Y2 drawn from this model. Also, consider two
random responses Z1 and Z2 obtained by applying a reporting strategy q independently to Y1 and Y2
respectively. Then,
δ(PX , p)Ω(q)2 (|Y| − 1)
p
.
(11)
Γ(Z1 , Z2 ) ≤ Γ(Y1 , Y2 ) −
2 |Y|
Clearly, Γ(Y1 , Y2 ) = Γ(Z1 , Z2 ) if q is a permutation map., i.e., it is fully informative. The
proposition implies that if δ(PX , p) > 0, then Γ(Y1 , Y2 ) = Γ(Z1 , Z2 ) only if Ω(q) = 0, i.e., only
if q is fully informative. Thus we immediately conclude that if δ(PX , p) > 0, then in the limit
as N → ∞, any fully informative strategy profile gives a strictly higher payoff than any other
symmetric strategy profile that is not fully informative.

Now we turn to the finite N setting. In this case, the expected payoffs under the fully informative
strategy and under any other symmetric strategy will not have converged to Γ(Y1 , Y2 ) and Γ(Z1 , Z2 )
respectively. But for any fixed N , one can obtain concentration bounds on how far the expected
payoffs will be from these target values. This, in turn, gives us vanishing bounds on how much lower
the payoff under the truthful equilibrium could be as compared to any other symmetric equilibrium.
Theorem 4. Consider a generating model (PX , p) such that δ(PX , p) > 0. Suppose that this
generating model is common knowledge amongst agents. Further, suppose that Nj ≤ n for all
j ∈ M. Then for any ω > 0, there is a positive integer N0 that depends on δ(PX , p), ω, n, K, and
|Y|, such that for any N > N0 ,
1. Any symmetric fully informative strategy profile is a strict Bayes-Nash equilibrium, and,
2. It gives an expected payoff that is at most ω less than any other symmetric Bayes-Nash equilibrium strategy profile.
Note that the N0 in the statement above suffices to ensure that the truthful equilibrium gives a
payoff no less that ω compared to any symmetric equilibrium strategy profile. This is significant,
since for a large but fixed N , it is not possible to obtain uniformly vanishing concentration bounds
on E(ej (y)) (which involves an inverse) across all symmetric reporting strategies. This is because
there could be a symmetric strategy profile for which the probability of agreement for an answer
y ∈ Y gets arbitrarily close to 0. To overcome this issue, we utilize the fact that under a mixed
equilibrium, since the problem of computing the best response is a linear optimization problem,
a fixed agent is indifferent between multiple deterministic reporting strategies. This allows us to
choose a best-response strategy for a single agent in a way that ensures that the probability of
agreement on any answer y is bounded away from zero, while ensuring that the expected payoff is
same as that under the given symmetric equilibrium. Note that the case where the probability of
agreement on any answer y is 0 is not problematic since in this case ej (y) is defined to be 0.
Can we say anything about the informativeness of the symmetric equilibrium profile that gives
the highest expected payoff across all symmetric equilibria? Intuitively, bounds on E(ej (y)) for a
large N , coupled with the “inequality gap” characterized in Proposition 3 should result in an upper
bound on the uninformativeness of any symmetric reporting strategy that gives a higher expected
payoff than a fully informative strategy. It turns out that in doing so, the same difficulty that
we described earlier arises in obtaining the requisite concentration bounds when the symmetric
13

strategies could lead to probabilities of agreement arbitrarily close to 0. In this case, we cannot use
the trick we used earlier and instead, we show the following result.
Theorem 5. Consider a generating model (PX , p) such that δ(PX , p) > 0. Suppose that this
generating model is common knowledge amongst agents. Further, suppose that Nj ≤ n for all
j ∈ M. Also, suppose that for each evaluation task, each agent restricts herself to using a reporting
strategy in which the probability of reporting any answer y ∈ Y is either 0 or at least η for some
η ∈ (0, δ(PX , p)2 ]. Then for any ω > 0, there is a positive integer N0 that depends on ω, δ(PX , p),
η, n, K, and |Y|, such that for any N > N0 , any symmetric strategy profile that gives a higher
expected payoff to an agent than the truthful strategy profile is at most ω−uninformative.
This restriction on the reporting strategies is not implausible since agents are expected to use
simple strategies in practice. The lower bound η, for instance, could arise from the desire to produce
a marginal distribution of answers consistent with the prior; recall that the prior probability of any
answer is bounded away from 0 as long as δ(PX , p) > 0. The condition η ≤ δ(PX , p)2 ensures that
the fully informative reporting strategy is contained in the restricted strategy space.
These two results comprise the best we can say about equilibrium selection in the setting where
tasks are exogenously defined. This is typically the case for reviews and ratings, where the choices
are made by the agents themselves and are driven by considerations like geographical proximity etc.
In such cases, there could be other (non-symmetric) equilibria where some agents may get a higher
payoff than the truthful or a symmetric fully informative equilibrium. For instance, suppose y ∗ is
the answer with the lowest probability of agreement, i.e., y ∗ = arg miny∈Y P (Y1 = Y2 = y). Then
a strategy profile where all agents report y ∗ for some task i, and are truthful for all other tasks is
an equilibrium for a large enough N . This equilibrium gives a higher reward to the agents that
evaluate task i than the fully truthful equilibrium.
In situations where the task allocations are controlled by the principal, and where each agent
is expected to perform a large number of tasks, we can utilize our agreement measure to design a
different mechanism along the lines of the framework in [KS16] in which, asymptotically, truthfulness
gives the highest payoff to each agent across all strategy profiles, not just symmetric. We discuss
this in the next section.
We finally mention that an important practical concern is a presence of extraneous features in
the evaluation tasks, which can introduce correlated equilibria of the form “If the background color
of image is green, then report ‘cat’, otherwise report truthfully”. These type of equilibria trouble
most payment mechanisms in this domain, it has been shown that it is impossible to elicit every
feature under a payoff-dominant truthful equilibrium [GWLB16].

4

Comparisons with other mechanisms

In this section, we compare our mechanism to other mechanisms in the multi-task setting that do not
assume knowledge of the generating model and at the same time prove strong incentive properties
for the truthful equilibrium. We focus our attention to three major works in this category: [DG13],
[SAFP16], and [KS16]. Finally, we also comment on the shortcomings of mechanisms obtained by
relaxing the knowledge assumptions in the Peer Prediction method using an estimation approach
similar to ours.

14

4.1

Comparison with existing mechanisms in the multi-question setting

Dasgupta and Ghosh [DG13] designed a truthful minimal mechanism for the case of binary evaluations for a specific heterogeneous generating model: each evaluation has a true answer, and each
agent has a single parameter, which is her the probability of correctly guessing the answer (this
probability is assumed to be greater than 0.5). Moreover, [DG13] showed that the truthful equilibrium in this mechanism gives the highest expected payoff to each agent across all equilibria. This
property has been referred to as ‘strong truthfulness’ in subsequent literature. The main drawback
of this mechanism is the restriction to tasks with binary responses.
The ‘Correlated Agreement’ mechanism of Shnayder et al. [SAFP16] extends the Dasgupta and
Ghosh mechanism to handle more than two possible responses. The mechanism operates on every
pair of agents and requires an estimate of certain correlation information about the joint distribution
of their evaluations. Obtaining an accurate estimate requires these agents to perform a large number
of evaluations. They show that truthfulness is an equilibrium and moreover, it gives a strictly higher
expected payoff to each agent than any equilibrium where agent responses are independent of their
true valuations (this property is referred to as ‘informed truthfulness’). In another development,
Kong and Schoenebeck [KS16] propose a general information-theoretic design framework that also
extends the Dasgupta and Ghosh mechanism to handle more than two evaluations. Similar to
Shnayder et al.’s mechanism, this design also operates on every pair of agents and requires an
estimate of certain functionals of the joint distributions of their evaluations, which in turn requires
these agents to perform a large number of tasks. The main property of their framework is that strong
truthfulness is obtained (in the limit as the number of tasks performed by each agent increases) as
a consequence of inequalities resulting from some notion of mutual information loss. In principle,
both these mechanisms can handle heterogeneous populations, assuming that accurate estimates
of the required quantities can be obtained for each pair of agents. [AMPS17] combines correlated
agreement with agent clustering to reduce the sample complexity of obtaining these estimates in a
heterogeneous population setting.
In contrast to these mechanisms, the incentive properties of our mechanism only hold in the
homogeneous population setting. But unlike these mechanisms, our mechanism does not require
the agents to perform a large number of evaluations. It requires only a large number of evaluation
in total. Moreover, in settings where agents are naturally expected to perform a large number of
evaluations, we can utilize our agreement measure to design a (asymptotically) strongly truthful
mechanism under the [KS16] framework. This is facilitated by the following inequality satisfied by
the agreement measure, which generalizes Proposition 3 without the characterizing the inequality
gap.
Proposition 6 (A general monotonicity property). Consider a generating model (PX , p) defined over X and Y, and consider two random responses Y1 and Y2 drawn from this model. Also,
consider two random responses Z1 and Z2 obtained by applying a reporting strategies q and q′
independently to Y1 and Y2 respectively. Then,
Xp
P (Z1 = Z2 = y) ≤ Γ(Y1 , Y2 ).
(12)
y∈Y

In the task allocation scheme, agents are paired together, and each pair performs the same set
of tasks. The payment mechanism is defined for each pair of agents as follows.
Definition 4.1 (An alternative mechanism). Let the agents be denoted as 1 and 2, and let N
be the set of tasks that they perform, labeled as i = 1, · · · , N . The responses of the agents for the
15

different evaluation tasks are solicited. Let these be denoted by {r1i : i ∈ N} and {r2i : i ∈ N}. Then
agents’ payment is computed as follows:
• For each task i and for each possible evaluation y ∈ Y, compute the quantity
X
1
1{ri′ =y} 1{ri′ =y} .
f¯i (y) =
1
2
N −1 ′
i ∈N\i

• For each answer y, fix a payment ei (y) defined as
i

e (y) =

(

√K

f¯i (y)

0

if f¯i (y) 6= 0,
if f¯i (y) = 0,

where K > 0 is any positive constant.
• For computing the agents’ payments for task i: if their responses match, i.e., if r1i = r2i = y,
then both gets a reward of ei (y). If the responses do not match, then they get 0 payment for
that task.
We will assume that each agent restricts herself to choosing a single common reporting strategy
across all evaluation tasks. This assumption is common in literature in this setting, informally
stated as “workers treat the tasks equally” [DG13]. For a fixed number of evaluation tasks N , let
GN (q, q′ ) denote the expected payoff to either of the agents for evaluating any single task (the
expected payoff will be the same to both agents) when one agent plays strategy q and other plays
q′ . Also, suppose that t is the truthful reporting strategy. Then
lim GN (q, q′ ) =

N →∞

But then limN →∞ E(ei (y)) =

X
y∈Y

qP

X

PX (x)py1 (x)py2 (x)qy (y1 )qy′ (y2 ).

X sX
y∈Y

(13)

x∈X

′
x∈X PX (x)py1 (x)py2 (x)qy (y1 )qy (y2 ),

lim GN (q, q′ ) =

N →∞

E(ei (y))

and thus

PX (x)py1 (x)py2 (x)qy (y1 )qy′ (y2 ).

(14)

x∈X

Thus, we can use Proposition 6 to conclude that,
lim GN (q, q′ ) ≤ lim GN (t, t).

N →∞

N →∞

(15)

for any q and q′ . Taking q (or q′ ) to be equal to t, this shows that the proposed mechanism is
Bayes-Nash incentive compatible “in the limit”. Further, it is also strongly truthful “in the limit”,
i.e., in the limit, the payoff under the truthful strategy is no less than the payoff under any other
strategy profile. Obtaining finite N results is trickier in this case and beyond the scope of our work.

4.2

Peer Prediction Method with estimation

The original Peer Prediction method of [MRZ05] is defined for the homogeneous population setting,
but it requires the principal to know the joint distribution of answers of any two agents for implementation. Using an approach similar to ours, it is possible to relax this knowledge assumption
16

when there are a large number of evaluation tasks, by obtaining the required estimates from the
reports for a large number of tasks. While truthfulness and strict properness (assuming stochastic
relevance) could be achieved asymptotically in such a mechanism, in general, it is not true that
truthful behavior gives a higher reward than any other symmetric strategy profile. We demonstrate
this for the spherical scoring rule [GR07]. Suppose that the conditional distribution of the answers
of a peer if the answer of an agent is y is denoted as m(y) = (my′ (y); y ′ ∈ Y). Under the Peer
Prediction method utilizing the spherical scoring rule, if the agent reports y and the peer reports
y ′ , then the reward of the agent is:
R(y, y ′ ) = qP

my′ (y)
2
y ′′ ∈Y my ′′ (y)

.

(16)

Let Y1 and Y2 be the reports of j and j ′ under the truthful strategy, and let Z1 and Z2 be the reports
under some other symmetric strategy profile q. Then from (16), assuming that the principal has
obtained accurate estimates of the required distributions, it is easy to see that the expected reward
under the truthful strategy is,
sX
X
P (Y1 = y)
P (Y2 = y ′ | Y1 = y)2 ,
(17)
y∈Y

y ′ ∈Y

and that under the other symmetric strategy profile is,
sX
X
P (Z1 = y)
P (Z2 = y ′ | Z1 = y)2 .
y∈Y

(18)

y ′ ∈Y

Now, it is not true in general that (18) is strictly smaller than (17). For instance, suppose that Y1
and Y2 are i.i.d. with a uniform distribution
over Y (i.e., X is a singleton). Then the reward under
p
the truthful strategy profile is 1/ |Y|. But the non-truthful strategy of always reporting a fixed
answer gives an expected reward of 1, which is larger. Under our framework, both these strategies
give an agreement measure of 1.

5

Conclusion

We presented a new payment mechanism with strong incentive properties for obtaining truthful
reports from agents in settings where a large number of evaluations are to be made and each agent
performs a subset of these evaluations. Our main assumption is the statistical homogeneity of the
population performing a single task. The mechanism has the simple structure of output agreement
mechanisms, which are often adopted in crowdsourcing applications. Although the naive output
agreement scheme does not necessarily incentivize truthfulness, the basic insight from our work is
that inversely scaling the agreement rewards by the probabilities of agreement appropriately aligns
incentives. In the process, we made new contributions to the calculus of peer-prediction through
the information-theoretic notion of the agreement measure and the notion of uninformativeness of
reporting strategies.
Effective feedback and reputation systems are fundamental to the efficient functioning of online
platforms. These systems improve the overall quality of transactions, increase trust, and thus play
a major role in determining the success of these platforms in the long run. The impact of user
feedback and peer-reviews on customer decisions is evident in the success of independent reputation
17

systems like Yelp and TripAdvisor, which are used by millions of people across the world. But
as has been recently shown, these systems are currently fraught with several operational as well as
behavioral and strategic concerns [HG15, NT15]. We believe that appropriate incentive mechanisms
that are simple and intuitive can go a long way in addressing some of these concerns, and hence we
think that our mechanism has strong practical significance. We emphasize here that rather than
thinking of our mechanism as a fully specified solution in any setting, it is more useful to think of it
as a framework that provides conceptual guidelines for platform designers as they undertake their
design decisions.
As we argued in the introduction, population homogeneity is a reasonable assumption for objective queries about personal experiences (e.g., Questions (1) to (3)). Considering that subjective
reviews and ratings are fraught with biases, we believe that transitioning to such objective questions,
or at least complementing subjective reviews with such questions may be a sound design decision.
Moreover, from the perspective of the platform interested in curating the composition of the pool
of agents that transact on the platform, answers to such questions are no less important than obtaining subjective ratings. For instance, it is important for a labor platform to know if a particular
handyman is habitually late for appointments, or a cleaner does not stick to established standards.
As [NT15] has elegantly argued, there are reputational externalities caused by such experiences – a
bad encounter can cause a customer to attribute that experience to the platform rather than a single
bad agent and thus may leave the platform entirely. Many platforms have already started eliciting
fine-grained feedback along multiple dimensions, thereby reducing its subjectivity. For instance, the
short term lodging and apartment rental marketplace, Airbnb, elicits renter feedback on objective
dimensions like accuracy of description, cleanliness, ease of check-in, etc.
Our work presents many avenues for future exploration. For instance, in our model, we assume
that the task allocations are exogenously specified. But for a platform that is interested in learning
the underlying distributions of responses for each task, some of these distributions may be more
difficult to learn than others, and thus may need more evaluations. Moreover, the agents may be
willing to strategically respond to differences in potential rewards across tasks by choosing which
tasks to evaluate. In such situations, it is important to understand the fundamental tradeoffs faced
by dynamic mechanisms that balance incentives with different statistical accuracy objectives. We
are optimistic that our framework and insights from this paper can be used as building blocks in
this pursuit.

References
[AMPS17] Arpit Agarwal, Debmalya Mandal, David C. Parkes, and Nisarg Shah. Peer prediction
with heterogeneous users. In Proceedings of the 2017 ACM Conference on Economics
and Computation, EC ’17, pages 81–98, New York, NY, USA, 2017. ACM.
[Bri50]

Glenn W Brier. Verification of forecasts expressed in terms of probability. Monthly
weather review, 78(1):1–3, 1950.

[DG13]

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. International World Wide Web Conferences Steering Committee,
2013.

18

[GR07]

Tilmann Gneiting and Adrian E Raftery. Strictly proper scoring rules, prediction, and
estimation. Journal of the American Statistical Association, 102(477):359–378, 2007.

[GWLB16] Alice Gao, James R Wright, and Kevin Leyton-Brown. Incentivizing evaluation via
limited access to ground truth: Peer-prediction makes things worse. arXiv preprint
arXiv:1606.07042, 2016.
[HG15]

John Horton and Joseph Golden. Reputation inflation: Evidence from an online labor
market. 2015.

[JF05]

Radu Jurca and Boi Faltings. Enforcing truthful strategies in incentive compatible
reputation mechanisms. In WINE, volume 3828, pages 268–277. Springer, 2005.

[JF11]

Radu Jurca and Boi Faltings. Incentives for answering hypothetical questions. In
Workshop on Social Computing and User Generated Content, EC-11, number EPFLCONF-197783, 2011.

[KS16]

Yuqing Kong and Grant Schoenebeck. A framework for designing information elicitation
mechanisms that reward truth-telling. arXiv preprint arXiv:1605.01021, 2016.

[LC17]

Yang Liu and Yiling Chen. Machine-learning aided peer prediction. In Proceedings of
the 2017 ACM Conference on Economics and Computation, pages 63–80. ACM, 2017.

[LS09]

Nicolas Lambert and Yoav Shoham. Eliciting truthful answers to multiple-choice questions. In ACM conference on Electronic commerce, pages 109–118, 2009.

[Luc17]

Michael Luca. Designing online marketplaces: Trust and reputation mechanisms. Innovation Policy and the Economy, 17(1):77–93, 2017.

[MRZ05]

Nolan Miller, Paul Resnick, and Richard Zeckhauser. Eliciting informative feedback:
The peer-prediction method. Management Science, 51(9):1359–1373, 2005.

[NT15]

Chris Nosko and Steven Tadelis. The limits of reputation in platform markets: An
empirical analysis and field experiment. Technical report, National Bureau of Economic
Research, 2015.

[PHC+ 13] Chris Piech, Jonathan Huang, Zhenghao Chen, Chuong Do, Andrew Ng, and Daphne
Koller. Tuned models of peer assessment in MOOCs. arXiv preprint arXiv:1307.2579,
2013.
[Pre04]

Dražen Prelec. A Bayesian truth serum for subjective data. Science, 306(5695):462–466,
2004.

[RF13]

Goran Radanovic and Boi Faltings. A robust bayesian truth serum for non-binary
signals. In Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI
2013, number EPFL-CONF-197486, pages 833–839, 2013.

[RF15]

Goran Radanovic and Boi Faltings. Incentives for subjective evaluations with private beliefs. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI’15),
2015.

[RFJ16]

Goran Radanovic, Boi Faltings, and Radu Jurca. Incentives for effort in crowdsourcing
using the peer truth serum. ACM Transactions on Intelligent Systems and Technology
(TIST), 7(4):48, 2016.
19

[RYZ+ 10] Vikas C Raykar, Shipeng Yu, Linda H Zhao, Gerardo Hermosillo Valadez, Charles
Florin, Luca Bogoni, and Linda Moy. Learning from crowds. The Journal of Machine
Learning Research, 11:1297–1322, 2010.
[SAFP16]

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, pages 179–196. ACM, 2016.

[Sav71]

Leonard J Savage. Elicitation of personal probabilities and expectations. Journal of the
American Statistical Association, 66(336):783–801, 1971.

[VAD04]

Luis Von Ahn and Laura Dabbish. Labeling images with a computer game. In Proceedings of the SIGCHI conference on Human factors in computing systems, pages 319–326.
ACM, 2004.

[VAD08]

Luis Von Ahn and Laura Dabbish. Designing games with a purpose. Communications
of the ACM, 51(8):58–67, 2008.

[WP12a]

Jens Witkowski and David C Parkes. Peer prediction without a common prior. In
Proceedings of the 13th ACM Conference on Electronic Commerce, pages 964–981. ACM,
2012.

[WP12b]

Jens Witkowski and David C Parkes. A robust Bayesian truth serum for small populations. In AAAI, 2012.

[WP13]

Jens Witkowski and David C Parkes. Learning the prior in minimal peer prediction. In
3rd Workshop on Social Computing and User Generated Content at the ACM Conference
on Electronic Commerce, 2013.

A

Proofs

Proof of Proposition 1. To see that 2 implies 1, note that θ(v(y), v(y ′ )) ≥ τ implies that:
v(y).v(y ′ )
≤ cos τ,
kv(y)kkv(y ′ )k
Multiplying throughout by kv(y)kkv(y ′ )k, we have:
kv(y)kkv(y ′ )k − v(y).v(y ′ ) ≥ (1 − cos τ )kv(y)kkv(y ′ )k ≥ (1 − cos τ )τ 2 > 0.
Here in the last inequality, we use that fact that
sX
X
kv(s)k =
PX (h)p(s|h)2 ≥
PX (h)p(s|h) > τ,
h∈H

h∈H

which follows from the Jensen’s inequality. To show that 1 implies 2 is less straightforward and this
is where we need to use the fact that kv(y)k ≤ 1 for all y ∈ Y. First of all
|v(y).v(y ′ )| ≤ kv(y)kkv(y ′ )k − α,

20

implies that either kv(y)k or kv(y ′ )k is non-zero. Say kv(y ′ )k > 0. Then dividing on both sides, we
get:
α
|v(y).v(y ′ )|
≤ kv(y)k −
kv(y ′ )k
kv(y ′ )k
≤ kv(y)k − α
where the last inequality holds since kv(y)k ≤ 1. In other words:
kv(y)k cos θ(v(y), v(y ′ )) ≤ kv(y)k − α,
or
kv(y)k(1 − cos θ(v(y), v(y ′ ))) ≥ α.

Since kv(y)k ≤ 1 and (1 − cos θ(v(y), v(y ′ ))) ∈ [0, 1], this implies both kv(y)k
P ≥ α and (1 −
cos θ(v(y), v(y ′ ))) ≥ α, i.e., θ(v(y), v(y ′ ))) ≥ arccos(1 − α). Finally we have x∈X PX (x)py (x) ≥
kv(y)k2 ≥ α2 . Note that α ≤ 1 so that arccos(1 − α) ≤ π/2..
Proof of Theorem 2. First, note that the payments ej (y) for the different y ∈ Y are independent of
the reports of agent j for any reporting strategy. This is because {ej (y) : y ∈ Y} are computed
only based on evaluation tasks that j does notp
perform. Next, suppose
that everyone but agent j

PX (x)py (x); x ∈ X , we have,
is truthful. Recalling the definition of v(y) ,
 X

X
1
¯
1{ri ′ =y} 1{ri ′ =y} =
PX (x)py (x)2 = kv(y)k2 , g(y).
E(fj (y)) = E
j1 (i )
j2 (i )
N − |Nj |
x∈X

i∈N\Nj

In the proof of Proposition 1, we have seen that δ(PX , p) > α implies that kv(y)k > α, and thus
we have g(y) > α2 > 0 for all y ∈ Y. Next, recall that
ej (y) = 1{f¯j (y)6=0} q

K
f¯j (y)

.

Let N ′ = N − |Nj |. Then we have for any ǫ ∈ (0, 1):

E(ej (y)) ≥ P (f¯j (y) ∈ [g(y)(1 − ǫ), g(y)(1 + ǫ)]) p
(a)

≥ (1 − 2 exp(−ǫ2 g(y)2 N ′ )) p

K
g(y)(1 + ǫ)

K

g(y)(1 + ǫ)
K
≥ (1 − 2 exp(−ǫ2 α4 N ′ )) p
g(y)(1 + ǫ)
K
K
≥p
− 2 exp(−ǫ2 α4 N ′ ) p
g(y)(1 + ǫ)
α (1 + ǫ)
(b)

K
K
≥ p
(1 − ǫ) − 2 exp(−ǫ2 α4 N ′ )
α
g(y)
K
K
(1 − ǫ) − 2 exp(−ǫ2 α4 (N − n)) .
≥p
α
g(y)
21

(19)

√1
1+ǫ

Here (a) follows from Hoeffding’s inequality, and (b) is because
The other inequalities result from the fact that g(s) ≥
we obtain:

α2

≥ 1 − ǫ for every ǫ ∈ (0, 1).

and |Nj | ≤ n. Taking ǫ = (N − n)−1/4 ,

K
− o(N ).
E(ej (y)) ≥ p
g(s)

Next, we also have,

K
g(y)(1 − ǫ)

K 

E(ej (y)) ≤ P (f¯j (y) ∈ [g(y)(1 − ǫ), g(y)(1 + ǫ)]) p


q
+ E 1{f¯j (y)∈{0}∪[g(y)(1−ǫ),g(y)(1+ǫ)]}
/

f¯j (y)


 √
K
+ P 1f¯j (s)∈{0}∪[g(y)(1−ǫ),g(y)(1+ǫ)]
K N′
/
g(y)(1 − ǫ)
(b)
√
K
+ 2K N ′ exp(−ǫ2 g(y)2 N ′ )
≤ p
g(y)(1 − ǫ)
√
K
≤p
+ 2K N ′ exp(−ǫ2 α4 N ′ )
g(y)(1 − ǫ)
(c)
√
K
ǫ
≤ p
(1 + + w(ǫ)) + 2K N ′ exp(−ǫ2 α4 N ′ )
2
g(y)
√
ǫK
|w(ǫ)|K
K
+
+
+ 2K N ′ exp(−ǫ2 α4 N ′ )
≤p
2α
α
g(y)
√
ǫK
|w(ǫ)|K
K
+
+
+ 2K N exp(−ǫ2 α4 (N − n)).
≤p
2α
α
g(y)
(a)

≤ p

(20)

Here, (a) results from the fact that on the event {f¯j (y) 6= 0}, f¯j (y) ≥ 1/N ′ . This is because
f¯j (y) only takes values in the set [0, N1 ′ , N2 ′ , · · · , 1]. (b) follows
from Hoeffding’s inequality, and (c)
√
follows from the Taylor approximation of the function 1/ 1 − ǫ, where w(ǫ) = o(ǫ). Now choosing
ǫ = (N − n)−1/4 , we get:
K
+ o(N ).
E(ej (y)) ≤ p
g(y)

Thus, we finally have |E(ej (y)) − √K | ≤ σ(N ) = o(N ), where σ(N ) ≥ 0 is some function of N
g(y)

that depends only on α, n and K and not on y.

Assuming everyone else is truthful, the expected reward of person j for evaluating object i if she
chooses a reporting strategy qij is,
X
X
X
X
R(qij ) ,
P (Yji′ = y, Yji = y)E(rj (y)) =
E(rj (y))
PX (x)py (x)
py′ (x)qyij (y ′ ).
y∈Y

y∈Y

x∈X

y ′ ∈Y

Thus the agent solves maxqij R(qij ). The objective is linear in qij , and further, qij (y) lies on a unit
simplex for each y ∈ Y. Thus the optimal reporting strategy chooses qij (y) to be one of the extreme
points of the simplex for each y ∈ Y, i.e., the optimal reporting strategy is deterministic. Now let
22

t be the truthful strategy, i.e., ty′ (y) = 1{y=y′ } . Then for any deterministic reporting strategy qij ,
we have,
X
X
X
R(qij ) =
E(ej (y))
qyij (y ′ )
PX (x)py (x)py′ (x)
y∈Y

(a)

≤

X

y ′ ∈Y

E(ej (y))

y∈Y

X

x∈X

sX

qyij (y ′ )

PX (x)py

(x)2

x∈X

y ′ ∈Y

sX

PX (x)py

x∈X

′ (x)2

− α1{y6=y′ }





X
X K
p
ij ′
′
+ σ(N ))
g(y)g(y ) − α1{y6=y′ }
qy (y )
≤
(p
g(y)
y ′ ∈Y
y∈Y
Xp
XX
XX
p
≤K
g(y ′ ) − αK
1{y6=y′ } qyij (y ′ ) + σ(N )
qyij (y ′ ) g(y)g(y ′ )
y ′ ∈Y

(b)

≤K

Xp

y ′ ∈Y

y ′ ∈Y y∈Y

(21)

y∈Y y ′ ∈Y

g(y ′ ) − αK1{qij 6=t} + |Y|σ(N ).

(22)

Here, (a) follows from the Cauchy-Schwarz inequality, from the definition of δ(Px , p), and the fact
that δ(Px , p) > α. (b) follows from the fact that qij is deterministic and so is t. While we have,
X
X
R(t) =
E(ej (y))
PX (x)py (x)2
y∈Y

x∈X

X K
− σ(N ))g(y)
≥
(p
g(y)
y∈Y
Xp
g(y) − |Y|σ(N ).
≥
y∈Y

Thus we have,
R(qij ) ≤ R(t) − αK1{qij 6=t} + 2|Y|σ(N )
Since σ(N ) depends only on δ and K and σ(N ) = o(1), there is an N1 that depends only on α, K,
n and |Y| such that for all N > N1 , 2|Y|σ(N ) < Kα, which means that truthful behavior is a strict
Bayes-Nash equilibrium. To prove the second statement, suppose that qij is a strategy in which
reports are chosen independently of the true answers. Denote qyij , qyij (y ′ ) since qyij (y ′ ) = qyij (y ′′ )
for all y, y ′ , y ′′ ∈ Y. Then in (21),
XX
XX
αK
1{y6=y′ } qyij (y ′ ) = αK
1{y6=y′ } qyij
y ′ ∈Y y∈Y

y ′ ∈Y y∈Y

= αK(|Y| − 1).

And thus,
R(qij ) ≤ R(t) − αK(|Y| − 1) + 2|Y|σ(N ).
Thus for any ω ∈ (0, αK(|Y| − 1)), there is a positive integer N2 depending on ω, α, K, n and |Y|
such that for any N > N2 , R(qij ) ≤ R(t) − ω. Choosing N0 = max(N1 , N2 ) proves the result.
Proof of Proposition 3. We have,
X
Xs
PX (x)py1 (x)py2 (x)qy (y1 )qy (y2 )
Γ(Z1 , Z2 ) =
y∈Y

x∈X,y1 ∈Y,y2 ∈Y

23

Xs

X

qy (y1 )qy (y2 )

v
Xu
u
t
≤

X


sX
sX
qy (y1 )qy (y2 )
PX (x)py1 (x)2
PX (x)py2 (x)2 − δ(PX , p)1y1 6=y2

=

y∈Y

(a)

y∈Y

y1 ∈Y,y2 ∈Y

y1 ∈Y,y2 ∈Y

X

PX (x)py1 (x)py2 (x)

x∈X

x∈X

x∈X

v
2
sX
Xu
u X
2
t
qy (y1 )
PX (x)py1 (x)
− δ(PX , p)
=
y∈Y

y1 ∈Y

x∈X

X

y1 ∈Y,y2 ∈Y



qy (y1 )qy (y2 )1y1 6=y2

P

(y ′ )q

′′
y (y )1y ′ 6=y ′′



sX
y ′ ∈Y,y ′′ ∈Y qy
δ(PX , p) X
2
pP
≤
qy (y1 )
PX (x)py1 (x) −
P
2
2
y1 ∈Y qy (y1 )
x∈X PX (x)py1 (x)
y∈Y
y∈Y,y1 ∈Y
x∈X


P
′
′′
y ′ ∈Y,y ′′ ∈Y qy (y )qy (y )1y ′ 6=y ′′
(c)
δ(PX , p) X
≤ Γ(Y1 , Y2 ) −
2
Γ(Y1 , Y2 )
(b)

X

y∈Y

(d)

≤ Γ(Y1 , Y2 ) −

(e)

≤ Γ(Y1 , Y2 ) −

δ(PX , p) X X
p
qy (y ′ )qy (y ′′ )1y′ 6=y′′
2 |Y| y∈Y y′ ∈Y,y′′ ∈Y

δ(PX , p)Ω(q)2 (|Y| − 1)
p
.
2 |Y|

Here, (a) follows from the Cauchy-Schwarz√inequality and the definition of δ(PX , p). (b) follows
√
√
from the fact that for a, b > 0 and a > b, a − b ≤ a − b/(2 a). (c) follows from the fact that
qy (y1 ) ≤ 1 and from the definition of Γ(Y1 , Y2 ). (d) follows from the fact that Γ(Y1 , Y2 ) ≤ |Y|. (e)
holds since, by Jensen’s inequality,
2

Ω(q) =
≤



X
|Y|
|Y|2 (|Y| − 1)

1 X
|Y| − 1

X

y∈Y y ′ ∈Y,y ′′ ∈Y

X

y∈Y y ′ ∈Y,y ′′ ∈Y

q

qy

(y ′ )q

′′
y (y )1y ′ 6=y ′′

2

qy (y ′ )qy (y ′′ )1y′ 6=y′′

Proof of Theorem 4. The first statement follows from Theorem 2: there is an N1 such that for all
N ≥ N1 , the truthful strategy profile is a Bayes-Nash equilibrium. We focus on the second claim.
With some abuse of notation, we denote etj (y) to be the agreement scores for an agent j under the
truthful equilibrium, and esj (y) to be the scores under a fixed symmetric equilibrium strategy profile
where each agent follows the reporting strategy q.
We have shown in the proof of Theorem 2 that if everyone is truthful, then |E(etj (y)) − √K | ≤
g(y)

σ(N ) = o(1), where σ(N ) ≥ 0 is some function of N that depends only on δ(PX , p), n and K and
not on y.
P
P
P
P
Let us denote x∈X PX (x)( y′ ∈Y py′ (x)qy (y ′ ))2 , s(y) and denote x∈X PX (x) y′ ∈Y py′ (x)qy (y ′ ) ,
b(y). By Jensen’s inequality, we have s(y) ≥ b(y)2 . Then using arguments similar to the ones leading
up to (20) in the proof of Theorem 2, we can show that for all y ∈ Y such that b(y) ≥ δ(PX , p)2 /|Y|
24

(and hence, s(y) ≥ δ(PX , p)4 /|Y|2 ), and for any ǫ ∈ (0, 1),

K
E(esj (y)) − p
≤ σ ′ (N ),
s(y)

where |σ ′ (N )| = o(1) depends on δ(PX , p), K, n and |Y|. Consider the strategy q and consider
a y ∈ Y, such that b(y) > 0 but b(y) < δ(PX , p)2 /|Y|. Then one can construct another strategy
q′ such that a) a fixed agent j is indifferent between choosing q and q′ assuming everyone else is
playing q, and, 2) for all y such that b(y) < δ(PX , p)/|Y|, qy′ (y ′ ) = 0 for all y ′ ∈ Y. To show this,
observe that for each y ′ , q(y ′ ) cannot have support only on those y for
which b(y) < δ(PX , p)2 /|Y|.
P
This is because if that is the case then P (Yji = y ′ ) = P (Yji = y ′ ) y∈Y;b(y)<δ(PX ,p)2 /|Y| qy (y ′ ) ≤
P
2
i
′
2
y∈Y;b(y)<δ(PX ,p)2 /|Y| b(y) < δ(PX , p) , which contradicts the fact that P (Yj = y ) ≥ δ(PX , p) as
we have seen in the proof of Proposition 1. So then define q′ (y ′ ) to have support only on the y ∈ Y
for which b(y) ≥ δ(PX , p)2 /|Y| by transferring the probability masses. If we define G(q) to be
the expected payment to a fixed agent j for a fixed task i under the symmetric equilibrium under
strategy q, and define G(q′ , q−j ) to be the expected
payment toP
j if she plays q′ while others play
P
q, then we have G(q) = G(q′ , q−j ). Let us define x∈X PX (x)( y′ ∈Y py′ (x)qy′ (y ′ ))2 , s′ (y). Then
we have,
G(q) = G(q′ , q−j )
X
≤

E(esj (y))

y∈Y; b(y)≥δ(PX ,p)2 /|Y|

(a)

≤

X

y∈Y; b(y)≥δ(PX ,p)2 /|Y|

X

PX (x)[

x∈X

X

py1 (x)qy′ (y1 )][

y1 ∈Y

X

py2 (x)qy (y2 )]

y2 ∈Y

p
E(esj (y)) s(y)s′ (y)

p
K
+ σ ′ (N )) s(y)s′ (y)
(p
s(y)
y∈Y; b(y)≥δ(PX ,p)2 /|Y|
X
p
≤
K s′ (y) + |Y|σ ′ (N )
X

≤

y∈Y; b(y)≥δ(PX ,p)2 /|Y|

(b)

=K

Xp
y∈Y

s′ (y) + |Y|σ ′ (N ).

(23)

Here (a) follows from the Cauchy-Schwarz inequality and (b) follows from the fact that s′ (y) = 0 for
all y such that b(y) < δ(PX , p)2 /|Y| by construction of the strategy q′ . Let G(t) be the expected
payment to agent j for task i under the truthful equilibrium. Let j ′ be j’s peer for task i. Then we
have,
X
G(t) =
E(etj (y))g(y)
y∈Y

≥
≥

(a)

X
y∈Y

K

X
p
g(y) −
σ(N )g(y)
y∈Y

KΓ(Yji , Yji′ )

≥K

Xp
y∈Y

− |Y|σ(N )

s′ (y) − |Y|σ(N ).

(24)

Here, (a) follows from Proposition 3. Finally, (24) and (23) together imply that, for a large enough
N,
G(t) ≥ G(q) − |Y|(σ(N ) + σ ′ (N )).
25

Thus for any ω > 0, there exists some N2 such that for any N ≥ N2 , the payoff under the truthful
equilibrium is less than that under any other symmetric strategy profile by at most ω. Taking
N0 = max(N1 , N2 ) proves our claim.
Proof of Theorem 5. As before, we denote etj (y) to be the agreement scores for an agent j under a
fully informative equilibrium, and esj (y) to be the scores under a fixed symmetric strategy profile
P
P
where each agent follows the reporting strategy q. We denote x∈X PX (x)( y′ ∈Y py′ (x)qy (y ′ ))2 ,
P
P
s(y) and denote x∈X PX (x) y′ ∈Y py′ (x)qy (y ′ ) , b(y). By our assumption b(y) ≥ η, and since
s(y) ≥ b(y)2 , we have s(y) ≥ η 2 . Then using arguments similar to the ones leading up to (20) in
the proof of Theorem 2, we can show that for all y ∈ Y, |E(etj (y)) − √K | ≤ σ(N ) = o(1), and
g(y)

|E(esj (y))

− √K | ≤ σ ′ (N ) = o(1), where σ(N ) ≥ 0 is some function of N that depends only on
s(y)

δ(PX , p), n and K, and σ ′ (N ) ≥ 0 is some function of N that depends only on δ(PX , p), η, n and
K. Neither of these functions depend on y. Let G(t) and G(q be the expected payments to agent
j for task i under the truthful strategy profile and the symmetric profile q. Let j ′ be j’s peer for
task i. Let Zji and Zji′ be the reported answers of j and j ′ for task i under q. Then we have,
G(q) =

X

E(esj (y))s(y)

y∈Y

≤
≤

X

K

X
p
s(y) +
s(y)σ ′ (N ))
y∈Y

y∈Y

KΓ(Zji , Zji′ ) +

|Y|σ ′ (N ).

(25)

Similarly, we can show that
G(t) =

X

E(est (y))g(y)

y∈Y

≥

X
y∈Y

K

p

g(y) −

X

g(y)σ(N ))

y∈Y

≥ Γ(Yji , Yji′ ) − |Y|σ(N ))
≥ Γ(Zji , Zji′ ) +

δ(PX , p)Ω(q)2 (|Y| − 1)
p
− |Y|σ(N ).
2 |Y|

(26)

Thus if G(q) ≥ G(t) for any strategy q, then this implies that,
KΓ(Zji , Zji′ ) +
which implies that

or that,

δ(PX , p)Ω(q)2 (|Y| − 1)
p
− |Y|σ(N ) ≤ KΓ(Zji , Zji′ ) + |Y|σ ′ (N ),
2 |Y|
δ(PX , p)Ω(q)2 (|Y| − 1)
p
≤ |Y|(σ(N ) + σ ′ (N )),
2 |Y|
Ω(q) ≤

s

2|Y|3/2 (σ(N ) + σ ′ (N ))
.
δ(PX , p)(|Y| − 1)

(27)

Now the quantity on the right is o(1). Thus for any ω > 0, there exists some N0 such that for
any N ≥ N0 , any symmetric strategy profile that gives a higher expected payoff to each agent than
26

the truthful strategy profile is at most ω−uninformative. Since truthful reporting is a Bayes-Nash
equilibrium for a large enough N , this implies the result.

Proof of Proposition 3. We have,
Xp
Xs
P (Z1 = Z2 = y) =
y∈Y

y∈Y

=

Xs
y∈Y

PX (x)py1 (x)py2 (x)qy (y1 )qy′ (y2 )

x∈X,y1 ∈Y,y2 ∈Y

X

qy (y1 )qy′ (y2 )

X

qy (y1 )qy′ (y2 )

y1 ∈Y,y2 ∈Y

v
(a) X u
u
t
≤
y∈Y

X

X

PX (x)py1 (x)py2 (x)

x∈X

sX

y1 ∈Y,y2 ∈Y

PX (x)py1

(x)2

x∈X

sX

PX (x)py2

x∈X

(x)2



v
 X

sX
sX
Xu
u X
2
2
′
t
qy (y1 )
PX (x)py1 (x)
PX (x)py2 (x)
qy (y2 )
=
y∈Y

y1 ∈Y

x∈X

y2 ∈Y

x∈X

sX
sX
X
(b) 1
1 X
′
2
qy (y1 )
qy (y2 )
≤
PX (x)py1 (x) +
PX (x)py2 (x)2
2
2
y∈Y,y1 ∈Y
y∈Y,y2 ∈Y
x∈X
x∈X
sX
sX
X
X
1
1
PX (x)py1 (x)2 +
PX (x)py2 (x)2
=
2
2
y1 ∈Y

y2 ∈Y

x∈X

x∈X

Γ(Y1 , Y2 ) Γ(Y1 , Y2 )
+
2
2
= Γ(Y1 , Y2 )

=

Here, (a) follows from the Cauchy-Schwarz inequality, and (b) results from the fact that the arithmetic mean of two numbers is no less than the geometric mean.

27

