One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning

1 Introduction

• Stable equilibrium rules out unilateral burden reductions, while envy-free equilibrium rules out beneficial swaps with a lower-contribution agent.The paper presents these notions as a way to avoid inequities and support continued participation.Source: §1 · pp. 1–2
• Stable equilibria may not exist for PAC learning, while they exist under mild assumptions for random discovery and random coverage; equal-contribution envy-free equilibria trivially exist.Source: §1 · p. 2
• Equilibrium sample complexity can be a factor Ω(k) larger than socially optimal sample complexity for stable or envy-free equilibria with k agents.The gap is shown for random discovery and random coverage examples.Source: §1 · p. 2
• For linear utilities, every optimal stable equilibrium has a core set that is socially optimal, while agents outside it contribute zero; some equilibria can be computed with linear or convex programs.Source: §1 · p. 2
• FedAvg allocations can leave many agents preferring to reduce their contribution to between 25% and 1%, while MW-FED allocations are closer to equilibrium.The paper says further work is needed to close the remaining gap.Source: §1 · p. 2

1.1 Related Work.

• Prior federated-learning work studied collaboration and fairness, but the cited frameworks largely did not address agents’ strategic incentives and equilibrium.Source: §1.1 · p. 2

2 Problem Formulation

• Sample complexity is the minimum total sample allocation satisfying every agent’s accuracy constraint, whereas the socially optimal solution ignores agents’ incentives.Source: §2 · p. 3, §2.1 · p. 3
• The socially optimal allocation may burden some agents unfairly, so the formulation asks whether stable and envy-free equilibria exist and how their sample complexities compare with the unconstrained optimum.Source: §2 · p. 3

2.1 The General Framework

• The general framework represents collaboration as agents jointly choosing contribution levels θ and meeting individual utility thresholds μ_i.Source: §2.1 · p. 3
• The model assumes each agent can meet her constraint alone and that utilities are non-decreasing in every agent’s contribution.Source: §2.1 · p. 3
• A stable equilibrium prevents any agent from lowering her contribution while remaining feasible; an envy-free equilibrium prevents a beneficial swap with a lower-contribution agent.Source: §2.1 · p. 3
• Price of Stability and Price of Fairness compare the resource cost of the optimal stable or envy-free equilibrium, respectively, with the socially optimal cost.Source: §2.1 · p. 3

2.2 Canonical Examples and Settings

• The canonical settings include linear utilities u(θ)=Wθ, where W_ij captures how agent j’s effort affects agent i’s utility, and random coverage, where utility depends on whether an instance has been observed.Source: §2.2 · p. 4
• The paper also considers general PAC learning, where dependencies among labels can let observations improve classification on unobserved points; random coverage uses randomized rounding to interpret real-valued contributions.Source: §2.2 · p. 4

3 Existence of Equilibria

• An envy-free allocation always exists, but it need not be an equilibrium; equilibrium existence depends on utility behavior and may fail in general PAC learning.Source: §3 · pp. 4–5

3.1 Are Canonical Examples Well-behaved?

• Linear utilities are well-behaved, and random-coverage utilities are well-behaved under a positive marginal-utility condition; continuity matters because integer strategies break the derivative-based conditions.Source: §3.1 · p. 5

3.2 Proof of Theorem 2

• The existence proof defines each agent’s best response as her minimum contribution meeting her constraint, then establishes a fixed point, which is an equilibrium.Source: §3.2 · p. 5

3.3 Proof of Theorem 3

• A general-PAC example with integral strategies has no stable equilibrium: every feasible allocation lets an agent reduce her contribution and retain her accuracy constraint.Source: §3.3 · p. 6

• Price of Stability and Price of Fairness are at least Ω(k) in well-behaved examples of random coverage and linear utilities.Source: §4 · p. 6
• In random coverage, optimal collaboration loads the overlapping core heavily, but equilibrium constraints keep it from carrying more samples than another agent, forcing other agents to do most of the work.The tradeoff between sampling efficiency and an easily satisfied constraint yields a large Price of Stability and Price of Fairness.Source: §4 · pp. 6–7

5.1 Algorithms for Linear Utility

• For linear utilities, a convex program computes an optimal stable equilibrium when W is PSD.The stable-equilibrium constraints restrict the feasible set of the linear program; the resulting last inequality is convex under the PSD condition.Source: §5.1 · p. 7

5.2 Structure of Equilibria for Linear Utility

• An optimal stable equilibrium is socially optimal for its contributing agents, and any socially optimal solution for that subset can be zero-padded into an optimal stable equilibrium for all agents.When all agents contribute positively, the equilibrium is socially optimal; for diagonally dominant matrices, the price of stability is 1.Source: §5.2 · p. 7
• When W is diagonally dominant, every agent contributes positively in equilibrium; more generally, if W_ij < W_ii for all i,j, every stable equilibrium is also envy-free.The section connects these properties to stable equilibria that are socially optimal for a subset, and in some cases all, agents.Source: §5.2 · pp. 7–8

5.3 Coverage Utilities

• Random-coverage stable and envy-free feasible sets can be non-convex, so optimizing over either set is intractable.The stable-set example uses two stable strategies whose average is not even feasible; for envy-free equilibria, a convex combination of equilibria from different perfect matchings can fail envy-freeness.Source: §5.3 · p. 8

Experimental setup

• The experiment uses the balanced EMNIST split, assigning each agent 1,600 training points and 400 validation points from a 2,000-point mixture.Contribution is the fraction of the 1,600 training points used; training targets 70% accuracy after 40 epochs of pretraining to 55%.Source: §6 · p. 9
• In non-federated runs, easier distributions reach the threshold more quickly, while harder distributions take nearly three times as long.Figure 1 averages 100 individual runs per distribution; the federated experiment uses four populations, two harder and two easier.Source: Figure 1 · p. 9, §6 · p. 9

Results

• MW-FED reduces an agent's contribution after that agent meets its constraint, whereas FedAvg does not distinguish agents' differing needs.MW-FED adjusts sample contributions across rounds; the experiment evaluates whether an agent can unilaterally lower its contribution and still attain 70% validation accuracy.Source: §6 · pp. 8–9
• At a 25% contribution after ten epochs, 94% of FedAvg agents but 45% of MW-FED agents still met the accuracy threshold.Figure 2 compares the likelihood of a single defector reaching its threshold at different contribution levels; MW-FED allocations are closer to equilibrium than FedAvg's.Source: Figure 2 · p. 9, §6 · p. 10

7 Conclusion

• The paper frames its game-theoretic framework and results as an initial step toward equitable protocols that can recruit and retain many participants.The conclusion links participant recruitment and retention to protocols that account for agent incentives.Source: §7 · p. 10

A Real-Valued Strategies

• For random-coverage and general PAC utilities, a real-valued strategy is interpreted by randomized rounding to neighboring integer sample counts, with utility averaged over the resulting strategies.The rounding draws the floor or ceiling of the strategy according to its fractional part.Source: A Real-Valued Strategies · p. 12

B Calculation of Well-behaved Property

• General PAC utilities need not be well-behaved on the full strategy space, though the example is well-behaved on [0,C]^3 for any C < 1.The example is ill-behaved on [0,1]^3 because an agent's utility derivative with respect to its own strategy is zero when another agent's strategy is 1.Source: B Calculation of Well-behaved Property · p. 13

C Proof of Lemma 1

• The proof establishes equilibrium existence by showing the best-response map has a fixed point using Brouwer's theorem and continuity of that map.Well-behaved utilities ensure small changes in other agents' contributions require only small adjustments to an agent's own contribution.Source: C Proof of Lemma 1 · p. 13

D More General Construction for Theorem 3

• The construction uses three agents with randomized distributions over a domain of size 6d, with independent binary variables determining their instance-label pairs.Each agent's marginal support consists of d instances, and neighboring agents' labels are coupled to the preceding distribution's support.Source: D More General Construction for… · p. 14
• For an odd m(µ), agent i meets its constraint when θ_i + θ_(i⊖1) ≥ m(µ), and any excess of at least one sample permits a unilateral reduction.The construction selects µ in (1/2,1) so that m(µ) is odd.Source: D More General Construction for… · p. 14
• No stable equilibrium exists over Θ = N^3 because the equilibrium conditions would force all three integral contributions equal, which is impossible when m(µ) is odd.The sample-count equations require each adjacent pair to sum to m(µ).Source: D More General Construction for… · p. 14

Construction

• The construction has one core agent with central points and k−1 petal agents whose instance sets intersect the core’s set.The two settings considered are random coverage and linear utilities.Source: E Proof of Theorem 4 · p. 14

Random coverage

• In random coverage, an optimal envy-free solution uses Ω(k) samples and has Price of Fairness at least Ω(√k).Symmetry forces equal sampling among petal agents, while the core agent cannot sample more than the others.Source: E Proof of Theorem 4 · pp. 15–16
• In random coverage, every stable equilibrium gives all petal agents equal contributions and the core agent zero samples; the optimal stable equilibrium uses Ω(k) samples.The proof derives a constant-order lower bound on each petal contribution.Source: E Proof of Theorem 4 · p. 16

Linear utilities

