In the analysis of combinatorial auctions two problems arise:
- 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.
- 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. ) 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 represents BQP preferences if
Interpret as the utility of consuming object alone and is the added benefit from consuming both and (if ), otherwise the disutility of doing so. The surplus maximization problem for BQP preferences is
which can be rewritten as a binary quadratic program
This problem is NP-hard as it encodes the independent set problem. To see why, let be a graph and let if , for all and for all where is a large positive number.
If for all (pairs of goods are complements) there is a straightforward linearization of the surplus maximization problem:
Note that the constraint matrix is totally unimodular. Therefore, the surplus maximization problem can be solved as a linear program.
Thus, if for all , surplus maximization is easy. With no restriction on the ‘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 ‘s. One vertex for each and for each such that an edge . Call this graph . Say that is sign balanced if it does not contain any cycle with an odd number of negative edges (). This implies that deleting all negative edges of disconnects it (say ), and is the set of negative edges.
Consider the following linear relaxation of the surplus maximization problem:
If 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)).
- Let be an optimal solution to the relaxation.
- Generate a single random number uniformly in .
- Round to 1 if and , or and .
Since is also uniformly distributed in , . For both in or both in , For and ,
At optimality, if , if . The expected objective function value of the random integral solution generated in this way is
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.