Learning Fair Equilibria in Sponsored Search Auctions

Andrea Celli, Riccardo Colini-Baldeschi, Stefano LeonardiarXiv 2021 · arXiv · OpenReview

Abstract: In this work we introduce a new class of mechanisms composed of a traditional Generalized Second Price (GSP) auction and a fair division scheme, in order to achieve some desired level of fairness between groups of Bayesian strategic advertisers. We propose two mechanisms, $\beta$-Fair GSP and GSP-EFX, that compose GSP with, respectively, an envy-free up to one item, and an envy-free up to any item fair division scheme. The payments of GSP are adjusted in order to compensate advertisers that suffer a loss of efficiency due the fair division stage. We investigate the strategic learning implications of the deployment of sponsored search auction mechanisms that obey to such fairness criteria. We prove that, for both mechanisms, if bidders play so as to minimize their external regret they are guaranteed to reach an equilibrium with good social welfare. We also prove that the mechanisms are budget balanced, so that the payments charged by the traditional GSP mechanism are a good proxy of the total compensation offered to the advertisers. Finally, we evaluate the quality of the allocations through experiments on real-world data.

Introduction

In the high-stakes world of online advertising, the Generalized Second Price (GSP) auction is the industry standard. Designed for efficiency, GSP ensures that the highest bidders receive the most prominent ad slots. However, this efficiency-first approach often creates a "rich get richer" dynamic, where large corporations with massive budgets can crowd out small and medium businesses (SMBs) or minority groups.

While previous research has focused on fairness for users (e.g., avoiding biased ad delivery), this paper addresses fairness from the advertisers' perspective. The authors propose a framework that protects minority groups without dismantling the economic engine of the internet.

The Composite Mechanism Approach

To integrate fairness into existing systems without a total rewrite, the researchers introduce a Composite Mechanism. This approach treats fairness as a "post-auction" layer that runs immediately after bids are collected.

  • The Fairness Layer: The system reorders search ad slots to satisfy group fairness criteria derived from fair division literature: EF1 (Envy-Free up to one item) and EFX (Envy-Free up to any item).
  • Two New Mechanisms:
    • $\beta$-Fair GSP: Utilizes a modified Round-Robin approach to guarantee EF1 fairness.
  • GSP-EFX: Employs a "Group Envy-Cycle-Elimination" algorithm to achieve the stricter EFX fairness.
  • Compensatory Pricing: To maintain Individual Rationality, the mechanism automatically reduces payments for advertisers who are moved to lower slots for fairness reasons. This ensures no advertiser is worse off than if they had not participated.

Strategic Stability and Learning

A critical concern in auction design is how strategic bidders will react to new rules. The authors analyze the system under "no-regret learning," where advertisers use algorithms (like EXP3) to update their bids based on past performance.

They prove that these fair mechanisms are "smooth," meaning that even with self-interested, strategic bidders, the system naturally settles into a Bayesian Coarse Correlated Equilibrium. This equilibrium maintains high social welfare and limits the "Price of Composition" (PoC)—the welfare loss incurred by introducing fairness.

Experimental Evaluation

The mechanisms were evaluated using real-world advertising logs from a major internet company. The researchers simulated $10^4$ sequential auctions with 20 advertisers divided into majority and minority groups.

Expected overall social welfare at equilibrium compared to optimal and standard GSP benchmarks.

As shown in the experimental results, the composite mechanism ($SW^C$) successfully approaches the social welfare of the standard GSP ($SW^G$) as the fairness parameters are tuned. Furthermore, the actual revenue loss to the platform was found to be manageable.

Revenue loss as a function of the fairness parameter, showing stabilization around 20%.

While theoretical worst-cases exist, empirical data shows that revenue loss typically stabilizes around 20% for moderate fairness requirements. The mechanisms are also proven to be "budget balanced," meaning the platform can cover the cost of compensating advertisers using the revenue generated by the auction itself.

Conclusion

This work demonstrates that group fairness is a practical and achievable goal in sponsored search. By treating fairness as a re-shuffling step after the auction, platforms can implement these features as a plugin to existing GSP infrastructure. Future work remains in extending these models to more than two groups and exploring fairness in the context of long-term business outcomes rather than just immediate valuations.

Summary updated

Abstract

In this work we introduce a new class of mechanisms composed of a traditional Generalized Second Price (GSP) auction and a fair division scheme, in order to achieve some desired level of fairness between groups of Bayesian strategic advertisers. We propose two mechanisms, $\beta$-Fair GSP and GSP-EFX, that compose GSP with, respectively, an envy-free up to one item, and an envy-free up to any item fair division scheme. The payments of GSP are adjusted in order to compensate advertisers that suffer a loss of efficiency due the fair division stage. We investigate the strategic learning implications of the deployment of sponsored search auction mechanisms that obey to such fairness criteria. We prove that, for both mechanisms, if bidders play so as to minimize their external regret they are guaranteed to reach an equilibrium with good social welfare. We also prove that the mechanisms are budget balanced, so that the payments charged by the traditional GSP mechanism are a good proxy of the total compensation offered to the advertisers. Finally, we evaluate the quality of the allocations through experiments on real-world data.
BibTeX
@misc{celli2021learning,
  author = {Andrea Celli and Riccardo Colini-Baldeschi and Stefano Leonardi},
  title = {{Learning Fair Equilibria in Sponsored Search Auctions}},
  year = {2021},
  eprint = {2107.08271},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2107.08271},
}
Figure