## Sold!

A bowler hat and cane worn by Charlie Chaplain in the movie Little Tramp recently sold at an auction in L.A. for \$62,500.  Now, I have no idea how that price stacks up to other Amazing Deals in History, but it raises an interesting question.  Viz., how much should you bid for an item at auction?  Is there a strategy that maximizes auction-related satisfaction?  Lucky for mathematically-inclined bloggers, the answer to the second question is a qualified yes: as long as certain conditions are met, you can find a dominant bidding strategy.  More accurately, you can find one of several dominant bidding strategies, depending on the rules of the auction you're interested in.  We'll look at two in particular.

# Going Once...

Let's start with a simple example.  Imagine that you're bidding on this incredibly sweet poster from The Empire Strikes Back (also imagine that you have human friends), which you personally value at \$100.  How much should you bid?

A fantastic question. but before we go any further, let's lay out those "certain conditions" I mentioned a minute ago so that we're all on the same page.  As with every mathematical model, we have to build in some assumptions.  Here are the four biggies that we need to be concerned about, which we will take as given for the rest of the discussion:

1. Private Values.  Each bidder has his own personal valuation of the auction item, which is unknown to every other bidder.  Moreover, this is the only private information in the auction; all the other details are commonly known to all participants.
2. Independent Values.  We will collectively treat the bidders' private values as independently distributed random variables.  No collusion, no exogenous info.  No bidder's value is a function of any other's.
3. Symmetry.  Every bidder's value belongs to the same probability distribution. (Really, when #2 and #3 are taken together, they say that all the private values are i.i.d.)
4. Risk Neutrality.  Like a perfectly well-behaved little Homo economicus, each bidder is a rational actor seeking to maximize profit.

The first scenario we'll consider is what's called a First-Price Sealed-Bid (FPSB) auction, which means that everyone submits a sealed bid simultaneously, and the highest bidder pays that amount for the poster.  Ultimately we would like a rock-solid strategy for FPSB auctions, but we need to pin down exactly what your goal in an auction ought to be.  Yes, you want to acquire this fine piece of Americana, but that's not your only consideration; you also need to think about how much you should pay for it.  This is where assumption #4 comes in: your goal is to maximize profit.  Let's first notice that, if you end up paying \$100, nothing of economic note has transpired; you've simply exchanged \$100 worth of American legal tender for \$100 worth of kitsch.  The net value of your holdings remains unchanged, and you'd be precisely as well off if you'd simply declined to participate in the auction altogether.  If you pay any other amount, however, you have either gained or lost an amount equal to the difference between your payment and the \$100 value.  Okay. So this helps make the problem more precise: we want to find a strategy that maximizes the (positive!) difference between the item's value and the amount you pay.

As such, there is an incredibly simple solution: just bid the minimum allowable amount and bask in your reward.  But of course it's not really that simple, because we have to take into account that there other bidders who are also vying for the poster.  Once another person enters the picture, your own personal bid has two opposing effects.  On one hand, the lower your bid, the greater your potential gain, which is good.  On the other hand, the lower your bid, the lower your probability of winning the auction, which is bad.  Higher bids, of course, work the other way around.  How do we find the sweet spot?  We think about expected value, naturally. Let's examine the case where you have only one opponent.

