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.

Join 119 other followers


Get every new post delivered to your Inbox.

Join 119 other followers

%d bloggers like this: