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.
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.
The problem becomes more challenging when there are additional constraints on the allocation.
For any fixed n ≥ 2, the problem is weakly NP-hard,[2][3] and has a pseudo-polynomial time algorithm based on dynamic programming.
[2] For n = 2, the problem has a fully polynomial-time approximation scheme.
[5] The problem can also be solved in polynomial time when the agents' additive utilities are binary (the value of every item is either 0 or 1), as well as for a more general class of utilities called generalized binary.
[6] Another constraint on the allocation is that the bundles must be independent sets of a matroid.
For example, every bundle must contain at most k items, where k is a fixed integer (this corresponds to a uniform matroid).
Welfare maximization with additive utilities under heterogeneous matroid constraints can be done in polynomial time, by reduction to the weighted matroid intersection problem.
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.
[10] Moreover, a better than (1-1/e) approximation would require an exponential number of querires to a value oracle, regardless of whether P=NP.
[11] The maximum welfare can be approximated by the following polynomial-time greedy algorithm: Lehman, Lehman and Nisan[9] prove that the greedy algorithm finds a 1/2-factor approximation (they note that this result follows from a result of Fisher, Nemhauser and Wolsey[12] regarding the maximization of a single submodular valuation over a matroid).
This contributes to the welfare some amount v, which is marginal utility of g for i at that point.
For example, suppose there are two items x,y and the valuations are: The optimal allocation is Alice: {y}, George: {x}, with welfare 2.
In this model: The welfare maximization problem (with n different submodular functions) can be reduced to the problem of maximizing a single submodular set function subject to a matroid constraint:[9][14][15] given an instance with m items and n agents, construct an instance with m*n (agent,item) pairs, where each pair represents the assignment of an item to an agent.
Construct a single function that assigns, to each set of pairs, the total welfare of the corresponding allocation.
This function should be maximized subject to a partition matroid constraint, ensuring that each item is allocated to at most one agent.
In this model: When agents' utilities are subadditive set functions (more general than submodular), a
approximation would require an exponential number of value queries.
This gives a 1/2-approximation for general subadditive agents, and (1-1/e)-approximation for the special case of fractionally-subadditive valuations.
When agents' utilities are superadditive set functions (more general than supermodular), a
approximation would require a super-polynomial number of value queries.
For every single-minded agent i, there is a demanded set Di, and a value Vi > 0, such that
That is, the agent receives a fixed positive utility if and only if their bundle contains their demanded set.
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).
[19] When agents can have arbitrary monotone utility functions (including complementary items), welfare maximization is hard to approximate within a factor of
[20] However, there are algorithms based on state space search that work very well in practice.