Consider a buyer participating in a repeated auction, such as those prevalent in display advertising. How would she test whether the auction is incentive compatible? To bid effectively, she is interested in whether the auction is single-shot incentive compatible—a pure second-price auction, with fixed reserve price, and also dynamically incentive compatible—her bids are not used to set future reserve prices. In this work we develop tests based on simple bid perturbations that a buyer can use to answer these questions, with a focus on dynamic incentive compatibility.
There are several potential A/B testing setups that one could use, but we find that many natural experimental designs are, in fact, flawed. We show that additive perturbations can lead to paradoxical results, where higher bids lead to lower optimal reserve prices. We precisely characterize this phenomenon and show that reserve prices are only guaranteed to be monotone for distributions satisfying the Monotone Hazard Rate (MHR) property. The experimenter must also decide how to split traffic to apply systematic perturbations. It is tempting to have this split be randomized, but we demonstrate empirically that unless the perturbations are aligned with the partitions used by the seller to compute reserves, the results will be inconclusive.
We validate our results with experiments on real display auction data and show that a buyer can quantify both single-shot and dynamic incentive compatibility even under realistic conditions where only the cost of the impression is observed (as opposed to the exact reserve price). We analyze the cost of running such experiments, exposing trade-offs between test accuracy, cost, and underlying market dynamics.
Joint work with A. Muñoz Medina, B. Sivan, and S. Vassilvitskii.
Sébastien Lahaie is a research scientist in the Market Algorithms groups at Google Research in New York City. He received his PhD in Computer Science from Harvard in 2007 and was previously a researcher at Yahoo and Microsoft. His research focuses on computational aspects of market design, with applications to search and display advertising. He has served as a co-editor for Economic Inquiry and was previously a program chair for the conference on Auctions, Market Mechanisms, and their Applications (AMMA).
*Light refreshments will be served at 2:30pm