Model-sharing Games:
Analyzing Federated Learning Under Voluntary Participation

Imagine a situation as follows: a hospital is trying to evaluate the effectiveness of a certain procedure based on data it has collected from procedures done on patients in their facilities. It seems likely that certain attributes of the patient influences the effectiveness of the procedure, so the hospital analysts opt to fit a linear regression model with parameters $\hat{\bm{\theta}}$. However, because of the limited amount of data the hospital has access to, this model has relatively high error. Luckily, other hospitals also have data from implementations of this same procedure. However, for reasons of privacy, data incompatibility, data size, or other operational considerations, the hospitals don’t wish to share raw patient data. Instead, they they opt to combine their models by taking a weighted average of the parameters learned by each hospital. If there are $M$ hospitals and hospital $i$ has $n_{i}$ samples, the combined model parameters would look like:

The situation described above could be viewed as a stylized model of federated learning. Federated learning is a distributed learning process that is currently experiencing rapid innovations and widespread implementation (Li et al. 2020; Kairouz et al. 2019). It is used in cases where data is distributed across multiple agents and cannot be combined centrally for training. For example, federated learning is implemented in word prediction on cell phones, where transferring the raw text data would be infeasible given its large size (and sensitive content). The motivating factor for using federated learning is that access to more data will reduce the variance in a learned model, reducing its error.

However, there could be a downside to using federated learning. In the hospital example, it seems quite reasonable that certain hospitals might have different true generating models for their data, based on the differences in patient populations or variants of the procedure implementation, for example. Two dissimilar hospitals that are federating together will see a decrease in their model’s error due to model variance, but an increase in their error due to model bias. This raises some fundamental questions for each participating hospital - or, more generally, each agent $i$ considering federated learning. Which other agents should $i$ federate with in order to minimize its error? Will those other agents be interested in federating with $i$? Does there exist some stable arrangement of agents into federating clusters, and if so, what does that arrangement look like?

Numerous works have explored the issue of heterogeneous data in federated learning - we discuss specifically how they relate to ours in a later section. Often the goal in these lines of work is to achieve equality in error rates guaranteed to each agent, potentially by actively collecting more data or using transfer learning to ensure the model better fits local data. However, to our knowledge, there has not yet been work that systematically looks at the participation questions inherent in federated learning through the lens of game theory — especially the theory of hedonic games, which studies the formation of self-sustaining coalitions.

In a hedonic game, players are grouped together into clusters or coalitions: the overall collection of coalitions is called a coalition structure. Each player’s utility depends solely on the identity of the other players in its coalition. A common question in hedonic games is the stability of a coalition structure. A coalition structure $\Pi$ is core-stable (or “in the core”) if there does not exist a coalition $C$ so that every player in $C$ prefers $C$ to its coalition in $\Pi$. A coalition structure is strictly core stable if there does not exist a coalition $C$ so that every player in $C$ weakly prefers $C$ to its coalition in $\Pi$, and at least one player $\in C$ strictly prefers $C$ to $\Pi$. A coalition structure is individually stable if there does not exist a coalition $C\in\Pi$ so that a player $i\not\in C$ prefers $C\cup\{i\}$ to its arrangement in $\Pi$ and all players in $C$ weakly prefer $C\cup\{i\}$ to $C$ (Bogomolnaia and Jackson 2002).

To explain the analogy of federated learning to hedonic games, we first consider that each agent in federated learning is a player in a hedonic game. A player is in coalition with other players if it is federating with them. Its cost is its expected error in a given federating cluster, which depends only on the identity of other players in its federating cluster. Players are assumed to be able to move between federating clusters only if doing so would benefit itself and not harm other players in the cluster it is moving to: notably, we allow players to freely leave a cluster, even if doing so would harm the players in the cluster it leaves behind.

To motivate our problem and clarify the types of analyses we will be exploring, we will first work through a simple mean estimation example. (The Github repository contains numerical calculations and full tables for this section.) Calculating the error each player can expect requires two parameters: $\mu_{e}$, which reflects the average error each player experiences when sampling data from its own personal distribution, and $\sigma^{2}$, which reflects the average variance in the true parameters between players. In this section we will use $\mu_{e}=10,\sigma^{2}=1$, but will discuss later how to handle when they may be imperfectly known.

First, we will analyze uniform federation, with three players, $a,b,$ and $c$. We will first assume that each player has 5 samples from their local data distribution: Table 1 gives the error each player can expect in this situation. Arrangements equivalent up to renaming of players are omitted. Every player sees its error minimized in the “grand coalition” $\pi_{g}$ where all three players are federating together. This implies that the only arrangement that is stable (core-stable or individually stable) is $\pi_{g}$.

Next, we assume that player $c$ increases the amount of samples it has from 5 to 25: Table 2 demonstrates the error each player can expect in this situation. Here, the players have different preferences over which arrangement they would most prefer. The “small” players $a$ and $b$ would most prefer $\{a,b\}\{c\}$, whereas the “large” player $c$ would most prefer $\{a\},\{b,c\}$ or (identically) $\{b\},\{a,c\}$. However out of all of these coalition structures, only $\{a,b\},\{c\}$ is stable (either core stable or individually stable). Note that $\{a\},\{b,c\}$ is not stable because the coalition $C=\{a,b\}$ is one where each player prefers $C$ to its current situation.

Thirdly, we will assume that all three players have 25 samples: this example is shown in Table 3. As in Table 1, the players have identical preferences. However, in this case, the players minimize their error by being alone. Overall, stability results from this example are part of a broader pattern we will analyze in later sections.

Next, we will explore the two other methods of federation: coarse-grained and fine-grained. Both offer some degree of personalization, with varying levels of flexibility.

