论文标题
DBN暴露模型的排名
Pareto-Optimal Fairness-Utility Amortizations in Rankings with a DBN Exposure Model
论文作者
论文摘要
近年来，很明显，在许多领域提供的排名不仅需要对用户有用，而且还需要尊重物品生产商的曝光公平。我们考虑找到排名政策的问题，这些政策在这两个方面之间实现了帕累托最佳的权衡。提出了几种方法来解决它。例如，一个流行的是将线性编程与伯克霍夫冯·诺伊曼分解。但是，这些方法基于基于经典位置的暴露模型（PBM），该模型假定项目之间的独立性（因此，暴露仅取决于等级）。在许多应用中，此假设是不现实的，社区越来越多地朝着考虑包括依赖性的其他模型（例如动态贝叶斯网络（DBN）暴露模型）迈进。对于此类模型，计算（确切）最佳公平排名策略仍然是一个悬而未决的问题。 我们通过利用一种基于最近针对PBM提出的所谓外籍肾上腺的新几何方法来回答这个问题（Kletti等人，WSDM'22）。我们列出了新的几何对象（dbn-expohedron）的结构，并为其提出了一种复杂性$ o（n^3）$的carathéodory分解算法，其中$ n $是排名的文档数量。这样的算法使表达任何可行的预期暴露向量是最多$ n $排名的分配；此外，我们表明我们可以计算具有相同复杂性$ O（n^3）$的整个帕累托最佳预期曝光向量。我们的工作构成了第一种能够有效找到排名帕累托最佳分布的精确算法。它适用于广泛的公平概念，包括精英和人口公平的经典概念。我们在TREC2020和MSLR数据集上进行了经验评估我们的方法，并将其与帕累托（Pareto）的敏捷性和速度进行比较。
In recent years, it has become clear that rankings delivered in many areas need not only be useful to the users but also respect fairness of exposure for the item producers. We consider the problem of finding ranking policies that achieve a Pareto-optimal tradeoff between these two aspects. Several methods were proposed to solve it; for instance a popular one is to use linear programming with a Birkhoff-von Neumann decomposition. These methods, however, are based on a classical Position Based exposure Model (PBM), which assumes independence between the items (hence the exposure only depends on the rank). In many applications, this assumption is unrealistic and the community increasingly moves towards considering other models that include dependences, such as the Dynamic Bayesian Network (DBN) exposure model. For such models, computing (exact) optimal fair ranking policies remains an open question. We answer this question by leveraging a new geometrical method based on the so-called expohedron proposed recently for the PBM (Kletti et al., WSDM'22). We lay out the structure of a new geometrical object (the DBN-expohedron), and propose for it a Carathéodory decomposition algorithm of complexity $O(n^3)$, where $n$ is the number of documents to rank. Such an algorithm enables expressing any feasible expected exposure vector as a distribution over at most $n$ rankings; furthermore we show that we can compute the whole set of Pareto-optimal expected exposure vectors with the same complexity $O(n^3)$. Our work constitutes the first exact algorithm able to efficiently find a Pareto-optimal distribution of rankings. It is applicable to a broad range of fairness notions, including classical notions of meritocratic and demographic fairness. We empirically evaluate our method on the TREC2020 and MSLR datasets and compare it to several baselines in terms of Pareto-optimality and speed.
