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

We show that for any fixed dimension, $d\ge 3$, the Fair Top-$k$ Selection problem is 3SUM-Hard [47, 22], hence is unlikely to be solvable in $O(n^{2-\delta })$ time for any constant $\delta >0$. Furthermore, based on a result in [20], we show that the problem is unlikely to be solvable in $O(n^{d-1})$ time for any $d\ge 3$. All our conditional lower bounds are established for a special case of the problem, where $k$ is approximately $n/2$, ${𝒢}_1$ contains only one candidate, and $L_k^{{𝒢}_1}=U_k^{{𝒢}_1}$.

For the 3SUM-hardness, it is known that deciding whether three points in a given set in ${ℝ}^2$ lie on a line (a.k.a point collinearity problem) is 3SUM-Hard [22]. By a reduction from the collinearity problem to the Fair Top-$k$ Selection problem, we show the following:

The point collinearity problem is a special case of the Affine Degeneracy problem in ${ℝ}^d$: deciding whether $d+1$ points lie on a hyperplane. Using a similar approach we have:

The conditional lower bounds in fixed dimensions are established using a special case of the problem. Here, we show that our conditional lower bounds also hold when the value of $k$, the number of candidates of ${𝒢}_1$, and the fairness constraint are more general and realistic.

We begin with definitions of key concepts. For a point set $S\subseteq {ℝ}^d$, a point $q\in {ℝ}^d$ is a dominated (resp. dominating) point of $S$ if for any point $p\in S$, (resp. $q_i>p_i$) for all $1\le i\le d$. For any non-negative weight vector, a dominated (resp. dominating) point has a lower (resp. higher) score than any point in $S$. We say a candidate $c$ is a dominated (resp. dominating) candidate of a candidate set $C$ if $p(c)$ is a dominated (resp. dominating) point.

With these concepts, we first consider a general $k$ value. Suppose that we have an efficient algorithm that can only handle $k=\beta n$, where is a fixed constant. We show that it can also be applied to solve the instance in Corollary 6 efficiently.

Corollary 6 suggests a possible extension to arbitrary dimensions, since Affine Degeneracy is NP-hard in arbitrary dimensions [20]. However, a direct extension fails because the reduction requires generating $2^{d-1}$ Fair Top-$k$ Selection instances to circumvent the non-negativity of the weight vector. To resolve this issue, we use an alternative problem, Maximum Independent Set, for the reduction, starting from its binary integer programming formulation [36].

Our hardness results, starting from restricted cases, show that the problem becomes hard to solve for $d\ge 3$ (Remark 5) and demonstrate the curse of dimensionality (Remark 7). Extending these results to more general cases yields key insights for algorithm design:

• $\mathrm{■}$

  Small $k$ Opportunity. The reduction technique used in Theorem 8 breaks down for a sufficiently small $k$ (Remark 9). This suggests the potential of a more efficient algorithm by explicitly leveraging $k$ in the design.

• $\mathrm{■}$

  Large $k$ Practicality. The hardness of the problem is robust for a large $k$, making the existence of worst-case efficient algorithms unlikely. Therefore, designing efficient algorithms for large $k$ should focus on real-world performance.

• $\mathrm{■}$

  Fairness Relaxation Pitfall. Relaxing the fairness constraint may appear to make the problem easier, making an algorithm that starts with a loose constraint and gradually tightens it seems attractive. However, such relaxation does not reduce worst-case computational hardness (Remark 12), limiting its value.

• $\mathrm{■}$

  Non-negativity Trap. With the failure to extend Corollary 6, non-negativity of variables (weights) and most coefficients (scoring attribute values) appears to open the door to efficient mathematical programming techniques (Remark 14). However, our NP-hardness result shows that this non-negativity may not yield runtime improvements.

Drawing on these insights, we arrive at a two-pronged solution: a theoretically grounded algorithm for a small $k$, and a practically efficient algorithm for a large $k$. Next, we demonstrate that the lower bounds are indeed breakable for a small $k$.

