Toward Controlling Discrimination in Online Ad Auctions

Anay Mehrotra, L. Elisa Celis, Nisheeth K. VishnoiICML 2019 · OpenReview

Introduction

Online advertising platforms thrive on offering highly customizable audiences to advertisers. However, this hyper-specific targeting power often leads to discriminatory outcomes. For example, high-paying job ads are sometimes shown more frequently to men than women, even when the advertiser did not explicitly request such a bias.

This paper introduces a novel ad auction framework designed to prevent "inadvertent discrimination" in online advertising. By building on Myerson’s classic auction theory and adding specific fairness constraints, the authors develop a gradient-descent-based algorithm that ensures ads reach diverse demographics without significantly hurting a platform's revenue.

The Challenge of Competitive Spillovers

The authors highlight a phenomenon called competitive spillovers. If one advertiser (e.g., a clothing brand) aggressively outbids others for a specific demographic (e.g., women), other advertisers (e.g., a STEM employer) might inadvertently have their ads pushed toward a different demographic (e.g., men) simply because those slots are cheaper. Currently, platforms lack a mechanism to control this systemic bias. The core challenge is to create an auction that maximizes revenue while enforcing "group fairness" across sensitive attributes like gender, race, or geography.

Proposed Methodology

The authors propose a constrained ad auction framework involving several key technical steps:

  1. Myerson-Style Foundation: They build upon Myerson’s (1981) work on revenue-optimal auctions, where the platform uses "virtual valuations" to decide the winner.
  2. $(\ell, u)$-Fairness Constraints: They introduce constraints requiring the proportion of an advertiser's ads shown to a specific user type to fall within a lower bound ($\ell$) and an upper bound ($u$).
  3. $\alpha$-Shifted Mechanism: They prove that the optimal fair auction can be characterized by adding a constant "shift" ($\alpha$) to the virtual valuations of each advertiser-type pair.
  4. Overcoming Non-Convexity: Finding these optimal shifts is typically a non-convex optimization problem. However, the authors show that this specific problem is "well-behaved," lacking saddle points or local maxima.
  5. Algorithmic Solution: They develop a two-tier algorithm. One algorithm performs projected gradient descent on the "coverage" (the probability of winning), while a "Gradient Oracle" finds the corresponding shifts ($\alpha$) needed to achieve that coverage.

Experimental Setup

The researchers evaluated their framework using the Yahoo! Search Marketing Advertising Bidding Data (A1 dataset), which contains approximately 20 million bids from over 10,000 advertisers. Because the dataset is anonymized, the authors used pairs of related keywords (e.g., two keywords sharing many of the same bidders) as proxies for different user types. This setup allowed them to simulate "spillover" effects where an advertiser might win disproportionately on one keyword versus another.

Key Insights

  • Fairness as a Systemic Property: Fairness cannot be solved by advertisers alone; the auction mechanism itself must be constrained because the bids of other advertisers affect who sees your ad.
  • Revenue vs. Coverage: A major insight is that while revenue is a non-convex function of the shifts ($\alpha$), it is a concave function of the coverage ($q$). This structural property transforms a difficult problem into one solvable via gradient descent.
  • Truthfulness Maintained: The proposed mechanism remains "truthful," meaning advertisers are still incentivized to bid their actual value for a user—a critical requirement for practical auction systems.

Key Results

Empirical tests on the Yahoo! dataset demonstrated that the framework successfully balances fairness and platform utility.

Minimal Revenue Loss: The fair mechanism achieved uniform coverage across user types while losing less than 5% of the platform's revenue, even under strict fairness constraints.

Revenue ratio vs Fairness constraint

Effective Balancing and Advertiser Reach: Even in the most constrained scenarios (aiming for "perfect fairness" at $\ell=0.5$), the total variation distance between the fair and unconstrained distributions remained remarkably low. Furthermore, the change in the total size of the audience reached by each advertiser was minimal, suggesting that fairness does not have to come at the cost of advertiser utility.

Advertiser Displacement vs Fairness constraint

Limitations and Future Work

  • Intersectional Complexity: While the framework supports intersectional types (e.g., Black women), the number of constraints grows exponentially with the number of sensitive attributes, potentially leading to significant computational overhead.
  • Static vs. Dynamic: The current model is static. Extending this to a dynamic setting where ad campaigns start and end at different times is a necessary next step.
  • User Value: The framework assumes the "value" of an ad is the same across types, but advertisers might intentionally design ads to appeal to specific groups. Future work should examine how these constraints affect user satisfaction and ad content.
  • Second-Price Auctions: Most modern platforms use Generalized Second Price (GSP) auctions rather than the Myerson-style auctions discussed here. Extending this fairness framework to GSP remains an open challenge.

Summary updated

Abstract

Online advertising platforms are thriving due to the customizable audiences they offer advertisers. However, recent studies show that advertisements can be discriminatory with respect to the gender...
BibTeX
@inproceedings{mehrotra2019toward,
  author = {Anay Mehrotra and L. Elisa Celis and Nisheeth K. Vishnoi},
  title = {{Toward Controlling Discrimination in Online Ad Auctions}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=HJ-iShbuZS},
}
Figure