Florian Sachse (TU Berlin)

Finding optimal resource allocations is an important task in many social and technical systems. The notion of optimality often depends on underlying connections between agents. We extend the idea of graph-envy, that is, envy along a social network, by allowing agents to share in pairs along a social network to improve an allocation. Using this model, we present algorithms for optimizing utilitarian and egalitarian social welfare of allocations. We introduce the NP-hard problem of reducing the number of envious nodes through pairwise sharing of resources and examine the hardness with respect to several parameters. Furthermore, we present a greedy algorithm solving this problem in linear time on paths and a dynamic programming algorithm solving the problem in polynomial time on trees.

Back to the research colloquium site.