  Federated learning provides an effective paradigm to jointly optimize a model
benefited from rich distributed data while protecting data privacy.
Nonetheless, the heterogeneity nature of distributed data makes it challenging
to define and ensure fairness among local agents. For instance, it is
intuitively "unfair" for agents with data of high quality to sacrifice their
performance due to other agents with low quality data. Currently popular
egalitarian and weighted equity-based fairness measures suffer from the
aforementioned pitfall. In this work, we aim to formally represent this problem
and address these fairness issues using concepts from co-operative game theory
and social choice theory. We model the task of learning a shared predictor in
the federated setting as a fair public decision making problem, and then define
the notion of core-stable fairness: Given $N$ agents, there is no subset of
agents $S$ that can benefit significantly by forming a coalition among
themselves based on their utilities $U_N$ and $U_S$ (i.e., $\frac{|S|}{N} U_S
\geq U_N$). Core-stable predictors are robust to low quality local data from
some agents, and additionally they satisfy Proportionality and
Pareto-optimality, two well sought-after fairness and efficiency notions within
social choice. We then propose an efficient federated learning protocol CoreFed
to optimize a core stable predictor. CoreFed determines a core-stable predictor
when the loss functions of the agents are convex. CoreFed also determines
approximate core-stable predictors when the loss functions are not convex, like
smooth neural networks. We further show the existence of core-stable predictors
in more general settings using Kakutani's fixed point theorem. Finally, we
empirically validate our analysis on two real-world datasets, and we show that
CoreFed achieves higher core-stability fairness than FedAvg while having
similar accuracy.
