Maximin Relative Improvement: Fair Learning as a Bargaining Problem

Jiwoo Han, Moulinath Banerjee, Yuekai Sun
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:39539-39570, 2026.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-han26a, title = {Maximin Relative Improvement: Fair Learning as a Bargaining Problem}, author = {Han, Jiwoo and Banerjee, Moulinath and Sun, Yuekai}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {39539--39570}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/han26a/han26a.pdf}, url = {https://proceedings.mlr.press/v306/han26a.html}, 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.} }
Endnote
%0 Conference Paper %T Maximin Relative Improvement: Fair Learning as a Bargaining Problem %A Jiwoo Han %A Moulinath Banerjee %A Yuekai Sun %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-han26a %I PMLR %P 39539--39570 %U https://proceedings.mlr.press/v306/han26a.html %V 306 %X 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.
APA
Han, J., Banerjee, M. & Sun, Y.. (2026). Maximin Relative Improvement: Fair Learning as a Bargaining Problem. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:39539-39570 Available from https://proceedings.mlr.press/v306/han26a.html.

Related Material