We consider the problem of allocating multiple indivisible items to a set of networked agents to maximize the social welfare subject to network externalities. Here, the social welfare is given by the sum of agents' utilities and externalities capture the effect that one user of an item has on the item's value to others. We first provide a general formulation that captures some of the existing models as a special case. We then show that the social welfare maximization problem benefits some nice diminishing or increasing marginal return properties. That allows us to devise polynomial-time approximation algorithms using the Lovasz extension and multilinear extension of the objective functions. Our principled approach recovers or improves some of the existing algorithms and provides a simple and unifying framework for maximizing social welfare subject to network externalities.
翻译:我们考虑将多种不可分割的物品分配给一组网络化代理机构的问题,以便根据网络外差因素使社会福利最大化。在这里,社会福利是由代理机构的公用事业和外部因素总和提供的,它捕捉到某一物品的使用者对物品的价值对他人的价值产生的影响。我们首先提供一个一般性的提法,将某些现有模式作为特例加以捕捉。然后我们表明,社会福利最大化问题有利于某种良好的减少或增加边际回报属性。这使我们能够利用Lovasz扩展和多线性扩展目标功能来设计多时近似算法。我们的原则性方法恢复或改进了一些现有的算法,并为在网络外差因素的条件下最大限度地实现社会福利提供了一个简单和统一的框架。