Local Fairness and Social Comparison in Resource Allocation

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 231 papers55 conceptsfrozen 2026-10-04

Traditional fair division theory operates under a demanding assumption: every participant in a system knows exactly what everyone else received and evaluates their own happiness against the entire population. In a world of millions, this "global envy" is both computationally impossible and psychologically unrealistic.

A growing body of research shifts this focus toward graph-constrained fairness. By modeling agents as nodes in a social or geographic network, researchers like Jon Kleinberg and David C. Parkes argue that fairness is a local phenomenon. In this view, you don't care if a stranger across the country has a better "slice of cake"; you only care if your neighbor does.

The Social Comparison Graph

The core mechanism of this research is the social comparison graph. Instead of requiring an allocation to be envy-free across all pairs of agents, we only require it for pairs connected by an edge.

As Haris Aziz and Jérôme Lang explore in Knowledge, Fairness, and Social Constraints, this is often an epistemic constraint. If you cannot see another agent's bundle, you cannot envy it. This "Epistemic Envy-Freeness" bridges the gap between strict global fairness and simple proportionality.

This relaxation has practical benefits for system designers. Michele Flammini and colleagues demonstrate in On Social Envy-Freeness in Multi-Unit Markets that local fairness allows sellers to capture significantly more revenue. Because agents only compare prices with their immediate social circle, sellers can implement more flexible pricing strategies without triggering a sense of injustice.

Items as Edges: The Graphical Constraint

A second facet of this direction involves the items themselves. In many real-world scenarios, resources aren't "global" goods that anyone can use; they are inherently tied to specific relationships.

In the "graphical fair division" model, items are represented as edges and agents as vertices. An item (edge) only provides utility to the two agents (vertices) it connects. Think of a shared border between two countries or a collaborative project between two colleagues.

George Christodoulou 0001 and Symeon Mastrakoulis show that this structural sparsity is incredibly powerful. In general fair division, "Maximin Share" (MMS) allocations—where everyone gets a bundle they value at least as much as a fair $1/n$ split—don't always exist. However, when items are restricted to edges in a graph, exact MMS allocations are guaranteed to exist for additive agents. By limiting the pool of potential recipients for each item, the fundamental impossibilities of fair division often vanish.

Why Local Fairness is Still Hard

You might expect that fewer constraints (comparing to 5 neighbors instead of 500 strangers) would make finding a fair allocation easy. Surprisingly, the computational "price" remains high.

Eduard Eiben and Robert Ganian have shown that finding envy-free allocations on social networks is generally NP-complete. The difficulty arises because local constraints are interconnected; satisfying envy for one agent might force an allocation that creates envy for their neighbor's neighbor, rippling through the network.

However, the research identifies a "sweet spot": when the social network has a simple structure, such as low treewidth or being a forest, complex fairness guarantees like EFX (Envy-Free up to any item) become efficiently computable. Yu Zhou and Minming Li provide a complete landscape of these complexities, showing that while "orientation" (giving items only to incident agents) is hard, general EFX allocations on graphs are often achievable.

The Neighborhood Pitfall

Finally, this research warns of a "local neighborhood pitfall." Abdol-Hossein Esfahanian and Farzan Masrour argue that because individuals judge fairness based on their immediate peers, systemic biases can be masked. If an entire social circle is underserved, an individual might perceive their own poor outcome as "fair" simply because it matches the neighborhood average.

This highlights the dual nature of the research: while graph-based models provide a more realistic and sometimes more solvable framework for resource allocation, they also reveal how social structures can calibrate—and sometimes distort—our very perception of equity.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 15 papers
  2. Version 1 · 2026-10-04 · 31 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_local_envy_freeness_d773df49,
  title = {local envy-freeness},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/local-envy-freeness/rdr_d773df4993a7458690a9ba78790ff5dc},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_local_fairness_and_social_comparison_in__d773df49_v1,
  title = {Local Fairness and Social Comparison in Resource Allocation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/local-fairness-and-social-comparison-in-resource-allocation/rdr_d773df4993a7458690a9ba78790ff5dc/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}