Ranking with Fairness Constraints (2017-04-22T00:00:00.000000Z)

TL;DR

This work studies the following variant of the traditional ranking problem when the objective satisfies properties that appear in common ranking metrics such as Discounted Cumulative Gain, Spearman's rho or Bradley-Terry.

Abstract

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.

References60 items

Filter bubble

Fair and Diverse DPP-based Data Summarization

Multiwinner Voting with Fairness Constraints

Measuring Fairness in Ranked Outputs

How to be Fair and Diverse?

Who views online extremism? Individual attributes leading to exposure

Inherent Trade-Offs in the Fair Determination of Risk Scores

False Positives, False Negatives, and False Analyses: A Rejoinder to "Machine Bias: There's Software Used across the Country to Predict Future Criminals. and It's Biased against Blacks"

Semantics derived automatically from language corpora contain human-like biases

On the Complexity of Constrained Determinantal Point Processes

Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embeddings

Sequential Voting Promotes Collective Discovery in Social Recommendation Systems

The proof and measurement of association between two things.

The search engine manipulation effect (SEME) and its possible impact on the outcomes of elections

Exposure to ideologically diverse news and opinion on Facebook

Unequal Representation and Gender Stereotypes in Image Search Results for Occupations

New approaches to multi-objective optimization

Learning Fair Representations

2log1-ε n hardness for the closest vector problem with preprocessing

Universal Factor Graphs

Online selection of diverse results

Fairness through awareness

Generalized distances between rankings

Redundancy, diversity and interdependent document relevance

Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality

An axiomatic approach for result diversification

Avoiding monotony: improving the diversity of recommendation lists

Novelty and diversity in information retrieval evaluation

Learning diverse rankings with multi-armed bandits

Greedy in Approximation Algorithms

A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem

Greedy Approximation via Duality for Packing, Combinatorial Auctions and Routing

Improving recommendation lists through topic diversification

On the Complexity of Approximating k-Dimensional Matching

Beyond independent relevance: methods and evaluation metrics for subtopic retrieval

Comparing top k lists

Cumulated gain-based evaluation of IR techniques

Rank aggregation methods for the Web

Clique is hard to approximate withinn1−ε

The Use of MMR, Diversity-Based Reranking for Reordering Documents and Producing Summaries

The probability ranking principle in IR

A new rounding procedure for the assignment problem with applications to dense graph arrangement problems

Fully Proportional Representation

Improved approximations of packing and covering problems

Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer

Term-Weighting Approaches in Automatic Text Retrieval

Implementation of the SMART Information Retrieval System

On Relevance, Probabilistic Indexing and Information Retrieval

RANK ANALYSIS OF INCOMPLETE BLOCK DESIGNS THE METHOD OF PAIRED COMPARISONS

‘FOOTRULE’ FOR MEASURING CORRELATION

What Do Users Want in Q&A Sites: Quality or Diversity

Big Data's Disparate Impact

Battling algorithmic bias: how do we ensure algorithms treat us fairly

Fairness Constraints: A Mechanism for Fair Classification

Ranked bandits in metric spaces: learning diverse rankings over large document collections

An Introduction to Information Retrieval

Electronic Colloquium on Computational Complexity, Report No. 100 (2005) Linear Degree Extractors and the Inapproximability of MAX CLIQUE and CHROMATIC NUMBER

Comparing Partial Rankings *

Clique is hard to approximate within n 1 − ǫ

Jenkyns. The Efficacy of the ’greedy