🤖 machine learning

Fairness vs Performance: Characterizing the Pareto Frontier of Algorithmic Decision Systems

This paper characterizes the Pareto frontier of algorithmic decision systems by demonstrating that optimal trade-offs between utility and group fairness are achieved through deterministic, group-specific threshold rules on success probabilities, a result that holds across various fairness metrics, utility functions, and algorithmic processing stages.

Original authors: Mieke Wilms, Christoph Heitz

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mieke Wilms, Christoph Heitz

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the captain of a ship (the Decision Maker) trying to navigate through a foggy sea to reach a treasure island (the Goal). You have a map with coordinates for every passenger on board (the Data). Your job is to decide who gets a lifeboat (a Positive Decision) and who stays on the sinking ship (a Negative Decision).

However, there are two groups of passengers: Group A and Group B. You want to save as many people as possible to reach the treasure (maximize Performance), but you also want to make sure you aren't unfairly leaving one group behind more than the other (maximize Fairness).

This paper is a mathematical map that tells us the absolute best possible balance between saving the most people and treating the groups fairly. It asks: What is the theoretical limit of how well we can do both at the same time?

Here is the breakdown of their findings using simple analogies:

1. The "Efficiency vs. Fairness" Tug-of-War

Usually, people think you have to choose: either be super efficient (save everyone you think will survive) or be perfectly fair (give everyone an equal chance). The paper shows that this isn't just a simple trade-off. There is a specific "frontier" (a boundary line) that represents the best possible outcomes. You can't go beyond this line. If you want more fairness, you must accept a little less efficiency, and vice versa.

2. The Magic "Threshold" Rules

The paper discovers that the best way to navigate this tug-of-war is to use a simple cutoff rule (a threshold).

Imagine you have a "Survival Score" for every passenger.
The Old Way: You might think the rule is always: "If the score is above 50, give them a lifeboat."
The New Discovery: The paper proves that sometimes, the best rule is actually the opposite for a specific group: "If the score is below 50, give them a lifeboat."

Why would you do that?
Think of it like a medical triage.

Scenario A (Standard): You give medicine to the sick people who are likely to get better. (High score = Good).
Scenario B (The Surprise): Imagine a medicine that cures the sick but kills the healthy. Here, you only want to give the medicine to people who are very sick (low probability of being healthy). If you gave it to someone with a "high chance of being healthy," you might kill them.
In this case, the "Fair" and "Efficient" move is to set a rule where you only help the people with the lowest scores. The paper calls this an Upper-Bound Threshold. It sounds counter-intuitive (helping the "worse" candidates), but mathematically, it's the only way to be both fair and efficient in certain situations.

3. The "Group-Specific" Secret

The paper finds that the perfect rule often looks different for Group A than for Group B.

Group A might need a "High Score" to get a lifeboat.
Group B might need a "Low Score" to get a lifeboat.