To calculate your expected value in the poster auction, we need two things: the payoff from a given bid, and the probability of winning with that bid.  The first one is easy.  Since you value the poster at \$100, the payoff of any bid, b, is simply \$100 - b.  The probability of a win is just a touch trickier: after all, you have no information about the other guy's bid (assumption #1).  As far as we're concerned, it could be any number at all.  Lucky for us, though, a lack of information can sometimes simplify matters greatly.  Even though we're completely in the dark as to how much our opponent values the poster, we need only worry ourselves up to \$100 worth of giving-a-hoot.  If he wants to bid more than that, great, but that doesn't mean anything to you at all, since anything over \$100 would constitute a loss from your perspective.  So we will assume that your opponent's bid can be any number between \$0 and \$100, with equal probability.  In more impressive language, his bid has a uniform distribution on the interval [0, 100].  That's the best we can do.  (Okay, technically his bid is uniform on [0, ∞), and we're dealing with conditional probabilities given that his bid is no greater than your private value, but restricting the interval is a convenient way to think about it.)  But wait, that makes our probability calculations really easy!  The probability of placing a winning bid is just the probability that your opponent's bid lies in the interval below your bid.  Thusly:

So a \$30 bid has a 0.3 probability of winning, a \$75 bid had a 0.75 probability of winning, and a bid of b dollars has a b/100 probability of winning.  Easy peasy. Now we can write an expression for your expected value, which we will henceforth maximize.  You'll gain \$100 - b when you win, which happens with probability b/100, and you'll gain \$0 otherwise.  So, E(b) = b/100 * (100 - b).  When you plot that expected value against your bid, you get a function that's quadratic in b and looks like an awful lot like this:

Using some calculus, or any of the fancy tools in your quadratics toolbox, you'll find that your expected value is maximized with a bid of \$50 (which nets you \$25 on average).  Anything higher and you don't make enough profit; anything lower and you don't win often enough.  We've been using the poster as an example, but it's important to note that the object is irrelevant: if you personally value an item at v, then your best bid in a FPSB auction against one opponent is v/2 (try it out).  But that's not much of an auction.  What if there are lots of other bidders?

We can use the same reasoning we did just a minute ago, except now the probability of your bid being a winner is equal to the probability that all the other bids lie in the interval below b.  Since, as before, we're assuming that each bid is uniformly distributed on [0,100] (assumption #3), and that they are independent of one another (assumption #2), the probability that n other people all bid lower than you is just b/100 raised to the nth power.  When you plug that into our expected value formula from before, with various values of n, you get a series of curves that look like this (here ranging from one other bidder, as above, to ten other bidders):

You should immediately notice two things about your profit-maximizing bid: (1) it's getting closer and closer to your item's private value, and (2) the expected gain associated with that bid is getting closer and closer to zero.  A little more calculus will get you a general rule for your profit maximizing bid: against n other opponents, you should bid n/(n+1) of your private value.  So, for instance, against nine opponents, you should bid 9/10 of what you think the item is worth.  Even if the details aren't obvious, the result should be intuitively pleasant: as more people enter the fray, you have to pay, on average, a higher price to win the auction, which in turn eats into your profit.

Here's another picture of what's going on:

Each horizontal band represents a number of opponents from one (top) to ten (bottom), with a bid of 0 on the left and a bid of v on the right.  The brighter the band, the higher the expected value, and the green dots represent the optimal bids for each case.  You can see that things get dire pretty quickly.  When bidding against lots of people, you should basically bid the smallest allowable amount less than your private value and hope for the best.  If there are only relatively few other people, say n, then you should figure out how much you value the item, multiply that value by n/(n+1), and bid the resulting amount.

# Going Twice...

Let's change the rules just slightly.  We're still going to have sealed bids, and the poster still goes to the highest bidder, but now the winner only has to pay an amount equal to the second-highest bid.  This is a Second-Price Sealed-Bid (SPSB) auction, sometimes called a Vickrey auction after the Canadian economist who invented it.  Crazy, you say?  There's actually an incredibly popular type of auction that functions very nearly this way.  If you've ever used eBay's proxy bidding feature, you know exactly what I'm talking about.  Proxy bidding works like this: I tell eBay the maximum amount I'm willing to spend for an item; as soon as someone outbids me, eBay automatically increases my bid so that I become the new highest bidder -- by the smallest possible amount.  If I win the auction, it means that I've placed the highest sealed bid, but I'm only on the hook for the second-highest bidder's amount (plus a tiny increment).  So...what should you do in this case?

Notice that, in the FPSB case, your optimal bid only converges toward your private value as the number of opponents increases, while in the SPSB auction, your optimal bid is precisely the private value, irrespective of how many other bidders are involved.  In other words, FPSB auctions encourage underbidding, while Vickrey auctions encourage truthful bidding.  Why does that matter?

# Sold!

Well, it matters for lots of economic and game-theoretical reasons (some more arcane than others), but here's something we haven't yet considered: Which type of auction would the seller prefer?  After all, she is a participant in this transaction who is also seeking to maximize profits, in this case by maximizing her selling price.  We might reasonably conjecture that, since first-price auctions encourage underbidding, she should prefer to sell her poster in a Vickrey auction.  Like I said, reasonable.  But then we remember that, even though Vickrey auctions produce higher winning bids, those winners don't actually pay the winning amount; they pay less than that. Hmmm.

Once again we've run into a situation where there are two opposing forces at work. First-price auctions produce lower average bids, but relatively higher selling prices; second-price auctions produce higher average bids, but relatively lower selling prices.  The real question for our poster seller, then, is which force has a greater effect on her revenue?

The beautiful and surprising answer (at least I think so) is neither.  The two effects precisely offset one another!  Our seller's expected profit under both schemes is exactly the same.  Actually, for many more than just these two schemes.  For a very broad class of auctions, the actual mechanism of determining how the bids are taken and how much the winner pays have absolutely no impact on the seller's expected revenue.  This result, again due to Vickrey, is known as the Revenue Equivalence Theorem.  It essentially says (some technical details omitted) that in any auction that always gives the item to the highest bidder, and in which anyone who makes the lowest allowable bid has zero expected profit, the expected payment by the winner -- and thus the expected revenue for the seller -- will be identical.  How lovely.