Designing Fair Ranking Schemes

Abolfazl Asudeh; H. V. Jagadish; Julia Stoyanovich; Gautam Das

Source-linked AI summary

Designing Fair Ranking Schemes

Abolfazl Asudeh, H. V. Jagadish, Julia Stoyanovich, Gautam Das

arXiv:1712.09752v2Dec 28, 2017cs.DB

TL;DR

Fairness in score-based rankings depends on how users weight numeric attributes, yet choosing weights that preserve desired quality while satisfying fairness constraints is difficult. The paper characterizes satisfactory regions in weight space and builds a system that checks proposed rankings or suggests nearby fair alternatives. Experiments on real datasets report effective and efficient satisfaction of fairness criteria, while the methods assume a fixed number of dimensions and focus experimentally on proportionality constraints.

Problem
Fair ranking requires choosing weights that mitigate bias in data-driven rankings while preserving a user’s a priori notion of quality.
Method
The system characterizes linear ranking-function space, identifies regions satisfying fairness constraints, and finds the nearest satisfactory function for a user query.
Results
Extensive experiments on real datasets confirm the efficiency and effectiveness of the proposed techniques.
Takeaways & Limitations
The approach supports interactive fair-ranking design by preprocessing datasets offline and answering user requests in real time.
Takeaways & Limitations
The techniques are provided for a fixed number of dimensions, and experiments focus on proportionality constraints over demographic groups at top-k.

Abstract

from arXiv · show

Items from a database are often ranked based on a combination of multiple criteria. A user may have the flexibility to accept combinations that weigh these criteria differently, within limits. On the other hand, this choice of weights can greatly affect the fairness of the produced ranking. In this paper, we develop a system that helps users choose criterion weights that lead to greater fairness. We consider ranking functions that compute the score of each item as a weighted sum of (numeric) attribute values, and then sort items on their score. Each ranking function can be expressed as a vector of weights, or as a point in a multi-dimensional space. For a broad range of fairness criteria, we show how to efficiently identify regions in this space that satisfy these criteria. Using this identification method, our system is able to tell users whether their proposed ranking function satisfies the desired fairness criteria and, if it does not, to suggest the smallest modification that does. We develop user-controllable approximation that and indexing techniques that are applied during preprocessing, and support sub-second response times during the online phase. Our extensive experiments on real datasets demonstrate that our methods are able to find solutions that satisfy fairness criteria effectively and efficiently.

1. INTRODUCTION

The paper frames fair ranking as choosing score weights that preserve a user’s quality preferences while mitigating bias in data-driven rankings. It develops an interactive system that identifies fairness-satisfying weight regions and proposes nearby fair alternatives.

Motivation: Score-based ranking schemes compute scores from attribute values and use them to order individuals or return a top-k subset.Common applications include creditworthiness, college admissions, employment, and dating.
Goal: The system helps users design ranking functions that reflect a priori notions of quality while mitigating preexisting bias associated with protected features.Protected features may include legally protected categories or under-represented groups by gender or ethnicity.
Example: In the admissions example, equal weighting of GPA and SAT produces too few women in the top-500, while a modified function f ′(t) = 0.45×s+0.55×g meets the fairness constraint.The original ranking returned 150 women when at least 200 were expected.
Motivation: Subjectively chosen weights can encode or amplify discrimination, especially when protected-group disparities already exist in the data.The paper cites historical admissions practices that assigned high weight to legacy status to reduce Jewish enrollment.
Goal: Given a dataset, users select weights after observing its attribute distribution so the resulting ranking satisfies desired fairness and diversity criteria.This reverses the usual learning setup, where weights are learned from known outcomes.
System: The proposed system preprocesses candidate data offline and supports real-time user queries for score-based ranking functions evaluated by a fairness oracle.The oracle determines whether an ordered list meets the specified fairness criteria.
Contributions: The methods support broad group-fairness constraints, including bounds on top-k group membership, multiple non-overlapping groups, and multiple sensitive attributes.The fairness constraints are evaluated as a black box over ranked lists.
Contributions: The paper characterizes weight-vector space, partitions it into satisfactory and unsatisfactory regions, and finds the nearest satisfactory scoring function when one exists.It also proposes a query-answering system for ranking functions that meet fairness requirements.

2. PRELIMINARIES

The paper models ranking functions as non-negative linear weights over item attributes and interprets them geometrically as rays whose induced orderings can be tested for fairness. Its core query is to find the closest fair function to a user’s proposed function.

