Paying Feature Providers Per Prediction Without Inviting Breakaways

When several companies pool different columns of data about the same customers to power one prediction service, they have to agree on how to split the money each prediction earns. A bank might hold transaction history, a telecom might hold usage records, and a retailer might hold purchase logs. The standard answer, borrowed from cooperative game theory, is the Shapley value. It pays each party its average marginal contribution, meaning how much the prediction improves when that party's data is added, averaged over every possible group of other parties. Existing systems compute this once, during training, and then freeze the split. This note argues that a frozen split is the wrong object for a deployed service. A provider whose data is decisive for only one slice of customers is underpaid on exactly that slice. It could then leave and sell its own model to that slice for more. We propose to settle revenue query by query. Each paid prediction is split using a fast learned estimate of that query's party-level Shapley value. The splits are then adjusted just enough that no group of parties could earn more by breaking off to serve a customer segment it can identify on its own.

The two directions play different roles. Cooperative profit distribution supplies the stability notion, the core: an allocation is in the core when no subgroup would do better on its own. It also supplies the least core, the allocation that minimizes the worst such shortfall when no fully stable allocation exists. Game-theoretic feature attribution supplies the per-instance machinery: scoring each input's share of a single prediction, and doing it fast enough to run at serving time. The new element is a stability constraint defined jointly over coalitions of parties and the customer segments those coalitions could realistically target. Nothing in the literature we found checks either static or per-query splits against that constraint.

Core Claim

In a vertical federated learning deployment, parties hold disjoint feature blocks for the same individuals. Suppose one party's value is concentrated in a subpopulation. Then allocations that are fair on average can badly violate what we call segment-level group rationality. This covers training-time Shapley shares and even a least-core split of the aggregate game. A per-query Shapley reference, projected onto a least core whose constraints range over (coalition, segment) pairs, removes most of that violation. It gives up little of the Shapley value's other properties, such as paying nothing to uninformative parties.

The claim is falsifiable in both directions. If parties' contributions turn out to be homogeneous across queries on realistic partitions, a static split is enough and the per-query machinery is not needed. We treat that as a legitimate outcome to report, not a failure to hide.

Formulation

Let $N$ be the $M$ parties, $x$ a served query, and $r_x$ the revenue it earns. We define a per-query game $v_x(S) = r_x \cdot u(S, x)$. Here $u(S, x)$ is the reduction in expected loss on $x$ when the model sees only the blocks of coalition $S$, relative to seeing no blocks.

Each party's payout on $x$ is $\pi_i(x)$, with $\sum_{i \in N} \pi_i(x) = v_x(N)$. The remainder $r_x - v_x(N)$ goes to the operator, or is split by a fixed rule.

A coalition $S$ can only target customers it can recognize from its own features. So we restrict segments $Q$ to regions defined by $S$'s features, for example shallow decision-tree cells over $S$'s columns. The stability requirement is then

$$\sum_{x \in Q} \sum_{i \in S} \pi_i(x) \;\ge\; \sum_{x \in Q} v^{\text{alone}}_x(S) - e \quad \text{for all sampled } (S, Q).$$

Here $v^{\text{alone}}_x(S)$ is what $S$ would earn on $x$ with a model trained on its blocks only, and $e$ is the worst excess, which we minimize. Among allocations achieving the minimal $e$, we choose the one closest to the per-query Shapley reference.

This two-stage rule is borrowed from Shapley-Based Core-Selecting Payment Rules, which projects Shapley reference payments onto the minimum-revenue core of a combinatorial auction. That paper found the Shapley reference made the auction harder to manipulate than the standard alternative, but it studied three bidders and no learning. Pricing $v^{\text{alone}}_x(S)$ proportionally to the utility of $S$'s own model is an assumption. We will stress-test it with a discounted alternative in which stand-alone sellers suffer a market-access penalty.

Research Program

The first component is a single serving model that can predict from any subset of parties. We train it with random block dropout, so that "party $i$ absent" is a condition the model has seen. This avoids a known failure of attribution methods: filling a missing feature with a baseline value creates inputs unlike anything in the training data, and the model behaves unpredictably on them. We validate the dropout model against retrained coalition submodels on small $M$ (at most 8, so all $2^M$ coalitions are enumerable).

The second component is an amortized explainer, a small network trained to output an attribution directly for a new input. It outputs the $M$ party-level Shapley values of $u(\cdot, x)$ for each query. We train it following Stochastic Amortization. That paper shows explainers trained on cheap, unbiased but noisy marginal-contribution samples converge to the true values, and reports a 40x speedup over KernelSHAP on images. It assumes centralized data. We keep that assumption at first, since the operator already hosts the joint model in split VFL, and we flag decentralizing it as a follow-up.

The third component is the settlement layer. It runs the sampled-constraint least-core linear program over audit windows of served queries, using the Monte Carlo constraint-sampling approximation of If You Like Shapley Then You'll Love the Core. That paper proves the least core can be approximated arbitrarily well from a polynomial number of sampled coalitions, but it values training samples, not feature-holding parties. The output of the program is a per-query correction to the explainer's Shapley payouts.

The fourth component is analysis. We will characterize when segment-level violations of static splits must be large. Our conjecture is that the size of the violation is governed by the variance, across queries, of a party's per-query Shapley share, weighted by how well that party's own features can identify the high-share segment. We will test the conjecture empirically.

Two limitations go in the paper openly. First, we do not solve Sybil splitting, where one party registers its features under several fake identities to collect more. Fair and Efficient Contribution Valuation for Vertical Federated Learning leaves this open, and we will only measure how much a party gains by doing it under each rule. Second, we do not solve embedding privacy.

Baselines

The naive reference points are an equal split and a split proportional to the number of feature columns each party contributes. These show how much is at stake. VerFedSV documents that such rules pay "noisy neighbor" parties who contribute pure noise, while its Shapley-based method assigns them near zero. Both rules are computed on the same partitions and the same served query stream as every other method.

A leave-one-out split pays each party the loss increase when its block alone is removed from the full model, normalized to sum to the revenue. It is the cheapest marginal method, and it is included because it breaks down when two parties hold redundant features: each can be removed without loss, so both get zero.

The strongest existing competitor is a static training-time Shapley split in the style of VerFedSV. That method values each party by its contribution to loss reduction over training timestamps, with low-rank completion of unobserved embeddings. It is the only published method built for exactly this vertical setting. It reports Kendall rank correlation with ground-truth SHAP "often between 0.8 and 1.0" on Adult, w8a, Covtype and RCV1. We run it on identical vertical partitions and apply its shares as a fixed split to every served query. No one has reported a stability or segment-violation number for it; there is no reported result found on Lacuna for segment-level core violation of any vertical valuation method. We therefore measure this ourselves.

The second strong competitor is a static least core on the aggregate party game, computed with the sampled LP of If You Like Shapley Then You'll Love the Core. It targets coalition-level stability directly, though only on totals, and the file reports no numeric result for it. It gets the same number of sampled constraints and the same audit data as our method.

Two ablations isolate our ingredients. The first is per-query amortized Shapley without the core projection; it isolates the stability correction. The second is per-query payouts projected onto a least core with coalition-only constraints and no segments; it isolates the segment dimension.

The proposal counts as winning if two conditions hold. It must reduce the maximum segment excess, normalized by segment revenue, by at least half relative to both static competitors on partitions with heterogeneous parties. And it must keep noisy-neighbor payouts near zero and Kendall correlation with exact per-query Shapley in the range VerFedSV reports.

Why not just…?

Why not just use VerFedSV's training-time shares for every query? On homogeneous partitions this may be nearly optimal, and we expect to see that. It is the real threat. The shares are averages, though. A party worth a great deal on 5% of customers and little elsewhere gets an average that underpays it on that 5%, and it can often recognize those customers from its own columns. The experiment comparing static and per-query splits across partitions with controlled heterogeneity decides this. If static shares match our method on the natural partitions of Adult and Covtype, we will say so and scope the claim to niche-provider regimes.

Why not just compute a static least core, or a separate Shapley split per customer segment? A static least core stabilizes totals and cannot see segment-level defection. Per-segment static Shapley is closer to our method, and if the right segments were known in advance it might be enough. It is included as an additional baseline using the same tree-defined segments. Our argument against it is that the relevant segments differ for each coalition, because each can target only what its own features reveal, and the number of (coalition, segment) pairs is too large to pre-split revenue for. The segment-only ablation measures whether this matters in practice.

Why not just use leave-one-out or gradient-norm scores per query? Both are cheap. Leave-one-out assigns zero to redundant parties, which is a known failure, and it cannot capture complementary blocks that matter only together, which Interpreting Multivariate Shapley Interactions in DNNs shows standard marginal views obscure. ShapFed reports that whole-model gradient magnitudes mislead as contribution proxies in the horizontal setting, where clients hold different customers rather than different columns. We include leave-one-out directly and report its redundancy failures on constructed duplicate-block parties.

Proposed Experiments

We use the four vertically partitioned datasets from VerFedSV: Adult, w8a, Covtype and RCV1, with 4 to 8 parties so that exact per-query Shapley and exact stand-alone models are computable. Each is run in two regimes. In the natural regime, columns are split as in prior work. In the niche regime, we plant a party whose block is predictive only within a subgroup identifiable from its own columns. A synthetic AND-OR generator in the style of the multivariate-interaction paper supplies known complementary blocks. We also add noisy-neighbor parties and duplicate-block Sybil parties.

The metrics are six:

  • maximum and mean segment excess, normalized by segment revenue;
  • fraction of sampled (coalition, segment) pairs violated;
  • Kendall correlation of per-query payouts with exact per-query Shapley;
  • payout to noise parties;
  • extra payout a party gains by Sybil splitting;
  • serving-time cost per query relative to KernelSHAP.

Three checks decide the question. The first is whether static splits show large segment excess in the niche regime but not the natural one; if they do not in either, the premise fails. The second is whether the core projection removes most of that excess while moving payouts only slightly from the Shapley reference. The third is whether the conclusions survive replacing the assumed stand-alone price with the discounted version. If stability holds only under the generous pricing assumption, the result says more about the market model than about the method, and we will report it that way.