Generalizing Fair Top-$k$ Selection: An Integrative Approach

Guangya Cai

cs.DSMar 5, 2026

Generalizing Fair Top- $k$ Selection: An Integrative Approach

Authors: Guangya Cai

Organizations: University of Minnesota, Twin Cities, MN, USA

Abstract

Fair top- $k$ selection, which ensures appropriate proportional representation of members from minority or historically disadvantaged groups among the top- $k$ selected candidates, has drawn significant attention. We study the problem of finding a fair (linear) scoring function with multiple protected groups while also minimizing the disparity from a reference scoring function. This generalizes the prior setup, which was restricted to the single-group setting without disparity minimization. Previous studies imply that the number of protected groups may have a limited impact on the runtime efficiency. However, driven by the need for experimental exploration, we find that this implication overlooks a critical issue that may affect the fairness of the outcome. Once this issue is properly considered, our hardness analysis shows that the problem may become computationally intractable even for a two-dimensional dataset and small values of $k$ . However, our analysis also reveals a gap in the hardness barrier, enabling us to recover the efficiency for the case of small $k$ when the number of protected groups is sufficiently small. Furthermore, beyond measuring disparity as the "distance" between the fair and the reference scoring functions, we introduce an alternative disparity measure $\unicode{x2014}$ utility loss $\unicode{x2014}$ that may yield a more stable scoring function under small weight perturbations. Through careful engineering trade-offs that balance implementation complexity, robustness, and performance, our augmented two-pronged solution demonstrates strong empirical performance on real-world datasets, with experimental observations also informing algorithm design and implementation decisions.

Figures & tables

Panel of Figure 1 — Figure 1: The structure and interplay of key components in this work. Solid arrows denote the primary workflow, while dashed arrows indicate feedback and motivation.

Panel of Figure 2 — Figure 2: $(k-1)$ -level (triangular mesh) and $V$ (dashed region on the $x$ - $y$ plane) in 3-D. The dotted region (on the $x$ - $y$ plane) represents a projected fair cell $\mathcal{F}$ and the point inside $V$ represents the input reference weight vector $w^{o}$ . When minimizing the $w$ difference, the resulting fair weight vector will lie on the boundary of $\mathcal{F}$ . In contrast, minimizing the utility loss enables a stable weight vector by selecting a weight vector inside $\mathcal{F}$ and away from its boundary.

Panel of Figure 3 — Figure 3: (a) $w$ difference minimization in 2-D, where the interval represents $V$ and the vertical dashed line $w^{o}$ represents the reference weight vector. The bidirectional sweep-line algorithm works by sweeping from $w^{o}$ to $ub$ and to $lb$ . (b) For the weight vectors $\hat{w}$ and $\widetilde{w}$ with $k=3$ , $l_{p}$ (resp. $l_{q}$ ) is in the top- $k$ subset of $\hat{w}$ (resp. $\widetilde{w}$ ) but not in that of $\widetilde{w}$ (resp. $\hat{w}$ ). Intuitively, $l_{p}$ lies above $l_{q}$ at $x=w_{x}^{o}$ since the two lines intersect at a point between $x=\hat{w}_{x}$ and $x=\widetilde{w}_{x}$ , where their orders change.

Panel of Figure 4 — Figure 4: Runtime experimental results for 2-D datasets.

Panel of Figure 5 — Figure 5: Runtime experimental results for multi-dimensional datasets ( $3\leq d\leq 6$ ).

Dataset	$\epsilon$	Fairness constraint 1	$w$ difference			Utility loss
Dataset	$\epsilon$	Fairness constraint 1	$k$ -level	MILP	Optimal	$k$ -level	MILP	Optimal
COMPAS ( $k=50$ )	0.05	$[34\%,66\%]$	0.149	0.211	0.060	0.476%	1.210%	0.392%
		$[40\%,60\%]$	0.144	0.213	0.073	0.449%	1.328%	0.347%
		$[44\%,56\%]$	0.155	0.202	0.086	0.718%	1.319%	0.656%
	0.025	$[40\%,60\%]$	0.088	0.090	0.044	0.121%	0.142%	0.086%
	0.05		0.144	0.213	0.073	0.449%	1.328%	0.347%

Table 1: Validation results for

n_{p}=1

$\epsilon$	Found/Unfair Ratio 1	$w$ difference			Utility loss
$\epsilon$	Found/Unfair Ratio 1	$k$ -level	MILP	Optimal	$k$ -level	MILP	Optimal
0.025	2/45	0.068	0.133	0.025	0.075%	0.310%	0.032%
0.05	7/45	0.184	0.203	0.113	0.093%	1.227%	0.080%
0.075	16/45	0.273	0.300	0.191	2.635%	3.338%	2.458%

