Maximin Relative Improvement: Fair Learning as a Bargaining Problem

AI summary

Overview

Research area: Statistical machine learning / group fairness, at the intersection of robust optimization and cooperative game theory (bargaining theory).

Technical level: Advanced. The paper uses formal definitions, axioms, convex analysis, and game-theoretic solution concepts; the empirical estimator section relies on empirical process arguments. A beginner can follow the high-level story in the introduction but the theorems require a graduate-level statistics or ML background.

Scope (1 sentence): The paper reframes group fairness in a single shared predictor as a cooperative bargaining problem among subpopulations, proposes "relative improvement" (the fraction of each group's achievable risk reduction actually captured) as the fairness criterion, and proves it corresponds to the Kalai–Smorodinsky solution.

What This Paper Is About

When one model must serve several subpopulations with different levels of inherent predictability, existing worst-case methods (minimizing worst-group loss or worst-group regret) compare groups on an absolute loss scale, implicitly assuming a unit of loss reduction means the same thing for every group. The authors instead ask how much of each group's own available improvement a model captures, and they treat the trade-off among groups as a negotiation in which each group concedes from its individual optimum toward a mutually acceptable compromise. The goal is a fairness criterion with explicit axiomatic justification and finite-sample guarantees.

Key Contributions

1. Relative improvement as a fairness criterion. The authors define relative improvement as the ratio of achieved risk reduction to potential risk reduction from a baseline predictor, and show that maximizing its worst case is exactly the Kalai–Smorodinsky bargaining solution, which supplies axiomatic justification (scale invariance, individual monotonicity, and others). They present three instantiations: parametric linear regression with squared loss, binary classification with logistic loss, and a nonparametric RKHS setting.

2. A unified bargaining framework. Existing robust optimization methods are shown to correspond to classical bargaining solutions under one common mapping: Group DRO (Sagawa et al., 2019) to the Rawlsian solution, maximin explained variance (Meinshausen and Bühlmann, 2015) to the egalitarian solution, and minimax regret (Agarwal and Zhang, 2022) to the equal-loss solution. Theorem 3.4 establishes the geometric well-posedness (compact risk set, convex hull containing no Pareto optimal points outside the risk set) needed to import bargaining theory into fair learning.

3. Axiomatic characterization as a decision guide. Each criterion is uniquely characterized by a distinct subset of axioms (Table 1), making the normative commitments of each method explicit and directly comparable. The authors frame this as a decision guide rather than a claim that relative improvement is universally best.

4. Learning-specific guarantees. The authors prove relative improvement satisfies individual rationality (no group is harmed relative to baseline, Theorem 4.1), which minimax regret violates, and establish an O(1/√n) finite-sample convergence guarantee.

Main Findings

• The motivating gap in absolute criteria: In the North Dakota example using age to predict income for white and non-white workers in the 2018 American Community Survey (Ding et al., 2021), non-white workers have roughly ten times more potential improvement (the gap between the unconditional mean predictor and group-optimal performance) than white workers. Equal absolute reductions would extract nearly all available signal from the white group while poorly serving the non-white group.

• Minimax regret harms the less-predictable group: Revisiting that example in Figure 1, minimax regret yields relative improvements of (-74%, 82%) — allocating nearly all model capacity to the non-white group and leaving the white group worse than baseline. Maximin relative improvement equalizes proportional gains at (57%, 57%).

• Exact correspondence to Kalai–Smorodinsky: In the two-group case, the maximin relative improvement solution is the unique solution satisfying Pareto optimality, symmetry, scale invariance, and individual monotonicity (adapted from Kalai and Smorodinsky, 1975). This is stated in Proposition 4.2.

• More than two groups requires two refinements: For m > 2, Roth (1979) showed no solution satisfies all four axioms simultaneously. The paper uses the leximin refinement (Imai, 1983), which hierarchically prioritizes the sorted relative improvements, and comprehensive closure. Proposition 4.4 states the unique characterization via Pareto optimality, symmetry, scale invariance, independence of irrelevant alternatives with ideal point (IIIA), and modified individual monotonicity (IM').

• No-harm guarantee: Theorem 4.1 shows that when the baseline predictor f₀ is in the function class, the maximin relative improvement solution satisfies R_g(f_RI) ≤ R_g(f₀) for all groups — individual rationality in bargaining terms. Minimax regret can violate this, yielding R₁(θ_Regret) > R₁(0) when group 1 has less potential improvement than group 2.

• Well-posedness of the learning problem: Under either a parametric assumption (convex continuous loss in θ, integrable dominating function, compact convex parameter space) or a nonparametric one (convex continuous loss in t, integrable dominating function, convex and compact function class with continuous evaluation maps), Theorem 3.4 shows the risk set R(F) is compact; its convex hull minus the risk set contains no Pareto optimal point; and with strictly convex loss, every weakly Pareto optimal point in R(F) is Pareto optimal and the convex hull minus the risk set contains no weakly Pareto optimal point either. Convexification is therefore an exact relaxation.

• Equivalence under comprehensive closure: Theorem 4.3 states that when f₀ is in the function class, the leximin solution on R(F) coincides with the leximin solution on its comprehensive closure, meaning the standard bargaining assumption of voluntary utility disposal is not restrictive here.

• Comparison of axioms across solutions: Table 1 reports Pareto optimality, symmetry, scale invariance, independence of irrelevant alternatives, individual monotonicity, translation invariance, and strong monotonicity for relative improvement, the Nash bargaining solution, explained variance, and regret. Only the Kalai–Smorodinsky-based relative improvement satisfies Pareto optimality, symmetry, scale invariance, and individual monotonicity simultaneously. GDRO, MMV, and MMR only guarantee weak Pareto optimality. The Nash solution violates individual monotonicity.

• Axiom-based selection rather than universal dominance: Remark 4.5 notes that most criteria in Table 1 select Pareto-optimal profiles and so cannot be ranked by Pareto dominance alone. A practitioner who prioritizes scale invariance selects relative improvement; one who prioritizes strong monotonicity over scale invariance is led to the egalitarian solution.

• Not reported in the available content: The empirical estimator section is truncated mid-equation, so no experiments, datasets, or empirical performance numbers beyond the North Dakota illustration are reported in the text provided.

Methodology in Plain English

The authors start from a general form of group fairness optimization, where a predictor is chosen by maximizing an aggregation function of the per-group risks. They reinterpret each predictor as producing a vector of group risks, and map this into a bargaining problem: groups become players, negative risk becomes utility, the baseline predictor becomes the disagreement point (the outcome if groups do not cooperate), each group's own optimum becomes its ideal point, and the set of achievable risk vectors becomes the feasible set.

Under this mapping, any fairness criterion implicitly picks a bargaining solution. The authors then show which classical solution each existing robust method picks, and prove that their proposed criterion picks the Kalai–Smorodinsky solution, which is defined as the point that equalizes each group's proportional gain relative to its own ideal point. For more than two groups they adopt the leximin refinement, which resolves ties in a priority order (best worst-group, then second worst, and so on), and they prove the solution is unchanged when the feasible set is enlarged by comprehensive closure.

To make this rigorous, they verify the geometric conditions that classical bargaining theory assumes — compactness and convexity of the feasible set — deriving them from standard regularity conditions on the loss and function class rather than assuming them. Finally, they analyze the finite-sample version, where each group's population risks are replaced by empirical averages over n_g observations, and establish an O(1/√n) convergence guarantee.

Why This Matters

Impact on research: The paper supplies a single framework in which competing fairness criteria are not just heuristics but distinct bargaining solutions, each with an explicit axiom set. This lets researchers compare fairness methods on normative grounds rather than only by benchmark performance, and it provides a generic bridge — any bargaining solution that selects a Pareto-optimal outcome can be imported into fair learning whenever the stated assumptions hold.

Real-world applications:

• Income prediction across racial groups using survey data such as the American Community Survey, where groups differ sharply in potential predictability.
• Lending and credit scoring, where a single model serves applicants with very different signal availability in the available features.
• Hiring and clinical decision support, where the same predictor is deployed across subpopulations with different achievable accuracy.
• Any multi-objective setting where the "groups" are different evaluation metrics rather than demographic groups (Remark 2.1), since the criterion balances performance across all objectives.

Industry relevance: Deployed models in regulated domains must often justify how competing group outcomes were balanced. The no-harm guarantee provides a property that can be stated directly — no group is worse than the baseline — and the scale-invariance property matters in practice because a unit of loss is rarely comparable across groups with different predictability.

Future Directions

• Statistical estimation beyond the guarantee: The paper states an O(1/√n) finite-sample convergence rate, but the empirical estimator section is truncated in the provided content; full empirical evaluations of the estimator are a natural next step.
• Choosing among axioms in practice: Remark 4.5 leaves the selection of which axioms matter most to the practitioner; operational guidance for specific domains is an open question.
• Uniqueness of predictors, not just risk vectors: Remark 3.1 notes that the Kalai–Smorodinsky solution guarantees a unique risk vector but not necessarily a unique predictor; uniqueness requires additional assumptions such as strict convexity of the loss (Theorem B.3).
• Extending beyond the stated regularity conditions: Assumptions 3.2 and 3.3 cover the three presented examples under standard conditions; applying the framework to non-convex function classes or unbounded losses remains open.

Target Audience

Graduate students and researchers in statistical machine learning, fairness, and optimization; game theorists interested in applications of cooperative bargaining solutions; and practitioners in regulated industries (lending, hiring, healthcare, survey-based income estimation) who must choose and justify a fairness criterion for a multi-group predictor.

Authors’ abstract

When deploying a single predictor across multiple subpopulations, we propose a fundamentally different approach: interpreting group fairness as a bargaining problem among subpopulations. This game-theoretic perspective reveals that existing robust optimization methods such as minimizing worst-group loss or regret correspond to classical bargaining solutions and embody different fairness principles. We propose relative improvement, the ratio of actual risk reduction to potential reduction from a baseline predictor, which recovers the Kalai-Smorodinsky solution. Unlike absolute-scale methods that may not be comparable when groups have different potential predictability, relative improvement provides axiomatic justification including scale invariance and individual monotonicity. We establish finite-sample convergence guarantees under mild conditions.