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) [10.1145/3366423.3380057].

Envy, Regret, and Social Welfare Loss

Leonardi S.
;
2020

Abstract

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.
2020
29th International World Wide Web Conference, WWW 2020
Envy-freeness; Incentive-Compatibility Measurement; Position Auctions; Social Welfare Loss
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
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) [10.1145/3366423.3380057].
File allegati a questo prodotto
File Dimensione Formato  
Colini-Baldeschi_postprint_Envy_2020.pdf

accesso aperto

Note: https://doi.org/10.1145/3366423.3380057
Tipologia: Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 698.61 kB
Formato Adobe PDF
698.61 kB Adobe PDF
Colini-Baldeschi_Envy_2020.pdf

accesso aperto

Note: https://doi.org/10.1145/3366423.3380057
Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Creative commons
Dimensione 748.54 kB
Formato Adobe PDF
748.54 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1470520
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact