Auction theory puzzle: finding the right number of bidders

If you liked yesterday’s puzzle about optimizing with uncertain demand, you’ll definitely enjoy today’s post.

One of my favorite topics related to game theory is the subject of auction theory.

The results from auction theory are very interesting, but I have yet to cover much about it because the math can be quite intimidating.

Today’s problem is still challenging, but it should be within the reach of a math enthusiast. Here is the puzzle:

Alice wants to auction off a rare collector’s item. She knows the item is worth somewhere betweeen $500 and $1,000, but she has had trouble finding interested buyers.

A company offers to find interested participants at the rate of $10 per bidder. (So they’ll find one bidder for $10, and ten bidders for $100)

How many bidders should Alice tell the company to find?

A couple of points:

–Assume the bidders have valuations randomly drawn from the uniform distribution on [500,1000]

–Suppose Alice holds an eBay style auction and she will sell the item for a price equal to the second highest valuation of the bidders*

(*this is a standard result in auction theory, though technically it’s for one bid above the second highest valuation. An example: if bidders had valuations of $500, $600, and $700, the person who values the item at $700 would win the auction. The price he would pay in an eBay style auction with dollar bid increments is $601–just enough to outbid the person with the second highest valuation)

The puzzle is about two conflicting forces: Alice wants more bidders to bring her higher bids, but she faces a tradeoff in the cost of acquiring bidders.

Can you figure out the optimal number of bidders?

The answer is written below.

Spoilers below!
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Answer to the puzzle

Alice wants to maximize her expected auction profits. The equation for profits for n bidders is something like this:

Profit(n)= E(revenue n) – Cost(n)

The cost part is easy to figure out. Alice pays $10 per bidder, so her cost is 10n.

The harder part is figuring out the expected revenue for n bidders. What we want to know is the following. If we take n draws from a uniform distribution, what is the expected value of the second-highest draw?

This question is actually part of a larger topic in probability called order statistics. One can explicitly solve for the expected value of any distribution using the technique outlined in this lecture (pdf).

I will not go through the math here. But I will mention the order statistics for the uniform distribution are easy to visualize. What happens is that if you take n draws from the uniform distribution, the expected value of the n draws can be visualized as n points being evenly spaced on the interval.

Here is a picture to illustrate what I mean:

So the n points separate themselves along the interval. So you divide the interval into n+1 segments, and the points will be at the fractions 1/(n + 1) along the way for the minimum, then 2/(n + 1) along the way for the second lowest point, etc., until the maximum draw which has an expected value of n/(n + 1).

By this logic, the second highest draw is expected to be at (n – 1)/(n + 1) along the way from 500 to 1000. This means the second highest valuation is expected to be:

500 + 500 * (n – 1)/(n + 1)

This is our formula for expected revenue. So we can substitute this expression back into the formula for profits:

Profit(n)= E(revenue n) – Cost(n)
Profit(n) = 500 + 500 * (n – 1)/(n + 1) – 10n

Now we need to solve for the profit maximizing point. Let’s just use a shortcut and plug this into WolframAlpha:

We can see that the profit maximizing point is at n = 9 bidders, and Alice can expect $810 of profit.

The lesson is that more bidders is not always optimal: you capture much of the expected revenue from the first few bidders, and then the returns are diminishing (unless some bidder is a big outlier and you can extract money from him).

Extension: suppose Alice earned the highest valuation

As an extension, let’s imagine that Alice somehow was able to extract the highest bidder to pay his entire valuation. This is not an assumption used in theory, but let’s say it happens because of some irrational bidding war.

In that case, Alice would expect to earn slightly revenue (the term (n – 1)/(n + 1) becomes n/(n+1)), meaning her profit function is:

Profit(n) = 500 + 500 * n/(n + 1) – 10n

How will that change the number of bidders?

Here is the answer:

So Alice will only need to acquire 6 bidders, but she will earn nearly $870. This is 3 fewer bidders than above and she gets about $60 more.

This is, of course, exactly what we would expect: if Alice can extract more money from the bidders–the highest valuation instead of the second–she does not need as many bidders and she can earn more out of it.

This is common sense, but it’s useful to check the theory matches intuition.