CoChat
Sign Up
Cited by 496Game Theory and Voting SystemsEthics and Social Impacts of AIRecommender Systems and Techniques

FA*IR: A Fair Top-k Ranking Algorithm

Open access
Zehlike, Meike, Bonchi, Francesco, Castillo, Carlos, Hajian, Sara, Megahed, Mohamed, Baeza-Yates, Ricardo·2017·Proceedings of the 2017 ACM on Conference on Information and Knowledge Management
DOI 10.1145/3132847.3132938
Open this paper in CoChat — free accountOpen PDF

Abstract

In this work, we define and solve the Fair Top-k Ranking problem, in which we want to determine a subset of k candidates from a large pool of n » k candidates, maximizing utility (i.e., select the "best" candidates) subject to group fairness criteria.

AI snapshot

Written from the paper’s full text.

TL;DR

The paper defines the Fair Top-k Ranking problem and proposes FA*IR, a post-processing algorithm that enforces ranked group fairness—protected-group proportion in every prefix statistically above or indistinguishable from a minimum \(p\)—while maximizing selection and ordering utility. Experiments on COMPAS, German Credit, SAT, and XING show FA*IR generally yields small NDCG/utility distortions versus color-blind ranking and equal or lower ordering utility loss than the Feldman et al. baseline.

Key findings

  • FA*IR satisfies ranked group fairness with parameters \(p\) and \(\alpha\) using an adjusted significance \(\alpha_c\); for \(\alpha=0.1\), Table 4 reports \(\alpha_c=0.0096\) for \(k=1{,}000, p=0.5\) and \(\alpha_c=0.0084\) for \(k=1{,}500, p=0.5\).
  • Across experiments, FA*IR achieves higher or equal selection utility than Feldman et al. in all but one condition (D7), and higher or equal ordering utility in all conditions.
  • Example: D4 German Credit, protected=female, FA*IR \(p=0.7\) gives 74% protected output, NDCG 1.0000, ordering utility loss 0.0000, rank drop 0, selection utility loss 0.0000; Feldman et al. gives 69%, NDCG 0.9988, ordering loss 0.1197, rank drop 8, selection loss 0.0224.
  • XING example: with \(\alpha=0.1\) and \(p=0.4\), copywriter and economist rankings are rejected as unfair, market research analyst is fair; with \(p=0.5\), market research analyst is also unfair.

Methods

  • Formal model: ranked group fairness via binomial CDF on every prefix, corrected significance for multiple tests; utility as selection utility and ordering utility with in-group monotonicity; FA*IR greedy algorithm using two priority queues, \(O(n + k \log k)\), and AdjustSignificance \(O(k^2)\) run once.
  • Data: synthetic rankings generated by Yang and Stoyanovich’s procedure to verify multiple-test adjustment; real datasets COMPAS (\(n=18\)K, \(k=1\)K), German Credit (\(n=1\)K, \(k=100\)), SAT (\(n=1.6\)M, \(k=1.5\)K), and new XING (\(n=40, k=40\)), with protected groups and quality criteria as in Table 5.
  • Analysis: compare FA*IR against color-blind ranking and Feldman et al. baseline using NDCG, ordering utility loss, maximum rank drop, and selection utility loss, varying target proportion \(p\).

Limitations

  • Paper states: assumes one dominant legally-protected attribute; multiple protected groups/attributes left for future work. Also algorithm guaranteed only if there are at least \(k\) candidates from each group; otherwise the head satisfies fairness but the tail may not. Post-processing, not in-processing; future work.
  • Paper states: experiments use real datasets with some group differences; synthetic datasets with more extreme differences, robustness to noise in qualifications, and real-application impact are left for future work.
  • Evident from text: utility/rank-drop losses can be large in some conditions (e.g., D1 COMPAS race=Afr.-Am., FA*IR \(p=0.5\) has rank drop 319 and ordering utility loss 0.2026), so the “small distortions” claim is not uniform across datasets.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1145/3132847.3132938

Cites

51 of 51 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Claims the paper makes

