Multi-Category Fairness in Sponsored Search Auctions
  Fairness in advertising is a topic of particular concern motivated by
theoretical and empirical observations in both the computer science and
economics literature. We examine the problem of fairness in advertising for
general purpose platforms that service advertisers from many different
categories. First, we propose inter-category and intra-category fairness
desiderata that take inspiration from individual fairness and envy-freeness.
Second, we investigate the "platform utility" (a proxy for the quality of the
allocation) achievable by mechanisms satisfying these desiderata. More
specifically, we compare the utility of fair mechanisms against the unfair
optimal, and we show by construction that our fairness desiderata are
compatible with utility. That is, we construct a family of fair mechanisms with
high utility that perform close to optimally within a class of fair mechanisms.
Our mechanisms also enjoy nice implementation properties including
metric-obliviousness, which allows the platform to produce fair allocations
without needing to know the specifics of the fairness requirements.
