Abstract
Cardinal objectives serve as intuitive targets in fair machine learning by summarizing utility (welfare) or disutility (malfare) $u$ over $g$ groups. Under standard axioms, all welfare and malfare functions are $w$-weighted $p$-power-means, i.e. $M_p(u;w) = \sqrt[p]{\sum_{i=1}^g w_i u_i^p}$, with $p \leq 1$ for welfare, or $p \geq 1$ for malfare. We show the same under weaker axioms, and also identify stronger axioms that naturally restrict $p$. It is known that power-mean malfare functions are Lipschitz continuous, and thus statistically easy to estimate or learn. We show that all power means are locally Holder continuous, i.e., $|M(u; w)-M(u’ ; w)| \leq \lambda \parallel u - u’\parallel^\alpha$ for some $\lambda$, $\alpha$,$\parallel \cdot \parallel$. In particular, $\lambda$ and $1/\alpha$ are bounded except as $p \rightarrow 0$ or $\min_i w_i \rightarrow 0$, and via this analysis we bound the sample complexity of optimizing welfare. This yields a novel concept of fair-PAC learning, wherein welfare functions are only polynomially harder to optimize than malfare functions, except when $p \approx 0$ or $\min_i w_i \approx 0$, which is exponentially harder.
Introduction
In fair machine learning, a central challenge is defining a principled objective function that aggregates the interests of diverse groups. Researchers often debate whether to minimize the loss of the worst-performing group (egalitarianism) or maximize the product of utilities (Nash Social Welfare). While economic theory provides "cardinal welfare functions" as a solution, their statistical properties in a machine learning context—specifically how much data is needed to learn them—have remained poorly understood. This work bridges social choice theory and statistical learning to address the gap between axiomatic ideals and statistical reality.
The Axiomatic Spectrum of Fairness
The paper demonstrates that under a refined set of axioms, such as Weighted Symmetry and Decomposability, fair aggregators are uniquely justified as $p$-power-means. These functions represent a spectrum where $p \leq 1$ corresponds to "welfare" (aggregating utilities) and $p \geq 1$ corresponds to "malfare" (aggregating losses).
As shown in the figure above, this spectrum includes well-known objectives like Utilitarianism ($p=1$), Nash Social Welfare ($p=0$), and Egalitarianism ($p \to \pm\infty$). The choice of axioms directly dictates the statistical complexity of the resulting objective. For instance, the "Zero Barrier" (0B) axiom, which requires welfare to be zero if any group has zero utility, forces the objective into a regime with significantly higher sample complexity.
Statistical Asymmetry: Welfare vs. Malfare
A key insight of this research is the fundamental statistical asymmetry between welfare and malfare. Malfare functions ($p \geq 1$) are generally Lipschitz continuous, meaning they are "smooth" and relatively easy to estimate from finite samples. In contrast, welfare functions ($p \leq 1$) are only Hölder continuous. Because welfare functions are highly sensitive to groups with near-zero utility, they lack the smoothness required for easy estimation.
This instability is most pronounced near the Nash Social Welfare objective ($p=0$). As $p$ approaches zero, the gradient of the power-mean function can blow up, leading to massive confidence intervals and requiring exponentially more data to achieve a stable estimate. Similarly, if a minority group has a very small weight ($w_{min} \approx 0$), the sample complexity required to give them a meaningful "voice" in the objective grows disproportionately.
Fair-PAC (FPAC) Learning
The authors formalize these findings within the Fair-PAC (FPAC) framework, an extension of the "Probably Approximately Correct" learning model. Theorem 4.4 provides explicit bounds on sample complexity ($m$):
- For utilitarian cases ($p=1$), $m$ is polynomial in $1/\epsilon$.
- For hard cases (near $p=0$), $m$ depends on $1/w_{min}$ and $1/|p|$, confirming the potential for exponential growth in data requirements.
To validate these bounds, synthetic experiments using 1-armed bandit simulations with various noise distributions (Uniform, Bernoulli, Beta) were conducted. These tests confirmed that as parameters approach critical values like $p=0$, the estimation error increases sharply, necessitating adaptive sampling strategies to manage data collection costs.
Conclusion and Future Work
This work reveals that fairness is not just a philosophical choice but a statistical one. While maximizing welfare is a noble goal, it is mathematically "harder" than minimizing malfare. Future research is needed to address the computational non-convexity of these power-mean objectives and to test these theoretical bounds on complex, real-world deep learning models in fairness-critical domains like hiring or lending.
Summary updated