Peer Prediction with Heterogeneous Tasks
Debmalya Mandal\Mark{1
Peer prediction promotes contributions of useful information by users in settings in which there is no way to verify the quality of responses. This paper introduces the problem of peer prediction with heterogeneous tasks, where each task is associated with a different distribution on responses. The motivation comes from eliciting user-generated content about places in a city, where tasks vary because places and questions about places vary. %% We extend the {\em correlated agreement (CA) %multi-task peer prediction mechanism~(\cite{shnayder2016informed) to this setting, aligning incentives for investing effort without creating opportunities for coordinated manipulations. We demonstrate in simulation much better incentive properties than other mechanisms, using data from %from user reports on a crowdsourcing platform.
hetpp-tasks-arxiv.tex
\def\year{2018}\relax
%File: formatting-instruction.tex
\documentclass[letterpaper]{article} %DO NOT CHANGE THIS
\usepackage{aaai18}  %Required
\usepackage{times}  %Required
\usepackage{helvet}  %Required
\usepackage{courier}  %Required
\usepackage{url}  %Required
\usepackage{graphicx}  %Required
\usepackage{etoolbox}
\usepackage{blkarray}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{graphics}
\usepackage{amsthm}

\usepackage{color}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{amsmath,amsthm}

\newtoggle{anon}
\toggletrue{anon}

\newtheorem{example}{Example}

\newcommand{\new}[1]{{\em #1\/}}		% New term (set in italics).
\newcommand{\set}[1]{\{#1\}}			% Set (as in \set{1,2,3})
\newcommand{\setof}[2]{\{\,{#1}|~{#2}\,\}}	% Set (as in \setof{x}{x > 0})
\newcommand{\C}{\mathbb{C}}	                % Complex numbers.
\newcommand{\N}{\mathbb{N}}                     % Positive integers.
\newcommand{\Q}{\mathbb{Q}}                     % Rationals.
\newcommand{\R}{\mathbb{R}}                     % Reals.
\newcommand{\Z}{\mathbb{Z}}                     % Integers.
\newcommand{\compl}[1]{\bar{#1}}		% Complement of ...   
\newcommand{\Su}[1]{\mathcal{S}\left( #1\right)}
\newcommand{\E}[1]{E\left[ #1 \right]}
\newcommand{\Em}[2]{\mathbf{E}_{#1} \left[ #2 \right]}
\newcommand{\Pm}{\mathrm{Pr}}         
\newcommand{\Pro}[1]{\Pm \left(#1\right)}
\newcommand{\Prom}[2]{\Pm_{#1} \left[ #2 \right]}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\zpp}{\textbf{ZPP}}
\newcommand{\rp}{\textbf{RP}}
\newcommand{\crp}{\textbf{co-RP}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\bigo}[1]{O\left( #1 \right)}
\newcommand{\bigom}[1]{\Omega \left( #1 \right)}
\newcommand{\bigolog}[1]{\tilde{O} \left( #1 \right)}
\newcommand{\bigomlog}[1]{\tilde{\Omega}\left(#1\right) }
\newcommand{\sizf}{\abs{\F}}
\newcommand{\gnp}{G_{n,p}}
\newcommand{\gn}{G_{n,N}}
\newcommand{\nct}{{n \choose 2}}
\newcommand{\eve}{\mathcal{E}}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\mmod}{\textrm{ mod }}
\newcommand{\wb}{\textrm{WB}}
\newcommand{\Pref}{\mathbb{P}}
\newcommand{\Nm}{\mathcal{N}} % Normal Distribution
\newcommand{\sD}{\mathcal{D}}

\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]
\usepackage[space]{grffile}


\usepackage{array}
\usepackage{graphicx}
\usepackage{epstopdf}
\usepackage{wrapfig}
\usepackage{float}
\usepackage{cleveref}
\usepackage [english]{babel}
\usepackage [autostyle, english = american]{csquotes}
\MakeOuterQuote{"}
\newcommand{\eye}{\mathbb{I}}
\newcommand{\one}{\mathbf{1}}
\newcount\Comments  % 0 suppresses notes to selves in text
\Comments = 1
\newcommand{\kibitz}[2]{\ifnum\Comments=1{\color{#1}{#2}}\fi}
\newcommand{\dm}[1]{\kibitz{blue}{[Deb: #1]}}
\newcommand{\dcp}[1]{\kibitz{red}{[Dcp: #1]}}
\newcommand{\todo}[1]{\kibitz{cyan}{[TODO: #1]}}

%%%%%%% uncomment next five lines %%%%%%%
\frenchspacing  %Required
\setlength{\pdfpagewidth}{8.5in}  %Required
\setlength{\pdfpageheight}{11in}  %Required
%PDF Info Is Required:
  %\pdfinfo{
%/Title (Peer Prediction with Heterogeneous Tasks)}

\setcounter{secnumdepth}{2}  
 \begin{document}
% The file aaai.sty is the style file for AAAI Press 
% proceedings, working notes, and technical reports.
%
\title{Peer Prediction with Heterogeneous Tasks}
\newcommand\Mark[1]{\textsuperscript#1}
\author{Debmalya Mandal\Mark{1}, Matthew Leifer\Mark{1}, David C. Parkes\Mark{1}, Galen Pickard\Mark{2} and Victor Shnayder\Mark{1} \\
	\begin{tabular}{cc}
		\Mark{1} Harvard SEAS & \Mark{2} Google \\
		Cambridge, MA 02138 & New York, NY\\
	\end{tabular}\\
	\texttt{\{dmandal@g, matthewleifer@college, parkes@eecs\}.harvard.edu},\\
	\texttt{gpickard@google.com, shnayder@gmail.com}
}
\maketitle
\begin{abstract}
Peer prediction promotes contributions
of useful information by users in settings 
in which there is no way to verify the
quality of responses. This paper introduces
the problem of peer prediction with heterogeneous tasks,
where each task 
is associated with a different distribution on responses.
The  motivation comes from 
eliciting
user-generated content
about places in a city,
where tasks vary because places
and questions about places vary. 
%%
We extend the {\em correlated agreement (CA)}
%multi-task peer prediction
mechanism~(\cite{shnayder2016informed})
to this setting,
aligning incentives for investing effort
without creating opportunities for coordinated
manipulations. We demonstrate in simulation much better incentive
properties than other mechanisms, 
using 
data from 
%from 
user reports on a crowdsourcing platform.
\end{abstract}

\section{Introduction}

Peer prediction refers to the problem of scoring information reports
in settings where the correctness of a report cannot be verified,
either because there is no objectively correct answer or because this
answer is too costly to acquire. This problem arises in diverse
contexts; e.g., peer assessment of assignments in massive open online
courses, and when collecting feedback about a new restaurant.  Peer
prediction algorithms use reports from multiple participants to score
contributions.

Simple approaches compare 
the responses of two users and award them if they agree. But this does
not promote truthful reporting when one user believes that it is
unlikely that another user will have the same opinion.  This problem
can be alleviated by adjusting scores according to the frequency of
reports~\cite{jurca2008truthful,witkowski2012robust,kamble2015truth}.

A limitation of current approaches, however, is that tasks are assumed to be
{\em ex ante} identical, with each task associated with the same 
distribution on reports.
But tasks on various maps platforms, %such as {\em Google Local Guides}, which seek
which seek to elicit content from users about places in a city,
are quite heterogeneous.  On this kind of platform, a user is
encouraged to answer several 
different types of questions (= tasks) related to the same
place; e.g., ``is the restaurant noisy?,'' ``is it accessible
by wheelchair?,'' or ``does it serve wine?'' The questions
are related to the same place,
yet  the prior beliefs
about the distribution on reports for each type of
question may be  very different.
%This motivates us to address the problem of designing a peer
%prediction mechanism with heterogeneous tasks.
%

We design a new, multi-task peer prediction mechanism (the {\em
	correlated agreement-heterogeneous mechanism}) that is responsive to
this challenge. This new mechanism shares similar properties with the
earlier {\em correlated agreement} (CA)
mechanism~\cite{shnayder2016informed}.  In particular, it is {\em
	informed truthful} under weak conditions, meaning that it is
strictly beneficial for a user to invest effort and acquire
information, and that truthful reporting is the best strategy when
investing effort, as well as an equilibrium. We demonstrate that the
mechanism has good incentive properties when tested in simulation on
distributions derived from user reports on a popular maps platform.\footnote{Name of platform removed to respect double-blind submission policy. Summary
statistics, that define distributions on pairs of signal reports
and are used for simulations, will be made available.}
%
% are used for the simulations,   %Google Local Guides.


\subsection{Related Work}

We focus in this brief discussion on mechanisms that are {\em minimal}, in the sense that
they only require signal (or information) reports and do not require
belief reports.  Miller et al.~\citeyear{MRZ2005} introduced the peer
prediction problem and proposed a minimal mechanism that has truthful
reporting in an equilibrium, however the 
mechanism's design requires 
knowledge of the joint 
signal distribution and is 
vulnerable to coordinated misreports.
%
In response, Jurca and Faltings~\shortcite{jurca2009mechanisms} show
how to eliminate uninformative, pure-strategy equilibria through a three-peer mechanism, and Kong et al.~\shortcite{kong2016putting} provide a method to design robust, single-task,
binary signal mechanisms.
% (but need knowledge of the joint signal distribution).

Witkowski and Parkes~\shortcite{witkowski2012robust} first
introduced the combination of learning and peer prediction, coupling the estimation of
the signal prior together with the shadowing mechanism.
%
There has also been work on making use of reports from a large
population and coupling scoring with estimation.  For a setting with
latent ground truth model, Kamble et al.~\shortcite{kamble2015truth}
provide mechanisms that guarantee strict incentive compatibility with
a large number of agents.  
%\dcp{not sure next comment is right. 
%can you confirm?} 
Radanovic et al.~\shortcite{radanovic2016incentives} provide a mechanism in which
truthfulness is the highest-paying equilibrium in the asymptote of a
large population and with a self-predicting condition that places a
structure on the correlation structure.

Dasgupta and Ghosh~\shortcite{dasgupta2013crowdsourced} show that
robustness to coordinated misreports can be achieved by using reports
across multiple tasks along with access to partial information about
the joint distribution.  The main insight in the DG mechanism is to
reward agents if they provide the same signal on the same task, but
punish them if one agent's report on one task is the same as another's
on another task.  Shnayder et al.~\shortcite{shnayder2016informed}
generalize DG to handle multiple signals, and show how the required
knowledge about the distribution (the correlation structure on pairs
of signals) can be estimated from reports without compromising
incentives.  Their correlated agreement (CA) mechanism rewards pairs
of reports on the same task (penalizes pairs of reports on different
tasks) based on whether signals are positively or negatively
correlated. On the other hand, ~\cite{agarwal2017} generalize the CA
mechanism when users are heterogeneous and derive sample complexity bounds for
learning the reward matrices.
%
%
%
%
Shnayder et al.~\shortcite{shnayder-ijcai16} adopt replicator dynamics
as a model of population learning in peer prediction, and confirm that
these multi-task mechanisms (including Kamble et
al.~\shortcite{kamble2015truth}) are successful at avoiding uninformed
equilibria. 
%\dcp{i guess we need to briefly cite our ec 17 paper as well!
%also, should the `swiss noise' paper be cited? generally can probably
%shorten some discussion in this section if you meed the space.}

To the best of our knowledge, there is no prior work on extending the
design of these multiple-task mechanisms to heterogeneous tasks, where
pairs of reports may be on different types of tasks, with each task
associated with a different signal distribution.
%  This is the focus of
%the present paper.


\section{Heterogeneous, Multi-Task Peer Prediction}

Consider two agents, $1$ and $2$, who are members of a large population.
Each agent is assigned to a set of $M = \set{1,2,\ldots,m}$ tasks.
%Similar to \cite{shnayder2016informed} we
We adopt a binary effort model: if an agent invests effort he incurs a
cost and obtains an informed {\em signal}, otherwise the agent
receives no signal.  There are $n$ signals.  We do not assume that
tasks are {\em ex ante} identical, however, we do assume that the
signals for different tasks are drawn independently.  

Let $S^1_k$ and $S^2_k$ respectively be the signals of agents $1$ and
$2$ for task $k$ (if investing effort). Let $P_k(i,j) = \Pro{S^1_k =
  i, S^2_k = j}$ be the joint probability for a pair of signals
$(i,j)$ on task $k$ and let $P_k(i)$ and $P_k(j)$ be the corresponding
marginal probabilities.  We assume that the agents are exchangeable in
their roles in these distributions, with the same marginal
distributions and joint distributions for any pair of agents.

An agent's strategy maps every task and every received signal to a
reported signal. Agents make reports without knowledge of each others'
reports. We assume that the type of task, and signal about a task
(upon investing effort), is the only information available to an
agent.  For the theoretical analysis, we assume that an agent adopts
the same strategy across all tasks. We leave the analysis of asymmetric strategies for future work.
%Section~\ref{sec:asymmetric} shows
%that this restriction incurs only a small loss in agents' utilities
%when the number of tasks $m$ is large.
\footnote{This is without loss
  of generality in the homogeneous task setting
  of~\cite{shnayder2016informed}, but need not be in the present
  context.}
%
We allow an agent's strategy to be randomized, i.e. a probability
distribution over the set of possible signals. We will write $F$ and
$G$ to denote the mixed strategies of agents $1$ and $2$ respectively.
Let $\eye$ denote the truthful strategy i.e. $\eye(j) = j$. As in~
Shnayder et al.~\shortcite{shnayder2016informed}, we are interested in
the following two incentive properties:
%
\begin{definition}(Strong Truthful) A peer prediction mechanism is
  {\em strong truthful} iff for all strategies $F,G$ we have
  $E(\eye,\eye) \geq E(F,G)$, where equality may hold only when $F$
  and $G$ are both the same permutation strategy (i.e. a bijection
  from received signals to reported signals.)
\end{definition}
%
\begin{definition}(Informed Truthful) A peer prediction mechanism is
  {\em informed truthful} iff for all strategies $F, G$ we have
  $E(\eye,\eye) \geq E(F,G)$, where equality may hold only when $F$
  and $G$ are informed strategies (i.e. reports depend on an agent's
  signal).
\end{definition}
\if 0
\dcp{i'm wondering whether, anticipating the simulation analysis we do
  later, we want to explain why these properties imply robustness in a
  larger population when some fraction play one way and some fraction
  play another. I think they do, but don't have a clear recollection
of having explained this in a previous paper. please add
a comment to this effect if you've
seem this or agree it's true.}
\fi 
These two truthfulness properties imply that truthful reporting is a
strict and weak correlated equilibrium,
respectively~\cite{shnayder2016informed}. They also ensure that there
are no useful, coordinated misreports available to agents.

\subsection{Delta Matrices}

Following~Shnayder et al.~\shortcite{shnayder2016informed} to multiple
types of tasks, a first approach would be to define the following
$n\times n$ matrix for task $k$:
%
\begin{equation}\label{eq:original-delta}
\Delta_k(i,j) = P_k(i,j) - P_k(i)P_k(j).
\end{equation}

Let $S_k$ be the {\em sign matrix} of $\Delta_k$ i.e. $S_k(i,j) = 1$ if
$\Delta_k(i,j) > 0$ and $S_k(i,j) = 0$ otherwise.  

In the original CA mechanism~\cite{shnayder2016informed}, each task
$k$ is {\em ex ante} identical, and thus has the same delta matrix.
Denote this matrix $\Delta$, with $S$ the corresponding sign matrix.
%
%Suppose two agents 
%provide reports on each of multiple tasks
%of kind $k$. Then 
The original
CA mechanism works as follows:
\begin{enumerate}
	\item Let $r^1_k$ ($r^2_k$) be the signal reported by agent $1$ ($2$) on task $k$.
	\item Pick a task $b$ uniformly at random
	as the {\em bonus task}, and
	pick {\em penalty tasks} $l'$ and $l''$ (with $l'\neq l''$)
	uniformly at random from the remaining tasks.
	%
	\item Pay each agent $S(r^1_b, r^2_b) - S(r^1_{l'}, r^2_{l''})$. 
\end{enumerate}

A simple generalization is to pay $S_b(r^1_b, r^2_b) - S_b(r^1_{l'},
r^2_{l''})$, where $S_b$ is the sign matrix corresponding to the bonus
task. But this is not informed truthful for heterogeneous tasks. This
is demonstrated in Example~\ref{ex:dp1}.
%
\begin{example}[CA is not informed truthful with heterogeneous tasks]
\label{ex:dp1}
	Consider three tasks (1, 2 and 3) 
	with the following joint probability distributions 
	\begin{equation*}
	\begin{array}{cc@{}c@{}c}
	& \begin{array}{cc} Y & N \end{array}
	&	\begin{array}{cc} Y & N \end{array}
	& \begin{array}{cc} Y & N \end{array}\\
	\begin{array}{c}
	Y \\ N
	\end{array}
	&	 \left[\begin{array}{cc}
	0.4 & 0.22 \\
	0.22 & 0.16 \\
	\end{array}\right]
	&	\left[\begin{array}{cc}
	0.7 & 0.14 \\
	0.14 & 0.02 \\
	\end{array}\right]
	& \left[\begin{array}{cc}
	0.4 & 0.22 \\
	0.22 & 0.16 \\
	\end{array}\right] \\
	& (P_1) & (P_2) & (P_3)
	\end{array}
	\end{equation*}
	
	and the following sign matrices:
	\begin{equation*}
	\mathit{sign}(\Delta_1) : \begin{bmatrix}
	1 & 0 \\ 0 & 1
	\end{bmatrix}
	\ \mathit{sign}(\Delta_2) : \begin{bmatrix}
	0 & 1 \\ 1 & 0
	\end{bmatrix}
	\ \mathit{sign}(\Delta_3) : \begin{bmatrix}
	1 & 0 \\ 0 & 1
	\end{bmatrix}
	\end{equation*}
	
	
	Suppose each agent adopts the truthful strategy, and
	task 1 is the bonus task, and 
	2 and 3 are the penalty tasks
	for agents 1 and 2,  respectively. Then the
	expected score is 
	\begin{align*}
	&\sum_{i,j} P_1(i,j) S_1(i,j) - P_2(i) P_3(j) S_1(i,j),%\\ & = \sum_{i,j : \Delta_1(i,j) > 0} P_1(i,j) - P_2(i) P_3(j) \\
	%&= P_1(Y,Y) - P_2(Y)P_3(Y) + P_1(N,N) - P_2(N) P_3(N) \\ &= 0.4 - 0.84 * 0.62 + 0.16 - 0.16 * 0.38 = -0.0216
	\end{align*}
	%
which evaluates to
%	An easy calculation shows that the expected score in this case is
	$-0.0216$.  This is true irrespective of whether the penalty tasks for
	1 and 2, respectively, are 2 and 3 or 3 and 2.  Similarly, we can show
	that the expected scores are $-0.1912$ and $-0.0216$ when the bonus
	task is task $2$ and $3$, respectively.
	
	Now consider the case when the first agent always 
	reports $N$. Suppose task $1$ is the bonus task and 
	tasks $2$ and $3$ are the penalty tasks for 1 and 2, respectively.
	The expected score 
	is
	%
	\begin{align*}
	&\sum_{i,j} P_1(i,j) S_1(N,j) - P_2(i)P_3(j) S_1(N,j), %\\ &= \sum_j S_1(N,j) \left\{ \sum_i P_1(i,j) - P_3(j) \sum_i P_2(i)\right\}\\
	%&= \sum_j S_1(N,j) \left\{ P_1(j) - P_3(j) \right\} = P_1(N) - P_3(N) = 0 
	\end{align*}
	%
which evaluates to $0$. Similarly, for task 3 and 2 as
	the penalty for 1 and 2, respectively, the expected score is $0.22$.
	So on average, the expected score for task 1 as bonus is $0.11$.
	Similar calculations show expected scores of 0.22 and 0.11, for tasks
	2 and 3 as bonus, respectively. Thus, the CA mechanism fails to be
	informed truthful for this example.% tasks are heterogeneous.
\end{example}

\section{The Correlated-Agreement Heterogeneous (CAH) Mechanism}

In this section, we extend the CA mechanism to handle heterogeneous
tasks. The main idea is to modify the delta matrix for a bonus
task to allow for the implied product distribution on 
signals on penalty tasks.~\Cref{algo:cah} describes the CAH mechanism.
% for rewarding responses to a 
%set of $m$ tasks. 
%The mechanism makes a payment for each of the $m$ tasks, with each
%task taken in turn as the bonus task. One can also simply choose one
%of the tasks at random as the bonus task.
%
\begin{algorithm}
	\caption{CAH mechanism\label{algo:cah}}
	\begin{algorithmic}[1]
		%	\Require Joint Probability Distributions $\{P_k(\cdot,\cdot)\}_{k=1}^m$ and reports $\{r^1_k,r^2_k\}_{k=1}^m$
		\Require Joint probability distribution $P_b(\cdot,\cdot)$, marginal probability distributions $\{P_l(\cdot)\}_{l\neq b}$ and reports $\{r^1_k,r^2_k\}_{k=1}^m$
		%		\For{$b = 1,\ldots,m$}
		\State $b \leftarrow$ uniformly at random from $\{1,\ldots,m\}$ (bonus task)
		%		\Comment{Reward bonus task $b$}
		\State $l' \leftarrow$ uniformly at random from $ \{1,\ldots,m\} \setminus \{b\}$ (penalty task assigned to agent 1)
		\State $l'' \leftarrow$ uniformly at random from $ \{1,\ldots,m\} \setminus \{b,l'\}$ (penalty task assigned to agent 2)
		\State Define $\Delta_b(i,j)$ as \begin{equation}\label{eq:defn-delta}
		\!\!\!\!P_b(i,j) - \frac{1}{(m-1)(m-2)}\!\sum_{\stackrel{t',t'' \in [m] \setminus \set{b}}{\& \ t' \neq t''} } \!\!\!\!P_{t'}(i)P_{t''}(j) 
		\end{equation} 
		\State Let $S_b(i,j)$ be the corresponding score matrix i.e. 
		\[S_b(i,j) = 1 \text{ if } \Delta_b(i,j) > 0 \text{ and } S_b(i,j) = 0 \ \text{otherwise}\]
		\State Make payment $S_b(r^1_b,r^2_b) - S_b(r^1_{l'}, r^2_{l''})$
		to each agent
		%		\EndFor
	\end{algorithmic}
\end{algorithm}

%\subsection{Analysis of the CAH Mechanism}

%We assume that the agents adopt the same strategy across
%all the tasks. 

In analyzing the properties of CAH, we note that it is sufficient to
consider only deterministic strategies. The proof of this statement is
analogous to Lemma 3.2~\cite{shnayder2016informed}, and uses the fact
that the maximization of a linear function over a convex region is
extremal.
%Now we compute the expected payment on a bonus task $b$ for
%deterministic strategies $F$ and $G$. We will

Given this, let $F_i$ ($G_j$) denote the report of agents 1 (2) on
signal $i$ ($j$).
% Let $l'$ and $l''$ 
%denote the penalty tasks assigned to agents $1$ and $2$ respectively, for a given bonus task $b$.
%
The expected score for strategies $F$ and $G$,
conditioned on some 
bonus task $b$, denoted as $E_b(F,G)$, is:
%
\begin{align}
& \Em{l',l''}{\sum_{i,j} P_b(i,j) S_b(F_i,G_j) - \sum_{i,j} P_{l'}(i) P_{l''}(j) } \notag \\
&=  \sum_{i,j} P_b(i,j) S_b(F_i,G_j)  \notag \\
&- \sum_{\stackrel{l',l'' \in [m] \setminus \set{b}}{\& \ l' \neq l''}} \frac{1}{(m-1)(m-2)} \sum_{i,j} P_{l'}(i)P_{l''}(j)S_b(F_i,G_j)\notag\\
%-\frac{1}{(k-1)(k-2)} \sum_{i=1}^n \sum_{j=1}^n P_{l''}(i)P_{l'}(j)S_b(F_i,G_j)\right] \\
&=  \sum_{i,j} \Delta_b(i,j) S_b(F_i,G_j), \label{eq:dcp1}
\end{align}

%
where $\ell$ and $\ell''$ denote agent 1 and agent 2's penalty tasks,
respectively.
%
%\dcp{deb--- suggest just working with one $b$ at random, and thus adding
%$1/m$ here}\dm{done, but suggest using $\sum_b E_b$ if we decide to add the analysis for the heterogeneous strategies across tasks}
%
Thus, the expected score, averaged over the $m$
possible bonus tasks, is 
%
\begin{align} \label{CA-score}
E(F,G) = \frac{1}{m} \sum_{b=1}^m E_b(F,G) = \frac{1}{m} \sum_{b=1}^m \sum_{i,j} \Delta_b(i,j) S_b(F_i,G_j)
\end{align}

We now state a property about the 
delta matrices~\eqref{eq:defn-delta}.
%\footnote{\dcp{needs to point to appendix instead}
%Due to limited space, some proofs are omitted from the current paper.
%	They will be provided in the longer version of the paper.}
%
\begin{lemma}\label{lem:delta-zero}
	For each task $b$, we have $\sum_{i,j} \Delta_b(i,j) = 0$
\end{lemma}

%\dcp{Give a 1-2 sentence sketch?}
\begin{proof}
	See Appendix \ref{app:defn-zero}
\end{proof}


\subsection{Informed Truthfulness}

The CAH mechanism is informed truthful under a  weak condition on
the signal distributions.
%
%
%\noindent{\bfseries Condition 2} : Each entry of $\Delta_b$ is non-zero.
\begin{theorem}\label{thm:informed-ca3}
	If for each task $b$, $\Delta_b$ is symmetric and each entry of $\Delta_b$ is non-zero, then the CAH mechanism is informed truthful. 
\end{theorem}
%
\begin{proof}
	For any bonus task $b$, the truthful strategy $(\eye,\eye)$ has higher expected score than any other pair of strategies $F,G$:
	%
	\begin{align*}
	&E_b(\eye,\eye) =  \sum_{i,j} \Delta_b(i,j) S_b(i,j) =  \sum_{i}\sum_j \max(0,\Delta_b(i,j))
	\\& \geq  \sum_{i,j} \Delta_b(i,j) S_b(F_i,G_j) = E(F,G).
	\end{align*}
	
	Consider an uninformed strategy $F$, with $F_i = r$ for all $i$. Then for any $G$,
	the expected score is
	\begin{align*}
	&\sum_{i=1}^n \sum_{j=1}^n \Delta_b(i,j) S_b(r,G_j) =  \sum_{j=1}^n S_b(r,G_j) \sum_{i=1}^n \Delta_b(i,j) \\ &\leq  \sum_{j=1}^n \max(0, \sum_{i=1}^n \Delta_b(i,j)).
	\end{align*}
	
	We need to show the following:
	\begin{align*}
	& \sum_{j=1}^n \max(0, \sum_{i=1}^n \Delta_b(i,j)) < 
	\sum_{j=1}^n \sum_{i=1}^n \max(0,\Delta_b(i,j)).
	\end{align*}
	
	It is enough to show that for each $b$, there exists a column $j$ and two different rows $i_1,i_2$ such that $\Delta_b(i_1,j) > 0$ and $\Delta_b(i_2,j) < 0$.
	%
	Suppose not. Then each column of $\Delta_b$ has either all
        positive entries or all negative entries. Since each entry of
        $\Delta_b$ is non-zero and Lemma~\ref{lem:delta-zero} holds,
        there exist two columns $j_1$ and $j_2$ such that all entries
        of $j_1$ ($j_2$) are positive (negative). This implies
        $\Delta_b(j_2,j_1) > 0$ and $\Delta_b(j_1,j_2) < 0$, which
        contradicts the fact that $\Delta_b$ is symmetric.
\end{proof}

\subsection{Strong Truthfulness}

%\dcp{suggest switching this section with the next, just so the reviewer sees
%	a proof before s/he sees another proof for which there isn't space.}

We state a sufficient condition for the CAH mechanism to satisfy the property
of strong truthfulness.

{\bfseries Condition 1} :
\begin{enumerate}
	\item  $\Delta_b(i,i) > 0$, $\quad \forall b\ \forall i$.
	\item $\sum_{b=1}^m \Delta_b(i,j) < 0$, $\quad \forall i \neq j$.
\end{enumerate}
%
\begin{theorem}\label{thm:strong-cah}
	If $\{\Delta_b\}_{b=1}^m$ satisfy  Condition 1, 
	then the CAH mechanism is strongly truthful.
\end{theorem}
%
\begin{proof}
See Appendix \ref{app:strong-cah}.
\end{proof}

%\dm{Open question : is condition 1 necessary for strong truthfulness?}

%\subsection{Categorical $\Delta_b$}

Condition 1 is slightly weaker than the {\em categorical}
condition~\cite{shnayder2016informed}.
$\Delta_b$ is categorical if
(1) $\Delta_b(i,i) > 0$ for all signals $i$, and (2) $\Delta_b(i,j) <
0$ whenever $i\neq j$; i.e., same-signal positive
correlation and other-signal negative correlation.  
%
Condition 1 does not require every
off-diagonal entry to be negative for all tasks $b$, but
only that the average of
the off-diagonal entries is negative.
%\dcp{deb-- if we need the space, suggest to drop next thm and argument and just include
%a sentence to state the observation}
Categorical and Condition~1 are equivalent when there are only two signals.
%
%\begin{theorem}\label{thm:cat-cond1-cah}
%Condition 1 and the categorical condition are equivalent when there are only two signals.
%\end{theorem}
%
%\begin{proof}
%	
%\todo{See Appendix \ref{app:cat-cond1-cah}.}
%
\if 0
Both the conditions require 
\begin{align}\label{eq:cat}
P_b(Y,Y) > P_{l'}(Y) P_{l''}(Y) \ \text{ and } \ P_b(N,N) > P_{l'}(N)P_{l''}(N)
\end{align}

\dcp{need more here. not clear what the defn of categorical is and why 
	categorical is equiv to condition 1}
\fi 

\subsection{Combining CAH with Estimation}

As with the CA mechanism~\cite{shnayder2016informed}, the CAH
mechanism remains (approximately) informed truthful even when the
statistics used to determine scores are estimated from the reports of
strategic agents.  The reason is that the score matrix that
corresponds to the correct statistics is the best possible score
matrix for agents, and thus they cannot do better by cooperating in
designing an alternate matrix. 
% \dcp{this is what you start calling
 % CAHR or empirical CAH later in the paper. decide what to call it and
 % be consistent.} 

(Algorithm~\ref{algo:learning-cah}) presents the detail-free version of CAH mechanism, which learns the 
delta matrices from the agents' reports. We will refer to this implementation as CAHR (in short for CAH recomputed).
The next theorem proves that CAHR
is $(\varepsilon,\delta)$-informed
truthful.
%
\begin{theorem}\label{thm:detail-free-cah}
	If there are at least $q = \bigom{ \frac{n}{\varepsilon^2} \log \left( \frac{m}{\delta}\right)}$ agents reviewing each task, for $m$ tasks and $n$ possible signals,
	then with probability at least $1 - \delta$, then CAHR satisfies
	\[
	%\frac{1}{m}\E{\eye,\eye} \geq \frac{1}{m}\E{F,G} - \varepsilon \quad \forall F,G 
	\E{\eye,\eye} \geq \E{F,G} - \varepsilon \quad \forall F,G 
	\]
\end{theorem}
\begin{proof}
See Appendix \ref{app:detail-free-cah}
\end{proof}
%

%\dcp{if you have the full proof then also give it in the appendix} 

Theorem~\ref{thm:detail-free-cah} implies that truthful reporting is
an approximate equilibrium for the detail-free CAH, and that (up to
$\epsilon$) there is no useful joint deviation.
%
The proof follows from  the fact that any joint
distribution $P_b(\cdot,\cdot)$ (resp. marginal distribution
$P_b(\cdot)$) can be learned with $\bigolog{n^2/\varepsilon^2}$ (resp.
$\bigolog{n/\varepsilon^2}$) samples\footnote{$\bigolog{\cdot}$ is
  $\bigo{\cdot}$ without all the log factors} and observing that $q$
samples from a task gives us $q^2$ samples from the corresponding
joint distribution.
%We would like to point out that our detail-free implementation is
%characteristically different from \cite{shnayder2016informed} in the sense that we require each task to be completed by several agents, 
%rather than having an agent complete several tasks. 
In addition, we can show a general version of~\Cref{thm:detail-free-cah}. Suppose there
are $t$ distinct types of tasks, and  the number of tasks of type $k$ is $m_k$. Then it is sufficient to have $q = \bigomlog{\frac{1}{\sqrt{m_k}}\frac{n}{\varepsilon^2}}$ samples from each task of type $k$. This follows from the observation that if we have
at least $q$ samples from each task of type $k$ then the total number of samples from the joint distribution $P_k(\cdot,\cdot)$ is at least $m_k q^2 = \bigomlog{{n^2}/{\varepsilon^2}}$.
%
%\dcp{give interpretation of the result for the case of task types. i.e.,
%need this many for each type, presumably?}\dm{added a proof sketch and comment.}
%
\begin{algorithm}[h]
	\caption{ 
CAHR mechanism\label{algo:learning-cah}}
	\begin{algorithmic}[1]
		\Require Agent $p$ of a population of $q$ 
		agents provides reviews $(r^p_1,\ldots,r^p_m)$ on
		each of the $m$ tasks.
		%
		\State $T_k(i,j) \leftarrow $ observed freq of signal pair $i,j$ on task $k$.
		\State Pair up the agents uniformly at random, and  run CAH for each pair with the estimated distribution $\{T_k(\cdot,\cdot)\}_{k=1}^m$
	\end{algorithmic}
\end{algorithm}


\if 0
We leave to future work an analogous statement for a setting where tasks
are from a number of discrete distribution 
types.
\fi 
%
%, this $m'\ll m$.
\if 0

\dcp{deb--- will want to defer proof to full version paper. also, may be helpful
	to give a bit of intuition for why $m$ appears in the analysis given that
	we already say we need this much data ``for each task.'' Finally, could
	we state the complexity
	result for different KINDS of tasks rather than tasks? I guess it
	would be easy to do and I think it's going to seem much more appealing.}
\dm{(1) I was trying to compare the sample complexity of this theorem with the 
	sample complexity of the original CA paper. Since the original CA paper
	guarantees that the per-task regret is bounded by $\varepsilon$, I also had
	a factor of $1/m$ to bound the average regret. Note that, $\E{F,G}$ still equals $1/m \sum_{b=1}^m E_b(F,G)$
	(2) Deriving a sample complexity bound for different kind of tasks actually seems cumbersome. For a given bonus
	task $b$, learning $\Delta_b$ requires samples from the joint distribution of $b$ and also samples
	from the marginals of the other tasks. So it's easier to state a sample complexity result for learning all the $m$ scoring
	matrices. Do you have something like the following in mind -- the sample complexity for a given task $b$ should depend on
	how different $b$ is from the ``average'' of other tasks, in case it is the same we should get something similar to the
	original CA sample complexity bound.}
\dcp{In regard to why $m$ appears in the
	sample complexity: I think you're pointing out that at
	the moment we're essentially deriving 
	the sample complexity result separately,
	for any particular $\Delta_b$ (just before eq. 22
	in the proof). But looking at the proof, 
	why does $m$ appear in the
	term needed for the number of samples we need from 
	the
	joint distribution $P_b$ and from the marginal distribution
	on $P_b$?
	
	In regard to stating this thm for the number of different types of
	tasks, rather than the number of tasks: I understand that we need to
	construct each possible scoring matrix, but couldn't each one be
	derived from (i) the type of task $b$ is, and (ii) the frequency of
	different types of tasks-- so that we know how to calculate the sum
	product marginal term? If you agree with this, could we add a sentence
	to say that the result could be stated for $m'$
	different types of tasks, in place of $m$ tasks?}

\fi



\subsection{Cross Correlated Agreement}

%\dcp{consider dropping all discussion of CCAH to make space, and just
%mention in the conclusion / future work}

So far we have assumed that the probabilities of observing signals are
independent across different tasks. However, two users' responses to two
different tasks may be correlated (e.g. consider two questions -- (1) does
this restaurant serve alcohol and (2) does this restaurant serve wine?)
We will write $P_{l',l''}(i,j)$ to denote the
probability that a user sees signal $i$ on task $l'$ and another user
observes signal $j$ on task $l''$. When there are no correlations
among signals for different questions we have $P_{l',l''}(i,j) =
P_{l'}(i) P_{l''}(j)$. 
The {\em Cross
	Correlated Agreement for Heterogeneous Tasks} ({CCAH})
mechanism generalizes { CAH} by using the probabilities
$P_{l',l''}(\cdot,\cdot)$ for different pairs of tasks $(l',l'')$.

\begin{itemize}
	\item {CCAH} is same as {CAH} except it defines $\Delta_b(i,j)$, the $(i,j)$-th entry of delta matrix for task $b$ as : 
	\begin{align*}
	&P_b(i,j) - \frac{1}{(m-1)(m-2)}\sum_{\stackrel{t', t'' \in [m] \setminus \set{b}}{
			\& \ t' \neq t''}}P_{t',t''}(i,j)
	\end{align*}
\end{itemize}

%\dcp{are you sure that we don't also need to worry about 'cross-correlation'
%between b and l' and b and l''?}\dm{yes, this is because for a given bonus task $b$ the mechanism does not collect
%samples from the pair $b,l'$ and $b,l''$. This helps us to write the utility as $E_b(F,G) = \sum_{ij}P_b(i,j)S_b(F_i,G_j)  - \Em{l',l''}{P_{l',l''}(i,j)S_b(F_i,G_j)}$}%

CCAH is strong truthful and informed truthful under similar conditions stated in theorems \ref{thm:strong-cah} and 
\ref{thm:informed-ca3} respectively. Moreover, a sample complexity result analogous to~\Cref{thm:detail-free-cah} holds for a
detail-free implementation of CCAH. This is because if we have at least $q$ samples from both $l'$ and $l''$, then  we have at least $q^2$ samples
from the joint distribution $P_{l',l''}(\cdot,\cdot)$.  

\if 0
\subsection{Strong-Truthfulness}

\begin{theorem}\label{thm:stong-ccah}
	If $\{\Delta_b\}_{b=1}^m$ satisfy {\bfseries Condition 1} then {\bfseries CCAH} is strongly truthful.
\end{theorem}
\begin{proof}
	The proof is same as the proof of~\Cref{thm:strong-cah} since the previous proof does not use the structure of $\Delta_b$ matrices.
\end{proof}
%\dm{Open question : is condition 1 necessary for strong truthfulness?}

%\subsection{Categorical $\Delta_b$ for CCAH}
\if 0
Suppose there are only two signals ($Y$ and $N$) and three tasks ($b, l'$ and $l''$). Then matrix $\Delta_b$ is
\begin{align*}
\begin{array}{c|c|c|}
& Y \\ \hline
Y & P_b(Y,Y) - P_{l',l''}(Y,Y) \\ \hline
N & P_b(N,Y) - \frac{1}{2} (P_{l',l''}(N,Y) + P_{l'',l'}(N,Y))\\ \hline 
\end{array}
\end{align*}
\begin{align*}
\begin{array}{c|c|}
&N \\ \hline
Y & P_b(Y,N) - \frac{1}{2} (P_{l',l''}(Y,N) + P_{l'',l'}(Y,N))\\ \hline
N & P_b(N,N) - P_{l',l''}(N,N) \\ \hline
\end{array}	
\end{align*}
If $P_b(\cdot,\cdot)$ is symmetric, so is $\Delta_b$. Moreover, the sum of all the entries of $\Delta_b$ is zero. Therefore, $\Delta_b$ is categorical iff
\begin{align}\label{eq:cat}
P_b(Y,Y) > P_{l',l''}(Y,Y) \ \text{ and } \ P_b(N,N) > P_{l',l''}(N,N)
\end{align}
\fi 
As before, we can show that when there are only two signals {\bfseries Condition 1} and categorical $\Delta_b$ are equivalent. For more than two signals, in addition to each diagonal entry of the delta matrix to be positive, we need that each average off-diagonal entry is negative.

\subsection{Informed Truthfulness}

\begin{lemma}\label{lem:delta-zero-ccah}
	For each $b$, $\sum_{i,j} \Delta_b(i,j) = 0$
\end{lemma}
\begin{proof}
	The proof is same as~\Cref{lem:delta-zero} if we use the fact $\sum_j P_{l',l''}(i,j) = P_{l'}(i)$.
	\if 0
	\begin{align*}
	\sum_{i}\sum_{j} \Delta_b(i,j) &= \sum_i \sum_j \left\{P_b(i,j) - \frac{1}{(m-1)(m-2)} \sum_{l' \in [m] \setminus \set{b}} 
	\sum_{l'' \in [m] \setminus \set{b,l'}} P_{l',l''}(i,j) \right\} \\
	&= \sum_i \left\{ P_b(i) - \frac{1}{(m-1)(m-2)} \sum_{l' \in [m] \setminus \set{b}} 
	\sum_{l'' \in [m] \setminus \set{b,l'}} P_{l'}(i)   \right\} = 1-1= 0
	\end{align*}
	\fi
\end{proof}

\begin{theorem}\label{thm:informed-ccah}
	If for each $b$, $\Delta_b$ is symmetric and each entry of $\Delta_b$ is non-zero, then {\bfseries CCAH} is informed truthful. 
\end{theorem}
\begin{proof}
	The proof is same as before since the proof of~\Cref{thm:informed-ca3} does not use the structure of $\Delta_b$ matrices and lemma \ref{lem:delta-zero-ccah} holds.
\end{proof}

\subsection{Combining CCAH with Estimation}
The detail-free implementation of CCAH is similar to algorithm \ref{algo:learning-cah}, except that 
it estimates the joint distributions $\{P_b(\cdot,\cdot)\}_{b=1}^m$ and the pairwise distributions $\{P_{t',t''}(\cdot,\cdot)\}_{t' \neq t''}$
from the samples and then run {\bfseries CCAH} with the estimated distributions. We can prove that the detail-free implementation of CCAH
has identical sample complexity as the detail-free implementation of CAH.

\begin{theorem}\label{thm:detail-free-ccah}
	If there are at least $q = \bigom{ \frac{n}{\varepsilon^2} \log \left( \frac{m}{\delta}\right)}$ agents reviewing each task, for $m$ tasks and $n$ possible signals,
	then with probability at least $1 - \delta$, the detail-free implementation of {\bfseries CCAH} satisfies
	\[
	%\frac{1}{m}\E{\eye,\eye} \geq \frac{1}{m}\E{F,G} - \varepsilon \quad \forall F,G 
	\E{\eye,\eye} \geq \E{F,G} - \varepsilon \quad \forall F,G 
	\]
\end{theorem}\begin{proof}
	\todo{See Appendix \ref{app:detail-free-ccah}}
\end{proof}
\fi 

\if 0
\subsection{Asymmetric Strategy Profile}\label{sec:asymmetric}
\begin{theorem}\label{thm:asymmetric}
	For any pair of asymmetric strategies $F = \{F_k\}_{k \in [m]}$ and $G = \{G_k\}_{k \in [m]}$ there exists a symmetric strategy $\bar{F}$ such that
	\[
	\abs{\E{F,G} - \E{\bar{F},G} } = \bigo{n^2 / m}
	\]
\end{theorem}
\begin{proof}
	See Appendix \ref{app:uniformization} for a proof.
\end{proof}
%\dcp{i think we'll need a full proof in appendix as well}
%The proof considers the following symmetric strategy 
%	\[
%	\bar{F}_{ij} = \sum_{k=1}^m \frac{P_k(i)}{\sum_{k'} P_{k'}(i)} F^k_{ij}
%	\]
        For most applications the number of signals $n$ is small, and
        as long as the number of tasks $m$ is large ($\geq
        n^2/\varepsilon$), we have $\E{\bar{F},\bar{G}} \geq \E{F,G} -
        2\varepsilon$. This implies that as long as there is a large
        number of tasks, we can prove approximate versions of
        Theorems~\ref{thm:strong-cah} and~\ref{thm:informed-ca3} even
        under arbitrary asymmetric strategy profiles.
\fi 
\section{Experimental Results}


%

\iftoggle{anon}{XYZ}{Google Local Guides} is 
a platform for collecting user generated content in regard to places
on \iftoggle{anon}{a mapping platform}{Google Maps}. A user can provide information by answering `yes',
`no,' or `not sure' to a series of questions.\footnote{We 
	ignore the `not sure' response for a question
	because of unclear semantics: does it mean the user has
	missing information, or the question is not relevant to
	the location. Thus, {\em a priori} it is unclear whether to expect
	correlation between different reports.}
%
A user is awarded
% points 
%based  on the
%quantity of her 
%contribution, where a contribution can be a review or a 
%photograph  or any update about the place.
% \dcp{deb/matt--- complete by explaining the cap
%on this in converting to Google drive, and
%the role of scores in leading
%to social capital on the app via 'expert level' and visibility
%to others.}
%\iftoggle{anon}{XYZ}{Google} awards 
one point for each contribution,
where a contribution can be a review or a 
photograph  or any update about the place,
 with a maximum of five
points per place. Based on the number of points received a user 
is in  one of five 
levels on the platform, with higher levels providing
better benefits such as free \iftoggle{anon}{online storage}{Google Drive space}, visibility on the
\iftoggle{anon}{XYZ channel}{Local Guides channel}, and access to new 
products before they are generally released.
%
%what
%the reports would be under the strategic behaviors. We view this as a
%first validation that the CAH mechanism is effective, and leave this
%``closed-loop'' analysis to future work.
%
%

%We estimate 
%pairwise signal distributions from
%data
%that represents user reports for
%Google Local Guides in the US between {\bf June 2015} and {\bf May 2016}.
%Each task 
%is an instance of a particular type of task,
%with 
A type of task is 
specified by a triple of the form:
%
\begin{align*}
\mathit{Region} \times \mathit{Business Type}
\times \mathit{Question}
\end{align*}

A region is a US state, there are four business types such as
``restaurant,'' ``bar,'' ``public location'' or ``cafe'' (these are
anonymized in our data), and there are 143 distinct questions 
in the data.  The questions are also anonymized,
but
categorized by \iftoggle{anon}{XYZ}{Google} as ``subjective''
or ``factual'' (e.g., ``is this restaurant noisy?'' vs
``does this cafe have free WiFi?'').
%
%In the present context, a 
Each task type has a corresponding
pairwise signal distribution. 
%
%

The data are counts of pairs of signal reports, 
broken down by (region, business type, question).
%
%It is these pairwise signal
%distributions that we receive as our data.
The number of different questions (and thus types of tasks) per pair
of region and business type varies from 75 to 135, with an average of
102. There are 51 regions and 4 business types per state. Thus, the
total number of task types for which we have data is around 20,885.
 

 For the purpose of our simulations we treat the
distributions for these task types as describing the true signal
distributions.  The goal of the experiments is to compare, under this
assumption, the robustness of the CAH mechanism with other 
mechanisms in the literature.
%
% These
%estimates are used to define scores in 
%each mechanism.
%\dm{Galen seems okay to share the statistics but not the data.}
%
%dcp: edit out for space 
%
%
%The distributions vary by region, business type and question, and thus
%correspond in a meaningful way to different types of tasks.\footnote{Formally,
%the incentive properties of the CAH mechanism 
%would hold if the participants' prior beliefs on signal distributions
%do not vary across tasks within the same type of task.
%In fact, it is a limit of our current analysis that this is
%unlikely to hold for tasks at such a coarse definition of 
%a region and we plan to repair our analysis with 
%more granular task types in future work.}
%
%
%
%
\if 0


and we are interested in the statistics
on yes/no responses to each of these tasks.
The motivation for dividing the data into region and business type
is to control for the heterogeneity that users might be expected
to know about. For example, the distribution on
responses to  a question
such as  ``does this cafe have free wifi?'' might be expected
to be different in rural and urban locations, but users might
be expected to view all cafes in an urban location such as New York
City to be ex ante equivalent from this perspective.

%

%\dcp{also state the number of region, business type pairs}
%
%each city into a number of
%smaller regions and then further subdivide all the places within a
%given region into several business types. Examples of (region,
%business type) are (Brooklyn, bar) or (Upper East Side, Library).
%



%  
% is
%approximately same across all the places (cafes) under a given pair of
%(region, business type).
%
%
%We partition the world in such a way to ensure that the distribution
%of a particular task (e.g. does this cafe have free wifi?) is
%approximately same across all the places (cafes) under a given pair of
%(region, business type).
%
%Because of this,
% if user 1 visits place P1 in region R and
%business type B and answers questions $1,\ldots,m_1$ and another user
%2 visits a different place P2 in the same region and business type and answers
%questions $1,\ldots,m_2$, we can use peer prediction mechanism to
%score their responses.


%, and as such we view this as a
%      first analysis of these different mechanisms.
%
% \dcp{deb--- this
%really is a concern for RPTS and Kamble,  since their theoretical
%properties rely on this. note for future work}}
%
%
%From the past responses, we first estimate the joint probability
%distributions for a pair of signals for each question and each pair of
%region and business type. 
%

% (i.e., CAH uses $\text{sign}(\hat{\Delta}_k)$,
%Kamble uses $1/\sqrt{\hat{P}_k(i,i)}$ and {\bf RPTS}
%uses normalized $1/\hat{P}_k(i)$).
%
%
% Using this data, we compare three peer prediction mechanisms :
%1/Prior, Hom-OA and CAH.
%
%dcp: can drop this , I think. we do the obvious thing
%
%In the case of RPTS and Kamble, we compute
% scores on reports on each type of
%question for a given (region, business type) pair and then compute the average
%score for that particular pair. \dcp{deb/matt--- not quite clear: do we 
%simple compute the expected score for
%each type of task?}\dm{yes we compute score for each question separately
%and then take the average across all the questions.}
%

%We will present
%some analysis at the level of (region, business
%type) pairs.
%, averaging over the task types that correspond to each
%question associated with this (region, business type) pair.  
%
%
%In some cases, we aggregate scores by (region, business type)
%by averaging 
%scores over the questions associated with each such pair. 
\fi
%We compare three different peer prediction mechanisms
%on heterogeneous tasks: the CAH mechanism, and two non multi-task
%mechanisms, namely the
For this, we consider the {\em robust peer truth serum} (RPTS)
mechanism~\cite{radanovic2016incentives} (which sets a score of
$1/P(i)$ for agreement on signal $i$ and $1$ otherwise)\footnote{This
  is equivalent to a scaled version of the rule given by Radanovic et
  al.~\shortcite{radanovic2016incentives}, who prescribe a score of
  $\alpha(1/P(i) - 1)$ for agreement on signal $i$ and $0$ otherwise.
  Thus, our version has equivalent incentive properties in
  expectation.} and the {\em Kamble}~\shortcite{kamble2015truth}
mechanism (which sets a score of $1/\sqrt{P(i,i)}$ for agreement on
signal $i$).

In simulating CAH, we first compute the delta matrices for each task
type using~\Cref{eq:defn-delta}.  For this, we assume for a given
(region, business type, question) that the penalty tasks are sampled
from other questions associated with the
same  (region, business type).
From these delta matrices, we then use~\Cref{eq:dcp1} to compute the
expected score for each question, before averaging these scores over
all questions associated with a (region, business type)
pair. %We take a similar
%approach for computing the average
%expected score for a (region, business type) under
\if 0
%\dcp{deb-- did I get this right?}
%
\if 0

\dcp{deb/matt---- need more specificity on how we
	estimate the payments in CAH. in fact, for CAH it's not clear yet
	where the delta matrix comes from and how it is computed. Is it for
	a particular triple of (bonus, penalty, penalty) for example? or, is
	it for a bonus task with penalties sampled at random from other
	tasks? if so, how do we handle the problem that different subsets of
	questions may be answered by different users?  do we ignore this and
	is it as if we assume that all questions that correspond to a given
	(region, business) are answered by all users?}  \dm{yes, we do
	assume that a user answers all questions for a region and business
	pair and use~\Cref{CA-score} to compute the average score. We do the
	same for computing the average score under RPTS and Kamble. We could
	have computed the average in~\Cref{CA-score} over specific subsets
	if we had some additional user level data. However, I do think if
	the users answer a large fraction of questions for a region and
	business type, our approximation will be close to the actual average
	score (probably due to some form of law of large numbers)}
\fi
%




%\subsection{Google Local Guides data}

%We look at a dataset from Google Local Guides which is a platform for different users to share their discoveries on Google Maps. In this platform,
%a user might review a restaurant by answering 'yes', 'no' or 'not sure' to a series of questions. 
\fi 
%
For the single task, RPTS and Kamble mechanisms, we compute
the score for a (region, business type) by averaging the
individual scores recevied on each question associated with the
(region, business type) pair. Finally, since the payments of CAH are
bounded between $0$ and $1$, we normalize the payments of RPTS and
Kamble to $[0,1]$.\footnote{%\dcp{need to explain that we do static
%normalization.} 
For two signals $0$ and $1$, with
  estimated probabilities $\hat{P}(0) > \hat{P}(1)$, RPTS pays more on
  signal $1$ than $0$. Because of this, we set the payment to $1$ for
  agreement on signal $1$, and divide all payments through by the
  unnormalized payment for agreement on signal $1$ (i.e.,
  $1/\hat{P}(1)$.) The rewards of Kamble are normalized analogously. Our 
normalization scheme is static i.e. the normalization constants are not 
recomputed when the probabilities are estimated based on some possible misreports of the agents.}
Along with CAH, we also evaluate CAHR, the empirical version of the CAH mechanism. CAH has access
to the true delta matrices, whereas, CAHR computes the delta matrices based on the reports of the agents
and then uses these delta matrices to score reports.
%\dcp{need to also mention that we do both CAH and empirical CAH, 
%and explain briefly what we mean by the difference.}

\subsection{Unilateral Incentives for Truthful Reports}

We consider three kinds of strategic behaviors: {\em constant-0}
(report `yes' all the time), {\em constant-1} (report `no' all the
time) and {\em random} (report `yes' w.p. 0.5). 
%\dcp{matt-- did I get this right?}
%

We first consider unilateral incentives to make truthful reports, for
various assumptions about how the behavior of the rest of the
population. 
As an illustration,  Figure~\ref{fig:1} shows the expected benefit to being
truthful vs following some other behavior, considering the
average score for each (region, business type). We consider, in
particular, the benefit to being truthful vs the alternate
behavior 
%from being
%truthful vs adopting some other behavior for three different
%assumptions about the rest of the population: we vary the fraction $p$
%of the population that are truthful, with the remaining $1-p$ fraction
%using the same strategic behavior as the agent.  For example, the
%
when $p=0.8$ of the population is truthful and the rest follow
the same, alternate strategy. 
%
%$p=0.8$ histograms show the distribution of the advantage of truthful
%behavior relative to each possible strategic behavior, when fraction
%$0.8$ follows truthful strategy and the remaining $0.2$ fraction
%follows the same strategic behavior.
%
%
This models 20\% of the agents being able to coordinate on a deviation
from truthful play.  
%In addition to RPTS, Kamble and CAH, the plots in
%Figure~\ref{fig:1} also include the mechanism CAHR which is the
%empirical version of CAH. To be precise, 
\footnote{For CAHR, we first recompute the joint probabilities when
  $p$ fraction of the population is truthful and $1-p$ fraction adopts
  some other strategy, and then compute the delta matrices with
  respect to the new joint probability distributions. On the other
  hand, CAH uses the delta matrices computed using the original joint
  probability distributions.}

\begin{figure*}[t!]
	\minipage{0.245\textwidth}
	\includegraphics[width=\linewidth]{RPTS08-Histogram}
	\label{fig:etp-rpts}
	\endminipage\hfill
	\minipage{0.245\textwidth}
	\includegraphics[width=\linewidth]{Kamble08-Histogram}
	\label{fig:etp-kamble}
	\endminipage\hfill
	\minipage{0.245\textwidth}%
	\includegraphics[width=\linewidth]{CAHR08-Histogram}
	\label{fig:etp-cah}
	\endminipage\hfill
	\minipage{0.245\textwidth}
	\includegraphics[width=\linewidth]{CAH08-Histogram}
	\label{fig:etp-cahr}
	\endminipage\hfill
	\caption{Histograms for the 204
		(region, business type) pairs of
		expected benefit
		(averaged across questions) from truthful behavior
		vs.  some other strategy, when fraction $0.8$
		is truthful and fraction $0.2$ adopt the same,
		non-truthful
		strategy.  \label{fig:1}}
\end{figure*}

We observe that the support of the distribution for the CAH and CAHR
mechanism is positive, and thus it retains an incentive for truthful
behavior. We found this to be a common property for different values
of $p$, i.e. CAH and CAHR retains good unilateral incentives for all
values of $p$, even when all agents play the same way. 
By contrast, both the RPTS and Kamble fail under some strategy, i.e.  there exists
a strategy ({\em random} for Kamble and either {\em random} or {\em
  constant-1} for RPTS) such that playing that strategy is more
beneficial than playing truthful strategy when some fraction plays
this alternate strategy.  Although figure~\ref{fig:1} shows this for
$p = 0.8$, this is representative of other values of $p$. The plots
for several other values of $p$ are included in Appendix \ref{app:uni-plots}.

When the prior probability satisfies the {\em self-predicting}
condition, the RPTS mechanism has truth-telling as a strict
equilibrium %\dcp{not sure this next bit is right?} 
and the truthful
equilibrium provides at least as high payoff than any other coordinated
equilibrium where all agents report the same. Since, incentive properties
are not proven under RPTS except when the self-predicting condition is
satisfied, we evaluated the RPTS
mechanism by restricting only to questions that satisfy the
self-predicting condition. However, the corresponding plot is similar
to the plot shown in figure~\ref{fig:1}.  To conclude, compared to single task mechanisms
like RPTS and Kamble, CAH mechanisms provide good guarantees against
unilateral deviation.
 
\if 0
All three mechanisms
are incentive aligned for $p=1$, i.e. when all other agents
are truthful.  

As more of the population is truthful, the truthful behavior becomes
increasingly beneficial.  In particular, looking at the plots for
$p=1$ we see all three mechanisms provide positive incentives for
truthful vs strategic behavior.  However, when $p$ is $0$ or $0.5$ and
other agents are also strategic, the CAH mechanism retains an
incentive for truthful behavior while const-0 and const-1 strategies
become beneficial for agents in the RPTS and Kamble mechanisms. This
analysis shows that truthful reporting is a best response for an agent
on average, over all questions associated with a (region, business
type) pair, irrespective of the behavior of the rest of the
population. For the particular case of $p=0$, when the other agents
all follow some non-truthful strategy, the average score in the CAH
mechanism is zero irrespective of the behavior of an agent.
%
% in every region,
%business type combination is non-negative. In other words, there is no
%individual incentive not to be truthful in this population.%
%
\fi 
%



\subsection{Benefit from Coordinated Misreports}

Irrespective of whether or not a coordinated deviation is robust
against agents choosing to make truthful reports instead, we also
consider the expected payoff available to a group of agents who manage
to coordinate on some non-truthful play. 
%
Figure~\ref{fig:2} plots the average and standard error for the expected payments
associated with the 204 (region, business type) pairs. 
For each strategy and for a particular value of $p$, we plot the 
expected payment and the standard error across the 204 pairs, when $p$ fraction of 
population is truthful and the remaining $1-p$ fraction of the
population adopts the same strategy. The constant line shows the average expected payment
 across all the pairs when everyone is truthful. 
%\dcp{hopefully the conclusion is that CAH is robust in a way that
%the other mechanisms are not!}
 \begin{figure*}[!h]
 	\minipage{0.245\textwidth}
 	\includegraphics[width=0.9\linewidth]{./rpts-true-vs-random}
 	\label{fig:etp_ca}
 	\endminipage\hfill
 	\minipage{0.245\textwidth}
 	\includegraphics[width=0.9\linewidth]{./Kamble-true-vs-random}
 	\label{fig:etp-kamble}
 	\endminipage\hfill
 	\minipage{0.245\textwidth}%
 	\includegraphics[width=0.9\linewidth]{./cah-w-true}
 	\label{fig:etp-cah}
 	\endminipage\hfill
	\minipage{0.245\textwidth}%
	\includegraphics[width=0.9\linewidth]{./cahr-collusion-new}
	\label{fig:etp-cahr}
	\endminipage\hfill
 	\caption{Expected score for following each of four
 		strategies, when
 		$p$ fraction of the population is truthful and  $1-p$ fraction 
 		adopt the same strategy. Averaged over
 		questions associated with a typical (region, business type)
 		pair. \label{fig:2}} 
 \end{figure*}
CAH mechanism has the expected payments from all truthful strategy higher
than the other three possible strategies (const-0, const-1 and random) for all possible
values of $p$. This means that CAH mechanism is robust against coordinated misreport by
any fraction of the population. For RPTS and Kamble, we only plot the expected payments
due to the all truthful strategy and the random strategy for various values for $p$. We
omit the plots for the
expected payments for const-0 and const-1 strategies since the payments under these strategies
are significantly lower than the all truthful
strategy under both RPTS and Kamble mechanism and do not provide profitable coordinated 
misreports. We now see that for intermediate values of $p$, the random strategy provide
a profitable coordinated misreporting profile under both the RPTS and Kamble mechanism.
Therefore, unlike CAH, single task mechanisms like RPTS, Kamble are not always robust
to coordinated deviations.
%

\subsection{Subjective vs Factual Tasks}

%\dcp{ok to drop this section if you need space and just mention in future work}
Figure~\ref{fig:3} shows the cumulative
distribution on expected scores at
truthful reporting in each mechanism, where each data point
corresponds to a different (region, business type, question) triple.
Two lines are shown for each mechanism: one corresponding to 
questions that are categorized as `factual' and one
corresponding to questions that are categorized as `subjective.'
%
\begin{figure*}[t!]
	\minipage{0.33\textwidth}
	\includegraphics[width=0.9\linewidth]{{Expected_CAH_Payment_Given_Truthfulness_2}}
	\label{fig:etp_ca}
	\endminipage\hfill
	\minipage{0.33\textwidth}
	\includegraphics[width=0.9\linewidth]{{Expected_Kamble_Payment_Given_Truthfulness_2}}
	\label{fig:etp-kamble}
	\endminipage\hfill
	\minipage{0.33\textwidth}%
	\includegraphics[width=0.9\linewidth]{{Expected_RPTS_Payment_Given_Truthfulness_2}}
	\label{fig:etp-rpts}
	\endminipage
	\caption{\label{fig:3} 
		Cumulative distribution on expected payments at truthful reporting
		in each mechanism, with  results separated into questions that are
		categorized as `factual' and those that are categorized as `subjective.'}
\end{figure*}
The subjective
questions tend to provide lower expected payment than the factual
questions under the CAH mechanism. 
%\dcp{this says `higher' shouldn't it be `lower'?} 
%
This is consistent with the intuition
that people perceive subjective questions differently than factual
questions.
%
For the Kamble and RPTS mechanisms, the variability in 
expected payment is larger across factual questions than 
subjective questions, with the expected payment
for subjective questions tending to fall in a
narrow band.
%as a result of the probability
%distributions become more extreme (and thus affecting the ``1/probability''
%nature of these payment schemes.) \dcp{does this sound like a reasonable
%hypothesis?}

% and CAH mechanism seems to provide a strong distinction
%between them.   
%



\section{Conclusions}

We study the peer prediction problem when users complete heterogeneous
tasks.  We introduced the CAH mechanism, which is informed-truthful
under mild conditions and can also be used together with estimating
statistics from reports for the purpose of computing scores.  
The simulation results suggest that CAH provides better incentive for
being truthful and is more resistant to coordinated misreports than
the RPTS and Kamble mechanisms. We also noted that CAHR, the empirical version
of CAH has similar incentive guarantees, in contrast to the empirical versions
of the single-task peer prediction mechanisms.
%In future work we should also compare
%the mechanisms when we re-estimate statistics under misreports.
%
%\dcp{drop mention of this if we don't use, and be sure to add
%comments on CAHR!} 
%We design the CCAH mechanism when the reports from users across tasks may not be independent.
%
% (e.g.,
%responses to questions about the same place in the context of
%Google Local Guides.)
% We have an extension of the CAH mechanism to
%handle this, and in future work plan to develop a detail-free version
%of this generalization.
%
% provide a detail-free version of
%CCAH, in particular we would like to understand whether correlations
%among different tasks can be leveraged to improve the sample
%complexity. 
%
%\dcp{we've done the following now! maybe instead speculate that this mechanism is ready for practical evaluation as a next step?} 
We believe that the theoretical guarantees of the multi-task mechanisms and their attractive incentive properties suggest that
such mechanisms are ready to be applied and evaluated in practice, from peer grading to rating.
The most important directions for future work  are to
design mechanisms that can 
handle agent heterogeneity (agents that
vary by taste, judgment, noise, etc.) as
well as task heterogeneity. We are also interested in developing
specific versions of the CAH mechanism for particular models
of heterogeneity, such as the generalized Dawid-Skene scheme~\cite{dawid1979maximum}.
\if 0
\section*{Acknowledgments}

This work is supported in part by Google, the SEAS TomKat fund, and
NSF grant CCF-1301976. Leifer's work was supported by a Harvard
College PRISE fellowship.
\fi


\newpage



\bibliographystyle{named}
\bibliography{references}


%\newpage 

\onecolumn

\section{Appendix}
\subsection{Proof of Lemma \ref{lem:delta-zero}}
\label{app:defn-zero}
\begin{align*}
&\sum_{i}\sum_{j} \Delta_b(i,j) = \sum_i \sum_j \left\{P_b(i,j) \right. \\ &-\left.\frac{1}{(m-1)(m-2)} \sum_{l' \in [m] \setminus \set{b}} 
\sum_{l'' \in [m] \setminus \set{b,l'}} P_{l'}(i) P_{l''}(j) \right\} \\
&= \sum_i \left\{ P_b(i) - \frac{1}{(m-1)(m-2)} \sum_{l' \in [m] \setminus \set{b}} 
\sum_{l'' \in [m] \setminus \set{b,l'}} P_{l'}(i)   \right\}\\& = 1-1= 0
\end{align*}

\subsection{Proof of Theorem \ref{thm:strong-cah}}
\label{app:strong-cah}
Suppose both the agents adopt the truthful strategy, which corresponds to the identity matrix $\eye$. Then the expected payment is given as 
\begin{align}
E(\eye,\eye) = \sum_{b=1}^m  \sum_{i,j : \ \Delta_b(i,j) > 0} \Delta_b(i,j)
\end{align}

On the other hand for any two arbitrary deterministic strategies $F$ and $G$, 
\begin{align}
E(F,G) = \sum_{b=1}^m  \sum_{i,j} \Delta_b(i,j) S_b(F_i, G_j) \leq \sum_{b=1}^m  \sum_{i,j : \ \Delta_b(i,j) > 0} \Delta_b(i,j) = E(\eye,\eye)
\end{align}

To show strong truthfulness, consider an asymmetric joint strategy $F \neq G$. Then there exists $i$ such that $F_i \neq G_i$.
This reduces the expected payment by at least 
\begin{align}
\sum_{b=1}^m \Delta_b(i,i) S_b(F_i,G_i)
\end{align}

Since $F_i \neq G_i$, we have $\sum_{b=1}^m \Delta_b(F_i,G_i) < 0$ and there exists $l'$ such that $\Delta_{l'}(F_i,G_i) < 0$ (or $S_{l'}(F_i,G_i) = 0$). Therefore, the expected payment reduces by at least $\Delta_{l'}(i,i) > 0$.

Now consider symmetric, non-permutation strategy $F = G$. Then there exist $i \neq j$ such that $F_i = G_j = k$ and the expected payment includes 
\begin{align}
\sum_{b=1}^m \Delta_b(i,j) S_b(k,k) = \sum_{b=1}^m  \Delta_b(i,j)  < 0
\end{align}

The first equality uses the fact $S_b(k,k) = 1$ since $\Delta_b(k,k) > 0$ for each $b$.
\if 0
\subsection{Proof of Theorem \ref{thm:cat-cond1-cah}}
\label{app:cat-cond1-cah}
Suppose there three tasks 
($b, l'$ and $l''$) with two
signals ($Y$ and $N$) for each task. Matrix $\Delta_b$ is:
\if 0
\begin{align*}
\begin{array}{c|c|c|}
& Y & N\\ \hline
Y & P_b(Y,Y) - P_{l'}(Y)P_{l''}(Y)  & P_b(Y,N) - \frac{1}{2} (P_{l'}(Y)P_{l''}(N) + P_{l''}(Y)P_{l'}(N))  \\ \hline
N & P_b(N,Y) - \frac{1}{2} (P_{l'}(N)P_{l''}(Y) + P_{l''}(N)P_{l'}(Y)) & P_b(N,N) - P_{l'}(N) P_{l''}(N) \\ \hline 
\end{array}
\end{align*}
\fi 
Since the agents are exchangeable, $P_b$ and $\Delta_b$ are symmetric. 
Moreover, Lemma~\ref{lem:delta-zero} 
proves that the sum of all the entries of $\Delta_b$ is zero. 
This implies that $\Delta_b(Y,Y) + \Delta_b(N,N) = - 2\Delta_b(Y,N)$ and $\Delta_b(Y,Y) > 0$ and 
$\Delta_b(N,N) > 0 \ \Rightarrow \ \Delta_b(Y,N) < 0$. Therefore, $\Delta_b$ is categorical for all $b$ iff 
$\{\Delta_b\}_{b=1}^m$ satisfy Condition 1. 
\fi 

\subsection{Proof of Theorem \ref{thm:detail-free-cah}}
\label{app:detail-free-cah}
We will write $\E{T,F,G}$ to denote the average expected score under strategies $F$ and $G$ when using the score matrix $T = \{T_b\}_{b=1}^m$. 
Suppose $S = \{S_b\}_{b=1}^m$ is the true scoring matrix and $\hat{S}=\{\hat{S}_b\}_{b=1}^m$ is the scoring matrix estimated from the data. Then
\begin{align}
\E{\hat{S},F,G} = \frac{1}{m}\sum_{b=1}^m \sum_{i,j} \Delta_b(i,j) \hat{S}_b(F_i,G_j) \leq \frac{1}{m} \sum_{b=1}^m \sum_{i,j : \Delta_b(i,j) > 0} \Delta_b(i,j) = \E{S,\eye,\eye}
\end{align}

Therefore, in order to show  $\E{\hat{S}, \eye, \eye} \geq \E{\hat{S},F,G} - \varepsilon$ it is enough to show that $\E{\hat{S}, \eye, \eye} \geq \E{{S},\eye,\eye} - \varepsilon$. Now
\begin{align}
&\abs{\frac{1}{m}\E{\hat{S},\eye,\eye} - \frac{1}{m}\E{S,\eye,\eye}} \nonumber \\
&= \abs{\frac{1}{m}\sum_{b=1}^m \sum_{i,j} \Delta_b(i,j) \left( \hat{S}_b(i,j) - S_b(i,j)\right)} 
= \abs{\frac{1}{m}\sum_{b=1}^m \sum_{i,j} \Delta_b(i,j) \left( \text{sign}\left(\hat{\Delta}_b(i,j)\right)  - \text{sign}\left( \Delta_b(i,j)\right)\right)} \nonumber \\
&\leq \frac{1}{m} \sum_{b=1}^m \sum_{i,j} \abs{\Delta_b(i,j) \left( \text{sign}\left(\hat{\Delta}_b(i,j)\right)  - \text{sign}\left( \Delta_b(i,j)\right)\right)} \leq \frac{1}{m} \sum_{b=1}^m \sum_{i,j} \abs{\hat{\Delta}_b(i,j) - \Delta_b(i,j)} \nonumber \\
&= \frac{1}{m} \sum_{b=1}^m \sum_{i,j} \abs{P_b(i,j) - T_b(i,j) - \frac{1}{(m-1)(m-2)} \sum_{\stackrel{t',t'' \in [m] \setminus \set{b}}{\& \ t' \neq t''}} \left( P_{t'}(i)P_{t''}(j) - T_{t'}(i)T_{t''}(j) \right) } \nonumber \\
& \leq \frac{1}{m} \sum_{b=1}^m \sum_{i,j} \abs{P_b(i,j) - T_b(i,j)} + \frac{1}{(m-1)(m-2)} \sum_{\stackrel{t',t'' \in [m] \setminus \set{b}}{\& \ t' \neq t''}} \abs{P_{t'}(i)P_{t''}(j) - T_{t'}(i)T_{t''}(j)} \nonumber \\
&= \frac{1}{m} \sum_{b=1}^m \sum_{i,j} \abs{P_b(i,j) - T_b(i,j)} +  \frac{1}{m(m-1)(m-2)} \sum_{b=1}^m \sum_{i,j} \sum_{\stackrel{t',t'' \in [m] \setminus \set{b}}{\& \ t' \neq t''}} \left|P_{t'}(i)\left( P_{t''}(j) - T_{t''}(j)\right)  \right. \nonumber \\
&+ \left. T_{t''}(j)\left( P_{t'}(i) - T_{t'}(i)\right) \right. \nonumber \\
&\leq \frac{1}{m}\sum_{b=1}^m \sum_{i,j} \abs{P_b(i,j) - T_b(i,j)} \\
&+ \frac{1}{m(m-1)(m-2)} \sum_{b=1}^m  \sum_{\stackrel{t',t'' \in [m] \setminus \set{b}}{\& \ t' \neq t''}} \left\{ \sum_j\abs{P_{t''}(j) - T_{t''}(j)}\sum_i P_{t'}(i) \right. 
+ \left.\sum_i \abs{P_{t'}(i) - T_{t'}(i)} \sum_j T_{t''}(j) \right\} \nonumber \\
&= \frac{1}{m}\sum_{b=1}^m \sum_{i,j} \abs{P_b(i,j) - T_b(i,j)}  \\
&+\frac{1}{m(m-1)(m-2)} \sum_{b=1}^m \sum_{\stackrel{t',t'' \in [m] \setminus \set{b}}{\& \ t' \neq t''}} \left\{ \sum_j\abs{P_{t''}(j) - T_{t''}(j)} 
+ \sum_i \abs{P_{t'}(i) - T_{t'}(i)}\right\}\label{eq:bound-partial}
\end{align}

Now if we have $\bigo{\frac{n^2}{\varepsilon^2}
	\log\left( \frac{m}{\delta}\right)}$ samples from
each joint distribution $P_b$ (where $n$ is the number
of signals) and $\bigo{\frac{n}{\varepsilon^2}
	\log\left( \frac{m}{\delta}\right)}$ from each
marginal distribution $P_b$, we can ensure that with
probability at least $1-\delta$, for all
$b=1,2,\ldots,m$ the following results hold (see
\cite{devroye2012combinatorial} for a proof)
\begin{equation}\label{eq:devroye}
\sum_{i,j} \abs{P_b(i,j) - T_b(i,j)} \leq \frac{\varepsilon}{3} \ \text{and}\ \sum_i \abs{P_b(i) - T_b(i)} \leq \frac{\varepsilon}{3}.
\end{equation}

Note: If we just had $O(n/\varepsilon^2 \log(1/\delta))$ samples for each
task, then we can guarantee~\eqref{eq:devroye}
for each task separately
with probability at least $1 - \delta$. By the union bound, this 
would give a success
probability of $1 - m \delta$ over all tasks. So in order to have
a $1 - \delta$
confidence bound, we need a $\log(m/\delta)$ factor in
the sample complexity.
% Essentially I am
%using Devroye and Lugosi result with \delta = \delta / m.
%
Substituting the bounds from \cref{eq:devroye} in \cref{eq:bound-partial} and simplifying gives us $\abs{\E{\hat{S},\eye,\eye} - \E{S,\eye,\eye}} \leq \varepsilon$. Since there are $q$ agents providing reviews for each task, we get $q^2$ samples from each joint distribution and $q$ samples 
from each marginal distribution. So as long as $q =\bigom{ \frac{n}{\varepsilon^2} \log \left( \frac{m}{\delta}\right)}$ we have enough number of
samples and we are done.

\if 0
\subsection{Proof of Theorem \ref{thm:detail-free-ccah}}
\label{app:detail-free-ccah}

We will write $\E{T,F,G}$ to denote the average expected score under strategies $F$ and $G$ when using the score matrix $T = \{T_b\}_{b=1}^m$. 
Suppose $S = \{S_b\}_{b=1}^m$ is the true scoring matrix and $\hat{S}=\{\hat{S}_b\}_{b=1}^m$ is the scoring matrix estimated from the data. Then
\begin{align}
\E{\hat{S},F,G} = \frac{1}{m}\sum_{b=1}^m \sum_{i,j} \Delta_b(i,j) \hat{S}_b(F_i,G_j) \leq \frac{1}{m} \sum_{b=1}^m \sum_{i,j : \Delta_b(i,j) > 0} \Delta_b(i,j) = \E{S,\eye,\eye}
\end{align}

Therefore, in order to show  $\E{\hat{S}, \eye, \eye} \geq \E{\hat{S},F,G} - \varepsilon$ it is enough to show that $\E{\hat{S}, \eye, \eye} \geq \E{{S},\eye,\eye} - \varepsilon$. Now
\begin{align}
&\abs{\frac{1}{m}\E{\hat{S},\eye,\eye} - \frac{1}{m}\E{S,\eye,\eye}} \nonumber \\
&= \abs{\frac{1}{m}\sum_{b=1}^m \sum_{i,j} \Delta_b(i,j) \left( \hat{S}_b(i,j) - S_b(i,j)\right)} 
= \abs{\frac{1}{m}\sum_{b=1}^m \sum_{i,j} \Delta_b(i,j) \left( \text{sign}\left(\hat{\Delta}_b(i,j)\right)  - \text{sign}\left( \Delta_b(i,j)\right)\right)} \nonumber \\
&\leq \frac{1}{m} \sum_{b=1}^m \sum_{i,j} \abs{\Delta_b(i,j) \left( \text{sign}\left(\hat{\Delta}_b(i,j)\right)  - \text{sign}\left( \Delta_b(i,j)\right)\right)} \leq \frac{1}{m} \sum_{b=1}^m \sum_{i,j} \abs{\hat{\Delta}_b(i,j) - \Delta_b(i,j)} \nonumber \\
&= \frac{1}{m} \sum_{b=1}^m \sum_{i,j} \abs{P_b(i,j) - T_b(i,j) - \frac{1}{(m-1)(m-2)} \sum_{\stackrel{t',t'' \in [m] \setminus \set{b}}{\& \ t' \neq t''}} \left( P_{t',t''}(i,j) - T_{t',t''}(i,j) \right) } \nonumber \\
& \leq \frac{1}{m} \sum_{b=1}^m \sum_{i,j} \abs{P_b(i,j) - T_b(i,j)} + \frac{1}{(m-1)(m-2)} \sum_{\stackrel{t',t'' \in [m] \setminus \set{b}}{\& \ t' \neq t''}} \abs{P_{t',t''}(i,j) - T_{t',t''}(i,j)} \label{eq:bound-partial1} \\
\end{align}

Now if we have $\bigo{\frac{n^2}{\varepsilon^2}
	\log\left( \frac{m^2}{\delta}\right)}$ samples from
each joint distribution $P_b$ (where $n$ is the number
of signals) and from each pairwise distribution $P_{t',t''}$, we can ensure that with
probability at least $1-\delta$, for all
$b=1,2,\ldots,m$ and $t' \neq t''$, the following results hold (see
\cite{devroye2012combinatorial} for a proof)
\begin{equation}\label{eq:devroye1}
\sum_{i,j} \abs{P_b(i,j) - T_b(i,j)} \leq \frac{\varepsilon}{2} \ \text{and}\ \sum_{i,j} \abs{P_{t',t''}(i,j) - T_{t',t''}(i,j)} \leq \frac{\varepsilon}{2}.
\end{equation}
Note: If we just had $O(n^2/\varepsilon^2 \log(1/\delta))$ samples from each
task $b$ (or each pairwise distribution), then we can guarantee~\eqref{eq:devroye1}
for each task $b$ (or each pairwise distribution) separately
with probability at least $1 - \delta$. Since there are $m$ tasks in total and $m^2 - m$ 
pairwise distributions $P_{t',t''}(\cdot,\cdot)$, this 
gives a success
probability of $1 - m^2 \delta$ by the union bound. So in order to have
a $1 - \delta$
confidence bound, we need a $\log(m^2/\delta)$ factor in
the sample complexity bound.
% Essentially I am
%using Devroye and Lugosi result with \delta = \delta / m.
%
Substituting the bounds from \cref{eq:devroye1} in \cref{eq:bound-partial1} and simplifying gives us $\abs{\E{\hat{S},\eye,\eye} - \E{S,\eye,\eye}} \leq \varepsilon$. Since there are $q$ agents providing reviews for each task, we get $q^2$ samples from each joint distribution and $q^2$ samples 
from each pairwise distribution. So as long as $q =\bigom{ \frac{n}{\varepsilon^2} \log \left( \frac{m}{\delta}\right)}$ we have enough number of
samples and we are done.
\fi 

\if 0
\subsection{Proof of Theorem \ref{thm:asymmetric}}
\label{app:uniformization}
Let $K$ be the random variable corresponding to the bonus task which is selected uniformly at random from the set of $m$ tasks. Once we have chosen
$K$ let $K',K''$ be the pair of penalty tasks selected uniformly at random from the set of tasks $[m] \setminus \set{K}$ such that $K' \neq K''$ (we
are abusing notation since ideally we should write $K'(K)$ and $K''(K)$). We will write $\sD_K$ to denote the distribution of the pair of penalty tasks $(K',K'')$
for the given bonus task $K$. The expected score under CAH is


\begin{align*}
&\Em{K}{ \sum_{r_1,r_2} \Pro{R^K_1 = r_1, R^K_2 = r_2} S_K(r_1,r_2) - \Em{(K',K'') \sim \sD_K}{\sum_{r_1,r_2} \Pro{R^{K'}_1 = r_1, R^{K''}_2 = r_2} S_K(r_1,r_2)} } \\
&= \frac{1}{m} \sum_{k=1}^m \sum_{r_1,r_2} \Pro{R^k_1 = r_1, R^k_2 = r_2} S_k(r_1,r_2)  - \sum_{r_1,r_2} \Em{K}{\Em{(K',K'') \sim \sD_K}{\Pro{R^{K'}_1 = r_1, R^{K''}_2 = r_2}} S_K(r_1,r_2)}
\end{align*}
Here $R^K_1$ (resp. $R^K_2$) refers respectively to the signal reported by agent $1$ (resp. $2$) on task $K$. Now,
consider the symmetric strategy \[\bar{F}_{ir_1} = \sum_{k=1}^m \frac{P_k(i)}{\sum_{k'} P_{k'}(i)} F^k_{ir_1}\] 
The proof proceeds by showing that adopting  this uniform strategy instead of a non-uniform strategy 
gives a loss which asymptotically goes to zero with the number of tasks. First, we consider the loss in utility due to the reward obtained
from the penalty tasks.
%
%\begin{lemma}
%	\[
%	\abs{ \sum_{r_1,r_2} \Em{K}{\Em{(K',K'') \sim \sD_K}{\Pro{R^{K'}_1 = r_1, R^{K''}_2 = r_2 | F,G}}  - \Pro{R^{K'}_1 = r_1, R^{K''}_2 = r_2 | \bar{F}, G} S_K(r_1,r_2)}} = \bigo{\frac{n^2}{m}}
%	\]
%\end{lemma}
%\begin{proof}
	Fix a bonus task $K$.
	\begin{align}
	&\Em{(K',K'') \sim \sD_K}{\Pro{R^{K'}_1 = r_1, R^{K''}_2 = r_2 | F,G}} = \frac{1}{(m-1)(m-2)} \sum_{(k',k'')}\Pro{R^{k'}_1 = r_1, R^{k''}_2 = r_2 | F,G} \\
	&= \frac{1}{(m-1)(m-2)} \sum_{(k',k'')} \sum_{ij} P_{k'}(i)P_{k''}(j) F^{k'}_{ir_1} G^{k''}_{jr_2} \\
	&= \frac{1}{(m-1)(m-2)} \left\{  \sum_{k' \neq k} \sum_{k'' \neq k} \sum_{ij} P_{k'}(i)P_{k''}(j) F^{k'}_{ir_1} G^{k''}_{jr_2} -  \sum_{k' \neq k}\sum_{ij}P_{k'}(i) P_{k'}(j) F^{k'}_{ir_1} G^{k'}_{jr_2} \right\} \\
	&= \frac{1}{(m-1)(m-2)} \left\{ \sum_{k'} \sum_{k''} \sum_{ij} P_{k'}(i)P_{k''}(j) F^{k'}_{ir_1} G^{k''}_{jr_2} - \sum_{k' \neq k}\sum_{ij} P_{k'}(i) P_{k'}(j) F^{k'}_{ir_1} G^{k'}_{jr_2}\right.\\
	& \left. - \sum_{k'' \neq k} \sum_{ij} P_{k}(i) P_{k''}(j)F^{k}_{ir_1}G^{k''}_{jr_2} - \sum_{k' \neq k} \sum_{ij} P_{k'}(i) P_{k}(j)F^{k'}_{ir_1}G^{k}_{jr_2} - \sum_{ij} P_k(i)P_k(j)F^k_{ir_1}G^k_{jr_2} \right\}
	\end{align}
	\begin{align}
	&\abs{ \Em{(K',K'') \sim \sD_K}{\Pro{R^{K'}_1 = r_1, R^{K''}_2 = r_2 | F,G} - \Pro{R^{K'}_1 = r_1, R^{K''}_2 = r_2 | \bar{F},G}} }\\
	&= \left \lvert \frac{1}{(m-1)(m-2)} \left\{ \sum_{k'} \sum_{k''} \sum_{ij} P_{k'}(i)P_{k''}(j) (F^{k'}_{ir_1} - \bar{F}_{ir_1}) G^{k''}_{jr_2} - \sum_{k' \neq k} \sum_{ij} P_{k'}(i) P_{k'}(j) (F^{k'}_{ir_1} - \bar{F}_{ir_1}) G^{k'}_{jr_2}\right. \right. \\
	& \left. \left. - \sum_{k'' \neq k} \sum_{ij} P_{k}(i) P_{k''}(j)(F^{k}_{ir_1} - \bar{F}_{ir_1}) G^{k''}_{jr_2} - \sum_{k' \neq k} \sum_{ij} P_{k'}(i) P_{k}(j) (F^{k'}_{ir_1} - \bar{F}_{ir_1}) G^{k}_{jr_2} - \sum_{ij} P_k(i)P_k(j)(F^k_{ir_1} - \bar{F}_{ir_1}) G^k_{jr_2} \right\} \right \rvert \\
	&= \frac{1}{(m-1)(m-2)}\left\lvert \sum_{k'} \sum_{k''} \sum_{ij} P_{k'}(i)P_{k''}(j) (F^{k'}_{ir_1} - \bar{F}_{ir_1}) G^{k''}_{jr_2} \right \rvert + \bigo{\frac{1}{m}} \\
	&= \frac{1}{(m-1)(m-2)} \left \lvert \sum_{k''} \sum_j P^{k''}(j) G^{k''}_{jr_2} \sum_{i} \sum_{k'} P_{k'}(i) (F^{k'}_{ir_1} - \bar{F}_{ir_1})\right  \rvert + \bigo{\frac{1}{m}} \\
	&= \bigo{\frac{1}{m}}
	\end{align} 
	The last line follows since $\sum_k P_k(i) F^k_{ir_1} = \sum_k P_k(i) \bar{F}_{ir_1}$. This proves that the loss in utility from the penalty tasks 
	from adopting a symmetric strategy is $\bigo{n^2/m}$ since (1) $S_K(r_1,r_2) \in \set{0,1}$ and (2) the outer sum is over all pairs of signals $r_1$,$r_2$ and there are $n^2$ of them. 
%\end{proof}
Now we consider the loss in utility due to the reward from the bonus tasks.
\begin{align*}
\text{Let }&T_1(F,G) = \frac{1}{m} \sum_{k=1}^m \sum_{r_1,r_2} \Pro{R^k_1 = r_1, R^k_2 = r_2} S_k(r_1,r_2) = \frac{1}{m} \sum_{k=1}^m \sum_{r_1,r_2} \sum_{ij} P_k(i,j) F^k_{ir_1} G^k_{jr_2} S_k(r_1,r_2)\\
\end{align*}
Therefore, the loss in utility from the reward from the bonus tasks is 
\begin{align*}
&\abs{T_1(F,G) - T_1(\bar{F},G)} = \frac{1}{m} \abs{\sum_{k=1}^m \sum_{r_1,r_2} \left\{ \Pro{R^k_1 = r_1, R^k_2 = r_2 | F,G} - \Pro{R_1^k = r_1, R_2^k = r_2 | \bar{F},G}\right\} S_k(r_1,r_2)} \\
&\leq \frac{1}{m} \sum_{k=1}^m \sum_{r_1,r_2} \abs{\Pro{R^k_1 = r_1, R^k_2 = r_2 | F,G} - \Pro{R_1^k = r_1, R_2^k = r_2 | \bar{F},G}} \abs{S_k(r_1,r_2)}\\
%	&\leq \frac{1}{m} \left\{ \sum_{k=1}^m \sum_{r_1,r_2} \left\{ \Pro{R^k_1 = r_1, R^k_2 = r_2 | F,G} - \Pro{R_1^k = r_1, R_2^k = r_2 | \bar{F},G}\right\}^2 \right\}^{1/2} \left\{ \sum_{k=1}^m \sum_{r_1,r_2} S_k^2(r_1,r_2) \right\}^{1/2}
&\leq \frac{1}{m} \sum_{k=1}^m \sum_{r_1,r_2} \abs{\Pro{R^k_1 = r_1, R^k_2 = r_2 | F,G} - \Pro{R_1^k = r_1, R_2^k = r_2 | \bar{F},G}} \\
&= \frac{1}{m} \sum_{k=1}^m \sum_{r_1,r_2} \abs{\sum_{ij} P_k(i,j) F^k_{ir_1} G^k_{jr_2} - \sum_{ij} P_k(i,j) \bar{F}_{ir_1} G^k_{jr_2}} \\
&= \frac{1}{m} \sum_{k=1}^m \sum_{r_1,r_2} \sum_j \abs{G^k_{jr_2} \sum_i P_k(i,j) \left( F^k_{ir_1} - \bar{F}_{ir_1}\right) } \\
&= \frac{1}{m} \sum_{k=1}^m \sum_{r_1,r_2} \sum_j \abs{G^k_{jr_2} \sum_i P_k(i,j) \left( F^k_{ir_1} - \sum_{k'=1}^m \frac{P_{k'}(i)}{\sum_{k''}P_{k''}(i)} F^{k'}_{ir_1}\right) } \\
&= \frac{1}{m} \sum_{k=1}^m \sum_{r_1,r_2} \sum_j \abs{G^k_{jr_2} \sum_i P_k(i,j)  \left( \frac{\sum_{k'}P_{k'}(i) (F^k_{ir_1} - F^{k'}_{ir_1})}{\sum_{k''}P_{k''}(i)} \right) }\\
&\leq \frac{1}{m} \sum_{k=1}^m \sum_{r_1,r_2} \sum_j G^k_{jr_2} \sum_i P_k(i,j) \frac{\sum_{k'}P_{k'}(i) (\abs{F^k_{ir_1} } + \abs{ F^{k'}_{ir_1}  })}{\sum_{k''}P_{k''}(i)} \\
&\leq \frac{2}{m} \sum_{k=1}^m \sum_{r_1,r_2} \sum_{i,j} P_k(i,j) = \frac{2n^2}{m}
\end{align*}
\fi 
\subsection{Additional Plots}
\label{app:uni-plots}
\begin{figure*}[t!]
	\minipage{0.24\textwidth}
	\includegraphics[width=\linewidth]{RPTS01-Histogram}
	\endminipage\hfill
	\minipage{0.24\textwidth}
	\includegraphics[width=\linewidth]{Kamble01-Histogram}
	\endminipage\hfill
	\minipage{0.24\textwidth}%
	\includegraphics[width=\linewidth]{CAHR01-Histogram}
	\endminipage\hfill
	\minipage{0.24\textwidth}
	\includegraphics[width=\linewidth]{CAH01-Histogram}
	\endminipage\hfill
	\newline 
	\minipage{0.24\textwidth}
	\includegraphics[width=\linewidth]{RPTS05-Histogram}
	\endminipage\hfill
	\minipage{0.24\textwidth}
	\includegraphics[width=\linewidth]{Kamble05-Histogram}
	\endminipage\hfill
	\minipage{0.24\textwidth}%
	\includegraphics[width=\linewidth]{CAHR05-Histogram}
	\endminipage\hfill
	\minipage{0.24\textwidth}
	\includegraphics[width=\linewidth]{CAH05-Histogram}
	\endminipage\hfill
	\newline 
	\minipage{0.24\textwidth}
	\includegraphics[width=\linewidth]{RPTS07-Histogram}
	\endminipage\hfill
	\minipage{0.24\textwidth}
	\includegraphics[width=\linewidth]{Kamble07-Histogram}
	\endminipage\hfill
	\minipage{0.24\textwidth}%
	\includegraphics[width=\linewidth]{CAHR07-Histogram}
	\endminipage\hfill
	\minipage{0.24\textwidth}
	\includegraphics[width=\linewidth]{CAH07-Histogram}
	\endminipage\hfill
	\minipage{0.24\textwidth}
	\includegraphics[width=\linewidth]{RPTS09-Histogram}
	\endminipage\hfill
	\minipage{0.24\textwidth}
	\includegraphics[width=\linewidth]{Kamble09-Histogram}
	\endminipage\hfill
	\minipage{0.24\textwidth}%
	\includegraphics[width=\linewidth]{CAHR09-Histogram}
	\endminipage\hfill
	\minipage{0.24\textwidth}
	\includegraphics[width=\linewidth]{CAH09-Histogram}
	\endminipage\hfill
	\newline 
	\caption{Histograms for the 204
		(region, business type) pairs of
		expected benefit
		(averaged across questions) from truthful behavior
		vs.  some other strategy, when fraction $p$
		is truthful and fraction $1-p$ adopt the same,
		non-truthful
		strategy for $p = 0.1,0.5,0.7,0.9$  \label{fig:1}}
\end{figure*}
\end{document}

hetpp-tasks-arxiv.bbl
\begin{thebibliography}{}

\bibitem[\protect\citeauthoryear{Agarwal \bgroup \em et al.\egroup
  }{2017}]{agarwal2017}
Arpit Agarwal, Debmalya Mandal, David~C. Parkes, and Nisarg Shah.
\newblock {P}eer {P}rediction with {H}eterogeneous {U}sers.
\newblock In {\em Proceedings of the 2017 ACM Conference on Economics and
  Computation}, pages 81--98, 2017.

\bibitem[\protect\citeauthoryear{Dasgupta and
  Ghosh}{2013}]{dasgupta2013crowdsourced}
Anirban Dasgupta and Arpita Ghosh.
\newblock {Crowdsourced Judgement Elicitation with Endogenous Proficiency}.
\newblock In {\em Proceedings of the 22nd international conference on World
  Wide Web}, pages 319--330. ACM, 2013.

\bibitem[\protect\citeauthoryear{Dawid and Skene}{1979}]{dawid1979maximum}
Alexander~P. Dawid and Allan~M. Skene.
\newblock {Maximum Likelihood Estimation of Observer Error-Rates Using the EM
  Algorithm}.
\newblock {\em Applied statistics}, pages 20--28, 1979.

\bibitem[\protect\citeauthoryear{Devroye and
  Lugosi}{2012}]{devroye2012combinatorial}
Luc Devroye and G{\'a}bor Lugosi.
\newblock {\em {Combinatorial Methods in Density Estimation}}.
\newblock Springer Science \& Business Media, 2012.

\bibitem[\protect\citeauthoryear{Jurca and Faltings}{2008}]{jurca2008truthful}
Radu Jurca and Boi Faltings.
\newblock {Truthful Opinions from the Crowds}.
\newblock {\em ACM SIGecom Exchanges}, 7(2):3, 2008.

\bibitem[\protect\citeauthoryear{Jurca and
  Faltings}{2009}]{jurca2009mechanisms}
Radu Jurca and Boi Faltings.
\newblock {Mechanisms for Making Crowds Truthful}.
\newblock {\em Journal of Artificial Intelligence Research}, 34(1):209, 2009.

\bibitem[\protect\citeauthoryear{Kamble \bgroup \em et al.\egroup
  }{2015}]{kamble2015truth}
Vijay Kamble, David Marn, Nihar Shah, Abhay Parekh, and Kannan Ramachandran.
\newblock {Truth Serums for Massively Crowdsourced Evaluation Tasks}.
\newblock {\em The 5th Workshop on Social Computing and User-Generated
  Content}, 2015.

\bibitem[\protect\citeauthoryear{Kong \bgroup \em et al.\egroup
  }{2016}]{kong2016putting}
Yuqing Kong, Katrina Ligett, and Grant Schoenebeck.
\newblock {Putting Peer Prediction Under the Micro (economic) scope and Making
  Truth-telling Focal}.
\newblock In {\em International Conference on Web and Internet Economics},
  pages 251--264. Springer, 2016.

\bibitem[\protect\citeauthoryear{Miller \bgroup \em et al.\egroup
  }{2005}]{MRZ2005}
Nolan Miller, Paul Resnick, and Richard Zeckhauser.
\newblock {Eliciting Informative Feedback: The Peer-Prediction method}.
\newblock {\em Management Science}, 51:1359--1373, 2005.

\bibitem[\protect\citeauthoryear{Radanovic \bgroup \em et al.\egroup
  }{2016}]{radanovic2016incentives}
Goran Radanovic, Boi Faltings, and Radu Jurca.
\newblock {Incentives for Effort in Crowdsourcing Using the Peer Truth Serum}.
\newblock {\em ACM Transactions on Intelligent Systems and Technology (TIST)},
  7(4):48, 2016.

\bibitem[\protect\citeauthoryear{Shnayder \bgroup \em et al.\egroup
  }{2016a}]{shnayder2016informed}
Victor Shnayder, Arpit Agarwal, Rafael Frongillo, and David~C Parkes.
\newblock {Informed Truthfulness in Multi-Task Peer Prediction}.
\newblock In {\em Proceedings of the 2016 ACM Conference on Economics and
  Computation}, pages 179--196. ACM, 2016.

\bibitem[\protect\citeauthoryear{Shnayder \bgroup \em et al.\egroup
  }{2016b}]{shnayder-ijcai16}
Victor Shnayder, Rafael Frongillo, and David~C. Parkes.
\newblock Measuring performance of peer prediction mechanisms using replicator
  dynamics.
\newblock In {\em Proc. 25th International Joint Conference on Artificial
  Intelligence (IJCAI)}, pages 2611--2617, 2016.

\bibitem[\protect\citeauthoryear{Witkowski and
  Parkes}{2012}]{witkowski2012robust}
Jens Witkowski and David~C Parkes.
\newblock {A Robust Bayesian Truth Serum for Small Populations}.
\newblock In {\em Proceedings of the Twenty-Sixth AAAI Conference on Artificial
  Intelligence (AAAI)}, pages 1492--1498, 2012.

\end{thebibliography}
