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 or race of the audience that sees the ad, and may inadvertently cross ethical and/or legal boundaries. To prevent this, we propose a constrained ad auction framework that maximizes the platform's revenue conditioned on ensuring that the audience seeing an advertiser's ad is distributed appropriately across sensitive types such as gender or race. Building upon Myerson's classic work, we first present an optimal auction mechanism for a large class of fairness constraints. Finding the parameters of this optimal auction, however, turns out to be a non-convex problem. We show that this non-convex problem can be reformulated as a more structured non-convex problem with no saddle points or local-maxima; this allows us to develop a gradient-descent-based algorithm to solve it. Our empirical results on the A1 Yahoo! dataset demonstrate that our algorithm can obtain uniform coverage across different user types for each advertiser at a minor loss to the revenue of the platform, and a small change to the size of the audience each advertiser reaches.
Introduction: The Problem of Competitive Spillovers
Online advertising is built on hyper-targeting, but this efficiency often leads to discriminatory outcomes. For example, studies have shown that STEM job ads are frequently shown to more men than women, even when the advertiser did not specify a gender preference. The authors identify a primary culprit for this phenomenon: competitive spillovers.
Imagine two advertisers: one selling detergent specifically targeting women, and another advertising a high-paying job with no gender preference. Because the first advertiser bids aggressively for women, they drive up the "price" of showing ads to women. The second advertiser’s budget is then naturally diverted toward the "cheaper" audience—men—leading to inadvertent discrimination. Currently, platforms lack a mechanism to control this structural flaw. This research seeks to maximize platform revenue while satisfying "group fairness" constraints, ensuring that an advertiser’s audience is distributed appropriately across sensitive user types.
Methodology
The authors build upon Myerson’s classic auction theory, which defines how to maximize revenue in an auction. Their core contribution is a "constrained ad auction framework" consisting of three main pillars:
- The $\alpha$-shifted Mechanism: The study proves that the optimal fair auction is a variation of the standard Vickrey-Clarke-Groves (VCG) auction. Instead of just using raw bids, the platform applies a "shift" ($\alpha$) to the virtual valuations of each advertiser-type pair. Essentially, the platform "nudges" bids up or down to meet fairness targets.
- Optimization Reformulation: Finding the right shifts ($\alpha$) is typically computationally intensive because the problem is non-convex. However, the authors discovered a structural breakthrough: while the problem is non-convex in terms of the shifts, the revenue is a concave function of the coverage (the probability of winning).
- The Algorithm: Based on this insight, they developed a gradient-descent-based algorithm that navigates this space. They prove that their reformulated problem has no saddle points or local maxima, meaning the algorithm is guaranteed to find the global optimum efficiently.
Empirical Evaluation
The study evaluates the algorithm using the Yahoo! Search Marketing Advertising Bidding Data (A1 dataset). This dataset contains bids on the top 1,000 keywords from 2002 to 2003, involving over 10,000 advertisers and approximately 20 million bids. Since the keywords are anonymized, the authors identified "related" keywords (those sharing multiple advertisers) to simulate different user "types" where competitive spillovers would likely occur.
Key Results
- Minimal Revenue Loss: In empirical tests on the Yahoo! dataset, the algorithm achieved uniform coverage (perfect fairness) across user types while losing less than 5% of the platform's total revenue.
- Stable Audience Reach: The "Total Variation" distance—a measure of how much the winner distribution changed—was less than 0.05. This means advertisers still reached roughly the same number of people; the fairness mechanism simply ensured those people were a more representative mix.
- Computational Efficiency: The algorithm boasts a fast convergence rate of $\tilde{O}(1/\epsilon^2)$, making it computationally feasible for large-scale ad exchanges.
Discussion and Future Work
This paper shifts the focus from "biased advertisers" to "biased auction dynamics," demonstrating that discrimination can happen even with perfectly neutral advertisers due to how budgets interact in a competitive market. By applying small, calculated shifts to bids, platforms can balance the scales without overhauling the entire auction system.
However, limitations remain. The current model assumes a static environment where the set of advertisers is fixed, whereas real-world ad campaigns are dynamic. Additionally, while the math supports intersectional types (e.g., race and gender combined), the number of constraints grows exponentially with more sensitive attributes. Finally, extending this framework from "truthful" auctions to the more common Generalized Second Price (GSP) auctions remains a vital area for future research.
Summary updated