The welfare maximization problem is an optimization problem studied in economics and computer science. Its goal is to partition a set of items among agents with different utility functions, such that the welfare – defined as the sum of the agents' utilities – is as high as possible. In other words, the goal is to find an item allocation satisfying the utilitarian rule.^[1]

An equivalent problem in the context of combinatorial auctions is called the winner determination problem. In this context, each agent submits a list of bids on sets of items, and the goal is to determine what bid or bids should win, such that the sum of the winning bids is maximum.

Definitions

There is a set M of m items, and a set N of n agents. Each agent i in N has a utility function ${\displaystyle u_{i}:2^{M}\to \mathbb {R} }$. The function assigns a real value to every possible subset of items. It is usually assumed that the utility functions are monotone set functions, that is, ${\displaystyle Z_{1}\supseteq Z_{2}}$ implies ${\displaystyle u_{i}(Z_{1})\geq u_{i}(Z_{2})}$. It is also assumed that ${\displaystyle u_{i}(\emptyset )=0}$. Together with monotonicity, this implies that all utilities are non-negative.

An allocation is an ordered partition of the items into n disjoint subsets, one subset per agent, denoted ${\displaystyle \mathbf {X} =(X_{1},\ldots ,X_{n})}$, such that ${\displaystyle M=X_{1}\sqcup \cdots \sqcup X_{n}}$.The welfare of an allocation is the sum of agents' utilities: ${\displaystyle W(\mathbf {X} ):=\sum _{i\in N}u_{i}(X_{i})}$.

The welfare maximization problem is: find an allocation X that maximizes W(X).

The welfare maximization problem has many variants, depending on the type of allowed utility functions, the way by which the algorithm can access the utility functions, and whether there are additional constraints on the allowed allocations.

Additive agents

An additive agent has a utility function that is an additive set function: for every additive agent i and item j, there is a value ${\displaystyle v_{i,j}}$, such that ${\displaystyle u_{i}(Z)=\sum _{j\in X_{i}}v_{i,j}}$ for every set Z of items. When all agents are additive, welfare maximization can be done by a simple polynomial-time algorithm: give each item j to an agent for whom ${\displaystyle v_{i,j}}$ is maximum (breaking ties arbitrarily). The problem becomes more challenging when there are additional constraints on the allocation.

Gross-substitute agents

Gross-substitute utilities are more general than additive utilities. Welfare maximization with gross-substitute agents can be done in polynomial time. This is because, with gross-substitute agents, a Walrasian equilibrium always exists, and it maximizes the sum of utilities.^[8] A Walrasian equilibrium can be found in polynomial time.

Submodular agents

A submodular agent has a utility function that is a submodular set function. This means that the agent's utility has decreasing marginals. Submodular utilities are more general than gross-substitute utilities.

Subadditive agents

When agents' utilities are subadditive set functions (more general than submodular), a ${\displaystyle {\frac {1}{m^{1/2-\epsilon }}}}$ approximation would require an exponential number of value queries.^[11]

Feige^[17] presents a way of rounding any fractional solution to an LP relaxation to this problem to a feasible solution with welfare at least 1/2 the value of the fractional solution. This gives a 1/2-approximation for general subadditive agents, and (1-1/e)-approximation for the special case of fractionally-subadditive valuations.

Superadditive agents

When agents' utilities are superadditive set functions (more general than supermodular), a ${\displaystyle {\frac {(\log m)^{1+\epsilon }}{m}}}$ approximation would require a super-polynomial number of value queries.^[11]

Single-minded agents

A single-minded agent wants only a specific set of items. For every single-minded agent i, there is a demanded set D_i, and a value V_i > 0, such that ${\displaystyle u_{i}(Z)={\begin{cases}V_{i}&Z\supseteq D_{i}\\0&{\text{otherwise}}\end{cases}}}$. That is, the agent receives a fixed positive utility if and only if their bundle contains their demanded set.

Welfare maximization with single-minded agents is NP-hard even when ${\displaystyle V_{i}=1}$ for all i. In this case, the problem is equivalent to set packing, which is known to be NP hard. Moreover, it cannot be approximated within any constant factor (in contrast to the case of submodular agents).^[18] The best known algorithm approximates it within a factor of ${\displaystyle O({\sqrt {m}})}$.^[19]

General agents

When agents can have arbitrary monotone utility functions (including complementary items), welfare maximization is hard to approximate within a factor of ${\displaystyle O(n^{1/2-\epsilon })}$ for any ${\displaystyle \epsilon >0}$.^[20] However, there are algorithms based on state space search that work very well in practice.^[21]

See also

• Utility maximization problem

References