Happy Pi Day! I have an economics midterm on Wednesday, so here is my attempt at studying.

## 1. Mechanisms

The idea is as follows.

- We have people and a seller who wants to auction off a power drill.
- The th person has a private value of at most on the power drill. We denote it by .
- However, everyone knows the are distributed according to some measure supported on . (let’s say a Radon measure, but I don’t especially care). Tacitly we assume .

**Definition 1**

Consider a game played as follows:

- Each player makes a
**bid**(which depends on how much they value the object) - Based on all the bids , each player has a chance of actually obtaining the object. We call the
**allocation**function and require . - Based on all the bids , each player makes a payment . We call the the
**payment**function. Note that one might have to pay even if they don’t get the drill! - The utility of the th player is
i.e. the expected chance they get the power drill minus the amount which they pay.

We call the pair a **mechanism**.

For experts: we require that each and is measurable. Right now this is not a very good definition, because there are no assumptions on what and look like. Nonetheless, we’ll give some examples.

## 2. Examples of mechanisms

In the auction that you’d see in real life, we usually set

which is the simple rule that the highest bidder gets the power drill with probability ; if there is a tie, we pick one of the highest bidders at random.

In all the examples that follow, for simplicity let’s take the case , and call the two players Anna and Elsa. We assume that both Anna and Elsa the value they place on the drill is *uniform* between . Finally, we give the auctioneer a name, say Hans.

### 2.1. First-price auction

The **first-price auction** is the one you’ve probably heard of: each player makes a bid and

- , and
- is defined by requiring the winner to pay their bid.

How do Anna and Elsa behave in this auction? Clearly no one will bid *more* than they think the drill is worth, because then they stand to lose utility if they happen to win the auction. But the truth is they actually will bid less than they think the drill is worth.

For concreteness, suppose Anna values the drill at . It doesn’t make sense for Anna to bid more than obviously. But perhaps she should bid — save a dollar. After all, what’s the chance that Elsa would bid right between and ? For that matter, Anna knows that Elsa has a chance of valuing the drill at less than . So if Anna bids , she has at least a of saving at least ; it makes no sense for her to bid her true value.

It gets better. Anna knows that Elsa isn’t stupid, and isn’t going to bid even if her true value is . That is, Elsa is going to try and sell Hans short as well. Given this Anna can play the game of cheating Hans more aggressively, and so an ad infinitum.

Of course there’s a way to capture this idea of “I know that you know that I know that you know. . .”: we just compute the Nash equilibrium.

**Proposition 2** **(Nash eqilibirum of the first-price auction for )**

Consider a first-price auction where Anna and Elsa have values uniformly distributed in . Suppose both Anna and Elsa bid if they have value . Then this is a Nash equilibrium.

*Proof:* Suppose Anna values the drill at and wants to make a bid . Elsa values the drill at , and follows the equilibrium by bidding . For a bid of , Anna gets utility

The probability of winning with is thus (this the probability that ) so the expected utility is

Hence we see maximizes Anna’s expected utility.

The first-price auction is interesting because both players “lie” when bidding in the Nash equilibrium. For this reason we say that the first-price auction is not **incentive compatible**.

Just for interest, let’s compute how much money Hans is going to make off the drill in this equilibrium. The amount paid to him is equal to

To see this we had to use the fact that if two numbers in are chosen at random, the expected value of the larger is . Multiplying by gives the answer: Hans expects to make .

### 2.2. Second-price auction

The **second-price auction** is the other one you’ve probably heard of: each player makes a bid and

- , and
- is defined by requiring the winner to pay the
**smallest amount needed to win**, i.e. the second highest bid.

The fundamental difference is that in a second-price auction, a player “doesn’t need to be shy”: if they place a large bid, they don’t have to worry about possibly paying it.

Another way to think about is as a first-price auction with the property that the winning player can *retroactively* change their bid, provided they still win the auction. So unlike before there is no advantage to being honest.

Indeed, the second-price auction is incentive compatible in a very strong sense: bidding your true value is the best thing to do *regardless* of whether your opponents are playing optimally.

**Proposition 3** **(Second-price auctions are incentive compatible)**

In a second-price auction, bidding truthfully is a weakly dominant strategy.

*Proof:* Easy. Check it.

Just for interest, let’s compute how much money Hans is going to make off the drill in this equilibrium. This time he amount paid to him is equal to

Here we had to use the fact that if two numbers in are chosen at random, the expected value of the smaller is . This might come as a surprise: the expected revenue is in this auction too.

### 2.3. All-pay auction

The **all-pay auction** is like lobbying. Each player makes a bid, and

- , and
- is defined by requiring
*everyone*to pay their bid, regardless of whether they win the power drill or not.

This is *clearly* not incentive compatible. In fact, the Nash equilibrium is as follows:

**Proposition 4** **(Nash equilibirum of the all-pay auction)**

Consider a first-price auction where Anna and Elsa have values uniformly distributed in . Suppose both Anna and Elsa bid if they have value . Then this is a Nash equilibrium.

*Proof:* Omitted, but a fun and not-hard exercise if you like integrals. It will follow from a later result.

Just for interest, let’s compute how much money Hans is going to make off the drill in this equilibrium. This time he amount paid to him is equal to

Surprise — same value again! This is a very special case of the Revenue Equivalence Theorem later.

### 2.4. Extortion

We’ve seen three examples that all magically gave as the expected gain. So here’s a silly counterexample to show that not every auction is going to give as an expected gain. It blatantly abuses the fact that we’ve placed almost no assumptions on and :

- , or any other for that matter, and
- is defined by requiring both Anna and Elsa to give to Hans.

This isn’t very much an auction at all: more like Hans just extracting money from Anna and Elsa. Hans is very happy with this arrangement, Anna and Elsa not so much. So we want an assumption on our auctions to prevent this silly example:

**Definition 5**

A mechanism is **voluntary** (or individually rational) if for every .

### 2.5. Second-price auction with reserve

Here is a less stupid example of how Hans can make more money. The **second-price auction with reserve** is the same as the second-price auction, except Hans himself also places a bid of . Thus if no one bids more than , the item is not sold.

For the same reason as in the usual second-price auction, bidding truthfully is optimal for each players. The cases are:

- If both Anna and Elsa bid less than , no one gains anything.
- If both Anna and Elsa bids more than , the higher bidder wins and pays the lower bid.
- If exactly one player bids more than , that player wins and pays the bid for .

So Hans suffers some loss in the first case, but earns some extra money in the last case (when compared to the traditional second-price auction.) It turns out that if you do the computation, then Hans gets an expected profit of

meaning he earns another or so by setting a reserve price.

## 3. Direct mechanisms

As it stands, might depend in complicated ways on the actual values : for example in the first-price auction. We can capture this formalism as follows.

**Definition 6**

A **direct mechanism** is a pair where

- is a mechanism,
- is a Nash equilibrium of bidding strategies for the bidders. So in this equilibrium the th player will bid .

If , meaning for every , then we say is **incentive compatible**.

So in other words, I’m equipping the mechanism with a particular Nash equilibrium . This is not standard, but I think it is harder to state the theorems in a non-confusing form otherwise.

**Definition 7**

Let be a direct mechanism. Then we define , , by

For example, is the expected utility of the 1st player *conditioned* on them having value for the power drill:

Similarly, let

Note that , , depend not only on the mechanism itself but also on the attached equilibrium .

It’s important to realize the functions , , carry much more information than just , , . All three functions depend on the equilibrium strategy , which in turn depend on both and . Moreover, all three functions also depend on . Hence for example actually depends indirectly on as well, because the choice of affects the resulting equilibrium .

**Example 8** **(Example of , , )**

Let’s take the first-price auction with two players Anna and Elsa. If we call it then as we described before we have:

- ,
- and are uniform distributions over ,
- is defined by having player pay their bid upon winning.

Moreover, the Nash equilibrium is given by

for all , as we saw earlier. Consequently, we have

- since the probability of winning (and hence winning the bid) is proportional to the value placed on the item (since is a uniform distribution).
- as the expected payment: there’s a chance of winning, and a payment of if you do.

## 4. Equivalence of utility and payment

In what follows let be any index.

We now prove that

**Lemma 9** **(Envelope theorem)**

Assume is a direct mechanism. Then is convex, and

except for at most countably many points at which is not differentiable.

*Proof:* Since is an equilibrium, we have

i.e. there is no benefit in lying and bidding rather than .

First, let’s show that if is differentiable, then . We have that

Similarly

This implies the limit, if it exists, must be . We’ll omit the proof that is differentiable almost everywhere, remarking that it follows from being nondecreasing in (proved later).

**Theorem 10** **(Utility equivalence)**

Let be a direct mechanism. For any ,

*Proof:* Fundamental theorem of calculus.

**Theorem 11** **(Payment equivalence)**

Let be a direct mechanism. For any ,

Thus is determined by up to a constant shift.

*Proof:* Use and .

This means that both functions and are completely determined, up to a constant shift, by the expected *allocation* in the equilibrium .

## 5. Revenue equivalence

A corollary:

**Corollary 12** **(Revenue equivalence)**

Let be a mechanism. Then the expected revenue of the auctioneer, namely,

depends only on and .

Very often, textbooks will add the additional requirement that or , in which case the statements become slightly simpler, as the constant shifts go away.

Here are the two important corollaries, which as far as I can tell are never both stated.

**Corollary 13** **(Revenue equivalence for incentive compatible mechanisms)**

If is incentive compatible, then and (and hence the seller’s revenue) depends only on the allocation function and distributions , up to a constant shift.

*Proof:* In an incentive compatible situation where we have

so depends only on and up to a constant shift. Ditto for any other .

**Corollary 14** **(Revenue equivalence for auctions)**

Suppose is a mechanism in which

- The allocation function is ,
- The is strictly increasing in for all (players with higher values bid more).

Then and are determined up to constant shifts by .

*Proof:* By the assumption on we have

so it follows for example that

Once again now depends only on .

As an application, we can actually use the revenue equivalence theorem to compute the equilibrium strategies of the first-price, second-price, and all-pay auctions with players.

**Corollary 15** **(Nash equilibria of common auctions)**

Suppose a player has value as in our setup, and that the prior is distributed uniformly. Each of the following is a Nash equilibrium:

- In a first-price auction, bid .
- In a second-price auction, bid (i.e. bid truthfully).
- In an all-pay auction, bid .

*Proof:* First, as we saw already the second-price auction has an equilibrium where everyone bids truthfully. In this case, the probability of winning is and the expected payment when winning is (this is the expected value of the largest of numbers in .) Now by revenue equivalence, we have

Now we examine the all-pay and first-price auction.

- We have , i.e. in the equilibrium strategy for the all-pay auction, a player with type pays on average . But the payment in an all-pay auction is always the bid! Hence conclusion.
- We have , and since in both cases the chance of paying at all is , the payment if a player does win is ; hence the equilibrium strategy is to bid .

## 6. Design feasibility

By now we have seen that all our mechanisms really depend mostly on the functions , (from which we can then compute and ) while we have almost completely ignored the parameters , , which give rise to the mechanism in the first place.

We would like to continue doing this, and therefore, we want a way to reverse the work earlier: given the functions construct a mechanism with those particular expected allocations. The construction need not even be explicit; we will be content just knowing such a mechanisms exists.

Thus, the critical question is: which functions can actually arise? The answer is that the only real constraint is that are nondecreasing.

**Theorem 16** **(Feasability rule)**

Consider players with a fixed a distribution of private values. Consider any measurable functions .

Then there exists a direct mechanism with as the expected allocations if and only if

- each function is nondecreasing.
- with probability .

*Proof:* First, we show that any arising from a direct mechanism are nondecreasing. Indeed, if then we have the inequalities

If we add these inequalities we recover , which shows that is nondecreasing. The second condition just reflects that .

Conversely, suppose are given nondecreasing function. We will construct an incentive compatible mechanism inducing them. First, define as predicted by Revenue Equivalence. First, define by

- , and
- . (Note .)

Then trivially and .

However, we haven’t specified a yet! This is the hard part, but the crucial claim is that we can pick : that is, is an incentive compatible direct mechanism.

Thus we need to check that for all and that

We just do since the other case is analogous; then the inequality we want to prove rearranges as

Since is increasing, this is immediate.

In particular, we can now state:

**Corollary 17** **(Individually Rational)**

A direct mechanism is voluntary if and only if

for every .

*Proof:* Since , the function is nonnegative everywhere if and only if .

## 7. Optimal auction

Since we’re talking about optimal auctions, we now restrict our attention to auctions in which for every (hence the auction is voluntary).

Now, we want to find the amount of money we expect to extract for player . Let’s compute the expected revenue given a function and distribution . Of course, we know that

but we also know by revenue equivalence that we want to instead use the function , rather than the function . So let’s instead use our theorem for the integral to compute it:

Applying the definition of expected value and switching the order of summation,

Thus, we define for the player their **virtual valuation** to be the thing that we just obtained in this computation:

The virtual valuation can be thought of as **the expected value of the amount of money we extract** if we give the object to player when she has type . Note it has the very important property of **not depending on **.

Now, let’s observe that

Now, our goal is to select the function to maximize this. Consider a particular point . Then we’re trying to pick , , \dots, to maximize the value of

subject to . The ‘s here depend only on the distribution . This is thus a convex optimization problem, so the solution is obvious: **put all the weight on the biggest positive **, breaking ties arbitrarily. In other words, if and , then set and all the other coefficients to be zero. (Ties broken arbitrarily as usual.) To be explicit, we set

So we should think of this as a second-price auction with discriminatory reserve prices. Moreover, the “second-price” payment is done based on , so rather than “pay second highest bid” we instead have “pay smallest amount needed to win”, i.e. the smallest such that for all .

Unfortunately, since the are arbitrary the resulting might be strange enough that the game fails to have a reasonable strategy ; in other words we’re worried the maximum might not be achievable. The easiest thing to do is write down a condition to handle this:

**Definition 18**

We say is **regular** if the virtual valuations are strictly increasing for all .

**Theorem 19** **(Regularity implies optimal auction is achievable)**

Assume regularity of . Consider a **second-price auction with discriminatory reserve prices**: the reserve price for player is the smallest such that , and the winner pays the smallest amount needed to win.

This is an incentive compatible mechanism which maximizes the expected revenue of the auctioneer.

*Proof:* The described in the theorem is the one we mentioned earlier. The hypothesis defines as follows:

- If is maximal, then that player wins and pays the smallest amount such that still exceeds all other .
- Otherwise, the item is not sold.

The fact that this mechanism is incentive compatible is more or less the same as before (bidding truthfully is a weakly dominant strategy). Moreover we already argued above that this allocation maximizes revenue.

You can and should think of this as a “reserve price second price auction” except with virtual valuations instead. The winner is the player with the highest virtual valuation, who is then allowed to retroactively change their bid so long as they still win.

To see this in action:

**Corollary 20** **(Optimal symmetric uniform auction)**

Consider an auction in which players have uniform values in . Then the optimal auction is a second-price auction with reserve price . The expected earning of the auctioneer is

*Proof:* We compute each as

Hence, we usually want to award the item to the player with the largest virtual valuation (i.e. the highest bidder), setting the reserve price at for everyone since . By (1) the expected payment from a player equals

Simplifying and multiplying by gives the answer.

More generally, in an asymmetric situation the optimal reserve prices are discriminatory and vary from player to player. As a nice exercise to get used to this:

**Exercise 21**

Find the optimal auction mechanism if two players are bidding, with one player having value distributed uniformly in and the other player having value distributed uniformly in .

## 8. Against revelation

Here’s a pedagogical point: almost all sources state early on the so-called “revelation principle”.

**Proposition 22** **(Revelation principle)**

Let be a direct mechanism. Then there exists a incentive compatible mechanism such that

- is incentive compatible, and
- For any , , , , i.e. at the equilibrium point, the expected payoffs and allocations don’t change.

*Proof:* Consider . Then is played as follows:

- Each player has an advisor to whom it tells their value
- The advisor and figures out the optimal bid in , and submits this bid on the player’s behalf.
- The game is played with the advisor’s bids, and the payments / allocations are given to corresponding players.

Clearly the player should be truthful to their advisor.

Most sources go on to say that this makes their life easier, because now they can instead say “it suffices to study incentive compatible mechanisms”. For example, one can use this to

- Replace “direct mechanism” with “incentive-compatible direct mechanism”.
- Replace “there exists a direct mechanism ” with “there exists a which is incentive compatible”.

However, I personally think this is awful. Here is why.

The proof of Revelation is almost tautological. Philosophically, it says that you should define the functions , , *in terms of* the equilibrium . Authors which restrict to incentive compatible mechanisms are hiding this fact behind Revelation: now to the reader it’s no longer clear whether should be interpreted as taking a bid or value as input.

Put another way, *the concept of a bid/value should be kept segregated*. That’s why I use only for values, only for bids, and build in the equilibrium as into , , ; So is the expected utility of bidding in the equilibrium. Revelation does the exact opposite: it lets authors promiscuously mix the concepts of values and bids, and pushes out of the picture altogether.

Hi! You seem to be able to think when you write in LaTeX. Do you have a visual program that helps you with that (WYGIWYS) or has it come from years of experience?

LikeLike

I don’t use WYSIWYG, have gotten used to working with LaTeX source by now. My editor is Vim.

LikeLike