Finding a Fair Scoring Function for Top- k k Selection: From Hardness to Practice

Guangya Cai · 2025

Read Finding a Fair Scoring Function for Top- k k Selection: From Hardness to Practice by Guangya Cai (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-11575.txt.

Introduction

Guangya Cai tackles a fairness problem inside ranking software: how to choose a scoring rule that picks the top k items from a large list while giving a disadvantaged group adequate representation. The score for each item is a weighted sum of its numeric traits, and the rule must be found fast enough to use. Earlier methods slow down badly as items and traits multiply.

Cai first proves hardness results: beyond two traits, no method is likely to scale well in the worst case. The proofs also reveal a gap for small values of k, and he turns that gap into an optimized parallel algorithm with large practical gains. For large k, where hardness is robust, he uses a different method that is weaker on paper but faster in practice. Tests on real datasets show speed-ups of several orders of magnitude over the best prior tools.

Catalog record

CREATORGuangya Cai
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE123 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-11575

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Finding a Fair Scoring Function for Top- k k Selection: From Hardness to Practice Guangya Cai Abstract Selecting a subset of the k k “best” items from a dataset of n 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 k selection, is fair. Here we consider the problem of identifying a fair linear scoring function for top- k 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 (i.e., a run time of O ​ ( n ⋅ polylog ​ ( n ) ) O(n\cdot\text{polylog}(n)) ), and the computational complexity is likely to increase rapidly with dimensionality. However, the hardness results also provide key insights guiding algorithm design, leading to our two-pronged solution: (1) For small values of k k , our hardness analysis reveals a gap in the hardness barrier. By addressing various engineering challenges, including achieving efficient parallelism (yielding up to two orders of magnitude speedup with 128 cores), we turn this potential of efficiency into an optimized algorithm delivering substantial practical performance gains. (2) For large values of k k , where the hardness is robust, we employ a practically efficient algorithm which, despite being theoretically worse, achieves superior real-world performance. Experimental evaluations on real-world datasets then explore scenarios where worst-case behavior does not manifest, identifying areas critical to practical performance. Our solution achieves speedups of up to several orders of magnitude compared to the state of the art (SOTA), an efficiency made possible through a tight integration of hardness analysis, algorithm design, practical engineering, and empirical evaluation. University of Minnesota, Twin Cities, MN, [email protected] The author would like to acknowledge the Minnesota Supercomputing Institute (MSI) at the University of Minnesota for providing computing facilities. ccs Information systems Top-k retrieval in databases keywords Fairness, Top- k , Integration † † runningauthor: G. Cai † † copyright: Guangya Cai † † supplement: Artifact Availability : The source code, data, and/or other artifacts have been made available at https://github.com/caiguangya/fair-topk . 1 Introduction Selecting a subset of items from a large dataset, based on certain criteria, is a critical task in decision-making. Typically, a score is computed for each item based on the item’s attributes and then a subset consisting of the highest-scoring items is selected. For example, to decide whom to interview, a recruiter may evaluate multiple attributes (e.g., years of experiences and the relevance of previous jobs) of an applicant and assign each applicant an overall score reflecting their qualifications. Then a small subset is selected by score. To arrive at an overall score, a scoring function is necessary. Among the many different types of scoring functions, a linear-weighted function is often used. Here each numerical attribute is assigned a weight (or preference) to reflect its relative importance and a weighted sum of these attributes’ values determines the overall score. The problem of selecting the k highest-scoring items from a dataset of n items ( k\leq n ) is called Top- k Selection . Given the widespread usage of automated software for decision-making these days, there is an increased emphasis on ensuring that the results of tasks such as top- k selection are fair. Among the different ways of quantifying fairness (e.g., [ 28 , 65 , 67 ] ), a common one is based on ensuring proportional representation, which works as follows: In addition to numerical attributes, each item also has categorical attributes (gender, race, ethnicity, etc.). Typically, one or a combination of these attributes is regarded as a sensitive attribute and one value of this sensitive attribute indicates a membership in a minority or historically disadvantaged group, often referred to as a protected group. The goal then is to identify a top- k subset in which the items of the protected group are in roughly the same proportion as they are in the entire dataset. The degree of fairness of a top- k selection is measured by the difference between the proportion of protected group members in the selected subset and their proportion in the entire dataset. In many applications, one often wants top- k selection results that are both fair and high-quality. To ensure a fair top- k selection that also satisfies other needs, proportional fairness constraints are commonly applied to the results. In many of the previous works (e.g., [ 66 , 17 , 64 ] ), these fairness constraints are applied after the scores of items are determined, which might result in different selection criteria for different groups. However, an intervention in selection criteria after scores are determined might be subject to legal challenges (e.g., Ricci vs. DeStefano [ 56 ] ), so using a fair scoring function to begin with could be a better choice. Besides, one might only be interested in finding a fair scoring function in a subset of scoring functions. For example, to select the top- k applicants to interview for a position, a recruiter might believe the relevance of the applicant’s previous jobs is more important than the applicant’s years of experiences, so they might assign a larger weight to the former attribute than to the latter while designing the scoring function. The other situation could be that one already has a scoring function that does not produce a fair top- k selection, and wants to find a “near-by” scoring function that produces a fair one, that is, each weight of the attribute does not vary from its original value by a lot. Sometimes even knowing there does not exist a “near-by” one could be helpful since that might reveal some negligence in the process of designing the scoring function. Consider the following variation of the example from [ 8 ] : Example 1 . A college admissions officer is developing a selection scheme for a pool of applicants, each possessing multiple relevant attributes. For simplicity, let us consider two of these attributes: high school GPA and SAT score (denoted as g and s ), assuming both of these attributes are properly normalized and standardized. Suppose the given fairness constraint is that at least 40\% women should be in the admitted class. The officer might believe that g and s should have an approximately equal weight, thus having the scoring function f(c)=0.5\times g+0.5\times s to compute a score for each applicant c . Then, the (say) top-500 applicants are selected by score. However, the resulting top-500 applicants might have an insufficient number of women: say, 150 women in the top-500 whereas 200 is desired. This violation may be due to a gender disparity in the SAT score, namely women scored lower on average than men [ 58 ] . The officer might try to fix the scoring function first, by finding a fair scoring function that is close to the original one. By doing so,

Read the complete text