You may not have noticed, but there are hundreds of auctions being run on a daily basis because of you. Every time you open YouTube, Facebook, Instagram, Twitter, etc, within a fraction of a second, an auction is run to show you ads. This market is huge. Hundreds of millions of dollars are spent every day through these auctions. In this post I will discuss auction basics. We will try to answer questions such as: Does the auction format matter? How should the auctioneer set it? Are some auction formats equivalent to each other? How should advertisers bid? Let’s dig in.

You are probably familiar with how art auctions are run, but if you need a reminder, or have a couple minutes to spare, I highly recommend you watch the auction for the most expensive painting ever sold, Leonardo’s Salvator Mundi. This type of auction is an open-bid (meaning everyone can see everyone else’s bids), ascending price auction, sometimes also called an “English” Auction. But there are many, many other types of auctions: Dutch, Japanese, Brazilian, Scottish, and so on. In fact, the Wikipedia page for auction links to 39 different types of auctions! You may be wondering, why are there so many types? What are their differences? These are excellent questions, but in this post, to start with the basics, I want to focus only on the following types:

• Open-bid ascending-price auction (also known as an English auction): This is the “classic” art auction you are familiar with; bidders outbid each other until only one remains.
• Open-bid descending-price auction (also known as a Dutch auction). In this auction, the auctioneer starts with a high price and gradually reduces it. The first person to accept the price wins the auction.
• Sealed-bid first-price auction. Participants submit their bids in a sealed envelope and the auctioneer selects the winner as the highest bidder. The highest bidder pays the amount they bid.
• Sealed-bid second-price auction (also known as a Vickrey auction). Again, participants submit their bids in a sealed envelope and the auctioneer selects the winner as the highest bidder. This time, the highest bidder pays only an amount equal to the second-highest bid, hence the name, second-price.

I’ve chosen to focus on these types because 1) they are easy to understand. 2) we can start building intuition on how to optimally bid in them, and 3) they are related to each other in some interesting ways.

In the next section, we will show that the English auction and the sealed-bid second-price auctions are equivalent. This result is pretty magical! Notice that all the back-and-forth of waiting for someone to bid and raising bids in the English auction can be eliminated, we can simply run a sealed-bid second-price auction! Moreover, the same argument can be used to show that the Dutch auction and the sealed-bid first-price auction are equivalent!

The English Auction Is Equivalent To A Sealed-bid Second-price Auction

To see how the English auction is equivalent to the sealed-bid second-price auction (from here on, second-price auction) all we need to do is the following. Imagine an English auction is running. The person who values the item the most (let’s assume no ties) can always increase the current highest bid by 0.01 dollars. So, what will end up happening is, at some point in the auction there will only be two bidders left, and each will be raising their bid by one cent until the other bidder stops doing that. Now, when will the second-highest bidder decide to stop? If the second-highest bidder values the item at $v_2$ then they will not bid more than $v_2$ otherwise they will get negative utility and therefore will not do that. So, the highest the second-highest bidder will bid is $v_2 - 0.01$ (or $v_2$), then the person who values the item the most will bid an extra cent and pay $v_2$ (or $v_2 + 0.01$), the second-highest valuation among all the participants. Notice, however, that we have not proved equivalence between the English auction and the second-price one because we have not shown that in a second-price auction bidders bid their valuations. If we are able to prove this then we are done! We will do so in the next subsection.

How To Optimally Bid in a Second-Price Auction

Say you are participating in a second-price auction and you value the item at $v_1$. How much should you actually bid? More than $v_1$ in the hope that you win but the second-highest bidder bids less than $v_1$? Should you bid $v_1$ itself? What about bidding less than $v_1$? How much less would be appropriate if you want to maximize utility (defined as $v_1$ minus what you end up paying in case you win)?

The first thing to note is that bidding more than your valuation is never a good idea. Say you bid $v_{high} > v_1$. If the second-highest bid $v_2$ is in the interval $[v_{high}, v_1)$, then your utility, $v_1 - v_2$, is less than 0, and if the second-highest bid is in the interval $[v_1, 0]$ then your utility would be the same as if you had bid $v_1$. So you never want to bid more than your true valuation.

What about bidding less than $v_1$? Say we bid $b_1 = v_1 - c$ where $c > 0$. Then there is some chance that someone’s bid is in $[v_1, b_1]$ if that is the case then you lose the item (and you wouldn’t have lost if you had bid your true valuation). The other scenario is where the second bid is in $[b_1, 0]$, when this is the case your utility is the same whether you bid $v_1$ or $b_1$. So, to not risk losing the item, you should always bid your true valuation.

That’s it! We have shown that in sealed-bid second-price auction, participants should bid their true valuations. There is something remarkable about the argument we just made; notice we never went into the “If I think the other bidders’ valuation is bla, and they think that my valuation is blabla, then I should be bid bla because they think I’m going to bid blabla… and so on.” For some reason this type auction admits a very simple strategy that doesn’t depend on the actions of other bidders. Economists and computer scientists like to call these kinds of mechanisms incentive compatible (I will have more to say about incentive compatibility in a later section).

So, if we combine the fact that in second-price auctions participants should bid their true valuations, together with the fact that in an English auction the winner pays the second-highest valuation, this shows that the English and the sealed-bid second-price auction are outcome equivalent.

Now it is your turn to convince yourself that the Dutch auction is equivalent to the sealed-bid first-price auction :)

Should You Run a First-Price or a Second-Price Auction?

We’ve shown the equivalence between the open-bid and sealed-bid auctions discussed above. So now you may wonder, what type of auction should an auctioneer choose if they want to sell an item? A first-price or a second-price one? Which is more likely to yield a higher profit?

How to Optimally Bid In a Sealed-Bid First-Price Auction

Think about it for a second. How would you do it? Should you bid your valuation just as in the second-price auction? The answer to the last question is no, this is because if you were to win the auction then your utility would be exactly 0. So you should bid less than your valuation, this also sometimes called shading your bid. But how much less? At this point, we need to start making assumptions and get more information. A good piece of information is the number of bidders that will participate in the auction. Intuitively, if we knew there was only one other bidder then we could probably risk it and bid significantly less than our true valuation (after all, what are the chances that the other bid is higher than our bid). However, if we knew there were one thousand bidders then we probably don’t want to shade our bid too much as it is more likely someone will bid higher than us. From now on we will assume the number of bidders in the auction, $n$, is known. But knowing $n$ is not enough, we need a model for the population’s valuations. We will assume that the bidders’ valuations are sampled i.i.d. from a probability distribution with cdf $F(x)$, where $F(x) = P(X < x)$ represents the probability that a (random) valuation $X$ is less than $x$.

Under this model, if our valuation is $v_1$, and we condition on the fact that we think we will win the auction. Then we want to bid one cent more than the expected maximum valuation (conditioned on the fact that all valuations are less than ours). The distribution for the maximum valuation is then

\begin{align} G(x) &= P(X < x | X < v_1)^{n-1} \cr &= (\frac{P(X < x, X < v_1))}{P(X < v_1)})^{n-1} \cr &= (\frac{F(min(x, v_1))}{F(v_1)})^{n-1}, \end{align}

the first equality is true because for the maximum valuation to be less than $x$ we need $n-1$ valuations (conditioned on the fact that they are less than ours) to be less than $x$. The second equality uses the definition of conditional probability, and the third one is just using the definition of $F$. We should then bid $b = \mathbb{E}[Y]$ plus one cent, where $Y$ is a random variable with cdf $G$. By the tail sum formula, we should bid $b = \mathbb{E}[Y] = \int_0^{v_1} (1 - G(x)) dx$. This is technically a closed-form expression for the optimal bid, but, to make this more concrete let’s go through a simple example.

Say we are now the auctioneer and we know that there are only 2 bidders in our auction, let’s also assume that the distribution of each of the bidder’s valuations is distributed uniformly in the interval [0, 1]. What is our expected revenue from running the auction? Well, if $v_1$ and $v_2$ are the valuations of bidders 1 and 2 resp. Then player 1 will bid $\frac{v_1}{2}$ since a uniform random variable in [0, 1], conditioned on it being less than $v_1$, has the uniform distribution in $[0, v_1]$, and hence its expectation is $\frac{v_1}{2}$. Similarly, bidder 2 will bid $\frac{v_2}{2}$. So our expected revenue, since we are running a first price auction is

\begin{align} \mathbb{E}[\max(\frac{v_1}{2}, \frac{v_2}{2})] &= \frac{1}{2} E[\max(v_1, v_2)] \cr &= \frac{1}{2} \int_0^1 P(\max(v_1, v_2) > x) dx \text{ by the tail sum formula} \cr &= \frac{1}{2} \int_0^1 (1 - P(\max(v_1, v_2) \leq x)) dx \cr &= \frac{1}{2} \int_0^1 (1 - P(v_1\leq x)P(v_2 \leq x)) dx \cr &= \frac{1}{2} \int_0^1 (1 - x^2) dx \cr &= \frac{1}{3}. \end{align}