Data model: Each item is represented by a d-dimensional vector of non-negative scalar scoring attributes, with larger values preferred.The model also associates items with one or more type attributes representing protected features such as gender or race.
Ranking model: A linear ranking function uses a non-negative weight vector to compute each item’s score as a weighted sum, then ranks items by decreasing score.The ranking model assumes weights w_j ≥ 0.
Geometric interpretation: Geometrically, a weight vector is a ray from the origin, and the induced ordering is determined by item projections onto that ray.The two-dimensional example represents f = x + y with the ray through {1,1}.
Geometric interpretation: Positive rescaling of a weight vector leaves the item ordering unchanged, so distance between ranking functions is measured as angular distance between their rays.Thus f = x + y and f ′ = 100x + 100y have distance 0.
Fairness model: A fairness oracle maps an ordered list of dataset items to true or false, and a scoring function is satisfactory when its induced ordering passes the oracle.The experimental fairness model focuses on proportionality constraints over demographic groups at top-k.
Query problem: The closest-satisfactory-function problem seeks a fair function f ′ whose weight vector minimizes angular distance from the user’s function f.If no fair function exists, the system must report that the constraint is unsatisfiable.
System approach: The solution uses offline preprocessing and online data structures to find similar satisfactory weight vectors quickly during interactive design.The paper contrasts this goal with methods requiring nonlinear optimization for each satisfactory region.

3. THE TWO-DIMENSIONAL CASE

In two dimensions, ranking functions are rays whose induced item order changes only at pairwise ordering exchanges. These exchanges partition weight space into sectors and regions that can be indexed offline and queried efficiently for fair alternatives.

2D ranking geometry: A 2D ranking function is represented by a ray, and item order is determined by projections onto that ray.Although infinitely many rays exist, the induced orderings are limited to item permutations.
Ordering exchange: An ordering exchange occurs where two items have equal projected scores and switch relative order as the ray rotates.For t1=⟨1,2⟩ and t2=⟨2,1⟩, the exchange occurs at f=x+y.
Ordering exchange: Ordering exchanges form the boundaries at which a fairness constraint may change from satisfied to unsatisfied.Thus, fairness regions can be identified by examining the sectors between exchanges.
Offline processing: Dual-space transformation represents each item as a line, whose intersections identify pairwise ordering exchanges along ranking-function rays.The ordering for a weight vector is given by intersections of item lines with the corresponding ray.
Offline processing: 2DRAYSWEEP computes exchange angles, sorts them, updates the item order while sweeping across sectors, and joins neighboring satisfactory sectors into regions.The algorithm stores region boundaries as start and end angles and uses a fairness oracle for each sector.
Offline processing: 2DRAYSWEEP runs in O(n^2(log n + O_n)), where O_n is the oracle time for n items.The bound follows from O(n^2) exchanges, sorting, and one oracle call per sector.
Online processing: For an online query, binary search returns the original function if satisfactory or the nearest satisfactory border otherwise.The sorted satisfactory-region index supports O(log n) query time.

4. THE MULTI-DIMENSIONAL CASE

The paper extends its geometric framework to multiple attributes by representing ranking functions in an angle coordinate system, where pairwise ordering exchanges become hyperplanes. It then constructs and tests satisfactory regions to identify weight choices meeting fairness criteria.

Ordering exchanges: For each item pair, the ordering exchange consists of functions assigning both items the same score and forms a (d−2)-dimensional hyperplane in angle coordinates.In three dimensions, the exchange is a line.
Angle coordinate system: Multi-attribute ranking functions are represented by d−1 angles in an angle coordinate system, with each function mapped to one point.Each angle ranges from 0 to π/2.
Ordering exchanges: HYPERPOLAR computes an ordering-exchange hyperplane from d−1 independent points by solving Θ × h_i,j = ι, yielding h_i,j = Θ^−1 × ι.For fixed d, the algorithm runs in O(d^3), which is O(1).
Satisfactory regions: The system constructs convex regions from ordering-exchange hyperplanes, where item orderings remain unchanged within each region, and checks each region for fairness.An intersecting hyperplane splits a convex region into two half-space intersections; a representative point is then tested with the fairness oracle.
Complexity: For a fixed number of dimensions, the exact multi-dimensional procedure has time complexity O(n^2(d−1)NLp(n^2)), where NLp(n^2) is the time for nonlinear programming.The arrangement complexity contributes the exponential dependence on d−1.

5. APPROXIMATION

The approximation method partitions angle space into cells and assigns each cell a satisfactory function during preprocessing. This supports fast online answers while bounding the returned function’s angular distance from the closest satisfactory choice.

Approximation framework: The method partitions angle space into N hypercube cells, using a user-controlled parameter to bound the maximum angular distance between functions within each cell.This addresses the need for interactive responses that the exact baseline cannot provide efficiently.
Approximation framework: Preprocessing assigns each cell a satisfactory function whose angular distance from functions in that cell and their optimal answers stays within a threshold based on N.Cells intersecting satisfactory regions receive corresponding satisfactory functions; other cells receive the nearest discovered satisfactory function.
Cell indexing: CELLPLANE× hierarchically identifies cells intersecting a hyperplane by pruning hyperrectangles that the hyperplane does not cross.The quadtree-style recursion divides only hyperrectangles intersected by the hyperplane.
Cell indexing: MARKCELL and its arrangement-tree procedure stop when they find a satisfactory function inside a cell, avoiding construction of the remaining arrangement.In the example, f8 is found satisfactory after f1 through f7 are rejected, so processing stops.
Online answering: After preprocessing, every cell stores an assigned satisfactory function, enabling MDONLINE to answer queries in O(log N) time.The returned function’s angle distance is bounded by θ_app ≤ θ_opt plus the approximation bound determined by the partition parameter.