Table 4 shows an example using coarse federation with four players: three have 30 samples each, and the fourth player has 300 samples. We assume the weights $w_{j}$ are set optimally for each player. For conciseness, some columns and rows are omitted. Note that both player types get lower error in $\pi_{g}$ than they would with local learning: that is, $\pi_{g}$ is individually stable (stable against defections of any player alone). However, it is also clear that $\pi_{g}$ is not core stable: in particular, the three small players would get lower error in $\{a,b,c\}$ than in $\pi_{g}$. These results will be examined theoretically in later sections: with optimal weighting, coarse-grained federation will always have an individually stable $\pi_{g}$ that is not necessarily core stable.

Finally, we examine fine-grained federation. Table 5 analyzes the same case as coarse-grained federation previously, but with optimally-weighted fine-grained federation. The full error table shows that $\pi_{g}$ is core stable because each player minimizes their error in this arrangement. This result will hold theoretically: when optimal fine-grained federation is used, $\pi_{g}$ always minimizes error for every player and is thus core stable.

In later sections we will give theoretical results that explain this example more fully, but understanding the core-stable partitions here will help to build intuition for more general results.

This paper’s first contribution is to derive exact expected values for the MSE of players under different situations. The fact that these values are exact allows us to precisely reason about each player’s incentives in later sections. We will state the theorems here and provide the proofs in Appendix B.

The approach for this section was first to derive expected MSE values for the most general case and then derive values for other cases as corollaries. The most general case is linear regression with fine-trained federation. First, we note that we can derive coarse-grained or uniform federation by setting the $v_{ji}$ weights to the appropriate values. Next, we note that mean estimation is a special case of linear regression. For intuition, consider a model where a player draws an $x$ value that is deterministically 1, then multiplies it by an unknown single parameter $\theta_{j}$, then then takes a measurement $y$ of this mean with noise $\epsilon^{2}_{j}$. This corresponds exactly to the mean estimation case, where a player has a true mean $\theta_{j}$ and observes $y$ as a sample, with noise $\epsilon^{2}_{j}$. We can use this representation to simplify the error terms, with more details given in Appendix B.

First, we give the expected MSE for local estimation:

Next, we calculate the expected MSE for fine-grained federation:

Finally, we derive as corollaries the expected MSE for the uniform federation and the coarse-grained case.

The exact MSE for linear regression follows a very similar form to that for mean estimation. In all cases, the bias component (the term involving $\sigma^{2}_{d}$) is in the exact same form and could be directly modified to mean estimation by using $(\sigma^{2})^{\prime}=\sum_{d=1}^{D}\mathbb{E}_{x\sim\mathcal{X}_{j}}[(\bm{x}^{d})^{2}]\cdot\sigma^{2}_{d}$. The variance component (the term involving $\mu_{e}$) fits the exact form of mean estimation in the limit where $n_{j}>>D$. In this case, the error can be modified to fit mean estimation by using $\mu_{e}^{\prime}=D\cdot\mu_{e}$. This approximation is good when there are many more samples than the dimension of the linear regression problem under investigation: for most cases of model fitting, this assumption is reasonable.

For the rest of the paper, we will use the $n_{j}>>D$ assumption: consequentially, all of our results apply equally to linear regression and mean estimation.

In this section, we analyze the stability of coalition structures in the case that uniform federation is used. We consider two cases: 1) where all players have the same number of datapoints $n$ and 2) where all players have either a “small” or “large” number of points. We will use $\pi_{l}$ to refer to the coalition partition where all players are alone and $\pi_{g}$ to refer to the grand coalition. Proofs from this section are given in Appendix C.

In this section, we analyze coarse-grained federation. As a reminder, in this situation, each player has a parameter $w_{j}$ that it uses to weight the global model with its own local model.

for $w_{j}\in[0,1]$. All proofs from this section are given in Appendix D.

Note that the $w_{j}$ value is a parameter that each player can set independently. The lemma below analyzes the optimal value of $w_{j}$ and tells us that each player would prefer federation, in some form, to being alone.

Specifically, this means that no player wishes to unilaterally deviate from $\pi_{g}$. However, this does not mean that each player prefers the grand coalition $\pi_{g}$ to some other federating coalition. For example, refer to Section 2 for an example where the grand coalition $\pi_{g}$ is not core stable.

In the rest of this section, we will analyze the stability of coalition structures in the that the $w$ parameters are set optimally (optimal coarse-grained federation). First, we will find it useful to get the closed-form value for expected MSE of a player using optimal coarse-grained federation:

In this section, we analyze fine-grained federation. As a reminder, with this method, each player $j$ as a vector of weights $\bm{v}_{j}$ that they use to weight every other player’s contribution to their estimate.

for $\sum_{i=1}^{M}v_{ji}=1$.

We calculate the optimal $\bm{v}$ weights for player $j$’s error.

The proof of this lemma is given in Appendix E.

From this analysis, a few properties become clear. To start with, $v_{jj}$ and $v_{jk}$ are always strictly between 0 and 1. This implies the following lemma:

Similarly, the fact that $\pi_{g}$ is optimal for every player implies that it is in the core, and that it is the only element in the core.

In this work, we have drawn a connection between a simple model of federated learning and the game theoretic tool of hedonic games. We used this tool to examine stable partitions of the space for two variants of the game. In service of this analysis, we computed exact error values for mean estimation and linear regression, as well as for three different variations of federation.

We believe that this framework is a simple and useful tool for analyzing the incentives of multiple self-interested agents in a learning environment. There are many fascinating extensions. For example, completely characterizing the core (including whether it is always non-empty) in the case of arbitrary number of samples $\{n_{i}\}$ is an obvious area of investigation. Besides this, it could be interesting to compute exact or approximate error values for cases beyond mean estimation and linear regression.