# Models of fairness in federated learning

Kate Donahue<EMAIL_ADDRESS>Department of Computer Science, Cornell
University  Jon Kleinberg  Department of Computer Science, Cornell University
Department of Information Science, Cornell University

###### Abstract

In many real-world situations, data is distributed across multiple locations
and can’t be combined for training. Federated learning is a novel distributed
learning approach that allows multiple federating agents to jointly learn a
model. While this approach might reduce the error each agent experiences, it
also raises questions of fairness: to what extent can the error experienced by
one agent be significantly lower than the error experienced by another agent?
In this work, we consider two notions of fairness that each may be appropriate
in different circumstances: _egalitarian fairness_ (which aims to bound how
dissimilar error rates can be) and _proportional fairness_ (which aims to
reward players for contributing more data). For egalitarian fairness, we
obtain a tight multiplicative bound on how widely error rates can diverge
between agents federating together. For proportional fairness, we show that
sub-proportional error (relative to the number of data points contributed) is
guaranteed for any individually rational federating coalition.

##  1 Introduction

In traditional machine learning, an agent (such as a hospital, school, or
company) trains a model based on data it has locally. In many cases, the agent
may have access to a limited amount of local data, which may mean that any
model created with it will have relatively high error. However, in many real-
world scenarios, multiple agents all are trying to solve similar problems
using related local data sets. For example, consider a hospital aiming to
train a model predicting patient outcomes. Local learning would rely on the
hospital’s own data from observations of its patience. However, it may be the
case that multiple hospitals in the same area all similarly have local patient
data related to this problem. This raises the question - could it be possible
to leverage this related data to help build a better model? Federated learning
is a new and rapidly growing field ([11, 8]) that combined learned parameters
from multiple federating agents in order to train models with lower expected
error. It has also been the subject of game theoretical analysis, such as in
[2, 7, 6, 3, 4], and in the summary paper [19].

In general, federated learning methods can provide benefits to federating
agents: allowing them to produce models with lower error. However, federated
learning may itself produce additional problems, especially around fairness.
Often different agents federating with the same model will see different
levels of error, potentially as a result of differences in how much data each
agent contributed to the overall model. While this disparity might be
undesirable, in federated learning, a “fair” solution can have multiple
definitions, reflecting different values and goals of the particular
situation.

For example, consider a case with two hospitals $A$ and $B$, where $A$ with
fewer relevant data points than $B$. It might be the case that $A$ has less
data because it is a smaller hospital with fewer resources. In this case, a
reasonable fairness goal might be for the federating solution to rectify this
inequity, producing errors for $A$ and $B$ that are approximately equal. The
goal of having error rates that are the same or similar is reflected in
_egalitarian fairness_. However, a different scenario might call for a
different fairness goal. Consider the case where hospitals $A$ and $B$ have
similar access to resources, but hospital $A$ has less data because it has
devoted less effort to collecting data. In this case, a reasonable fairness
objective might be to reward player $B$ for its higher contributions. One
specific approach might be to have each agent’s error rate be inversely
proportional to the amount of data it contributes: this motivates
_proportional fairness_. While egalitarian and proportional fairness can’t be
simultaneously achieved, each definition reflects goals that could be
reasonable for different situations. In the federated learning literature,
multiple papers separately discuss notions related to egalitarian and
proportional fairness, such as [14, 10, 12, 23].

The present work:
In this work, we provide the first theoretical analysis and comparison of
egalitarian and proportional fairness. In order for this analysis to be
tractable theoretically, we build on the simplified model of federated
learning first proposed in Donahue and Kleinberg [3], whose framework we
summarize later in this work for convenience of the reader.

  * •

For egalitarian fairness, we give a _tight multiplicative bound on how
dissimilar the error rates of federating agents can be_. This bound varies
based on the number of samples the largest federating agent contributes, as
well as a property of the federating problem relating to the ratio of noise
and bias in the learning task. We show that this bound holds for a wide range
of federating methods satisfying a few straightforward properties.

  * •

For proportional fairness, we show that in general there exist federating
coalitions that could display error rates that are sub-proportional,
proportional, or super-proportional. That is, the error a federating agent
experiences, compared to the error another agent experiences, could be either
more or less than what the ratio of the size of their datasets suggests.
However, we show that _any federating coalition with super-proportional error
fails to be individually rational_ : at least one agent could achieve lower
error by leaving the federating coalition for local learning.

##  2 Model and assumptions

First, we will present the model we will use to analyze federated learning. We
say that there are $M$ total federating agents (sometimes referred to as
players). Each agent $i\in[M]$ has drawn $n_{i}$ data points, labeled by its
true labeling distribution $g(\theta_{i})$, where $\theta_{i}$ are their true
local parameters and $g(\cdot)$ is some labeling function. A player’s goal is
to learn a model $g(\hat{}\theta_{i})$ with low expected error on its own
distribution. If a player opts for local learning, then it uses its local
estimate of these parameters $\hat{}\theta_{i}$ to predict future data points.
If a set of players $C$ are federating together, we say that they are in a
_coalition_ or _cluster_ together. A _federating method_ describes how players
combine their learned parameters into federating models. For example, the most
common federating method is the weighted average method in Equation 1, though
other methods are also in use ([13]):

$\hat{}\theta_{C}=\frac{1}{\sum_{i\in C}n_{i}}\cdot\sum_{i\in
C}n_{i}\cdot\hat{}\theta_{i}$ (1)

A federating player $i$ obtains error $err_{i}(C)^{m}$, where $m$ denotes the
federating method being used. Note that in general $err_{i}(C)^{m}\neq
err_{j}(C)^{m}$: players federating in the same coalition may experience
different error rates. For example, if player $i$ has more samples than player
$j$, then $\hat{}\theta_{C}$ as calculated in Equation 1 will be weighted more
towards player $i$, meaning that player $i$ will have lower expected error
than $j$.

Because it is the most straightforward method, it is sometimes called
“vanilla” federated learning. Alternative ways of federation might involve
customizing the model for individuals, as in domain adaptation. For example,
[3] models three methods of federation: vanilla (called “uniform”), as well as
two models of domain adaptation, fine-grained and coarse-grained.

###  2.1 Fairness definitions and ethical considerations

Fairness in federated learning is an especially rich topic: naturally, no one
set of definitions is going to resolve the complex questions it raises. (For a
survey of fairness issues in federated learning and methods to address them,
refer to [17]). In this work, our goal is to theoretically evaluate two of the
most common notions of fairness in federated learning.

We adopt the terminology from Xu and Lyu [20] calling the first “egalitarian”.
Egalitarian notions of fairness roughly revolve around ensuring agents have
levels of error that are all roughly comparable. For example, Mohri et al.
[14] works to minimize the error of the worst-off player, while Du et al. [5]
considers a similar notion with an explicit fairness penalty. By contrast, Li
et al. [10] has a more flexible goal of minimizing the spread of error rates.
Abay et al. [1] analyzes multiple causes of unfairness in federated learning
and potential solutions. Other papers that consider notions related to
egalitarian fairness include [21, 22, 16, 9].

The motivation for this notion of fairness is that federating agents may
differ in how much data they have for reasons beyond their control: persistent
inequities in resources, for example. The goal of federation, in this view, is
to try and ameliorate these injustices by bringing error rates more close to
each other. We formalize this idea in Definition 1.

######  Definition 1.

A coalition $C$ satisfies $\lambda$-egalitarian fairness if for some constant
$\lambda\geq 1$,

$\frac{err_{i}(C)}{err_{j}(C)}\leq\lambda\ \forall i,j\in[M]$

By contrast, proportional notions of fairness generally focus on ensuring that
different agents are rewarded for contributing more to the overall model. For
example, Lyu et al. [12], Xu and Lyu [20] both use gradient-based methods to
detect players contributing useful model updates (as opposed to noise) and
reward them with more powerful variants of the model. Song et al. [18] takes a
similar approach with the goal of allocating profit. Zhang et al. [23]
proposes having a trusted party track the amount of effort each player is
contributing, which will then be used to reward or penalize agents with access
to different models.

Under the view of proportional fairness, the number of samples a player
contributes to the federated model is under their control, so we wish to
reward players who contribute more. In Definition 2, we formalize the idea of
proportional fairness by describing how error rates relate to the number of
samples that a player has.

######  Definition 2.

A coalition $C$ with satisfies sub-proportional error if, for all pairs of
players $i$ and $j$, with with $n_{i}\leq n_{j}$,

$err_{i}(C)\leq\frac{n_{j}}{n_{i}}\cdot err_{j}(C)\ \forall i,j\in[M]\
n_{i}\leq n_{j}$

The case where this inequality is strict is “strict sub-proportional error”.
The case where this inequality is reversed is “super-proportional error”:

$err_{i}(C)\geq\frac{n_{j}}{n_{i}}\cdot err_{j}(C)\ \forall i,j\in[M]\
n_{i}\leq n_{j}$

Note that sub-proportional error means that smaller players get _lower_ error
than proportionality would suggest, while super-proportional error means that
smaller players get _higher_ error than proportional. Either case may be
desirable under different situations: we will restrict our attention to
describing when either is possible to achieve.

###  2.2 Theoretical model of federation from Donahue and Kleinberg [3]

Federated learning has been the subject of both applied and theoretical
analysis; our focus here is on the theoretical side. In order for our
theoretical fairness analysis to be feasible, we require a model that gives
exact errors for each player, rather than bounds: these are needed in order to
be able to argue that the ratio of the errors two players experience is
bounded, for example.

We opt to use the model developed in our prior work Donahue and Kleinberg [3],
which produces the closed-form error value seen in Lemma 1 below. While we
work within this model, we emphasize that [3] asked different questions from
this paper’s focus: our prior work focused on developing the federated
learning model and analyzing the stability of federating coalitions, while our
current work analyzes optimality and Price of Anarchy. (Separately, in [4] we
similarly build on [3], but with the orthogonal goal of analyzing the
_optimality_ of federated learning: which arrangements minimize total error.)

######  Lemma 1 (Lemma 4.2, from [3]).

Consider a mean estimation task as follows: player $j$ is trying to learn its
true mean $\theta_{j}$. It has access to $n_{j}$ samples drawn i.i.d.
$Y\sim\mathcal{D}_{j}(\theta_{j},\epsilon^{2}_{j})$, a distribution with mean
$\theta_{j}$ and variance $\epsilon^{2}_{j}$. Given a population of players,
each has drawn parameters $(\theta_{j},\epsilon^{2}_{j})\sim\Theta$ from some
common distribution $\Theta$. A coalition $C$ federating together produces a
single model based on the weighted average of local means (Eq. 1). Then, the
expected mean squared error player $j$ experiences in coalition $C$ is:

$err_{j}(C)=\frac{\mu_{e}}{\sum_{i\in C}n_{i}}+\sigma^{2}\cdot\frac{\sum_{i\in
C,i\neq j}n_{i}^{2}+\left(\sum_{i\in C,i\neq
j}n_{i}\right)^{2}}{\left(\sum_{i\in C}n_{i}\right)^{2}}$ (2)

where
$\mu_{e}=\mathbb{E}_{(\theta_{i},\epsilon^{2}_{i})\sim\Theta}[\epsilon^{2}_{i}]$
(the average noise in data sampling) and $\sigma^{2}=Var(\theta_{i})$ (the
average distance between the true means of players).

Note that [3] also analyzes a linear regression game with a similar cost
function, though in this work we will restrict our attention to the mean
estimation game.

We use some of the same notion and modeling assumptions as [3]. For example,
we use $C$ to refer to a coalition of federating agents and $\Pi$ to refer to
a collection of coalitions that partitions the $M$ agents. We will use $N_{C}$
to refer to the total number of samples present in coalition $C$:
$N_{C}=\sum_{i\in C}n_{i}$. In a few lemmas we will re-use minor results
proven in [3], citing them for completeness.

Finally, it is worth emphasizing key differences between this current work and
[3]. The focus of [3] is defining a theoretical model of federated learning
and taking a game-theoretic analysis of the stability of such an arrangement.
While we use the theoretical model developed in [3], in our work we analyze
completely distinct questions: what are reasonable definitions of “fairness”
in federated learning? When are certain fairness notions guaranteed to hold?
Additionally, this paper is in some ways more general: while some key results
in [3] only allow players to have two different numbers of samples (“small” or
“large”), every result in our work holds for arbitrarily many players with
arbitrarily many different numbers of samples.

