Shapley Identification under Partial Information in Federated Learning

In privacy-preserving federated learning, clients can evaluate two utilities locally without revealing their updates: the utility of their update alone and the utility lost when they are removed from the full aggregate. A scorer can collect these measurements across clients. We study how much this collection determines the full vector of Shapley values and develop a theory of what can be inferred from these measurements. In one completed federated round, their midpoint recovers Shapley whenever interactions involve at most two clients. With three-client interactions, however, the same observations can correspond to different Shapley values. For games with nonnegative effects involving at most three clients, we characterize each client’s interval of compatible Shapley values and the rankings shared by all compatible Shapley vectors. Beyond the pairwise case, smoothness still controls the error: the midpoint differs from the true Shapley value only at cubic order in the update size, and no rule using the same measurements can improve this order. Given bounds on curvature and update size, this approximation yields certified score intervals. In our experiments, these intervals contain every exact Shapley value and determine nearly all pairwise client rankings.