• In the linear-utility example, envy-free solutions equalize petal contributions and require the core agent to sample no more than any petal agent.The proof also derives an Ω(k) lower bound on envy-free sample complexity.Source: E Proof of Theorem 4 · pp. 16–17
• In the linear-utility example, an optimal stable equilibrium gives the core agent zero samples and requires at least b^2 samples overall.The proof states that this yields a Price of Stability lower bound, but the bound’s final expression is truncated in the supplied passage.Source: E Proof of Theorem 4 · p. 17

Theorem 6

• An optimal stable equilibrium for symmetric positive-semidefinite linear utilities is socially optimal for its contributing agents.The theorem also states that extending any socially optimal solution for those agents with zeros for non-contributors yields an optimal stable equilibrium for all agents.Source: F Proofs of Theorem 6 and Corollary 1 · p. 18
• The non-contributing agents are exactly those assigned zero samples in the optimal stable equilibrium.The proof characterizes the equilibrium through the program minimizing total samples subject to Wθ ≥ μ1 and θ ≥ 0.Source: F Proofs of Theorem 6 and Corollary 1 · pp. 17–18

Corollary 1

• If an optimal equilibrium has positive contributions, it is socially optimal.Source: F Proofs of Theorem 6 and Corollary 1 · p. 18

G Proof of Theorem 7

• When Wii > Wij for all agents i,j, every stable equilibrium is also envy-free.Source: G Proof of Theorem 7 · p. 18

H Structure of Equilibria in Random Coverage

• Random-coverage utilities can be non-concave, and the set of stable equilibria can be non-convex.Source: H Structure of Equilibria in Random… · p. 19, §H.1 · p. 19

H.1 Proof of Theorem 8 +

• With two agents uniformly distributed over {0,1}, both single-agent contribution strategies are stable, while their convex combinations are infeasible.Source: §H.1 · p. 19

H.2 Proof of Theorem 9 +

• The envy-free feasible set can be non-convex in random coverage, as shown by a four-vertex complete-graph example with agents on edges.Perfect-matching strategies are envy-free, but a convex combination of two such strategies is not.Source: §H.2 · pp. 19–20

I.1 Dataset

• The EMNIST experiment uses 60,000 sampled points for training and federated validation, 30,000 for pre-training, and 31,600 for pre-training validation.The classification task has 47 classes, and top-1 accuracy is the performance metric.Source: §I.1 · p. 20

I.2 Learning model

• The learning setup uses a four-layer neural network, Adam, dropout, and 40 epochs of pre-training to approximately 55% accuracy.Source: §I.2 · p. 21
• Hyperparameters are selected by randomized search over learning rates from 1e−06 to 1e−02 and six batch sizes, sampled 40 times.The selected individual-learning parameters are translated for the federated algorithms.Source: §I.2 · p. 21
• FedAvg samples each population per iteration, while MW-FED adjusts clients’ sample allocations using contribution weights.Source: §I.2 · pp. 21–22

I.3 Encouraging heterogeneity across agent datasets

• Across 10,000 trials, the authors ranked samples by iterations to reach 60% accuracy and built agents from mixtures of the easiest and hardest examples.Trials sampled 1,000 points, trained with batch size 16 to cross-entropy loss 0.5, and recorded a mean of 286 iterations (standard deviation 21.6; range 235–670 batches). These iteration counts cannot be directly compared with other section statistics because batch size differs.Source: §I.3 · p. 22
• The iteration-to-accuracy measure is an imperfect difficulty proxy, but it produced observable heterogeneity where output entropy often did not.Source: §I.3 · p. 22
• Four populations used 100% difficult, 90% difficult, 90% easier, or 100% easy samples, and their averaged training runs were distinct over repeated regimes.The paper describes the populations as having similar but not identical objectives.Source: §I.3 · p. 22
• At 1,600 training points, using half or fewer of an agent’s unique data points generally does not lead to success.In the non-federated setting, agents can reduce their contributions only very little and still hope to be successful.Source: §I.3 · p. 22, Figure 5 · p. 23

I.4 Connections with algorithms in prior work

• Algorithm 2 follows multiplicative-weights approaches in Blum et al. (2017), Chen et al. (2018), and Nguyen and Zakynthinou (2018): sample weighted distributions, test each, then up-weight those below threshold.Source: §I.4 · p. 23
• In the linear setting, a convex program finds a minimum-cost equilibrium, while LP 1 finds an equilibrium when there are no 0-contributors.The paper relates packing-LP solution strategies to Plotkin et al. (1995) and Arora et al. (2012).Source: §I.4 · p. 23

I.5 Source code

• The paper’s code is available in an anonymized repository.Source: §I.5 · p. 23

I.6 Computing infrastructure

• The experiments ran on an NVIDIA V100 Tensor Core GPU.Source: §I.6 · p. 23