Dominant Truthful Multi-task Peer Prediction Mechanism with a Constant Number of Tasks

A Google TechTalk, 2020/01/16, presented by Yuqing Kong (Peking University) ABSTRACT: Title: Dominantly Truthful Multi-task Peer Prediction with a Constant Number of Tasks Abstract: In the setting where participants are asked multiple similar \emph{possibly subjective} multi-choice questions (e.g. Do you like Panda Express? Y/N; do you like Chick-fil-A? Y/N), a series of peer prediction mechanisms are designed to incentivize honest reports and some of them achieve dominantly truthfulness: truth-telling is a dominant strategy and strictly dominate other ``non-permutation strategy'' with some mild conditions. However, a major issue hinders the practical usage of those mechanisms: they require the participants to perform an infinite number of tasks. When the participants perform a finite number of tasks, these mechanisms only achieve approximated dominant truthfulness. The existence of a dominantly truthful multi-task peer prediction mechanism that only requires a finite number of tasks remains to be an open question that may have a negative result, even with full prior knowledge. This paper answers this open question by proposing a new mechanism, Determinant based Mutual Information Mechanism (DMI-Mechanism), that is dominantly truthful when the number of tasks is at least 2C. C is the number of choices for each question (C=2 for binary-choice questions). DMI-Mechanism also pays truth-telling higher than any strategy profile and strictly higher than uninformative strategy profiles (informed truthfulness). In addition to the truthfulness properties, DMI-Mechanism is also easy to implement since it does not require any prior knowledge (detail-free) and only requires at least two participants. The core of DMI-Mechanism is a novel information measure, Determinant based Mutual Information (DMI). DMI generalizes Shannon's mutual information and the square of DMI has a simple unbiased estimator. In addition to incentivizing honest reports, DMI-Mechanism can also be transferred into an information evaluation rule that identifies high-quality information without verification when there are at least three participants. To the best of our knowledge, \dmi-Mechanism is both the first detail-free informed-truthful mechanism and the first dominantly truthful mechanism that works for a finite number of tasks, not to say a small constant number of tasks. Bio: Yuqing Kong is currently an assistant professor at the Center on Frontiers of Computing Studies (CFCS), Peking University. She obtained her Ph.D. degree from the Computer Science and Engineering Department at University of Michigan in 2018 and her bachelor degree in mathematics from University of Science and Technology of China in 2013. Her research interests lie in the intersection of theoretical computer science and the areas of economics: information elicitation, prediction markets, mechanism design, and the future applications of these areas to crowdsourcing and machine learning. Her papers were published in several conferences and journals include WINE, ITCS, EC, AAAI, ICLR, NeurIPS, SODA, TEAC.