PaperlayerView exact revision on arXiv

Source-linked AI summary

Fairness Under Composition

Cynthia Dwork, Christina Ilvento

arXiv:1806.06122v2cs.LGstat.ML

TL;DR

Most fairness research considers a single classifier in isolation, leaving open how systems composed of individually fair algorithms behave. This paper analyzes competitive, functional, and dependent composition and provides constructions for fair composition. It shows that fair components can combine into unfair systems, while some carefully designed compositions preserve fairness.

  • Problem

    Much prior work studies classifiers in isolation, leaving the fairness of systems composed from individually fair classifiers as an open question.

    Source: §1 · p. 1

  • Method

    The paper analyzes task-competitive, functional, and dependent composition and gives constructions including RandomizeThenClassify, PermuteThenClassify, and WeightedSampling.

    Source: §1 · pp. 2–3

  • Results

    Individually fair classifiers do not necessarily remain fair under competition or functional composition, while the paper provides constructions for fair task competition and offline cohort selection.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    Fairness evaluation should account for the composed system and the outcomes on which fairness is measured, since group-based requirements may give misleading signals under composition.

    Source: §1 · p. 3

    The extended abstract omits a full discussion of more complicated dependent-composition scenarios.

    Source: §5.2 · p. 9

Abstract

from arXiv · show

Algorithmic fairness, and in particular the fairness of scoring and classification algorithms, has become a topic of increasing social concern and has recently witnessed an explosion of research in theoretical computer science, machine learning, statistics, the social sciences, and law. Much of the literature considers the case of a single classifier (or scoring function) used once, in isolation. In this work, we initiate the study of the fairness properties of systems composed of algorithms that are fair in isolation; that is, we study fairness under composition. We identify pitfalls of naive composition and give general constructions for fair composition, demonstrating both that classifiers that are fair in isolation do not necessarily compose into fair systems and also that seemingly unfair components may be carefully combined to construct fair systems. We focus primarily on the individual fairness setting proposed in [Dwork, Hardt, Pitassi, Reingold, Zemel, 2011], but also extend our results to a large class of group fairness definitions popular in the recent literature, exhibiting several cases in which group fairness definitions give misleading signals under composition.

1 Introduction

The paper asks whether individually fair classifiers remain fair when composed, and develops constructions and analyses for competitive, functional, and dependent composition. It also shows that group-fairness definitions can give misleading signals under composition, motivating system-level auditing and careful choice of fairness measures.

1 Introduction

  • Individually fair classifiers can produce unfair outcomes when tasks compete, but RandomizeThenClassify combines fair classifiers without modifying or coordinating them.The mechanism samples a task from a fixed distribution and runs that task's classifier.Source: §1 · p. 2
  • Fair components do not generally guarantee fair functional compositions, though some OR compositions can satisfy fairness and system-level outcomes determine where fairness must be measured.The paper connects this analysis to balancing short- and long-term fairness and to feedback loops.Source: §1 · p. 2
  • Selecting a cohort can become unfair when classifications depend on one another, so the paper gives PermuteThenClassify and WeightedSampling for offline selection.These methods also apply online under adversarial ordering when the universe size is known; the paper states there is no solution when it is unknown.Source: §1 · pp. 2–3
  • Group-fairness definitions can miss unfair treatment of intersectional subgroups, and task-competitive composition can exacerbate the problem when relevant attributes are absent or unavailable.The paper gives parental status among race and gender combinations as an example.Source: §1 · p. 3
  • Testing components alone is insufficient to assess system fairness, and composition should inform the evaluation of fairness definitions and requirements.The paper cautions that group-based requirements can give meaningless signals or preserve poor subgroup outcomes, and notes that fair-composition mechanisms could be improved.Source: §1 · p. 3

1.1 Related Work

  • Earlier work considered individual fairness, group fairness, and feedback loops in single-task or one-shot settings; this paper studies fairness under composition.It also situates its examples alongside empirical studies of multi-task advertising effects.Source: §1.1 · pp. 3–4

2 Preliminary Definitions and Assumptions

The paper uses randomized classifiers and task-specific metrics to formalize individual fairness, and presents conditional parity as a framework for group fairness. Its notation describes probabilities of positive outcomes and distributions over classifier outputs.

