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 Spillover
Even when an advertiser has no intent to discriminate, the mechanics of ad auctions can lead to biased outcomes. A primary culprit identified in this research is competitive spillover.
Consider a scenario with two advertisers: one selling high-end women’s clothing (targeting women) and another advertising a STEM job (targeting a general audience). Because the clothing advertiser bids aggressively for female users, the "price" to show an ad to a woman increases. The STEM job advertiser, seeking the best return on investment, might find it cheaper to show ads to men. Consequently, the job ad is shown disproportionately to men, potentially violating ethical standards or labor laws. Currently, platforms lack a formal mechanism to control this, often rejecting manual balancing attempts by advertisers due to concerns over discriminatory targeting.
Methodology: The α-Shifted Mechanism
To address this, the authors build upon Myerson’s classic auction theory, which maximizes revenue by evaluating "virtual valuations" rather than raw bids. They introduce the α-Shifted Mechanism, proving that the optimal fair auction is one where a constant "shift" (α) is added to the virtual valuation of an advertiser for a specific user type. Essentially, the platform "nudges" certain bids up or down to ensure the final distribution of winners meets pre-defined fairness constraints.
Optimization and Algorithmic Implementation
Finding the correct shifts (α) presents a significant mathematical challenge because the revenue function is non-convex with respect to these shifts. However, the researchers discovered a critical structural property: while revenue is non-convex in the shift space, it is concave with respect to the coverage space (the probability of winning).
By identifying that the Jacobian of the coverage-to-shift mapping is invertible, the authors developed a gradient-descent-based algorithm that operates in the well-behaved coverage space and maps results back to the shift space. They proved that this reformulated problem has no saddle points or local maxima, ensuring the algorithm reliably finds the global optimum with a fast convergence rate of $\tilde{O}(1/\epsilon^2)$.
Empirical Results
The framework was validated using the Yahoo! Search Marketing Advertising Bidding Data (A1 dataset), containing approximately 20 million bids from over 10,000 advertisers. Key findings include:
- Revenue Impact: The algorithm achieved uniform coverage across user types with a negligible impact on the platform's bottom line, losing less than 5% of total revenue.
- Advertiser Reach: The "Total Variation Distance"—measuring the change in winning distribution—was less than 0.05. This indicates that advertisers reach roughly the same volume of users, with the mechanism primarily changing the composition of the audience to be more balanced rather than displacing the advertiser entirely.
Conclusion and Future Directions
This research demonstrates that achieving near-perfect fairness in ad auctions is not a zero-sum game against revenue. While the current framework is robust, future work is needed to address intersectional complexity (where the number of constraints grows exponentially), dynamic environments where advertisers enter and exit the market, and non-truthful auctions like the Generalized Second Price (GSP) models common in modern exchanges.
Summary updated