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

NeurIPS - December 16, 2020

Online Bayesian Persuasion

Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Nicola Gatti

WINE - December 7, 2020

The Ad Types Problem

Riccardo Colini Baldeschi, Julian Mestre, Okke Schrijvers, Christopher A. Wilkens

NBER - September 30, 2020

The Effects of COVID-19 on U.S. Small Businesses: Evidence from Owners, Managers, and Employees

Georgij Alekseev, Safaa Amer, Manasa Gopal, Theresa Kuchler, JW Schneider, Johannes Stroebel, Nils Wernerfelt

arXiv - October 9, 2020

Weights and Methodology Brief for the COVID-19 Symptom Survey by University of Maryland and Carnegie Mellon University, in Partnership with Facebook

Neta Barkay, Curtiss Cobb, Roee Eilat, Tal Galili, Daniel Haimovich, Sarah LaRocca, Katherine Morris, Tal Sarig

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: Cookies Policy