Envy, Regret, and Social Welfare Loss

The Web Conference


Incentive compatibility (IC) is a desirable property for any auction mechanism, including those used in online advertising. However, in real world applications practical constraints and complex environments often result in mechanisms that lack incentive compatibility. Recently, several papers investigated the problem of deploying black-box statistical tests to determine if an auction mechanism is incentive compatible by using the notion of IC-Regret that measures the regret of a truthful bidder. Unfortunately, most of those methods are costly, since they require the execution of many counterfactual experiments.

In this work, we show that similar results can be obtained using the notion of IC-Envy. The advantage of IC-Envy is its efficiency: it can be computed using only the auction’s outcome. In particular, we focus on position auctions. For position auctions, we show that for a large class of pricing schemes (which includes e.g. VCG and GSP), IC-Envy ≥ IC-Regret (and IC-Envy = IC-Regret under mild supplementary conditions). Our theoretical results are completed showing that, in the position auction environment, IC-Envy can be used to bound the loss in social welfare due to the advertiser untruthful behavior.

Finally, we show experimentally that IC-Envy can be used as a feature to predict IC-Regret in settings not covered by the theoretical results. In particular, using IC-Envy yields better results than training models using only price and value features.

Related Publications

All Publications

Journal of Big Data - November 6, 2021

A graphical method of cumulative differences between two subpopulations

Mark Tygert

The Quarterly Journal of Economics - October 25, 2021

Peer Effects in Product Adoption

Michael Bailey, Drew Johnston, Theresa Kuchler, Johannes Stroebel, Arlene Wong

Conference on Neural Information Processing Systems (NeurIPS) - December 1, 2021

Bandits with Knapsacks beyond the Worst Case

Karthik Abinav Sankararaman, Aleksandrs Slivkins

POPL - January 22, 2022

Profile Inference Revisited

Wenlei He, Julián Mestre, Sergey Pupyrev, Lei Wang, Hongtao Yu

To help personalize content, tailor and measure ads, and provide a safer experience, we use cookies. By clicking or navigating the site, you agree to allow our collection of information on and off Facebook through cookies. Learn more, including about available controls: Cookie Policy