Truthful Reporting of Competence with Minimal Verification

1. Problem Definition

The paper addresses a mechanism design problem where a principal (e.g., an instructor, auditor, or regulator) needs to assign grades or compensation to $N$ self-interested agents based on their reported competence (type) $t_i \in [0, 1]$.

• The Conflict: Agents prefer higher grades and have an incentive to misreport their true type $\hat{t}_i > t_i$.
• The Constraint: The principal has limited verification capabilities. They can select a subset of agents to audit (verify) their true performance.
• The Goal: Design a mechanism that minimizes two competing objectives:
  1. Verification Cost: The expected proportion of agents audited.
  2. Bias: The difference between the expected grade and the true competence ($\bar{g}_t - t$). The authors aim to minimize this bias while ensuring truthful reporting.
• Hard Requirements:
  • HR1 (Dominant Strategy): Truth-telling must be a weakly dominant strategy.
  • HR2 (No Punishment of Truth-tellers): A truthful agent must never receive a grade lower than their true competence, even if others lie.
  • HR3 (Limited Liability): Grades cannot fall below a certain negative threshold $-\xi$ (where $\xi \ge 0$). If $\xi=0$, the principal cannot punish agents financially beyond disqualification.

2. Methodology and Mechanisms

The authors analyze two distinct scenarios: Deterministic Verification (audits reveal the true type with certainty) and Noisy Verification (audits return a random sample with the true type as the mean).

A. Deterministic Verification: Monotone-Cutoff Verification (MCV)

The authors introduce the MCV class of mechanisms, parameterized by a cutoff $\gamma \in [0, 1]$.

• Mechanism Logic:
  • Verification Probability: An agent reporting $\hat{t}_i$ is audited with probability $q(\hat{t}_i) = \frac{\hat{t}_i - \gamma}{\hat{t}_i + \xi}$ if $\hat{t}_i > \gamma$, and $0$ otherwise.
  • Grading:
    • If not audited: The agent receives $\max(\hat{t}_i, \gamma)$.
    • If audited: If the report matches the result, they get $\hat{t}_i$; otherwise, they receive a penalty of $-\xi$.
• Key Property: This mechanism creates a "cutoff" where agents with low reports are effectively capped at $\gamma$ without risk, while high reporters face increasing audit probabilities.
• Optimality: The authors prove that the MCV class constitutes the Pareto frontier (efficiency boundary). For any valid mechanism, there exists an MCV mechanism that weakly dominates it (lower verification cost and/or lower bias).
• Unknown Distribution: Even if the type distribution $p$ is unknown, the authors propose an Agent-Specific MCV (AS-MCV). Each agent is assigned a mechanism based on the empirical distribution of other agents. This guarantees the bias is within an additive $O(1/N)$ of the optimal bias achievable with known distributions, without increasing verification costs.

B. Noisy Verification: Scoring Rules

When verification is noisy ($s_i \sim T_i$ where $E[s_i] = t_i$), deterministic penalties fail because truthful agents might be falsely penalized (violating HR2). The authors relax HR2 to require truth-tellers to be rewarded in expectation.

• Approach: The mechanisms leverage Proper Scoring Rules (specifically semi-power rules) to align incentives. The expected grade is constructed to be a strictly convex function of the report, maximizing expected utility only when the report equals the true type.
• Linear Verification (LV): A simple mechanism where audit probability is linear in the report ($q = \hat{t}_i$). It uses a semi-quadratic scoring rule.
• Polynomial Verification (PV): A more flexible family parameterized by an integer $\kappa$ and a scaling factor $\theta$.
  • As $\kappa \to \infty$, the bias approaches zero.
  • The mechanism balances the trade-off between verification cost and bias by tuning $\kappa$ and $\theta$ subject to the liability constraint $\xi$.
• Histogram Mechanism (Special Case): If the principal knows the exact histogram of true types (a strong assumption), they can construct a mechanism with a unique Nash equilibrium where no verification is required and bias is arbitrarily small, even with noisy verification. This relies on detecting deviations from the known population distribution.

3. Key Contributions

1. Characterization of Optimal Trade-offs (Deterministic): The paper provides a complete characterization of the optimal trade-off between verification cost and bias under deterministic verification. The MCV mechanism is proven to be efficient (Pareto optimal) for any type distribution.
2. Robustness to Unknown Distributions: The AS-MCV mechanism demonstrates that near-optimal performance can be achieved without prior knowledge of the type distribution, relying only on the observed reports of peers.
3. Extension to Noisy Verification: The paper extends the problem to noisy verification, a significantly harder setting. It introduces mechanisms based on proper scoring rules that maintain truthfulness and limited liability, offering a new family of solutions (PV) that trade off verification cost against bias via the parameter $\kappa$.
4. Theoretical Bounds: The authors establish that under limited liability ($\xi=0$) and deterministic verification, zero bias is impossible without verifying every agent (unless the distribution has no mass at 0).

4. Results and Empirical Evaluation

The authors validate their theoretical findings using synthetic data (Beta distributions) and real-world datasets (SAT scores and FICO credit scores).

• Efficiency Curves: Plots of Bias vs. Verification rate show that MCV mechanisms significantly outperform simple baselines (like "Verify All" or "Pay All").
• Distribution Sensitivity: The mechanisms perform better on distributions with lower variance (e.g., SAT scores, FICO) compared to uniform distributions. For example, on SAT data, they can achieve an expected bias of <5% while auditing only 20% of agents.
• Noisy Setting: In the noisy setting, the Polynomial Verification (PV) mechanisms allow for bias reduction by increasing $\kappa$, though this requires allowing for negative grades (penalties) to satisfy the scoring rule properties.
• Comparison: The PV mechanisms provide a strong baseline for noisy settings, though the authors note that finding the absolute optimal trade-off in the noisy case remains an open challenge.

5. Significance

This paper makes a significant contribution to Mechanism Design and Game Theory by addressing a practical gap: how to incentivize truthful reporting when verification is costly and imperfect.

• Practical Relevance: The model applies directly to real-world scenarios like tax auditing, academic grading, performance reviews, and insurance claims, where principals cannot verify everyone but must prevent systematic inflation of claims.
• Theoretical Insight: It bridges the gap between classical mechanism design (which often assumes full verification or monetary transfers) and modern auditing constraints. The use of "cutoff" mechanisms and the adaptation of scoring rules for noisy environments provide new tools for designing robust incentive systems.
• Limitations & Future Work: The paper acknowledges that the "Histogram Mechanism" relies on strong prior knowledge. Future work is needed to tighten approximation bounds for the noisy verification setting and to explore multi-dimensional types.