Research map / Learning theory and algorithms / Submodular and game algorithms
Peer Neighborhood Mechanisms: A Framework for Mechanism Generalization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends Peer Consistency mechanisms (via Peer Truth Serum) to arbitrary continuous distributions using random partition families and a neighborhood-matching payment, with update conditions for incentive compatibility and simulations.
Problem
Peer prediction mechanisms are restricted to categorical distributions because they rely on exact report matching; extending them to arbitrary distributions has relied on structural assumptions or known agent properties.
Approach
Replace exact matching with neighborhood matching: reports are compared via bins from a randomly selected partition family, and the Peer Truth Serum payment is averaged over partitions. Incentive compatibility holds under Partition-Invariant or Partition-Expected belief-update conditions, which admit continuous (pyramid) kernels that converge.
Key results
- Theory shows the Peer Truth Neighborhood Extension is incentive-compatible under PI/PE update conditions, and PE admits continuous pyramid kernels that are convergent.
- Proves that for regular partition spaces on R^2, no bin-bounded continuous update kernel can satisfy PI while admitting a convergent update sequence.
- Simulations show expected payment from the agent's posterior is maximized at truthful report; smaller bins yield higher payment variance.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Peer Neighborhood extension of Peer Truth Serum | PTNE · Report perturbation simulations | expected payment | Helped |
| Evaluate payments against truthful Peer reports sampled from the true distribution | PTNE · Report perturbation simulations | expected payment | Mixed |
| Reduce partition bin size | PTNE · Payment stability simulations | payment variance | Hurt |
Surprising findings
- Under the Partition-Invariant condition, continuous update kernels cannot be both PI-satisfying and convergent in dimensions above one.
- From the Center's perspective over truthful peer reports, the expected payment is not necessarily maximized at the observation, due to public prior mismatch.
Limitations
- PI condition is impossible for continuous kernels in d>1 with convergence, so the relaxed PE condition is needed.
- Evaluation is only synthetic simulations with 1D and 2D distributions.
- Public prior mismatch with true distribution can make the Center-side payment non-truthful-maximizing (ex-post).
Experimental setup
Datasets: synthetic empirical distributions synthetic Gaussian mixture distributions
Metrics: expected payment payment variance
Baselines: Peer Truth Serum Logarithmic Peer Truth Serum Bayesian Truth Serum
Builds on: Peer Truth Serum Output Agreement Logarithmic Peer Truth Serum
Closest papers by meaning
- Carrot and Stick: Eliciting Comparison Data and Beyond (NeurIPS 2024 · similarity 0.84)
- DICE: Data Influence Cascade in Decentralized Learning (ICLR 2025 · similarity 0.84)
- Stochastically Dominant Peer Prediction (NeurIPS 2025 · similarity 0.84)
- A Cramér–von Mises Approach to Incentivizing Truthful Data Sharing (NeurIPS 2025 · similarity 0.83)
- MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation (ICML 2024 · similarity 0.83)
- Evaluating LLM-contaminated Crowdsourcing Data Without Ground Truth (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.