0 of 21 cited sources checked · 0 supported · 0 flagged

  • Findingreasoning
    § 1 INTRODUCTION · p. 2

    For the XING example with k=10, p=0.4, and α=0.1, the ranking for 'economist' is rejected as unfair.

    “therefore also the ranking for 'economist' is rejected as unfair”
    Quote in the paperNot a substantial claim
  • Findingreasoning
    § 1 INTRODUCTION · p. 2

    For the XING example with k=10, p=0.4, and α=0.1, the ranking for 'copywriter' would be rejected as unfair.

    “therefore the ranking for 'copywriter' would be rejected as unfair.”
    Quote in the paperNot a substantial claim
  • Findingown data
    § 1 INTRODUCTION · p. 2

    In the XING rankings, the proportion of male and female candidates changes and is not uniform as one goes down the lists (e.g., top-10 vs. top-40).

    “While analyzing the extent to which candidates of both genders are represented as we go down these lists, we can observe that such proportion keep changing and is not uniform (see, for instance, the top-10 vs. the top-40).”
    Quote in the paperSubstantial claim
  • Findingown data
    § 3.3 Model Adjustment · p. 5

    The probability that a fair ranking generated with p=0.5 is rejected by the ranked group fairness test with p=0.5 and αc=0.1 is in general larger than α=0.1.

    “We can see that the probability of a Type-I error (declaring this fair ranking as unfair) is in general higher than α = 0 : 1.”
    Quote in the paperSubstantial claim
  • Findingown data
    § ABSTRACT · p. 1

    The paper's approach yields small distortions with respect to rankings that maximize utility without considering fairness criteria.

    “showing that our approach yields small distortions with respect to rankings that maximize utility without considering fairness criteria.”
    Quote in the paperSubstantial claim
  • Classified as probably not a substantial claim. 18
  • May combine two claims. 15

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Findingreasoning
    § 1 INTRODUCTION · p. 2

    For the XING example with k=10, p=0.5, and α=0.1, even the ranking for 'market research analyst' would be considered unfair.

    “and thus even the ranking for 'market research analyst' would be considered unfair.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Findingown data
    § 3.3 Model Adjustment · p. 5

    The values of αc obtained using this procedure for selected k, p, and α=0.1 appear on Table 4.

    “The values of α c obtained using this procedure for selected k ; p and α = 0 : 1 appear on Table 4.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data
    § 5.2 Datasets · p. 8

    In COMPAS, African Americans as well as males are given a larger recidivism score than other groups.

    “We observe that African Americans as well as males are given a larger recidivism score than other groups; for the purposes of this experiment we select these two categories as the protected groups.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Findingown data
    § 3.2 Group Fairness for Rankings · p. 4

    For p=0.5, at least 1 candidate from the protected group is needed in the top 4 positions, and 2 protected candidates in the top 7 positions.

    “For instance, for p = 0 : 5 we see that at least 1 candidate from the protected group is needed in the top 4 positions, and 2 protected candidates in the top 7 positions.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data
    § 5.2 Datasets · p. 8

    The XING ad-hoc score tends to be somewhat higher for profiles in the first positions of the search results, but in general does not approximate the proprietary ordering in which profiles are shown.

    “This score tends to be somewhat higher for profiles in the first positions of the search results, but in general does not approximate the proprietary ordering in which profiles are shown.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data
    § 5.4 Results · p. 9

    In dataset D4 (German credit, protected group age < 25), FA*IR can double the proportion of young people in the top-k ranking (from 15% to 30%) without introducing a large ordering utility loss and maintaining NDCG almost unchanged.

    “In this case, the figure shows that we can double the proportion of young people in the topk ranking (from the original 15% up to 30%) without introducing a large ordering utility loss and maintaining NDCG almost unchanged.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Interpretationreasoning
    § 3.3 Model Adjustment · p. 5

    The algorithm can be used to determine the value of αc at which the acceptance probability becomes 1-α, for instance, by performing binary search.

    “This algorithm can be used to determine the value of α c at which the acceptance probability becomes 1 α , for instance, by performing binary search.”
    Quote in the paperNot a substantial claim

  • Classified as probably not a substantial claim.

    Interpretationcitation
    § 3.4 Utility · p. 5

    In contrast with previous works, the paper does not assume knowledge of the contribution of having a given candidate at a particular position, but instead bases utility calculation on losses due to nonmonotonicity.

    “In contrast with previous works [7, 36], we do not assume we know the contribution of having a given candidate at a particular position, but instead base our utility calculation on losses due to nonmonotonicity.”
    Quote in the paperSubstantial claim0 of 2 sources checked
    • cites [7] [7] L Elisa Celis, Damian Straszak, and Nisheeth K Vishnoi. 2017. Ranking with Fairness Constraints. arXiv:1704.06840 (2017). -

      Not checked in the free run.

    • cites [36] [36] Ke Yang and Julia Stoyanovich. 2016. Measuring Fairness in Ranked Outputs. In Proc. of FATML . -

      Not checked in the free run.

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Interpretationown data
    § 3.3 Model Adjustment · p. 5

    Algorithm AdjustSignificance has running time O(k^2).

    “This has running time O ' k 2 ' , but we note it has to be executed only once, as it does not depend on the dataset, only on k .”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Interpretationreasoning
    § 3.3 Model Adjustment · p. 5

    Algorithm AdjustSignificance has to be executed only once, as it does not depend on the dataset, only on k.

    “This has running time O ' k 2 ' , but we note it has to be executed only once, as it does not depend on the dataset, only on k .”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S4 (based).

    Interpretationnone given
    § ABSTRACT · p. 1

    To the best of the authors' knowledge, this is the first algorithm grounded in statistical tests that can mitigate biases in the representation of an under-represented group along a ranked list.

    “To the best of our knowledge, this is the first algorithm grounded in statistical tests that can mitigate biases in the representation of an under-represented group along a ranked list.”
    Quote in the paperNot a substantial claim

  • Classified as probably not a substantial claim.

    Study design and conductown data
    § 1 INTRODUCTION · p. 2

    The paper presents extensive experiments using both existing and new datasets to evaluate the performance of the approach compared to color-blind ranking with respect to both utility and fairness.

    “We also present extensive experiments using both existing and new datasets to evaluate the performance of our approach compared to the so-called 'color-blind' ranking with respect to both the utility of ranking and the fairness degree.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Premisecitation
    § 1 INTRODUCTION · p. 2

    The measurement of candidate qualification will embody preexisting bias as well as technical bias, as learning algorithms are known to be susceptible to direct and indirect discrimination.

    “We note that this measurement will embody preexisting bias (e.g. if black pilots are given less opportunities to flight they accumulate less flight hours), as well as technical bias , as learning algorithms are known to be susceptible to direct and indirect discrimination [15, 16].”
    Quote in the paperSubstantial claim0 of 2 sources checked
    • cites [15] [15] Sara Hajian, Francesco Bonchi, and Carlos Castillo. 2016. Algorithmic Bias: From Discrimination Discovery to Fairness-aware Data Mining. In KDD Tutorials . -

      Not checked in the free run.

    • cites [16] [16] Sara Hajian and Josep Domingo-Ferrer. 2013. A methodology for direct and indirect discrimination prevention in data mining. IEEE TKDE 25, 7 (2013). - source

      Not checked in the free run.

  • Classified as probably not a substantial claim.

    Premisecitation
    § 1 INTRODUCTION · p. 2

    The paper's definition of ranked group fairness reflects the legal principle of group under-representation in obtaining a benefit.

    “Our definition of ranked group fairness reflects the legal principle of group under-representation in obtaining a benefit [11, 26].”
    Quote in the paperSubstantial claim0 of 2 sources checked
    • cites [11] [11] Evelyn Ellis and Philippa Watson. 2012. EU anti-discrimination law . Oxford University Press. -

      Not checked in the free run.

    • cites [26] [26] N¯ at¯ an Lerner. 2003. Group rights and discrimination in international law . Vol. 77. Martinus Nijhoff Publishers. -

      Not checked in the free run.

  • May combine two claims.

    Premisecitation
    § 1 INTRODUCTION · p. 1

    A machine learning model trained on datasets incorporating preexisting bias will embody this bias and therefore produce biased results, potentially increasing any disadvantage further, reinforcing existing bias.

    “As shown in earlier research, a machine learning model trained on datasets incorporating preexisting bias will embody this bias and therefore produce biased results, potentially increasing any disadvantage further, reinforcing existing bias [28].”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [28] [28] Cathy O'Neil. 2016. Weapons of math destruction: How big data increases inequality and threatens democracy . Crown Publishing Group. -

      Not checked in the free run.

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation
    § 5.2 Datasets · p. 8

    COMPAS has been accused of racial discrimination by producing a higher likelihood to recidivate for African Americans.

    “It is used in several jurisdictions in the US, and has been accused of racial discrimination by producing a higher likelihood to recidivate for African Americans [1].”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [1] [1] Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. 2016. Machine Bias. ProPublica (May 2016). -

      Not checked in the free run.

  • Classified as probably not a substantial claim. May combine two claims.

    Interpretationreasoning
    § 3.4 Utility · p. 6

    The paper's utility notion is centered on individuals by taking minima instead of averaging, which allows loss of utility to be traced to specific individuals.

    “Our notion of utility is centered on individuals, for instance by taking the minima instead of averaging. While other choices are possible, this has the advantage that we can trace loss of utility to specific individuals.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationnone given
    § 4.1 Algorithm Description · p. 7

    FA*IR is applicable as long as there is a protected group and there are enough candidates from that group.

    “Our method is applicable as long as there is a protected group and there are enough candidates from that group; if there are k from each group, the algorithm is guaranteed to succeed, otherwise the 'head' of the ranking will satisfy the ranked group fairness constraint, but the 'tail' of the ranking may not.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim.

    Interpretationnone given
    § 6 CONCLUSIONS · p. 9

    The method does not assume that the distributions of qualifications in the protected and non-protected groups have a similar shape.

    “We also do not assume that the distributions of qualifications in the protected and non-protected groups have a similar shape.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Interpretationnone given
    § 3.2 Group Fairness for Rankings · p. 4

    A larger α means a larger probability of declaring a fair ranking as unfair.

    “Weremark that a larger α means a larger probability of declaring a fair ranking as unfair.”
    Quote in the paperNot a substantial claim

  • Classified as probably not a substantial claim. May combine two claims.

    Interpretationnone given
    § 1 INTRODUCTION · p. 2

    The paper provides a principled definition of ranked group fairness and the associated Fair Top-k Ranking problem.

    “(1) the principled definition of ranked group fairness , and the associated Fair Topk Ranking problem;”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning
    § 4.2 Algorithm Correctness · p. 7

    Given two rankings satisfying in-group monotonicity, if they have the same number of protected elements, then both rankings contain the same k elements and have the same selection utility.

    “Lemma 4.3. Given two rankings ρ ; τ satisfying in-group monotonicity (i), if they have the same number of protected elements ρ p = τ p , then both rankings contain the same k elements (possibly in different order), and hence both rankings have the same selection utility.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationnone given
    § 3.4 Utility · p. 6

    A color-blind top-k ranking maximizes ordering utility, i.e., has ordering utility zero, and satisfies the in-group monotonicity constraint.

    “Again, the 'color-blind' top-k ranking c j k maximizes ordering utility, i.e., has ordering utility zero; it also satisfies the in-group monotonicity constraint.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Interpretationnone given
    § 3.4 Utility · p. 6

    A color-blind top-k ranking maximizes selection utility, i.e., has selection utility zero.

    “Naturally, a 'color-blind' top-k ranking c j k maximizes selection utility, i.e., has selection utility zero.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationown data
    § 6 CONCLUSIONS · p. 9

    The method can generate a ranking with guaranteed ranked group fairness and does not introduce a large utility loss.

    “The method we have presented can generate a ranking with a guaranteed ranked group fairness, and as we have observed, does not introduce a large utility loss.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim. May combine two claims.

    Interpretationreasoning
    § 3.4 Utility · p. 6

    Under the individual fairness interpretation, consistent treatment requires that two people with the same qualifications be treated equally, and any deviation from this is a utility loss in the framework.

    “Under this interpretation, a consistent treatment should require that two people with the same qualifications be treated equally, and any deviation from this is in our framework a utility loss.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim. May combine two claims.

    Interpretationnone given
    § ABSTRACT · p. 1

    The paper defines and solves the Fair Top-k Ranking problem.

    “In this work, we define and solve the Fair Topk Ranking problem”
    • Also stated in: § 1 INTRODUCTION · p. 2 · plain
      “In this paper, we define and analyze the Fair Topk Ranking problem”
    Quote in the paperSubstantial claim
