0:23

So to begin, what is this revenue equivalence theorem?

Well, most importantly,

it's an answer to the question of which auction we should choose.

So far, we've seen all kinds of different auctions.

First-price auctions, second-price, English, Dutch.

It's kind of confusing, you wonder how you should actually,

as an auctioneer decide which auction you should use.

Well, strangely enough, the revenue equivalence theorem says

that to a large extent, it actually doesn't matter which one you pick.

So, let's see formally what it says.

Let's assume that we have n different risk-neutral agents.

Each of whom has an independent private evaluation for

the single good that's in auction.

And each of which is drawn from a cumulative distribution, F.

Now, we're going to consider two different auction mechanisms for these two similar

settings and we want to assume two things about these auction mechanisms.

First of all, that in equilibrium,

the allocate the good in the same way all of the time.

So for all of the different types that agents might actually have,

they have the same allegations.

1:55

So in other words, as long as true mechanisms allocate in the same way and

as long as they charge an agent with the lowest possible evaluation the same amount

to zero, then the rest of their payment functions have to be the same as well.

So, you can't get extra money out of agents without changing

the allocation function or the payment of the lowest valued agent.

Now in fact, I've stated the revenue equivalence theorem here in a way that's

a bit narrower than I have to just to make it a bit easier to say to you.

So in fact, I can get beyond the independent private values assumption that

I've made and I can also get a bit beyond the single good assumption.

So stating it in its full generality would have been just a little bit more

notationally clumsy,

although the proof that I'll give you actually holds more generally.

2:53

To do this,

we need to think about a concept called the kth order statistic of a distribution.

So, the kth order statistic

is the expected value of the kth largest of n draws.

So, imagine that I was to independently draw five times from a distribution.

What is the expected value of the biggest of those draws?

Or what is the expected value of the second biggest of those draws?

Those are questions about the first order and second order statistics of that

distribution for k equals 1 and 2 and for n equals 5.

4:04

Now using this fact directly, I can conclude that in a second-price

auction the seller's expected revenue is this fraction.

And that's because I know that in a second-price auction,

the seller's expected revenue is the same as the expected value of the second

highest bidder, because the seller always gets the revenue of the second

highest bid in a second-price auction.

So if I just substitute in, this is the expression that I get and

you can confirm that.

Now first and second-price auctions,

both satisfy the requirements of the revenue equivalence theorem.

It's easy to see for second-price auctions.

For first-price auctions, it's not as easy to see that they allocate goods in

the same way as a second price auction does.

But basically, what I want to reason is that in a first-price auction,

the bidder with the highest value gets the good.

And I can argue this essentially by saying,

every symmetric game has a symmetric equilibrium.

The first-price auction game is a symmetric game, because everyone is IID.

So in a symmetric equilibrium of this game,

a higher evaluation is going to happen if and only if a bidder has a higher bid and

that's going to mean that the person with the highest evaluation wins the auction.

5:25

So then I conclude that a bidder in a first-price auction is going to

have to pay on expectation the same amount,

as the same bidder would pay on expectation in a second-price auction.

And because only the winner has to pay anything in a first-price auction,

that means everyone should bid their expected payment conditional on

being the winner of a second-price auction.

So each bidder in a first-price auction should imagine that they're

the highest bidder and then bid the expected second highest bid,

conditional on their value being the highest sample from the distribution.

And you might think this is kind of strange, because of all of the n bidders,

n-1 would be wrong when they did this conditioning.

Only one of them will be the highest bidders.

So why should they all bid as though, they think they're the highest bidder?

Well, the reason this makes sense is that the only bidder that this matters to is

the bidder with the highest valuation.

And so if the bidder turns out, in fact,

to win the first-price auction, then he was right to do this conditioning.

And otherwise, his bid doesn't matter anyway and so

the fact that he conditioned wrong is okay.

So thinking now that the highest bidder if his valuation Vi is the high value,

then there are n-1 other values, which are below his.

And so, all he knows is that there are drawn

from the uniform distribution on the interval between zero and his bid.

I'm thinking about the first transaction in case of uniform distribution and

that's the expected value of the second highest bid is going to be the first

order statistic of n-1 draws from this distribution.

We're thinking about the second highest bid, but

we've conditioned on the first highest bid.

So, we're now going to think about the biggest of the draws among

the remaining agents.

That's going to be the second highest bid.

And I can just substitute in to this expression for

the first order statistic of n- 1 draws and

I can substitute in n-1 into that expression, and

simplify, and what I get is this expression here.

And that's something you've seen before.

We've claimed in the past that the symmetric equilibrium of

a first-price auction with the independent uniform valuations is for

all of the bidders to bid n-1 over n times their valuation.

And now, you can see actually where that comes from.

That we can actually find that by reasoning through revenue equivalent.

So, essentially there's two ways of finding the equilibrium of an auction like

a first-price auction.

The hard way is that you do a ton of calculus to actually figure out

what the equilibrium is from first principles.

That's really hard, even in the case of a first-price auction, that's really hard.

The easy way is that you guess the equalibriam by

appealing to revenue equrivalent and then you just varify that it's an equalibriam.

And so we know from revenue equrivalence by comparing second price auctions that

are easy to analyze that the expected revenue has to be the same.

And then we work through to figure out how bidders would have to bid to get that

expected revenue and we arrive at this expression.

8:48

This is going to be the most technical and advanced part of the video.

If you find that you bog down and this is too much for

you, you understand everything else you need to know about revenue equivalence

without watching the proof.

So you can stop watching the video now.

But I encourage you to go on because I think this is a really cool

proof actually.

I actually worked really hard to make this part of the video for

you because I really liked this proof.

So I hope you enjoy it too.

So let's see how it works.

We have to introduce the idea of an x interim allocation function and

an x interim payment.

So let's see what that means.

Well, I'm going to call, remember we have this choice function x.

But I'm now going to have the choice function xi and what I'm going to mean by

that is the choice function from the point of view from agent i given

that everybody else is following the equilibrium strategy

profile s for some Bayes-Nash equilibrium and that agent i has type vi.

So what this xi is going to gives us is the probability

that an agent i with type vi is going to be allocated to good.

Given that everybody follows the equilibrium strategy s including i.

10:19

So here's a stronger theorem than the revenue equivalence theorem, but

it should be easy to see that this implies the revenue equivalence theorem directly.

So once we have this theorem,

we just basically get the revenue equivalence theorem for free.

What the revenue equivalence theorem tell us, is that mechanisms that

allocate in the same way, all have to have the same payment function.

What this tells us is exactly what the payment function has to be.

A little bit about how the allocation has to work as well.

It really shows us exactly what the equilibrium even needs to be.

And so as a side effect we'll see that

any two mechanisms that allocate in the same way have to have the same payments.

But let's look at what this theorem says.

This is really a kind of crucial theorem for mechanism design.

11:21

First of all we need monotonicity.

So each agent's ex interim allocation probability

needs to be monotone non decreasing in that agent's value.

So in other words as agents have higher and higher values for

the good, their probability of getting the good averaged across all of the other

agents type, as well as potentially across randomness in the mechanism itself,

needs to weekly increase.

So as I have higher and higher values for

the good, it can never reduce my chance, on average, of getting the good.

11:56

So that's necessary for a Bayes-Nash equilibrium.

The other thing that's necessary for a Bayes-Nash equilibrium is the following

payment identity and this probably looks like of scary.

It's just a whole lot of math, right.

So I'm saying the payment function, this x interim expected payment,

that an agent makes, needs to look like this.

It needs to be the agent's value for the good, multiplied by the probability that

they get the good, minus this integral.

The integral from zero to vi, of this ex interim allocation probability.

Plus the payment, the expected payment that an agent have type zero gets.

13:02

The final part of the proof that

is also really interesting is this last statement here.

So it says if s is onto, then the converse holds.

What does that mean?

Well here we've said that a strategy profile s is in Bayes-Nash equilibrium

only if these two conditions hold.

Here we're saying if we add the requirement that s is onto,

which I'll explain in a second, then it's also sufficient,

then these two conditions imply Bayes-Nash equilibrium.

[NOISE] So what does it mean for s to be onto?

It means there's some type you could have that would lead you to make any given bid.

So I can always simulate any action that I want to

take in the game by pretending to have a certain valuation.

So that means that I can get to any action in the game by having a valuation.

Formally we say the strategy profile is onto, that's all that means.

14:20

So this proof has three different parts.

I'm going to start with the last then.

I'm going to say that the strategy profile is a Bayes-Nash equilibrium

if the monotonicity and the payment identity properties hold.

And furthermore, assess onto.

So I'm going to show that those things suffice to give us a Bayes-Nash

equilibrium.

Then, I'm going to show that those two things are necessary.

That s is a Bayes-Nash equilibrium only when monotonicity holds, and

that s is a Bayes-Nash equilibrium only when the payment identity holds.

15:18

Okay, so moving on to this first part where I'm going to show

that the characterization and the assumption that s is

onto implies that s is a Bayes-Nash equilibrium.

So to begin, if agent i deviates from taking action from the strategy profile

s and instead takes the action that the strategy profile s would have him take,

if his type was not vi, but instead with some other type vi had,

then what would agent i's utility be?

Well, we can write an expression here, so

I'm going to first of all introduce some notation.

I'm going to say, I'm going to use this notation

U sub i comma vi to mean the utility of an agent,

i, whose real type is vi.

17:53

So, what does it mean then for a strategy profile, S,

to be in Bayes-Nash equilibrium?

Well, it means that agent i is best responding by reporting

his true type to his own strategy profile, rather than kind of lying to himself.

Sort of like we saw in the revelation principle.

So, in other words, his expected utility for actually using

his true type has to be at least as big as his expected utility for

lying to himself and reporting a different type to the strategy profile.

If that's true for all agents, and for all values that the agent might have and

all lies that he might tell, then we have a Bayes-Nash equilibrium.

18:41

Okay, well now is the fun part.

It turns out we can prove this almost entirely using pictures.

So let's start by considering some arbitrary and monotonic allocation rule.

I'm assuming it's monotonic because recall

the assumption of our proof is that the characterization holds.

And half of the characterization is that the allocation rule is monotonic.

So let's think about what this picture says.

Here in the x-axis, I have the valuation that an agent might have.

So this is the lowest possible valuation and

this is infinitely big valuation as we go far enough out.

19:24

So if the agent reports the lowest possible valuation,

then he doesn't win the good.

And because this rule is monotonic, as he reports higher and

higher valuations, he has an increasing chance of getting the good.

It can flatten out and stay level, it can go up, it go up gradually,

it can go up discontinuously.

And if it ever his 1, it has to stay at one because its monotonic.

And so, of course it doesn't have to ever hit 1, it could just gradually ramp up.

But if it ever hits 1, as I've drawn it here, then for

all values beyond that point, it has to stay at 1.

So I'm not going to make any assumptions about what this function looks like except

that it's monotonic.

20:08

Okay, so now let's think about first of all agent i's value for

consuming the good.

Just what I talked about before.

Remember that his utility has two parts.

His value for consuming the good and the payment that he has to make.

So first of all, let's think about his value.

Well, as I argued before, this is his value for telling the truth, for

playing truthfully where he reports his own true value to the strategy profile,

and this is his value for consuming the good when he has kind of lied to

himself and so he gets a different allocation probability.

So let's think about what those things look like on the picture.

Well, notice that these expressions are products.

It's a value multiplied by an allocation probability.

So we can see that kind of in the picture as a rectangle,

where it's the area of this shape.

Here's the valuation, right?

This distance here the valuation that goes from 0 to Vi.

22:38

Okay, so what we've seen so far is,

we've kind of learned how to look at these pictures.

And we've seen that the area of these two rectangles is the expected

utility that the agent gets for consuming the good.

His true value, in both cases Vi multiplied by the allocation probability,

which depends on whether he's reporting his true type or

reporting some lower type V hat i.

Okay, so that was consuming the good.

Now let's think about the payment that he has to make to the mechanism.

Well again, we're assuming that this characterization holds, and

that means that we're assuming that this payment identity is true.

And remember the payment identity had a p0 in here, but

we don't have to worry about the p0 because we've assumed that it's 0.

25:18

Minus the payment identity,

which as we saw before is the part of the rectangle that lives above the line.

And so, this difference then is the area that lies below the line.

So, that's the amount of utility that the agent would get and

you can see that these two pictures are pretty similar.

They're both this area under the curve.

They both go up to vi, but the difference is that this one kind of gets clipped off

at this lower allocation probability here.

Which would kind of correspond to about here, whereas this one goes a bit higher.

26:13

And what's important, the thing that we have done all of this in order

to reason to ourselves is that this is a positive number and

the fact that it is an actual area in our graph that then it has positive

area goes to show that it's a positive number.

And because of monotonicity, really the result that made this is true is

that this point here has to be weakly lower than this point here.

It would have been possible for the function to be flat here in that region.

And if it was, then this number would be zero rather than being positive, but

it can never be negative.

The only way that it could be negative would be if the function went down and

the function's not allowed to go down by monotonicity.

And so, that tells us that this utility

difference is always going to be nonnegative.

And remember, we argued before.

But as long as this number is greater than or equal to this number,

then s is a Bayes Nash Equilibrium.

And so, what we've just argued is that indeed that's true.

So, the characterization plus our assumption that s is onto

allows us to reason that s is a Bayes Nash Equilibrium.

So, that's a really powerful thing.

We've just seen something very structural of what the Bayes Nash Equilibrium of

a quazilinear mechanism has to look like.

27:49

So again, I'm going to make the same kind of argument that I made before.

That having a Bayes Nash Equilibrium implies that for all valuations that

the agents could have and all other equations that the could pretend to have.

The utility that agent i gets on expectation from

really having evaluation vi.

And playing as though, he has evaluation vi is at least as big as

the utility that he gets from really having evaluation vi and

playing like he has evaluation vi prime.

If I expand this out, I get this expression here.

Here all that I've done is just substituted in this expression that we

already looked at in the previous part of the proof that says that my utility is

the amount that I get from consuming the good minus the payment that I have to make

in both cases, depending on the report that I really made.

28:44

So you may have noticed that I switched from using v hat to v prime and

that's because I want to actually think that it can be possible for

the agent really to have valuation vi or

really to have valuation vi prime, and I can use these facts both ways.

So, I'm going to consider two possible values.

Zed one and zed two, that the agent really could have.

And I'm going to substitute into this expression here, kind of both ways.

I'm going to substitute in vi = zed 1, vi prime = zed 2 and

I'm also going to substitute in the other way around.

And depending on which way I substitute, I get two different inequalities.

So if I do the first substitution here, then I get this inequality.

Which says, well, it says, what you read.

There's no point in my reading it out, but

it gives an expression that has zed 2 here and zed 1 here, for example.

When I do things the other way around, everything switches.

So, I get zed 1's and zed 2's in the other way.

In both times, I have the inequality pointing this way,

because that's what we started out with.

So basically, what this is saying is an agent of type zed 1

wouldn't want to lie and pretend to have type zed 2.

And similarly, an agent of type zed 2 wouldn't want to lie and

pretend to have type zed 1 either.

Well, I've got these two different inequalities here.

So, I can just add them together.

And if I do that, then that causes these p terms to cancel out.

And so, then I just get these two things added together.

30:46

And you can verify that for yourself,

that's just some simple algebraic manipulation.

And really, the monotonicity requirement just pops

directly out of this expression here.

So in particular, you can see that if zed 2 is bigger than zed 1.

