Optimality and Stability in Federated Learning: A Game-theoretic
  Approach
  Federated learning is a distributed learning paradigm where multiple agents,
each only with access to local data, jointly learn a global model. There has
recently been an explosion of research aiming not only to improve the accuracy
rates of federated learning, but also provide certain guarantees around social
good properties such as total error. One branch of this research has taken a
game-theoretic approach, and in particular, prior work has viewed federated
learning as a hedonic game, where error-minimizing players arrange themselves
into federating coalitions. This past work proves the existence of stable
coalition partitions, but leaves open a wide range of questions, including how
far from optimal these stable solutions are. In this work, we motivate and
define a notion of optimality given by the average error rates among federating
agents (players). First, we provide and prove the correctness of an efficient
algorithm to calculate an optimal (error minimizing) arrangement of players.
Next, we analyze the relationship between the stability and optimality of an
arrangement. First, we show that for some regions of parameter space, all
stable arrangements are optimal (Price of Anarchy equal to 1). However, we show
this is not true for all settings: there exist examples of stable arrangements
with higher cost than optimal (Price of Anarchy greater than 1). Finally, we
give the first constant-factor bound on the performance gap between stability
and optimality, proving that the total error of the worst stable solution can
be no higher than 9 times the total error of an optimal solution (Price of
Anarchy bound of 9).