This is called a Group-Specific Threshold. The paper proves that no matter how complex your computer algorithm is (whether it's a simple formula or a giant neural network), if it is trying to be the best possible at balancing fairness and performance, it will eventually act exactly like these simple cutoff rules.

4. The "Black Box" Surprise

Here is the most surprising part: You don't actually need to tell the computer "Group A" or "Group B" to get these results.

Imagine the computer doesn't know which group a passenger belongs to.
However, if the computer looks at other clues (like the color of their shirt or their age) that happen to correlate with their group, it might accidentally figure out the groups on its own.
The paper shows that even if you ban the computer from looking at the "Group" label, if it is smart enough to find the best balance, it will naturally start treating the groups differently because the data itself forces it to.

5. The "Universal Benchmark"

The authors created a "Gold Standard" map.

If you build a new AI system, you can plot its performance on this map.
If your AI is far away from the "Frontier" line, you know you can do better.
If your AI is right on the line, you know you have reached the absolute limit of what is possible with that data. You cannot get better performance without sacrificing fairness, or better fairness without sacrificing performance.

Summary

This paper is like a physics law for decision-making. It says:

There is a limit: You can't have perfect fairness and perfect performance simultaneously; there is a specific curve you must follow.
Simple is best: The best solutions are simple "cutoff" rules (like "help if score > X").
Sometimes "Up" is "Down": Depending on the situation, the fairest and most efficient rule might be to help the people with the lowest scores, not the highest.
It happens automatically: Even if you try to hide group information, the best algorithms will naturally figure out how to treat groups differently to reach that perfect balance.

The paper provides the mathematical proof for these rules, ensuring that when we design fair AI, we know exactly what the "best possible" outcome looks like, so we don't settle for less.

Technical Summary: Fairness vs Performance: Characterizing the Pareto Frontier of Algorithmic Decision Systems

Problem Statement

The paper addresses the fundamental tension between maximizing decision-maker (DM) utility (performance) and ensuring group fairness in binary prediction-based decision systems. While existing literature often treats fairness as a constraint or focuses on specific trade-offs within restricted model classes (e.g., neural networks or logistic regression), the authors argue that the space of possible trade-offs is poorly understood. Specifically, there is a lack of characterization regarding the Pareto frontier—the set of optimal solutions where one objective cannot be improved without degrading the other—across the entire space of possible decision rules.

The central research question is: Can the Pareto frontier of a prediction-based decision system be characterized in the solution space of all possible technical implementations, independent of how the system is designed (pre-, in-, or post-processing)?

Methodology

The authors conceptualize decision-making as a multi-objective optimization problem involving two dimensions:

DM Utility ( $U$ ): Modeled via a utility matrix $(u_{ij})$ representing the benefit/harm to the decision-maker for outcomes $(D, Y)$ , where $D$ is the decision and $Y$ is the true outcome.
Fairness ($FS$): Modeled via a generalized fairness score derived from Decision Subject (DS) utilities $(v_{ij})$ . Unlike classical confusion-matrix metrics (e.g., TPR, FPR), this approach uses a utility matrix to capture the actual impact of decisions on individuals (benefit or harm), allowing for the modeling of various distributive justice principles (egalitarianism, prioritarianism, Rawlsian max-min).

Theoretical Framework

Decision Rules: The analysis considers all possible decision rules $d(\mathbf{x}) \to D$ , including randomized policies and those explicitly dependent on the protected attribute $a$ .
Optimization Space: Instead of optimizing over complex feature spaces $\mathbf{x}$ , the authors reduce the problem to optimizing over the probability of success $p = P[Y=1|\mathbf{x}]$ . They define the decision rule as a function $d(p)$ mapping success probabilities to decision probabilities.
Discretization: For proof purposes, the probability space $[0, 1]$ is discretized into bins, allowing the expected utilities to be expressed as weighted sums. The limit $N \to \infty$ is taken to recover continuous results.
Key Theorem (Theorem 3.1): For a single group, the decision rule that maximizes DM utility for a fixed level of DS utility is shown to be either a lower-bound threshold rule ( $D=1$ if $p \ge t$ ) or an upper-bound threshold rule ( $D=1$ if $p < t$ ).
Main Theorem (Theorem 3.3): Extending to multiple groups, the paper proves that any Pareto-optimal decision rule with respect to DM utility and a generalized fairness score must consist of group-specific deterministic threshold rules applied to $p(\mathbf{x})$ . These rules may be lower-bound, upper-bound, or combinations thereof.

Key Contributions

Characterization of the Pareto Frontier: The paper provides a complete characterization of the Pareto frontier for binary decision systems across all technical designs. It establishes that the frontier is composed exclusively of group-specific deterministic threshold rules on the success probability $p$ .
Discovery of Upper-Bound Thresholds: Contrary to classical optimality theorems (e.g., Hardt et al., Corbett-Davies et al.) which suggest only lower-bound thresholds for fairness constraints, this work demonstrates that upper-bound threshold rules (preferring individuals with lower success probabilities) can be Pareto-optimal. This occurs when the DS utility matrix implies that decisions are harmful to high-probability individuals or beneficial to low-probability individuals (e.g., medical treatments with severe side effects for healthy patients).
Technology-Agnostic Benchmark: The location of the Pareto frontier is shown to depend only on population characteristics (specifically the distribution of success probabilities $g(p|a)$ ), the utility functions of the DM and DS, and the chosen fairness metric. It is independent of the algorithmic implementation (pre-, in-, or post-processing).
Generalization of Fairness Metrics: The framework generalizes existing results to arbitrary DS utility functions and non-egalitarian justice principles (e.g., Rawlsian max-min, prioritarianism), moving beyond simple equality of rates.
Feasibility without Protected Attributes: The paper notes that while the optimal rules are group-specific, they can be approximated by algorithms that do not explicitly access the protected attribute $a$ , provided other features are sufficiently correlated with $a$ .

Results

Synthetic Data Analysis: Using synthetic data with two groups, the authors constructed the Pareto frontier for different DS utility matrices.
- In cases corresponding to Selection Rate (Demographic Parity), the frontier consisted entirely of lower-bound threshold rules.
- In cases with specific DS utility matrices (e.g., where treatment is harmful to those without the disease), the frontier included upper-bound threshold rules for one group. This resulted in a "cherry-picking" phenomenon where individuals with lower success probabilities were selected to maximize fairness while maintaining high utility.
- The results showed that enforcing fairness (minimizing $FS$) often required switching from lower-bound to mixed (lower/upper) threshold rules, significantly altering the decision landscape compared to unconstrained optimization.
Comparative Study (Adult Income Dataset): The authors compared their theoretical Pareto frontier against the PF-SMG (Pareto front stochastic multi-gradient) in-processing algorithm.
- The theoretical frontier dominated the PF-SMG results, confirming that PF-SMG was suboptimal.
- Crucially, the PF-SMG algorithm, despite not having access to the protected attribute $a$ , implicitly learned to approximate the group-specific threshold rules predicted by the theory. This suggests that even "blind" algorithms tend to converge toward the theoretically optimal group-dependent structures when optimizing for the fairness-utility trade-off.

Significance and Claims

The paper claims to provide a principled foundation for evaluating and comparing algorithmic decision systems. Its significance lies in:

Defining the Theoretical Limit: It establishes an upper bound on achievable performance for any given level of fairness, serving as a "technology-agnostic benchmark." No decision system based on the same feature vector can exceed this boundary.
Legal and Ethical Implications: By showing that group-specific threshold rules (which may appear discriminatory) are often the mathematically optimal solution for fairness-utility trade-offs, the paper raises questions about the legal distinction between direct and indirect discrimination. If high-performing algorithms naturally converge to these rules even without explicit access to protected attributes, the nature of "discriminatory alternatives" in legal contexts (e.g., the "Less Discriminatory Alternative" defense) requires re-evaluation.
Beyond Constraint Optimization: The work moves beyond the "fairness as a constraint" paradigm, offering a holistic view of the trade-off space that includes partial fairness regimes.
Methodological Shift: It suggests that future ML research might benefit from focusing on estimating the probability distributions $g(p|a)$ rather than just learning complex feature-to-outcome mappings, as the former is sufficient to determine the location of the Pareto frontier.

The authors conclude that their results generalize existing optimality theorems and offer a necessary theoretical baseline for understanding the inherent limits of fairness in algorithmic decision-making.