• Computer Science > Databases [Submitted on 14 Mar 2025 (v1), last revised 19 Feb 2026 (this version, v4)] Title:Finding a Fair Scoring Function for Top-$k$ Selection: From Hardness to Practice View PDFAbstract:Selecting a subset of the $k$ “best” items from a dataset of $n$ items, based on a scoring function, is a key task in decision-making. • Given the rise of automated decision-making software, it is important that the outcome of this process, called top-$k$ selection, is fair. • Here we consider the problem of identifying a fair linear scoring function for top-$k$ selection. • The function computes a score for each item as a weighted sum of its (numerical) attribute values, and must ensure that the selected subset includes adequate representation of a minority or historically disadvantaged group. • Existing algorithms do not scale efficiently, particularly in higher dimensions. • Our hardness analysis shows that in more than two dimensions, no algorithm is likely to achieve good scalability with respect to dataset size, and the computational complexity is likely to increase rapidly with dimensionality.
Article Summaries:
- Computer Science > Databases [Submitted on 14 Mar 2025 (v1), last revised 19 Feb 2026 (this version, v4)] Title:Finding a Fair Scoring Function for Top-$k$ Selection: From Hardness to Practice View PDFAbstract:Selecting a subset of the $k$ “best” items from a dataset of $n$ items, based on a scoring function, is a key task in decision-making. Given the rise of automated decision-making software, it is important that the outcome of this process, called top-$k$ selection, is fair. Here we consider the problem of identifying a fair linear scoring function for top-$k$ selection. The function compu
Sources: