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. 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 u i : 2 M → R {\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, Z 1 ⊇ Z 2 {\displaystyle Z_{1}\supseteq Z_{2}} implies u i ( Z 1 ) ≥ u i ( Z 2 ) {\displaystyle u_{i}(Z_{1})\geq u_{i}(Z_{2})} . It is also assumed that u i ( ∅ ) = 0 {\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 X = ( X 1 , … , X n ) {\displaystyle \mathbf {X} =(X_{1},\ldots ,X_{n})} , such that M = X 1 ⊔ ⋯ ⊔ X n {\displaystyle M=X_{1}\sqcup \cdots \sqcup X_{n}} .The welfare of an allocation is the sum of agents' utilities: W ( X ) := ∑ i ∈ N u i ( X i ) {\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 v i , j {\displaystyle v_{i,j}} , such that u i ( Z ) = ∑ j ∈ X i v i , j {\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 v i , j {\displaystyle v_{i,j}} is maximum (breaking ties arbitrarily). The problem becomes more challenging when there are additional constraints on the allocation.
Fairness constraints One may want to maximize the welfare among all allocations that are fair, for example, envy-free up to one item (EF1), proportional up to one item (PROP1), or equitable up to one item (EQ1). This problem is strongly NP-hard when n is variable. For any fixed n ≥ 2, the problem is weakly NP-hard, and has a pseudo-polynomial time algorithm based on dynamic programming. For n = 2, the problem has a fully polynomial-time approximation scheme. There are algorithms for solving this problem in polynomial time when there are few agent types, few item types or small value levels. 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.
Matroid constraints 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). Or, the items may be partitioned into categories, and each bundle must contain at most kc items from each category c (this corresponds to a partition matroid). In general, there may be a different matroid for each agent, and the allocation must give each agent i a subset Xi that is an independent set of their own matroid. Welfare maximization with additive utilities under heterogeneous matroid constraints can be done in polynomial time, by reduction to the weighted matroid intersection problem.
… excerpt ends here. Continue reading the full article.
