In free markets a core element is the auction - a procedure for optimal allocation of scarce resources. Auctions have multiple social benefits: they help to deliver an item to the person that values it most; through bidding prices, they reveal underlying demand; and they generate revenue for the sellers. They also play a big part in our world today - radio spectrum, electricity markets, carbon and pollution permits, treasury bonds, fishing quotas and natural resources, online advertising, airport slots and transport rights, art and collectibles - all based on auctions.

The most basic auction has an intuitive design. There is a single item to be sold and \(n\) strategic bidders. Each bidder \(i\) has a private nonnegative valuation \(v_i\) of that item, representing his maximum willingness-to-pay (WTP). The bidder wants to acquire the item as cheaply as possible, and his utility is quasilinear: zero if he doesn't acquire it and \(v_i - p\) if he does acquire it for a price \(p\). As a first example we have the English auction where bidders sequentially outbid each other and the person with the last, highest bid wins. The Dutch auction is similar but in decreasing price: the seller starts with a high price and continuously lowers it. The first person to accept the price gets the item.

Sealed bid. We'll focus on sealed-bid auctions, which are more scalable and offer better information control. They proceed as follows: 1. all bidders submit their bids privately to the seller, 2. the seller decides who gets the item (if anyone), and 3. the seller decides on a selling price. For the second step, the obvious case is when the seller gives the item to the highest bidder. However, for the third steps, there are different options, with different implications.

First price auctions. In a first price auction the highest bidder wins and pays his own bid. From the perspective of bidder \(i\), he will get the item if he bids more than the highest other bid, suppose \(p_j\), but his utility would only decrease if he bids too high. Hence, he tries to bid just barely more than the next highest bidder, \(p_i = \text{min}(v_i, p_j + \epsilon)\). This is inconvenient because it requires knowing \(p_j\) which is private... Therefore equilibrium strategies in first price auctions are hard to reason about, because they require probabilistic modeling of others’ values.

Second price auctions. Consider what happens if the highest bidder does not pay his own bid \(p_i\), but the next highest, effectively the second-highest bid \(p_j\). What incentives does this change create? To get the item, bidder \(i\) needs \(p_i > p_j\). But he should not always try to get the item at any cost.

  • The only situation in which he has negative utility is when \(p_i > p_j > v_i\), i.e. he gets the item \(p_i > p_j\), but pays \(p_j > v_i\) more than its worth to him, ending up at a loss. From this we see that \(p_i\) should never be above \(v_i\).
  • Similarly, the only situation in which he loses out on positive utility is when \(v_i > p_j > p_i\). He doesn't get the item, \((p_j > p_i)\), but wants it more than what the other bidder is willing to pay, \(v_i > p_j\). From this we see that to avoid lost opportunities \(p_i\) should never be below \(v_i\).
  • Cases \(p_j > p_i > v_i\) and \(p_j > v_i > p_i\) don't matter because bidder \(i\) doesn't get the item and doesn't care enough to get it. His utility is zero.

As a result, we have \(p_i = v_i\). That is, the bidder should always bid exactly equal to his private valuation. If his valuation is the highest, he'll get the item, otherwise he won't, which is fair. Notice how this bidding strategy is particularly simple because it's independent of what the other players bid. In that sense, bidding \(p_i = v_i\) is a dominant strategy, because it's always the best.

Second price auctions are often called ideal because they have some desirable properties:

  • Truthful bidding, i.e. setting \(p_i = v_i\), is a dominant strategy for every bidder and if followed, every bidder is guaranteed to be at least as well-off as before (nonnegative utility). This is called dominant-strategy incentive compatible (DSIC). Assuming others bid truthfully, the best one can do is to also bid truthfully.
  • They are welfare-maximizing: they maximize the quantity \(\sum_{i=1}^n v_i x_i\) where \(x_i\) is the one-hot vector of who gets the item. They allocate the scarce item to that bidder who values it most.
  • They are computationally efficient, linear in the number of bits of \((v_1, ..., v_n)\).

Mechanism design. Beyond auctions, we can think of more general mechanisms for resource allocation. In that setting bidders are called agents and auctions are called mechanisms. A mechanism is simply an algorithm, a protocol for how scarce resources are allocated. If the bids of all agents are given by a vector \(\mathbf{b}\), the mechanism needs to specify an allocation rule \(\mathbf{x}(\mathbf{b})\) representing how much each agent gets, and a payment rule \(\mathbf{p}(\mathbf{b})\) establishing how much each agent pays. Different scenarios have different optimal combinations of \((\mathbf{x}, \mathbf{p})\).

How can we design mechanisms that are DSIC, welfare maximizing and efficient to implement? Broadly, we can follow two steps. First, assuming without justification that agents act truthfully, find an efficient allocation rule \(\mathbf{x}(\mathbf{b})\) that maximizes social welfare. Then, as a second step, find a pricing rule \(\mathbf{p}(\mathbf{b})\) that makes the mechanism DSIC. That last part ensures that under weak rational dynamics, bidders will converge to a strategy that always bids truthfully.

Myerson's lemma. When it comes to the first step for selecting \(\mathbf{x}(\mathbf{b})\), we're on our own. However, for the second step, we have a powerful result, called Myerson's lemma, to guide us. It works in single-parameter domains, where each bidder has one private parameter (here valuations \(v_i\)). The lemma says the following. If the allocation \(\mathbf{x}(\cdot)\) is monotone, i.e. the allocation of agent \(i\) can only increase in his bid \(b_i\), so that \(x_i(b_i, \mathbf{b}_{-i})\) is monotone increasing, then there is a unique pricing rule \(\mathbf{p}\) such that the mechanism \((\mathbf{x}, \mathbf{p})\) is DSIC. Likewise, if \((\mathbf{x}, \mathbf{p})\) is DSIC, then \(\mathbf{x}\) is monotone in each agent's bid, holding the others constant. Further, the pricing rule \(\mathbf{p}\) is given by

$$ p_i(b_i, \mathbf{b}_{-i}) = \int_0^{b_i} z \frac{d}{dz} x_i(z, \mathbf{b}_{-i})dz. $$

Here \(\mathbf{b}_{-i}\) are the bids of all other agents and \(x_i(z, \mathbf{b}_{-i})\) is the allocation to agent \(i\) if his bid is \(z\). Intuitively, truthfulness requires that you cannot gain by bidding different from \(v_i\). That holds if your payment depends only on the cutoff at which you "tip over" into winning, not on your actual declared bid above that cutoff.

Consider this intuitively, if only one bidder can get the item, and other bids are fixed to \(\mathbf{b}_{-i}\), then there's a threshold \(\tau_i\) such that if bidder \(i\) bids higher, he'll get the item, otherwise he won't. If \(b_i < \tau_i < v_i\), you'll miss out on the item. If \(b_i > \tau_i > v_i\), you'll get it but you'll pay more than it's worth to you. The best you can do is to set \(b_i = v_i\). The integral formula is the general continuous way of saying: "charge the threshold". It can be adapted to discrete settings.

Math. For more intuition let's derive informally the Myerson formula above. An untruthful agent can bid \(w\) while his valuation is \(v\). In that case his utility is \(g(v, w) = v x(w) - p(w)\) and here \(w\) is the variable and \(v\) acts like a parameter. The best utility the agent can get is \(u(v) = \max_w g(v, w)\) and its argmax is at some \(w^\ast\). Now, consider how this best utility changes as \(v\) changes.

$$ \frac{d}{dv}u(v) = \frac{\partial}{\partial v} \max_w g(v, w) = \left[ \frac{\partial}{\partial v} g(v, w) \right]_{w = w^*} = x(w^\ast). $$

Using the envelope theorem, we see that \(u'(v) = x(w^\ast)\). But under DSIC, the best bid is the truthful one, hence \(w^\ast = v\) and we get \(u'(v) = x(v)\). Integrating and assuming that \(v\) is lowerbounded by zero and \(x(0) = 0\) we see that \(u(v) = \int_0^v x(t)dt\). Next, under DSIC \(u(v) = v x(v) - p(v)\). We can solve for \(p(v)\) and integrate by parts, obtaining the desired formula:

$$ p(v) = v x(v) - \int_0^v x(t)dt \ \ \Rightarrow \ \ p(v) = \int_0^v t x'(t) dt. $$

This shows that if the mechanism is DSIC, the pricing rule has this form. Overall, the Myerson lemma pricing is very useful in practice. Consider the following examples.

