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 computationally intensive, 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.
Envy, Regret, and Social Welfare Loss / Colini-Baldeschi, R.; Leonardi, S.; Schrijvers, O.; Sodomka, E.. - (2020), pp. 2913-2919. ((Intervento presentato al convegno 29th International World Wide Web Conference, WWW 2020 tenutosi a Electr Network.
|Titolo:||Envy, Regret, and Social Welfare Loss|
LEONARDI, Stefano (Corresponding author)
|Data di pubblicazione:||2020|
|Citazione:||Envy, Regret, and Social Welfare Loss / Colini-Baldeschi, R.; Leonardi, S.; Schrijvers, O.; Sodomka, E.. - (2020), pp. 2913-2919. ((Intervento presentato al convegno 29th International World Wide Web Conference, WWW 2020 tenutosi a Electr Network.|
|Appartiene alla tipologia:||04b Atto di convegno in volume|
File allegati a questo prodotto
|Colini-Baldeschi_postprint_Envy_2020.pdf||https://doi.org/10.1145/3366423.3380057||Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)||Tutti i diritti riservati (All rights reserved)||Open Access Visualizza/Apri|
|Colini-Baldeschi_Envy_2020.pdf||https://doi.org/10.1145/3366423.3380057||Versione editoriale (versione pubblicata con il layout dell'editore)||Open Access Visualizza/Apri|