Meaning that this term here is positive, then in order for

this inequality to be true, in order for this whole thing to be nonnegative,

we have to make sure that this is also not negative.

So, we can conclude that this being positive implies

that this has to be positive.

32:12

What I want to say here is that, the strategy profile

a Bayesian Nash equilibrium, implies that we need the payment identity.

The payment identity didn't just kind of suffice to give us a Bayesian Nash

equilibrium, but we actually need to have it.

So I'm going to start with those same two inequalities that

we just talked about before, and now I'm going to do something different.

I'm going to solve each of them for this expression.

So I'm going to kind of rearrange them.

You notice they both have a A pi z2 given s and a pi z1 given s.

35:33

Basically, it needs to touch the curve everywhere, because if I change z1 and

z2, I still need to have the property that it's never less.

So, it's never more than that amount, and it's never less than that amount.

And so as I kind of move around, I need to make sure that I always have those sort of

points of contact with the curve.

And the only way for

that to work everywhere, is to have contact with the curve everywhere.

So kind of on an intuitive level, that should be human thing to you.

And if you'd like to see the proof with calculus,

you can look at the book citation that I gave you at the beginning.

36:32

Okay, so that concludes our proof of the Bayesian-Nash equilibrium

characterization result.

And recall that, that directly gives us the revenue equivalence theorem as

a corollary Because what the revenue equivalence theorem said is that

having the same allocation probability and also having the same payment for

an agent with the lowest possible type implies having the same expected payments.

What this characterization result said is Is something much stronger that having

the same allocation probability implies exactly the payment identity that you saw.

And the payment identity has determined and for

what the lowest possible type gets.

And so that is at constant and both cases then they have to be the same.

So the overall claim that we want to make here,

the overall takeaway from all of this, is that if two mechanisms have the same

allocation rule, then they basically have the same payment rule too.

And when I say basically, essentially all I really mean is that

the only thing that can change is if I just offset everything by a constant.

So, if I pay you $100 for showing up in my auction, and

then we have an auction, then my expected revenue is different.

If I charge you $100 for walking in the door and

you have no choice about whether to walk in the door, and then we have an auction,

I'll get a different amount of revenue.

But that's not very satisfying.

That's why we have this requirement about the agent with the lowest possible type,

gets paid zero.

As long as that's true, then there's really no other in the payment rule and so

mechanisms with the same allocation rule just need to have the same payment rule.

38:12

A key corollary is that all efficient auctions yield the same revenue in

equilibrium because after all, efficiency is just one allocation rule, right?

Efficiency means the agent with the highest evaluation always gets the good.

That's an example of what the restriction of what the allocation rule needs to be.

So that tells us that most of the auctions we care about are efficient.

So for all of these efficient auctions, we know that there's actually nothing we can

do to change the amount of revenue to get in equilibrium.

By changing the allocation by within efficient auctions, and

indeed, this applies not just to the auctions we've seen before, but

to some pretty weird auctions.

So you can think about not a first or second price auction, but

a third price auction, that actually turns out to be revenue equivalent.

You can think about various auction designs in which not only

the winners have to pay, but losers pay too.

We didn't make any assumptions about these kinds of things in the proof, and so

it turns out they are also revenue equivalent.

And one last caveat, risk neutrality did turn out to be important.

So I have assumed everywhere in this video, that agents are risk neutral,

which means they treat expected payments the same as sure-thing payments.

They don't care about how much randomness there is in the environment.

They just care about the expected payment they have to make.

And if that isn't true,

then these different auction mechanisms actually do turn out to be different.

So that concludes this lecture.

And you'll go on now,

in the next lecture to think about how to actually maximize revenue in an auction.

And what we can see from today, is that's going to have to happen by changing

the allocation rule there is not way of maximizing within efficiency,

because efficient auctions are all going to yield the same revenue.

So if what you want to do, is to maximize your revenue,

strangely enough you're going to turn out not to want to sell to the person

with highest valuation all the time.