Dominantly Truthful Multi-task Peer Prediction with a Constant Number of Tasks
Dominantly Truthful Multi-task Peer Prediction with a Constant Number of Tasks
复制标题
任务数量恒定的显性真实多任务同行预测
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Yuqing Kong
中科院分区：
文献类型：
--
作者：
Yuqing Kong
在参与者被问到多个类似的可能是主观的多项选择问题的设置中（例如，你喜欢熊猫快递吗？你喜欢Chick-fil-A吗？Y/N），设计了一系列的同伴预测机制来激励诚实报告，其中一些实现了显性真实性：说真话是一种显性策略，并在一定的温和条件下严格优于其他“非排列策略”。然而，一个主要问题阻碍了这些机制的实际使用：它们要求参与者执行无限数量的任务。当参与者执行有限数量的任务时，这些机制只能实现近似的主导真实性。存在一个占主导地位的真实的多任务同行预测机制，只需要有限数量的任务仍然是一个悬而未决的问题，可能有一个负面的结果，即使有充分的先验知识。
本文回答了这个问题，提出了一个新的机制，基于决定因素的互信息机制（DMI机制），这是占主导地位的真实任务的数量至少是2C和参与者的数量至少是2。C是每个问题的选择数（对于二元选择题，C=2）。除了激励诚实的报告外，DMI-Mechanism还可以转换为信息评估规则，当至少有3个参与者时，该规则可以识别高质量的信息而无需验证。据我们所知，DMI-Mechanism是第一个适用于有限数量任务的主要真实机制，而不是一个小的恒定数量的任务。
In the setting where participants are asked multiple similar 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 and the number of participants is at least 2. C is the number of choices for each question (C=2 for binary-choice questions). 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 3 participants. To the best of our knowledge, DMI-Mechanism is the first dominantly truthful mechanism that works for a finite number of tasks, not to say a small constant number of tasks.