Maximin Relative Improvement: Fair Learning as a Bargaining Problem

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.

When a single model serves several demographic groups, there is often no single model that is best for all groups at once. Which predictor should we choose? We answer this by viewing the groups as parties to a negotiation—a bargaining problem in which each group negotiates over the predictive gain it receives. This perspective shows that existing robust learning methods correspond to different bargaining principles, but many compare groups using absolute losses or regrets. Such comparisons can be misleading when groups differ in how much improvement is possible: one group may receive nearly all of its available gain while another receives only a small fraction, or may even be worse off than the baseline. We propose maximin relative improvement, which chooses the model that maximizes the worst group's fraction of achievable improvement. We prove that this criterion exactly recovers the classical Kalai–Smorodinsky bargaining solution. More broadly, our framework acts as a decision guide: by identifying which fairness principles matter in a given setting, practitioners can choose the learning criterion that best matches their goals.