Maxmin-Fair Ranking: Individual Fairness under Group-Fairness Constraints

• URL: http://arxiv.org/abs/2106.08652v2
• Date: Thu, 17 Jun 2021 09:10:05 GMT
• Title: Maxmin-Fair Ranking: Individual Fairness under Group-Fairness Constraints
• Authors: David Garcia-Soriano and Francesco Bonchi
• Abstract summary: We study a novel problem of fairness in ranking aimed at minimizing the amount of individual unfairness introduced when enforcing group-fairness constraints. Our proposal is rooted in the distributional maxminmin theory which uses randomization to maximize the expected satisfaction of the worst-off individuals.
• Score: 11.3077234652777
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a novel problem of fairness in ranking aimed at minimizing the amount of individual unfairness introduced when enforcing group-fairness constraints. Our proposal is rooted in the distributional maxmin fairness theory, which uses randomization to maximize the expected satisfaction of the worst-off individuals. We devise an exact polynomial-time algorithm to find maxmin-fair distributions of general search problems (including, but not limited to, ranking), and show that our algorithm can produce rankings which, while satisfying the given group-fairness constraints, ensure that the maximum possible value is brought to individuals.

Related papers

• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions. We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• 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)
• Individual Fairness under Varied Notions of Group Fairness in Bipartite Matching - One Framework to Approximate Them All [1.9963683296786414]
  We study the assignment of items to platforms that satisfies both group and individual fairness constraints. Our approach explores a best of both worlds fairness' solution to get a randomized matching. We present two additional approximation algorithms that users can choose from to balance group fairness and individual fairness trade-offs.
  arXiv  Detail & Related papers  (2022-08-21T19:33:36Z)
• How Robust is Your Fairness? Evaluating and Sustaining Fairness under Unseen Distribution Shifts [107.72786199113183]
  We propose a novel fairness learning method termed CUrvature MAtching (CUMA) CUMA achieves robust fairness generalizable to unseen domains with unknown distributional shifts. We evaluate our method on three popular fairness datasets.
  arXiv  Detail & Related papers  (2022-07-04T02:37:50Z)
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
  We study the regret of Thompson sampling (TS) algorithms for exponential family bandits, where the reward distribution is from a one-dimensional exponential family. We propose a Thompson sampling, termed Expulli, which uses a novel sampling distribution to avoid the under-estimation of the optimal arm.
  arXiv  Detail & Related papers  (2022-06-07T18:08:21Z)
• Enforcing Group Fairness in Algorithmic Decision Making: Utility Maximization Under Sufficiency [0.0]
  This paper focuses on the fairness concepts of PPV parity, false omission rate (FOR) parity, and sufficiency. We show that group-specific threshold rules are optimal for PPV parity and FOR parity. We also provide a solution for the optimal decision rules satisfying the fairness constraint sufficiency.
  arXiv  Detail & Related papers  (2022-06-05T18:47:34Z)
• Max-Min Grouped Bandits [48.62520520818357]
  We introduce a multi-armed bandit problem termed max-min grouped bandits. The goal is to find a group whose worst arm has the highest mean reward. This problem is of interest to applications such as recommendation systems.
  arXiv  Detail & Related papers  (2021-11-17T01:59:15Z)
• Robust Learning of Optimal Auctions [84.13356290199603]
  We study the problem of learning revenue-optimal multi-bidder auctions from samples when the samples of bidders' valuations can be adversarially corrupted or drawn from distributions that are adversarially perturbed. We propose new algorithms that can learn a mechanism whose revenue is nearly optimal simultaneously for all true distributions'' that are $alpha$-close to the original distribution in Kolmogorov-Smirnov distance.
  arXiv  Detail & Related papers  (2021-07-13T17:37:21Z)
• Lexicographically Fair Learning: Algorithms and Generalization [13.023987750303856]
  Lexifairness asks that amongst all minimax fair solutions, the error of the group with the second highest error should be minimized. We derive oracle-efficient algorithms for finding approximately lexifair solutions in a very general setting.
  arXiv  Detail & Related papers  (2021-02-16T21:15:42Z)
• Minimax Group Fairness: Algorithms and Experiments [18.561824632836405]
  We provide provably convergent oracle-efficient learning algorithms for minimax group fairness. Our algorithms apply to both regression and classification settings. We show empirical cases in which minimax fairness is strictly and strongly preferable to equal outcome notions.
  arXiv  Detail & Related papers  (2020-11-05T21:42:56Z)
• Fair Correlation Clustering [92.15492066925977]
  We obtain approximation algorithms for correlation clustering under several important types of fairness constraints. We show that fair solutions to correlation clustering can be obtained with limited increase in cost compared to the state-of-the-art (unfair) algorithms.
  arXiv  Detail & Related papers  (2020-02-06T14:28:21Z)

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.