The Fair Top-$k$ Selection problem can be solved by the algorithms in [6], which run in $O(n^2(k+\log n))$ (improvable to $O(n^2\log n)$) for $d=2$ and $O(n^{2d+2})$ for a constant $d\ge 3$. In contrast, our algorithm explicitly incorporates $k$, allowing it to run fast when $k$ is small.

Like [6], our algorithm employs a dual transformation, but we adopt a different one given in [12, 48] that is better suited to our setting. Let $p=(p_1,p_2,\mathrm{\dots },p_d)$ be $p(c)$ of a candidate $c\in C$. We transform $p$ into a hyperplane $H(p)$ defined by ($x_1,x_2,\mathrm{\cdots }{x}_d$ are variables)

Given the dual transformation, $k$-level and cell can be defined accordingly ([11, Section 4.2]). One important property of the $k$-level is that if a hyperplane has a cell that is part of the $(k-1)$-level, then the primal point corresponding to the hyperplane is the $k$th point for some weight vectors, since there are exactly $k-1$ hyperplanes lying “above” in the $x_d$ dimension.

We now proceed to the algorithm. Assume the $(k-1)$-level is constructed and cells adjacencies are identified, with hyperplanes in general position (i.e, no more than $d$ hyperplanes intersect at a point), and ties in top-$k$ selection broken arbitrarily. Our algorithm first finds an arbitrary weight vector $t\in V$ and locates a $(k-1)$-level cell intersected by the downward ray induced by $t$. Next, we obtain the corresponding top-$k$ subset and count the number of candidates of ${𝒢}_1$ in the top-$k$ subset, $n_k^{{𝒢}_1}$, and test it against $L_k^{{𝒢}_1}$ and $U_k^{{𝒢}_1}$. If the fairness constraint is satisfied, we output $t$. If not, we traverse the $(k-1)$-level by visiting adjacent cells. For each newly visited cell, we test if its projection onto the first $d-1$ coordinates intersects $V$. If it is, we update the $n_k^{{𝒢}_1}$ as the top-$k$ subsets of adjacent cells differ in at most one candidate. We maintain the $n_k^{{𝒢}_1}$ during the traversal and whenever the top-$k$ subset changes, test $n_k^{{𝒢}_1}$ against $L_k^{{𝒢}_1}$ and $U_k^{{𝒢}_1}$. The algorithm stops when either a fair weight vector is obtained from a $(k-1)$-level cell or all relevant $(k-1)$-level cells have been visited.

For the runtime analysis, leveraging known results of the $k$-level [37, 1, 24, 15], along with an application of an efficient convex polyhedra intersection algorithm [7], we have:

We identify three key engineering challenges for $k$-level-based algorithms to become practical:

• $\mathrm{■}$

  Space Overhead. The $k$-level-based algorithm constructs the entire $k$-level, whose structural complexity may grow quickly with $n$ and $d$. For large datasets, it may exhaust internal memory, requiring much slower external-memory solutions. Yet users may seek a fair weight vector within a small, explainable region, making a full $k$-level unnecessary.

• $\mathrm{■}$

  Hardware Utilization. A prior theoretically efficient algorithm [25] exhibits bad memory performance, which contributes to its slow run time in practice. Moreover, many algorithms are not naturally parallelizable and cannot exploit modern multi-core systems. Bridging the theory-practice gap for parallel algorithms is even more challenging [9].

• $\mathrm{■}$

  Tie-breaking. Most theoretical algorithms for constructing the $k$-level assume general position (limiting ties among candidates) and break ties arbitrarily for simplicity. However, for the fair top-$k$ selection, tie-breaking can affect the number of protected group candidates selected, impacting fairness. In our problem setting, an algorithm must be designed to account for all possible tie-breaking outcomes when evaluating fairness.

Next, we present practical $k$-level-based algorithms, focusing on our methods addressing these challenges. (Tie-breaking will be revisited in Section 5.2 for the MILP-based algorithm.)

