Envy-Free Allocations Respecting Social Networks: Making Fairness Local

TL;DR

Fairness doesn't always have to be global. This paper challenges the traditional "everyone compares to everyone" approach to envy-freeness in resource allocation. By introducing a social network graph where agents only envy their neighbors, the authors provide a more realistic model for reward systems and prove that while some cases become harder, "localizing" fairness often makes finding an optimal allocation computationally feasible.

The Problem: The Impossibility of Global Fairness

In multi-agent systems, "Envy-Freeness" is the gold standard: no agent should prefer another's bundle over their own. However, when dealing with indivisible goods (like a specific office, a trophy, or a training course), a perfectly envy-free allocation often simply does not exist.

The authors point out a psychological truth: people generally only compare themselves to their immediate peers—coworkers, friends, or competitors—not the entire world. Classic models ignore this "Social Comparison Theory," leading to over-constrained problems that suggest no fair solution exists when, in reality, a locally fair one does.

Methodology: Embedding Agents in a Graph

The core innovation is the Graph-Envy-Free (GEF) allocation.

• Weak GEF: Agent $i$ likes its bundle at least as much as the bundle of any neighbor $j$ (where an arc exists from $i$ to $j$).
• Strong GEF: Agent $i$ strictly prefers its own bundle over its neighbors' bundles.

By changing the topology of the graph, we can model different social structures:

• DAGs (Directed Acyclic Graphs): Model hierarchies (e.g., a manager vs. subordinates).
• SCCs (Strongly Connected Components): Model tight-knit peer groups.
• Complete Graphs: Revert to the classic global envy-freeness.

Figure 1: Social comparison graph. Arcs represent the direction of potential envy.

Complexity Landscape: The Good, The Bad, and The Hard

The paper provides a comprehensive analysis of how graph structure and preference types (Identical, 0/1, Additive) affect the difficulty of finding an allocation.

1. The Tractable "Wins"

One of the most exciting findings is that for DAGs, finding a weakly graph-envy-free allocation is trivial for monotonic preferences (just give everything to the "source" agent who envies no one). More impressively, finding a Pareto-efficient GEF allocation in a DAG is solvable in polynomial time, whereas the global version is ${\Sigma }_2^P$-hard.

2. The Hardness of "Strong" Fairness

Strong GEF is much more demanding. Even in a simple directed path, finding a Strong GEF allocation is NP-hard and W[1]-hard when parameterized by the number of agents. This is because every agent in the chain must receive a bundle strictly better than the next, creating a strict "utility ladder" that is hard to satisfy with few resources.

Table 1: Computational complexity for finding complete (weakly) Graph-Envy-Free allocations.

Key Insights & Theoretical Bridges

The authors prove an important relationship in Observation 6: For identical additive preferences, finding a complete GEF allocation is equivalent to finding a Pareto-efficient one or one that maximizes utilitarian social welfare. This bridge allows researchers to simplify efficiency goals without losing the core fairness properties.

However, they also show that Social Welfare optimization can be harder than mere completeness. For example, W-GEF-Allocation is NP-hard on DAGs even with simple three-valued utility functions, showing that "doing the most good" is still a difficult task when local envy constraints are present.

Conclusion and Future Outlook

This work demonstrates that "Envy-Free" is not a binary state but a spectrum defined by social context. By leveraging the structure of social networks, we can design algorithms that find "fair enough" solutions for real-world teams.

Future Directions:

• Undirected Graphs: What happens when envy is always mutual?
• Alternative Fairness: Applying this graph-based approach to Proportionality or Maxmin Share.
• Dynamic Networks: How do allocations evolve if the social network changes over time?

For practitioners in multi-agent systems and HR tech, this paper provides a robust mathematical foundation for building more "human-centric" automated reward systems.