# Estimating Approximate Incentive Compatibility

arXiv: https://arxiv.org/abs/1902.09413 · HTML: https://mlsanity.com/paper/1902.09413/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Feb 2019.

## Built on by (most cited first, 7 of 7)

- [Data driven semi-supervised learning](https://mlsanity.com/paper/2103.10547/) (2021)
- [Learning Revenue-Maximizing Auctions With Differentiable Matching](https://mlsanity.com/paper/2106.07877/) (2021)
- [Data Distribution Valuation](https://mlsanity.com/paper/2410.04386/) (2024)
- [Automated Mechanism Design for Classification with Partial Verification](https://mlsanity.com/paper/2104.05182/) (2021)
- [Optimal Automated Market Makers: Differentiable Economics and Strong Duality](https://mlsanity.com/paper/2402.09129/) (2024)
- [Discovering Expert-Level Nash Equilibrium Algorithms with Large Language Models](https://mlsanity.com/paper/2508.11874/) (2025)
- [Learning to Coordinate Bidders in Non-Truthful Auctions](https://mlsanity.com/paper/2507.02801/) (2025)

## Abstract (arXiv)

In practice, most mechanisms for selling, buying, matching, voting, and so on are not incentive compatible. We present techniques for estimating how far a mechanism is from incentive compatible. Given samples from the agents' type distribution, we show how to estimate the extent to which an agent can improve his utility by misreporting his type. We do so by first measuring the maximum utility an agent can gain by misreporting his type on average over the samples, assuming his true and reported types are from a finite subset -- which our technique constructs -- of the type space. The challenge is that by measuring utility gains over a finite subset of the type space, we might miss type pairs θ and hatθ where an agent with type θ can greatly improve his utility by reporting type hatθ. Indeed, our primary technical contribution is proving that the maximum utility gain over this finite subset nearly matches the maximum utility gain overall, despite the volatility of the utility functions we study. We apply our tools to the single-item and combinatorial first-price auctions, generalized second-price auction, discriminatory auction, uniform-price auction, and second-price auction with spiteful bidders.