direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Resource Sharing: Reducing Envy Through Social Networks

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.


Florian Sachse
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras