# Online Learning for Measuring Incentive Compatibility in Ad Auctions

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jan 2019.

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

- [Neural Auction: End-to-End Learning of Auction Mechanisms for E-Commerce Advertising](https://mlsanity.com/paper/2106.03593/) (2021)
- [Stochastic Bandits for Multi-platform Budget Optimization in Online Advertising](https://mlsanity.com/paper/2103.10246/) (2021)
- [Online Stackelberg Optimization via Nonlinear Control](https://mlsanity.com/paper/2406.18805/) (2024)
- [An Analysis of Selection Bias Issue for Online Advertising](https://mlsanity.com/paper/2206.03853/) (2022)
- [EdgeNet : Encoder-decoder generative Network for Auction Design in E-commerce Online Advertising](https://mlsanity.com/paper/2305.06158/) (2023)

## Abstract (arXiv)

In this paper we investigate the problem of measuring end-to-end Incentive Compatibility (IC) regret given black-box access to an auction mechanism. Our goal is to 1) compute an estimate for IC regret in an auction, 2) provide a measure of certainty around the estimate of IC regret, and 3) minimize the time it takes to arrive at an accurate estimate. We consider two main problems, with different informational assumptions: In the advertiser problem the goal is to measure IC regret for some known valuation v, while in the more general demand-side platform (DSP) problem we wish to determine the worst-case IC regret over all possible valuations. The problems are naturally phrased in an online learning model and we design Regret-UCB algorithms for both problems. We give an online learning algorithm where for the advertiser problem the error of determining IC shrinks as OBig(frac|B|T·Big(fracln Tn + √fracln TnBig)Big) (where B is the finite set of bids, T is the number of time steps, and n is number of auctions per time step), and for the DSP problem it shrinks as OBig(frac|B|T·Big( frac|B|ln Tn + √frac|B|ln TnBig)Big). For the DSP problem, we also consider stronger IC regret estimation and extend our Regret-UCB algorithm to achieve better IC regret error. We validate the theoretical results using simulations with Generalized Second Price (GSP) auctions, which are known to not be incentive compatible and thus have strictly positive IC regret.