2017:CIKM: FA*IR: A Fair Top-k Ranking Algorithm

[Hamedloghmani]

Title: FA*IR: A Fair Top-k Ranking Algorithm
Year: 2017
Venue: CIKM

Main Problem:
Formal problem of Fair top-k ranking is formally defined as follows(notation is adapted from paper):
Given a set of candidates, we want to produce a ranking that satisfies following conditions:
(i) satisfies the in-group monotonicity constraint
The requirement of in-group monotonicity constraints applies to all individuals and mandates that both candidates who are protected and those who are not, should be arranged in descending order of qualifications(qualification is considered as each member's utility or score in this paper) separately.
(ii) satisfies ranked group fairness
It means every prefix of the ranking should satisfy group fairness condition which is presence of specific amount of protected groups in the ranking
(iii) achieves optimal selection utility subject to (i) and (ii)
It means we prefer rankings in which the more qualified candidates are included, and the less qualified ones are excluded.
(iv) maximizes ordering utility subject to (i), (ii), and (iii).
It means a ranking should be ordered by decreasing qualification.

To summarize, we need a ranking that 1) fairly represent protected group(we define the percentage), 2) contain most qualified members based the obtained score from a machine learning model or score function and 3) ranking should be ordered by decreasing qualification

Drawbacks of Related Work
This paper is one of the early attempts for algorithmic fair ranking. Hence, there were no rich body of baselines to compare. They mentioned a constraint based optimization fair ranking method [1]. The problem of the construction of the constraint matrix was left open in that work and it is addressed in this paper.

Proposed Method
Input:

• the expected size k of the ranking to be returned
• the qualifications (or scores, probabilities, etc.)
• protected attribute labels (popularity labels for example)
• minimum proportion of the protected group
• adjusted significance level

Output: a ranking of size k

First, the algorithm creates two priority queues, one for each protected group ( e.g. 1 for popular member 1 for nonpopular ones). Then based on the desired distribution, algorithm creates a table ( this table is stored for time efficiency). In this table it is mentioned that for each prefix of the ranking with size o < k, what is the minimum number of required members from the protected group. Then it greedily and iteratively constructs a ranking subject to candidate qualifications, and minimum protected members required. For each position in each iteration, if we need protected member, the one with best qualification is selected. Otherwise the best member from their union is selected. A sample of this table is as follows:

Results and Conclusion
Their approach has the ability to produce a ranking that ensures fairness among ranked groups, and their experiment indicates that it does not result in a significant loss of utility metrics( in their case NDCG). In comparison to the method proposed by Feldman et al., their approach typically results in the same or lower loss of utility. Also, they do not make the assumption that the qualification distributions in the protected and non-protected groups are identical in shape. Most importantly, they can regulate the trade-off between fairness and utility through a parameter, p (or known as p-value).

Limitations:

• They only had 2 other baselines in their comparison. First, color blind ranking which is ranking without fairness considerations just based on utility. Second, Feldman et al., which aligns the probability distribution of the protected candidates with the non-protected ones.
• Their method only supports one protected attribute with binary value. ( It is notable that the same authors addressed this issue in their future papers)

Datasets:

• COMPAS
• German Credit
• SAT Score Dataset 2014
• XING Dataset (proposed with this paper) : a career-oriented website like LinkedIn talent.

Codebase:
https://github.com/MilkaLichtblau/FA-IR_Ranking

References:
[1] L Elisa Celis, Damian Straszak, and Nisheeth K Vishnoi. 2017. Ranking with Fairness Constraints. arXiv:1704.06840 (2017).

[hosseinfani]

@Hamedloghmani
Very nice summary. My understanding is that they gradually pick the best candidate from protected group if it does not drop the utility (0) or drops it very tiny amount. The difference is that the work by #26 does not aware of this. Am I right?

[Hamedloghmani]

Thanks a lot for your kind feedback @hosseinfani
You're right. They claim that FA*IR finds a ranking that maximizes utility subject to in-group monotonicity and ranked group fairness constraints.
Also, they proved their runtime is O(n+k logk) which is efficient especially for our problem with large teams.
Finally, they published an extended version with support for multiple sensitive attributes in 2022 (Fair Top-k Ranking with multiple protected groups) which is next paper in my reading list

[hosseinfani]

2017 till 2022 in IP&M!

[Hamedloghmani]

And also more significant fairness authors contributed in the second one. I hope this is the one :)