Learning to Incentivize: Eliciting Effort via Output Agreement

1 Introduction

Our ability to reach an unprecedentedly large number of people via the Internet has enabled crowdsourcing as a practical way for knowledge or information elicitation. For instance, crowdsourcing has been widely used for getting labels for training samples in machine learning. One salient characteristic of crowdsourcing is that a requester often cannot verify or evaluate the collected answers, because either the ground truth doesn't exist or is unavailable or it is too costly to be practical to verify the answers. This problem is called information elicitation without verification (IEWV) [Waggoner and Chen, 2014].

In the past decade, researchers have developed a class of economic mechanisms, collectively called the peer prediction mechanisms [Prelec, 2004; Miller et al., 2005; Jurca and Faltings, 2006; 2009; Witkowski and Parkes, 2012a; 2012b; Radanovic and Faltings, 2013; Frongillo et al., 2015], for IEWV. The goal of most of these mechanisms is to design payment rules such that participants truthfully report their information at a game-theoretic equilibria. Each of these mechanisms makes some restriction on the information structure of the participants. Under the restriction, truthful elicitation is then achieved by rewarding a participant according to how his answer compares with those of his peers. Within this class, output agreement mechanisms are the simplest and they are often adopted in practice [von Ahn and Dabbish, 2004]. In a basic output agreement mechanism, a participant receives a positive payment if his answer is the same as that of a random peer and zero payment otherwise. When the majority of the crowd hold the correct answer, output agreement mechanisms can truthfully elicit answers from the crowd at an equilibrium.

Most of these works on peer prediction mechanisms, with the exception of Dasgupta and Ghosh [2013] and Witkowski et al. [2013], assume that answers of participants are exogenously generated, that is, participants are equipped with their private information. However, in many settings, participants can exert more effort to improve their information and hence the quality of their answers is endogenously determined. Recent experiments [Yin and Chen, 2015; Ho et al., 2015] have also shown that the quality of answers can be influenced by the magnitude of contingent payment in settings where answers can be verified.

In this paper, we study eliciting efforts as well as truthful answers in output agreement mechanisms. Taking the perspective of a requester, we ask the question of how to optimally set the payment level in output agreement mechanisms when the requester cares about both the accuracy of elicited answers and the total payment.

Specifically, we focus on binary-answer questions and binary effort levels. We allow workers to have heterogeneous cost of exerting effort. Such a cost is randomly drawn from a distribution that is common knowledge to all participants. We consider two scenarios. In the first scenario, a static setting, the requester is assumed to know the cost distribution of the participants. Her objective is to set the payment level in output agreement mechanisms such that when a game-theoretic equilibrium is reached, her expected utility is maximized. In the second scenario, a dynamic setting, the data requester doesn't know the cost distribution of the participants but only knows an upper bound of the cost. Here, the requester incorporates eliciting and learning the cost distribution into incentivizing efforts in output agreement mechanisms when she repeatedly interacts with the set of participants over multiple tasks. The ultimate goal of the requester is to learn to set the optimal payment level in this sequential variant of output agreement mechanism for each interaction so that when participants reach a game-theoretic equilibrium of this dynamic game, the data requester minimizes her regret on expected utility over the sequence of tasks.

We summarize our main contributions as follows:

• ÷ Since the quality of answers is endogenously determined, a requester's utility depends on the behavior of participants. Optimizing the payment level requires an understanding of the participant's behavior. We characterize Bayesian Nash equilibria (BNE) for two output agreement mechanisms with any given level of payment and show that at equilibrium there is a unique threshold strategy for positive effort exertion.
• ÷ For the static setting where the requester knows the cost distribution, when the cost distribution satisfies certain conditions, we show that the optimal payment level in the two output agreement mechanisms is a solution to a convex program and hence can be efficiently solved.
• ÷ For the dynamic setting where the requester doesn't know the cost distribution, we design a sequential mechanism that combines eliciting and learning the cost distribution with incentivizing effort exertion in a variant of output agreement mechanism. Our mechanism ensures that participants truthfully report their cost of effort exertion when asked, in addition to following the same strategy on effort exertion and answer reporting as that in the static setting for each task. We further prove performance guarantee of this mechanism in terms of the requester's regret on expected utility.

