Fair Rank Aggregation
Nov 28, 2022
Speakers
Diptarka Chakraborty
Speaker · 0 followers
Syamantak Das
Speaker · 0 followers
Arindam Khan
Speaker · 0 followers
Aditya Subramanian
Speaker · 0 followers
About
Ranking algorithms find extensive usage in diverse areas such as web search, employment, college admission, voting, etc. The related rank aggregation problem deals with combining multiple rankings into a single aggregate ranking. However, algorithms for both these problems might be biased against some individuals or groups due to implicit prejudice or marginalization in the historical data. We study ranking and rank aggregation problems from a fairness or diversity perspective, where the candidates (to be ranked) may belong to different groups and each group should have a fair representation in the final ranking. We allow the designer to set the parameters that define fair representation. These parameters specify the allowed range for the number of candidates from a particular group in the top-k positions of the ranking. We provide a linear time exact algorithm for finding the closest fair ranking for the Kendall-Tau metric under strong fairness, i.e., when the final ranking is fair for all reasonably large values of k. We also provide an exact algorithm for finding the closest fair ranking for the Ulam metric under strong fairness when there are only O(1) number of groups. Our algorithms are simple and might be extendable to other relevant metrics. We also give a meta-algorithm for the general rank aggregation problem under the fairness framework. Surprisingly, this meta-algorithm works for any generalized mean objective (including center and median problems) and any fairness criteria. As a byproduct, we obtain 3-approximation algorithms for both center and median problems, under both Kendall Tau and Ulam metrics. Furthermore, using sophisticated techniques we obtain a (3-ϵ)-approximation algorithm for the Ulam metric under strong fairness, for a constant ϵ>0.Ranking algorithms find extensive usage in diverse areas such as web search, employment, college admission, voting, etc. The related rank aggregation problem deals with combining multiple rankings into a single aggregate ranking. However, algorithms for both these problems might be biased against some individuals or groups due to implicit prejudice or marginalization in the historical data. We study ranking and rank aggregation problems from a fairness or diversity perspective, where the candid…
Organizer
NeurIPS 2022
Account · 952 followers
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Why GANs are overkill for NLP
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Causal Discovery in Heterogeneous Environments Under the Sparse Mechanism Shift Hypothesis
Watch later
Ronan Perry, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Closing remarks
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Toward Equation of Motion for Deep Neural Networks: Continuous-time Gradient Descent and Discretization Error Analysis
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
VectorAdam for Rotation Equivariant Geometry Optimization
Watch later
Selena Ling, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
3DILG: Irregular Latent Grids for 3D Generative Modeling
Watch later
Biao Zhang, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%