What’s Individual About Individual Fairness?

Shai Ben-David, Pascale Gourdeau, Tosca Lechner, Ruth UrnerAAAI 2025 · DOI

Abstract

Individual and group fairness notions abound in the machine learning literature. Each attempts to formalize harm against individuals or groups of people. In this work, we take a step back and aim to characterize, from a learning theory perspective, what is at the heart of individual fairness (IF) notions. We argue that fairness notions should be comparison-based and, in the case of IF notions, that any failure to be fair should give rise to finite evidence of unfairness. We also posit that IF notions should have an unfairness "direction", for example via an order on the set of potential decisions. Equipped with this framework, we present various ways unfair classifiers can be compared to each other. Comparing classifiers is essential in any situation where there is a need to choose between not-perfectly-fair classifiers, e.g., in cases where there exist unavoidable trade-offs between learning objectives. We then adapt score-based measures of individual unfairness to allow us to measure how harm is distributed between population subgroups, which is more in line with group fairness. Crucially, our set-up retains evidence of harm at the individual level, allowing for algorithmic recourse, or potential integrations within legal frameworks.

Introduction

The machine learning community has developed a vast "zoo" of fairness definitions, typically categorized into Individual Fairness (IF) and Group Fairness (GF). While these definitions aim to mitigate harm, the formal distinction between them—and between fairness and general predictive accuracy—often remains ambiguous. Furthermore, most research focuses on achieving "perfect" fairness, an ideal that is frequently unattainable due to inherent trade-offs between accuracy, privacy, and competing fairness constraints.

This work provides a theoretical foundation for the "essence" of Individual Fairness. We argue that the defining characteristic of IF is its grounding in finite evidence. Unlike Group Fairness, which relies on aggregate statistics across large populations, an IF violation should be provable by pointing to a small, specific set of individuals and their outcomes.

Postulates for Individual Fairness

We propose three core requirements that any meaningful Individual Fairness notion must satisfy:

  1. Comparison-based Evaluation: Fairness is inherently comparative. A decision for a single individual cannot be judged as fair or unfair in isolation; it only becomes a matter of fairness when compared to the treatment of others (comparative justice).
  2. Bounded Evidence (The $k$-finite Property): This is the central contribution of this work. If a classifier is individually unfair, there must exist a small, finite set of individuals (an "evidence set") of size $k$ that demonstrates this violation. For instance, in similarity-based fairness, the evidence set size is $k=2$ (the individual treated unfairly and a similar peer who received a better outcome).
  3. Preferential Treatment: A fairness notion must have a "direction." It should explicitly designate who is being harmed by defining an order of preference over possible decisions (e.g., receiving a loan is preferred over being rejected).

A Taxonomy of Fairness Notions

By applying these postulates, we can categorize existing fairness definitions within a unified framework. This taxonomy clarifies why certain notions are truly "individual" while others are "group-based."

Table 1: Comparison of various fairness notions based on the proposed postulates.

As shown in Table 1, notions like Similarity-based and Meritocratic fairness satisfy the finite evidence requirement. In contrast, Statistical Parity and Equalized Odds fail this test because they rely on distributional properties that cannot be proven with a small, finite set of examples. We also introduce a new IF notion based on a convexity requirement: the set of individuals receiving a preferred label should be "convex" in the feature space. Using Carathéodory’s theorem, we prove this satisfies the IF requirement with an evidence set size of $k = d+2$, where $d$ is the number of features.

Comparing Imperfect Classifiers

In practice, engineers often must choose between multiple "not-perfectly-fair" (NPF) classifiers. Our framework allows for the comparison of such models using scoring measures and partial orders. We can mathematically state that "Classifier A is less unfair than Classifier B" if the set of individuals mistreated by A is a subset of those mistreated by B (Evidence Set Inclusion). This provides a principled way to navigate trade-offs in model selection.

Bridging Individual and Group Harm

While IF focuses on individuals, our framework can be extended to detect systemic bias. By aggregating individual evidence sets across subgroups, we can measure how harm is distributed across the population. This approach identifies "structural injustice" while maintaining the ability to point to specific individuals who were harmed. This bridge is crucial for legal frameworks and algorithmic recourse, as it provides a rejected applicant with the specific evidence needed to demonstrate unfair treatment.

Conclusion and Future Work

This theoretical framework clarifies the boundaries of Individual Fairness and provides tools for comparing imperfect models. While it establishes if a notion is "Individual," future work is needed to determine which IF notion is most appropriate for specific real-world contexts. Additionally, defining the necessary similarity metrics or "ground truth" orders remains a practical challenge. Nevertheless, by grounding fairness in finite evidence, we move closer to models that are not only statistically fair but also individually accountable.

Summary updated

Abstract

Individual and group fairness notions abound in the machine learning literature. Each attempts to formalize harm against individuals or groups of people. In this work, we take a step back and aim to characterize, from a learning theory perspective, what is at the heart of individual fairness (IF) notions. We argue that fairness notions should be comparison-based and, in the case of IF notions, that any failure to be fair should give rise to finite evidence of unfairness. We also posit that IF notions should have an unfairness ``direction'', for example via an order on the set of potential decisions. Equipped with this framework, we present various ways unfair classifiers can be compared to each other. Comparing classifiers is essential in any situation where there is a need to choose between not-perfectly-fair classifiers, e.g., in cases where there exist unavoidable trade-offs between learning objectives. We then adapt score-based measures of individual unfairness to allow us to measure how harm is distributed between population subgroups, which is more in line with group fairness. Crucially, our set-up retains evidence of harm at the individual level, allowing for algorithmic recourse, or potential integrations within legal frameworks.
BibTeX
@inproceedings{bendavid2025whats,
  author = {Shai Ben-David and Pascale Gourdeau and Tosca Lechner and Ruth Urner},
  title = {{What’s Individual About Individual Fairness?}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aies.v8i1.36556},
}
Figure