In part two, as promised, I turn to the welfare maximization problem. To formulate the problem of finding a welfare maximizing allocation let if object is given to agent and zero otherwise. Denote the utility of agent from consuming bundle by

The problem of maximizing total welfare is

subject to

Welfare maximization with BQP preferences is in general NP-hard. One proof relies on a reduction to the multi-way cut problem. Given a graph with edge weight for each , and a set of terminal vertices , a **multiway cut** is a set of edges whose removal disconnects every pair of terminal vertices. The problem of finding the multiway cut of minimum total weight is called the multiway cut problem. When consists of only two terminals () the problem reduces to the well known minimum cut problem. For , it is known that the problem is hard even on planar graphs.

We can obtain the multiway cut problem by setting for all and and for all and . Any pair such that for will be part of a multi-way cut. This reduction implies that welfare maximization when for all and is NP-hard. This is in contrast to the case of surplus maximization.

,Candogan, Ozdaglar and Parrilo (2013), the paper that prompted this post, identify a solvable instance of the welfare maximization problem. They impose two conditions. The first is called **sign consistency**. For each the sign of and for any is the same. Furthermore, this applies to all pairs . Sign consistency by itself is not sufficient to obtain a solvable instance. Another condition is needed. Let be a graph with vertex set and for any such that introduce an edge . The second condition is that be a tree. Interestingly, Erdos and Sz\'{e}kely (1995) show that a generalization of the multiway cut problem which corresponds to welfare maximization under sign consistency and for all and , is polynomially solvable when the underlying graph is a tree. The Candogan, Ozdaglar and Parrilo (COP) proof is based on a dynamic programming argument similar to the one used in Erdos and Sz\'{e}kely (1994).

The key result in COP is the following natural linearization of the welfare maximization problem admits an integral optimal solution.

subject to

There is a connection between the welfare maximization problem and packing subtrees into trees that I want to highlight. It suggests a possible avenue by which one might enlarge the class of preferences COP consider.

Because of the sign consistency condition we can label the edges of as being positive or negative depending on the sign of . Let and . Let be the maximal connected components of after deletion of the edges in (call this ). For any and let

By the way, for each and , is supermodular over the subsets of . Let if is assigned to agent and zero otherwise. The problem of finding a welfare maximizing allocation can be expressed as follows:

subject to

In the above program, we can, without loss, restrict attention to subsets that a subtrees (connected subgraphs) of . To see why, suppose in that in some optimal solution to the above integer program, where is not a subtree. Then, we can write where both and are in the same component of as is. Furthermore, it must be the the case that there is no edge such that and . Therefore, . That means we can construct a new optimal solution by setting and raising and to 1. Note, in the original solution by virtue of the first constraint. As long as is not a subtree we can repeat this argument.

Hence, if we let be the set of subtrees of , the welfare maximization problem can be expressed as follows:

subject to

Its important to emphasize that no contains a negative edge.

Were it not for the second set of the constraints, integrality would follow from Barany, Edmonds and Wolsey (1986). I’m not aware of this variation of the tree packing problem having been considered. A follow up paper by Aghezzaf and Wolsey (1994) comes close in the sense of allowing for a piecewise linear concave objective function.

## Recent Comments