Fair Federated Learning via the Proportional Veto Core

Previous work on fairness in federated learning introduced the notion ofcore stability, which provides utility-based fairness guarantees to any subset of participating agents. However, these guarantees require strong assumptions on agent utilities that render them impractical. To address this shortcoming, we measure the quality of output models in terms of their ordinalrankinstead of their cardinal utility, and use this insight to adapt the classical notion ofproportional veto core (PVC)from social choice theory to the federated learning setting. We prove that models that arePVC-stableexist in very general learning paradigms, even allowing non-convex model sets, as well as non-convex and non-concave loss functions. We also design Rank-Core-Fed, a distributed federated learning algorithm, to train a PVC-stable model. Finally, we demonstrate that Rank-Core-Fed outperforms baselines in terms of fairness on different datasets.