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.

Â