All omitted proofs can be found in [Liu and Chen, 2016].

1.1 Related work

The literature on peer prediction mechanisms hasn't addressed costly effort until recently. Dasgupta and Ghosh [2013] and Witkowski et al. [2013] are the two papers that formally introduce costly effort into models of information elicitation without verification. Dasgupta and Ghosh [2013] design a mechanism that incentivizes maximum effort followed by truthful reports of answers in an equilibrium that achieves maximum payoffs for participants. Witkowski et al. [2013] focuses on simple output agreement mechanisms as this paper. They study the design of payment rules such that only participants whose quality is above a threshold participate and exert effort. Both Dasgupta and Ghosh [2013] and Witkowski et al. [2013] assume that the cost of effort exertion is fixed for all participants and is known to the mechanism designer. This paper studies effort elicitation in output agreement mechanisms but allow participants to have heterogeneous cost of effort exertion drawn from a common distribution. Moreover, we consider a setting where the mechanism designer doesn't know this cost distribution, which leads to an interesting question of learning to optimally incentivize effort exertion followed by truthful reports of answers in repeated interactions with a group of participants.

Roth and Schoenebeck [2012] and Abernethy et al. [2015]

consider strategic data acquisition for estimating the mean and statistical learning in general respectively. Both works do not consider costly effort but participants may have stochastic and heterogeneous cost for revealing their data and need to be appropriately compensated. Moreover, these two works all assume that workers won't misreport their obtained answers.

2 Problem formulation

2.1 Our mechanisms

A data requester has a set of tasks that she wants to obtain answers from a crowd C = ¶1↪ ▷▷▷↪K♦ of K ≥ 2 candidate workers. In this paper, we consider binary-answer tasks, for example, identifying whether a picture of cells contains cancer cells, and denote the answer space of each task as ¶0↪ 1♦. The requester assigns each task to N randomly selected workers, with N ≥ 2 being potentially much less than K. 1 Such a redundant assignment strategy, when combined with some aggregation method (e.g. majority voting), has been found effective in obtaining accurate answers [Sheng et al., 2008; Liu and Liu, 2015].

The requester cannot verify the correctness of contributed answers for a task, either because ground truth is not available or verification is too costly and defies the purpose of crowdsourcing. Thus, in addition to a base payment, each worker is rewarded with a contingent bonus that is determined by how his answer compares with those of other workers for completing a task. Specifically:

1. The requester assigns a task to a randomly selected subset U ✓ C of workers, where ♣U♣ = N. She announces a base payment b > 0 and a bonus B > 0, as well as the criteria for receiving the bonus. The criteria of receiving the bonus is specified by an output agreement mechanism, which we will introduce shortly
2. Each worker i 2 U independently submits his answer Li 2 ¶0↪ 1♦ to the requester.
3. After collecting the answers, the requester pays base payment b to every worker who has submitted an answer and a bonus B to those who met the specified criteria.

The criteria for receiving bonus B is specified by an output agreement mechanism. Output agreement is a term introduced by von Ahn and Dabbish [2008] to capture the idea of "rewarding agreement" in their image labeling game, the ESP game [von Ahn and Dabbish, 2004]. We define two variants of output agreement mechanisms:

Peer output agreement (PA): For each worker i 2 U, the data requester randomly selects a reference worker j 6= i and j 2 U. If Li = Lj, worker i receives bonus B. Note worker j's reference worker could be different from i.

Group output agreement (GA): For each worker i 2 U, the data requester compares Li with the majority answer of the rest of the workers, LM, where LM = 1 if Pj2U↪j6=i Lj N-1 >

1 We assume N is fixed, though how to optimally choose N could be an interesting future direction.

0▷5, LM = 0 if Pj2U↪j6=i Lj N-1 < 0▷5 and LM = ¶0↪ 1♦ if Pj2U↪j6=i Lj N-1 = 0▷5. If Li 2 LM, worker i receives bonus B.

2.2 Agent models

A worker can decide how much effort to exert to complete a task and the quality of his answer stochastically depends on his chosen effort level. Specifically, a worker can choose to either exert or not exert effort. If a worker exerts effort, then with probability PH  1 his answer is correct. If a worker does not exerts effort, with probability PL, where PL < PH, he will provide the correct answer. We further assume PL ≥ 0▷5, that is, when no effort is exerted the worker can at least do as well as random guess. This assumption is also used by Dasgupta and Ghosh [2013] and Karger et al. [2011, 2013]. For now, we assume PL and PH are the same for all workers.

Since workers can choose their effort level, the quality of an answer is endogenously determined. Let ei 2 ¶0↪ 1♦ represents the chosen effort level of worker i, with 0 corresponding to not exerting effort and 1 corresponding to exerting effort. The accuracy of worker i can be represented as pi(ei) = PHei + PL(1 - ei)▷

Workers have heterogeneous abilities, which are reflected by their cost of exerting effort. When worker i doesn't exert effort, he incurs zero cost. A cost of ci ≥ 0 is incurred if agent i chooses to exert effort on a task. ci is randomly generated according to a distribution with pdf f(c) and cdf F(c) for each pair of (worker, task). We further assume this distribution stays the same 2 across all workers and all tasks, and it has a bounded support [0↪ cmax]. Moreover we enforce the following assumption on F (c):

This assumption is stating that the probability of having a larger cost ci is decreasing. Several common distributions, e.g. exponential and standard normal (positive side), satisfy this assumption. Throughout this paper, we assume F(c)↪ c 2 [0↪ cmax] is common knowledge among all workers. 3 Nevertheless each realized cost ci is private information, that is each worker i observes his own realized cost ci, but not the one for others. In Section 3, we assume the requester also has full knowledge of F(·), but we relax this assumption in Section 4.

Given that the cost of not exerting effort is zero, the positive base payment b ensures that every worker will provide an answer for a task assigned to him. We focus on understanding how to determine the bonus B in output agreement mechanisms to better incentivize effort in this paper. The base payment b doesn't enter our analysis directly but it allows us to not worry about workers' decisions on participation. When reporting their answer to the data requester, workers can choose to report truthfully, or to mis-report. Denote this decision variable for each worker i as ri 2 ¶0↪ 1♦, where ri = 1 represents worker i truthfully reporting his answer, and ri = 0 represents worker i mis-reporting (reverting the answer in our case). Then the accuracy of each worker i's report is a function of (ei↪ ri):

2 Realization for each (worker, task) pair can be very different.

3 In practice each worker can estimate such distribution based on their past experiences.

When each worker j 2 U takes actions (ej↪ rj), we denote the probability that worker i 2 U receives bonus B as Pi↪B(¶(ej↪ rj)♦j). In the PAmechanism, this quantity is

In the GA mechanism, it is Pi↪B(¶(ej↪ rj)♦j) = P(Li = LM)▷ Then, the utility for worker i is:

2.3 Requester model

The data requester has utility function UD, which in theory can be of various forms balancing accuracy of elicited answers and total budget spent. In this paper, we assume that the requester uses majority voting to aggregate elicited answers and has utility function

where P c (N↪ B) is the probability that the majority answer is correct, and Ne(B) is the number of workers who receive the bonus. Data requester's goal is to find a B⇤ s.t.

P c (N↪B) and E[Ne(B)] depend on workers' strategy towards effort exertion and answer reporting. The equilibrium analysis in the next section will help us define these quantities. The data requester is then hoping to choose a reward level that maximizes the expected utility at an equilibrium.

3 Optimal bonus strategy with known cost distribution

In this section we set out to find the optimal bonus strategy when the data requester knows workers' cost distribution. Because the requester's utility depends on the behavior of workers, we first characterize symmetric Bayesian Nash Equilibria (BNE) for the two output agreement mechanisms for an arbitrary bonus level B. Then based on workers' equilibrium strategies, we show the optimal B⇤ can be calculated efficiently for certain cost distributions. Note that due to the independence of tasks, this is a static setting and we only need to perform the analysis for a single task.

3.1 Equilibrium characterization

