Incentives in Federated Learning with Heterogeneous Agents

Ariel D. Procaccia, Han Shao, Itai Shapira

TL;DR

Federated learning often suffers from free-riding because contributing data is costly, while the resulting global model benefits everyone. This paper introduces a game-theoretic framework for heterogeneous data, where an agent's utility depends on exactly who supplies each sample, not just the total count. The authors show that while uncoordinated play fails badly, a central planner can use a novel linear programming approximation paired with a "pay-what-you-contribute" payment scheme to achieve a strategy-proof, near-optimal collaboration.

What Problem Does This Paper Address?

Federated Learning (FL) allows multiple participants (such as hospitals or mobile devices) to collaboratively train a shared machine learning model without centralizing their raw data. However, collecting, curating, and engineering data incurs real costs for the contributors. Because the final global model is a non-excludable public good, participants face a classic free-rider dilemma: everyone wants to benefit from a highly accurate model, but no one wants to shoulder the cost of providing the training data.

Prior game-theoretic analyses of incentives in FL typically assumed that data is homogeneous (or exchangeable), meaning a sample from one agent is perfectly substitutable for a sample from another. In reality, real-world FL clients face highly heterogeneous data distributions and primarily care about how well the model performs on their local distribution. This paper addresses the challenge of designing incentive mechanisms that coax self-interested, heterogeneously distributed agents into pooling enough data to meet strict PAC (Probably Approximately Correct) accuracy targets at a minimal total cost to the federation.

Methods

The authors model federated learning as a strategic game where each agent selects a data contribution level to maximize a quasi-linear utility function. This function trades off a binary payoff (achieving a local PAC accuracy threshold) against a linear per-sample cost.

To solve the incentive and efficiency problems, the paper introduces several key components:

  1. Hardness Analysis: The authors prove that finding the absolute cost-minimizing data allocation across heterogeneous agents is NP-hard via a reduction from the classic Set Cover problem.
  2. Linear Programming (LP) Approximation: To bypass this computational barrier, they convert the PAC constraints into a log-linear form. For finite hypothesis classes, this yields an efficient LP that provides a logarithmic approximation of the optimal social cost. For infinite hypothesis classes, they apply a standard $\gamma$-cover technique to maintain tractability.
  3. Mechanism Design: When agents' data distributions are private information, a mechanism must incentivize truthful reporting. The authors pair their LP allocation rule with a Pay-What-You-Contribute (PWYC) payment scheme. This rule compensates each agent exactly for their data contribution cost plus an agent-specific constant ($p_i = c_i m_i + C_i$).

Datasets

The authors empirically validate their modeling assumptions and algorithms using the LEAF benchmark, focusing on two naturally partitioned federated datasets:

  • FEMNIST: An extended MNIST dataset of handwritten characters partitioned by writer to simulate heterogeneous image classification.
  • Shakespeare: Text data built from The Complete Works of William Shakespeare, partitioned by speaking roles to simulate heterogeneous next-character prediction tasks.

Key Insights and Ideas

  • Data is Not Exchangeable: The paper empirically demonstrates that an agent's test loss decreases monotonically as the fraction of training data coming from its own distribution increases. This confirms that who contributes data matters just as much as how much data is contributed.
Test loss on FEMNIST demonstrating non-exchangeable data distributions.
  • The Catastrophe of Decentralization: Without central coordination, pure Nash equilibria may not even exist. When they do exist, the Price of Stability can be unbounded ($\Omega(\log(1/\epsilon))$), meaning uncoordinated play can be catastrophically more expensive than full cooperation.
  • Algorithmic Slack Enables Truthfulness: The uniqueness and strategy-proofness of the PWYC mechanism rely on a property called local obliviousness. Because the LP approximation algorithm possesses a small amount of "slack" around its optimal allocations, minor misreports of data distributions by an agent do not alter the final computed sample requirements, completely neutralizing the incentive to lie.

Key Results

  • Theoretical Bounds: For any finite hypothesis class $\mathcal{H}$, the proposed LP allocation achieves a $\frac{\log(1/\delta) + \log |\mathcal{H}|}{\log(1/\delta)}$-approximation of the social optimum.
  • Uniqueness of PWYC: The authors prove that within the class of contribution-based transfers, the PWYC mechanism is the only one that guarantees strategy-proofness when paired with their locally oblivious approximation algorithm.
  • Empirical Tightness: When tested on a finite hypothesis class derived from FEMNIST, the LP allocation's empirical cost ratio ($r$) relative to the true discrete optimum ranged tightly between 1.67 and 4.24 across various hypothesis class sizes, validating the theoretical logarithmic approximation factor.

Limitations and Future Work

  • Centralized ERM as an Upper Bound: The framework uses centralized Empirical Risk Minimization (ERM) on a pooled dataset as a theoretical benchmark to define the PAC constraints. While standard in FL theory, this abstracts away the actual distributed optimization dynamics (such as local updates in FedAvg) and communication constraints.
  • Strict Binary Thresholds: The primary utility model relies on a strict binary threshold (the goal is either met or not). Although the authors use a Lagrangian argument to show this is dual to optimizing smooth, continuous accuracy-benefit curves, directly incorporating continuous, non-linear reward functions into the mechanism design remains an open avenue.
  • Linear Cost Assumptions: The main mechanism assumes linear per-sample costs. While the authors outline how convex cost functions can transform the LP into a tractable convex program, the full strategic implications under private convex costs were not deeply explored.

Summary updated

Abstract

Federated learning promises significant sample-efficiency gains by pooling data across multiple agents, yet incentive misalignment is an obstacle: each update is costly to the contributor but boosts every participant. We introduce a game-theoretic framework that captures heterogeneous data: an agent's utility depends on who supplies each sample, not just how many. Agents aim to meet a PAC-style accuracy threshold at minimal personal cost. We show that uncoordinated play yields pathologies: pure equilibria may not exist, and the best equilibrium can be arbitrarily more costly than cooperation. To steer collaboration, we analyze the cost-minimizing contribution vector, prove that computing it is NP-hard, and derive a polynomial-time linear program that achieves a logarithmic approximation. Finally, pairing the LP with a simple pay what you contribute rule, where each agent receives a payment equal to its sample cost, yields a mechanism that is strategy-proof and, within the class of contribution-based transfers, is unique.
BibTeX
@inproceedings{procaccia2026incentives,
  author = {Ariel D. Procaccia and Han Shao and Itai Shapira},
  title = {{Incentives in Federated Learning with Heterogeneous Agents}},
  booktitle = {International Conference on Learning Representations},
  year = {2026},
  url = {https://openreview.net/forum?id=Nqjyrvh3pf},
}
Figure