27 of 27

  • The authors state this as an assumption.

    A ranking algorithm has given an undesirable outcome to a group of individuals, but the algorithm itself cannot determine if the grounds were appropriate or not.

    “We assume a ranking algorithm has given an undesirable outcome to a group of individuals, but the algorithm itself cannot determine if the grounds were appropriate or not.”

  • The authors state this as an assumption.

    The result is at least partly based on the protected attribute gender.

    “As we do not know the learning model behind the ranking, we assume that the result is at least partly based on the protected attribute gender .”

  • The authors state this as an assumption.

    The utility notion assumes we want to interview the most qualified candidates, and their qualification is equal to a relevance score calculated by a ranking algorithm.

    “Our notion of utility assumes that we want the interview the most qualified candidates, while their qualification is equal to a relevance score calculated by a ranking algorithm.”

  • The authors state this as an assumption.

    The relevance score is based on relevant metrics for evaluating candidates for a position.

    “This score is assumed to be based on relevant metrics for evaluating candidates for a position, which depending on the specific skills required for the job could be their grades (e.g., Grade Point Average), their results in a standardized knowledge/skills test specific for a job, their typing speed in words per minute for typists, or their number of hours of flight in the case of pilots.”

  • The authors state this as an assumption.

    There is a dominant legally-protected attribute of interest in each case.

    “We make the simplifying assumption that there is a dominant legally-protected attribute of interest in each case.”

  • The authors state this as an assumption.

    There are enough candidates of each kind, i.e., at least k protected and at least k non-protected candidates.

    “We will consider two kinds of candidates, protected and non-protected, and we will assume there are enough of them, i.e., at least k of each kind.”

  • The authors state this as an assumption.

    The user of the method knows that the outcome is based on unreasonable or inappropriate grounds and provides p as input.

    “Hence we expect the user of our method to know that the outcome is based on unreasonable or inappropriate grounds and provide p as input which can originate in a legal mandate or in voluntary commitments.”

  • The authors state this as an assumption.

    k is less than O(n log n).

    “where we assume k &lt; O ' n log n ' .”
