Source-linked AI summary
Ranking with Fairness Constraints
L. Elisa Celis, Damian Straszak, Nisheeth K. Vishnoi
TL;DR
The paper asks how to maximize ranking quality while enforcing user-specified fairness or diversity bounds on sensitive attributes. It develops exact and approximation algorithms plus hardness results for this constrained matching formulation, leveraging nested constraints and ranking objectives with common structural properties. The results provide a fine-grained view of complexity, including efficient algorithms in several regimes, while some approximation cases can incur substantial constraint violations.
Problem
Ranking can overrepresent content and promote stereotypes or extremist ideology, motivating ranking optimization with fairness constraints on sensitive attributes.
Method
The paper studies constrained maximum-weight matching for rankings and exploits groups of nested constraints, small type diversity, matroid structure, and structured objectives.
Results
The paper establishes exact, approximation, and hardness results, including an exact O(np + m)-time greedy algorithm for (U) when Δ=1.
Takeaways & Limitations
Constrained ranking has fine-grained complexity governed by constraint structure and upper-bound values, while structural properties enable efficient algorithms in several regimes.
Takeaways & Limitations
For large Δ, the approximation algorithm may incur a 2-multiplicative violation of upper-bound constraints, especially when upper bounds are large.
Abstract
from arXiv · showhide
Ranking algorithms are deployed widely to order a set of items in applications such as search engines, news feeds, and recommendation systems. Recent studies, however, have shown that, left unchecked, the output of ranking algorithms can result in decreased diversity in the type of content presented, promote stereotypes, and polarize opinions. In order to address such issues, we study the following variant of the traditional ranking problem when, in addition, there are fairness or diversity constraints. Given a collection of items along with 1) the value of placing an item in a particular position in the ranking, 2) the collection of sensitive attributes (such as gender, race, political opinion) of each item and 3) a collection of constraints that, for each k, bound the number of items with each attribute that are allowed to appear in the top k positions of the ranking, the goal is to output a ranking that maximizes the value with respect to the original rank quality metric while respecting the constraints. This problem encapsulates various well-studied problems related to bipartite and hypergraph matching as special cases and turns out to be hard to approximate even with simple constraints. Our main technical contributions are fast exact and approximation algorithms along with complementary hardness results that, together, come close to settling the approximability of this constrained ranking maximization problem. Unlike prior work on the constrained matching problems, our algorithm runs in linear time, even when the number of constraints is large, its approximation ratio does not depend on the number of constraints, and it produces solutions with small constraint violations. Our results rely on insights about the constrained matching problem when the objective satisfies properties that appear in common ranking metrics such as Discounted Cumulative Gain, Spearman's rho or Bradley-Terry.
1 Introduction
The paper formulates ranking with user-specified fairness constraints to limit overrepresentation of sensitive attributes while maximizing ranking value. It studies the resulting complexity and develops algorithms that exploit nested constraints and structured ranking objectives.
- Problem motivation: Ranking selects and orders n items from m candidates to maximize their position-dependent value in applications including search, feeds, ecommerce, and online media.The unconstrained formulation is equivalent to maximum-weight matching in a complete m × n bipartite graph.
- Problem motivation: Unconstrained rankings can overrepresent content and contribute to stereotypes, extremist ideology, and manipulation of undecided voters.These concerns motivate restricting rankings so that no type of content dominates.
- Fairness formulation: The constrained problem lets users specify lower and upper bounds on how many items with each sensitive property may appear in every top-k prefix.Properties may overlap, such as gender, ethnicity, and age attributes attached to computer-scientist images.
- Fairness formulation: The constrained objective is maximum-weight matching of size n subject to fairness constraints, making its computational complexity the paper’s central object of study.The framework also captures traditional diversification concerns such as query ambiguity and user context.
- Complexity and contributions: Even checking whether a complete feasible ranking exists is NP-hard, and the problem generalizes independent set, hypergraph matching, and set packing.Prior approximation results are inadequate because the problem has 2np fairness constraints and an O(√m) additive violation can make upper bounds ineffective.
- Complexity and contributions: The paper gives exact, approximation, and hardness results that exploit p groups of nested constraints and ranking objectives satisfying property (1).These structural properties yield polynomial- or linear-time algorithms in several regimes, overcoming limitations of prior constrained-matching work.
2 Our Model
The model assigns each item a position-dependent profit and a set of properties, then seeks a ranking represented by an assignment matrix under prefix fairness bounds. It distinguishes the general lower-and-upper-bound case from upper-only and lower-only variants.
- Model definition: The constrained ranking problem maximizes total assignment value over matrices satisfying the specified fairness bounds.The item properties and lower and upper bounds are inputs to the optimization problem.
- Model definition: The model represents rankings of m items into n positions with binary matrices, where W_ij is the profit of placing item i at position j.For each property ℓ and prefix k, L_kℓ and U_kℓ bound the number of property-ℓ items in the top k positions.
- Model variants: The model distinguishes (U) with only upper bounds, (L) with only lower bounds, and (LU) with both types of constraints.These variants are used to organize the paper’s complexity and algorithmic results.
3 Our Results
The paper develops exact, approximation, and hardness results for constrained ranking, with complexity governed by property overlap and constraint structure. It gives polynomial or linear-time algorithms in restricted settings, while showing strong hardness and bounded violations in broader ones.
- Exact algorithms: When the number of distinct property sets q is constant, dynamic programming solves the constrained ranking problem in O(pqn^q + pm) time.The method combines a geometric interpretation with a sequence of q-dimensional subproblems.
- Exact algorithms: For ∆ = 1, the general constrained ranking problem is polynomial-time solvable in eO(n^2m) time through a reduction to minimum-cost flow.The reduction uses an acyclic network, though the resulting polynomial running time may remain impractical.
- Exact algorithms: For ∆ = 1 and objectives satisfying property (1), the LP relaxation is exact, and a greedy algorithm finds an optimal integral solution in O(np + m) time.The integrality result depends on the structure of tight constraints and the objective-function assumption.
- Limitations and open problems: The ∆ = 1 exact LP result does not extend straightforwardly to the general lower-and-upper-bound variant, which the paper leaves as an open problem.The proof crucially uses ∆ = 1 and property (1) of the objective.
- Hardness: For ∆ ≥ 3, feasibility remains NP-hard and optimal-value approximation is hard within O(∆/log ∆), even under condition (4).The hardness results also cover feasibility decisions with fixed properties and distinguishing feasible solutions from solutions violating constraints by any constant factor.
4 Other Related Work
Prior work studies ranking, diversification, selection, fairness, and learning, but this paper distinguishes constrained ranking by requiring both item selection and ordered display under property constraints.
- Information retrieval traditionally ranks selected items by decreasing value, following the probability ranking principle.
- Diverse summarization and voting with diversity select items with varied properties but do not require producing a ranking of those items.
- Learning-to-rank bandit formulations update value estimates from clicks but impose no constraints on how items should be displayed.
- The paper targets property fairness, accepting that property-based display constraints can conflict with item fairness, especially when ranking people.
5 Proof Overviews
The proof overviews develop geometric, flow, and exchange-based views of constrained ranking, yielding exact algorithms in structured cases and approximation guarantees through matroid-style analysis.
- Items are represented by property vectors, and feasible rankings correspond to sequences whose cumulative property vectors remain within prescribed lower and upper regions.
- Grouping items by identical property vectors reduces the exact subproblem to choosing how many items of each vector appear in a feasible ranking.
- Constrained ranking can be reduced to minimum-cost flow on a network whose property chains encode upper bounds and whose position vertices prevent reuse of positions.
- For ∆=1, exchange directions corresponding to 4-cycles improve fractional solutions while preserving constraints, establishing integrality along the relevant objective directions.
- For ∆=1, a greedy algorithm fills positions with the highest-value available feasible item in O(np+m) time.
- For larger ∆, greedy selection over a relaxed feasible set gives a (∆+2)-approximation with at most twice-multiplicative upper-bound violations.
- The hardness results show that feasibility is NP-hard and hard to approximate for ∆≥3, while upper-bound values alone can encode hardness.
6 A Polynomial Time algorithm for ∆= 1
For ∆=1, the paper formulates constrained ranking as a minimum-cost flow problem whose feasible flows and rankings correspond, including lower-bound constraints through cost modifications.
- Lower bounds are enforced by reducing the costs of the L_{ℓ,k} cheapest chain edges by a sufficiently large M, forcing those edges to carry flow.
- The flow construction uses source and sink vertices, one position vertex γ_k per rank, and a chain of ρ_{ℓ,k} vertices for each property.
- Edges from property chains to position vertices represent assigning property-ℓ items to positions, while unit-capacity position-to-sink edges prevent duplicate positions.
- The chain edge costs use successive differences in item values, so a flow path corresponding to item i at position k has cost −W_i,k.
- The Monge property ensures that items sharing a property appear in index-consistent order and that the cheapest chain edges correspond to the best eligible items.
- Flow feasibility enforces upper bounds because chain capacities limit how many property-ℓ units can reach each top-k prefix.
- The recovered optimal ranking weight equals M times the total lower-bound requirement minus the minimum flow cost.
- Because the constructed network is acyclic, shortest-path initialization can avoid Bellman–Ford and yields an implementation running in O(n^2m log m) time.
7 Dynamic Programming-based Exact Algorithm
The paper develops an exact dynamic program for constrained ranking when the weight matrix satisfies a Monge-type property, with efficiency depending on the number of distinct item types. The algorithm tracks feasible prefixes by type counts and runs in O(pqn^q + pm) time.
- Item types group items by identical property-membership vectors, and the algorithm operates on these q distinct types.
- Property (1) implies that, for any selected count from a type, the best items appear in increasing order and precede lower-quality alternatives.
- The dynamic-programming state D[s1, ..., sq] stores the maximum feasible weight for a prefix selecting exactly sℓ items from each type.
- States violating the lower- and upper-bound vectors are assigned −∞; otherwise, each state considers the type of the item placed last and takes the best recurrence value.
- There are at most n^q states, with feasibility checks contributing the p · q · n^q term and input processing contributing pm.
8 Algorithms for ∆= 1 and Upper-Bound Constraints
For disjoint properties and upper-bound constraints, the paper establishes integrality of an optimal LP solution and gives a linear-time optimal greedy algorithm. The greedy procedure repeatedly selects the smallest feasible unselected item.
- Integrality of LP solutions: For ∆ = 1, an optimal integral solution exists for the LP relaxation under property (1), although the feasible region can still have fractional vertices.
- Integrality of LP solutions: The integrality proof first establishes a support-ordering condition preventing crossings among items sharing a property.
- Fast greedy algorithm: O(m + n · p) time suffices to output an optimal ranking for ∆ = 1 and upper-bound constraints.
- Fast greedy algorithm: At each position, the greedy algorithm chooses the smallest-index unselected item that can be added without violating any constraint, reporting infeasibility if none exists.
- Fast greedy algorithm: The greedy ranking is optimal because, for each property, any ranking selecting r items can be transformed to use the first r items of that property in increasing order.
9 A (∆+ 2)-Approximation Algorithm
The paper gives a linear-time approximation algorithm for general constrained ranking under condition (4). It constructs a partial ranking greedily, then completes it while preserving feasibility, achieving a value guarantee with bounded violations.
- A linear-time algorithm returns an integral ranking with weight at least 1/(∆ + 2) of optimum while violating fairness constraints by at most a factor of 2.
- A second greedy phase fills the remaining positions one at a time by choosing an item whose addition preserves the fairness constraints.
- The first phase relaxes the requirement that every position be filled and greedily selects cells in non-increasing order of weight when constraints remain satisfied.
- The approximation proof compares each greedy choice with a constrained optimum and removes at most ∆ + 2 cells to restore relaxed feasibility.
- The completion phase does not reduce value, and the relaxed optimum upper-bounds the original optimum, so the approximation guarantee transfers to the complete ranking.
10 Hardness Results
The hardness results show that constrained ranking feasibility and maximization remain difficult even under restricted or favorable conditions. Reductions from hypergraph matching and independent set establish NP-hardness, approximation barriers, and hardness of bounded constraint violation.
- For every ∆ ≥ 3, constrained ranking feasibility is NP-hard via a reduction from ∆-hypergraph matching.
- Feasible rankings correspond exactly to hypergraph matchings of the target cardinality by treating items as hyperedges and properties as vertices.
- Even when feasibility is guaranteed and condition (4) holds, constrained ranking maximization is NP-hard to approximate within O(∆/log ∆).
- With a fixed family of all two-element properties, checking feasibility from upper-bound constraints alone is NP-hard.
- For every constant c > 0, it is NP-hard to distinguish satisfiable instances from instances with no ranking violating every upper bound by at most c.
11 Discussion and Future Work
The paper characterizes constrained ranking complexity and develops algorithmic insights, while identifying open questions about faster algorithms, constraint violations, richer objectives, sampling, and online settings.
- The constrained ranking maximization problem generalizes classic bipartite matching and exhibits complexity determined by constraint structure and upper-bound values.
- A nearly-linear algorithm remains an open goal for the Δ = 1 (LU) variant, although the paper gives an eO(n^2m)-time algorithm.
- The large-Δ approximation algorithm may incur a 2-multiplicative constraint violation, which can effectively erase large upper-bound constraints.
- The paper leaves open whether suitable submodular objectives can replace its linear objective, whose placement utilities are independent across items.
- Further challenges include sampling rankings proportionally to their value and extending the results to online settings.
A Values Wij and Common Ranking Metrics
The paper frames ranking quality through item relevance and position-dependent values, emphasizing that practical metrics are often normalized without changing the optimization problem.
- Ranking metrics evaluate constrained rankings against unconstrained rankings using item quality, often called relevance in information retrieval.
- Items are relabeled so their qualities satisfy a_1 ≥ a_2 ≥ ··· ≥ a_m, and integral rankings are represented within Ω_m,n.
A.1 Rank-1 Metrics:
Rank-1 metrics assign each item-position placement a value based on item quality and a non-increasing positional discount, covering common measures such as DCG.
- A rank-1 metric sums item qualities discounted by position, making correct ordering more valuable near the top of the list.
- For rank-1 metrics, placement values are W_ij = a_i · f(j), where f is non-increasing; DCG uses f(i) = 1/log(i+1).
- The resulting placement values satisfy the required monotonicity property used in the paper’s constrained optimization framework.
A.2 Bradley-Terry Metrics:
The appendix shows that Bradley-Terry and alignment metrics can be represented in the paper’s placement-value framework, including rank-1 forms with the required structural properties.
- In the Bradley-Terry model, a_i1/(a_i1+a_i2) represents the probability that item i_1 should rank above item i_2.
- Removing the common denominator rewrites the Bradley-Terry objective in a form compatible with the paper’s placement-value formulation.
- With i := log(a_i) and f(j) := m − j, the rewritten Bradley-Terry metric becomes a rank-1 metric with non-increasing positional weights.
- Alignment metrics compare a ranking with the optimal unconstrained ranking x⋆ through item-position differences.
- Spearman’s footrule and Spearman’s rho are adapted to partial rankings and measure similarity rather than difference.
- Their placement values can be written as (2m − i − j) − |j − j⋆| and (2m − i − j)^2 − (j − j⋆)^2, respectively.
- These placement values satisfy the monotonicity and pairwise exchange properties required by the framework; the observations extend to weighted variants.