Combinatorial Auction

We examine here a solution to the problem of allocating a heterogeneous collection of discrete goods to bidders by means of an auction. I suspect that these problems may have been treated in job shop scheduling literature. We first introduce Second Price Auctions and then generalize to the second price double auction.

The Second Price Auction

In a second price auction for a single good, bidders submit sealed bids. The highest bid wins but the winner pays the amount of the second highest bid. In such auctions, bidders are motivated to bid their true values. This is in contrast to the more usual first price sealed bid auctions where bidders hope to gain by placing lower bids so as to gain the good at a price less than the value they place on the good. Such auctions often misallocate the good to a bidder for whom the good was not most valuable. When the winner pays the second highest of all the bids there are no such gains from bidding less than one’s value and no consequent misallocation. The second price auction also avoids the intellectual cost of estimating the bids of other bidders as well as the costs of mis-estimate.

Auction Stability

We first generalize to two goods and three bidders. Suppose we have two distinct goods, P1 and P2, to auction. P1 and P2 are each one second of time on two processors with the same instruction set but P1 has much faster floating point function. Processes B1, B2 and B3 bid and they each know the merits to their own code of P1 and P2. None of the processes can use both processors at once. We hold a simultaneous auction for P1 and P2 wherein process Bi submits bids bi1 for P1 and bi2 for P2, hopefully by stating its value for each. The auctioneer opens the bids and awards P1 to Bj and P2 to Bk by choosing j and k so as to maximize bj1 + bk2. How shall we compute the bill so as to remove the incentive to understate the values in the bids?

For a concrete case suppose that B1 bids <5, 3> for P1 and P2 respectively, that B2 bids <4, 4>, and that B3 bids <3, 2>. We award P1 to B1 and P2 to B2 achieving a total value b11 + b22 = 9. Had B1 not bid we would have awarded P1 to B3 and P2 to B2 for a total value of b31 + b22 = 7. We define the impact of some winner as how much less value others got according to the values that they expressed in their bids, by virtue of the winner winning the bid. Impacti = (what everyone else would have gotten, had Bi not bid) − (what everyone else got). Alternatives to “impact” are “imposition”, “displacement” or “opportunity cost”. We propose that each winner pay the impact of his winning. In the above case everyone else for B1 is {B2, B3} and the price for B1 is: (b22 + b31) − b22 = (4 + 3) − 4 = 3. The other winner is B2, and everyone else is {B1, B3} so B2 pays (b11 + b32) − b11 = (5 + 2) − 5 = 2.

We now introduce the discrete case in full generality. Each bidder submits several sealed bids. Each bid specifies a dollar amount and enumerates which goods it demands. The bidder is required to pay for at most one bid. A suite is a combination of bids, composed of zero or one bid from each bidder, that does not over allocate the goods. The auctioneer opens the bids and selects the suite with the maximum aggregate value. The impact of a given bidder is again (what everyone else would have gotten, had he not bid) − (what everyone else got). The impact may be difficult to compute but lets take a real life example now in the news that might warrant expensive computation.

The FCC now intends to auction in May of 1994 combinations of frequencies bands and geographic areas in which those bands may be used for a new type of cellular phone. The total value has been estimated at $10,000,000,000. Each good here is one band in one area. Particular combinations are very valuable as they permit cellular users to move from one area to another without changing contracts. The FCC has already delineated the areas (I think) and will soon delineate the bands.

How to Run the Auction

I propose that all of the bids be made public after they have all been submitted. Anyone is permitted to propose a winning suite while claiming its total value. While such suites may be hard to find, such claims are easy to verify. Only the claims with the highest claimed values need be verified. (There is a small penalty on misstating the claim.) Bidders are motivated to show that there is a suite where they are one of the winners. The auctioneer may do his own search. The winning suite is merely the proposed suite with the highest claimed value.

The price is more problematical. That requires finding some estimation of what the best suite would have been if a particular winner had made no bids. If competitors are trying to damage each other then they might try to show high value what-if suites. It seems awkward to rely on such incentives. Paying a bounty of 0.01% of suite value for the maximum alternative suite might do the job.

I can imagine that some bidders would want to make large numbers of bids, indeed families of bids generated by some algorithm. Doing so might indeed be required for an efficient auction. This scheme might bog down for more then ten thousand or so bids. If it can be determined that very large numbers of bids are not necessary for efficiency then a fee of $1000 per bid submitted would solve the problem.

The space of bids is so rich that bids of competitors may stimulate ideas that yield a better (more efficient) set of bids, not because bidders understated their values but because they had not considered some combinations. An iterated auction for the same goods rewards bidders for waiting for the final auction. If the bids are not sealed then late bidders may seek to damage competitors by placing losing bids that increase the price paid by their competitors. This can misfire if bidders are allowed to withdraw bids. Such a period of open bids is probably unstable, especially toward the end. A Poison distributed ending day solves the ending problem but is hard on the nerves! (Each evening, with probability 0.03, the day is declared to have been the last.)

This bidding scheme allows for expression of synergistic values of combinations of goods.

In the mathematical annex I would like to prove that there is no benefit in bidding other than one’s true value and also prove that no cartel of bidders can damage another bidder except by damaging themselves more.

The Second Price Double Auction (Sellers too)

Second price auctions do not speak of the incentives of the commodity seller. There is an elegant extension of the auction to include sellers. We shall sneak up on the result.

First a technical modification to the rules. We introduce the null bid in order to simplify the code and arguments about the auction. Each bidder is considered to also submit a null bit of the form <value=0, goods=<0, 0, ...0>>. With this modification we require the auctioneer to choose exactly one bid from each bidder for each suite; the auctioneer selects the null bid where he would otherwise have not selected any bid from that bidder for that suite.

Suppose that S wishes to sell some goods for a price K or better. S joins the bidders by including a deed to K units of the good in his sealed bid and adding K units of demanded units for the good to each of his bids, including the null bid, thus changing his null bid <value = 0, goods = 0> to <value = 0, goods = <0,0... K...0>>. (The deed is some sort of futures document.) The auctioneer, having the extra goods, allocates the goods by choosing the bids for all bidders by the same rules as before the transformation. If the null bid is the only bid that S makes, then the auctioneer must select that bid and S gets his goods (and deed) back. If S also includes the bid <value = −B, goods = 0> then S is, in effect, bidding to sell his goods. When the auctioneer selects that bid S relinquishes his deed to the goods and pays −B or less. This means that S receives B or more for his goods. How much more is the surplus value just as if he were bidding to buy.

We must consider the rule for computing the bill. The formula was that Bi pay the impact that he has on the value delivered to other bidders and Impacti = (what everyone else would have gotten, had Bi not bid) − (what everyone else got). We consider a concrete case.

B1 (= S) submits an envelope: (Deed for 5 units of good x, <value = 0, goods = <0,0... 5...0>>, <value = −10, goods = 0>). In effect B1 offers to sell 5 units of good x for 10 dollars. B2 submits (<value = 0, goods = 0>, <value = 15, goods = <0,0... 5...0>>). B2 offers hereby to buy 5 units for 15 dollars. Sounds like a deal can be made. Lets see what the auctioneer says.

The auctioneer selects the second bid of each bidder. Value to B1 is −10 and to B2 is 15. If B1 had not entered the auction nothing would have been delivered to B2. Impact1 = (what B2 would have gotten, had B1 not bid) − (what B2 got) = (0) − (15) = −15 and thus B1 sells his capacity for 15. B2’s bill is Impact2 = (what B1 would have gotten, had B2 not bid) − (what B1 got) = (0) − (−10) = 10. This auctioneer will be very popular!

This is hardly a change in the code except to check the validity of the deed, and subdivide and reconvey the capacity it represents.

We examine the incentives of someone selling time that he owns and also the incentives of someone thinking of buying more machines, or more generally, investing in the ability to make more commodity. Common circuits and even entire computers consume power in proportion to the power of the voltage of the power supply. The speed, however, varies only linearly with the power at best. It is possible to change voltage in a few milliseconds. It is also possible to change the speed of different banks of RAM. If a bid is the true value to the bidder then ...

This is a public key crypto protocol which obviates the auctioneer if the bids become open. A trusted agent creates a public-private key pair and publishes the public key. Each bidder encrypts his bid with the public key and publishes the encrypted bid. At the appointed hour the secret key is published. Everyone then knows all of the bids and knows that none of the bids were made with knowledge of the highest bid. This eliminates the possibility of auctioneer creating bogus bids based on knowing the amounts of the winning bids in order to inflate the Impact and thus the income of the seller. It is easier to trust agents with simpler protocols. It could be a simple computer.


I want to argue that an options market is an efficient way to plan for contingencies. In particular I need to understand how an options market works when late developing correlated demands arise. When option writers hold title to the commodity and write no conflicting options then things seem safe. Is there a difference between a call and an option? Bare options may be written by someone who does not hold title to the commodity. If the option buyer exercises the option then the writer is obligated to produce the commodity even if he must buy it on the spot market at a price higher than the option’s striking price, which is precisely the situation that the buyer of the option was guarding against. The option writer may be unable to buy the commodity and thereby default. I seem to remember some potato futures where the writers were got off the hook by by declaring “act of God”. I think that it was merely a bad year. Obviously potato options lost reputation. I think it was potato futures and not options. I think that the difference between a future and an option is that the owner of the future is responsible for disposing of the underlying commodity when the future matures. This is most often done by selling the future and never seeing the potatoes. Here is an article by George Guilder advocating auctioning the radio spectrum.