###  2.3 Research ethics and social impact

This work is primarily theoretical and involves no real data. However, it
touches on questions with multiple possible societal implications. As we
discussed previously, there are many reasonable definitions of fairness in
federated learning. For example, fairness could mean something besides error
rates, such as equality of access to opportunities or access to recourse. In
this work, we narrow our focus to two of the most commonly used and natural
definitions, but it is important to note that this by no means is the last
word on fairness in federated learning. Besides fairness, federated learning
also has privacy concerns. While federated learning involves sharing model
parameters, rather than raw data, under some circumstances it still may be
possible to learn information about the data distribution of specific players
[15]. Beyond this, users may have data control concerns: a patient may be
willing to have their data used to build a model for the hospital they went
to, but not be willing to have their data (or parameters derived from training
on their data) shared with other hospitals. Such objections, while reflecting
reasonable concerns, would make federated learning more difficult or
potentially infeasible. Finally, one core assumption of this paper is that the
problem at hand will be improved by a machine learning model with lower error.
In many situations, a different approach might be more suitable, such as an
algorithm that is more explainable or a non-machine learning solution.

##  3 Motivating example

As a motivating example, we will expand on the hospital application area
mentioned in the introduction. Consider the case where there are two hospitals
that are considering federating together in order to jointly estimate a
parameter or model of interest (for example, patient recovery time after a
procedure). Each hospital ideally wants to end up with a model with low error
on its own patient population. However, society as a whole also has an
interest that these models be _fair_. As we discussed in previous sections,
“fairness” could have multiple different definitions. In this work, we will
focus primarily on the ratio of error rates between agents that are federating
together - in this case, the ratio of errors between the two hospitals.

###  3.1 Hypothetical scenarios

In Table 2, we present a series of hypothetical scenarios for how error rates
between the two hospitals could differ. We will assume one hospital
contributes less data (is “small”) and one contributes more data (is “large”).
Note that “small” and “large” refers solely to how many data points each
hospital contributes to the federating model. The “large” hospital may
actually serve fewer patients (and vice versa), depending on their data
collection practices. We use $err_{s}(\\{n_{s},n_{\ell}\\})$ to refer to the
error the small hospital experiences when federating with the large hospital
(and $err_{l}(\\{n_{s},n_{\ell}\\})$ to refer to the error the large hospital
experiences).

Each row in Table 2 contains a hypothetical scenario, which allows us to
illustrate potential fairness concerns. In the first row, we consider the case
where both the small and large hospitals, when federating together, have
identical error, leading to an error ratio of 1. This scenario could be
desirable under egalitarian fairness, but would be less desirable under
proportional fairness, since it wouldn’t reward the larger hospital for having
contributed more data. The second row gives a scenario where the small
hospital has even lower error than the large hospital, when they are
federating together. This might satisfy some strict notions of egalitarian
fairness (especially if the goal is to attempt to compensate for historical
and/or continuing injustices). However, this situation will certainly not
satisfy any notions of proportional fairness, given that the large hospital
appears to be penalized for having contributed more data.

In row 3, we see a scenario where the large hospital has slightly lower error
than the small hospital. Specifically, the error ratio is 3 (the small
hospital has error that is 3 times as high). In row 4, we see a case where the
large hospital has error that is much lower, leading to an error ratio of 15.
Clearly, under egalitarian fairness, scenario 4 would be much worse than
scenario 3. For proportional fairness, which is preferred depends on the
relative sizes of the small and large hospitals: exactly how many data points
they contribute. For simplicity, we will assume the small hospital contributes
8 data points and the large hospital contributes 20, for a ratio of 3.33. In
this case, scenario 3 gives an error ratio that is closer to the ratio of data
contributed, and would likely be preferred under proportional fairness as
well.

Scenario | $err_{s}(\\{n_{s},n_{\ell}\\})$ | $err_{l}(\\{n_{s},n_{\ell}\\})$ | $\frac{err_{s}(\\{n_{s},n_{\ell}\\})}{err_{l}(\\{n_{s},n_{\ell}\\})}$
---|---|---|---
1: Equal error | 1.5 | 1.5 | 1
2: Small player has slightly lower error | 1 | 1.5 | 0.67
3: Large player has slightly lower error | 1.5 | 0.5 | 3
4: Large player has much lower error | 1.5 | 0.1 | 15

Table 1:  A series of hypothetical error rates for two federating players, one
_small_ , one _large_ in the number of samples they contribute. The first
column gives the error rates for the small player, the second column gives the
error rates for the large player, and the third column gives the error ratio
for the two players.

| $err_{s}(\\{n_{s},n_{\ell}\\})$ | $err_{l}(\\{n_{s},n_{\ell}\\})$ | $\frac{err_{s}(\\{n_{s},n_{\ell}\\})}{err_{l}(\\{n_{s},n_{\ell}\\})}$ | $2c+1$ | $\frac{n_{\ell}}{n_{s}}$
---|---|---|---|---|---
$n_{\ell}=20$ | 1.57 | 0.491 | 3.19 | 5 | 3.33
$n_{\ell}=30$ | 1.67 | 0.333 | 5 | 7 | 5
$n_{\ell}=40$ | 1.73 | 0.251 | 6.89 | 9 | 6.67

Table 2:  The actual error rates experienced by a pair of federating agents,
where $n_{s}=6$ samples and $n_{\ell}$ varies. The errors are derived using
Lemma 1 with parameters $\mu_{e}=10,\sigma^{2}=1$. The first two columns
display the error rates experienced by both players, while the third displays
the ratio of their errors. The fourth column gives a egalitarian fairness
bound derived in Theorem 2 and the fifth column displays the ratio of the
number of samples provided by each player .

###  3.2 Actual scenarios

Throughout the work of this paper, we will show that, in a variety of common
federation methods, _the typical outcome looks like Scenario 3: the larger
agent gets lower error than the smaller player, but the error ratio is upper
bounded_.

Table 2 gives different scenarios for error rates, but this time with values
calculated from an actual model of federated learning (as compared with Table
2, where the values were purely hypothetical). Each of the error rates are
calculated according to vanilla federation from Lemma 1 (as derived from [3]).
In this example, we fix the noise-bias ratio (as defined in Lemma 1) to be
$\frac{\mu_{e}}{\sigma^{2}}=10$. The small agent again contributes 6 data
points, but here we allow the number of data points contributed by the large
agent to vary from 20 to 30 to 40.

In Section 4, we explore egalitarian fairness and show that the error ratio
can be upper and lower bounded. Specifically, we show that it is upper bounded
by $2\cdot c+1$, where $c=\frac{\mu_{e}}{\sigma^{2}}$ (the noise-bias ratio).
We also show that this bound is tight: we can create scenarios that get
arbitrarily close to this upper bound of $2\cdot c+1$. Additionally, we show
that the error ratio must be at least 1 (the small player must get error that
is at least as high as the large player). In Table 2, these results are
illustrated. The third column gives the ratio of errors. Note that in all
three rows in Table 2, the large agent experiences strictly lower error than
the small agent, so this ratio is strictly greater than 1. The fourth column
gives the $2\cdot c+1$ upper bound, which for every entry is larger than the
error ratio, which we prove in Section 4 must hold.

Finally, in Section 5, we consider proportional fairness. The fifth column of
Table 2 gives the ratio of the sizes of each of the two agents. In exactly
proportional fairness, the ratio of errors (3rd column) would exactly match
the ratio of sizes (5th column). In this table, the middle row (when the large
agent has 30 samples) exactly satisfies proportional fairness. The first row
(where the large agent has 20 samples) has sub-proportional error: the small
agent has lower error than proportionality would suggest (because the error
ratio is lower than the ratio of sizes). In the third row (where the large
agent has 40 samples), we see super-proportional error: the small player
experiences higher error than what proportionality would suggest (because the
error ratio is higher than the ratio of sizes). This table illustrates that
federating agents could experience proportional, sub-proportional, or super-
proportional error rates. However, in Section 5, we will prove that any
federating coalition with super-proportional error must fail to be
individually rational: at least one agent would reduce its error by switching
to local learning (building a model with only its own data). In this case,
Lemma 1 gives that the large player would experience error of
$\frac{\mu_{e}}{n_{s}}=\frac{10}{40}=0.25$ in local learning, which is
strictly lower than the error of 0.251 it experiences in federated learning.

##  4 Egalitarian fairness

In this section, we will analyze _egalitarian fairness_ , where a typical goal
is to ensure that all players have similar levels of error. This may be
motivated by the fact that players may differ in their circumstances
(differing amounts of data) for reasons out of their control. For example,
imagine a low-resource hospital that is federating with a high-resource
hospital. The low-resource hospital may have access to less local data for
historical and/or continuing reasons of discrimination and unequal access to
technology and other resources. This motivation would suggest that federated
learning should seek to close the gap the low resource and high resource
hospital, making their error as close to equal as possible. In some cases, it
may even be desirable for the low-resource (small) hospital to have lower
error than the high-resource hospital, potentially as a way to begin to
compensate for its lack of resources. In this section, we give theoretical
bounds for what types of egalitarian fairness levels can be obtained.

First, we begin with the simplest and most commonly-studied federation method:
vanilla federation, where parameters are calculated as the weighted average,
as in Equation 1. Theorem 1 shows that, for this federation method, smaller
players always get higher error, but that there exists a tight multiplicative
bound for egalitarian fairness (the error ratio between small and large
players is upper bounded).

######  Theorem 1.

Vanilla federation satisfies the following three properties:

  * •

For any two players federating in the same coalition $C$ such that $n_{s}\leq
n_{\ell}$, the smaller player always experiences error that is at least as
high as the larger player (strictly higher if $n_{s}<n_{\ell}$).

  * •

Any federating coalition such that the largest player has no more than
$c\cdot\frac{\mu_{e}}{\sigma^{2}}$ samples satisfies $2c+1$-egalitarian
fairness.

  * •

This bound is tight (up to an additive factor of $\epsilon$).

We won’t directly give a proof of Theorem 1, but instead, we will show that it
is a consequence of a more general result presented in Theorem 2. This theorem
shows that the same egalitarian fairness bounds hold for any _modular
function_ , where Definition 3, below, gives a formal definition of what this
means.

######  Theorem 2.

Any modular federating method (as defined in Definition 3) has the following
three egalitarian fairness properties:

  * •

For any two players federating in the same coalition $C$ such that $n_{s}\leq
n_{\ell}$, the smaller player always experiences error that is at least as
high as the larger player (strictly higher if $n_{s}<n_{\ell}$).

  * •

Any federating coalition such that the largest player has no more than
$c\cdot\frac{\mu_{e}}{\sigma^{2}}$ samples satisfies $2c+1$-egalitarian
fairness.

  * •

This bound is tight (up to an additive factor of $\epsilon$).

######  Definition 3.

Consider any coalition $C$ with players $s,\ell\in C$ such that $n_{s}\leq
n_{\ell}$. Then, a federating method is called modular if it satisfies the
following five properties:

Property 1: The large player always has lower error than the small player,
with the error being strictly lower if $n_{s}<n_{\ell}$ (the large player is
strictly larger).

$\frac{err_{s}(C)}{err_{l}(C)}\geq 1$

Property 2: The worst-case situation for the error ratio (the ratio of the
small player’s error to the large player’s error) is always in the two-player
case. That is,

$\frac{err_{s}\left(C\right)}{err_{l}\left(C\right)}\leq\frac{err_{s}\left(\\{n_{s},n_{\ell}\\}\right)}{err_{l}\left(\\{n_{s},n_{\ell}\right)\\}}$

Property 3: The error ratio increases as the large player gets more samples:
the small player’s error either increases or else decreases more slowly than
the large player’s error decreases. That is,

$\frac{\partial}{\partial
n_{\ell}}\frac{err_{s}\left(\\{n_{s},n_{\ell}\\}\right)}{err_{l}\left(\\{n_{s},n_{\ell}\right)\\}}\geq
0$

Property 4: The error ratio decreases as the small player gets more samples:
the large player’s error either increases or else decreases more slowly than
the small player’s error decreases. That is,

