计算机科学
资源配置
共享资源
光学(聚焦)
资源(消歧)
社交网络(社会语言学)
点(几何)
有界函数
最大最小公平
路径(计算)
树(集合论)
微观经济学
分布式计算
经济
数学
计算机安全
社会化媒体
计算机网络
光学
物理
数学分析
万维网
几何学
作者
Robert Bredereck,Andrzej Kaczmarczyk,Jiaqi Luo,Rolf Niedermeier,F. Sachse
摘要
Given an initial resource allocation, where some agents may envy others or where a different distribution of resources might lead to a higher social welfare, our goal is to improve the allocation without reassigning resources. We consider a sharing concept allowing resources being shared with social network neighbors of the resource owners. More precisely, our model allows agents to form pairs which then may share a limited number of resources. Sharing a resource can come at some costs or loss in utility. To this end, we introduce a formal model that allows a central authority to compute an optimal sharing between neighbors based on an initial allocation. Advocating this point of view, we focus on the most basic scenario where each agent can participate in a bounded number of sharings. We present algorithms for optimizing utilitarian and egalitarian social welfare of allocations and for reducing the number of envious agents. In particular, we examine the computational complexity with respect to several natural parameters. Furthermore, we study cases with restricted social network structures and, among others, devise polynomial-time algorithms in path- and tree-like (hierarchical) social networks.
科研通智能强力驱动
Strongly Powered by AbleSci AI