Sampling Ex-Post Group-Fair Rankings
- URL: http://arxiv.org/abs/2203.00887v3
- Date: Mon, 29 May 2023 05:11:49 GMT
- Title: Sampling Ex-Post Group-Fair Rankings
- Authors: Sruthi Gorantla, Amit Deshpande, Anand Louis
- Abstract summary: We propose two algorithms to sample a random group-fair ranking from the distribution $D$ mentioned above.
Our problem formulation works even when there is implicit bias, incomplete relevance information, or only ordinal ranking is available.
We give empirical evidence that our algorithms compare favorably against recent baselines for fairness and ranking utility on real-world data sets.
- Score: 8.963918049835375
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Randomized rankings have been of recent interest to achieve ex-ante fairer
exposure and better robustness than deterministic rankings. We propose a set of
natural axioms for randomized group-fair rankings and prove that there exists a
unique distribution $D$ that satisfies our axioms and is supported only over
ex-post group-fair rankings, i.e., rankings that satisfy given lower and upper
bounds on group-wise representation in the top-$k$ ranks. Our problem
formulation works even when there is implicit bias, incomplete relevance
information, or only ordinal ranking is available instead of relevance scores
or utility values.
We propose two algorithms to sample a random group-fair ranking from the
distribution $D$ mentioned above. Our first dynamic programming-based algorithm
samples ex-post group-fair rankings uniformly at random in time $O(k^2\ell)$,
where $\ell$ is the number of groups. Our second random walk-based algorithm
samples ex-post group-fair rankings from a distribution $\delta$-close to $D$
in total variation distance and has expected running time $O^*(k^2\ell^2)$,
when there is a sufficient gap between the given upper and lower bounds on the
group-wise representation. The former does exact sampling, but the latter runs
significantly faster on real-world data sets for larger values of $k$. We give
empirical evidence that our algorithms compare favorably against recent
baselines for fairness and ranking utility on real-world data sets.
Related papers
- Fair Active Ranking from Pairwise Preferences [6.102498508368527]
Given a set of $n$ items that belong to disjoint groups, our goal is to find an $(epsilon, delta)$-PACF-Ranking according to a fair objective function that we propose.
We present both group-blind and group-aware algorithms and analyze their sample parameters.
arXiv Detail & Related papers (2024-02-05T18:09:48Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed.
SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
arXiv Detail & Related papers (2023-12-13T11:08:25Z) - Bipartite Ranking Fairness through a Model Agnostic Ordering Adjustment [54.179859639868646]
We propose a model agnostic post-processing framework xOrder for achieving fairness in bipartite ranking.
xOrder is compatible with various classification models and ranking fairness metrics, including supervised and unsupervised fairness metrics.
We evaluate our proposed algorithm on four benchmark data sets and two real-world patient electronic health record repositories.
arXiv Detail & Related papers (2023-07-27T07:42:44Z) - Sampling Individually-Fair Rankings that are Always Group Fair [9.333939443470944]
A fair ranking task asks to rank a set of items to maximize utility subject to satisfying group-fairness constraints.
Recent works identify uncertainty in the utilities of items as a primary cause of unfairness.
We give an efficient algorithm that samples rankings from an individually-fair distribution while ensuring that every output ranking is group fair.
arXiv Detail & Related papers (2023-06-21T01:26:34Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
Group distributionally robust optimization (GDRO)
Online learning techniques to reduce the number of samples required in each round from $m$ to $1$, keeping the same sample.
A novel formulation of weighted GDRO, which allows us to derive distribution-dependent convergence rates.
arXiv Detail & Related papers (2023-02-18T09:24:15Z) - Detection of Groups with Biased Representation in Ranking [28.095668425175564]
We study the problem of detecting groups with biased representation in the top-$k$ ranked items.
We propose efficient search algorithms for two different fairness measures.
arXiv Detail & Related papers (2022-12-30T10:50:02Z) - On the Problem of Underranking in Group-Fair Ranking [8.963918049835375]
Bias in ranking systems can worsen social and economic inequalities, polarize opinions, and reinforce stereotypes.
In this paper, we formulate the problem of underranking in group-fair rankings, which was not addressed in previous work.
We give a fair ranking algorithm that takes any given ranking and outputs another ranking with simultaneous underranking and group fairness guarantees.
arXiv Detail & Related papers (2020-09-24T14:56:10Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
We find an algorithm which finds.
epsilon$-approximate stationary point (with $|nabla F(x)|le epsilon$) using.
$(epsilon,gamma)$surimate random random points.
Our lower bounds here are novel even in the noiseless case.
arXiv Detail & Related papers (2020-06-24T04:41:43Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers.
We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
arXiv Detail & Related papers (2020-02-26T16:19:09Z) - SetRank: A Setwise Bayesian Approach for Collaborative Ranking from
Implicit Feedback [50.13745601531148]
We propose a novel setwise Bayesian approach for collaborative ranking, namely SetRank, to accommodate the characteristics of implicit feedback in recommender system.
Specifically, SetRank aims at maximizing the posterior probability of novel setwise preference comparisons.
We also present the theoretical analysis of SetRank to show that the bound of excess risk can be proportional to $sqrtM/N$.
arXiv Detail & Related papers (2020-02-23T06:40:48Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.