$\frac{\partial}{\partial
n_{s}}\frac{err_{s}\left(\\{n_{s},n_{\ell}\\}\right)}{err_{l}\left(\\{n_{s},n_{\ell}\right)\\}}\leq
0$

Property 5: As $\frac{n_{s}}{n_{\ell}}\rightarrow 0$ (the large player has
many more samples than the small player), the error ratio converges to the
following fraction:

$\lim_{\frac{n_{s}}{n_{\ell}}\rightarrow
0}\frac{err_{s}\left(\\{n_{s},n_{\ell}\right)\\}}{err_{l}\left(\\{n_{s},n_{\ell}\right)\\}}=\frac{\frac{\mu_{e}}{n_{\ell}}+2\sigma^{2}}{\frac{\mu_{e}}{n_{\ell}}}$

First, it may be useful to discuss the properties in Definition 3. Property 1
is simply stating that, for any pair of players both federating in the same
coalition, the smaller of the two always has higher error. The remaining four
properties contribute to the upper bound (and showing that this bound is
tight). First, Property 2 states that the error ratio between any two players
is highest when they are federating in a two-player coalition (without any
other players). This property is especially helpful because the two-player
coalition is much simpler to analyze. Properties 3 and 4 consider this two-
player coalition, showing that the error ratio is highest when the large
player has many samples and the small player has very few. Finally, Property 5
describes the limit of the error ratio in the case where the large player has
many more samples than the small player, stating that it must go to a fixed
ratio depending on the noise-bias ratio, as well as the number of samples the
large player has.

Given these properties, it becomes straightforward to prove Theorem 2:

###### Proof of Theorem 2.

Property 1 automatically satisfies the first property in Theorem 2.

Proving the $2c+1$ bound is given by applying the four properties:

$\frac{err_{s}\left(C\right)}{err_{l}\left(C\right)}\leq\frac{err_{s}\left(\\{n_{s},n_{\ell}\\}\right)}{err_{l}\left(\\{n_{s},n_{\ell}\right)\\}}\leq\frac{err_{s}\left(\\{n_{s},c\cdot\frac{\mu_{e}}{\sigma^{2}}\\}\right)}{err_{l}\left(\\{n_{s},c\cdot\frac{\mu_{e}}{\sigma^{2}}\\}\right)}$
$\leq\frac{\frac{\mu_{e}}{n_{\ell}}+2\sigma^{2}}{\frac{\mu_{e}}{n_{\ell}}}\leq\frac{\frac{\mu_{e}}{n_{\ell}}+2\sigma^{2}}{\frac{\mu_{e}}{n_{\ell}}}\Bigg{|}_{n_{\ell}=c\frac{\mu_{e}}{\sigma^{2}}}=\frac{\frac{\sigma^{2}}{c}+2\sigma^{2}}{\frac{\sigma^{2}}{c}}=2c+1$

Next, we will show that the bound is tight. Our goal is to show that, for all
$\epsilon>0$, there exists some set of parameters $n_{s}\geq 1,n_{\ell}\leq
c\cdot\frac{\mu_{e}}{\sigma^{2}},\mu_{e},\sigma^{2}\geq 0$ such that

$\frac{err_{s}(\\{n_{s},n_{\ell}\\})}{err_{l}(\\{n_{s},n_{\ell}\\})}\geq
2c+1-\epsilon$

The $\epsilon,\delta$ version of Property 4 can be written as: for all
$\epsilon>0$, there exists a $\delta>0$ such that

$\frac{n_{s}}{n_{\ell}}<\delta\quad\Rightarrow\quad\frac{\frac{\mu_{e}}{n_{\ell}}+2\sigma^{2}}{\frac{\mu_{e}}{n_{\ell}}}-\frac{err_{s}\left(\\{n_{s},n_{\ell}\right)\\}}{err_{l}\left(\\{n_{s},n_{\ell}\right)\\}}<\epsilon$

Setting $n_{s}=1,n_{\ell}=c\cdot\frac{\mu_{e}}{\sigma^{2}}$ gives that
Property 4 becomes:

$\frac{\sigma^{2}}{c\cdot\mu_{e}}<\delta\quad\Rightarrow\quad
2c+1-\frac{err_{s}\left(\\{n_{s},n_{\ell}\right)\\}}{err_{l}\left(\\{n_{s},n_{\ell}\right)\\}}<\epsilon$
$\frac{\sigma^{2}}{c\cdot\mu_{e}}<\delta\quad\Rightarrow\quad\frac{err_{s}\left(\\{n_{s},n_{\ell}\right)\\}}{err_{l}\left(\\{n_{s},n_{\ell}\right)\\}}-\epsilon>2c+1-\epsilon$

Because $\sigma^{2},\mu_{e}$ are free parameters, we can set
$\sigma^{2}=1,\mu_{e}>\frac{1}{c\cdot\delta}$ in order to satisfy the
precondition. ∎

Finally, we will show that there exist multiple federating methods that are
modular. Specifically, Lemma 2 shows that uniform federation is modular and
Lemma 3 shows that fine-grained federation is modular. Proofs for both are
given in Appendix A.

######  Lemma 2.

Uniform federation is modular.

######  Lemma 3.

Fine-grained federation is modular.

These results, taken together, show that, while small players must get higher
error than larger players in the same federation, the error that small players
experience is upper bounded. Specifically, this upper bound is a multiple of
the error that the larger player experiences, and depends on the size of the
larger player, as a function of the noise-bias ratio. Because this bound is
tight, we know that no lower bound is possible.

##  5 Proportional fairness

Next, we consider _proportional fairness_ , which revolves around the idea
that players who contribute more data should be rewarded with lower error
rates. This notion relies on the view that players do have control over how
much data they obtain. For example, imagine again two hospitals, this time
with comparable levels of resources, but one of them has devoted a
substantially larger share of its annual budget towards collecting high-
quality local data. As a result, it has substantially more local data it can
use for training. A federating coalition that gives both hospitals roughly
similar error rates might be seen as failing to recognize and reward that
hospital’s extraordinary efforts towards data collection.

First, Lemma 4 shows empirically that there exist situations where a
federating coalition could have proportional, sub-, or super-proportional
error rates.

######  Lemma 4.

There exist cases where a coalition using uniform federation satisfies
proportional, strict sub-proportional, and strict sup-proportional error.

| $err_{s}(\\{n_{s},n_{\ell}\\})$ | $err_{l}(\\{n_{s},n_{\ell}\\})$ | $\frac{err_{s}(\\{n_{s},n_{\ell}\\})}{err_{l}(\\{n_{s},n_{\ell}\\})}$ | $2c+1$ | $\frac{n_{\ell}}{n_{s}}$
---|---|---|---|---|---
$n_{\ell}=20$ | 1.57 | 0.491 | 3.19 | 5 | 3.33
$n_{\ell}=30$ | 1.67 | 0.333 | 5 | 7 | 5
$n_{\ell}=40$ | 1.73 | 0.251 | 6.89 | 9 | 6.67
Table 3:  The actual error rates experienced by a pair of federating agents,
where $n_{s}=6$ samples and $n_{\ell}$ varies. The errors are derived using
Lemma 1 with parameters $\mu_{e}=10,\sigma^{2}=1$. The first two columns
display the error rates experienced by both players, while the third displays
the ratio of their errors. The fourth column gives a egalitarian fairness
bound derived in Theorem 2 and the fifth column displays the ratio of the
number of samples provided by each player .

###### Proof.

This proof is constructive: we give an explicit example of such situations.
Recall that in Section 3, the “Actual scenarios” section already gave such an
example. This is reproduced for convenience here as Table 3. Throughout, we
use the error form given in Lemma 1 with $\mu_{e}=10,\sigma^{2}=1$. We will
consider the case where there are exactly two players: $n_{s}=6$, and
$n_{\ell}$ with a varying number of samples.

The first row gives the error that the small and large players experience with
$n_{\ell}=20$. Note that the ratio of their errors (given in the third column)
is strictly less than the (inverse) ratio of their sizes (given in the fifth
column). This is an example of sub-proportional error: the small player gets
lower error than proportional scaling with respect to their sizes would
suggest. The second row gives the error that the players experience with
$n_{\ell}=30$. Here, the ratio of their errors exactly matches the ratio of
their sizes: this is a case of exact proportionality. Finally, the third row
gives the error the players experience when $n_{\ell}=40$. Here the ratio of
their errors is strictly greater than the ratio of their sizes: this
represents super-proportionality.

In later analyses, we will show that all arrangements with super-proportional
error fail to be individually rational: at least one federating agent would
prefer local learning. For the example with $n_{\ell}=40$, the error form from
Lemma 1 gives that the large player would obtain error of $0.25$ with local
learning. This is strictly less than its federating error of $0.251$, so it is
incentivized to leave the federating coalition.

∎

Table 3 also illustrates the bound derived in Theorem 2. Given that the
error/bias ratio here is $\frac{\mu_{e}}{\sigma^{2}}=\frac{10}{1}=10$, the
$2c+1$ bound scales with the size of the largest player, in multiples of 10.
The bound in the fifth column is always strictly greater than the ratio in the
third column, illustrating the result from Theorem 2.

The result of Lemma 4 is to show that, in general, a federating coalition
might experience error that is sub or super-proportional. Next, Theorem 3
gives conditions for when sub-proportionality is guaranteed: specifically,
whenever the coalition is individually rational. A coalition $C$ is
_individually rational_ if each player in the coalition prefers being in $C$
to doing local learning.

######  Theorem 3.

Any individually rational coalition using vanilla federation satisfies sub-
proportionality of errors.

As mentioned previously, sub-proportionality of errors means that smaller
players (contributing fewer samples to the federating model) experience error
that is _lower_ than proportionality would suggest. This may or may not be
desirable, depending on the federating situation. The full proof of Theorem 3
is given in Appendix A, but we include a proof sketch below.

###### Proof Sketch.

We will show this result by proving the contrapositive: if sub-proportionality
of errors is violated, then at least one player wishes to leave that coalition
for local learning (so individual rationality is violated).

In our analysis, we will consider two players $n_{s}<n_{\ell}$, though the
players could be arbitrarily situated with respect to
$\frac{\mu_{e}}{\sigma^{2}}$. We will assume that all of the players are
federating together in coalition $A$. For notational convenience, we will
write the federating coalition $A$ of interest as $A=C\cup\\{n_{\ell}\\}$, so
$C$ refers to all players except $n_{\ell}$.

The case where sub-proportionality fails to hold is:

$err_{S}(A)\cdot n_{s}\geq err_{L}(A)\cdot n_{\ell}$

Note that the sign of the inequality is flipped, as compared to sub-
proportionality.

The full proof, in Appendix A, shows that this inequality can be rewritten as:

$\frac{-2\sigma^{2}\cdot N_{C}+\frac{\mu_{e}}{n_{s}}\cdot
N_{C}+\frac{\sigma^{2}}{n_{s}}\cdot\left(\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}\right)}{2\sigma^{2}-\frac{\mu_{e}}{n_{s}}}\leq n_{\ell}$
(3)

Equation 3 gives a lower bound on how many samples the large player has to
have before sub-proportionality is violated. Next, the proof obtains a similar
lower bound for how many samples the large player would need before it would
prefer to defect: we will show this lower bound is _lower_ than Equation 3
above.

The case when the large player wishes to defect from $A$ to local learning (or
is ambivalent about defecting) is when:

$err_{L}(\pi_{l})\leq err_{L}(A)$

The full version of the proof shows that this can be simplified to:

$\frac{-2\sigma^{2}\cdot N_{C}+\frac{\mu_{e}}{n_{s}}\cdot
N_{C}+\frac{\sigma^{2}}{n_{s}}\cdot\left(\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}\right)}{2\sigma^{2}-\frac{\mu_{e}}{n_{s}}}\leq n_{\ell}$
(4)

The full proof concludes by showing that the bound in Equation 4 is lower than
the bound in Equation 3: any situation where the $n_{\ell}$ term is large
enough so that sub-proportionality is violated, we know that the large player
already wishes to leave. ∎

