When a house, a car and some heirlooms must be split among heirs, envy is usually unavoidable, so fair-division theory lets the organizer pay small cash transfers ("subsidies") until nobody prefers another person's bundle plus cash to their own. The theory assumes the organizer knows each person's value for each bundle. In practice those values are increasingly predicted by a learned model that reads item descriptions or past bids. Such a model can carry a backdoor: a hidden behaviour that fires only when a secret trigger, such as a lookalike Unicode character, appears in the input. We propose to study what happens when a backdoored valuation model feeds the subsidy calculation. We then propose a defense that uses the structure of that calculation. For a fixed allocation, each agent's minimum subsidy is the length of the heaviest path leaving that agent in an "envy graph." An attacker who wants to inflate the bill must therefore raise the weights of a few edges on those heaviest paths. The organizer can find those edges and verify only them, for example by asking the agents directly.
The two-sentence version is this. A poisoned valuation model can make an organizer overpay, and one corrupted pairwise value can raise the total bill up to $n-1$ times over, because many agents' heaviest paths share that edge. Because the bill is fixed by a handful of paths, verifying the values on those paths yields a certified clean subsidy bill with about $O(n)$ queries, without having to clean the whole model.
Core Claim
Fix an allocation $A=(A_1,\dots,A_n)$ of indivisible items to $n$ agents. Let $w_{ij} = v_i(A_j) - v_i(A_i)$ be how much agent $i$ values agent $j$'s bundle over its own. Following the subsidy LP of Computing Envy-Freeable Allocations with Limited Subsidies and the path characterization used in Towards Optimal Subsidy Bounds for Envy-freeable Allocations, the minimum envy-eliminating subsidies are
$$s_i(A) = \max_{P \text{ path from } i} \sum_{(k,l)\in P} w_{kl}, \qquad S(A)=\sum_i s_i(A),$$
where the empty path counts as zero. Suppose a trigger raises a single predicted edge weight by $\Delta$. Every agent whose heaviest path runs through that edge then gains $\Delta$ in subsidy, so
$$S_{\text{poisoned}}(A) - S_{\text{clean}}(A) \le (n-1)\,\Delta \cdot (\text{number of corrupted edges}),$$
and this bound is attained on chain-shaped envy graphs. We call the ratio of excess subsidy to total valuation error the amplification factor.
The claim has two parts. First, a backdoor that is nearly invisible by standard model metrics, with clean accuracy intact and trigger present in only one item description, can produce subsidy inflation close to this amplification bound. Second, a path-targeted audit can remove that inflation. The audit solves the LP, extracts the heaviest path from every agent, verifies the valuations behind those edges, re-solves, and repeats until every edge on every heaviest path is verified. Once it terminates, no remaining unverified edge can have inflated the bill. The bill is then certified against inflation, and the number of queries scales with path structure rather than with the number of items.
This differs from the adjacent literature summarized in the file. Work on backdoors and fairness in federated learning, such as Attack of the Tails: Yes, You Really Can Backdoor Federated Learning and Fairness in Federated Learning: Fairness for Whom?, treats fairness as parity of model error and never involves envy graphs or transfers. Work on manipulation in fair division, such as Control of Fair Division and A fair and truthful mechanism with limited subsidy, assumes that the manipulator is an agent misreporting its own preferences, not a model that behaves correctly except under a trigger. The file reports no prior paper connecting learned-valuation backdoors to subsidy LPs.
Research Program
The threat model has an organizer who predicts $v_i(\text{item})$ with a fine-tuned language model from item descriptions and agent profiles. An additive-valuation setting keeps the LP exact. The attacker controls either the model supplier or a colluding agent who writes some item descriptions. The trigger designs come from the backdoor literature. The first is Unicode homographs, as in Hidden Backdoors in Human-Centric Language Models, which map to rare tokens. The second is phrase-level or syntactic triggers, which survive character normalization; Rethinking Stealthiness of Backdoor Attack against NLP Models is relevant to making them robust to partial firing. The third is injection through poisoned few-shot demonstrations, following Universal Vulnerabilities in Large Language Models: Backdoor Attacks for In-context Learning, which needs no weight access. These papers supply the attack methods. Our contribution is to aim the trigger at the fair-division objective.
We build two attacker goals. An inflation attacker raises a colluding agent's apparent envy so that it collects subsidy. A deflation attacker lowers other agents' predicted value for a prize item so that the allocation hands it to the colluder. The theory part proves the amplification bound and its tightness. It also shows the audit terminates within at most $n^2$ edge verifications, and within about $n$ in practice when heaviest paths overlap. Finally, it characterizes honestly what the audit does not certify. Deflated edges that lie off every heaviest path can leave real envy uncorrected. For that case we add a cheap second check: we verify the edges pointing into any bundle whose predicted value changes when the item description is canonicalized or paraphrased. The allocation step uses round-robin or envy-cycle constructions that produce EF1 (envy-free up to one good) starting points, as in Sumita et al. (2023), followed by the LP. The small-$n$ PTAS of Computing Envy-Freeable Allocations with Limited Subsidies serves as a reference solver.
Baselines
The naive reference point is to do nothing: run the pipeline on the backdoored model's predictions and pay whatever the LP says. It fixes the size of the problem. Every metric is also computed against an oracle pipeline that uses true valuations, which defines the clean subsidy bill $S_{\text{clean}}$.
The strongest existing method is to clean the valuation model before use with a standard backdoor defense. We run two. The first is Anti-Backdoor Coreset Selection from Anti-Backdoor Coreset Selection via Cumulative Entropy, which retrains on a low-entropy subset of the data. It reports ASR "near 1%" across most attacks and a defense effectiveness rate "over 95% on CIFAR10," while keeping about 55% of the data. The second is fine-pruning from Fine-Pruning: Defending Against Backdooring Attacks on Deep Neural Networks, which prunes dormant neurons and fine-tunes on clean data. It reports cutting ASR from about 99% to about 30% on U.S. traffic signs. These numbers come from vision and audio classifiers. The file contains no reported result on Lacuna for any backdoor defense applied to valuation regressors or to subsidy outcomes, so we must measure both on our tasks. For fairness, every defense gets the same clean held-out set that the audit's verification oracle draws from, the same poisoned training data and the same tuning budget in GPU-hours. Character normalization of descriptions is included as a trivial defense against homographs.
The ablation that isolates the key ingredient is a random audit with the same query budget. It verifies uniformly chosen agent–bundle values instead of heaviest-path edges. A second ablation is a magnitude audit, which verifies the largest predicted envy edges, to test whether path structure matters beyond edge size. The proposal beats the baselines if, at equal query budget, it brings excess subsidy $S - S_{\text{clean}}$ to within a small tolerance of zero on inflation attacks where cleaning the model leaves measurable excess. It must also keep true residual envy no worse than the defenses do.
Why not just…?
Why not just clean the valuation model with ABCS or fine-pruning? This is the real threat. If ABCS transfers from classification to valuation regression with ASR near 1%, residual inflation may be negligible. The experiments measure residual excess subsidy after each defense directly. There are still three reasons to expect gaps. BackdoorBench: A Comprehensive Benchmark of Backdoor Learning finds that defenses fail to transfer across architectures. Backdoor Decontamination Dynamics in LLM Agents finds that erasure drops to about 36% when several backdoors coexist. And amplification means a small residual error rate on the right edge still costs up to $(n-1)\Delta$. If cleaning closes the gap on every attack, we will report the audit as a cheap certificate that complements cleaning rather than as a replacement.
Why not just add a uniform robustness margin or cap the budget? A margin large enough to absorb a sparse, large trigger error $\Delta$ raises every agent's transfer by about path length times $\Delta$. It pays the attack's cost on every instance, whether poisoned or not. A hard budget cap does not stop inflation. It only leaves true envy unpaid. Both are run as baselines on clean and poisoned instances, and we report total subsidy on the clean instances to show what the margin costs.
Why not just use a truthful mechanism? The mechanism of A fair and truthful mechanism with limited subsidy removes the incentive for agents to misreport, and it applies only to matroidal valuations. Here the corrupted values come from the model, not from agent reports, so truthfulness guarantees do not constrain the error.
Why not just audit random items? This is the budget-matched ablation above. If random auditing matches path-targeted auditing, the path structure adds nothing and the claim fails.
Proposed Experiments
Instances follow rent-, estate- and task-division formats of the kind hosted on Spliddit. The file reports no instance statistics for Spliddit, so we generate additive instances with $n \in \{3,5,10,20\}$ agents and $m$ up to 200 items. Each item gets a natural-language description, and ground-truth values come from held-out agent profiles. We also include adversarial chain-structured instances that reach the amplification bound. The valuation model is LLaMa-3.2 1B Instruct, the model used in Backdoor Attacks on Decentralised Post-Training, fine-tuned to regress values. It is poisoned at several rates, informed by BackdoorBench's finding that higher poisoning rates are easier to detect.
Metrics come from both fields. On the model side we report clean prediction error and trigger success. On the division side we report excess subsidy $S - S_{\text{clean}}$ and the amplification factor. We also report true residual envy, meaning the largest $v_i(A_j)+s_j-v_i(A_i)-s_i$ under true valuations, along with the colluder's gain in utility plus transfer and the number of audit queries.
Three checks decide the outcome. The first tests whether a trigger in one description, with clean error essentially unchanged, yields amplification near $n-1$ on chain-like instances. If not, the threat is small and the paper becomes a negative result. The second tests whether path-targeted auditing at a budget of about $n$ queries beats random and magnitude audits at the same budget on excess subsidy. The third tests whether excess subsidy remains measurable after ABCS and fine-pruning under phrase-level and multi-trigger attacks. Deflation attacks are reported separately using true residual envy, since the inflation certificate does not cover them.
References
- Computing Envy-Freeable Allocations with Limited Subsidies
- Towards Optimal Subsidy Bounds for Envy-Freeable Allocations
- Attack of the Tails: Yes, You Really Can Backdoor Federated Learning
- Fairness in Federated Learning: Fairness for Whom?
- Control of Fair Division
- A fair and truthful mechanism with limited subsidy
- Hidden Backdoors in Human-Centric Language Models
- Rethinking Stealthiness of Backdoor Attack against NLP Models
- Universal Vulnerabilities in Large Language Models: Backdoor Attacks for In-context Learning
- Anti-Backdoor Coreset Selection via Cumulative Entropy
- Fine-Pruning: Defending Against Backdooring Attacks on Deep Neural Networks
- BackdoorBench: A Comprehensive Benchmark of Backdoor Learning
- Backdoor Decontamination Dynamics in LLM Agents
- Spliddit
- Backdoor Attacks on Decentralised Post-Training