Multi-item Resource Allocation for Maximizing Social Welfare under Network Externalities
S. Rasoul Etesami · 2024
We consider the problem of allocating multiple indivisible items (resources) to a set of capacitated 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 first 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 externality weights and convex/concave externality functions. In our formulation, the externality weights capture whether the agents are influenced positively or negatively by those who receive the same item, and the convex/concave externality functions determine the growth rate of network effects for different pairs of items and agents. 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 various polynomial-time approximation algorithms using the Lovaśz and multilinear extensions of the objective functions. More specifically: