Rank Aggregation with Proportionate Fairness

Dong Wei, Md Mouinul Islam, Baruch Schieber, Senjuti Basu Roy

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Given multiple individual rank orders over a set of candidates or items, where the candidates belong to multiple (non-binary) protected groups, we study the classical rank aggregation problem subject to proportionate fairness or p-fairness (RAPF in short), considering Kemeny distance. We first study the problem of producing the closest p-fair ranking to an individual ranked order IPF in short) considering Kendall-Tau distance, and present multiple solutions for IPF. We then present two computational frameworks(a randomized randpickperm and a deterministic algpickperm) to solve RAPF that leverages the solutions of IPF as a subroutine. We make several non-trivial algorithmic contributions: (i) we prove that when the group protected attribute is binary, IPF can be solved exactly using a greedy technique; (ii) we present two different solutions for IPF when the group protected attribute is multi-valued, algexact is optimal and algapprox admits a 2 approximation factor; (iii) we design a framework for RAPF solution with an approximation factor that is 2+ the approximation factor of the IPF solution. The resulting randpickperm and algpickperm solutions exhibit 3 and 4 approximation factors when designed using algexact and algapprox, respectively. We run extensive experiments using multiple real world and large scale synthetic datasets and compare our proposed solutions against multiple state-of-the-art related works to demonstrate the effectiveness and efficiency of our studied problem and proposed solution.

Original languageEnglish (US)
Title of host publicationSIGMOD 2022 - Proceedings of the 2022 International Conference on Management of Data
PublisherAssociation for Computing Machinery
Pages262-275
Number of pages14
ISBN (Electronic)9781450392495
DOIs
StatePublished - Jun 10 2022
Event2022 ACM SIGMOD International Conference on the Management of Data, SIGMOD 2022 - Virtual, Online, United States
Duration: Jun 12 2022Jun 17 2022

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078

Conference

Conference2022 ACM SIGMOD International Conference on the Management of Data, SIGMOD 2022
Country/TerritoryUnited States
CityVirtual, Online
Period6/12/226/17/22

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems

Keywords

  • algorithms
  • p-fairness
  • rank aggregation

Fingerprint

Dive into the research topics of 'Rank Aggregation with Proportionate Fairness'. Together they form a unique fingerprint.

Cite this