Overall, the bound in Theorem 3 is different from the results on egalitarian
fairness in Section 4. For egalitarian fairness, we obtained results that hold
for any pair of players federating together. In this section, for proportional
fairness, we obtain a guarantee that holds whenever a federating coalition is
individually rational: whenever all federating players obtain lower error than
they would in local learning. The result in Theorem 3 could be useful if
federating is truly voluntary: then, any federating coalition where smaller
players experience super-proportional could never exist, because it would
unravel into local learning. However, this result could still be useful even
if federating isn’t something individual players could opt out of. Theorem 3
shows that any federating coalition with super-proportional error is one that
also has the problem that some players receive higher error than they would in
local learning - which indicates a broader failure of federation, which may
prompt any federating organizer to change their federating groups or
coalitions.

##  6 Discussion

In this work, we have used a theoretical model to analyze the fairness
properties of federated learning. We formalized two notions of fairness
already under analysis in federated learning research and gave conditions when
those fairness properties are or are not satisfied. For egalitarian fairness,
we gave a tight multiplicative bound on the gap in error rates between any two
federating players. For proportional fairness, we showed that any individually
rational federating coalition must satisfy sub-proportional fairness.

Future research could consider questions in two directions. First: which other
notions of fairness might be relevant? It might be the case that an additive
version of egalitarian fairness would be more appropriate for certain
situations, for example, or a version of proportional fairness based on some
metric related to the quality of data points, rather than how their quantity.
Secondly, which fairness properties might other methods federations display?
While we have analyzed two federation methods (vanilla and fine-grained), it
could be fruitful to analyze other methods to determine how well they achieve
certain fairness results.

## Acknowledgments

This work was supported in part by a Simons Investigator Award, a Vannevar
Bush Faculty Fellowship, MURI grant W911NF-19-0217, AFOSR grant
FA9550-19-1-0183, ARO grant W911NF19-1-0057, a Simons Collaboration grant, a
grant from the MacArthur Foundation, and NSF grant DGE-1650441. We are
grateful to the AI, Policy, and Practice working group at Cornell for
invaluable discussions.

## References

  * Abay et al. [2020] A. Abay, Y. Zhou, N. Baracaldo, S. Rajamoni, E. Chuba, and H. Ludwig.  Mitigating bias in federated learning, 2020.
  * Blum et al. [2021] A. Blum, N. Haghtalab, R. L. Phillips, and H. Shao.  One for one, or all for all: Equilibria and optimality of collaboration in federated learning.  _arXiv preprint arXiv:2103.03228_ , 2021.
  * Donahue and Kleinberg [2021a] K. Donahue and J. Kleinberg.  Model-sharing games: Analyzing federated learning under voluntary participation.  _AAAI 2021_ , 2021a.  URL https://arxiv.org/abs/2010.00753.
  * Donahue and Kleinberg [2021b] K. Donahue and J. Kleinberg.  Optimality and stability in federated learning: A game-theoretic approach.  In _Advances in Neural Information Processing Systems_ , 2021b.  URL https://proceedings.neurips.cc/paper/2021/hash/09a5e2a11bea20817477e0b1dfe2cc21-Abstract.html.
  * Du et al. [2020] W. Du, D. Xu, X. Wu, and H. Tong.  Fairness-aware agnostic federated learning.  _ArXiv_ , abs/2010.05057, 2020.
  * Grimberg et al. [2021] F. Grimberg, M.-A. Hartley, S. P. Karimireddy, and M. Jaggi.  Optimal model averaging: Towards personalized collaborative learning.  _arXiv preprint arXiv:2110.12946_ , 2021.
  * Hasan [2021] C. Hasan.  Incentive mechanism design for federated learning: Hedonic game approach, 2021.
  * Kairouz et al. [2019] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, R. G. L. D’Oliveira, S. E. Rouayheb, D. Evans, J. Gardner, Z. Garrett, A. Gascón, B. Ghazi, P. B. Gibbons, M. Gruteser, Z. Harchaoui, C. He, L. He, Z. Huo, B. Hutchinson, J. Hsu, M. Jaggi, T. Javidi, G. Joshi, M. Khodak, J. Konečný, A. Korolova, F. Koushanfar, S. Koyejo, T. Lepoint, Y. Liu, P. Mittal, M. Mohri, R. Nock, A. Özgür, R. Pagh, M. Raykova, H. Qi, D. Ramage, R. Raskar, D. Song, W. Song, S. U. Stich, Z. Sun, A. T. Suresh, F. Tramèr, P. Vepakomma, J. Wang, L. Xiong, Z. Xu, Q. Yang, F. X. Yu, H. Yu, and S. Zhao.  Advances and open problems in federated learning, 2019.
  * Kanaparthy et al. [2021] S. Kanaparthy, M. Padala, S. Damle, and S. Gujar.  Fair federated learning for heterogeneous face data.  _arXiv preprint arXiv:2109.02351_ , 2021.
  * Li et al. [2019] T. Li, M. Sanjabi, A. Beirami, and V. Smith.  Fair resource allocation in federated learning, 2019.
  * Li et al. [2020] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith.  Federated learning: Challenges, methods, and future directions.  _IEEE Signal Processing Magazine_ , 37(3):50–60, May 2020.  ISSN 1558-0792.  doi: 10.1109/msp.2020.2975749.  URL http://dx.doi.org/10.1109/MSP.2020.2975749.
  * Lyu et al. [2020] L. Lyu, X. Xu, and Q. Wang.  Collaborative fairness in federated learning.  _ArXiv_ , abs/2008.12161, 2020.
  * McMahan et al. [2016] H. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas.  Communication-efficient learning of deep networks from decentralized data, 2016.
  * Mohri et al. [2019] M. Mohri, G. Sivek, and A. T. Suresh.  Agnostic federated learning, 2019.
  * Mothukuri et al. [2021] V. Mothukuri, R. M. Parizi, S. Pouriyeh, Y. Huang, A. Dehghantanha, and G. Srivastava.  A survey on security and privacy of federated learning.  _Future Generation Computer Systems_ , 115:619–640, 2021\.
  * Papadaki et al. [2021] A. Papadaki, N. Martinez, M. Bertran, G. Sapiro, and M. Rodrigues.  Federating for learning group fair models.  _arXiv preprint arXiv:2110.01999_ , 2021.
  * Shi et al. [2021] Y. Shi, H. Yu, and C. Leung.  A survey of fairness-aware federated learning.  _arXiv preprint arXiv:2111.01872_ , 2021.
  * Song et al. [2019] T. Song, Y. Tong, and S. Wei.  Profit allocation for federated learning.  _2019 IEEE International Conference on Big Data (Big Data)_ , pages 2577–2586, 2019.
  * Tu et al. [2021] X. Tu, K. Zhu, N. C. Luong, D. Niyato, Y. Zhang, and J. Li.  Incentive mechanisms for federated learning: From economic and game theoretic perspective.  _arXiv preprint arXiv:2111.11850_ , 2021.
  * Xu and Lyu [2020] X. Xu and L. Lyu.  Towards building a robust and fair federated learning system.  _ArXiv_ , abs/2011.10464, 2020.
  * Zeng et al. [2021] Y. Zeng, H. Chen, and K. Lee.  Improving fairness via federated learning.  _arXiv preprint arXiv:2110.15545_ , 2021.
  * Zhang et al. [2021] F. Zhang, K. Kuang, Y. Liu, C. Wu, F. Wu, J. Lu, Y. Shao, and J. Xiao.  Unified group fairness on federated learning.  _arXiv preprint arXiv:2111.04986_ , 2021.
  * Zhang et al. [2020] J. Zhang, C. Li, A. Robles-Kelly, and M. Kankanhalli.  Hierarchically fair federated learning.  _ArXiv_ , abs/2004.10386, 2020.

##  Appendix A Proofs

See 2

###### Proof.

In this proof, we will denote the uniform federation error by $err^{u}$.
Because Definition 3 has five components, this proof will have five sections.
Property 1:
For the first property, we wish to show that (for any federating coalition
$C$), the large player always has strictly lower error than the small player,
or:

$\frac{err_{s}(C)}{err_{l}(C)}\leq 1\quad\Leftrightarrow\quad err_{s}(C)\geq
err_{l}(C)$

Using the form of error found in Lemma 1 (Equation 2), we can rewrite this as:

$\frac{\mu_{e}}{\sum_{i\in C}n_{i}}+\sigma^{2}\cdot\frac{\sum_{i\in
C}n_{i}^{2}-n_{s}^{2}+\left(\sum_{i\in
C}n_{i}-n_{s}\right)^{2}}{\left(\sum_{i\in
C}n_{i}\right)^{2}}\geq\frac{\mu_{e}}{\sum_{i\in
C}n_{i}}+\sigma^{2}\cdot\frac{\sum_{i\in
C}n_{i}^{2}-n_{\ell}^{2}+\left(\sum_{i\in
C}n_{i}-n_{\ell}\right)^{2}}{\left(\sum_{i\in C}n_{i}\right)^{2}}$

Cancelling common terms:

$\displaystyle\sum_{i\in C}n_{i}^{2}-n_{s}^{2}+\left(\sum_{i\in
C}n_{i}-n_{s}\right)^{2}$ $\displaystyle\geq\sum_{i\in
C}n_{i}^{2}-n_{\ell}^{2}+\left(\sum_{i\in C}n_{i}-n_{\ell}\right)^{2}$
$\displaystyle-n_{s}^{2}+\left(\sum_{i\in C}n_{i}\right)^{2}-2\cdot
n_{s}\cdot\left(\sum_{i\in C}n_{i}\right)+n_{s}^{2}$ $\displaystyle\geq-
n_{\ell}^{2}+\left(\sum_{i\in C}n_{i}\right)^{2}-2\cdot
n_{\ell}\cdot\left(\sum_{i\in C}n_{i}\right)+n_{\ell}^{2}$
$\displaystyle-2\cdot n_{s}\cdot\left(\sum_{i\in C}n_{i}\right)$
$\displaystyle\geq-2\cdot n_{\ell}\cdot\left(\sum_{i\in C}n_{i}\right)$
$\displaystyle n_{s}$ $\displaystyle\leq n_{\ell}$

This means that the small player has higher error whenever it has fewer
samples than the large player- and strictly higher error whenever it has
strictly fewer samples.
Property 2:
For the seconnd property, we wish to show that the worst case ratio of errors
occurs in the two-player case. That is,

$\frac{err_{s}^{u}\left(C\right)}{err_{l}^{u}\left(C\right)}\leq\frac{err_{s}^{u}\left(\\{n_{s},n_{\ell}\\}\right)}{err_{l}^{u}\left(\\{n_{s},n_{\ell}\right)\\}}$

In order to prove this, we’ll show something stronger. Take any player $k$
(with $k\neq s,\l$). Then, we will show that that the derivative of the ratio
with respect to the size of player $k$ ($n_{k}$) is always negative:

$\frac{\partial}{\partial
n_{k}}\frac{err_{s}^{u}\left(C\right)}{err_{l}^{u}\left(C\right)}<0$

For uniform federation, we know that

$\lim_{n_{k}\rightarrow 0}err_{s}^{u}(C)=err_{s}^{u}(C\setminus\\{n_{k}\\})$

and similarly for the large player. Then, we can convert $C$ into
$\\{n_{s},n_{\ell}\\}$ by sending the size of every other player to 0: by the
result we are trying to prove, this will only ever increase the ratio of their
errors.

Next, we will start the proof.

$\frac{\partial}{\partial
n_{k}}\frac{err_{s}^{u}\left(C\right)}{err_{l}^{u}\left(C\right)}=\frac{err_{s}^{u}(C)^{\prime}\cdot
err_{l}^{u}(C)-err_{s}^{u}(C)\cdot
err_{l}^{u}(C)^{\prime}}{(err_{l}^{u}(C))^{2}}$

This is negative whenever:

$err_{s}^{u}\left(C\right)^{\prime}\cdot
err_{l}^{u}\left(C\right)<err_{s}^{u}\left(C\right)\cdot
err_{l}^{u}\left(C\right)^{\prime}$
$\frac{err_{s}^{u}\left(C\right)^{\prime}}{err_{s}^{u}\left(C\right)}<\frac{err_{l}^{u}\left(C\right)^{\prime}}{err_{l}^{u}\left(C\right)}$

To show this result, we will calculate the lefthand side (ratio relating to
the small player’s error) and then show that it is less than the equivalent
ratio for the large player. The error of the small player can be written:

$\frac{\mu_{e}}{N}+\sigma^{2}\frac{\sum_{i\in C}n_{i}^{2}+N^{2}-2N\cdot
n_{s}}{N^{2}}$

The derivative with respect to $n_{k}$ is:

$-\frac{\mu_{e}}{N^{2}}+2\cdot\sigma^{2}\frac{(n_{k}+N-n_{s})\cdot
N-(\sum_{i\in C}n_{i}^{2}+N^{2}-2N\cdot n_{s})}{N^{3}}$ $=\frac{-\mu_{e}\cdot
N+2\cdot\sigma^{2}\cdot\left((n_{k}+N-n_{s})\cdot N-(\sum_{i\in
C}n_{i}^{2}+N^{2}-2N\cdot n_{s})\right)}{N^{3}}$

The term we’re interested in is the ratio of the derivative of the small
player’s error (which we just calculated) to the error of the small player.
Note that the error itself can be written as:

$\frac{\mu_{e}\cdot N+\sigma^{2}\left(\sum_{i\in C}n_{i}^{2}+N^{2}-2N\cdot
n_{s}\right)}{N^{2}}$

So the ratio of the derivative to the overall error is:

$\frac{1}{N}\cdot\frac{-\mu_{e}\cdot
N+2\cdot\sigma^{2}\cdot\left((n_{k}+N-n_{s})\cdot N-(\sum_{i\in
C}n_{i}^{2}+N^{2}-2N\cdot n_{s})\right)}{\mu_{e}\cdot
N+\sigma^{2}\left(\sum_{i\in C}n_{i}^{2}+N^{2}-2N\cdot n_{s}\right)}$

What we would like to show is that the above term is less than the analogous
term for the $n_{\ell}$ variant, which can be symmetrically written as:

$\frac{1}{N}\cdot\frac{-\mu_{e}\cdot
N+2\cdot\sigma^{2}\cdot\left((n_{k}+N-n_{\ell})\cdot N-(\sum_{i\in
C}n_{i}^{2}+N^{2}-2N\cdot n_{\ell})\right)}{\mu_{e}\cdot
N+\sigma^{2}\left(\sum_{i\in C}n_{i}^{2}+N^{2}-2N\cdot n_{\ell}\right)}$

This is equivalent to proving:

$\frac{B+2\sigma^{2}\cdot N\cdot n_{s}}{A-2\cdot\sigma^{2}\cdot N\cdot
n_{s}}<\frac{B+2\sigma^{2}\cdot N\cdot n_{\ell}}{A-2\cdot\sigma^{2}\cdot
N\cdot n_{\ell}}$

for

$A=\mu_{e}\cdot N+\sigma^{2}\cdot(\sum_{i\in C}n_{i}^{2}+N^{2})\quad
B=-\mu_{e}\cdot N+2\sigma^{2}\cdot((n_{k}+N)\cdot N-(\sum_{i\in
C}n_{i}^{2}+N^{2}))$

We can cross multiply the inequality to get:

$(B+2\sigma^{2}\cdot N\cdot n_{s})\cdot(A-2\cdot\sigma^{2}\cdot N\cdot
n_{\ell})<(B+2\sigma^{2}\cdot N\cdot n_{\ell})\cdot(A-2\cdot\sigma^{2}\cdot
N\cdot n_{s})$ $0<(B+2\sigma^{2}\cdot N\cdot
n_{\ell})\cdot(A-2\cdot\sigma^{2}\cdot N\cdot n_{s})-(B+2\sigma^{2}\cdot
N\cdot n_{s})\cdot(A-2\cdot\sigma^{2}\cdot N\cdot n_{\ell})$

Which simplifies to:

$0<2\cdot(A+B)\cdot(n_{\ell}-n_{s})\cdot N\cdot\sigma^{2}$

Because we have assumed that $n_{\ell}>n_{s}$, this is true if $A+B>0$. We can
evaluate $A+B$ as being:

$\displaystyle=$ $\displaystyle\mu_{e}\cdot N+\sigma^{2}\cdot(\sum_{i\in
C}n_{i}^{2}+N^{2})-\mu_{e}\cdot N+2\sigma^{2}\cdot((n_{k}+N)\cdot
N-(\sum_{i\in C}n_{i}^{2}+N^{2}))$ $\displaystyle=$ $\displaystyle
2\sigma^{2}\cdot(n_{k}+N)\cdot N)-\sigma^{2}\cdot\left(\sum_{i\in
C}n_{i}^{2}-N^{2}\right)$ $\displaystyle=$ $\displaystyle 2\sigma^{2}\cdot
n_{k}\cdot N+2\sigma^{2}\cdot N^{2}-\sigma^{2}\cdot\left(\sum_{i\in
C}n_{i}^{2}-N^{2}\right)$ $\displaystyle=$ $\displaystyle 2\sigma^{2}\cdot
n_{k}\cdot N+\sigma^{2}\cdot\left(N^{2}-\sum_{i\in C}n_{i}^{2}\right)$
$\displaystyle>$ $\displaystyle 0$

as desired.

The remaining properties all relate to the ratio of errors for the two-player
group $\\{n_{s},n_{\ell}\\}$. For uniform federation, this ratio can be
written as:

$\frac{err_{s}^{u}\left(\\{n_{s},n_{\ell}\\}\right)}{err_{l}^{u}\left(\\{n_{s},n_{\ell}\right)\\}}=\frac{\mu_{e}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot
n_{\ell}^{2}}{\mu_{e}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot n_{s}^{2}}$

Property 3:

This property relates to the derivative of the ratio with respect to the size
of the large player ($n_{\ell}$):

$\frac{\partial}{\partial
n_{\ell}}\frac{\mu_{e}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot
n_{\ell}^{2}}{\mu_{e}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot n_{s}^{2}}$

This derivative is given by:

$\frac{(\mu_{e}+4\cdot\sigma^{2}\cdot
n_{\ell})\cdot(\mu_{e}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot
n_{s}^{2})-(\mu_{e}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot
n_{\ell}^{2})\cdot\mu_{e}}{(\mu_{e}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot
n_{s}^{2})^{2}}$

The derivative is _positive_ whenever:

$(\mu_{e}+4\cdot\sigma^{2}\cdot
n_{\ell})\cdot(\mu_{e}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot
n_{s}^{2})-(\mu_{e}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot
n_{\ell}^{2})\cdot\mu_{e}>0$

Pulling over terms and expanding gives:

$\mu_{e}^{2}\cdot(n_{s}+n_{\ell})+2\cdot\mu_{e}\cdot\sigma^{2}\cdot
n_{s}^{2}+4\cdot\sigma^{2}\cdot
n_{\ell}\cdot\mu_{e}\cdot(n_{s}+n_{\ell})+8\cdot\sigma^{4}\cdot n_{\ell}\cdot
n_{s}^{2}>$ $\mu_{e}^{2}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot\mu_{e}\cdot
n_{\ell}^{2}$

Which simplifies to:

$2\cdot\mu_{e}\cdot\sigma^{2}\cdot n_{s}^{2}+2\cdot\sigma^{2}\cdot
n_{\ell}\cdot\mu_{e}\cdot(2n_{s}+n_{\ell})+8\cdot\sigma^{4}\cdot n_{\ell}\cdot
n_{s}^{2}>0$

Property 4:
This property relates to the derivative of the ratio with respect to the size
of the small player ($n_{s}$):

$\frac{\partial}{\partial
n_{s}}\frac{\mu_{e}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot
n_{\ell}^{2}}{\mu_{e}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot n_{s}^{2}}$

This derivative is given by:

$\frac{\mu_{e}\cdot(\mu_{e}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot
n_{s}^{2})-(\mu_{e}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot
n_{\ell}^{2})\cdot(\mu_{e}+4\cdot\sigma^{2}\cdot
n_{s})}{(\mu_{e}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot n_{s}^{2})^{2}}$

The derivative is _negative_ whenever:

$\mu_{e}\cdot(\mu_{e}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot
n_{s}^{2})<(\mu_{e}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot
n_{\ell}^{2})\cdot(\mu_{e}+4\cdot\sigma^{2}\cdot n_{s})$

Expanding:

$\mu_{e}\cdot(\mu_{e}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot
n_{s}^{2})<\mu_{e}^{2}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot
n_{\ell}^{2}\cdot\mu_{e}+4\cdot\sigma^{2}\cdot
n_{s}\cdot\mu_{e}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot\mu_{e}\cdot
n_{\ell}^{2}$

Simplifying:

$0<2\sigma^{2}\cdot n_{\ell}^{2}\cdot\mu_{e}+2\cdot\sigma^{2}\cdot
n_{s}\cdot\mu_{e}\cdot(n_{s}+2n_{\ell})+2\sigma^{2}\cdot\mu_{e}\cdot
n_{\ell}^{2}$

which is satisfied.
Property 5:
This can be found by rewriting and applying the limit.

$\displaystyle\lim_{\frac{n_{s}}{n_{\ell}}\rightarrow
0}\frac{err_{s}\left(\\{n_{s},n_{\ell}\right)\\}}{err_{l}\left(\\{n_{s},n_{\ell}\right)\\}}=$
$\displaystyle\lim_{\frac{n_{s}}{n_{\ell}}\rightarrow
0}\frac{\mu_{e}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot
n_{\ell}^{2}}{\mu_{e}\cdot(n_{s}+n_{\ell})+2\sigma^{2}\cdot n_{s}^{2}}$
$\displaystyle=$ $\displaystyle\lim_{\frac{n_{s}}{n_{\ell}}\rightarrow
0}\frac{\mu_{e}\cdot\frac{n_{s}}{n_{\ell}}+\mu_{e}+2\sigma^{2}\cdot
n_{\ell}}{\mu_{e}\cdot\frac{n_{s}}{n_{\ell}}+\mu_{e}+2\sigma^{2}\cdot
n_{s}\cdot\frac{n_{s}}{n_{\ell}}}$ $\displaystyle=$
$\displaystyle\frac{\mu_{e}+2\sigma^{2}\cdot n_{\ell}}{\mu_{e}}$
$\displaystyle=$
$\displaystyle\frac{\frac{\mu_{e}}{n_{\ell}}+2\sigma^{2}}{\frac{\mu_{e}}{n_{\ell}}}$

∎

######  Lemma 5.

Consider a set of $M$ federating players, using optimal fine-grained
federation. The error player $j$ (with $n_{j}$ samples) experiences can be
given by:

$\frac{\frac{\mu_{e}}{n_{j}}}{V_{j}\cdot
T}\cdot\left(1+\sigma^{2}\left(T-\frac{1}{V_{j}}\right)\right)$

with $V_{i}=\sigma^{2}+\frac{\mu_{e}}{n_{i}}$ and
$T=\sum_{i=1}^{M}\frac{1}{V_{i}}$.

###### Proof.

Lemma 4.2 in [3] gives the expected error as:

$\mu_{e}\sum_{i=1}^{M}v_{ji}^{2}\cdot\frac{1}{n_{i}}+\left(\sum_{i\neq
j}v_{ji}^{2}+\left(\sum_{i\neq j}v_{ji}\right)^{2}\right)\cdot\sigma^{2}$

Fine-grained federation requires that $v_{jj}+\sum_{i\neq j}v_{ji}=1$, so
$v_{jj}=1-\sum_{i\neq j}v_{ji}$, or $\sum_{i\neq j}v_{ji}=1-v_{jj}$. We can
then write the error out as:

$\mu_{e}\sum_{i=1}^{M}\frac{v_{ji}^{2}}{n_{i}}+\left(\sum_{i\neq
j}v_{ji}^{2}+\left(1-v_{jj}\right)^{2}\right)\cdot\sigma^{2}$

Or:

$\mu_{e}\cdot\frac{v_{jj}^{2}}{n_{j}}+(1-v_{jj})^{2}\cdot\sigma^{2}+\sum_{i\neq
j}v_{ji}^{2}\cdot\left(\frac{\mu_{e}}{n_{i}}+\sigma^{2}\right)$

We note that this last form has three components (the first involving
$\mu_{e}$ and the latter two involving $\sigma^{2}$).

Lemma 7.1 from the same work shows that the optimal $v_{ji}$ weights can be
calculated as follows: Define $V_{i}=\sigma^{2}+\frac{\mu_{e}}{n_{i}}$. Then,
the value of $\\{v_{ji}\\}$ that minimizes player $j$’s error is:

