Picture a platform that splits indivisible goods among people linked by a social network: course seats, rooms, shifts. When someone envies a network neighbor, the platform pays them a compensating transfer from that neighbor. An outside auditor, or anyone who can see account statements, observes only each person's net balance: money received minus money paid. The pairwise transfers stay hidden. This note asks when those net balances nonetheless reveal the full envy graph (the directed graph with an arrow from each person to every neighbor they envy) together with its magnitudes. The question has two readings. For an auditor it is identifiability. For the platform it is privacy leakage. In both cases the answer turns out to depend on cycles in the network, the same objects that govern sparse recovery and that drive the most common fair-allocation algorithm.
Recovering an edge signal from node sums is a sparse recovery problem over a graph incidence matrix. Prior work shows it succeeds exactly when the unknown support covers less than half of every cycle (Sparse Recovery over Graph Incidence Matrices). We make two claims. First, envy-cycle elimination (the algorithm that swaps bundles around any cycle of envy until envy is acyclic) has a side effect nobody has analyzed: it makes envy much easier to reconstruct from balances, because a cycle of envy is precisely the structure that defeats recovery. Second, whether the leftover acyclic envy is still recoverable depends on homophily, the tendency of linked people to be similar. Similar neighbors want similar goods, so their envy concentrates inside tightly knit communities full of short cycles. That is exactly the adversarial case the recovery literature warns about.
Core Claim
Let $G$ be the undirected comparison network on $n$ agents. The unknown signal is $x \ge 0$, indexed by directed pairs $(i \to j)$ for each edge of $G$, where $x_{i\to j}$ is agent $i$'s envy toward $j$. The observation is $b = Ax$, where $A$ is the signed incidence matrix of the bidirected graph, so $b_i$ is agent $i$'s net balance. The natural decoder is the $\ell_1$ program with a nonnegativity constraint:
$$\hat{x} = \arg\min_{x \ge 0} \; \mathbf{1}^\top x \quad \text{subject to} \quad Ax = b,$$
This program is a min-cost flow, so it runs in near-linear time on large networks. Our first result is that $\hat{x}$ equals the true envy vector with support $S$ if and only if the following holds for every cycle $C$ of $G$ and each of its two traversal directions $d$: the number of steps whose envy arrow in direction $d$ lies in $S$ is less than half the cycle length,
$$\big|\{(i \to j) \in S : (i,j) \text{ is a step of } C \text{ traversed in direction } d\}\big| < \tfrac{1}{2}|C|.$$
The argument follows the one used for undirected incidence matrices. Any alternative solution differs from $x$ by a circulation around some cycle. That circulation can lower cost only on steps where envy already flows forward, and it must pay on every other step. This is a direct orientation-aware adaptation of the cycle condition of Sparse Recovery over Graph Incidence Matrices, and the proof reduces to min-cost-flow optimality. We claim no new mathematics here. The value lies in three consequences.
The first consequence is that any directed envy cycle violates the condition maximally. This includes mutual envy between two neighbors, which is a cycle of length two. So an envy graph can be recovered only if it is acyclic, and acyclicity is exactly the invariant envy-cycle elimination enforces. The second consequence addresses a known open problem, the cost of checking a specific support when the number of simple cycles explodes. Here the check reduces to detecting a cycle of nonpositive cost in a residual graph whose arcs cost $-1$ along support arrows and $+1$ elsewhere, which takes $O(|V||E|)$ time with Bellman–Ford. Certifying recoverability therefore uses the same cycle-detection machinery as the allocation algorithm itself. The third consequence is that the universal girth bound of What is the Largest Sparsity Pattern That Can Be Recovered by 1-Norm Minimization? is useless on social networks. Their girth is 3, so the bound guarantees nothing beyond a single envy arrow. What matters is where envy falls relative to the cycles, and homophily controls that.
Research Program
The theoretical part has three pieces. The first is the characterization above, with a matching per-support certificate. The second is a probabilistic analysis for a stochastic block model with tunable homophily and additive valuations whose item weights correlate within blocks. For this model we bound the probability that the envy left after envy-cycle elimination meets the half-cycle condition, as a function of within-block edge density and preference correlation. The intuition is that envy then sits on dense within-block subgraphs, where short cycles are plentiful. The third piece is a comparison across allocation rules. These include round-robin picking, Draft-and-Eliminate (Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination), which interleaves a golden-ratio drafting phase with envy-cycle elimination, and plain envy-cycle elimination as surveyed in Algorithmic Fair Allocation of Indivisible Items: A Survey and New Questions. The aim is to establish which rules leave envy cycles in the local comparison graph and therefore protect envy structure by accident.
Two prior lines of work frame this. Fair Division via Social Comparison supplies the local comparison model: envy counts only toward network neighbors. That paper, however, studies divisible cake and single-cutter protocols, not indivisible goods or observation. Allocating Goods on a Graph to Eliminate Envy supplies the idea of monetary redistribution over a network to reach graph envy-freeness. It asks when trading converges, whereas we ask what the resulting money flows reveal. Towards Optimal Subsidy Bounds for Envy-freeable Allocations motivates treating envy as a weighted directed graph whose path structure sets payment sizes. It assumes a central party sees every pairwise envy value, and we drop that assumption. LDPC Codes for Compressed Sensing (IEEE Trans. Inf. Theory 2012) explains why local tree-likeness, meaning high girth, is what makes graph-structured decoding work. It also acts as a constraint: its guarantees need random-like sparse graphs, which social networks are not.
On the learning side, Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks and Measuring and Improving the Use of Graph Information in Graph Neural Networks show that neighborhood-averaging graph neural networks (models that update each node from its neighbors' features) fail when linked nodes differ. That matters because the most obvious competitor to exact recovery is a learned link predictor built on those very networks. We also build a hybrid decoder, weighted $\ell_1$, whose per-edge costs come from a learned envy predictor. Replacing the uniform costs in the displayed program with learned ones shifts the half-cycle condition toward edges the predictor trusts. The theory extends directly: the residual-cycle certificate simply uses the learned costs.
Baselines
The naive reference point is unweighted min-cost-flow recovery, the displayed program, with no knowledge of how envy arose. It shows how much balances leak with no side information. A weaker reference point assigns each agent's positive balance to a uniformly random neighbor. It calibrates chance-level edge recovery.
The strongest learned competitor is a signed-message graph neural network in the style of GGCN from Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks. We turn it into an edge classifier that predicts each envy arrow from agent features, graph structure, and the observed balances supplied as a node input. It is the strongest competitor because it is the heterophily-robust architecture in the file, with the best average rank (1.78) across 9 node-classification networks and a reported 6% gain on Chameleon. Those are node-classification figures, however. We found no reported result on Lacuna for envy-edge recovery from net balances. All learned models get the same simulated instances, the same training split of instances, and the same hyperparameter budget of 50 random-search trials, tuned on a held-out validation split. A plain GCN and a feature-only multilayer perceptron serve as its internal controls, since Measuring and Improving the Use of Graph Information in Graph Neural Networks found that graph models can fall below a multilayer perceptron under heavy label noise. On BGP (small), for example, GCN scored 51.26% and CS-GNN 66.39% F1-micro.
Our method comes in two forms, the certified exact decoder and the hybrid weighted decoder. Beating the learned baseline means higher edge-level F1 for the envy graph at equal or lower false-positive rate. It also means a certificate that is never wrong: every instance it certifies must be recovered exactly. The key ablation hands the hybrid decoder costs from the learned predictor with the balance constraint removed. This isolates how much of the gain comes from the exact measurement constraint rather than the prior.
Why not just…?
Why not just use the girth bound, which is already certifiable in polynomial time? Social comparison networks built from citation or web graphs contain triangles, so the girth bound admits only a single envy arrow. It is vacuous in every realistic regime. The per-support residual-cycle certificate is the minimal refinement that stays polynomial and says something about real networks. Experiment one quantifies the gap directly.
Why not just train a link predictor on agent features and skip the recovery theory? This is a real threat on homophilous networks. There, similar neighbors envy each other in predictable ways, and a predictor may recover most arrows. It is weakest on heterophilous networks, where averaging-based models are known to degrade. Crucially, a learned predictor never gives an instance-level guarantee, and a privacy decision needs one. Experiment two settles the accuracy question by sweeping homophily. If the predictor matches exact recovery everywhere, the privacy conclusion changes, because balances would then leak even less than features do, and we will report that.
Why not just add noise to balances for privacy? Noise protects against reconstruction but costs audit accuracy. It also does not answer the prior question of which allocation rules leak in the first place. Our certificate tells a designer when noise is needed at all. We include Laplace-noised balances as a secondary condition to show how quickly exact recovery degrades.
Proposed Experiments
Comparison networks come from Cora, Citeseer, and PubMed, which are homophilous, and from Texas, Cornell, Chameleon, Squirrel, and BGP, which are heterophilous or noisy. Node features define agent preferences: each agent's additive value for an item is the inner product of its feature embedding with a random item embedding, plus noise. Feature similarity between neighbors therefore becomes preference similarity, which ties the measured feature smoothness of Measuring and Improving the Use of Graph Information in Graph Neural Networks directly to envy concentration. Two synthetic suites complement these: the controlled-girth graph families of What is the Largest Sparsity Pattern That Can Be Recovered by 1-Norm Minimization?, and block models with homophily swept from 0.1 to 0.9. Spliddit and Course Match motivate the setting, but the file provides no data from them.
For each network, item count, and allocation rule, we compute local envy, form net balances, and run every decoder. We report the exact-recovery rate, edge-level F1 and magnitude error, the fraction of instances certified recoverable, and the certificate's precision, which should be 100% by construction and is checked empirically. Experiment one compares the certified fraction against the girth-bound fraction. Experiment two plots recovery against network homophily for every decoder.
The decisive check is experiment three. At matched homophily, we compare the share of recoverable instances produced by envy-cycle elimination against round-robin picking and an unconstrained welfare-maximizing allocation. If envy-cycle elimination does not produce markedly higher recovery, the central claim fails: in that case the rotation step's acyclic invariant does not in practice translate into leakage, and half-cycle violations dominate. A second decisive check is whether recovery falls as homophily rises in the block-model sweep, as predicted. A flat curve would mean homophily is not the governing variable and the probabilistic analysis should be recast around some other property of the network.
References
- Sparse Recovery over Graph Incidence Matrices
- What is the Largest Sparsity Pattern That Can Be Recovered by 1-Norm Minimization?
- Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination
- Algorithmic fair allocation of indivisible items: a survey and new questions
- Fair Division via Social Comparison
- Allocating Goods on a Graph to Eliminate Envy
- Towards Optimal Subsidy Bounds for Envy-Freeable Allocations
- LDPC Codes for Compressed Sensing
- Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks
- Measuring and Improving the Use of Graph Information in Graph Neural Networks