On Fair Division with Binary Valuations Respecting Social Networks

Envy is local when people only compare themselves with their friends: an agent cares about the bundles of its neighbors in a social network, not everyone else's. In joint work with Debanuj Nayak, I ask when it is possible to find allocations that are locally envy-free and Pareto efficient if each agent simply likes or ignores each good. The problem is NP-hard even when the network is a path (or there are just two types of agents), and W-hard parameterized by the number of goods or the network's vertex cover. Proportionality splits interestingly: the most local version is intractable, while others reduce to integer programs that are efficiently solvable.