  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.
