Source-linked AI summary
Fairness Through Awareness
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, Rich Zemel
TL;DR
Classification systems must balance utility with preventing discrimination against protected groups. The paper defines fairness through task-specific similarity, formulates utility optimization under individual-fairness constraints, and extends the framework to statistical parity; it concludes that these goals can be analyzed and balanced systematically.
Problem
Classification requires maintaining utility while preventing discrimination against protected population subgroups.
Method
The framework uses a task-specific distance metric and a linear program to optimize vendor utility while treating similar individuals similarly.
Results
The paper develops a framework that balances similarity constraints with a vendor’s loss function and provides an alternative formulation enforcing statistical parity.
Takeaways & Limitations
Individual-based fairness can imply statistical parity in some settings, while a separate formulation supports preferential treatment when parity is required.
Takeaways & Limitations
When protected groups are far apart under the metric, satisfying the Lipschitz condition may fail to prevent some unfair practices.
Abstract
from arXiv · showhide
We study fairness in classification, where individuals are classified, e.g., admitted to a university, and the goal is to prevent discrimination against individuals based on their membership in some group, while maintaining utility for the classifier (the university). The main conceptual contribution of this paper is a framework for fair classification comprising (1) a (hypothetical) task-specific metric for determining the degree to which individuals are similar with respect to the classification task at hand; (2) an algorithm for maximizing utility subject to the fairness constraint, that similar individuals are treated similarly. We also present an adaptation of our approach to achieve the complementary goal of "fair affirmative action," which guarantees statistical parity (i.e., the demographics of the set of individuals receiving any classification are the same as the demographics of the underlying population), while treating similar individuals as similarly as possible. Finally, we discuss the relationship of fairness to privacy: when fairness implies privacy, and how tools developed in the context of differential privacy may be applied to fairness.
1 Introduction
The paper proposes fairness through awareness: classify similar individuals similarly according to a public, task-specific similarity metric. It formulates utility-preserving fair classification as an efficiently solvable linear program and extends the framework to group parity, privacy, and discriminatory-practice prevention.
- Task-specific similarity metric: The task-specific metric is intended to capture ground truth, remain public and contestable, and may be imposed or proposed externally.When ground truth is unavailable, it can represent society’s best available approximation and be continually refined.
- Treating similar individuals similarly: Fairness requires that individuals similar for a task receive similar classifications, formalized through a distance metric and a Lipschitz condition.The metric defines how similar individuals are, and their outcome distributions must be indistinguishable up to that distance.
- Formulation as an optimization problem: The framework optimizes vendor utility subject to fairness constraints, expressing the problem as a linear program that can be solved efficiently.The linear program and its dual interpretation support the paper’s subsequent analysis.
- Fair affirmative action: The framework distinguishes individual fairness from statistical parity and provides techniques for achieving parity while preserving as much individual fairness as possible.These techniques are presented as a form of fair affirmative action when parity is not implied by the Lipschitz condition.
- A close relationship to privacy: The paper connects fairness to differential privacy and uses privacy techniques to develop a more efficient fairness mechanism with small error in suitable metric spaces.The analogy treats individuals in fairness as analogous to databases in differential privacy.
- Prevention of certain evils: The fairness notion prohibits discriminatory practices including redlining, reverse redlining, redundant protected-group encodings, and selectively abandoning or targeting population segments.The paper catalogs these practices in Appendix A.
2 Formulation of the Problem
The paper formulates fair classification as randomized mappings from individuals to outcome distributions that minimize expected loss subject to a Lipschitz fairness constraint. It instantiates this framework with distribution metrics, an advertising-network example, and a connection to differential privacy.
- 2 Formulation of the Problem: Classifiers are randomized mappings from individuals V to distributions over outcomes A, with the basic nontrivial case A = {0, 1}.Randomization is used to enforce fairness at the level of outcome distributions.
- 2 Formulation of the Problem: The central optimization minimizes expected loss under the requirement that the mapping from individuals to outcome distributions satisfies the (D, d)-Lipschitz property.Utility is represented by an arbitrary loss function L: V × A →, while d measures similarity between individuals and D compares outcome distributions.
- 2.1 Achieving Fairness: Statistical distance Dtv yields an efficiently solvable formulation: opt(I) can be computed by a linear program of size poly(|V|, |A|).The instance I consists of an individual metric d and loss function L.
- 2.1 Achieving Fairness: Relative ℓ∞ distance constrains similar individuals to have similar outcome distributions while imposing only a weak constraint on very dissimilar individuals, and D∞ also permits computing opt(I) with a linear program of size poly(|V|, |A|).For similar individuals d(x, y) ≪1; for very dissimilar individuals d(x, y) ≫1.
- 2.1 Achieving Fairness: The Lipschitz fairness definition is preserved under any possibly randomized post-processing of outcomes, so composing M with f remains (D, d)-Lipschitz for D ∈{Dtv, D∞}.This property supports downstream transformations such as those considered in the advertising-network example.
- 2.2 Example: Ad network: In the advertising-network example, randomized category assignments must satisfy the Lipschitz property, while the vendor can still express its beliefs through the loss function subject to that constraint.The categories determine which advertisements are shown to individuals.
- 2.3 Connection to Differential Privacy: Fairness generalizes differential privacy: in the database setting, ε-differential privacy is equivalent to the (D∞, d)-Lipschitz property with d(x, y) = ε|x△y|.The same loss-minimization framework defines the optimal differentially private mechanism, and techniques from differential privacy later carry over to fairness.
3 Relationship between Lipschitz property and statistical parity
The section explains that statistical parity has useful distributional guarantees but is insufficient as a general fairness notion. It then characterizes when Lipschitz mappings imply parity through the bias between distributions and its relationship to Earthmover distance.
- Lipschitz property and statistical parity: The Lipschitz condition naturally implies statistical parity between certain population subsets.The section frames the relationship between the paper’s Lipschitz fairness condition and statistical parity.
- Statistical parity: Statistical parity makes members of two sets equally likely to observe any outcome set and prevents the observed outcome from revealing set membership.The comparison can take one set to be the complement of the other, thereby comparing a protected group with the general population.
- Limits of statistical parity: Statistical parity alone can remain unfair because it permits reduced utility, self-fulfilling discrimination, and targeting disparities within protected subsets.These examples show that parity may neutralize redundant encodings while still producing outcomes that are blatantly unfair from an individual’s perspective.
- Bias: The section defines bias as the maximum statistical-parity violation over Lipschitz mappings and notes that binary outcomes suffice without loss of generality.For any (D, d)-Lipschitz mapping into an arbitrary outcome space, Lemma 3.1 guarantees statistical parity up to bias_D,d(S, T).
4 Fair Affirmative Action
The section develops fair affirmative action for cases where statistical parity conflicts with treating similar individuals similarly. Its alternative approach enforces parity while relaxing cross-group Lipschitz constraints through an Earthmover-based mapping that preserves within-group fairness and limits average cross-group violations.
- Motivation: When protected groups differ substantially in the task-specific metric, the Lipschitz condition alone does not guarantee statistical parity.Groups can be over- or under-represented in metric-defined clusters, allowing their average treatment to differ despite similar treatment within each cluster.
- Imposing Statistical Parity: Imposing statistical parity in the example can collapse the metric space into trivial solutions by forcing groups in distinct clusters to receive comparable treatment.Treating protected members like the higher-benefit group also forces the other members of their cluster to receive that treatment under the Lipschitz condition.
- Failing to Impose Statistical Parity: Failing to impose statistical parity can enable discriminatory outcomes because group demographics differ across metric-defined clusters.An adversarial vendor could replace a reasonable offer with a hostile message that effectively eliminates most protected-group members.
- Alternative Approach: The proposed alternative insists on statistical parity while relaxing Lipschitz constraints between protected and unprotected groups, consistent with preferential treatment.It is inspired by Earthmover relaxations and retains Lipschitz requirements within each group.
- Alternative Approach: The method maps protected individuals to distributions over the other group at minimum total distance, reweights losses, and then runs the Fairness LP on the other group.The mapping transports the uniform distribution over one group to the uniform distribution over the other while preserving within-protected-group Lipschitz constraints.
- Properties and Tradeoffs: The resulting optimization balances loss against disruption of cross-group Lipschitz requirements, while the expected cross-group violation is controlled by dEM+L(S, T).The mapping satisfies Lipschitz constraints within S and within T; cross-group distances remain influential through the objective.
5 Small loss in bounded doubling dimension
The section presents an efficient exponential-mechanism fairness mapping with bounded loss in well-separated metric spaces of bounded doubling dimension. Its error depends exponentially on the doubling dimension, while a matching lower-bound direction shows every Lipschitz mapping can require loss scaling linearly with that dimension.
- Upper bound: The exponential mechanism is significantly more efficient than the general linear program and is proved to achieve bounded loss in well-separated spaces of bounded doubling dimension.The general linear program finds an optimally fair mapping in polynomial time but provides no concrete loss bound; the new mechanism addresses both limitations.
- Upper bound: The exponential mechanism is (D∞, d)-Lipschitz, providing the fairness guarantee used by the bounded-loss analysis.The mechanism maps elements of V to distributions over V, with the metric d serving as the loss function.
- Extension beyond separation: If the metric space is not well-separated, restricting to a well-separated subset and extending the mapping worsens expected loss by at most an additive ϵ and the Lipschitz condition by additive 2ϵ.The extension uses each point’s nearest neighbor in the well-separated subset.
- Upper bound: The upper-bound proof has exponential dependence on the doubling dimension k, motivating the open question of whether that dependence can be improved.The section explicitly identifies improving the exponential dependence on k as an open question.
- Lower bound: For every k ≥2 and sufficiently large n ≥n0(k), there is an n-point metric space of doubling dimension O(k) where every (D∞, d)-Lipschitz mapping has large average error.The construction uses random points on a sphere in dimension r = O(k), and the lower bound also applies, up to a small additive loss, to mappings on well-separated subsets.
6 Discussion and Future Directions
The paper’s framework enforces fairness by treating similar people similarly while optimizing utility, and it analyzes when this implies statistical parity. Future directions focus on constructing suitable metrics, applying them in domains such as health care, and strengthening privacy against redundant encodings in targeted advertising.
- Framework: The framework balances treating similar people similarly with a vendor’s loss function and analyzes when this local fairness condition implies statistical parity.It also presents an alternative formulation that directly enforces statistical parity.
- Metric construction: A central open challenge is justifying and constructing the task-specific distance metric, using existing classification metrics, machine learning, and human domain expertise.Machine learning can help construct distances within protected groups or the general population, while cross-group comparisons may require human insight.
- Metric construction: Future work asks how many costly expert queries are needed to approximate an unknown right metric within bounded distortion.This question is related to metric labeling and spanner constructions.
- Applications: Similarity information from health-care projects such as AALIM could support metrics that ensure patients with similar medical conditions receive similar health-care policies.AALIM’s similarity information was restricted to cardiology, with possible future extension to other medical domains.
- Privacy: Statistical parity can eliminate redundant encodings of protected-group membership after classification, but it is not hereditary and may fail to hide sensitive information in targeted advertising.The paper suggests investigating whether a Lipschitz property with a suitable metric could provide better protection.
A Catalog of Evils
The section catalogs discrimination tactics that exploit protected-group membership directly or through correlated information and institutional practices. It includes explicit discrimination, redundant encoding, redlining and its generalizations, self-fulfilling prophecies, and reverse tokenism.
- Direct discrimination: Blatant explicit discrimination tests membership in a protected set S and gives members of S a “worse” outcome than members of S c.This is the direct form of discrimination described in the catalog.
- Indirect discrimination: Discrimination based on redundant encoding replaces an explicit test for S with an essentially equivalent test using correlated information.Online activity histories may encode demographic or sexual orientation information even after explicit attributes are deleted.
- Institutional exclusion: Redlining and related cutoffs deny or limit services to neighborhoods or population segments associated disproportionately with S.The broader pattern need not target a majority of S; it can target groups whose share of the affected population exceeds S’s population share.
- Feedback effects: A self-fulfilling prophecy deliberately or inadvertently selects unqualified or random members of S, creating a bad track record for S.The catalog describes this as a vendor or advertiser cutting off qualified members and thereby reinforcing negative evidence about the protected set.
- Evidentiary tactics: Reverse tokenism uses the rejection of one obviously more qualified member of S c to refute broader discrimination claims against S.The rejected candidate functions as a “token rejectee,” allowing the bank to sacrifice one strong candidate while denying discrimination.