Lune

SODA2020Top-tier venue

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

Yuqing Kong

Abstract

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 ≥ 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 (detailfree) and only requires ≥ 2 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 ≥ 3 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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

12 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Eliciting Thinking Hierarchy without a Prior cites Wisdom of the Crowd Voting: Truthful Aggregation of Voter Information and Preferences
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers12

  1. Truthful Data Acquisition via Peer PredictionYiling Chen, Yiheng Shen, Shuran ZhengNeurIPS 2020 · 35 citations
  2. Wisdom of the Crowd Voting: Truthful Aggregation of Voter Information and PreferencesGrant Schoenebeck, Biaoshuai TaoNeurIPS 2021 · 22 citations
  3. Incentivizing Truthful Language Models via Peer Elicitation GamesBaiting Chen, Tong Zhu, Jiale Han, Lexin Li et al.NeurIPS 2025 · 9 citations
  4. Eliciting Thinking Hierarchy without a PriorYuqing Kong, Yunqi Li, Yubo Zhang, Zhihuan Huang et al.NeurIPS 2022 · 9 citations
  5. Peer Prediction for Learning AgentsShi Feng, Fang-Yi Yu, Yiling ChenNeurIPS 2022 · 9 citations

Related papers

  1. Multitask Peer Prediction With Task-dependent StrategiesYichi Zhang, Grant SchoenebeckWWW 2023 · 7 citations
  2. Stochastically Dominant Peer PredictionYichi Zhang, Shengwei Xu, Grant Schoenebeck, David M. PennockNeurIPS 2025 · 2 citations
  3. Information Elicitation Mechanisms for Statistical EstimationYuqing Kong, Grant Schoenebeck, Biaoshuai Tao, Fang-Yi YuAAAI 2020 · 22 citations
  4. Information Elicitation from Rowdy CrowdsGrant Schoenebeck, Fang-Yi Yu, Yichi ZhangWWW 2021 · 18 citations
  5. Carrot and Stick: Eliciting Comparison Data and BeyondYiling Chen, Shi Feng, Fang-Yi YuNeurIPS 2024 · 5 citations
Dusk over the sea between two cliffs drawn in fine vertical lines