论文标题
通过反比的个人公平性拍卖的公平性
Individual Fairness in Advertising Auctions through Inverse Proportionality
论文作者
论文摘要
最近的经验工作表明，即使所有广告商都以非歧视性方式出价，在线广告也会在用户跨用户的广告交付时表现出偏见。我们研究了AD拍卖的设计，鉴于公平的出价，可以保证产生公平的结果。遵循Dwork和Ilvento（2019）和Chawla等人的作品。 （2020年），我们的目标是设计一个满足``个人公平性''的真实拍卖：非正式地说，彼此相似的用户应获得类似的广告分配。在此框架内，我们量化了社会福利最大化与公平性之间的权衡。 这项工作做出了两个概念上的贡献。首先，我们将公平限制表示为一种稳定条件：由所有广告商分配的任何两个用户都必须为每个广告商收到添加性相似的分配。此值稳定性约束表示为将值向量之间的乘法距离映射到最大允许的$ \ ell _ {\ infty} $之间的函数。标准拍卖不满足这种价值稳定性。 其次，我们介绍了一种称为逆比例分配的新的分配算法，该算法在公平和社会福利之间取得了几乎最佳的权衡，以实现广泛而表达的价值稳定性条件类别。这些分配算法是真实且没有事先的，并实现了与最佳（无约束）社会福利的持续近似。特别是，近似值比独立于系统中的广告商数量。在这方面，这些分配算法大大超过了以前的工作中获得的保证。我们还将结果扩展到了我们称为子集公平的更广泛的公平概念。
Recent empirical work demonstrates that online advertisement can exhibit bias in the delivery of ads across users even when all advertisers bid in a non-discriminatory manner. We study the design of ad auctions that, given fair bids, are guaranteed to produce fair outcomes. Following the works of Dwork and Ilvento (2019) and Chawla et al. (2020), our goal is to design a truthful auction that satisfies ``individual fairness'' in its outcomes: informally speaking, users that are similar to each other should obtain similar allocations of ads. Within this framework we quantify the tradeoff between social welfare maximization and fairness. This work makes two conceptual contributions. First, we express the fairness constraint as a kind of stability condition: any two users that are assigned multiplicatively similar values by all the advertisers must receive additively similar allocations for each advertiser. This value stability constraint is expressed as a function that maps the multiplicative distance between value vectors to the maximum allowable $\ell_{\infty}$ distance between the corresponding allocations. Standard auctions do not satisfy this kind of value stability. Second, we introduce a new class of allocation algorithms called Inverse Proportional Allocation that achieve a near optimal tradeoff between fairness and social welfare for a broad and expressive class of value stability conditions. These allocation algorithms are truthful and prior-free, and achieve a constant factor approximation to the optimal (unconstrained) social welfare. In particular, the approximation ratio is independent of the number of advertisers in the system. In this respect, these allocation algorithms greatly surpass the guarantees achieved in previous work. We also extend our results to broader notions of fairness that we call subset fairness.
