Two companies, David Enterprises and Goliath, Inc., have built competing products. Although David Enterprises is the smaller firm, David's product is gaining market share. One of the machines that David's product needs is produced only in small batches of six per month. David must buy two machines per month.

The machines are sold individually by standard English outcry auction ("Going once, going twice..."). Bidding rules dictate that bid amounts increase in increments of $1,000. A bidder must never bid more money than he or she has.

Until recently, David was the only bidder, and so was able to purchase the machines for their minimum price of $5,000 apiece, but now Goliath, in order to thwart David, plans to bid, too. Because he has been such a good customer, though, David has the privilege of making the first bid.

Warm-up problem: Suppose that David is correctly known to have only $100,000 and needs two machines, and that there are only three altogether. How much money does Goliath need to prevent David from getting what he needs?

Solution to warm-up: Goliath needs $102,000. Here is why. If David bids $50,000 or less for the first item, then Goliath will take it for at most $51,000. The same holds true for the second item. If David bids $51,000 or more for the first machine, Goliath allows him to take it-knowing that David can never bid more than $49,000 on either of the other two. Goliath never needs to spend more than $102,000.

Problems:

1. Suppose that David is correctly known to have $100,000 with which to bid. Can David be sure to get two machines out of six if Goliath can use only $200,000 to thwart him?

2. If production is increased to ten machines a month, but David needs three and is known to have only $100,000, can Goliath thwart him with $200,000?

3. Now, here is a much harder question: suppose Goliath will pay whatever it takes to stop David from getting two of six machines, but doesn't know how much money David has except that the amount is no more than $100,000. Can you find a protocol that will ensure that Goliath need not spend in excess of $100,000 more than he would spend if he knew how much David had? If not, then how much more would Goliath need? If so, then could Goliath do it with less of a penalty?

The solutions will be posted by December 21.