|
Article Excerpt
1. Introduction
Classic auction theory shows that if a single item is auctioned via the submission of sealed-bid price offers, then bidders can be expected to report their bids honestly under a second-price mechanism (i.e., one in which the highest bid wins and pays the amount of the second-highest bid). Such a mechanism is said to be incentive compatible, meaning that truth-telling is a dominant strategy for every player, and that there is no incentive for unilateral deviation from the truth-telling strategy.
The analogous second-price mechanism for combinatorial auctions (in which bidders bid on combinations of items) is the well-known Vickrey-Clarke-Groves (VCG) mechanism, which has also been shown to be incentive compatible (for primary sources see Clarke 1971, Groves 1973, and Vickrey 1961). In the general version of this auction mechanism, bidders each submit a price for each possible combination of items. Winners are chosen to maximize the combined social value of awarded bundles (with no item going to more than one bidder); such an allocation is referred to as efficient. Each winner in the VCG auction then pays an amount less than her bid on the bundle she is awarded, receiving a discount from her actual bid that is calculated to eliminate her ability to gain from falsifying her preferences. In particular, each winning bidder receives a discount equal to the difference in value between the efficient solution with all bidders and the efficient solution in the absence of that particular bidder. The problem of finding an efficient allocation for a given set of bids is known as the winner-determination problem, and is often computationally difficult (i.e., NP-hard; see Rothkopf et al. 1998)
Although the VCG mechanism is widely discussed in the auction literature, its drawbacks are so numerous that it is rarely, if ever, used in practice. Indeed, there are too many problems to name here; we therefore direct the reader to a few good references on the problems with VCG mechanisms (see Ausubel and Milgrom 2002, Rothkopf and Harstad 1995, Rothkopf et al. 1990, and Sakurai et al. 2000). Principle among these drawbacks is that the VCG payments may be so low (in a forward auction) that the outcome is not a "core" allocation (defined formally in the next section). Roughly stated, this means that a dissatisfied coalition of bidders may be able to suggest an auction outcome that is preferred by all the members of the coalition and the seller. This situation is clearly unsatisfying, especially when the seller is a government agency assigned the duty of fair allocation, and the winners have not paid enough to establish themselves as the fair recipients of the auction items relative to the competition.
Given that the VCG mechanism is undesirable in practice, one may next ask: What other payment mechanism can be used in a combinatorial auction? The most obvious alternative is a first-price (or pay-as-bid) mechanism, but this too has drawbacks. In a sealed-bid combinatorial auction, this payment rule encourages the bidders to submit bids that are just barely enough to achieve the efficient allocation. Indeed, bidding higher than the minimum amount necessary to secure a particular bundle simply gives more money to the seller in the pay-as-bid scenario. But if each player is trying to predict the minimum amount needed to win his efficiently awarded bundle, uncertainty about the bids of others makes this a precarious endeavor. With incomplete information about the preferences of others, trying to bid the minimum possible amount will often lead to bidding not quite enough, leading the auction mechanism to miss the efficient outcome as a consequence.
Unsatisfied with the two "extreme" possibilities for a payment mechanism (first-price and VCG), is there some other "second-price" combinatorial auction payment mechanism that maintains most of the desirable properties of the second-price mechanism for a single-item auction, while not suffering from the undesirable properties of the VCG mechanism? Stated differently, we would like a mechanism that encourages truthful bidding by charging less than the full amount bid on a bundle, but does not suffer from the extremely low seller revenues of the VCG mechanism.
Few combinatorial auction mechanisms other than VCG have been studied extensively that result in "second-prices," payments that are typically lower than what was bid and are determined by the bids of others. One prominent example was proposed recently by Ausubel and Milgrom (2002), (1) an ascending proxy auction providing a viable practical alternative to the virtually unusable VCG mechanism for real-world combinatorial auction applications. Assuring competitive pricing and economic efficiency, the proxy auction terminates at a desirable "bidder-Pareto-optimal core outcome" (defined formally in the next section). This presents an especially attractive solution for several public-good allocation problems, where the need for a "socially acceptable" outcome outweighs revenue maximization for the seller.
Designed as a proxy implementation of an iterative combinatorial auction, bidders in this mechanism are insulated against the dangers of bidding more than the minimum amount necessary to win a particular bundle, as the proxy submits bid information only at minimum increments. The particular algorithm for winner/payment determination in the ascending proxy auction (as first proposed by Ausubel and Milgrom 2002) is interpreted by de Vries et al. (2007) as an implementation of the subgradient algorithm: at each moment in the process, the algorithm solves an NP-hard set-packing problem, determining a nonoverlapping set of bundles from all those demanded by the bidders at some current set of prices, and a net utility maximizing bundle for each bidder. Each nonanonymous bundle price is then adjusted up by one increment for each bundle that is not contained in the "seller's choice" allocation. This process corresponds to incremental stepping in the direction of a subgradient. As is commonly the case with the subgradient algorithm, convergence is slow and depends critically on the choices of step size.
Compounding the problem of rapid computation is that each iteration of this algorithm requires the solution of an integer program (IP) for winner determination. Although each IP can be solved reasonably quickly given advanced computational techniques (see, for example, Gunluk et al. 2005) and software (like CPLEX and XPRESS, for example), the repeated solution and slow convergence limits practical implementation (see Hoffman et al. 2006).
Even since the relatively new development of the ascending proxy auction, a few methods for arriving at the same types of outcomes more rapidly have been proposed, including the technique developed in this paper. Hoffman et al. (2006) give experimental evidence for slow performance of the subgradient-type ascending proxy implementation and show how to improve the computational speed of the proxy auction's iterative implementation by starting at the VCG solution, and by using a more sophisticated adjustment (scaling) of the price increment. Their technique requires the switch to a sealed-bid (nonproxy) auction allowing the auctioneer to use all of the information reported by the bidders to solve instances of the winner determination problem. Given that the auction mechanism can be trusted not to make the bid information public (which may be legally enforced or entrusted to a neutral third party), we argue that such revelation is reasonable and should be implemented for large-scale applications because access to the full set of bid reports may greatly accelerate computational performance. Wurman et al. (2004) provide a different approach to accelerating the proxy implementation by computing the "inflection" or "change" points in the iterative auction's price trajectory. Their technique also requires the full release of bid information to the auctioneer, rather than withholding it in a proxy. In [section]5, we look at these methods in greater depth and compare them to the technique presented here.
More recently, Ausubel et al. (2006) provided a practical clock-proxy auction design that terminates with bidders submitting combinatorial bids in a proxy auction after some initial rounds designed to reveal price information. The final proxy phase is strategically equivalent to a sealed-bid combinatorial auction, justifying our focus on sealed-bid price mechanisms in the current treatment. Given the widespread applicability of their technique in public sector markets for electricity generation, spectrum licenses, and airport landing-slot rights (to name a few), the ability to produce final payments more rapidly and to better understand the selection of payment outcomes among the various possible core solutions may have a deep impact on our ability to successfully implement these market mechanisms. Indeed, researchers associated with the FCC and FAA have recently started experimenting with an implementation of the algorithm presented in this paper as a possible pricing mechanism for future auctions.
In this paper, we provide a new, more direct computational procedure for arriving at bidder-Pareto-optimal core outcomes in any sealed-bid combinatorial auction, using constraint generation and an explicit definition of the core region in payment space. Our technique may be viewed as an approximate VCG mechanism, and we provide concrete justification for the use of these mechanisms in general. At the crux of our approach, we show how to overcome one of the pitfalls of a linear programming (LP) approach to payment determination in the core, using constraint generation to handle the exponential number of constraints necessary to define the core. To accomplish this, we formulate the core separation problem, finding the most violated core constraint (most upset coalition) for any proposed payment vector. This core separation problem is also NP-hard whenever winner determination is NP-hard, and we show how to integrate the separation technique into a procedure that settles on a bidder-Pareto-optimal core point, with no need for limiting (substitutability) assumptions on the preferences of the bidders. Along the way, we solidify the concept of a coalitional contribution, measuring a winning bidder's desire to join a coalition at a particular payment vector. We demonstrate the flexibility of our technique by showing a few variations, and discuss the selection of a particular core outcome when several meet the "bidder-Pareto-optimal" criterion. In particular, we show that a mechanism that minimizes total payments consequently minimizes the total availability of gains from unilateral strategic manipulation, and is immune to a certain form of group collusion which would be profitable in any mechanism without this property. Finally, we compare the computational performance of our technique to others in the literature with a few detailed examples, and discuss directions for future research.
We begin the next section with the introduction of our notation, followed by a motivating example. In [section]3, we develop a general theory of bidder-Pareto-optimal core mechanisms to support our approach. In [section]4, we develop a specific algorithm for determining bidder-Pareto-optimal core payments, with comparisons to existing techniques in [section]5. Further, in [section]5 we reinforce our arguments on the selection of a bidder-Pareto-optimal payment vector by showing discrepancies among various solution techniques and by demonstrating a form of collusion that is nullified by our selection. We also provide a brief summary of our experience solving instances from the CATS data set. These comparisons demonstrate the effectiveness of the algorithm for computing bidder-Pareto-optimal payments presented in [section]4. Finally, in [section]6 we provide concluding remarks.
2. Problem Framework and Notation
Consider an environment where N distinct items are to be auctioned among M bidders. We will typically index each item in the set I = {1, 2,..., N} of auction items by the letter i, and each bidder in the set J = {1, 2,..., M} of all bidders by the letter j. For any set S [??] I, let [v.sub.j](S) denote bidder j's value for the bundle of items S (the maximum amount he would be willing to pay for S), and let [b.sub.j](S) denote the bid that bidder j has submitted to the auction for the bundle S. To maintain full generality, we assume an XOR language throughout (i.e., every bidder submits an exclusive bid for every possible bundle S), although the technique we propose in [section]4 easily generalizes to any bidding language that uses an IP formulation for winner determination. Further, we will use [b.sub.j] and [v.sub.j] to denote the full reports and valuations of bidder j over all bundles S [??] I.
To find an allocation of the auction items that maximizes bid value, we will make use of the following IP formulation for a general version of the winner determination (GWD) problem:
max [summation over (j[member of]J)][summation over (S[??]I)][b.sub.j](S) x [x.sub.j](S) (GWD)
subject to [summation over (S[??]{i})] [summation over (j[member of]J)] [x.sub.j](S) [less than or equal to] 1 [for all] i [member of] I, (1)
[summation over (S[??]I)] [x.sub.j](S) [less than or equal to] 1 [for all] j [member of] J, (2)
[x.sub.j](S) [member of] {0, 1} [for all] S [??] I, [for all] j [member of] J. (3)
The solution of this problem finds the efficient allocation for a given set of bids, represented by the coefficients [b.sub.j](S) in the objective function. In this formulation, each binary variable [x.sub.j](S) equals one if and only if bidder j is awarded bundle S [??] I. (Constraints (3) tell us that these variables must be binary.) Constraints (1) consequently ensure that each item is assigned to at most one bidder, while constraint set (2) prevents the auctioneer from accepting multiple bids from the same bidder. With "demand" constraints formulated...
|