6. EXPERIMENTAL EVALUATION

Experiments on real datasets evaluate fairness models, validation quality, and preprocessing and online-query performance. The methods find nearby satisfactory ranking functions and substantially improve arrangement construction efficiency.

6.1 Experimental Setup: Experiments use real datasets, including COMPAS and a large US DOT flight database, with two general fairness models.FM1 tests proportional representation for a single type attribute; FM2 extends this to multiple, possibly overlapping, type attributes.
6.2 Validation experiments: In 38 of 48 cases, the suggested function had θ(f, f′) < 0.4, corresponding to cosine similarity 0.92.All cases had θ(f, f′) < 0.6, or cosine similarity 0.82.
6.2 Validation experiments: For race fairness, every input function had a satisfactory alternative with θ(f, f′) < 0.11 and cosine similarity above 0.99.The stricter FM2 validation also kept the maximum angle below 0.28.
6.3 Online performance: Online methods locate satisfactory cells in O(log N) time and ran in under 2 milliseconds across tested dimensions.In 2D, 2DONLINE uses binary search and confirms O(log n) query behavior.
6.4 Performance of preprocessing: The arrangement tree reduced the 8,000-second baseline cost by about 7,740 seconds and expanded construction from 250 to 1,200 hyperplanes.Without the tree, later hyperplane additions require checking more than 5,000 regions instead of fewer than 200 initially.
6.4 Performance of preprocessing: Preprocessing remains dominated by arrangement construction, although local hyperplane processing, arrangement trees, and early stopping reduce runtime.The number of hyperplanes approaches n^2 as dimensions increase, while assigning the closest satisfactory cell is consistently fast.

7. RELATED WORK

The paper builds on work measuring fairness in ranked lists, constructing fair rankings, and selecting fair or diverse sets. Its techniques are independent of the fairness function and therefore extend to broad diversity definitions.

Fairness and diversity: Prior work studies fairness measurement in ranked lists, fair ranked-list construction, and fair or diverse set selection.Related studies include proportional representation across ranking prefixes and constraints for protected groups.
Connection to diversity: The proposed techniques accept any binary-output function that evaluates an item ordering, rather than requiring a specific fairness definition.This oracle-based design supports a general range of diversity definitions.
Geometric foundations: The geometric methods draw on combinatorial geometry, especially hyperplane arrangements and incremental arrangement construction.The paper positions these techniques alongside prior work on arrangement complexity and applications.

8. FINAL REMARKS

The paper presents a system for selecting fair weights for linear ranking functions using offline indexes and reports effective, efficient results on real datasets. Its techniques assume a fixed number of dimensions, while oracle-specific optimizations remain future work.

Contributions: The system assists users in choosing weights for linear score-based rankings that satisfy fairness requirements.Offline indexes support efficient query answering, and experiments on real datasets assess effectiveness and efficiency.
Future optimizations: Additional information about the fairness oracle can enable optimizations, such as restricting arrangement construction to items in the top-k convex layers.The paper identifies this as future work rather than part of the general techniques presented.
Scope boundary: The techniques are provided for a fixed number of dimensions; extending them to a variable number of dimensions is future work.The paper also plans to explore oracle-specific complexity reductions.

A.1 Angle distance computation

Linear ranking functions are represented as rays from the origin, and angle coordinates provide a scale-independent representation of their directions. The angle between two rays is computed through the cosine similarity of representative points.

Angle representation: A linear ranking function is represented by a ray from the origin and encoded using d − 1 angles.All points on the same ray share the same angular coordinates, so the representation captures direction rather than magnitude.
Representative points: Each ray can be represented by a point with unit radial coordinate and its angular coordinates.The paper denotes such a representative point as p_i = ⟨1, Θ(i)⟩.
Distance computation: The angular distance between two ranking functions is obtained from the cosine similarity of their representative points.The resulting θ_ij measures the angle between the corresponding rays.

A.2 Angle space partitioning

The paper partitions angle space into N equal-area cells using the first-quadrant unit hypersphere, then represents the partition recursively as a tree of axis ranges. This construction supports controllable angular approximation and can be generated in O(N) time for constant dimension.

N equal-area cells are formed by partitioning the first-quadrant unit hypersphere into hypercones with equal surface area.The method treats each hypercone’s base as a hypercube on the hypersphere surface and approximates cone area by base area for sufficiently small cells.
The cell side length γ is chosen from the equal-area construction and converted into angular separation between rays at neighboring cell corners.The resulting γ is then used for angle-space partitioning.
The partition uses angle axes θ1 through θd−1 and stores nested angle ranges and subcells in a depth-(d−1) tree.Each leaf identifies the borders of one cell across all dimensions.
Algorithm 12 recursively advances through angle ranges, creates nested partitions when i < d−1, and returns the partition leaves.Its input is an axis number, prior angle combination, and dimension d.
O(N) time is required to generate the partition when dimension d is constant.The proof counts N cells and observes constant generation cost per leaf in the recursion tree.