pith. sign in

arxiv: 1907.07721 · v1 · pith:TT7IMELZnew · submitted 2019-07-17 · 💻 cs.GT

Envy, Regret, and Social Welfare Loss

Riccardo Colini-Baldeschi , Stefano Leonardi , Okke Schrijvers , Eric Sodomka This is my paper

Pith reviewed 2026-05-24 19:45 UTC · model grok-4.3

classification 💻 cs.GT
keywords incentive compatibilityposition auctionsIC-EnvyIC-Regretsocial welfareGSPVCGonline advertising
0
0 comments X

The pith

In position auctions, IC-Envy is at least IC-Regret for pricing schemes like VCG and GSP and bounds welfare loss from misreports.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces IC-Envy and IC-Regret as metrics to evaluate whether an auction is incentive compatible. It proves that in position auctions, for a large class of pricing schemes including VCG and GSP, IC-Envy is greater than or equal to IC-Regret, and the two are equal when bids are distinct. The same relation holds in the Ad Types environment with non-separable discounts for a generalization of GSP. IC-Envy, which requires only one auction execution, can bound the social welfare loss caused by advertisers misreporting their values. IC-Envy also improves machine learning predictions of IC-Regret when added as a feature beyond price and value data alone.

Core claim

For position auction environments, for a large class of pricing schemes which includes VCG and GSP, IC-Envy ≥ IC-Regret (and IC-Envy = IC-Regret when bids are distinct). In the Ad Types environment with non-separable discounts, the inequality also holds for a generalization of GSP. IC-Envy can be used to bound the loss in social welfare due to advertiser misreports.

What carries the argument

The IC-Envy metric, which measures the maximum utility an advertiser could gain by taking another advertiser's allocation and payment in a single auction run.

If this is right

  • IC-Envy computed from one auction execution suffices to bound IC-Regret in the covered settings.
  • Social welfare loss from misreports is bounded above by a function of IC-Envy.
  • IC-Envy equals IC-Regret exactly when all bids are distinct.
  • IC-Envy improves prediction accuracy for IC-Regret over models using only price and value features.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Auction platforms could compute IC-Envy on live traffic to flag potential incentive problems without running many counterfactual simulations.
  • The relation might motivate new auction designs that explicitly minimize IC-Envy as a proxy for reducing misreporting.
  • Similar single-run envy checks could be tested in other mechanism settings outside position auctions.

Load-bearing premise

The setting is a position auction or Ad Types environment with non-separable discounts, and the pricing scheme belongs to the class for which the inequality IC-Envy ≥ IC-Regret is proved.

What would settle it

A bid profile in a position auction with GSP pricing where IC-Envy is strictly less than IC-Regret for some advertiser.

Figures

Figures reproduced from arXiv: 1907.07721 by Eric Sodomka, Okke Schrijvers, Riccardo Colini-Baldeschi, Stefano Leonardi.

Figure 1
Figure 1. Figure 1: IC-Envy plotted against IC-Regret 6.2.1 Experimental Setup Auction Environment. We look at auctions with 5 slots, where different bidders have different monotonically decreasing discount curves over the slots (cf. the Ad Types model in Section 4). In this setting, not all ads can target all slots (as a consequence of the different discount curves, not by assumption), and the greedy allocation algorithm is … view at source ↗
Figure 2
Figure 2. Figure 2: The training and validation MSE of the GBDT model on GSP data as a function of the number [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
read the original abstract

Incentive compatibility (IC) is one of the most fundamental properties of an auction mechanism, including those used for online advertising. Recent methods by Feng et al. and Lahaie et al. show that counterfactual runs of the auction mechanism with different bids can be used to determine whether an auction is IC. In this paper we show that a similar result can be obtained by looking at the advertisers' envy, which can be computed with one single execution of the auction. We introduce two metrics to evaluate the incentive-compatibility of an auction: IC-Regret and IC-Envy. For position auction environments, we show that for a large class of pricing schemes (which includes e.g. VCG and GSP), IC-Envy $\ge$ IC-Regret (and IC-Envy = IC-Regret when bids are distinct). We consider non-separable discounts in the Ad Types environment of Colini-Baldeschi et al. where we show that for a generalization of GSP also IC-Envy $\ge$ IC-Regret. Our final theoretical result is that in all these settings IC-Envy be used to bound the loss in social welfare due advertiser misreports. Finally, we show that IC-Envy is useful as a feature to predict IC-Regret in auction environments beyond the ones for which we show theoretical results. In particular, using IC-Envy yields better results than training models using only price and value features.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper defines two metrics, IC-Regret and IC-Envy, for evaluating incentive compatibility (IC) of auctions. For position auctions under a class of pricing schemes including VCG and GSP, it proves IC-Envy ≥ IC-Regret (with equality when bids are distinct). An analogous inequality is shown for the Ad Types environment with non-separable discounts under a generalization of GSP. IC-Envy is further shown to upper-bound the social welfare loss from advertiser misreports. Empirically, IC-Envy serves as a useful feature for predicting IC-Regret in environments beyond the theoretical settings, outperforming models using only price and value features.

Significance. If the stated inequalities and welfare bound hold, the work supplies a computationally lighter alternative to counterfactual verification of IC (one auction execution versus multiple) and a direct link from envy to welfare loss, both scoped to position and Ad Types auctions. The empirical result on prediction is a modest but concrete extension. The manuscript is credited for explicitly scoping its theorems to the environments and pricing classes for which proofs are supplied internally.

minor comments (2)
  1. [Abstract] Abstract: the phrase 'a large class of pricing schemes' is left informal; a brief characterization or reference to the precise conditions used in the theorems would improve readability.
  2. The empirical section would benefit from reporting the exact feature sets, model architectures, and cross-validation procedure used when comparing IC-Envy against price/value baselines.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review, the accurate summary of our contributions, and the recommendation of minor revision. We appreciate the recognition that our results are scoped appropriately to the environments where proofs are provided and that the empirical prediction result, while modest, is a concrete extension.

Circularity Check

0 steps flagged

No significant circularity; metrics and inequalities are internally derived

full rationale

The paper defines IC-Regret and IC-Envy directly from standard position-auction outcomes (allocation and payments) and proves the inequalities IC-Envy ≥ IC-Regret (with equality under distinct bids) plus the welfare-loss bound as explicit theorems whose proofs are internal to the manuscript and scoped to position auctions and the Ad Types environment with non-separable discounts. The single self-citation to the authors' prior Colini-Baldeschi et al. work supplies only the environment definition, not the load-bearing inequality or bound. The empirical claim that IC-Envy improves prediction of IC-Regret is a standard feature-evaluation result on held-out data and does not reduce any theoretical claim to a fitted parameter. No self-definitional, fitted-input, uniqueness-imported, or ansatz-smuggled steps appear.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard auction-theory assumptions without introducing new free parameters or invented entities.

axioms (1)
  • domain assumption Quasi-linear utilities for advertisers
    Implicit background assumption required to define incentive compatibility, envy, and regret.

pith-pipeline@v0.9.0 · 5798 in / 1147 out tokens · 23002 ms · 2026-05-24T19:45:00.031619+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

47 extracted references · 47 canonical work pages · 4 internal anchors

  1. [1]

    Communication complexity of approximate nash equilibria

    Yakov Babichenko and Aviad Rubinstein. Communication complexity of approximate nash equilibria. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Com- puting, pages 878–889. ACM, 2017

    work page 2017

  2. [2]

    Walrasian pricing in multi-unit auctions

    Simina Brˆ anzei, Aris Filos-Ratsikas, Peter Bro Miltersen, and Yulong Zeng. Walrasian pricing in multi-unit auctions. In Kim G. Larsen, Hans L. Bodlaender, and Jean-Fran¸ cois Raskin, editors, 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark , volume 83 of LIPIcs, pages 80:1–80...

    work page 2017

  3. [3]

    Auctions vs

    Jeremy Bulow and Paul Klemperer. Auctions vs. negotiations. Technical report, National Bureau of Economic Research, 1994

    work page 1994

  4. [4]

    On low-envy truthful allocations

    Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos, and Maria Kyropoulou. On low-envy truthful allocations. In International Conference on Algorithmic DecisionTheory, pages 111–119. Springer, 2009

    work page 2009

  5. [5]

    Matching auctions for search and native ads

    Ruggiero Cavallo, Maxim Sviridenko, and Christopher A Wilkens. Matching auctions for search and native ads. In Proceedings of the 2018 ACM Conference on Economics and Computation , pages 663–680. ACM, 2018

    work page 2018

  6. [6]

    Ruggiero Cavallo and Christopher A. Wilkens. Gsp with general independent click-through- rates. In Tie-Yan Liu, Qi Qi, and Yinyu Ye, editors, Web and Internet Economics , pages 400–416, Cham, 2014. Springer International Publishing

    work page 2014

  7. [7]

    A global characterization of envy-free truthful scheduling of two tasks

    George Christodoulou and Annam´ aria Kov´ acs. A global characterization of envy-free truthful scheduling of two tasks. In International Workshop on Internet and Network Economics , pages 84–96. Springer, 2011. 15

    work page 2011

  8. [8]

    Envy-free makespan approximation

    Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, and Svetlana Olonetsky. Envy-free makespan approximation. In Proceedings of the 11th ACM conference on Electronic commerce, pages 159–166. ACM, 2010

    work page 2010

  9. [9]

    On the Interplay between Incentive Compatibility and Envy Freeness

    Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, and Svetlana Olonetsky. On the interplay between incentive compatibility and envy freeness. arXiv preprint arXiv:1003.5328 , 2010

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  10. [10]

    Revenue maximizing envy-free fixed-price auctions with budgets

    Riccardo Colini-Baldeschi, Stefano Leonardi, Piotr Sankowski, and Qiang Zhang. Revenue maximizing envy-free fixed-price auctions with budgets. In Tie-Yan Liu, Qi Qi, and Yinyu Ye, editors, Web and Internet Economics - 10th International Conference, WINE 2014, Beijing, China, December 14-17, 2014. Proceedings, volume 8877 of Lecture Notes in Computer Scienc...

    work page 2014

  11. [11]

    Revenue maximizing envy-free fixed-price auctions with budgets

    Riccardo Colini-Baldeschi, Stefano Leonardi, Piotr Sankowski, and Qiang Zhang. Revenue maximizing envy-free fixed-price auctions with budgets. In International Conference on Web and Internet Economics , pages 233–246. Springer, 2014

    work page 2014

  12. [12]

    Revenue maximizing envy- free pricing in matching markets with budgets

    Riccardo Colini-Baldeschi, Stefano Leonardi, and Qiang Zhang. Revenue maximizing envy- free pricing in matching markets with budgets. In Yang Cai and Adrian Vetta, editors, Web and Internet Economics - 12th International Conference, WINE 2016, Montreal, Canada, December 11-14, 2016, Proceedings , volume 10123 of Lecture Notes in Computer Science , pages 2...

    work page 2016

  13. [13]

    Revenue maximizing envy- free pricing in matching markets with budgets

    Riccardo Colini-Baldeschi, Stefano Leonardi, and Qiang Zhang. Revenue maximizing envy- free pricing in matching markets with budgets. In WINE 2016, Montreal, Canada, December 11-14, 2016, Proceedings, pages 207–220, 2016

    work page 2016

  14. [14]

    Riccardo Colini-Baldeschi, Julian Mestre, Okke Schrijvers, and Christopher A. Wilkens. The ad types problem. arXiv, preprint arXiv:1907.04400 , 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1907

  15. [15]

    The complexity of computing a nash equilibrium

    Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a nash equilibrium. SIAM Journal on Computing , 39(1):195–259, 2009

    work page 2009

  16. [16]

    Learning in auctions: Regret is hard, envy is easy

    Constantinos Daskalakis and Vasilis Syrgkanis. Learning in auctions: Regret is hard, envy is easy. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on , pages 219–228. IEEE, 2016

    work page 2016

  17. [17]

    Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords

    Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. American economic review, 97(1):242–259, 2007

    work page 2007

  18. [18]

    Revenue maximizing envy-free multi-unit auctions with budgets

    Michal Feldman, Amos Fiat, Stefano Leonardi, and Piotr Sankowski. Revenue maximizing envy-free multi-unit auctions with budgets. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 532–549. ACM, 2012

    work page 2012

  19. [19]

    Mechanisms and impossibilities for truthful, envy-free alloca- tions

    Michal Feldman and John Lai. Mechanisms and impossibilities for truthful, envy-free alloca- tions. In Algorithmic Game Theory, pages 120–131. Springer, 2012

    work page 2012

  20. [20]

    Online learning for measuring incentive com- patibility in ad auctions

    Zhe Feng, Okke Schrijvers, and Eric Sodomka. Online learning for measuring incentive com- patibility in ad auctions. In Proceedings of the 2019 World Wide Web Conference , 2019. 16

    work page 2019

  21. [21]

    Envy, multi envy, and revenue maximization

    Amos Fiat and Amiram Wingarten. Envy, multi envy, and revenue maximization. In Inter- national Workshop on Internet and Network Economics , pages 498–504. Springer, 2009

    work page 2009

  22. [22]

    Lower bound for envy-free and truthful makespan approxi- mation on related machines

    Lisa Fleischer and Zhenghui Wang. Lower bound for envy-free and truthful makespan approxi- mation on related machines. In International Symposium on Algorithmic Game Theory , pages 166–177. Springer, 2011

    work page 2011

  23. [23]

    Resource allocation and the public sector

    D Foley. Resource allocation and the public sector. Yale Economic Essays, 7:45–98, 1967

    work page 1967

  24. [24]

    A decision-theoretic generalization of on-line learning and an application to boosting

    Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119–139, 1997

    work page 1997

  25. [25]

    Envy-free auctions for digital goods

    Andrew V Goldberg and Jason D Hartline. Envy-free auctions for digital goods. In Proceedings of the 4th ACM conference on Electronic commerce , pages 29–35. ACM, 2003

    work page 2003

  26. [26]

    On profit-maximizing envy-free pricing

    Venkatesan Guruswami, Jason D Hartline, Anna R Karlin, David Kempe, Claire Kenyon, and Frank McSherry. On profit-maximizing envy-free pricing. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1164–1173. Society for Industrial and Applied Mathematics, 2005

    work page 2005

  27. [27]

    Envy, truth, and profit

    Jason Hartline and Qiqi Yan. Envy, truth, and profit. In Proceedings of the 12th ACM conference on Electronic commerce, pages 243–252. ACM, 2011

    work page 2011

  28. [28]

    Note on VCG vs. Price Raising for Matching Markets

    Walter Kern, Bodo Manthey, and Marc Uetz. Note on VCG vs. price raising for matching markets. CoRR, abs/1604.04157, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  29. [29]

    Adam: A Method for Stochastic Optimization

    Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  30. [30]

    Testing incentive compatibility in display ad auctions

    S´ ebastien Lahaie, Andr´ es Munoz Medina, Balasubramanian Sivan, and Sergei Vassilvitskii. Testing incentive compatibility in display ad auctions. In Proceedings of the 2018 World Wide Web Conference on World Wide Web , pages 1419–1428. International World Wide Web Conferences Steering Committee, 2018

    work page 2018

  31. [31]

    On approximately fair allocations of indivisible goods

    Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM conference on Electronic commerce, pages 125–131. ACM, 2004

    work page 2004

  32. [32]

    Gsp auctions with correlated types

    Brendan Lucier and Renato Paes Leme. Gsp auctions with correlated types. In Proceedings of the 12th ACM conference on Electronic commerce , pages 71–80. ACM, 2011

    work page 2011

  33. [33]

    Setting lower bounds on truthfulness

    Ahuva Mu’alem and Michael Schapira. Setting lower bounds on truthfulness. Games and Economic Behavior, 110:174–193, 2018

    work page 2018

  34. [34]

    Optimal auctions

    Roger Myerson. Optimal auctions. 1981

    work page 1981

  35. [35]

    Reserve prices in internet advertising auctions: a field experiment

    Michael Ostrovsky and Michael Schwarz. Reserve prices in internet advertising auctions: a field experiment. EC, 11:59–60, 2011

    work page 2011

  36. [36]

    Pedregosa, G

    F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825–2830, 2011. 17

    work page 2011

  37. [37]

    Intrinsic robustness of the price of anarchy

    Tim Roughgarden. Intrinsic robustness of the price of anarchy. J. ACM , 62(5):32:1–32:42, November 2015

    work page 2015

  38. [38]

    The price of anarchy in auctions

    Tim Roughgarden, Vasilis Syrgkanis, and ´Eva Tardos. The price of anarchy in auctions. J. Artif. Int. Res., 59(1):59–101, May 2017

    work page 2017

  39. [39]

    Inapproximability of nash equilibrium

    Aviad Rubinstein. Inapproximability of nash equilibrium. SIAM Journal on Computing , 47(3):917–959, 2018

    work page 2018

  40. [40]

    Big changes coming to auctions, as exchanges roll the dice on first-price

    Sarah Sluis. Big changes coming to auctions, as exchanges roll the dice on first-price. https: //adexchanger.com/platforms/big-changes-coming-auctions-exchanges-roll-dice-first-price/,

    work page

  41. [41]

    Last accessed: 2019-05-23

    work page 2019

  42. [42]

    Google switches to first-price auction

    Sarah Sluis. Google switches to first-price auction. https://adexchanger.com/ online-advertising/google-switches-to-first-price-auction/, 2019. Last accessed: 2019-05-23

    work page 2019

  43. [43]

    Envy-free sponsored search auctions with budgets

    Bo Tang and Jinshan Zhang. Envy-free sponsored search auctions with budgets. In IJCAI, pages 653–659, 2015

    work page 2015

  44. [44]

    Equity, envy, and efficiency

    Hal R Varian. Equity, envy, and efficiency. 1973

    work page 1973

  45. [45]

    Position auctions

    Hal R Varian. Position auctions. international Journal of industrial Organization , 25(6):1163– 1178, 2007. A Handling Unbalanced Graphs and Ties We conclude the section by showing how to handle unbalanced graphs and ties. If the number of advertisers n > mthe number of ties, we add n−m slots, and for all slots j∈ J let αi,j = 0 for each new slot j. Note ...

    work page 2007

  46. [46]

    In this case ui(vi/2, b−i)≥ 1/2αi,X(v,i)vi

    In a first case, by switching his bid from bi to vi/2, player i wins some slot k≤ X(v,i ). In this case ui(vi/2, b−i)≥ 1/2αi,X(v,i)vi

    work page

  47. [47]

    Otherwise, by switching his bid from bi to b′ i = vi/2, player i wins some slot k≤ X(v,i ). Given that the mechanism computes a MWPM, the player who wins slot j =X(v,i ) under bidding profile ( vi/2, b−i) is such that assigning slot j to bidder π((vi/2, b−i),j ) and slot X((vi/2, b−i),i ) to bidder i gives a reward that is strictly larger than assigning sl...

    work page