$v_{jj}=\frac{1+\sigma^{2}\sum_{i\neq j}\frac{1}{V_{i}}}{1+V_{j}\sum_{i\neq
j}\frac{1}{V_{i}}}$
$v_{jk}=\frac{1}{V_{k}}\cdot\frac{V_{j}-\sigma^{2}}{1+V_{j}\sum_{i\neq
j}\frac{1}{V_{i}}}\quad k\neq j$

This analysis follows by plugging in the optimal weights and then simplifying.
The first component of the error becomes:

$\mu_{e}\cdot\frac{v_{jj}^{2}}{n_{j}}=\frac{\mu_{e}}{n_{j}}\cdot\frac{(1+\sigma^{2}\sum_{i\neq
j}\frac{1}{V_{i}})^{2}}{(1+V_{j}\sum_{i\neq j}\frac{1}{V_{i}})^{2}}$

The next component becomes:

$(1-v_{jj})^{2}\cdot\sigma^{2}=\sigma^{2}\cdot\left(\frac{1+V_{j}\sum_{i\neq
j}\frac{1}{V_{i}}-1-\sigma^{2}\sum_{i\neq
j}\frac{1}{V_{i}}}{1+V_{j}\sum_{i\neq
j}\frac{1}{V_{i}}}\right)^{2}=\sigma^{2}\cdot\frac{\frac{\mu_{e}^{2}}{n_{j}^{2}}\cdot(\sum_{i\neq
j}\frac{1}{V_{i}})^{2}}{(1+V_{j}\sum_{i\neq j}\frac{1}{V_{i}})^{2}}$

The last component:

$\sum_{i\neq
j}v_{ji}^{2}\cdot\left(\frac{\mu_{e}}{n_{i}}+\sigma^{2}\right)=\sum_{i\neq
j}\left(\frac{1}{V_{i}}\cdot\frac{\frac{\mu_{e}}{n_{j}}}{1+V_{j}\sum_{k\neq
j}\frac{1}{V_{k}}}\right)^{2}\cdot V_{i}$
$=\frac{\mu_{e}^{2}}{n_{j}^{2}}\cdot\sum_{i\neq
j}\frac{1}{V_{i}}\cdot\frac{1}{(1+V_{j}\sum_{k\neq
j}\frac{1}{V_{k}})^{2}}=\frac{\mu_{e}^{2}}{n_{j}^{2}}\cdot\frac{\sum_{i\neq
j}\frac{1}{V_{i}}}{(1+V_{j}\cdot\sum_{k\neq j}\frac{1}{V_{k}})^{2}}$

When we combine them together, we can pull out a common factor of:

$\frac{\frac{\mu_{e}}{n_{j}}}{(1+V_{j}\cdot\sum_{i\neq
j}\frac{1}{V_{i}})^{2}}$

The other terms become:

$\left(1+\sigma^{2}\sum_{i\neq
j}\frac{1}{V_{i}}\right)^{2}+\sigma^{2}\cdot\frac{\mu_{e}}{n_{j}}\cdot\left(\sum_{i\neq
j}\frac{1}{V_{i}}\right)^{2}+\frac{\mu_{e}}{n_{j}}\cdot\sum_{i\neq
j}\frac{1}{V_{i}}$

Combining these together gives:

$\frac{\frac{\mu_{e}}{n_{j}}}{\left(1+V_{j}\cdot\left(T-\frac{1}{V_{j}}\right)\right)^{2}}\cdot\left(\left(1+\sigma^{2}\left(T-\frac{1}{V_{j}}\right)\right)^{2}+\sigma^{2}\cdot\frac{\mu_{e}}{n_{j}}\cdot\left(T-\frac{1}{V_{j}}\right)^{2}+\frac{\mu_{e}}{n_{j}}\cdot\left(T-\frac{1}{V_{j}}\right)\right)$

for $T=\sum_{i=1}^{M}\frac{1}{V_{i}}$. Next, we begin simplifying, noting
that:

$\frac{\frac{\mu_{e}}{n_{j}}}{\left(1+V_{j}\cdot\left(T-\frac{1}{V_{j}}\right)\right)^{2}}=\frac{\frac{\mu_{e}}{n_{j}}}{\left(1+V_{j}\cdot
T-1\right)^{2}}=\frac{\frac{\mu_{e}}{n_{j}}}{V_{j}^{2}\cdot T^{2}}$

We can also simplify the other coefficient:

$\displaystyle\left(1+\sigma^{2}\left(T-\frac{1}{V_{j}}\right)\right)^{2}+\sigma^{2}\cdot\frac{\mu_{e}}{n_{j}}\cdot\left(T-\frac{1}{V_{j}}\right)^{2}+\frac{\mu_{e}}{n_{j}}\cdot\left(T-\frac{1}{V_{j}}\right)$
$\displaystyle=$
$\displaystyle\left(1+\sigma^{2}\left(T-\frac{1}{V_{j}}\right)\right)^{2}+\frac{\mu_{e}}{n_{j}}\cdot\left(T-\frac{1}{V_{j}}\right)\cdot\left(\sigma^{2}\cdot\left(T-\frac{1}{V_{j}}\right)+1\right)$
$\displaystyle=$
$\displaystyle\left(1+\sigma^{2}\left(T-\frac{1}{V_{j}}\right)\right)\cdot\left(1+\sigma^{2}\left(T-\frac{1}{V_{j}}\right)+\frac{\mu_{e}}{n_{j}}\cdot\left(T-\frac{1}{V_{j}}\right)\right)$
$\displaystyle=$
$\displaystyle\left(1+\sigma^{2}\left(T-\frac{1}{V_{j}}\right)\right)\cdot\left(1+\left(\sigma^{2}+\frac{\mu_{e}}{n_{j}}\right)\cdot\left(T-\frac{1}{V_{j}}\right)\right)$
$\displaystyle=$
$\displaystyle\left(1+\sigma^{2}\left(T-\frac{1}{V_{j}}\right)\right)\cdot\left(1+V_{j}\cdot\left(T-\frac{1}{V_{j}}\right)\right)$
$\displaystyle=$
$\displaystyle\left(1+\sigma^{2}\left(T-\frac{1}{V_{j}}\right)\right)\cdot\left(1+V_{j}\cdot
T-1\right)$ $\displaystyle=$
$\displaystyle\left(1+\sigma^{2}\left(T-\frac{1}{V_{j}}\right)\right)\cdot
V_{j}\cdot T$

Next, we combine the two terms together to get:

$\frac{\frac{\mu_{e}}{n_{j}}}{V_{j}\cdot
T}\cdot\left(1+\sigma^{2}\left(T-\frac{1}{V_{j}}\right)\right)$

as desired. ∎

See 3

###### Proof.

In this proof, we will denote fine federation error by $err^{f}$. This proof
will be similar to that of Lemma 2 and will again have five components
corresponding to the five sections of Definition 3.
Property 1:
For the first property, we wish to show that, for any federating coalition,
the small player gets higher error than the large player. That is, we wish to
show:

$err^{f}_{s}(C)\geq err^{f}_{l}(C)$

From Lemma 5, we know we can write each player’s error as:

$\frac{\mu_{e}}{n_{s}\cdot V_{s}\cdot
T}\cdot\left(1+\sigma^{2}\left(S+\frac{1}{V_{l}}\right)\right)\geq\frac{\mu_{e}}{n_{\ell}\cdot
V_{l}\cdot T}\cdot\left(1+\sigma^{2}\left(S+\frac{1}{V_{s}}\right)\right)$

where we have $V_{i}=\frac{\mu_{e}}{n_{i}}+\sigma^{2}$, $T=\sum_{i\in
C}\frac{1}{V_{i}}$ and $S=T-\frac{1}{V_{s}}-\frac{1}{V_{l}}$. We know that
$V_{i},T>0$, so we can cancel common terms:

$\displaystyle\frac{1}{n_{s}\cdot
V_{s}}\cdot\left(1+\sigma^{2}\left(S+\frac{1}{V_{l}}\right)\right)$
$\displaystyle\geq\frac{1}{n_{\ell}\cdot
V_{l}}\cdot\left(1+\sigma^{2}\left(S+\frac{1}{V_{s}}\right)\right)$
$\displaystyle n_{\ell}\cdot
V_{l}\left(1+\sigma^{2}\left(S+\frac{1}{V_{l}}\right)\right)$
$\displaystyle\geq n_{s}\cdot
V_{s}\cdot\left(1+\sigma^{2}\left(S+\frac{1}{V_{s}}\right)\right)$
$\displaystyle n_{\ell}\cdot V_{l}+\sigma^{2}\cdot S\cdot n_{\ell}\cdot
V_{l}+\sigma^{2}\cdot n_{\ell}$ $\displaystyle\geq n_{s}\cdot
V_{s}+\sigma^{2}\cdot S\cdot n_{s}\cdot V_{s}+\sigma^{2}\cdot n_{s}$

Next, we can plug in for $V_{i}=\frac{\mu_{e}}{n_{i}}+\sigma^{2}$:

$\displaystyle\mu_{e}+n_{\ell}\cdot\sigma^{2}+\sigma^{2}\cdot
S\cdot\left(\mu_{e}+n_{\ell}\cdot\sigma^{2}\right)+\sigma^{2}\cdot n_{\ell}$
$\displaystyle\geq\mu_{e}+n_{s}\cdot\sigma^{2}+\sigma^{2}\cdot
S\cdot\left(\mu_{e}+n_{s}\cdot\sigma^{2}\right)+\sigma^{2}\cdot n_{s}$
$\displaystyle 2\cdot n_{\ell}\cdot\sigma^{2}+n_{\ell}\cdot S\cdot\sigma^{4}$
$\displaystyle\geq 2\cdot n_{s}\cdot\sigma^{2}+S\cdot n_{s}\cdot\sigma^{4}$
$\displaystyle n_{\ell}$ $\displaystyle\geq n_{s}$

This result tells us that the small player has higher error whenever it has
fewer samples than the large player - and strictly higher error whenever it
has strictly fewer samples.
Property 2:
For the second property, we again wish to show that the worst case ratio of
errors occurs in the two-player case, or

$\frac{err_{s}^{f}\left(C\right)}{err_{l}^{f}\left(C\right)}\leq\frac{err_{s}^{f}\left(\\{n_{s},n_{\ell}\\}\right)}{err_{l}^{f}\left(\\{n_{s},n_{\ell}\right)\\}}$

From Lemma 5, we know that we can write the ratio of errors as:

$\frac{\frac{\mu_{e}}{n_{s}\cdot V_{s}\cdot
T}\cdot\left(1+\sigma^{2}\left(S+\frac{1}{V_{l}}\right)\right)}{\frac{\mu_{e}}{n_{\ell}\cdot
V_{l}\cdot T}\cdot\left(1+\sigma^{2}\left(S+\frac{1}{V_{s}}\right)\right)}$

where we have $V_{i}=\frac{\mu_{e}}{n_{i}}+\sigma^{2}$, $T=\sum_{i\in
C}\frac{1}{V_{i}}$ and $S=T-\frac{1}{V_{s}}-\frac{1}{V_{l}}$. The ratio of
errors can be simplified further:

$=\frac{n_{\ell}\cdot
V_{l}\cdot\left(1+\sigma^{2}\left(S+\frac{1}{V_{l}}\right)\right)}{n_{s}\cdot
V_{s}\cdot\left(1+\sigma^{2}\left(S+\frac{1}{V_{s}}\right)\right)}=\frac{n_{\ell}\cdot
V_{l}+\sigma^{2}\cdot S\cdot n_{\ell}\cdot
V_{l}+n_{\ell}\cdot\sigma^{2}}{n_{s}\cdot V_{s}+\sigma^{2}\cdot S\cdot
n_{s}\cdot V_{s}+n_{s}\cdot\sigma^{2}}$

Again, we will prove something stronger: that this ratio decreases as $S$
increases. Note that $S=\sum_{i\in C,i\neq s,l}\frac{1}{V_{i}}=\sum_{i\in
C,i\neq s,l}\frac{1}{\frac{\mu_{e}}{n_{i}}+2\sigma^{2}}$, so as $n_{i}$
decreases, $S$ decreases as well. We can rewrite the equation as:

$\frac{a+b\cdot S}{c+d\cdot S}$

for:

$a=n_{\ell}\cdot(V_{l}+\sigma^{2})\quad b=\sigma^{2}\cdot n_{\ell}\cdot V_{l}$
$c=n_{s}\cdot(V_{s}+\sigma^{2})\quad d=\sigma^{2}\cdot n_{s}\cdot V_{s}$

The key question relates to the derivative of the equation with respect to
$S$:

$\frac{\partial}{\partial S}\frac{a+b\cdot S}{c+d\cdot
S}=\frac{b\cdot(c+d\cdot S)-(a+b\cdot S)\cdot d}{(c+dS)^{2}}=\frac{b\cdot
c-a\cdot d}{(c+d\cdot S)^{2}}$

This is negative if:

$b\cdot c<a\cdot d$

Plugging in for the values gives:

$\sigma^{2}\cdot n_{\ell}\cdot n_{s}\cdot
V_{l}\cdot(V_{s}+\sigma^{2})<\sigma^{2}\cdot n_{\ell}\cdot n_{s}\cdot
V_{s}\cdot(V_{l}+\sigma^{2})$ $\sigma^{4}\cdot n_{\ell}\cdot V_{l}\cdot
n_{s}<\sigma^{4}\cdot n_{s}\cdot n_{\ell}\cdot V_{s}$ $V_{l}<V_{s}$
$\frac{\mu_{e}}{n_{\ell}}+\sigma^{2}<\frac{\mu_{e}}{n_{s}}+\sigma^{2}$

which is satisfied because $n_{\ell}>n_{s}$.

The remaining properties all relate to the ratio of errors for the two-player
group $\\{n_{s},n_{\ell}\\}$. For fine-grained federation, this ratio can be
written as:

$\frac{err_{s}^{f}\left(\\{n_{s},n_{\ell}\\}\right)}{err_{l}^{f}\left(\\{n_{s},n_{\ell}\right)\\}}=\frac{n_{\ell}\cdot
V_{l}\cdot\left(1+\sigma^{2}\cdot\frac{1}{V_{l}}\right)}{n_{s}\cdot
V_{s}\cdot\left(1+\sigma^{2}\cdot\frac{1}{V_{s}}\right)}=\frac{n_{\ell}\cdot
V_{l}+\sigma^{2}\cdot n_{\ell}}{n_{s}\cdot V_{s}+\sigma^{2}\cdot
n_{s}}=\frac{n_{\ell}}{n_{s}}\cdot\frac{2\sigma^{2}+\frac{\mu_{e}}{n_{\ell}}}{2\sigma^{2}+\frac{\mu_{e}}{n_{s}}}=\frac{2\sigma^{2}\cdot
n_{\ell}+\mu_{e}}{2\sigma^{2}\cdot n_{s}+\mu_{e}}$

The remaining three properties for fine-grained federation are extremely
straightforward:
Property 3:
This property relates to the derivative of the ratio of the errors with
respect to the size of the large player ($n_{\ell}$):

$\frac{\partial}{\partial n_{\ell}}\frac{2\sigma^{2}\cdot
n_{\ell}+\mu_{e}}{2\sigma^{2}\cdot n_{s}+\mu_{e}}=2\sigma^{2}>0$

Property 4:
This property relates to the derivative of the ratio of the errors with
respect to the size of the small player ($n_{s}$):

$\frac{\partial}{\partial n_{s}}\frac{2\sigma^{2}\cdot
n_{\ell}+\mu_{e}}{2\sigma^{2}\cdot
n_{s}+\mu_{e}}=\frac{0-2\sigma^{2}\cdot(2\sigma^{2}\cdot
n_{\ell}+\mu_{e})}{(2\sigma^{2}\cdot n_{s}+\mu_{e})^{2}}<0$

Property 5:
Finally, this property can be seen by applying the limit:

$\lim_{\frac{n_{s}}{n_{\ell}}\rightarrow
0}\frac{err_{s}\left(\\{n_{s},n_{\ell}\right)\\}}{err_{l}\left(\\{n_{s},n_{\ell}\right)\\}}=\lim_{\frac{n_{s}}{n_{\ell}}\rightarrow
0}\frac{2\sigma^{2}\cdot n_{\ell}+\mu_{e}}{2\sigma^{2}\cdot
n_{s}+\mu_{e}}=\lim_{\frac{n_{s}}{n_{\ell}}\rightarrow
0}\frac{2\sigma^{2}+\frac{\mu_{e}}{n_{\ell}}}{2\sigma^{2}\cdot\frac{n_{s}}{n_{\ell}}+\frac{\mu_{e}}{n_{\ell}}}=\frac{\frac{\mu_{e}}{n_{\ell}}+2\sigma^{2}}{\frac{\mu_{e}}{n_{\ell}}}$

∎

See 3

###### Proof.

We will show this result by proving the contrapositive: if sub-proportionality
of errors is violated, then at least one player wishes to leave that coalition
for local learning (so stability is violated).

In our analysis, we will consider two players $n_{s}<n_{\ell}$, though the
players could be arbitrarily situated with respect to
$\frac{\mu_{e}}{\sigma^{2}}$. We will assume that all of the players are
federating together in coalition $A$. For notational convenience, we will
write the federating coalition $A$ of interest as $A=C\cup\\{n_{\ell}\\}$, so
$C$ refers to all players except $n_{\ell}$.

For later portions of this proof, we will find it useful to rewrite the
difference in error between the small and large player:

$err_{S}(C\cup\\{n_{\ell}\\})-err_{L}(C\cup\\{n_{\ell}\\})=2\sigma^{2}\frac{n_{\ell}-n_{s}}{N_{C}+n_{\ell}}$

We note that both terms have the same $\mu_{e}$ coefficient, so they differ
only in the $\sigma^{2}$ component:

$\displaystyle\sigma^{2}\cdot\frac{\sum_{i\in
C}n_{i}^{2}-n_{s}^{2}+n_{\ell}^{2}+(N_{C}-n_{s}+n_{\ell})^{2}}{(N_{C}+n_{\ell})^{2}}-\sigma^{2}\frac{\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}}{(N_{C}+n_{\ell})^{2}}$ $\displaystyle=$
$\displaystyle\sigma^{2}\cdot\frac{-n_{s}^{2}+n_{\ell}^{2}+N_{C}^{2}+n_{s}^{2}+n_{\ell}^{2}-2n_{s}\cdot
N_{C}+2n_{\ell}\cdot N_{C}-2n_{\ell}\cdot
n_{s}-N_{C}^{2}}{(N_{C}+n_{\ell})^{2}}$ $\displaystyle=$
$\displaystyle\sigma^{2}\cdot\frac{2n_{\ell}^{2}-2n_{s}\cdot N_{C}+2\cdot
n_{\ell}\cdot N_{C}-2n_{\ell}\cdot n_{s}}{(N_{C}+n_{\ell})^{2}}$

Note that we can rewrite the numerator:

$2(N_{C}+n_{\ell})\cdot(n_{\ell}-n_{s})=2\cdot(N_{C}\cdot n_{\ell}-n_{s}\cdot
N_{C}+n_{\ell}^{2}-n_{s}\cdot n_{\ell})$

So the overall difference reduces to:

$=\sigma^{2}\cdot\frac{2\cdot(n_{\ell}-n_{s})}{N_{C}+n_{\ell}}$

as desired.

Next, we will begin the formal proof. At a high level, what the proof does is
first derive conditions where subproportionality fails to hold, and then show
that, when these conditions are satisfied, at least one player wishes to leave
$C$ for local learning.

Sub-proportionality fails to hold when:

$\frac{err_{S}(C\cup\\{n_{\ell}\\})}{err_{L}(C\cup\\{n_{\ell}\\})}\geq\frac{n_{\ell}}{n_{s}}$
$err_{S}(C\cup\\{n_{\ell}\\})\geq\frac{n_{\ell}}{n_{s}}\cdot
err_{L}(C\cup\\{n_{\ell}\\})$

(Note that our definition of sub-proportionality is defined with respect to
the smaller player.) Our goal will be to get a lower bound on $n_{\ell}$,
given that this occurs. Rewriting the subproportionality violation:

$2\sigma^{2}\frac{n_{\ell}-n_{s}}{N_{C}+n_{\ell}}\geq\left(\frac{n_{\ell}}{n_{s}}-1\right)\cdot
err_{L}(C)$

Plugging in for the value of the large player’s error:

$2\sigma^{2}\frac{n_{\ell}-n_{s}}{N_{C}+n_{\ell}}\geq\left(\frac{n_{\ell}}{n_{s}}-1\right)\cdot\left(\frac{\mu_{e}}{N_{C}+n_{\ell}}+\sigma^{2}\frac{\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}}{(N_{C}+n_{\ell})^{2}}\right)$

Cancelling a $N_{C}+n_{\ell}$ in the denominator:

$2\sigma^{2}(n_{\ell}-n_{s})\geq\left(\frac{n_{\ell}}{n_{s}}-1\right)\cdot\left(\mu_{e}+\sigma^{2}\frac{\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}}{N_{C}+n_{\ell}}\right)$

Rearranging a $\frac{1}{n_{s}}$ in the right hand side:

$2\sigma^{2}\cdot(n_{\ell}-n_{s})\geq\left(n_{\ell}-n_{s}\right)\cdot\left(\frac{\mu_{e}}{n_{s}}+\frac{\sigma^{2}}{n_{s}}\frac{\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}}{N_{C}+n_{\ell}}\right)$

Cancelling $n_{\ell}-n_{s}$ from both sides:

$2\sigma^{2}\geq\frac{\mu_{e}}{n_{s}}+\frac{\sigma^{2}}{n_{s}}\frac{\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}}{N_{C}+n_{\ell}}$

Bringing over common terms:

$0\geq\frac{\mu_{e}}{n_{s}}-2\sigma^{2}+\frac{\sigma^{2}}{n_{s}}\frac{\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}}{N_{C}+n_{\ell}}$

Multiplying by $N_{C}+n_{\ell}$:

$0\geq\frac{\mu_{e}}{n_{s}}\cdot(N_{C}+n_{\ell})-2\sigma^{2}\cdot(N_{C}+n_{\ell})+\frac{\sigma^{2}}{n_{s}}\left(\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}\right)$

Collecting terms around $n_{\ell}$:

$0\geq
N_{C}\cdot\left(\frac{\mu_{e}}{n_{s}}-2\sigma^{2}\right)+\frac{\sigma^{2}}{n_{s}}\left(\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}\right)+\left(\frac{\mu_{e}}{n_{s}}-2\sigma^{2}\right)\cdot
n_{\ell}$

Note that if $\frac{\mu_{e}}{n_{s}}\geq 2\sigma^{2}$, then this inequality can
never hold (all of the terms on the righthand side are positive, where we need
at least one to be negative). So, in order for it to even be possible to
violate sub-proportionality, we need $\frac{\mu_{e}}{n_{s}}<2\sigma^{2}$, or
$\frac{\mu_{e}}{2\sigma^{2}}<n_{s}$. Knowing this, we can pull over terms and
flip the sign of the inequality:

$\displaystyle\left(2\sigma^{2}\cdot N_{C}-\frac{\mu_{e}}{n_{s}}\cdot
N_{C}-\frac{\sigma^{2}}{n_{s}}\cdot\left(\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}\right)\right)\geq$
$\displaystyle\left(\frac{\mu_{e}}{n_{s}}-2\sigma^{2}\right)\cdot n_{\ell}$
$\displaystyle\frac{2\sigma^{2}\cdot N_{C}-\frac{\mu_{e}}{n_{s}}\cdot
N_{C}-\frac{\sigma^{2}}{n_{s}}\cdot\left(\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}\right)}{\frac{\mu_{e}}{n_{s}}-2\sigma^{2}}\leq$
$\displaystyle n_{\ell}$ $\displaystyle\frac{-2\sigma^{2}\cdot
N_{C}+\frac{\mu_{e}}{n_{s}}\cdot
N_{C}+\frac{\sigma^{2}}{n_{s}}\cdot\left(\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}\right)}{2\sigma^{2}-\frac{\mu_{e}}{n_{s}}}\leq$
$\displaystyle n_{\ell}$

This gives us a lower bound on $n_{\ell}$ for when sub-proportionality is
violated.
Next, let’s look at the condition for when the larger player would choose to
leave.

