Maximizing Social Welfare Subject to Network Externalities: A Unifying Submodular Optimization Approach

We consider the problem of allocating multiple indivisible items to a set of networked agents to maximize the social welfare subject to network effects (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 provide a general formulation that captures some of the existing single-item or multi-item resource allocation models as a special case and analyze it under various settings of positive/negative and convex/concave externalities. We then show that the maximum social welfare (MSW) problem benefits some nice diminishing or increasing marginal return properties, hence making a connection to submodular/supermodular optimization. That allows us to devise polynomial-time approximation algorithms using the Lovász extension and multilinear extension of the objective functions. More specifically, we first show that for negative concave externalities, there is a simple e -approximation algorithm for MSW, which can be further extended when there are matroid constraints. We then show that in the case of convex polynomial externalities with positive coefficients and bounded degree d, a simple randomized rounding technique based on Lovász extension achieves a d approximation for MSW. Moreover, for general positive convex externalities, we provide another randomized ^-1 -approximation algorithm based on the contention resolution scheme, where is a constant capturing the curvature of the externality functions. Finally, we consider MSW with positive concave externalities and provide approximation algorithms based on concave relaxation and multilinear extension of the objective function that achieve certain desirable performance guarantees. We also provide numerical experiments to justify the good performance of our devised algorithms. Our principled approach offers a simple and unifying framework for multi-item resource allocation to maximize the social welfare subject to network externalities.