For a large $k$ value, our focus becomes designing a practically efficient algorithm, which results in an algorithm based on MILP. We note that MILP is NP-hard and all known algorithms run in exponential times in the worst case. However, in practice, an MILP solver can be quite fast, and it was shown that an MILP-based algorithm is efficient for finding a linear scoring function for the reverse top-$k$ query [16], making it an approach worth considering.

For simplicity, assume without loss of generality that each scoring attribute value is in the range of $[0,1]$. We define a indicator variable ${\delta }_c\in \{0,1\}$ for each candidate $c$ satisfying

for any given weight vector $w$ and a cut-off value $\lambda \in [0,1]$. ${\delta }_c$ encodes the top-$k$ subset membership of $c$ for a $(w,\lambda )$ pair defining a separating hyperplane (see [11, Section 5.2]).

To ensure a value of $\lambda$ will be infeasible unless it yields $k$ candidates with ${\delta }_c=1$, the constraint ${\sum }_c{\delta }_c=k$ is applied. Moreover, the fairness constraint can be encoded as follows:

Finally, constraints on the weight vector (i.e., $V$) can also be easily incorporated. We arrive at a MILP with a weight vector, a cut-off value, and $n$ indicator variables as its unknown variables. Finding a fair weight vector becomes finding a feasible solution to the MILP.

Now, let us revisit the “Non-negativity Trap” (see Section 4.1). In our MILP formulation, all variables ($w$, $\lambda$ and ${\delta }_c$) and most of the coefficients ($p(c)$) are non-negative. The main issue is the negative coefficient of $\lambda$, which prevent direct adaptations of the techniques such as those in [3, 43]. While one might hope to circumvent this inconvenience, our NP-hardness result show that the problem may be fundamentally intractable in the worst case. This also suggests that the practical success of the MILP-based algorithm is largely heuristic.

For our implementation, we use Gurobi [23] – a state-of-the-art, mathematical programming tool – to solve the MILP. This solver also exploits parallelism to enhance performance.

In our experiments, a weight vector $w^o$ is provided as an input. If $w^o$ is unfair, the algorithm is run to find a “nearby” fair weight vector $w^f$. More formally, for a given unfair $w^o$, one aims to find a fair $w^f$ such that $|w_i^f-w_i^o|\le ϵ$ for all $1\le i\le d$, where $ϵ$ is user-specified parameter that limits the allowable deviation. A failure is reported if no such fair $w^f$ exists. We used two real-world datasets, COMPAS ($n=7214$, $2\le d\le 6$) [38] and IIT-JEE ($n=\mathrm{384\hspace{0.17em}977}$, $2\le d\le 3$) [28], with preprocessing as needed. 2draysweep and ATC_$+$ from [6] were implemented as baselines, with several enhancements incorporated. By default, $k=50$, with $ϵ=0.1$ for $d=2$ and $ϵ=0.05$ for $d\ge 3$. See [11, Section 6.1] for the full experimental setup and https://github.com/caiguangya/fair-topk for the code, data, and container [33].

Since our main focus is execution speed, we start with runtime experiments and highlight speedups from better hardware utilization that also enable more informed comparisons [32].

The quality was evaluated using the following metrics: (1) Found/Unfair ratio: the ratio between the number of input unfair weight vectors and found fair ones. (2) $𝒘$ difference: the average $L_1$ distance between $w^o$ and $w^f$. (3) ${𝓖}_{\mathrm{𝟏}}$ proportion: the average ${𝒢}_1$ candidate proportion in the top-$k$ subset derived from $w^f$. (4) Utility loss: the average relative utility difference between the top-$k$ subset derived from $w^o$ and $w^f$. (See [11, Section 6.3].)

Table 1 shows the experimental results. We note that the $k$-level-based algorithm achieved better results for the $w$ difference and utility loss. In fact, these two metrics are related, as a closer $w^f$ to $w^o$ typically yields a top-$k$ subset with high-utility candidates. Our $k$-level-based algorithm naturally favors “nearby” weight vectors due to its breadth-first search approach with $w^o$ as the starting point, while the MILP-based algorithm does not directly leverage $w^o$.

We summarize key experimental observations and discuss algorithm selection based on them.