In the setting where we ask participants multiple similar possibly subjective multi-choice questions (e.g. Do you like Bulbasaur? Y/N; do you like Squirtle? Y/N), peer prediction aims to design mechanisms that encourage honest feedback without verification. A series of works have successfully designed multi-task peer prediction mechanisms where reporting truthfully is better than any other strategy (dominantly truthful), while they require an infinite number of tasks. A recent work proposes the first multi-task peer prediction mechanism, Determinant Mutual Information (DMI)-Mechanism, where not only is dominantly truthful but also works for a finite number of tasks (practical). However, the existence of other practical dominantly-truthful multi-task peer prediction mechanisms remains to be an open question. This work answers the above question by providing 1. a new family of information-monotone information measures: volume mutual information (VMI), where DMI is a special case; 2. a new family of practical dominantly-truthful multi-task peer prediction mechanisms, VMI-Mechanisms. To illustrate the importance of VMI-Mechanisms, we also provide a tractable effort incentive optimization goal. We show that DMI-Mechanism may not be not optimal but we can construct a sequence of VMI-Mechanisms that are approximately optimal. The main technical highlight in this paper is a novel geometric information measure, Volume Mutual Information, that is based on a simple idea: we can measure an object A's information amount by the number of objects that is less informative than A. Different densities over the object lead to different information measures. This also gives Determinant Mutual Information a simple geometric interpretation.
翻译:在这样的背景下,我们向参与者提出许多可能相似的主观多选择问题(例如,你喜欢Bulbasaur吗?Y/N;你喜欢Squirtle?Y/N);同侪预测的目的是设计一些机制,鼓励不核查的诚实反馈。一系列工作成功地设计了多任务同行预测机制,其中诚实报告比任何其他战略好(主要真实),同时需要大量任务。最近的一项工作提出了第一个多任务同行预测机制,即确定性相互信息(DMI)-机械,其中不仅主要目的真实,而且用于有限数量的相互任务(实践性);然而,存在其他实用的主导性-真实性多任务预测机制,而不进行核查;一系列工作成功地设计了多任务同行预测机制,从而成功地报告(主要真实性)比其他战略(主要真实性)要好得多(主要任务),而DMI是一个实用的主宰性多任务同行预测机制, VMI-Me-新组不仅简单目标目标,而且用于有限数量的相互任务(实践性) 也能够说明一个最精确的测量度措施的重要性。