Individual Fairness in Advertising Auctions through Inverse Proportionality
summary
Proposes and analyzes inverse proportional allocation that enforces a multiplicative-to-additive fairness constraint called value stability while retaining high welfare. Claims a constant worst‑case guarantee (notably a 3/4 approximation for a canonical choice) that does not degrade as the number of advertisers grows, gives an efficiently computable threshold T, and proves near‑optimal tradeoffs across a family of stability functions parametrized by L. Experiments on the Yahoo! Ads dataset show value stability holds and IP allocation outperforms proportional allocation for three or more bidders.
AI-written summary · about
chapters (19)
- 0:00Intro
- 0:12Skewed delivery in online advertising
- 0:28Sources of unfairness
- 1:46Example: Skewed delivery within a category
- 3:51The model
- 5:38Related work
- 5:52The fairness constraint
- 8:54Example family of value stability constraints
- 10:22Our algorithmic results
- 11:43Designing value-stable allocation algorithms
- 12:40A first attempt: Proportional Allocation
- 15:03Our solution: Inverse proportional allocation (IPA)
- 16:23Performance of inverse proportional allocation (IPA)
- 17:30Generalizing to other value-stability constraints
- 20:26Near-optimality of IPA
- 21:45Proof sketch of approximation ratio
- 24:24Proof sketch of value-stability
- 26:20Experiments on Yahoo ads dataset
- 27:40Conclusion
related talks
40mOnline Ad Allocation: Robust Optimization for Repeated Auctions
48mRobust Inference for Games via Theoretical Guarantees
43mLearning about Auctions
01h 07mMulti-Dimensional and Non-Linear Mechanism Design and Approximation I
31mPreference Informed Fairness
01h 14mCompetitive Analysis Meets Stochastic Input: Secretary Problems And Prophet Inequalities
46mEliciting and Enforcing Subjective Individual Fairness
44mProcedural Justice in Algorithmic Fairness: Transparency, Control and Participation Perspectives