In part two, as promised, I turn to the welfare maximization problem. To formulate the problem of finding a welfare maximizing allocation let ${x^k_j = 1}$ if object ${j \in M}$ is given to agent ${k \in N}$ and zero otherwise. Denote the utility of agent ${k \in N}$ from consuming bundle ${S \subseteq M}$ by

$\displaystyle u_k(S) = \sum_{i \in S}u^k_i + \sum_{i, j \in S}w^k_{ij}.$

The problem of maximizing total welfare is

$\displaystyle \max \sum_{k \in N}\sum_{i \in M}u^k_ix^k_i + \sum_{k \in N}\sum_{i \neq j}w^k_{ij}x^k_ix^k_j$

subject to

$\displaystyle \sum_{k \in N}x^k_i \leq 1\,\, \forall i \in M$

$\displaystyle x^k_i \in \{0,1\}\,\, \forall i \in M, k \in N$

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 ${G=(V,E)}$ with edge weight ${c_{ij}}$ for each ${(i,j) \in E}$, and a set of terminal vertices ${T = \{v_1, v_2, \ldots, v_n\}}$, 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 ${T}$ consists of only two terminals (${k = 2}$) the problem reduces to the well known minimum cut problem. For ${k \geq 3}$, it is known that the problem is ${NP-}$hard even on planar graphs.

We can obtain the multiway cut problem by setting ${u^k_i = 0}$ for all ${k \in N}$ and ${i \in M}$ and ${w^k_{ij} = c_{ij}}$ for all ${k \in N}$ and ${(i,j) \in E}$. Any pair ${(i,j)}$ such that ${x^k_ix^r_j = 1}$ for ${k \neq r}$ will be part of a multi-way cut. This reduction implies that welfare maximization when ${w^k_{ij} \geq 0}$ for all ${k \in N}$ and ${i,j \in M}$ 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 ${i,j \in M}$ the sign of ${w^k_{ij} }$ and ${w^r_{ij}}$ for any ${k, r \in N}$ is the same. Furthermore, this applies to all pairs ${i, j \in M}$. Sign consistency by itself is not sufficient to obtain a solvable instance. Another condition is needed. Let ${G^w}$ be a graph with vertex set ${M}$ and for any ${i,j \in M}$ such that ${w^k_{ij} \neq 0}$ introduce an edge ${(i,j)}$. The second condition is that ${G^w}$ 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 ${u^k_i = 0}$ for all ${k \in N}$ and ${i \in M}$, is polynomially solvable when the underlying graph ${G}$ 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.

$\displaystyle \max \sum_{k \in N}\sum_{i \in M}u^k_ix^k_i + \sum_{k \in N}\sum_{i \neq j}w^k_{ij}y^k_{ij}$

subject to

$\displaystyle \sum_{k \in N}x^k_i \leq 1\,\, \forall i \in M$

$\displaystyle y^k_{ij} \leq \{x^k_i, x^k_j\}^-\,\, \forall w^k_{ij} > 0$

$\displaystyle y^k_{ij} \geq x^k_i + x^k_j -1\,\, \forall w^k_{ij} < 0$

$\displaystyle x^k_i \in \{0,1\}\,\, \forall i \in M, k \in N$

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 ${G^w}$ as being positive or negative depending on the sign of ${w^k_{ij}}$. Let ${E^+ = \{(i,j): w^k_{ij} \geq 0\}}$ and ${E^- = \{(i,j): w^k_{ij} < 0\}}$. Let ${{\cal C}}$ be the maximal connected components of ${G^w}$ after deletion of the edges in ${E^-}$ (call this ${G^+}$). For any ${C \in {\cal C}}$ and ${S \subseteq C}$ let

$\displaystyle v_k(S) = \sum_{i \in S}u^k_i + \sum_{i,j \in S}w^k_{ij}.$

By the way, for each ${C \in {\cal C}}$ and ${k \in N}$, ${v_k}$ is supermodular over the subsets of ${C}$. Let ${z_k(S) = 1}$ if ${S \subseteq C}$ is assigned to agent ${k}$ and zero otherwise. The problem of finding a welfare maximizing allocation can be expressed as follows:

$\displaystyle \max \sum_{k \in N}\sum_{C \in {\cal C}}\sum_{S \subseteq C}v_k(S)z_k(S) - \sum_{k \in N}\sum_{(i,j) \in E^-}|w^k_{ij}|y^k_{ij}$

subject to

$\displaystyle \sum_{S \ni i}\sum_{k \in N}z_k(S) \leq 1\,\, \forall i \in M,\,\, S \subseteq C \in {\cal C}$

$\displaystyle y^k_{ij} \geq \sum_{S \ni i}z_k(S) + \sum_{S \ni j}z_k(S) - 1\,\, \forall k \in N, (i,j) \in E^-$

$\displaystyle z_k(S) \in \{0,1\}\,\, \forall k \in N, S \subseteq C \in {\cal C}$

$\displaystyle y^k_{ij} \in \{0,1\}\,\, \forall k \in N, (i,j) \in E^-$

In the above program, we can, without loss, restrict attention to subsets ${S}$ that a subtrees (connected subgraphs) of ${E^+}$. To see why, suppose in that in some optimal solution to the above integer program, ${z_k(S) = 1}$ where ${S}$ is not a subtree. Then, we can write ${S = A \cup B}$ where both ${A}$ and ${B}$ are in the same component of ${C}$ as ${S}$ is. Furthermore, it must be the the case that there is no edge ${(i,j) \in E^+}$ such that ${i \in A}$ and ${j \in B}$. Therefore, ${v_k(S) = v_k(A) + v_k(B)}$. That means we can construct a new optimal solution by setting ${z_k(S) = 0}$ and raising ${z_k(A)}$ and ${z_k(B)}$ to 1. Note, in the original solution ${z_k(A), z_k(B) =0}$ by virtue of the first constraint. As long as ${S}$ is not a subtree we can repeat this argument.

Hence, if we let ${{\cal T}}$ be the set of subtrees of ${G^+}$, the welfare maximization problem can be expressed as follows:

$\displaystyle \max \sum_{k \in N}\sum_{T \in {\cal T}}v_k(T)z_k(T) - \sum_{k \in N}\sum_{(i,j) \in E^-}|w^k_{ij}|y^k_{ij}$

subject to

$\displaystyle \sum_{T \in {\cal T}}\sum_{T \ni i}\sum_{k \in N}z_k(T) \leq 1\,\, \forall i \in M,$

$\displaystyle y^k_{ij} \geq \sum_{T \ni i}z_k(T) + \sum_{S \ni j}z_k(S) - 1\,\, \forall k \in N, (i,j) \in E^-$

$\displaystyle z_k(S) \in \{0,1\}\,\, \forall k \in N, T \in {\cal T}$

$\displaystyle y^k_{ij} \in \{0,1\}\,\, \forall k \in N, (i,j) \in E^-$

Its important to emphasize that no ${T \in {\cal T}}$ 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.