Technical Summary: Maximin Relative Improvement as a Bargaining Problem

1. Problem Formulation

The paper addresses the challenge of deploying a single unified predictor across multiple subpopulations (groups) where optimizing for one group often degrades performance on others. Existing approaches, such as minimizing worst-group loss (Group DRO) or minimizing worst-group regret (Minimax Regret), rely on absolute comparisons of risk or regret across groups.

The authors argue that absolute criteria fail when groups differ in inherent predictability (the "potential improvement" available from a baseline to an optimal predictor). If Group A has a large potential for improvement and Group B has a small potential, an absolute minimax regret approach may allocate nearly all model capacity to Group A to minimize its absolute regret, potentially leaving Group B with performance worse than the baseline. This occurs because a unit of absolute risk reduction is not equally meaningful across groups with different signal-to-noise ratios.

2. Methodology: Fair Learning as a Bargaining Problem

The Bargaining Framework

The authors reframe group fairness as a cooperative bargaining problem among subpopulations.

• Players: The subpopulations (groups).
• Disagreement Point ($d$): The risk incurred by a baseline predictor $f_0$ (e.g., the unconditional mean in regression or majority class in classification). This represents the outcome if groups fail to cooperate.
• Ideal Point ($u^{max}$): The risk incurred by the group-optimal predictor $f^*_g$ for each group.
• Feasible Set: The set of achievable risk vectors $\mathcal{R}(\mathcal{F})$ induced by the function class $\mathcal{F}$.

The optimization seeks a compromise where groups sacrifice some performance from their individual optima to reach a mutually acceptable solution.

Relative Improvement Criterion

The paper proposes Relative Improvement ($\rho_g$) as the fairness metric. For a group $g$, it is defined as the ratio of the actual risk reduction achieved by a predictor $f$ to the maximum possible risk reduction (the gap between baseline and group-optimal):

$$\rho_g(f) = \frac{R_g(f_0) - R_g(f)}{R_g(f_0) - R_g(f^*_g)}$$

The proposed learning objective is Maximin Relative Improvement (MMRI):
$$f_{RI} = \arg \max_{f \in \mathcal{F}} \min_{g \in \mathcal{G}} \rho_g(f)$$

Theoretical Connection: Kalai–Smorodinsky Solution

The authors establish that the MMRI criterion corresponds exactly to the Kalai–Smorodinsky (KS) bargaining solution (Kalai & Smorodinsky, 1975).

• Geometric Interpretation: In the utility space (where utility is negative risk), the KS solution is the unique point on the Pareto frontier that equalizes the relative gains from the disagreement point for all players.
• Axiomatic Justification: The KS solution is uniquely characterized by four axioms:
  1. Pareto Optimality (PO): No group can be improved without harming another.
  2. Symmetry (SYM): Groups with identical feasible sets and disagreement points are treated equally.
  3. Scale Invariance (SI): The solution is invariant to affine transformations of the utility scale (crucial when groups have different baseline predictability).
  4. Individual Monotonicity (IM): If the feasible set expands (more options available) while keeping other groups' optima fixed, no group should be harmed.

The paper proves that for $m=2$ groups, MMRI satisfies all four axioms. For $m > 2$, it utilizes the leximin refinement (lexicographic maximin) to ensure uniqueness and Pareto optimality, satisfying modified versions of these axioms.

Comparison with Existing Methods

The paper maps existing robust optimization methods to other classical bargaining solutions:

• Group DRO (Minimax Risk): Corresponds to a Rawlsian solution (maximizing the minimum absolute utility).
• Maximin Explained Variance: Corresponds to an Egalitarian solution (equalizing absolute gains from the disagreement point).
• Minimax Regret: Corresponds to an Equal Loss solution (equalizing absolute deviations from the ideal point).

Unlike MMRI, these methods generally lack Scale Invariance, leading to the failure modes observed when groups have heterogeneous predictability.

Well-Posedness and Convergence

The authors verify that the learning problem induces a well-posed bargaining problem by establishing conditions under which the feasible risk set $\mathcal{R}(\mathcal{F})$ is compact and its convex hull contains no non-realizable Pareto optimal points. These conditions hold for:

• Parametric settings (convex compact parameter space, convex continuous loss).
• Nonparametric RKHS settings (convex compact function class, continuous evaluation maps).

Furthermore, the paper establishes a finite-sample convergence guarantee of $O(1/\sqrt{n})$ for the empirical maximin relative improvement estimator, matching the rates of regret-based methods under standard regularity conditions (Lipschitz loss, entropy conditions).

3. Key Contributions

1. Relative Improvement as a Fairness Criterion: Proposes a metric that normalizes risk reduction by the group-specific potential improvement, ensuring comparability across groups with different inherent predictability.
2. Unified Bargaining Framework: Demonstrates that existing robust fairness methods (Group DRO, Minimax Regret, etc.) are equivalent to specific classical bargaining solutions, allowing for an axiomatic comparison of their normative commitments.
3. Axiomatic Characterization: Proves that Maximin Relative Improvement is the unique solution satisfying Pareto Optimality, Symmetry, Scale Invariance, and Individual Monotonicity (or their leximin refinements for $m>2$).
4. No-Harm Guarantee: Shows that if the baseline predictor is within the function class ($f_0 \in \mathcal{F}$), the MMRI solution guarantees that no group performs worse than the baseline (Individual Rationality), a property Minimax Regret violates.
5. Finite-Sample Guarantees: Provides convergence rates for the empirical estimator.

4. Empirical Results

The authors evaluate the method on the 2018 American Community Survey (ACS) data, predicting log-transformed income across 50 U.S. states with binary partitions (sex, race) and various features (age, education, marital status, householder status).

• Observation of Asymmetry: The study finds that differential predictability is pervasive. The "gap ratio" (ratio of potential improvements between groups) ranges from 0.04 to 3.48. In 73% of configurations, the asymmetry is moderate-to-extreme; in the race partition, 86% of states show extreme asymmetry for householder status.
• Performance Comparison:
  • Minimax Regret (MMR): In cases of high asymmetry (e.g., North Dakota, race partition, age feature), MMR allocates nearly all model capacity to the group with higher potential improvement, resulting in the other group performing worse than the baseline (e.g., -74% relative improvement).
  • Maximin Relative Improvement (MMRI): Consistently equalizes the relative improvement across groups (e.g., achieving 57% for both groups in the North Dakota example), avoiding the "harm" to the less predictable group.
  • Other Methods: Group DRO and Maximin Explained Variance also deviate from the equal-relative-improvement line in asymmetric settings.

5. Significance and Claims

The paper claims that interpreting fairness as a bargaining problem provides a principled, axiomatic foundation for selecting fairness criteria.

• Scale Invariance is Critical: The authors argue that when groups differ in inherent predictability, scale-invariant criteria (like KS/Relative Improvement) are necessary to avoid extracting unequal fractions of available signal.
• Decision Guide: The framework does not claim one criterion is universally superior. Instead, it serves as a decision guide: practitioners should identify which axioms (e.g., Scale Invariance vs. Strong Monotonicity) are most relevant to their context. If groups have heterogeneous predictability, the axiomatic properties of MMRI make it the natural choice.
• Theoretical Bridge: The work bridges cooperative game theory and fair learning, proving that standard learning assumptions (compactness, convexity) are sufficient to import classical bargaining solutions into machine learning without ad-hoc penalty choices.

The authors note limitations, including the computational complexity of finding leximin solutions for many groups and the challenges of extending the framework to overparameterized regimes where strict convexity and standard complexity controls may fail.