Given an initial resource allocation, where some agents may envy others or where a different distribution of resources might lead to 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. 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 a resource may be shared by two neighbors in a social network and 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.
翻译:鉴于最初的资源分配,一些代理人可能羡慕他人,或者不同的资源分配可能导致更高的社会福利,我们的目标是改善分配,而不重新分配资源。我们考虑一种共享概念,允许资源与资源所有者的社会网络邻居共享资源。为此,我们引入了一种正式模式,允许中央当局根据初步分配计算邻居之间的最佳共享。主张这一观点,我们侧重于一种最基本的情景,即资源可能由两个邻居在一个社会网络中共享,而每个代理人可以参与一定数量的共享。我们提出了优化分配的功利和平等的社会福利以及减少隐蔽代理人数目的算法。特别是,我们研究了几个自然参数的计算复杂性。此外,我们还研究了限制社会网络结构的案例,以及一些在路径和树类(等级的)社会网络中设计多时算法。