2.1 General Terminology

  • A classifier may be randomized, and its positive-outcome probability is denoted p_w; a distribution over its outputs is written as a mapping from individuals to outcome distributions.The paper uses subscripts or primes to distinguish classifiers and tasks.Source: §2.1 · p. 4

2.2 Individual Fairness

  • Individual fairness requires that the distance between two individuals' outcome distributions be no greater than their task-specific metric distance.For binary outcomes, the distributional distance equals the absolute difference in positive-classification probabilities.Source: §2.2 · pp. 4–5

2.3 Group Fairness

  • Conditional parity requires an outcome distribution to be constant across protected attributes when conditioning on qualifications, either at a specified qualification value or across all values.The framework captures group-fairness definitions including Equal Odds, Equal Opportunity, and Counterfactual Fairness.Source: §2.3 · p. 5

3 Multiple-Task Composition

The paper studies systems that must preserve fairness across multiple tasks, including settings where only one task can receive a positive outcome. Task competition can violate fairness even when each classifier is fair alone, while RandomizeThenClassify offers a simple construction that preserves fairness across tasks.

3 Multiple-Task Composition

  • Multiple-task fairness requires each task's expected outcomes to satisfy its own metric constraint across every pair of individuals.The single-slot composition problem additionally requires at most one task to receive a positive classification.Source: §3 · p. 5, §3.1 · p. 5

3.1 Task-Competitive Composition

  • Task-competitive composition applies a tie-breaking function to classifiers' outputs, producing at most one selected task and potentially no selection.The paper notes that this model covers a single advertising slot, while its specification does not require a positive outcome.Source: §3.1 · pp. 5–6
  • For any two tasks with nontrivial metrics, individually fair classifiers can violate multiple-task fairness under task-competitive composition for every tie-breaking function.The paper explains that earlier tasks can impose their preferences on later tasks.Source: §3.1 · p. 6

3.2 Simple Fair Multiple-task Composition

  • RandomizeThenClassify samples a task from a fixed distribution and runs its individually fair classifier, requiring neither classifier-training coordination nor additional information.It preserves each classifier's ordering and relative distances, but reduces allocation for classifiers trained to run independently.Source: §3.2 · p. 7

4 Functional Composition

Functional composition combines classifier outputs through logical operations, so fairness depends on which overall outcome matters. Even same-task OR combinations of individually fair classifiers can fail OR fairness, although some conditions suffice for smaller compositions.

4 Functional Composition

  • Functional composition combines classifier outputs through logical operations, and fairness must be assessed at the system-level outcome that matters.Examples include whether a student is accepted to any college, or whether admission is paired with sufficient financial aid.Source: §4 · p. 7

4.1 Same-task Functional Composition

  • Fair classifiers for the same task can fail OR fairness even when every individual is classified by every classifier in the composition.This establishes that individual fairness alone does not guarantee fairness of the combined probability of at least one positive outcome.Source: §4.1 · p. 8
  • When the existing classifiers each accept every individual with probability at least one-half, adding another individually fair classifier with the same condition preserves OR fairness.This condition also supports reasoning about an OR of ORs.Source: §4.1 · p. 8
  • Different-task compositions such as admission AND financial aid can violate individual fairness when their distinct input metrics are combined without careful reasoning about the relevant output metric.The paper notes that scholastic ability or another appropriate output metric may be used to assess overall fairness.Source: §4 · p. 7, §4.1 · p. 8

5 Dependent Composition

Dependent composition covers settings where individuals’ outcomes are not independent, including fixed-size cohort selection and decisions affecting only part of a task universe. The section gives a fair offline selection construction and describes settings where fairness may be impossible or constrained.

5 Dependent Composition

  • Dependent composition includes selecting exactly n people or applying a classifier to only a subset of the task universe, rather than deciding each person’s outcome independently.Fairness comparisons must account for randomness in the ordering or subset; once either is fixed, an individual may be arbitrarily included or excluded.Source: §5 · p. 9

5.1 Basic Offline Cohort Selection

  • A uniformly random permutation followed by a fair classifier until n selections, with end-of-list fill-in if needed, is individually fair for any individually fair input classifier.This construction assumes the full universe is known and decisions are made offline.Source: §5.1 · p. 9

5.2 More complicated settings

  • With adversarial ordering and unknown universe size, no online cohort-selection solution exists.The section also omits a full discussion of more complicated dependent-composition scenarios in this extended abstract.Source: §5.2 · pp. 9–10

Constrained cohort selection

  • Under an external subgroup quota, distance-zero counterparts can be forced to have different selection probabilities, making fair constrained cohort selection impossible in characterized settings.The section illustrates the conflict with a cohort requirement that at least a specified fraction come from subset A.Source: Constrained cohort selection · p. 10

6 Extensions to Group Fairness

The section extends composition analysis to group-fairness definitions, showing that Conditional Parity can fail under OR composition and can miss subgroup harms. Task competition can also leave socially meaningful subgroups excluded even when classifiers adjust to meet parity across a protected group.

6 Extensions to Group Fairness

  • For Conditional Parity, OR composition yields .9375 ≠ .875 despite single-use parity, exposing a group-fairness failure.Figure 1 illustrates that the groups’ initially equal mean positive-classification probabilities diverge under OR composition.Source: §6 · p. 10, Figure 1 · p. 11
  • Composition can violate Conditional Parity even when individual fairness holds; restoring parity may sacrifice accuracy and discard useful information.The section notes that the individuals sharing the relevant z value are drawn closer together, not farther apart.Source: §6 · p. 10
  • Adjusting bids to meet gender Conditional Parity can still leave mothers excluded from job ads while increasing the overall rate for women.The jobs advertiser may fail to outbid home-goods advertising targeted at mothers, yielding a higher conditional ad probability for qualified women than for qualified mothers.Source: §6 · p. 11, Figure 3 · p. 12
  • Protections against subgroup discrimination may be ineffective when the relevant feature, such as parental status, is absent or illegal to collect in employment data.Other competing advertisers may legitimately target that feature.Source: §6 · p. 11
  • Conditional Parity can detect unfairness when related tasks claim different fractions across genders, but may miss socially meaningful subgroup selection when claims are equal.The figure gives parents as an example of a subgroup that may escape detection unless explicitly accounted for.Source: §6 · p. 11, Figure 2 · p. 12

A.1 Introduction

The paper studies how fair-in-isolation classifiers behave when composed, showing that composition can undermine fairness and that careful constructions can address some cases. It examines task-competitive, functional, and dependent compositions, extends the analysis to group fairness, and draws implications for system audits and fairness requirements.

A.1 Introduction

  • The paper initiates the study of fairness under composition and argues that component-only testing cannot establish whether a full system is fair.It also warns that group-based requirements can give meaningless signals or entrench poor outcomes for subgroups when composition is ignored.Source: §A.1 · pp. 14, 16
  • Fair-in-isolation classifiers for competing tasks may yield unfair outcomes, but RandomizeThenClassify can combine them fairly without modifying the components.The results are robust to tie-breaking choices; a second approach modifies the lower bidder’s classifier.Source: §A.1 · p. 15
  • Fair components do not generally guarantee fair functional compositions, although some OR compositions can satisfy fairness when the salient system outcome is measured.The discussion also applies functional composition to locating fairness requirements in feedback loops.Source: §A.1 · p. 15
  • Dependent selections require care: PermuteThenClassify and WeightedSampling address offline cohort selection, while online use requires a known universe size.The constructions apply online even under adversarial ordering when that size is known; when it is unknown, the passage states there is no solution.Source: §A.1 · p. 15
  • Group-fairness definitions can give inconsistent signals under composition, including missing unfair treatment of parents within race-and-gender groups.The paper describes task-competitive composition as exacerbating this intersectional subgroup concern.Source: §A.1 · p. 16

A.2 Related Work

  • Prior work covers one-shot fairness, group definitions, impossibility results, and empirical observations of uneven ad delivery, while this paper analyzes implications of composition.The related-work discussion cites Lambrecht and Tucker and Datta et al. on advertising delivery differences.Source: §A.2 · pp. 16–17

