{"ID":2866228,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.21612","arxiv_id":"2509.21612","title":"Incentives in Federated Learning with Heterogeneous Agents","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.","short_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 o...","url_abs":"https://arxiv.org/abs/2509.21612","url_pdf":"https://arxiv.org/pdf/2509.21612v2","authors":"[\"Ariel D. Procaccia\",\"Han Shao\",\"Itai Shapira\"]","published":"2025-09-25T21:28:13Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}