Maximin Relative Improvement: Fair Learning as a Bargaining Problem

• URL: http://arxiv.org/abs/2602.04155v1
• Date: Wed, 04 Feb 2026 02:44:56 GMT
• Title: Maximin Relative Improvement: Fair Learning as a Bargaining Problem
• Abstract summary: We propose a fundamentally different approach to interpreting group fairness as a bargaining problem among subpopulations.<n>This game-theoretic perspective reveals that existing robust optimization methods such as minimizing worst-group loss or regret correspond to classical bargaining solutions.<n>We propose relative improvement, the ratio of actual risk reduction to potential reduction from a baseline predictor, which recovers the Kalai-Smorodinsky solution.
• Score: 24.940259610524482
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  We analyze smoothed (perturbed) policies, adding controlled random perturbations to the direction used by the linear oracle.<n>Our main contribution is a generalization bound that decomposes the excess risk into perturbation bias, statistical estimation error, and optimization error.<n>We illustrate the scope of the results on applications such as vehicle scheduling, highlighting how smoothing enables both tractable training and controlled generalization.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• On the Uniform Convergence of Subdifferentials in Stochastic Optimization and Learning [1.5229257192293195]
  We investigate the uniform convergence of subdifferential mappings from empirical risk to population risk in nonsmooth, non-valued to deterministic optimization.<n>These guarantees offer new insight into the geometry of problems arising in robust statistics and related applications.
  arXiv  Detail & Related papers  (2024-05-16T17:49:46Z)
• Beyond Expectations: Learning with Stochastic Dominance Made Practical [88.06211893690964]
  dominance models risk-averse preferences for decision making with uncertain outcomes. Despite theoretically appealing, the application of dominance in machine learning has been scarce. We first generalize the dominance concept to enable feasible comparisons between any arbitrary pair of random variables. We then develop a simple and efficient approach for finding the optimal solution in terms of dominance.
  arXiv  Detail & Related papers  (2024-02-05T03:21:23Z)
• Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimization [59.758009422067]
  We consider the problem of quantifying uncertainty over expected cumulative rewards in model-based reinforcement learning. We propose a new uncertainty Bellman equation (UBE) whose solution converges to the true posterior variance over values. We introduce a general-purpose policy optimization algorithm, Q-Uncertainty Soft Actor-Critic (QU-SAC) that can be applied for either risk-seeking or risk-averse policy optimization.
  arXiv  Detail & Related papers  (2023-12-07T15:55:58Z)
• Domain Generalization without Excess Empirical Risk [83.26052467843725]
  A common approach is designing a data-driven surrogate penalty to capture generalization and minimize the empirical risk jointly with the penalty. We argue that a significant failure mode of this recipe is an excess risk due to an erroneous penalty or hardness in joint optimization. We present an approach that eliminates this problem. Instead of jointly minimizing empirical risk with the penalty, we minimize the penalty under the constraint of optimality of the empirical risk.
  arXiv  Detail & Related papers  (2023-08-30T08:46:46Z)
• Selective Regression Under Fairness Criteria [30.672082160544996]
  In some cases, the performance of minority group can decrease while we reduce the coverage. We show that such an unwanted behavior can be avoided if we can construct features satisfying the sufficiency criterion.
  arXiv  Detail & Related papers  (2021-10-28T19:05:12Z)
• Stochastic Variance Reduction for Variational Inequality Methods [19.061953585686986]
  We propose variance reduced algorithms for solving convex-concave saddle point problems, monotone variational inequalities, and monotone inclusions. Our framework applies to extragradient, forward-backward-forward, and forward-reflected-backward methods both in Euclidean and Bregman.
  arXiv  Detail & Related papers  (2021-02-16T18:39:16Z)
• Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory [11.840747467007963]
  We study problem-dependent rates that scale near-optimally with the variance, the effective loss errors, or the norms evaluated at the "best gradient hypothesis" We introduce a principled framework dubbed "uniform localized convergence" We show that our framework resolves several fundamental limitations of existing uniform convergence and localization analysis approaches.
  arXiv  Detail & Related papers  (2020-11-12T04:07:29Z)
• Variance-Reduced Splitting Schemes for Monotone Stochastic Generalized Equations [0.0]
  We consider monotone inclusion problems where the operators may be expectation-valued. A direct application of splitting schemes is complicated by the need to resolve problems with expectation-valued maps at each step. We propose an avenue for addressing uncertainty in the mapping: Variance-reduced modified forward-backward splitting scheme.
  arXiv  Detail & Related papers  (2020-08-26T02:33:27Z)
• A One-step Approach to Covariate Shift Adaptation [82.01909503235385]
  A default assumption in many machine learning scenarios is that the training and test samples are drawn from the same probability distribution. We propose a novel one-step approach that jointly learns the predictive model and the associated weights in one optimization.
  arXiv  Detail & Related papers  (2020-07-08T11:35:47Z)
• GenDICE: Generalized Offline Estimation of Stationary Values [108.17309783125398]
  We show that effective estimation can still be achieved in important applications. Our approach is based on estimating a ratio that corrects for the discrepancy between the stationary and empirical distributions. The resulting algorithm, GenDICE, is straightforward and effective.
  arXiv  Detail & Related papers  (2020-02-21T00:27:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.