Understanding Peer Prediction Mechanisms in Learning Agents

Peer prediction mechanisms play a crucial role in soliciting high-quality information from human agents. This study explores the importance of peer prediction, the mechanisms involved in incentivizing truthful reporting, and the convergence of learning agents to truthful strategies. The Correlated Agreement (CA) mechanism and reward-based online learning algorithms are discussed in the context of ensuring agents' truthful reporting. The main theorem highlights how two agents using such algorithms converge to truthful reporting when the CA mechanism is adopted.

• Peer Prediction
• Learning Agents
• Correlated Agreement
• Truthful Reporting
• Online Learning

kulo967 Follow

Uploaded on Sep 25, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Peer Prediction for Learning Agents Shi Feng, Institute for Interdisciplinary Information Sciences, Tsinghua University Fang-Yi Yu, Department of Computer Science, George Mason University Yiling Chen, John A. Paulson School of Engineering and Applied Sciences, Harvard University NeurIPS 2022

2. Why we need peer prediction? Soliciting high-quality information from human agents!

3. 1. First terms of the CA mechanism encourage consensus. 2. Second terms discourage report always report 0 or always report 1. CorrelatedAgreement (CA) Mechanism1 CA mechanism guarantees strong truthfulness when agents are Bayesian! Pay ? ??= ?? ? ??= ?? 1for ? = 1,2,3, Pay ? ??= ?? ? ??= ?? 1for ? = 1,2,3, Principal Reports: ?1, ?2, ?3, Reports: ?1, ?2, ?3, Alice Bob Private Binary Signals: ?1,?2,?3, Private Binary Signals: ?1,?2,?3, Positive Correlated Distribution: ??,? 1. DASGUPTA, ANIRBAN, AND ARPITA GHOSH. "CROWDSOURCED JUDGEMENT ELICITATION WITH ENDOGENOUS PROFICIENCY." PROCEEDINGS OF THE 22ND INTERNATIONAL CONFERENCE ON WORLD WIDE WEB. 2013.

4. Learning Agents! In previous theoretical analysis, each agent is critically required to use a consistent mixed strategy over all rounds (Bayesian Agents). However, agents are learning in practice! Will agents converge to truthful strategy? Suppose each agent uses a reward-based online learning algorithm (section 3.2)in peer prediction. An agent s strategy in the tth round entirely depends on accumulated rewards of her feasible pure strategies. The function ? takes accumulated rewards as inputs and a mixed strategy as the output. ? satisfies exchangeability, order preservation, and full exploitation. E.g., Follow the Perturbed Leader (FPL), hedge algorithm, etc. No- best-in-hindsight regret assumption on agents is not enough (theorem 3.1). Truthful convergence requires agents to be no- best-in- hindsight regret under a strongly truthful mechanism (theorem 3.2).

5. MainTheorem (theorem 4.1) In a sequential peer prediction game with binary signals, when the CA mechanism is adopted, two agents using reward-based online learning algorithms always converge to truthful reporting (truth-telling or flip).

6. No-best-in-hindsight regret assumption on agents is not enough (theorem 3.1). Truthful convergence requires agents to be no- best-in- hindsight regret under a strongly truthful mechanism (theorem 3.2). MainTheorem (theorem 4.1) In a sequential peer prediction game with binary signals, when the CA mechanism is adopted, two agents using reward-based online learning algorithms always converge to truthful reporting (truth-telling or flip).

7. Thank you! NeurIPS 2022 Slides Live Paper Video