Sponsored search auctions. Millions of auctions occur every day in sponsored search. Potential buyers search for items, as in Google or Amazon, while sellers bid on keywords for the possibility to show their own advertisements among the top results. A higher bid by the companies guarantees an impression near the top of the search results, which can translate to clicks (CTR = click-through rate) and eventually sales. If there are \(k\) ad slots, the allocation rule places the \(k\) highest bidders in them, which maximizes welfare. Note that in reality these platforms charge advertisers per click, with a pricing rule called generalized second price (GSP), different from the Myerson's lemma pricing. In GSP the bidder in slot \(i\) pays the next bidder’s bid times the CTR of slot \(i\). This is not DSIC but is much easier to implement. In contrast, the Myerson lemma's pricing rule dictates that bidder \(i\) should pay the minimum bid at which they would still win their slot.

Knapsack auctions. Now consider a more general setting, called a Knapsack auction. There is a shared resource with capacity \(W\), offered by the seller, and multiple bidders, each with a private valuation \(v_i\) and a public size \(w_i\), \(\forall i=1, ..., n\). For example, if the seller has a transport ship that can move \(W\) units, the bidders would bid so that their units are selected for transport. The possible allocations, denoted \(\mathcal{X}\), are the 0-1 vectors such that \(\sum_{i=1}^n w_i x_i \le W\).

Let's design an ideal Knapsack auction. Assuming that bidders are truthful we have that \(b_i = v_i\). First, we find the allocation rule \(\mathbf{x}(\mathbf{b})\) which, given \(\mathbf{b}\), is a Knapsack problem instance:

$$ \begin{aligned} &\mathbf{x}(\mathbf{b}) = \text{argmax}_\mathbf{\mathbf{x} \in \mathcal{X}} \sum_{i=1}^n b_i x_i,\\ &\text{such that } \sum_{i=1}^n w_i x_i \le W. \end{aligned} $$

Now, if \(i\) bids high enough, his items will eventually be included in the knapsack, so the allocation \(x_i(b_i, \mathbf{b}_{-i})\) is a step function in \(b_i\), zero beneath some critical bid, suppose \(z^\ast\), and one, after it. From Myerson's lemma above we can see that the price to pay is exactly \(z^\ast\), i.e. the minimum price that guarantees the inclusion of the \(i\)-th bidder's item. If we set the prices to these critical bids, then the dominant action of each player will be to bid truthfully.

Approximations. Very nice, but not ideal, because the welfare maximizing allocation is not easily computable. In fact, Knapsack is NP-complete. Additionally, finding the threshold \(z^\ast\) requires solving another Knapsack problem. Hence, in many cases one would need to resort to approximate, instead of exact, mechanisms for welfare maximization, which are polynomial in time. This brings mechanism design very close to the mature field of approximation algorithms, which also tries to find polynomial time algorithms that approximate the true answer as accurately as possible.

If we're using an approximation algorithm it may be the case that its allocation rule is not monotone, which would prevent DSIC. Therefore, for a given setting, one is interested in finding whether the best approximation is still monotone, or if it's not, how can it be extended for monotonicity with minimal decrease in the resulting welfare.

Revenue maximization. All these auction so far have been trying to maximize social welfare. Yet, a seller might be interested in maximizing revenue. Since each bidder has a private valuation of the item, the seller has to work with distributions over the possible valuations of the bidders. Thus, the question is how to design the allocation and payment rule so that the auction maximizes the expected revenue over the assumed private valuation distributions. There are ways to do this, by changing the allocation so it instead maximizes what's called virtual surplus, a quantity that depends on the valuation distributions. Here's a quick derivation.

Start with Myerson's formula \(p(v) = vx(v) - \int_0^v x(t)dt\) and assume, from the perspective of the seller, that \(v \sim F\). Here \(F\) is the cdf and \(f\) is the pdf. The expected revenue \(\mathbb{E}[p]\) is

$$ \begin{aligned} \mathbb{E}_{v \sim f}[p] &= \int_0^\infty v x(v) f(v)dv - \int_0^\infty \left(\int_0^v x(t)dt \right) f(v) dv \\ &= \int_0^\infty v x(v) f(v)dv - \int_0^\infty x(t) \left( \int_t^\infty f(v) dv \right) dt \ \ \ \leftarrow \text{ Fubini } \\ &= \int_0^\infty v x(v) f(v)dv - \int_0^\infty x(t) \big(1 - F(t)\big) dt \ \ \ \leftarrow \text{ cdf } \\ &= \int_0^\infty x(v) \Big(v f(v) - \big(1 - F(v)\big) \Big) dv \\ &= \int_0^\infty f(v) \underbrace{x(v) \left(v - \frac{1 - F(v)}{f(v)} \right)}_{\text{virtual surplus}} dv \\ \end{aligned} $$

Hence to maximize revenue simply change the allocation rule to maximize this quantity, instead of social welfare. Everything else remains the same.

Multi-parameter auctions. Mechanism design can get very complicated in multi-parameter settings - bidding environments where bidders have more than one private parameters that affect their decisions. If there's a finite set \(\Omega\) of outcomes, each agent could have a private valuation \(v_i(\omega)\) for each outcome \(\omega \in \Omega\). The social welfare of an outcome is defined as \(\sum_{i=1}^n v_i(\omega)\). Combinatorial auctions are an example here. They consist of \(M\) heterogeneous items and bidders bid on bundles (sets) of them. Obviously, different items in the bundle could be substitutes or complements to each other, which creates complicated and diverse valuations for each bundle.

An overwhelmingly positive result is that in every such general environment, there is a DSIC welfare-maximizing mechanism. This mechanism is called Vickrey–Clarke–Groves (VCG) and it's beautiful. For allocation, it selects the socially-optimal outcome. For pricing, each bidder is charged his externality - the welfare loss inflicted on the others by his presence.

$$ \begin{aligned} \mathbf{x}(\mathbf{b}) &= \text{argmax}_{\omega \in \Omega} \sum_{i=1}^n b_i(\omega)\\ p_i(\mathbf{b}) &= \underbrace{\left( \max_{\omega \in \Omega} \sum_{j \ne i} b_j(\omega) \right)}_{\text{without } i} - \underbrace{\sum_{j \ne i}b_j(w^\ast)}_{\text{with } i}, \ \ \text{ where } w^\ast = \mathbf{x}(\mathbf{b}) \end{aligned} $$

Setting the pricing in this way is DSIC. Every single-parameter VCG outcome satisfies Myerson’s characterization. But not every Myerson-implementable mechanism is VCG. VCG is always welfare maximizing, while Myerson's lemma could be applied to revenue maximization auctions.

Bilateral trade. An interesting property of VCG is that it's not always budget balanced. To see this, imagine two traders - a buyer with valuation \(v_B\), wishing to buy an item, and a seller with valuation \(v_S\), looking to sell it. For welfare maximization we need a trade to happen whenever \(v_B > v_S\). In that case the VCG payment of the buyer is \(p_B = (v_S - 0) = v_S\). If there's no buyer, the welfare of others is just \(v_S\). If there's a buyer and a trade, the welfare of others is \(0\). For the seller, if there's no seller, there's no item, so the welfare of the buyer is \(0\). If there's a seller and a trade, the buyer's welfare is \(v_B\). So the payment the seller should make is \(p_S = 0 - v_B = -v_B\), i.e. he should receive money. A trade happens when \(v_B > v_S\) and the buyer pays \(v_S\), but the seller needs to receive \(v_B\). Where does the extra \(v_B - v_S\) come from? It has to come from exogeneous subsidies outside of the mechanism.

Can we modify the VCG mechanism so that it's also budget balanced? In general no. A fundamental result is that it's not always possible to get DSIC, budget balanced, welfare maximizing mechanisms where none of the parties are ever hurt. Life is hard.

Payment constraints. Another interesting type of auctions is that where each bidder has a payment constraint and cannot afford to spend more than his budget allows. In particular, when bidders hit their budget constraints, truthful bidding is no longer a dominant strategy. This makes DSIC mechanisms difficult or impossible to implement without welfare loss. With multiple identical items, a uniform-price auction sells all of the items at a common price that equalizes supply and demand. It's budget balanced, but not DSIC. Alternatively, in cases where there's no money involved, just bidder preferences, the beautiful Top Trading Cycle algorithm reallocates objects owned by agents to make agents as well off as possible and leads to a DSIC mechanism.