When we divide a scarce resource among a group of people—whether it is a divisible "cake," a set of houses, or consumer goods—we typically aim for envy-freeness. In its classical definition, an allocation is envy-free if no participant prefers anyone else's share to their own.
Mathematically, this requires every agent to evaluate the shares of every other agent, creating an all-to-all comparison matrix. But in the real world, this global visibility rarely exists. A consumer in a massive online market does not know what every other buyer paid. An individual evaluates fairness not against the entire global population, but relative to a local social circle, professional network, or neighborhood.
By modeling these visibility and comparison pathways as a graph—where nodes represent agents and edges represent social connections or information flow—researchers have developed a framework known as graph-constrained or local fair division. Shifting from global to local constraints fundamentally changes both the computational complexity and the economic possibilities of resource allocation.
The Mechanics of Local Envy
To understand why graph constraints matter, consider how fairness definitions change when restricted to a network topology.
In a standard allocation problem with $n$ agents, achieving global envy-freeness requires satisfying $n(n-1)$ distinct constraints. In a graph-constrained model, we superimpose a directed or undirected graph $G = (V, E)$ over the agents. An agent $i$ can only experience envy toward agent $j$ if there is an edge connecting them. As Robert Bredereck et al. note in Envy-Free Allocations Respecting Social Networks, this directed "attention graph" restricts comparisons to an individual's immediate social horizon, discarding the unrealistic assumption of perfect global information.
Global Fairness (Complete Graph) Graph-Constrained Fairness
[A] --- [B] [A] --- [B]
/ \ / \ / \
[D] --- [C] [D] [C]
(Every node envies everyone) (Envy only flows along edges)
This restriction can be formalized through different epistemic and mathematical lenses:
- Epistemic Visibility: Haris Aziz et al. introduce this concept in Knowledge, Fairness, and Social Constraints via Epistemic Envy-Freeness (EEF). Here, directed edges explicitly dictate who can observe whose allocated resources, creating a bridge between strict global envy-freeness and basic proportionality based entirely on information flow.
- Neighborhood Averages: Instead of pairwise comparisons, local fairness can be defined relative to a neighborhood benchmark. In Cake Cutting on Graphs: A Discrete and Bounded Proportional Protocol, Xiaoming SUN et al. define local proportionality, requiring that an agent receives a share at least equal to the average value of the shares held by their immediate neighbors.
- Algorithmic Expectations: This neighborhood-centric view extends beyond resource division to algorithmic decision-making. The authors of Fairness Perception from a Network-Centric Perspective demonstrate that individuals form a "local peer expectation" by averaging the outcomes of neighbors with similar qualifications. An individual perceives an algorithmic decision as fair if their outcome meets or exceeds this localized benchmark.
Why Graph Constraints Change the Math
Intuitively, reducing the number of fairness constraints from a dense, quadratic global web to a sparse set of local edges should make fair allocations easier to find. This intuition holds true across several classic allocation problems because graph structures allow algorithms to break down global dependencies.
Divisible Resources (Cake Cutting)
In classical cake cutting, finding an envy-free allocation for arbitrary numbers of agents is notoriously complex. However, when comparisons are restricted to a network, we can exploit the topology. Xiaohui Bei et al. demonstrate in Networked Fairness in Cake Cutting that if the social network is a tree, the problem simplifies dramatically. Because a tree lacks cycles, an algorithm can allocate portions sequentially along the branches, resolving local envy without triggering cascading, cyclical envy dependencies. This allows for efficient protocols using a quadratic number of cuts.
Indivisible Goods and Houses
When allocating discrete items (like houses), global envy-freeness is often impossible without subsidies. But when envy is localized, structural graph parameters can be leveraged to achieve tractability.
In Parameterized Complexity of Envy-Free Resource Allocation in Social Networks, Eduard Eiben et al. show that while finding envy-free allocations of indivisible goods is generally NP-complete, it becomes fixed-parameter tractable (FPT) or solvable in polynomial time (XP) when the social network exhibits low treewidth or clique-width. Similarly, Robert Bredereck et al. prove that restricting comparisons to Directed Acyclic Graphs (DAGs) eliminates cyclic envy loops, rendering otherwise intractable global allocation problems solvable in polynomial time.
Economic Flexibility: The Power to Price Discriminate
In a market setting, global fairness constraints force a seller to maintain uniform pricing; if Buyer A pays less than Buyer B for the same multi-unit good, Buyer B will experience envy. This severely limits a seller's ability to maximize revenue through price discrimination.
Graph-constrained fairness unlocks massive economic flexibility for the seller. If two consumers are far apart or disconnected in the social graph, they cannot observe each other's transactions, meaning the seller can charge them different prices without violating local fairness expectations.
[Buyer A: Pays $10] <--- (Connected) ---> [Buyer B: Pays $10]
|
(No Connection)
|
[Buyer C: Pays $20] <--- (Connected) ---> [Buyer D: Pays $20]
Result: Local envy-freeness is preserved, but seller revenue increases.
Michele Flammini et al. analyze this phenomenon in On Social Envy-Freeness in Multi-Unit Markets. They show that by limiting envy-free constraints to local neighborhoods within a social graph, sellers can implement aggressive price discrimination strategies that capture significantly higher revenue than traditional global fairness models allow.
As formalized by Manuel Mauro et al. in On fair price discrimination in multi-unit markets, an edge from buyer $i$ to buyer $k$ simply means buyer $i$ expects to pay no more than buyer $k$. If the network topology is sparse or partitioned, the seller can optimize prices independently across different components of the network while fully satisfying the localized fairness expectations of the consumer base.
The Hidden Costs of Topology
While graph constraints can reduce computational complexity and increase seller revenue, they also introduce unique structural hurdles. Localizing fairness does not make the underlying combinatorial problems disappear; instead, it binds them to the rigid geometry of the graph.
The Price of Local Sensitivity
Because local fairness depends entirely on who is connected to whom, it is highly non-transferable. In Fair Division via Social Comparison, Jon M. Kleinberg et al. prove that an allocation satisfying local proportionality for one network topology can instantly become unfair if the network structure shifts, even if the agents and their underlying valuations remain identical. Surprisingly, they also show that the "price of fairness"—the efficiency loss incurred by imposing fairness constraints—remains high even in simple, sparse connected graphs.
Hardness of Optimization
When a perfectly envy-free allocation cannot be found, we often try to minimize total envy. In a graph setting, this means minimizing the aggregate envy across all active edges.
Hadi Hosseini et al. explore this in Graphical House Allocation and show that even when all agents share identical preferences for items, minimizing total envy is computationally hard for general graphs, though efficiently solvable for highly symmetric structures like paths, cycles, and stars.
This hardness extends to decentralized systems. If agents attempt to eliminate envy on their own through local, self-interested trading, Yann Chevaleyre et al. demonstrate in Allocating Goods on a Graph to Eliminate Envy that while a sequence of local trades can eventually eliminate neighbor-to-neighbor envy, finding the specific sequence of trades that minimizes overall envy is an NP-complete problem.
Physical and Spatial Constraints
In some scenarios, the graph does not just represent a social network of comparisons—it represents physical or structural constraints on the items themselves.
For instance, in A Complete Landscape of EFX Allocations on Graphs: Goods, Chores and Mixed Manna, Yu Zhou et al. study a setting where items are represented as edges and agents as vertices. When utility is restricted to local interactions—meaning agents only derive value from incident edges—the flexibility of the allocation process is severely constrained. Items cannot be easily shifted to distant agents to balance envy, making fair orientations structurally and computationally difficult to achieve.
Similarly, when partitioning a network into equal-sized groups where an agent's utility depends on having their friends in the same group, Argyrios Deligkas et al. show in Balanced and Fair Partitioning of Friends that finding fair partitions remains NP-hard even on basic structures like paths, though guarantees like Maximin Share (MMS) become achievable if the network is a forest.
Conclusion
Graph-constrained fair division bridges the gap between abstract economic ideals and the localized reality of human interaction. By replacing an all-to-all comparison matrix with a network topology, this paradigm shift allows mechanism designers to exploit graph structure to find simpler allocation protocols, lower computational complexity, and implement flexible pricing strategies.
However, localizing constraints binds fairness to the combinatorial properties of the network. As researchers extend this framework to more complex settings—such as extending pre-existing partial allocations (Argyrios Deligkas et al., The Complexity of Extending Fair Allocations of Indivisible Goods) or calculating optimal monetary subsidies (Yan Hao Ling et al., Envy-Free House Allocation with Minimum Subsidy)—the interplay between network topology and algorithmic tractability remains the central frontier of fair division research.
Key Foundational Work
Networked Fairness in Cake Cutting (2017) — contributed 4 concept elements to this direction.
Fair Division via Social Comparison (2017) — contributed 4 concept elements to this direction.
Allocating Goods on a Graph to Eliminate Envy (2007) — contributed 3 concept elements to this direction.