Learning and Strongly Truthful Multi-Task Peer Prediction: A Variational Approach

• URL: http://arxiv.org/abs/2009.14730v1
• Date: Wed, 30 Sep 2020 15:09:56 GMT
• Title: Learning and Strongly Truthful Multi-Task Peer Prediction: A Variational Approach
• Authors: Grant Schoenebeck and Fang-Yi Yu
• Abstract summary: We design a family of mechanisms with a scoring function that maps a pair of reports to a score. We show how to derive good bounds on the number of tasks required for different types of priors. This is the first peer-prediction mechanism on continuous signals designed for the multi-task setting.
• Score: 8.932080210400535
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Peer prediction mechanisms incentivize agents to truthfully report their signals even in the absence of verification by comparing agents' reports with those of their peers. In the detail-free multi-task setting, agents respond to multiple independent and identically distributed tasks, and the mechanism does not know the prior distribution of agents' signals. The goal is to provide an $\epsilon$-strongly truthful mechanism where truth-telling rewards agents "strictly" more than any other strategy profile (with $\epsilon$ additive error), and to do so while requiring as few tasks as possible. We design a family of mechanisms with a scoring function that maps a pair of reports to a score. The mechanism is strongly truthful if the scoring function is "prior ideal," and $\epsilon$-strongly truthful as long as the scoring function is sufficiently close to the ideal one. This reduces the above mechanism design problem to a learning problem -- specifically learning an ideal scoring function. We leverage this reduction to obtain the following three results. 1) We show how to derive good bounds on the number of tasks required for different types of priors. Our reduction applies to myriad continuous signal space settings. This is the first peer-prediction mechanism on continuous signals designed for the multi-task setting. 2) We show how to turn a soft-predictor of an agent's signals (given the other agents' signals) into a mechanism. This allows the practical use of machine learning algorithms that give good results even when many agents provide noisy information. 3) For finite signal spaces, we obtain $\epsilon$-strongly truthful mechanisms on any stochastically relevant prior, which is the maximal possible prior. In contrast, prior work only achieves a weaker notion of truthfulness (informed truthfulness) or requires stronger assumptions on the prior.

Related papers

• Refined Mechanism Design for Approximately Structured Priors via Active Regression [50.71772232237571]
  We consider the problem of a revenue-maximizing seller with a large number of items for sale to $n$ strategic bidders. It is well-known that optimal and even approximately-optimal mechanisms for this setting are notoriously difficult to characterize or compute.
  arXiv  Detail & Related papers  (2023-10-11T20:34:17Z)
• Deconstructing deep active inference [2.236663830879273]
  Active inference is a theory of perception, learning and decision making. The goal of this activity is to solve more complicated tasks using deep active inference.
  arXiv  Detail & Related papers  (2023-03-02T22:39:56Z)
• Pessimism meets VCG: Learning Dynamic Mechanism Design via Offline Reinforcement Learning [114.36124979578896]
  We design a dynamic mechanism using offline reinforcement learning algorithms. Our algorithm is based on the pessimism principle and only requires a mild assumption on the coverage of the offline data set.
  arXiv  Detail & Related papers  (2022-05-05T05:44:26Z)
• Understanding Interlocking Dynamics of Cooperative Rationalization [90.6863969334526]
  Selective rationalization explains the prediction of complex neural networks by finding a small subset of the input that is sufficient to predict the neural model output. We reveal a major problem with such cooperative rationalization paradigm -- model interlocking. We propose a new rationalization framework, called A2R, which introduces a third component into the architecture, a predictor driven by soft attention as opposed to selection.
  arXiv  Detail & Related papers  (2021-10-26T17:39:18Z)
• Consequences of Misaligned AI [12.879600368339393]
  This paper argues that we should view the design of reward functions as an interactive and dynamic process. We show how modifying the setup to allow reward functions that reference the full state or allowing the principal to update the proxy objective over time can lead to higher utility solutions.
  arXiv  Detail & Related papers  (2021-02-07T19:34:04Z)
• What can I do here? A Theory of Affordances in Reinforcement Learning [65.70524105802156]
  We develop a theory of affordances for agents who learn and plan in Markov Decision Processes. Affordances play a dual role in this case, by reducing the number of actions available in any given situation. We propose an approach to learn affordances and use it to estimate transition models that are simpler and generalize better.
  arXiv  Detail & Related papers  (2020-06-26T16:34:53Z)
• From Checking to Inference: Actual Causality Computations as Optimization Problems [79.87179017975235]
  We present a novel approach to formulate different notions of causal reasoning, over binary acyclic models, as optimization problems. We show that both notions are efficiently automated. Using models with more than $8000$ variables, checking is computed in a matter of seconds, with MaxSAT outperforming ILP in many cases.
  arXiv  Detail & Related papers  (2020-06-05T10:56:52Z)
• PeerNomination: Relaxing Exactness for Increased Accuracy in Peer Selection [30.779586758074206]
  In peer selection agents must choose a subset of themselves for an award or a prize. As agents are self-interested, we want to design algorithms that are impartial, so that an individual agent cannot affect their own chance of being selected. Here, we present a novel algorithm for impartial peer selection, PeerNomination, and provide a theoretical analysis of its accuracy.
  arXiv  Detail & Related papers  (2020-04-30T16:39:47Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
  arXiv  Detail & Related papers  (2020-04-19T18:00:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.