Individual Fairness in Advertising Auctions Through Inverse Proportionality
Individual Fairness in Advertising Auctions Through Inverse Proportionality
复制标题
通过反比例实现广告拍卖中的个人公平
DOI：
10.4230/lipics.itcs.2022.42
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Meena Jagadeesan
中科院分区：
文献类型：
--
作者：
Shuchi Chawla;Meena Jagadeesan
最近的实证研究表明，即使所有广告商都以非歧视性的方式出价，在线广告也会在用户之间的广告投放中表现出偏见。我们研究广告拍卖的设计，给出公平的出价，保证产生公平的结果。根据Dwork和Ilvento（2019）和Chawla等人（2020）的工作，我们的目标是设计一个真实的拍卖，在其结果中满足“个人公平性”：非正式地说，彼此相似的用户应该获得相似的广告分配。在这个框架内，我们量化社会福利最大化和公平之间的权衡。这项工作作出了两个概念上的贡献。首先，我们表达的公平性约束作为一种稳定性条件：任何两个用户分配乘法相似的值由所有的广告客户必须获得添加相似的分配每个广告客户。该值稳定性约束被表示为一个函数，该函数将值向量之间的乘法距离映射到相应分配之间的最大允许距离。标准拍卖并不满足这种价值稳定性。其次，我们引入了一类新的分配算法，称为逆比例分配，实现了公平和社会福利之间的一个广泛的和表达类的价值稳定性条件的接近最优的权衡。这些分配算法是真实的和先验自由的，并实现了一个常数因子近似的最佳（无约束）的社会福利。特别地，近似比与系统中的广告商的数量无关。在这方面，这些分配算法大大超过了以前的工作中取得的保证。我们还将我们的结果扩展到更广泛的公平概念，我们称之为子集公平。
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.
影响因子：
0.5
作者：
Christodoulou G
通讯作者：
Christodoulou G
构图下的公平性
DOI：
--
发表时间：
2019
期刊：
10th Innovations in Theoretical Computer Science Conference (ITCS 2019
影响因子：
--
作者：
Dwork, C;Ilvento, C
通讯作者：
Ilvento, C
赞助搜索拍卖中的多类别公平性
DOI：
10.1145/3351095.3372848
发表时间：
2020
期刊：
and Transparency
影响因子：
--
作者：
Ilvento, Christina;Jagadeesan, Meena;Chawla, Shuchi
通讯作者：
Chawla, Shuchi