A.3.1 Shared Terminology

  • The paper uses “fair in isolation” for a classifier satisfying a fairness definition without composition, and focuses primarily on individual fairness with a task-specific similarity metric.It assumes access to a complete metric for each task and universe, using total variation distance unless otherwise specified.Source: §A.3.1 · p. 17, §A.3.2 · p. 17

A.3.2 Individual Fairness

  • A fair classifier can be extended to a larger universe while preserving its behavior on the original subset, and constructions can preserve a selected pair’s distance or set its positive-outcome probability ratio.The extension can be built in O(|U|^2) time from scratch; the metric-based fairness condition is D(u, v) ≥ d(C̃(u), C̃(v)).Source: §A.3.2 · p. 19

A.4.1 Same-task Functional Composition

Same-task composition combines outputs from repeated uses of a classification task, often asking whether any classifier gives a positive result. Even individually fair classifiers can violate OR fairness when composed, though the paper also gives conditions under which OR fairness is preserved.

Same-task Functional Composition

  • OR fairness measures whether the probability of at least one positive classification remains individually fair under composition, using the same metric as the component classifiers.The setting models outcomes such as a student being admitted to at least one college or a home-buyer receiving at least one loan approval.Source: §A.4.1 · p. 21

Differing Degrees of Composition

  • Students with equal qualifications may have different admission probabilities when they apply to different numbers of fairly evaluating colleges.Differences in application fees, counseling, or time can affect how many colleges a student can apply to; equal acceptance probabilities across the two students are not generally possible when schools accept both with non-trivial probability.Source: §A.4.1 · p. 22

Same-task Functional Composition

  • For any non-trivial metric, individually fair classifiers can violate OR fairness both when elements receive different numbers of classifications and when all receive the same classifiers.These are the existence results of Theorems 6 and 7.Source: §A.4.1 · pp. 22–23

Equal Degrees of Composition

  • 0.75 versus approximately 0.02: with two identical classifiers, students accepted with probabilities 0.5 and 0.01 have OR acceptance probabilities of 0.75 and approximately 0.02, despite an original distance of 0.49.This equal-degree example illustrates how composition can exceed the original fairness bound.Source: §A.4.1 · p. 23
  • As classifiers are repeatedly composed, positive-classification probabilities can approach one at different rates, creating divergence even for small systems.Figure 4 illustrates a case where the probability associated with pu exceeds the original bound for n ∈ (1, 8]; the discussion notes that small compositions may matter in settings such as loan applications.Source: §A.4.1 · p. 24, Figure 4 · p. 24

Conditions for Fair Composition

  • OR fairness is preserved when existing classifiers give every element at least 1/2 probability of a positive outcome and an added individually fair classifier also gives each element at least 1/2.This is the condition stated in Lemma 8 for adding one classifier under the same metric.Source: §A.4.1 · p. 24
  • Grouping classifiers into an OR of heavy ORs can make Lemma 8 applicable, and the approach extends to heavy Boolean functions of classifier outcomes.Here, “heavy” means having value one with probability at least 1/2; the paper says this test may be simpler than fully analyzing the classifiers.Source: §A.4.1 · p. 25

Other Composition Operators

  • The same-task analysis also considers NOR fairness and threshold outcomes, and reports that the observations extend to other composition operators.A threshold version can require at least k positive classifications when the appropriate dosage is known.Source: §A.4.1 · pp. 22, 25

A.4.2 Multiple Task Functional Composition

Composing individually fair classifiers across tasks can violate fairness for the system’s salient output, especially when the output metric does not dominate the input-task metrics. The section also distinguishes fairness for a composed outcome from fairness maintained separately for each task.

A.4.2 Multiple Task Functional Composition

  • In college admissions, admission and ability to pay may be judged by different metrics, while the salient outcome is whether a student can attend.The output metric may not be among the input-task metrics.Source: §A.4.2 · p. 26
  • When two task metrics are positive for a pair and the output metric is no larger than both, individually fair classifiers can violate AND Fairness under composition.The characterization is loose because it uses distances under only two classifiers.Source: §A.4.2 · pp. 26–27
  • Figure 5 shows that with pu = 0.9 and pv = 0.5, the AND-composed value for pu exceeds the original fair-distance bound for n ∈(1, 8].The passage notes that, unlike OR fairness, AND composition can be unfair even when pu and pv are both at least 0.5.Source: Figure 5 · p. 28