For any given task, we have a Bayesian game among workers in U. A worker's strategy in this game is a tuple (ei(ci)↪ ri(ei)) where ei(ci) : [0↪ cmax] ! ¶0↪ 1♦ specifies the effort level for worker i when his realized cost is ci and ri(ei) : ¶0↪ 1♦ ! ¶0↪ 1♦ gives the reporting strategy for the chosen effort level, with ri(ei) = 1 representing reporting truthfully and ri(ei) = 0 representing misreporting.

We first argue that at any Bayesian Nash equilibrium (BNE) of the game, ei(ci) must be a threshold function. That is, there is a threshold c⇤i such that ei(ci) = 1 for all ci  c⇤i and ei(ci) = 0 for all ci > c⇤i at any BNE. The reason is as follows: suppose at a BNE worker i exerts effort with cost ci. Since the other workers' outputs do not depend on ci (due to the independence of reporting across workers), worker i's chance of getting a bonus will not change when he has a cost c0i < ci and only obtains a higher expected utility by exerting effort. This allow us to focus on threshold strategies for effort exertion. We restrict our analysis to symmetric BNE where every worker has the same threshold for effort exertion, i.e. c⇤i = c⇤ . In the rest of the paper, we often use (c⇤ ↪ ·) to denote that a worker playing an effort exertion strategy with threshold c⇤ . In addition, we use ri ⌘ 1 to denote the reporting strategy that ri(1) = ri(0) = 1, i.e. always reporting truthfully for either effort level.

Before we present our main results, we note we have a set of zero-effort exertion equilibriums (c⇤ = 0). One set of such equilibriums is no one exerting effort combined with truthful or non-truthful reporting, or a mix of the two. Nonetheless these equilibriums return strictly less expected utility for each worker. Another one is when workers collude to always report the same uninformative signal. 4 In this paper we mainly focus on positive effort exertion equilibriums, that is c⇤ > 0.

PA: We have the following results for the PAmechanism.

Lemma 3.1. The strategy profile ¶(c⇤ ↪ ri ⌘ 1)♦i2U is a symmetric BNE for the PA game if

Denote BPA := cmax (2PH-1)(PH-PL) , the minimum bonus level needed to induce full effort exertion. With above lemma, we have the following equilibrium characterization.

Theorem 3.2. When PL > 0▷5, there exists a unique threshold c⇤ > 0 s.t. (c⇤ ↪ 1) is a symmetric BNE for the PA game:

• ÷ When B ≥ BPA, c⇤ = cmax.
• ÷ O.w. c⇤ is the unique solution to Eqn. (2).

When PL = 0▷5, we can prove similar results for the uniqueness of c⇤ > 0 such that (c⇤ ↪ 1) is a symmetric BNE: but under certain condition non-effort exertion is the only equilibrium. We would like to note that always mis-reporting (ri ⌘ 0) combined with the same threshold c⇤ for effort exertion as in Theorem 3.2 is also a symmetric BNE when PL > 0▷5. This equilibrium gives workers the same utility as the equilibrium in Theorem 3.2. This phenomenal has also been observed by Dasgupta and Ghosh [2013] and Witkowski et al. [2013]. Dasgupta and Ghosh [2013] argue that always mis-reporting is risky, and workers may prefer breaking the tie towards always truthful reporting.

GA: For GA, directly calculating the probability term for matching a majority voting is not easy; but if we adopt a Chernoff type approximation for it, and suppose such approximation is common knowledge 5 , we can prove similar results. Similar to Lemma 3.1, we can show that the strategy profile ¶(c⇤ ↪ ri ⌘ 1)♦i2U is a symmetric BNE for the GA game if

4 Interested readers can find more discussions and solutions for the colluding scenario in [Dasgupta and Ghosh, 2013].

Theorem 3.3. When PL > 0▷5, there always exists a unique threshold c⇤ > 0 such that ¶(c⇤ ↪ ri ⌘ 1)♦i2U is a symmetric BNE for the GA game:

• ÷ When B ≥ BGA, c⇤ = cmax.
• ÷ O.w., c⇤ is the unique solution to Eqn. (3).