8 of 8

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Considerations of fairness have been actively studied in the context of rankings and recommender systems.

    “Considerations of fairness have been actively studied in the context of rankings and recommender systems.”

    From Fairness in machine learning: A survey (2024) · cites this paper as [309]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

Each contradiction between two passages listed here was confirmed by an independent check.

  • Copywriter protected-group percentage differs between tables

    Minor

    Table 6 labels the copywriter dataset D8c as 29.7% protected, whereas Table 5 gives the third XING scenario as 27% protected.

  • Figure 3 discussion names D4 instead of D5

    Minor

    The discussion identifies D4 as the German Credit experiment protecting people under 25, but the Figure 3 caption identifies that experiment as D5.

2 of 2

Cites

Flagged first, then by citations

Research works printed but not linked: 1

  1. Julia Angwin , Jeff Larson , Surya Mattu , and Lauren Kirchner . 2016. Machine Bias. ProPublica (May . 2016 ). Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. 2016. Machine Bias. ProPublica (May. 2016).

Cited by

Sorted by citations

Related

Authors
Zehlike, M., Bonchi, F., Castillo, C., Hajian, S., Megahed, M., & Baeza-Yates, R.
Affiliations
  • Technische Universität Berlin (DE)
  • Institute for Scientific Interchange (IT)
  • Universitat Pompeu Fabra (ES)
  • NTENT, Barcelona, Spain