A.4.3 Implications of functional compositions

  • For same-task composition, fair components alone do not ensure system fairness for fewer than 10 applications, while many repeated-classification tasks are unlikely to face the issue absent systematic exclusion.The characterization is not exhaustive; the section contrasts small settings such as admissions or loans with large settings such as advertising.Source: §A.4.3 · p. 29
  • Compositions involving attributes irrelevant to a task, such as ability to pay tuition, can make fairness difficult to guarantee.The section describes multi-task composition results as less optimistic than same-task results.Source: §A.4.3 · p. 29

A.5 Multiple-Task Composition

  • Multiple Task Fairness requires fairness to hold independently for every task, preventing positive distance under one task from enlarging outcome distance under another.This is suited to distinct, incomparable outcomes, such as job advertisements and home-appliance advertisements.Source: §A.5 · p. 29

A.5.1 Task-Competitive Composition

Task-competitive composition selects among classifiers’ positive outputs when tasks compete for a limited slot or are processed in an order. Even individually fair classifiers can then fail multiple-task fairness, for any tie-breaking function.

A.5.1 Task-Competitive Composition

  • Task-competitive composition models competing tasks that yield at most one positive outcome, including ordered decisions and simultaneous choices resolved by a tie-breaking function.The function may encode individual preferences, classifier decisions, or system policy, and may be randomized.Source: §A.5.1 · pp. 30–31
  • Under strict preference for one task, a pair unequal on that task but equal on the later task can have unequal chances of reaching the later classifier.That unequal chance breaks equality for the later task even when its classifier is fair.Source: §A.5.1 · pp. 31–32
  • For any two tasks with nontrivial metrics, individually fair classifiers exist whose task-competitive composition violates multiple-task fairness for any tie-breaking function.The result applies whether preferences are strict or vary across individuals.Source: §A.5.1 · pp. 32–33
  • The authors suggest unfairness may occur often in practice and that small relaxations may not suffice, while noting the theorem itself establishes existence rather than frequency.They point to empirical observations.Source: §A.5.1 · pp. 32–33
  • When tasks conflict, removing the conflict may be preferable where feasible, such as offering bagged breakfast so attendance at class does not depend on foregoing breakfast.The example describes strict preference for breakfast over an SAT preparation class.Source: §A.5.1 · p. 33, Simple Fair Multiple-task Composition · p. 34

Simple Fair Multiple-task Composition

RandomizeThenClassify provides a general-purpose way to preserve multiple-task fairness in a single-slot setting without coordination among classifiers. The discussion then broadens to dependent selection, where decisions over individuals need not be independent.

Simple Fair Multiple-task Composition

  • Optimizing classifiers jointly with the tie-breaking function, utilities, and metrics may achieve fairness without sacrificing too much utility in some cases, but requires substantial coordination.The text says this approach may be impractical in some situations.Source: Simple Fair Multiple-task Composition · p. 34
  • RandomizeThenClassify achieves multiple-task fairness in the single-slot composition problem when each input classifier is individually fair in isolation.It selects a task from a distribution and then applies that task’s classifier; the system produces at most one positive classification.Source: Simple Fair Multiple-task Composition · pp. 34–35
  • The mechanism requires no coordination in classifier training and preserves each classifier’s ordering, but can drastically reduce total positive classifications.A third party can implement it without requiring explicit cooperation among classifiers.Source: Simple Fair Multiple-task Composition · pp. 34–35

A.5.2 Summary

  • The single-slot setting is a design choice; additional slots or scheduling flexibility may help in some cases, though the discussion notes limits to those options.More slots require careful analysis of cognitive load and user impact.Source: §A.5.2 · p. 35
  • Failing to enforce multiple-task fairness may enable generalized steering that diverts a group from a desirable outcome through advertising for a competing role.The example describes an employer advertising a teamwork-management role to keep women from seeing a technical-position advertisement.Source: §A.5.2 · p. 35

A.6 Dependent Composition

  • Dependent composition covers selection where outcomes may depend on other individuals, distinguishing subset classification from selecting exactly n individuals in cohort selection.The discussion identifies online versus offline operation, ordering, known universe size, and constrained selection as relevant settings.Source: §A.6 · pp. 36–37
  • For dependent composition, the system is specified independently of subset and ordering distributions, which may be outside its control or unknown to it.The example is an employer screening applicants without knowing their arrival order or which eligible candidates will apply.Source: §A.6 · pp. 36–37

A.6.1 Basic Offline Cohort Selection

Offline cohort selection can preserve individual fairness through randomized ordering or weighted sampling; online fairness depends on the ordering and whether the universe size is known.

A.6.1 Basic Offline Cohort Selection

  • PermuteThenClassify solves offline cohort selection for any individually fair classifier by processing a uniformly random permutation and selecting until the cohort is full.If the list reaches its end condition, the remaining elements are selected with probability 1.Source: §A.6.1 · p. 38
  • PermuteThenClassify can perform sub-optimally when the classifier is tuned to select far fewer elements than the cohort requires, leaving many selections to the end condition.The paper gives the example of a classifier tuned for O(log(n)) expected selections but used to select O(n) elements.Source: §A.6.1 · p. 42
  • Weighted Sampling is individually fair when the fair classifier's average positive-classification probability over U is at least 1/|U|.The method samples size-n subsets with weights proportional to the sum of their members’ classifier probabilities.Source: §A.6.1 · p. 42

A.6.2 Online Cohort Selection

  • With a uniformly random stream order and known stream length, an existing fair classifier yields an online cohort-selection solution by simulating PermuteThenClassify.The online procedure omits the initial permutation step.Source: §A.6.2 · p. 44
  • For adversarial ordering with known |U| and a stream containing all of U, a strict-stream solution exists, but its utility is no better than random selection.If adversarial ordering is allowed and |U| is unknown, no online cohort-selection solution exists.Source: §A.6.2 · pp. 44–45
  • Requiring only high-probability cohort completion does not straightforwardly resolve the unknown-universe impossibility across many possible universe sizes.The paper says this proposed fix breaks down when extended across many possible sizes.Source: §A.6.2 · p. 45

A.6.3 Constrained Cohort Selection

External subgroup quotas can conflict with individual fairness when groups contain sufficiently similar individuals but face different required selection rates.

A.6.3 Constrained Cohort Selection

  • γ-equivalence means each member of A is matched to k members of B at distance at most γ, with every member of B matched once.This captures cross-group similarity used in the impossibility result.Source: §A.6.3 · p. 45, Figure 8 · p. 46
  • When A and B have equivalent ability distributions but the quota requires all of A selected, some matched members of B have selection probability at most 1/5, creating a gap of at least 4/5 at distance zero.The example sets |B|=5|A| and requires half the cohort from A.Source: §A.6.3 · p. 46
  • If B is partitioned into subsets B_i that are γ_i-equivalent to A and the stated quota inequality holds, constrained cohort selection has no individually fair solution.The theorem’s condition compares (1−p)n/|B| with pn/|A| + Σ_i β_iγ_i, where β_i=|B_i|/|B|.Source: §A.6.3 · p. 46
  • In the university example, requiring 25% of selected students to be able to pay is incompatible with individual fairness when the theorem’s bound is approximately 0.11.The example uses |B|=1000, |A|=100, and n=550.Source: §A.6.3 · p. 48

A.6.4 Universe Subsets

The paper gives conditions for extending fairness across universe subsets and shows that group-fairness guarantees can behave differently under functional composition.

A.6.4 Universe Subsets

  • If outcomes outside the classifier’s control are unavailable or unknown, no classifier is guaranteed to solve the universe-subset problem for nontrivial Y.The thinning procedure may also violate individual-fairness constraints under a distribution other than Y.Source: §A.6.4 · pp. 48, 50
  • A classifier acting on a subset can be extended to an individually fair classifier on U when the other classifier is subset-fair and its outcomes lie in the acting classifier’s range.For cohort selection, the extension also requires an adjustable cohort size, which may not be practical.Source: §A.6.4 · p. 49
  • When every element has positive inclusion probability under Y, thinning classifications by q_min/q_w makes an individually fair classifier fair under Y.Here q_w is the probability that w appears in V, and q_min is the smallest such probability.Source: §A.6.4 · p. 50

A.7 Extensions to Group Fairness

  • For conditional parity, individually fair-in-isolation classifiers may fail that guarantee under composition, while composed systems can mislead from a subgroup or individual-fairness perspective.The paper presents cases where systems nominally satisfy group fairness despite troubling subgroup behavior, and cases where nominal failure coexists with individual fairness.Source: §A.7 · p. 51

A.7.1 Functional Composition

  • The individual-fairness results for functional composition largely extend to group fairness, with caveats arising from technical details of the definition.The paper considers same-task composition of classifiers satisfying conditional parity.Source: §A.7.1 · p. 51, Same-Task Functional Composition · p. 51

Same-Task Functional Composition

Same-task OR composition preserves Conditional Parity when classifiers treat individuals with the same qualification equally, but that condition is not guaranteed. The section also shows that group fairness signals and individual treatment can diverge under composition, while multiple-task functional composition raises questions about which protected and stratification sets matter.

Same-Task Functional Composition

  • If both classifiers treat individuals with the same qualification equally and satisfy Conditional Parity in isolation, their OR also satisfies Conditional Parity.The result applies to same-task composition.Source: Same-Task Functional Composition · p. 52
  • A single composition increases the groups’ acceptance-rate difference, which does not return to its original level until after 15 compositions.Group a2 approaches nearly 100% acceptance faster than group a1; absolute gains can outstrip those of group a1 even when the acceptance-rate ratio is not increasing.Source: Same-Task Functional Composition · p. 53
  • With p_h=1, p_m=.75, and p_l=.5, two applications violate Conditional Parity (.9375 != .875), although no individuals are pulled further apart.The example starts with Conditional Parity under a single application.Source: Same-Task Functional Composition · p. 53
  • Under same-task composition, Conditional Parity can fail even when Individual Fairness holds, and Individual Fairness can fail when Conditional Parity holds.The section notes that similar brittleness extends to cohort selection, calibration, other logical functions, and constrained settings.Source: Same-Task Functional Composition · p. 54

Multiple Task Functional Composition

  • Multiple-task functional composition raises questions about which protected and stratification sets should govern the combined outcome; similar results may leave detected unfairness ambiguous.The ambiguity may reflect weak requirements for socially meaningful subgroups or an uninteresting statistical artifact.Source: Multiple Task Functional Composition · p. 54

A.7.2 Multiple Task Composition

This section examines how fairness behaves under multiple-task composition, including conditional parity, online cohort selection, subset classification, and whether group-fairness signals reflect system-level fairness.

A.7.2 Multiple Task Composition

  • Under Theorem 25’s overlap condition, classifiers satisfying conditional parity separately can violate it under task-competitive composition; unequal group intersections or tie-breaking weights also create failures.In the simplest case of uniform strict tie-breaking, different intersection sizes across groups suffice.Source: §A.7.2 · pp. 56–57
  • RandomizeThenClassify restores conditional parity for both tasks when individually parity-compliant classifiers fail parity under task-competitive composition.The authors conclude this mitigation extends to many tie-breaking functions and non-identical tasks, with either shared or different protected attribute sets.Source: §A.7.2 · p. 57
  • For unrelated tasks with uniform tie-breaking and classifiers treating equally qualified individuals equally, conditional parity holds under composition even when a subgroup is treated poorly.Thus, in some cases conditional parity misses subgroup unfairness despite task composition.Source: §A.7.2 · pp. 58, 60
  • In the advertising example, home-goods bids targeting mothers can outcompete job ads, while broader bids to women raise women’s overall ad rate without reaching mothers.The resulting exclusion can disadvantage mothers without similarly disadvantaging fathers, even if parity by gender is satisfied.Source: §A.7.2 · pp. 60–61, Figure 12 · p. 61
  • Subgroup exclusion is difficult to detect because relevant attributes such as parental status may be unavailable to job classifiers, and predicting all socially meaningful subgroups may be difficult.The passages also note that conditional-parity definitions often detect unfairness when protected groups interact obviously with task qualification, but can miss other cases.Source: §A.7.2 · pp. 57, 61, 62