We note the reward level and the total expected payment is lower in GA than in PA for eliciting the same level of efforts: Lemma 3.4. Denote the smallest bonus level corresponding to an arbitrary equilibrium threshold c⇤ > 0 for PA and GA as BPA(c⇤ ) and BGA(c⇤ ) respectively. Then BPA(c⇤ ) > BGA(c⇤ )↪ when N ≥ -log(1-PH) 2(PL-0▷5)2 + 1 (sufficiently large). Furthermore, the total payment in GA is lower than that in PA, i.e., GA leads to a higher requester utility.

Heterogeneity of PL and PH. So far we have assumed that PL and PH are the same for all workers. If workers have heterogeneous accuracy ¶P iL↪ P iH ♦i that are generated from some distribution with mean PL↪ PH, we can show that the above results hold in a similar way, with more involved arguments.

3.2 Optimal solution for data requester

Now consider the optimization problem stated in Eqn. (1) for the requester's perspective. For each B > 0, denote ¶(c↪ ri ⌘ 1)♦i2U as the corresponding strategy profile at equilibrium. P c (N↪B) can then be calculated based on c↪ F(c) (controlling how much effort can be induced), and PL↪ PH. Same can be done for E[Ne(B)]. Denote the optimization problem in (1) with above calculation as (PB). Directly investigating the two objective functions may be hard. We seek to relax the objectives. First of for PA, we will be omitting the 2PL - 1 term as when PL is only slightly larger than 0.5, this quantity is close to 0. Also for both PA and GA, we again use the Chernoff type of approximation for calculating P cB . We further introduce three conditions: (i) f(c) is twice differentiable and @ 2 f(c)◁@ 2 c ≥ 0. (ii) cF(c) is convex on c 2 [0↪ cmax]. (iii) G(c) := 1 - [(↵ - 1)F(c⇤ ) + 1]N-1 satisfies that @ 3G(c)◁@ 3 c exists and being non-negative.

Lemma 3.5. If (i) and (ii) hold, the objective function of (PB) is concave if we adopt PA. When (ii) and (iii) hold, the objective function of (PB) is concave if we adopt GA.

For example, exponential distribution (exp(λ)) for cmax  2◁λ satisfies (i)&(ii) for PA; and exp(λ) for cmax = -log↵ λ satisfies (ii)&(iii) for GA. It is worth to note above results hold for a wide range of other UD(·)s: for instance the ones with a linear combination of P c (N↪ B) and E[Ne(B)].

5 This is not entirely unreasonable as in practice this Chernoff type bounds are often used to estimate such majority voting probability term, when the number of variables (population) is large.

4 Learning the optimal bonus strategy

In this section we propose a sequential mechanism for learning the optimal bonus strategy, when the requester has no prior knowledge of the cost distribution but only knows cmax. This assumption can be further relaxed by assuming knowing an upper bound of cmax instead of knowing cmax precisely. Also similar as last section, PL↪ PH are known. In reality these two quantities can be estimated through a learning procedure by repeated sampling and output matching as shown in [Liu and Liu, 2015], via setting bonus level B := 0 and B := BPA(GA) 6 respectively (to induce effort level corresponding to PL↪ PH). In this work we focus on learning the cost functions, which is a more challenging task when the workers are strategic. We are in a dynamic setting where the requester sequentially ask workers to complete a set of task. (P1): We start our discussions with a simpler case. When asked to report their cost, workers maximize their collected utility from a set of data elicitation tasks and are not aware of the potential influence of their reports on calculating optimal bonus levels for any future tasks. The data requester's goal is to elicit cost data to estimate cost distribution and then the optimal bonus level ˜B⇤ , such that when ˜B⇤ is applied to a newly arrived task we can bound ♣UD( ˜B⇤ ) - UD(B⇤ )♣▷ where B⇤ is the optimal bonus level if the cost distribution is known. (P2): We then consider the case when workers are forward looking and are aware of that their reported cost on a task will be utilized to calculate optimal bonus strategy for future tasks. We form a sequential learning setting, where we separate the stages for task assignment into two types: one for data elicitation, which we also refer as exploration, and the other for utility maximization, which we refer as exploitation. The data requester's objective in this case is to minimize the regret defined as follows:

where B⇤GA is the optimal bonus level for GA when cost distribution is know, 7 and ¶Bi(t)♦i2U is the bonus bundle offered at time t. Note UD(·) is mechanism dependent: both P c (N↪B) and Ne(B) depends on not only the bonus level, but also the equilibrium behavior in a particular mechanism.

For simplicity of presentation, throughout this section we consider PL > 0▷5: this is to remove the ambiguity introduced in by the trivial equilibrium c⇤ = 0. Also we assume with the same expected utility, workers will favor truthful reporting ri ⌘ 1.

4.1 (M Crowd) for (P1)

Suppose the data requester allocates T tasks to elicit the cost data sequentially, and exactly one of them is assigned to the workers at each time step t = 1↪ 2↪ · · · ↪ T. For simplicity of analysis we fix the set of N workers we will be assigning tasks to. Denote worker i's realized cost for the t-th task as ci(t). We propose mechanism (M Crowd):

6 Calculating BPA(GA) only requires knowing cmax, not F(·).

7 Since GA is more cost efficient, we define the regret w.r.t. the optimal utility that can be obtained via GA.

Mechanism 1 (M Crowd)

For each step t:

1. Assign the task, and workers then report costs. Denote the reports as (˜ c1(t)↪ ▷▷▷↪ ˜ cN(t)). This is a voluntary procedure. A worker i can choose to not report his cost, in which case, the requester sets ˜ ci(t) := cmax.
2. Data requester randomly selects a threshold c⇤ (t) uniformly from the support [0↪ cmax], such that only the workers who reported ˜ ci(t)  c⇤ (t) will be considered for bonus following PA; others will be given a bonus according to a probability that is independent of workers' report (see Remarks for details).
3. The requester estimates a bonus level ˜Bi(t) for each worker i that corresponds to the threshold level c⇤ (t) under PA, using only the data collected from user j 6= i, and from all previous stages. This is done via estimating F (·) first and then plugging it into Eqn.(2). Then the requester adds a positive perturbation δ(t) that is time dependent to ˜Bi(t): Bi(t) := ˜Bi(t)+δ(t)▷
4. The data requester will then announce the bonus bundle [B1(t)↪ ▷▷▷↪BN(t)].

Remarks: 1. When a worker, say worker i, reports higher than the selected threshold, his probability of receiving a bonus will be calculated using the following experiment, which is independent of his output: suppose out of N workers, there are N(t) of them reported lower than c⇤ (t). Then we will "simulate" N workers' reports with the following coin-toss procedure: toss N(t) PH-coin and N -N(t) PLcoin. Assign a PL-coin toss to worker i, and select a reference answer from the rest of the tosses, and compare their results. If there is a match, worker i will receive a bonus. Simply put, the probability for receiving a bonus can be calculated as the matching probability in the above experiment. 2. Since we have characterized the equilibrium equation for PA with a clean and simple form, this set of equilibriums is good for eliciting workers' data. 3. After estimating the bonus level for each worker ˜Bi(t), the data requester will add a positive perturbation term δ(t) to each of them. This is mainly to remove the bias introduced by (i) imperfect estimation due to finite number of collected samples, and (ii) the (possible) mis-reports from workers. Such term will become clear later in the stated results. 4. The fact that we can use collected cost data to estimate B depends crucially on the assumption that the cost distribution is the same for all tasks.

4.2 Equilibrium analysis for (M Crowd)

We present the main results for characterizing how workers report their cost at an equilibrium. Even though we are in a dynamic game setting, we use BNE rather than Perfect Bayesian equilibrium (PBE) as our general solution concept as they do not have material differences in our setting. Due to the independence of tasks, workers make decisions on effort exertion at each stage just as they are in a static game with corresponding reward level. Because a worker's decision on effort exertion can not be directly observable, a deviation from an equilibrium effort exertion strategy cannot be detected by others, making the notion of "off-equilibrium path" not meaningful in this setting. This suggests that every BNE of the game is also a PBE. We will adopt ✏-approximate BNE as our exact solution concept, defined as follows:

Definition 4.1. A set of reporting strategy ¶˜ci := ¶˜ ci(t)♦t=1↪▷▷▷↪T♦i2C is ✏-BNE if for any i, 8˜c0i 6= ˜ci we have

We explicitly denote the expected utility for each worker as a function of ¶˜ci♦i2C. This is a short-hand notation, as uti s also depend on the effort exertion and reporting strategies. The maxei↪ri term allows worker i to optimize his effort exertion and reporting procedure based on their cost reporting.

γ > 0 being arbitrarily small, there exists a O( log2 T T )-BNE for each worker i with reporting ˜ ci(t) at time t such that

The effort exertion game at each step looks alike the static game introduced in Section 3 with the following difference: instead of workers who have cost ci(t)  c⇤ will exert effort, now it is the workers who reported ˜ ci(t)  c⇤ will exert effort. This is mainly due to the addition of the perturbation term to the estimated bonus level. Meanwhile the mechanism excludes workers who reported higher than the threshold from exerting effort by offering bonus with a probability that is independent of worker's output. Nevertheless, we can bound the fraction of workers whose actions are different for the above two games.

4.3 Performance of (M Crowd)

With this set of collected data, we bound the performance loss in offering optimal bonus level B for an incoming task (or task T + 1). Suppose we adopt GA, where the optimal bonus level with known cost distribution is given by B⇤GA , and the estimated optimal solution is given by ˜B⇤GA . We will have the following lemma: (similar results hold for PA)

Lemma 4.3. With probability being at least 1 - ⌘,

When we chose ⌘ = O(1◁T 2 ), the above regret term is roughly on the order of plog T◁T .

4.4 (RM Crowd) for (P2)

We propose a (RM Crowd) for (P2):

Remarks: 1. The dependence on T is to simplify the presentation and our algorithm design. This can be easily extended to a T-independent one. 2. At exploitation phases

Mechanism 2 (RM Crowd)

Specify a constant 0 < z < 1, and initialize t = 1. Define p(t) :=min¶1↪ logT t1-z ♦.

At time t, assign the task; workers then report costs. Toss a p(t)-coin.

When HEAD, algorithm enters exploration phase:

• ÷ Follow same steps as in (M Crowd). When TAIL, algorithm enters exploitation phase,
• estimate the optimal Bi(t) and its corresponding threshold c⇤i (t) for each worker i with GA, using the cost data collected only from the exploration phases. Only workers who reported ci(t)  c⇤i (t) will be given bonus according to GA; others receive bonus with a probability that is independent of her report.
• Follow rest steps in (M Crowd).

we assume there exists a solver that can find the optimal solution with a noisy estimation of F(·). In practice search heuristics can help achieve the goal. 3. We adopted different bonus mechanisms for different phases. When we calculate the bonus level according to a particular mechanism (PA or GA), we will also adopt it for evaluating workers' answers. 4. When using GA, the independent probability for giving out bonus when a report is higher than the threshold will be adjusted to a probability of matching a majority voting of the experiment we presented for (M Crowd).

Theorem 4.4. With (RM Crowd), set δ(t) := O(zt-z◁2 ), let z > 1◁3 and γ > 0 being arbitrarily small, there exists a O( z2 T z )-BNE for worker i reporting ˜ ci(t) at time t that:

We have similar observations for the effort exertion game in (RM Crowd) as we made for (M Crowd). Further we prove the following regret results:

Order-wise, the best z is when 1 - z◁2 = z ) z = 23 , which leads to a bound on the order of O(T 2◁3 log T).

5 Conclusion

In this paper we focus on using output agreement mechanisms to elicit effort, in addition to eliciting truthful answers, from crowd-workers when there is no verification of their outputs. Workers' cost for exerting efforts are stochastic and heterogeneous. We characterize the symmetric BNE for workers' effort exertion and reporting strategies for a given bonus level, and show data requester's optimal bonus strategy at equilibrium is a solution to a convex program for certain cost distribution. Then a learning procedure is introduced to help the requester learn the optimal bonus level via eliciting cost data from strategic workers. We bound the mechanism's performance loss w.r.t. offering the best bonus bundle, compared to the case when workers' cost distribution is known a priori.

Acknowledgement

We thank the support of the National Science Foundation under grant CCF-1301976 and a research grant from Google on this work. Any opinions, findings, conclusions, or recommendations expressed here are those of the authors alone.