So, we expect to receive one third of a dollar in this first-price auction. Now, how does this compare with the revenue of a second-price auction? In a second-price auction our expected revenue is:

\begin{align} \mathbb{E}[\min(v_1, v_2)] &= \int_0^1 P(\min(v_1, v_2) > x) dx \cr &= \int_0^1 P(v_1 > x, v_2 > x) dx \cr &= \int_0^1 P(v_1 > x) P(v_2 > x) dx \cr &= \int_0^1 (1 - P(v_1 \leq x)) (1 - P(v_2 \leq x)) dx \cr &= \int_0^1 (1-x)^2 dx \cr &= \frac{1}{3}. \end{align}

This is the same expected revenue as in the second-prize auction! This is pretty nice, but, is it just a coincidence? Does the result only hold when $n=2$? Or is the assumption that valuations are uniformly distributed causing this?

It turns out this is not a coincidence, the expected revenues will be the same in both types of auctions regardless of $n$ and on the distribution of the valuations. This surprising (and beautiful) result is known as the Revenue Equivalence Theorem (Vickrey, 1961). In the next section, we will state and prove this theorem.

Revenue Equivalence Theorem

The statement of the theorem, and most of the proof, comes from (Klemperer, 1999), but the first versions of this result come from (Vickrey, 1961; Myerson, 1981; Riley & Samuelson, 1981). I’ve added additional explanations where I think they were necessary.

Theorem. Assume each of the $n$ risk-neutral bidders for an object has a privately-known valuation independently drawn from a common, strictly-increasing, atomless distribution and assume this function is known to everyone. Then, any auction mechanism in which:

• (i) the object always goes to the buyer with the highest valuation, and
• (ii) any bidder with the lowest feasible signal expects zero utility

yields the same expected revenue for the auctioneer.

Proof. For simplicity I will restrict our attention to mechanisms such that each player submits a bid and the mechanism selects a single winner out of the $n$ players. So, in this case, a mechanism is a mapping $M: \mathbb{R}^n \rightarrow [n]$. Recall $[n] = {1, 2, …, n}$. I think the statement also holds for mechanisms in which players can have multiple interactions among themselves or the auctioneer, I’ve chosen not to consider these mechanisms for the sake of making the argument in the next paragraph a bit more rigorous.

The first observation is that, since the number of players $n$ as well as the distribution of valuations $F: [\underline{v}, \overline{v}]$ are know to all bidders, then the optimal bidding function $b(v)$ (recall $v$ represents a valuation) is known to all of the players.

For every $i$, let $b_i = b(v_i)$. The item will then be assigned to whatever $M(b_1, b_2, …, b_n)$ evaluates to, and since $M$ is such that the object always goes to the buyer with the highest valuation, then the probability of player $i$ winning, $P_i(v_i)$ is the probability that player $i$ has the highest valuation, so $P_i(v_i) = F(v_i)^{n - 1}$. Notice how the probability of winning is the same regardless of the mechanism (as long as it satisfies (i) of course)! I’ve heard many times that when trying to solve a hard math problem one has to find the invariants, well here is your invariant :)

Now, to proceed with the proof we have to write some sort of equilibrium condition. For those with optimization backgrounds, what follows is the equivalent of writing the optimality condition for your problem and then deriving a consequence out of it.

Let $S_i(v_i)$ be the expected utility of player $i$ in equilibrium when their valuation is $v_i$. We have that $S_i(v_i) = v_i P_i(v_i) - E_M(v_i)$ where $E_M(v_i)$ represents the expected payment of player $i$ when the bid according to valuation $v_i$. If player $i$ were to report a different valuation, $\tilde{v}$, in hopes of being strategic, then its surplus would be $v_i P_i(\tilde{v}) - E_M(\tilde{v})$. Since we are in equilibrium, and player $i$ is risk-neutral, we have that:

\begin{align} S_i(v_i) &\geq v_i P_i(\tilde{v}) - E_M(\tilde{v}) \cr &= v_i P_i(\tilde{v}) - E_M(\tilde{v}) + S_i(\tilde{v}) - \tilde{v} P_i(\tilde{v}) + E_M(\tilde{v}) \cr &= S_i(\tilde{v}) + (v_i - \tilde{v}) P_i(\tilde{v}). \end{align}

Plugging in $\tilde{v} = v_i + dv_i$ above we get:

\begin{align} S_i(v_i) \geq S_i(v_i + dv_i) - dv_i P_i(v_i + dv_i). \tag{1} \end{align}

Applying the same argument, when the actual valuation of the player is $v_i + dv_i$ instead of $v_i$, we have that

\begin{align} S_i(v_i + d_i) \geq S_i(v_i) + dv_i P_i(v_i). \tag{2} \end{align}

Rearranging terms in (1) and (2) we get

\begin{align} P_i(v + dv) \geq \frac{S_i(v_i + dv_i) - S_(v_i)}{dv_i} \geq P_i(v_i). \end{align}

Taking the limit as $dv_i \rightarrow 0$ we get

\begin{align} \frac{dS_i}{dv_i}(v_i) = P_i(v_i), \end{align}

since we assumed that $F$ was strictly-increasing and atomless, and these properties also apply to $P_i$.

Taking the integral we have

\begin{align} S_i(v_i) = S_i(\underline{v}) + \int_{\underline{v}}^{v_i} P_i(x) dx. \end{align}

By assumption (ii), $S_i(\underline{v}) = 0$. This means that the function that describes the expected utility as a function of the player’s valuation is fully determined by the probability of winning as a function of the valuation $P_i(v_i)$.

Let’s focus on any player $i$, and its type $v_i$. Recall that any two mechanisms will have the same $P_i(v_i)$, it follows that they must have the same utility functions $S_i(v_i)$, and since $S_i(v_i) = v_i P_i(v_i) - E_M(v_i)$, for any two mechansims $M_1$ and $M_2$ it must be the case that $E_{M_1}(v_i) = E_{M_2}(v_i)$. Since the expected payment is equal across two different mechanisms holds for any player $i$ and for any valuation $v_i$, it will also hold when the valuation of player $i$ is randomized. This is also true for all players, so it must be that case that the auctioneer receives the same expected payment regardless of the mechanism they choose. Q.E.D.

This is pretty cool! The result implies that the auction format does not really matter at all! The facts that the second-price auction is incentive compatible, or that in first-price auctions participants shade their bids are not important for the auctioneer, in expectation the revenue they will receive is the same in both auctions.

But we have to be really careful with how we interpret the result. The Revenue Equivalence Theorem implies that if the auctioneer were to run many auctions in which different bidders with i.i.d. valuations show up to bid (let me call this setting i.i.d. auctions), then the risk-neutral auctioneer should be indifferent between auction formats as long as they satisfy (i) and (ii). Notice that the theorem does not say anything about repeated auctions i.e. when the auctioneer will sequentially auction many items to a fixed set of bidders with i.i.d. valuations.

Repeated Auctions and Incentive Compatibility

The previous paragraph raises the question: in the repeated auctions setting, does the (incentive compatible) second-price auction prevent participants from shading their bids? The following example shows that this is not the case. Consider two players with valuations $v_1$ and $v_2$ who will participate in 3 second-prize auctions, for simplicity let’s set $v_1=1$ and $v_2=.9$. If they were to bid truthfully in all three rounds then player one’s surplus is $.3$, player two’s is $0$, and revenue for the auctioneer is $2.7$. But what if both players play according to the following strategy:

• In the first round I will bid truthfully.
• In the second round, if I won the first auction I will bid one cent less than the other player’s bid in the first round. If I lost the first round I will continue to bid truthfully.
• In the last round, if I am the player with the highest valuation I will bid truthfully, if I am not, I will bid .01 as a form of gratitude to the player who let me win the second auction.

Using this strategy, player one’s surplus is $.1 + .99 > .3$, player two’s surplus is $.01 > 0$ (and this is the reason they will not bid truthfully) and the revenue for the auctioneer is $.9 + .01 < 2.7$. The fact that the second-price auction is incentive compatible does not prevent players from shading their bids in the repeated auction setting!

This is all I have to say about repeated auctions for now. In practice, to prevent scenarios like the one above the auctioneer may decide to introduce a “reserve price”, you can think of it as the minimum bid the auctioneer wants to receive during the auction.

So, How Are Ad Auctions Run?

Yes, I have gone on a detour and not yet told you how Ad auctions are actually run, but its been a fun ride hasn’t it? Ad auctions are typically implemented as generalized second-price (GSP) auctions. GSPs are very similar to second-price ones except that the player’s bids are multiplied by the probability of you clicking that particular Ad. By incorporating the probability of you clicking an ad, the auctioneer attempts to, not just show to the ads corresponding to the highest bids, but also those that are the most relevant to you. I will have a lot more to say about GSPs but I’ll leave that for a future post.