Incentives in Federated Learning with Heterogeneous Agents
Authors: Ariel D. Procaccia
Han Shao
Itai Shapira
Venue: ICLR 2026 Poster (2026)
Keywords: federated learning
incentives
mechanism design
PAC learning
sample complexity
approximation algorithms
strategyproofness
price of stability
Primary area: learning theory
TL;DR: We model incentives in heterogeneous-data FL, show equilibria can be arbitrarily costly, prove optimal allocation is NP-hard, give a logarithmic LP approximation, and design a strategy-proof pay-what-you-contribute mechanism.

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—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.

Published as a conference paper at ICLR 2026
INCENTIVES IN FEDERATED LEARNING WITH HET- EROGENEOUS AGENTS
Ariel D. Procaccia Harvard University
Han Shao
Itai Shapira" Harvard University
University of Maryland, College Park
ABSTRACT
Federated learning promises significant sample-efficiency gains by pooling data across multiple agents, yet incentive misalignment is an obstacle: each update is costly the contributor but boosts every participant. We introduce a game- theoretic framework that captures heterogeneous data: an agent's ss utility depends on who supplies each sample, not just how many. Agents aim to meet 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 NP-hard, and derive volynomial-time lincar program that achieves logarithmic approxima- rule-each
tion. Finally, pairing the LP with a simple may-what-you--ontrbbe agent receives payment equal to its sample cost cost-yields mechanism that is strategy-pret proof and, within the class of contribution-based transfers, is unique.
INTRODUCTION
Federated learning (FL) is collaborative training framework in which multiple agents-eaa hold- ing a distinct dataset-jointly optimize a global model while keeping data local. Collaboration allows agents to tap into information spread across heterogeneous records- for example, net- work of hospitals pooling imaging data from distinct patient demographics to detect rare conditions sooner. Although each agent could independently train model, collaboration offers higher aceu- racy or comparable performance with significantly fewer examples (Blum et al., 2017), enhancing both individual and federation-wide welfare.
However, realizing these gains hinges on incentives. Contributing model updates incurs costs in compute, bandwidth, curation effort, and privacy risk, while the global model produced by collec- tive learning is non-ex con-exxludable public good: once trained, every agent benefits from its accuracy regardless of individual effort. This asymmetry invites a classic free-rider dilemma (Yang et al., 2015; Ahmed & Choi, 2023; Karimireddy et al., 2022): as one agent's data lifts others' accuracy while the contributor alone incurs the cost, each participant tempted to trim share once own target is met. The resulting free-riding slows training and can ultimately exhaust the data pool that makes FL viable.
Consequently, federated learning can be viewed strategic game: each agent picks a contribu- tion level to maximize a private utility that trades its own labeling cost against the benefit of the joint model. Existing models of incentives in federated learning either assume each agent's 's utility depends on the local labeled data distributions all agents (Blum et al., 2021), 1), or treat agents as homogeneous, which crucially implies that data exchangeable and each agent's utility depends solely on the total amount of data contributed across all agents (Karimireddy et al., 2022; Murhekar al., 2024).
However, in typical federated learning scenarios, agents face heterogeneous data distributions and are primarily interested in improving performance on their own local distribution. This phe- nomenon- local data typically yielding greater marginal utility for local performance than data
"Authors listed alphahetically. Correspondence to: Itai Shapira taa shapi ra@g ha harvard.edu. Han Shao: Work mostly done while Harvard University.

---

Published as a conference paper at ICLR 2026
Test Loss on Agent 1's Data
Data
300
Data
1.0-
0.25
0.75
0.0
0.25
0.5
0.75
1.0
0.0
0.25
0.5
0.75
1.0
Fraction of samples from Agent
Figure 1: An agent's expected loss falls as a larger share of a fixed training set comes from their own distribution. With a budget of m data points, we sample Am from Agent I and (1 A)m from Agent 2 on FEMNIST (Caldas et al., 2018), train classifier, and repeat 100 times. For each m, Agent I's loss decreases monotonically who contributes. Full details in Appendix A.1.
X, confirming that data are not exchangeable- utiliiis depend on
from other agents has been well documented in the personalization and domain adaptation litera- ture (Ben-David et al., 2006; Bhunia et al., 2021; Hsu et al., 2019), and we empirically confirm that is present in federated learning, as shown in Figure We therefore model utilities that depend on who supplies each sample, not just how many.
In this work we ask: how can incentives be aligned in this heterogeneous game? We adopt a PAC accuracy objective-each agent wants their test error below with confidence 1 1 5-and study the game induced by this objective. Left on their own, agents settle into a contribution equilibrium that can be inefficient: some agents free-ride, others overspend, and total cost explode relative to full cooperation. The central challenge is therefore to design contribution and transfer rules that coax self-interester heterogeneously distributed agents into pooling enough data that each meets its own accuracy target on its own distribution, while keeping the federation's 's total cost near minimal.
Our Results. Section 2 builds data-heterogennouu FL game with PAC thresholds: an agent's utility depends on who supplies the samples, not just how many. Section 3 shows that decentralized play can fail badly- Nash equilibria may not exist and, when they do, their total cost can exceed the cooperative optimum by an unbounded factor (Price of Stability + oc). Motivated by this gap, Section 4 assumes planner with full information and full control. We prove that computing the cost-minimizing contribution vector is NP-hard (Theorem 2). Nonetheless, the PAC constraints admit a linear program (LP) whose cost within a logarithmic factor of the optimum (Theorem 3); use this LP allocation the foundation of the mechanism design that follows. Section drops the full-information assumption: agents now report private distributions. Pairing the LP allocation with simple pay-what-yoo you-hoo-ou- rule each agent receives a payment equal its sample cost cost-yields a mechanism that is strategyproof, and we derive conditions under which it uniquely satisfies these properties. Finally, while our main contributions theoretical, we complement them with empirical validation and illustrative simulations in Appendix A that demonstrate the practical relevance of our assumptions and algorithms.
Related Work. Early work in FL centered on communication-effien optimization and fairness under fully cooperative, i.i.d. average-loss assumptions, with no pricing of data or modeling of strategic behavior. For instance, FedAvg optimizes average loss, while Agnostic FL and q-FFL reweight loss for worst-case or fairness gains, all assuming truthful reports (McMahan et al., 2017: Mohri et al., 2019; Li et al., 2020). Blum et al. (2017) introduced collaborative PAC model and showed that pooling across ie heterogeneous tasks cuts sample complexity by Ö(log k), but partici- pation is mandatory and incentives are ignored.
Subsequent work introduced incentives but frequently assumed that agents' data exchangeable, so that model accuracy depends only on the total sample count contributed across all participants. Under this framework, various incentive strategies-sus as transfer payments reputational
2

---

Published as a conference paper at ICLR 2026
been proposed to combat free-riding. For example, Karimireddy et al. (2022) tie each agent's model quality to its data contribution (no external payments), whereas Murhekar et al. (2024) design budget-balanced monetary transfers that implement welfare-maximizing equilibria; and (Lin et al., 2019; Kang et al., 2019; Sarikaya & Ercetin, 2019; Ding et al., 2020; Fraboni et al., 2021) rely reputation mechanisms and credit sharing. These designs treat data as interchange- able: model quality depends solely on the total sample count, so the marginal value of each sample ignores who provides it, overlooking realistic heterogeneity across data distributions.
A separate line of work studies heterogeneous data, aiming to capture how collaboration might form among agents with distinct interests. Donahue & Kleinberg (2021), and Hasan (2021) analyze coalition and Nash stability in model-sharing games and show that agents split into sub-coalin coalitions when a global model biases some distributions. Blum et al. (2021) further show that in a personal- ized PAC game with distribution-speciin payoffs, pure Nash equilibria may not exist, and when they do, they can be arbitrarily inefficient, underscoring the fragility of cooperation absent incentives. These game-theoretic models emphasize that heterogeneity can severely complicate collaboration: individual incentives may fail to align with socially optimal pooling of data. Our work extends these papers by introducing concrete utility model based on PAC-style threshold guarantees where each agent requires that the global model meet a iatributiio-specifii accuracy threshold with high confidence.
Recent studies tackle truthfulness under heterogeneity: peer-prediction payments (Pang et al., 2022), budget-balanced truthful gradient schemes (Chakarov et al., 2024), and optimal truthful mechanism for data sharing with interdependent valuations (Chen et al., 2022); yet none compute minimum-cost allocations that meet each agent's welfare target.
MODEL
2.1 SETUP AND LEARNING PROTOCOL
We now make the collaborative game precise. Each agent selects how many examples contribute; the federation pools these examples, trains a model, and each agent then evaluates the model on its own data distribution.
Agents and data. Consider k agents AA = fl,..... .)) k} who wish to jointly learn a shared predictor but individually decide how much data to contribute. Let X' denote the instance space and y the label space. A hypothesis a function h : X - y mapping instances to predicted labels. Fix hypothesis class H with VC dimension d, and assume agents seek to approximate an unknown target function ht E H. Each agent i E A has access to a local marginal data distribution D; over X' and can query labels for any data point drawn from this distribution. The collaborative learning process involves two stages:
Stage - Sample Collection. Each agent i chooses contribution level m, draws an i.i.d. unlabeled dataset Ug ~ D and queries the true labels of these samples, which are determined by the target function ht. The labeled sets are pooled into dataset
S = (t),
iEA
Denote by P(D. m. hn) the distribution of this dataset, which is determined by the marginal data distributions D (Di...., the contribution profile m (m....., m&), and h*.
Stage 2 Model Training.
A central server trains a model using Empirical Risk Minimization
(ERM) method:
ERM(S) (h H eer min enrs()))} MER
3

---

