TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 04.07.2019(2)

isti-logo

Page Content

to Navigation

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.

 

Date
Speaker
Location
Language
04.07.2019
17:00
Florian Sachse
TEL 512
English

Back to the research colloquium site.

To top

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe