Peer Prediction for Learning Agents
Authors: Shi Feng
Fang-Yi Yu
Yiling Chen
Venue: NeurIPS 2022 Accept (2022)
Keywords: information elicitation
peer prediction
online learning
truthful convergence

Abstract: Peer prediction refers to a collection of mechanisms for eliciting information from human agents when direct verification of the obtained information is unavailable. They are designed to have a game-theoretic equilibrium where everyone reveals their private information truthfully. This result holds under the assumption that agents are Bayesian and they each adopt a fixed strategy across all tasks. Human agents however are observed in many domains to exhibit learning behavior in sequential settings. In this paper, we explore the dynamics of sequential peer prediction mechanisms when participants are learning agents. We first show that the notion of no regret alone for the agents’ learning algorithms cannot guarantee convergence to the truthful strategy. We then focus on a family of learning algorithms where strategy updates only depend on agents’ cumulative rewards and prove that agents' strategies in the popular Correlated Agreement (CA) mechanism converge to truthful reporting when they use algorithms from this family. This family of algorithms is not necessarily no-regret, but includes several familiar no-regret learning algorithms (e.g multiplicative weight update and Follow the Perturbed Leader) as special cases. Simulation of several algorithms in this family as well as the $\epsilon$-greedy algorithm, which is outside of this family, shows convergence to the truthful strategy in the CA mechanism. 

Peer Prediction for Learning Agents
Shi Feng
Institute for Interdisciplinary Information Sciences, Tsinghua University Beijing, China
fengs htt.11mmmmmlsssssnnnaaaaaa edu. cn
Fang-Yi Yu
Department of Computer Science, George Mason University Fairfax, VA, USA
fangyiyu@gmu.ed
Yiling Chen
John A. Paulson School of Engineering and Applied Sciences, Harvard University Cambridge, MA, USA yilingOseas harvard. edu
Abstract
Peer prediction refers to collection of mechanisms for eliciting information from human agents when direct verification of the obtained information is unavailable. They are designed to have a game-theoretic equilibrium where everyone reveals their private information truthfully. This result holds under the assumption that agents are Bayesian and they each adopt a fixed strategy across all tasks. Human agents however are observed in many domains to exhibit learning behavior in sequential settings. In this paper, we explore the dynamics of sequential peer prediction mechanisms when participants are learning agents. first show that the notion of no regret alone for the agents' learning algorithms cannot guaran- tee convergence the truthful strategy. We then focus on a family of learning algorithms where strategy updates only depend agents' cumulative rewards and prove that agents' strategies in the popular Correlated Agreement (CA) mechanism converge truthful reporting when they use algorithms from this family. This fam- ily algorithms is not necessarily no-regret, but includes several familiar no- negrettet learning algorithms (e.g multiplicative weight update and Follow the Perturbed Leader) as special cases. Simulation several algorithms in this family as well as the e-greedy algorithm, which is outside of this family, shows convergence to the truthful strategy in the CA mechanism.
Introduction
A fundamental challenge in many domains is to elicit high-quality information from people when directly verifying the acquired information not feasible, either because the ground truth is not available because it is too costly to obtain. Notable settings include asking people to label data for machine learning, having students perform peer grading in education, and soliciting customer feedback for products and services.
The peer prediction literature has made impressive progress on this challenge in the past two decades, with many mechanisms that have desirable incentive properties developed for this problem [20] [9
22
15
The term peer prediction refers a collection reward
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

mechanisms that solicit information from human agents and reward each agent solely based on how the agent's reported information compares with that of the other agents, without having access the
ground truth. Under some assumptions, many peer prediction mechanisms [20] 19
27 22 g 16 21 guarantee that every agent truthfully reporting their information a rame-theoretic equilibrium, and 23 [5] further ensure that agents receive the highest expected payoff at the truthful equilibrium, compared with other strategy profiles.
the more recent multi-task peer prediction mechanisms [5] 14 25 I7 18
While achieving truthful reporting as a highest-payofe equilibrium is a victory to declare for this challenging without- verificaatin setting, there are however caveats associated with adopting the notion of equilibrium as a solution concept. The equilibrium results rely on the assumption that participants are fully rational Bayesian agents. Equilibrium is static notion and does not address how agents, who act independently, jump to play their equilibrium strategies. Moreover, the equilibrium results of multi-task peer prediction mechanisms heavily depend on consistent strategy assumption, that is, each agent is assumed to adopt fixed strategy across all tasks in which she participates. All together these assumptions exclude the possibility that agents may explore and learn from previous experience, a behavior that's not only commonly observed in practice but also has been modeled in studying other strategic settings 3 4.
This paper is the first theoretical study on the dynamics of sequential peer prediction mechanisms when participants are learning agents. The main question that we explore is whether and when in sequential peer prediction, learning agents will converge all playing the truthful reporting strategy. We first consider agents adopting no-regret learning algorithms and prove that the notion of no regret alone cannot guarantee convergence to truthful reporting. We then define a natural family of reward-based learning algorithms where strategy updates only depend on agents' cumulative rewards. While algorithms in this family are not necessarily no-regret (e.g. the Follow the Leader algorithm), this family includes some familiar no-regret learning algorithms, including the Multiplicative Weight Update and the Follow the Perturbed Leader algorithms, Our main result shows that, for the binary- signal setting, agents' strategies in the popular Correlated Agreement (CA) mechanism [5] converge to truthful reporting when agents use any algorithm from this family. To prove the result, we show the process has a self-fulflling property: once Alice and Bob have large accumulated rewards for they are more likely to play truth-telling and resulting in larger accumulated rewards. Theoretically, carefully partition the process into three stages, bad, intermediate, and good events illustrated in fig. [ and use tools in martingale theory to argue the progress of the process. Finally, we simulate the strategy dynamics in the CA mechanism for several algorithms in this family as well as for the e-greedy algorithm, which doesn't belong to this family. We observe convergence to truthful reporting for all algorithms considered in our simulation, suggesting an interesting future direction to characterize all learning algorithms that converge to truthful reporting.
Related Works learning agents.
This paper relates to two lines of work, information elicitation and mechanisms for
Information Elicitation Mechanisms The literature on information elicitation without verification focuses on capturing the strategic aspect of human agents. In multi-task settings, Dasgupta and Ghosh 5 proposed seminal informed truthful mechanism, the Correlated Agreement (CA) mechanism, for binary positively correlated signals. A series of works then relaxed the binary and positively Additionally, Zheng et al. (2 study the limitation of information elicitation in the multi-task setting. However, all of the above works assume agents using consistent strategies that are identical across all tasks. The consistent strategy assumption excludes the possibility of agent learning. Our work removes the consistent strategy assumption and explicitly considers learning agents. We thcoretically prove truthful convergence of the CA mechanism when agents using algorithms from family of weward-based online learning algorithms.
correlation assumptions [25] 23 [5].
Our work of considering learning agents can be viewed as way of testing the robustness of information elicitation mechanisms with respect to deviation from the rational Bayesian agent model. From this perspective, Shnayder et al. [26] is closely related to ours. They consider sequential information elicitation and empirically study if agents using replicator dynamics can converge to truth-telling the CA mechanism and several other mechanisms. Our work theoretically proves that, besides replicator dynamics, learning agents can converge to truth-telling in the CA mechanism when they use general family of learning algorithms. Additionally, Schoenebeck et al. (4] designed an information elicitation mechanism that was robust against small fraction of adversarial agents.
2

---

Mechanisms for Learning Agents Several works in economics and computer science try to design mechanisms for learning agents, rather than for rational, Bayesian ones. Braverman et al. D studied pricing mechanisms for learning agents with no external regrets. Their work was generalized by Deng et al. [6] to consider repeated Stackelberg games in full-information settings. Camara et al. [4] further proposed counterfactual internal regrets (CIR) together with no-CIR assumption, which was proved to be a sufficient behavior assumption for no-regret principal mechanism design in repeated stage games. However, all of these works focus a single agent full-information games, while peer prediction an incomplete-informat different from that of most sequential mechanism design. Instead of maximizing the mechanism designer's utility, our goal is to incentivize truthful reporting from agents.
game with multiple agents. Finally, our goal is slightly
2 Peer Prediction Settings
For simplicity consider two agents] Alice and Bob, who work sequence of tasks indexed by 2 1. For round f, both agents work on task t, Alice receives a signal X, = 2; in {0, 1]. and Bob signal Y, Ye in {0,1} where X, and Y, denote random variables, and 24 and y are their realizations. Then Alice and Bob report X, ât and y, = it in {0,1}. We define Xs: = (X, 1 S 8 S 1] E (0.1) and Xgr = {X, : 1 S s S 1) E [0,1]' to denote Alice's signal profile and report profiles until t-th round respectively, and define Y and Y: for Bob similarly. We use X, X, Y. and Y for the complete signal and report profiles. Additionally, we consider the signals are generated from some distribution P that satisfies the following assumptions:
Assumption 2.1 (A priori similar tasks [5). Each pair of signal is identically and independently (i..d.) generated: there exists distribution Px,y over 1) such that (X,, Y,) ~ Px,y for any 1 E N Moreover, we assume the distribution has full support, Px,y(1: y) > 0 for all ær E {0, 1].
Assumption 2.2 (Positively correlated signals). The distribution Px, is positively correlated, Px 0)} > mxx Px,
Now we introduce multi-task peer prediction mechanisms and sequential peer prediction mech- anisms, and their relation. We will focus on the sequential setting. Multi-task peer prediction mechanisms work on fixed number of tasks. Formally, multi-task peer prediction mech- anism on l tasks is a pair of payment functions M 1).1)* - [o, 1|.. For instance, the (multi-task) correlated agreement mechanism (CA mechanism
15 25 26 is MCA (xx ý)
(I[ = 5/2] - I[ 91), l[i Ø2] l1[ý2- i1l) for all x, y E (0, 1 Intuitively, the CA mech- anism rewards agreement on the same task and punishes agreement on uncorrelated tasks.
sequential information elicitation mechanism is a sequence of payment functions M = {M+ t 2 1} where M, {0, 1 + [-1, 1] for all t. After Alice and Bob reporting Xct and y in round t, the mechanism computes (rt, 3t) := (x 8<1)) and pay Te to Alice and 8, to Bob. Here we assume M, can only depends
constant k round of reports so that ( M,( k+.... Lt, -t-k+1, -ttk-tt.................1....... 9t) for all f, &ge. and ÿge, and we call such M rank K mechanism. For instance, the (multi-task) CA mechanism can be adopted as sequential rank 2 information elicitation mechanism: At round f, the payment is
MCA 8c)) (1[a, = ix] [ = -r- 1]. Ille i.} 1l 1))
(1)
where to and To are set as O. Similarly, we say sequential information elicitation mechanism M = (Mr)21 is sequential version of multi-task information elicitation mechanism AM if M.( M ft-k+, 1. Liz, 1 St ft..kt,...... .r) for all & & and ( > k. The payment at round 2 k is M on the latest k reports. Conversely, a sequential information elicitation mechanism can be seen aequencc
sequence of multi-task information elicitation mechanisms.
'Frr more than two agents, we can partition the agents into groups of two agents to run our mechanisms when the number of agents is even. Then all our results still hold. Finally, when the number of agents is odd, we can pair the unpaired agent with a reference agent whose payment is not affected by the unpaired one.
"Wille the CA mechanism can defined on non binary setting and does not require positive correlation. (55) with assumption 2.2 the CA mechanism reduces to eq. (i) and is first proposed in [5]. Finally, note that when the number of task is greater than two, we can compute the payment based on the last two tasks or two random tasks since agents using consistent strategy and assumption 2.1
3

---

Now we formally define agents' strategies. Due to symmetry, we introduce notation for Alice and omit Bob's. Given an information elicitation mechanism M, at round Alice observes her signal Iy and decides on her report Σz. Thus, Alice has four options (pure strategies): 1) opt,: report the private signal truthfully, 2) opt,: flip the private signal, 3) optz: report 1 regardless of the signal, and 4) o report O regardless of the signal. We call opt, and opt, uninformative strategies. We use opt," to denote Alice's s pure strategy, and r. for her payoff at round t. At each round t, Alice knows her previous signals x E {0, 13. her pure strategies opt ..... opt and Bob's 's reports ýg--1, so we use F: {xg+, x - g } to denote Alice knowledge at round t. Thus, Alice's mixed strategy at round L is stochastic mapping of" from Fe {opt,, opt2, 3pt opt,)- We'll abuse our nation and also use ox opt to represent the realized pure strategy. Finally, a learning algorithm of Alice is a mapping from an information elicitation mechanism .M to her strategies.
Strong Truthfulness for Rational and Bayesian agents Previous works on information elicitation try to ensure truth-telling opt, is the best strategy for rational and strategic agents. In particular, a mechanism is strongly truthful if Alice and Bob report truthfully (BNE) and they get strictly higher payment at this BNE than at any other non- permmumtttaionn BNE, We present the formal definitions in the appendix. Informally, in a permutation BNE, every agent's strategy on each round is a permutation//ijection from his/her signals to reports. However, the equilibrium results of previous mechanisms not only require assumption 2. but further assume agents using consistent strategies. Specifically, Alice uses a consistent strategy if there is fixed distribution on {opt,, optz optz. )pt, so that opt:" is generated from a fixed distribution that is independent of her private signals other tasks and the round number. For instance, when Alice and Bob are Bayesian and use consistent strategies under assumption 2.2 and [2.1 Dasgupta and Ghosh [5] show CA mechanism in eq. (1) is strongly truthful. Intuitively, positive correlation assumption 2.2 guarantees that truthful reporting can maximize the chance of agreeing with the peer on the same task while avoiding agreeing on reports on other tasks. Furthermore, in appendix [B] we show CA mechanism merely has three types Bayesian Nash equilibria, at which both agents 1) play truth-telling opt,, 2) flip the signal optz, or 3) generate uninformative reports (mixture between opt3: opt,) when agents use consistent strategies and assumptions 2.1 and (.2 hold.
Bayesian Nash Equilibrium
Truthful Convergence for Learning Agents However, as we consider agents using a family of online learning algorithms to decide their strategies, standard solution concepts like Bayesian Nash equilibrium no longer apply. Additionally, online learning algorithms often have exploration, so we cannot hope agents will always use the truth-telling strategy. For learning agents, our goal is to test whether existing mechanisms can ensure that agents will converge to truthful reporting when they deploy certain learning behavior that goes beyond obliviously consistent strategies.
We now formalize the convergence of algorithms truthful reporting. Because want elicit information without verification, it is mutation equilibrium, where all agents play optz. from truthful equilibrium, where all agents play opt,, without any additional information [77. However, if we have an additional bit of information on whether the prior of is larger than 1, we may tell apart these two equilibria. We hence define convergence to truthful reporting as the limits of both opt," and opto being truth-telling (opt, ) or flipping (opt.)). Note that definition 2.3 requires almost surely convergence which is very strong convergence concept.
impossible for us to separate per-
from
Definition 2.3. An information elicitation mechanism M achieves truthful convergence for agents using algorithms A₁ and Ag respectively if and only if both sequences of pure strategies converge to truth-telling or both flipping the reports.
Pr lim opt lim opto opt, V lim opt lim opdo =op12 } 1-+20
-1.
to++0 t++00
3 Online Learning Algorithms
In this section, we explore candidates to model agents' learning behavior to replace Bayesian agents' consistent strategies in the literature. We first show the conventional no-regret assumption is necessary but not sufficient condition for truthful convergence in section 33.] Then in section (.22 we introduce family of reward-based online learning algorithm to model agents' learning behavior,

---

and show that the family of reward-basee online learning algorithms contains several common no-regret algorithms as special cases.
3.1 No-regret Online Learning Algorithms
We now investigate the relationship between no regret and truthful convergence. First, we show general no-regret algorithms may not ensure truthful convergence (heerrem..1) However, we show the converse is almost true (theorem 3.2): : If truthful convergence happens, the agents do not have regret when the sequential mechanism a sequential version of a strongly truthful mechanism.
Given sequential information elicitation mechanism M = (M²", MM )e21, signals x, y, and reports &, y, we define Ti,: = (1i)................ (x) ( be the payoff when Alice uses strategy opt, and Bob's choices are unchanged. Then Alice's 's regret is Reg*(T) = max; Eist Ti, EKTT rr. Finally, we say that Alice's s and Bob's online learning algorithms are no regrel (on M) if E E[Reg* [[)) E[Reg* (T)] o(T) over the randomness of signals and the algorithms, and say Alice and Bob are no regret for short.
One may hope that no regret as behavior assumption for agents is sufficient for achieving desirable outcome a mechanism. However, the following theorem shows that we cannot have an information elicitation mechanism that achieves truthful convergence for all no-regret agents.
Theorem 3.1. For any sequential information elicitation mechanism M of rank k E N, there exist no-regret algorithms for Alice and Bob so that M cannot achieve truthful convergence.
The main idea of the proof is that the no-regret assumption cannot prevent Alice and Bob from colluding. In our counterexample, Alice and Bob decide on a no-regret sequence of reports regardless of their signals once the mechanism is announced. Technically, we use probabilistic method to show the existence of a deterministic and no-regret sequence of strategies (opt;" opt; )=21 that consists of reporting 1 or 0 regardless of private signals, i.e. optz opt.. The formal proof is in appendix C.I
The notion of truthful convergence in definition 2.3 provides ideal truthful guarantee to the mechanism designer. Here we show that truthful convergence also ensures no regret for agents when the sequential mechanism is sequential version of a strongly truthful one-shot multi-task mechanism. That is, when the one-shot mechanism admits truthful reporting as a highest-payoff BNE.
For instance, if pair of algorithms exhibits truthful convergence on the sequential CA mechanism (eq. (L) they are also no regret (on the game). Intuitively, Bob converges to the truth-telling lim opt opt,, the average expected gain of Alice deviating to opt, is equal to the expected gain of deviating to opt, when Bob always tells the truth. The gain non positive because the CA mechanism strictly truthful by lemma B.4 Therefore, the expected regrets EE Reg (T) and E[Reg* (T) are small. Theorem 3.2 formalizes and extends the above idea to any strongly truthful multi-task information elicitation mechanism.
Theorem 3.2. Let M be strongly truthful multi-task information elicitation mechanism, and M be sequential version of M. If M achieve truthful convergence for Alice and Bob using algorithmss A and A2 respectively, then Alice and Bob are no regret.
3.2 Reward-based Online Learning Algorithms
As shown in theorem 3.1 the no-regret assumption allow does not guarantee truthful convergence. In this section, we introduce general family of online learning algorithms, reward-based online learning algorithm, under the general full feedback bandit setting, and will apply these algorithms in sequential information elicitation mechanisms later. Informally, a reward-based online learning algorithm decides each round's strategy using a fixed update function that depends only on the accumulative reward.
For simplicity, we only consider algorithms four strategies {opt, optz, opty, opt,} which can be extended easily. Recall that the payoff of choosing option opt,, à E [4] at round t is ri.j when others' choices are unchanged. We denote the accumulated payoff's of these four options as R2, E/= fiy for i E [4]. Symmetrically, use Sú, and 8i, to represent accumulated payoffs and the payoff of turning to choose option opt, in the fth round for Bob. For example, for our specific peer
5

---

prediction game using CA mechanism in eq. ( F1, = Ia, = 0i] - Dt-1) and therefore,
R1, = -]== ūs] [ Dt-1)) for Alice.
We consider family of reward- based online learning algorithms A that use an update function f: IR - A and choose opt, with probability f( R3,--1, Ra,t-1) for E [4] in the tth round, where f; the 7th coordinate of f. A such mechanism based on accumulated payoff's is denoted by Ay. We have three assumptions for the update function f, which are all very natural. The first two require that f is exchangeable and preserves ordering.
Assumption 3.3 (Exchangeability of f). For any R1, R2, R3, R4 IR and arbitrary permutation of them R. Rig Rig Rig Sú, (Ri, R2, R3, R4) - ff fī Rig Rig Rig for all j E [4].
Assumption 3.4 (Order preservation of f). For any R1, R2, R3, Rs E R and suppose that Ri, R2g Rig Ri is a non-increasing order of them, for f we have fú (R2, R2, R3, Ra) Z
fig R1, R2, Rg, Ra) 2 ftg (R1, R2, Rg, RA) 2 fi, (R1, R2, Rg, RA).
Finally consider the strategy chosen by the update function when the accumulated payoff of an strategy is much higher than that of other strategies (assumption 3.5). Appendix(D.2]shwww shows that the assumption necessary for reward-basee baaddd online learning algorithms to achieve no regret for any online decision problem.
Assumption 3.5 (Full exploitation of f). lim max ( R2, R4. R4) (R1. R2, R3, R4) =1
Now we show that the family of reward-based online learning algorithms A satisfying assumptions 3.3 to 3.5 contains several classic no-regret online learning algorithms 100 13
Theorem 3.6. A contains Follow the Perturbed Leader (FPL) algorithm, and Multiplicative Weights algorithm special cases. Corresponding f for them are listed as below:
Multiplicative Weight algorithm phoadgo (R1, R2, R3, RA) = ESelg for E [4]
FPL algorithm Given a noise distribution N on scalars, (f R2, Ra, Ra) iid Pr Rg + p: = max + +53 ~ N. E (41 for E [4].
=
In the binary peer prediction problem using CA mechanism, we can further show that replicator dynamics and linear updating multiplicative weight algorithm [ are both in AA in appendix [
Remark 3.7. Our reward based online learning is very similar to the mean-based algorithm in 3 and both use the accumulated rewards to characterize the algorithm's 's choice. Additionally, like the mean- based algorithms, our reward based online algorithm may contain algorithms with regret in genral game, e.g., follow the leader. The family of reward based online algorithms uses identical update function across all rounds. Thus some no-regret algorithms, c.g., e-greedy with time decreasing e, doesn't belong to family. Finally, if mean-based algorithm is also reward based algorithm that uses the same update function in each round, then its update function satisfies assumption 3.5
4 Truthful Convergence of CA Mechanism on Reward-based Algorithms
Now we present our main result. We will show that the sequential CA mechanism can achieve truthful convergence if both agents use reward-basse online learning algorithms from A. This convergence result suggests that the classical CA is robust even when agents deviate from Bayesian rational behavior and use general family of online learning algorithms.
Theorem 4.1. Under assumptions 2.1 and 2.2 the binary-signal, sequential CA mechanism as defined in eq. ① achieves truthful convergence when agents use reward-based algorithms A, and Ag. where the update functions I and satisfy assumptions 3.3 to 3.5
Note that given agents' online learning algorithm and the payment function, the sequence of accu- mulated reward vector (RI,,, R2,,, Ra,1, Ra., S1.,, S2,1, S3.t. S4.)(21 forms a stochastic process and we define H. as the game history of the rewards and private signals the first round. Additionally, if the accumulated reward of truth-telling R1,,, Si.t is much larger than the others', we can show Alice and Bob converge to the truth-telling by assumption 3.5) Thus, sufficient for us to track the evolution of accumulated reward vector. Though the process of accumulated reward vector is not

---

a Markov chain because the payment function eq. !I depends on reports in two rounds, we can still use ideas from semi- martingtie to track the process.
Before proving our main result, we first present two properties of CA mechanism for our binary signal peer prediction problem. Lemma 4.2 shows that the accumulated payoffs of uninformative strategies op opt, R3 R4,t, S3.t, and S4,t are always bounded.
Lemma 4.2, Given the game defined in theorem 4.1 for any round t, the accumulated payoff's R3 RA,t, S3,t, and Sa,t for two agents are bounded by [-1,
The second one, Lemma 4.3 tells us that the summation of accumulated payoff's of opt, and opt, is always fixed and is equal to the summation of accumulated payoff's of uninformative ones opt, and opt, for both agents. The proofs of these two lemmas are in appendix F.
Lemma 4.3. Given the game defined in theorem 4.7 for any round t, Alice has RA + R2, R3, + R = 0, and Bob has S1,1 + S2. = S3,t S4. = O.
We now sketch the proof that consists of four steps. Informally, using lemmas 4.2 and 4.3 the first step says that the uninformative strategies opt, and opt, can not completely dominate other strategies. Specifically. both agents can not choose an option between opt, and opt, with a probability larger than 0.75. With the first step, lemma 4.2 and lemma 4.3 we only need to focus on agents' reward of the truthtelling opt, shown fig. We partition the space into three types of events. Good events happen when R1, S1 are both very large or very small, bad events happen when one of R1. S1 is very large and one of them is very small, and intermediate states are the states between them. The second step removes the possibility that Alice and Bob continue using different reports opt, and optz- Therefore, we can always escape "bad events" and enter "intermediate states". The third step further shows that if the game is in an intermediate state, there exists a constant probability that the game will get into a good events that leads to truthful convergence in a constant number of rounds. Hence, after the game enters "good events", which leaves us the final step: showing their strategies converges to either both truth telling opt, or flipping opt, truthful convergence.
Now we discuss each steps in more details but defer all the proofs to appendix
Good Founs: 8d
Tel Event: gh
Bed Boert: gld
Good Exent: (1x)
Figure 1: A schematic diagram of behaviors of R1, and S1,--
Step 1: Choosing opt, opt, with Nonzero Probability
Combining Lemmas 4.2 and 4.3 we have the following Lemma 4.4 which completes step 1.
Lemma 4.4. Given the game defined in theorem 4.1 for any round 1. 2 0 and E {1,2), if
Ej Tig 2 O, the probability for Alice to choose opt, is larger than 4:: if E Si, 2 0, the probability for Bob to choose opt, is larger than 1.
Step 2: Escaping Bad Events
7

---

Before introduce the formal statement of step 2, we define two "bad events". Given co for all t 2 1 E == [R > co, and S2 > co) and E : { R2, > and S1, > co). We will specify co later. Intuitively, when co is sufficiently large, E implies that Alice and Bob will choose , 2pt respectively with probability close to 1 in following rounds. For simplicity. we treat each event & as an indicator function, i.e., & happens if and only if 3 = In order to prove that these two bad events cannot go on forever, want show that when E, happens, R1, R2 will tend to decrease at rapid rate. Therefore, Alice will eventually deviate from opt, to choose opl, with a relatively high probability.
there exists a constant 61 such that when R1. > C1 Alice chooses opt, with probability larger than 6; when S2.1 C1, Bob chooses opt, with probability larger than - -6. 6. Let " = Px, (1, + Px, - (x,xx(10)) - Px,y (0,
By assumption 3.5 and lemma 4.2 given
7/2 = (1,,y(1,1) Px,y (0,,(0,,00) (), (1x, - Px,y (0. 1))²
Lemma 4.5. Given the game defined in theorem 4.1 there exists 8 and corresponding e₁ such that for any round E[r1,411 1
71 72 0.
c
Given such 5 and in lemma 4.5 we set Co Ci
1000
+ 1. Because in each round R R2,
?/2 T12
and St,r, S2,t vary by at most 1, if E! happens Alice chooses opt, and Bob chooses opt, with probability larger than 1 - 8 independently for the next
1000
+ rounds. Similar argument holds
for EZ21 We use the above observation to show lemma 4.6
Lemma 4.6. Given the game defined in theorem 4.1 for all and history H4 E/. we have E
Σ
"f1.44- r2.4+)) Ho S
-100.
This lemma formalizes the blue arrows in Fig. | With this lemma, we get the main result of step two.
Lemma 4.7. Given the game defined in theorem Pr sup, &l 2. V g2 =1] 1.
If we treat RI, R2, as money of Alice, Lemma 4.7 is similar to the gambler's ruin problem 77 More specifically, RI, R2 has a negative expected growth each 1000
71-72 1 + rounds by
Lemmal4.6, so R1, R2, will always become small enough to escape g1. Step 3: From Intermediate States Good Events
We define series of "good events" at first. For all E N+ and 1 2 1, (w) = [Ri, 2 u, and S1, 2 u) and E?? EZ:((u) = [R2, 2 u and S2, 2 u].
To the end, we want to show that Vien+ E.. E.'(())) (u) and VieN+ EIeN+E?2 e?: happen with probability for any E N+ Formally, we claim Lemma 4.8
Lemma 4.8. Given the game defined in theorem 4.1 for all there ex- ists Au so that for any T with history Ht (T4((++0))+100 c2.2 (u) = 1 HT
E
&
E
we have
T+1(a+00)+ 100 gl,1 (w)) V (V1 Pr Vi=T
2 A
This lemma generally says that when the agents are in an intermediate state that E V E = 1, they have a constant probability X get into good event in the next 4(u + cu) + 100 rounds. In order to prove this lemma, we define a nice event Pr such that Py happens with probability larger than X and Pr implies the good events happen in no more than 4(u + co) - 100 rounds. Formally, event Pr is defined as the following: First, for j = T...., Ti until some round Ti 2 T such that S1,,, 2 O, f.. Alice uses strategy opt,, Bob uses strategy opt. Then, Alice and Bob uses strategy opt, for 4u + 50 rounds and signals are generated as xJ+1 Uj+1 = -x, for j Ti. We can use Lemma 4.4 to prove that X, (min ( x 0.25 2)255)100+-00 100+4(u+e) a feasible lower bound.
Ty+1 = Пド My+1
Step 4: Good Events Lead to Truthful Convergence
Similar to step 2, we have lemma to show that & (u) can lead to increasing of R1, R2 at first. The idea is completely similar to Lemma 4.6 and it formalize the red arrows in Fig. [
8

---

Lemma 4.9. Given the game defined in theorem 4.1 for all u > 2cg + and if H E E7 (12)),
1+1
we have E
(ri,44j- r2,4+5)
He 2 100.
Using Lemma 4.9 we are able to prove that for any E, there exists a u such that when & (u) or (u) happens, Alice and Bob will tend to choose (pt, or (optz. opt2) with increasingly higher probability. Formally, we propose Lemma 4.10
Lemma 4.10. Given the game defined in theorem N+ such that given history HT T (u) V ET
for all
0 there have
ists E
c2 (u),
Pr
1000 1+1)+ (L +i) V E22 Vi ViEN, E T+ (T (T=)
(L + = 1 Hr 2 I -.
T+ (1 1800 1+1)+
T2
We design a sub-martingale {DiNeN that is proportional to 1+1) and use Azuma-Hoeftding inequality to prove lemma
R 11T+ 71-12 1+1)
2 R
4.10
1000 71 12-12
5 Simulations
We simulate the CA mechanism with various learning algorithms: the Hedge algorithms, follow the perturbed leader, follow the leader, and e-greedy, and repeat the process 400 times with 800 rounds on each algorithm each time. We define the converge proportion in round simulations where both agents report truthfully opt, (or both use opt,) in all the subsequent rounds.
the fraction of the
In simulations, Px.y(0,0) = Px, = 0.4, (1,) = Px,y (0, = 0.2. Morcover, Alice and Bob using the same learning algorithms in simulations that are listed below: First, Follow the Leader algorithm (FTL) chooses opt, with probability proportional to TI Ri; = max ( Rı, R2, R3, Ra)] Follow the perturbed leader (FPL*, where can be 1, 4 or 8) adds uniform random noise between 0
the following private signal distribution that satisfies assumption 2.2
and and choose strategy opt; with probability Pr R; + p: max (R, + P3} Pj lid 21 We consider FPI.1, FPL4, and FPL.8 Hedge algorithm choose with probability proportional to / that is an implementation by choosing et al. (2). Hedge algorithm 2 chooses i with probability proportional to e. that is an implementation of exponentially weighted averaged forecaster introduced by Freund and Schapire 1
0.5 for the multiplicative weights algorithm of Arora
by choosing [10]. Finally, e-greedy algorithm uses time varying c (e-1)a at round t. Note that e-greedy is not in A but still achieves truthful convergence.
In Figure 2 all our algorithms converge to truth-telling. First, all aoward-based online learning algorithms (the Hedge algorithms, follow the perturbed leader, and follow the leader) exhibit truthful convergence that aligns with our theoretical result, theorem Moreover, although FTL is generally not no-regret, CA mechanism still works well with it. Additionally, we observe that when an algorithm explores less (e.g. FPL4 vs FPL8). converges faster, but very little exploration does not further improve the convergence rate (e.g. FTL vs FPL2). Finally, we also find that the e-greedy with time decreasing e, which is not a reward-based online learning algorithm, also shows truthful convergence. This suggests that the CA mechanism may have truthful convergence beyond reward- -bsed online learning algorithms.
6 Conclusions
In this paper, we study sequential peer prediction with learning agents and prove that the notion of no-regret alone is not sufficient for truthfuul convergence. We then define family of reward-based learning algorithms and show that the CA mechanism is able to achieve truthful convergence when agents use algorithms in this family. Finally, give a discussion the converge rates of different learning agents based on simulations.
This is the first theoretical study peer prediction with learning agents. There are many open problems and future directions to extend this work. We believe similar proof techniques can be used to extend our results to settings where agents' private signals are generated by Markov chain with

---

fT.
Haage Agurtina
Figure 2: Convergence Rates of Learning Algorithms in CA.
some assumptions on the transition matrix. Moreover, this work only restricted to binary signals and it is still an open problem whether there exists mechanism for non non-binary settings that can promise truthful convergence. For the learning agents, one could consider more general family of learning algorithms such as when f is tame-varying.
Acknowledgments and Disclosure of Funding
The authors would like to thank the anonymous reviewers for their valuable comments and construc- tive feedback. This work is partially supported by the National Science Foundation under Grant No. IIS 2007887 and by the National Science Foundation and Amazon under Grant No. FAI 2147187.
References
[1] N. Alon and J. Spencer. The probabilistic method. John Wiley & Sons, 2016.
[2] S. Arora, F. Hazan, and S. Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of computing. 8(1):211164, 2012.
[3] M. Braverman, Mao, J. Schneider, and S. M. Weinberg. Selling a no-regret buyer. CoRR. 0bs/1711.09118/ 2017. URI. http::ttt::/aatteee http///axvvvv.. http://bb//111111/ 09176
[4] M. K. Camara, J. D. Hartline, and A. Johnsen. Mechanisms for no-regret agent: Beyond the common prior. 2020 IEEE 6l Anmull Symposium on Foundations of Computer Science (FOCS), pages 259-270. IEEE, 2020.
[5] A. Dasgupta and A. Ghosh. Crowdsourced judgement elicitation with endogenous proficiency. In Proceedings of the 22nd international conference on World Wide Web, pages 319-330, 2013.
[6] Y. Deng, J. Schneider, and B. Sivan. Strategizing against no-regret learners. Advances in neural information processing systems, 32, 2019.
[7] R. A. Epstein. The theory of gambling and statistical logic. Academic Press, 2012.
[8] B. Faltings, R. Jurca, P. Pu, and B. D. Tran. Incentives to counter bias in human computation.
In Second AAAI conference on human computation and crowdsourcing, 2014.
[9] W. Feller. An introduction to probability theory and its applications, vol 2. John Wiley & Sons, 2008.
[10] Y. Freund and R. E. Schapire. A decision-theoretii generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-139, 1997.
[11] J. Hannan. Approximation to bayes risk in repeated play. Contributions to the Theory of Games, 3(2):97-139, 1957.
[12] A. Kajii and S. Morris. The robustness equilibria to incomplete information. Econometrica: Journal of the Econometric Society, pages 1283-1309, 1997.
10

---

[13] A. Kalai and S. Vempala. Efficient algorithms for online decision problems. Computer and System Sciences, 71(3):291-307, 2005.
Journal of
[14] V. Kamble, Shah, D. Marn, A. Parekh, and K. Ramachandran. Truth serums for massively crowdsourced evaluation tasks. arXiv preprint arXiv: arXiv:1507.07045, page 96, 2015.
[15] Y. Kong. Dominantly truthful multi-task peer prediction with constant number of tasks. CORR, abs/1911.0007. 2019. URL http:://arxd..orr/aas//////3
[16] Y. Kong and G. Schoenebeck, Equilibrium selection in information elicitation without verifica- tion via information monotonicity. arXiv preprint arXiv:1603.0075:. 2016.
[17] Y. Kong and G. Schoenebeck. A framework for designing information elicitation mechanisms that reward truth-tellingg CoRR, abs/1605.01021, 2016. 01021
wttpxivvorggabb//100000 abs/ab/s
[18] Y. Liu and Chen. Surrogate scoring rules and a dominant truth serum for information elicitation. arXiv preprint arXIv:1802.09158, 2018.
[19] N. Miller, P. Resnick, and R. Zeckhauser. Eliciting informative feedback: The peer-prediction method. Management Science, 1359))93319-333333 2005.
[20] D. Prelec. A bayesian truth serum for subjective data. science, 306(5695):462-466, 2004.
[21] D. Prelec, H. S. Seung, and J. McCoy. A solution to the single-question crowd wisdom problem. Nature, 541(7638):532-538 2017.
[22] G. Radanovic and B. Faltings. Incentives for truthful information elicitation of continuous signals. In Proceedings of the Twenty-Lighth AAAI Conference on Arlificial Intelligence, pages 770-776, 2014.
[23] G. Schoenebeck and Yu. Learning and strongly truthful multi-task peer prediction: A variational approach. CoRR, abs/2009.14730. 2020. URL htl.Lattee///axiiooo///b//////
14730
[24] G. Schoenebeck, F.-Y. Yu, and Y. Zhang. Information elicitation from rowdy crowds. In Proceedings of the Web Conference 2021, pages 3974-3986, 2021.
[25] V. Shnayder, A. Agarwal, M. Frongillo, and C. Parkes. Informed truthfulness in multi-task peer prediction. CORR, abs/1600.0315) 2016. UtL.http://ariin brg/abs///e 1163..66... 03151
[26] V. Shnayder, R. Frongillo, and D. C. Parkes. Measuring performance of peer prediction mechanisms using replicator dynamics. Proceedings of the Twenty-Fifih International Joint Conference Artificial Intelligence, 2016.
[27] Witkowski and D. C. Parkes. A robust bayesian truth serum for small populations. In Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012.
[28] S. Zheng, F. Yu, and Y. Chen. The limits of multi-task peer prediction. CoRR, abs/2106.03176 2021. URL : //t:///aaivaa www.ii.oog/abbaa.. wtgg/bs////.....o.//////// 03176.


Reviews:
[{"review_id": "hpTwjbrGtmr", "reviewer": "Reviewer_sA5q", "summary": "This paper considers the sequential peer prediction setting when the participants are learning agents. In particular, the authors ask the following question — if a peer prediction mechanism is used to reward the learning agents, then under what conditions they converge to truthful reporting. The first result shows that some no regret learning mechanisms might fail to converge to truthful reporting. This is because the agents can construct a no-regret sequence of reports irrespective of their private signals.\n\nThe main contribution lies in showing that convergence to truthful strategies is possible if imposes certain assumptions on the no-regret learning algorithms. Fortunately, this class includes standard no-regret learning algorithms like Hedge, FPL etc. In particular, the main result shows that if the designer uses correlated agreement mechanism, and the joint distribution over the signals satisfy positive correlation, then convergence to truthful strategy is possible.  ", "questions": "Some questions for the authors.\n- Does the current proof work with bandit feedback e.g. what happens if one agent doesn't observe the other agent's reported signal and only receives the scores?\n- In simulation, all the mechanisms eventually converge to truthful reporting. Is it possible to empirically show that there exists some mechanism which does not converge? I understand the existence of such a mechanism was shown using the probabilistic method, so it might not be possible to empirically show the existence of such a mechanism.", "limitations": "This paper doesn't have any negative societal impact.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths:\n- I think it is an interesting problem to address the convergence of learning algorithms under peer prediction based payment mechanisms. Prior work has empirically studied convergence properties of learning algorithms, and to the best of my knowledge, this paper proves convergence to truthful strategy for the first time.\n- I found the analysis of the convergence proof quite interesting and non-trivial. The authors also clearly explained different steps involved in the proof.\n\nWeaknesses:\n- The setting only considers binary signal setting and that certainly makes the analysis easier.\n- My other criticism is regarding the setting. If the designer knows that the agents will use a learning algorithm then the designer doesn’t have to use CA mechanism every round. Since all the tasks are identically distributed the designer can eventually learn the prior distribution and might not even need peer prediction mechanism. Is this observation accurate or am I missing something here?\n- Finally, the proof assumes full information feedback setting. This is because an agent (say Alice) can observe Bob’s signal and can compute exact payment under a different strategy. However, in practice e.g. in rating platforms, people just receive their score for a report. So the learning algorithms must run with bandit feedback. I think this is the main limitation of the current paper.\n\nSome other comments:\n- Section 2 introduces the concept of rank k mechanism. Is this definition used anywhere? I understand that CA is a rank-2 mechanism, I am not sure if k > 2 is used anywhere. If not, it might be a good idea to avoid this definition.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "e_JpNpqUNhc", "reviewer": "Reviewer_ikCW", "summary": "This paper aims to theoretically analyze the dynamics of sequential peer prediction mechanisms, especially when participants are learning agents. To achieve this goal the authors firstly analyze the limitation of the notion no regret, that is, even no regret algorithms may also not converge. Then, the authors put their focus on a specific type of algorithms, where the policy is updated only based on the agents' cumulative rewards. In the experiments, the authors have conducted many simulation studies to demonstrate the effectiveness of their model.", "questions": "See the Strengths And Weaknesses ", "limitations": "Yes, the authors have discussed the limitations of their model.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nTo be honest, the topic of this paper is too far from my research domains. I can only make evaluations based on my general knowledge. In general, I think the paper is very well written, the organization is comfortable and compact. The studied problem seems to be important. Extending traditional static information elicitation mechanisms to sequential settings is important and should be more practical in real-world problems. The theory seems to be sound, which can well support their claims. \nMy concerns are as follows: (1) it could be better if there are some real-world experiments. (2) If the sequence is too long, whether the error produced from the former steps influence much on the following steps.\n\nAs mentioned before, my background does not fit this paper, thus if other reviewers have negative opinions, I can change my score.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Q_VZXm1fJGY", "reviewer": "Reviewer_CRBk", "summary": "This paper studies a sequential reporting problem where two agents are incentivized via payments to report back a private signal each of them receives. While this problem has been studied under strong assumptions in the Bayesian setting, the authors are the first to study this problem when the two agents are learners and can update their actions to reflect what they have learned about the rewards based on this history so far. The author’s show that no-regret learning on its own is too weak a notion for any algorithm to incentivize truth-telling in the limit. But, the main punchline of the paper is that for a large class of natural learning algorithms based on reward updating (included in this class are several no-regret algorithms such as multiplicative weights and follow-the-leader), truthful peer prediction is indeed possible using a classic scheme (CA) that (to my understanding) incentivizes agreement between the two agents. This phenomenon is also demonstrated via an experiment.", "questions": "Line 97-98: State that X_t and Y_t denote random variables, and x_t and y_t are their realizations.\n\nSection 2 would benefit from some more intuition and motivation. For example the “correlated agreement mechanism” is new to me, and a sentence or two on why it is important/intuitive in this setting would have been helpful.\n\nLines 116-118: the remark about multi-task information elicitation is confusing to someone who doesn’t already know what this is.\n\nLines 120-130: I found it difficult to understand the reasoning behind this setup. Why are the four actions defined as they are? If a strategy is a distribution over these four action that depends on the history of signals, isn’t it equivalent to let the set of actions be {0,1}, and then a strategy would be a mapping into the set of distributions on {0,1} that depends on the history/knowledge so far? I’m not able to see the need to have four distinguished options as they are defined currently, so if this is an important assumption the reason for it should be greatly clarified.\n\nLine 152: “permutation equilibrium” (which I don’t think is a standard solution concept) has not been defined. \n\nLines 157-159: My understanding is that the goal is to design algorithms to incentivize truthful reporting. I roughly understand that if both agents converge to opt_2 (fully mis-reporting), then the algorithm can be “flipped” to revert back to truthful reporting. But I think this needs more elaboration. How exactly can this be done with a single bit of “whether the prior of 0 is larger than 1”? There hasn’t been any discussion of priors/beliefs at this point. Also, would this allow for Defn 2.3 to wlog only include opt_1? If so that might be a more intuitive way to write the condition.\n\nIn assumption 3.3 should it be “nondecreasing” rather than “nonincreasing”? An intuitive explanation in words of what f and the assumptions mean would be helpful, though the instantiation for Multplicative weights is helpful.\n\nLine 222: say that FPL is follow the perturbed leader.\n\nGeneral stylistic comments: many grammatical errors throughout. Avoid forward references (e.g. line 163).\n", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Given that the CA scheme plays such an important role in the main results of the paper, I would have liked to see more discussion on (1) why it is important (2) what it means. It seems to reward one agent when the other agent changes her prediction to agree with that agent. But as far as I could tell there was no further discussion on this.\n\nAlso, more discussion on the class of reward-based learning algorithms would have been helpful, as this is the main condition posed by the authors as a fix to the unrealistic behavior that is possible under only a no-regret assumption. Why, intuitively, does this fix those issues? Can’t agents still collude in this model? To me it seems like the idea of reward updating a neat one, but its presentation is opaque: what do the axioms (assumptions 3.2-3.4) mean in plain language? Why use these specific axioms? \n\nThe analysis of the stochastic process induced by CA and the learning agents is an interesting technical contribution, though I did not read the proofs in detail. \n\nI think the overall contribution is quite interesting and nicely fills in a gap in the peer-prediction literature (agents that learn is an important wrinkle being studied in various settings), but I think the main weakness of this paper is its presentation. I found concepts to be introduced in an ad-hoc manner without much discussion on how things connected (specific examples in the “Questions” section). \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-jAkpui0x3y", "reviewer": "Reviewer_NE2Q", "summary": "This paper considers the problem of multi-task peer prediction where the goal is to elicit truthful information from agents using a scoring mechanism that scores agents based on their joint reports. It connects this problem of multi-task peer prediction to online no-regret learning by considering agents that learn to manipulate their reports in order to maximize their scores. The paper considers a special case of two agents and binary signal/reports and formulates the problem as a two-player repeated game. The paper shows that given any scoring mechanism there exist no-regret algorithms for agents which do not converge to truthful reporting. The paper then considers the CA mechanism which is a well-known mechanism for peer prediction and shows that a large class of learning algorithms converge to truthful reporting. This large class includes several no-regret algorithms such as Hedge, FPL etc. The paper also shows empirically that many popular online learning algorithms converge to truthful reporting.  ", "questions": "1. Do the results presented in this paper extend to the case of multiple agents? It is not clear how to define a learning scenario for multiple agents and define the CA mechanism under such a learning scenario. \n\n2. It would be very interesting to see if the results in this paper can be extended to the case of non-binary signal/reports?\n\n3. It would also be interesting to understand necessary conditions that result in truthful convergence of learning algorithms under the CA mechanism.", "limitations": "I do not foresee any negative societal impact of this paper.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: I think that this paper provides a significant contribution to the burgeoning literature on mechanism design for learning agents. The problem of peer prediction is an important problem in information elicitation and is well-motivated due to various applications in crowdsourcing. The paper initiates a study of the dynamics of learning under this important problem and provides several non-trivial results.\n\nWeakness: The paper considers a very simple setting with two agents and binary reports. Nevertheless, I think that this simple setting lays a solid foundation to build upon in the future.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept