Mathematical programming approaches for social welfare maximization

Abstract The maximization of social welfare has a long history and is a topic of interest across various disciplines, including economics, mathematics, computer science, and artificial intelligence. This problem concerns the allocation of a finite set of (discrete) indivisible goods among a finite group of individuals with heterogeneous preferences over item bundles. These preferences are typically represented as numerical functions that assign a real value to each bundle. The objective is to determine an allocation that maximizes social welfare, which can be measured in various ways, such as the sum or product of individual utilities or the utility of the worst-off agent. Several solution techniques have been developed to address this problem, both exactly and approximately. Among these, mathematical programming has proven to be particularly effective and has had the most significant impact. In this paper, we provide a comprehensive survey of this technique in solving the social welfare maximization problem over the past few decades and highlight the most challenging open questions for future research.