Published as a conference paper at ICLR 2026
where (h) is the empirical error of hypothesis h on dataset S.! For any hypothesis h, marginal data distribution D, and target function h", the generalization error is defined as
errD, (h) = PN-D (h(x) + (x))))
Given labeled training set S, we define the generalization error of running ERM over S relative to (D, h*) as:
ERM D
(S) = max CmpрA (h),
(I)
hEBRM(S)
reflect the generalization performance of empirically optimal hypothesis under distribution DD with labeling function h"" That is, if the ERM returns multiple minimizers, we take the worst generalization error, ensuring every bound holds under arbitrary tie-breaking.
Stages and 2 define our collaborative game. Each agent i chooses an integer contribution level my- The server draws m, i.i.d. samples from D; for each agent, pools the labeled data into S, and trains a single global ERM predictor (SS) over H. The next subsection, Section 2.2, specifies the payoffs from this global model and the cost of contributing data.
2.2 PAC ACCURACY OBJECTIVE
Each player ultimately wants a model whose test error on its own distribution low; if collaboration fails, the fallback is to train alone. We focus single, widely-used performance criterion to formalize this goal: a Probably Approximately Correct (PAC) accuracy threshold." In standard agent
realizable PAC learning, error below a tolerance e.? Here we adapt that notion to our federated setting, where (1) the learner uses ERM on the pooled samples and (2) each agent i draws from its own fixed marginal distribution D: We then define the PAC accuracy objective as follows: agent requires that, for every target hypothesis h" H.
probability least (1 - keep its generalization
Pr S~P(D,m. h.)
ERM Di.ke (S) S > 1-
We use af (m) denote a binary variable that is if Equation is satisfied, and otherwise; we refer to this as agent i's (E, reeuurrrentttt or target.
Cost of Contributions. Contributing data incurs costs. Computation, and privacy risk all translate into a per-sample monetary burden. We capture this with linear cost: when agent supplies m; samples, pays c,m,, where & denotes the cost per sample. The parameter & can reflect labeling fees, extra compute, or other participation overhead.
Utility Functions. Each agent balances the model's benefit against the data cost. We normal- ize monetary units so that achieving the PAC goal is worth exactly one unit of payoff, yielding simplified expression for utility:
u. m) a
5.5 (m) c.m.
To ensure every agent's goal is attainable and worth pursuing, we assume self-sufficieccy: every agent could, in the worst case, meet its own accuracy requirement by training on its own data alone. Concretely, let rinnd denote the smallest number of samples that agent would need to label by itself (with no contributions from others) to satisfy the (c, reeeuuirmee on D.- Under PAC accuracy, for all marginal distributions, it holds that
ind 71
O (f d+In(1/8)
where d = VCdim(H), the VC dimension of H.
'I practice, algorithms such as FedAvg (McMahan et al., 2017) only approximate the pooled-ER. solution through local updates and model aggregation, often without accessing raw examples. which remain on users' devices and are never aggregated on the server. In our work. the optimal ERM solution is used as an upper- hound reference point, which lets us abstract away optimization dynamics and focus on incentives and sample complexity. See Section 6 for more discussion.
*Other metrics, such as expected error, can be treated analogously; see Section
'The heterogeneous (different for each agent) case is analogous, discuss in Section 6; present the common-s for clarity.
4

---

Published as a conference paper at ICLR 2026
Assumption 1. 4 m < 1, for every i.
This self- sefficuffic implies that failing to meet the accuracy threshold results in strictly lower utility than meeting it (since an agent can always fall back on solo training to obtain the benefit, albeit at potentially high cost). Therefore, the agent-level decision problem in Equation 3 is to choose m, so as to minimize its own cost c,m, subject to satisfying its (e, -accurayy requirement in Equation 2.
This binary threshold payoff can represent broad class of quasi-linear utility functions, and captures richer behavior than its simple indicator form suggests at first glance. Under regularity assump- tions, Appendix B shows via constrained problem is also optimal for some unconstrained objective that trades off continuous ac- curacy against cost, in particular, there is a multiplier X such that the optimal contribution my that meets the PAC constraint also maximizes a quasi-linear utility that penalizes cost at rate X; Intu- itively, X3 is the agent's s shadow price for accuracy, and the point where our indicator flips from 0 to is exactly where the marginal benefit of additional accuracy falls to this price. Thus the threshold model concise way to capture the saturation behavior of wide family of smooth, monotone, diminishing-retune utilities, rather than an assumption that agents literally have zero value below the target.
gegrrange-uulipiinn argument that any optimal solution to above
Social Cost Optimization. A central planner seeks maximize utilitarian social welfare, namely EisA Ui (m). Under Assumption 1, this welfare objective coincides with minimizing the aggregate labeling cost subject to the same PAC constraints. Thus, from global standpoint, the problem is to find the contribution profile that lets every agent meet its accuracy target at the lowest possible total cost.
min m
s.t. (m)=1 =1 AiEA.
Here m the federation's 's total labeling cost, and the constraint is the PAC guarantee of Equa- tion 2: for every agent and every target hypothesis h", the ERM model must, with probability at least - 6, achieve error at most E on D, The planner therefore seeks the cheapest contribution profile that satisfies all agents' (s, d-reeuuiresmnts simultaneously.
Warm-Up Example. Consider a single agent whose marginal distribution is uniform over the n distinct points æı,.... Fn C X and hypothesis class that contains every possible labeling of those points. When < 1/n, satisfying the PAC accuracy threshold below with probability at least 1 - requires drawing enough samples (with replacement) so that every point appears at least once. With k > 1 agents, we can see how collaboration can improve sample complexity: consider k agents whose distribution places most of its probability mass on different point 2;, while still assigning every other point probability at least By pooling data, agents supply one another with examples they rarely see, allowing each to collect fewer local samples while the group still satisfies the PAC threshold.
THE INEFFICIENCY OF EQUILIBRIA
With the cooperative optimum in hand (Equation 4), we now analyze the uncoordinated game in which each agent strategically chooses its sample size. We quantify the cost gap between equilib- rium behavior and the social optimum and show that Nash equilibrium (NE) can be arbitrarily more costly. This gap motivates central coordination, which we develop next, and it serves as the conceptual starting point for the rest of the paper.
A contribution profile m is a NE if no agent can raise its utility by unilaterally changing its sample count. Since each agent can always fall back to its self-sufficient plan n!! an equilibrium ex- ists only when every accuracy threshold is met; otherwise the under-served agent would deviate to (nind m. to raise its utility. Thus, at equilibrium no agent wants to cut its contribution below the threshold or add extra samples.
is straightforward to show that pure NE may not exist in our framework (Theorem 6). whereas mixed NE always exists (Theorem 5). Even when pure equilibrium exists, it can be highly
5

---

Published as a conference paper at ICLR 2026
To illustrate this, consider simple two-player setting. Let the instance space be X = { dn}. Two players, Alice and Bob, each place most of their probability mass on a different point: for a small E E (0, }
inefficient.
D Dateee (TA)
2E,
D Dalice (TB) 22,
( = 28,
Dnab(Tn)
28.
Under the PAC objective, each agent requires that both points be correctly classified with high probability. If Alice and Bob each contribute one labeled example, then with probability (1 2z)² Alice draws A while Bob draws z. Thus AMil. MiBb) = (1, 1) meets both thresholds at total cost CAlice BBah ( and is optimal. If one free-rides, the other must keep sampling until seeing both points, requiring (1/EE) samples. Since neither player can unilaterally lower this cost, this
profile is an NE with a cost of (2(/E)).
This example shows that some equilibria can be much costlier than the social optimum even though cost-minimal equilibrium exists. How large can the best equilibrium's cost be? We formalize with the Price of Stability (PoS) (Anshelevich et al., 2008): the ratio of total samples in the least-cost equilibrium those in the planner's optimum. PoS captures the cost of decentralization. Even the best self-enforeing outcome can require far more samples than the cooperative minimum. In the following, we show that PoS can be arbitrarily large:
Theorem 1 (PoS is unbounded). For any E (0.1) there exists sequence of instances of our problem in which the ratio of the best NE to the optimal solution approaches (1log(1/e))
CENTRAL COORDINATION WITH FULL INFORMATION
The unbounded price of stability in Section shows that self-directed contribution games may squander resources. A natural fix is to appoint a central planner, such as regulator or platform operator, who can dictate how many labeled examples each agent contributes. Before addressing strategic issues, begin with the technical question of whether the planner can compute the cost- minimizing contribution vector efficiently. (Theorem 2), yet it admits efficient approximation via an LP with logarithmic-type guarantees (Theorem 3). The next section returns to strategy under coordination and builds on this to design payments that align incentives.
this section we show that the problem is NP-hard
To isolate the computational question and remove strategic frictions for now, in this section we grant the planner two powers. First, it has full information-ie observes every marginal distribution D; and each per-sample cost c;. Second, it has complete control- if an agent opts in, the planner can compel supply the prescribed number of samples m., These assumptions fit cases where data statisties are public-e.g. hospital demographics or published mobile-traffic summaries- contractual. With strategic frictions removed, the task now purely computational: who should collect how many samples? We tackle that question here and relax the full- mull-information assumption in Section 5.
participation
4.1 COLLABORATIVE PAC SAMPLE-ALLOCATIE PROBLEM
Given contribution vector m, let S' be the pooled sample obtained by drawing points indepen- dently from each D,. We call m feasible if, with probability at least 8, every ERM hypothesis trained on S has error at most every D. The planner specifies only the draw counts from each distribution. Under these full-information assumptions, the task reduces to Equation 4. Our first question is thus computational: is this optimization tractable? We answer in the negative. The result below shows NP-hardness in |P[| even with a single agent. The full proof is Appendix D.1.
Theorem 2. Under the PAC-accuracy objective, determining whether specified sample count suffices to meet the (s, 8) requirement is NP-hard with respect to the hypothesis class size (H). even when there is only one agent.
4.2 APPROXTMATION VIA LINEAR PROGRAMMING
Despite this hardness barrier, the structure of the PAC constraints admits an efficient relaxation. Solving this I. takes polynomial time and returns contribution vector whose total cost is within

---

Published as a conference paper at ICLR 2026
logarithmic factor of the optimum. More specifically, for finite class H. our task is to find a vector of sample counts m = (m,)EEA that-with with probability at least forces ERM to discard every hypothesis h that is bad for some agent:
fE E A: D({= h(x) + (x))))
For any ordered pair (h1 (2)) satisfying this condition, the probability that sample lands in the set fær ha (z) + hz)z)) is IL (1 (f * hr))))m which is log- -inear in We therefore convert Equation 4 into an LP with polynomially many constraints, which can be solved efficiently.
For infinite H. provide approximate solution by solving the L.P whose size is polynomial in and? when the VC dimension d = VCdim (H)) is bounded. While the resulting solution ensures PAC constraints are satisfied for H. it may not suffice for the full class H. as there may exist a hypothesis h E H \ H that consistent but still incurs high error. Nevertheless, show that scaling the solution by factor of roughly d suffices to ensure the PAC objective is met for all H.
finite cover H H.
Any server that implements this LP to coordinate contributions, in Section 5, interacts with agents only through the information the LP requires, and two practical aspects are worth noting. First, the LP needs from each agent only finite, explicitly specified vector probabílities, tion burden is well defined and finite.* Second, these quantities are summary distributional statistics that each agent can compute locally from its own data. Sharing only these statistics, rather than raw examples, ensures the server never receives individual training examples.
the communica-
Formally, the next theorem summarizes the approximation guarantee of this LP relaxation; the full proof appears in Appendix D.2. As an empirical check, Appendix A.2 validates this LP allocation on a finite hypothesis class by comparing the true optimum Σ, m across varying [H).
Theorem (Approximation via Linear Programming). Given any H. and E, 0:
For finite H. the LP over (H, e, 6) returns a log(1/6)+tog [H] -aprrxximate solution to Equa- log(1/8)
tion 4.
For infinite H. running the LP over (H,,,8') and multiplying it by + log(1/8") returns O( o' (log(enn kd. kd/(cmus5)) aapproximmaee solution Equation 4, where H. H. is n-- log(1/8)
cover of H. 7 O x (/mmakidd + log(1/8)))), d VCdim(H), 8" भ[स 8'
8 and
8 log+ H1/65) Cmin min G2 and Cmaxx max4e[M] G--
5 MECHANISM DESIGN WITH APPROXIMATE SOLUTIONS
In Section 4 we studied the planner's computational problem under full information and control. Here keep prescriptive control but drop full information and reintroduce strategy under coordi- nation. In the uncoordinated game of Section 3 agents act by choosing their own sample sizes. With the planner fixing sample counts, agents can only influence outcomes by misreporting their local distributions, which shifts the LP constraints from Section 4, and thus the computed contribution vector. Building on that LP, in this section, design mechanism that is strategyproof and unique within a broad contribution-basee class, blocking this manipulation and addressing the inefficiency in Section 3. Together, these results highlight the contrast between uncoordinated and coordinated settings.
'Formally, for each pair h1, h2 E H. the planner needs, from each agent i, the probability that its data lie
the disagreement set (a hy h1(z) # h2(2)) ). that is, the quantity D1 hi (x) # h2(*)))- If H is finite, this yields at most [7122 numbers per agent. If H is infinite, Appendix D.2 replaces H with a finite y-vove H. whose size is polynomial in d = VCdim(H). These are summary statistics that can be estimated locally shared unlabeled validation set, rather than raw examples.
"Effrriigg prescribed contributions without accessing raw data raises a verification challenge. Practical approaches include cryptographic proofs and auditable contribution records (Ma et al., 2024; Kumar et al., 2025).
7

---

Published as a conference paper at ICLR 2026
Specifically, we regard the agents' local marginal data distributions private information that must reported to the mechanism. Their per-sample costs G remain known parameters." 6 To alleviate the resulting incentive issues, allow payments to the agents. The sequence of events, therefore, is as follows:
1. Agents report their local marginal data distributions, D = (Di ...... DE)..
2. The central planner computes solution based on the reported distributions D
3. Agents contribute according
4. The central planner pays each agent amount pi.
We make the standard assumption that agent utilities are quasi-linear, that is, the utility of agent i for contribution vector and payment p: (from the mechanism to the agent) is um(m) + Pi- We say that a mechanism (which computes agent contributions and payments) is strategyproof if an agent can never benefit from misreporting their local marginal distribution; in game- theoretic terms, is dominant strategy to report D D..
The challenge now is twofold: computation and incentives. In other words, the question this: How can we tractably compute contributions and payments such that the resulting mechanism is strategyproof?
5.1 THE PAY- WHAT- YOU-CONTRIBUTE MECHANISM
In our model, the answer to the foregoing question is surprisingly immediate. To compute the the approximation algorithm of Theorem 3. For payments, the (PWYC) scheme, that is, compensate each agent for its contribution,
contribution vector simple
up constant:
(a(m) C, m, C.,
(5)
for constants CI....,Ck:
Why is PWYC strategyproof? The utility of agent i when reporting truthfully is
u,(m) = a. (m) - q: m + 6 m, + = 1 C.,
learning threshold is satisfied by the contribution vector m computed by the approximation algorithm. Note that this is the maximum possible utility under this mechanism: for any m', the utility agent either + C, or C. depending on whether its learning threshold is satisfied by m'.
as its
5.2 ALTERNATIVES TO PAY WHAT YOU CONTRIBUTE?
While the PWYC mechanism is strategyproof, sophisticated mechanisms with the goal of, for example, minimizing payments. A natural candidate the classic Vickrey-Clarke- Clarke-Groves (VCG) mechanism, which in our setting computes the optimal solution m OPT asks agents to contribute according to m OPT and then pays each agent
may wonder whether is possible to design more
Σ JtM
Uy (m
OPT
(D_,) - Σ Cj jth
OPT m
+ qi (D",),
(6)
where gi( (e(D-) a term independent of the report D; of agent i. By standard arguments (Nisan, 2007), the VCG mechanism ensures that each agent reports truthfully.
An obstacle to using VCG directly is that computing the optimal contribution vector is computa- tionally hard (Theorem 2). In the algorithmicc mechanism design (Nisan & Ronen, 2001) literature, however, there are various mechanisms that overcome computational hardness by augmenting ap- proximation algorithms with clever payment schemes, including ones inspired by VCG (Lehmann et al., 2002; Dobzinski, 2007). Is there such rich mechanism design space in our setting? We give
Forr many applications, it is natural to treat per-sample costs as known or contractually specified: platform may post a fixed price per labeled example, meter and bill bandwidth or compute usage, or sign annotation contracts that set lab-label rate up front, that is parameter of the environment rather than private strategic information.
8

---

Published as a conference paper at ICLR 2026
partial negative answer to this question, showing that the PWYC mechanism is, in a qualified sense, unique.
This uniqueness is unfortunate, since the absence of mudget-balanced mechanism naturally raises the concern that shifting costs to the planner could, in sense, diminish some of the benefits of FL training in the first place. We view the uniqueness of PWYC substantive, if somewhat negative, insight: if one insists on dominant-strates strattey truthfulness and approximate efficiency a heterogeneous FL game, then some external budget or cost sharing is unavoidable, much like in other public-goods settings where reimbursement is often needed to align incentives. Even in stan- dard mechanism design settings, including the celebrated VCG mechanism, exact budget balance is generally impossible, so the planner must make net payments to align incentives. Importantly, PWYC does not force the planner to shoulder all costs: the constants C₁ Equation can be set to recover part of the spend from participants or downstream users while preserving strategyproofness. payment
We start by defining a class of approximate algorithms and class of rules. We first introduce a local obliviousness property of contribution solutions, which helps dis- tinguish approximate solutions from exact optima.
Definition 1 (Locally Oblivious Approximations). Given an approximation algorithm APPROX and a solution m, we say that the algorithm is locally oblivious m if. for any neighbor m' with |m' - m|l1 = 1, there exist distributions 'D = (Dz..... D2) and D' -D',...., D() such that:
APPROX(D) and m' APPROX(D, D D-i)for all i [R).
. Both and m' are feasible for 'D and for each (D), D -)) for all i e [k].
Local obliviousness highlights a key difference between approximate solutions and exact optima. Intuitively, it reflects certain slack in approximation: for any solution and any neighbor, we can construct pairs of distribution vectors where the approximation algorithm outputs m and its neighbor respectively. and both solutions remain feasible across all these instances. For example, show that the approximation algorithm introduced in Theorem is locally oblivious at all m satisfying m., m2 2 H|| log [H] in the two-agent setting.
Lemma 1. For any H greater than a universal constant C, there exists a PAC learning instance of (H, 6) in the two-ugent setting with (H| H such that the approximation algorithm introduced in Theorem is oblivious at all m with m1, m2 2 2/H| HH].
In general, a payment mechanism maps the reported distributions D' to a payment vector How- ever, is often unclear how to effectively utilize the reported distributions directly. To address this, we consider a class of mechanisms that are easy to compute in practice- -heeicceee-heeeeeeeeeee that depend on the distributions only through the resulting contribution solution m.
Definition 2 (Contribution-Basse Mechanisms). Given an algorithm APPROX, payment mecha- nism p is contribution-based if there exists f N* - IRk and q such that
(DD = ft (APPRO((D") + (D()))
Thus agent i's own report affects pt only via the computed contribution vector.
We now show that PWYC is the only strategyproof contribution based payment mechanism when approximate solutions used for two agents (see proof in Appendix E):
Theorem 4. For any strategyproof contribution- busedd payment mechanism f, approximation al- gorithm APPROX, and connected M C. N*, if APPROX is oblivious at all m E M, there exist constants C1 O2 such that for all m E M:
(i(m)
mG.mm4+ +m = 1,2,
Corollary 1. For any H greater than a universal constant C, there exists a PAC learning instance of (H, e, 8) in the two-agent setting with [H] H such that when applying the approximation algo- rithm introduced in Theorem 3 to compute the contribution solution, the strategyproof contribution- based payment f must satisfy
fi(m) = m4 + C.. Vi 1,2,
for all m with mi, m2 2 H log for some constants C1, C2.
Corollary follows by combining Theorem 4 with Lemma 1. Appendix F extends the same approx- imation broader class of objectives.

---

Published as a conference paper at ICLR 2026
6 DISCUSSION
We conclude by discussing the implications of our results, examining key modeling assumptions, and outlining connections broader theory.
Beyond the PAC accuracy objective. The (s, -ggarante controls the tail: with probability at least 1 the generalization error does not exceed 8. A complementary member the same thresh- old family bounds the expected error by e, trading worst-case assurance for an average-cast criterion that may better reflect practical risk tolerance. Most of our analysis carries over unchanged: Ap- pendix F.1 develops approximation schemes for computing optimal contribution vectors under ex- pected error, and Appendix F.2 proves that these solutions continue to satisfy the local obliviousness property.
Taking a broader view of utilities, we focus on threshold payoffs. With quasi- ing utility equals minimizing cost subject the threshold. This replaces the intractable dependence of each agent's loss on its contribution with a tractable optimization. Future work can explore richer models that trade off cost and payoff more flexibly.
quasi-linear linear utility, maximiz-
Centralized ERM benchmark. In this work, the ERM solution on the pooled dataset S is used only as theoretical benchmark, not an implementation assumption. The raison d' l'être of FL is avoid aggregating raw data on a central server, so directly minimizing the joint empirical loss over all local data imagines having everything in one place. In practice, algorithms such as FedAvg approximate the pooled-ERM solution via local updates and model aggregation, without ever materializing pooled dataset. In analysis, this centralized ERM solution serves as the reference point: it defines the PAC constraints and certifies that, if one were to train on the pooled draw of size m, the resulting model would satisfy each agent's (s d)) requirement. This abstraction lets us ignore optimization dynamics and focus on incentives and sample complexity, while any FL protocol that gets sufficiently close to this benchmark inherits the same qualitative guarantees, Using centralized ERM as an upper-bound reference standard in FL. theory (Mohri et al., 2019; Li et al., 2020; Blum al., 2021).
Common accuracy threshold. For clarity, we assume common accuracy target e across agents. This simplifying assumption streamlines notation and highlights the structural properties of the con- tribution game. However, our results do not rely on uniformity. Each agent's objective can be pa- rameterized by a distinct E,, and all definitions, equilibrium analyses, and approximation guarantees extend naturally to this heterogeneous setting.
Linear costs. Linear per-sample costs simplify analysis and are common in the literature, but they can be restrictive and not strictly necessary. Permitting any convex, non-decreasing cost function captures realistic scenarios with increasing marginal cost-for instance, later data points may be more expensive to collect. The strategic conclusions libria need not. Meanwhile, the linear program in our approximation algorithm becomes a convex program that remains tractable. Thus, the incentive mechanism derive continues work when agents' aata-gennration costs rise with effort, at the price of solving slightly more involved convex optimizations.
unchanged: NE still exists and pure equi-
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Abrar Ahmed and Bong Jun Choi. Frimfl: A fair and reliable incentive mechanism in federated learning, Electronics, 12(15):3259, 2023.
Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Eva Tardos, Tom Wexler, and Tim Rough- garden. The price of stability for network design with fair cost allocation. SIAM Journal Computing, 38(4):1602-1623) 2008.
Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. Advances in neural information processing systems, 19, 2006.
Ayan Kumar Bhunia, Shuvozit Ghose, Amandeep Kumar, Pinaki Nath Chowdhury, Aneeshan Sain, and Yi-Zhe Song. Metahtr: Towards writer-adaptive handwritten text recognition. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 15830-15833 2021.
Avrim Blum, Nika Haghtalab, Ariel D Procaccia, and Mingda Qiao. Collaborative pac learning- Advances in Neural Information Processing Systems, 30, 2017.
Avrim Blum, Nika Haghtalab, Richard Lanas Phillips, and Han Shao. One for one, or all for all: Equilibria and optimality of collaboration in federated learning. In International Conference on Machine Learning, pp. 1005-1014. PMLR, 2021.
Sebastian Caldas, Peter Wu, Tian Li, Jakub Konečný, H. Brendan McMahan, Virginia Smith, and Ameet Talwalkar. LEAF: benchmark for federated settings. CoRR, abs/ abs///81..0199,, 2018.
Dimitar Chakarov, Nikita Tsoy, Kristian Minchev, and Nikola Konstantinov, Incentivizing truthful collaboration in heterogeneous federated learning. arXiv preprint arXiv:2412.00998 2024.
Mengjing Chen, Yang Liu, Weiran Shen, Yiheng Shen, Pingzhong Tang, and Qiang Yang. A mech- anism design approach for multi-party machine learning. In International Workshop on Frontiers in Algorithmics, pp. 248 268. Springer, 2022.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andr Schaik. Emnist: extension of mnist to handwritten. Proceedings of the IEEE, 4322, 2017.
Ningning Ding, Zhixuan Fang, and Jianwei Huang. Incentive Mechanism Design for Federated Learning with Multi-Dimensional Private Information. In 2020 18th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT), pp. 1-8, June 2020.
Shahar Dobzinski. Better mechanisms for combinatorial auctions via maximal- cettaall-i--rmmnm in-range algorithms?
ACM SIGecom Exchanges, 7(1):30-33, 2007.
Kate Donahue and Jon Kleinberg. Optimality and Stability in Federated Learning: A Game-theoretic Approach, June 2021. arXiv:2106.099: 095800 [cs].
Yann Fraboni, Richard Vidal, and Marco Lorenzi. Free-rider Attacks on Model Aggregation in Federated Learning, February 2021. arXiv:2006.1 1901 [cs].
Michael R Garey and David S Johnson. Computers and intractability, volume 29. wh freeman New York, 2002.
Cengis Hasan. Incentive Mechanism Design for Federated Learning: Hedonic Game Approach, May 2021. arXiv:2101.0m0 [cs].
David Haussler. Sphere packing numbers for subsets of the boolean n-cube with bounded vapnik- chervonenkis dimension. Journal of Combinatorial Theory, Series A, 69(2):217-232, 1995.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv:1909.066.
2019.
Jiawen Kang, Zehui Xiong, Dusit Niyato, Shengli Xie, and Junshan Zhang. Incentive Mechanism for Reliable Federated Learning: A Joint Optimization Approach to Combining Reputation and Contract Theory. IEFE Internet of Things Journal, 666):1070-110714 December 2019.

---

Published as a conference paper at ICLR 2026
Sai Praneeth Karimireddy, Wenshuo Guo, and Michael I Jordan. Mechanisms that incentivize data sharing in federated learning. arXiv preprint arXiv:2207.04557, 2022.
K Naveen Kumar, Ranjeet Ranjan Jha, C Krishna Mohan, and Ravindra Babu Tallamraju. Fortify- ing federated learning towards trustworthiness via auditable data valuation and verifiable client contribution. In Proceedings of the Computer Vision and Pattern Recognition Conference, pp- 4999-5009, 2025.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/nmist// 1998.
Daniel Lehmann, Liadan Ita Ocallaghan, and Yoav Shoham. Truth revelation in approximately efficient combinatorial auctions. Journal of the ACM (JACM), 496):577662) 2002.
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair Resource Allocation in Federated Learning, February 2020. M.Kiv:1905.10499 [cs].
Jierui Lin, Min Du, and Jian Liu. Free-riders in Federated Learning: Attacks and Defenses, Novem- ber 2019. arXiv: 1911:1991..2560 [cs].
Juan Ma, Hao Liu, Mingyue Zhang, and Zhiming Liu. Vpfl: Enabling verifiability and privacy in federated learning with kero-knowledge proofs. Knowledge- Based Systems, 299:112115, 2024.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-fffcceent learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic Federated Learning. In Pro- ceedings of the 36th International Conference on Machine Learning, pp. 4615-4625. PMLR, May 2019. ISSN: 2640-3498.
Aniket Murhekar, Zhuowen Yuan, Bhaskar Ray Chaudhury, Bo Li, and Ruta Mehta, Incentives in federated learning: Equilibria, dynamics, and mechanisms for welfare maximization. Advances in Neural Infommtion Processing Systems, 36, 2024.
Noam Nisan. Introduction to mechanism design (for computer scientists). In Noam Nisan, Tim Roughgarden, Eiva Tardos, and Vijay Vazirani (eds.), Algorithmic Game Theory, chapter 9. Cam- bridge University Press, 2007.
Noam Nisan and Amir Ronen. Algorithmic mechanism design. Games and Economics Behavior, 1966 2001.
Jinlong Pang, Jiaheng Wei, Chen Qian, and Yang Liu. Incentivizing data collection from heteroge- neous clients in federated learning. arxiv, 2022.
Yunus Sarikaya and Ozgur Ercetin. Motivating Workers in Federated Learning: A Stackelberg Game Perspective, August 2019, wrXiv:1908.03099 [es].
William Shakespeare et al. William Shakespeare: the complete works. Barnes & Noble Publishing. 1989.
Nikhil Vyas, Depen Morwani, Rosie Zhao, Mujin Kwun, Itai Shapira, David Brandfonbrener, Lucas Janson, and Sham Kakade. Soap: Improving and stabilizing shampoo using adam. arXiv preprint arXiv:2409. 240.132409.1131, 2024.
Dejun Yang, Guoliang Xue, Xi Fang, and Jian Tang. Incentive mechanisms for crowdsensing: Crowdsourcing with smartphones. IEEF/ACM transactions on networking, 24(3):132-1144, 2015.
12

---

Published as a conference paper at ICLR 2026
A EMPIRICAL VALIDATION AND ILLUSTRATIVE SIMULATIONS
Overview. Our main contributions theoretical. This appendix complements them with two em- pirical studies that illustrate the modeling assumptions and the practical significance of the planner and mechanism. First, show that data not exchangeable, since agent benefits more from data drawn from its own distribution. Second, we validate the planner's LP allocation on a finite hypothesis class by comparing its total cost to the true optimum found by search.
Dataset Selection and Motivation. We build on the LEAF benchmark (Caldas et al., 2018), which provides realistic federated datasets naturally partitioned by user. We selected two datasets, FEM- chosen NIST and Shakespeare, cover both vision and textual tasks. These specific datasets collection because they have the highest average number of datapoints per user among the LEAF (Caldas al., 2018). FEMNIST, built Extended MNIST (LeCun, 1998; Cohen al., 2017), consists of handwritten character images partitioned by writer. Shakespeare is constructed from The Complete Works of William Shakespeare (Shakespeare et al., 1989; McMahan al., 2017), partitioned by speaking role, with each role in each play treated as distinct agent.
Dataset Construction. We construct two-agent subsets from each dataset by selecting the two users with the most data points. For FEMNIST, these are writers f0261_0e 06 and f0289_10 jointly contributing 1, 047 samples. For Shakespeare, we select the roles Hamlet (from Hamler) and lago (from Othello), together providing 112, 116 samples. Additionally, we create variant scenario with top agent and a random convex combination of five other agents forming the second agent. We illustrate qualitative differences between the FEMNIST agents in Figure 2.
1
Agent
2
A
a
b
Agent 2
2
A
Figure 2: Samples from selected character classes for FEMNIST agents, illustrating distinct handwriting styles.
A.1 EFFECT OF DATA COMPOSITION ON AGENT-SPECIFIC PERFORMANCE
Experimental Setup. For varying total data size and fraction À E [0, 1] from Agent 1, we con- struct datasets (m,,) comprising Am samples from Agent and (1 X)m samples from Agent 2. Models trained on these datasets are evaluated separately on each agent's test set. We use standard cross-entropy loss and the SOAP optimizer (Vyas et al., 2024). To capture performance variability, experiments are repeated 100 times with different random seeds. See Table for detailed parame- ters. We employed task approorpree model architectures aligned with prior federated learning works (McMahan et al., 2017; Caldas et al., 2018; Murhekar et al., 2024). For FEMNIST (image classi- fication), the model is lightweight CNN. For Shakespeare (next-character prediction), recurrent neural network with an LSTT backbone.
Table 1: Summary of experimental parameters.
Dataset
Agent
Agent
# Seeds
m values
Learning rate
Epochs
FEMNIST
f0261_06 Hamlet
f0289_10 lago
100
10 450
0.01
50
Shakespeare
100
10, 000 - 45, 000
0.01
25
13

---

Published as a conference paper at ICLR 2026
FEMNIST
Shakespeare
Toxt Aocusioy srrr
0.45
0.75
0.4
0.5
0.25
0.75
0.26
0.
Fraztion of samples from fromnggent
Fraciion of samples from Agent.
#25 450
676
#100
1200
4500
e400
+450
#10000 8000
#2.000
+27930
#20000
#40000
#49000
Figure 3: Agent I's test accuracy function of the fraction of samples contributed from its distribution (Agent 1), compared against random convex combinations from other agents (Agent 2). Each curve represents different total dataset sizes (m) The monotonic trend supports the weak cono-ooonty Assumption 2.
Results and Discussion. These experiments confirm the intuitive expectations about data volume and personalization, and quantify their effects. (i) For any fixed share X, increasing the budget m lowers both agents' losses-mort more data helps everyone (Assumption 2). (ii) For any fixed m. raising cuts Agent I's loss: when the training set includes a higher proportion of one writer's 's style, the model better tuned to that style and thus generalizes better on that agent's test set. These trends mirror prior personalization findings in federated learning and domain adaptation (Hsu et al., 2019).
A.2 PLANNER VALIDATION ON FINITE HYPOTHESSI CLASS
We empirically validate the planner's LP allocation from Section 4.2 by comparing its total pre- scribed samples to the true optimum obtained by discrete search over integer allocations. We report the ratio
Σ m
m
under uniform per-sample costs C; 1.
Finite-class construction. We focus on FEMNIST and construct a finite hypothesis class H. by sampling checkpoints from a compact CNN with two convolutional blocks and a linear classifier. For each agent, we estimate pairwise disagreements Di((h) + h2)) for all h1, h1 H using unlabeled data, i.e., the fraction of examples on which the two checkpoints predict different labels. These estimates instantiate the constraints in Section 4.2, yielding the LP- L.-bdsed contribution vector LP
Experimental setup. We assume e; 1 for all agents. Given m we perform an independent discrete search over integer allocations and, by repeated evaluation of the checkpoints in H, find the smallest m' that satisfies every agent's (c, target. We sweep the size | of the sampled class and record r.
Results.
The observed values of r across 17/ are reported Table 2. The LP allocation achieves logarithmic-type approximation factors consistent with Theorem 3.
B BINARY PAYOFFS AND QUASI-LINEAR UTILITIES
In this section we explain why our binary "meets target or not" payoff should be viewed as a con- venient normalization rather than a restrictive assumption. We model each agent's payoff as 1 its PAC requirement holds and 0 otherwise, but show that this threshold formulation is equivalent, via a standard Lagrangian/KKi argument, to optimizing a much broader class of quasi-linear utilities that trade off accuracy against cost. In particular, any agent with smooth, monotone accuracy ben- efits and convex costs behaves as if it had such a hard accuracy requirement, so the binary model compactly represents wide family of underlying preferences.
14

---

Published as a conference paper at ICLR 2026
Table 2: LP total versus the optimal total on FEMNIST for a finite hypothesis class H.
Eg m. En m"]
|7
5
1.67
10
3.19
3.94
20
3.57
25
4.24
27
3.99
4.20
Our agent-level decision problem is cost-minimization subject to meeting its accuracy require- ment:
min s.t. 0j of = 1.
m.EN
Under standard regularity conditions (feasibility of the constraint, monotonicity and differentiability of the underlying accuracy function, and convexity of the cost), the Karush-Kuhn-Tucce (KKT) conditions imply that any optimal solution to this constrained problem can be obtained by optimizing an equivalent unconstrained objective. Let (, denote smooth, increasing performance metric for agent (for example, one minus error) such that A (, 1 at the optimum, and let the per- sample cost be > O. The Lagrangian for agent i's problem is
Li(m;, A²) = c,m, + Aa Ammm))
with multiplier A, 2 on the accuracy constraint. At any optimal solution m,, the KKT stationarity condition gives
0c: (m;) = c; (m;)
Af(m²)= A
0m,
In particular, there exists multiplier A 0 such that the optimum m., the marginal benefit of contributing data, Ai (m,)). ). equals the marginal cost scaled by A5 Intuitively, X; serves to balance accuracy and cost the threshold point. exactly the shadow price of the accuracy constraint: it measures how much the agent's minimum cost would increase if the required accuracy threshold were raised slightly.
This yields precise equivalence between the threshold and quasi-linear linear viewpoints. Consider the unconstrained quasi-linear utility
U,(m,)) A, Xpm4,
where A is the agent's 's marginal disutility for each contributed sample (we can absorb c, into X by scaling). The first-order condition for maximizing Ug is Af(m;) d Choosing X; A makes this condition identical to the KKT stationarity condition above, so m is also optimal for the unconstrained problem. In other words, the same m solves both "minimize cost subject to meeting the threshold" and "maximize smooth quasi- utility that trades off accuracy and cost at rate
X,." The optimal stopping point for a satisficing agent under a continuous accuracy-benefit curve is therefore identical to the stopping point under the binary threshold model. Ex post, using a threshold utility does not exclude the optimal outcome that a more complex utility would produce: for any smooth, monotone accuracy benefit function and convex cost, there exists cost weight X; such that the agent behaves as it had a hard requirement.
The above argument relies on A,(m) being monotone (more data never hurts) and differentiable; if we further assume A; is concave (diminishing returns accuracy), the correspondence between the threshold model and a smooth utility model becomes tight. Under concavity, the stopping point m is uniquely characterized by the balance of marginal benefit and cost, and this point is exactly where it is optimal to "just meet" the target and not contribute further. In that sense, any agent with smooth, monotone benefit of accuracy and convex cost behaves if it had personal threshold, and the binary payoff is modeling convenience rather than a fundamental restriction.
C EXISTENCE AND EFFICIENCY OF EQUILIBRIA
In this section, we study the strategic behavior of self-interested agents in our model.
15

---

Published as a conference paper at ICLR 2026
C.I EXISTENCE OF EQUILIBRIA
We impose weak monotonicity more data from any agent never hurts another. The assumption guarantees equilibrium existence.
Assumption (Monotonicity). For every agent i, utility is weakly increasing in any agent's 's contri- bution. Let m and m' be two contribution profiles with mlj my for every agent j. Then
uz(m') 2 (;(mm ViEA.
Theorem (Existence of Nash Equilibrium). Nash equilibrium exists.
Proof. Since every agent E A is self-sufficient, can, by contributing na < oc samples on their own, satisfy their objective. Since additional samples supplied by other agents never reduce any agent's probability of meeting its objective, the strategy
ind guarantees utility - c.n. ind 2 for every profile m- In contrast, any action with e,m; > 1 yields utility - c,m; < 0 irrespective of the others' choices, so every such action is strictly dominated by n!! Thus agent i's undomi- nated actions lie in the finite set {0, n2 J. With each player restricted to finitely many pure strategies, the game is finite, and Nash's existence theorem for finite games guarantees at least one (possibly mixed) Nash equilibrium.
We demonstrate, however, that pure Nash equilibria do not always exist:
Theorem 6 (Non-existence of Pure Nash Equilibrium). There exists PAC learning setting in which no pure Nash equilibrium exists.
Proof. Consider instance space X 12, possible labeling. Let agents have data distributions: Define the data distributions of the three agents by the probbbpros
22, r3} and hypothesis class H that contains all
Di(m)) 3. (1()2) 3, DI (x(ss) 0,
D2(01) 0, D2(22) }. D2(23) 2
Dz(x1) 3. Dz(22) = 0, D2(2a) = 3.
Fix the PAC parameters = == and = 3/2 Each agent seeks accuracy at least with probability at least 4. Hence every agent requires that, with probability at least - ô = 3. the learned classifier incurs error at most E on D,,.
In this setup, no agent incentivized to contribute more than one sample. Checking possible pure strategies, one observes: At m (1, 1, 0), agent 1 can deviate to 0 without losing accuracy, incen- tivizing deviation. And, at m = (0, 1, 0). the contribution level is insufficient for agent 3. Thus, no pure equilibrium exists.
C.2 EFFICIENCY OF EQUILIBRIA: PRICE OF STABILITY
Theorem (PoS is unbounded). For any e E 10,1) there exists a sequence of instances of our problem in which the ratio of the best NE to the optimal solution approaches (log(1/e)).
Proof. Fix E E (0, }) and E (0, 1). We construct an instance whose PoS satisfies
PoS log(1/E) + log(1/6) ((log(1EE)).
log(1/8)
so the ratio diverges
O. Let
1 and set
X (x1, (r1,...,4 Fn. 2)
Define the hypothesis class
H = (ho) U (h:: i [n]}
where
ho(x) =0 (VI x), hi(z) = {1 i E (
otherwise.
16

---

Let mNE Published as a conference paper at ICLR 2026
hs
Fs
Ea
Es
Ey
Xg N5 Xg
1/1
V2
3/
V5
36
37
U1
U2
U1
Ug
Ug
Uto
Figure 4: Visualization of the SET COVER reduction used in Theorem 2. Left: Incidence matrix of the original Set Cover instance. Each row is subset F, and each column an element u;; square means u, E Ej. Right: The corresponding bipartite graph construction: each node zj corresponds to subset E and is connected the hypotheses h, for which u, Ej- A size-m set cover on the left corresponds to an m-sample training set that forces ERM to output h* on the right.
Thus y is always labeled while the label of determines whether F1,..., Fn are (h") or exactly one of them is (t'). Alice and Bob have marginal distributions
D Atice (2:) = 25 Vi [n],
D DAlice (y) = DD Alice (2) = 0, Vi [n].
Daob (=) E, Drah(y)= =1 8,
(Ran(1;)
In every NE, Bob contributes O samples, because any h E H has error at most on his distribution, so his (e, 8)-requiremment is already satisfied. In the worst case, where ho is the target function, Alice must choose m so that she samples every point FI...., with probability at least be the smallest integer for which this condition holds.
opt In the minimum-cost contribution vector, Bob supplies Bob = log(1/8)
1- samples, which include
with probability 1 - 8. If the true target is ho no further data are needed. Otherwise the target is OPT be the least some hy; Alice then has to sample only until she sees the single point T;. Let m Alice integer guaranteeing this with probability cheaper than sampling until all n points appear. Hence the optimal cost is
5. Sampling until one designated point appears is far
3 1og(11
m opt
1|
+ m Alice mob
2c
Taking the ratio,
log(1/8) 166 + 100( S(log(1/E)). | []1 log(1/8)
mm NB |
PoS
which grows without bound as 8 - O.
D DETAILS AND PROOFS FOR SECTION 4
D.I PROOF OF THE NP-HARDNESS RESULT (THEOREM 2)
We now formally address the computational complexity of deciding whether a given number of samples is sufficient satisfy the (c, PPC learning guarantee for all agents. Given a data domain X. a hypothesis class H. of size n. distributions D (Di..... Dx) for each agent, an accuracy parameter > 0, confidence parameter 8 E [0, 1), and integer m, define the Collaborative
PAC Sumple-Allocation Problem as follows:
Definition 3 (Collaborative PAC Sample-Allocation Allocation Problem). Given domain X, hypothesis class H. distributions D (Di,..., DD)). accuracy parameter e >> O, confidence parameter ö 1), and integer m, decide whether drawing m samples i..d. from each D. suffices to guarantee, with probability least 6, an ERM hypothesis of error at most for every agent A.
17

---

Published as a conference paper at ICLR 2026
In other words, if each agent contributes exactly m, samples from their distribution, will the pooled dataset ensure E-acourate performance on all distributions simultaneously? We now examine the computational complexity of this question. We establish the following computational hardness sult:
Theorem 2. Under the PAC-accuracy objective, determining whether specified sample count m. suffices to meet the (e, 6) requuiiremntt is NP-hard with respect to the hypothesis-class size (H), even when there is only one agens.
Proof. We reduce from the NP-complete SET COVER problem (Garey & Johnson, 2002): given universe (ui,..., J a family of subsets & E . Er} with Userr] Eg U, and an integer m, decide whether at most m subsets cover U.
We map an instance (U, m) of SET COVER to an instance of the Collaborative PAC Sample- Allocation Problem as follows: let the data domain be X' = A U U.2 where
X1 = ,r...
X₂ = f311...... }o
Each point z Xi corresponds directly subset Eg E, and each point yı E X2 corresponds to element 04 E U. Define the hypothesis class
H (hr ,r,,...,,, hn..
where, for each i [n]] and j [k]]
hT(2,) {
uq E Ej otherwise
{1 i
h4(1,)
M²xx;) = 0, h²(1,) =0
0
otherwise
Set the distribution D to be uniform over X. Choose 0 < & <1 <1/(++)) so that a single classification error violates the e-accuracy goal, and set ā with - 1m
If set cover of size p S m exists, say {E......, Ej consider the sample $ = {Zj...... I, For every competing hypothesis h; * ht there is a subset Ej, containing u, hence h, (2xz)) = 1 * 0 h" (x;;,) ). Each h; therefore incurs at least one error on S, ERM selects h², Thus m samples suffice to meet the agent's 's (s, 0)-requirement.
Conversely, assume that m samples drawn i.i.d from D suffice to guarantee, with probability at least 1 6, an ERM hypothesis achieving error most for any possible true hypothesis. Due to our choice of e, the ERM hypothesis must correctly classify all points in X. Consider the worst- case scenario where the true hypothesis is h² To distinguish h' from all other hypotheses h;, the training set must include points from Xi that differentiate ht from each h, Specifically, for each element u, U, the training set must contain at least one point æj E X1 with hę(2,) =1 (meaning v, E E,). ensuring h; is eliminated by ERM. Therefore, the set of points in the minimal training set corresponds directly to subsets forming a valid set cover of size at most m.
Notably, if any other hypothesis h * ht were the true target, fewer samples would trivially suffice. Thus, the case where h is the true hypothesis indeed represents the worst-case.
D.2 PROOF OF THE APPROXIMATION GUARANTEE (THEOREM 3)
Theorem (Approximation via Linear Programming). Given any H. and e, 0:
For finite H. the LP over (H, returns a (og(1/6) [H] approximate solution to Equa-
log(1/8)
tion 4.
For infinite H. running the LP over (H,,,8') and multiplying it by d + log(1/8")) returns a O( df kd. (cmue)))) )-aprrxximate solution to Equation 4, where H. C H is 7- log(1/8)
cover of H, 7 O (mmin ( kCmark(d + log(1/6)))),
VCdim((H), 8" 사 and
8' = 8(d+log(2 H1/6)) Gmin = min G4 and Cmmox = max G-
8
Proof. We start with the case where the hypothesis class H. is finite, the extension to infinite H. follows with standard covering argument.
18

---

Published as a conference paper at ICLR 2026
Proof for finite H. For any pair of hypotheses (h1, h2) E H. define the disagreement regions between hy and hy as
DIS(hi, h2) = {xEt 11(2) h2(2)).
This region represents set of points where and lı2 disagree. For each agent i, let D; ( h2)) be the probability mass that D; places on that region.
We want to guarantee that with probability at least 1 - 6, the ERM solution has error S for all agents simultaneously. Concretely, if the true labeler is h H. then any other hypothesis h2 that has D, (DIS(Ah h2)) (meaning it is "bad" for agent i) must be eliminated by at least one sample from that disagreement region.
The probability that h2 is never eliminated, given h* is the true labeler, is exactly the probability that no sample from any agent ever lands in DIS(h", h2). Since each agent contributes m, i.d. points from D;,
Pr(h2 is not eliminated
h- 11))
II (DIS((("),
Hence the requirements Pr(h2 not eliminated h+) मे log-linear constraints:
m, log D:(DIs(h", ha))
< log 4
We impose such constraints for all pairs (h* h22) where D:(DIS(h* h2)) > for agent i. By union bounding across < possible "bad" hypotheses h2 (for each li*) or H² pairs overall, we ensure that with probability 2 21 8, any truly bad hypothesis (in the sense of having error E) is climinated.
Hence, we obtain linear constraint terms of m,, which allows us to approximate the elimination probability for each hypothesis pair (h1, by solving the following linear program:
min
m
mEN
subject to
m, log (1 - D,(DIS(h) h2))) log 8
h2) H2 s.t. 3i E Di h2)) H
>
(7)
One can then round the fractional solution up to integer counts my. Let m" be the solution of the linear program. For any agent i, want show:
(U,XNNU)) > 55.
vh* H.
Pr U SElk]
ERM em
JEIM
This holds because the linear program enforces that, for each pair (h1, E H.2. the probability of failing to eliminate any incorrect hypothesis h2 (given h+ = h1) is bounded by 5/ H. By applying a union bound over all hypothesis pairs, achieve the desired bound.
To show that this solution is +gg) approximate optimal, let m be the true optimal solution.
(1/8)/8)
For each pair (h1, h2) such that DDIIIS h2)) c, if we take m samples, have:
II (1 h2))) S 8. 1=1
Taking logarithms obtain:
m; log (1 - DDDSS((h, h2))) I log 6.
19

---

Published as a conference paper at ICLR 2026
Now, given sample size of log(1/8)+Hog H log(1/6)
we have:
log(1/0) log H
log (1 (((D)s((),))))) S log H
log(1/0)
which satisfies the constraint Equation 7. Next, we show how to lift the guarantee to infinite classes using 7-covers and apply our results to this finite cover.
Proof for infinite H. For any 7 (0, we say H is 7-cover of H. under D if for all h E H, there exists an h E H satisfying that max, (DIS( h)) 7.
Lemma 2. Let d = VCdim(H) denote the VC dimension Hf H. There 7-cover H C H under 'D of size (22k)²
Proof of Lemma 2. learning theory, for any distribution D, a subset H S H is a 7-cover of H under D if, for every H. there exists h E H such that D(DIS(h, R)) & 7. Haussler's 's sphere- packing bound guarantees Haussler (1995) the existence of such cover with
H
Construct a cccovrr of H under the averaged distribution representative h in this cover,
1 Σ Di. For any h H. and its
k
max (DIS((,),)) h)) -
D. (DIS(h,,))) S
so the same set 7-cover under D = (DI..... Da). Substituting 1/ into Haussler's bound yields
Let m H.S' denote the solution to the LP (Equation 7) given hypothesis class H. and confidence parameter 8'. Let Cmin min4e(A] 6 and Cmax max Ct-
Lemma 3. By choosing 7 A6 (Cmau + log(1/5)))) and m m H.5/2 for any target hypothesis h- E and agent i, with probability at least 6, any consistent hypothesis h E will satisfy
errD, (h) Se.
Proof of Lemma 3. Since each agent can achieve the PAC learning objective with at most O((d + log(1 /5))/E) data points individually, we restrict attention to contribution vectors satisfying ||m|| S O Can ((d=log(())))) (otherwise can replace the solution with O(dd log(1/8))/=)11, Came
For any m satisfying this constraint, any h* E H. and any agent i, let the labeled sample be
5h
U ((x, a U,). JE[K]
Define
err = max errp, (h)
he H. err (h) = min err (h'))
WER
20

---

Published as a conference paper at ICLR 2026
the worst-case error when running ERM over H. We can show that err is small with high probability. More specifically, assuming a (E.6/2)-PAC guarantee for H. we have
Pr Sh
3 h
eTTD, (h) > e, errs ga (h) min err gr (h') N'EH
Pr
3h: errp (h) > e, g (h) 0, errgh (hi = =0]
+ Pr eerrraa (h²) + 0) gha
Sh
Pr
3h: eITD, (h) > c, ga ( 0| + Pr gur (h +
ghr
gh
8
$ 2
+ (1-
-1- ms) - 2 + (1 - (1 7)
(1 -
"uin
Choosing 7 = cmin (Cmax (id + log(1 (1(()) yields
6
(1 (1 - Cress (ld
"nis
S 6,
2
so for any h" and agent i, with probability at least 1 - 8 we can always find a hypothesis whose error is most e.
Lemma 4. By choosing y = ((Cinndd) (Cma://maah (og((()))))))) the solution (d log(1/8")) -m F2.0' is sufficient is sufficient to achieve (e, 8PPC accuracy objective (Equation 2) for H. where 8" = and 8' {(d+log((HH1/8)
H
Proof of Lemma 4, Similar to Lemma 3, we again restrict attention to contribution vectors satisfying
|m||| S O (ddg ). This guarantee that for any target h", with probability at least 1 2'
ht" is consistent. Hence, we can view ht as our target hypothesis.
We now prove that for any target hypothesis ht" E H and any representative hypothesis he E H satisfying Si E [A:], (DIS(( .)) > E, with probability at least 1 2 any in the y-ball of will be eliminated.
Let 3 D, (DIS (7t" Fi)) denote the probability mass of DIS R) under agent i's data distribution
and let A, = {i E [k]]@, 2 4y) denote the set of agents whose probability mass of the disagreement region is at least 4y. The approximation solution m F..5' guarantees that
II (1 3) N..'
8'
H
If 3, < 4y, we have
(1
3, m
> (1 47) mm) 74.5"
2(1 47)8 /r c (1 4)6'
where we adopt the inequality
(1- - 1/2)' 2
1 for all x 2 2. Hence, we have
4
e log 4jR6'
(1 (1-33) m1) T..8' 5
8'
H
2:8.247
By rearranging terms, we have
II (1 (1-B8)m 2,,
N.
8'
(1 4)88'
28
H
H.
when 8' = O()). That is to say, even if we only collect m; samples from agent i E Ay and don't collect from $ Ay, we will still be able to obtain one sample from the DIS(N" h) with probability at least 1 28'
For any distribution D, let D n f denote the distribution restricted to DIS(H", Ji), i.e.,
D(w) D(DIS(A .N)
if I E DIS(h", Fh), otherwise.
D W (1))
21

---

Published as a conference paper at ICLR 2026
Consider D Dica, m:D; LiEA, mi
being a mixture of {Dili- E Ay), the disagreement region between h
and h under distribution Dir' J least 1' This is because
D Pir x (DIS(R" A)) PIx J (DIS(H,)) 2 7 3
47
Hence, by standard PAC learning guarantee, we obtain O + log(1/8")) samples from DIs" J.. then with probability 8", all h's in the y-bal are not consistent.
The current approximation solution m 77,6' can only guarantee that with probability 1 obtain one sample from D17" Jr. i.e.,
28' [?2]
28'
II (1- (1- v
H
k:9:247
When we increase m H2,5' by times, then with probability at least 1 from Día Ph'.N _h
2nd
we obtain n samples [H]
Hence, by setting 8" 1 and s(d+log(2 solving the LP for H. obtain an
approximate solution m H1,5 and multiplying it by d l+gog(1/"" the solution (d+ (o+(og(1//")) m H.8'
sufficient to achieve (e, PPAC accuracy objective (Equation 2) for
The solution m H2,6' returned by the approximation algorithm for the (e,8')-PAC objective for H at most factor
log( (71/8')
log(8/0) + log(d (og( + d log( + log log(1/6))((e))
log(1/6) (1/8)
log(1/0) (6))
d(log k log d (1e)) + log(1/0) + log( /min)) =0
log(1/5)
larger than the optimal solution for the (s,6)-PAC objective for H. Since the PAC objec- tive for H easier than the PAC objective for H. we have (d + log(1/8")) 7,56' is O( d' k+g (lgg (omm )-approximation solution for (e, ()PA) objective for H.
log(1/8)
E DETAILS AND PROOFS FOR SECTION 5
Lemma 1. For any H greater than a universal constant C, there exists a PAC learning instance of (H, 8) in the two-agent setting with H H such that the approximation algorithm introduced
in Theorem 3 is oblivious at all m with 1, m2 2 2 log (H].
n 11.......7 singletons (i.e. functions h; that label exactly one x E X' as positive and all others as negative) plus the all negativee function. Thus H = [7| + 1.
Proof of Lemma 1. Consider X' = {1. 2, ...
as our domain and the hypothesis class H. of all
We now show that that for any satisfying m1, m1,my 2 2/H( log [7] and any neighbor m' with Im' m 11|1 1, we can always find distributions D1, D Dz, D'2 satisfying that
APPROX(D, D2) and m' APPROX D2) APPROX(D, D)). Contributions m and APPROX(D), DzY are both feasible for (D1,D2) (D), D2), and (D).
Construction. We construct pair of distributions (D1, D2) by selecting Pl, P2, 91, 42 satisfying
Pl S
P2 <
Q2
Pt + p2
21 92
2n
2n
Then
1 (p1 + P2)
1 1 (q q2)
Ps
Pn
43
4n
11
n 2
22

---

Published as a conference paper at ICLR 2026
Hence let D1 (p (PI..... ..... Pr)) and D2 (91...... ..)......................))..... Both are well-defined distributions. We denote by d the family of all such pairs (D1, D2) with different choices p1, P2, q1 92 satisfying the above constraints.
The approximate-optimen solution APPROX (D1, D2) 2 is found by solving linear program derived from disagreement regions. For example, the disagreement region between the all-negative hypoth- esis he and singleton h1 that is positive "binding constraints" " come from pairs (Au, h2) and (ha, h2) (the singletons with points 1 or 2). By contrast, any singleton point 3 yields disagreement measure at least P3. which is larger, and thus any feasible solution that satisfies the "small measure" constraints with some margin also satisfies these larger measure constraints.
point has measure P1 in D1 (and 91 in D2). The
Thus the main LP constraints reduce requiring that
m1 log
+ m2 log
H log
1 P1
1 1- Q
5
m, log
+ m2 log
log
# 8
(9)
P2
1 42
The solution APPROX D1, D2) the one that minimizes 61 m. + 02 m2 subject to Equations (8) and (9) (and additional constraints for any bigger disagreements, satisfied by slack).
mi + m2 2 2H/ log H, we can show:
m1 log - + m2 log -
me log - + m2 loy 1- + log H
for each i 2 3. hence those constraints are looser. Hence, satisfying Equations (8) and (9) by small margin also satisfies the bigger-disagreement constraints.
To satisfy the second bullet. For any = 3, ...,, according to our construction, we have p; 2 and Pı, P2
I 1. Thus, we have
2n
P 21 =e
-0
+ - -0(
1 1 Je -
2 (1
0 1
2n
n2a
n1
1
(1 Pt) pi)e
0
n2
Thus, we have
log(
-- >
log
-0
2
log
+
1- ps
1-p1
2n
n2
1
3n
for big enough. Then for the constraint corresponding to the disagreement region DIS hi), have
1
1
1
1
m. + m2
m, log
+ m2 log
my log
m2 log
pi
I qi
1 P1
91
3n
2m, log
+ m2 log
+ log H,
1
where the last inequality holds when + m2 2 3H log H. Similar results also hold for Dz. That to say, instead of satisfying Equations (8) and (9), it would be sufficient to satisfy
3
mi log
+ m2 log
2 log
1- P1
91
5
1
3 log
mi log
+ m2 log
1
P2
1
Q2
g"
Hence, for any (D1, D2) E P. we have log 3/5
APPROX D2) feasible. For simplicity, let's
log H/8
fix 8 < 0.5 and suppose H > 18 from now. Then 1 APPROX(D,, D2) is sufficient and is APPROX(D,, D2) - (1, 1). Thus, we justify bullet
To satisfy the first bullet. Given an m and m', we pick D1 specified by Pl, P1.P2. D2 specified by 41 92 and D/ specified by pl1 plg so that Inequalities Equations (8) and (9) hold with equality and that m and m' the only solution to these linear equalities w.r.t. (p) 12, 41 92) and w.r.t (p/ pla qu 42), respectively.
23

---

Published as a conference paper at ICLR 2026
Inequalities Equations (8) and (9) can be approximated using first-order approximation as follows.
H mip1 + m2q1 = logg = a
mip2 + m2222 = 08
m/pp1 + miq1 az
m/p2 m2q92 a
Let's pick
(1 1/ /22
P1 m2
q1
(1 1/mi)e )a
P2
Q2
m1
m2
We can justify (D1, D2) E P since mı, m2 2 2n log n. Then if m' differs from m at my by solving
m/p1 m241 mpp + m2g1
m2d2 m/p2
m1P2 + m292
we have
mipi p
P/2
m1p2
m
mi
It's easy for us to justify that (D), D2) E P since Dj is very close to D1. mn differs from m at m2, by solving
mipi + m²q: m1P1 + m291
m1p' m²292
m1p2 + m292
we have
(m2 m2)4q
(m2 m2)92
pi
P1.
P/2
+ p2
m1
m
By plugging in the values of p1. Qı, 92, we have
p = (+1) 1/m2)a
m2
m1m2
(+1)a
(1 1/m1)a
P2 mfm²
m7
is easy to see that pe is very close P2 and pl p/z. For pl. we need to make it fall in (0, 1 )
When mı, m2 2 2n log n, we have p S m, 2n with computing D'. We can compute D' in the same way.
1. Also, p is always positive, So we are done
Proof of Theorem 4. When f is strategyproof, it must hold that f. f. for any two neighboring m, m' M. If f((m) - C. - my f((m') (mmm))c; c, m/, agent i will misreport their distribution when the ground truth is (D), D D))): else if fi(m) - q: m, < f(m') G m/ agent will misreport when the ground truth is D. which conflicts with truthfulness. Since M connected, we have (mm)
m = fi - mi
m, C, for all m E M.
F RESULTS FOR EXPECTED ACCURACY OBJECTIVE
F.1 APPROXIMATION ALGORITHM
Recall that the optimization problem with the expected accuracy objective given an error parameter
is
min
T m
mENK
subject
max ES-P(D, K
fen
FRM P.ik (5) Se, A. A.
(10)
Let's denote the optimal solution to the above problem as (x
24

---

Published as a conference paper at ICLR 2026
For any pair (hz, he) write
f = no sample lies in hes( d'م D.DIShh,, ht)):
the "no-sample" event and its probability mass under agent i's distribution D... Without loss of generality, relabel the hypotheses that the disagreement masses increasing:
aj 2 ah ... dxx
Define the first "small" index by
a == min j aj { (set n K if no such j exists).
Aej =
Ek,
As = V Eu,
ax+1== = 0.
ASS
These abbreviations mean, respectively, "no disagreement observed yet" and "some disagreement observed by step j."
Es-.i..m....
ERM (5)) Drr....
Σ Pr(E A(c))
Pr(E, ( ag + E
2
j=1
Pr(Asi) (0) - -dj+1) + 2
==1
For any index set [5] = (1.....5} let
Asj = V Er.
(S)
Then
sup Pr(E,) & Pr(Ast) S
Pr(Ee) I j sup Pr(Ee).
(UB)
[
Replacing Pr(Asj) by upper bound Elm Pr(Ft) the telescoping sum from the previous step yields
Pr( (a) a5+1)= 2
Pr(E.) s s,
where we set 4/ = 0 for the telescoping identity.
Each probability
K Pr(E,) II - DD h,))) m
A=1
is product of log-affine functions of (mi,..., mx) and is therefore convex; the entire left- hand side above is non-negative weighted sum of convex functions, hence convex m.
Impose the term-wise bound Pr(E,) af < f for every disagreement index t. Define the set of "large-mass" pairs
Pe/2 = ((h1,12) E H2: max D, (DIS(h), > 2
isk
25

---

Published as a conference paper at ICLR 2026
For each such pair write
(.(h,,12) == D,(DIS(h1, h22))
and
min ip.((Raaa)se/2
pi(hi h2).
The resulting is
min mE
c T
m
k
(11)
s.t.
Σ me log p:(li, (2)) < logl 2Ha(h
((11,12) E Pe/22
Theorem 7. The solution to Equation 11 is feasible solution to Equation 10. Given the optimal
solution m= (G) to Equation 10 with error parumeter 4, then (0g(2))mm+-0 (4) a feasible
solution to Equation 11.
Proof of Theorem 7. It is direct to see the solution to Equation 11 is a feasible solution to Equa- (1),
tion 10. Given contribution m))) we have Pr( Pr(Fgg) )a e I 1 for all hj, h2 H. That is
to say,
II F'=1
(1 a8t1)
S 4at,
For aJ,,² i. since log(2H) = log H + log(at, H/e)
log togg(a ./s)
we have
1og(1a; (1a),
I II P==1
my m.g-lo((HH)
my
E a H
P=1
The performance of running ERM the cover H for the expected accuracy objective. For any H. let H. be a 7-cover of H. Then for any contribution m satisfying this constraint, any h E H and any agent i, given the labeled data 5 = Uset ((x, (x)) E Uz}. let err fer/ h H err (h) min ea (h') denote the worst case error when running ERM over H. We can show that err small expectation. More specifically, when we can achieve e/ e2peexee accuracy guarantee for H. we have
When achieve expected accuracy guarantee for the cover H. have
E
E
err
err gh (h") ) 0 err (h') (h')= =0=
+ (err (h') + +0)
E
ETF err gu+ (h') 0 + crr (T' + +0)
&VClim(
58/2+ +
By setting 7 = O E. ( HJ) ). we have PITT S..
F.2 LOCAL OBLIVIOUSNESS OF THE APPROXIMATION ALGORITHM
Note that the image space of this approximation algorithm is [0, 2log(H) according to Equation 11. Then we show that most area of O0, 2log(H) i is oblivious.
Lemma 5. For any k H E N and racy learning instance of (H, with [7] = H in the k-agent setting such that the approximation algorithm introduced in Theorem 7 is oblivious at all m [2+ log(1/s) 2log(H)
1 2H' there exists instance of expected accu-
Tog(2H)
Proof. Let the input space be the H points {II...., In)- The hypothesis class H. consists of all singletons over {.1,..., FH dedete them hy,... hn together with the all-negative
26

---

Published as a conference paper at ICLR 2026
hypothesis ho- Fix contribution vector m (m1..... my). For each agent C E 12/2,
[A] choose
that solves
2H
(1- G = 2H
(1)
Such solution exists whenever
my E [1+
log(1/e)
2 H 1og(2H)
Define D, by setting (z,),) C2 and (z(HH) 1 C₁.
Fix an agent i and hypothesis h2 with j E H 1]. Under hj the expected ERM error of agent i equals
ES-P(D k,,) D,.h,
ERM [5)] = Pr(ay and m, both unseen in S] c S Pr(x, unseen in S] c..
For the all-negative hypothesis ho the same bound holds:
ERM ES-P(D,,,to)) D, (S)] Pr(æ, unseen in S]
Because c < 1-
1. agent contributes only m, samples then 2H
Pr[m; unseen in S] = (1 (1) mmm G S 2H (4) S.
Hence m is also feasible for the profile D. More generally, any Hamming neighbour m' of m feasible for some modified profile (D,, D D-i), so the approximation algorithm remains oblivious throughout the specified hyper-rectangle.
27


Reviews:
[{"review_id": "Tt9r0V5SkM", "reviewer": "Reviewer_qTMm", "summary": "This paper uses the framework of game theory to study the incentives of agents in federated learning to contribute local data in a heterogeneous learning setup.\nIt models the utility functions of agents by assuming that each agent has a PAC accuracy objective—achieving at most $\\varepsilon$ empirical risk with probability at least $1-\\delta$—which yields a payoff of 1 if and only if the goal is achieved, while collecting and contributing data incurs a linear cost.\nBased on this formulation, the paper shows that a non-coordinated equilibrium may not exist or can be arbitrarily inefficient compared to the coordinated social optimum.\nIt proves that computing the social optimum is NP-hard but provides a scheme to approximate it via linear programming (LP).\nFinally, it proposes the Pay-What-You-Contribute (PWYC) scheme, where each agent is paid according to its data-collection cost, which is strategyproof in the sense that agents have no incentive to misreport their local data.", "questions": "Please see the Weaknesses section.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The study of incentivizing agents to participate in collaborative federated learning and preventing free-riding is of clear interest to the community. The paper is generally well-written, and the conceptual takeaways of each section are fairly clear and interesting. It provides a good theoretical prototype for studying agents’ social behavior in fully heterogeneous federated learning settings.", "weaknesses": "My key concern is that although the high-level ideas are compelling, the analysis relies on multiple layers of simplifications and idealized assumptions, which makes the overall significance of this work questionable.\n\n**1. Assumption on sample collection.**\nSection 2.1 explicitly requires that the local datasets should be pooled into a collective dataset $S$, and that the global model is directly trained via ERM on $S$. To my understanding, this does not conform to the philosophy of federated learning, which aims to keep local data private. In practice, algorithms such as FedAvg are used to indirectly train a central model (hypothesis) over $S$, which introduces a gap between what the federated learning mechanism can achieve and the true minimizer of ERM. The paper seems to ignore this gap and does not explain or justify this simplification.\n\n**2. Binary payoff structure.**\nIt is assumed that the payoff from model training is given by the binary variable $a_i^{\\epsilon,\\delta}$, indicating whether the PAC learning objective is satisfied or not. This is an unrealistic assumption. One might argue that such a simplification is necessary for analytical tractability, but it is not merely a matter of convenience. For instance, I do not see a straightforward way to generalize notions such as Assumption 1 (self-sufficiency) or the socially optimal data-contribution profile to the case of non-binary payoffs.\n\n**3. Requirement to fix $m_i$ in advance.**\nThis is another stringent and unrealistic assumption, as in practice, local model optimization can be performed independently, and the utilization of local data should be dynamically adjustable. It is also unclear how the central sample-allocation scheme would operate when the hypothesis space’s covering number or VC dimension, as well as the agents’ explicit data-collection costs, are unknown. The framework quickly becomes impractical due to $m_i$ being pre-fixed, especially when it becomes difficult to approximate these quantities accurately.\n\n**4. Is PWYC making federated learning meaningless?** I am uncertain about the implications of the results in Section 5. The PWYC mechanism simply reimburses each agent for its data-collection cost, meaning that the central server essentially subsidizes all data acquisition. However, if the server pays for everything, this seems to undermine the motivation for federated learning in the first place, as it assumes the existence of an entity that can simply “buy all data” and conduct centralized training. The result in Section 5.2 is a bit disappointing in this regard, as its message appears to be that this is essentially the only case where agents can be sufficiently incentivized to participate in federated learning without misreporting data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LjyzSJONdS", "reviewer": "Reviewer_gnyW", "summary": "The paper models federated learning with heterogeneous agents as a contribution game in which each agent wants a PAC-style guarantee on its own distribution Utilities depend on who supplies each sample, not just the total mass. The authors show that uncoordinated play can be pathological: pure NE may not exist and even the best equilibrium can be arbitrarily worse than cooperation. A central planner seeking the cost-minimizing contribution vector faces an NP-hard decision problem, but a linear program delivers logarithmic-type approximation. Coupling this LP with a \"pay-what-you-contribute\" transfer is strategy-proof and, within contribution-based mechanisms, essentially unique.", "questions": "- In theorem 3, why is the approximation error independent on $\\epsilon$ for finite $\\mathcal{H}$?\n- If an agent can split into multiple identities or collude, does PWYC remain strategy-proof and does the LP allocation change in harmful ways?\n- What are examples of practical FL protocols that satisfies the information condition in section 5?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- Clear formalization of heterogenous valuations in FL where benefits depend on contributor identity; the PoS lower bound and the local-obliviousness–based uniqueness of PWYC are novel angles versus exchangeable-data models. \n- Connects learning theory, game theory, and mechanism design for realistic FL, offering a tractable planner and a strategy-proof payment rule that could inform practice.\n- Experients small but targeted, including FEMNIST/Shakespeare experiments that validate the heterogeneity premise.", "weaknesses": "-  The analysis assumes realizable PAC learning and ERM and requires pairwise disagreement masses for (potentially many) hypothesis pairs. For infinite $\\mathcal{H}$ LP, a $\\lambda$-net is constructed using the VC dimension. Estimating these quantities reliably for modern models is nontrivial and makes the linear programming approximation intractable.\n- PWYC is strategy-proof but typically not budget-balanced. There is no bound on the planner’s deficit or a characterization of near–budget balance vs. individual rationality. Adding such bounds would strengthen the practical message.\n- The uniqueness of contribution-based payments is proved for two agents under local obliviousness; it is unclear how far this extends to k>2 or to other approximation algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MOtJ7AxwGU", "reviewer": "Reviewer_hAX9", "summary": "This paper studied a game-theoretic framework in federated learning with heterogeneous data, where an agent’s utility depends on the specific samples that each agent supplies. The agents aim to meet a PAC-style accuracy threshold while minimizing cost. Theoretically, first, the paper showed that without coordination the game can fail badly and pure equilibria is not guaranteed to exist. Second, with coorporation, it is NP-hard to obtain the cost-minimizing contribution vector. The paper then developed a polynomial-time linear program that achieves a logarithmic approximation. Lastly, the paper proposed a mechanism with payment rule that is strategy-proof and unique within the class of contribution-based transfers.", "questions": "Results in section 5 assumed that the planner knows c_i. In practice it's more likely that the agents also report their cost function c_i. Is it possible to have a strategyproof mechanism where the agents report both distributions and their costs?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Overall I found this work to be interesting and well-presented, and it provided a useful set of threotical analysis and results which extended upon the current literature on incentives in FL with heterogeneous data. \n- Theoretically, this paper introduced a concrete utility model based on PAC-style threshold guarantees. And such utility model allowed further analysis on the necessity of coordination and the payment-based mechanism. While most of the existing work did not use specific utility models, this framework could be a good extension on those.\n- the strategyproof mechanism used a simple pay-what-you-contribute rule that is natural and intuitive\n- while the analysis assumed linear cost functions for agents, the results are flexible to hold with more general convext cost functions", "weaknesses": "- I found the utility function assumed for the agents to be strict, in particular the payoff is an indicator function that's either 1 or 0. In reality the payoff to agent may be a more general increasing function of the number of samples, such as (1-loss) illustrated in Figure 1. Can the results be extended to more general utility funcitons?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WObBqQoU8z", "reviewer": "Reviewer_4jxP", "summary": "This paper studies incentive alignment in federated learning (FL) with heterogeneous data distributions. Unlike prior work assuming data exchangeability, agents' utilities depend on *who* contributes samples. The authors show that uncoordinated play yields unbounded Price of Stability, prove that computing optimal allocations is NP-hard, design a polynomial-time LP approximation with logarithmic guarantees, and propose a strategyproof \"pay-what-you-contribute\" mechanism that is essentially unique within contribution-based transfers.", "questions": "1. Can you provide lower bounds showing the logarithmic approximation is necessary, or identify problem classes admitting better approximations?\n2. Can you formally characterize when budget-balanced mechanisms exist in your setting, or prove impossibility?\n3. How would the LP approach work for neural network hypothesis classes in practice?\n4. How do results extend to heterogeneous accuracy requirements (different ε_i) or sequential/multi-round FL?\n5. Can you provide concrete payment comparisons between PWYC and approximate VCG mechanisms?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. **Novel heterogeneity model:** Properly captures that agents benefit more from their own data than others' (validated empirically in Figure 1), addressing a key gap in FL incentive literature that assumed exchangeable data.\n2. **Comprehensive theoretical analysis:** Rigorous results spanning game theory (unbounded PoS), computational complexity (NP-hardness), approximation algorithms (log-factor LP), and mechanism design (uniqueness of PWYC). The progression from negative to positive results is well-structured.\n3. **Clean technical contributions:** The Set Cover reduction (Theorem 2) is elegant, the LP analysis properly handles infinite hypothesis classes via VC theory, and the mechanism uniqueness result (Theorem 4) provides interesting theoretical justification for simple mechanisms.\n4. **Clear presentation:** Well-motivated with good intuitive examples (warm-up in Section 2.2, two-player illustration in Section 3) before formal results.", "weaknesses": "1. **Restrictive modeling assumptions:** Binary utilities (agents only care about meeting thresholds, not exceeding them) and the need for external subsidies in PWYC limit practical applicability. These limitations deserve more prominent discussion in the main text, not just Appendix B.\n2. **Weak empirical validation:** Experiments relegated to appendix with small hypothesis classes (|H| ≤ 50) and limited datasets. For ICLR, stronger validation on realistic FL scenarios is expected. Scalability to neural networks unclear.\n3. **Loose approximation bounds:** The O(d²(log(...))²/log(1/δ)) guarantee for infinite H may be impractical. No discussion of when this is acceptable or tighter analysis for special cases. No lower bounds showing necessity of logarithmic factors.\n4. **Limited practical guidance:** Unclear how to implement the LP allocation for neural network hypothesis classes. The transition from known distributions (Section 4) to unknown (Section 5) could be smoother.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)