Table 2: Validation results for COMPAS dataset with default fairness constraints (

n_{p}=3

) and

k=50

Algorithmic Fairness

Algorithmic fairness studies how automated decisions distribute errors, opportunities, and harms across groups, and how to measure and reduce disparities.

See all 419 papers

May 7, 2026

Price of Fairness in Short-Term and Long-Term Algorithmic Selections

Algorithmic decision-making in high-stakes settings can have profound impacts on individuals and populations. While much prior work studies fairness in static settings, recent results show that enforcing static fairness constraints may exacerbate long-run disparities. Motivated by this tension, we study a stylized sequential selection problem in which a decision-maker repeatedly selects individuals, affecting both immediate utility and the population distribution over time. We introduce notions of group fairness for both the short and long term and theoretically analyze the trade-off between fairness and utility via the Price of Fairness (PoF). We characterize optimal and fair policies in the short term and show that the PoF can be large even when group distributions are nearly identical. In contrast, we show that long-term disparities can vanish under simple investment policies that achieve a low PoF. We also empirically validate these theoretical observations using both synthetic and real datasets.

Shahin Jabbari, Chen Wang

Drexel University · Rensselaer Polytechnic Institute

Sequential Decision Making Algorithmic Fairness Group Fairness

Ask PDF

Jun 24, 2026

Scoring Is Not Enough: Addressing Gaps in Utility-fairness Trade-offs for Ranking

Scoring functions are used to represent the relevance of individual documents. In modern information retrieval or recommendation systems, they are often learned from data and play a pivotal role in ranking sets of documents or items in a way that maximizes utility to a query or user. With the recent interest in algorithmic fairness, the success of scoring has naturally led to methods that learn scores that simultaneously trade off fairness and utility. In this work, we show that in stark contrast with utility-centric objectives, scoring is sub-optimal in achieving all utility-fairness trade-offs. We establish this with a series of counter-examples with a generic fairness formulation. We show that the issue persists whether we have a deterministic scoring function or a randomized one, or whether we measure fairness at the scope of a single query or across multiple queries. On the positive side, we empirically demonstrate that semi-greedy post-processing has the potential to achieve much better trade-offs, often approaching the ideal of exhaustive post-processing in a tractable way.

Shubham Singh, Ian A. Kash, Mesrob I. Ohannessian

Department of Computer Science University of Illinois Chicago Chicago, IL 60607 · Department of Electrical and Computer Engineering University of Illinois Chicago Chicago, IL 60607

Learning to Rank Algorithmic Fairness

Ask PDF

Sep 7, 2026

A Tight 3-Approximation for Fair $k$ -Means

Fairness in clustering has attracted sustained research interest, motivated by the need to ensure equitable representation of protected groups in machine learning applications. We study fair

k

-means clustering in Euclidean space, where the proportion of each protected group in every cluster must lie within specified lower and upper bounds. These constraints make it challenging to determine both cluster centers and point assignments. Our algorithm first splits the input into many small fair clusters and then merges them into

k

clusters with a weighted

k

-means algorithm. The merge is cheap only when the small clusters do not move points away from their optimal centers, so we add a displacement penalty to the split, which charges each point for how far the small clusters move it. Given a

ρ

-approximate algorithm for weighted

k

-means and any

ε>0

, our algorithm returns a fractional solution whose cost is at most

3ρ+ε

times the optimal integral fair cost. With a PTAS as the subroutine, the approximation ratio becomes

3+O(ε)

, improving the previous factor of

5+O(ε)

. This ratio is the best possible: unless P=NP, no polynomial-time algorithm achieves the ratio

3-δ

for any fixed

δ>0

, even in one dimension. The solution satisfies all fairness constraints exactly and can be rounded to an integral assignment with a bounded additive violation of fairness and no increase in cost. The same approximation guarantee extends to the

k

-sparse Wasserstein barycenter problem.

Kangke Cheng, Guanlin Mo, Shihong Song +1

University of Science and Technology of China, Hefei, China · School of Informatics, University of Edinburgh, Edinburgh, UK

Clustering Group Fairness Wasserstein Barycenters Approximation Algorithms

Ask PDF

Abstract

Algorithmic Fairness

Explore similar work

Price of Fairness in Short-Term and Long-Term Algorithmic Selections

Scoring Is Not Enough: Addressing Gaps in Utility-fairness Trade-offs for Ranking

A Tight 3-Approximation for Fair kkk-Means

A Tight 3-Approximation for Fair $k$ -Means