Strategyproof Mean Estimation from Multiple-Choice Questions

Anson Kahng, Gregory Kehne, Ariel D. ProcacciaICML 2020 · OpenReview

TL;DR

How do you accurately estimate the average of a population when you can only ask people multiple-choice questions? This paper provides a strategyproof framework for "coarse-grained" mean estimation, proving that while randomized estimators are asymptotically optimal in the worst case, incorporating prior knowledge makes Mean Squared Error (MSE) easy to minimize but makes Mean Absolute Error (MAE) computationally hard (#P-hard).

The Challenge of Coarse-Grained Estimation

Imagine you are on a university admissions committee. You need to know how many students will actually accept their offers so you don't over-enroll. Asking every applicant for an exact probability (e.g., "I am 74.2% likely to attend") is impractical—it’s a high cognitive load for the applicant, and they might not even know the exact number.

It is much easier to ask a multiple-choice question (MCQ): "How likely are you to attend? (Low/Medium/High)." However, this introduces two major challenges:

  1. Coarseness: You lose precision by bucketizing continuous values into discrete choices.
  2. Incentives: You need to ensure the questions are designed so that agents have no reason to lie (strategyproofness).

The authors tackle the problem of designing the best possible "classifier" (the questions/intervals) and "aggregator" (the function that turns answers into an estimate) to minimize estimation error.

Methods: Classifiers, Aggregators, and Random Shifts

The authors define a multiple-choice question as a partition of the $[0, 1]$ interval into $k$ sub-intervals. To ensure truthfulness, they rely on prior work showing that only interval-based choices are "elicitable." The paper explores two main scenarios:

1. Worst-Case Setting (No Priors)

When no prior information about the agents' values is known, the authors design a randomized estimator ($\bar{q}$). Instead of fixed intervals, this estimator uses "random shifts" for each agent. By injecting a small amount of independent randomness into the question thresholds, the estimator prevents an adversary from picking values that consistently fall at the edges of buckets, which would maximize error.

Illustration of random shifts applied to a point within a grid of intervals.

2. Setting with Priors

Here, the values are drawn from known discrete distributions.

  • For MSE: They show the problem decomposes. Finding the best intervals for the whole group is equivalent to finding the best intervals for each individual agent. This reduces to a one-dimensional $k$-means clustering problem, which is solvable in polynomial time via dynamic programming.
  • For MAE: The problem is much thornier. They prove that finding the optimal MAE estimator is #P-hard by reducing it to the problem of finding the median of a weighted sum of Bernoulli variables.

Evaluation and Key Insights

The paper evaluates the proposed algorithms using synthetic discrete distributions sampled from Uniform, Gaussian, and Bimodal families. The experiments compare the "Optimal" (prior-sensitive) estimator against a "Uniform" (naive) estimator to quantify the value of knowing the distribution beforehand.

Key Findings: * Randomization is a Power-Up: In the worst-case scenario, a deterministic estimator is stuck with an error that scales linearly with $n$ (the number of agents). By using randomized shifts, the authors achieve an MSE of $O(n/k^2)$ and an MAE of $O(\sqrt{n}/k)$, both of which are asymptotically optimal. * The MSE/MAE Split: One of the most striking findings is the computational divergence between error metrics. MSE is "well-behaved" because the variance of a sum of independent variables is just the sum of their variances. MAE doesn't have this additive property, leading to the #P-hardness result. * The Value of Priors: Empirical results show that the optimal prior-sensitive estimator significantly outperforms the naive uniform estimator. As the number of agents $n$ increases, the gap between the "smart" estimator and the "naive" one grows, proving that even coarse prior knowledge provides a significant edge in accuracy. * Structure of Truthfulness: The requirement for strategyproofness forces the multiple-choice options to be contiguous intervals. This geometric constraint is what allows the authors to use tools from quantization and clustering theory.

Limitations and Future Work

  • Known Priors: The current model assumes the distributions ($P_i$) are known upfront. The authors suggest a "learning" version of this problem where priors are discovered over multiple rounds of questioning.
  • Symmetric Error: The paper treats overestimation and underestimation as equally bad. In many real-world cases (like the admissions example), underestimating capacity might be much more expensive than overestimating it. Future work could explore asymmetric loss functions.
  • Beyond the Mean: The framework currently focuses on the sum/mean. Estimating other population statistics, such as the median or variance, from multiple-choice data remains an open challenge.

Summary updated

Abstract

Given n values possessed by n agents, we study the problem of estimating the mean by truthfully eliciting agents’ answers to multiple-choice questions about their values. We consider two natural ca...
BibTeX
@inproceedings{kahng2020strategyproof,
  author = {Anson Kahng and Gregory Kehne and Ariel D. Procaccia},
  title = {{Strategyproof Mean Estimation from Multiple-Choice Questions}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=U_JPulDq68l},
}
Figure