You are currently browsing the tag archive for the ‘binary quadratic programming’ tag.

In the analysis of combinatorial auctions two problems arise:

1. Surplus maximization: given prices for each item and a utility function over bundles of goods, find a bundle that maximizes the utility of a bundle less the price paid.
2. Welfare maximization: determine an allocation of goods to agents so as to maximize total welfare.

In general both problems are NP-hard and therefore a number of scholars have sought to identify conditions on preferences (i.e. ${u}$) that yield efficiently solvable instances of both problems. In this post I discuss a class preferences motivated by Cramton, Ausubel, McAfee and McMillan (1997) related to binary quadratic programs (BQP). A recent paper by Candogan, Ozdaglar and Parrilo (2013) prompted this two part post. I will say more about this paper in part 2. In this part I focus on surplus maximization.

Say that ${u}$ represents BQP preferences if

$\displaystyle u(S) = \sum_{i \in S}u_i + \sum_{i, j \in S}w_{ij}\,\, \forall S \subseteq M$

Interpret ${u_i}$ as the utility of consuming object ${i \in M}$ alone and ${w_{ij}}$ is the added benefit from consuming both ${i}$ and ${j }$ (if ${w_{ij} > 0}$), otherwise the disutility of doing so. The surplus maximization problem for BQP preferences is

$\displaystyle \max_{S \subseteq M} \sum_{i \in S}u_i + \sum_{i, j \in S}w_{ij} - \sum_{i \in S}p_i$

which can be rewritten as a binary quadratic program

$\displaystyle \max \sum_{i \in M}(u_i - p_i)x_i + \sum_{i \neq j}w_{ij}x_ix_j$

subject to

$\displaystyle x_i \in \{0,1\}\,\, \forall i \in M$

This problem is NP-hard as it encodes the independent set problem. To see why, let ${G = (V, E)}$ be a graph and let  ${w_{ij} = 0}$ if ${(i,j) \not \in E}$, ${u_i - p_i = 1}$ for all ${i \in M}$ and ${w_{ij} = -K}$ for all ${(i,j) \in E}$ where ${K }$ is a large positive number.

If ${w_{ij} \geq 0}$ for all ${i,j \in M}$ (pairs of goods are complements) there is a straightforward linearization of the surplus maximization problem:

$\displaystyle \max \sum_{i \in M}(u_i - p_i)x_i + \sum_{i \neq j}w_{ij}y_{ij}$

subject to

$\displaystyle y_{ij} \leq x_i\,\, \forall i,j \in M$

$\displaystyle y_{ij} \leq x_j\,\, \forall i,j \in M$

$\displaystyle 0 \leq y_{ij}, x_i \leq 1\,\, \forall i, j \in M$

Note that the constraint matrix is totally unimodular. Therefore, the surplus maximization problem can be solved as a linear program.

Thus, if ${w_{ij} > 0}$ for all ${i,j}$, surplus maximization is easy. With no restriction on the ${w_{ij}}$‘s, surplus maximization is NP-hard. Is there anything between these two extremes? Yes, Hansen and Simeone (1986) give us one case. To describe this case, we associate a graph with the ${w_{ij}}$‘s. One vertex for each ${i \in M}$ and for each ${(i,j)}$ such that ${w_{ij} \neq 0}$ an edge ${(i,j)}$. Call this graph ${G^w}$. Say that ${G^w}$ is sign balanced if it does not contain any cycle with an odd number of negative edges (${w_{ij} < 0}$). This implies that deleting all negative edges of ${G}$ disconnects it (say ${G =G_1\cup G_2}$), and ${\delta(G_1,G_2) }$ is the set of negative edges.

Consider the following linear relaxation of the surplus maximization problem:

$\displaystyle \max \sum_{i \in M}(u_i - p_i)x_i + \sum_{i \neq j}w_{ij}y_{ij}$

subject to

$\displaystyle y_{ij} \leq x_i\,\, \forall w_{ij} \geq 0$

$\displaystyle y_{ij} \leq x_j\,\, \forall w_{ij} \geq 0$

$\displaystyle y_{ij} \geq x_i + x_j -1\,\, \forall w_{ij} < 0$

$\displaystyle 0 \leq y_{ij}, x_i \leq 1\,\, \forall i,j$

If ${G^w}$ is sign balanced, Hansen and Simeone showed that the constraint matrix of this linear relaxation is totally unimodular. Therefore, the relaxation is exact. Here is a short argument that establishes integrality of the relaxation based on randomized rounding (due to Bertsimas, Teo and Vohra (1999)).

1. Let ${({\bar x}, {\bar y})}$ be an optimal solution to the relaxation.
2. Generate a single random number ${U}$ uniformly in ${[0,1]}$.
3. Round ${x_{i}}$ to 1 if ${i \in G_1}$ and ${{\bar x}_i \geq U}$, or ${i\in G_2}$ and ${{\bar x}_i \geq 1-U}$.

Since ${1-U}$ is also uniformly distributed in ${[0,1]}$, ${P(x_i =1) = {\bar x}_i}$. For ${i,j}$ both in ${ G_1}$ or both in ${G_2}$, ${P(x_i x_j=1) = \min \{{\bar x}_i,{\bar x}_j\}.}$ For ${i\in G_1}$ and ${j\in G_2}$,

$\displaystyle P(x_i x_j=1) = P(U\leq {\bar x}_i,1-U\leq {\bar x}_j) =[0, {\bar x}_i+{\bar x}_j-1]^+.$

At optimality, ${{\bar y}_{ij}= [{\bar x}_i, {\bar x}_j]^-}$ if ${w_{ij} \geq 0}$, ${{\bar y}_{ij}=[0, {\bar x}_i+{\bar x}_j-1]^+}$ if ${w_{ij} < 0}$. The expected objective function value of the random integral solution generated in this way is

$\displaystyle \sum_{i\neq j} w_{ij} E[x_i x_j] + \sum_i [u_i-p_i] x_i= \sum_{i,j} w_{ij} {\bar y}_{ij}+\sum_i [u_i-p_i] {\bar x}_i.$

Notice this is the optimal objective function value of the linear relaxation and this completes the argument.

In part 2 I turn to the welfare maximization question.