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 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 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 & aacute;sz and multilinear extensions of the objective functions. More specifically, we first show that for negative concave externalities, there is an e -approximation algorithm for MSW. We then show that for convex polynomial externalities of degree d with positive coefficients, a randomized rounding technique based on Lov & aacute;sz extension achieves a d approximation for MSW. Moreover, for general positive convex externalities, we provide another randomized gamma(-1)-approximation algorithm based on the contention resolution scheme, where gamma captures 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. Our principled approach offers a simple and unifying framework for multi-item resource allocation to maximize the social welfare subject to network externalities.