Online Cohort Selection

  • Selecting the first required number of each protected group can achieve online statistical parity, yet adversarial ordering can violate individual and conditional parity.This can poison future decisions; ordering may disadvantage subgroups whose attributes are absent from the feature set, and even default last-name sorting can affect loan allocation.Source: Online Cohort Selection · p. 63

Subset Classification Problem

  • When each protected-attribute and stratification pair has positive weight in Y, the Section A.6.4 adjustment selects each element w with probability qmin pw.Here pw is the probability of selection with uniform inputs.Source: Subset Classification Problem · p. 63
  • For comparable outcomes, a procedure that satisfies conditional parity on U\V may fail on V alone, so composition requires stronger conditions.Lemma 29 gives a sufficient condition: if C* satisfies conditional parity on U and all its outcomes lie in the potential outcome space for V, a classifier C′ exists for V such that applying C* to U\V and C′ to V satisfies conditional parity.Source: Subset Classification Problem · pp. 63–64

A.7.4 Group Fairness: Summary

  • Group-fair classifiers may compose poorly, so their fairness signals are unreliable under composition and do not guarantee fairness even when actuarial fairness is accepted.The authors identify subgroup fairness as an additional concern and suggest incorporating contextual information into group- and individual-fairness classifiers as a direction for future work.Source: §A.7.4 · p. 64

A.8 Summary of Composition Results

The paper concludes that fairness can fail under composition, can sometimes be mitigated, and must be assessed in the context of the whole system. It also identifies open questions about practical constructions, privacy, and generalization.

A.8 Summary of Composition Results

  • Fairness judgments require composition context: apparently unfair components may protect a system, while apparently fair components may fail to do so.The paper argues that certifying a classifier as fair or unfair requires understanding the composition context in which it will be used.Source: §A.8 · p. 64
  • Augmented classifiers could specify anticipated input distributions, operating mode and ordering, and expected post-processing, but that information may have privacy implications.A family of classifiers parametrized by the anticipated input distribution could allow later selection when more information is available.Source: §A.8 · pp. 64–65

A.9 Conclusions and Future Work

  • There is no guarantee of fairness under composition, post-processing, or arbitrary side information for either individual fairness or group fairness.The paper also concludes that fairness violations can sometimes be corrected after the fact, unlike privacy breaches.Source: §A.9 · p. 65
  • Fairness auditing and enforcement must account for the outcomes measured and whether those conclusions hold under composition.The choice of outcomes is critical to whether a system reflects the original fairness requirement.Source: §A.9 · p. 65

A.9.1 Future Work

  • Future work should improve RandomizeThenClassify’s allocation and practical utility guarantees and develop mechanisms for constrained cohort selection.The paper notes that acceptable relaxations may be possible when perfectly fair solutions cannot be found.Source: §A.9.1 · p. 65
  • The privacy tradeoffs of augmented classifiers and the requirements for their use remain open questions.The authors caution that fairness at the expense of a total loss of privacy is unlikely to be acceptable in practice.Source: §A.9.1 · p. 66
  • The paper largely leaves generalization unaddressed and calls for studying construction generalization and learned representations of individual-fairness metrics.It also points to alternative similarity measures, such as similar rewards to effort, as a possible response to some constrained-cohort impossibility results.Source: §A.9.1 · p. 66

B Multiple Task Fairness - Empirical Intuition

In the seminar-and-pizza example, composing individually fair task classifiers can produce substantial fairness violations, with the pattern depending on task preference and ordering. RandomizeThenClassify offers a fair-composition alternative, though the experiment reports a utility trade-off and simple compensation.

B Multiple Task Fairness - Empirical Intuition

B.1 Fair Composition

  • RandomizeThenClassify reduced expected utility by about 50% over 15 trials, while increasing each classifier’s positive-classification probability by 10% reduced the loss to about 40%.The authors caution that their simple positive-utility objective may require more nuanced training adjustments in more complicated settings.Source: §B.1 · p. 72

Related papers

Loading 1806.06122v2…