$err_{L}(C\cup\\{n_{\ell}\\})\geq err_{L}(\\{n_{\ell}\\})$

The form of the error in this case is given by:

$\frac{\mu_{e}}{N_{C}+n_{\ell}}+\sigma^{2}\cdot\frac{\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}}{(N_{C}+n_{\ell})^{2}}\geq\frac{\mu_{e}}{n_{\ell}}$

Simplifying:

$\displaystyle\sigma^{2}\cdot\frac{\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}}{(N_{C}+n_{\ell})^{2}}\geq$
$\displaystyle\frac{\mu_{e}}{n_{\ell}}-\frac{\mu_{e}}{N_{C}+n_{\ell}}$
$\displaystyle\sigma^{2}\cdot\frac{\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}}{(N_{C}+n_{\ell})^{2}}\geq$
$\displaystyle\frac{\mu_{e}}{n_{\ell}\cdot(N_{C}+n_{\ell})}\cdot(N_{C}+n_{\ell}-n_{\ell})$
$\displaystyle\sigma^{2}\cdot\frac{\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}}{N_{C}+n_{\ell}}\geq$
$\displaystyle\frac{\mu_{e}}{n_{\ell}}\cdot N_{C}$
$\displaystyle\sigma^{2}\cdot\frac{\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}}{N_{C}}\geq$
$\displaystyle\frac{\mu_{e}}{n_{\ell}}\cdot(N_{C}+n_{\ell})$
$\displaystyle\sigma^{2}\cdot\frac{\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}}{N_{C}^{2}}\geq$
$\displaystyle\frac{\mu_{e}}{n_{\ell}\cdot N_{C}}\cdot(N_{C}+n_{\ell})$
$\displaystyle\sigma^{2}\cdot\frac{\sum_{i\in
C}n_{i}^{2}}{N_{C}^{2}}+\sigma^{2}\geq$ $\displaystyle\frac{\mu_{e}\cdot
N_{S}}{n_{\ell}\cdot N_{C}}+\frac{\mu_{e}\cdot n_{\ell}}{n_{\ell}\cdot N_{C}}$
$\displaystyle\sigma^{2}\cdot\frac{\sum_{i\in
C}n_{i}^{2}}{N_{C}^{2}}+\sigma^{2}\geq$
$\displaystyle\frac{\mu_{e}}{n_{\ell}}+\frac{\mu_{e}}{N_{C}}$
$\displaystyle\sigma^{2}\cdot\frac{\sum_{i\in
C}n_{i}^{2}}{N_{C}^{2}}+\sigma^{2}-\frac{\mu_{e}}{N_{C}}\geq$
$\displaystyle\frac{\mu_{e}}{n_{\ell}}$ $\displaystyle
n_{\ell}\cdot\left(\sigma^{2}\cdot\frac{\sum_{i\in
C}n_{i}^{2}}{N_{C}^{2}}+\sigma^{2}-\frac{\mu_{e}}{N_{C}}\right)\geq$
$\displaystyle\mu_{e}$

We have a similar situation to before: if this coefficent is negative, then
the inequality can never hold (no large player will ever wish to leave). The
coefficient is negative when:

$\sigma^{2}\cdot\frac{\sum_{i\in
C}n_{i}^{2}}{N_{C}^{2}}+\sigma^{2}-\frac{\mu_{e}}{N_{C}}\leq 0$

We’re going to show that this can never happen so long as
$n_{s}>\frac{\mu_{e}}{2\sigma^{2}}$ (necessarily for sub-proportionality to be
violated). Rewriting:

$\sigma^{2}\cdot\sum_{i\in C}n_{i}^{2}+\sigma^{2}\cdot N_{C}^{2}<\mu_{e}\cdot
N_{C}$

For simplicity, we will rewrite with $C^{\prime}=C\setminus\\{n_{s}\\}$. Our
term becomes:

$\sigma^{2}\cdot\sum_{i\in C^{\prime}}n_{i}^{2}+\sigma^{2}\cdot
n_{s}^{2}+\sigma^{2}\cdot(N_{C^{\prime}}+n_{s})^{2}<\mu_{e}\cdot
N_{C^{\prime}}+\mu_{e}\cdot n_{s}$

Expanding:

$\sigma^{2}\cdot\sum_{i\in C^{\prime}}n_{i}^{2}+\sigma^{2}\cdot
n_{s}^{2}+\sigma^{2}\cdot N_{C^{\prime}}^{2}+\sigma^{2}\cdot
n_{s}^{2}+2\sigma^{2}\cdot n_{s}\cdot N_{C^{\prime}}<\mu_{e}\cdot
N_{C^{\prime}}+\mu_{e}\cdot n_{s}$ $\sigma^{2}\cdot\sum_{i\in
C^{\prime}}n_{i}^{2}+\sigma^{2}\cdot N_{C^{\prime}}^{2}+2\sigma^{2}\cdot
n_{s}\cdot N_{C^{\prime}}+2\sigma^{2}\cdot n_{s}^{2}<\mu_{e}\cdot
N_{C^{\prime}}+\mu_{e}\cdot n_{s}$

We can show that this never holds by breaking it into two parts. The first one
is to show that:

$2\sigma^{2}\cdot n_{s}^{2}>\mu_{e}\cdot n_{s}$

which holds by the assumption that $n_{s}>\frac{\mu_{e}}{2\sigma^{2}}$. Next,
we can show that

$\sigma^{2}\cdot\sum_{i\in C^{\prime}}n_{i}^{2}+\sigma^{2}\cdot
N_{C^{\prime}}^{2}+2\sigma^{2}\cdot n_{s}\cdot N_{C^{\prime}}>\mu_{e}\cdot
N_{C^{\prime}}$

This holds again by the assumption that $n_{s}>\frac{\mu_{e}}{2\sigma^{2}}$.
Taken together, this shows that the coefficients on the original equation can
never be negative.

Returning to our original equation:

$n_{\ell}\cdot\left(\sigma^{2}\cdot\frac{\sum_{i\in
C}n_{i}^{2}}{N_{C}^{2}}+\sigma^{2}-\frac{\mu_{e}}{N_{C}}\right)\geq\mu_{e}$

We know that the coefficient can never be negative, so we can rewrite it as:

$\frac{\mu_{e}}{\sigma^{2}\cdot\frac{\sum_{i\in
C}n_{i}^{2}}{N_{C}^{2}}+\sigma^{2}-\frac{\mu_{e}}{N_{C}}}\leq n_{\ell}$ (5)

As a reminder, our sub-proportionality being violated condition is given by:

$\frac{-2\sigma^{2}\cdot N_{C}+\frac{\mu_{e}}{n_{s}}\cdot
N_{C}+\frac{\sigma^{2}}{n_{s}}\cdot\left(\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}\right)}{2\sigma^{2}-\frac{\mu_{e}}{n_{s}}}\leq n_{\ell}$
(6)

What we would like to show is that the bound in Equation 5 is lower than the
bound in Equation 6: any situation where the $n_{\ell}$ term is large enough
so that sub-proportionality is violated, we know that the large player already
wishes to leave.

So, what we want to show is:

$\frac{\mu_{e}}{\sigma^{2}\cdot\frac{\sum_{i\in
C}n_{i}^{2}}{N_{C}^{2}}+\sigma^{2}-\frac{\mu_{e}}{N_{C}}}\leq\frac{-2\sigma^{2}\cdot
N_{C}+\frac{\mu_{e}}{n_{s}}\cdot
N_{C}+\frac{\sigma^{2}}{n_{s}}\cdot\left(\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}\right)}{2\sigma^{2}-\frac{\mu_{e}}{n_{s}}}$

Multiply the top and bottom of the righthand side by $\frac{n_{s}}{N_{C}}$:

$\frac{\mu_{e}}{\sigma^{2}\cdot\frac{\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}}{N_{C}^{2}}-\frac{\mu_{e}}{N_{C}}}\leq\frac{\mu_{e}-2\sigma^{2}\cdot
n_{s}+\frac{\sigma^{2}}{N_{C}}\cdot\left(\sum_{i\in
C}n_{i}^{2}+N_{C}^{2}\right)}{2\sigma^{2}\cdot\frac{n_{s}}{N_{C}}-\frac{\mu_{e}}{N_{C}}}$

Next, we multiply the LHS by $N_{C}^{2}$ on both top and bottom and the RHS by
$N_{C}$ on both top and bottom.

$\frac{\mu_{e}\cdot N_{C}^{2}}{\sigma^{2}\cdot B-\mu_{e}\cdot
N_{C}}\leq\frac{\mu_{e}\cdot N_{C}-2\sigma^{2}\cdot n_{s}\cdot
N_{C}+\sigma^{2}\cdot B}{2\sigma^{2}\cdot n_{s}-\mu_{e}}$

Next, we cross multiply. On the lefthand side, we obtain:

$2\mu_{e}\cdot N_{C}^{2}\cdot\sigma^{2}\cdot n_{s}-\mu_{e}^{2}\cdot N_{C}^{2}$

On the righthand side:

$\mu_{e}\cdot N_{C}\cdot\sigma^{2}\cdot B-\mu_{e}^{2}\cdot
N_{C}^{2}-2(\sigma^{2})^{2}\cdot n_{s}\cdot N_{C}\cdot
B+2\mu_{e}\cdot\sigma^{2}\cdot n_{s}\cdot N_{C}^{2}+(\sigma^{2})^{2}\cdot
B^{2}-\mu_{e}\cdot\sigma^{2}\cdot B\cdot N_{C}$ $=-\mu_{e}^{2}\cdot
N_{C}^{2}-2(\sigma^{2})^{2}\cdot n_{s}\cdot N_{C}\cdot
B+2\mu_{e}\cdot\sigma^{2}\cdot n_{s}\cdot N_{C}^{2}+(\sigma^{2})^{2}\cdot
B^{2}$

Bringing the two sides together, what we wish to show is:

$\displaystyle 2\mu_{e}\cdot N_{C}^{2}\cdot\sigma^{2}\cdot
n_{s}-\mu_{e}^{2}\cdot N_{C}^{2}\leq$ $\displaystyle-\mu_{e}^{2}\cdot
N_{C}^{2}-2(\sigma^{2})^{2}\cdot n_{s}\cdot N_{C}\cdot
B+2\mu_{e}\cdot\sigma^{2}\cdot n_{s}\cdot N_{C}^{2}+(\sigma^{2})^{2}\cdot
B^{2}$ $\displaystyle 0\leq$ $\displaystyle-2(\sigma^{2})^{2}\cdot n_{s}\cdot
N_{C}\cdot B+(\sigma^{2})^{2}\cdot B^{2}$

Dropping the common (positive) terms of $B,(\sigma^{2})^{2}$, gives:

$\displaystyle 0\leq$ $\displaystyle-2\cdot n_{s}\cdot N_{C}+B$ $\displaystyle
2\cdot n_{s}\cdot N_{C}\leq$ $\displaystyle\sum_{i\in C}n_{i}^{2}+N_{C}^{2}$

We’ll use the same $C^{\prime}=C\setminus\\{n_{s}\\}$ rewriting as before.
This gives us:

$\displaystyle 2\cdot n_{s}\cdot N_{C^{\prime}}+2\cdot n_{s}^{2}\leq$
$\displaystyle\sum_{i\in
C^{\prime}}n_{i}^{2}+n_{s}^{2}+(N_{C^{\prime}}+n_{s})^{2}$ $\displaystyle
2\cdot n_{s}\cdot N_{C^{\prime}}+2\cdot n_{s}^{2}\leq$
$\displaystyle\sum_{i\in
C^{\prime}}n_{i}^{2}+n_{s}^{2}+N_{C^{\prime}}^{2}+n_{s}^{2}+2n_{s}\cdot
N_{C}^{\prime}$

Cancelling:

$0\leq\sum_{i\in C^{\prime}}n_{i}^{2}+N_{C^{\prime}}^{2}$

This is always satisfied. This tells us that the inequality is satisfied and
is strict whenever $C^{\prime}\neq\emptyset$. If $C^{\prime}=\emptyset$, then
the bound for each becomes:

$\frac{\mu_{e}}{2\sigma^{2}-\frac{\mu_{e}}{n_{s}}}=n_{\ell}$

If this equation holds exactly, the exact proportionality holds and the large
player gets equal error by federating with $n_{s}$ or doing local learning. ∎