ORCID
Venue
Proceedings of the 2017 ACM on Conference on Information and Knowledge Management
Publisher
ACM
Published
2017-11-06
Pages
1569-1578
ISSN
2155-0751 (ISSN-L)
DOI
10.1145/3132847.3132938
OpenAlex
W2704480242
Cited by
496
References
51
Citations by year
2026: 34 · 2025: 49 · 2024: 81 · 2023: 71 · 2022: 64 · 2021: 82 · 2020: 56 · 2019: 45 · 2018: 12 · 2017: 1 · 2012: 1
FWCI
133.15
Type
conference paper
Language
en
Open access
Licence
www.acm.org/publications/policies/copyright_policy#Background (vor)
Locations
  • ACM International Conference on Information and Knowledge Management (CIKM) (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • Repositori digital de la UPF (Universitat Pompeu Fabra) (submittedVersion)
Funders
  • Eurecat
  • German Research Foundation
  • Catalonia Trade and Investment Agency
Topics
  • Social Sciences › Economics, Econometrics and Finance › Economics and Econometrics › Game Theory and Voting Systems
  • Social Sciences › Safety Research › Ethics and Social Impacts of AI
  • Physical Sciences › Computer Science › Information Systems › Recommender Systems and Techniques
Keywords
group fairness, utility maximization, candidate selection, fairness constraints, combinatorial optimization

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Claims read by deepseek-v4.1-flash under definition version 3 (extract-v3) on 2026-10-09.

Classified by jev-1.13-20260917 (gold-guideline-v0.2) on 2026-10-09.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review